OS Assignment: Disk Scheduling, Page Replacement Algorithms Analysis

This document presents solutions for an operating systems assignment focusing on disk scheduling and page replacement algorithms. The disk scheduling section analyzes the performance of FIFO, SSTF, SCAN, LOOK, and CSCAN algorithms, calculating the number of tracks traversed by each. The page replacement section evaluates LRU, FIFO, Optimal, and Clock algorithms with varying numbers of locked frames, determining the number of page faults and hits for each. The solutions include detailed tables illustrating the page replacement process, providing a comprehensive analysis of the algorithms' effectiveness under different conditions. Desklib provides this solved assignment to aid students in their operating systems studies.

Task 3: Number of tracks traversed
a) FIFO = 1078
b) SSTF = 316
c) SCAN = 312
d) LOOK = 300
e) CSCAN = 388
Task 4:
a.
LRU Page Replacement with 6 frames locked = 17 Page Faults
Page
Ref.
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 3 6 2 1 3 6
f1 1 1 3 3 1 1 3 3 6 6 2 2 1 1 3 3 3 3
f2 2 2 4 4 2 2 5 5 1 1 3 3 2 2 7 7 6
f3 x x x x x x x x x x x x x x x x x x
f4 x x x x x x x x x x x x x x x x x x
f5 x x x x x x x x x x x x x x x x x x
f6 x x x x x x x x x x x x x x x x x x
f7 x x x x x x x x x x x x x x x x x x
f8 x x x x x x x x x x x x x x x x x x
* * * * * * * * * * * * * * * *  *
* = Page faults = 17  = Page Hits = 1 x = Locked
LRU Page Replacement with 4 frames locked = 11 Page Faults
* = Page faults = 11  = Page Hits = 7 x = Locked
b.
Page
Ref.
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 3 6 2 1 3 6
f1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6 7 7 7
f2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 6
f3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2
f4 4 4 4 4 5 5 5 5 3 3 3 3 3 3 3
f5 x x x x x x x x x x x x x x x x x x
f6 x x x x x x x x x x x x x x x x x x
f7 x x x x x x x x x x x x x x x x x x
f8 x x x x x x x x x x x x x x x x x x
* * * *    * * * * *    *  *

FIFO page replacement with 6 locked frames = 17 page faults
Page
Ref.
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 3 6 2 1 3 6
f1 1 1 3 3 1 1 3 3 6 6 2 2 1 1 3 3 3 6
f2 2 2 4 4 2 2 5 5 1 1 3 3 2 2 7 7 7
f3 x x x x x x x x x x x x x x x x x x
f4 x x x x x x x x x x x x x x x x x x
f5 x x x x x x x x x x x x x x x x x x
f6 x x x x x x x x x x x x x x x x x x
f7 x x x x x x x x x x x x x x x x x x
f8 x x x x x x x x x x x x x x x x x x
* * * * * * * * * * * * * * * *  *
* = Page faults = 17  = Page Hits = 11 x = Locked
FIFO page replacement with 4 locked frames = 11 page faults
Pag
e
Ref.
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 3 6 2 1 3 6
f1 1 1 1 1 1 1 1 5 5 5 5 3 3 3 3 3 3 3
f2 2 2 2 2 2 2 2 6 6 6 6 6 6 6 7 7 7
f3 3 3 3 3 3 3 3 1 1 1 1 1 1 1 1 6
f4 4 4 4 4 4 4 4 2 2 2 2 2 2 2 2
f5 x x x x x x x x x x x x x x x x x x
f6 x x x x x x x x x x x x x x x x x x
f7 x x x x x x x x x x x x x x x x x x
f8 x x x x x x x x x x x x x x x x x x
* * * *    * * * * *    *  *
* = Page faults = 11  = Page Hits = 7 x = Locked

c.
Optimal page replacement with 6 locked frames = 13 page faults
Pag
e
Ref.
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 3 6 2 1 3 6
f1 1 1 3 4 1 1 1 1 1 1 1 1 1 2 2 7 7 6
f2 2 2 2 2 2 3 5 6 6 2 3 3 3 3 3 3 3
f3 x x x x x x x x x x x x x x x x x x
f4 x x x x x x x x x x x x x x x x x x
f5 x x x x x x x x x x x x x x x x x x
f6 x x x x x x x x x x x x x x x x x x
f7 x x x x x x x x x x x x x x x x x x
f8 x x x x x x x x x x x x x x x x x x
* * * * *  * * *  * *  *  *  *
* = Page faults = 13  = Page Hits = 5 x = Locked
Optimal page replacement with 4 locked frames = 7 page faults
Pag
e
Ref.
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 3 6 2 1 3 6
f1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 7 7 7
f2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
f3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
f4 4 4 4 4 5 6 6 6 6 6 6 6 6 6 6
f5 x x x x x x x x x x x x x x x x x x
f6 x x x x x x x x x x x x x x x x x x
f7 x x x x x x x x x x x x x x x x x x
f8 x x x x x x x x x x x x x x x x x x
* * * *    * *       *  
* = Page faults = 7  = Page Hits = 11 x = Locked

d.
Clock page replacement with 6 locked frames = 17 page faults
Pag
e
Ref.
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 3 6 2 1 3 6
Pag
e in
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 - 6
f1 01 01 03 03 01 01 03 03 06 06 02 02 01 01 03 03 13 03
f2 02 02 04 04 02 02 05 05 01 01 03 03 02 02 07 07 06
f3 x x x x x x x x x x x x x x x x x x
f4 x x x x x x x x x x x x x x x x x x
f5 x x x x x x x x x x x x x x x x x x
f6 x x x x x x x x x x x x x x x x x x
f7 x x x x x x x x x x x x x x x x x x
f8 x x x x x x x x x x x x x x x x x x
Pag
e
Out
- - 1 2 3 4 1 2 3 5 6 1 2 3 1 2 - 7
* * * * * * * * * * * * * * * *  *
* = Page faults = 17  = Page Hits = 1 x = Locked
Clock page replacement with 4 locked frames = 11 page faults
Pag
e
Ref.
1 2 3 4 1 2 3 5 6 1 2 3 1 2 3 7 3 6 2 1 3 6
Pag
e in
1 2 3 4 - - - 5 6 1 2 3 - - - 7 - 6
f1 01 01 01 01 11 01 01 05 05 05 05 03 03 03 13 03 13 03
f2 02 02 02 02 12 02 02 06 06 06 06 06 06 06 07 07 07
f3 03 03 03 03 13 03 03 01 01 01 11 01 01 01 01 06
f4 04 04 04 04 04 04 04 02 02 02 12 02 02 02 02
f5 x x x x x x x x x x x x x x x x x x
f6 x x x x x x x x x x x x x x x x x x
f7 x x x x x x x x x x x x x x x x x x
f8 x x x x x x x x x x x x x x x x x x
Pag
e
Out
- - - - - - - 1 2 3 4 5 - - - 6 - 1
* * * *    * * * * *    *  *
* = Page faults = 11  = Page Hits = 7 x = Locked