SCAN (elevator algorithm) in Operating Systems - Deep Dive

Overview - SCAN (elevator algorithm)

What is it?

The SCAN algorithm, also known as the elevator algorithm, is a method used by operating systems to schedule disk input/output requests. It works by moving the disk arm in one direction, servicing all requests along the way until it reaches the end, then reversing direction and servicing requests on the return trip. This approach reduces the total movement of the disk arm compared to simpler methods.

Why it matters

Without efficient disk scheduling like SCAN, the disk arm would move back and forth randomly, causing slow data access and poor system performance. SCAN helps minimize delays by organizing requests in a way that reduces unnecessary movement, making computers faster and more responsive when reading or writing data.

Where it fits

Before learning SCAN, you should understand basic disk structure and simple scheduling methods like First-Come-First-Served (FCFS). After SCAN, learners can explore more advanced algorithms like C-SCAN and LOOK, which improve on SCAN's efficiency and fairness.

Mental Model

Core Idea

SCAN moves the disk arm like an elevator, servicing requests in one direction until the end, then reversing, to minimize arm movement and reduce wait times.

Think of it like...

Imagine an elevator in a building that picks up and drops off passengers only while moving in one direction, then reverses at the top or bottom floor to serve requests going the other way. This avoids unnecessary trips up and down.

Disk Arm Movement:
┌─────────────┐
│ Start       │
│             │
│ → → → → → → │  (Arm moves in one direction servicing requests)
│             │
│             │
│ ← ← ← ← ← ← │  (Arm reverses direction and services requests back)
└─────────────┘

Build-Up - 6 Steps

1

Foundation

Understanding Disk Arm Movement Basics

Concept: Learn how a disk arm moves to read/write data on disk tracks.

A hard disk has many circular tracks. The disk arm moves across these tracks to access data. Moving the arm takes time, so minimizing movement speeds up data access.

Result

You understand that disk arm movement affects how fast data can be read or written.

Knowing that arm movement is costly helps explain why scheduling algorithms focus on reducing unnecessary travel.

2

Foundation

Simple Disk Scheduling: FCFS Explained

Concept: First-Come-First-Served (FCFS) schedules disk requests in the order they arrive without reordering.

Requests are handled one by one as they come. If the arm is far from the next request, it moves all the way there, even if it means jumping back and forth.

Result

Disk arm may move inefficiently, causing longer wait times.

FCFS is easy but can cause slow performance due to random arm movement.

3

Intermediate

SCAN Algorithm Mechanics

Concept: SCAN moves the disk arm in one direction, servicing all requests until the end, then reverses direction.

The disk arm starts moving toward one end of the disk. It services all requests on its path. When it reaches the last track in that direction, it reverses and services requests on the way back.

Result

Disk arm movement is more organized and efficient than FCFS.

Organizing requests by direction reduces wasted movement and improves average wait time.

4

Intermediate

Comparing SCAN to FCFS and SSTF

🤔Before reading on: Do you think SCAN always results in the shortest wait time compared to FCFS and SSTF? Commit to your answer.

Concept: SCAN balances fairness and efficiency better than FCFS and SSTF but may not always minimize wait time.

FCFS is simple but inefficient. SSTF (Shortest Seek Time First) picks the closest request next but can starve far requests. SCAN moves systematically, preventing starvation and reducing arm movement.

Result

SCAN provides a good compromise between fairness and efficiency.

Understanding trade-offs helps choose the right algorithm for different system needs.

5

Advanced

Handling Edge Cases in SCAN

🤔Before reading on: Does SCAN always service requests at the disk ends immediately? Commit to yes or no.

Concept: SCAN services requests in one direction fully before reversing, which can delay requests near the opposite end until the arm returns.

If requests arrive near the far end just after the arm passes, they must wait for the arm to go all the way to the end and back. This can cause longer wait times for some requests.

Result

Some requests may experience delays depending on their position and arrival time.

Knowing SCAN's behavior with edge requests helps anticipate and mitigate delays.

6

Expert

SCAN Algorithm in Modern Systems

🤔Before reading on: Do modern systems still use SCAN exactly as originally designed? Commit to yes or no.

Concept: Modern systems often use variations of SCAN, like LOOK or C-SCAN, to improve efficiency and fairness.

LOOK stops the arm at the last request in each direction instead of going to the disk end, reducing unnecessary movement. C-SCAN treats the disk as circular, jumping back to the start after reaching the end to provide more uniform wait times.

Result

These variations optimize SCAN's basic idea for better performance in real systems.

Understanding SCAN's evolution reveals how practical needs shape algorithm design.

Under the Hood

The disk arm moves physically across tracks. SCAN schedules requests by sorting them by track number and moving the arm in one direction, servicing requests in order. When the arm reaches the last track in that direction, it reverses. This reduces the total seek time by avoiding random jumps.

Why designed this way?

SCAN was designed to reduce the inefficiency of FCFS and the starvation risk of SSTF. By moving the arm like an elevator, it ensures all requests in one direction are serviced fairly before reversing, balancing efficiency and fairness.

Request Queue Sorted by Track Number:
┌─────────────────────────────┐
│ Track 0                    199│
│ Requests: 10, 35, 70, 120, 150│
│                             │
│ Arm moves → servicing 10, 35, 70, 120, 150
│ Then reverses ← (if any requests) 
└─────────────────────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does SCAN always minimize the total seek time compared to all other algorithms? Commit to yes or no.

Common Belief: SCAN always gives the shortest total seek time because it moves in one direction systematically.

Reality: While SCAN reduces seek time compared to FCFS, it does not always minimize total seek time. Algorithms like SSTF can sometimes have shorter seek times but risk starvation.

Why it matters: Believing SCAN is always optimal can lead to ignoring better algorithms for specific workloads, causing suboptimal performance.

Quick: Does SCAN prevent starvation of all requests? Commit to yes or no.

Common Belief: SCAN completely prevents starvation because it services requests in order along the arm's path.

Reality: SCAN reduces starvation risk but can still delay requests near the far end if they arrive just after the arm passes, causing them to wait for a full arm sweep.

Why it matters: Assuming no starvation can cause unexpected delays in time-sensitive applications.

Quick: Does SCAN always move the arm to the physical end of the disk? Commit to yes or no.

Common Belief: SCAN always moves the disk arm to the very end track before reversing direction.

Reality: Basic SCAN does, but variations like LOOK stop at the last requested track, avoiding unnecessary movement.

Why it matters: Misunderstanding this can lead to inefficient implementations that waste time moving to unused tracks.

Expert Zone

1

SCAN's performance depends heavily on the distribution and arrival times of requests; clustered requests can cause uneven wait times.

2

The choice of initial arm direction affects average wait time; some systems dynamically choose direction based on current requests.

3

Implementations must handle new requests arriving during arm movement carefully to avoid starvation or unfair delays.

When NOT to use

Avoid SCAN in systems with highly random or sparse requests where SSTF or C-SCAN might provide better average response times. For real-time systems requiring strict fairness, consider algorithms with guaranteed maximum wait times.

Production Patterns

In production, SCAN is often used as a base for more advanced algorithms like LOOK and C-SCAN. Systems may combine SCAN with request prioritization or batching to optimize throughput and fairness under varying workloads.

Connections

Elevator Control Systems

SCAN is inspired by elevator movement patterns that serve requests in one direction before reversing.

Understanding elevator scheduling helps grasp how SCAN balances efficiency and fairness in disk arm movement.

Shortest Seek Time First (SSTF)

SSTF and SCAN both aim to reduce disk arm movement but use different strategies; SSTF picks the closest request next, SCAN moves directionally.

Comparing these algorithms highlights trade-offs between minimizing seek time and preventing starvation.

Traffic Signal Timing

Like SCAN schedules disk requests directionally, traffic signals manage vehicle flow in one direction before switching, optimizing movement and reducing wait times.

Recognizing similar scheduling principles in traffic control deepens understanding of SCAN's approach to managing competing demands efficiently.

Common Pitfalls

#1 Ignoring new requests arriving during arm movement, causing starvation.

Wrong approach:

Process all requests present at start only; ignore new requests until next sweep.

Correct approach:

Continuously add new requests to the queue and service them in the current direction if possible.

Root cause:

Misunderstanding that SCAN must dynamically handle incoming requests to maintain fairness.

#2 Always moving the arm to the physical disk end even if no requests exist there.

Wrong approach:

Implement SCAN to move arm to track 0 or max track regardless of requests.

Correct approach:

Use LOOK variation to stop at the last requested track in each direction.

Root cause:

Not optimizing arm movement leads to wasted time and reduced efficiency.

#3 Choosing arm movement direction without considering current request distribution.

Wrong approach:

Always start moving arm in one fixed direction regardless of requests.

Correct approach:

Dynamically choose direction based on nearest requests to minimize wait time.

Root cause:

Static direction choice can increase average wait times unnecessarily.

Key Takeaways

SCAN schedules disk requests by moving the arm in one direction, servicing all requests before reversing, reducing unnecessary movement.

It balances efficiency and fairness better than simple methods like FCFS but can still delay some requests depending on their position.

Variations like LOOK and C-SCAN improve SCAN by avoiding unnecessary arm travel and providing more uniform wait times.

Understanding SCAN's mechanism helps in designing systems that optimize disk access and overall performance.

Recognizing SCAN's limitations and trade-offs is essential for choosing the right disk scheduling algorithm for specific workloads.