C191-Terms-Chapter-8

Question 1

Virtual memory (VM)

Answer 1

a collection of one or more logical address spaces, each of which may exceed the size of physical memory. A logical address is then referred to as a virtual address.

A paged VM creates a single large contiguous address space per process. A paged VM with segmentation creates multiple large address spaces per process, each of which is paged.

Question 2

Demand paging

Answer 2

the principle of loading a page into memory only when the page is needed, rather than at the start of the execution.

Question 3

present bit

Answer 3

a binary flag in each page table entry that indicates whether the corresponding page is currently resident in memory. If a page is resident, then the entry points to the frame that holds the page.

Question 4

page fault

Answer 4

an interrupt that occurs when a program attempts to reference a non-resident page. The interrupt triggers the operating system to find the page on disk, copy the page into a frame, and set the present bit to 1.

Demand paging makes the implementation of VM possible by moving pages to main memory only as needed.

Question 5

Page replacement

Answer 5

the act of overwriting a page in memory with a different page loaded from the disk when needed.

Moving pages between memory and the disk is very time consuming and must be minimized. When the page to be removed has not been modified during execution then an exact copy still exists on the disk and the page does not have to be copied back to the disk.

Question 6

modified-bit (m-bit)

Answer 6

a binary flag in each page table entry that indicates whether the corresponding page has been modified during execution. The modified bit is set to 1 automatically by any instruction that stores data into the page and is used by the operating system to minimize the movement of data to dis

Question 7

reference string

Answer 7

the sequence of page numbers referenced by an executing program during a given time interval. Reference strings are used to compare different page replacement algorithms by counting the number of page faults generated.

Question 8

optimal page replacement algorithm

Answer 8

selects the page that will not be referenced for the longest time in the future.

The algorithm is guaranteed to generate the smallest number of page faults for any reference string.

However, the algorithm is unrealizable because the replacement decisions depend on future references, which are unknown at runtime. But the algorithm provides a useful lower bound on the number of page faults for comparison with other algorithms.

Question 9

FIFO page replacement algorithm

Answer 9

selects the page that has been resident in memory for the longest time.

The algorithm is easy to implement, requiring only a single pointer to designate the oldest page in memory. When the page is replaced, the pointer is advanced to the next frame modulo n.

The FIFO algorithm takes advantage of the principle of locality. Except for branch instructions, which constitute only a small percentage of all instructions, execution is sequential.

As execution advances sequentially through the code, the likelihood of referencing a page used in the distant past diminishes with time. Similarly, many large data structures are processed in sequential order.

FIFO exploits the principle of locality to some degree but fails to recognize that a program frequently returns to pages referenced in the distant past.

FIFO replaces the oldest resident pages even if the pages have been referenced again recently and thus are likely to be referenced again in the near future.

Question 10

The least-recently-used page replacement algorithm

Answer 10

selects the page that has not been referenced for the longest time. The LRU requires the queue of pages to be modified at each memory reference, which makes the algorithm too inefficient in practice.

The implementation requires a queue of length n, where n is the number of memory frames. The queue contains the numbers of all resident pages.

Whenever a resident page p is referenced, p is moved from the head to the end of the queue. Thus the queue is always sorted from least recently used page to most recently used page.

When a non-resident page p is referenced, p is moved to the end of the queue and the least recently referenced page q at the head of the queue is removed. Page p then replaces q in memory.

Question 11

referenced bit (r-bit)

Answer 11

a bit associated with a page and is set automatically by the hardware whenever the page is referenced by any instruction.

Question 12

aging register

Answer 12

is associated with a page and is shifted periodically to the right by 1 bit. Unless the most significant bit is set to 1, the page is aging in the sense that the associated register value is steadily decreasing.

Question 13

aging page replacement algorithm

Answer 13

does not maintain pages sorted in the exact LRU order, but groups together pages referenced during a period of d consecutive references. Each period is represented by 1 bit in a periodically shifting aging register.

Question 14

second-chance page replacement algorithm

Answer 14

a coarse-grain approximation of LRU. The algorithm uses the r-bit to divide all pages into only two categories: recently referenced and not recently referenced. A page is selected from the not-recently referenced category.

Similar to FIFO, the algorithm maintains a pointer that cycles through the pages when searching for a page to be replaced. Because of its circular nature, the algorithm is also known as the clock algorithm.

At a page fault, the algorithm repeats the following steps until a page is selected for replacement:

If the pointer is at a page p with r = 0 then select p and advance the pointer to the next page.

Otherwise, reset r to 0, advance the pointer to the next page, and continue the search.

Question 15

The third-chance page replacement algorithm

Answer 15

The third-chance algorithm is a refinement of the second-chance algorithm. The algorithm takes advantage of both the r-bit and m-bit associated with every page.

Since replacing a modified page is more costly than replacing an unmodified page, the algorithm gives modified pages an additional chance to remain resident.

The third-chance page replacement algorithm, also known as the not-recently-used page replacement algorithm (NRU), is a coarse-grain approximation of LRU, which divides pages into 4 categories based on the 4 possible combination of the r- bit and the m-bit.

At a page fault, the algorithm repeats the following steps until a page is selected for replacement:

If the pointer is at a page p with r = 0 and m = 0 then select p and advance the pointer to the next page.

Otherwise, reset the bits according to the following table, advance the pointer to the next page, and continue the search.

A third bit is needed to remember if a page has been modified and thus needs to be written back to disk when selected for replacement.

Question 16

The working set concept

Answer 16

A program always needs a certain set of pages resident in memory to run efficiently. When not enough page frames are available, the page fault rate becomes too high and the process spends much of the time waiting for pages to be moved between the disk and the memory.

Question 17

optimal working set

Answer 17

of a process is the set of resident pages that will still be needed in the immediate future and thus should remain resident. The size of the working set varies with the program’s behavior.

When execution is highly localized in long tight loops and static data structures, the set contains a small number of repeated page numbers. When execution involves many branches or highly dynamic data structures, the set contains many different page numbers.

The optimal working set is unrealizable in practice because the algorithm requires advance knowledge of the RS.

The working set page replacement algorithm relies on the principle of temporal locality by assuming that recently referenced pages will be similar to pages referenced in the immediate future.

Question 18

To determine the size of the optimal working set:

Answer 18

To determine the optimal working set at time t, a window of size d is superimposed on the reference string.

Currently, resident pages that are still visible in the window belong to the set. The size and composition of the set change automatically as the window slides forward with each memory reference.

The window size is determined by the typical behavior of a newly started program. During the first few memory operations, the number of pages referenced increases rapidly but the rate of increase diminishes with time.

Thus d must be chosen to cover the period of rapid growth but not past the point where adding more pages is of only marginal benefit.

Question 19

working set (WS)

Answer 19

of a process at time, t is the set of pages referenced during the past d memory operations preceding t.

Question 20

working set page replacement algorithm

Answer 20

uses a trailing window of size d superimposed on the RS to determine the size and composition of the working set at time t. Analogous to the forward-looking window of the optimal working set, pages visible in the trailing window belong to the working set.

At each memory reference, the algorithm follows the steps:

Advance the sliding window by 1 to include the current reference.
Keep resident only the pages that appear in the window.

The working set page replacement algorithm is very effective in keeping the page fault frequency low but is difficult to implement in practice because the list of pages in the current working set changes with every memory reference.

Question 21

page-fault-frequency replacement algorithm

Answer 21

takes a direct approach to controlling the page fault rate by adjusting the current resident set based on how frequently consecutive page faults occur.

A constant d, determined experimentally, is used to decide if the page fault frequency is too high, and thus the resident set should be increased.

If the page fault frequency is acceptable then the resident set can be reduced by removing some of the pages not referenced recently.

When a page fault occurs:

Add the currently referenced page causing the page fault to the resident set.

When the time since the previous page fault is greater than d, remove all pages from the resident set that have not been referenced since the previous page fault.

The algorithm can be implemented efficiently since any action is taken only at a page fault.

Question 22

Page fault rate

Answer 22

is the number of page faults, f, occurring during a number of memory references, t. The page fault rate can be expressed as P = f/t, where 0 ≤ P ≤ 1.
P = 1 means that every memory reference results in a page fault, and P = 0 means that no page faults occur.

A page fault results in a significant overhead, which increases the average access time to memory.

Question 23

Effective access time

Answer 23

is the average time to access memory in the presence of page faults. The effective access time, E, depends on the frequency of page faults: E = (1 - P) * m + P * S where m is the time to access physical memory and S is the time to process a page fault.

Question 24

Load control

Answer 24

is the activity of determining how many processes should be running concurrently at any given time to maximize overall system performance.

Question 25

Thrashing

Answer 25

is an execution state during which most of the time is spent on moving pages between the memory and the disk while the CPU is mostly idle and no process is making any real progress.

Thrashing occurs when too many processes are sharing memory concurrently and no process has enough pages to operate without frequent page faults.

Page replacement algorithms that use variable numbers of frames prescribe the working set of every process. A process is allowed to run only if enough frames are available to hold the complete working set. The sum of all working sets thus imposes an automatic limit on how many processes can run at any given time.

Algorithms that use fixed numbers of frames do not impose any implicit limits. Consequently, a load control mechanism must be implemented to prevent thrashing.

Question 26

The choice of page size

Answer 26

The page size has a major impact on the time and space overhead of virtual memory and thus on the overall performance of the system.

The optimal page size depends on many factors, some of which favor a large size while others favor a small size. Consequently, the page size is always a compromise between the different factors.

The most common page sizes range between 512 and 4096 bytes but the number has been increasing in recent years with improvements in disk technology. To accommodate the needs of different programs, some systems even support multiple page sizes.