4.2 临界区管理.ppt

1、4.2 临界区管理,4.2.1 临界资源和临界区 互斥共享的资源称为临界资源。 在生产者和消费者进程中，缓冲区和变量count都是临界资源。 在程序中对临界资源访问的代码部分称为临界区。 每个进程访问临界资源前都要判断该资源能否访问，如果进程能够访问，才能进入到临界区访问临界资源； 如果不能访问，则进程需要等待，直到该资源能够访问为止，才能进入到临界区访问临界资源。 进程对临界资源访问结束后，需要将资源归还，使其他进程能够知道临界资源已经被当前进程访问结束。,4.2.1 临界资源和临界区（续）,在程序中，进入临界区代码之前，应该是对临界资源能否访问的判断，这部分代码称为进入区，进入区通常是测试

2、语句或判断语句，如while，if等。 临界区后面的代码应该体现对临界资源访问结束后的标志，即退出区。 程序中的进入区、临界区和退出区3个部分如图4.3所示。,4.2.1 临界资源和临界区（续）,（1）空闲让进，互斥使用 当没有进程访问临界资源，临界资源为空闲时，系统允许一个请求临界资源的进程进入临界区，访问临界资源。 （2）忙则等待 当已有进程正访问临界资源，临界资源为忙时，则系统不允许当前请求临界资源的进程访问临界资源，请求进程只能等待，以保证临界资源的互斥使用。 （3）有限等待 对请求访问临界资源的进程，如果不能访问临界资源，需要等待临界资源，则应该保证进程等待临界资源的时间是有限的，使

3、其在有限的时间内可以进入访问临界资源，不允许让进程无限等待临界资源。 （4）让权等待 当进程不能访问临界资源时，进程应该立即停止运行，让出处理器，同时进程的状态从运行转换到阻塞，以免进程陷入“忙等待”。此处的“权”是指处理器的执行权。,4.2.2 进程同步准则,4.2.2 进程同步准则（续）,假设存在A、B两个并发进程访问临界资源，如图4.4所示。,4.2.2 进程同步准则（续）,在程序设计时，进入区是判别能否访问临界资源的关键。 如果进程能访问临界资源，则通过进入区，进入临界区访问临界资源；否则，进程不能进入临界区访问临界资源； 当进程访问临界资源完后，通过退出区，释放临界资源。 并行的进程

4、需要共享整个系统资源或系统全局变量，进程并行同样存在进程之间资源的竞争和相互协调关系，在多处理器环境下系统同样需要采取同步措施。,1软件方法 软件方法在共享内存的单处理机或多处理机系统中实现进程的并发。 不需要硬件或操作系统或程序设计语言的任何支持。 主要思路：引入进程标志，分别指示进程进入临界区的情况,4.2.3 早期的临界区管理方法（续）,算法1：临界区标志法 为了实现临界区的管理，采用标志来表示哪个并发进程可以进入临界区访问。 对并发进程i和进程j，首先设置标志变量turn。 如果标志变量turn = i，表示允许进程i进入临界区访问； 如果标志变量turn = j，表示允许进程j进入临

5、界区访问。 while是一个判断语句，只要while后面的条件满足，则while一直等待在后面的条件上，只有条件不满足时，才进入while的下一个语句执行，直到end语句结束，进程完成一轮执行。 下一轮还需要访问临界资源时，又到while处判断，如此循环往复。两个进程不断地并发执行。,4.2.3 早期的临界区管理方法（续）,对进程i和进程j，算法代码如下： turn: integer; turn: = i; f_Pi; /* 创建进程Pi */ f_Pj; /* 创建进程Pj */ cobegin,Pi: /* 对进程i */ begin while turn = j do nothing;

6、critical section; turn = j; end;,Pj: /* 对进程j */ begin while turn = i do nothing; critical section; turn = i; end;,coend;,在程序初始化时将turn的初始值设置为i，所以，在进程i和进程j并发时，总是进程i首先进入临界区访问； 进程i访问完临界区后，将turn的值置为j，此时进程j进入临界区访问； 当进程j访问完临界区后，又将turn置为i，让进程i访问临界资源。这样相互轮流访问临界资源。,4.2.3 早期的临界区管理方法（续）,该算法存在的问题： 强制两个进程轮流进入临界区。

7、如果进程i访问完临界区后，进程j并未要求访问该临界资源，或者进程j暂时不访问该临界资源，而进程i又需要再次访问该临界资源，进程i却无法进入临界区，最终造成临界资源没有进程访问。 违背了进程同步机制中的“空闲让进”的原则。,4.2.3 早期的临界区管理方法（续）,算法2：先判断对方进程标志的进程数组标志法 采用查看标志的方法。 进程i每次访问临界资源前，首先查看其他进程访问临界资源的标志。如果其他进程标志处于正在访问，则进程i等待。 当其他进程标志处于没有访问临界资源时，进程i才能进入临界区访问。 设置数组flag为每个进程是否访问临界资源的标志。 对进程i，flagi为true，标志进程i正在

8、临界区访问；flagi为false表示进程i没有访问临界区。,4.2.3 早期的临界区管理方法（续）,turn: integer var flag: array1,2,n of Boolean; flag0 = false; /* flag初始化为false */ flag1 = false; f_Pi; /* 创建进程Pi */ f_Pj; /* 创建进程Pj */ cobegin,Pj /* 对进程j */ begin while flagi do nothing; flagj = true; critical section; /* 访问临界区 */ flagj = false; end

9、;,coend;,Pi： /* 对进程i */ begin while flagj do nothing; flagi = true; critical section; /* 访问临界区 */ flagi = false; end;,存在问题： 当进程i和进程j都没有进入临界区时，即各自的访问标志flag都为false时，进程while语句通过，进程进入下一个语句时设置进程自己的访问标志，双方都将自己的访问标志设置成true，都要访问临界区。此时，进程i和进程j都进入临界区访问，发生冲突，违背了“忙则等待”的同步准则。 当某个进程要访问临界区已经将自己的标志置为true之后，进程又放弃了临界

10、区的访问，从而会引起其它进程一直等待。,4.2.3 早期的临界区管理方法（续）,算法3：先设置自己标志的进程数组标志法 首先设置自己的标志flag为true，先表明自己需要访问临界资源，然后再判断对方进程是否在使用临界资源。 算法代码如下。 turn: integer var flag: array1,2,n of Boolean; flag0 = false; /* flag初始化为false */ flag1 = false; f_Pi; /* 创建进程Pi */ f_Pj; /* 创建进程Pj */ cobegin,4.2.3 早期的临界区管理方法（续）,Pi：/* 对进程i */ be

11、gin flagi = true; while flagj do nothing; critical section; flagi = false; end;,Pj: /* 对进程j */ begin flagj = true; while flagi do nothing; critical section; flagj = false; end;,4.2.3 早期的临界区管理方法（续）,coend;,算法3面临的问题： 双方进程都先将自己的访问标志设置为true，表明自己要访问临界资源，再判断对方是否访问临界资源，这最终会造成进程双方在判断对方是否访问临界资源时，首先看到的是对方设置了访问

12、标志为true，认为对方进程要访问临界资源，自己不能访问临界资源，最终导致并发进程在while语句上等待，而临界资源并没有进程在访问。 该算法违背了“空闲让进”的同步准则。,4.2.3 早期的临界区管理方法（续）,算法4：双标志法 1981年，GLPerterson总结了算法1和算法3的问题后，提出了算法4。 算法4既利用了标志flag，又利用了标志turn。 标志flag用于表示每个进程是否访问临界资源。 标志turn用于表示临界资源此时是否有对方进程在访问。 只有在对方进程的访问标志flag为true并且turn也为对方进程时，才表明对方进程在访问临界资源，需要等待对方进程访问完并释放资源

13、后才能访问；否则进程不需要等待对方进程而访问临界资源。,4.2.3 早期的临界区管理方法（续）,turn：integer: = i; var flag: array1,2,n of Boolean; flag0 = false; /* flag初始化为false */ flag1 = false; f_Pi; /* 创建进程Pi */ f_Pj; /* 创建进程Pj */ cobegin,4.2.3 早期的临界区管理方法（续）,算法代码如下：,Pi： /* 对进程i */ begin flagi = true; turn=j; while flagj and turn = j donothin

14、g; critical section; flagi = false; end;,4.2.3 早期的临界区管理方法（续）,Pj： /* 对进程j */ begin flagj = true; turn = i; while flagi and turn = i do nothing; critical section; flagj = false; end;,coend;,此处语句“while flagj and turn = j do nothing;”表示只有进程j的标志flagj为进程true，并且标志turn也为进程j时，才表示进程j访问临界区，进程i需要等待。 如果进程i要访问临界资

15、源，则首先将自己的标志flag设置为true，然后设置标志turn为对方进程j；如果此时进程j尚未申请访问临界资源，则flagj为false，进程i能够进入临界区； 如果此时进程j比进程i申请临界资源稍微晚一点，进程j会设置自己的访问标志flag为true后再设置turn为i，这样进程i在等进程j将turn设置为i后，便进入临界区访问。而进程j则需要等待进程i访问完里临界区后将flagi设置为false，便可访问临界区。 此算法可以很好的实现进程对临界资源的访问，turn变量的使用非常巧妙。,4.2.3 早期的临界区管理方法（续）,算法4是一个应用性非常方便的进程同步算法，如果有多个进程并发访

16、问临界资源，该算法也可以容易地实现。 虽然现在很少用上面的软件算法实现临界区管理问题，但是，这些算法对理解同步问题还是很有益处的。,4.2.3 早期的临界区管理方法（续）,软件解法的缺点,1. 忙等待（busy waiting） 2. 实现过于复杂，需要高的编程技巧,2硬件方法 在临界区访问标志算法中，出现了违背“忙则等待”或“空闲让进”准则的根本原因在于管理临界区标志要用两条指令： 一条指令是看对方的标志，一条指令是设置自己的标志。 进程并发，特别是单处理器上的并发，并发进程交替执行，可能导致一个进程在执行这两条指令时被另一个进程中断，最终产生进程对临界区的不正确访问。 要保证进程在执行这两

17、条指令时不被中断，系统可以采取锁的方式。,4.2.3 早期的临界区管理方法（续）,如果临界区没有被访问，则锁是打开的，在进程访问临界区时，只要进程一进入临界区，则系统立即上锁，使得其他进程不能进入临界区，直到访问临界区的进程离开临界区才打开锁。 只有锁打开了，等待临界区访问的进程才有机会进入临界区。 在锁的操作问题上，同样，测试锁和上锁这两个操作也是不能分开的，否则也会造成多个进程测试到锁打开而同时上锁的现象，引起冲突。 进程在执行这两个操作期间在处理器上的运行不能被中断。完全用软件方法来解决有一定局限性和难度，该方法已经很少被采用，现在一般都借助于硬件设施。,4.2.3 早期的临界区管理方法

18、（续）,（1）禁止中断方法 最简单的方法是硬件上的关中断，即禁止中断。在进入临界区标志的两条指令之前或锁测试之前将中断关上，计算机系统在进程测试并进入临界区期间不响应中断，只有临界区访问完后系统才打开中断，从而保证了对临界资源的互斥访问。,4.2.3 早期的临界区管理方法（续）,关中断会带来如下缺点： 影响计算机效率 如果对临界区的访问时间较长，关中断的时间太长，限制了处理器交叉执行程序的能力，影响计算机系统的效率。 不能及时处理重要程序 滥用关中断会引起计算机响应不及时，重要的中断程序不能及时处理，导致出现严重的后果。 在多处理器下方法失效 对于多处理器系统，要想通过关中断阻止进程在临界区执

19、行期间不被中断，毫无任何意义。因为相同的临界区代码会被另一个进程在另一个处理器上执行。,4.2.3 早期的临界区管理方法（续）,（2）测试并建立指令 许多计算机都提供了一些特殊的硬件指令，这些硬件指令在执行中不会被中断。因此，实现临界区管理可以利用硬件提供的“测试并建立(Test and Set)”指令TS。 将TS指令看成为一个函数过程，该函数有一个布尔参数x和一个返回条件码。当TS为true时则置x为false，根据测试到的x值形成条件码。 TS(x)： if x = true then x： = false； return true； else return false；,4.2.3 早

20、期的临界区管理方法（续）,可把临界区看为与布尔变量x相连。 如果x为true，表示没有进程在临界区内，没有上锁，临界资源可被使用，并立即将x置为false，即立刻对临界区上锁。 如果x为false，则表示进程在访问临界区，需要等待。,4.2.3 早期的临界区管理方法（续）,TS函数的应用为： var s: Boolean; s: = true; Pi： /* 对进程Pi，i=1， 2，3，n */ begin var Pi: Boolean; while(! TS(s) );/* 上锁 临界区; s： = true; /* 开锁 */ end；,4.2.3 早期的临界区管理方法（续）,（3）对换指令 在不被中断的硬件指令中，也可以用交换两个字内容的对换指令。 下面用对换指令实现对临界区的访问。 Swap是对换指令，用于交换两个字的内容，定义过程如下。 Swap(a, b) temp: = a; a: = b; b: = temp; ,4.2.3 早期的临界区管理方法（续）,Swap的应用为： var lock：Boolean; lock = false; Pi /*