操作系统大题.docx

1.这是一个从键盘输入到打印机输出的数据处理流图，其中键盘输入进程通 过缓冲区bufl把输入数据传送给计算进程，计算进程把处理结果通过缓冲 buf2传送给打印进程。bufl和buf2为临界资源，试写出键盘输入进程，计 算进程及打印进程间的同步算法。(10分)输入进程f bufl f计算进程f buf2 f打印进程解答：从键盘输入到打印机输出的数据传送过程，可以看作是由键盘输入进程到计算进程， 以及由计算进程到打印输出进程这两个数据传送进程所组成。其中，对键盘输入进程而言， 计算进程是消费者进程；而对打印输出进程而言，计算进程又是生产者进程。据此可将它 们之间的同步问题描述如下：var： mutexl，mutex2，emptyl，empty2，fulll，full2： =1，1，1，1，0，0； IP:beginrepeatP(empty);P(mutexl);input a charcter from keyboard;Add to buffer;V(mutexl);V(full);until falseendCP:beginrepeatP(full);P(mutex1);Take a charactor form bufferl;Add to ch1;V(mutex1);V(empty1);P(empty2);P(mutex2);Take a charactor form ch1;Add to buffer2;V(mutex2);V(full2);until falseendOP:beginrepeatp(full2);P(mutex2);Take a charactor from buffer2;Add to printer controler;start printer;V(mutex2);V(empty2);until falseend2.设在一个页面大小为1K的系统中，正在处理器上执行的一个进程的页表如图所示:页号状态位 访问位 修改位 物理块号01104111172000-310024000-51010起始页号和块号均为0。1.详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。解：2.5449的物理地址为：3292221的物理地址为：22213.设系统有三种类型的资源，数量为(4, 2, 2)，系统中有进程A, B, C按如 下顺序请求资源：进程A申请(3, 2, 1)剩余资源(1, 0, 1)(0, 0, 0)(3, 2, 1)1)1)0)(不满足)进程B申请（1，0, 1）进程A申请（0，1, 0）进程C申请（2, 0, 0）请你给出一和防止死锁的资源剥夺分配策略，完成上述请求序列，并列出 资源分配过程，指明哪些进程需要等待，哪些资源被剥夺。（10分） 解：（10分） 分配策略为：当进程pi申请类资源时，检查%中有无可分配的资源：有则分配给Pi； 否则将匕占有的资源全部释放而进入等待状态o（pi等待原占有的所有资源和新申请的资源） 资源分配过程：1进程A： （3, 2进程B： （1, 0进程A： （0, 1A的所有资源被剥夺，A处于等待(1, 2, 1)进程 C： （2, 0, 0）C, B完成之后，A可完成。4. 设公共汽车上，司机和售票员的活动分别是：司机：启动车辆正常行车到站停车售票员：上乘客关车门售票 开车门 '下乘客在汽车不断地到站，停车，行使过程中，这两个活动有什么同步关系？并用wait和signal原 语操作实现它们的同步。解：BEGIN integer stop,run;Stop:=0;Run:=0;COBEGINDriver: BEGINL1: wait（run）;启动车辆；正常行车；到站停车；signal(stop);Goto L1;ENDConductor: BEGINL2：上乘客;关车门； signal(run); 售票；wait(stop);开车门； 下乘客； Goto L2;ENDCOENDEND5、某虚拟存储器的用户编程空间共321KB,内存为16KB。假定某时刻一用户页表中已调入内存 的页面的页号和物理块号的对照表如下：则逻辑地址0A5C（H）所对应的物理地址是什么？答：逻辑地址0A5CH）所对应的二进制表示形式是：0000 1010 0101 1100,由于1K=210下划线部分前的编码为000010，表示该逻辑地址对应的页号为3查页表，得到物理块号是4 （十进制），即物理块地址为：0001 0010 0000 0000，拼接块内地址0000 0000 01011100，得 0001 0010 0101 1100,即 125C（H）。6、某段表内容如下：段号段首地址段长度0120K40K1760K30K2480K20K3370K20K一逻辑地址为（2, 154）的实际物理地址为多少？答：逻辑地址（2154）表示段号为2,即段首地址为480K，154为单元号，则实际物理地址 为 480K+154。7、设系统中有三种类型的资源（A，B，C）和五个进程（P1，P2, P3, P4, P5），A资 源的数量为17, B资源的数量为5, C资源的数量为20。在T0时刻系统状态如表1和表2 所示。（共10分）系统采用银行家算法实施死锁避免策略。 T0时刻是否为安全状态？若是，请给出安全序列。 在T0时刻若进程P2请求资源（0，3, 4），是否能实施资源分配？为什么？ 在的基础上，若进程P4请求资源（2, 0，1），是否能实施资源分配？为什么？ 在的基础上，若进程P1请求资源（0，2, 0），是否能实施资源分配？为什么？最大资源需求量已分配资源数量ABCABCP1559212P2536402P34011405P4425204P5424314表1T0时刻系统状态表2T0时刻系统状态ABC剩余资源数2338.系统中有五个进程PP2、P3、P4、5，有三种类型的资源：R1、R2、和R3。在T0 时刻系统状态如表所示。若采用银行家算法实施死锁避免策略，回答下列问题：（共9分, 每小题3分）1. T0时刻是否为安全状态？为什么？2. 若这时？4请求资源（1, 2, 0）,是否能实施资源分配？为什么？3. 在上面的基础上，若进程P3请求资源（0, 1, 0）,是否能实施资源分配？为什么？T0时刻系统状态已分配资源数量最大资源需求量R1R2R3R1R2R3P1001001P2200275P3003665P4115435P5033065R1R2R3剩余资源数330解：（共9分，每小题3分）1. T0时刻是安全的，安全序列为：P1, P4, P5, P2, P32. P4请求资源（1, 2, 0）,根据银行家算法，预分配后系统是安全的，安全 序列为：P1, P4, P5, P2, P33. P3请求资源（1, 1, 0）,根据银行家算法，预分配后系统不安全，所以不 能实施资源分配。9. 一个进程的大小占5个页面，每页的大小为1K，系统为它分配了 3个物理块。当前进程的页表如图所示：（共8分）块号存在位P 访问位R修改位M0x1C1100x3F1110000x5D1000001. 有那些页面不在内存？（ 2分）2. 请分别计算进程中虚地址为0x3B7、0x12A5、0x1432单元的物理地址（用十六进制表示），并说明理由。（6分）解：（共8分）不在内存的是第2和4页（按页号），或第3和5页（按序号）。（2分）0x3B7的物理地址=0x 73 B7（2分）0x12 A5的物理地址=0x176 A5,缺页，换出第三页。（2分）0x1432地址越界，出错。（2分）10. 系统运行有三个进程：输入进程、计算进程和打印进程，它们协同完成工 作。输入进程和计算进程之间共用缓冲区bufferl,计算进程和打印进程之间共 用缓冲区buffer2。输入进程接收外部数据放入bufferl中;计算进程从bufferl 中取出数据进行计算，然后将结果放入buffer2；打印进程从buffer2取出数据 打印输出。用算法描述这三个进程的工作情况，并用wait和signal原语实现其同步操作。 （共8分）解：（共8分）解答：输入进程、计算进程和打印进程之间的同步问题描述如下：var： mutexl, mutex2, emptyl, empty2, fulll, full2： =1, 1, 1, 1, 0, 0； InP:beginrepeatwait（empty1）;wait（mutex1）;input a data from keyboard;Add to buffer1;signal（mutex1）;signal（full1）;until falseendCalP:beginrepeatwait（full1）;wait（mutex1）;Take a data form buffer1;Add to ch1;signal（mutex1）;signal（empty1）;calculate chi;wait (empty2);wait(mutex2);Take a data form chi;Add to buffer2;signal (mutex2);signal (full2);until falseendOutP:beginrepeatwait(full2);wait(mutex2);Take a data from buffer2;Add to printer controler;signal(mutex2);signal(empty2);start printer;until falseend(评分标准：信号量设置2分，输入进程、计算进程、打印进程各2分)11.在一个请求分页系统中，有一个长度为5页的进程，假如系统为它分配3个物 理块，并且此进程的页面走向为2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2。试用FIFO 和LRU两种算法分别计算出程序访问过程中所发生的缺页次数。(10分)解：FIFO：232152453252第1页222555333第2页33322255第3页1114442缺页中断次数=6LUR：232152453252第1页22225553第2页3352335第3页114422缺页中断次数=512.进程A1, A2,，An通过K个缓冲区向进程B1, B2,，Bm 不断地发送 消息。发送和接收工作遵循如下规则：1. 每个发送进程一次发送一个消息，写入缓冲区，缓冲区大小与消息长度一致；2. 对每个消息，B1, B2,，Bm都需接收一次，读入各自的数据区内；3. K个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。试用wait和signalM语操作组织正确的发送和接收操作。（10分）解：BEGINInteger Mutex, Availn, Fullm;Integer I;Mutex:=1;FOR i:=1 TO m DOBEGINAvailI := k;FullI := 0;ENDPROCEDURE Send（K）Integer I;BEGIN13. 一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所 示（都为十进制数，且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算 法，哪一个物理块将被换出？并解释原因.（10分）页号块号加载时间访问时间访问位R修改位M20601610111130160000226162103320163111. IFO算法2. LRU算法3. CLOCK 算法4. 当页面的访问串为：“4, 0，0，0，2, 4, 2，1，0，3, 2”的OPT算法解：1.换出第3号虚页，因为它加载的时间最早；2. 换出第1号虚页，因为它最近最久没被访问；3. 换出第1号虚页，因为它最近既没被访问，又没被修改；4. 换出第3号虚页，因为它离访问点最远。14.用整型信号量描述在哲学家进餐问题中，至多允许4个哲学家同时进餐的算法。（10分） 解：public class diningphilosophers （semaphore fork = new semaphore 5 （1）;semaphore room = new semaphore （4）;int i;void philosopher (int i) (while (true) think();wait (room);wait (forki);wait (fork (i+1) % 5);eat();signal (fork (i+1) % 5);signal (forki);signal (room); void main() (parbegin (philosopher (0), philosopher (1), philosopher (2),philosopher (3), philosopher (4);15.考虑一个有150个存储器单元的系统，如下分配给三个进程：进程最大占有1 70452 60403 6015使用银行家算法，以确定下面的任何一个请求是否安全：a. 第4个进程到达，最多需要60个存储单元，最初需要25个单元;b. 第4个进程到达，最多需要60个存储单元，最初需要35个单元;如果安全给出安全序列；若不安全给出结果分配简表。（10分） 解：进程最大 占有 尚需 可用170452525260402036015454602535安全序夕列为:1、2、3、4所以系统是安全的，可以进行分配。b.进程最大占有尚需可用170452515260402036015454603525当前可用的资源不够任何一个进程运行完毕，所以不安全。16. Jruassic公园有一个恐龙博物馆和一个公园.有m个旅客和n辆车，每辆车只能容纳一 个旅客。旅客在博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它载入 一个旅客，然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车 的旅客需要等待；如果一辆车已经就绪，但没有旅客等待，那么这辆车等待。使用信 号量同步皿个旅客和n辆车的进程。（10分）解：visitors=m;cars=n;mutex=1;Pvi()Pci() repeat repeatwait(cars);wait(visitors);wait(mutex);wait(mutex);get on;start;travell;run;get off;stop;signal(cars);signal(visitors);wait(mutex);wait(mutex);until false;until false;17.读者与写者问题（reader - writer problems ）（10 分）在计算机体系中，对一个共享文件进行操作的进程可分为两类：读操作和写操作，它们分 别被称为读者和写者。访问该文件时读者和写者，写者和写者间必须实现互斥。只有在没 有读者访问文件时，写者才允许修改文件。或者写者在修改文件时不允许读者去读，否则 会造成读出的文件内容不正确。试写出算法描述读者和写者的问题。解：为了实现读者与写者的同步和互斥，我们设置一个信号量S，用于读者与写者之间或写 者与读者之间的互斥，初值为“1”。用一个变量rc表示当前正在读的读者个数，当进程可 以去读或读结束后都要改变rc的值，因此rc又成为若干读进程的共享变量，它们必须互 斥地修改rc。故必须定义另一个用于互斥的信号量Sr，初值也是“1”。读者-写者问题可描述如下:S, Sr： semaphore；int rc = 0;process Reader I (i=1,2,.,m) beginP(Sr); rc = rc+1; if (rc=1) P(S); V(Sr);read file F;P(Sr); rc = tc-1; if (rc=0) V(S); V(Sr);endS=Sr=1;process Writer j (j=1,2,.,k) beginP(S);Write file F;V(S);end18、若干个等待访问磁盘者依次要访问的磁道为20, 44, 40, 4, 80, 12, 76,假设每移动 一个磁道需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别写出访问序列并 计算为完成上述各次访问总共花费的寻道时间。（1）先来先服务算法；（2）最短寻道时间优先算法。（3）扫描算法（当前磁头移动的方向为磁道递增）（10分）解：（1）磁道访问顺序为：20，44, 40，4, 80，12, 76寻道时间=（20+24+4+36+76+68+64）*3=292*3=876（2）磁道访问顺序为：40，44, 20, 12, 4, 76, 80寻道时间=（0+4+24+8+8+72+4）*3=120*3=360（3）磁道访问顺序为：40，44, 76, 80, 20, 12, 4寻道时间=（0+4+32+4+60+8+8）*3=116*3=34819、生产者和消费者问题（10分）有一组生产者P1, P2,PM和一组消费者C1, C2,CK，他们通过由n个环形缓冲区构成的缓冲池进行通信，生产者把产品放入缓冲区，消费者从缓冲区取产品来消费。请用 wait和signalM语实现他们的同步操作。解：生产者和消费者问题beginVar mutex,emptyfull:semaphore:=1,n,0; buffer:array0,-U of item;in,out:integer := 0,0;parbeginproducer: begin repeat produce next product ; wait (empty); wait (mutex); buffer(in):=nextp ; in := (in+1) mod n ;signal (full);signal (mutex);until false ;endconsumer: beginrepeatwait (full);wait (mutex);nextc := buffer(out);out := (out+1) mod n;signal (empty);signal (mutex);consume the item in nextc;until false ;endparend end20、请用信号量描述哲学家进餐问题。(15分)解：哲学家进餐问题(15分)public void philosopher (int i) (while (true) (think();wait (forki);wait (fork (i+1) % 5);eat();signal(fork (i+1) % 5);signal(forki);21. 今有三个并发进程R, M, P,它们共享了一个可循环使用的缓冲区B,缓冲区B共有 N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个 单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“,”； 进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则 又可用来存放下一次读入的字符。请用PV操作为同步机制写出它们能正确并发执行的程序。(10 分)解：(10分)beginVar mutex,input,calculate,output:semaphore:=1,n,0,0;buffer:array0,一1i of item;in,mid,out:integer := 0,0,0;proR() do wait (input);wait (mutex);buffer(in):=input data;in := (in+1) mod n ;signal (calculate);signal (mutex);while true ;proM() do wait (calculate);wait (mutex);buffer(middle):=calculate data ;mid := (mid+1) mod n ;signal (output);signal (mutex); while true ;proP() do wait (output);wait (mutex);buffer(out):=calculate data ;out := (out+1) mod n ;signal (input);signal (mutex); while true ;22. 理发店里有一位理发师、一把理发椅子和五把供等候理发的顾客坐的椅子。如果没有顾 客，理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正 在理发时又有顾客来到，而如果有空椅子可坐，他们就坐下来等，如果没有空椅子，他就 离开。这里的问题是为理发师和顾客各编写一段程序来描述他们行为，并用wait和signal 原语操作实现其同步。(10分)解：理发师问题#define CHAIRS 5 typedef int semaphore; semphore customers=0; semaphore barbers=0 semaphore mutex=1; int waiting=0; void barber (void) ( while(TRUE) ( wait(customers); wait(mutex); waiting=waiting-1; signal(barbers); signal(mutex);cut_hair(); void customers (void) ( wait(mutex);if (waiting<CHAIRS) (/*为等候的顾客准备椅子数*/ /*运用你的想像力*/ /*等候服务的顾客数*/ /*等候服务的理发师数*/ /*用于互斥*/*还没理发的等候顾客*/*如果顾客数是0，则睡觉*/*要求进程等候*/*等候顾客数减1*/* 一个理发师现在开始理发*/*释放等候*/*理发(非临界区操作)*/waiting=waiting+1;signal(customers);signal(mutex);wait(barbers); else signal(mutex);23、根据如下的前趋图写出可并发执行的程序：(10分)解：(10)评分：变量、进程、程序主体每项一分。var a,b,c,d,e,f,g,h,i:semaphore := 0,0,0,0,0,0,0,0;begin parbeginbegin S1;signal(a); signal(b); endbegin wait(a); S2; signal(c);signal(d); endbegin wait(c); S3; signal(e);signal(f); endbegin wait(b); S4; signal(g); endbegin wait(d);wait(e) S5; signal(h); endbegin wait(f); wait(g); S6 ; signal(i); endbegin wait(h); wait(i); S7; endparendend24、在公共汽车上，乘客上完后，售票员关门，驾驶员开车，售票员售票，到站汽车 停稳后，售票员开门，乘客上下车，售票员和驾驶员之间密切配合，直到下班。请用 信号量描述公共汽车上售票员与驾驶员的工作过程。(10分)解：建立驾驶员和售票员两进程，驾驶员进程执行过程如下：(1) 判售票员关门没有(2) 开车(3) 到站后停车（4）重复（1） （3）售票员执行过程如下：（1）判断乘客上完没有（2）关门（3）售票（4）判车停稳没有（5）开门（6）重复（1） （5）评分标准：执行过程完善3分，驾驶员与售票员合作消息正确3分售票员与驾驶员合作消息正确3分书写格式1分25、设某作业占有7个页面，如果在主存中只允许装入4个工作页面（即工作集为4）,作业运行时，实际访问页面的顺序是：1, 2，3, 6, 4, 7, 3, 2, 1, 4, 7,5, 6, 5, 2, 1。试用FIFO、LRU和CLOCK页面置换算法，列出各自的页面淘汰顺序和页面置换次数。（10分）解：FIFO：1,2,3,6,4,7,3,2,1,4,7,5,6, 5,2,11111444455222277776333322226666111页面置换次数为：6次LRU：1,2,3,6,4,7,3,2,1,4,7,5,6,5,2,111114441111666222277744442233333337777166622225555页面置换次数为：10次CLOCK：1,2,3,6,4,7,3,2,1,4,7,5,6,5,2,111114441111666222277744442233333337777166622225555页面置换次数为：10次26、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购 票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个 进程，请回答下列问题：（1）用wait和signal操作管理这些并发进程时，应怎样定义信号量，写出信号量的初 值以及信号量各种取值的含义。（2）根据所定义的信号量，加上wait和signal原语，写出购票者进程的算法，以保证 进程能够正确地并发执行。（3）若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）。解：（1）定义一信号量S,初始值为20。意义：S>0 S的值表示可继续进入售票厅的人数S=0表示售票厅中已有20名顾客（购票者）S<0 |S|的值为等待进入售票厅的人数（2）int S=20;COBEGIN PROCESS PI（I=1，2，）begin进入售票厅；wait（S）；购票；signal（S）;退出；end；COEND（3）S的最大值为20S的最小值为20n27. 设正在处理器上执行的一个进程的页表如下表所示，表中的虚页号和物理块号是十进制 数，起始页号（块号）均为0。所有的地址均是存储器字节地址。页的大小为1024字节。（10 分） 详述在设有快表的请求分页存储管理系统中，一个虚地址转换成物理内存地址的过程。 下列虚地址对应于什么物理地址：5499, 2221。进程的页表虚页号状态位访问位修改位物理块号01104111172000-310024000-51010解：5499的物理地址为：3792221 的物理地址为：3*1024+173=324528、假定系统有三个并发进程read, move和print共享缓冲器B1和B2。进程read负 责从输入设备上读信息，每读出一个记录后把它存放到缓冲器B1中。进程move从缓 冲器B1中取出一记录，加工后存入缓冲器B2。进程print将B2中的记录取出打印输 出。缓冲器B1和B2每次只能存放一个记录。要求三个进程协调完成任务，使打印出 来的与读入的记录的个数，次序完全一样。请用wait和signal原语写出它们的并发程 序。(10分)解：begin SR,SM1,SM2,SP:semaphore;B1,B2:record;SR:=1;SM1:=0;SM2:=1;SP:=0Cobeginprocess readX:record;begin R:(接收来自输入设备上一个记录)X:=接收的一个记录；waiut(SR)；B1:=X;signal(SM1);goto R;end;Process moveY:record;BeginM:wait(SM1);Y:=B1;signal(SR)加工 Ywait(SM2)；B2:=Y;signal(SP);goto M;end;Process printZ:record;BeginP:wait(SP);Z:=B2;signal(SM2)打印Zgoto P;end; coend;end;29、考虑下述页面走向:12, 3, 42, 1, 56, 2, 12, 3, 76, 3, 21, 2, 36当内存块数量分别为3时，试问FIFO、LRU、OPT 答：所有内存块最初都是空的，所以第一次用到的页面都产生一次缺页。3时：4, 21, 5, 6, 2, 12, 3,1 1 1 42 2 23 33 576,3,21 ,2,364 4666111225 5111FIFO 1, 23,2 2 611 13 3发生缺页中断的次数为16在FIFO64、1、56之前调入的页面，分别为5、1、24,可见4 为最先进入内存的，本次应换出，然后把页6LRU 1, 23,4, 21, 5, 6, 2,12,3,76, 3,21, 2, 361 1 1 4455 5 11 7 72 222 2 2 2 2 6 6 6 3 3 3 3 333 31112 222661发生缺页中断的次数为15在LRU65、2、16之前调入的页面，分别为5、1、22为最近一段 时间内使用最少的，本次应换出，然后把页6调入内存。OPT 1，23，4, 21, 5, 6,2，12，3，76, 3, 21, 2,361111113 33362222227222345666611发生缺页中断的次数为11在OPT61、2、56后面要调入的页面，分别为2、1、2， 可见5为最近一段时间内使用最少的，本次应换出，然后把页64、答：引入缓冲技术 的主要目的是：（123）使得一次输入的信息能多次使用。30. 若干个等待访问磁盘的进程依次要访问的磁道为27, 63, 57, 24, 107, 35, 106当前 磁头的位置为57号磁道，根据下面的磁盘调度算法，请给出调度的顺序，并计算平均寻道 长度。（10分）1. 先来先服务算法2. 最短寻道时间优先3. 扫描算法（当前磁头移动的方向为磁道递增）4. 循环扫描算法（当前磁头移动的