cmsc 412-f98 Exam 2 SOLUTION
Solution to 1
a. LRU
request resulting fault
cache state
128 128 yes
12 128, 12 yes
3 128, 12, 3 yes
14 128, 12, 3, 14 yes
128 12, 3, 14, 128 no
8 3, 14, 128, 8 yes
3 14, 128, 8, 3 no
12 128, 8, 3, 12 yes
14 8, 3, 12, 14 yes
8 3, 12, 14, 8 no
15 12, 14, 8, 15 yes
8 faults.
Final cache state: 12, 14, 8, 15
b. FIFO
request resulting fault
cache state
128 128 yes
12 128, 12 yes
3 128, 12, 3 yes
14 128, 12, 3, 14 yes
128 128, 12, 3, 14 no
8 12, 3, 14, 8 yes
3 12, 3, 14, 8 no
12 12, 3, 14, 8 no
14 12, 3, 14, 8 no
8 12, 3, 14, 8 no
15 3, 14, 8, 15 yes
6 faults.
Final cache state: 3, 14, 8, 15
c. OPTIMAL (replacing an entry used latest in the future) gives the least
number of faults
request resulting fault
cache state
128 128 yes
12 128, 12 yes
3 128, 12, 3 yes
14 128, 12, 3, 14 yes
128 128, 12, 3, 14 no
8 12, 3, 14, 8 yes
3 12, 3, 14, 8 no
12 12, 3, 14, 8 no
14 12, 3, 14, 8 no
8 12, 3, 14, 8 no
15 ........., 15 yes
6 faults.
Final cache state: 3, 14, 8, 15
GRADING: 2 points for each part. Usually all or nothing, except -1 point
for very minor mistake.
Solution to 2
Access sequence:
/.inode + /.contents + /b.inode + /b.contents + /b/c.inode + /b/c.contents
+ /b/c/d.inode
Inode of /b/c/d has the required information.
GRADING: 2 points for the general idea. 1 point for starting off at
/.inode. 1 point for ending at /b/c/d.inode.
Solution to 3
a.
[1 point]
4K = 2^(2 + 10). So 12 bits for offset within page.
[1 point]
16 M = 2^(4 + 20). So 24 bit virtual address:
[12 bit virtual page number, 12 bit offset]
[1 point]
1 M = 2^(20). So 20 bit physical address:
[8 bit phsyical page number, 12 bit offset]
[1 point]
Page map table:
4K (= 2^12) entries.
Each entry consists of
[valid (1 bit), physical page # (8 bits), access/replacement info]
[1 point]
Associative map:
4 entries.
Each entry consists of
[valid (1 bit), virtual page # (12 bits), physical page # (8 bits),
access/replacement info]
GRADING: Usually all or nothing for each 1-point part.
b.
virtual virtual physical
address page # page #
020FE6 020 024
0231FD 023 027
0322A0 032 036
0AF570 0AF 0B3
0AF231 0AF 0B3
0231FD 023 027
01FFFF 01F 023
0AF570 0AF 0B3
Final contents of associative map:
valid virtual physical
bit page # page #
1 032 036
1 0AF 0B3
1 023 027
1 01F 023
GRADING: 1 point for getting virtual page numbers. 1 point for getting
physical page numbers. 3 points for map contents
Solution to 4
a. FCFS
N(t)
| J1
4 | J1 __________ J2
3 | J1 _________| |_______ J3
2 | J1 ______| |________ J4
1 |_____| |________
0 |________________________________________________________|____ time
0 2 3 7 11 16 25 35
J1 J2 J3 J4 J1 J2 J3 J4
arr arr arr arr dep dep dep dep
R1 = 11 (=11-0). R2 = 14 (=16-2). R3 = 22 (=25-3). R4 = 28 (=35-7).
R = (R1 + R2 + R3 + R4)/4 = 74/4.
N = Area under N(t) over [0,40] = (35 + 23 + 13 + 4)/40 = 75/40 =
System empties at time 35 ms.
b. SFJ premptive
N(t)
|
4 | J2 J1
3 | J2 _______________|________________ J3
2 | J1 ______| |________ J4
1 |_____| |________
0 |____________________________________________________________|____ time
0 2 3 7 16 25 35
J1 J2 J3 J4 J2 J1 J3 J4
arr arr arr arr dep dep dep dep
Priority
of jobs J1 J2,J1 J2,J1,J3 J1,J3,J4
Rem serv 11 5, 9 4, 9, 9 9, 9,10
R1 = 16 (=16-0). R2 = 5 (=7-2). R3 = 22 (=25-3). R4 = 28 (=35-7).
R = (R1 + R2 + R3 + R4)/4 = 71/4.
N = Area under N(t) over [0,40] = (35 + 23 + 13)/40 = 71/40
System empties at time 35 ms.
Alternatively, at time 7, if we start J3 instead of J1, we have R3=13 and R1=25.
GRADING: In each part, 2 points for getting the order of job servicing
and departure times. 1 point for response times. 1 point for average number
of customers. 1 point for system emptying time.