Page 198 - DCAP103_Principle of operating system

Unit 5: Memory Management

and its frames are reallocated to other processes. The suspended process can be restarted later. Notes
This working-set strategy prevents thrashing while keeping the degree of multiprogramming as
high as possible. Thus, it optimizes CPU utilization. The difficulty with the working-set model
is keeping track of the working set. The working-set window is a moving window. At each
memory reference, a new reference appears at one end and the oldest reference drops off the
other end. A page is in the working set if it is referenced anywhere in the working-set window.
We can approximate the working-set model with a fixed interval timer interrupt and a reference
bit. For example, assume A is 10,000 references and we can cause a timer interrupt every 5,000
references. When we get a timer interrupt, we copy and clear the reference-bit values for each
page. Thus, if a page fault occurs, we can examine the current reference bit and 2 in-memory
bits to determine whether a page was used within the last 10,000 to 15,000 references. If it was
used, at least 1 of these bits will be on. If it has not been used, these bits will be off. Those pages
with at least 1 bit on will be considered to be in the working set. Note that this arrangement
is not entirely accurate, because we cannot tell where, within an interval of 5,000, a reference
occurred. We can reduce the uncertainty by increasing the number of our history bits and the
frequency of interrupts (for example, 10 bits and interrupts every 1,000 references). However,
the cost to service these more frequent interrupts will be correspondingly higher.
5.12.3 Page-fault Frequency

The working-set model is successful, and knowledge of the working set can be useful for
prepaging but it seems a clumsy way to control thrashing. A strategy that uses the page-fault
frequency (PFF) takes a more direct approach.

Figure 5.38: Page-fault Frequency

The specific problem is how to prevent thrashing. Thrashing has a high page-fault rate. Thus,
we want to control the page-fault rate. When it is too high, we know that the process needs
more frames. Similarly, if the page-fault rate is too low, then the process may have too many
frames. We can establish upper and lower bounds on the desired page-fault rate. If the actual
page-fault rate exceeds the upper limit, we allocate that process another frame; if the page-fault
rate falls below the lower limit, we remove a frame from that process. Thus, we can directly
measure and control the page-fault rate to prevent thrashing.

LOVELY PROFESSIONAL UNIVERSITY 191