最新操作系统第九版部分课后作业习题答案分析解析

精品文档

assuming that page frame 1 contains the process and the other two are initially empty? a. for (int j = 0; j < 100; j++) for (int i = 0; i < 100; i++) A[i][j] = 0;

b. for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++) A[i][j] = 0; Answer: a. 5,000 b. 50

9.8 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, ?ve, six, or seven frames? Remember all frames are initially empty, so your ?rst unique pages will all cost one fault each. ?

LRU replacement ? FIFO replacement ?

Optimal replacement32 Chapter 9 Virtual Memory

精品文档

精品文档

Answer:

Number of frames LRU FIFO Optimal 1 20 20 20 2 18 18 15 3 15 16 11 4 10 14 8 5 8 10 7 6 7 10 7 7 77 7

9.9 Suppose that you want to use a paging algorithm that requires a reference

bit (such as second-chance replacement or working-set model), but the hardware does not provide one. Sketch how you could simulate a reference bit even if one were not provided by the hardware, or explain why it is not possible to do so. If it is possible, calculate what the cost would be. Answer:

You can use the valid/invalid bit supported in hardware to simulate the reference bit. Initially set the bit to invalid. On ?rst reference a trap to the operating system is generated. The operating system will set a software bit to 1 and reset the valid/invalid bit to valid.

9.10 You have devised a new page-replacement algorithm that you think

精品文档

精品文档

may

be optimal. In some contorted test cases, Belady’s anomaly occurs. Is the new algorithm optimal? Explain your answer. Answer:

No. An optimal algorithm will not suffer from Belady’s anomaly because —by de?nition—an optimal algorithm replaces the page that will not be used for the longest time. Belady’s anomaly occurs when a pagereplacement algorithm evicts a page that will be needed in the immediate

future. An optimal algorithm would not have selected such a page. 9.11

Segmentation

is

similar

to

paging

but

uses

variable-sized“pages.”De?ne

two segment-replacement algorithms based on FIFO and LRU pagereplacement schemes. Remember that since segments are not the same

size, the segment that is chosen to be replaced may not be big enough to leave enough consecutive locations for the needed segment. Consider strategies for systems where segments cannot be relocated, and those for systems where they can. Answer:

a. FIFO. Find the ?rst segment large enough to accommodate the incoming segment. If relocation is not possible and no one segment

精品文档

精品文档

is large enough, select a combination of segments whose memories are contiguous, which are “closest to the ?rst of the list” and which can accommodate the new segment. If relocation is possible, rearrange the memory so that the ?rstNsegments large enough for the incoming segment are contiguous in memory. Add any leftover space to the free-space list in both cases.Practice Exercises 33 b. LRU. Select the segment that has not been used for the longest period of time and that is large enough, adding any leftover space to the free space list. If no one segment is large enough, select a combination of the “oldest” segments that are contiguous in memory (if relocation is not available) and that are large enough. If relocation is available, rearrange the oldest N segments to be contiguous in memory and replace those with the new segment.

9.12 Consider a demand-paged computer system where the degree of multiprogramming is currently ?xed at four. The system was recently measured to determine utilization of CPU and the paging disk. The results are one of the following alternatives. For each case, what is happening? Can the degree of multiprogramming be increased to increase the CPU utilization? Is the paging helping?

a. CPU utilization 13 percent; disk utilization 97 percent b. CPU utilization 87 percent; disk utilization 3 percent c. CPU utilization 13 percent; disk utilization 3 percent

精品文档