计算机操作系统算法题（最全）(5)

17

N=0； V(S); Until false;

某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：

（1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。

（2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。 Cobegin PROCESS Pi(i=1,2,…) Begin

进入售票厅； 购票； 退出； End; Coend

若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）。

此题答案为：售票厅问题解答如下：

18

（1）定义一信号量S，初始值为20。 S>0 S的值表示可继续进入售票厅的人数； S=0 表示售票厅中已有20名购票者； S<0 |S|的值为等待进入售票厅中的人数。 （2）上框为P(S)，下框为V(S)。

（3）S的最大值为20，S的最小值为20－N，N为某一时刻需要进入售票厅的最多人数。

200362. 在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？

此题答案为：答：（1）批处理系统中的作业调度算法有：先来先服务算法（FCFS）、短作业优先算法（SJF）、优先级调度算法（HPF）和高响应比优先算法（RF）。批处理系统的进程调度算法有：先进先出算法（FIFO）、短进程优先算法（SPF）、优先级调度算法（HPF）和高响应比优先算法（RF）。

（2）分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。

（3）实时系统中只设有进程（不设作业调度），其进程调度算法调度有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统；后者用于时间要求严格的实时系统。后者又可细分为：非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。

19

注意，一个纯粹的实时系统是针对特定应用领域设计的专用系统。作业提交的数量不会超过系统规定的多道程序的道数，因而可全部进入内存。若将实时系统与批处理系统结合的话，就可以让作业量超过多道程序道数，使优先级低的作业呆在外存的后备队列上。

200372. 假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。 表1 进程到达和需要服务时间 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2

此题答案为： 表2 进程的完成时间和周转时间 进程 A B C D E 平均 FCFS 完成时间 3 9 13 18 20 周转时间 3 7 9 12 12 8.6

20