第四章 一、问答题
1、同步机制应遵循的准则是什么？
2、死锁产生的4个必要条件是什么？它们是彼此独立的吗？ 3、简述死锁的定义和死锁产生的原因。 4、简述死锁定理和解除死锁的方法。
5、什么是安全状态？怎么判断系统是否处于安全状态？ 6、同步机制应遵循的准则是什么？
7、死锁产生的4个必要条件是什么？它们是彼此独立的吗？ 二、计算题（共20分）
1、当前系统中出现下述资源分配情况：
P0 P1 P2 P3 P4 Allocation 0 1 1 0 0 0 0 3 3 0 3 0 5 3 1 2 0 4 2 4 0 1 2 0 0 Need 0 7 3 6 6 1 5 5 5 5 2 0 6 2 6 1 Available 6 2 2 利用银行家算法，试问如果进程P2提出资源请求Request（1，2，2，2）后，系统能否将资源分配给它？
2、当前某系统有同类资源7个，进程P，Q所需资源总数分别为5，4。它们向系统申请资源的次序和数量如表所示。回答：
次序 1 2 3 4 5 6
进程 Q P Q P P Q 申请量 2 1 1 3 2 1 问：采用死锁避免的方法进行资源分配，请你写出系统完成第3次分配后各进程占有资源量，在以后各次的申请中，哪次的申请要求可先得到满足?
3、一个计算机系统有6个磁带驱动器和4个进程。每个进程最多需要n个磁带驱动器。问当n为什么值时，系统不会发生死锁？并说明理由
4、 若系统有某类资源m×n+1个，允许进程执行过程中动态申请该类资源，但在该系统上运行的每一个进程对该资源的占有量任何时刻都不会超过m+1个。当进程申请资源时只要有资源尚未分配完则满足它的申请，但用限制系统中可同时执行的进程数来防止发生死锁，你认为进程调度允许同时执行的最大进程数应该是多少？并说明原因。
5、设系统中有3种类型的资源A、B、C和5个进程P0、P1、P2、P3、P4，A资源的数量为10，B资源的数量为5，C资源的数量为7。在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。（12分）
P0P1 P2 P3 P4 A 7 3 9 2 4 Max B 5 2 0 2 3 C 3 2 2 2 3 Allocation A B C 0 2 3 2 0 1 0 0 1 0 0 0 2 1 2 A 7 1 6 0 4 Need B 4 2 0 1 3 C 3 2 0 1 1 Available A B C 3 3 2 ①. T0时刻是否为安全状态？若是，请给出安全序列。
②在T0时刻若进程P1发出资源请求Request（1，0，2），是否能够实施资源分配？
③在②的基础上P4发出资源请求Request（3，3，0），是否能够实施资源分配？ ④在③的基础上P0发出资源请求Request（0，2，0），是否能够实施资源分配? 6、n个进程共享某种资源R，该资源共有m个，每个进程一次一个地申请或释放资源。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m＋n，试证明在这个系统中不可能发生死锁。
五、应用题
1、如果有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数。当缓冲器中无数时，进程R可以将从输入设备上读入的数存放到缓冲器中。若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。同时规定：进程R必须等缓冲区中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器的数只
能打印一次；W1和W2都不能从空缓冲中取数。写出这三个并发进程能正确工作的程序。
2、设计一种可以避免死锁的资源分配算法，要求写明数据结构和相应方案或算法。
3、复印室里有一个操作员为顾客复印资料，有5把椅子供顾客休息等待复印。如果没有顾客，则操作员休息。当顾客来到复印室时，如果有空椅子则坐下来，并唤醒复印操作员；如果没有空椅子则必须离开复印室。利用信号量机制解决该同步互斥问题。
4、a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。请用信号量机制为工具，对ab段实现正确管理以保证行驶安全。
5、某系统五个合作的进程前驱图如下，请用信号量方法控制它们的执行，以确保它们的执行顺序，请写出类c算法。
P2
P1 P4 P5 P3 5、一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。
6、现有四个进程R1、R2、W1、W2，它们共享可以存放一个数的缓冲器B。进程R1每次把来自键盘的一个数存入缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数存放到缓冲器B中，供进程W2打印输出。为防止数据的丢失和重复打印，问怎样用wait,signal操作来协调这四个进程的并发执行。
7、系统中有4种类型的资源A、B、C、D和5个进程P0、P1、P2、P3、P4，当前系统出现下表所示资源分配情况：
P0 P1 P2 P3 P4
试问：
①该状态是否安全？分析说明。
②如果进程P2提出资源请求Request（1，2，2，2）后，系统能否将资源分配给它？
8、某寺庙有小和尚和老和尚各若干人，水缸一只，由小和尚提水入缸给老和尚饮用。水缸可容水10桶，水取自同一口水井中。水井径窄，每次仅能容一只水桶取水，水桶总数为3个。若每次入、取水仅为1桶，而且不可同时进行。试用记录型信号量机制写出小和尚和老和尚的活动过程。
9、考虑三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷，做一支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可以做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。试设计一个同步算法来描述他们的活动。
10、假定有一个信箱可存放N封信，当信箱不满时发信者可把信件送入信箱；当信箱中有信时收信者可从信箱中取信。用指针R，K分别表示可存信和取信的位置， 请用信号量来管理这个信箱，使发信者和收信者能正确工作。
11、n个进程共享某种资源R，该资源共有m个，每个进程一次一个地申请或释放资源。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之
Allocation A 0 1 1 0 0 B 0 0 3 3 0 C 3 0 5 3 1 D 2 0 4 2 4 A 0 1 2 0 0 Need B 0 7 3 6 6 C 1 5 5 5 5 D 2 0 6 2 6 A 1 Available B 6 C 2 D 2