$[24$ points$]$ Problem $3$ Page Replacement Algorithms

Consider the following page reference string:

$1,2,5,3,1,5,4,2,5,3,4,2,3,1,3,2$

Assuming demand paging with $3$ frames. Please illustrate each step that the

following replacement algorithms work for this reference string and compute

the page faults in each algorithm.

FIFO replacement

LRU replacement

Optimal replacement

Second$-$chance $($Clock$)$ replacement $($initially$,$ all reference bits are $0)$

$[24$ points$]$ Problem $4$ Disk Scheduling

Suppose that a disk drive has $1000$ cylinders, numbered $0$ to $999.$ The drive is

currently serving a request at cylinder $142.$ The queue of pending requests, in

FIFO order, is:

$86,100,272,126,242,513,19,574,536,810,625,325$

Starting from the current head position $(142),$ write out the sequence of the disk

head positions, and the total seek distance $($in cylinders$)$ that the disk arm

moves to satisfy all the pending requests, for each of the following disk$-$

scheduling algorithms. The disk arm is moving from right to left $(999$ to $0).$

Note that for C$-$SCAN and C$-$LOOK, we assume the serving direction is "From

right to left".

a$)$ FCFS

b$)$ SSTF

c$)$ SCAN

d$)$ LOOK

e$)$ C$-$SCAN

f$)$ C$-$LOOK$[24$ points$]$ Problem $3$ Page Replacement Algorithms

Consider the following page reference string:

$1,2,5,3,1,5,4,2,5,3,4,2,3,1,3,2$

Assuming demand paging with $3$ frames. Please illustrate each step that the

following replacement algorithms work for this reference string and compute

the page faults in each algorithm.

$1)$ FIFO replacement

$2)$ LRU replacement

$3)$ Optimal replacement

$4)$ Second$-$chance $($Clock$)$ replacement $($initially$,$ all reference bits are $0)$

$[24$ points$]$ Problem $4$ Disk Scheduling

Suppose that a disk drive has $1000$ cylinders, numbered $0$ to $999.$ The drive is

currently serving a request at cylinder $142.$ The queue of pending requests, in

FIFO order, is:

$86,100,272,126,242,513,19,574,536,810,625,325$

Starting from the current head position $(142),$ write out the sequence of the disk

head positions, and the total seek distance $($in cylinders$)$ that the disk arm

moves to satisfy all the pending requests, for each of the following diskscheduling algorithms. The disk arm is moving from right to left $(999$ to $0).$

Note that for C$-$SCAN and C$-$LOOK, we assume the serving direction is $$From

right to left$.$

a$)$ FCFS

b$)$ SSTF

c$)$ SCAN$$

d$)$ LOOK$$

e$)$ C$-$SCAN

f$)$ C$-$LOOK