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
Answer:
a. Thrashing is occurring.
b. CPU utilization is suf?ciently high to leave things alone, and increase degree of multiprogramming. c. Increase the degree of multiprogramming.
9.13 We have an operating system for a machine that uses base and limit registers, but we have modi?ed the machine to provide a page table. Can the page tables be set up to simulate base and limit registers? How can they be, or why can they not be? Answer:
The page table can be set up to simulate base and limit registers provided that the memory is allocated in ?xed-size segments. In this way, the base of a segment can be entered into the page table and the valid/invalid bit used to indicate that portion of the segment as resident in the memory. There will be some problem with internal fragmentation.
9.27.Consider a demand-paging system with the following time-measured utilizations: CPU utilization 20% Paging disk 97.7% Other I/O devices 5%
Which (if any) of the following will (probably) improve CPU utilization? Explain your answer.
a. Install a faster CPU. b. Install a bigger paging disk.
c. Increase the degree of multiprogramming. d. Decrease the degree of multiprogramming. e. Install more main memory.
f. Install a faster hard disk or multiple controllers with multiple hard disks.
g. Add prepaging to the page fetch algorithms. h. Increase the page size.
Answer: The system obviously is spending most of its time paging, indicating over-allocation
of memory. If the level of multiprogramming is reduced resident processes
would page fault less frequently and the CPU utilization would improve. Another way to
improve performance would be to get more physical memory or a faster paging drum.
a. Get a faster CPU—No. b. Get a bigger paging drum—No.
c. Increase the degree of multiprogramming—No. d. Decrease the degree of multiprogramming—Yes.