CSE 451

Operating Systems

Spring 1998

Quiz #6

Distributed :  5/19/98 (Tuesday)
Due            :  5/21/98 (Thursday -- in the beginning of the Section)

1.  Consider the following page reference stream:

A B R A C A D A B R A

on a machine with 3 physical pages.
Show the sequence of page faults that occur:

  1. when using LRU page replacement
  2. when using FIFO page replacement
  3. when using OPT replacement.
For each of these replacement strategies, compute the effective vitrual address reference time assuming:
  1. time to access a memory location: 10 nanoseconds
  2. time to resolve a page fault: 10 milliseconds
2. Prove that for any given sequence of page references, the Optimal Algorithm produces the least number of page faults. More formally, given a sequence of page references p1, p2, p3, .... pm and a main memory size of N pages, prove that there exists no choice of pages to be paged out, which produces less page faults than the Optimal Algorithm. Note that you could have a sequence of choices for pages to be paged out, which will produce the same number of page faults as the Optimal Algorithm.

3. The VAX doesnot contain a R bit (Reference bit). Describe how you would simulate the R bit using the protection bits ?

4.  There are a number of Multiprocessor systems, with the following hardware configuration. The system consists of a number of independent processors with local memory. Each processor is directly connected to its local memory. Further, the processors can communicate using a high speed network. There is no global main memory. All the processors share all the devices like the disk, terminal etc. It is slower to fetch data from disk than another processor's memory, which is inturn slower than fetching data from the local memory of the processor. Messages on the network are notified using interrupts.

One way of running a multi-threaded program on this multiprocessor is to use a Shared Virtual Memory.  The different threads of the program run on different processors and all of them share a common address space. Communication between the threads is done by reading/writing from a common memory location. Describe how the operating system would implement such a shared virtual address space. Describe what messages need to be sent between the processors and when.

Note: Each of the processors is a normal CPU with a nomal MMU, which we discussed in class.