操作系统期末复习大题

1、设某计算机系统有一个CPU 一台输入设备，一台打印机。现有两个进程同时进 入就绪状态，且进程A先得到CPU1行，进程B后运行。进程A的运行轨迹是： 计算50m6打印信息100ms再计算50ms打印信息100ms结束。进程B的运 行轨迹为：计算50ms输入数据80ms再计算100ms结束。试画出它们的时 序关系图（甘特图），并说明：1 .开始运行后，CPM无空闲等待？若有，在哪段时间内等待？计算 CPU的禾I用 率。2 .进程A运行时有无等待现象？若有，在什么时候发生等待现象？3 .进程B运行时有无等待现象？若有，在什么时候发生等待现象？在一单道批处理系统中，一组作业的提交时间和运行时间如下表，

2、利用先来先服 务调度算法试计算以下三种作业的平均周转时间 T和平均带权周转时间W作业提交时间运行时间18.0M.028.50.539.010.249.10.1先来先服务(FCFS)调度算法二CF5调度算法导一种喝筒用的弱度算法：京调奏穿巾可以用于作业谑度也可M于进程调度.在杵业洞度中.耳 去萼次从后靠卡亚队列中谢军思先I芭入读队列的T-电3十作业.将它们调入内存.分配必要的贾源.创逑进程并 放人就造队列.在进1艘也FCFH调度篁法每次从就蔻仄列中解最先扒砌列的睡.檄诞机分0眸它，便之投A运行. 直到完成或因题原因碘叁时才礴处理机.下面通过Y期薛潴蛇口=名照度算法的性能.慢霹烧中痴个作业,玄扪的

3、提交时间分别是叫队人事瓦9.施行时间依欢是乙i 口.5、U.2,手联深用卜匚卜士阔度算法.这里作业的平均零法附间、平均周转时间和二均 书现圄转时司见表”工去2T FIF M词度算法至“辘作业提交附 问运行因 A开始时 问等访时同完思固问周玲时间,周玲的向1R28n1021284101.6112.62,638.80.5112.2U.S2.75.44Q03211,52,511.72.713S平均峰蝴闾 t = (0+1.6+2 2+2 5)/41.575平均周转时司 T (2-2.0+2.7+2.7/4-2,5平均81 词 W = J1+2.6+54113.S)/4=5.625短作业优先(SJF)

4、调度算法电归1k (海)优先祠篁算法指对短作业(i)优先调度的算法短但1k优先(SJF)词息算法是从后备M到中 选生个同最短的作业翔它们调人内存运行.而施进程优先(5PF滔专宣法.则是从就绪从 列中选择一个怙计运行时词最短的进程.每处邸0配给已 鹿之立娜行.直利史成或姓某事件而阻塞时，才 羟波处暹机.巨蛆.考老恚二7中4士1的一任咋若至线平书三峰伏关个豆算法三平均等再仁区.平飞匿柠归司和二华三 现周希比n司见表a -丸表ZT 5不凋宸算法的性箭件也弓提套前 同运行忖 间开效时 间等秸时间完罐时同就哪间用双周转时间182801Q21283110.72,311.73.33.3348.80.S10.

5、21.410.71.93.B90,31011021,35平肉等待时间 t = ；0-K2.3f 1.4+1/4=1 175平均间 T = (2+3 3+1.3+1.2)/4-2.1平均带我周转时间W = (l+J.3+3.H+b)/4=J.b2b假设系统中有4个进程P1,P2和p3,P4.它们的运行时间依次是6,8,7和3(单位 是ms).如果进程以p1,p2,p3, P4 的顺序在时刻0到达,并设置他们的优先级分别为1,2,3,4,数字越大优先级越高，采用优先级调度算法，计算其平均等待时 问.作业优先 级提交时 问运行时 问开始时 问完成时 问等待时 问P1106182418P2208101

6、810P33073103P4403030用pv原语解决司机与售票员的问题司机进程： while (1) 启动车辆正常驾驶到站停车售票员进程:while (1)关门售票开门L.分析：为保证车辆行驶安全，售票员必须关好车门，然后通知司机启动车辆，在行驶 过程中售票员不能打开车门，待车到站停稳后，司机通知售票员才能打开车门， 如此不断重复。为此，须设置两个信号量START OPENS来控制司机和售票员的 行为，初值都为00 司机进程：while(1)(P( START启动车辆正常驾驶到站停车V(OPEN.售票员进程：while(1)(关门V(START售票P(OPEN开门 16.用PV原语解决下图之

7、同步问题 提示：考虑对缓冲区S的同步get pirf设置两个信号量Sempty=1, Sfull=0get:while (1) (P(Sempty);将数放入S;V (Sfull); )copy: while (1) (P (Sfull );将数从S取出；V (Sempty);)此题类似于一个生产者一个消费者一个缓冲区的情况。17.扩充一下:设置四个信号量 Sempty=1, Sfull=0 , Tempty=1, Tfull=0 ; get:while (1)(P(Sfull );将数据取走；V (Sempty);V(Tempty)copy :while (1)(P (Tfull );P (

8、Sempty );将数从S取出放入T;V (Sfull);)putwhile (1)(P (Tempty );放数据到T;V(Tfull);)17.已知某分页系统，主存容量为64KB,页面大小为1KB,对于一个4页的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。(1)将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。(2)以十进制的逻辑地址1023为例，画出地址变换过程图。解：(1)对上述逻辑地址，可先计算出它们的页号和页内偏移量(逻辑地址除以页面大小，得到的商为页号，余数为页内偏移量)，然后通过页表转换成对应的物理地址。对于逻辑地址 1023:计算(in

9、t)1023/1KB ,得到页号 P1=0,页内偏移量 W1=1023,查页 表找到对应的物理块号为2,故物理地址 E1=2X 1KB+1023=3071。对于逻辑地址 2500:计算(int)2500/1KB ,得到页号 P2=2,页内偏移量 W2=452 ,查页表找到对应的物理块号为6,故物理地址 E2=6X 1KB+452=6596。对于逻辑地址 3500:计算(int)3500/1KB ,得到页号 P3=3,页内偏移量 W3=428 ,查页表找到对应的物理块号为7,故物理地址E3=7X 1KB+428=7596。对于逻辑地址 4500:计算(int)4500/1KB ,得到页号 P4=

10、4,页内偏移量 W4=404 ,因页号 不小于页表长度，故产生越界中断。(2)逻辑地址1023的地址变换过程如图所示。18.某系统采用页式存储管理方法，主存储器容量为256MB,分成64K个块。某用户作业有4页，其页号依次为 0, 1, 2, 3被分别放在主存块号为 2, 4, 1, 6的块中。要求：（1）写出该作业的页表；（2）指出该作业总长度的字节（Byte）数；（3）分别计算相对地址0 , 100和2 , 0对应的绝对地址（方括号内的第一元素为页号，第二元素为页内地址）。解答：9、门）页表如下C2每块大小为256MWIKV4KB蚱业息长度力=口对地址aLOO隙应的期对地址为4K*2+IQ

11、0 =总9工相对地址2, 0雨应的把对也址为4K*1 + Q -我痴19.某页式存储管理系统，内存的大小为 64KB,被分成16块，块号为0、1、2、15。 设某进程有4页，其页号为0、1、2、3,被分别装入内存的 2、4、7、5块，问：（1）该 进程的大小是多少字节？ （ 2）写出该进程每一页在内存的起始地址。（3）逻辑地址4146对应的物理地址是多少？解答：（1）内存的大小为 64KB,被分成16块，所以块的大小是 64KB/16=4KBo因为块的大小与 页面的大小相等，所以页的大小是4KB。该进程的大小是 4*4=16KB。2、 4、 7、 5。（2）因为进程页号为 0、1、2、3,被分

12、别装入内存的第0页在内存的起始地址是：2*4KB=8KB;第1页在内存的起始地址是：4*4KB=16KB;第2页在内存的起始地址是：7*4KB=28KB;第3页在内存的起始地址是：5*4KB=20KB。（3）逻辑地址4146对应的物理地址：4146/4096=1 ,，50。逻辑地址 4146对应的页号 为1,页内位移为50。查找页表，得知页号为 1的存储块号为4,所以逻辑地址4146对应 的物理地址是： 4*4096+50=16434。20. 某系统采用页式存储管理策略，某进程的逻辑地址空间为32页，页的大小为2KB,物理地址空间的大小是 4MB。（1）写出逻辑地址的格式。（2）该进程的页表有

13、多少项？每项 至少占多少位？ （ 3）如果物理地址空间减少一半，页表的结构有何变化？ 解答：（1）进程的逻辑地址空间为32页，故逻辑地址中的页号需要5位（二进制），由于每页的大小为2KB,因此页内位移须用 11位（二进制）表示，这样逻辑地址格式如下图。Il m0页内位移（2）因为进程的逻辑地址空间为32页，因此该进程的页表项有32项。页表中应存储每页的块号。因为物理地址空间的大小是 4MB, 4MB的物理地址空间内分成 4MB/2KB=2K个 块，因此块号部分需要 11位（二进制），所以页表中每项占16位。（3）如果物理地址空间减少一半，页表的页表项数不变，但每一项的长度从16位（二进制）减少

14、到15位（二进制）。21.对一个将页表存放在内存中的分页系统，请回答：（1）如果访问内存需要 0.2 s, 一个数据的有效访问时间是多少？（2）如果加一个快表，且假定在快表中找到页表项的命中率为90%,则访问一个数据的有效访问时间又是多少（假定查快表需要花费的时间为0）解：（1）在分页系统中，访问一个数据需要 2次内存访问，所以有效访问时间为：2X0.2=0.4 心So（2）在增加快表后，访问一个数据时先在快表中查找，若未找到再在页表中查找。快 表命中只需 0.2s,快表未命中需 0.4s,则有效访问时间为 90% X 0.2 s +10%X0.4科 s=0.22 s s。22.假设一个分页存

15、储管理系统中具有快表，多数活动页表项都可以存在其中。如果页表放在内存中，内存访问时间是1科s,若快表的命中率为 85%,则有效访问时间是多少？若快表的命中率为50%,则有效访问时间是多少？解：有效访问时间是指通过逻辑地址访问对应物理地址中的数据所花的时间。有快表时，先查找快表（由于速度很快，所花时间忽略不计），若找到了对应的页表项，取出物理块号并拼成物理地址，再访问内存，只须访问内存1次；若在快表中没有找到，再在页表中查找，需要访问内存 2次。若快表的命中率为 85%,则有效访问时间 =2X1 s+0-UsX85%=1.15so若快表的命中率为 50%,则有效访问时间=2X 1Ws+0-1 sx 50%=1.5科s。由于快表的访问时间相对很短，若题目中没有给出快表访问时间，通常可以看成快表访 问时间为0。23.现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下:段号生存起始地址（段基址）段长度012040176030248020337020计算逻辑地址（2, 15） , （0, 60） , （3, 18）的绝对地址