Thrashing

Thrashing

• Thrashing occurs when a process does not have "enough" frames allocated to store the pages it uses repeatedly, the page fault rate will be very high.

• A process is thrashing if it is spending more time for paging in/out than executing. Since thrashing leads to low CPU utilization, the operating system's medium or long term scheduler may step in, detect this and increase the degree of multiprogramming.

• Local replacement algorithms can limit the effects of thrashing. If the degree of multiprogramming is increased over a limit, processor utilization falls down considerably because of thrashing. Fig. 4.14.1 shows thrashing.

• The selection of a replacement policy to implement virtual memory plays an important part in the elimination of the potential for thrashing. A policy based on the local mode will tend to limit the effect of thrashing. Replacement policy based on the global mode is more likely to cause thrashing. Since all pages of memory are available to all transactions, a memory-intensive transaction may occupy a large portion of memory, making other transactions susceptible to page faults and resulting in a system that thrashes.

• Thrashing is solved by using working set model and page fault frequency.

Working Set Model

• Working sets model is proposed by Peter Denning to prevent thrashing.

• We define the working set of information W (t, τ) of a process at time t to be the collection of information referenced by the process during the process time interval (t- τ, t). Fig. 4.14.2 shows working set model.

• Here is the working set parameter. The elements of W (t, τ) are pages but they can be anything else used by a role of process.

• If the sum of all working sets of all runnable threads exceeds the size of memory, then stop running some of the threads for a while. Divide processes into two groups active and inactive.

• When a process is active its entire working set must always be in memory: never execute a thread whose working set is not resident. When a process becomes inactive, its working set can migrate to disk.

• Threads from inactive processes are never scheduled for execution. The collection of active processes is called the balance set. The system must have a mechanism for gradually moving processes into and out of the balance set. As working sets change, the balance set must be adjusted.

How to compute working sets ?

Δ = Working set windows size.

Example: Assume windows size is 10 and the reference string given below, on which the window is shown at different time instants.

Page Fault Frequency

• Page fault frequency is used to preventing thrashing. Page fault rate is controlled by using this method. In the per-process replacement policy, each process is allocated a fixed number of physical page frames. Then monitor the rate at which page faults are occurring for each process.

1. If the rate gets too high for a process, assume that its memory is overcommitted; increase the size of its memory pool.

2. If the rate gets too low for a process, assume that its memory pool can be reduced in size.

3. If the sum of all memory pools doesn't fit in memory, deactivate some processes. 

Example 4.14.1 Given the following reference string:

0 1 2 3 0 1 2 3 0 1 2 3 4 5 6 7

Determine WS(t_i) with Δ = 9.

Solution :

Locality of Reference

• Locality of reference is also known as the principle of locality. Many applications continually reference large amounts of data.

• Locality of reference is observes that an application does not access all of its data at once with equal probability. Instead, it accesses only a small portion of it at any given time.

• There are two basic types of reference locality.

1. Temporal locality 2. Spatial locality

1. Temporal locality: Temporal locality is locality over time. If at one point in time a particular memory location is referenced, then it is likely that the same location will be referenced again in the near future.