Thrashing
The high paging activity is called thrashing.
A process is thrashing if it is spending more time paging than executing.
If CPU utilization is too low, we increase the degree of
multiprogramming by introducing a new process. Later, a process enters a new
phase and needs more frames. It starts faulting and taking pages away from
other processes. But these processes need those pages, so they also fault,
taking pages from other processes. Now many processes wait for the paging, CPU
utilization decreases.
At this point, we must decrease the degree of multiprogramming to stop
thrashing.
We limit the effects of thrashing by using a local replacement
algorithm: If one process starts thrashing, it cannot steal frames from
another process and cause the latter to thrash as well.
To prevent thrashing, we must provide a process as many frames as it
needs. But how many?
Locality model:
A locality is a set of pages that are actively used together (a program is generally composed of several different localities, which may overlap).
This model states that as a process executes, it moves from locality to
locality.
For example: when a subroutine is called, it defines a new locality
(several pages in some frames of memory, memory references are made to this subroutine instructions, its local variables, etc). when this subroutine is finished, the process leaves this
locality, and goes to another locality (do something else).
-
It based on locality.
-
Using a parameter D to define the working-set
window
-
Exam the most recent D page references.
-
The set of pages in the most recent D page references is the
working set.
-
If a page is in active use, it is in the working
set, else, drop from the working set.
-
Example:
D=10 memory
reference
working set at time t1
is {1,2,5,6,7}
t2: {3,4}
process i needs WSSi frames
D=SWSSi D is the total
demand for frames.
If D>m (total demand > the total number
of available frames), thrashing will occur, because some processes will not
have enough frames.
-
Working set model prevents thrashing while keeping
the degree of multiprogramming as high as possible
-
It optimizes CPU utilization
-
We know, thrashing has a high page fault rate;
-
When page fault rate is too high, the process needs
more frames
-
If page fault rate is to low, then the process may
have too frames
-
We can have upper and lower bounds for the desired
page fault rate
-
If page fault rate is over the upper limit, we
allocate another frame to this process
-
If page fault rate is below the lower bound, we
remove a frame from it.