Thrashing begins when a system spends more effort moving pages than executing useful instructions. The tempting response to low CPU utilisation, admitting another process, can make the collapse worse. To answer GATE questions reliably, connect that feedback loop to frame allocation, the working set and the effective memory access time calculation.
Demand paging and the cost of a miss
Under demand paging, a process's page is brought into a physical frame only when the process references it. If the page is not resident, the reference causes a page fault. The operating system must locate the page on secondary storage, load it into a frame, update the page table and restart the interrupted instruction.
A normal main-memory access is measured in nanoseconds, while servicing a fault can take milliseconds. That large gap means a fault rate that looks numerically small can dominate the average access time.
The operating system therefore needs to give an active process enough frames to hold the pages it is using repeatedly. Memory Hierarchy and Virtual Memory: paging, the TLB, and address translation supplies the wider address-translation picture behind this frame budget.
Why page faults explode at the thrashing cliff
At first, raising the degree of multiprogramming helps. More processes make it likely that one can use the CPU while another waits for input or output. CPU utilisation rises.
The rise cannot continue indefinitely. Physical memory is fixed. Once too many active processes divide the frames, each process may hold fewer pages than its current locality needs. It faults, waits for a page, resumes briefly and faults again. Several processes now compete for the same limited frames and paging device.
The utilisation curve therefore rises to a peak and then drops sharply. If the scheduler interprets the low utilisation as a shortage of runnable work and admits more processes, each process receives even fewer frames. The resulting positive feedback is the classic thrashing loop.
Possible controls act on memory pressure rather than merely on CPU scheduling:
Local replacement prevents one process from taking frames allocated to another.
A working-set policy estimates the frames each active process currently needs.
A page-fault-frequency policy adds or removes frames according to fault-rate thresholds.
Suspending a process reduces the degree of multiprogramming and releases its frames.
The working set model defined precisely
The working set W(t, delta) is the set of distinct pages referenced in the most recent delta memory references ending at time t. The window length delta is measured here in references, not in the number of distinct pages found.
Use this reference string with delta = 4:
position: 1 2 3 4 5 6 7 8 9 10 11 12
page: 1 2 3 4 1 2 5 1 2 3 4 5At position 4, the last four references are 1 2 3 4. Their distinct-page set is {1, 2, 3, 4}, so the working-set size is 4.
At position 7, the window covers positions 4 through 7: 4 1 2 5. Its set is {1, 2, 4, 5}, again of size 4.
At position 11, the window covers positions 8 through 11: 1 2 3 4. Its set is {1, 2, 3, 4}, also of size 4.
Repeated references inside a window count once. For example, a window 1 2 1 2 contains four references but has working-set size 2.
For process i, let its working-set size be WSSi. The total demand is the sum of the active processes' working-set sizes. If that demand exceeds the number of available frames, every active working set cannot fit at once, so thrashing follows. The operating system can suspend a process and reallocate its frames until total demand fits.
Worked EMAT example and the tolerable fault rate
Suppose:
memory access time is
100 nspage-fault service time is
8 mspage-fault rate is
pacceptable effective memory access time is at most
200 ns, a two-times slowdown
First convert the units:
8 ms = 8 x 10^6 ns = 8,000,000 nsNow form the weighted average:
EMAT = (1 - p) x 100 + p x 8,000,000 ns
= 100 - 100p + 8,000,000p
= 100 + 7,999,900p nsApply the target:
100 + 7,999,900p <= 200
7,999,900p <= 100
p <= 100 / 7,999,900
p <= 0.000012500156...
p is approximately 1.25 x 10^-5The reciprocal is approximately 80,000, so the system can tolerate only about one page fault per 80,000 accesses before the average reaches 200 ns. An 8 ms fault service is 80,000 times a 100 ns memory access. Even that tiny fault probability doubles EMAT.
Traps GATE plants in thrashing questions
Thrashing is caused by insufficient frames for active localities, not simply by a slow paging device. A faster device reduces the fault penalty but does not remove an overcommitted frame demand.
The working set counts distinct pages, not references. Keep the fault-service unit consistent with the memory-access unit before using EMAT. Also retain both probability terms: (1 - p) for the ordinary access path and p for the fault path.
Local and global replacement have different consequences. Local replacement confines a process to its allocated frames. Global replacement lets it take a frame from another process, which can spread high fault rates. Page-fault frequency is a threshold-control method, while the working-set model estimates a locality from a recent window.
For the algorithm-level fault counting that often accompanies this concept, continue with Page Replacement Algorithms for GATE: FIFO, LRU and Optimal with Belady's Anomaly Explained.
How GATE tests working sets and EMAT
Typical questions ask you to identify the falling part of a utilisation curve, list the working set at an instant, compare replacement scopes, calculate EMAT or find a maximum fault rate for a stated slowdown.
For current subject weightage or paper-pattern details, use the official GATE 2027 portal. Working-set definitions and EMAT calculations are independent of the exam year.
Short version and next step
Thrashing occurs when active processes have too few frames for their localities. W(t, delta) is the distinct set of pages in the latest delta references, and the sum of working-set sizes estimates total frame demand. With an 8 ms fault service time, roughly one fault in 80,000 accesses already doubles a 100 ns access when service takes 8 ms.
Build the topic in GATE Guidance by Sanchit Sir, test it under time pressure in the GATE Test Series, and use the GATE preparation category to plan the rest of Operating Systems.
