本文共 2045 字,大约阅读时间需要 6 分钟。
标签(空格分隔): 操作系统 互斥
软件方法的实现方式能够解决并发进程在一个或者多个共享内存的处理器上执行的问题。这些方法通常是基于在访问内存是基本互斥条件的假设。即,尽管访问的顺序没有具体安排,同时访问内存中的同一个地址的操作被内存仲裁串行化(没有丢失)。此外,没有考虑硬件、操作系统或是编程语言的支持(相对通用)。
boolean flag[2]; //这里用两个进程举例,有两个flagint turn;void P0(){ while(true){ flag[0] = true; while(flag[1]){ if(turn == 1){ flag[0] = false; while(turn == 1);//do nothing; flag[0] = true; } } /*critical section*/; turn = 1; flag[0] = false; /*remainder*/; }}void P1(){ while(true){ flag[1] = true; while(flag[0]){ if(turn == 0){ flag[1] = false; while(turn == 0);//do nothing flag[1] = true; } } /*critical section*/ turn = 0; flag[1] = false; /*remainder*/; }}void main(){ flag[0] = false; flag[1] = false; turn = 1; parbegin(P0,P1);}
临界区:任何不想或不能被多个进程“同时”执行(单处理器的宏观同时或多处理器的同一时间)的代码片段。为了保证某个进程对某个资源的使用过程的连续性。特定临界区的代码任何时刻最多只能有一个进程在执行。
函数P0、P1用来模拟两个进程。每个进程在进入临界区前,先声明自己想进入,即将自己的flag变量置1。然后检查别的进程是否想进入临界区(检查别人的flag是不是1)。如果也有其他进程想访问临界区,那么检查仲裁变量turn,如果turn不归自己,就撤销自己的声明(flag清零)并等待turn;如果turn归自己,并且别人已经从临界区退出了,那么自己进入临界区。退出临界区是把turn给别人,并撤销自己的flag。
设计互斥算法的难点在于任何两个指令之间都有可能发生进程切换。
boolean flag[2];int turn;void P0(){ while(true){ flag[0] = true; turn = 1; while(flag[1] && turn == 1);//do nothing; /*critical section*/; flag[0] = false; /*remainder*/; }}void P1(){ while(true){ flag[1] = true; turn = 0; while(flag[0] && turn == 0);//do nothing /*critical section*/; flag[1] = false; /*remainder*/; }}void main(){ flag[0] = false; flag[1] = false; parbegin(P0,P1);}
Peterson算法比较好理解。
对于每一个进程都有自己的flag。整个系统有一个turn变量。每个进程想要进入临界区都要先经过两个步骤:1.将自己的flag置一 2.将turn置成自己的序号。然后进行判断:如果存在其他进程的flag为一(这表明别的进程也在试图进入临界区)而且turn为自己所置的序号(说明自己是此刻最后修改turn的进程)那么就忙等待。问题来了:操作系统精髓与设计原理(P506)这本书上说这个算法很容易扩展到多个进程的情况,怎么办?
转载地址:http://keqbb.baihongyu.com/