Page 203 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes 9. What is the purpose of paging the page tables?
10. Consider the hierarchical paging scheme used by the VAX architecture. How many
memory operations are performed when an user program executes a memory load
operation?

11. Compare the segmented paging scheme with the hashed page tables scheme for handling
large address spaces. Under what circumstances is one scheme preferrable over the
other?

12. Discuss the hardware support required to support demand paging.
13. What is the copy-on-write feature and under what circumstances is it beneficial to use
this feature? What is the hardware support required to implement this feature?

14. A certain computer provides its users with a virtual-memory space of 2 bytes. The
32
computer has 218 bytes of physical memory. The virtual memory is implemented by paging,
and the page size is 4096 bytes. A user process generates the virtual address 11123456.
Explain how the system establishes the corresponding physical location. Distinguish
between software and hardware operations.
15. Discuss situations under which the least frequently used page-replacement algorithm
generates fewer page faults than the least recently used page replacement algorithm. Also
discuss under what circumstance does the opposite holds.
16. Consider a demand-paging system with the following time-measured utilizations:

CPU utilization 20%
Paging disk 97.7%

Other I/O devices 5%
17. Suppose that your replacement policy (in a paged system) is to examine each page regularly
and to discarding that page if it has not been used since the last examination. What would
you gain and what would you lose by using this policy rather than LRU or second-chance
replacement?
18. A page-replacement algorithm should minimize the number of page faults. We can do
this minimization by distributing heavily used pages evenly over all of memory, rather
than having them compete for a small number of page frames. We can associate with each
page frame a counter of the number of pages that are associated with that frame. Then,
to replace a page, we search for the page frame with the smallest counter.

(a) Define a page-replacement algorithm using this basic idea. Specifically address the
problems of (1) what the initial value of the counters is, (2) when counters are increased,
(3) when counters are decreased, and (4) how the page to be replaced is selected.

(b) How many page faults occur for your algorithm for the following reference string,
for four page frames?

1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.
(c) What is the minimum number of page faults for an optimal page replacement strategy
for the reference string in part b with four page frames?

196 LOVELY PROFESSIONAL UNIVERSITY