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

答：作业ch8-第二题

第七版7.7 Consider a system consisting of m resources of the same type, being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock-free if the following two conditions hold:（假设一个系统有m个资源被n个进程共享，进程每次只请求和释放一个资源。证明只要系统符合下面两个条件，就不会发生死锁）

a. The maximum need of each process is between 1 and m resources（每个进程需要资源的最大值在1到m之间）

b. The sum of all maximum needs is less than m + n（所有进程需要资源的最大值的和小于m+n）

答：作业ch8-第三题

使用Section7.6.2的术语,可以有： a.

?ni?1Maxi

b. Maxi ≥ 1 for all i Proof: Needi = Maxi ? Allocationi If there exists a deadlock state then: c.

?ni?1Allocationi = m Use a. to get:Use c. to get:

?Need+ ?Allocation = ?Max< m + n iii?Need+ m < m + n iRewrite to get:

?ni?1Needi 这意味着存在一个Pi的进程，其Needi=0.如果 Maxi>=1，那么Pi进程至少有一个资源可以释放。从而系统就不会进入死锁状态。

第七版7.11 Consider the following snapshot of a system:

Answer the following questions using the banker’s algorithm:（使用银行家算法回答下面的问题）

a. What is the content of the matrix Need?（Need矩阵的内容是怎样的？） b. Is the system in a safe state?（系统是否处于安全状态？）

c. If a request from process P1 arrives for (0,4,2,0), can the request be granted immediately?（如果从进程P1发出一个请求（0 4 2 0），这个请求能否被满足？） 答：作业ch8-第四题

a. Need矩阵的内容是P0（0 0 0 0） P1（0 7 5 0） P2（1 0 0 2） P3（0 0 2 0） P4（0 6 4 0）。

b. 系统处于安全状态，因为Available矩阵等于（1 5 2 0），进程P0和P3都可以运行，当进程P3运行完时，它释放它的资源，而允许其它进程运行。 c. 可以被满足，满足以后，Available矩阵等于（1 1 0 0），当以次序P0，P2, P3, P1 ,P4运行时候，可以完成运行。 第八章

第七版8.3 Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would each of the First-fit, Best-fit, and Worst-fit algorithms place processes of 212K, 417K, 112K, and 426K (in order)? Which algorithm makes the most efficient use of memory?（按顺序给出5个部分的内存，分别是100KB,500KB,200KB,300KB和600KB，用 first-fit,best-fit和worst-fit算法，能够怎样按顺序分配进程212KB,417KB,112KB,426KB和426KB？哪个算法充分利用了内存空间？） 答：作业ch9-第二题

（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.