操作系统复习习题集.docx

《操作系统复习习题集.docx》由会员分享，可在线阅读，更多相关《操作系统复习习题集.docx（12页珍藏版）》请在优知文库上搜索。

1、1.假设一只盘子一次只能放一个水果，A只往盘中放苹果，B只往盘中放梨子，C只从盘中取苹果，D只从盘中取梨子。试用：(1)信号量和P、V操作；(2)管程，写出同步算法。解：(1)采用P、V操作的同步算法如下：semaphoreSAB=1;/A、B的资源信号量，同时又是它们的互斥信号量semaphoreSC=O;/C的资源信号量(用于与A同步)semaphoreSD=O;/D的资源信号量(用于与B同步)beginparbeginprocessA:进程A的算法描述(while(true)取一个苹果；wait(SAB);测试盘子是否为空将一苹果放入盘中；SignaI(SC)通知C盘中已有苹果(可能唤醒

2、C)processC:while(true)wait(SC);测试盘子是否有苹果从盘中取出苹果；SignaI(SAB);通知A(或B)盘子一空(可能唤醒A或B)消费该苹果；)processB:进程B的算法描述while(true)取一个梨子；wait(SAB);测试盘子是否为空将一梨子放入盘中；SignaI(SD)通知D盘中已有梨子(可能唤醒D)processD:(while(true)wait(SD);测试盘子是否有梨子从盘中取出梨子；SignaI(SAB);通知A(或B)盘子一空(可能唤醒A或B)消费该梨子；)parendend(2)采用管程的同步算法如下：首先定义管程MPC,该管程可描述

3、如下：typeMPC=monitorvarflag:integer;fIag=O:盘中无水果；=1盘中有苹果；=2盘中有梨子empty:condition;用于A或B等待空盘子W:array1.2ofconditionW用于等待苹果，W2用于等待梨子procedureentryput(integerk)beginifflagOthenempty.wait;生产者A或B进程阻塞fag=k;放一k号水果入盘中；设1号水果为苹果，2号水果为梨子ifWk.queuethenfull.signal;假设有等待k号水果者，那么唤醒之endprocedureentryget(integerk)beginif

4、fagkthenWk.wait;消费者C或D进程阻塞从盘中取k号水果；flag:=0;ifempty.queuethenempty.signal;假设等待队列非空，那么唤醒队首的一个生产者进程endbeginflag:=0;初始化内部数据endA、B、C、D四个进程的同步算法可描述如下：parbeginProcessAbegin任取一个苹果；MPCput(I);endProcessBbegin任取一个梨子；MPC.put(2);endProcessCbeginMPCget(I);吃苹果；endProcessDbeginMPC.get(2);吃梨子；endparend2.设自行车生产车间有两个货

5、架，货架A可以存放8个车架，货架B可以存放20个车轮；又设有4个工人，他们的活动是重复劳动，分别为：工人1加工一个车架放入货架A中；工人2、3分别加工车轮放入货架B中(每人每次放入1个车轮)；工人4从货架A中取一个车架，再从货架B中取两个车轮，组装成一辆自行车。试用PV操作实现四个工人的合作。【分析】信号量AemPty表示货架A的空位数，其初值为8：信号量AfUll表示货架A上存放的车架数，其初值为0;信号量BemPty表示货架B的空位数，其初值为20；信号量BfUIl表示货架B上存放的车轮数，其初值为0；信号量mutex用于互斥(初值为1)。解：BEGINsemaphoreAempty,Be

6、mpty,AfuILBfulhmutex；Aempty：=8；Bempty：=20：Afull：=0；Bfull：=0：mutex：=1；ParbeginWorkerl：BEGIN1.I：生产1个车架；P(Aemptyh测试货架A是否有空位置P(mutex)；互斥使用货架A车架放到货架A；V(AfuII);货架A上的车架数增1,必要时唤醒等待的进程V(mutex)；gotoLI；ENDWOrker2、3：BEGIN1.2：生产1个车轮；P(Bempty);测试货架B是否有空位置P(mutex)；互斥使用货架B车轮放到货架B：V(BfuII):货架B上的车轮数增1,必要时唤醒等待的进程V(mut

7、ex)：gotoL2；ENDWorker4:BEGIN1.3：P(AfuII);测试货架A上是否有车架P(BfuII);P(BfuII);测试货架B上是否有2个车轮P(mutex)；取1个车架；取2个车轮；V (Aempty);货架A空位置增1V (Bempty);V(BemPty)；货架B空位置增2V (mutex)；组装成一辆自行车；gotoL3；ENDPARENDEND3 .有两个作业A和B,分别在7:00和8:30到达系统，它们估计的计算时间分别为0.8小时和0.1小时，系统在9:00开场以响应比高者优先算法进展调度。在单道系统中该两个作业被选中时的响应比各为多少解：9:00时，作业A

8、的响应比=1+油.8=3.5作业B的响应比=1+0.5/0.1=6所以9:00时作业调度程序选中作业B9:06作业B完毕，调度作业A,此时作业A的响应比=1+2.1/0.8=3.625综上可知，在单道系统中A、B两个作业被选中时的响应比分别为3.625和64 .有一个具有两道作业的批处理系统（最多可有两道作业同时装入内存执行），作业调度采用计算时间短的作业优先调度算法，进程调度采用以优先数为根基的抢占式调度算法，今有如下作业序列，作业优先数即为进程优先数，优先数越小优先级越高：作业名到达时间估计运行时间优先数Jl10:1020分钟5J210:2030分钟3J310:3025分钟4J410:50

9、20分钟6列出所有作业进入内存时间及完毕时间。（1）计算平均周转时间。解：先作必要的分析（可在草稿纸上完成，分析过程不计分）：10：10JI被调入，开场运行10：20J2进入内存，因优先级高，开场运行JI运行了10分钟，还剩10分钟，因优先级低，运行态变就绪态10：30JI继续就绪J2运行了10分钟，还剩20分钟J3到达，但不能被调入10：50J2运行完毕，J4到达调入短作业J4,但因J4优先级比JI低，Jl开场继续运行11：00JI运行完毕J3被调入，因优先级高，开场运行J4因优先级低，仍就绪11：25J3运行完毕，J4开场运行11：45J4运行完毕（1）各个作业进入主存时间、完毕时间和周转

10、时间如下表所示：（6分）作业名提交时间进入时间完毕时间周转时间Jl10：1010：1011：0050J210：2010：2010：5030J310：3011：0011：2555J410：5010：5011：4555(2)平均周转时间：(50+30+55+55)/4=47.5(min)5 .有一个多道程序设计系统，采用不可移动的可变分区方式管理主存空间，设主存空间为100K,采用最先适应分配算法分配主存，作业调度采用响应比高者优先算法，进程调度采用时间片轮转算法(即内存中的作业均分CPU时间)，今有如下作业序列：作业名提交时间需要执行时间要求主存量Jl10:0040分钟25KJ210:1530分

11、钟60KJ310:3020分钟SOKJ410:3525分钟18KJ510:4015分钟20K假定所有作业都是计算型作业且忽略系统调度时间。答复以下问题：(1)列表说明各个作业被装入主存的时间、完成时间和周转时间；(2)写出各作业被调入主存的顺序；(3)计算5个作业的平均周转时间。解：先作必要的分析(可在草稿纸上完成，分析过程不计分)：10：00JI到达，被调入内存并开场运行，内存剩75KB10：15J2到达，被调入内存并开场与Jl一起运行。Jl运行了15分钟，还需执行25分钟。内存剩15KB10：30J3到达，因内存不能满足，不被调入。JI、J2继续运行。10：35J4到达，因内存不能满足，不

12、被调入。此时Jl相当于已运行了15+10=25分钟，还需执行15分钟；J2相当于已运行了10分钟，还需执行20分钟。10：40J5到达，因内存不能满足，不被调入。JI、J2继续运行。11：05JI运行完毕，J2还需执行5分钟。内存中的2个空闲分区分别是25K和15K,能满足J4或J5需求，但不能满足J3的需要。J4的响应比=1+30/25=2.2；J5的响应比=1+215=2.67,J5被调入内存并与J2一起运行，内存中的空闲分区大小是5KB和ISKo11：15J2运行完毕，内存中的空闲分区是65KB和15K。J3的响应比=1+420=3.25,J4的响应比=1+40/25=2.6,J3被调入

13、内存与J5一起运行。内存中的空闲分区大小是15KB和15KoJ3需执行20分钟，J5还需执行10分钟。11：35J5运行完毕，J4调入内存运行。J3还需执行10分钟，J4还需执行25分钟。11：55J3运行完毕12：10J4运行完毕答：(1)各个作业被装入主存的时间、完成时间和周转时间如下表所示：作业名装入主存时间作业完成时间周转时间Jl10：0011：0565J210：1511：1560J311：1511：5585J411：3512：1095J511：0511：3555(2)作业被调入主存的顺序为Jl,J2,J5,J3,J4。(3)平均周转时间=(65+60+85+95+55)/5=72(分

14、钟)。(3)(北京大学1997年试题)某系统有AB,C三类资源(数量分别为学,5,20)和P1P5五个进程，在To时刻系统状态如下表所示：进程最大资源需求量已分配资源数量ABCABCPl559212P2536402P34011405P4425204P5424314系统采用银行家算法实施死锁防止策略,请答复以下问题：TO时刻是否为安全状态假设是，请给出安全序列。在TO时刻假设进程P2请求资源（0,3,4）,是否能实施资源分配为什么在的根基上，假设进程P4请求资源（2,0,1）,是否能实施资源分配为什么解：由条件可得尚需矩阵Need和可用资源向量AValable如下：NeedAvalableABCABCPl347233P2134P3006P4221