操作系统试题库-综合题课件

1、1、设有三个进程，它们的提交时间及运行时间如下表，若采用短进程优先调度策略，试给出进程串行运行时的调度次序及平均周转时间。作业提交时间运行时间J104J228J335答：进程提交时间开始时间完成时间周转时间J10044J2291715J33496平均周转时间=(4+15+6)/3=25/3=8.33各进程的调度次序：J1,J3,J22、设有三道作业，它们的提交时间及运行时间如下表，若采用短作业优先调度策略，试给出作业单道串行运行(3分)时的调度次序及平均周转时间。(8分)作业提交时间(单位：基本时间单位)运行时间(单位：基本时间单位)J107J224J335作业提交时间开始时间完成时间周转时间

2、J10077J227114J33111613平均周转时间=29/319£7(7j9+13)/3=各作业的调度次序L3、 假定在单CP原件下，有A,B,C,D四个作业依次到达(后面的作业依次比前一作业迟到一个时间单位)四个作业分别需要运行11,6,2和1个时间单位，如果系统采用FCFS勺调度算法，请计算：(1)各作业的周转时间(2)系统此时的平均周转时间；(3)各作业的带权周转时间；(4)系统此时的平均带权周转时间;10、1、2、1、5(秒)，其优先解答：作业作业到达时间运行时间完成时间周转时间A01111111B1617162.67C2219178.5D31平均周转时间T=平均带权周

3、转时间2015.25W=7.291717带权周转时间4、假设在单处理机上有五个(1,2,3,4,5)进程争夺运行，其运行时间分别为级分别为4、1、3、5、2;在某时刻这五个进程按照1,2,3,4,5的顺序同时到达。试回答：(1)给出这些进程分别使用轮转法(时间片为2秒)、非剥夺优先级调度法时的运行进度表(2)在上述各算法的调度下每个进程的周转时间和等待时间为多少？解答：（1） 轮转法运行进度表：P1P2P3p4P5P1P5P1P5P10235681012141519非剥夺优先级调度法运行进度表：P4P1P3P5P20111131819（2）轮转法周转时间和等待时间作业运行时间（小时）周转时间（

4、小时）等待时间（小时）110190+6+2+1=921323253416555156+2+2=10非剥夺优先级调度法周转时间和等待时间作业优先级调度顺序运行时间（小时）周转时间1（小时）等待时向（小时）142101112151191833321311451110524518135、画出进程的五种状态变化图，并说明状态变化原因答：变化原因在图上说明（6） 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：（1）用PV（或wait和signal）操作管理这些并发进程时，应怎样定义信

5、号量，写出信号量的初值以及信号量各种取值的含义。（2）若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）。（3）根据所定义的信号量，把应执行的PV（或wait和signal）操作填入下述括号中，以保证进程能够正确地并发执行。Buyi（I=1,2,）Do进入售票厅；（）购票；（）退出；while(1)解答：（1）定义一彳t号量S,初始值为20。（1分）意义：S>0S的值表示可继续进入售票厅的人数（1分）S=0表示售票厅中已有20名顾客（购票者）（1分）S<0|S|的值为等待进入售票厅的人数（1分）S的最大值为20（1分）S的最小值为20-n（1分）上框为P（S）（1分

6、）下框为V（S）（1分）注：信号量的符号可不同（如写成t）,但使用时应一致（即上述的s全应改成t）7、现为某临界资源设一把锁w,当w=1时，表示关锁，w=0时，表示锁已打开，试写出开锁和关锁的原语，并说明如何利用它们去控制对该临界资源的互斥访问？（7分）开锁原语unlock（w）如下：unlock（w）:w：=0关锁原语lock（w）如下：Lock（w）:L:ifw=1thengotoLeelsew.=1；（4分）可设临界段cs放在两者之间来实现互斥，即Lock（w）；cs；unlock（w）（3分）8、有两个用户进程A和B,在运行过程中都要使用系统中的一台打印机输出计算结果。（7） 试说明A

7、B两进程之间存在什么样的制约关系？（2）为保证这两个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。解答：（1）A、B两进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。（2分）（8） mutex:用于互斥的信号量，初值为1。（2分）进程A进程BP(mutex)P(mutex)申请打印机使用打印机申请打印机使用打印机V(mutex)V(mutex)9、 进程process_A进行计算后通过进程process_B输出，这两个并发进程的程序如下:intCount=0;process_A

8、()doCount=Count+10while(1)process_B()doprint(Count)Count=0;while(1)请回答:(1)指出这两个并发进程的临界区。(2)指出它们并发执行时可能出现的与时间有关的错误。(3)用信号量机制进行管理，写出它们能正确并发执行的程序。解答：(1)临界区为process_A():Count=Count+10,process_B():print(Count)Count=0;(2)错误顺序(不是唯一的)print(Count)Count=Count+10Count=0;(3)实现同步信号量：S1=1,S2=0;信号量：mutex=1；intCoun

9、t=0;process_A()dowait(S1)wait(mutex);Count=Count+10Signal(mutex)Signal(S2)while(1)process_B()dowait(S2)wait(mutex);print(Count)Count=0;Signal(mutex)Signal(S1)while(1)10、有一个阅览室，共有100个座位，读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名等，读者离开时要消掉登记的信息，试问：(？)(1)为描述读者的动作，应编写几个程序，设置几个进程？(2)试用PV操作描述读者进程之间的同步关系。答：读者

10、的动作有两个，一是填表进入阅览室，这时要考虑阅览室里是否有座位；一是读者阅读完毕，离开阅览室，这时的操作要考虑阅览室里是否有读者。读者在阅览室读书时，由于没有引起资源的变动，不算动作变化。算法的信号量有三个：seats表示阅览室是否有座位(初值为100,代表阅览室的空座位数)；readers表示阅览室里的读者数，初值为0;用于互斥的mutex,初值为1o读者进入阅览室的动作描述getin:while(TRUE)P(seats);/*P(mutex)/*填写登记表；进入阅览室读书；V (mutex)/*V (readers)读者离开阅览室的动作描述getout：while(TRUE)没有座位则离

11、开*/进入临界区*/离开临界区*/Prreaders)/*P(mutex)/*消掉登记；离开阅览室；V(mutex)/*V(seats)/*阅览室是否有人读书*/进入临界区*/离开临界区*/释放一个座位资源*/11、打印机编号分配标志用户名一用户定义的设备名001020假定进程A负责为用户作业分配打印机，进程B负责释放打印机，系统中设立一个打印机分配表如下，由各个进程共用。试用P,V操作实现两进程对分配表的互斥操作。解答：设一个互斥信号量mutex,其初值为1。P1(分配进程)和P2(释放进程)的临界区代码可按下述形式组成:P(mutex)；分配打印机；(读写分配表)V(mutex)；(mut

12、ex)；释放打印机;(读写分配表)(mutex)；I12、设系统中只有一台打印机，有二个用户的程序在执行过程中都要使用打印机输出计算结果。设每个用户程序对应一个进程。问：这二个进程间有什么样的制约关系？试用P,V操作写出这二个进程使用打印机的算法。解答：因为打印机是一种临界资源，所以这二个进程只能互斥地使用这台打印机。即一个用户的计算结果打印完后，另一个用户再打印，因此是互斥关系。设两个进程分别为A和B,设一个互斥信号量mutex,其初值为1,其算法如下：A进程B进程*P(mutex)；使用打印机;V(mutex)；1r(mutex)；使用打印机;(mutex)；13、设P1,P2两进程共用一

13、个缓冲区F,P1向F写入信息，P2则从F中读出信息。问这两个进程间是什么样的制约关系？试用P,V操作写出这两个进程读写缓冲区的算法。解答：A,B两进程间是同步关系，即A进程向Q写满信息后，B进程才能从Q中取走信息。为此，设立两个信号量：empty:表示缓冲区Q为空(0为不空，1为空)，初值为1,full表示缓冲区Q为满(0为不满，1为满)，初值为0。算法如下：A进程：while(true)P(empty)；向Q写入信息;V(full);)Bwhile(true)P进程:(full)；从Q中读出信息;(empty)；注：若信号量初值不同,算法有些不同如若empty和full的初值均为0,则A进程

14、的算法中P(empty)语句应放在V(full)之后，即解法不惟一14、设A1,A2为两个并发进程，它们共享一临界资源，其临界区代码分别为CS1,CS2问这两个进程间是什么样的制约关系？试用P,V操作写出这两个进程共享临界资源的算法。解答：因为A,B两个进程是并发的，它们共享一个临界资源，所以两个进程间应互斥地进入临界区设立一个互斥信号量mutex,其初值为1。具体算法如下：A斑:程：B进程：1FP(mutex)；P(mutex)；临界区代码Csa；临界区代码Csb；V(mutex)；V(mutex)；15、设有一台计算机，有一条I/O通道，接一台卡片输入机，卡片机把一叠卡片逐一输入到缓冲区Q

15、1中，计算机从缓冲区Q1中取出数据再进行加工处理。假设系统中设一个输入进程Pr和一个计算进程Pc来完成这个任务。问这两个进程间有什么样的制约关系？请用P,V操作写出这些进程的算法。解答：进程Pr受Pc进程的影响，B1放满信息后，Pr进程要等待，等Pc进程将其中全部信息取走，才能继续读入信息；同样地，Pc进程受Pr进程的约束，B1中信息放满后Pc进程才能从中取走信息。因此，两者之间是同步制约关系。设两个信号量：B1full缓冲区B1满，初值为0；B1empty算法如下：缓冲区B1空，初值为1Pr进程：Pcwhile(true)while(true)P(B1empty)；P卡片信息写入缓冲区；V(

16、B1full);V)进程：（B1full）;从B1中取出信息;（B1empty）；注：若B1fullt和B1empty的初值均为0,这时进程Pr有所不同，即,P(B1empty);应放在V(B1full)之后。也即解法不惟一*利用信号量实现前趋关系Vara,b,c,d,e,f,g;semaphore：=0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S3;signal(e);end;beginwait(c);S4;sig

17、nal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;parendend16、多个进程共享一个文件，其中只读文件的进程称为读者，只写文件的进程称为写者。读者可以同时读，但写者只能独立写。下面的同步算法是用P、V操作写出的，并且它对写者优先，即一旦有写者到达，后续的读者必须等待。（8分）问题：1）、在上述算法的空白处填上正确的语句，使得该算法完整。2）、该算法有可能会出现什么问题？算法如下：intrmutex=1,wmutex=1,count=0（正在读的读者的个数）,s=1;main()parb

18、eginreader();writer();parend;)reader()while(1)_(1)_；_(2)_；if(count=0)p(wmutex);count+;_(3)_;_(4)_;读文件；答：1)问题1:(1)p(s)p(rmutex);count-;if(count=0)_(5)_;v(rmutex);)writer()while(1)P(s)；p(wmutex)写文件；v(wmutex);v(s);)(2)p(rmutex)(3)v(rmutex)(4)v(s)(5)v(wmutex)2)问题2:如果连续出现新的写者进程，则可能导致读者进程饿死。17、指出下列哲学家就餐问题

19、的算法在什么情况下会导致死锁，并改进此算法，使它不会产生死锁算法描述：图7.1五个哲学家在一张圆桌上进行思考和吃饭。哲学家思考时，并不影响他人。只有当他吃饭时，他才试图拿起左右两根筷子(一根一根的拿起)。如果筷子已在他人手上，则需等待。只有当他同时拿起左右两根筷子时，才可以吃饭。如图7-1所示：程序描述为：(第i个哲学家，i=0,1,2,3,4)Varchopstick:array0.4ofsemaphore;/*各信号量初值均为1*/RepeatP(chopsticki);/*P操作，拿左筷子*/P(chopsticki+1mod5);/*P操作，拿右筷子*/Eat();/*吃饭*/V(ch

20、opsticki);/*V操作，放下左筷子*/V(chopsticki+1mod5);/*V操作，放下右筷子*/Think();/*思考*/Untilfalse;答：1)、可能导致死锁的情况：每位哲学家都拿了左筷子，而在等待右筷子。即每位哲学家进程都只执行了语句:P(chopsticki)。2)、改进：编号为双数的哲学家先拿左筷子，而单数的先拿右筷子。程序为：Repeatif(imod2=0)P(chopsticki);P(chopsticki+1mod5);elseP(chopsticki+1mod5);P(chopsticki);Eat();V(chopsticki);V(chopstic

21、ki+1mod5);Think();Untilfalse;18、简述信号量的定义和作用。P,V操作原语是如何定义的？解答：信号量一般是由两个成员S,Q胤成的数据结构，其中一个成员是整型变量，表示该信号量的值，它是与相应资源的使用情况有关的；另一个是指向PCB的指针。当多个进程都等待同一信号量时，它们就排成一个队列，由信号量的指针指出该队列的头。信号量通常可以简单反映出相应资源的使用情况，它与P,V操作原语一起使用可实现进程的同步与互斥。P,V操作原语的定义:P(S):顺序执行下述两个动作：信号量S的值减1,即S=S-1;如果S>0,则该进程继续执行，如果S<0,则把该进程的状态置为

22、阻塞态，把相应的PCB连入该信号队列的末尾，并放弃处理机，进行等待。(直到有其它进程在S上执行V操作，把它释放出来为止。)V(S):顺序执行下述两个动作：信号量S的值力口1,即S=S+1如果S>0,则该进程继续执行，如果S<0,则释放信号量队列上的第一个PCB(即信号量指针所指向的PCB所对应的进程(把阻塞态改为就绪态)，执行V操作态的进程继续执行。19、某虚拟存储器的用户编程空间共321KB内存为16KR假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：则逻辑地址0A5c(H)所对应的物理地址是什么？解答：逻辑地址0A5CH所对应的二进制表示形式是:页号物理块号

23、0511024370000101001011100,由于1K=210,下划线部分前的编码为000010,表示该逻辑地址对应的页号为3查页表，得到物理块号是4(十进制)，即物理块地址为:0001001000000000,拼接块内地址0000000001011100,得0001001001011100,即125C(H)20、某段表内容如下：段号段首地址段长度0120K40K1760K30K2480K20K3370K20K一逻辑地址为(2,154)的实际物理地址为多少？答：逻辑地址(2154)表示段号为2,即段首地址为480K,154为单元号，则实际物理地址为480K+154。21、(1)某页式存储

24、系统页表如下，设每页1KB请写出逻辑地址为8300时所对应的页号和页的地址，以及在内存中对应的物理地址。(请详细写出运算过程)系统页表：页号012345678块号3561087124(2)已知如下段表：段号01234基址21923009013271952长度6001410058096在分段存储管理下系统运行时，下列逻辑地址(第一位表示段号(a)：(1,10)第二位表示段内位移)的物理地址是什么?(b):(4,112)答：(1)页号P=INTA/L=8300/1024=8页内地址d=AMODL=8300MOD1024=20物理地址4X1024+108=4024(2)(a):地址(1,10)的段号

25、为1,查表得基址为2300,段长为14,物理地址为：2300+10=2310。（b）:地址（4,112）的段号为4,查表得基址为1952,段长为96,地址（4,112）的段内位移为112,大于段长96,发生段越界，产生中断。22、在页式虚拟存储管理的计算机系统中，运行一个共有8页的作业，且作业在主存中分配到4块主存空间，作业执行时访问页的顺序为6,0,1,2,0,4,3,1,2,6,7,4,2,5,6,请问用FIFO和LRU替换算法时，它们的缺页中断率分别是多少。（要求图示出内存页面变化情况）。(1)FIFO算法12342156213763212361112234156213376621223

26、34156213776221334415621376621136+故障数：16页故障率：16/19*100%=84%(2)LRU(最近最久未用页面)算法1234215621376321236111234215621376331222342156213763212334215621376321236+故障数：15页故障率：15/19*100%=79%OPT算法1234215621376321236111111111133333333322222222227772222234445666666661116+故障数：11页故障率：11/19*100%=58%23、画出段页式存储管理系统的地址变换过程

27、图段页式春播系统的地址转校24、假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面读信息，并且有下述请求序列等待访问磁盘：试用：电梯调度SCAN®(2)最短寻道时间优先SSTF算法；分别列出实际处理上述请求的次序。(1)电梯调度算法的处理次序为：58143627(得4分)若写出58(得1分)若写出58143(得2分)(2)最短寻找时间优先算法的处理次序为：58627143(得4分)若写出58(得1分)若写出58627(得2分)亦即：前2个对(得1分)前5个对(得2分)25、假设一个活动头磁盘有200道，编号从0-199.当前磁头正在143道上服务，并且刚刚完成了

28、125道的请求.现有如下访盘请求序列(磁道号)：86,147,91,177,94,150,102,175,130试给出采用下列算法后磁头移动的顺序和移动总量(总磁道数).(1) .先来先服务(FCFS)磁盘调度算法.(2) .最短寻道时间优先(SSTF)磁盘调度算法.(3) .扫描法(SCAN)B盘调度算法.(假设沿磁头移动方向不再有访问请求时，磁头沿相反方向移动.)答案：磁头移动的顺序：(1) 86,147,91,177,94,150,102,175,130(2)当前磁头在143道上：147,150,130,102,94,91,86,175,177(3)当前磁头在143道上，并且刚刚完成12

29、5道的请求147,150,175,177,130,102,94,91,86磁头移动总量(总磁道数)：(1) (14386)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-130)=565(2) (147143)+(150-147)+(150-130)+(130-102)+(102-94)+(94-91)+(91-86)+(175-86)+(177-175)=162(3) (177-143)+(177-86)=12526、文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不

30、考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。答：(1)、采用二级索引，可寻址的文件的最大长度：(512/3)*(512/3)*512=170*170*512=14796800(字节)(2)、采用三级索引，可寻址的文件的最大长度：(512/3)*(512/3)*(512/3)*512=170*170*170*512=2515456000(字节)27、设当前的工作目录在da1请看图回答(4) 文件mc.c的绝对路径名(/data/da1/ma.c)。(5) 文件mc.c的相对路径名(mc.c)。(6) 要在文件abc原来的权限的基础上增加让所有用户都具有执行权

31、限，请用一条命令完成该功能(chmoda+xabcsss.c输入的命令是(cpmc.c(chmoda+rwxabc或chmod777(4)将文件mc.c在当前目录下复制一份副本，副本的文件名为sss.c)。(5)在当前目录下，创建子目录sd2命令是(mkdirsd2)(6)要让所有用户对文件abc都具有读、写、执行权限。命令是abc)。(7)命令$cat/data/da3/sun.c的实际的功能是(在屏幕上显示/data/da3子目录下的sun.c文件的内容)。(8)删除sd1子目录下、扩展名为BAS的所有文件，输入命令是(rmsd1/*BAS)。(9)删除子目录sd1下的所有文件和子目录，命

32、令是(rmr/data/da1/sd1)。(10)输入命令$chmod754abc后，同组用户对文件abc存取权限是(读和执行)、其它用户对文件abc的权限是(只读)。(11)删除文件mc.c。命令是(rmmc.c)。(12)在显示器上以长格式列出da1下的所有目录项(lsl/data/da1(或lsl).28、设系统中有三类资源最大需求量A、B和C,又设系统中有5个进程P1,已分配资源量ABCABCAP1864121211P2433311P31013413P4333322P5546113P2,P3,P4和P5.在T0时刻系统状态如下:剩余资源量BC(1)系统是否处于安全状态？如是,(2)如果

33、进程P5申请1个资源类则给出进程安全序列.A1个资源类B和1个资源类C,能否实施分配？为什么?答案:(1)利用安全性算法对T0时刻的资源分配情况进行分析，结果如下:WorkNeedAllocationWork+AllocationFinishP4211011322533trueP2533122311844trueP1844743121965trueP39656004131378trueP5137843311314811true系统处于安全状态，安全序列为：P4,P2,P1,P3,P5(5分)(2)P5发出请求向量Request5(1,1,1),系统按银行家算法进行检查:1)Request5(1

34、,1,1)<=Need5(4,3,3)2)Request5(1,1,1)<=Available(2,1,1)3）系统先假定可为P5分配资源，并修改Available、Allocations、Need5向量，资源变化情况如表3maxABCAllocationAvailableABCNeedABCABCP1864121100743P2433311122P31013413600P4333322011P5546224322不能实施分配，因为分配后找不到安全序列，系统将处于不安全状态.（4分）29、有三个进程P1,P2和P3并发工作。进程P1需用资源S3和S1;进程P2需用资源S1和S2;进程P3需用资源S2和S3。回答：（1）若对资源分配不加限制，会发生什么情况？为什么？（2）为保证进程正确工作，应采用怎样的资源分配策略？为什么？（1）可能会发生死锁（2分）例如：进程P1,P2和P3分别获得资源S3,S1和S2后再继续申请资源时都要等待（2分），这是循环等待。（或进程在等待新资源时均不释放已占资源）（2）可有几种答案：A.采用静态分配（2分）由于执行前已获得所需的全部资源，故不会出现占有资