Section Notes - 2/20/03

 Section Outline:
 - short (ungraded) quiz
 - page replacement
 - disk performance


 Quiz

1.   The following code is intended to be compiled and then placed in a library.  Is it thread-safe?  That is, if a multi-threaded application contains unsynchronized calls to this routine, is the sequence of results returned guaranteed to correspond to a sequence that could be generated by some set of calls issued sequentially (one at a time)?  If so, argue informally but convincingly that it is.  If not, modify it to make it thread-safe (you can use a mutex, re-arrange code, etc).

unsigned int total;
unsigned int grandTotal = -1;

unsigned int MyLibRoutine(unsigned char a, unsigned char b){
   unsigned int product, left right;
   product = a * b;
   left = a;
   right = b;
   total = 0;
   while(left > 0){
     if(left & 1){
        total += right;
     }
     left >>=1
     right <<=1;
   }
   grandTotal = grandTotal + (total - product);
   return grandTotal;
}

Two possible answers:

i) Create a new local unassigned int retVal and replace the return statement with:
 
retVal = grandTotal;
return retVal;

In addition, create a global mutex, lock it just before "total = 0;" and unlock it just before the (new) return statement.


ii) Move the declaration of total to inside MyLibRoutine (i.e. make it local), then do the same as in 1, except put the lock/unlock only around the two statements affecting grandTotal.

2.  Consider an operating system that uses paging in order to provide virtual memory capability; the paging system employs both a TLB and a single-level page table.  Assume that page tables are "wired" (pinned) in physical memory.

Draw a flow chart that describes the logic of handling a memory reference.  Your chart must include the possibility of TLB hits and misses, as well as page faults.  Be sure to mark which activities are accomplished by the OS's page fault exception handler.  (Draw on the back of this page).

Answer:


3.  Given a "flat" file system (i.e. one with only a single directory), a reasonable design decision is to place the directory on the middle cylinder of the disk.
a) Why?
b) Why doesn't the UNIX FFS put all of its directories (directory inodes) on the middle cylinder(s)?   (Hint: think of some common disk access patterns.)

Answer:
a) To minimize the seek time when accessing entries in the single directory.

b) For some disk access patterns, e.g. compiling all the .c files in one directory, we could get better performance by putting the directory inode AND the inodes of those files close to each other, instead of putting all the directory inodes together.

Page replacement question:

Given the following reference string:

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

And assuming we have 3 physical frames:
How many page faults occur and what gets thrown out on page replacement for the following schemes:

a) LRU
b) FIFO
c) Optimal
d) Second Chance

Is there any thrashing (>= 80% of references cause faults)?


Answer:

a) LRU: 17 faults, thrashing

  1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
frame 1: 1 1 1 4 4 4 5 5 5 3 3 3 7 7 7 2 2 2 2 2
frame 2:   2 2 2 1 1 1 6 6 6 6 2 2 2 3 3 3 3 3 3
frame 3:     3 3 3 2 2 2 1 1 1 1 1 6 6 6 1 1 1 6
fault: X X X X X X X X X X   X X X X X X     X
replaced:       1 2 3 4 1 2 5   6 3 1 2 7 6     1



b) FIFO: 17 faults, thrashing

  1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
frame 1: 1 1 1 4 4 4 5 5 5 3 3 3 3 6 6 6 1 1 1 1
frame 2:   2 2 2 1 1 1 6 6 6 6 2 2 2 3 3 3 3 3 6
frame 3:     3 3 3 2 2 2 1 1 1 1 7 7 7 2 2 2 2 2
fault: X X X X X X X X X X   X X X X X X     X
replaced:       1 2 3 4 1 2 5   6 1 3 2 7 6     3



c) Optimal: 11 faults

  1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
frame 1: 1 1 1 1 1 1 1 1 1 1 1 1 7 6 6 6 1 1 1 6
frame 2:   2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
frame 3:     3 4 4 4 5 6 6 3 3 3 3 3 3 3 3 3 3 3
fault: X X X X     X X   X     X X     X     X
replaced:       3     4 5   6     1 7     6     1



d) Second Chance: 17 faults, thrashing

  1 2 3 4 1 2 5 6 1 3 1 2 7 6 3 2 1 2 3 6
frame 1: 10 10 10 40 40 40 50 50 50 30 30 30 70 70 70 20 20 21 21 21
frame 2:   20 20 20 10 10 10 60 60 60 60 20 20 60 60 60 10 10 10 60
frame 3:     30 30 30 20 20 20 10 10 11 11 10 10 30 30 30 30 31 30
fault: X X X X X X X X X X     X X X X       X
replaced:       1 2 3 4 1 2 5     3 2 1 7       1

Disk performance question:

Assume your disk has the following attributes:

capacity: 36 GB = 36 * 230 bytes
# cylinders: 12,000 (assume all have the same capacity)
worst-case seek time: 10 ms  (assume proportional to the number of cylinders spanned)
transfer time: 15 MB/s = 15 * 220 bytes / sec
rotational speed: 7200 rpm = 120 revs / sec
disk block size: 4KB = 4 * 210 bytes

a) Assuming disk traffic is perfectly random, what is the average seek time of this device?

Avg seek length = 1/3 * (worst-case seek length) = 4000
Avg seek time = (4000 / 12,000) * (worst-case seek time)
                      = 10 / 3 ms


b) What is the average rotational latency of this device?

Rotational speed = 120 rps --> 1/120 sec per revolution
Avg rotational latency = 1/2 * (time for one rotation) = 1 / 240 s = 25 / 6 ms = 4.16 ms



c) Assume that the disk blocks for a give file are randomly scattered across the disk.  On average, how long does it take to read a 5 MB file?

5 MB file contains 5 MB / 4 KB blocks = 5 * 220 / 4 * 10 = (5 / 4) * 210 blocks = 1280 blocks

Once the read head is in position, the time it takes to read 1 block = read length / sequential read bandwidth

= 4 KB / 15 MB/s = (4/15) * 2-10 seconds

Since the blocks are randomly scattered, to position the head for the block, you will suffer the average seek time + the average rotational latency

= 10/3 ms + 25/6 ms = 15/2 ms = 15 / 2000 s = 3/400 s

Total time to read a file = # blocks * time to read a block = (1280) * (3/400 + (4/15)*2-10) sec = 9.9333 sec