进程同步与互斥习题课(最新).ppt

进程同步与互斥习题课进程同步与互斥习题课 河北工业大学河北工业大学 计算机学院计算机学院 李建伟李建伟 利用信号量实现进程间的互斥利用信号量实现进程间的互斥n由于各进程要求共享资源，而有些资源由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互这些资源，进程的这种关系为进程的互斥斥n临界资源：临界资源：critical resourcecritical resource系统中某些资源一次只允许一个进程使系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资用，称这样的资源为临界资源或互斥资源或共享变量源或共享变量临界区（互斥区）：critical section 一个程序片段的集合，这些程序片段分散在不同的进程中，对某个共享的数据结构（共享资源）进行操作 在进程中涉及到临界资源的程序段叫临界区a:=a-1 print(a)a:=a+1 print(a)P1互斥互斥P2互斥互斥If a 0then a:=a+1else a:=a-1P3互斥互斥 进程的互斥进程的互斥（间接作用）（间接作用）互互斥斥例例题题1 设设一一民民航航航航班班售售票票系系统统有有n个个售售票票处处。每每个个售售票票处处通通过过终终端端访访问问系系统统中中的的公公用用数数据据区区，假假定定公公共共数数据据区区中中一一些些单单元元xk(k=1,2,)分分别别存存放放月月日日次次航航班班的的现现存存票票数数。设设P1，P2，Pn表表示示各各售售票票处处的的处处理理进进程程，R1,R2,Rn表表示示各各进进程程执执行行时时所所用用的的工工作单元。作单元。用信号量实现进程间互斥的程序如下：用信号量实现进程间互斥的程序如下：beginS:Semaphore;S=1cobegin Process Pi(i=1,2,n)begin按旅客订票要求找到xk;P(S)Ri=xk;if Ri1 then begin Ri=Ri-1;xk=R1;V(S)输出一张票 end else begin V(S);输出“票已售完”end end;coend;end;互斥例题互斥例题2 2.利用信号量实现进程间的同步利用信号量实现进程间的同步 一般来说，一般来说，信号量初值为信号量初值为 0，两个进程之间的同两个进程之间的同步模型如下：步模型如下：进程进程P1 进程进程P2 L1：P(S)L2：V(S)例例 1 用信号量实现司机和售票员的同步。用信号量实现司机和售票员的同步。设设S1和和S2分分别别为为司司机机和和售售票票员员的的私私用用信信号号量量，初初值值均均为为0，则司机和售票员的同步，则司机和售票员的同步过程描述如下：过程描述如下：例例 2 设设进进程程A、B是是两两个个相相互互合合作作的的进进程程，共共用用一一个个缓缓冲冲区区。进进程程A负负责责从从卡卡片片输输入入机机读读入入卡卡片片送送到到缓缓冲冲区区，进进程程B取取走走缓缓冲冲区区中中的的卡卡片片信信息息进进行行加加工工处处理理。进进程程A在在完完成成将将卡卡片片送送入入缓缓冲冲区区后后，给给进进程程B发发一一信信号号。进进程程B收收到到信信号号后后，取取走走卡卡片片信信息息进进行行加加工工处处理理。反反之之，进进程程B取取走走卡卡片片信信息息后后，给给进进程程A发发一一信信号号，进进程程A再再将将卡卡片片信信息息读读入入缓缓冲冲区区。为为此此，我我们们利利用用两两个个私私用用信信号号量量S1和和S2，其其初初值值均均为为 0，信信号号量量S1表表示示缓缓冲冲区区是是否否有有卡卡片片信信息息，信信号号量量S2表表示示缓缓冲冲区区信信息息是是否否被被取取走走。利利用用P、V操操作作实实施施进程进程A、B的同步过程如下：的同步过程如下：n 读者-写者模型是现代操作系统中典型的进程同步互斥问题，以客户服务器模式为代表的多进(线)程通信系统应用都可以抽象为该模型的不同形式。因此,该模型的算法在这些领域具有重要的应用价值。典型同步互斥问题之一：典型同步互斥问题之一：读者与写者问题读者与写者问题(ReaderWriter Problems)n多个进程共享一个文件,其中只读文件进程称为读者,只写文件进程称为写者.多个读者和多个写者在某个时间段内对该文件资源异步进行读写.为避免文件数据出现丢失修改和读脏数据的情况,对读者和写者的读写操作限制如下.(1)写-写互斥,即不允许多个写者同时对文件进行写操作.(2)读-写互斥,即不允许读者和写者同时对文件分别进行读写操作.(3)读-读允许,即允许多个读者同时对文件进行读操作.读者优先方案n设计思想:读者优先意味着以下两条要求.(i)除非有写者正在写文件,否则读者不需要等待;(ii)仅当无读者时才允许写者使用文件.n读者优先算法实现:PReader(读者进程)P(mutexReaderCount)ReaderCount+If(ReaderCount=1)P(mutexShareFile)V(mutexReaderCount)从文件读信息P(mutexReaderCount)ReaderCount-If(ReaderCount=0)V(mutexShareFile)V(mutexReaderCount)PWriter(写者进程)P(mutexShareFile)向文件写信息V(mutexShareFile)算法分析:限制条件(1)(3)均可以得到满足,是彻底解决读者-写者问题的最基本方案.但读者的高优先级可能造成某个暂时得不到文件的写者由于被随后而来的源源不断的读者插队而长时间挂起,直到全部读者进程运行完毕后,才可以使用文件.读者读者-写者公平竞争方案写者公平竞争方案n设计思想设计思想:读者读者-写者公平竞争的要求读写者公平竞争的要求读者者-写者完全按照先来先服务的原则使用写者完全按照先来先服务的原则使用文件资源，一旦有写者到达，后续的读文件资源，一旦有写者到达，后续的读者都必须等待。不允许出现后来者超越者都必须等待。不允许出现后来者超越先来的等待资源者插队的现象。先来的等待资源者插队的现象。PReader(读者进程)P(mutexRegister)P(mutexReaderCount)ReaderCount+If(ReaderCount=P(mutexShareFV(mutexReaderCount)V(mutexRegister)从文件读信息P(mutexReaderCount ReaderCount-If(ReaderCount=0)V(mutexShareFile)V(mutexReaderCount)PWriter(写者进程)P(mutexRegister)P(mutexShareFile)向文件写信息 V(mutexShareFile)V(mutexRegister)算法分析n限制条件(1)(3)均可以得到满足,新的互斥信号量mutexRegister的引入使得在有写者处于等待状态的情况下,后来的读者进程会由于同写者进程对注册标记的竞争尝试失败而不得不挂起,从而实现了读者-写者间的先来先服务的公平竞争方案.写者优先方案n设计思想:写者优先有以下两条要求.n(i)仅当无写者时才允许读者使用文件;n(ii)唤醒时优先考虑写者.算法实现算法实现:PReader(读者进程读者进程)P(mutexEnhance)P(mutexRegister)P(mutexReaderCount)ReaderCount+If(ReaderCount=1)P(mutexShareFile)V(mutexReaderCount)V(mutexRegister)V(mutexEnhance)从文件读信息从文件读信息 P(mutexReaderCount)ReaderCount-If(ReaderCount=0)V(mutexShareFile)V(mutexReaderCount)PWriter(写者进程写者进程)P(mutexWriterCount)WriterCount+If(WriterCount=1)P(mutexRegister)V(mutexWriterCount)P(mutexShareFile)向文件写信息向文件写信息 V(mutexShareFile)P(mutexWriterCount)WriterCount-If(WriterCount=0)V(mutexRegister)V(mutexWriterCount)算法分析在满足限制条件(1)(3)的前提下,以写者进程为优先考虑对象,如果有写请求发出,则它会在被允许的最快时间内得到响应.其好处是在一个由很多客户端以读权限访问的服务器(如一般的公众服务器)上,如果管理员对服务器的某些内容或配置进行修改的话,那么它的及时性可以得到满足。总结n可由一类进程多次访问,而不同类的进程必须互斥访问资源的控制,是进程控制中常见的一类问题.n读者-写者模型正是这类问题中的一个典型,它给出了对于这类资源的控制方法,即采用一个资源计数变量进行控制,把对于该资源的访问控制变成对变量的访问.同时,资源计数变量作为新的临界资源,也需要用新的信号量对其进行互斥访问控制.练习题1n桌桌子子有有一一空空盘盘，允允许许存存放放一一个个水水果果。爸爸爸爸可可向向盘盘中中放放苹苹果果，也也可可以以向向盘盘中中放放桔桔子子，儿儿子子专专等等吃吃盘盘中中的的桔桔子子，女女儿儿专专等等吃吃盘盘中中的的苹苹果果。规规定定当当盘盘空空时时一一次次只只能能放放一一只只水水果果供供吃吃者者取取用用，请请用用P、V原原语语实实现现爸爸爸爸、儿儿子子、女女儿儿3个并发进程的同步。个并发进程的同步。练习题2n设有三个进程设有三个进程A A、B B、C C，其中其中A A与与B B构成一构成一对生产者与消费者对生产者与消费者(A A为生产者，为生产者，B B为消费为消费者者)，共享一个由，共享一个由n n个缓冲块组成的缓冲个缓冲块组成的缓冲池，池，B B与与C C也构成一对生产者与消费者也构成一对生产者与消费者（此时（此时B B为生产者，为生产者，C C为消费者），共享为消费者），共享另一个由另一个由m m个缓冲块组成的缓冲池。用个缓冲块组成的缓冲池。用P P、V V操作描述它们之间的关系。操作描述它们之间的关系。练习题3n 把把学学生生和和监监考考老老师师都都看看作作进进程程，学学生生有有N N人人，教教师师1 1人人。考考场场门门口口每每次次只只能能进进出出一一个个人人，进进考考场场原原则则是是先先来来先先进进。当当N N个个学学生生都都进进入入考考场场后后，教教师师才才能能发发卷卷子子。学学生生交交卷卷后后可可以以离离开开考考场。教师要等收上来全部卷子后才能离开考场。场。教师要等收上来全部卷子后才能离开考场。n 问共需设置几个进程？问共需设置几个进程？设设置置合合适适的的信信号号量量及及初初值值，试试用用P P、V V操操作作解解决上述问题中的同步和互斥关系决上述问题中的同步和互斥关系。练习题4n进程进程P1和和P2通过两个缓冲区给进程通过两个缓冲区给进程P11、P12、P21、P22传递信息，进程传递信息，进程P11、P12取进程取进程P1的信息，进程的信息，进程P21、P22取取进程进程P2的信息。假定这两个缓冲区一样的信息。假定这两个缓冲区一样大小，所要传递的信息也与缓冲区一样大小，所要传递的信息也与缓冲区一样大，同一时刻只能由一个进程往缓冲区大，同一时刻只能由一个进程往缓冲区中送信息或取信息。试用中送信息或取信息。试用PV操作来实现操作来实现这这6个进程之间的同步与互斥关系，只要个进程之间的同步与互斥关系，只要求写出进程求写出进程P1与与P11的同步算法。的同步算法。