Review 70-108 Flashcards
What are the advantages of using Virtual memory?
- Only part of the program needs to be in memory for execution
- Logical address space can be much larger than physical space
- Several processes can share address spaces
- More efficient utilization of physical memory
- More programs can run concurrently
- Less I/O needed to load processes
How could we implement Virtual memory?
Demand paging and demand segmentation
What is the usual practice in the utilization of virtual address space?
A program consists of a fixed-size code and different types of data. The stack starts at the highest virtual address, and the code begins at address zero. On top of the code are data, and on top of data, the heap of linked variables is placed.
What is a lazy swapper?
It starts swapping of segments only when the swap is needed to open up space in the physical memory.
What is a pager?
It performs the swapping operation on “pages” rather than on segments.
How is the “valid-invalid (VI)” bit used in a page table?
If there were no such a bit, then the table’s initial content may be considered valid frame numbers even if all the table entries were zero. Hence, initially, all of the “VI” bits are zero. Initially, the first demand page causes a “page fault” because the VI bit is zero. After the page is read, then the bit becomes valid (one).
Question # 76
What are the contents of entries of the page table below?
SEE IMAGE.
Line 0 of PT has 4, line 2 has 6, and line 5 has 9. Valid bits of these lines are 1. The rest of the page table is empty (valid bits are zero.)
Question # 77
What does the following diagram show?
- CPU is referencing a page that is not in the physical memory, and it has an “invalid” bit in the page table
- A trap (interrupt) occurs, and OS takes over the execution process
- OS finds the demanded page in the hard disk
- OS brings the demanded page into the physical memory
- OS updates the page table’s frame number and valid bit.
- The interrupted instruction of the process takes back the control and restart execution.
What is the “zero-fill-on-demand” strategy?
OS adds a frame to the list of “free-frame-list” by zeroing the content of a frame.
Does the zero-fill-on-demand strategy increase the efficiency of demand paging?
No. It adds an overhead. It doesn’t help identify free frames because checking the zero content of a frame is a lengthy process. It is much faster to test the valid bit of a frame to see if it is free. Hence, the only reason for zeroing the content is for security purposes.
For a demand paging system, consider the page fault rate is p, what is the Effective Access Time (EAT) for such a system?
Average access time is: (probability of finding the page in a frame × access time to frame) + (probability of page fault × delay time to get the page from the disk. The probability of page fault is p, and the probability of finding the page in a frame in main memory is 1 - p. The delay time to get the page from disk includes (page fault overhead + swap page out + swap page in). Hence:
EAT = (1 - p) * (main memory access time) + p*(page fault overhead + swap page out + swap page in)
For a demand paging system, assume the following. The main memory access time is 300 ns, and access time to the hard disk is 11 ms (includes all the overheads and swap in and out time.) We want the effective access time for such a system to be only 20% larger than the main memory access time. What should be the maximum page fault rate?
Question #81
EAT = (1 - p) * (main memory access time) + p*(page fault overhead + swap page out + swap page in)
EAT = (1 − 𝑝)300n𝑠 + 𝑝(11𝑚𝑠) = 300n𝑠 – 𝑝𝑝×300n𝑠 + 𝑝×11000000n𝑠
We want EAT to be 20% higher than 300ns. Therefore, we want EAT to be 300ns +20% (300ns) = 360ns= 120% of 300ns.
EAT = (1 − 𝑝)300n𝑠 + 𝑝(11m𝑠) = 300n𝑠 – 𝑝×300n𝑠 + 𝑝×11000000n𝑠 = 360ns
So, if EAT is supposed to be 360, what is the maximum value of page fault probability (what is the value of p)?
360ns = 300n𝑠 + (11000000n𝑠 – 300n𝑠)𝑝
60ns = (11000000ns – 300ns)𝑝 ⇒ 𝑝 = 10.0000054
This means that if you want the average access time to the memory be only 20% more than the access time to the main memory, the page fault frequency should be only 1 in 185185.
𝑝 = 1/85185 = 0.0000054.
What is copy on write?
Occasionally, two identical processes are created. Each one should have its own memory space. But OS places only one set of pages for both processes to use. If process1 writes into the shared page A, then page A is copied for process1. Process2 will have the original copy of page A. This is known as copy on write (CoW).
When a page fault occurs, what happens if there is no free frame?
OS has to replace a frame so it can bring in the demanded page.
What is a “modify (dirty) bit?” What is the difference between the “dirty” bit and a valid bit?
The valid shows whether the content of the page table is valid or not. The dirty bit shows whether the content of the frame has been changed or not. If the dirty bit is zero, then there is no need to write it back into the disk.
Suppose that we have the following sequence of references to virtual pages. Each number in this sequence of 21 references shows the page number that the CPU has referred.
1, 4, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1
Using FIFO, how many page faults occur if a) we only have one frame in our main memory? B) we have two frames in the memory? C) if we have three frames? D) if we have four frames in the memory?
If the main memory is only one frame, then each time the sequence wants to access a new page, a page fault occurs. For example, if the sequence has four consecutive 1’s, then only the first reference to page 1 would cause a fault, and the other three references to page 1 are hits. Hence, in the above sequence, 11 page- faults occur if we only have one frame. If we have 2 frames in the memory, then 4 page-faults occur. If we have 3 frames, then 3 faults occur, and with 4 frames, we will have 3 page-faults.
Suppose that we have the following string of references:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Further, assume that we only have three frames in the main memory. We want to use a FIFO strategy for page replacement. Fill out the frames in the image below with the appropriate page number.
Question #86
See image. Question # 86.
What is Belady’s optimal page replacement method?
It considers that it knows the future and replaces the page that will not be used shortly.
For the following string of references fill out the image with appropriate page numbers based on Belady’s Optimal replacement method:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Question # 88
See image. Question # 88
For the following string of references fill out the image with appropriate page numbers based on LRU (least recently used) replacement method:
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Question # 89
See image. Question # 89
What are the two main methods for implementing LRU?
1) using a counter next to each frame. Every time that frame is referenced the counter is incremented. When it comes to replacing a frame, the frame with the smallest counter value is replaced. After each frame replacement, all counters are reset to zero.
2) We can use a stack. When a page enters the main memory, the page number will be on top of the stack. Every time a page is referenced its number goes to the top of the stack. When we want to replace a frame the one at the bottom of the stack is replaced.
How is the “second chance” or the “clock” replacement method implemented?
A reference bit (W) is assigned to each frame. Every time that a frame is referenced, its W bit is set to 1. When a frame is replaced, all W bits are reset to zero. The FIFO strategy is implemented. When a page fault occurs, the frames are tested based on FIFO. If the frame has a zero W, then it is replaced. If the frame has one W, then it is given a second chance, and its W is reset to zero. Then the next frame based on FIFO is checked, and so on.
Suppose that the main memory consists of 4 frames. The followings equence of frames have been references:
0, 1, 2, 3, 2, 1, 0, 3, 2, 3
At the end of this sequence, a page fault occurs, and one of the frames must be replaced using the “clock” strategy. Which frame is replaced?
Question # 93
Frame 1 should be replace.
0 1 0 0
0 0 0 0
1 1 0 0
1 1 1 0
Suppose that the main memory consists of 4 frames. The followings equence of frames have been references:
0, 1, 2, 3, 2, 1, 0, 3, 2, 3
At the end of this sequence, a page fault occurs, and one of the frames must be replaced using the “clock” strategy. Which frame is replaced?
Question # 93
Frame 1 should be replace.
0 1 0 0
0 0 0 0
1 1 0 0
1 1 1 0
