Numerical on Disk Scheduling Algorithms

Q. 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

Initially arm is at 100. Find the Average Seek length using FIFO, SSTF, SCAN and C-SCAN algorithm.

Solution :

1. FCFS (First-Come, First-Served)

• Requests are serviced in the order they arrive.
• The head moves without optimization, leading to a high seek time.
• Total cylinders traveled: 498
• Average Seek Length:

4989=55.3\frac{498}{9} = 55.39498=55.3

2. SSTF (Shortest Seek Time First)

• The next closest request is serviced first, minimizing immediate seek time.
• Provides better performance than FCFS by reducing unnecessary head movement.
• Total cylinders traveled: 247.5
• Average Seek Length: 27.5

3. SCAN (Elevator Algorithm)

• The head moves in one direction servicing all requests, then reverses direction.
• Avoids starvation and ensures more uniform service.
• Total cylinders traveled: 250.2
• Average Seek Length: 27.8

4. C-SCAN (Circular SCAN)

• The head moves in one direction only, and after reaching the end, it returns to the start without servicing in reverse.
• Offers more uniform wait time but slightly higher seek time than SCAN.
• Total cylinders traveled: 320.4
• Average Seek Length: 35.6

Q2. There are 200 tracks on a disc (0 to 199). The prior request was at track 50 and the disk head is now at track 53. The following is the queue of pending requests arranged as they were received. [38 122 14 124 98 183 37 65 64]. Utilizing the disk scheduling algorithms listed below determine the total head movement.

FCFS stands for First-Come First-Served.

Shortest Seek Time First is known as SSTF

Elevator Algorithm

SCAN

LOOK

C-Scan

C-LOOK

Solution:

Let's calculate Total Head Movement for each algorithm:

1. FCFS:

Sequence: 53 → 98 → 183 → 37 → 122 → 14 → 124 → 65 → 67
Total Head Movement =
|53-98| + |98-183| + |183-37| + |37-122| + |122-14| + |14-124| + |124-65| + |65-67|
= 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 tracks

2. SSTF:

Choose the closest request to the current head.

Sequence: 53 → 65 → 67 → 37 → 14 → 98 → 122 → 124 → 183
Total Movement =
|53-65| + |65-67| + |67-37| + |37-14| + |14-98| + |98-122| + |122-124| + |124-183|
= 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236 tracks

3. SCAN (Assume moving towards 0 initially):

Sequence: 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183
Total Movement =
|53-37| + |37-14| + |14-0| + |0-65| + |65-67| + |67-98| + |98-122| + |122-124| + |124-183|
= 16 + 23 + 14 + 65 + 2 + 31 + 24 + 2 + 59 = 236 tracks

4. LOOK (Only go as far as needed):

Sequence: 53 → 37 → 14 → 65 → 67 → 98 → 122 → 124 → 183
Total Movement =
|53-37| + |37-14| + |14-65| + |65-67| + |67-98| + |98-122| + |122-124| + |124-183|
= 16 + 23 + 51 + 2 + 31 + 24 + 2 + 59 = 208 tracks

5. C-SCAN (Assume moving towards higher tracks):

Sequence: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 0 → 14 → 37
Total Movement =
|53-65| + |65-67| + |67-98| + |98-122| + |122-124| + |124-183| + |183-199| + |199-0| + |0-14| + |14-37|
= 12 + 2 + 31 + 24 + 2 + 59 + 16 + 199 + 14 + 23 = 382 tracks

6. C-LOOK:

Sequence: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 14 → 37
Total Movement =
|53-65| + |65-67| + |67-98| + |98-122| + |122-124| + |124-183| + |183-14| + |14-37|
= 12 + 2 + 31 + 24 + 2 + 59 + 169 + 23 = 322 tracks