32操作系统第三章.ppt

1、第三章 进程管理,sh_,本章主要内容,3.5 进程互斥,两种形式的制约关系 系统中诸进程之间在逻辑上存在着两种制约关系： 直接制约关系（进程同步）：即为完成同一个任务的诸进程间，因需要协调它们的工作而相互等待、相互交换信息所产生的直接制约关系。 间接制约关系（进程互斥） ：是进程共享独占型资源而必须互斥执行的间接制约关系。,3.5 进程互斥,同步与互斥比较,3.5 进程互斥,1、临界区、临界资源, 1次仅允许1个进程使用,具备这种特性的资源称为临界资源(critical resource)， 使用临界资源的那段程序称为临界段(critical section),从进程角度看，它被各个进程互斥

2、地使用,临界资源、临界区,例：有两个进程A和B，它们共享一个变量x，且两个进程按以下方式对变量X进行访问和修改: 其中R1和R2为处理机中的两个寄存器。 A与B均对X+1，即X+2。 若按另一顺序对变量进行修改： 结果x只加了1。,A: R1=X; B: R2=X; A: R1=R1+1; X=R1; B: R2=R2+1; X=R2;,临界资源、临界区,例2：getspace和release: getspace: begin local g g stacktop top top-1 end release(ad):begin top top+1 stacktop ad end 两个进程公用一

3、个堆栈，堆栈是临界资源；访问堆栈的程序段就是临界区。,临界资源、临界区,为了保证临界资源的正确使用，可以把临界资源的访问过程分成以下几部分：,进入区增加在临界区前面的一段代码，用于检查欲访问的临界资源此刻是否被访问。 退出区增加在临界区后面的一段代码，用于将临界资源的访问标志恢复为未被访问标志。 剩余区进程中除了进入区、临界区及退出区之外的其余代码。,临界资源、临界区,要进入临界区的若干进程必须满足： （1）一次只允许一个进程进入临界区 （2）任何时候，处于临界区的进程不得多于一个 （3）进入临界区的进程要在有限的时间内退出 （4）如果不能进入自己的临界区，则应让出处理机资源 解决临界区（互斥

4、）问题的几类方法： （1）软件方法 （2）硬件方法 （3）P-V操作,互斥的定义,互斥的定义： 不允许两个以上的共享某一公有资源的并发进程同时进入临界区称为互斥。,一组并发进程互斥执行需满足的准则,1.空闲让进 2.忙则等待 3.多中选一 4.有限等待：应保证为有限等待，不会产生死等。 5.让权等待：不能进入临界区的执行进程应放弃CPU执行权。,互斥的加锁实现,原理：当某个进程进入临界区之后，它将锁上临界区；直到它退出临界区时为止。 并发进程在申请进入临界区时，首先测试该临界区是否是上锁的，如果该临界区已被锁住，则该进程要等到该临界区开锁之后才有可能获得临界区,加锁后的临界区程序描述： Loc

5、k(keys)； (临界区) unLock(keys)； 引入锁定位keys=1（资源可用）或0（资源不可用） Lock(keys)定义三个动作： a. 检查keys是否为1； b. 若keys=1，则keys=0； c. 若keys=0，则返回a继续检测。 unLock(keys)定义一个动作：keys 1 。,互斥的加锁实现,问题： Lock(keys)必须满足 keys=0时，不允许任何进程进入临界区；keys=1时，仅允许一个进程进入临界区，实现起来较困难。,互斥的加锁实现,信号量（Sem）的物理意义： 信号量（Sem）是一整数； 当sem 0时代表可供并发进程使用的资源实体的数目；

6、当sem 0时则表示正在等待使用资源（如临界区）的进程数目。 信号量使用时应注意的问题： 用于进程互斥的信号量sem的初值应该大于零；建立一个信号量时必须说明所建信号量所代表的意义（物理）并赋初值。,3.5.3 信号量和P,V原语,P操作的定义： 信号量sem减1； 若sem减1后仍大于等于零，则进程继续执行； 若sem减1后小于零，则该进程被阻塞后加入与该信号相对应的等待队列中，然后转进程调度。,P,V原语,P操作流程图,V操作的定义： 信号量sem加1； 若sem加1后仍大于零，则进程继续执行； 若sem加1后小于或等于零，则从与该信号相对应的等待队列中唤醒一个等待进程，然后返回原进程继续

7、执行或转进程调度。 信号量的值仅能由P、V原语操作改变。,P,V原语,V操作流程图,实现P、V原语的软件方法：加锁法,P（sem）： Begin 封锁中断； lock(lockbit) valsem=valsem-1 if valsem0 保护当前进程CPU现场； 把当前进程状态置为等待； 将当前进程插入信号量sem的等待队列； 转进程调度； fi unlock(lockbit)； 开放中断； end,实现P、V原语的软件方法：加锁法,V（sem）： Begin 封锁中断； lock(lockbit) valsem=valsem + 1 if valsem 0 local K； 从sem等待队

8、列中选取一个等待进程，将其指针置入K中； 将K插入就绪队列； 进程状态置“就绪” fi unlock(lockbit)； 开放中断； end,用P、V操作实现简单的进程互斥或同步,解决此类问题的一般方式： 根据问题给出的条件，确定进程有几个或几类； 确定进程间的制约关系是互斥，还是同步； 各相关进程间通过什么信号量实现彼此的制约，标明信号量的含义和初值。 用P、V操作写出相应的代码段。 验证代码的正确性：设以不同的次序运行各进程，是否能保证问题的圆满解决。切忌按固定顺序执行各进程。,用P、V操作实现互斥,用信息量和P、V操作实现互斥的一般模型,进程1,P(mutex) 临界区 V(mutex)

9、,进程2,P(mutex) 临界区 V(mutex),进程n,P(mutex) 临界区 V(mutex),例子： 设某游艺场设置了一个自动计数系统，用一个计数器count 来指示在场的人数。当有一个人进入时，进程PIN实现计数加1，当退出一人时，进程POUT实现计数减1。由于入场和退场是随机的，因此PIN和POUT是并发的。 用cobegin和coend表示并发执行，这两个进程的程序如下：,用P、V操作实现互斥,main( ) begin count: integer; count:=0; cobegin process PIN Ru:integer; Begin Ru:=Count; Ru:

10、=Ru+1; Count:=Ru; End;,process POUT Cu:integer; Begin Cu:=Count; Cu:=Cu - 1; Count:=Cu; End; Coend; End;,用P、V原语实现进程的互斥（例如这里是互斥进入临界区） main( ) begin count: integer; S:semaphore; count:=0; S:=1;,cobegin process PIN Ru:integer; Begin P(s); Ru:=Count; Ru:=Ru+1; Count:=Ru; V(s); End;,process POUT Cu:integ

11、er; Begin P(s); Cu:=Count; Cu:=Cu - 1; Count:=Cu; V(s); End; Coend; End;,设置互斥信号量sem；给信号量置初值sem=1。 进入临界区前，安排一条P操作指令。 进入临界区。 退出临界区后，安排一条V操作指令。,用P、V原语实现进程的互斥方法,P（sem） V（sem）,临界区,P、V原语法和加锁法实现进程间互斥比较： 加锁法：当某个进程进入临界区之后，它将锁上临界区；直到它退出临界区时为止。其它进程要进入临界区，首先测试该临界区是否上锁，如果临界区已被锁住，则该进程要等到该临界区开锁才能获得临界区。 问题：循环测试浪费CPU时间；产生不公平现象。,P、V原语法和加锁法实现互斥的比较,P、V原语法：采用信号量管理临界资源，信号量的数值仅能由P、V操作改变，而P、V原语在执行期间是不