1、进程管理习题课,重点：用P、V原语实现同步与互斥,本章小结,进程是系统分配资源的基本单位,是一个具有独立功能的程序段对某个数据集的一次执行活动。为什么要引入进程的概念是由操作系统的资源有限性和处理上的并行性以及系统用户的执行起始时间的随机性所决定的。进程具有动态性、并发性等特点。进程动态特性的是进程状态的变化。进程要经历创建、等待资源、就绪准备执行,以及执行和执行后释放资源消亡等几个过程和状态。进程的状态转换要由不同的原语执行完成。,本章小结,P78,进程的并发特性反映在进程对资源的竞争以及由资源竞争所引起的对进程执行速度的制约。这种制约可分为直接制约和间接制约。直接制约是被制约进程和制约进程
2、之间,存在着使用对方资源的需求,只有制约进程执行后,被制约进程才能继续往前推进。具有固定的执行顺序间接制约是被制约进程共享某个一次只能供一个进程使用的系统资源,只有得到该资源的进程才能继续往前推进,其他进程在获得资源进程执行期间不允许交叉执行。没有固定的执行顺序。操作实现：间接制约可利用加锁法和P,V原语操作实现。直接制约既可用P,V原语实现,也可用其他互相传递信号的方式实现。,进程上下文：一个进程的静态描述是处理机的一个执行环境,被称为进程上下文。进程上下文由以下部分组成：PCB(进程控制块)、正文段和数据段以及各种寄存器和堆栈中的值。寄存器中主要存放将要执行指令的逻辑地址,执行模式以及执行
3、指令时所要用到的各种调用和返回参数等。而堆栈中则存放CPU现场保护信息、各种资源控制管理信息等。进程通信：进程间通信又可分为传送控制信号的低级通信和大量传送数据的高级通信。通信方式来看,又可分为主从式、会话式、消息与邮箱方式、以及共享虚存方式。,本章小结(续),P79,常用的死锁排除方法是检测与恢复方法。造成死锁：无论是互相通信的进程或是共享某些不同类型资源的进程,都可能因通信顺序不当或资源分配顺序不当而造成死锁。死锁是一种因各并发进程等待资源而永久不能向前推进的系统状态。排除死锁的方法是预防、回避、检测与恢复三种。线程是进程内的一段程序的基本调度单位。线程可分为用户级线程和系统级线程。用户级
4、线程的管理全部由线程库完成,与操作系统内核无关。线程组成由寄存器、堆栈以及程序计数器等组成,同一进程的线程共享该进程的进程空间和其他所有资源。线程主要用于多机系统以及网络系统的操作系统中。,本章小结(续),P79,第一题,一、用P、V操作描述前趋关系。P1、P2、P3、P4、P5、P6为一组合作进程，其前趋图如图所示，试用P、V操作描述这6个进程的同步。,第二题,二、生产者-消费者问题 它描述了一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投放产品，消费者从中取得产品。生产者-消费者问题是许多相互合作进程的一种抽象。我们把一个长度为n的有界缓冲区(n0)与一群生产者进程P
5、、P、Pm和一群消费者进程C、C、Ck联系起来，如图所示。提取物品。,第二题（续）,假定这些生产者和消费者是互相等效的。只要缓冲区未满，生产者就可以把产品送入缓冲区，类似地，只要缓冲区未空，消费者便可以从缓冲区中取走物品并消耗它。生产者和消费者的同步关系将禁止生产者向满的缓冲区输送产品，也禁止消费者从空的缓冲区中,第三题（选择）,三、在操作系统中，进程是一个具有一定独立功能的程序在某个数据集上的一次。A等待活动 B运行活动 C单独操作 D关联操作 答：B,第四题（选择）,四、多道程序环境下，操作系统分配资源以为基本单位。A程序 B指令 C进程 D作业 答：C,第五题（选择）,五、对于两个并发进
6、程，设互斥信号量为mutex，若mutex=O，则。A.表示没有进程进入临界区 B.表示有一个进程进入临界区 C.表示有一个进程进入临界区，另一个进程等待进入 D.表示有两个进程进入临界区 答：B,第六题（选择）,六、两个进程合作完成一个任务。在并发执行中，一个进程要等待其合作伙伴发来消息，或者建立某个条件后再向前执行，这种制约性合作关系被称为进程的。A.同步 B互斥 C.调度 D执行 答：A,第七题（选择）,七、为了进行进程协调，进程之间应当具有一定的联系，这种联系通常采用进程间交换数据的方式进行，这种方式称为。A.进程互斥 B进程同步 C.进程制约 D进程通信 答：D,第八题,八、在测量控
7、制系统中，数据采集任务把所采集的数据送入一单缓冲区;计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。,分析,分析及相关知识 在本题中采集任务与计算任务共用一个单缓冲区当采集 任务采集到一个数据后，只有当缓冲区为空时才能将数据送入缓冲区中存放，否则应等待缓冲区腾空;当缓冲区中有数据时，计算任务才能从缓冲区中取出数据进行计算，否则也应等待。,答案,int Se=l;int Sf=0;main()cobegin get();compute();coend get()while(采集工作未完成)采集一个数据：p(Se);将数据送入缓冲区中;v(Sf);,co
8、mpute()while(计算工作未完成)p(Sf);从缓冲区中取出数据;v(Se);进行数据计算;,第九题,九、下图给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关系，并用P、V操作描述它。,第十题,十、桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。P37,分析,分析及相关知识 在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是桔子，则允许儿
9、子吃，女儿必须等待;若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。,答案,int S=1;int Sa=0；int So=0；main()cobegin father();son();daughter()：coend father()while(1)p(S);将水果放入盘中;if(放入的是桔子)v(So)：else v(Sa);,son()while(1)p(So);从盘中取出桔子;v(S);吃桔子;daughter()while(1)p(Sa);从盘中取出苹果;
10、v(S);吃苹果;,十一题,十一、(华中理工大学1999年试题)设公共汽车上，司机和售票员的活动分别是：p41 司机的活动：启动车辆：正常行车;到站停车;售票员的活动：关车门;售票：开车门;在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系?用信号量和P、V操作实现它们的同步。,分析,在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。因此司机启动车辆的动作必须与售票员关车门的动作取得同步;售票员开车门的动作也必须与司机停车取得同步。,答
11、案,int s1=0;int s2=0;driver()while(1)p(s1);启动车辆;正常行车;到站停车;v(s2);,busman()while(1)关车门;v(s1);售票;p(s2);开车门;上下乘客;,十二题,十二、设有一个发送者进程和一个接收者进程，其流程图如图所示。s是用于实现进程同步的信号量，mutex是用于实现进程互斥的信号量。试问流程图中的A、B、C、D四框中应填写什么?假定缓冲区有无限多个，s和mutex的初值应为多少?p42,分析,分析及相关知识发送者进程与接收者进程之间的同步关系是：发送者进程生成的信息送入消息链中，接收者进程从消息链中接收信息;由于发送者进程产
12、生一个消息并链入消息链后用V操作增加消息计数并唤醒接收者进程，这表示发送者进程和接收者进程是通过信号量s实现同步的，因此接收者进程应该在取信息之前先使用一个P操作来查看消息链上是否有消息，若无消息则阻塞自己;另外，发送者和接收者对消息链的访问应使用信号量进行互斥，即在访问前使用P操作，在访问后使用V操作。,答案,A框 P(mutex)B框 V(mutex)C框 P(s)D框 P(mutex)开始时，消息链上没有可供接收的信息，所以s的初值为0;互斥信号量mutex的初值应为1。,十三题,十三、(北京大学1990年试题)p46 写出P、V操作的定义。有三个进程PA、PB和PC合作解决文件打印问题
13、：PA将文件记录从磁盘读入主存 的缓冲区1，每执行一次读一个记录;PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。,分析,分析及相关知识 信号量是一个确定的二元组(s，q)，其中s是一个具有非负初值的整型变量，q是一个与s相关联的初始状态为空的队列整型变量s表示系统中某类资源的数目，当其值大于0时，表示系统中当前可用资源的数目;当其值小于0时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目除信号量的初值外，信号量的值仅能由P操作和V操作改变。,答案,P操作记为
14、P(S)，其中S为一信号量，它执行时主要完成下述动作：S=S-1 若S0，则进程继续运行。若S0，则进程继续执行。若S0，则从信号量等待队列中移出队首进程，使其变为就绪状态。,十四题,十四、设有8个程序progl、prog2、prog8。它们在并发系统中执行时有如图所示的制约关系，试用P、V操作实现这些程序间的同步。P48,分析,由图表明开始时，progl及prog2先执行。当progl和prog2都执行完后，prog3、prog4、prog5才可以开始执行。prog3完成后，prog6才能开始执行。prog5完成后，prog7 才能开始执行。prog6、prog4、prog7都结束后，pro
15、g8才可以开始执行。为了确保这一执行顺序，设7个同步信号量f1、f7分别表示程序progl、prog7是否执行完，其初值均为0。,十五题,十五、(北京大学1991年试题)有一个仓库，可以存放A和B两种产品，但要求：(1)每次只能存入一种产品(A或B);(2)-N(A产品数量一B产品数量)M。其中，N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。,分析,分析及相关知识 本题给出的第一个条件是临界资源的访问控制，可用一个互斥信号量解决该问题。第二个条件可以分解为：-NA产品数量一B产品数量 A产品数量一B产品数量M 也就是说，A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比
16、B产品的数量多M个以上,分析,在本题中，我们可以设置两个信号量来控制A、B产品的存放数量，sa表示当前允许A产品比B产品多入库的数量，即在当前库存量和B产品不入库的情况下，还可以允 许sa个A产品入库;sb表示当前允许B产品比A产品多入库的数量，即在当前库存量和 A产品不入库的情况下，还可以允许sb个B产品入库。初始时，sa为M一1，sb为N一1，当往库中存放入一个A产品时，则允许存入B产品的数量也增加1;当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。,十六题,十六、(南开大学1997年试题)在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但
17、其中有一个小的安全岛M(同时允许两辆自行车停留)，可供两辆自行车已从两端进入小路情况下错车使用，如图所示。试设计一个算法使来往的自行车均可顺利通过。,分析,由于小路中间的安全岛M仅允许两辆自行车停留，本应该作为临界资源而设置信号量，但仔细分析可以发现：在任何时刻进入小路的自行车最多不会超过两辆(南开和天大方向各一辆)，因此，无需为安全岛M设置信号量。在路口S处，南开出发的若干自行车应进行进入小路权的争夺，以决定谁能够进入小路SK段，为此，设置信号量S(初值为1)来控制南 开路口资源的争夺。同理，设置信号量T(初值为1)来控制天大路口资源的争夺。此外，小路SK段仅允许一辆自行车通过，所以设置信号
18、量SK(初值为1)来进行控制，而对于LT 段则设置信号量LT(初值为1)进行控制。,答案,totian()/*从南开大学去天津大学*P(S)；/*与其他南开方向的争夺路口S使用权*P(SK)；/*同对面来的争夺SK路段的使用权*通过SK路段；进入安全岛M；V(SK)；/*一旦进入安全岛M便可释放SK*P(LT)；/*同对面来的争夺LT路段*通过LT路段：V(LT)；*已通过LT路段释放路段LT*V(S)/*已经通过小路，允许在路口S等待的自行车争夺再次进入S的 使用权*,十七题,十七、(中国科学院软件研究所1995年试题)多个进程共享一个文件，其中只读文件的称为读者，只写文件的称为写者。读者可
19、以同时读，但写者只能独立写。请：说明进程间的相互制约关系，应设置哪些信号量?用P、V操作写出其同步算法。修改上述的同步算法，使得它对写者优先，即一旦有写者到达，后续的读者必须等 待。而无论是否有读者在读文件。,分析,本题前两问是经典读者写者问题，第三问对读者写者问题加了一些限制，即使算法对写者优先。进程间的相互制约关系有三类：一是读者之间允许同时读;二是读者与写者之间须互斥;三是写者之间须互斥。为了解决读者、写者之间的同步，应设置两个信号量和一个共享变量;读互斥信号量 rmutex，用于使读者互斥地访问共享变量count，其初值为1;写互斥信号量wmutex，用于实现写者与读者的互斥及写者与写
20、者的互斥，其初值为1;共享变量count，用于记录当前正在读文件的读者数目，初值为0。,答案,为了提高写者的优先级，增加一个信号量s，用于在写进程到达后封锁后续的读者。其控制流程如下：int rmutex=1;int wmutex=l;int count=0;int s=1;,reader()p(s);p(rmutex);if(coun=0)p(wmutex);count+;v(rmutex);v(s);读文件;p(rmutex);count-;if(count=0)v(wmutex);v(rmutex);,答案,writer()p(s);p(wmutex);写文件;v(wmutex);v(S);,
