SCAN (elevator algorithm) in Operating Systems - Step-by-Step Execution

Concept Flow - SCAN (elevator algorithm)

Start at initial head position

↓

Move head in one direction

↓

Serve requests in order

↓

Reach end of disk

↓

Reverse direction

↓

Serve remaining requests

↓

End

The SCAN algorithm moves the disk head in one direction, serving requests as it goes, then reverses at the end to serve remaining requests.

Execution Sample

Operating Systems

Requests = [10, 22, 20, 2, 40, 6]
Head = 15
Direction = up
# Serve requests while moving up
# Reverse at end
# Serve requests moving down

This simulates the SCAN algorithm serving disk requests starting at position 15 moving upwards first.

Analysis Table

Step	Head Position	Direction	Request Served	Action
1	15	up	20	Move up, serve 20 (closest above 15)
2	20	up	22	Move up, serve 22
3	22	up	40	Move up, serve 40
4	40	up	None	Reached end, reverse direction
5	40	down	10	Move down, serve 10
6	10	down	6	Move down, serve 6
7	6	down	2	Move down, serve 2
8	2	down	None	Reached start, end

💡 All requests served; head reached both ends and reversed direction once.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
Head Position	15	20	22	40	40	10	6	2	2
Direction	up	up	up	up	down	down	down	down	down
Requests Served	[]	[20]	[20,22]	[20,22,40]	[20,22,40]	[20,22,40,10]	[20,22,40,10,6]	[20,22,40,10,6,2]	[20,22,40,10,6,2]

Key Insights - 2 Insights

Why does the head reverse direction only after reaching the end of the disk?

Because SCAN moves the head in one direction serving all requests until it reaches the disk's end, then reverses to serve remaining requests, as shown in steps 4 and 5 in the execution_table.

Why are requests served in order as the head moves?

SCAN serves requests in the order the head encounters them while moving in one direction, ensuring efficient servicing without jumping back and forth, as seen in steps 1 to 3 and 5 to 7.

Visual Quiz - 3 Questions

Look at the execution_table, what is the head position at step 3?

A 20

B 22

C 40

D 15

💡 Hint

Check the 'Head Position' column at step 3 in the execution_table.

At which step does the head reverse direction?

A Step 5

B Step 3

C Step 4

D Step 7

💡 Hint

Look for the 'Action' column mentioning reversing direction in the execution_table.

If the initial head position was 5 instead of 15, which request would be served first?

A 6

B 2

C 10

D 20

💡 Hint

With head at 5 moving up, the closest request above 5 is served first, see variable_tracker for similar logic.

Concept Snapshot

SCAN (Elevator Algorithm):
- Disk head moves in one direction serving requests in order.
- Upon reaching disk end, head reverses direction.
- Efficiently reduces seek time by servicing requests on the way.
- Like an elevator moving up and down serving floors.
- Ensures no starvation of requests in either direction.

Full Transcript

The SCAN algorithm starts the disk head at an initial position and moves it in one direction, serving requests as it encounters them. When the head reaches the end of the disk, it reverses direction and serves remaining requests on the way back. This process continues until all requests are served. The execution table shows the head moving up from position 15, serving requests at 20, 22, and 40, then reversing direction at the end and moving down to serve requests at 10, 6, and 2. Variables like head position and direction change step-by-step, illustrating the algorithm's flow. Key points include the head reversing only at disk ends and serving requests in order along the path, which helps reduce seek time and prevents starvation. The visual quiz tests understanding of head positions, direction changes, and request servicing order. SCAN is often compared to an elevator moving up and down floors, efficiently serving requests in both directions.