- Nachos VM Worksheet
- Chapter 8: 8.9, 8.12
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?
- Chapter 9: 9.10
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|
|s2| = |w| and |s1|
= n - |p| - |w|
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.
- [Java Monitors] As additional practice with monitors, the final
problem will be solving one of the midterm synchronization problems
using Java monitors.
A group of students are studying for the CSE 120 midterm. The
students can study only while eating pizza. If a student finds that
the pizza is gone, the student waits until another pizza arrives. The
first student to discover that the group is out of pizza phones
Leucadia Pizzeria to order another Meat Combo pizza and then waits for
the pizza to arrive. Each pizza has S slices.
Implement GetSlice and DeliverPizza methods to properly
synchronize student threads and the pizza delivery thread using Java
monitor mechanisms (Wait and Notify/NotifyAll). Your solution should
be in the form of a Java class that compiles and runs. Your solution
should avoid deadlock and phone Leucaida (i.e., wake up the delivery
thread) exactly once each time a pizza is exhausted. No piece of
pizza may be consumed by more than one student.
Below are five Java files to help you with the implementation.
Your job is to implement the guts of the monitor in the fourth file,
PizzaMonitor.java. The fifth file, BSem.java, is an example
program showing how to use notify and wait.
- First, here's the top level program, StudyGroup.java. It's the most complex of
the lot. When you run it, you supply as arguments the number of
slices per pizza and the list of student names, e.g.:
java StudyGroup 8 Amako Byun Cheyenne Dmitrii Eija
When you test your program, try it both with more slices per pizza
than students (like above) and more students than slices per pizza.
- Next is the life of a studying student, Student.java. Note that this extends Thread.
When the "start" method on an object of this class is invoked, the
thread starts running by executing the method "run".
- And then the pizzeria, Luecadia.java.
It is also a thread.
- Here's the monitor that you will implement, PizzaMonitor.java. It has two entry
methods; one for students and one for pizzerias. Note that this
monitor does nothing; you need to add the variables and the code for
the two methods. This file is the one that you will modify to solve
- Finally, here is an example program, BSem.java, that shows the use of notify and wait