Due Date: June 8, 1999
These can be answered in a sentence or two,
and are intended to reinforce important points.
(4 points) What is the difference between segmentation and paging?
(4 points) Consider a logical address space of eight pages of 1024
words each, mapped onto a physical memory of 32 frames.
How many bits are there in the logical address?
In the physical address?
These questions require some thought and longer answers than the
short-answer questions. They are intended to have you use the concepts
discussed in class, to be sure you understand them and can work with
(12 points) A virtual memory has a page size of 1024 words,
eight virtual pages, and four physical page frames.
The page table is as follows:
|virtual page||page frame|
|2||not in main memory|
|3||not in main memory|
|5||not in main memory|
|7||not in main memory
Make a list of all virtual addresses that will cause page faults.
What are the physical addresses for 0, 3728, 1023, 1024, 1025, 4096, and 7800?
- (25 points) Consider the following page reference string:
1 2 3 4 1 5 6 2 1
How many page faults would occur for the following replacement
algorithms, assuming first 4, and then 7 frames? Remember all frames
are initially empty, so your first unique pages will all cost one fault
First In First Out (FIFO)
Optimal (OPT, MIN)
Least Recently Used (LRU)
Not Recently Used, Not Used Recently (NRU, NUR); assume all references to pages 2, 4, and 6 are writes.
- (20 points) Consider a demand paged system with the following time-measured utilizations:
Which (if any) of the following will (probably) improve CPU utilization?
Explain your answer.
|Other I/O devices||5%|
- Install a faster CPU.
- Install a bigger paging disk.
- Increase the degree of multiprogramming.
- Decrease the degree of multiprogramming.
- Install faster, other I/O devices.
- (20 points) Consider the reference string
w = 1234523432442444
Assuming the working set replacement strategy, determine the minimum
window size such that the string generates at most five page faults.
Show which pages are in memory at each reference, as well as which
pages are being brought into, and removed from, memory.
- (15 points) You are the president of Cheapo Computronics,
Inc., and your star hardware designer has suggested a brilliant idea:
Implement segmentation, but let the least significant m bits of a
virtual adress be used to select the segment, and let the other bits
determine the offset. Should the designer retire or get a raise?
- (10 points) Prove that Belady's anomaly
cannot occur in a stack algorithm.
- (15 points) A particular database program repeatedly scans
an array of 1,000 pages. Each scan starts with page 0 and continues to
page 999. There is only enough main store to hold 100 pages. None of
the page replacement policies we discussed does very well. Suggest a
different policy that will do as well as the optimal page replacement
policy OPT for this program.
Send email to
Department of Computer Science
University of California at Davis
Davis, CA 95616-8562
Page last modified on 5/27/99