:PROPERTIES: :ID: 8c3b743c-8836-418b-a1be-3f5f10e35cf0 :mtime: 20240316061037 :ctime: 20240316061036 :END: #+title: thrashing (memory) #+filetags: :operatingsystems:public:project: * Thrashing If the number of [[id:f4c06160-2fba-4dce-b76f-14519c8817ea][frames]] allocated to a low-priority [[id:ea9ceb4e-ff99-4939-ad40-90d5dae2d567][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. - This high paging activity is called thrashing. - A process is thrashing if it is spending more time paging than executing. ** Cause 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. ** Working Set Solution - the working-set model is based on the assumption of locality. - This model uses a parameter, Δ, to define the working-set window. - The idea is to examine the most recent Δ page references. - The set of pages in the most recent Δ page references is the [[id:90e4cdf4-6dae-4ed4-be1c-189bf55db2e1][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 Δ time units after its last reference. Thus, the working set is an approximation of the program’s locality. - The accuracy of the working set depends on the selection of Δ. If Δ is too small, it will not encompass the entire locality; - if Δ is too large, it may overlap several localities. In the extreme, if Δ is infinite, the working set is the set of pages touched during the process execution.