操作系统全部课件3.2临界区管理

1、1主要内容：互斥与临界区实现临界区管理的几种尝试实现临界区管理的软件方法实现临界区管理的硬件设施 3.2 临界区管理 2一、互斥与临界区 (1) 飞机票售票系统之所以会产生错误，原因在于多个售票进程交叉访问了共享变量Aj。Dijkstra在1965年首先提出临界区的概念。1.“临界区”(Critical Section)与“临界资源”(Critical Resource)并发进程中与共享变量有关的程序段叫“临界区” ，共享变量代表的资源叫“临界资源” 。 3一、互斥与临界区 (1) 飞机票售票系统中，进程T1的临界区为：X1= Aj;if X1=1 then begin X1= X1-1; A

2、j= X1;输出一张票；end进程T2的临界区为：X2= Aj;if X2=1 then begin X2= X2-1; Aj= X2;输出一张票；end与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。如果能保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。 4一、互斥与临界区 (4) 2.临界区的调度原则 (1)一次至多一个进程能够进入临界区内执行；(2)如果已有进程在临界区，其他试图进入的进程应等待；(3)进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入。临界区调度原则概括为： 互斥使用

3、、有空让进， 忙则等待、有限等待， 择一而入、算法可行。算法可行是指不能因为所选的调度策略造成进程饥饿甚至死锁。 5二、实现临界区管理的几种尝试 (1) 首先讨论用软件方法实现互斥，软件方法是为在具有一个处理器或共享主存的多处理器上执行的并发进程实现的，这种方法假定对主存中同一个单元的同时访问必定由存储器进行仲裁，使其串行化。下面的程序是采用标志方法实现互斥的一种尝试。 6二、实现临界区管理的几种尝试 (2) bool inside1=false; /P1不在其临界区内bool inside2=false; /P2不在其临界区内cobegin /*cobegin和coend表示括号中的进程是一

4、组并发进程*/process P1( ) process P2( ) while(inside2);/等待 while(inside1);/等待 inside1=true; inside2=true; 临界区; 临界区; inside1=false; inside2=false; coend 这种方法是错误的，下面是一个说明错误的执行实例：7二、实现临界区管理的几种尝试 (4) 全局共享变量：inside1= falseinside2= falseprocess P1process P2while (inside2);while (inside1);inside1 = true;inside2

5、 = true;临界区;临界区;inside1 = false;inside2 = false;进程P1、P2同时进入了临界区。时间8二、实现临界区管理的几种尝试 (5) 下面是第二个尝试，它会造成永远等待：bool inside1=false; /P1不在其临界区内bool inside2=false; /P2不在其临界区内cobeginprocess P1( ) process P2( ) inside1=true; inside2=true; while(inside2);/等待 while(inside1);/等待临界区; 临界区; inside1=false; inside2=fal

6、se;coend9二、实现临界区管理的几种尝试 (7) 全局共享变量：inside1= falseinside2= falseprocess P1process P2inside1 = true;inside2 = true;while (inside2);/无限等待while (inside1);/无限等待时间进程P1和P2永远等待10三、实现临界区管理的软件方法 (1) 1981年，由Peterson提出一个简单巧妙的算法解决进程互斥进入临界区的问题。该方法为每个进程设置一个标志，当该标志为true时表示此进程要求进入临界区，另外再设置一个指示器turn以指示可以由哪个进程进入临界区。若t

7、urn=i则进程Pi可以进入临界区。11三、实现临界区管理的软件方法 (7) Peterson算法如下：bool inside2;inside0=false;inside1=false;enum 0,1 turn;cobeginprocess P0( ) inside0=true; turn=1; while(inside1&turn=1); 临界区; inside0=false; process P1( ) inside1=true; turn=0; while(inside0&turn=0);临界区; inside1=false; coend12三、实现临界区管理的软件方法 (10) 算法

8、分析与理解： 两个进程同时执行时情况分析：全局共享变量：turn = 1，0inside0 = false，true，falseinside1 = false，true，falseprocess P0process P1inside0= true;inside1 = true; turn = 1;turn = 0;while (inside1&turn=1) ;/不等待while (inside0&turn=0) ;/等待临界区;inside0 = false;while (inside0&turn=0) ;/不等待临界区;inside1 = false;13三、实现临界区管理的软件方法 (1

9、2) 一个进程单独执行时情况分析：全局共享变量：turn = 1inside0 = false，true，falseinside1 = falseprocess P0inside0= true;turn = 1;while (inside1 and turn=1);/不等待临界区;inside0 = false;任何一个进程任何时候都可以自由连续多次进入临界区，而不需要通过两个进程交替执行才能进入临界区。14三、实现临界区管理的软件方法 (13) Peterson算法能够正确实现2个进程的互斥，符合临界区调度三原则。证明：（1）两个进程P0和P1不会都等待在临界区外进不去。假设两个进程P0和P

10、1都等待在临界区外进不去，只会在while循环处等待，等待时两个while 条件需同时为真。即inside1=true且turn=1且inside0 =true且turn=0， turn不可能既是1又是0，因此矛盾，假设不成立，两个进程P0和P1不可能都等待在临界区外进不去，至少有一个进程会进入临界区。15三、实现临界区管理的软件方法 (13) （2）两个进程P0和P1不会同时进入临界区。假设两个进程P0和P1同时进入临界区，则inside1=true且turn=1且inside0 =true且turn=0， turn不可能既是1又是0，因此矛盾，假设不成立，两个进程P0和P1不会同时进入临界

11、区，至多有一个进程进入临界区。如果进程数目超过2，例如达到100，该算法如何扩展解决100进程之间的互斥？16四、实现临界区管理的硬件设施 (1) 在单处理器计算机中，并发进程只会交替执行。为了保持互斥，仅需要保证一个进程不被中断就可以了。 管理临界区的软件尝试算法中用到了标志，在进入临界区之前需要首先测试标志，然后设置标志，这两个动作不能分开，否则，两个进程就可能同时进入临界区。 用来实现互斥的硬件设施主要有：关中断测试并建立指令对换指令 17四、实现临界区管理的硬件设施 (2) 1.关中断 关中断是实现互斥的最简单方法之一。进程在进入临界区之前先关中断，退出临界区时开中断。在关中断期间，进

12、度调度程序失去中断激活的机会，不会切换进程，保证了临界区的互斥执行。 18四、实现临界区管理的硬件设施 (2) 关中断方法的缺点：关中断时间过长会影响系统效率，限制处理器交叉执行程序的能力；关中断方法不适用于多CPU系统，因为，在一个处理器上关中断，并不能防止进程在其他处理器上执行相同临界区代码；关中断权利赋予用户很危险，如果用户未开中断，系统可能因此终止。 19四、实现临界区管理的硬件设施 (3) 2.测试并建立指令 硬件提供的测试并建立指令的执行过程如下： TS(x): 若x=true，则x=false；return true；否则 return false； TS指令管理临界区时，可把一

13、个临界区与一个布尔变量s相连，由于变量s代表了临界资源的状态，可把它看成一把锁。 s初值为true，表示没有进程在临界区内，资源可用。20四、实现临界区管理的硬件设施 (3) 用TS指令实现临界区管理（互斥）的算法如下： bool TS(bool &x) if(x) x=false; return true; else return false; 21四、实现临界区管理的硬件设施 (3) /TS指令实现进程互斥bool s=true;cobeginprocess Pi( ) /i=1,2,.,n while(!TS(s); /上锁 临界区; s=true; /开锁coend22四、实现临界区管理的硬件设施 (5) 3.对换指令 对换（Swap）指令的功能是交换两个字的内容，处理过程如下： void SWAP(bool &a,bool &b) bool temp=