Hints for Homework3

There are a number of ways to implement the proportional sharing memory management scheme for homework 3. Some are significantly more difficult than others. The purpose of this note is provide some hints to avoid having you waste time on the more difficult implementations. These are suggestions; you may choose alternative implementations, as long as proportional sharing is achieved.

1. Start by deciding on a metric for determining proportions. The RSS (resident set size) is the number of pages a process has in physical memory. The RSS is stored in the mm_struct of the task_struct of a process. This count may include pages which are shared with other processes. A page is shared among multiple processes if it's count is greater than 1. Therefore, one measure of how much physical memory a process is using is RSS. Another measure would be to attribute 1 page for every unshared page and a fraction of a page if that page is being shared among multiple processes (e.g. if a process had 1 unshared page and 1 shared page with count=4, the process could be attributed 1.25 pages; whereas its RSS value would simply be 2).

   For the purposes of this assignment, either of these metrics is acceptible. If RSS is used to specify the memory attributed to a process, then the proportion of memory allocated to the process would be RSS/total_RSS where total_RSS is the sum of the RSS values of all processes. For the remainder of this discussion we will assume the use of total RSS.

2. Think of the memory mangement scheme as having 2 distinct personalities. On the one hand, whenever a process asks for memory the VMM will seem quite generous, and, as long as there are free pages available, will simply hand over pages to the asking process. On the other hand, kswapd is running in the background, checking whether each process should really have this many pages, and, if not, taking them back. So, it is in kswapd that decisions are made (in our case based on weight) on whether a process will maintain (or loose) physical memory share. Therefore, it is important that you spend some time understanding how kswapd operates (see Chapter 3: Memory Mangement of "The Linux Kernel"). You will change kswapd so it selects a process to victimize (take back pages from), based on the proportions defined in step 1.

3. Now that you know the information required to make a decision (pick a victim) and where to make that decision (kswapd), you need to know how to collect that information. You could track the total weight and total RSSes of all processes as they change (this is what was done for the scheduler in homework 2). However, kswapd does not have the same time-critical nature as the scheduler. Therefore, although homework 2 specified that your solution track the total weight of processes in the run queue (instead of walking the run queue twice within the scheduler),your solution for homework 3 need not continually track the total weight and RSS of processes in the task list (you may add a walk of the task list within kswapd).

4. Although you may traverse the task list to calculate the total weight and RSS, you should note that traversing the task list requires that you lock the task list. You should also note that while kswapd is attempting to take back pages, other processes should be allowed to run (don't just lock the task list for the duration of the swap_out function). Allowing other processes to run means that the total weight and RSS may change. So you will need to think about where these changes could occur. There are many places where the actual value of RSS is changed. However, there are four logical places (other than kswapd) where the decision to change RSS is made.

5. Finally, since the total weight and total RSS will be accessed from various locations, you will need to synchronize access. You should define a single spin lock (spinlock_t) for this purpose. You do not need to block interrupts while the locks are held (i.e., just use spin_lock() and spin_unlock() to acquire and release the lock).