Tutorial – 6
CSC-204
Answers
1. For FCFS disk scheduling, request queue is 98, 183, 37, 122, 14, 124, 65, 67. The
head starts at 53. What is the total head movement?
Answer: (183−53) + (183−37) + (122−37) + (122−14) + (124−14) + (124−65) +
(67−65)
=130 + 146 + 85 + 108 + 110 + 59 + 2
=640
2. Consider the following page reference string:
g, e, b, c, e, c, a, g, d, a, g, b
With four frames, how many page faults would occur with the optimal page
replacement algorithm?
Answer: 6
RS g e b c e c a g d a g b
F0 g g g g g g g g g g g g
F1 e e e e e a a a a a a
F2 b b b b b b b b b b
F3 c c c c c d d d d
Page 1 2 3 4 x x 5 x 6 x x x
Fault
3. Suppose we have a magnetic disk (resembling an IBM Microdrive) with the following
parameters: Average seek time 12ms, rotation rate 3600rpm, transfer rate 3.5 MB /sec,
number of sectors per track 64, sector size 512 bytes and controller overhead 5.5ms.
What is the average time to read a single sector?
Answer: Disk Access Time = seek time + rotational delay + transfer time + controlled
overhead
= 12 + (0.5*60*103 / 3600) + (512/(3.5*220)) * 1000 + 5.5 = 25.97ms
4. Disk requests are received by a disk drive for cylinder 5, 25, 18, 3, 39, 8 and 35 in that
order. A seek takes 5ms per cylinder moved. The seek time required to serve these
requests if serviced by SSTF(Shortest seek time first) disk scheduling algorithm.
Assume that the arm is at cylinder 20 when the last of these request is made with none
of these requests are yet served.
Answer: Requests: 5, 25, 18, 3, 39, 8, 35
Initial head at 20
Seek time = 5 ms per cylinder
SSTF Order:
20 → 18 → 25 → 35 → 39 → 8 → 5 → 3
Movements (in cylinders):
2 + 7 + 10 + 4 + 31 + 3 + 2 = 59 cylinders
Total seek time:
59 × 5 = 295 ms
5. What is the average time to read or write a 512-byte sector for a typical disk rotating
at 7200 RPM? The advertised average seek time is 8ms, the transfer rate is 20MB/sec,
and the controller overhead is 2ms. Assume that the disk is idle so that there is no
waiting time.
Answer: Disk Access Time = seek time + rotational delay + transfer time + controller
overhead
= 8 + (0.5*60*1000/7200) + (512/20*220) *1000+ 2 = 14.17ms
6. 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 page is available or the
replaced page is not modified, and 20 milliseconds if the replaces page is modified.
Memory access time is 100 nanoseconds. Assume that the page to be replaced is
modified 70 percent of the time. What is the maximum acceptable page fault rate for
an effective access time of no more than 200 nanoseconds?
Answer:EAT = (1−P) × Memory Access Time + P × Average Page Fault Service Time
EAT = 0.2 microseconds = (1−P) * 0.1 microseconds + (0.3P) * 8 milliseconds +
(0.7P) * 20 milliseconds
Simplifying:
0.1 = − 0.1P + 2400P + 14000P
0.1 ≈ 16,400P
P≈0.000006
7. A demand paging system has page fault service time as 125 time units if page is not
dirty and 400 time units of page fault service time if it is a dirty page. Memory access
time is 10 time units. The probability of a page fault is 0.3. In case of page fault, the
probability of page being dirty is P. It is observed that average access time is 50 time
units. What is the value of P?
Answer: Page fault rate = 0.3
Hence page hit rate = 0.7
Memory access time = 10 time units
Page fault service time = 125 time units
Let probability of page being duty = p
Give effective access time = 50ms
EMAT = 0.7 * MAT + 0.3 [p*(400PFST) + (1-p) * PFST]
=> 0.7 * 10 + 0.3 * [400 * 125p + 125 – 125p] = 50
=> 7 + 0.3*[5000p – 125p +125] = 50
=> 0.3 * [49875p +125] = 43
p = 0.0004
8. Consider the following snapshot of the system
Answer the following questions using the banker’s algorithm:
a. What is the content of the matrix Need?
b. Is the system in a safe state?
c. If a request from process P1 arrives for (0,4,2,0), can the request be granted
immediately?
Answer: a. The values of Need for processes P0 through P4, respectively, are
(0,0,0,0), (0,7,5,0), (1,0,0,2), (0,0,2,0), and (0,6,4,2).
b. Yes, with Available being equal to (1,5,2,0), either process P0 or P3 could run.
Once process P3 runs, it releases its resources which allow all other existing processes
to run.
c. Yes, it can. This results in the value of Available being (1,1,0,0). One ordering of
the processes that can finish is P0, P2, P3, P1, and P4.