操作系统

1.桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿3各个并发进程的同步。2.设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；3.进程A1，A2，…，An1通过m个缓冲区向进程B1,B2,…,Bn2不断地发送消息，发送和接收工作遵循如下规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样；（2）对每一个消息，B1,B2,…,Bn2都需各接收一次，读入各自的数据区内；（3）M个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。试用P、V操作组织正确的发送和接收操作。4.如表所示，把所示的作业交给单道批处理系统，在系统短作业优先和最高响应比优先调度算法时分别计算其平均周转时间T。作业提交时间和运行时间作业号1234提交时间/h8.009.009.009.00运行时间/h5.004.002.003.005.在一单道批处理系统中，一组作业的提交时间和运行时间如表所示。试计算一下3种作业调度算法的平均周转时间T和平均带权周转时间W（时间单位：小时，已十进制进行计算）。作业提交时间和运行时间作业号提交时间运行时间18.01.028.50.539.00.249.10.1（1）先来先服务（2）短作业优先（3）响应比高者优先6.有5个批处理的作业（A、B、C、D、E）几乎同时到达一个计算中心，估计的运行时间分别为2、4、6、8、10分钟，它们的优先数分别为1、2、3、4、5（1为最低优先级）。对下面的每种调度算法，分别计算作业的平均周转时间。（1）最高优先级优先（2）时间片轮转（时间片为2分钟）解题思入：：：ABCDEBCDECDEDEE周转时间A第二次全部B结束时间从A——第二个B第三个是到全部D结束第四个是全部E结束（3）FIFO（作业到达顺序为C、D、B、E、A）（4）短作用优先7.银行家算法P115228.设系统中有3种类型的资源（A、B、C）和5个进程（P1、P2、P3、P4、P5），A资源的数量为17，B资源的数量为5，C资源的数量为20,。在T0时刻系统状态如下表：最大资源需求量已分配资源数量ABCABCP1559212P2P3P4P55364011425424402405204314剩余资源数量ABC2339.考虑如下访问序列：0,1,0,3,1,2,4,3.驻留集大小为两个页面，分别求出采用LRU和OPT替换算法控制上述访问串的故障数和页故障率。10.设某作业占有7个页面，如果再主存中只允许装入4个工作页面（即工作集为4），作业运行时，实际访问页面的顺序是1,2,3,6,4,7,3,2,1,4,7,5,6,5,2,1。试用FIFO与LRU页面调度算法，列出各自的页面淘汰顺序和缺页中断次数，以及最后留驻主存4页的顺序（假设开始的4个页面已装入主存）。11.会了》》》某请求分页存储管理系统使用一级页表，假设页表总在主存中。（1）如果依次存储访问需要200ns，那么访问一个数据需要多长时间？（2）现在增加一个快表，在命中或失误时均有20ns的开销，假设快表的命中率为85%，那么访问一个数据的时间为多少？答案（1）由于访问一个数据需要两次访问存储器，一次取页表信息，一次取数据信息。故访问一个数据的时间为：200*2=400ns(2)增加快表后，现在快表中取页表信息，若页表项不在快表中，再到内存取页表信息。故访问一个数据的时间为：0.85*（200+20）+0.15*（20+200+200）=250ns12.对于一个利用快表且页表存于内存的分页系统，假设CPU一次访存时间为1us，访问快表的时间可以忽略不计。（1）如果85%的地址映射可以直接通过快表完成（即命中率为85%），那么进程完成一次内存读/写的平均有效时间是多少？（2）若快表的命中率只有50%，那么进程完成一次内存读/写的平均有效时间是多少？（3）快表命中率对平均有效访问时间有何影响？快表命中率提供可以减少进程完成依次内存读/写的平均有效访问时间12.答案(1)平均有效访问时间为=0.85*1+0.15*（1+1）=1.15us(2)平均有效访问时间为=0.5*1+0.5*（1+1）=1.5us(3)快表命中率提供可以减少进程完成依次内存读/写的平均有效访问时间14设正在处理器上执行的一个进程的页表如下，页表的虚页号和物理块号时十进制数，起始页号（块号）均为0，所有的地址均是存储器字节地址，页的大小为1024字节。计算下列虚地址对应什么物理地址：（1）5499（2）2221虚页号状态位访问位修改位物理块号01114111072000---310024000---51010注释：访问位：当某页被访问时，其访问位被置为1.参考答案：5499=1024*5+379，故其虚地址为（5,379），从页表可知，其块号为0，故物理地址为（0,379）2221=1024*2+173，故其虚地址为（2,173），从页表可知，其不在内存。13.考虑一个由8个页面，每页1024字节组成的存储空间，把它映射到容量为32个物理块的存储器中，试问逻辑地址和物理地址分别是多少位？131514.假定某页式存储管理系统中，主存为128KB，分成32块，块号为0,1,2,3，…，31；某作业有5块，其页号为0,1,2,3,4，被分别装入主存的3,8,4,6,9块中。有一逻辑地址为【3,70】，试求出相应的物理地址。参考：4KB*6+70=2464617.在某段式存储管理系统中，有一作业共4段，短号分别为0,1,2,3，段表如下表所示：试计算逻辑地址【4,45】，【1,50】，【2,60】，【3,90】相应的主存地址。当无法进行地址转换时，应说明产生何种中断（其中方括号中的第一个元素为页号，第二个元素为业内地址，按十进制计算）。段表段号段长主存起始地址状态0500150001400260002120---13853800参考逻辑地址【0,45】，因45500，地址合法，对应主存地址为1500+45=1545逻辑地址【1,50】，因50500，地址合法，对应主存地址为：2600+50=2650；逻辑地址【2,60】，因60120，地址合法，但该段状态位为1，所以产生缺段中断，带缺段调入主存后再进行地址变换；逻辑地址【3,90】，因9085，地址非法，产生地址越界中断。18.管理，允许用户编程空间为32个页面（每页1KB），主存为16KB，如有一个用户程序有10页长，且某时刻该用户页面映射表如表所示，如果程序执行时遇到以下两个虚地址：0AC5H，1AC5H,试计算它们对应的物理地址。页面映射表虚页号物理块号012387410参考：每页大小为1KB=1024B，03FFH=（111111111）2（1）逻辑地址0AC5H的页号p和业内位移w如下：P=0AC5H10=2W=0AC5H&&3FFH=2C5H而从页面映射表可知，页面2对应物理块4，因此对应的物理地址为：4*1024+2C5H=1C5H（2）逻辑地址1AC5H的页号p和业内位移w如下：P=1AC5H10=6W=0AC5H&&3FFH=2C5H从页面映射表可知，页面6不在内存中，发缺页中断，由缺页中断处理程序将缺页调入内存后再进行地址变换。1.在本题中，爸爸，儿子，女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘的是桔子，则允许儿子吃，女儿必须等待；若放入果盘中的是苹果，则允许女儿吃，儿子必须等待。本题实际上是生产者-消费者问题一个变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。在本题中，应设置3个信号量S，So，Sa，信号量S表示盘子是否为空，其初值为1，信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0.同步描述如下：IntS=1;IntSo=0，Sa=0;Main(){Father();Son(0;Danghter();}Father(){While(1){P(s);将水果放入盘中；If(放入的是桔子)v(So);ElseV(Sa);}}Son(){While(1){P(So);从盘中取出桔子；V(s);吃桔子；}}Daughter(){While(1){P(Sa);从盘中取出苹果；V(s);吃苹果；}}2.在汽车行驶过程中，司机活动与售票员活动之间的同步关系为：售票员关车门后，向司机发开车信号，司机接到开车信号后启动车辆，在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门让乘客上下车。引出司机启动车辆的动作必须与售票员关车门的动作取得同步；售票员开车门的动作也必须与司机停车取得同步，在本题中，应设置两个信号量：s1,s2,s1表示是否允许司机启动汽车，其初值为0；s2表示是否允许售票员开门，其初值为0.用p,v原语描述如下：Ints1=s2=0;Main(){Driver();Busman();}Driver(){While(1){P(s1);启动车辆；正常行车；到站停车；V(s2);}}Busman(){While(1){关车门；V(s1);售票；P(s2);开车门；上下乘客；}}用P，V操作控制实现生活中的操作流程是一类常见的试题。这类试题要求解题者能将生活中的控制流程用形式化的方式表示出来。3.这是一个变形的生产-消费问题。每个缓冲区只需写一次，但需读n2次。可以把一组缓冲区看做n2组缓冲区，这样，每个生产者需要同时写n2个缓冲区组中相应的n2个缓冲区，而每个消费者只需读它自己对应的那组缓冲区中的单元。生产者须在n2个缓冲区都为空闲时方可写入。这样，就可以用n2组信号量（avail,free）来实现这一流程。Intmutex=1,avail[n2],full[n2];IntI;For(i=1;i=n2;i++)avail[i]=m;full[i]=0Send(m){while(1){IntI;For(i=1;i=n2;i++)P(avail[i]);V(mutex);将消息放入缓冲区；For(i=1;i=n2;i++)V(full[i]);V(mutex);}}Receive(m,i){while(1){P(full[i]);P(mutex);从缓冲区中取消息；V(avail[i]);V(mutex);}}5(1)采用FIFS调度算法的作业运行情况如表作业号提交时间运行时间开始时间完成时间周转时间带权周转时间18.01.08.09.01.01.028.50.59.09.51.02.039.00.29.59.70.73.549.10.19.79.80.77.0平均周转时间T=（1.0+1.0+0.7+0.7）4=0.85平均带权周转时间W=(1.0+2.0+3.5+7.0)/4=3.375（2）采用最高响应比优先算法在8:00时，因为只有作业1到达，系统将作业1投入运行，作业1运行5h后（即13.00）完成，此时剩下3个作业的响应比为：作业2=1+4/4=2作业3=1+4/2=3作业4=1+4/3=2.3作业3的响应比最高，作业3被先调度运行，2h后（15.00）作业3运行结束，此时作业2和作业4的响应比分别为：作业2=1+6／４＝２．５作业４=1+6/2=3作业4的响应比最高，作业4被先调度运行由此可见，4个作业的调度顺序为1、3、4、2.短作业优先调度算法的执行顺序相同，因此各作业的周转时间也如上表所示。平均周转时间为8.25.。15.13.在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：115,228,120,88,446,102,321,432,260,167，若该作业的第0页已经装入主存，现分配给作业的主存共300字，也的大小为100字，请回答下列问题：（2）按FIFO调度算法将产生几