Chapter Ten Notes

Question 1

LRU Algorithm

Answer 1

Use past knowledge rather than future

Replace page that has not been used in the most amount of time
Associate time of last use with each page
12 faults - better than FIFO but worse than OPT

Question 2

LRU Implementations and requirements

Answer 2

May require substantial hardware assistance.

Counters. In the simplest case, we associate with each page-table entry a time-of-use
field and add to the CPU a logical clock or counter. We replace the page with the smallest
time value.
2. Stack. Whenever a page is referenced, it is removed from the stack and put on the top. In
this way, the most recently used page is always at the top of the stack, and the least
recently used page is always at the bottom. Using doubly linked list the tail pointer points
to the bottom of the stack, which is the LRU page.

Question 3

Second change algorithm

Answer 3

One way to implement the second-
chance algorithm (sometimes referred to
as the clock algorithm) is as a circular
queue.
* A pointer (that is, a hand on the clock)
indicates which page is to be replaced
next.
* When a frame is needed, the pointer
advances until it finds a page with a 0
reference bit.
* As it advances, it clears the reference bits.
* Once a victim page is found, the page is
replaced, and the new page is inserted in
the circular queue in that position

Question 4

Enhanced second chance algorithm

Answer 4

Improve algorithm by using reference bit and modify bit (if available)
in concert
* Take ordered pair (reference, modify)
1. (0, 0) neither recently used nor modified – best page to replace
2. (0, 1) not recently used but modified – not quite as good, must
write out before replacement
3. (1, 0) recently used but clean – probably will be used again soon
4. (1, 1) recently used and modified – probably will be used again soon
and need to write out before replacement
* When page replacement called for, use the clock scheme but use the
four classes replace page in lowest non-empty class
* Might need to search circular queue several times

Question 5

Fixed allocation

Answer 5

Equal allocation – For example, if there are 100 frames (after allocating
frames for the OS) and 5 processes, give each process 20 frames
* Keep some as free frame buffer pool

Question 6

Priority allocation

Answer 6

Use a proportional allocation scheme using priorities rather than
size
* If process P i generates a page fault,
* select for replacement one of its frames
* select for replacement a frame from a process with lower priority
number

Question 7

Global allocation

Answer 7

typically refers to the allocation of memory that persists throughout the entire program’s execution. Global variables, for example, are allocated space in memory when the program starts and retain that space until the program terminates.

Question 8

Local Allocation

Answer 8

Local allocation, on the other hand, usually refers to the allocation of memory that is tied to a specific function or scope. Local variables in a function, for instance, are allocated memory when the function is called and deallocated when the function exits.