W4118 OPERATING SYSTEMS I

Homework 5 is due 04/14 at 3:09pm EDT

The written problems are to be done individually. The programming problems are to be done in your assigned programming groups. All homework submissions are to be made via Courseworks. Refer to the homework policy section on the class web site for further details.

Written Assignment (40 pts)

Exercise numbers refer to the course textbook, Operating System Concepts. Each problem is worth 4 points.

1. Suppose that a machine has 48-bit virtual addresses and 32-bit physical addresses.
   1. If pages are 4 KB, how many entries are in the page table if it has only a single level?
   2. Suppose this same system has a TLB with 32 entries. Furthermore, suppose that a program contains instructions that fit into one page and it sequentially reads long integer elements from an array that spans thousands of pages. How effective will the TLB be for this case?


2. Consider the following C program:

           int X[N];
           int step = M; // M is some predefined constant
           for(int i=0; i< N; i+=step) X[i] = X[i] + 1;
         

   If this program is run on a machine with a 4-KB page size and 64-entry TLB, what values of M and N will cause a TLB miss for every execution of the loop?


3. Ch 9 Exercise 14


4. Ch 9 Exercise 20


5. Ch 9 Exercise 23


6. Ch 9 Exercise 24


7. Ch 9 Exercise 27


8. Ch 9 Exercise 28


9. Describe how the Linux kernel implements copy-on-write for fork(). Be sure to list the relevant procedures, data structures, and variables; explain the meaning of each.


10. Consider the following two-dimensional array:

              int X[64][64];
              

    Suppose that a system has four page frames and each frame is 128 words (an integer occupies one word). Programs that manipulate the X array fit into exactly one page and always occupy page 0. The data are swapped in and out of the other three frames. The X array is stored in row-major order (i.e., X[0][1] follows X[0][0] in memory). Which of the two code fragments shown below will generate the lowest number of page faults? Explain and compute the total number of page faults.

     
                Fragment A
                for(int j=0; j<64; ++j)
                     for(int i=0; i<64; ++i)
                         X[i][j] = 0;
              

                Fragment B
                for(int i=0; i<64; ++i)
                     for(int j=0; j<64; ++j)
                         X[i][j] = 0;
              

Please complete and submit a private group programming assignment evaluation. The evaluation should be in a separate file called evaluation.txt that is submitted with your individual written assignment submission.

Programming Assignment: Adding a New Page Replacement Policy to Linux (60 pts)

Programming problems are to be done in your assigned groups using copies of the virtual machine (VM) image already provided. 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.

You will build your own Linux kernel for this class. 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. You will base your changes on the 2.6.11 kernel that you installed for Homework 2, but without the modifications you made for the new systems calls you wrote for Homework 2. In particular, submitted kernel patches should be patched against your modified KDB-enabled kernel from Homework 2, i.e. do not include KDB code in your patch.

Description

The assignment is to add a new page replacement algorithm to the Linux kernel.

In systems that support virtual memory, the kernel and hardware cooperate to provide applications the illusion of having fast memory as large as the hard disks. These systems implement virtual memory by exploiting application's locality of memory references: they store in memory the pages an application is likely to access in the near future and leave other pages to hard disk. When a page stored in disk is referenced, however, these systems must make space for the referenced page by removing another page in main memory if no free pages are available.

Linux kernel uses a LRU-based algorithm for page replacement. As we learned in class, no practical page replacement policy suits all workloads. For example, LRU-based algorithms perform badly with repeated scans of data set larger than main memory.

To solve this problem, in this assignment, you will implement a Most-Recently-Used (MRU) page replacement algorithm in Linux, which works best for repeated scans.

You are strongly advised to read Understanding Linux Kernel Chapter 8 Memory Management, Chapter 15 The Page Cache, Chapter 17 Page Frame Reclaiming before starting the programming assignment. Linux uses page cache to denote the memory region for storing pages. The directory mm/ contains majority of code that deals with paging and virtual memory. You will find the struct zone data structure in mmzone.h helpful. In particular, the active_list and inactive_list fields are the key to implement the default Linux page replacement policy.

1. (50 pts.) Design and implement a MRU page replacement algorithm to Linux.

   Add a new system call, long set_cachepolicy(int policy), to Linux kernel. This system call should be numbered 289. The policy argument can be CACHE_NORMAL (the original Linux policy) or CACHE_MRU (our new policy). Note you need to define both CACHE_* macros by yourselves in a header file in the kernel. When this system call is invoked, the kernel should set the page replacementi policy accordingly. To simplify things, the effect of this system call should be global: it affects the page replacement policy of all memory regions and all proccesses. That is, you do not have to implement per-memory-region or per-process policies.

   You should not make any assumptions about whether the system is a uniprocessor or multiprocessor system. Be sure to properly synchronize access to your data structures. Moreover, be sure to select the appropriate synchronization primitives such that they are both correct and efficient, in this order. For instance, you should prefer a spinlock over a semaphore if-and-only-if you don't plan to sleep while holding it.

   You should properly handle errors that may occur and report meaningful error codes. As always, you are encouraged to look for existing kernel code that performs similar tasks and follow the coventions and practices it provides.

2. (10 pts.) Write a testcase that runs faster using MRU than the original Linux page replacement policy.

   Please note that you should measure and report the execution times of your testcase under both MRU and the orignal Linux page replacement policy. If you use a repeated scan workload, you must make the data set larger than the size of the page cache. HINT: The max number of pages that can be stored in the Linux page cache depends on your virtual machine's memory size. We recommend you to change this memory size to 256M or smaller for this homework.

Additional Information