Thrashing

Thrashing

If a process does not have the number of frames it needs to support pages in active use, it will quickly page fault. At this point it must replace some page that will be needed again immediately. Consequently it quickly page faults again, and again, and again replacing pages that it must bring back immediately.

This high paging activity is called Thrashing. A process is thrashing if it is spending more time paging than executing.

Cause of Thrashing

Early process scheduling schemes would control the level of multi programming allowed based on CPU utilization, adding in more processes when CPU utilization was low. The problem is that when memory filled up and processes started spending lots of time waiting for their pages to page in, then CPU utilization would lower, causing the schedule to add in even more processes and worsen the problem. Eventually the system would essentially grind to a halt.

To limit the effects of thrashing a local replacement algorithm can be used. With local replacement if one process starts thrashing it cannot steal frames from another process and cause it to thrash. However, the problem is not entirely solved. The effective access time will increase even for a process that is not thrashing.

To prevent thrashing, a process needs to be provided with as many frames as it needs. There are several techniques to do so.

The working-set strategy is a approach which defines the locality model of process execution.

The locality model notes that processes typically access memory references in a given locality, making lots of references to the same general area of memory before moving periodically to a new locality. If we could just keep as many frames as are involved in the current locality, then page faulting would occur primarily on switches from one locality to another.

Working-Set Model

The working set model is based on the concept of locality, and defines a working set window, of length (∆) delta. Whatever pages are included in the most recent delta page references are said to be in the processes working set window, and comprise its current working set. 

The selection of delta is critical to the success of the working set model - If it is too small then it does not encompass all of the pages of the current locality, and if it is too large, then it encompasses pages that are no longer being frequently accessed.

The total demand, D, is the sum of the sizes of the working sets for all processes. If D exceeds the total number of available frames, then at least one process is thrashing, because there are not enough frames available to satisfy its minimum working set. If D is significantly less than the currently available frames, then additional processes can be launched.

The working-set strategy prevents thrashing while keeping the degree of multi-programming as high as possible.

The hard part of the working-set model is keeping track of what pages are in the current working set, since every reference adds one to the set and removes one older page. An approximation can be made using reference bits and a timer that goes off after a set interval of memory references