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

Figure 1. shared memory size of common processes

It frequently happens that applications which
share a piece of memory will have an almost equal
size of shared memory. If the shared memory stems
from a 'fork' system call, the child process will
be created from its parent; hence the size of the
shared memory in the parent process and the child
process will be almost equal, unless the child or
the parents allocate a large piece of new shared
memory. The same will be correct, if processes
share an IPC or a common text segment. If there
is no other shared memory obtained by just one
the processes, the shared memory size will be
almost equal.
Figure 1 shows the shared memory size in
some common cases. The data was obtained from
a running Linux machine that serves the Computer
Science department in Bar-Ilan University. Many
processes do not have shared memory and they
have been omitted from the figure. However,
when processes do share memory, it can be seen
that they usually have the same size of shared
memory.
Linux calculates the shared memory size of
each process. Based on the shared size character-
istic, we would like to suggest a simple solution
for the issue of large shared memory. When the
medium-term scheduler recalculates the bins of

the processes, it will first sort the vector of the
processes by the shared memory size. Then, us-
ing the greedy approximation, the processes with
almost equal shared memory size will usually
be in the same bin or in adjacent bins; hence no
swapping will be needed when replacing the pages
of two processes with shared memory.
We have chosen to use insertion sort for this.
Since we use the old sorted list of processes,
insertion sort is executed in the shortest time
(Manber, 1989).

group time Slice

Sometimes we can be lucky and the sizes of the
total memory needs in all the different groups are
almost equal. This is the best situation, because
a fixed time slice that will be given to the groups
is usually quite fair. However, when the sizes of
the total memory allocations are significantly dif-
ferent, some processes might get an implicit high
priority. When the medium-term scheduler uses
the greedy approximation, such a situation usu-
ally occurs when the last processes are assigned
to a bin. The last bin is sometimes almost empty;
hence the processes in this bin gain precedence,
because in the time slice of this bin, there are less