还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
1.若一只盘子一次只能放一个水果,A只往盘中放苹果,B只往盘中放梨子,C只从盘中取苹果,D只从盘中取梨子试用1信号量和P、V操作;2管程,写出同步算法解1采用P、V操作的同步算法如下semaphoreSAB=1;//A、B的资源信号量,同时又是它们的互斥信号量semaphoreSC=0;//C的资源信号量用于与A同步semaphoreSD=0;//D的资源信号量用于与B同步beginparbeginprocessA://进程A的算法描述{whiletrue{取一个苹果;waitSAB;//测试盘子是否为空将一苹果放入盘中;signalSC//通知C盘中已有苹果可能唤醒C}}processC:{whiletrue{waitSC;//测试盘子是否有苹果从盘中取出苹果;signalSAB;//通知A或B盘子一空可能唤醒A或B消费该苹果;}}processB://进程B的算法描述{whiletrue{取一个梨子;waitSAB;//测试盘子是否为空将一梨子放入盘中;signalSD//通知D盘中已有梨子可能唤醒D}}processD:{whiletrue{waitSD;//测试盘子是否有梨子从盘中取出梨子;signalSAB;//通知A或B盘子一空可能唤醒A或B消费该梨子;}}parendend2采用管程的同步算法如下首先定义管程MPC,该管程可描述如下typeMPC=monitorvarflag:integer;//flag=0:盘中无水果;=1盘中有苹果;=2盘中有梨子empty:condition;//用于A或B等待空盘子W:array[
1..2]ofcondition//W
[1]用于等待苹果,W
[2]用于等待梨子procedureentryputintegerkbeginifflag0thenempty.wait;//生产者A或B进程阻塞flag=k;放一k号水果入盘中;//设1号水果为苹果,2号水果为梨子ifW[k].queuethenfull.signal;//若有等待k号水果者,则唤醒之endprocedureentrygetintegerkbeginifflagkthenW[k].wait;//消费者C或D进程阻塞从盘中取k号水果;flag:=0;ifempty.queuethenempty.signal;//若等待队列非空,则唤醒队首的一个生产者进程endbeginflag:=0;//初始化内部数据endA、B、C、D四个进程的同步算法可描述如下parbeginProcessAbegin任取一个苹果;MPC.put1;endProcessBbegin任取一个梨子;MPC.put2;endProcessCbeginMPC.get1;吃苹果;endProcessDbeginMPC.get2;吃梨子;endparend
2.设自行车生产车间有两个货架,货架A可以存放8个车架,货架B可以存放20个车轮;又设有4个工人,他们的活动是重复劳动,分别为工人1加工一个车架放入货架A中;工人
2、3分别加工车轮放入货架B中(每人每次放入1个车轮);工人4从货架A中取一个车架,再从货架B中取两个车轮,组装成一辆自行车试用PV操作实现四个工人的合作【分析】信号量Aempty表示货架A的空位数,其初值为8;信号量Afull表示货架A上存放的车架数,其初值为0;信号量Bempty表示货架B的空位数,其初值为20;信号量Bfull表示货架B上存放的车轮数,其初值为0;信号量mutex用于互斥(初值为1)解BEGINsemaphoreAempty,Bempty,Afull,Bfull,mutex;Aempty=8;Bempty=20;Afull=0;Bfull=0;mutex=1;PARBEGINWorker1BEGINL1生产1个车架;P(Aempty);//测试货架A是否有空位置P(mutex);//互斥使用货架A车架放到货架A;V(Afull);//货架A上的车架数增1,必要时唤醒等待的进程V(mutex);gotoL1;ENDWorker
2、3BEGINL2生产1个车轮;P(Bempty);//测试货架B是否有空位置P(mutex);//互斥使用货架B车轮放到货架B;V(Bfull);//货架B上的车轮数增1,必要时唤醒等待的进程V(mutex);gotoL2;ENDWorker4BEGINL3P(Afull);//测试货架A上是否有车架P(Bfull);P(Bfull);//测试货架B上是否有2个车轮P(mutex);取1个车架;取2个车轮;V(Aempty);//货架A空位置增1V(Bempty);V(Bempty);//货架B空位置增2V(mutex);组装成一辆自行车;gotoL3;ENDPARENDEND
3.有两个作业A和B,分别在7:00和8:30到达系统,它们估计的计算时间分别为
0.8小时和
0.1小时,系统在9:00开始以响应比高者优先算法进行调度在单道系统中该两个作业被选中时的响应比各为多少?解9:00时,作业A的响应比=1+2/
0.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.有一个具有两道作业的批处理系统(最多可有两道作业同时装入内存执行),作业调度采用计算时间短的作业优先调度算法,进程调度采用以优先数为基础的抢占式调度算法,今有如下作业序列,作业优先数即为进程优先数,优先数越小优先级越高列出所有作业进入内存时间及结束时间计算平均周转时间解先作必要的分析(可在草稿纸上完成,分析过程不计分)1010J1被调入,开始运行1020J2进入内存,因优先级高,开始运行J1运行了10分钟,还剩10分钟,因优先级低,运行态变就绪态1030J1继续就绪J2运行了10分钟,还剩20分钟J3到达,但不能被调入1050J2运行结束,J4到达调入短作业J4,但因J4优先级比J1低,J1开始继续运行1100J1运行结束J3被调入,因优先级高,开始运行J4因优先级低,仍就绪1125J3运行结束,J4开始运行1145J4运行结束
(1)各个作业进入主存时间、结束时间和周转时间如下表所示(6分)平均周转时间(50+30+55+55)/4=
47.5(min)
5.有一个多道程序设计系统,采用不可移动的可变分区方式管理主存空间,设主存空间为100K,采用最先适应分配算法分配主存,作业调度采用响应比高者优先算法,进程调度采用时间片轮转算法(即内存中的作业均分CPU时间),今有如下作业序列假定所有作业都是计算型作业且忽略系统调度时间回答下列问题1列表说明各个作业被装入主存的时间、完成时间和周转时间;2写出各作业被调入主存的顺序;3计算5个作业的平均周转时间解先作必要的分析(可在草稿纸上完成,分析过程不计分)答
(1)各个作业被装入主存的时间、完成时间和周转时间如下表所示
(2)作业被调入主存的顺序为J1,J2,J5,J3,J4
(3)平均周转时间=(65+60+85+95+55)/5=72(分钟)北京大学1997年试题某系统有ABC三类资源(数量分别为17,5,20)和P1~P5五个进程,在T0时刻系统状态如下表所示系统采用银行家算法实施死锁避免策略请回答下列问题
①T0时刻是否为安全状态?若是,请给出安全序列
②在T0时刻若进程P2请求资源(0,3,4),是否能实施资源分配?为什么?
③在
②的基础上,若进程P4请求资源(2,0,1),是否能实施资源分配?为什么? 解
①由已知条件可得尚需矩阵Need和可用资源向量Avalable如下NeedAvalableABCABCP1347233P2134P3006P4221P5110利用银行家算法对此时刻的资源分配情况进行分析如下表从上述分析可知,存在一个安全序列P4,P2,P3,P5,P1,故T0时刻系统是否安全的
②在T0时刻若进程P2请求资源0,3,4,不能实施资源分配因为当前C类资源剩余3个而P2请求4个,客观条件无法满足它的请求,因此不能实施资源分配,P2阻塞
③在
②的基础上,若进程P4请求资源(2,0,1),可以实施资源分配因为由
①可知,P4是安全序列中的第一个进程,只要P4的请求量没有超出它的尚需量,系统满足它的请求后仍处于安全状态,即仍然存在安全序列P4,P2,P3,P5,P
16.有5个任务A,B,C,D,E,它们几乎同时到达,预计它们的运行时间为10,6,2,4,8min其优先级分别为3,5,2,1和4,这里5为最高优先级对于下列每一种调度算法,计算器平均进程周转时间(进程切换开销不考虑)1先来先服务按ABCDE顺序算法;2优先级调度算法;3时间片轮转算法设时间片为1min——原题无此假设解1采用先来先服务算法时,5个任务在系统中的执行顺序、完成时间及周转时间如下表所示5个进程的平均周转时间为10+16+18+22+30/5=
19.2min2采用最高优先级调度算法时,5个任务在系统中的执行顺序、完成时间及周转时间如下表所示5个进程的平均周转时间为6+14+24+26+30/5=20min采用时间片轮转调度算法时,可以认为5个进程均分CPU时间,它们在系统中的执行情况如下第一轮A,B,C,D,E(5min)第二轮A,B,CC完成,即C的周转时间为8min,D,E(5min)第三轮A,B,D,E(4min)第四轮A,B,DD完成,即D的周转时间为17min,E(4min)第五轮A,B,E(3min)第六轮A,BB完成,即B的周转时间为23min,E(3min)第七轮A,E(2min)第八轮A,EE完成,即E的周转时间为28min(2min)第九轮A(1min)第十轮AA完成,即A的周转时间为30min(1min)所以,5个进程的平均周转时间为8+17+23+28+30/5=
21.2min
7.页式存储管理中,主存空间按页分配,可用一张“位示图”构成主存分配表假设主存容量为2M字节,页面长度为512字节,若用字长为32位的字作主存分配的“位示图”需要多少个字?如页号从1开始,字号和字内位号(从高位到低位)均从0开始,试问第2999页对应于何字何位;99字19位又对应于第几页?解1内存总块数=2MB/512B=4096位示图需要字数=4096/32=1282字号=2999-1/32=93位号=2999-1%32=22即第2999内存页对应于位示图中93字的22位399*32+19+1=3188即位示图99字19位对应于内存的3188页
8.某操作系统采用可变分区分配存储管理方法,用户区为512K且始址为0,用空闲分区表管理空闲分区若分配时采用分配空闲低地址部分的方案,其初始时用户区的512K空间空闲,对下述申请序列申请300K,申请100K,释放300K,申请150K,申请30K,申请40K,申请60K,释放30K;回答下列问题
(1)采用首次适应算法,空闲分区中有哪些空闲块(给出始址,大小)?序号始址大小1150K30KB2280K20KB3400K112KB
(2)采用最佳适应算法,空闲分区中有哪些空闲块(给出始址,大小)?答1序号始址大小1210K90KB2400K30KB3470K42KB29.一个32位地址的计算机系统使用二级页表,虚地址分为10位顶级页表,10位二级页表,其余是页内偏移试问1页面长度是多少?2虚拟地址空间有多少个页面?
10.在采用页式存储管理的系统中,某作业的逻辑地址空间为4页(每页2048字节),且已知该作业的页表如下表试借助地址转换图(即要求画出页式存储管理系统地址转换示意图)求出逻辑地址4688所对应的物理地址页表解逻辑地址4688所在的页号和页内偏移分别为页号P=4688/2048=2页内偏移W=4688%2048=592页表始址页表长度页号P=2页内偏移W=592+越界中断页表寄存器逻辑地址2469页号块号bbW页表物理地址•0123物理地址=62048+592=12880从上述地址转换图可知,进行地址转换的步骤如下由虚地址计算出页号和页内偏移量;根据页号和进程的页表首址,查页表,找到对应的页表项,取出帧号内存块号;帧号*页面大小+页内偏移形成物理地址即62048+592=
1288011.在一个采用页式虚拟存储管理的系统中,有一用户作业,它依次要访问的字地址序列是115,228,120,88,446,102,321,432,260,167,若该作业的第0页已经装入主存,现分配给该作业的主存共300字,页的大小为100字,请回答下列问题(此图类似地4题)
(1)按FIFO调度算法将产生的缺页中断次数、依次淘汰的页号和缺页中断率各为多少?
(2)按LRU调度算法将产生的缺页中断次数、依次淘汰的页号和缺页中断率各为多少?答由题目的已知条件,可得页面走向为12104134211FIFO的页面置换图如下按FIFO调度算法将产生5次缺页中断,依次淘汰的页号为012,缺页中断率为5/10=50%2LRU算法的页面置换图如下按LRU调度算法将产生6次缺页中断,依次淘汰的页号为2013,缺页中断率为6/10=60%
12.某系统对主存采用页式管理,供用户使用的主存区域共640K字节,被分成160块,块号为0,1,…,159现有一作业的地址空间共占4页,其页号为0123,被分配到主存的第2,4,1,5块中请回答1作业每一页的长度为多少字节?2写出该作业被装入主存时,其对应的页表3把该作业的每一页在主存中的起始地址用16进制表示填在下表中解1作业每一页的长度为4K字节2该作业被装入主存时,其对应的页表为3该作业的每一页在主存中的起始地址用16进制表示如下表所示作业名到达时间估计运行时间优先数J110:1020分钟5J210:2030分钟3J310:3025分钟4J410:5020分钟6作业名提交时间进入时间结束时间周转时间J110101010110050J210201020105030J310301100112555J410501050114555作业名提交时间需要执行时间要求主存量J110:0040分钟25KJ210:1530分钟60KJ310:3020分钟50KJ410:3525分钟18KJ510:4015分钟20K1000J1到达,被调入内存并开始运行,内存剩75KB1015J2到达,被调入内存并开始与J1一起运行J1运行了15分钟,还需执行25分钟内存剩15KB1030J3到达,因内存不能满足,不被调入J
1、J2继续运行1035J4到达,因内存不能满足,不被调入此时J1相当于已运行了15+10=25分钟,还需执行15分钟;J2相当于已运行了10分钟,还需执行20分钟1040J5到达,因内存不能满足,不被调入J
1、J2继续运行1105J1运行结束,J2还需执行5分钟内存中的2个空闲分区分别是25K和15K,能满足J4或J5需求,但不能满足J3的需要J4的响应比=1+30/25=
2.2;J5的响应比=1+25/15=
2.67,J5被调入内存并与J2一起运行,内存中的空闲分区大小是5KB和15K1115J2运行结束,内存中的空闲分区是65KB和15KJ3的响应比=1+45/20=
3.25,J4的响应比=1+40/25=
2.6,J3被调入内存与J5一起运行内存中的空闲分区大小是15KB和15KJ3需执行20分钟,J5还需执行10分钟1135J5运行结束,J4调入内存运行J3还需执行10分钟,J4还需执行25分钟1155J3运行结束1210J4运行结束作业名装入主存时间作业完成时间周转时间J11000110565J21015111560J31115115585J41135121095J51105113555进程最大资源需求量已分配资源数量ABCABCP1559212P2536402P34011405P4425204P5424314进程WorkNeedAllocationWork+AllocationFinishP4233221204437trueP2437134402839trueP383900640512314trueP51231411031415418trueP11541834721217520true执行顺序预计运行时间开始执行时间完成时间周转时间A1001010B6101616C2161818D4182222E8223030执行顺序预计运行时间优先数开始执行时间完成时间周转时间B65066E8461414A103142424C22242626D41263030页号内存块号02142639页面走向1210413421页帧00004444441111113333222222221是否缺页√√√√√被淘汰页号012页面走向1210413421页面队列12104134210121041342002104134是否缺页√√√√√√被淘汰页号2013页号起始地址0123逻辑页号主存块号02142135页号起始地址02000H14000H21000H35000H。