操作系统课后重点习题整理(3)

（1）first-fit,best-fit和worst-fit算法分配进程如下： First-fit:

212K is put in 500K partition 417K is put in 600K partition

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

212K is put in 300K partition 417K is put in 500K partition 112K is put in 200K partition 426K is put in 600K partition Worst-fit:

212K is put in 600K partition 417K is put in 500K partition

112K is put in 388K partition 426K must wait

（2）Best-fit算法充分利用了内存空间。

第七版8.12 Consider the following segment table:

What are the physical addresses for the following logical addresses? a. 0,430 b. 1,10 c. 2,500 d. 3,400 e. 4,112

答：作业ch9-第四题

a. 430<600, 219+430 = 649 ； b. 10<14, 2300+10 = 2310 ； c. 500>100, illegal ；

d. 400<580, 1327+400 = 1727 ； e. 112>96, illegal 第九章

9.13 一个页面置换算法应使发生页错误的次数最小化。怎样才能通过将使用频率高的页平均分配到整个内存而不只是竞争少数几个页帧页来达到这种最小化。可以对每个页帧设置一个计数器来记录与此帧相关的页数。那么当置换一个页时，就可以查找计数器值最小的页帧 Answer:

a.定义一个页面置换算法解决问题：

Ⅰ.计数器初始值——0；

Ⅱ.计数器值增加——每当新的一页与此帧相关联；

Ⅲ.计数器值减少——每当与此帧相关联的一个页不再需要； Ⅳ.怎样选择要被置换的页——找到带有最小计数器值的帧。使用先进先出算法解

除其关系 b.14个页错误 c.11个页错误

9.15 颠簸的原因是什么？系统怎样检测颠簸？一旦系统检测到颠簸，系统怎样做来消除这个问题？ Answer:

分配的页数少于进程所需的最小页数时发生颠簸，并迫使它不断地页错误。该系统可通过对比多道程序的程度来估计CPU利用率的程度，以此来检测颠簸。降低多道程序的程度可以消除颠簸。 第十章

第六版10.11 Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.

How many page faults would occur for the following replacement algorithms, assuming

one, two, three, four, five, six, or seven frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each. LRU replacement FIFO replacement Optimal replacement

第十二章

12.1 Consider a file currently consisting of 100 blocks. Assume that the file control block (and the index block, in the case of indexed allocation) is already in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level)

allocation strategies, if, for one block, the following conditions hold. In the contiguousallocation case, assume that there is no room to grow in the beginning, but there is room to grow in the end. Assume that the block information to be added is stored in memory. a. The block is added at the beginning. b. The block is added in the middle. c. The block is added at the end.

d. The block is removed from the beginning. e. The block is removed from the middle. f. The block is removed from the end.

12.2 Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently

serving a request at cylinder 143, and the previous request was at cylinder 125.

The queue

of pending requests, in FIFO order, is

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

Starting from the current head position, what is the total distance (in cylinders) that

the disk arm moves to satisfy all the pending requests, for each of the following diskscheduling

algorithms?（假设一个错哦盘驱动器有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.