Due by Monday, May 1.
The managing TA for all Xen track assignments is Pin Lu. All email inquiries about this assignment should be addressed to the TA and cc the instructor. This assignment will be examined through demo with the TA. Please schedule your time slot with the TA on Monday, May 1 or Tuesday, May 2. We expect each demo would take around 30 minutes. Please reserve your time slot with the TA ahead of the time. If you cannot make this time frame, it is possible for setting up the demo at a different time. Please contact the TA for such arrangement.
Disclaimer: This assignment is adapted from a project developed by Dr. Jason Nieh at Columbia University.
Whenever the Linux kernel needs to allocate frames of physical memory for something, it has to come from somewhere. If the machine was just booted, it will have lots of unused memory lying around, ready to be claimed. However, unused memory is wasted memory, so Linux does its best to fill a large percentage of memory as soon as possible. If programs aren't eating up lots of memory themselves, Linux uses the extra memory for caching disk data (in the buffer cache). Therefore, it never takes long before a request for memory cannot be satisfied from the pool of unused frames. When this happens, a frame that is in use must be freed, possibly by swapping out a page that is currently held in a frame. There is also a kernel process, called kswapd, that frees page frames asynchronously. This is necessary because some kernel code has to allocate frames without the possibility of old pages being swapped out.
It may be helpful to read some references. One example are chapters 10, 13, and 14 of the Linux Kernel Development book.
The default Linux memory management employs two LRU lists: the active and inactive lists. Frames in both lists are managed by the second-chance LRU approximation algorithm. Frames evicted from the active list go to the inactive list. Frames evicted from the inactive list are free (their contents are pushed out of the memory). Frames in the inactive list may also be promoted into the active list in certain circumstance. In this assignment, you are asked to replace the second-chance LRU approximation algorithm in each list with a two-bit clock algorithm:
try_to_free_pages() is called, frames should be
scanned just as in the stock kernel. Don't try to scan periodically.mm/vmscan.c.
Write a user program that you can use to test your page replacement implementation and compare it against the default page replacement algorithm in Linux. Include in your writeup an explanation of how it works and why it is useful for comparing the page replacement implementations. Describe the experiments you ran and show and explain the measurements you obtained. Explain which algorithm performed better, how much better it performed, and how this is justified based on the respective implementations.
The implementation portion will constitute 60% of the grades while the measurement/comparison/analysis writeup will constitute 40%.