2021年操作系统试题库综合题.doc

1、 设有三个进程，它们提交时间及运营时间如下表，若采用短进程优先调度方略，试给出进程串行运营时调度顺序及平均周转时间。作业提交时间运营时间J1 04J2 2 8J3 35答：进程提交时间开始时间完毕时间周转时间 J1 0 044 J2 2 9 1715 J3 3 4 9 6 平均周转时间(4156)/325/38.33各进程调度顺序： J1，J3，J22、 设有三道作业，它们提交时间及运营时间如下表，若采用短作业优先调度方略，试给出作业单道串行运营时调度顺序及平均周转时间。 (8分)作业提交时间(单位：基本时间单位)运营时间(单位：基本时间单位)J1J2J3023745作业提交时间开始时间完毕时间周转时间 J1 0 077 J2 2 7 114 J3 311 16 13平均周转时间(7913)/329/39.67(4分)各作业调度顺序： (3分)3、 假定在单CPU条件下，有A，B，C，D四个作业依次到达（背面作业依次比前一作业迟到一种时间单位）。四个作业分别需要运营11，6，2和1个时间单位，如果系统采用FCFS调度算法，请计算：（1） 各作业周转时间（2） 系统此时平均周转时间；（3） 各作业带权周转时间；（4） 系统此时平均带权周转时间；解答:作业 作业到达时间 运营时间 完毕时间 周转时间 带权周转时间 A 0 11 11 11 1 B 1 6 17 16 2.67 C 2 2 19 17 8.5 D 3 1 20 17 17平均周转时间T= 15.25平均带权周转时间 W= 7.294、 假设在单解决机上有五个（1,2,3,4,5）进程争夺运营，其运营时间分别为10、1、2、1、5（秒），其优先级分别为4、1、3、5、2；在某时刻这五个进程按照1,2,3,4,5顺序同步到达。试回答：(1) 给出这些进程分别使用轮转法（时间片为2秒）、非剥夺优先级调度法时运营进度表。(2) 在上述各算法调度下每个进程周转时间和等待时间为多少？解答：(1) 轮转法运营进度表：P1 P2 P3 p4 P5 P1 P5 P1 P5 P1 0 2 3 5 6 8 10 12 14 15 19非剥夺优先级调度法运营进度表： P4 P1 P3 P5 P2 0 1 11 13 18 19(2) 轮转法周转时间和等待时间：作业运营时间（小时）周转时间(小时)等待时间(小时)110190+6+2+1=921323253416555156+2+2=10非剥夺优先级调度法周转时间和等待时间：作业优先级调度顺序运营时间（小时）周转时间(小时)等待时间(小时)142101112151191833321311451110524518135、 画出进程五种状态变化图，并阐明状态变化因素。答：变化因素在图上阐明。6、 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外购票者可及时进入，否则需在外面等待。若把一种购票者看作一种进程，请回答下列问题：(1)用PV（或wait和signal）操作管理这些并发进程时，应如何定义信号量，写出信号量初值以及信号量各种取值含义。(2)若欲购票者最多为n个人，写出信号量也许变化范畴(最大值和最小值)。(3)依照所定义信号量，把应执行PV（或wait和signal）操作填入下述括号中，以保证进程可以对的地并发执行。Buyi(I=1，2，) Do 进入售票厅； （ ） 购票；（ ）退出； while(1)解答： (1)定义一信号量S，初始值为20。(1分)意义：S0S值表达可继续进入售票厅人数(1分)S=0表达售票厅中已有20名顾客(购票者)(1分)S0|S|值为等待进入售票厅人数(1分)(2) S最大值为20(1分) S最小值为20n(1分)(3) 上框为P(S)(1分) 下框为V(S)(1分)注：信号量符号可不同(如写成t)，但使用时应一致(即上述s全应改成t)。7、 现为某临界资源设一把锁w，当w1时，表达关锁，w0时，表达锁已打开，试写出开锁和关锁原语，并阐明如何运用它们去控制对该临界资源互斥访问？(7分) 开锁原语unlock(w)如下：unlock(w)：w：0 关锁原语lock(w)如下：Lock(w)：L：if w1 then go to L eelsew：1；(4分) 可设临界段cs放在两者之间来实现互斥，即Lock(w)；cs；unlock(w) (3分)8、 有两个顾客进程A和B，在运营过程中都要使用系统中一台打印机输出计算成果。(1) 试阐明A、B两进程之间存在什么样制约关系？(2) 为保证这两个进程能对的地打印出各自成果，请用信号量和P、V操作写出各自关于申请、使用打印机代码。规定给出信号量含义和初值。解答：(1) A、B两进程之间存在互斥制约关系。由于打印机属于临界资源，必要一种进程使用完之后另一种进程才干使用。(2分)（2）mutex：用于互斥信号量，初值为1。（2分） 进程A 进程B . . P(mutex) P(mutex) 申请打印机 申请打印机 使用打印机 使用打印机 V(mutex) V(mutex) . .9、 进程process_A 进行计算后通过进程process_B输出，这两个并发进程程序如下：int Count=0;process_A() do Count = Count + 10 while(1)process_B() do print(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 + 10 Count =0;（3）实现同步 信号量：S11，S20；process_B() do wait(S2) wait(mutex);print(Count) Count =0;Signal(mutex)Signal(S1) while(1) 信号量：mutex1；int Count=0;process_A() do wait(S1) wait(mutex);Count = Count + 10Signal(mutex)Signal(S2) while(1)10、 有一种阅览室，共有100个座位，读者进入时必要先在一张登记表上登记，该表为每一座位列一表目，涉及座号和读者姓名等，读者离开时要消掉登记信息，试问：（？）（1）为描述读者动作，应编写几种程序，设立几种进程？（2）试用PV操作描述读者进程之间同步关系。答：读者动作有两个，一是填表进入阅览室，这时要考虑阅览室里与否有座位；一是读者阅读完毕，离开阅览室，这时操作要考虑阅览室里与否有读者。读者在阅览室读书时，由于没有引起资源变动，不算动作变化。算法信号量有三个：seats表达阅览室与否有座位（初值为100，代表阅览室空座位数）；readers表达阅览室里读者数，初值为0；用于互斥mutex，初值为1。读者进入阅览室动作描述getin：while(TRUE)P (seats)； /*没有座位则离开*/P（mutex） /*进入临界区*/填写登记表;进入阅览室读书;V（mutex） /*离开临界区*/V（readers） 读者离开阅览室动作描述getout：while(TRUE)P（readers） /*阅览室与否有人读书*/P（mutex） /*进入临界区*/消掉登记；离开阅览室； V（mutex） /*离开临界区*/V（seats） /*释放一种座位资源*/11、 假定进程A负责为顾客作业分派打印机，进程B负责释放打印机，系统中设立一种打印机分派表如下，由各个进程共用。 打印机编号分派标志顾客名顾客定义设备名001020试用P，V操作实现两进程对分派表互斥操作。解答：设一种互斥信号量mutex，其初值为1。 P1（分派进程）和P2（释放进程）临界区代码可按下述形式构成： P（mutex）； P（mutex）； 分派打印机； 释放打印机； （读写分派表） （读写分派表） V（mutex）； V（mutex）；12、 设系统中只有一台打印机，有二个顾客程序在执行过程中都要使用打印机输出计算成果。设每个顾客程序相应一种进程。问：这二个进程间有什么样制约关系？试用P，V操作写出这二个进程使用打印机算法。解答：由于打印机是一种临界资源，因此这二个进程只能互斥地使用这台打印机。即一种顾客计算成果打印完后，另一种顾客再打印，因而是互斥关系。 设两个进程分别为A和B，设一种互斥信号量mutex，其初值为1，其算法如下： A进程 B进程 P（mutex）； P（mutex）； 使用打印机； 使用打印机； V（mutex）； V（mutex）； 13、 设P1，P2两进程共用一种缓冲区F，P1向F写入信息，P2则从F中读出信息。问这两个进程间是什么样制约关系？试用P，V操作写出这两个进程读写缓冲区算法。解答： A，B两进程间是同步关系，即A进程向Q写满信息后，B进程才干从Q中取走信息。为此，设立两个信号量： empty：表达缓冲区Q为空（0为不空，1为空），初值为1， full： 表达缓冲区Q为满（0为不满，1为满），初值为0。 算法如下：A进程： B进程： while(true) while(true) P（empty）； P（full）； 向Q写入信息； 从Q中读出信息； V（full）； V（empty）； 注：若信号量初值不同，算法有些不同。如若empty和full初值均为0，则A进程算法中P(empty)语句应放在V(full)之后，即 解法不惟一 。14、 设A1，A2为两个并发进程，它们共享一临界资源，其临界区代码分别为CS1，CS2。问这两个进程间是什么样制约关系？试用P，V操作写出这两个进程共享临界资源算法。解答： 由于A，B两个进程是并发，它们共享一种临界资源，因此两个进程间应互斥地进入临界区。设立一种互斥信号量mutex，其初值为1。详细算法如下： A进程： B进程： P（mutex）； P（mutex）； 临界区代码Csa； 临界区代码Csb； V（mutex）； V（mutex）；15、 设有一台计算机，有一条I/O通道，接一台卡片输入机，卡片机把一叠卡片逐个输入到缓冲区Q1中，计算机从缓冲区Q1中取出数据再进行加工解决。假设系统中设一种输入进程Pr和一种计算进程Pc来完毕这个任务。问这两个进程间有什么样制约关系？请用P，V操作写出这些进程算法。解答： 进程Pr受Pc进程影响，B1放满信息后，Pr进程要等待，等Pc进程将其中所有信息取走，才干继续读入信息；同样地，Pc进程受Pr进程约束，B1中信息放满后Pc进程才干从中取走信息。因而，两者之间是同步制约关系。 设两个信号量：B1full缓冲区B1满，初值为0； B1empty缓冲区B1空，初值为1。算法如下：Pr进程： Pc进程：while(true) while(true)P（B1empty）； P（B1full）；卡片信息写入缓冲区； 从B1中取出信息； V（B1full）； V（B1empty）； 注：若B1fullt 和B1empty初值均为0，这时进程Pr有所不同，即，P(B1empty)；应放在V(B1full)之后。也即解法不惟一 。* 运用信号量实现前趋关系 Var a,b,c,d,e,f,g；semaphore=0,0,0,0,0,0,0; begin parbegin begin S1；signal(a)；signal(b)；end; begin wait(a)；S2；signal(c)；signal(d)；end; begin wait(b)；S3；signal(e)；end; begin wait(c)；S4；signal(f)；end; begin wait(d)；S5；signal(g)；end; begin wait(e)；wait(f)；wait(g)；S6；end; parend end 16、 各种进程共享一种文献，其中只读文献进程称为读者，只写文献进程称为写者。读者可以同步读，但写者只能独立写。下面同步算法是用P、V操作写出，并且它对写者优先，即一旦有写者到达，后续读者必要等待。（8分）问题：1）、在上述算法空白处填上对的语句，使得该算法完整。2）、该算法有也许会浮现什么问题？算法如下：int rmutex=1，wmutex=1,count=0（正在读读者个数）,s=1;main()p(rmutex);count-;if (count=0) _(5)_；v(rmutex);writer() while(1) p(s)；p(wmutex); 写文献；v(wmutex);v(s);parbegin reader(); writer();parend;reader()while(1)_(1)_;_(2)_;if (count=0) p(wmutex);count+;_(3)_;_(4)_;读文献；答：1）问题1： （1）_p(s)_ （2）_p(rmutex)_(3)_v(rmutex)_ （4）_v(s)_ （5）_v(wmutex)_ 2)问题2：如果持续浮现新写者进程，则也许导致读者进程饿死。17、 指出下列哲学家就餐问题算法在什么状况下会导致死锁，并改进此算法，使它不会产生死锁。 算法描述： 五个哲学家在一张圆桌上进行思考和吃饭。哲学家思考时，并不影响她人。只有当她吃饭时，她才试图拿起左右两根筷子（一根一根拿起）。如果筷子已在她人手上，则需等待。只有当她同步拿起左右两根筷子时，才可以吃饭。如图7-1所示：程序描述为：（第i个哲学家,i=0,1,2,3,4） Var chopstick：array0.4 of semaphore；/* 各信号量初值均为1*/ Repeat P(chopsticki)；/* P操作，拿左筷子*/ P(chopsticki+1 mod 5)；/* P操作，拿右筷子*/ Eat();/*吃饭*/ V(chopsticki)；/*V操作，放下左筷子*/ V(chopsticki+1 mod 5)；/* V操作，放下右筷子*/ 图7.1 Think();/*思考*/ Until false;答：1）、也许导致死锁状况：每位哲学家都拿了左筷子，而在等待右筷子。即每位哲学家进程都只执行了语句：P(chopsticki)。2）、改进：编号为双数哲学家先拿左筷子，而单数先拿右筷子。程序为：Repeat if (i mod 2 = 0) P(chopsticki)；P(chopsticki+1 mod 5)； else P(chopsticki+1 mod 5)；P(chopsticki)； Eat()； V(chopsticki)；V(chopsticki+1 mod 5)；Think(); Until false;18、 简述信号量定义和作用。P，V操作原语是如何定义？解答：信号量普通是由两个成员构成数据构造，其中一种成员是整型变量，表达该信号量值，它是与相应资源使用状况关于；另一种是指向PCB指针。当各种进程都等待同一信号量时，它们就排成一种队列，由信号量指针指出该队列头。信号量普通可以简朴反映出相应资源使用状况，它与P，V操作原语一起使用可实现进程同步与互斥。 P，V操作原语定义：P（S）：顺序执行下述两个动作： 信号量S值减1，即S=S-1； 如果S0，则该进程继续执行，如果S0，则把该进程状态置为阻塞态，把相应PCB连入该信号队列末尾，并放弃解决机，进行等待。（直到有其他进程在S上执行V操作，把它释放出来为止。） V（S）：顺序执行下述两个动作： 信号量S值加1，即S=S+1； 如果S0，则该进程继续执行，如果S0，则释放信号量队列上第一种PCB（即信号量指针所指向PCB）所相应进程（把阻塞态改为就绪态），执行V操作态进程继续执行。19、 某虚拟存储器顾客编程空间共321KB，内存为16KB。假定某时刻一顾客页表中已调入内存页面页号和物理块号对照表如下：页号物理块号051102437则逻辑地址0A5C（H）所相应物理地址是什么？解答：逻辑地址0A5CH）所相应二进制表达形式是：0000 1010 0101 1100 ，由于1K=210，下划线某些前编码为000010，表达该逻辑地址相应页号为3查页表，得到物理块号是4（十进制），即物理块地址为：0001 0010 0000 0000 ，拼接块内地址0000 0000 0101 1100，得0001 0010 0101 1100，即125C（H）。20、 某段表内容如下：段号段首地址段长度0120K40K1760K30K2480K20K3370K20K 一逻辑地址为（2，154）实际物理地址为多少？答：逻辑地址（2154）表达段号为2，即段首地址为480K，154为单元号，则实际物理地址为480K+154。21、 (1) 某页式存储系统页表如下，设每页1KB，请写出逻辑地址为8300时所相应页号和页地址，以及在内存中相应物理地址。（请详细写出运算过程） 系统页表： 页号012345678块号3561087124（2）已知如下段表：段号01234基址21923009013271952长度6001410058096在分段存储管理下系统运营时，下列逻辑地址（第一位表达段号，第二位表达段内位移）物理地址是什么？（a）：（1，10） （b）：（4，112）答：（1）页号P=INTA/L=8300/1024=8 页内地址d=A MOD L=8300 MOD 1024=20 物理地址 41024+108=4024 (2) (a)：地址（1，10）段号为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算法： 访问串601204312674256 驻留集666664444444222000003333333551111111666666222222277777与否缺页缺页中断率为：10/15=66.67%（2）、采用LRU算法： 访问串601204312674256 驻留集666664444666655000000022222221111333377776222211114444与否缺页缺页中断率为：13/15=86.67%教材P156，6题（中南大学出版社）解答：访问串为：1，2，3，4，2，1，5，6，2，1，3，7，6，3，2，1，2，3，6（一）、页框数为3时：(1) FIFO算法1 2 3 4 2 1 5 6 2 1 3 7 6 3 2 1 2 3 6111223415621337662122334156213776221334415621376621136+ + + + + + + + + + + + + + + +故障数：16 页故障率：16/19 * 100% = 84%(2) LRU(近来最久未用页面)算法1 2 3 4 2 1 5 6 2 1 3 7 6 3 2 1 2 3 6111234215621376331222342156213763212334215621376321236+ + + + + + + + + + + + + + +故障数：15 页故障率：15/19 * 100% = 79%(3) OPT算法1 2 3 4 2 1 5 6 2 1 3 7 6 3 2 1 2 3 6111111111133333333322222222227772222234445666666661116+ + + + + + + + + + +故障数：11 页故障率：11/19 * 100% = 58%23、 画出段页式存储管理系统地址变换过程图。24、 假定在某移动臂磁盘上，刚刚解决了访问75号柱面祈求，当前正在80号柱面读信息，并且有下述祈求序列等待访问磁盘： 试用：(1)电梯调度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道上服务， 并且刚刚完毕了125道祈求. 既有如下访盘祈求序列(磁道号): 86，147，91，177，94，150，102，175，130 试给出采用下列算法后磁头移动顺序和移动总量(总磁道数). (1). 先来先服务(FCFS)磁盘调度算法. (2). 最短寻道时间优先(SSTF)磁盘调度算法.(3). 扫描法(SCAN)磁盘调度算法.(假设沿磁头移动方向不再有访问祈求时，磁头沿相反方向移动.)答案：磁头移动顺序：（1）86，147，91，177，94，150，102，175，130 （2）当前磁头在143道上： 147，150，130，102，94，91，86，175，177 （3）当前磁头在143道上，并且刚刚完毕125道祈求 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字节，如果不考虑逻辑块号在物理块中所占位置，分别求二级索引和三级索引时可寻址文献最大长度。答：（1）、采用二级索引，可寻址文献最大长度： （512/3）*（512/3）*512=170*170*512=14796800（字节）（2）、采用三级索引，可寻址文献最大长度： （512/3）*（512/3）*（512/3）*512=170*170*170*512=（字节）27、 设当前工作目录在da1请看图回答(1) 文献mc.c绝对途径名 （ /data/da1/ma.c ） 。(2) 文献mc.c 相对途径名 （ mc.c ） 。(3) 要在文献abc本来权限基本上增长让所有顾客都具备执行权限，请用一条命令完毕该功能 （ chmod a + x abc ） 。(4) 将文献mc.c在当前目录下复制一份副本，副本文献名为sss.c输入命令是 （ cp mc.c sss.c ） 。(5) 在当前目录下，创立子目录sd2命令是 （ mkdir sd2 ） 。(6) 要让所有顾客对文献abc都具备读、写、执行权限。命令是 （ chmod a + rwx abc 或 chmod 777 abc ） 。(7) 命令$ cat /data/da3/sun.c 实际功能是 （ 在屏幕上显示/data/da3子目录下sun.c文献内容） 。（8） 删除sd1子目录下、扩展名为 BAS 所有文献，输入命令是 （ rm sd1/ *.BAS ） 。（9） 删除子目录sd1下所有文献和子目录，命令是 （ rm r /data/da1/sd1 ） 。 (10) 输入命令 $ chmod 754 abc 后，同组顾客对文献abc存取权限是 （ 读和执行 ） 、其他顾客对文献abc权限是 （ 只读 ） 。 (11) 删除文献mc.c。 命令是 （ rm mc.c ） 。 (12) 在显示屏上以长格式列出da1下所有目录项 （ ls l /data/da1 （或 ls l） ） .28、 设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：最大需求量已分派资源量剩余资源量A B CA B CA B C P1 8 6 41 2 12 1 1 P2 4 3 33 1 1 P3 10 1 34 1 3 P4 3 3 33 2 2 P5 5 4 61 1 3(1) 系统与否处在安全状态？如是，则给出进程安全序列.(2) 如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实行分派？为什么？答案：（1）运用安全性算法对T0时刻资源分派状况进行分析，成果如下：