Homework 3

22C:116, Spring 1997

Due Friday Feb. 14, 1997, in class

1. Consider a memory management unit which allows TLB entries to be marked as either: Inaccessable, Read-only or Read-write. Consider a page fault service routine such as that discussed in class:

   	page fault service routine:
   	    if reference is to page not in TLB
   		if referenced page is in main memory
   		    soft page fault for TLB update
   		else
   		    select page to replace
   		    if page is dirty, write it to disk
   		    read desired page from disk
   		    update TLB and map
   		endif
   	    else
   		access violation
   	    endif
   	return
   

   Suppose we wanted to expand on this framework with software support for a mark bit indicating that a page has been used and a dirty bit indicating that a page has been written. The TLB entries supported by our MMU do not have any hardware support for these, so we must use soft page faults.

   The problem, Part A: What data must be added to each entry in the page frame table in order to support this.

   The problem, Part B: Present pseudocode that clearly explains how to use your added data to distinguish between real access violations and the soft page faults needed to record changes to the state of a page frame, and that updates the added data to correctly record the fact that a page has been marked or written.

2. The classical discussions of page replacement all assume that there is only one running process. Now, consider the case where there are multiple processes! Assume that all processes share the same address space, and assume that, when a (hard) page fault occurs, only the process that caused that fault is blocked to allow the I/O to complete and the page table to be updated -- other processes may continue.

   The problem, Part A: Now, page faults must be served, in part, by the page-fault service routine, and in part by the disk interrupt service routine when a disk I/O transfer finishes. At a level of pseudocode comparable to that above, outline how the job of page fault service is divided between the page-fault and the disk interrupt service routine. Assume, for the moment, that the disk is used only for page faults and that no other page faults occur before the disk I/O is finished. Note that your pseudocode must include interactions with the scheduler!

   The problem, Part B: What possible mutual exclusion or synchronization problems are raised by the solution you outlined in part A, assuming that some second process may have a page fault while the fault for the first process is being served, and that second fault may involve the same or a different page.

3. Certain pages, such as the pages holding the page fault service routine and the root structures of the page table must be locked into main memory or the system will be unable to service page faults -- this is discussed in Tannenbaum. The page table itself, however, may be so large that it is impossible to fit it entirely in memory. Therefore, it is possible that the page-fault service routine will itself cause a page fault when it tries to access an entry in the page table in order to update the TLB! Assuming that our target architecture allows an interrupt service routine to be interrupted, how can we guarantee that this recursion will terminate with successful handling of all page faults and an eventual return to the user program?

   Big Hint: Tannenbaum, Section 3.3.3.