COS 111, Fall 1999 - Problem Set 6

The first two questions deal with an operating system that provides a virtual memory system with 1Kilobytes-sized pages. Suppose on this computer system, each byte of memory has an address, and memory addresses are 32 bits long, which I will represent using 8 hexadecimal digits. Each page in virtual memory starts at a byte whose address ends in 10 bits of zero, for example addresses 11111000, 11111400, 11111800, and 11111C00 in hex. The system actually has 16 Megabytes of memory, represented with 32-bit addresses 00000000 through 00FFFFFF (hex). The memory manager of the operating system keeps a table, called a page table with an entry for each page of the virtual memory saying where that page is: the location of its first byte either in physical memory or on disk. A page is always put in 1024 consecutive physical memory locations starting with an address ending in 10 bits of zero or put in a continuous section of disk.

Problem 1
a) How much virtual memory is available in the system described above in bytes? in pages?
b) What is the advantage of placing a page in physical memory so that the first byte is at a physical memory address ending in 10 bits of zero?

Problem 2
Suppose the page table indicates that virtual addresses 10000000 through 10FFFFFF are currently in physical memory, and address F11119F2 is requested by the CPU. Note that this address is on the page that starts with byte F1111800. Describe what the memory manager must do. Show what entries in the page table will change and how. State any assumptions you need to make.

Problem 3
Here is the sorted list of faculty in the Computer Science Department:

                       1  Andrew Appel
                       2  Sanjeev Arora
                       3  David August
                       4  Bernard Chazelle
                       5  Douglas Clark
                       6  Perry Cook
                       7  David Dobkin
                       8  Edward Felten
                       9  Adam Finkelstein
                       10 Thomas Funkhouser
                       11 Brian Kernighan
                       12 Andrea LaPaugh
                       13 Kai Li
                       14 Richard Lipton
                       15 Larry Peterson
                       16 Robert Sedgewick
                       17 Jaswinder Singh
                       18 Mona Singh
                       19 Kenneth Steiglitz
                       20 Robert Tarjan
                       21 Randy Wang
                       22 Kevin Wayne
                       23 Andrew Yao

Problems 4
Brookshear, Chapter Four Review Problem 21 (pp 220).