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

alities: adjusting user memory space allocation
and collecting system data. To flexibly adjust
the available memory space for user programs
in the experiments, the monitor program requests
a memory space of certain pre-defined size, and
excludes it from the page replacement with the
help from the kernel. The remaining memory is
available for executions of application programs
in our experiments. The monitor program will not
affect the experiment measurements, because (1) it
consumes few CPU cycles; (2) Its resident memory
is excluded from the global page replacement
scope, so its memory usage has no interactions
with application programs. The monitor program
dynamically collects following memory system
statistics once in every one second for each in-
teresting process:

routine is periodically called to examine
all the reference bits in the process's page
table to get the number.

In the experiments each program is first run in
a dedicated environment to observe its memory
access behavior without occurrence of major page
faults and page replacements because the memory
demand from a single program is smaller than the
available user space.

memory access behavior in
the dedicated environment

We use memory-time graphs to show the memory
usage of the selected programs in the dedicated
execution environment. In the graphs, the x axis
represents the execution time, and the y axis
represents the number of memory pages for three
memory usage curves: memory allocation demand
(MAD), resident set size (RSS), and number of
accessed pages (NAP). The memory usage curves
of the five benchmark programs measured by
MAD, RSS, and NAP are presented in Figures 1
and 2. With regard to the development of memory
demands, the memory usage patterns for the pro-
grams can be classified in three types according
to the graphs:

• Memory Allocation Demand ( MAD ): is the

total amount of requested memory space,
in pages, reflected in the page table of the
process. This memory allocation demand
is maintained and recorded in the kernel
data structure of task_struct .
Resident Set Size ( • RSS ): is the total amount

of physical memory used by the process, in
pages, and can be read from task_struct .
Number of Page Faults ( • NPF ): is the num-

ber of page faults of the process, and can
be read from task_struct. There are two
types of page faults for each process: mi-
nor page faults and major page faults. A
minor page fault will cause an operation to
relink the requested page in memory into
the page table. The cost of a minor page
fault is negligible. A major page fault hap-
pens when the requested page is not in
the memory and has to be retrieved from
the disk. We only collect major page fault
events for each process.
Number of Accessed Pages (

• Quickly acquiring memory allotments :

This type of programs demands stable
memory allocations from the beginning of
program executions. When the available
space is sufficient, they can quickly ac-
quire their allotments in the early stage of
their executions. Programs bit-r and gzip
belong to this type.

• Gradually acquiring memory allot-

ments : This type of programs gradually
increases their memory allotments as their
executions proceed, and accesses their
data sets regularly in each stage until their
executions complete. When the available
space is sufficient, their RSS sizes in each

• NAP ): is the

number of accessed pages by the process
within the last time interval of one sec-
ond. During a program execution, a system