Swap Token - Advanced Operating Systems and Kernel Applications - page 100

the limitations of the global LRU replacement
implementation, the fairness issue remains to be
addressed in the load control policies.

We let two instances of the program run si-
multaneously, allocating a 53 MB array for one
process (referred as small process hereafter) and
a 58 MB array for another process (referred as
large process hereafter) by adjusting variable size
in the program. Closely tracing the page access
behaviors of each process before and after the
token was set in the system, we present the impact
of the token to each of the interacting programs.
Figure 8 presents space-time graphs for the small
process (left graph) and the large process (right
graph) during their interaction, where y -axis
represents three types of memory pages at dif-
ferent virtual addresses: recently visited pages
(or the pages that have been accessed in the last
one-second time window}, swapped-out pages,
and resident but not recently visited pages, and
the x -axis represents the execution time sequence.
The RSS size of each process can be approximated
by the sum of the number of “visited pages” and
the number of “resident but not visited pages” at
any execution point.
We have observed that each of the processes
expanded its RSS through page faulting and
meanwhile lost some of its pages under the false
LRU condition. The combination of these two
activities causes three effects: (1) neither process
could establish its working set; (2) the RSS size
of each process fluctuated; and (3) little useful
work could be done.
The token was set in the system and taken by
the small process (left graph in Figure 8) at the
execution time of 125 th second. After this time,
this process successfully kept its useful memory
pages and avoided false LRU pages, whose ef-
fect is reflected in the increased lightly gray area
for “resident but not visited pages”. During the
same period of time, the large process reduced its
number of “resident but not visited pages”. Once
the small process established its working set, all its
obtained pages were frequently visited. The token
only avoids swapping out the false LRU pages,
but still treats the true LRU pages as replacement
candidates. This can be confirmed by observing

a close look at the effect
of Swap token

To show how a swap token functions and its ef-
fectiveness, let us take a close look at its running
behavior during program interactions. The follow-
ing program segment is used in the experiment:

#define LOOP 1000
#define SIZE (53*1024*1024/
sizeof(double));

double * mem_page;
int size= SIZE;

mem_page = (double *)calloc(SIZE,
sizeof(double));
for (i = 0; i < LOOP; i++){
for (j = 0; j < SIZE; j += step){
mem_page[j] = mem_page[j] + 1;
Other computing work only on mem_
page[j];
}
if ((i+1)%10 == 0)
SIZE = (long)(0.9*SIZE);
}

This program uses 1000 loop iterations to ac-
cess a large array.At first the program sequentially
accesses its entire data array for ten times. Then for
each of its next ten iterations, the program reduces
its accessing range over the array by removing
10% of all its accesses at the end of the array. The
available user memory space was adjusted to 60
MB. The access pattern produces a large number
of page faults when there is a memory shortage.
In this experiment, we will demonstrate how the
token works to address the serious performance
degradation by reducing false LRU pages in
program interaction environment.