Kernel programming assignment #5 - Memory Management

Due by Tuesday, December 3rd.

Please use the class discussion board (you can find it on your blackboard) as a communication and Q&A tool.  Should you still need to send an e-mail inquiry, address it to the TA (Xiaowan Dong: xdong at cs...) and cc the instructor. This assignment will be examined through demo with the TA. The demo time should be conducted with the TA by the due date or earlier. We expect that each demo will take 20-30 minutes. Please reserve your time slot with the TA ahead of time.

This is a group assignment. You may form a group of two to complete this assignment. As in prior assignments, please rotate partners (you must have partnered with at least 3 different people).

Disclaimer: This assignment is adapted from a project developed by Dr. Jason Nieh at Columbia University.

Assignment background

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. Therefore, it doesn't take 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.

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 freed (their contents are pushed out of the memory). Frames in the inactive list may also be promoted into the active list in certain circumstances.

It may be helpful to read some references. One example is Chapter 11 of the Linux Kernel Development book (2nd edition). Most (but not all) of the code you'll need to read for this assignment is in mm/vmscan.c.

Assignment description

Part I: report memory management statistics.
In this part, you are asked to collect a number of memory management statistics:

  1. the current number of pages in the active list (over all memory zones);
  2. the current number of pages in the inactive list (over all memory zones);
  3. the current number of pages in the active list whose reference bits are set (over all memory zones);
  4. the current number of pages in the inactive list whose reference bits are set (over all memory zones);
  5. the cumulative number of pages moved from the active list to the inactive list (since the last machine boot);
  6. the cumulative number of pages evicted from the inactive list (since the last machine boot);
Provide a system call that reports these statistics to user level applications.

For each of statistics 3, 4, 5, 6, you should provide a program that triggers a change in the statistics and reason about the change. Taking statistic 6 (the cumulative number of pages evicted from the inactive list) as an example, you should provide a program that triggers additional page evictions from the inactive list so the reported statistics 6 will change after you run the program. It is OK if you use one program to trigger the changes of multiple statistics as long as you can reason about why these changes occurred.

Part II: counter-based clock page replacement.
In this part, you are asked to replace the second-chance LRU approximation algorithm in both the active and inactive lists with a counter-based clock algorithm:

  1. Keep a reference counter for each frame, which is set at 0 initially.
  2. When try_to_free_pages() is called, you scan a frame in the following way. First, you add the reference bit value to the frame reference counter (and clear the reference bit at the same time). Then you check the reference counter. If the counter is 0, you evict the page. Otherwise, you decrement the counter by 1 and move the frame to the back of list (as the original second-chance LRU approximation normally does).
  3. Action #2 (above) alone will result in a replacement algorithm equivalent to the original second-chance LRU approximation. To effectively utilize the reference counter, you need additional counter maintenance at other occasions. To this end, you should scan the frames periodically (e.g., as part of the timer interrupt) and add the reference bit value to the frame reference counter (and clear the reference bit at the same time).
  4. Note that the reference counter may overflow. If the reference counter is already at its maximum value, keep it unchanged when adding the reference bit to it.
Note that we only ask that you replace the existing LRU approximation algorithm in each list with a new one. You can leave the basic Linux two-list memory management in place. Also, you do not need to make any changes to how Linux handles dirty page eviction. If a frame to be freed contains a dirty page, it will have to be swapped out, but this shouldn't affect your decision on which frame to free.

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 explain the measurements you obtained. Explain the different performance of the two algorithms (or the lack thereof) and how this is justified based on the design/implementation of the two algorithms.