Thrashing

     If the number of frames allocated to a low-priority process falls below the minimum number required by the computer architecture, we must suspend that process's execution. We should then page out its remaining pages, freeing all its allocated frames. This provision introduces a swap-in, swap-out level of intermediate CPU scheduling.

     In fact, look at any process that does not have "enough" frames. If the 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. 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.A process is thrashing if it is spending more time paging than executing.

Reason of Thrashing

     Thrashing results in severe performance problems. Consider the following scenario, which is based on the actual behavior of early paging systems.

     The operating system monitors CPU utilization. If CPU utilization is too low, we increase the degree of multiprogramming by introducing a new process to the system. A global page-replacement algorithm is used; it replaces pages without regard to the process to which they belong. Now suppose that a process enters a new phase in its execution and needs more frames. It starts faulting and taking frames away from other processes. These processes need those pages, however, and so they also fault, taking frames from other processes. These faulting processes must use the paging device to swap pages in and out. As they queue up for the paging device, the ready queue empties. As processes wait for the paging device, CPU utilization decreases.

     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 longer 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. The page fault rate increases tremendously. As a result, the effective memory-access time increases. No work is getting done, because the processes are spending all their time paging.

     This phenomenon is illustrated in Figure 9.18, in which CPU utilization is plotted against the degree of multiprogramming. As the degree of multiprogramming increases, CPU utilization also increases, although more slowly, until a maximum is reached. If the degree of multiprogramming is increased even further, thrashing sets in, and CPU utilization drops sharply. At this point, to increase CPU utilization and stop thrashing, we must decrease the degree of multiprogramming.

     We can limit the effects of thrashing by using a local replacement algorithm  (or priority replacement algorithm) With local replacement, if one process starts thrashing, it cannot frames from another process and cause the latter to thrash as well. However, the problem is not entirely solved. 

Prevent thrashing

To resolve thrashing due to excessive paging, a user can do any of the following:

• Increase the amount of RAM in the computer.
• Decrease the number of programs being run on the computer.
• Replace programs that are memory-heavy with equivalents that use less memory.
• Assign working priorities to programs, i.e. low,normal,high.
•  Improve spatial locality by replacing loops like:

int m[256][256]; 

  for (row=0; row<256; row++) {

    for (column=0; column<256; column++) {

      // consecutive columns reside in adjacent memory locations 

      m[row][column] = foo(); 

    } 

  }