第四章
一、问答题
1、什么叫临界资源？什么叫临界区？对临界区的使用应符合哪些规则？（同步机制应遵循的准则是什么？）
2、死锁产生的4个必要条件是什么？它们是彼此独立的吗？
3、何谓死锁？为什么将所有资源按类型赋予不同的序号，并规定所有进程按资源序号递增的顺序申请资源后，系统便不会产生死锁？
4、什么是安全状态？怎么判断系统是否处于安全状态？
5、简述死锁定理和解除死锁的方法。
二、计算和证明
1、当前系统中出现下述资源分配情况：
利用银行家算法，试问如果进程P2提出资源请求Request（1，2，2，2）后，系统能否将资源分配给它？
2、若系统有某类资源m×n+1个，允许进程执行过程中动态申请该类资源，但在该系统上运行的每一个进程对该资源的占有量任何时刻都不会超过m+1个。
当进程申请资源时只要有资源尚未分配完则满足它的申请，但用限制系统中可同时执行的进程数来防止发生死锁，你认为进程调度允许同时执行的最大进程数应该是多少？并说明原因。
3、n个进程共享某种资源R，该资源共有m个，每个进程一次一个地申请或释放资源。
假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m＋n，试证明在这个系统中不可能发生死锁。
4、当前某系统有同类资源7个，进程P，Q所需资源总数分别为5，4。
它们向系统申请资源的次序和数量如表所示。
回答：
问：采用死锁避免的方法进行资源分配，请你写出系统完成第3次分配后各进程占有资源量，在以后各次的申请中，哪次的申请要求可先得到满足?
5、一个计算机系统有6个磁带驱动器4个进程。
每个进程最多需要n个磁带驱动器。
问当n为什么值时，系统不会发生死锁？并说明理由
6、n个进程共享某种资源R，该资源共有m个可分配单位，每个进程一次一个地申请或释放资源单位。
假设每个进程对该资源的最大需求量均小于m，问各进程最大需求量之和至少小于多少，系统不会发生死锁，并证明。
7. 考虑某一系统，它有4类资源R1，R2，R3，R4，有5个并发进程P0，P1，P2，P3，P4。
请按照银行家算法回答下列问题；
⑴各进程的最大资源请求，已分配的资源矩阵和当前资源剩余向量如下图所示，计算各进程的需求向量组成的矩阵。
⑵系统当前是处于安全状态吗？
⑶当进程P2申请的资源分别为（0,3,2,0）时，系统能立即满足吗？
8、假定系统有4个同类资源和3个进程，进程每次只申请或释放一个资源。
每个进程最大资源需求量为2。
请问，这个系统为什么不会发生死锁？
9、考虑这样一种资源分配策略：对资源的申请和释放可以在任何时刻进行。
如果一个进程的资源得不到满足，则考查所有由于等待资源而被阻塞的进程，如果它们有申请进程所需要的资源，则把这些资源取出分给申请进程。
例如，考虑一个有3类资源的系统，Avai1ab1e=(4,2,2)。
进程A申请(2,2,1)，可以满足；进程B申请（1,0,1），可以满足，若A再申请(0,0,1)，则被阻塞（无资源可分）。
此时，若C申请(2,0,0)，它可以分得剩余资源(1,0,0)，并从A已分得的资源中获得一个资源，于是，进程A的分配向量变成：Available=(1,2,1)，而需求向量变成：Need=(1,0,1)。
⑴这种分配方式会导致死锁吗？若会，举一个例子；若不会，说明死锁的哪一个必要条件不成立。
⑵这种分配方式会导致某些进程的无限等待吗？
10、.有3个进程P1、P2和P3并发执行。
进程P1需使用资源r3和r1，进程P2需使用资源r1和r2，进程P3需使用资源r2和r3。
⑴若对资源分配不加限制，会发生什么情况，为什么？
⑵为保证进程能执行到结束，应采用怎样的资源分配策略？
11、设有A B、C三个进程，它们共享十个资源，每个进程最大需求量分别为4，7，8，它们对资源请求的序列如下表：（8分）
⑴请画出执行完序号4时的资源分配矩阵；
⑵为使系统不发生死锁，执行完序号6时，3个进程各处于什么状态，获得多少
同类资源？
⑶按照上题时的状态，系统会发生死锁吗？为什么？
三、综合题
1、如果有三个进程R、W1、W2共享一个缓冲器B，而B中每次只能存放一个数。
当缓冲器中无数时，进程R可以将从输入设备上读入的数存放到缓冲器中。
若存放到缓冲器中的是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的是偶数，则允许进程W2将其取出打印。
同时规定：进程R必须等缓冲区中的数被取出打印后才能再存放一个数；进程W1或W2对每次存入缓冲器的数只能打印一次；W1和W2都不能从空缓冲中取数。
写出这三个并发进程能正确工作的程序。
2、设计一种可以避免死锁的资源分配算法，要求写明数据结构和相应方案或算法。
3、写一个管程，用于实现读者——写着问题，要求写者优先。
4、生产者消费者问题
5、请设计检测资源分配时系统是否安全的安全检测方案。
6、有一个仓库，可以存放A和B两种产品，但要求：1）每次只能存入一种产品（A或B）；2）-N＜A产品数量—B产品数量＜M。
其中，N和M是正整数。
试用同步算法描述产品A与产品B的入库过程。
7、在一个系统中，不采用死锁避免和预防措施，但当死锁发生后需要能够检测出来，请设计一个可行的死锁检测方案。
8、一个数据文件或记录（统称数据对象），可被多个进程共享。
有些读进程要求读，而另一些写进程对数据对象进行写或修改。
允许多个写进程同时读一个共享对象，决不允许一个写进程和其他读进程或写进程同时访问共享对象。
请用信号量或管程为工具，实现读写进程并发的正确管理。
9、假定有一个信箱可存放N封信，当信箱不满时发信者可把信件送入信箱；当信箱中有信时收信者可从信箱中取信。
用指针R，K分别表示可存信和取信的位置，请用信号量来管理这个信箱，使发信者和收信者能正确工作。
10、考虑三个吸烟者进程和一个经销商进程的系统。
每个吸烟者连续不断地做烟卷并抽他做好的烟卷，做一支烟卷需要烟草、纸和火柴三种原料。
这三个吸烟者
分别掌握有烟草、纸和火柴。
经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可以做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。
试设计一个同步算法来描述他们的活动。
11、现有四个进程R1、R2、W1、W2，它们共享可以存放一个数的缓冲器B。
进程R1每次把来自键盘的一个数存入缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数存放到缓冲器B中，供进程W2打印输出。
为防止数据的丢失和重复打印，问怎样用信号量操作来协调这四个进程的并发执行。
12、信号量方法控制进程的执行顺序。
13、a，b两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在ab段外等待；当ab之间无车辆在行驶时，到达a点(或b点)的车辆可以进入ab段，但不能从a点和b点同时驶入，当某方向在ab段行驶的车辆驶出了ab段且暂无车辆进入ab段时，应让另一方向等待的车辆进入ab段行驶。
请用信号量机制为工具，对ab段实现正确管理以保证行驶安全。
14、哲学家就餐问题
15、某寺庙有小和尚和老和尚各若干人，水缸一只，由小和尚提水入缸给老和尚饮用。
水缸可容水10桶，水取自同一口水井中。
水井径窄，每次仅能容一只水桶取水，水桶总数为3个。
若每次入、取水仅为1桶，而且不可同时进行。
试用一种同步工具写出小和尚和老和尚的活动过程。
