操作系统课后习题答案

答：在运行I/O操作前，I/0限制的程序只运行很少数量的计算机操作。而CPU约束程序一般来说不会使用很多的CPU。另一方面，CPU约束程序会利用整个时间片，且不做任何阻碍I/O操作的工作。因此，通过给I/O约束程序优先权和允许在CPU 约束程序之前运行，可以很好的利用计算机资源。

5.3考虑用于预测下一个CPU区间长度的指数平均公式。将下面的值赋给算法中的参数的含义是什么？ A.a=0 且 t0=100 ms

B.a=0.99 且t0=10 ms

答：当a=0且t0=100 ms时，公式总是会预测下一次的CPU区间为100毫秒。当 a=0.99且t0=10毫秒时，进程将给予更高的重量以便能和过去相比。因此，调度算法几乎是无记忆的，且简单预测未来区间的长度为下一次的CPU执行的时间片。

5.4考虑下面一组进程，进程占用的CPU区间长度以毫秒来计算：

进程

P1 P2 P3 P4 P5

区间时间 10 1 2 1 5

优先级 3 1 3 4 2

假设在0时刻进程以P1、P2、P3、P4、P5的顺序到达。

a.画出 4 个 Gantt 图分别演示用 FCFS、SJF、非抢占优先级（数字小代表优先级高）和 RR（时间片＝1）算法调度时进程的执行过程。 b.每个进程在每种调度算法下的周转时间是多少？ c.每个进程在每种调度算法下的等待时间是多少？ d.哪一种调度算法的平均等待时间最小？ 答a.

FCFS：

P1 0 SJF： P2 0 1 P4 2 P3 4 P5 9 P1 19 10 P2 11 P3 13 P4 14 P5 19 非抢占优先级： P2 0RR：

P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 0

b.周转时间：

P1 P2 P3 P4 P5 FCFS 10 11 13 14 19 SJF 19 1 4 2 9 非抢占优先级 16 1 18 19 6 RR 19 2 7 4 14 P5 1 6 P1 16 P3 P4 18 19 P1 19 1 2 3 4 5 6 7 8 9 10 11 12 13 14

c.等待时间：

P1 P2 P3 P4 P5 FCFS 0 10 11 13 14 SJF 9 0 2 1 4 非抢占优先级 6 0 16 18 2 RR 9 1 5 3 9

d.从上表中可以看出SJF的等待时间最小。

5.5下面哪种调度算法能导致饥饿? a.先到先服务 b.最短作业优先 c.轮转法 d.优先级

答：最短作业优先和优先级调度算法能导致饥饿。因为对于优先级较低的作业来说，最短作业优先和优先级调度算法会使其无穷等待CPU，长期得不到调用，这就导致了饥饿问题，也叫无穷阻塞。

5.9考虑下面的动态改变优先级的抢占式优先级调度算法。大的优先级数代表高优先级。当一个进程在等待 CPU 时（在就绪队列中，但未执行），优先级以α速率改变；当它运行时，优先级以β速率改变。所有的进程在进入等待队列时被给定优先级为 0。参数α 和β可以进行设定得到许多不同的调度算法。 a.β>α>0是什么算法？ b.α<β<0时是什么算法？

答：a.FCFS先到先服务调度算法。当进程进入到就绪队列时，其PCB链接到队列的尾部，优先级以α速率改变；当CPU空闲时，CPU分配给位于队列头的进程，优先级加快，以β速率改变，接着该运行进程从队列中删除。

b.LIFO后进先服务调度算法。同上，当进程进入到就绪队列时，优先级以α速率改变，等待后进的进程先调度，之后轮到该进程时，优先级加快，以β速率改变，完成调度。

6.1第一个著名的正确解决两个进程的临界区问题的软件方法是Dekker设计的。两个进程P0和P1共享以下变量：

boolean flag[2]; int turn;

进程Pi(i==0或1)的结构见6.25，,另一个进程为Pj(j==0或1)。证明这个算法满足临界区问题的所有三个要求。 do{

flag[i]=TRUE; while(flag[j]){

/*initially false*/

if(turn==j){

flag[i]=false; while(turn==j) ; //do nothing flag[i]= TRUE;

} }

//critical section turn==j； flag[i]=FALSE; //remainder section }while(TRUE);

图6.25 Dekker算法中的进程pi结构 答：这个算法满足临界区问题的三个要求： （1）

在标记和返回变量的使用中，互斥条件是保证的。如果两个进程将它们的标识设为

真，那么只有一个进程会成功进行，即轮到的那个进程。当另一个进程更新它的返回变量时，等待的那个进程只能进入它的临界区域。 （2）

就绪的进程，通过标志，返回变量。这个算法没有提供严格的交替。如果一个进程

想要进入它们的临界区域，它可以将它的标识设为真，然后进入它们的临界区域。当退出它的临界区域，它可以设置转向其他进程的值。如果这个进程想要在其他进程之前再次进入它的临界区域，它会重复这样的进程：进入它的临界区域，在退出时转向另一个进程。 （3）

在双 T 返回变量的使用过程中，临界等待受阻。假设两个进程想要进入它们的责

任所在的临界区域。它们都将它们的标志的值设为真；而只有轮到的那个线程可以执行；其他的线程处于等待状态。如果临界等待没有受阻，当第一个进程重复“进入-退出”它的临界区域这一过程。Dekker 算法在一个进程中设置一个转向另一个进程的值，从而保证另一个进程接下来进入它的临界区域。

6.2 第一个将等待次数降低到n-1范围内的正确解决n个进程临界区问题的软件解决方法是由Eisenberg和Mcguire设计的。这些进程共享以下变量：

enum pstate{idle, want in, in cs}; pstate flag[n]; int turn;

flag的所有成员被初始化为idle；turn的初始值无关紧要（在0和n-1之间）。进程pi的结构见图6.26。试证明这个算法满足临界区问题的所有三个要求。

do{

while(TRUE){ }

flag[i] = in cs; j = 0;

while((jj++;

flag[i] = want in; j = turn; while(j != i){

if(flag[j] != idle){

j = turn;

else

j = (j+1)%n;

if((j >= n) && (turn == I || flag[turn] == idle)) }

break;

//critical section

j =(turn + 1)%n; while(flag[j] == idle)

j = (j + 1)%n;

turn = j; flag[i] = idle;

//remainder section

}while(TRUE);

图6.26 Eisenberg和McGuire算法中的进程pi结构

答：（1）互斥：注意到一个进程只有在下列条件满足时才能进入临界区域：没有其他进程在 CS 中有设置的标识变量。保证没有两个进程同时进入临界区域。

（2）有空让进:当多进程同时在 CS 中设置它们的标识变量时，检查是否有其他进程在 cs 中设置标识变量。这种情况发生时，所有的进程意识到这里存在进程竞争，在外层 while(1)的循环下进入下一次迭代，重置它们的标识变量到 want 中。这个进程仅能进入临界区域。

（3）有限等待：当进程 k 在打算进入临界区域时，它的标识不再置为空闲。任何序号不在轮次和 k 之间的进程不能进入临界区域。与此同时，所有序号落在轮次和 k 之间且又想要进入临界区域的进程能够进入临界区域（这是基于系统一直在进步的事实），这个轮次值变得越来越接近 k。最后，要么轮次变为 k，要么没有哪些序号在轮次和 k 之间的进程，这样进程 k 就进入临界区域了。

6.9试说明如果wait()和signal()操作不再是原子化操作，那么互斥可能是不稳定的。 答：买卖操作自动递减和信号量有关的值。如果两个买卖操作在信号量的值为 1 的信号量上执行，而且这两种操作不是自动执行的，那么这两个操作在进展中会递减信号量的值，从而干扰互斥。

6.11理发店问题。一家理发店有一间有n把椅子的等待室和一间有一把理发椅的理发室。如果没有顾客，理发师就去睡觉。如果顾客来时所有的椅子都有人，那么顾客就会离去。如果理发师在忙，而又有空闲的椅子，那么顾客会坐在其中一个空闲的椅子上。如果理发师在睡觉，顾客会摇醒他。编写一个程序来协调理发师和顾客。

答：当系统中某一进程使用某一资源时，可以看作是消耗，且该进程称为消费者。而当某个进程释放资源时，则它就相当一个生产者。因此此题可看作是n个生产者和1个消费者问题。顾客作为生产者，每到来一个就使计数器count增加1，以便让理发师理发（相当于消费）至最后一个顾客（相当于产品）。并且，第1个到来的顾客应负责唤醒理发师；如果不是第1个到达的顾客，则在有空椅子的情况下坐下等待，否则离开理发店（该消息可由计数器count获得）,所以可以通过一个有界缓冲区把理发师和顾客联系起来通过对信号进行P、V操作来实现有关问题和相关描述。

控制变量waiting 用来记录正在等候顾客的理发师数；

信号量customers用来记录等候理发的顾客数，并用作阻塞理发师进程； 信号量barbers用来记录正在等候顾客的理发师数，并用作阻塞顾客进程。 信号量mutex用于互斥。 初始化：

int long waiting(0);//正在等待的顾客的数目 customers,barbers,mutex:semaphore; customers:0;

barbers:=1; waiting:=0; mutex:=NULL;

理发师进程： barber() begin

顾客进程：

do{

P(customers)

;//若无顾客，理发师睡眠 p(mutex) ;//进程互斥 waiting-- ;//等候顾客减1 V(barbes)

;//理发师为下一个顾客理发 V(mutex) ;//开放临界区 cut-hair() ;//正在理发

}while(TURE)//是否还有顾客

customer() begin

do{

P(mutex);//进程互斥 if(waiting){

waiting++;//等待顾客数加1

} else

V(customers);//唤醒理发师 V(mutex);//开放临界区

P(barbers);//理发师没空，顾客等候 get-haircut;//顾客准备理发

V(utex);//无空闲位，顾客离开

}while(TRUE)

6.15试论述读者-写者问题的操作公平性及吞吐量，并设计一个新方法解决读者-写者问题且不会产生饥饿。

答：读者-作者问题中吞吐量是受利益多的读者所影响的，而不是让一个作家独占式地获得。另一个方面，有利于读者则可能会导致饥饿的作者。在读者-写者问题中能够通过保持和等待进程有关的时间来避免。当作者完成他的任务，那么唤醒那些已经等了最长期限的进程。当读者到达和注意到另一个读者正在访问数据库，那么它只有在没有作者等待的情况下才能进入临界区域。