2011-12操作系统复习题及答案(3)

? 进程同步7：一售票厅只能容纳300人，当少于300人时，可以进入；否则，需在

外等候。若将每一个购票者作为一个进程，请用wait、signal操作给出进程程序结构，并写出信号量及初值。

? 进程同步8：针对如下所示的优先图，使用信号量给出正确的程序结构。

S1 S4 S2 S5 S6 S3

(二) 进程调度与死锁

? 进程调度与死锁1 ：5个进程，3种资源，某个时刻，资源分配情况如下： Allocation Max Available

A B C A B C A B C P0 0 1 0 7 5 3 ,3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3

问：系统是否处于安全状态？如果P1再提出请求1个A类，2个C类资源，是否该批准？

? 进程调度与死锁2：假设一个系统有某类资源m个，被n个进程共享，进程每次只

请求和释放一个资源，证明只要系统满足下面两个条件，就不会发生死锁： (1) 每个进程需求资源的最大值在1到m之间； (2) 所有进程需要资源的最大值的和小于m+n。

证明：

设每个进程最多申请资源x个（1≤x≤m），

最坏情况下，为进程分配资源数为n（x-1） 。系统剩余资源为m- n（x-1） 。 只要 m- n（x-1）≥1；则系统不会出现死锁。整理得： nx ≤m+n-1，所以nx ≤m+n时，不会引起死锁

? 进程调度与死锁3：和死锁1相同，系统的资源数量为：（10，5，7）。经过一段时

间的分配后，资源分配与占用情况见下表所示。 MAX 进程 P0 P1 A B C 7 5 3 3 2 2 Allocation A B C 0 1 0 2 0 0 Need Available A B C 7 4 3 3 3 2 1 2 2 A B C

P2 P3 P4 9 0 2 2 2 2 4 3 3 3 0 2 2 1 1 0 0 2 6 0 0 0 1 1 4 3 1 分析进程P0的请求(0, 1, 0)能否满足？

? 进程调度与死锁4：假设系统有4个相容类型的资源被3个进程共享，每个进程最

多需要2个资源，证明这个系统不会死锁。

假设每个进程都需要2个资源，3个进程先每个进程分一个资源，共需3个资源，这时候只需要再有一个资源就能保证至少有一个进程能够执行，系统即不会死锁

? 进程调度与死锁5：有三个进程P1、P2和P3并发工作。进程P1需要资源S3和

S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3，回答： (1) 若对资源分配不加限制，会发生什么情况？为什么？

(2) 为保证进程正确地工作，应采用怎样的资源分配策略？为什么？

1) 若对进程间的资源分配不加限制，可能会发生死锁。若进程P1、P2和P3分别获得资源S3、S1和S2，后再继续申请资源时会导致进程间的“循环等待”，并且这种状态将永远持续下去。

(2) 为保证系统处于安全状态，应采用下面列举3种资源分配策略： 1) 采用静态资源分配：由于执行前已获得所需全部资源，故不会出现占有资源又等待资源的现象，从而避免资源的循环等待。

2) 采用资源按序分配，避免出现循环等待资源的现象。 3) 采用银行家算法进行分配资源前的检测。

? 进程调度与死锁6：有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运

行时间为10，6，2，4，8min。其优先级分别为3，5，2，1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。

(1) 先来先服务（按A，B，C，D，E）算法。 (2) 优先级调度算法。 (3) 时间片轮转算法。

? 进程调度与死锁7：设某系统进程的状态有创建状态、运行状态、阻塞状态、延迟

状态和完成状态。试画出系统的进程状态变迁图，并说明状态变迁可能的原因。