作业题汇总：第2章到第6章

第2章

2-9 有五个作业正等待运行，它们估计运行时间分别为9，6，3，5和x。为了获得最小的平均周转时间，应按照什么顺序运行它们？（你给出的答案应是x的函数）。

答案：
-平均周转时间:$$ 平均周转时间 = \frac{(完成时间 - 到达时间)}{进程个数} = \frac{(等待时间 + 运行时间)}{进程个数} $$
（1）当 $$( x \leq 3 )$$

• 运行顺序为 Px, P3, P5, P6, P9
• $$ T = \frac{(x + (x + 3) + (x + 3 + 5) + (x + 3 + 5 + 6) + (x + 3 + 5 + 6 + 9))}{5} = x + 9.6 $$
  （2）当 $$( 3 < x \leq 5 )$$
• 运行顺序为 P3, Px, P5, P6, P9
• $$ T = \frac{(3 + (3 + x) + (3 + x + 5) + (3 + x + 5 + 6) + (3 + x + 5 + 6 + 9))}{5} = 0.8x + 10.2 $$
  （3）当 $$( 5 < x \leq 6 )$$
• $$ T = 0.6x + 11.2 $$
  （4）——当 $$( 6 < x \leq 9 )$$
• $$ T = 0.4x + 12.4 $$
  （5）当 $$( 9 < x )$$
• $$ T = 0.2x + 14.2 $$

2-12 假定系统有四道作业，它们的提交时间及估计执行时间（以小时为单位）如下表所示。在单道批处理系统中，采用先来先服务、最短作业优先和响应比高者优先的调度的方法，分别计算下表列出作业的平均周转时间。

作业号	提交时刻	估计运行	开始运行时刻			完成时刻
			FCFS	SJN	HRN	FCFS	SJN	HRN
1	8.0	2.0	8.0	8.0	8.0	10.0	10.0	10.0
2	9.0	1.2	10.0	10.8	10.5	11.2	12.0	10.7
3	9.5	0.5	11.2	10.0	10.6	11.7	10.5	11.2
4	10.2	0.3	11.7	10.5	11.7	12.0	10.8	12.0

答案：
-FCFS作业运行顺序：1，2，3，4。
各作业的周转时间Ti和平均周转时间T:
$$
T_1 = 10.0 - 8.0 = 2.0 \
T_2 = 11.2 - 9.0 = 2.2 \
T_3 = 11.7 - 9.5 = 2.2 \
T_4 = 12.0 - 10.2 = 1.8
$$
$$
T = \frac{(T_1 + T_2 + T_3 + T_4)}{4} = \frac{(2.0 + 2.2 + 2.2 + 1.8)}{4} = \frac{8.2}{4} = 2.05
$$

-SJN作业运行顺序：1，3，4，2
各作业的周转时间Ti和平均周转时间T:
$$
T_1 = 10.0 - 8.0 = 2.0 \
T_2 = 12 - 9.0 = 3.0 \
T_3 = 10.5 - 9.5 = 1.0 \
T_4 = 10.8 - 10.2 = 0.6
$$、
$$
T = \frac{(T_1 + T_2 + T_3 + T_4)}{4} = \frac{(2.0 + 3.0 + 1.0 + 0.6)}{4} = \frac{6.6}{4} = 1.65
$$

-HRN 作业运行顺序：1，3，2，4
响应比公式:$$ \text{响应比} = \frac{(\text{等待时间} + \text{运行时间})}{\text{运行时间}} $$
先选择作业1运行，8.00-10.00。当作业1完成时，选择运行:

• 作业2、3的响应比:
  $$
  \text{作业2的响应比} = \frac{((10-9.0) + 1.2)}{1.2} = 1.83 \
  \text{作业3的响应比} = \frac{((10-9.5) + 0.5)}{0.5} = 2.0
  $$
• 由于作业4未到，只能选择作业3运行。
  作业3运行到10.5结束，再计算剩余的作业2和4:
• 作业2、4的响应比:
  $$
  \text{作业2的响应比} = \frac{((10.5 - 9.0) + 1.2)}{1.2} = 2.25 \
  \text{作业4的响应比} = \frac{((10.5 - 10.2) + 0.3)}{0.3} = 2
  $$
• 选择作业2运行
  各作业的周转时间:
  $$
  t1 = 2 \
  t2 = 11.7 - 9.0 = 2.7 \
  t3 = 10.5 - 9.5 = 1 \
  t4 = 12 - 10.2 = 1.8
  $$
  各作业的平均周转时间:
  $$
  T = \frac{(t1 + t2 + t3 + t4)}{4} = \frac{(2 + 2.7 + 1 + 1.8)}{4} = 1.875
  $$

2-13 给出5个批作业A~E，它们几乎同时到达计算中心。”们各自所需的运行时间大约为10，6，2，4和8分钟，优先级分别为3，5，2，1和4。假定5是最高优先级，所有作业都是计算型的，且一次仅运行一个作业的进程，直到它完成对于下面的调度算法忽略它们调度时所用时间，求作业进程的平均周转时间。
(1)轮转法(时间片为2分钟)，按照作业的顺序轮转。
(2)优先级调度法。

答案:
(1)轮转法（假定时间片 = 2 分钟）

• 作业完成的顺序为 C,D,B,E,A

• 开始作业轮转一周需10分钟，

  • 作业C的周转时间: $$ T_C = 6 分钟（10 分钟） $$
  • C完成后，剩下四个作业，轮转一周需8分钟，
  • 作业D的周转时间: $$ T_D = 10 + 6 = 16 分钟（18 分钟） $$
  • D完成后，剩下三个作业，轮转一周需 6 分钟，
  • 作业B的周转时间:$$ T_B = 18 + 4 = 22 分钟（24 分钟） $$
  • B完成后，剩下两个作业，轮转一周需 4 分钟，
  • 作业E的周转时间:$$ T_E = 24 + 4 = 28 分钟（28 分钟） $$
  • E完成后，只剩下作业A, 轮转2分钟
  • 作业A的周转时间:$$ T_A = 28 + 2 = 30 分钟（30 分钟） $$

• 平均周转时间:$$ T = \frac{(6 + 16 + 22 + 28 + 30)}{5} = 20.4 \ \text{分钟}$$

作业	A	B	C	D	E
时间	10	6	2	4	8
优先级	3	5	2	1	4
第 1 轮	8	4	0	2	6
第 2 轮	6	2	-	0	4
第 3 轮	4	-	-	-	2
第 4 轮	2	-	-	-	0
第 5 轮	0	-	-	-	-

（2）优先级调度法

-作业完成顺序为: B, E, A, C, D

• $$T_B = 6 \ \text{分钟}$$
• $$T_E = 6 + 8 = 14 \ \text{分钟}$$
• $$T_A = 14 + 10 = 24 \ \text{分钟}$$
• $$T_C = 24 + 2 = 26 \ \text{分钟}$$
• $$T_D = 26 + 4 = 30 \ \text{分钟}$$

-平均周转时间:
$$T = \frac{(6 + 14 + 24 + 26 + 30)}{5} = 20 \ \text{分钟}$$

作业	A	B	C	D	E
时间	10	6	2	4	8
优先级	3	5	2	1	4

第3章

3-7 设系统中有n+1个进程。其中n个发送进程和1个接收进程。A1、A2、…、An通过一个缓冲区向进程B发消息，B不断取走缓冲区中的消息，不能重复接收同一个消息，而且，每次必须取走发来的每一个消息。刚开始时，缓冲区为空试用P、V操作正确实现进程之间的同步。
示意图：3-7示意图 提取码7568

答案:
现可用PV操作描述如下:
int s1=1; s2=0;
进程B执行的过程为:
begin
P(s2)
从缓冲区BUF取消息
V(s1)
消耗消息
end
若缓冲区容量为m个，这个问题就变为生产者和消费者问题

3-8 有一容量为 100 的循环缓冲区，有多个并发执行进程通过该缓冲区进行通信。为了正确地管理缓冲区，系统设置了两个读写指针分别为 OUT、IN。IN和OUT的值如何反映缓冲区为空还是满的情况?
示意图：3-8示意图 提取码7568

分析:
-首先这里的IN和OUT分别表示读写指针，而不是信号量。
-在系统初启时，环行缓冲区为空，此时IN和OUT都初始化为0。
-当并发进程通过环行缓冲区通信时，写进程不断地写，读进程不断地读，使得读写指针不断变化。
-写进程的速度太快，缓冲区会满:
-读进程的速度太快，缓冲区会空。

答案:
-已知循环缓冲区的容量为100。
-则当 ( IN + 1 ) % 100 = 0UT时，说明缓冲区已满。
-当 IN = OUT 时，说明缓冲区已空。

3-9.有一阅览室，共有100个座位。为了很好地利用它，读者进入时必须先在登记表上进行登记，该表表目设有座位号和读者姓名，离开时再将其登记项擦除。
试问:
(1)为描述读者的动作，应编写几个程序?应设几个进程?它们之间的关系是什么?
(2)试用P、V操作描述读者之间的同步算法。

分析:
-为描述阅览室，用一个登记表来记录使用情况，表中共有100项。
-每当有读者进入阅览室时，为了正确地登记，各读者应互斥使用。
-为此设两个信号量:
-mutex:互斥信号量，用来制约各读者互斥地进行登记，初值为1;
-empty:用来制约各读者能同时进入阅览室的数量资源信号量，初值为100。

int empty=100, mutex=1;
-进入:
-p(empty);
-p(mutex);
-找到一个登记项登记
-v(mutex);
-进入阅览室阅读
-退出:
-p(mutex);
-找到自己的登记项擦除
-v(mutex);
-v(empty);

3-14 假定系统有N个进程共享M个同类资源，规定每个进程至少申请一个资源，每个进程的最大需求不超过M，所有进程的需求总和小于M+N。为什么在这种情况下不会发生死锁?试证明。

证明:

假定会死锁，则根据死锁定义:
-N个进程之间相互等待，至少需要N个单位资源，
-又系统M个资源已分完，故所有进程需求总和大于或等于M+N
-这与题中的所有进程需求总和小于M+N矛盾，
-故假设不成立。
因此，在这种情况下不会死锁。

3-15.设有8个进程 M1，M2,…,M8,它们有如图所示的优先关系，试用P、V操作实现这些进程间的同步。
示意图：3-15 提取码7568

分析：
-设置路径为互斥体
-M1-M2计为:s12
-M1-M3计为:s13
…
-初值为0先执行完的释放互斥体
-后面的才可以执行

答案：
答案图：3-15答案 提取码7568

3-16.设有5个哲学家，共享一张放有5把椅子的圆桌。每人分得1把椅子。但是，桌子上总共只有5支子。哲学家们在肚子饥饿时才试图分两次从两边检起2支筷子就餐。条件:
a.每人只有拿到2 支筷子时，哲学家才能吃饭。
b.如果筷子已在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子。
c.任性的哲学家在自己未拿到2支筷子吃饭之前，决不放下自己手中的筷子。
试问:
(1)什么情况下5个哲学家全部吃不上饭?
(2)描述一种避免有人饿死(永远拿不到2个筷子)的算法。

答案：
（1）每个哲学家拿到1支筷子，同时在等另1支。
（2）一共有五种算法：

• 破坏循环等待:资源按照顺序申请，给5支筷子编号0-4，先申请编号小的筷子，再申请编号大的筷子。
• 破坏循环等待:控制4个以下的哲学家一起进餐，这样总有一个哲学家可以拿到左右两边的筷子。
• 破坏循环等待:控制拿筷子顺序，奇数先拿左边，偶数先拿右边。
• 一次得到所有资源:设置一个临界区，只有一个进程可以进入并获取左右2支筷子。
  • 如果没有2支筷子，就退出临界区等待再次进入。
  • 如果吃的很频繁，可能导致某些哲学家申请不到筷子而饿死。
• 主动释放占有资源:当5个哲学家都拿起左边的筷子时，让偶数编号的哲学家放弃自己拿起的筷子。
  • 这种做法，在资源使用很频繁的时候，可能导致部分线程饿死。

可能吃不上饭的写法

• 筷子是临界资源，在一段时间内只允许一个哲学家使用。

• 一个信号量表示1支筷子，5个信号量构成信号量数组，初值为1。

• 方法1伪代码

  int mutex=1;
  int stick[0]=stick[1]=...=stick[4]=1;
  //第i个哲学家所执行的程序:
  do{
      P(stick[i]);
      P(stick[(i+1)mod5]);
      吃饭
      V(stick[i]);
      V(stick[(i+1)mod5]); 
  }while(1);

• 方法2伪代码

  int semaphore=2,3,4;
  int stick[0]=stick[1]=...=stick[4]=1;
  //第i个哲学家所执行的程序:
  do{
      P(semaphore);
        P(stick[i]);
        P(stick[(i+1)mod5]);
        V(semaphore);
      吃饭
      V(stick[i]);
      V(stick[(i+1)mod5]);
  }while(1);

• 方法3伪代码

  //偶数先拿左边，奇数先拿右边
  //第i个哲学家所执行的程序:
  do{
      P(stick[i+(i%2)]);
      P(stick[(i+(i+1)%2)mod5]);
      吃饭
      V(stick[i+(i%2)]);
      V(stick[(i +(i+1)%2)mod5]);
  }while(1);

• 方法4伪代码

  int stick[0]=stick[1]=...=stick[4]=1;
  //第i个哲学家所执行的程序:
  do{
      ifi>(i+1)%5{
          P(stick[(i+1)mod5]);
          P(stick[i]);
      }
      else{
          P(stick[i]);
          P(stick[i+1]);
          吃饭
          V(stick[i]);
          V(stick[i+1]);
      }
  }while(1);

3-17 在本章前面的读者与写者问题中，是用读者优先解决问题的。试分别用读者与写者公平竞争(无写者时，读者仍遵循多个读者可以同时读)、写者优先的算法解决这个问题.
答案：

int wmutex=1,readcount=0,rmutex=1;
Reader:
    P(rmutex);    //互斥访问readcount
    if readcount==0 then P(wmutex);
      readcount++;
    V(rmutex);
------------
    读文件;
------------
    P(rmutex);
    readcount= readcount-1;
    if readcount==0 then V(wmutex);
    V(rmutex);
Writer: …
    P(wmutex);
    写文件;
    V(wmutex);
    …

解析：
允许多个读进程同时读。当没有读进程正在读时，第一个试图读的读进程需要通过P(wmutex)实现读写互斥;当至少已经有一个读进程在读时，随后的读进程无需等待，可以直接进入。

(1)公平竞争（无写者时，读者仍遵循多个读者可以同时读）

• rmutex互斥共享readcount;
• rwmutex读写互斥，写写互斥
• 读写进程在z上排队。
  int rmutex=1,rwmutex=1, readcount=0;

(2)写者优先
int readcount, writecount;
semaphore rmutex=1,wmutex=1, rwmutex=1, z=1, x=1;
当来了一个写进程时，通过p(x)禁止其后读进程读，直到写进程写完为止。

Reader:
while(1){
    p(z);   //其他读进程在z上排队
    p(x);   //1读进程与1写进程在x上竞争
    p(rmutex);    //读进程互斥访问readcount
    ++readcount;
    if(readcount==1)p(rwmutex);
    v(rmutex);
    v(x);
    v(z);
    read data; //临界区
    p(rmutex);
    --readcount;
    if(readcount==0)v(rwmutex);
    v(rmutex);
}

Writer:
while(1){
    p(wmutex);    //写进程互斥访问writecount
    ++writecount;
    if(writecount==1) p(x);   //1写进程与1读进程在x上竞争
    v(wmutex);    
    p(rwmutex);   //其他写进程在rwmutex上排队
    write data;   //临界区
    v(rwmutex);
    p(wmutex);
    --writecount;
    if(writecount==0) v(x);   //写进程都写完时，通过v(x)允许读进程读
    v(wmutex);
}

附加题:读者写者，规定仅允许5个进程同时读，怎样修改程序?
增加一个资源信号量s，初值为5。即int s=5;

Reader: begin
    P(rmutex);
    readcount=readcount+1;
    if(readcount=-1) then P(rwmutex);
    V(rmutex);
    P(s);
    read file();
    V(s);
    P(rmutex);
    readcount=readcount-1;
    if(readcount==0) then V(rwmutex);
    V(rwmutex);
  end

Writer:
begin
    p(rwmutex);
    write data;
    v(rwmutex);
    …
  end

3-18 有一个理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便坐在椅子上睡觉，当一个顾客到来时，必须唤醒理发师，请求理发;如果理发师正在理发时又有顾客来到，只要有空椅子，他就坐下来等待，如果没有空椅子，他就离开。请为理发师和顾客各编写一段程序来描述他们的同步过程。

方法一：int s1=0,s2=n;
顾客进程:
P(s2);
V(s1);
坐椅子等理发
理发师进程:
P(s1);
给顾客理发
V(s2)

方法二: int customers=0, barber=0, mutex=1, waiting=0;
顾客进程:
P(mutex);
if(waiting<n)
{
waiting++;
V(mutex);
V(customers);
P(barber);
理发
}
else
V(mutex);

理发师进程:
P(customers);
V(barber);
P(mutex);
waiting–;
V(mutex);
理发

3-19 假定系统中只有一类资源，进程一次只申请一个单位的资源，且进程申请的资源数不会超过系统拥有的资源总数。假定进程申请的资源总数为2，且系统资源总数如下，问下列哪些情况会发生死锁？

进程数	资源数					进程数	资源数
(1)	1					(4)	3
(2)	2					(5)	3
(3)	2	3				(6)	4

答案：（2）和（4）会发生死锁。

3-20 系统有同类资源10个，进程P1，P2 和P3 需要该类资源的最大数量分别为8，6，7。它们使用资源的次序和数量如图。

(1) 试给出采用银行家算法分配资源时，进行第5次分配后各进程的状态及各进程占用资源情况。

(2) 在以后的申请中，哪次的申请可以得到最先满足？给出一个进程完成序列。

次序	进程数	资源数					次序	进程数	资源数
(1)	P1	3					(5)	P2	2
(2)	P2	2					(6)	P1	3
(3)	P3	4					(7)	P3	4
(4)	P1	2