Description
Problem 1
(9 points) You are given 5 memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600
KB (in order). How would you place the process of 212 KB, 417 KB, 112 KB, and 426 KB
(in order) by using the first-fit, best-fit, and worst-fit algorithms? Which of these algorithms
has the most efficient memory usage? Show your work.
Problem 2
(3+4 points) A system with 30-bit logical (virtual) address uses a two-level page table.
Logical addresses are split into an 8-bit top-level page table field, a 12-bit second-level page
table field, and an offset.
What is the size of a page in this system (assume that the size of a memory location is 1
Byte)? How many pages are there in the address space? Explain the reason.
Problem 3
(9+9 points) Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7,
6, 3, 2, 1, 2, 3, 6. How many page faults would occur for the page replacement algorithms:
LRU, FIFO, Optimal in the following cases? Explain your answer. Remember all frames are
initially empty, so your first unique pages will all cost one fault each.
a) 5 frames are allocated for the process
b) 6 frames are allocated for the process
Problem 4
(6 points) Consider a system that uses pure demand paging to manage memory. Describe
the page fault rate (a) when a process first starts execution, (b) once the working set for a
process is loaded into memory, (c) when a process changes its locality and its new working
set size is larger than the size of free memory.
