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

the M i s in each group not exceeding the size of
the real memory. Practically, the kernel and some
other daemons occupy part of the memory, so the
sum should not exceed a smaller memory size.
This splitting problem is well known and called
the Bin Packing problem (Scholl et al., 1997).
The Bin Packing problem is defined as a set
of numbers X 1 , X 2 , ..., X n , with X i ∈ [0, 1] for
each i. The problem is finding the smallest natural
number m for which:

◦ Open a new bin and put the current

number in it.

• Else

◦ Put the current number in the current

bin.

In our tests, we used a version of this approxi-
mation algorithm with a slight modification. We
usually achieved the minimal number of bins
and the cost of execution time was usually low.
Below we describe the version that has been use
in this chapter.. • X

1 , X 2 , ..., X n can be partitioned into m
sets.
The sum of the members of each set is not •

bin pacKing baSed paging higher than one.

The Bin Packing problem is NP-hard (Karp,
1972). However, some polynomial time approxi-
mations have been introduced over the years, such
as (Fekete and Schepers, 2001), (Gent, 1998) and
(Martello and Toth, 1990). The approximation
algorithms use no more than (1+E)*OPT(I) num-
ber of bins, where OPT(I) is the number of bins
in the optimal solution for case I. If E is smaller,
the result will be closer to the optimal solution,
but unfortunately good approximations are usu-
ally time consuming (Coffman et al., 1997). We
would like to choose one of the approximation
algorithms which is not time consuming, but yet
tries minimizing (1+E)*OPT(I).
A simple idea of an approximation algorithm
for the Bin Packing problem is the greedy ap-
proach (Albers and Mitzenmacher, 2000), also
known as the First-Fit approach. This algorithm
is defined as follow:

It is well known that increasing the level of mul-
titasking in any operating system may sometimes
cause thrashing. In order to avoid thrashing, we
would like to suggest a new approach: All the
processes will be split into several groups such
that the sum of physical memory demands within
each group will not be higher than the amount of
physical memory available on the machine. In
(Alverson et al., 1995) the authors give some ideas
to use a Bin Packing approximation (First Fit) to
improve the Backfilling scheduling of a specific
Operating System (Tera). We would like to use
the Bin Packing Algorithms to improve the Linux
scheduling using more approximations.

medium-term Scheduler

A new scheduler procedure will be added to the
Linux operating system. The new scheduler will
operate in the manner of the medium-term sched-
uler, which was part of some operating systems
(Stallings, 1998). The medium-term scheduler
will load the groups into the Ready queue of the
Linux scheduler in a Round-Robin manner. The
traditional Linux scheduler will do the schedul-
ing within the current group in the same way the
scheduling is originally done on Linux machines.
The time slice of each group in the medium-term

• Sort the vector X

1 , X 2 , ..., X n by the allo-
cated memory size.
Open a new bin and put the highest number •

in it.
While there are more numbers •

• If adding the current number to one of the

existing bins exceeds the size of the bin