Department of Electrical Engineering

Max Marks: 15                       EEL 602, Operating Systems

1. Suppose we have a demand-paged memory. The page table is held in registers. It takes 8 milliseconds to service a page fault if an empty frame is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified. Memory access time is 100 nanoseconds.

Assume that the page to be replaced is modified 70 percent of time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?                                                                                                                                                                                                                                                                                     [4]

 Find the effective access time (EAT) for a given page-fault rate (p) - Can solve the following equation:

        EAT = (1-p)*(100) + (p) * (100+(1-0.7) * (8msec) + (0.7)*(20msec))

                = 100 -100p + 100p + (2.4e6) *p + (14e6)*p

       200 = 100 + (16.4e6)*p

       p = 100/16.4e6

        Many of you did not account for this '100' and marks were therefore debited.

2. (a) Consider a demand paging system with four physical memory frames and the following reference string over seven pages:                                                          [3]

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6

Assuming that memory starts empty, how many page faults will occur and what will be the final contents of memory under the FIFO page replacement policy?

Clearly Circle your answers.

 1, 3, 6, 7 in memory and 11 page faults

(b) Answer the problem of part (a) for the LRU policy.

Clearly circle your answers.

             2, 3, 6, 7 in memory and 9 page faults

(c) Answer the problem of part (a) for the OPTIMAL policy.

Clearly circle your answers.

             Several valid answers for contents -- 6, plus any 3 of 1, 2, 3, 7, is possible

             7 page faults

      Many of you ignoring the first four page faults and missed the correct number. 

3. Consider the following snapshot of a system. There are no current outstanding queued

unsatisfied requests.

A request from p3 arrives for (0, 1, 0, 0). In what state (deadlocked, safe, unsafe) would immediately granting the whole request leave the system? Which processes, if any, are or may become deadlocked if this whole request is granted immediately?                          [2]

Firstly, we require still need matrix as follows;

Change available to (2, 0, 0, 0) and p3’s row of “still needs” to (6, 5, 2, 2). Now p1, p4, and p5 can finish, but with available now (4, 6, 9, 8) neither p2 nor p3’s “still

needs” can be satisfied. So, it is not safe to grant p3’s request. Correct answer - state is unsafe as the system may or may not deadlock. Processes p2 and p3 may deadlock

Above question/solution looks fine?

2. Consider a multi-level memory management using the following virtual addresses: 

Each virtual address has 2 bits of virtual segment #, 8 bits of virtual page #, and 12 bits of offset. Page table entries are 8 bits. All values are in hexadecimal.

Translate the following virtual addresses into physical addresses:                                           [6]

(+ 1 marks a piece, -0.5 for every incorrect answer!)