操作系统复习题集及答案 下载本文

4. 按顺序给出5个部分的内存,分别是100KB,500KB,200KB,300KB和600KB,用 first-fit,best-fit和worst-fit算法,能够怎样按顺序分配进程212KB,417KB,112KB,426KB和426KB?哪个算法充分利用了内存空间? 答: a. First-fit:

b. 212K is put in 500K partition c. 417K is put in 600K partition

d. 112K is put in 288K partition (new partition 288K = 500K ? 212K) e. 426K must wait f. Best-fit:

g. 212K is put in 300K partition h. 417K is put in 500K partition i. 112K is put in 200K partition j. 426K is put in 600K partition k. Worst-fit:

l. 212K is put in 600K partition m. 417K is put in 500K partition n. 112K is put in 388K partition o. 426K must wait

Best-fit: 算法充分利用了内存空间。

5. 考虑一个分页系统在内存中存储着一张页表。

a.如果内存的查询需要200毫秒,那么一个分页内存的查询需要多长时间? b.如果我们加上相关联的寄存器,75%的页表查询可以在相关联的寄存器中找到,那么有效的查询时间是多少?(假设如果入口存在的话,在相关的寄存器中找到页表入口不花费时间)

答:a.400毫秒:200毫秒进入页表,200毫秒进入内存中的字 b.有效进入时间=0.75*200毫秒+0.25*400毫秒=250毫秒

6. 假设有一个请求调页存储器,页表放在寄存器中:处理一个页错误,当有空的帧或被置换的页设有被修改过时要用8ms,当被置换的页被修改过明用20ms,存储器访问时间为100ns。

假设被置换的页中有70%被修改过,有效访问时间不超过200ns时最大可接受的页错误率是多少?

答:0.2 sec = (1 ? P) × 0.1 sec + (0.3P) × 8 millisec + (0.7P) × 20 millisec

0.1 = ?0.1P + 2400 P + 14000 P 0.1= 16,400 P P = 0.000006

7. 假设一个请求调页系统具有一个平均访问和传输时间为20ms的分页磁盘。地址转换是通过在主存中的页表来进行的,每次内存访问时间为1μs。这样,每个通过页表进行的内存引用都要访问内存两次。为了提高性能,加入一个相关内存,当页表项在相关内存中时,可以减少内存引用的访问次数。

假设80%的访问发生在相关内存中,而且剩下中的10%(总量的2%)会导致页错误。内存的有效访问时间是多少? 答:

有效访问时间= (0.8) × (1 μsec)+ (0.1) × (2 μsec) + (0.1) × (5002 μsec)

= 501.2 μsec ≈ 0.5 millisec

8. 某虚拟存储器的用户空间共有32个页面,每页1KB,主存16KB。试问: (1)逻辑地址的有效位是多少? (2)物理地址需要多少位?

(3)假定某时刻系统用户的第0,1,2,3页分别分配的物理块号为5,10,4,7,试将虚地址0A5C和093C变换为物理地址。

(1)程序空间的大小为32KB,因此逻辑地址的有效位数是15位。 (2)内存空间的大小是16KB,因此物理地址至少需要14位。

(3)当页面为1KB时,虚地址0A5C表示页号为00010,页内地址是1001011100。该页在内存的第4块,即块号为0100,因此0A5C的物理地址是01001001011100,即125CH。

(4)用同样的方法可以求得,093C的物理地址是113CH。

9. 若在一分页存储管理系统中,某作业的页表如下所示。已知页面大小为1024字节,试将逻辑地址1011,2148,3000,5012转化为相应的物理地址(注:此处块号即为页面号)。

页号 块号 0 2 1 3 2 1 3 6 解 本题中,为了描述方便,设页号为P,页内位移为W,逻辑地址为A,内存地址为M,页面大小为L,则

P=int(A/L) W=A mod L

对于逻辑地址1011 P=int(1011/1024)=0

W=1011 mod 1024=1011 A=1101=(0,1101)

查页表第0页在第2块,所以物理地址为M=1024*2+1101= 3059。

对于逻辑地址为2148 P=2148/1024=2

W=2148 mod 1024=100 A=2148=(2,100)

查页表第2页在第1块,所以物理地址为M=1024*1+100=1124。

对于逻辑地址为3000 P=3000/1024=2

W=3000 mod 1024=952 A=3000=(2,952)

查页表第2页在第1块,所以物理地址为M=1024*1+952=1976

对于逻辑地址5012 P=5012/1024=4

W=5012 mod 1024=916

因页号超过页表长度,该逻辑地址非法。

10. 某段式存储管理系统中,有一作业的段表(SMT)如下表所示,求逻辑地址[0,65],[1,55],[2,90],[3,20]对应的主存地址(按十进制)。(其中方括号中的第一个元素为段号,第二个元素为段内地址)

段号 段长(容主存起始地址 状态 量) 0 200 600 1 1 50 850 1 2 100 1000 1 — 3 150 0 解 逻辑地址[0,65]:对应的主存地址为600+65=665。

逻辑地址[1,55]:因段内地址超过段长,所以产生段地址越界中断。 逻辑地址[2,90]:对应的主存地址为1000+90=1090。

逻辑地址[3,20]:因为状态位为0,即该段在辅存中,所以产生缺段中断。

11.对页面访问串:1,2,3,4,1,2,5,1,2,3,4,5,指出在驻留集大为3时,使用FIFO、OPT和LRU替换算法的缺页次数。(OPT和LRU如果出现多选项时使用FIFO)

答: FIFO: 缺页11次 页√ √ √ √ √ √ √ 面 号 1 2 3 4 1 2 5 1 1 1 1 4 4 4 4 4 2 2 2 1 1 1 1 3 3 3 2 5 5 OPT: 缺页7次 页√ √ √ √ 面 号 1 2 3 4 1 1 1 1 1 1 2 2 2 2 3 4 4 2 1 2 4 √ 5 1 1 1 2 2 5 5 √ √ √ √ 2 3 4 5 2 2 2 5 1 3 3 3 5 5 4 4 2 1 2 5 2 5 1 2 √ √ 3 4 5 3 3 3 2 4 4 5 5 5 √ √ √ 3 4 5 3 3 3 1 4 4 2 2 5 LRU: 缺页10次 页√ √ √ √ √ √ √ 面 号 1 2 3 4 1 2 5 1 1 1 1 4 4 4 5 5 2 2 2 1 1 1 1 3 3 3 2 2 2

12.假设一个磁盘驱动器有5000个柱面,从0到4999,驱动器正在为柱面143的一个请求提供服务,且前面的一个服务请求是在柱面125.按FIFO顺序,即将到来的请求队列是

86,1470,913,1774,948,1509,1022,1750,130

从现在磁头位置开始,按照下面的磁盘调度算法,要满足队列中即将到来的请求要求磁头总的移动距离(按柱面数计)是多少? a. FCFS b. SSTF c. SCAN d. LOOK e. C-SCAN 答:

a. FCFS的调度是143 , 86 , 1470 , 913 , 1774 , 948 , 1509 , 1022 ,

1750 , 130 。总寻求距离是7081 。

b. SSTF的调度是143 , 130 , 86 , 913 , 948 , 1022, 1470, 1509,

1750, 1774。总寻求距离是1745。

c. SCAN的调度是143 , 913 , 948 , 1022, 1470, 1509, 1750, 1774 ,

4999 , 130 , 86 。总寻求距离是9769 。

d. LOOK的调度是143 , 913 , 948 , 1022, 1470, 1509, 1750, 1774,

130 , 86 。总寻求距离是3319 。

e. C-SCAN的调度是143 , 913 , 948 , 1022 , 1470 , 1509 , 1750 ,

1774 , 4999 , 86 , 130 。总寻求距离是9813 。

f. C-LOOK的调度是143 , 913 , 948 , 1022 , 1470 , 1509 , 1750 ,

1774 , 86 , 130 。总寻求距离是3363 。

13.假设有两个并发进程P1和P2, 程序代码为 P1: begin P2: begin A; C; B; D; end end

其中,A, B, C和D均为原语。请给出P1和P2两个进程所有可能的执行过程。 答:ABCD,ACBD,ACDB,CDAB,CABD,CADB

14. 桌上有一空盘,只允许存放一个水果。爸爸可向盘中放苹果,也可向盘中放桔子。儿子专等吃盘中的桔子,女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用,请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。

分析 在本题中,爸爸、儿子、女儿共用一个盘子,且盘中一次只能放一个水果。当盘子为空时,爸爸可将一个水果放入果盘中。若放入果盘中的是苹果,则允许女儿吃,儿子必须等待;若放入果盘中的是桔子,则允许儿子吃,女儿必须等待。本题实际上是生产者-消费者问题的一种变形。这里,生产者放入缓冲区的产品有两类,消费者也有两类,每类消费者只消费其中固定的一类产品。

解 在本题中,应设置三个信号量S、So、Sa,信号量S表示盘子是否为空,其初值为1;信号量So表示盘中是否有桔子,其初值为0;信号量Sa表示盘中是否有苹果,其初值为0。同步描述如下:

int S=1; int Sa=0; int So=0;