OS习题课部分答案.doc

_OS习题课部分答案存储管理2、某系统采用请求分页式管理，页面淘汰算法为LRU，每个作业占15页，其中一页用来存放程序，每一页存放200个整型变量，考虑如下程序：int a20100,b20100,i,j;for(i=1;i=20;i+)for(j=1;j=100;j+)aij=0;for(i=1;i=20;i+)for(j=1;j=100;j+)bij=aij;设数组ab均按行存储，程序已经调入主存，变量ij放在程序页中，问此程序会产生多少次缺页中断？最后留在内存中有哪些页面？解：数组a，2000个元素，共需占用10个页面，每两行一页数组b，2000个元素，共需占用10个页面，每两行一页第一个循环，aI,j=0会将a矩阵全部调入内存被赋值0，发生10次缺页中断，还剩4块；第二个循环，先读a，再写b，剩余的空闲4块内存，可放入b数组的07行，此时内存已满，若用A1表示a数组的a0和a1行占据的页面编号，则a数组的A0A19和b数组的B0B3页面（b0b7行）均被读入内存，即bij=aij;的循环中从b8行开始要进行LRU淘汰，根据该循环特点，b8行=a8行与b9行=a9行这两次循环的页面访问是A4B4A4B4，整个循环序列为：A4B4A4B4,A5B5A5B5,A13B13A13B13,可化简为A4B4,A5B5,A13B13A4B4A5B5A6B6A7B7A8B8A9B9A10B10A11B11A12B12A13B13A0B4B111B5B122B6B133B74A4A115A5A126A6A137A78A89B8b0A9b1B9b2A10b3B1014次缺页中断+总共发生14+15=29次缺页中断，内存中最终页面A7-A13,B7-B133. 考虑以下程序：int a100150,b150200,c100200,i,j,k;For (i=1;i=100;i+) for(j=1;j=200;j+) for(k=1;k=150;k+) cij=cij+aik*bkj;设a、b矩阵已经置好初值，c矩阵初始为0，各矩阵以页为单位连续存放；主存初始为空，请求分页时采用fifo算法。问：当作业分配10个页面，每个页面可存储100整数，缺页次数是多少？留在内存的最后的页面abc矩阵各占多少页？解：矩阵a100150 共需150页 每行占1.5个页面矩阵b150200 共需300页 每行占2个页面矩阵c100200 共需200页 每行占2个页面程序的逻辑地址空间中，总共需要650个页面，试编号为：a占用1-150号页面；b占151-450号；c占451-650号.cij=cij+aik*bkj读a,读b,计算a*b,读c，计算c+a*b，写c；而与内存访问有关的操作可简化为：读a,读b,读c，写c对于依次访问的a,b,c矩阵，只要不跨页，不会发生缺页中断；比如每次访问aI,k和cI,j时；但是，在每次访问bkj的时候，由于是按列读取，必然跨页。采用fifo算法，页面调度过程如下：循环变量读写操作内存页面i,j,k12345678910缺页1,1,1读a1缺读b1151缺读c写c1151451缺1,1,2读a1151451读b1151451153缺读c写c11514511531,1,3读a1151451153读b1151451153155缺读c写c1151451153155每次循环发生1次缺页，且都是为读b而生，从151-165都被载入内存1,1,8读a1151451153155157159161163读b1151451153155157159161163165缺读c写c1151451153155157159161163165此时内存全满1,1,9读a1151451153155157159161163165读b167151451153155157159161163165缺读c写c1671514511531551571591611631651,1,10读a1671451153155157159161163165缺读b1671169153155157159161163165缺读c写c1671169451155157159161163165缺1,1,11读a1671169451155157159161163165读b1671169451171157159161163165缺读c写c1671169451171157159161163165每次循环发生1次缺页1,1,100读a1331333335337339341343345347缺读b1349333335337339341343345347缺读c写c1349451335337339341343345347缺1,1,101读a13494512a矩阵跨页了337339341343345347缺读b13494512351339341343345347缺读c写c13494512351452c矩阵也跨页了341343345347缺100,200,148读a150428430432434436438440442444缺读b150446430432434436438440442444缺读c写c150446650432434436438440442444缺100,200,149读a150446650432434436438440442444读b150446650448434436438440442444缺读c写c150446650448434436438440442444100,200,150读a150446650448434436438440442444读b150446650448450436438440442444缺读c写c150446650448450436438440442444规律：当循环次数为n*9+1或n*100+1时，读a,b,c都会发生缺页；其他情况，只有读b时发生1次缺页；所以，读b总共发生缺页次数：100*200*150次，而对于b和c来说：总共100*200*150=3000000次循环中，n*9+1出现次数为：3000000/9=333333次而n*100+1出现的次数为：3000000/100=29999次;而n*9+1与n*100+1均出现的次数为3000000/900=3333次，此次数有重复计数，需减去，所以总缺页次数为：(100*200*150)+(333333+29999-3333)*2次，即3719998次缺页中断。4、有一个虚拟存储系统采用LRU算法，每个程序占3页内存，其中一页存放程序和变量i,j(不做他用)。每一页可存放150个变量，程序A和B如下：A：int c150100,i,j;for(i=0;i=150;i+) for(j=1;j=100;j+) cij=0;B:int c150100;for(j=1;j=100;j+) for(i=1;i=150;i+) cij=0;数组C按行存储，试问：（1）程序A和B执行完后，分别缺页多少次？（2）最后留在内存中的各是C的哪一部分？解：（1）数组C共需占100页，因为按行存储，所以每读入一个页面，会读入c数组的1.5行，如下所示：页面1 页面2c11. c251.c1100 .c2150c21. c31.c250 .c350对于程序A，c按行访问，每循环150次发生1次缺页中断，故总共发生100次缺页中断。对于程序B，c按列访问，每循环3次就要发生2次调页，c11,c21,c31.共发生2*15000/3=10000次缺页。（2）对于程序A，后300次循环访问的c数组元素，是保存在最后两个页面中的元素对于程序B，后3次循环访问的c数组元素，是保存在最后两个页面的元素。、 在南开大学与天津大学之间有一条小路，其中从S到T每次只允许一辆自行车通过，但中间有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车在已从两端进入小路情况下错车使用，如下图所示。试用PV操作设计一个算法使得来往的自行车顺利通过。（南开）天津大学TKM LS南开大学、设有8个进程，它们在并发系统中执行时有下图的顺序关系，试用PV操作实现这些进程的同步。（北大91考研题）P1P2P3P5P4P6P7P8、有一个仓库，可以存放A、B两种产品，仓库的存储空间足够大，但要求：（1）每次只能存入一种产品（A或B）（2）-nA产品数-B产品数声请R1-R2-申请R1-释放R1-释放R2-释放R1(1) 说明系统运行中是否有产生死锁的可能？为何？(2) 如果有可能的话，请举出一种情况,并画出其死锁状态的进程-资源图。（南开95）9、设系统中有3类资源（A,B,C）和5个进程(P1,P2,P3,P4,P5),A资源数量为17,B 5, C 20,在T0时刻系统状态见下表： 最大资源需求量已分配资源量ABCABCP1559212P2536402P34011405P4425204P5424314剩余资源数233以银行家算法为分配策略。(1) T0时刻是否为安全状态，5个进程以何种顺序分配资源不会出现死锁？(2) T0时刻若P2请求资源(0,3,4),能否实施资源分配？为什么？(3) 在(2)的基础上，若进程P4请求资源(2,0,1),能否实施资源分配？为什么？(4) 在（3）的基础上，若进程P1请求资源（0，2，0），能否实施资源分配？为什么？（PKU97）10、证明：短作业优先的作业调度算法可以得到最短的平均响应时间。答案：、 从天津大学到南开：T-L;into M;K-S;从南开到天津相反。T-L和K-S路段1次只允许1辆，各1个信号量，M可2量，再设1个信号量。又由于M只供错车使用，因此意味者每个方向上1次只能有1辆车在路上（若一个方向上出现2车，其速度快慢不同不好控制），因此再设2个信号量，代表两个方向上的车数：tn,ntMain()TN()NT()p(tn)p(nt);int l=1,k=1,m=2,tn=1,nt=1;p(l);p(k);cobegin:t-l;s-k;TN();NT();p(m); p(m);v(l);v(k);Coendinto m;into m;p(k);p(l);v(m);v(m);k-s;l-t;v(k);v(l);v(tn);v(nt);、main()p1()v(s3);v(s4);v(s5);p2()同p1int s3=s4=s5=s6=s7=s8=0;p3()ps3;ps3;vs6;cobegin:p4()ps4;ps4;vs8;p1;p2;p3;p4;p5;p6;p7;p8;p5()ps5;ps5;vs7coendp6()ps6;vs8;p7()ps7;vs8; p8()ps8;ps8;ps8;、 两个进程是通过数量上的关系达到相互制约的，因此是一个同步问题。关键是搞清楚两个进程Pa Pb自己的私有信号量的问题。AAAAB不能比A多n个以上，想象n-1个为满缓冲区，A为消费者，拿走1个B BBBBB才能往里放1个，所以Pa的私有信号量Sa初值为n-1AAAAA不能比B多m个，同理Pb的私有信号量Sb初值为m-1.BBBB又：每次只能放1种产品，因此仓库是临界资源，设1个共有信号量m;main()PaPbp(sb);p(sa);int m=1,sa=n-1,sb=m-1;p(m);p(m);v(m);v(sa);v(m);v(sb);、 理发师问题：理发师需要一个私有信号量barber,初值为0，代表刚开始时，理发师睡觉无资源。顾客需要1个私有信号量customer，初值为0，代表刚开始时无顾客。设变量count，代表顾客个数。理发师和顾客在访问椅子数量期间，必须对count互斥，故设信号量mutex=1,代表对count的互斥。Main()int baber=0,customer=0,count=0，mutex=1;baber()customer()p(mutex);/进来首先看有无空位，访问countp(customer);/看看有无顾客，否则睡觉。 If(count1时，必须对写者互斥，直到全部读者均已经读完，读者进程数为0时，才开放对写者的互斥。因此设一个变量rc，代表读者进程的个数。Rc本身为临界资源，设1个公有信号量Sr互斥。Main()reader()p(sr);int mutex=1,sr=1,rc=0; rc+; if(rc=1) p(mutex);/当只有1读者时，才需要对写者互斥 v(sr);/多于1个的读者后来进来时，无须对写者互斥，直接rc+ 开始读； p(sr); sr-; if(rc=0) v(mutex); v(sr);writer()p(mutex);开始写；v(mutex);、 设一个信号量mutex代表桥就行。Main()ps()pn()与ps()相同。int mutex=1;p(mutex);过桥；v(mutex);、 R1有3,R2有4;（1）4个进程每个均需R1 2台，R2 2台，即总共需要(8,8)台，可能发生死锁。只要具备4条件。(1) （2）当3个进程执行完第1步（各得R1 一台），开始执行第2步时，第4个进程会被阻塞；(2) 当这3个进程执行完第2步后（各的一台R2）,3个进程又同时申请R1(此时R1为0)，全部被阻塞，出现死锁。P1P2P3P4 9、（1）T时刻为安全状态，因为可以按照P4-P5-P1-P2-P3顺序进行资源分配。（2）不能分配，P2请求(0,3,4),但C资源只有3个。（3）系统还有(2,3,3),P4请求(2,0,1),可以满足；分配完成后：总(0,3,2),P1(3,4,7),P2(0,3,4),P3(0,0,6),P4(0,2,0),P5(1,1,0);所以，按照P4P5P1P2P3顺序可以进行。 （4）P4完成后，系统还有(0,3,2)，此时P1(0,2,0),完成后：总(0,1,2),P1(3,2,7),P2(0,3,4),P3(0,0,6),P4(0,2,0),P5(1,1,0)没有一个可以分配得下，所以不能分配。、 证明：设有n个作业j1jn,其执行时间t1tn,满足t1t2tn;则，按照短作业优先算法，作业执行顺序为j1jn，则该系统的平均响应时间为：T1=(t1+(t1+t2)+(t1+t2+t3)+(t1+tn)/n=(n*t1+(n-1)*t2+tn)/n若用非短作业优先算法，作业执行顺序为：ji1,ji2,jin,其中i1in为1n的一个排列，其平均响应时间为：T2=(n*ti1+ti2(n-1)+tin)/n因为t1t2(n-1)1;有t1*n+t2*(n-1)+tn是两式相乘最小的，所以T1T2、 在一间酒吧里有三个音乐爱好者，第一位音乐爱好者只有随身听；第二个只有CD；第三个只有电池，而要听音乐就要三者齐全。酒吧老板一次借出这三种物品中的任意两种；当一名音乐爱好者得到这三种物品，并开始听完一首乐曲后，老板才能再一次借出任意两种，于是第二名音乐爱好者才能得到这三种物品并开始听音乐。不断循环下去。解：制约关系：1） 听音乐的爱好者不听完，老板不会新一轮借出。2） 老板不借出2/3的物品，对应的拥有1/3物品的爱好者不能开始听音乐；关键问题在于，要根据借出的2/3物品，将各种物品组合分开.1） 制约关系，设音乐爱好者私有信号量wait，代表是否听完音乐，初值为02） 制约关系，设老板的私有信号量Ss1,s2,s3对应三种物品组合：S1:CD+电池；S2：电池+随身听；S3：CD+随身听Boss()int s=genservice();/生成三种物品组合if(s=1) v(S1); else if(S=2) v(S2); else v(S3);P(wait);Fans(i)P(Si);听音乐；V(wait);12解：制约关系：在过相同的某一号船闸的时候，P2A方向应该互斥A2P方向，纯互斥问题。int ST=1;/为每个船闸设置一个信号量countPAT=0;/Pacific to Atlantic的船数量countAPT=0;/Atlantic to Pacific的船数量A2P()for(j=1;j=T;j+)P(mutex);if(countj=0)P(sj);countj+;V(mutex);过第j+1船闸;P(muntex);countj-;if(countj=0)V(sj);V(mutex);int mutex=1;/对两类count进行互斥P2A()for(i=1;i=T;i+)P(mutex);if(counti=0)P(si);counti+;V(mutex);过第i+1船闸;P(muntex);counti-;if(counti=0)V(si);V(mutex);、 某银行有人民币储蓄业务，由n个柜员负责。每个顾客进入银行后先取一个号，并等着叫号。当一个柜台人员空闲下来，就叫下一个号。使用PV操作实现同步。解：制约关系：1） 柜员不空闲，不会给顾客服务；设柜员的私有信号量S1，代表有无空闲柜员，初值n;2） 没有顾客，柜员受到制约；设顾客私有信号量S2,代表有无顾客，初值0;对于叫号机，需要设共有信号量mutex，互斥一切并发访问。main()int mutex=1,S1=n,S2=0; cobegin:teller();customer();coend;customer()P(mutex);取号;V(mutex);P(S1);享受服务;V(S2);Teller()P(S2);P(mutex);叫号;V(mutex);服务;V(S1);另解：号码队列list：新号由队尾插入，叫号由队头取出；设信号量mutex对其互斥；只需为customer设一个私有信号量S，初值为0;Teller()P(S);P(mutex);从队列list中叫号;V(mutex);服务;customer生成新号;P(mutex);新号入list;V(mutex);V(S);享受服务；注：teller无私有资源，也就是说不管你有无空闲，叫号队列是不断增长的。18、写者优先问题：解1：(对应题目如果要求“一旦有写者来，则后续读者必须等待，唤醒时优先考虑写者”)考虑到互斥的情况，设变量readcount，初始值为0，并设置信号量mutex。 设读者与写者两个队列（ReadQ与WriterQ），文件状态 FileState变量。对应的，设三个信号量，依次为mutexReadQ，mutexWriterQ和mutexFileState。 代码如下： Reader（） P(mutexWriteQ); while(WriteQ.Length()!=0) ； /这里体现写者优先 V(mutexWriteQ); P(mutex); /只有写者为0，才能走到这里 readcount +; if (readcount=1) P(mutexFileState); /首个读者将文件加锁，后续读者不 V(mutex); Read.do(); /读者执行读操作 P(mutex); readcount -; if (readcount=0) V(mutexFileState); V(mutex); Writer() P(mutexWriteQ); WriterQ.push(); /写者入队 V(mutexWriteQ); P(mutexFileState);/这里似乎无法互斥非首个读者 P(mutexWriteQ); writer=WriterQ.pop()； V(mutexWriteQ); writer.do(); /写者执行写操作 V(mutexFileState); V(mutexWriteQ); 另解：设变量rc=0，代表读者的数目；为它设一互斥信号量mutex=1；信号量Sr=1，实现对文件的互斥，包括读写互斥，写写互斥；信号量w=1，实现写-读优先；Reader() P(w); /任何一个读者都要与写者互斥wP(mutex);rc+;if(rc=1) P(Sr); /这里保证读者对写者互斥，即读-写互斥V(mutex);V(w); / rc+后，读者就要释放出w开始读；读完；P(mutex);rc-;if(rc=0) V(Sr);V(mutex);Writer()P(w); /只要有读者在其后来到，保证writer先于它们；同时保证写-写互斥P(Sr); /保证文件的互斥写；V(Sr);V(w);19、桌上有1只盘子，每次只能放/取1个水果；爸爸专门向盘中放苹果，妈妈专门放桔子；女儿专吃苹果，儿子专吃桔子；请用PV操作实现4个人的同步关系。解：制约关系：1） 盘子不为空，father受到（儿子或女儿）制约，mother也受到（儿子或女儿）制约；儿子或者女儿每运行一次，会产生一个空盘子；所以，为儿子女儿设共同的私有信号量S=1，代表盘子是否为空.2） 儿子受到mother制约，为mother设私有信号量So=0，代表有无苹果3） 女儿受到father制约，为father设私有信号量Sa=0