Assignment 7, due Mar 28

Always, on every assignment, please write your name legibly as it appears on your University ID and on the class list! All assignments will be due at the start of class on the day indicated (usually a Friday). The only exceptions to this rule will be by advance arrangement unless there is what insurance companies call "an act of God" - something outside your control. Homework must be turned in on paper and in class! Late work may be turned in to the teaching assistant's mailbox, but see the late work policy. Never push late work under someone's door!

1. Background: The data structures for a virtual memory system typically involve a page table mapping virtual page numbers to physical frame numbers, and a frame table, mapping frame numbers back to page numbers. You might think that one of these tables, alone, would suffice, since the contents of each table can be computed from the other.

   a) Assume that there is only a frame table. At what point (or points) is it necessary to search the frame table, and what system component (hardware or software) is obligated to perform this search. (0.5 points)

   b) Assume that there is only a page table. At what point (or points) is it necessary to search the page table, and what system component (hardware or software) is obligated to perform this search. (0.5 points)

2. Background: Consider a machine where each page table entry has the following fields:
   • frame number - big enough to address all frames of physical memory
   • access rights - 3 bits, corresponding to read-write-execute
   • spare - 3 bits, available for arbitrary use by software

   The frame number and access rights fields are used by the MMU. The MMU has no knowledge of any segment table, although you can assume that the software maintains a frame table.

   a) We would like to use this system with the clock page-replacement algorithm. The problem is, the MMU does not have a mechanism to set the mark bit on each page frame (or rather, on the frame-table entry for each page frame) each time it is referenced by a running program. Therefore, we have to use software, specifically the page-fault service routine, to set the mark bit.

   Outline the structure of a page-fault service routine that will do this. You may abbreviate the part of the new service routine that does conventional page-fault handling by calling it the conventional page-fault service part of the new routine.

   Hint: You don't need to set the mark bit each time a page is referenced, only on the first reference after the mark has been reset. You can use access rights to force a trap even if the page is actually in memory. You can use the spare field in the page-table entry to hold the real access rights for the page, so only if the spare field equals the access-rights field is this page fault a real page fault. (0.5 points)

   b) When the decision is made to replace the page in some frame, we would like to avoid copying that frame back to disk, but the MMU does not have a mechanism to set the dirty bit on each page frame whenever a write to that frame is allowed.

   Suggest how your solution to part a) can be modified to also set the dirty bit on a page frame when that frame is first modified. (0.5 points)

3. Background: Suppose we had a machine with 64-bit addressing, and we decided to integrate the virtual memory system of the operating system of that machine with the file system. One possible way to integrate these is to treat the 64-bit virtual address as the concatenation of a 32-bit i-node number with a 32-bit address of a byte in the file.

   Obviously, this virtual address space is larger than either the main memory (probably under a few gigabytes) and far larger than the backing storage (probably disk, and probably under a few terabytes). It is extremely unlikely that the backing storage will be 16 exabytes (giga-gigabytes, the size of the virtual address space).

   a) Given that programs use position independent or self-relocating jumps for all internal control transfers, how do you load and run a program on this system? (0.2 points)

   b) In theory, a program could manipulate a file by simply referencing memory at an address in the range for that file. Why would users still want to have an open command. (0.2 points)

   c) Suppose a program tries to read from address X in memory. Enumerate and briefly explain the different reasons that this read operation might fail, that is, reasons the page-fault-trap interrupt service routine might have to raise an exception in the application program (one can imagine that each of these reasons might lead to a different exception).

   d) For a 32-bit machine, there is something "magic" about dividing virtual addresses into 12 bits of byte-in-page, 10 bits of page-in-segment, and 10 bits for the segment number. This is because 1024 32-bit page-table or segment-table entries fit perfectly in one 4096-bit page of memory. Give a reasonably natural division for 64-bit virtual addresses, making reasonable assumptions about the page-table-entry size. (Hint, it is not as "magic" as the division of a 32-bit address space.) (0.2 points)

   e) What about the user's stack and heap? Suggest how these might look if we unified the concepts of file system and virtual memory. (0.2 points)