OS-04进程同步与互斥

1、金金 海海 溶溶办公室：办公室： 2A314操作系统设计中的核心问题是关于进程和线程的管操作系统设计中的核心问题是关于进程和线程的管理理 多道程序技术多道程序技术管理单处理器系统中的多个进程管理单处理器系统中的多个进程 多处理技术多处理技术管理多处理器系统中的多个进程管理多处理器系统中的多个进程 分布处理技术分布处理技术管理多台分布式计算机系统管理多台分布式计算机系统 (集群集群) 中多中多个进程的执行个进程的执行 考虑一个支持单用户单处理器、多道程序设计系统考虑一个支持单用户单处理器、多道程序设计系统 将其当作一个共享过程，载入到所有应用程序公用的全局将其当作一个共享过程，载入到所有应用程序

2、公用的全局存储区中。这样每个应用程序都能使用这个过程，由于每存储区中。这样每个应用程序都能使用这个过程，由于每个应用程序只需使用个应用程序只需使用echoecho过程的一个副本，从而节省空间过程的一个副本，从而节省空间进程间共享主存是非常有用的，它允许进程间有效而紧进程间共享主存是非常有用的，它允许进程间有效而紧密的交互，有利于进程的相互通信。但是，共享也可能密的交互，有利于进程的相互通信。但是，共享也可能会带来一些问题会带来一些问题 P1P2XXgetchar（）（）YYYputchar（）（）Y错误原因之错误原因之1： 进程执行交叉进程执行交叉;错误原因之错误原因之2： 涉及公共变量涉及公

3、共变量(chin和和chout)。P1调用调用echo超时，就绪超时，就绪P2调用调用echo阻塞状态阻塞状态调度运行调度运行释放释放echo由此可见，解决共享资源的保护，唯一的办法是由此可见，解决共享资源的保护，唯一的办法是互斥的使用互斥的使用共享资源共享资源（如变量，代码等）（如变量，代码等） 即：一次只允许一个进程访问共享资源即：一次只允许一个进程访问共享资源临界资源和临界区：临界资源和临界区：临界资源临界资源 某些在一段时间内只允许一个进程使用的共享资源称为临某些在一段时间内只允许一个进程使用的共享资源称为临界资源界资源临界区（段）临界区（段） 访问临界资源的程序段称为临界区。即互斥执

4、行的程序段访问临界资源的程序段称为临界区。即互斥执行的程序段进程进程P1和和P2共享同一打印机资源，其操作流程如共享同一打印机资源，其操作流程如下：下： p1: entry codep1: entry code使用打印机使用打印机exit codeexit code p2: entry code p2: entry code使用打印机使用打印机exit codeexit code系统打印机即为系统打印机即为临界资源临界资源P1和和p2的访问临界资源打印机的代码即为的访问临界资源打印机的代码即为临临界区界区Repeat 临界区临界区 其余代码其余代码Until false entry secti

5、on exit section 例：司机例：司机-售票员问题售票员问题 司机活动：司机活动： 售票员活动：售票员活动： do do 启动车辆启动车辆 关车门关车门 正常行驶正常行驶 售售 票票 到站停车到站停车 开车门开车门 while( (1) ) while( (1) )lPeterson算法算法lDekker算法算法lLamport面包店算法面包店算法lEisenberg/Mcguire算法算法 中断禁用中断禁用 信号量（信号量（Semaphore）管程管程( (monitor) )事件事件缺点：缺点：l使用了忙等待，当一个进程在等待资源时，依然会消耗使用了忙等待，当一个进程在等待资源时

6、，依然会消耗CPU时间时间l可能会发生饥饿，有些进程由于长时间得不到资源。可能会发生饥饿，有些进程由于长时间得不到资源。l可能无法彻底实现互斥，有可能可能无法彻底实现互斥，有可能2个及以上的进程进入临个及以上的进程进入临界区。界区。l可能死锁。当低优先级进程获取资源的情况下，被高优先可能死锁。当低优先级进程获取资源的情况下，被高优先级进程抢占级进程抢占cpu，且高优先级进程申请同一资源，由于互，且高优先级进程申请同一资源，由于互斥机制，高优先级进程会进入永远的忙等待。斥机制，高优先级进程会进入永远的忙等待。信号量（信号量（semaphore）：）：一个与资源有关的，初值一个与资源有关的，初值为

7、非负数的整型变量称为信号量。用为非负数的整型变量称为信号量。用S表示，初值表示，初值和资源有关和资源有关信号量是一种特殊的变量，只能由信号量是一种特殊的变量，只能由semWaitsemWait，semSignalsemSignal原语进行原语进行操作操作访问。访问。semWait/semSignal原语都是低级通信原语，一个正原语都是低级通信原语，一个正在执行在执行 semWait/semSignal 操作的进程，不允许任操作的进程，不允许任何其他进程中断它的操作，这样就保证了同时只能何其他进程中断它的操作，这样就保证了同时只能有一个进程对信号量有一个进程对信号量 S 施行施行 semWait

8、或或semSignal实现互斥的例子与分析实现互斥的例子与分析 打印机是一种临界资源，必须互斥使用，则：打印机是一种临界资源，必须互斥使用，则： semWait(S)使用打印机使用打印机semSignal(S)P1P2P3P4P3P4用用信号量信号量实现同步的例子：司机实现同步的例子：司机-售票员问题：售票员问题：司机活动：司机活动： 售票员活动：售票员活动： Do Do 关关车门车门 启动车辆启动车辆 正常行驶正常行驶 售售 票票 到站停车到站停车 开开车门车门 While(1) While(1)设置信号量设置信号量S1,S1,初值为初值为0 0，用于司机用于司机“启动汽车启动汽车”和售票员

9、和售票员“关车门关车门”的的同步同步设置信号量设置信号量S2,S2,初值为初值为0 0，用于司机用于司机“到站停车到站停车”和售票员和售票员“开车门开车门”的的同步同步分析：从分析：从 以上几个例子可以看出以上几个例子可以看出l在在semWaitsemWait中中 S:= S-1 S:= S-1 表示进程请求获得一个资源表示进程请求获得一个资源l当信号量当信号量 S 0 S 0 时，时，S S 的值表示的值表示某类资源可用的数量某类资源可用的数量lS 0S 1 then V(entry) ; P(wait) ; else V(entry) ;V(barber) ; “Shave”P(entry

10、) ;count := count 1;if count 0 then V(wait) ;V(entry) ;=1理发师理发师barberbarber信号量队列信号量队列waitwait信号量队列信号量队列entryentry信号量队列信号量队列 count=5count=5count=4P（barber） 解解:var a, b, c, d, e, f, g, h: semaphore (初值初值=0)parbeginbegin S1; V(a); V(b); V(c); end;begin P(a); S2; V(d); V(e); end;begin P(b); S3; V(f); en

11、d;begin P(c); P(d); S4; V(g); end;begin P(e); P(f); S5; V(h); end;begin P(g); P(h); S6; end;parend例例: 考虑右图所示的优先图，请用并发语句和信号量表达该考虑右图所示的优先图，请用并发语句和信号量表达该优先图。优先图。桌上有一个空盘，允许存放一个水果。父亲可向盘桌上有一个空盘，允许存放一个水果。父亲可向盘中放苹果，也可向盘中放橘子，儿子专等吃盘中的中放苹果，也可向盘中放橘子，儿子专等吃盘中的橘子，女儿专等吃盘中的苹果。规定当盘空时一次橘子，女儿专等吃盘中的苹果。规定当盘空时一次放一个水果供吃者取用

12、，请用放一个水果供吃者取用，请用P，V原语实现父亲、原语实现父亲、儿子、女儿三个并发进程的同步。儿子、女儿三个并发进程的同步。分析同步分析同步/ /互斥关系：互斥关系： 父亲和儿子之间父亲和儿子之间同步同步 父亲和女儿之间父亲和女儿之间同步同步更为高级的同步机构中更为高级的同步机构中, 最重要的是管程最重要的是管程建立管程的基本理由：建立管程的基本理由： 由于临界区的执行分散在各进程中，由于临界区的执行分散在各进程中， PVPV操作可能分布在各操作可能分布在各个程序中个程序中，很难看出在信号量上的操作所产生的整体效果；，很难看出在信号量上的操作所产生的整体效果；也也很难发现和纠正分散在用户程序

13、中的对同步原语的错误很难发现和纠正分散在用户程序中的对同步原语的错误使用等问题使用等问题，也，也不便于系统对临界资源的控制和管理不便于系统对临界资源的控制和管理 开锁、关锁原语和信号量上的开锁、关锁原语和信号量上的 P P、V V 操作，是低级的同步操作，是低级的同步机构，很难表示更为复杂的并发性问题机构，很难表示更为复杂的并发性问题 把分散的各把分散的各同类临界区集中同类临界区集中起来，并为每个可共享资源设起来，并为每个可共享资源设立一个专门的立一个专门的管程管程来统一管理各进程对该资源的访问，这来统一管理各进程对该资源的访问，这样既便于系统管理共享资源，又能保证互斥访问样既便于系统管理共享

14、资源，又能保证互斥访问什么是管程？什么是管程？ 临界资源的管理者或封装者，进程必须通过管程访问临界临界资源的管理者或封装者，进程必须通过管程访问临界资源资源 管程主要由两部分组成：管程主要由两部分组成： 局部于该管程的共享数据，这些数据表示了相应的资源局部于该管程的共享数据，这些数据表示了相应的资源 局部于该管程的局部过程，由这些过程对临界资源进行操作局部于该管程的局部过程，由这些过程对临界资源进行操作 管程一次只允许一个进程进入其内（即访问管程内的某个管程一次只允许一个进程进入其内（即访问管程内的某个过程）过程）这是由编译系统保证。这是由编译系统保证。生产者生产者/ /消费者问题消费者问题生

15、产者生产者/ /消费者问题消费者问题.生产者生产者/ /消费者问题消费者问题初值：初值：k0；in0； out0；n用管程实现生产者和消费者问题：用管程实现生产者和消费者问题：Producer：begin repeat produce an item； buffer.put（item）；）； until false； end；Consumer：begin repeat buffer.get（item）；）； consume the item； until false； End；进程进程通讯通讯：进程同步，互斥及信息交换统称为进程：进程同步，互斥及信息交换统称为进程通信通信低级通讯（简单信号）低

16、级通讯（简单信号）高级通讯（交换大宗的信息）高级通讯（交换大宗的信息） 共享内存模式共享内存模式消息传递模式消息传递模式send发送区发送区（消息）（消息）接接收收区区（消息）（消息）receivehptrmutexsmsptrnptrtextsptrnulltextaddpnulltextpaddpnulltextpnptr发送进程将消息连入接受方的消息队列中；接收发送进程将消息连入接受方的消息队列中；接收进程按进程按先来先服务先来先服务原则处理消息队列中的消息。原则处理消息队列中的消息。处理完一个消息之后，向发送进程回送一个处理完一个消息之后，向发送进程回送一个“回回答答”信号信号为了能高

17、效率地实现进程通信，操作系统设计了为了能高效率地实现进程通信，操作系统设计了多种高级通信原语多种高级通信原语send(R,M) 原语和原语和receive(PID,N)原语原语send(R,M) (发送消息发送消息) 原语原语send(R,M ) send(R,M ) 原语用来发送消息，原语用来发送消息，M M是发送进程提供的发是发送进程提供的发送信息送信息send(R,M) send(R,M) 原语先申请一个消息缓冲区，然后把发送区原语先申请一个消息缓冲区，然后把发送区的内容复制到消息缓冲区中。然后找到接收进程的的内容复制到消息缓冲区中。然后找到接收进程的PCBPCB，把消息缓冲区连入接收进

18、程的消息缓冲区队列中把消息缓冲区连入接收进程的消息缓冲区队列中代码代码procedure send（R,MR,M）；）； bengin new（p）；）；/创建一个空消息缓冲区创建一个空消息缓冲区 将信息写入消息缓冲区将信息写入消息缓冲区 寻找到接收者寻找到接收者R的的PCB; semWait(mutex); 将消息加入将消息加入R的消息队列的消息队列; semSignal(sm); semSignal(mutex); end；receive(PID,N) (读取消息读取消息) 原语原语receive(receive(PID,N) ) 原语用来读取消息，原语用来读取消息，A A是接收进程提供是

19、接收进程提供的接收区起始地址的接收区起始地址receive(receive(PID,N) ) 原语把消息缓冲区中的消息内容、消息原语把消息缓冲区中的消息内容、消息长度以及发送进程的名字长度以及发送进程的名字读取到接收区读取到接收区，然后把消息缓冲，然后把消息缓冲区从链表中去掉，并区从链表中去掉，并释放消息缓冲区释放消息缓冲区如果没有消息可读取，则阻塞接收进程，直至消息发送来如果没有消息可读取，则阻塞接收进程，直至消息发送来为止为止procedure receive（PID,N） bengin semWait(Sm); semWait(mutex); 从消息队列中取下一个消息从消息队列中取下一个

20、消息; semSignal(mutex); 将来自将来自PID进程的消息存入接收区进程的消息存入接收区N; free(p);/释放消息缓冲区释放消息缓冲区 阅读消息阅读消息; end；间接通信方式，也叫信箱通信方式间接通信方式，也叫信箱通信方式 进程间的通信需要通过作为某种共享数据结构进程间的通信需要通过作为某种共享数据结构的实体信箱。发送进程将消息发送到信箱，的实体信箱。发送进程将消息发送到信箱，接受进程到信箱接收属于自己的消息。接受进程到信箱接收属于自己的消息。相当于生产者相当于生产者/消费问题消费问题 题：有题：有P，Q，R 三个进程，三个进程，P读入数据后传递给读入数据后传递给Q，Q进

21、行一些处理后将数据传递给进行一些处理后将数据传递给R，R整理好数据后整理好数据后输出，请用输出，请用pv操作实现三者的同步关系。操作实现三者的同步关系。l进程进程P,QP,Q共享一个缓冲区，进程共享一个缓冲区，进程Q,RQ,R共享一个缓冲区共享一个缓冲区l进程进程P,QP,Q共享一个有共享一个有m m个缓冲区的缓冲池，进程个缓冲区的缓冲池，进程Q,RQ,R共享一个共享一个有有n n个缓冲区缓冲池个缓冲区缓冲池P126页页选择选择题题P126页思考题：页思考题：3）、）、4），），10） (1).进程进程P,Q共享一个缓冲区，进程共享一个缓冲区，进程Q,R共享一个缓冲区共享一个缓冲区 分析：分析

22、： P,Q之间是相互依赖协作的关系之间是相互依赖协作的关系同步同步 Q,R之间也是相互依赖协作的关系之间也是相互依赖协作的关系同步同步 设置信号量设置信号量：假设初始两个缓冲区都为空：假设初始两个缓冲区都为空 P的私有信号量的私有信号量 Pempry 初值为初值为1 Q与与P同步的私有信号量同步的私有信号量Qfull0 Q与与R同步的私有信号量同步的私有信号量Qempty1 R的私有信号量的私有信号量Rfull0P( )：While true doGet message;P(Pempty);Buffer1message；V(Qfull); Q( )：While true doP(Qfull);temp1 Buffer1 ；V(Pempty); P(Qempty); Buffer2temp1；V(Rfull）； R( )：While true doP(Rfull);temp2 Buf