cmsc 412 f98        Exam 2        name:

Total points 30. Total time 75 mins. 4 problems over 3 pages. No book, no notes, no calculator.

1. [6 pts]  A process has a page table of 2K entries and has 4 physical pages allocated to it. The physical pages are initially empty, and the process generates the following page reference string:

            128,   12,   3,   14,   128,   8,   3,   12,   14,    8,    15

a.

For LRU replacement, state the number of page faults and the final contents of the four physical pages.

b.

For FIFO replacement, state the number of page faults and the final contents of the four physical pages.

c.

What is the least number of page faults possible, and why?

2. [4 pts]  Consider a Unix file system using index-nodes (inodes). Assume one file block per disk block. Assume that main memory contains the disk address of the root's inode. Assume that every directory in the file system has at most 6 entries (an entry is a file or another directory). List the sequence of disk blocks needed to be accessed to determine the owner of the file /b/c/d ?

3. [10 pts]  Consider demand-paging with virtual address space of 16 M words, physical memory of 1 M words, page size of 4 K words, FIFO page replacement, and an associative map of 4 entries using FIFO replacement.

a.

Give the organization (format, field labels, widths) of the following:
virtual address,   physical address,   page map table,   associative map.

b.

Assume the CPU starts executing a process whose virtual page i is mapped to physical page i+4. Assume the associative map is initially empty and the process generates the following sequence of addresses (in HEX):

 020FE6
 0231FD
 0322A0
 0AF570
 0AF231
 0231FD
 01FFFF
 0AF570

Describe the contents of the associative map at the end (in HEX).

4. [10 pts]  Below are the arrival and service times in ms of four jobs. Service times are known to the scheduler.

       arrival   service
   J1      0       11
   J2      2        5
   J3      3        9
   J4      7       10

Determine the response time of each job, the time at which the system becomes empty, and the average number of jobs in the system over the time interval [0, 40], for each of the following disciplines:

a.

FCFS

b.

SRPT (i.e. Shortest Job First Preemptive)