SSTF (Shortest Seek Time First) in Operating Systems - Step-by-Step Execution

Concept Flow - SSTF (Shortest Seek Time First)

Start at current head position

↓

Calculate distance to each request

↓

Select request with shortest distance

↓

Move head to selected request

↓

Remove serviced request

↓

Are requests left?

No→End

↩Back to Calculate distance

SSTF chooses the disk request closest to the current head position, moves there, then repeats until all requests are served.

Execution Sample

Operating Systems

Requests = [55, 58, 39, 18, 90, 160, 150, 38, 184]
Head = 50
while requests:
  Find closest request to Head
  Move Head to it
  Remove request

This simulates SSTF disk scheduling by moving the head to the nearest request each time.

Analysis Table

Step	Current Head	Requests	Distances to Requests	Selected Request	Action	New Head
1	50	[55,58,39,18,90,160,150,38,184]	[5,8,11,32,40,110,100,12,134]	55	Move head to 55	55
2	55	[58,39,18,90,160,150,38,184]	[3,16,37,35,105,95,17,129]	58	Move head to 58	58
3	58	[39,18,90,160,150,38,184]	[19,40,32,102,92,20,126]	39	Move head to 39	39
4	39	[18,90,160,150,38,184]	[21,51,121,111,1,145]	38	Move head to 38	38
5	38	[18,90,160,150,184]	[20,52,122,112,146]	18	Move head to 18	18
6	18	[90,160,150,184]	[72,142,132,166]	90	Move head to 90	90
7	90	[160,150,184]	[70,60,94]	150	Move head to 150	150
8	150	[160,184]	[10,34]	160	Move head to 160	160
9	160	[184]	[24]	184	Move head to 184	184
10	184	[]	[]	None	All requests serviced	184

💡 All requests have been serviced; no requests remain.

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	Final
Head	50	55	58	39	38	18	90	150	160	184	184
Requests	[55,58,39,18,90,160,150,38,184]	[58,39,18,90,160,150,38,184]	[39,18,90,160,150,38,184]	[18,90,160,150,38,184]	[18,90,160,150,184]	[90,160,150,184]	[160,150,184]	[160,184]	[184]	[]	[]

Key Insights - 3 Insights

Why does SSTF sometimes cause longer wait times for some requests?

Because SSTF always picks the closest request next (see execution_table steps 3-5), requests far from the current head can wait longer, causing possible starvation.

How do we calculate which request is closest?

At each step (see execution_table column 'Distances to Requests'), we find the absolute difference between the current head and each request, then pick the smallest.

What happens when there are no requests left?

The algorithm stops (see execution_table step 10), as all requests have been serviced.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4. What is the current head position before moving?

A 38

B 58

C 39

D 55

💡 Hint

Check the 'Current Head' column at Step 4 in execution_table.

At which step does the head move to request 90?

A Step 6

B Step 5

C Step 7

D Step 8

💡 Hint

Look at the 'Selected Request' column in execution_table to find when 90 is chosen.

If the initial head was at 100 instead of 50, which request would SSTF select first?

A 150

B 90

C 58

D 55

💡 Hint

Compare distances from 100 to each request as done in execution_table's 'Distances to Requests' column.

Concept Snapshot

SSTF (Shortest Seek Time First):
- Always pick the request closest to current head.
- Calculate absolute distance to all requests.
- Move head to nearest request and remove it.
- Repeat until all requests are served.
- Can cause starvation for far requests.

Full Transcript

SSTF is a disk scheduling method where the disk head moves to the closest pending request next. Starting from the current head position, it calculates the distance to all requests, picks the shortest one, moves the head there, and removes that request from the queue. This repeats until no requests remain. The execution table shows each step with the head position, requests left, distances, and chosen request. SSTF is efficient but can cause some requests to wait longer if they are far from the current head position.

Practice

1. What does SSTF (Shortest Seek Time First) disk scheduling algorithm prioritize?

easy

A. The request closest to the current head position

B. The request that arrived first

C. The request farthest from the current head position

D. Requests in a fixed circular order

Solution

1. Step 1: Understand SSTF purpose

   SSTF aims to reduce the seek time by choosing the disk request nearest to the current head position.

2. Step 2: Compare options with SSTF behavior

   Only the request closest to the current head position matches this behavior; others describe different algorithms.

3. Final Answer:

   The request closest to the current head position -> Option A

4. Quick Check:

   SSTF = closest request [OK]

Hint: Pick the request nearest to the head position [OK]

Common Mistakes:

• Confusing SSTF with FCFS (First Come First Serve)
• Thinking SSTF picks requests in arrival order
• Assuming SSTF picks the farthest request

2. Which of the following is the correct way to describe SSTF in disk scheduling?

easy

A. It processes requests in the order they arrive.

B. It selects the request with the longest waiting time first.

C. It selects the request closest to the current head position.

D. It moves the head in one direction servicing all requests.

Solution

1. Step 1: Review SSTF definition

   SSTF selects the disk request closest to the current head position to minimize seek time.

2. Step 2: Match options with SSTF behavior

   The option "It selects the request closest to the current head position." correctly describes SSTF. Other options describe different algorithms like FCFS or SCAN.

3. Final Answer:

   It selects the request closest to the current head position. -> Option C

4. Quick Check:

   SSTF = closest request selection [OK]

Hint: Remember SSTF picks nearest request, not oldest [OK]

Common Mistakes:

• Mixing SSTF with FCFS or SCAN algorithms
• Assuming SSTF picks requests by waiting time
• Confusing direction-based scheduling with SSTF

3. Given the disk head is at position 50 and requests are at positions [45, 70, 10, 55], which request will SSTF service first?

medium

A. 45

B. 70

C. 10

D. 55

Solution

1. Step 1: Calculate distances from head position 50

   Distances: 45 (5), 70 (20), 10 (40), 55 (5)

2. Step 2: Identify closest request

   Requests at 45 and 55 are both 5 units away. SSTF can pick either, but usually picks the first closest found, here 45.

3. Final Answer:

   45 -> Option A

4. Quick Check:

   Closest request = 45 [OK]

Hint: Calculate absolute distance, pick smallest [OK]

Common Mistakes:

• Choosing the farthest request by mistake
• Ignoring equal distances and picking wrong one
• Confusing SSTF with FCFS order

4. A disk head is at position 30. Requests are at [35, 25, 40, 20]. A student incorrectly picks 40 as the next request in SSTF. What is the error?

medium

A. They ignored the current head position.

B. They chose the farthest request instead of the closest.

C. They picked the request with the longest waiting time.

D. They selected requests in arrival order.

Solution

1. Step 1: Calculate distances from head position 30

   Distances: 35 (5), 25 (5), 40 (10), 20 (10)

2. Step 2: Identify correct SSTF choice

   Closest requests are 35 and 25 (5 units away). Choosing 40 (10 units) is incorrect.

3. Final Answer:

   They chose the farthest request instead of the closest. -> Option B

4. Quick Check:

   SSTF picks closest, not farthest [OK]

Hint: Always pick request with minimum distance [OK]

Common Mistakes:

• Picking requests based on arrival time
• Ignoring actual distances from head
• Confusing SSTF with other algorithms

5. A disk head starts at position 100. The request queue is [120, 89, 130, 80, 110]. Using SSTF, what is the order in which requests will be serviced?

hard

A. [110, 120, 130, 89, 80]

B. [89, 80, 110, 120, 130]

C. [110, 120, 89, 80, 130]

D. [110, 89, 80, 120, 130]

Solution

1. Step 1: Start at head position 100 and find closest request

   Distances: 120(20), 89(11), 130(30), 80(20), 110(10). Closest is 110 (10 units).

2. Step 2: Move head to 110 and repeat

   Remaining: 120(10), 89(21), 130(20), 80(30). Closest is 120 (10).

3. Step 3: Move head to 120 and repeat

   Remaining: 89(31), 130(10), 80(40). Closest is 130 (10).

4. Step 4: Move head to 130 and repeat

   Remaining: 89(41), 80(50). Closest is 89 (41).

5. Step 5: Move head to 89 and last request is 80 (9 away)

   Order: 110, 120, 130, 89, 80.

6. Final Answer:

   [110, 120, 130, 89, 80] -> Option D

7. Quick Check:

   SSTF services closest request each step [OK]

Hint: Pick closest request step-by-step from current head [OK]

Common Mistakes:

• Not updating head position after each request
• Choosing requests by arrival order
• Ignoring equal distances and picking wrong request