CSE 451

Operating Systems

Spring 1998

Quiz #6 : Solution 

1. (5 points)

2. (not graded)

3. (4 points)

There should be an array of R bits somewhere in the operating system. To clear the simulated R bit for a page, clear all the protection bits. (Save the original protection bits in some OS data structure). When the page is referenced, there will be a protection violation exception. The exception handler should restore the original protection bits, set the R bit in the OS and restart the instruction. Any page replacement algorithm can look at the array R bits for reference information. Note that this is slower than having a hardware R bit because the exception handler has to be executed.
 

4. (6 points)

The shared virtual address space enables the threads running on different processors to run as if they were running on a single processor system. So each thread, irrespective of where they are running, have access to the full virtual address space. The following describes how this might be implemented by the OS using the mechanisms provided by the MMU of a normal processor.

We can think of the local physical memories of each processor to be a cache of the pages on disk. The shared virtual address space is stored on disk. When a processor accesses a page, a page fault occurs and the page is brought into the processor's local memory. Since more than one processor may access the same virtual page, we need some kind of cache coherency mechanism. Here is how it works:
 

  1. Each processor has a page table for the shared virtual address space in its local memory. Each processor has the code of the OS also in its local memory.
  2. Initially all the entries are marked invalid in the page table.
  3. When a page fault occurs, the page fault handler broadcasts a message on the network to see if the page is available in the local memory of some other processor. If it is the page is brought in and the faulting instruction restarted. Otherwise the page is brought in from disk.
The above algorithm doesnot take care of consistency. For example if two processors write to the same virtual page, they might actually be writing to two different local physical pages. So what each processor sees after the write is different. To give the illusion to each thread that they are running on a single processor, we need to make sure that both the processors see the same data. So we make the following modifications.

The algorithm consists of many parts:

On a page fault on processor P1, the following handler is executed:

  1. if it is a read fault:
    1. See if any processor has a copy of this virtual page.
    2. If another processor, P2, has a copy, get a copy of the virtual page from P2. Ask all the processors having the page (including P2) to mark the page read-only in theiri local memories. Get the page a mark it read-only.
    3. If nobody has a copy of the page, read it from disk and mark it read-only.
  2. if it is a write fault:
    1. If the page is in the local memory of P1 with read-only permissions, then ask all processors to make their copes of the virtual page invalid (turn the valid bit off for the page in their page tables), set the read-write bit for the page in P1 and restart the faulting instruction.
    2. If P1 doesnot have a copy of the page and another processor, P2, has a copy, then get a copy of the virtual page from P2. Ask all the processors to invalidate their copies of the page. Set the read-write bit for the page in P1 and continue.
    3. If P1 doesnot have a copy of the page and other processors don't have copies of the page, then get the page from disk, set the read-write bit on and restart the faulting instruction.
When a page needs to be paged out, it is written to the disk if it is dirty, just as in a normal paging scheme.
Other processors respond to P1 in their interrupt handlers for network messages. This same algorithm is run on all the processors.

The algorithm is such that at any point of time, a page can be in one of the following states:

  1. It can be on disk only.
  2. It can be in exactly one processor's local memory with read-write permissions set.
  3. It can be in more than one processors local memories with read-only permission.
The above conditions make sure that all threads have a consistent view of the shared virtual memory pages.