Chapter Ten Notes Flashcards

1
Q

LRU Algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

LRU Implementations and requirements

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Second change algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Enhanced second chance algorithm

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Fixed allocation

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Priority allocation

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Global allocation

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Local Allocation

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly