[SOLVED] VMProcess VMKernel Project 3

In project 2, each process had a page table that was initialized with physical pages and their contents when the process was created. In project 3, you will be implementing a more sophisticated memory management system where physical pages are allocated on demand and pages that cannot fit in physical memory will be stored on disk.

You will implement and debug virtual memory in two steps. First, you will implement demand paging using page faults to dynamically initialize process virtual pages on demand, rather than initializing page

exec

frames for each process in advance at time as you did in project 2. Next, you will implement

page replacement, enabling your kernel to evict a virtual page from memory to free up a physical page frame to satisfy a page fault. Demand paging and page replacement together allow your kernel to “overbook” memory by executing more processes than would fit in machine memory at any one time, using page faults to multiplex the available physical page frames among the larger number of process virtual pages. When implemented correctly, virtual memory is undetectable to user programs unless they monitor their own performance.

You project will implement the following functionality:

1. . Pages will be in physical memory only as needed. When no physical pages are free, it is necessary to free pages, possibly evicting pages to swap.

2. . To fulfill the spirit of demand paging, processes should load no pages when started, and depend on demand paging to provide even the first instruction they execute. When you are

   

   loadSections

done, will not allocate even a single page.

1. . At times it will be necessary to “pin” a page in memory, making it temporarily impossible to evict.

vm

The changes you make to Nachos will be in these two files in the

VMProcess.java

— an extension of UserKernel

UserProcess	. Try to depend
	readVirtualMemory

— an extension of UserProcess

directory:

UserKernel

You will notice that these classes inherit from

and

on the

implementation of your base classes as much as possible. Note that, with and

, very little code needs to know the details of virtual addressing. For example,

read

you should not have to change any of the primary code which serviced the syscall. That said, you

nachos

proj2

should not change the base classes in any way that makes them dependent on project 3. It should still

be possible to run

from the

subdirectory to run user-level programs.

proj3

You will compile and run the project in the directory. Unlike the first two projects, you will not

need to learn any new Nachos modules and will continue to use functionality that you became familiar with in project 2. Before starting your implementation, also see the Tips section below.

Central to this project are the following design aspects:

1. You will extend your kernel’s handling of the page tables to use three special bits in each TranslationEntry (TE):

   Valid bit: Nachos will set or clear the valid bit in each TE to tell the CPU which virtual pages are resident in memory (a valid translation) and which are not resident (an invalid translation). If a user process references an address for which the TE is marked invalid, then the CPU raises a page fault exception and transfers control to the Nachos exception handler.

   Used bit: The CPU sets the used bit (aka reference bit) in the TE to pass information to Nachos about page access patterns. If a virtual page is referenced by a process, the machine sets the corresponding TE reference bit to inform the kernel that the page is active. Once set, the reference bit remains set until the kernel clears it.

   Dirty bit: The CPU sets the dirty bit in the TE whenever a process executes a store (write) to the corresponding virtual page. This step informs the kernel that the page is dirty; if the kernel evicts the page from memory, then it must first “clean” the page by writing its contents to disk. Once set, the dirty bit remains set until the kernel clears it.

   StubFileSystem

2. To manage swapped out pages on disk, use the (via

   ThreadedKernel.fileSystem

) as in project 2. There are many design choices, but we suggest using a single, global swap file across all processes. This file should last the lifetime of your kernel, and be properly deleted upon Nachos termination. Be sure to choose a reasonably unique file name.

When designing the swap file, keep in mind that the units of swap are pages. Thus you should try to conserve disk space using the same techniques applied in virtual memory: if you end up having gaps in your swap space (which will necessarily occur with a global swap file upon program termination), try to fill them. As with physical memory in project 2, a global free list works well. You can assume that the swap file can grow arbitrarily, and that there should not be any read/write errors. Assert if there are.

1. In addition to tracking free pages (which may be managed as in project 2), there are now two additional pieces of memory information of relevance to all processes: which pages are pinned, and which process owns which pages. The former is necessary to prevent the eviction of certain “sensitive” pages. The latter is necessary to managing eviction of pages. There are many approaches to solving this problem, but we suggest using a global inverted page table (see the tips below).

   

   writeVirtualMemory

COFF

1. When your code is using a physical page for system calls (e.g., in

   readVirtualMemory or

   ) or I/O (e.g., reading from the

   file or

   the swap file), you will need to “pin” the physical page while you are using it. Consider the following actions:

   read

   1. Process A is executing the program at user-level and invokes the system call.

   2. Process A enters the kernel, and is part way through writing to user memory.

   3. A timer interrupt triggers a context switch, entering process B.

      read

   4. Process B immediately generates numerous page faults, which in turn cause pages to be evicted from other processes, including some used by process A.

   5. Eventually, process A is scheduled to run again, and continues handling the as before.

syscall

In this example, the page to which A is writing should be pinned in memory so that it is not chosen for page eviction. Otherwise, if process B evicted the page, then when process A was rescheduled it would accidentally write over the page B loaded. Just use another data structure to keep track of which pages are pinned.

1. (30%) Implement demand paging. In this first part, you will continue to preallocate a physical page

   exec

   exec

   frame for each virtual page of each newly created process at before, for now continue to return an error from the

   time, just as in project 2. And as system call if there are not enough free

   page frames to hold the process’ new address space. You will not yet need to implement the swap file, page replacement, page pinning, an inverted page table, etc. Instead, you just need to make the following changes:

   VMProcess.loadSections

1. 1. In , initialize all of the TranslationEntries as . This will cause

      the machine to trigger a page fault exception when the process accesses a page. Also do not initialize the page by, e.g., loading from the COFF file. Instead, you will do this on demand when

      loadSections

the process causes a page fault. As a result, will continue to allocate physical

page frames in the page table for each virtual page, but delay loading the frames with content until they are actually referenced by the process.

1. 1. Handle page fault exceptions in . When the process references

      an invalid page, the machine will raise a page fault exception (if a page is marked valid, no fault is generated). Modify your exception handler to catch this exception and handle it by preparing the requested page on demand.

   2. Add a method to prepare the requested page on demand. Note that faults on different pages are handled in different ways. A fault on a code page should read the corresponding code page from

      COFF

      COFF

      the file, a fault on a data page should read the corresponding data page from the

      file, and a fault on a stack page or arguments page should zero-fill the frame.

      COFF

      For this step, for reference look at the file loading code from

      UserProcess.loadSections

from project 2. If the process faults on page 0, for example, then load the first page of code from the executable file into it. More generally, when you handle a page fault you will use the value of the faulting address to determine how to initialize that page: if the faulting address is in the code segment, then you will be loading a code page; if the address is in the data segment, then load the appropriate data page; if it is any other page, zero-fill it. It is fine

COFF

to loop through the sections of the file until you find the approprate section and page to

COFF

use (assuming it is in the file).

Once you have paged in the faulted page, mark the TranslationEntry as . Then let the machine restart execution of the user program at the faulting instruction: return from the exception, but do not increment the PC (as is done when handling a system call) so that the machine will re-execute the faulting instruction. If you set up the page (by initializing it) and page table (by setting the valid bit) correctly, then the instruction will execute correctly and the process will continue on its way, none the wiser.

1. 1. Update

      and

      to handle invalid pages and page

      faults. Both methods directly access physical memory to read/write data between user-level virtual address spaces and the Nachos kernel. These methods will now need to check to see if the virtual page is valid. If it is valid, it can use the physical page as before. If the page is not valid, then it will need to fault the page in as with any other page fault.

      As long as there is enough physical memory to fully load a program, then you should be able to use test programs from project 2 to test this part of project 3. See the tips in the Testing section below

      write10

      for how you can control (increase or decrease) the number of physical pages (e.g., is going to

      swap4

      swap5

      exit

      need more than the default of 16 pages). If you give Nachos enough physical pages, you can even run

      the

      and

      tests (and these tests do not use any system calls other than ).

2. (70%) Now implement demand paged virtual memory with page replacement. In this second part, not only do you delay initializing pages, but now you delay the allocation of physical page frames until a process actually references a virtual page that is not already loaded in memory.

   VMProcess.loadSections

1. 1. In part one for , you allocated physical pages for each virtual page,

      but you marked them as invalid so that they would be initialized on a page fault. Now change

      VMProcess.loadSections

so that it does not even allocate a physical page. Instead, merely mark all the TranslationEntries as invalid.

1. 1. Extend your page fault exception handler to allocate a page frame on-the-fly when a page fault occurs. In part one, you just initialized the contents of the virtual page when a page fault occurred. In this part, now allocate a physical page for the virtual page and use your code from part 1 above to initialize it, mark the TranslationEntry as valid, and return from the exception.

You can get the above two changes working without having page replacement implemented for the case where you run a single program that does not consume all of physical memory. Before moving on, be sure that the two changes above work for a single program that fits into memory.

Now implement page replacement to free up a physical page frame to handle page faults:

1. Extend your page fault exception handler to evict pages once physical memory becomes full. First, you will need to select a victim page to evict from memory. Your page eviction strategy should be the clock algorithm. Then mark the TranslationEntry for that page as invalid.

2. Evict the victim page. If the page is clean (i.e., not dirty), then the page can be used immediately; you can always recover the contents of the page from disk. If the page is dirty, though, the kernel must save the page contents in the swap file on disk.

3. Read in the contents of the faulted page either from the executable file or from swap (see below).

4. Implement the swap file for storing pages evicted from physical memory. You will want to implement methods to create a swap file, write pages from memory to swap (for page out), read from swap to memory (for page in), etc.

As you implement the above operations, keep the following points in mind:

As in the first part of the project, the first time a page is touched it needs to be initialized (e.g., from the executable file for code and data). If this page is subsequently evicted to swap, it will be read from there on further page faults. To be concrete, consider a page used for data. On the first access (fault) on that page, you will read that page in from the executable file. Assume the process dirties the page. When this page gets evicted, you should write it to the swap. If the process faults on the page again, you should read the page in from the swap, not from the executable file (the executable file contains the initial version of the page, the swap contains the most recent version of the page).

When running multiple processes, the page replacement algorithm may select a victim page to evict from another process. As a result, you will need to update the TranslationEntry in the page table for that process, not the faulting one.

and will need to pin memory. It is possible that

a process needs a page, but not only are all pages in use (meaning an eviction must occur), but all pages are pinned (meaning an eviction must not occur now ). Handle this situation using synchronization. If process A needs to evict a page, but all pages are pinned, block A. When another process unpins a page, it can unblock A. In terms of prioritizing, implement this functionality towards the end after you have general page replacement working.

COFF COFF

Finally, you should only do as many page reads and writes as necessary to execute the program, and as dictated by the page replacement algorithm. You will soon discover that the first page fault is different than subsequent ones on a particular page. As described above, on the first fault on a page you need to read from the executable file, and on the second you may need to read from swap. Your implementation needs to be able to handle this situation. In short:

COFF COFF

Read-only Read/write

sections originate in the sections originate in the

file, and should never appear in swap.

file, but may need to enter swap if modified.

COFF

Other pages should be zero-initialized, and are never read from the file.

Read Ryan Huang’s tips for project 3.

There are many potential race conditions in this project because multiple processes are accessing shared data structures. We suggest using a coarse-grained lock to protect the data structures. This will only be necessary once you start working with multiple processes, and do not worry about it until after you have page replacement working with a single process whose virtual address space exceeds physical memory.

proj2

Occasionally check to make sure that you can still run project 2 from the subdirectory.

Here are a couple of example test programs you can use to get started on testing your implementation:

swap4.c: Initialize and read a large array

swap5.c: Initialize, read, and modify a large array

exec

Begin testing with a running program that does not use . When you start implementing

swapping, you can control the number of pages (and thus, indirectly, the necessity to swap) with

-m

nachos

proj3

the paramater to :

or by modifying

in the

subdirectory. Your implementation should not

depend upon any particular number of physical pages, but we will always test with at least four physical pages.

Implement a method to print memory state, and use it liberally when hunting for errors.

and will also continue to be helpful.

As with the earlier projects, you do not have to do anything special to submit your project. We will use a snapshot of your Nachos implementation in your github repository as it exists at the deadline, and grade that version. (Even if you have made changes to your repo after the deadline, that’s ok, we will use a snapshot of your code at the deadline.)

As a final step, create a file named README in the proj3 directory. The README file should list the members of your group and provide a short description of what code you wrote, how well it worked, how you tested your code, and how each group member contributed to the project. The goal is to make it easier for us to understand what you did as we grade your project in case there is a problem with your code, not to burden you with a lot more work. Do not agonize over wording. It does not have to be poetic, but it should be informative.

You can discuss concepts with students in other groups, but do not cheat when implementing your project. Cheating includes copying code from someone else’s implementation, or copying code from an implementation found on the Internet. See the main project page for more information.

We will manually check and also run code plagiarism tools on submissions and multiple Internet distributions (if you can find it, so can we).