Loop:

P (full[I]); P(Mutex);

从消息缓冲区取出消息； v(Mutex); v(empty[I]); Goto Loop; End;

CoEnd;

9、进程A、B、C坐在圆桌旁讨论问题（面朝圆桌），每个人都从其右边那个人的信箱里取得讨论的问题，回答完一个问题后提出一个新问题放在左边的信箱中。假设A右边的信箱可放3个问题，B右边的信箱可以放2个问题，C右边的信箱可以放3个问题，初始时A右边的信箱中有2个问题。用信号量写出三个人讨论问题的同步算法。

A信箱A信箱BC信箱CB

10、战地指挥官通过无线电不断向他的三个士兵下达作战指令，但是他必须在得到所有士兵对前一条指令的“确认”之后才能下达新的指令。请用信号量或管程进行指挥官和士兵之间的协同管理。

11、有三个并发进程R,M,P，它们共享了一个可循环使用的缓冲区B，该缓冲区共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存入缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符是，则把它改成“，”；进程P负责吧处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。用P，V操作写出能正确并发执行的程序。

12、有4个进程A,B,C,D共享一个缓冲区，进程A负责循环地从文件读一个整数放入缓冲区，进程B从缓冲区取出MOD 3为0的整数并累计求和；进程C从缓冲区取出MOD 3为1的整数并累计求和；进程D从缓冲区取出MOD 3为2的整数并累计求和.请用PV操作写出能够正确执行的程序。

2.5 进程通信

1、在UNIX中，（）用于吧一个进程的输出连接到另一个进程的输入（普通文件；索引文件；目录文件；管道文件） 2、关于进程通信的说法，判断：

（1）进程通信有两种方式，直接通信和间接通信。 （2）直接通信固定在一对进程之间。

16

（3）间接通信是通过第三个进程转发信件的，不必在两个进程间直接相互通信。 （4）间接通信方式以信箱为媒介实现通信，信箱由接收信件的进程设置。

2.6线程

1、以下描述中，（）并不是多线程系统的特长。（浙大06） （1）利用线程并行地执行矩阵乘法运算； （2）Web服务器利用线程响应HTTP请求

（3）键盘驱动程序为每一个正在运行的应用配备一个线程，用来响应该应用的键盘输入 （4）基于GUI的debugger用不同的线程分别处理用户输入、计算、跟踪等操作。 2、若一个进程拥有100个线程，这些线程属于用户级线程，则该进程在系统调度执行时间上占用（）个时间片：1；100；1/100；0

3、判断：属于同一个进程的线程可以共享进程的程序段和数据段。 4、关于进程和线程的说法，判断：

（1）线程是进程中可独立执行的子任务，一个进程可以包含一个多多个线程，一个线程可以属于一个或多个进程。

（2）线程又称为轻型进程，因为线程都比进程小。

（3）多线程技术具有明显的优越性，如速度快、通信简便、并行性高等。 （4）由于线程不作为资源分配单位，线程之间可以无约束地并行执行。

第三章 处理机调度与死锁

3.3 调度算法

1、既考虑作业的执行时间又考虑作业的等待时间的调度算法是（）。（选项：短作业优先；先来先服务；响应比高者优先；优先级调度）

2、给定一组作业J1,J2,…Jn，它们的运行时间分别为T1,T2,…Tn，假定这些作业是同时到达，并且将在一台cpu上按单道方式运行。证明：若按最短作业优先调度算法运行这些作业，则平均周转时间最短。（东南大学、北京大学） 证明：先对J1,J2,…Jn按照T1,T2,…Tn的大小升序排列，得到K1,K2…,Kn，这组进程的运行时间t1<=t2<=…<=tn。SJF调度就是从K1到Kn这个序列。设SJF调度这n个进程的周转时间之和Z，则：

T=Z/n=[t1+(t1+t2)+ (t1+t2+t3)+…+ (t1+t2+t3+…+tn)]/n =[n*t1+(n-1)*t2+(n-2)*t3+…+1*tn]/n

因为n>(n-1)>(n-2)>…>1,所以t1<=t2<=…<=tn时，平均周转时间最小。

3、判断：在剥夺优先级调度方式下，现运行进程的优先级不低于系统中所有进程的优先级。

17

4、设某计算机系统有一个cpu，一台输入设备，一台打印机。现有两个进程同时进入就绪状态，且进程A先得到cpu运行，进程B后运行。进程A的运动轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图，并说明开始运行后，cpu有无空闲等待？计算cpu的利用率。（浙大05）

3、一个操作系统具有分时兼批处理的功能，设个一个合理的调度策略，使得分时作业响应快，批作业也能及时得到处理。

4、一个具有分时兼批处理功能的操作系统应怎样调度和管理作业?

要点提示：

1)优先接纳终端作业，仅当终端作业数小于系统可以允许同时工作的作业数时，可以调度批处理作业。

2)允许终端作业和批处理作业混合同时执行。 3)把终端作业的就绪进程排成一个就绪队列，把批处理作业的就绪进程排入另外的就绪队列中。

4)有终端作业进程就绪时，优先让其按“时间片轮转”法先运行。没有终端作业时再按确定算法选批处理作业就绪进程运行。

4、现有两道作业同时执行，一道以计算为主，另一道以输出为主，应该如何为两作业设置处理器的优先级？

5、有5个待运行的作业为A,B,C,D,E，各自运行时间为9，6，3，5，x，试问采用哪种运行次序使得平均响应时间最短？

提示：假设x<3，x在3和5间，在5和6间，在6和9间分别讨论。

6、某个操作系统的设计目标是同时支持实时任务和交互式任务，它的实现采用混合式多线程策略，处理器调度策略采用多队列策略，在系统资源不足时，可采用中级调度来平衡系统负载。

（1）问该系统中存在着哪些与处理器调度有关的实体？（进程、内核级线程、用户级线程）

（2）设计一个合理的多队列进程调度策略，它既能满足实时任务调度的需要，又能从外设访问角度来满足交互式任务调度的需要。

提示：划分成实时优先级层次和交互式优先级层次，其中前者优先级层次高。实时优先级层次包括多个优先级，可以组织成多个就绪线程队列或一个优先级队列；可采用抢占式优先级调度策略，时间片较长。交互式优先级层次可以分成3个就绪队列，按照优先级从高到低依次为：访问字符设备的就绪线程队列、访问块设备的就绪线程队列、时间片完成的就绪线程队列，其中优先级较高的就绪线程队列具有较短的时间片。 7、（浙大02）假设一个计算机系统具有如下特征：处理一次中断，平均耗时1ms；一次进程调度，平均耗时2ms；将CPU分配给选中的进程，又平均需要1ms。再假设其定时器芯片每秒产生100次中断，问：

（1）系统将百分之几的CPU时间用于时钟中断处理？（提示：每秒处理中断的时间是100ms，100ms/1s=10%

18

（2）如果采用轮转法调度，10个时钟中断为一个时间片，那么，系统将百分之几的CPU时间用于进程调度（包括雕刻、分配CPU和引起调度的时钟中断处理时间）？ 每次调度所花时间=一次进程调度2ms+分配cpu的1ms+引起调度的时钟中断1ms，每秒会进行10次调度，则：（2ms+1ms+1ms）*10/1s=4% 8、有一个多道批处理系统，作业调度采用“短作业优先”调度算法；进程调度采用“优先数抢占式”调度算法，且优先数越小优先级越高。如系统拥有打印机一台，采用静态方法分配，忽略系统的调度开销。现有如下作业序列到达系统： 作业名 J1 J2 J3 J4 J5 到达系统时间 14：00 14：20 14：30 14：50 15：00 Cpu运行时间 40min 30min 50min 20min 10min 打印机需求 优先数 1 0 1 0 1 4 2 3 5 1 回答：（1）按作业运行结束的次序排序；（2）作业的平均周转时间和平均带权周转时间是多少？

提示：作业调度与内存大小有关，本题没有给条件，所以只需考虑进程调度，得出结束次序为：J2,J1,J5,J3,J4.

9、设在某多道程序系统中有用户使用的内存100KB，打印机1台。系统采用可变分区动态分配算法管理内存，而对打印机采用静态分配。假设输入输出操作时间忽略不计，采用最短剩余时间优先的进程调度算法，进程剩余时间相同时采用先来先服务的算法，进程调度时间选择在进程执行结束或新进程创建时。现有进程如下：

进程 0 1 2 3 4 创建时间 0 4 10 11 16 要求执行时间 8 4 1 20 14 要求内存 15KB 30KB 60KB 20KB 10KB 申请打印机 1 1 0 1 1 假设系统优先分配内存低地址区域，且不允许移动，那么： （1）给出进程调度算法选中进程的次数。 （2）全部进程执行结束所用的时间是多少？

10、就绪队列中有n个就绪进程等待cpu调度，如果采用不同的调度算法，总共可能有（）种调度顺序。（浙大06） 11、一个实时系统使用了4个周期事件，其周期分别为50ms，100ms，200ms，250ms。假设这4个周期事件分别需要35ms，20ms，10ms和x ms的CPU时间。保持系统可调

19

度的最大x值是多少？

提示：该实时系统是以周期进行调度，即m个周期事件，时间i以周期Pi发生，需要Ci秒钟CPU时间处理一个事件，那么可处理负载的条件是：C1/P1+C2/P2+C3/P3+C4/P4=35/50+20/100+10/200+x/250≤1,则x≤12.5ms。

3.5 死锁的基本概念

1、判断：死锁是指系统中的全部进程都处于阻塞状态。（北京理工01）

2、判断：PV操作不仅可以用来实现进程同步，还可以用来防止进程的死锁。（南京理工01）

3、有3个进程P1,P2和P3并发工作，进程P1需要资源S3和S1，进程P2需要资源S1和S2，进程P3需要资源S2和S3.那么： （1）若对资源分配不加限制，可能发生什么情况？ （2）为保证进程正确地工作，应采用怎样的资源分配策略？

4、设系统有一类数量为M的独占性资源，系统中N个进程竞争该类资源，个进程对资源的最大需求为W。当M,N,W分别取下列个值时，系统可能发生死锁？（上海交大） （1）M=2;N=2;W=2; （2）M=3;N=2;W=2;

（3）M=3;N=2;W=3; （4）M=5;N=3;W=2; （1）M=6;N=3;W=3; 5、在有m个进程的系统中出现死锁时，死锁进程的个数范围是（）（北大97） 6、死锁现象并不是计算机系统所独有的，判断下列哪些现象是死锁的体现：（浙大06） （1）杭州西泠桥塞车，因为大修，桥上只有一个车道供双方通行； （2）高速公路大堵车，因为桥被台风吹跨了； （3）两列相向行驶的列车在单轨铁路上迎面相遇；

（4）两位木匠钉地板，每位木匠必须有榔头和钉子才能工作。一位只握一把榔头，而另一位没有榔头，却有钉子；

7、资源的有序分配策略可以破坏死锁的（）条件。 8、如下图所示，相交的四条单行线不幸塞车。（浙大03） 9、在多进程的并发系统中，肯定不会因竞争( D )而产生死锁。 A.打印机 B.磁带机 C.磁盘 D.CPU

20