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

the available memory size, the solution will not
be effective and the process will thrash within
itself. In fact, most of the thrashing cases are not
caused by one process. However, if such a case
does occur, none of the solutions that have been
presented in section 1 can be useful. In such a case,
only the original Linux solution that kills such a
process will be beneficial, but it can be harmful
if the process is essential.

medium-term scheduler does not call the Linux
swap management at this point, because it might
swap out pages that may be needed again for the
next group.

Shared memory

Often, two or more processes share some memory.
Shared memory widely exists in most of the
operating systems and Linux has some tools to
handle it too.
When using the medium-term scheduler, it
will be inefficient to put two processes that share
a large piece of memory into two different groups
of processes. For example, consider the follow-
ing scenario:
Suppose processes A and B share a piece of
memory, process A is of group #1 and process B is
of group #3. After group #1 completes its execu-
tion, the pages of group #1 are swapped out and
the pages of group #2 are loaded and placed in
the physical memory instead, as we explained in
the previous section. The same swapping happens
when the operating system replaces group #2 by
groups #3. The pages of process B are loaded by
demand, so the same pages, albeit not all of them,
are loaded and swapped twice, once for process
A and once again for process B.
This situation is illogical and inefficient; hence,
the medium-term scheduler must put processes
with a large shared memory in the same group.
In order to tackle this situation we must know
which processes share pages, and which pages
they share. Each process that uses a page incre-
ments the “count” field of the page (Bovet and
Cesati, 2003), so reading this field can easily let
the Linux know which pages are shared. However,
the medium-term scheduler must still know which
processes use the page. A naive approach would
be searching the page table of all the processes, in
order to extract the addresses of the given pages.
Obviously, this will be very time consuming and
will probably impair the medium-term scheduler
efficiency.

Swapping management

When the time slice of a group ends, a context
switch of groups will be performed. This context
switch will probably cause many page faults:
The kernel uses its swap management to make
room for the processes of the new group and this
procedure might be long and fatiguing. The previ-
ous group of processes has most probably used
up most of the available physical memory, and
when the swap thread executes the LRU function
to find the best pages to swap out to the disk, it
will probably find pages of the old group. This
procedure is wasteful because the paging function
is performed separately for every new required
page. Linux kernel does not know at the context
switch time that the recently used pages of the
previous group will not be needed for a long time,
and can be swapped out.
In order to overcome this Linux kernel manage-
ment, we modified Linux kernel as follow: when
the medium-term scheduler is invoked, it calls the
Linux swap management functions to swap out
all of the pages that belong to the processes of
the previous group. This gives Linux a significant
amount of empty frames for the new group. This
swapping management approach is much quicker
than incrementally loading the pages of the new
process group, and for each page fault searching
for the oldest page in the physical memory to swap
out. When a round of the medium-term scheduler
is completed, the medium-term scheduler will
rebuild the process groups and some processes
may migrate from one group to another; hence the