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

Figure 13. The memory performance of two LU programs (LU1 and LU2), each with a different input,
in their concurrent execution managed with swap token.

while the RSS curve of LU2 accordingly rose by
obtaining true LRU pages from LU1 . The mea-
surements show that the execution times of both
processes are significantly reduced by the swap
token compared with the ones in the original Linux
LRU. The slowdown of LU1 is 2.57 (a reduc-
tion of 28%), and is 2.99 for LU2 (a reduction
of 12%). The page fault reductions for LU1 and
LU2 are 87% and -116%, respectively. It is noted
that the execution time of LU2 was still reduced,
though its number of page faults was significantly
increased. This is because the page fault penalty
was reduced with more available I/O bandwidth
after the token was taken by LU1 .

recently proposed, including 2Q, LIRS, andARC.
However, in a multiprogramming environment,
the interactions between concurrently running
programs can have a large impact on memory
usage pattern. Specifically, an uncoordinated use
of memory among the processes can lead to the
system thrashing when their aggregate memory de-
mand considerately exceeds physical memory.
In the chapter, we have investigated sources
of memory performance degradation in program
interactions by carefully examining the LRU
memory page replacement and its representative
implementations in Linux systems. We have exper-
imentally demonstrated that the false LRU pages
can be a serious loophole in the LRU replacement
implementations because these implementations
do not correctly reflect and predict memory access
patterns of interacting programs.
In order to overcome the limitations in the LRU
replacement in program interactions, the swap
token mechanism is designed and implemented
in the memory management system of the Linux
kernel. Rather than pinning all pages of a token-
holding process in memory, the swap token only
protects its true LRU pages from swapping to
establish an orderly page replacement, and allows

concluding remarKS

Management of memory hierarchies has been an
intensive study for several decades. Regarding
the large gap in access time between memory and
disk, a lot of work has been done to reduce the
number of page faults for each program. Research
on page replacement algorithms have been a clas-
sical topic since 1960s and many improvements
over the LRU page replacement policy have been