Programming problems are to be done in your assigned groups using the VM that has been assigned to your group. For all programming problems you will be required to submit source code, a README file documenting your files and code, and a test run of your programs. For source code submissions, you only need to submit new source code files that you created and kernel source code files that you changed. You should clearly indicate your names, email addresses, and assigned group number on your submission. Each group is required to submit one writeup for the programming assignment using the SUBMIT program. Refer to the homework submission page on the class web site for additional submission instructions.
The basic operation of the Linux virtual memory management subsystem Is as follows. A process runs in a virtual address space. Virtual addresses are converted into physical memory addresses by using components of the virtual address as indices into the page directory and page table. This mapping allows the mapping of physical memory into a much larger virtual memory space. This mapping is detailed in the optional textbook "Linux Kernel Internals".
The virtual address space of a process consists of a kernel segment and a user segment. Since the page tables of the kernel segment are identical for all processes, this exercise is concerned only with the memory allocated for the user segment of a process.
In addition to mapping physical memory into a much larger virtual memory space, the indirection provided through the page directories and page tables allows multiple processes to share the specific memory pages. This allows, for example, 2 users to run the /bin/bash program, with both processes referring to the same code pages in physical memory (although data pages would differ). When a process is created (forked), the parent's page directories and tables are copied for the child process. After forking, if either process modifies data, then the pages holding the memory being modified will be copied. You will see this referred to throughout the memory management code as copy-on-write or COW.
When a process begins to execute, not all of the image is pulled into memory. Instead, Linux waits until the process attempts to reference the page in virtual memory. If the page is not in memory, a page fault occurs signalling Linux to bring the page into physical memory and update the process's page tables. To ensure there are physical memory pages available to bring in requested pages, Linux attempts to maintain a minimum of free_pages_low pages of memory. This maintenence is performed by kswapd which we will describe in more detail later.
Another way of looking at this is, when processes are loaded, only a minimal amount of memory is allocated. The scheduler decides which process has the right to run. Once this decision is made, the process's actions will determine how much additional physical memory space it is given. Since physical memory is finite, the memory management system must ensure it can give a process the memory space it needs, when it needs it. The Linux memory management subsystem does this by keeping a pool of free pages. It attempts to maintain this pool by reclaiming pages which it estimates are not being used. This results in physical memory being shared by all loaded processes, but with a very high preference to current working set.
As described earlier, kswapd continuously sweeps memory space to determine which pages are most likely to hold data which is not part of the current working set, and frees those pages by swapping out or discarding their contents. The operation of kswapd is detailed in Chapter 3 of "The Linux Kernel". Kswapd will first attempt to free pages in the buffer and page caches and then proceed to examining the shared memory pages. Finally, it will consider each process. It will iteratively select the process with the most resident memory as a 'victim.' It does not attempt to swap out the entire 'victim' process, but instead looks for pages of that 'victim' which are not being referenced (or at least are not frequently referenced). So for a given process, the space is examined on a page-by-page basis. In a given sweep, kswapd may retrieve enough pages simply by examining the page and buffer caches. If so, then the next time it runs, it will start its sweep where it left off (with the shared memory pages in this example).
For this assignment you will be changing kswapd to use an LRU page replacement algorithm. Since Intel does not provide hardware support for LRU, you will have to keep track of page information in kernel space.
The pte_t structure maintains some information describing
a page. The file include/asm/pgtable.h contains some
routines for manipulating and reading elements of this page
structure.
lru_page_list, that contains pointers to every page held
by every process in the system. This queue should be sorted to
reflect the most recently used pages, which should be at the front.
Since Intel lacks hardware support for page timestamps, you will have
to manipulate this list on every timer interrupt. Every 10ms, you
should update the ordering of pages on the queue based on what pages
have been accessed since the last timer interrupt. There is a
reference bit associated with each page that you can use to determine
what pages have been accessed since the last timer interrupt. All
pages that have been recently used should be moved to the front of the
queue. You should keep track of what processes have run since the
last timer interrupt to avoid having to navigate the entire task list
to compute the page usage of every single process.
lru_page_list data structure,
implement an LRU page-replacement scheme for any processes that have
swappable pages. Your scheme must not swap out pages that kswapd would ordinarily not consider.