Homework 4 – Memory Management, Virtual Memory

 Page 1
COMP 3500 Introduction to Operating Systems
Homework 4 – Memory Management, Virtual Memory
Maximum Points Possible: 100
Individual Assignment
Question 1 (3x4 Points = 12 Points):
What are the differences between the following concepts?
a. Logical address and physical address.
b. Contiguous and non-contiguous storage allocation.
c. First-fit placement and best-fit placement.
Question 2 (3x4 Points = 12 Points):
Suppose that we have free partitions with sizes: 6, 17, 25, 14, and 19. Place a program
with size 15kB in a free partition using first-fit, best-fit, next-fit, and worst fit strategies.
Provide the partition selected for placement of program with each strategy.
Question 3 (2x4 Points = 8 Points):
What are the advantages of following?
a. Overlays allocation storage.
b. Compaction.
Question 4 (5x3 Points = 15 Points):
Assume that the memory physical address space is partitioned into 30 frames of size 4
bytes each. Of those, the free frames are 6, 7, 10, 12, 18, 20, 21, 25, 26, and 29. Consider
a user program with logical address space of size 7 pages and page size is 4 bytes. The
user program consists of 26 instructions aa, bb, cc, . . . yy, zz. Each instruction takes 1
byte. Provide the following.
a. Allocate each page of the program to a free frame.
b. Draw the logical / physical mapping.
c. Show page table.
d. Find the physical addresses for the instructions bb, ff, rr, vv.
e. Calculate the fragmentation, if any.
Question 5 (2x4x3 Points = 24 Points):
Consider the following page reference string: 8,7,6,8,5,7,6,4,3. Assume that the process
has been allocated 3 frames and that initially all frames are empty.
1. How many page faults would occur for the two page-replacement algorithms:
(a) OPT (b) LRU
2. For each reference, show the content of the frames.
3. For each algorithm, show which references result in a page fault.
4. Compute the page fault rate for the two approaches, OPT and LRU.
Note: Page fault rate
 Page 2
= Percentage of references which resulted in page faults
= Number of page faults / Number of references * 100.
Question 6 (7x3 Points = 21 Points):
Consider a demand-paging system with the following time-measured utilizations: CPU
utilization (20%), Paging disk (97.7%), and Other I/O devices (5%). For each of the
following, say whether it will (or is likely to) improve CPU utilization. Explain your
answers.
1. Install a faster CPU.
2. Install a bigger paging disk.
3. Increase the degree of multiprogramming.
4. Decrease the degree of multiprogramming.
5. Install more main memory.
6. Install a faster hard disk.
7. Increase the page size.
Question 7 (4 Points):
Consider a system that uses pure demand paging. Characterize the page fault rate of a
process:
1. At the start of execution of the process.
2. After the working set of the process is loaded into memory
Question 8 (4 Points):
Assume a process changes its locality, and the size of the new working set is too large to
be stored into available free memory. Identify some options system designers could
choose from to handle this situation?