- Nachos VM Worksheet
(8.9) Consider a paging system with the page table stored
a. If a memory reference takes 200 nanoseconds, how long
does a paged memory reference take?
b. If we add TLBs, and 75 percent of all page-table
references are found in the TLBs, what is the effective memory
reference time? (Assume that finding a page-table entry in the TLBs
takes zero time, if the entry is there.)
- (8.12) Consider the following segment table:
What are the physical addresses for the following logical addresses?
- (9.10) Consider a demand-paging system with the following
CPU utilization: 20%
Paging disk: 97.7% (demand, not storage)
Other I/O devices: 5%
For each of the following, say whether it will (or is likely to)
improve CPU utilization. Briefly explain your answers.
a. Install a faster CPU
b. Install a bigger paging disk
c. Increase the degree of multiprogramming
d. Decrease the degree of multiprogramming
e. Install more main memory
f. Install a faster hard disk, or multiple controllers with multiple hard disks
g. Add prepaging to the page-fetch algorithms
h. Increase the page size
- Consider the following information about a virtual memory system
that employs both paging and segmentation.
Let |s1|, |s2|,
|p| and |w| denote the length, in bits, of each of the four
address components. Hence, n = |s1| + |s2|
+ |p| + |w|.
- The word size is 32 bits.
- The page and segment table entries each occupy one word.
- The page size is 512 words.
- A page table occupies at most one page.
- A virtual address is n bits long and is a
reference to a word. It has the form (s1, s2,
What is the value of |w|?
What is the maximum number of pages per segment and
what is the corresponding value of |p|?
Using the determined values of |w| and |p|,
which of the following is choices for |s1| and |s2|
|s1| = |w| and
|s2| = n - |p| - |w| - |s1|
|s2| = |w| and |s1|
= n - |p| - |w| - |s2|
Would either choice result in a larger virtual
address space? Explain.
- If a large number of programs is kept in main memory, then there is
almost always another ready program when a page fault occurs. Thus,
CPU utilization is kept high. If, however, we allocate a large memory
space to each of a few programs, then each program produces a smaller
number of page faults. Thus, CPU utilization is kept high.
Are these two arguments correct? Which policy, if either, should be
- [Crowley] Suppose we have an average of one page fault every
20,000,000 instructions, a normal instruction takes 2 nanoseconds, and
a page fault causes the instruction to take an additional 10
milliseconds. What is the average instruction time, taking page
faults into account? Redo the calculation assuming that a normal
instruction takes 1 nanosecond instead of 2 nanoseconds.
- [Crowley] Suppose we have a computer system with a 44-bit
virtual address, page size of 64K, and 4 bytes per page table
- How many pages are in the virtual address space?
- Suppose we use two-level paging and arrange for all page tables
to fit into a single page frame. How will the bits of the address
be divided up?
- Suppose we have a 4 GB program such that the entire program
and all necessary page tables (using two-level pages from above)
are in memory. (Note: It will be a lot of memory.)
How much memory, in page frames, is used by the program,
including its page tables?
- [Tanenbaum] If FIFO page replacement is used with four page
frames and eight pages, how many page faults will occur with the
reference string 0172327103 if the four frames are initially empty?
Now repeat this problem for LRU.