Head is at 143 and the previous request was at 125. Which way is the head moving?

Upward (towards higher cylinders)

How is the FCFS total computed here?

Sum of absolute differences between successive requests in FIFO order, starting from 143 (7141)

Sum of distances in sorted cylinder order

Distance from 0 to the highest request

Sum of distances to the nearest pending request each time

Why is SCAN (9799) so much larger than LOOK (3349) here?

SCAN goes all the way to cylinder 4999 before reversing, while LOOK turns at the last request 1774

LOOK serves fewer requests than SCAN

LOOK ignores cylinders below the head

In C-SCAN the 9985 total includes which extra movement compared with SCAN-style sweep?

The return jump 4999 to 0 (4999) and then 0 to 56

Serving 130 and 56 on the way down

Nothing; it is the same as SCAN

Asked 2/13
2072 Magh · 10 marks

Disk scheduling with 5000 cylinders

Short answer

For head at 143 moving upward, FCFS gives 7141 cylinders, SCAN to 4999 then reverse gives 9799, LOOK to 1774 then reverse gives 3349, C-SCAN with return jump counted gives 9985, SSTF gives 1805 cylinders.

Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143, and the previous request was at cylinder 125. The queue of pending requests, in FIFO order is: 56, 1470, 913, 1774, 948, 1509, 1022, 1750, 130 Starting from the current head position, what is the total distance (in cylinder) that the disk arm moves to satisfy all the pending requests, for each of the following algorithms: FCFS, SCAN, LOOK, CSCAN, SSTF

Disk: 5000 cylinders (0 to 4999), head at 143, previous request 125, so the head is moving upward. Queue (FIFO): 56, 1470, 913, 1774, 948, 1509, 1022, 1750, 130.

FCFS

FCFS: service order (head at 143): 56, 1470, 913, 1774, 948, 1509, 1022, 1750, 130

  143 -> 56    = 87
   56 -> 1470  = 1414
 1470 -> 913   = 557
  913 -> 1774  = 861
 1774 -> 948   = 826
  948 -> 1509  = 561
 1509 -> 1022  = 487
 1022 -> 1750  = 728
 1750 -> 130   = 1620
Total = 87 + 1414 + 557 + 861 + 826 + 561 + 487 + 728 + 1620 = 7141

SCAN (up to 4999, then reverse)

SCAN: service order (head at 143): 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 56

  143 -> 913   = 770
  913 -> 948   = 35
  948 -> 1022  = 74
 1022 -> 1470  = 448
 1470 -> 1509  = 39
 1509 -> 1750  = 241
 1750 -> 1774  = 24
 1774 -> 4999  = 3225
 4999 -> 130   = 4869
  130 -> 56    = 74
Total = 770 + 35 + 74 + 448 + 39 + 241 + 24 + 3225 + 4869 + 74 = 9799

LOOK (up to 1774, then reverse)

LOOK: service order (head at 143): 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 56

  143 -> 913   = 770
  913 -> 948   = 35
  948 -> 1022  = 74
 1022 -> 1470  = 448
 1470 -> 1509  = 39
 1509 -> 1750  = 241
 1750 -> 1774  = 24
 1774 -> 130   = 1644
  130 -> 56    = 74
Total = 770 + 35 + 74 + 448 + 39 + 241 + 24 + 1644 + 74 = 3349

C-SCAN (up to 4999, jump to 0, continue upward)

C-SCAN: service order (head at 143): 913, 948, 1022, 1470, 1509, 1750, 1774, 56, 130

  143 -> 913   = 770
  913 -> 948   = 35
  948 -> 1022  = 74
 1022 -> 1470  = 448
 1470 -> 1509  = 39
 1509 -> 1750  = 241
 1750 -> 1774  = 24
 1774 -> 4999  = 3225
 4999 -> 0     = 4999  (return jump)
    0 -> 56    = 56
   56 -> 130   = 74
Total = 770 + 35 + 74 + 448 + 39 + 241 + 24 + 3225 + 4999 + 56 + 74 = 9985

SSTF

SSTF: service order (head at 143): 130, 56, 913, 948, 1022, 1470, 1509, 1750, 1774

  143 -> 130   = 13
  130 -> 56    = 74
   56 -> 913   = 857
  913 -> 948   = 35
  948 -> 1022  = 74
 1022 -> 1470  = 448
 1470 -> 1509  = 39
 1509 -> 1750  = 241
 1750 -> 1774  = 24
Total = 13 + 74 + 857 + 35 + 74 + 448 + 39 + 241 + 24 = 1805

Summary

Algorithm	Total head movement (cylinders)
FCFS	7141
SCAN	9799
LOOK	3349
C-SCAN	9985 (4986 if the return sweep is not counted)
SSTF	1805

Answer: FCFS 7141, SCAN 9799, LOOK 3349, C-SCAN 9985, SSTF 1805 cylinders.

✓ Answer checked by Claude Opus 5.5 (high effort)

Disk scheduling with 100 cylinders · Operating System, chapter 6 · asked 2×
Disk scheduling with 50 cylinders · Operating System, chapter 6
Disk scheduling with 150 cylinders · Operating System, chapter 6 · asked 2×
Disk scheduling, 1000 cylinders, head at 345 · Operating System, chapter 6
Disk scheduling: FCFS, SSF, SCAN at 53 · Operating System, chapter 6 · asked 3×
Disk scheduling: FCFS, SSTF, SCAN, LOOK, C-SCAN · Operating System, chapter 6
Device driver; FCFS, SSF, SCAN numerical · Operating System, chapter 6 · asked 2×

All Operating System chapter 6 questions →