CSE 120 Homework #3

Fall 2007

1. [Page replacement policies] A computer that has a page size of 1,024 bytes. Consider the following reference string for this computer:
   220, 1054, 2320, 4441, 1220, 2321, 5764, 5944, 3200, 10, 11, 2090

   What are the number of page faults generated for this string when:

   1. The page replacement policy is optimal and there are three page frames.
   2. The page replacement policy is optimal and there are four page frames.
   3. The page replacement policy is LRU and there are three page frames.
   4. The page replacement policy is LRU and there are four page frames.
   5. The page replacement policy is FIFO and there are three page frames.
   6. The page replacement policy is FIFO and there are four page frames.

   For each case, assume that all page frames are vacant when the first address in the reference string is referenced. In addition, indicate which reference results in a page fault.

2. [From last winter's final] Consider the following fragment of a page table:

   page number	frame	valid	permissions	referenced	dirty
   12	40	1	r	1	0
   13	32	0	rx	0	0
   14	1	1	rw	0	0
   15	11	1	rw	0	0
   16	17	1	rx	0	0
   17	6	1	r	0	0

   The valid bit indicates whether or not the page frame listed in the page table entry is, in fact, associated witih the virtual page number.

   The virtual memory system uses Clock with the clock hand scanning the pages in increasing virtual page number order. The hand is currently point to page 15, and this is the page that Clock will consider next when a page frame is needed.

   Assume that the page size (and page frame size) is 100 bytes. Consider the operations given below. They are executed in order. For each operation, indicate what happens. For example, if the operation results in a fault, say what kind of fault it is. If it is a page fault, then say which page frame is used to satisfy the page fault and how the clock hand and page table are updated. If the operatino does not result in a fault, then say which physical address results from the virtual address translation, and say how the page table is updated.

   1. Read virtual address 1280.
   2. Write virtual address 1444.
   3. Write virtual address 1745.
   4. Read virtual address 1310.
   5. Jump to virtual address 1660.

3. [Tanenbaum/Woodhull 4.13] Suppose that a 32-bit virtual address is divided into four fields a, b, c and d. The first three are used for a three-level page table system, and the fourth field d is the offset. Does the number of pages depend on the size of all four fields? If not, which ones matter and which ones do not?

4. [Tanenbaum/Woodhull 4.28] It has been observed that the number of instructions executed between page faults is directly proportional to the number of page frames allocated to a program. If the available memory is doubled, then the mean interval between page faults is also doubled. Suppose that a normal instruction takes 1 microsecond, but if a page fault occurs, it takes 2 milliseconds to handle the fault. If a program takes 60 seconds to run during which time it gets 15,000 page faults, how long would it take to run if twice as much memory were available?

5. [Page fault behavior] Give a reference string that has the following property: both doubling and halving the page size will result in more page faults. Use an LRU page replacement policy. You can choose whatever amount of physical memory and the initial page size you wish when constructing this reference string (hint: choose something small). Show what page faults result in the three cases: original page size, page size doubled, and page size halved.