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

scheduler will be significantly higher than the
average time allocated to the processes by the
original Linux scheduler. The processes in the
real memory will not be able to cause thrashing
during the execution of the group, because their
total size is not higher than the size of the avail-
able physical memory i.e. the size of each bin.
Only at the beginning of each group execution
there will be an intensive swapping, because the
new group's pages are swapped into the memory.
This approach can improve the system ability to
support memory-consuming processes in a more
tolerant way than killing them.
There are some methods to calculate the work-
ing set size needed by each process. One of these
methods can be found in (Zhou et al., 2004). In
this paper, the authors suggest a way that adds
7-10% overhead. Obviously, such an overhead is
time consuming and not suitable for the concept
of the bin packing approach. The scheduler needs
to know the working set size on every context
switch and calculating this working set often is
costly. We use another simple approach. The resi-
dent size of each process was taken from /proc/
PROCESS_NO/status file. This size is the process'
last pages total size. This size is not accurate and
if the system is not busy, the resident size may
include large portions of stale pages that are not
currently essential. However, when the system
is not busy, there will be no thrashing and this
overestimation will make no harm.
In our implementation, the group time slice
was half a second or one second, whereas the
Linux scheduler gives time slices of some dozen
milliseconds. When Linux thrashes, any context
switch causes many page faults, whereas with the
medium-term scheduler, intensive swapping will
occur only when switching between groups. This
lets the operating system in our implementation
swapping a significant amount of pages only in a
few percents of the cases, in contrast to conven-
tional Linux during thrashing conditions.
The processes which are not in the current
group should be kept on a different queue, so that

Linux scheduler will not be able to see them. In
order to implement this feature, we added a new
record to Linux kernel code. This record has the
same structure as the “active” and “expired” re-
cords described in (Beck et al., 1998) and it holds
the hidden processes.
When the last group finishes its execution,
the medium-term scheduler is invoked, and re-
builds the process groups, taking into account
any changes to the old processes (e.g. exited or
stopped) and adding any new processes to the
groups.
Sometimes the current group finishes executing
all the processes within the time slice awarded to
it by the medium-term scheduler. Even if there are
still some processes in the group, these processes
might be sleeping. If not all the processes in the
group are ready to be executed, the Linux scheduler
has been modified to invoke the medium-term
scheduler, which promptly switches to the next
waiting group.
The medium-term scheduler takes the sum of
the memory sizes that are currently needed by the
processes and divides this sum by the available
physical memory size. The quotient is taken to be
the number of bins. After that, the medium-term
scheduler scatters the processes between these
bins. The medium-term scheduler uses the greedy
algorithm until the medium-term scheduler is
unable to fit another process into the bins. Next,
the medium-term scheduler tries to find room for
all the remaining processes in the existing bins.
If it fails to find room in one of the existing bins,
it exceeds the size of the smallest bin by add-
ing the unfitting process to it. The original Bin
Packing problem does not allow such an excess,
but in this case it might be preferable to have a
few page faults within a group than adding an
additional bin.
One of our assumptions for a working solu-
tion is that there exist a considerable number
of processes for a good bin packing, and some
small memory demands processes are even better.
However, if one process demand is larger than