操作系统典型题目讲解

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

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4