计算机操作系统算法题(最全).docx

《计算机操作系统算法题(最全).docx》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、6.算法题（共32个题目）.在信号量机制中，若P（S）操作是可中断的，则会有什么问题？此题答案为：答：P（S）的操作如下：  Begin       S.Value:=S.Value-1;        ①       IfS.Value<0Then           ②           Begin           Insert(*,S.L);           Block(*)                ③           End  End.若P（S）可中断的，例如进程A在执行了语句①之

2、后从CPU上退下了，假定此时S.Value＝0；这时换另一进程B，B又将S.Value的值减1使之为－1，在执行语句③时，B被阻塞；然后又换回A执行，由于A的"断点"是语句①之后，当它执行语句②时，由于这时S.Value已经是－1，故进程继续执行而被阻塞。这就出现了错误：本来A操作P（S）操作后，S.Value＝0，是不应该被阻塞的，现在却被阻塞了。.何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？   ＃definetrue;   #definefalse;     Intflag[2];   

3、  flag[1]=flag[2]=false;     enter-crtsec(i)     inti;    {      While(flag[1-i])      flag[i]=true;     }     feave-crtsec(i)    Inti;   {     flag[i]=false;    }    processI;     …   Enter-crtsec(i);   Incriticalsection;   Leave-crtsec(i);此题答案为：答：一次仅允许一个进

4、程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。这种算法不是安全的。因为，在进入临界区的enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个flag均为false），则这两个进程可同时进入临界区。.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购

5、票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：（1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。（2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。  CobeginPROCESSPi(i=1,2,…)      Begin     　进入售票厅；　　　　购票；　　　　退出；　　　　End;  Coend(3)若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值

6、）。此题答案为：售票厅问题解答如下：（1）定义一信号量S，初始值为20。   S>0 S的值表示可继续进入售票厅的人数；   S=0 表示售票厅中已有20名购票者；   S<0 

7、S

8、的值为等待进入售票厅中的人数。（2）上框为P(S)，下框为V(S)。（3）S的最大值为20，S的最小值为20－N，N为某一时刻需要进入售票厅的最多人数。 .在批处理系统、分时系统和实时系统中，各采用哪几个进程（作业）调度算法？此题答案为：答：（1）批处理系统中的作业调度算法有：先来先服务算法（FCFS）、短作业优先算法（SJF）

9、、优先级调度算法（HPF）和高响应比优先算法（RF）。批处理系统的进程调度算法有：先进先出算法（FIFO）、短进程优先算法（SPF）、优先级调度算法（HPF）和高响应比优先算法（RF）。（2）分时系统中只设有进程调度（不设作业调度），其进程调度算法只有轮转法（RR）一种。（3）实时系统中只设有进程（不设作业调度），其进程调度算法调度有：轮转法、优先级调度算法。前者适用于时间要求不严格的实时系统；后者用于时间要求严格的实时系统。后者又可细分为：非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度

10、。注意，一个纯粹的实时系统是针对特定应用领域设计的专用系统。作业提交的数量不会超过系统规定的多道程序的道数，因而可全部进入内存。若将实时系统与批处理系统结合的话，就可以让作业量超过多道程序道数，使优先级低的作业呆在外存的后备队列上。.假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CP