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
|