第4讲 进程管理之进程同步.doc

第四讲 进程管理之进程同步一、 为什么要引入进程同步？进程同步有什么作用？在引入了进程后，提高了资源的利用率但是由于有限的资源也导致进程之间的资源竞争和共享现在我们来看在进程的并发执行过程中存在的制约1、两种形式的制约关系A. 间接制约－由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象如两个进程都要使用打印机，则只有一个进程能获得，另一个进程只有等待只有当打印机被释放后，该进程才能执行B. 直接制约－简单说就是一组异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程进程同步的任务也就是其作用是使并发执行的诸进程之间能有效共享资源和相互合作，从而使程序的执行有可再现性也就是能使诸进程能够顺利执行下去从这里我们可以看出，进程同步只有解决了进程间的间接制约和直接制约关系，才能使进程顺利协调执行解决A的方法是：保证诸进程互斥访问临界资源即进程互斥解决B的方法是：协调相互合作的诸进程的执行次序，狭义的同步即进程同步那么现在明白了，进程同步包括，解决间接制约的进程互斥和解决直接制约的进程同步二、 进程同步的基本概念一） 临界资源Ø 概念：一段时间内只允许一个进程访问的资源。

也就是竞争的那个公有资源Ø 要求：共享临界资源的诸进程必须互斥访问临界资源Ø 举例：生产者－消费者问题生产者（） 消费者（）… ….放产品 取产品Counter:=counter+1 Counter:=Counter -1…. ….机器语言形式为：现在我们来看结果，由于生产者和消费者并发执行，并共享Counter，因此有：假设Counter的当前值是5，正确的结果应该是5这表明：程序的执行不具有可再现性为了解决此错误，应把变量Counter作为临界资源处理也就是要生产者进程和消费者进程互斥的访问变量Counter.Ø 结论：作为临界资源，生产者进程和消费者进程应该互斥访问也就是，虽然生产者进程和消费者进程并发执行，但在执行Counter加1，减1时，要顺序执行也就是只能安上述A或B的顺序执行不能交替。

Ø 临界资源实例：硬件中的打印机、磁带机软件中的变量、队列、缓冲区等二） 临界区（critical section）1、 概念：不允许多个并发进程交叉执行的一段程序就称为临界区，也就是每个进程中访问临界资源的那段代码例如：生产者的Counter:=counter+1 ，消费者的Counter:=Counter -1都是CS2、 临界区的进入：要互斥的进入临界区，就可实现对临界资源的互斥访问要做到这点，必须在进入临界区之前对欲访问的临界资源进行检查，若此刻临界资源未被访问，则该进程进入临界区，对该资源访问，并设置它正被访问的标志；否则，该进程不能进入临界区因此描述为如下：v 进入区—增加在临界区前面的一段代码，用于检查欲访问的临界资源此刻是否被访问v 退出区—增加在临界区后面的一段代码，用于将临界资源的访问标志恢复为未被访问标志v 剩余区—进程中除了进入区、临界区及退出区之外的其余代码进入区临界区退出区剩余区要进入临界区的若干进程必须满足：同学们看一下加深理解1）一次只允许一个进程进入临界区（2）任何时候，处于临界区的进程不得多于一个（3）进入临界区的进程要在有限的时间内退出（4）如果不能进入自己的临界区，则应让出处理机资源 3、 同步机制准则：看课本说一下空闲让进当无进程处于临界区内时，必须让一个要求进入临界区的进程立即进入，以有效地利用临界资源。

忙则等待当已有进程处于临界区内时，其它试图进入临界区的进程必须等待，以保证它们互斥地进入临界区有限等待对要求进入临界区的进程，应在有限时间内使之进入，以免陷入“死等”让权等待对于等待进入临界区的进程而言，它必须立即释放处理机，以免进程“忙等” 三、 信号量机制semaphore在解决临界区问题上，有些课本还提到了软件方法和硬件方法，有兴趣的同学自己下去看信号量和P、V原语概念都是由荷兰科学家Dijkstra提出来的我们用信号量及PV操作来实现进程的同步和互斥PV操作属于进程的低级通信一） 信号量概念1、 整型信号量n 整型信号量——非负整数，除了初始化外，只能通过两个原子操作wait和signal（P，V）来访问n wait和signal操作描述： wait(S)： while S£0 do no-op 测试有无可用资源 no-op是无操作 S:=S-1; 可用资源数减一个单位 signal(S): S:=S+1;n 主要问题：只要S£0， wait操作就不断地测试（盲等），因而，未做到“让权等待” 2、 记录型信号量由于采用了记录型结构而得名。

n 基本思想 1、设置一个代表资源数目的整型变量value（资源信号量） 2、设置一链表L用于链接所有等待的进程n 记录型信号量的数据结构 Type semaphore=record value:integer; L: list of process; endn wait和signal操作描述： wait(S)： S.value:=S.value-1; if S.value<0 then block(S.L); signal(S): S.value:=S.value+1; if S.value£0 then wakeup(S.L);做到“让权等待” 3、 AND型信号量和一般信号量集 了解一下就可以n AND型信号量的基本思想 将进程在整个运行过程中所需要的所有临界资源，一次性全部分配给进程，待进程使用完后再一起释放。

只要有一个资源未能分配给进程，其它所有可能分配的资源也不分配给该进程从而可避免死锁发生在wait操作中，增加了一个“AND”条件，故称为AND同步n 一般信号集的基本思想 一次可分配多个某种临界资源，而不需执行N次的P操作；每次分配前都测试该种资源数目是否大于测试值，低于此值，不分配总结和补充：注意：用于互斥的信号量初值应该大于0信号量的值仅能由PV操作来改变这是因为进程互斥是由资源共享造成的间接制约产生的，因此信号量初值大于0，这样说明出初始时有资源二）P、V原语1、什么是P、V原语？ P操作和V操作是不可中断的程序段，称为原语P,V原语中P是荷兰语的Passeren，相当于英文的pass, V是荷兰语的Verhoog,相当于英文中的incremnet一般来说，信号量S³0时，S表示可用资源的数量执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S£0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

Ø P原语操作的动作是： 指的是记录型信号量（1）       sem减1； （2）       若sem减1后仍大于或等于零，则进程继续执行； （3）       若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度Ø V原语操作的动作是： 指的是记录型信号量（1）       sem加1； （2）       若相加结果大于零，则进程继续执行； （3）       若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度注意：就是P,V操作对于每一个进程来说，都只能进行一次而且必须成对使用且在P,V愿语执行期间不允许有中断的发生P原语图 V原语图四、 信号量机制的应用一） 利用信号量实现前趋关系利用信号量描述程序或语句之间的前趋关系如：设S1,S2,S3,S4为一组合作进程，其前趋图如图所示，用P、V操作实现其同步S1S2S3S4abcd解：说明：比较好理解，每一个进程执行都要先以上一个进程为入口，并以唤醒下一个进程为出口看例子，课本也行var a,b,c,d:semaphore:=0,0,0,0; /*表示进程是否执行完*/ main()　process S4()　{ P(c)P(d) …… ……. }　process S1()　{ …… ……. V(a)}　process S3()　{ P(a)P(b) …… ……. V(d)}　process S2()　{ …… ……. V(b)V(c)} { cobegin s1(); s2(); s3(); s4(); coend}二）利用信号量和PV操作实现进程互斥的一般模型是：1、信号量实现进程互斥原理：由于用于互斥的信号量sem与所有的并发进程有关，所以称之为公有信号量。

公有信号量的值反映了公有资源的数量把临界区置于P(sem) 和V(sem)之间当一个进程想要进入临界区时，它必须先执行P原语操作以将信号量sem减1，在进程完成对临界区的操作后，它必须执行V原语操作以释放它所占用的临界区从而就实现了进程的互斥：举个例子说明一下，只要把临界区置于P(sem)和V (sem)之间，即可实现进程间的互斥就象火车中的每节车厢只有一个卫生间，该车厢的所有旅客共享这个公有资源：卫生间，所以旅客间必须互斥进入卫生间，只要把卫生间放在P(sem)和V(sem)之间，就可以到达互斥的效果2、一般模型进程P1 进程P2 …… 进程Pn…… …… ……P（S）； P（S）； P（S）；临界区； 临界区； 临界区；V（S）； V（S）； V（S）；…… …… …… …… 其中信号量S用于互斥，初值为1。