Review 70-108

Question 1

What are the advantages of using Virtual memory?

Answer 1

• 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

Question 2

How could we implement Virtual memory?

Answer 2

Demand paging and demand segmentation

Question 3

What is the usual practice in the utilization of virtual address space?

Answer 3

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.

Question 4

What is a lazy swapper?

Answer 4

It starts swapping of segments only when the swap is needed to open up space in the physical memory.

Question 5

What is a pager?

Answer 5

It performs the swapping operation on “pages” rather than on segments.

Question 6

How is the “valid-invalid (VI)” bit used in a page table?

Answer 6

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 7

Question # 76

What are the contents of entries of the page table below?

Answer 7

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 8

Question # 77

What does the following diagram show?

Answer 8

• 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.

Question 9

What is the “zero-fill-on-demand” strategy?

Answer 9

OS adds a frame to the list of “free-frame-list” by zeroing the content of a frame.

Question 10

Does the zero-fill-on-demand strategy increase the efficiency of demand paging?

Answer 10

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.

Question 11

For a demand paging system, consider the page fault rate is p, what is the Effective Access Time (EAT) for such a system?

Answer 11

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)

Question 12

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

Answer 12

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.

Question 13

What is copy on write?

Answer 13

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).

Question 14

When a page fault occurs, what happens if there is no free frame?

Answer 14

OS has to replace a frame so it can bring in the demanded page.

Question 15

What is a “modify (dirty) bit?” What is the difference between the “dirty” bit and a valid bit?

Answer 15

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.

Question 16

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?

Answer 16

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.

Question 17

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

Answer 17

See image. Question # 86.

Question 18

What is Belady’s optimal page replacement method?

Answer 18

It considers that it knows the future and replaces the page that will not be used shortly.

Question 19

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

Answer 19

See image. Question # 88

Question 20

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

Answer 20

See image. Question # 89

Question 21

What are the two main methods for implementing LRU?

Answer 21

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.

Question 22

How is the “second chance” or the “clock” replacement method implemented?

Answer 22

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.

Question 23

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

Answer 23

Frame 1 should be replace.

0 1 0 0
0 0 0 0
1 1 0 0
1 1 1 0

Question 24

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

Answer 24

Frame 1 should be replace.

0 1 0 0
0 0 0 0
1 1 0 0
1 1 1 0

Question 25

Question # 94

Answer 25

Question # 94

Question 26

What is the “enhanced second-chance”replacement method?

Answer 26

It uses two bits for each frame, a dirty-bit and a reference bit.

00 means that the page is not referenced since the last page fault, and it is not modified. Such a frame has the highest priority for replacement.

10 shows that the frame is referred to but has not been changed. This page has the second-highest priority replacement since it does not need a write- back.

01 indicates that the page is not referenced, but it is modified. This page has the second-lowest priority for removal since we need to write it back into the disk.

11 means that the page has been referenced and has been modified. This page has the lowest priority for replacement.

Based on FIFO, frames are tested. If the pair of bits are 00, then the page is replaced. Otherwise, the reference bit of the page is set to zero, and the next frame is tested. If no frame is found in the first round, then a second round is performed.

Question 27

What is thrashing?

Answer 27

If a process uses all of its allocated memory space and needs another page, then a page fault would occur. An active page of this process has to be replaced, which causes another page fault. Hence, each page fault replaces a frame that is being used and causes another page fault. Continuous page faults severely reduce performance. This situation is known as “thrashing.”

Question 28

What is the relationship between locality and thrashing?

Answer 28

If the overall locality of all active processes is larger than the physical memory, then thrashing occurs. This situation means that active processes need to refer to a more extensive space than the main memory. Hence, one active frame has to be replaced by a new page, and this loop causes threshing.

Question 29

Question # 98

Answer 29

Question # 98

Question 30

Windows implements “demand-paging” using “clustering.” What is clustering?

Answer 30

Besides bringing in the demanded page, it brings in the surrounding pages too. For example, if page number N from the virtual space is demanded, then pages N-1 and N+1 are also brought into the main memory.

Question 31

What is the working set of a Process Pi?

Answer 31

It is the list of all pages referenced in the most recent ∆ time steps.

Question 32

Question # 101

Answer 32

Question # 101

Question 33

What happens if the working set consists of a small number of page references?

Answer 33

It means that the locality of the process is very high;

hence, the process has needed to reference only a few pages.

Question 34

Question # 103

Answer 34

Question # 103

Question 35

Windows uses two concepts of “working set minimum” and “working set maximum.” What are these two concepts, and how are they used?

Answer 35

Working set minimum is the minimum number of pages the process is guaranteed to have in memory. A process may be assigned as many pages up to its working set maximum.

Question 36

What are the similarities between Windows, Solaris, and Linux in dealing with virtual memory?

Answer 36

They all use demand paging and copy-on- write. Each system also uses a variation of LRU approximation known as the clock algorithm.

Question 37

What does Windows do when a process loses frames below its “working set minimum”?

Answer 37

Windows will take away frames from those processes that have frames more than their “working set minimum” and gives them to those processes that have frames less than their minimum.

Question 38

What is prepaging?

Answer 38

When a process starts, it has a high page fault rate because none of its needed pages are resident in the main memory. To avoid high page faults, all or most of the pages of the process are brought into the main memory before they are demanded and before generating page faults. After a while, if some of these pages are not being used, they will be replaced.

Question 39

What is page fault frequency?

Answer 39

Number of page faults that occur in a unit of time for a process is called page fault frequency. For example, suppose the number of faults that arise for a process in every 10000 references is very low. In that case, it means that the process has a high locality and is not using all of its allocated frames, and we can take away some of its unused frames. If the page-fault frequency is very high, it means that the process needs more frames, and we should assign more frames to that process.