Disk Arm Scheduling Algorithm

Lists of Descriptive Questions Answers and Short Study Notes On Operating System – Disk Arm Scheduling Algorithm

  • (1) Explain Disk Arm Scheduling Algorithm
  • (2) Consider an imaginary disk with 51 cylinders. A request comes in to read a block on cylinder 11. While the seek to cylinder 11 is in progress, new requests come in for cylinders 1, 36, 16, 34, 9, and 12, in that order. Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk scheduling Algorithms? 1. FCSC (First come first serve) 2. SSTF (Shorted seek time first) 3. SCAN 4. C-SCAN 5. LOOK (Elevator) 6. C-LOOK

 

Questions – 1 Explain Disk Arm Scheduling Algorithm.

The time required to read or write a disk block is determined by three factors:

  1. Seek time (the time to move the arm to the proper cylinder).
  2. Rotational delay (the time for the proper sector to rotate under the head).
  3. Actual data transfer time.

 

For most disks, the seek time dominates the other two times, so reducing the mean seek time can improve system performance substantially.

 

Various types of disk arm scheduling algorithms are available to decrease mean seek time.

  1. FCSC (First come first serve)
  2. SSTF (Shorted seek time first)
  3. SCAN
  4. C-SCAN
  5. LOOK (Elevator)
  6. C-LOOK

 

Question-2 Consider an imaginary disk with 51 cylinders. A request comes in to read a block on cylinder 11. While the seek to cylinder 11 is in progress, new requests come in for cylinders 1, 36, 16, 34, 9, and 12, in that order. Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk scheduling Algorithms? 1. FCSC (First come first serve) 2. SSTF (Shorted seek time first) 3. SCAN 4. C-SCAN 5. LOOK (Elevator) 6. C-LOOK

 

FCSC (First come first serve) Scheduling

disk scheduling Algorithms -1

  • Here requests are served in the order of their arrival.
  • In given example disk movement will be 11, 1, 36, 16, 34, 9 and 12 as first come first served.
    Total cylinder movement: (11-1)+ (36-1)+ (36-16) + (34-16) +(34-9)+(9-12) = 111

 

SSTF (Shortest seek time first)

disk scheduling Algorithms -2

  • We can minimize the disk movement by serving the request closest to the current position of the head.
  • In given example starting head position is 11, closest to 11 is 12, closest to 12 is 9, and so on.
  • As per SSTF request will be satisfied in order 11, 12, 9, 16, 1, 34, 36.
  • Total cylinder movement: (12-11) + (12-9) + (16-9) + (16-1) + (34-1) + (36-34) = 61

 

LOOK (Elevator) disk arm scheduling

disk scheduling Algorithms -3

  • Keep moving in the same direction until there are no more outstanding requests pending in that direction, then algorithm switches the direction.
  • After switching the direction the arm will move to handle any request on the way. Here first go it moves in up direction then goes in down direction.
  • This is also called as elevator algorithm.
  • In the elevator algorithm, the software maintains 1 bit: the current direction bit, which takes the value either UP or DOWN.
  • As per LOOK request will be satisfied in order 11, 12, 16, 34, 36, 9, 1.

Total cylinder movement: (12-11) + (16-12) + (34-16) + (36-34) + (36-9) + (9-1)=60

 

C-LOOK

disk scheduling Algorithms -4

  •  Keep moving in the same direction until there are no more outstanding requests pending in that direction, then algorithm switches direction.
  •  When switching occurs the arm goes to the lowest numbered cylinder with pending requests and from there it continues moving in upward direction again.
  • As per CLOOK requests will be satisfied in order 11, 12, 16, 34, 36, 1, 9
  • Total cylinder movement: (12-11) + (16-12) + (34-16) + (36-34) +(36-1)+(9-1)=68

 

SCAN

disk scheduling Algorithms -5

  • From the current position disk arm starts in up direction and moves towards the end, serving all the pending requests until end.
  • At that end arm direction is reversed (down) and moves towards the other end serving the pending requests on the way.
  • As per SCAN request will be satisfied in order: 11, 12, 16, 34, 36, 50, 9, 1
  • Total cylinder movement: (12-11) + (16-12) + (34-16) +(36-34) +(50-36) + (50-9) + (9-1) = 88

 

CSCAN

disk scheduling Algorithms -6

  • From the current position disk arm starts in up direction and moves towards the end, serving request until end.
  • At the end the arm direction is reversed (down), and arm directly goes to other end and again continues moving in upward direction.
  • As per SCAN request will be satisfied in order: 11, 12, 16, 34, 36, 50, 0, 1,9
  • Total cylinder movement: (12-11) + (16-12) + (34-16) +(36-34) +(50-36) + (50-0) + (1-0)+(9-1) = 98