Authors Top

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

1. Introduction

In this tutorial, we’ll discuss the concept of thrashing.

2. Thrashing

In Operating Systems, paging is a storage mechanism used to retrieve processes from the secondary storage into the main memory in the form of pages.

Every process needs a minimum number of pages to execute. If the process doesn’t have the number of frames it needs to support pages in active use, it’ll quickly page-fault. At this point, it must replace some pages. However, since all its pages are in active use, it must replace a page that will be needed again right away.

Consequently, it quickly faults again, and again, and again, replacing pages that it must bring back in immediately. This high paging activity is called thrashing.

3. Cause of Thrashing

CPU consumption is monitored by the operating system. If CPU utilization is too low, a new process is introduced to improve multiprogramming. A global page-replacement technique is used, which replaces pages regardless of which process they belong to.

Let’s assume that a process begins a new phase of execution and requires more frames. It begins to fault and steal frames from other processes. These processes, however, require those pages, and as a result, they also fail, stealing frames from other processes.

To swap pages in and out, these faulting processes must employ the paging device. The ready queue empties as they queue for the paging device. CPU utilization drops when processes wait for the paging device.

The CPU scheduler sees the decreasing CPU utilization and increases the degree of multiprogramming as a result. The new process tries to get started by taking frames from running processes, causing more page faults and a long queue for the paging device. As a result, CPU utilization drops even further, and the CPU scheduler tries to increase the degree of multiprogramming even more. Thrashing has occurred, and system throughput plunges:

thrash

4. Solution for Thrashing

4.1. Local Replacement Algorithm

When using local replacement, if one process starts thrashing, it cannot steal frames from another process and cause the latter to thrash as well.

4.2. Working Set Model or Locality Model

As a process executes, it moves from locality to locality, where a locality is a set of pages that are actively used together. This model uses a parameter \Delta to define the working set window. The set of pages in the most recent \Delta page references is the working set. If a page is in active use, it will be in the working set. If it is no longer being used, it will drop from the working set \Delta time units after its last reference.

The accuracy of the working set depends on the selection of \Delta. If \Delta is too small, it will not encompass the entire locality; if \Delta is too large, it may overlap several localities. The most important property of the working set, then, is its size.

If there are m processes, we compute the working-set size, WSS{i}, for each process in the system. We can then consider that D= \sum WSS{i}, where D is the total demand for frames. Each process is actively using the pages in its working set. Thus, process i needs WSS{i} frames. If the total demand is greater than the total number of available frames (D > m), the thrashing will occur because some processes will not have enough frames.

After selecting Δ, 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 selects a process to suspend.

In the following figure, the series of numbers is the pages required by a process. If the working set size is taken as nine, then the pages in the working set are shown at time t{1} and t{2}:

ws

4.3. Page Fault Frequency Strategy

We can establish upper and lower bounds on the desired page-fault rate. If the actual page-fault rate exceeds the upper limit, another frame is allocated to the process; if the page-fault rate falls below the lower limit, a frame is removed from the process:

pagefault

5. Conclusion

In this article, we’ve discussed the concept of thrashing, its causes, and strategies to deal with thrashing.

Authors Bottom

If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our Contribution Guidelines.

Comments are closed on this article!