Individual written problems are to be done individually. Group programming problems are to be done in your assigned programming groups. The deadline for group programming problems applies to both CVN and non-CVN students. All homework submissions are to be made via the submit programs. Refer to the homework policy page on the class web site for further details.

Individual Written Problems:

1. Name two differences between logical and physical addresses.

2. Given memory partitions of 500K, 100K, 200K, 400K, and 300K (in order), how would each of the first-fit, best-fit and worst-fit algorithms place processes of 212K, 417K, 112K, and 326K (in order)? Which algorithm makes the most efficient use of memory?

3. Suppose a paging system has 2^(g+h) virtual addresses and uses 2^(h+k) locations in primary memory. Wath is the page size of the system that is implied by the virtual and physical address sizes? How many bits are required to store a virtual address?

4. A certain computer provides its users with a virtual memory space of 2^32 bytes. The computer has 2^18 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4096 bytes. A user process generates the virtual address 1234567. List the steps that the system goes through to establish the corresponding physical location. Distinguish between software and hardware operations.

5. Suppose we have a demand-paged memory. The page table is held in registers. It takes 8 ms to service a page fault if an empty frame is available or the replaced page is not modified, and 20 ms if the replaced page is modified. Memory access time is 100 ns. Assume that the page to be replaced is modified 70 percent of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 ns?

6. Exercise 9.16

7. Exercise 10.6

8. Exercise 10.11

9. Exercise 10.13

10. Exercise 10.18

Group Programming Problems:

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. In addition, you should submit a cover sheet using either homework_work.txt or homework_nonwork.txt, depending on whether or not the programming assignment is completely working or not. 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.

The image of the kernel you build for this assignment should be vmlinuz.hmwk5. Grading for this assignment will be done based on vmlinuz.hmwk5. The kernel you use for this assignment should be the Linux 2.4.2 kernel you built and installed as part of Homework #2.

Background

The purpose of this assignment is to gain better understanding of Linux's virtual memory management subsystem, to extend this subsystem with new memory management policies, and to evaluate your implementation.

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 Linux reference textbook "Understanding the Linux Kernel".

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 at least some minimum number of free pages of memory. This maintainence is performed by kswapd, which 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.

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.

Now we get to the fun part!

1. (10 pts) Describe how to extend the Linux memory management system to proportionally share physical memory space among processes. Your explanation should include details of what and how specific functions need to be modified. The proportion given to a process should be based on a weight assigned to that process. Valid weights are in the range 1-5, with 5 receiving the largest proportion. If a weight is not assigned to a process, a default weight of 3 should be used.

   Your management scheme need not enforce proportional sharing when physical memory is not constrained. For example, suppose only 2 processes with the following properties are running:

   	Process		Memory Requirements		Weight
   	   A			20MB			  1
   	   B			12MB			  3
   

   If the system has 64MB of available physical memory, then process A and process B should receive 20MB and 12MB respectively. If however, the system has only 16MB of available physical memory, then process A should receive only 4MB and process B should receive 12MB.

2. (25 pts) Implement the proportional memory management scheme described in part 1.

   You may extend the task_struct to include a weight field, but be sure to make it the last field of the task_struct and to update the hard coded definition of the init task to reflect the change. You will need to add a system call to set this value for a process. The prototype for this call should be:

   	int set_weight(int weight)
   

   You should implement set_weight() by updating the syscall table (as you did for pinfo) and use the __syscall1() macro to invoke it. The return value is 0 if successful and -1 if not. The only cause for a -1 return code is an invalid weight.

3. (10 pts) Write a simple program which incrementally allocates and touches memory to test your policy. Your test program should account for the fact that if memory is not touched, physical memory space may not be allocated. And if this memory is not being referenced, the physical memory space allocated for this data may be freed. Test your implementation by writing a control script or program that runs 5 different copies of the test program concurrently, with respective weights 1, 2, 3, 4, 5.

4. (15 pts) Show that the physical memory space allocated to each process is in proportion to its weight. Since utilities such as rusage may not provide the detail you require, you should extend your pinfo system call to include the amount resident memory your program has allocated. You may use your own code for the basis of pinfo system call, or the code posted in the solutions for Homework 2.

   For your final report, use statistics collected by a small program utilizing your extended pinfo system call to retrieve the resident memory allocation of each of your weighted test processes at 1 second intervals. Plot the resident space allocated for each of the 5 processes over a period of at least 20 sample points. Your writeup must describe how the statistics and graph verify that proportional sharing has been achieved.