Unit 4
1. Address translation
2. Preocdure to handle page fault
[Link] allocation methods
Unit 5
[Link] attributes in os
2. file allocation methods
3. types of files
[Link] scheduling algorithm
Consider a disk with 200 tracks and the queue has random requests from different processes
in the order: 55, 58, 39, 18, 90, 160, 150, 38, 184 CO5 L3 5 Initially arm is at 100. Find the
Average Seek length using FIFO, SSTF, SCAN and C-SCAN algorithm.
ChatGPT said:
Let's compute the Average Seek Length using different disk scheduling algorithms (FIFO,
SSTF, SCAN, and C-SCAN), given:
🔧 Given:
Total tracks: 200 (numbered 0 to 199)
Initial head position: 100
Request queue:
CopyEdit
55, 58, 39, 18, 90, 160, 150, 38, 184
1. 🎯 FIFO (First In First Out)
Order of execution:
CopyEdit
100 → 55 → 58 → 39 → 18 → 90 → 160 → 150 → 38 → 184
Seek operations:
|100−55| = 45
|55−58| = 3
|58−39| = 19
|39−18| = 21
|18−90| = 72
|90−160| = 70
|160−150| = 10
|150−38| = 112
|38−184| = 146
Total Seek = 45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498
Average Seek Length = 498 / 9 = 55.33
2. 🤏 SSTF (Shortest Seek Time First)
Start at 100. At each step, go to the nearest unvisited request.
Unvisited queue: [55, 58, 39, 18, 90, 160, 150, 38, 184]
Steps:
From 100 → 90 (distance 10)
From 90 → 58 (32)
58 → 55 (3)
55 → 39 (16)
39 → 38 (1)
38 → 18 (20)
18 → 150 (132)
150 → 160 (10)
160 → 184 (24)
Total Seek = 10 + 32 + 3 + 16 + 1 + 20 + 132 + 10 + 24 = 248
Average Seek Length = 248 / 9 = 27.56
3. 🧭 SCAN (Elevator Algorithm)
Assume direction: towards 0 initially.
Start at 100, go down to 0, then reverse and go up.
Requests:
Lower than 100: 90, 58, 55, 39, 38, 18
Higher than 100: 150, 160, 184
Execution Order:
100 → 90 → 58 → 55 → 39 → 38 → 18 → 0 → 150 → 160 → 184
Seek distances:
100 → 90 = 10
90 → 58 = 32
58 → 55 = 3
55 → 39 = 16
39 → 38 = 1
38 → 18 = 20
18 → 0 = 18
0 → 150 = 150
150 → 160 = 10
160 → 184 = 24
Total Seek = 10 + 32 + 3 + 16 + 1 + 20 + 18 + 150 + 10 + 24 = 284
Average Seek Length = 284 / 9 = 31.56
4. 🔁 C-SCAN (Circular SCAN)
Assume direction: upwards (towards 199)
When reaching the end, the head jumps to the start (0) without servicing requests during the
jump.
Execution Order:
100 → 150 → 160 → 184 → 199 (end) → jump to 0 (no cost) → 18 → 38 → 39 → 55 → 58
→ 90
Seek distances:
100 → 150 = 50
150 → 160 = 10
160 → 184 = 24
184 → 199 = 15
199 → 0 = 199 (include the jump)
0 → 18 = 18
18 → 38 = 20
38 → 39 = 1
39 → 55 = 16
55 → 58 = 3
58 → 90 = 32
Total Seek = 50 + 10 + 24 + 15 + 199 + 18 + 20 + 1 + 16 + 3 + 32 = 388
Average Seek Length = 388 / 9 = 43.11