A process has a memory reference pattern as follows: 2 3 1 3 1 2 4 3 2 1 3 2 The
ID: 3856357 • Letter: A
Question
A process has a memory reference pattern as follows:
2 3 1 3 1 2 4 3 2 1 3 2
The above pattern (which represents the virtual page numbers of the process) repeats
throughout the execution of the process. Assume that there are only 3 physical frames. Please fill up the following Table to
show the paging activity for a True LRU page replacement policy. Show an LRU
stack and the page that is replaced (if any) for the first 12 accesses. Clearly indicate
which accesses are hits and which are page faults.
H = Hit, PF= Page Fault, NA= Not Available (Do not fill up anything if it is NA)
2
3
1
3
1
2
4
3
2
1
3
2
Frame 1
Frame 2
Frame 3
LRU
NA
NA
NA
NA
NA
NA
NA
NA
NA
NA
NA
NA
Stack
Stack
Stack
H/PF
2
3
1
3
1
2
4
3
2
1
3
2
Frame 1
Frame 2
Frame 3
LRU
NA
NA
NA
NA
NA
NA
NA
NA
NA
NA
NA
NA
Stack
Stack
Stack
H/PF
Explanation / Answer
Under what circumstances do page faults occur? Describe the actions taken by the operating system when a page fault occurs. Answer: A page fault occurs when an access to a page that has not been brought into main memory takes place. The operating system verifies the memory access, aborting the program if it is invalid. If it is valid, a free frame is located and I/O is requested to read the needed page into the free frame. Upon completion of I/O, the process table and page table are updated and the instruction is restarted. 9.2 Assume that you have a page-reference string for a process with m frames (initially all empty). The page-reference string has length p; n distinct page numbers occur in it. Answer these questions for any page-replacement algorithms: a. What is a lower bound on the number of page faults? b. What is an upper bound on the number of page faults? Answer: a. n b. p 9.3 Consider the page table shown in Figure 9.30 for a system with 12-bit virtual and physical addresses and with 256-byte pages. The list of free page frames is D, E, F (that is, D is at the head of the list, E is second, and F is last). Convert the following virtual addresses to their equivalent physical addresses in hexadecimal. All numbers are given in hexadecimal. (A dash for a page frame indicates that the page is not in memory.) • 9EF • 111 29 30 Chapter 9 Virtual Memory • 700 • 0FF Answer: • 9E F - 0E F • 111 - 211 • 700 - D00 • 0F F - EFF 9.4 Consider the following page-replacement algorithms. Rank these algorithms on a five-point scale from “bad” to “perfect” according to their page-fault rate. Separate those algorithms that suffer from Belady’s anomaly from those that do not. a. LRU replacement b. FIFO replacement c. Optimal replacement d. Second-chance replacement Answer: Rank Algorithm Suffer from Belady’s anomaly 1 Optimal no 2 LRU no 3 Second-chance yes 4 FIFO yes 9.5 Discuss the hardware support required to support demand paging. Answer: For every memory-access op
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.