Alleviating the Thrashing by Adding Medium-Term Scheduler - Advanced Operating Systems and Kernel Applications - page 118

Chapter 7
Alleviating the Thrashing
by Adding Medium-
Term Scheduler

Moses Reuven
Bar-Ilan University, Israel

Yair Wiseman
Bar-Ilan University, Israel

abStract

A technique for minimizing the paging on a system with a very heavy memory usage is proposed. When
there are processes with active memory allocations that should be in the physical memory, but their accu-
mulated size exceeds the physical memory capacity. In such cases, the operating system begins swapping
pages in and out the memory on every context switch. The authors lessen this thrashing by placing the
processes into several bins, using Bin Packing approximation algorithms. They amend the scheduler to
maintain two levels of scheduling - medium-term scheduling and short-term scheduling. The medium-
term scheduler switches the bins in a Round-Robin manner, whereas the short-term scheduler uses the
standard Linux scheduler to schedule the processes in each bin. The authors prove that this feature does
not necessitate adjustments in the shared memory maintenance. In addition, they explain how to modify
the new scheduler to be compatible with some elements of the original scheduler like priority and real-
time privileges. Experimental results show substantial improvement on very loaded memories.

introduction al., 1991), (Wiseman and Feitelson, 2003).

Usually, most of the processes do not make
use of the entire memory that has been allocated
for them. This shows the way to the principle of
virtual memory (Denning, 1970): Many processes
have allocations in the virtual memory, but only
the pages which are currently required will be
physically stored in the memory; therefore, many
more processes can be executed in parallel, while
occupying less physical memory space.

One of the most substantial computer resources is
the RAM. Multitasking operating system executes
several processes simultaneously. Each one of the
processes uses several sections of the memory.
The connection of the memory and the scheduling
strategy is an old subject for research (Zahorjan et