If there is an increase in the number of processes submitted to the CPU for execution, then the CPU utilization will be increased. But by increasing the process continues at a certain time, the CPU utilization falls sharply and sometimes it reaches 0. This situation is said to be thrashing.

Scope

This article explains thrashing in detail

Definition

If CPU utilization is too small, then we increase the degree of multiprogramming by introducing a new process to the system. 

Suppose a process enters a new phase in its execution and needs more frames. It starts faulting and taking processes away from other processes. These faulting processes use the paging device to swap pages in and out. As the process waits for the paging device, CPU utilization decreases.

The CPU scheduler increases the degree of multiprogramming on finding a decrease in CPU utilization. The new processes start taking frames from each other processes thereby causing more page faults and a long queue for the paging device. Due to all this, CPU utilization decreases further thus making the CPU scheduler increase the degree of multiprogramming even more. This causes thrashing and also throughput decreases.

This can be represented as –

From the figure, we can see that the degree of multiprogramming increases with the increase in CPU utilization although more slowly until the maximum is reached. 

Now if the degree of multiprogramming increases even further, thrashing comes into the picture, and CPU utilization drops sharply. 

At this point, we must decrease the degree of multiprogramming in order to increase CPU utilization and stop thrashing. 

The effects of thrashing can be minimized by local replacement (priority replacement algorithm). So what happens in local replacement is that if one process starts thrashing it cannot steal frames from another process thereby causing the latter to thrash as well.

If the processes are thrashing the average time for the page fault will increase because they will be in a queue for paging devices most of the time. The effective access time will increase. 

The working set strategy starts by looking at how many frames a process is actually using. This approach is known as the locality model of process execution.

The locality model states that, as a process executes, it moves from locality to locality. A locality is a set of pages that are actively used together. It also states that all programs will exhibit a basic memory reference structure. 

WORKING SET MODEL – Based on the assumption of locality :

• This model uses a parameter Δ to define a working set window. It is to examine the most recent Δ page references. 
• If the page is in active use, it will be in the working set and if it is no longer being used, it will drop from the working set Δ time units after its last reference. Thus the working set is the approximation of the program’s locality. 
• The accuracy of the working set depends on the selection of Δ.

If  Δ is too small, it will not encompass the entire locality.

If  Δ is too large, it will overlap several localities

If  Δ is infinite, the working set is the set of pages touched during the process execution.

• The most important property of a working set is its size. The working set size for each process can be computed :

                  D = Σ WSSi        D – total demand for frames

• Each process is actively using the pages in its working sets. Thus the process needs WSSi frames.
• If there are not enough frames to fulfill demand then thrashing will occur because some processes will not have enough frames. 
• The working set strategy prevents thrashing while keeping the degrees of multiprogramming as high as possible. Thus it optimizes CPU utilization.
• It is difficult to keep 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 at the other end.

Summary

• A process is thrashing if it spends more time in paging than executing.
• If the CPU scheduler increases the degrees of multiprogramming and CPU utilization drops sharply then thrashing occurs.
• Effects of thrashing can be minimized using a priority replacement algorithm and working set model. 

Special thanks to Ami Jangid for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article