Swap Studies
From PEL Wiki
Contents |
Overview
We are trying to come up with a study that shows that swap performance can be improved. We feel that one shortcoming of swap is that there is only one bit of information of usage history. When the hardware uses a page it sets the access bit. This bit is cleared by the OS each epoch. Now when the OS goes to select a page to swap out, it only knows whether or not the page has been used in the last epoch. If we can collect more information, the OS can make better decision on which page to swap out.
The OS cannot collect more usage information because it does not know about individual memory accesses. (The user processes do not want to make a system call each time it wants to access memory.) The ideal solution is DiskRAM.
In this study we want to make a case for using DiskRAM by showing that with more information the OS can choose better pages to swap out.
Collecting more information
DiskRAM is a one way of collecting more information. In order to show that DiskRAM is needed, we put a history on each page in memory. That the OS will have more than one bit of information to use when deciding which page to swap out.
Papers
Token-ordered LRU: an effective page replacement policy and its implementation in Linux systems.
I found this paper in Understanding the Linux Kernel. They gather benchmarks and use them to study how thrashing begins. They then come up with a token system, that one process can claim. Once a process claims this token, its pages are protected from being swapped out. The idea is that if one process can be protected it will be able to continue until finished, thus freeing up resources for the other processes. They show that this prevents thrashing from happening.
They do mention that one process could want to hog all the memory. They use meassure to stop this process from claiming the token. They suggest that in such circumstances you just need to get more memory. What we want to show is that we can handle this situation by collecting more information and deciding which process to swap out.
Their algorithm is now part of the Linux 2.6.9 kernel.
Dynamic Tracking of Page Miss Ratio Curve for Memory Management
This is a paper that uses the protection bits on the page descriptor to create extra page faults to gather more information to choose which page to swap out.
Current Linux Swap Systems
From reading Understanding the Linux Kernel, I have gathered the following information about how Linux handles swap: (The next step is to verify this in the code).
- Linux uses two LRU lists to keep track of pages in memory. The lists store the page frame discriptors and not the actual page table entries.
- The active list stores recently used pages.
- The inactive list stores pages that haven't been accessed in a while and are eligiable for removal.
- The referenced bit in the page discriptor is used to create a "state machice" for moving the pages from one list to another.
- The reference bit gets set when the page is loaded (demand paging), loading on demand a memory mapped file, when swapping in a page, when looking up a page in the buffer cache, etc. (pg 693)
- As of now, I do not think that Linux uses the page table entries at all. The page frame discriptor just stores a count of the number of page table entries that point to this page.
- This means that the kernel never even looks at the accessed bits set by the processor.
Categories: Pel | Chris | Swap
