Thrashing – Virtual Memory

Thrashing

Thrashing is a situation in which a system spends more time in processing page faults than executing instructions of processes. Thrashing degrades the performance of a system. There may be a situation when the memory is full with pages that are accessed frequently. A page fault will occur if the required page is not present in memory.

In order to make space for swapping in the required page, one of the frequently accessed pages is swapped out from main memory. Soon, the page that is swapped out is required for execution and this again results page fault. Thus, a series of page fault occur and swapping becomes a large overhead. Thrashing generally occurs in multitasking operating system. As in multitasking, thee are several processes running at the same time, so memory becomes over-committed and it leads to thrashing.

In other words, thrashing is directly related to degree of multiprogramming (number of process that are being executed simultaneously) in following manner: 

1. When a global page replacement algorithm is used, it replaces pages with no regard to the process to which they belong.
2. After increasing the degree of multiprogramming, if a particular process enters a new phase, it may need more frames.
3. Under these circumstances, this process starts faulting and takes away frames from other processes.
4. These processes need those pages, however and so they also fault and take frames from other processes.
5. All these faulting processes then queues up for the paging device to swap pages in and out. As processes wait for paging device, CPU utilization decreases.
6. When CPU scheduler sees the decrease in CPU utilization, it increases the degree of multiprogramming. Thus new processes enter the system and take the frames from running processes. This results in more page faults and longer queue for paging devices.
7. As a result, CPU utilization drops even further and thrashing sets in.

The performance of system is satisfactory to certain extent. When degree of multiprogramming is increased, it leads to thrashing and system performance degrades.

Methods to handle thrashing

The various methods used for handling thrashing are:

1. The operating system attempts to recover from thrashing by suspending the execution of current processes and preventing the execution of new processes to start.
2. Thrashing can be removed by selecting an appropriate page replacement algorithm.
3. Thrashing can also be avoided by using a local page replacement algorithm. With local replacement, the process cannot take frames from another process. It just selects and swaps the page which belongs to the same process. In this way, thrashing of a particular process does not affect other processes and therefore they can continue execution properly.
4. Thrashing can also be prevented by allocating a process as many frames as it needs. The need of a particular process can be determined by working set model.

Working set model

• The working set of a process is a collection of pages referenced by a process during a recent interval of time.
• The working-set model is based on the assumption of locality.
• It is important that for a program to run effectively its working set of pages must be maintained in main memory, otherwise thrashing might occur as the program repeatedly requests pages from the secondary storage.
• This model uses a parameter, Δ, to define the working set window. The idea is to examine the most recent Δ page references.
• The working set is usually expressed using functional notation W(t, Δ) where W represent the working set, t represents the time, and Δ represents the window size.
• For example, given the sequence of memory references. If Δ= 10 memory references, then the working set at time t, is (1, 2, 5, 6, 7). By time t, working set has changed to {3, 4}.

• The goal is to pick a value for Δ so that the working set reflects the locality of reference.
• If the value of Δ is too small, it will not include all the pages in the current activity. If the value of A is too large, it may overlap several localities and include pages from a previous locality.

Use of working set

• The operating system monitors the working set of each process and allocates to that working set enough frames to provide it with its working set size.
• If there are enough extra frames, another process can be initiated.
• If the sum of the working set sizes increases, exceeding the total number of available frames, the operating system select a process to suspend.
• The process’ pages are written out and its frames are reallocated to other processes. The suspended process can be restarted later.
• Thus, working set model prevents thrashing while keeping the degree of multiprogramming as high as possible. This results in optimum CPU utilization.