OPERATING SYSTEM - CHAPTER 28

Disk Scheduling Algorithms in OS: FCFS, SSTF, SCAN, C-SCAN, LOOK & C-LOOK

A hard disk can receive many read and write requests at the same time. If the disk head moves randomly from one cylinder to another, a large amount of time can be wasted only in head movement.

Disk Scheduling Algorithms decide which pending disk request should be served next so that seek movement, waiting time and I/O overhead can be controlled.

The main algorithms studied in Operating System are FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK.

Quick Answer:

Disk Scheduling is the operating-system technique used to decide the order in which pending disk I/O requests should be served.

FCFS serves requests in arrival order.
SSTF serves the request nearest to the current disk head.
SCAN moves like an elevator toward one disk end and then reverses.
C-SCAN serves requests in one direction and then returns to the opposite end.
LOOK works like SCAN but reverses at the last request instead of moving unnecessarily to the physical disk boundary.
C-LOOK is the circular version of LOOK.

Jump to a Topic

Disk Basics Why Scheduling Important Terms FCFS SSTF SCAN C-SCAN LOOK C-LOOK Comparison Simulator Exam Revision FAQ

First Understand How a Hard Disk Works

Traditional Hard Disk Drives store data on magnetic circular platters. Data is organised into tracks and sectors. A read/write head must move to the required position before data can be accessed.

Platter Circular magnetic surface where data is stored.

Track Circular path on the platter.

Sector Smaller division of a track used to store data.

Read/Write Head Component that reads or writes data on the disk surface.

What Is a Disk Cylinder?

When multiple platters are used, tracks at the same radius across platter surfaces form a cylinder.

In most Operating System numerical questions, requests are represented by cylinder numbers.

Example:

Disk cylinders: 0 to 199

Current head position: 53

Pending request: 98

Seek Time, Rotational Latency and Transfer Time

HEAD MOVEMENT Seek Time Time required to move the disk head to the required track or cylinder.

ROTATION Rotational Latency Time waiting for the required sector to rotate under the disk head.

DATA Transfer Time Time required to actually transfer the requested data.

COMPLETE ACCESS Disk Access Time Approximate combination of seek, rotational and transfer delays.

ACCESS TIME Approximate Disk Access

Access Time ≈ Seek Time + Rotational Latency + Transfer Time

ROTATION Average Rotational Latency

Average Latency ≈ 30000 / RPM milliseconds

TRANSFER Transfer Time

Transfer Time = Data Size / Transfer Rate

Disk Scheduling Algorithms mainly try to reduce unnecessary seek movement. In textbook numericals, total head movement is often used as a simple measure of performance.

Average Rotational Latency Example

Suppose a hard disk rotates at:

RPM = 7200

Average rotational latency:

Average Rotational Latency = 30000 / RPM = 30000 / 7200 ≈ 4.17 ms

A 7200 RPM disk has an average rotational latency of approximately 4.17 milliseconds.

Why Do We Need Disk Scheduling?

Several processes can generate disk requests at almost the same time.

Suppose the current head is at Cylinder 53 and pending requests are:

98, 183, 37, 122, 14, 124, 65, 67

The operating system must decide: Which request should be served first?

Main objectives of Disk Scheduling:

Reduce total head movement
Reduce seek time
Improve throughput
Reduce average waiting time
Improve response time
Provide reasonable fairness
Avoid starvation where possible

Visualising a Disk Request Queue

Cylinder Range: 0 to 199 | Current Head: 53

Important Terms in Disk Scheduling Numericals

Request Queue List of pending cylinder requests.

Initial Head Position Cylinder where the head starts.

Direction SCAN, C-SCAN, LOOK and C-LOOK may require an initial movement direction.

Cylinder Range Example: 0 to 199.

Head Movement Absolute distance travelled from one cylinder to another.

Starvation A request waits for a very long time because other requests keep being selected first.

Six Important Disk Scheduling Algorithms

FCFS

First Come First Serve

Serve requests in arrival order.

SSTF

Shortest Seek Time First

Serve the request closest to the current head.

SCAN

Elevator Algorithm

Move in one direction to the disk boundary, then reverse.

C-SCAN

Circular SCAN

Serve in one direction, jump back and continue in the same direction.

LOOK

Smarter SCAN

Reverse at the last pending request, not the physical disk end.

C-LOOK

Circular LOOK

Move to the last request in one direction, jump to the opposite pending request.

Common Example Used for All Algorithms

Request Queue: 98, 183, 37, 122, 14, 124, 65, 67 Initial Head Position: 53 Cylinder Range: 0 to 199 For SCAN, C-SCAN, LOOK and C-LOOK: Initial Direction = Toward Higher Cylinder Numbers

Using the same queue for every algorithm makes comparison easy.

FCFS Disk Scheduling Algorithm

FCFS stands for First Come First Serve.

Requests are served in exactly the same order in which they enter the disk request queue.

FCFS Rule:

First request in queue = First request served.

FCFS Service Route

53

→

98

→

183

→

37

→

122

→

14

→

124

→

65

→

67

FCFS Solved Example

Head Movement: |98 - 53| = 45 |183 - 98| = 85 |37 - 183| = 146 |122 - 37| = 85 |14 - 122| = 108 |124 - 14| = 110 |65 - 124| = 59 |67 - 65| = 2

Total Head Movement = 45 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 640 cylinders

FCFS Result:
Total Head Movement = 640 cylinders

Advantages and Disadvantages of FCFS

Advantages	Disadvantages
Very simple to implement	Can produce very large head movement
Requests are treated in arrival order	Poor average seek time in many workloads
Does not normally starve old requests	Does not consider request location

SSTF Disk Scheduling Algorithm

SSTF stands for Shortest Seek Time First.

From the current head position, the algorithm chooses the pending request with the smallest cylinder distance.

SSTF Rule:

Next request = Nearest pending cylinder.

From Head 53:

Distance to 65 = 12 Distance to 67 = 14 Distance to 37 = 16 Therefore: Choose 65 first.

SSTF Solved Example

SSTF Route

53

→

65

→

67

→

37

→

14

→

98

→

122

→

124

→

183

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

SSTF Result:
Total Head Movement = 236 cylinders

Can SSTF Cause Starvation?

Yes.

Suppose the head is serving many requests around Cylinders 50 to 80. A request at Cylinder 190 may wait for a very long time if new nearby requests continuously arrive.

SSTF can favour nearby requests so strongly that a far-away request may suffer starvation.

SCAN Disk Scheduling Algorithm

SCAN is often called the Elevator Algorithm.

Imagine an elevator moving upward. It serves all requested floors in that direction, reaches the end, and then moves in the opposite direction.

SCAN Rule:

Move in one direction → serve requests on the way → reach disk boundary → reverse direction.

SCAN Solved Example

Initial direction: toward higher cylinders.

SCAN Route

53

→

65

→

67

→

98

→

122

→

124

→

183

→

199

→

37

→

14

Head moves: 53 → 199 = 146 cylinders Then: 199 → 14 = 185 cylinders Total Head Movement: 146 + 185 = 331 cylinders

SCAN Result:
Total Head Movement = 331 cylinders

C-SCAN Disk Scheduling Algorithm

C-SCAN means Circular SCAN.

The disk head serves requests only while moving in one direction.

When it reaches the end, it jumps to the opposite end and starts serving in the same direction again.

C-SCAN Rule:

Serve in one direction → reach disk end → jump to opposite end → continue in same direction.

C-SCAN Solved Example

C-SCAN Route

53

→

65

→

67

→

98

→

122

→

124

→

183

→

199

↺

0

→

14

→

37

53 → 199 = 146 199 → 0 = 199 0 → 37 = 37 Total Head Movement = 146 + 199 + 37 = 382 cylinders

C-SCAN Result:
Total Head Movement = 382 cylinders

The circular return movement is normally counted in standard textbook total-head-movement calculations unless the question states otherwise.

LOOK Disk Scheduling Algorithm

LOOK is similar to SCAN, but it avoids unnecessary travel to the physical disk boundary.

The head only goes as far as the last pending request in the current direction.

LOOK Rule:

Move in one direction → serve all pending requests → reverse at the last request.

Difference from SCAN:

SCAN may move to Cylinder 199.
LOOK stops at Cylinder 183 in this example because there is no request beyond 183.

LOOK Solved Example

LOOK Route

53

→

65

→

67

→

98

→

122

→

124

→

183

←

37

←

14

53 → 183 = 130 183 → 14 = 169 Total Head Movement = 130 + 169 = 299 cylinders

LOOK Result:
Total Head Movement = 299 cylinders

C-LOOK Disk Scheduling Algorithm

C-LOOK combines the circular idea of C-SCAN with the boundary-saving idea of LOOK.

The head moves only up to the last pending request, then jumps to the first pending request on the opposite side.

C-LOOK Rule:

Serve requests in one direction → stop at last request → jump to first pending request on the other side → continue in same direction.

C-LOOK Solved Example

C-LOOK Route

53

→

65

→

67

→

98

→

122

→

124

→

183

↺

14

→

37

53 → 183 = 130 183 → 14 = 169 14 → 37 = 23 Total Head Movement = 130 + 169 + 23 = 322 cylinders

C-LOOK Result:
Total Head Movement = 322 cylinders

FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK Results

For the same queue, head position and initial direction:

FCFS 640 Cylinders

SSTF 236 Cylinders

SCAN 331 Cylinders

C-SCAN 382 Cylinders

LOOK 299 Cylinders

C-LOOK 322 Cylinders

These values apply only to this specific request queue, head position, cylinder range and direction. A different workload can produce a different result.

Difference Between Disk Scheduling Algorithms

Algorithm	Selection Rule	Direction Required?	Starvation Risk	Main Idea
FCFS	Arrival order	No	Very low	Simple queue
SSTF	Nearest request	No	Possible	Minimum immediate seek
SCAN	Serve requests while moving toward disk end	Yes	Lower than SSTF	Elevator movement
C-SCAN	Serve in one direction only	Yes	Low	More uniform directional service
LOOK	SCAN without unnecessary disk-end travel	Yes	Low	Reverse at last request
C-LOOK	Circular LOOK movement	Yes	Low	Jump between extreme pending requests

SCAN vs LOOK

Basis	SCAN	LOOK
Movement	Moves to physical disk boundary before reversing	Stops at last pending request
Unnecessary Travel	Possible	Reduced
Example	May move to Cylinder 199	May stop at Cylinder 183

C-SCAN vs C-LOOK

Basis	C-SCAN	C-LOOK
Forward End	Moves to disk boundary	Moves only to last pending request
Return	Jumps to opposite disk boundary	Jumps to opposite extreme pending request
Unnecessary Movement	Can be higher	Usually reduced

SSTF vs SCAN

SSTF makes a locally attractive decision: select the nearest current request.

SCAN follows a stable movement direction.

SSTF = nearest request now

SCAN = serve requests along one organised sweep

SSTF can cause starvation when requests keep arriving near the current head position. SCAN generally provides more predictable service across cylinder ranges.

Average Head Movement Formula

Average Head Movement

= Total Head Movement / Number of Requests

For SSTF in our example:

Total Head Movement = 236 cylinders Number of Requests = 8 Average Head Movement = 236 / 8 = 29.5 cylinders per request

Calculating Approximate Seek Time from Head Movement

Some exam questions may provide an approximate time per cylinder.

Total Head Movement = 236 cylinders Suppose: Average movement cost = 0.1 ms per cylinder Approximate Seek Time = 236 × 0.1 = 23.6 ms

Real hard-disk seek time is not always perfectly linear with cylinder distance. Use this simple multiplication only when the numerical question explicitly gives such a model.

Why Initial Direction Matters in SCAN, C-SCAN, LOOK and C-LOOK

Direction-based algorithms need to know whether the head initially moves toward lower cylinder numbers or higher cylinder numbers.

If the direction changes, the service order and total head movement can also change.

Never solve a SCAN, C-SCAN, LOOK or C-LOOK numerical without checking the given initial direction. If the exam question does not specify a direction, clearly state the assumption you are using.

Common Mistakes in Disk Scheduling Numericals

Mistake 1: Forgetting the Initial Head Position

The first movement always starts from the given head position.

Mistake 2: Sorting FCFS Requests

FCFS must use the original arrival order.

Mistake 3: Choosing the Globally Smallest Cylinder in SSTF

SSTF chooses the cylinder nearest to the current head, not simply the smallest pending cylinder.

Mistake 4: Treating SCAN and LOOK as the Same

SCAN moves to the physical boundary. LOOK reverses at the last request.

Mistake 5: Treating C-SCAN and C-LOOK as the Same

C-SCAN uses physical disk boundaries. C-LOOK uses extreme pending requests.

Mistake 6: Ignoring Circular Jump Distance

In most textbook calculations, the circular return movement contributes to total head movement.

Mistake 7: Ignoring Direction

Direction directly affects SCAN-family results.

Fairness and Starvation in Disk Scheduling

Algorithm	Fairness Idea	Starvation
FCFS	Arrival-order fairness	Usually not a major problem
SSTF	Favors nearby requests	Possible
SCAN	Systematic sweep	Much less likely
C-SCAN	More uniform directional waiting	Low
LOOK	SCAN-style service without empty travel	Low
C-LOOK	Circular service over requested range	Low

Are These Algorithms Important for SSDs Too?

FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK were developed mainly around mechanical hard disks.

An SSD has no mechanical read/write head that must physically move from Cylinder 20 to Cylinder 180.

HDD: physical seek movement matters greatly.

SSD: no mechanical seek head, so traditional cylinder-based scheduling has much less relevance.

Modern storage stacks can still schedule and merge I/O requests for latency, throughput, fairness and device characteristics, but the reason is no longer simply mechanical head movement.

Disk Scheduling in Modern Systems

Real operating systems may use more advanced I/O schedulers than the classic textbook algorithms.

Storage controllers can also perform their own request reordering. Modern HDDs may support command queuing, while SSD and NVMe devices have highly different internal architectures.

FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK remain extremely important because they teach the core principles of request ordering, seek optimisation, fairness and starvation.

Related Disk Scheduling Variants

N-Step SCAN Divides the request queue into batches and processes each batch using SCAN-style movement.

FSCAN Uses separate queues so that newly arriving requests do not continuously disturb the current SCAN sweep.

Deadline-Based Scheduling Modern systems can consider request deadlines and latency, not only cylinder position.

Best Method to Solve Disk Scheduling Numericals

1. Write the complete request queue exactly as given.
2. Note the initial disk-head position.
3. Note minimum and maximum cylinder numbers.
4. For SCAN-family algorithms, write the initial direction.
5. Arrange requests only when the chosen algorithm requires it.
6. Write the complete service route.
7. Calculate absolute movement between every two consecutive positions.
8. Add all movements carefully.
9. Recheck boundary movement for SCAN and C-SCAN.
10. Recheck circular jump for C-SCAN and C-LOOK.

Interactive Disk Scheduling Simulator

Enter your own request queue, initial head position, disk range, direction and algorithm.

FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK Simulator

Request Queue

Initial Head

Maximum Cylinder

Algorithm FCFS SSTF SCAN C-SCAN LOOK C-LOOK

Initial Direction Toward Higher Cylinders Toward Lower Cylinders

One-Minute Disk Scheduling Revision

Disk Scheduling Selects the order of pending disk I/O requests.

Seek Time Time required to move the disk head.

FCFS Serve requests in arrival order.

SSTF Serve nearest request first.

SCAN Move to disk end and reverse.

C-SCAN Serve in one direction and circularly return.

LOOK Reverse at last pending request.

C-LOOK Circular movement between extreme pending requests.

SSTF Problem Far requests may suffer starvation.

Disk Scheduling Algorithms Exam Preparation

2-Mark Definition

Disk Scheduling is the operating-system technique used to determine the order in which pending disk I/O requests are serviced.

FCFS

FCFS serves disk requests in the same order in which they arrive.

SSTF

SSTF selects the pending request closest to the current disk-head position.

SCAN

SCAN moves the disk head in one direction, servicing requests on the way until the disk boundary is reached, then reverses direction.

C-SCAN

C-SCAN serves requests in one direction only. After reaching one disk end, the head returns to the opposite end and continues in the same direction.

LOOK

LOOK works like SCAN but reverses at the last pending request instead of travelling to the physical disk boundary.

C-LOOK

C-LOOK serves requests in one direction up to the final pending request, then jumps to the first pending request on the other side.

Important Numerical Formula

Total Head Movement = Sum of absolute differences between consecutive head positions Average Head Movement = Total Head Movement / Number of Requests

For a 5-Mark Answer

1. Define Disk Scheduling.
2. Explain seek time.
3. Define FCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK.
4. Mention starvation in SSTF.
5. Write one difference table.

For a 10-Mark Answer

1. Hard disk structure.
2. Track, sector, cylinder and head.
3. Seek time.
4. Rotational latency.
5. Need for Disk Scheduling.
6. FCFS working and numerical.
7. SSTF working and numerical.
8. SSTF starvation.
9. SCAN working and numerical.
10. C-SCAN working and numerical.
11. LOOK working and numerical.
12. C-LOOK working and numerical.
13. Comparison table.
14. Advantages and disadvantages.
15. HDD vs SSD relevance.

Frequently Asked Questions

What is Disk Scheduling in Operating System?

Disk Scheduling is the operating-system technique used to decide the order in which pending disk I/O requests should be serviced.

Why is Disk Scheduling needed?

Disk Scheduling helps reduce unnecessary head movement, seek time and waiting time while improving disk throughput.

What is FCFS Disk Scheduling?

FCFS serves requests in the same order in which they arrive.

What is SSTF Disk Scheduling?

SSTF selects the pending request closest to the current disk-head position.

Can SSTF cause starvation?

Yes. A request far from the current disk head may wait for a long time if nearby requests continue to arrive.

What is SCAN Disk Scheduling?

SCAN moves the head in one direction, serves requests along the path, reaches the disk boundary and then reverses direction.

Why is SCAN called the Elevator Algorithm?

SCAN behaves like an elevator that serves requests while moving in one direction and then reverses after reaching an end.

What is C-SCAN?

C-SCAN serves requests in one direction only and then returns to the opposite disk end before continuing in the same direction.

What is LOOK Disk Scheduling?

LOOK works like SCAN but reverses at the last pending request instead of travelling to the physical disk boundary.

What is C-LOOK Disk Scheduling?

C-LOOK is the circular version of LOOK. It serves requests in one direction, then jumps from the last request to the opposite extreme pending request.

What is the main difference between SCAN and LOOK?

SCAN goes to the physical disk boundary, while LOOK reverses at the last pending request.

What is the difference between C-SCAN and C-LOOK?

C-SCAN uses physical disk boundaries, while C-LOOK uses the highest and lowest pending requests.

Do SSDs need traditional Disk Scheduling?

SSDs do not have a mechanical disk head, so traditional seek-based cylinder scheduling is much less important. Modern operating systems may still schedule SSD I/O for other performance and fairness reasons.

Conclusion

Disk Scheduling Algorithms decide the order in which pending storage requests are processed.

For mechanical hard disks, good scheduling can reduce read/write-head movement and therefore reduce seek overhead.

FCFS is simple and follows arrival order, but can create large head movement.

SSTF chooses the nearest request and can reduce immediate movement, but far-away requests can suffer starvation.

SCAN provides an organised elevator-like sweep across cylinders.

C-SCAN serves requests in one direction to provide more uniform directional service.

LOOK improves the SCAN idea by avoiding unnecessary movement to a disk end where no request exists.

C-LOOK applies the same improvement to circular scanning.

These algorithms are especially important for understanding mechanical HDD behaviour, seek optimisation, starvation, fairness and storage I/O scheduling.

Final Memory Trick:

FCFS = Arrival Order

SSTF = Nearest Request

SCAN = Go to End and Reverse

C-SCAN = One Direction + Circular Return

LOOK = Reverse at Last Request

C-LOOK = Circular Jump Between Last Requests

SSTF = Starvation Possible

LOOK = SCAN Without Unnecessary Boundary Travel