Homework 3

22C:116, Spring 1995

Due Friday Feb. 10, 1995, in class

1. Background: On the VAX-11/780, each page table entry may be marked as either invalid, read-write, or read-only. There is no referenced bit, as required by the clock page replacement algorithm, and the hardware maintains no dirty bit, as required to determine whether a page should be cleaned (written back to disk) before replacement. There are, however, a number of spare bits per page table entry, available for use by the software.

   In addition, each page-table entry has the usual address field; if the page is in main memory, this contains the page-frame number of holding the page. If the page is not in main memory, this can be used as the disk address where the page is stored. Furthermore when a page fault occurs on this machine, the page-fault-service routine can easilty determine what kind of memory access occurred (instruction fetch, operand fetch or operand store).

   The question: How can the page fault service routine maintain a software-implemented referenced bit, and a software-implemented clean-dirty bit? Give your answer by describing the meanings of the software bits you need in the page table entries, plus a mapping function from kind of memory access that caused the page fault and the state (hardware and software) of the page table entry to the new state.

   Hint: The trick involves what are called soft page faults, faults where, despite the fact that the page is actually accessible, the memory management unit causes a page fault when it is time to set the referenced bit and when it is time to set the dirty bit. To cause such a fault, you have to set the hardware state of the page table entry to invalid or read-only when, in fact, the page is actually intended to be valid or writable.

2. Background: In protected mode, the 80286 processor has a segmented virtual address space consisting of up to 64K segments of up to 64K bytes per segment. At any instant, the running program can only address 4 of these segments, the code segment, the stack segment, and the two extra segments. The descriptions of these segments are held in segment descriptor registers in the CPU.

   Operand addresses on 80286 instructions are 16 bits, specifying the byte in the segment. The particular segment being addressed is implied by or explicitly stated in the opcode.

   In addition to the directly addressable segments, each 80286 process has a base segment containing up to 64K segment descriptors, and a special instruction is available for loading one of the 4 segment descriptor registers with any descriptor from the base segment.

   Alternatives: On such an architecture, there are two ways that segment faults could be reported. They could be reported when a reference is made to a byte in a segment with an invalid descriptor, or they could be reported when an attempt is made to load an invalid descriptor from the base segment into a segment register.

   The question: What are the significant differences between these alternatives. Would you expect performance differences? Would you expect implementation problems with one alternative that are solved by the other?

3. Lazy copying was invented to speed up the fork operation on virtual memory UNIX systems. The idea is to share all pages of virtual memory between the parent and child processes until either the parent or child tries to make a change to the shared page. Only at that time is the shared page duplicated.

   a) What hardware support is needed to implement lazy copying (beyond that needed for the basic demand paged virtual memory mechanism)?

   b) Assuming that all reports from the memory management unit to the CPU are delivered to a single trap service routine, outline how this routine would distinguish between a conventional page-fault and a lazy-fork-fault (the latter requires that a page be duplicated).

   c) Outline the response of the trap service routine to a lazy-fork-fault.