FCFS disk scheduling in Operating Systems - Step-by-Step Execution

Concept Flow - FCFS disk scheduling

Start at initial head position

↓

Take next request in arrival order

↓

Move disk head to requested track

↓

Serve the request

↓

Check if more requests

↓

Repeat for next

FCFS disk scheduling serves disk requests in the exact order they arrive, moving the disk head sequentially to each requested track.

Execution Sample

Operating Systems

Initial head = 50
Requests = [82, 170, 43, 140, 24]
Serve requests in order
Calculate head movement each step

This example shows the disk head starting at track 50 and moving to each requested track in the order they arrive.

Analysis Table

Step	Current Head Position	Next Request	Head Movement	New Head Position
1	50	82	32 (82-50)	82
2	82	170	88 (170-82)	170
3	170	43	127 (170-43)	43
4	43	140	97 (140-43)	140
5	140	24	116 (140-24)	24
6	24	No more requests	0	24

💡 All requests served in arrival order; no more requests left.

State Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
Head Position	50	82	170	43	140	24	24
Request Served	None	82	170	43	140	24	All

Key Insights - 3 Insights

Why does the head sometimes move a large distance between requests?

Because FCFS serves requests strictly in arrival order without optimizing path, the head may jump far between distant tracks as shown in steps 2 and 3 in the execution_table.

Does FCFS reorder requests to reduce movement?

No, FCFS does not reorder requests; it always serves them in the order they arrive, which can cause inefficient head movement as seen in the execution_table.

What happens when there are no more requests?

The disk head stops moving, as shown in step 6 of the execution_table where no more requests remain.

Visual Quiz - 3 Questions

Look at the execution_table, what is the head position after serving the third request?

A 170

B 140

C 43

D 82

💡 Hint

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

At which step does the head move the greatest distance?

A Step 1

B Step 3

C Step 5

D Step 2

💡 Hint

Look at the 'Head Movement' values in the execution_table to find the largest number.

If the initial head position was 100 instead of 50, how would the head movement in step 1 change?

A It would decrease

B It would increase

C It would stay the same

D It would be zero

💡 Hint

Compare the initial head position and next request in step 1 from the variable_tracker and execution_table.

Concept Snapshot

FCFS Disk Scheduling:
- Serve disk requests in order of arrival
- Move head directly to each requested track
- Simple but can cause long head movements
- No reordering or optimization
- Easy to implement but may be inefficient

Full Transcript

FCFS disk scheduling works by serving disk requests in the exact order they arrive. Starting from an initial head position, the disk head moves to each requested track one by one. The execution table shows each step: the current head position, the next request, the distance the head moves, and the new head position. The head can move large distances if requests are far apart because FCFS does not reorder requests to minimize movement. When no requests remain, the disk head stops. This method is simple but can be inefficient due to potentially long head movements.

Practice

1. What does FCFS stand for in disk scheduling?

easy

A. Fastest-Cylinder First Service

B. First-Come, First-Served

C. Frequent Cylinder File System

D. First-Come, Fast-Served

Solution

1. Step 1: Understand the abbreviation FCFS

   FCFS is a common term in scheduling that means requests are handled in the order they arrive.

2. Step 2: Match the full form

   First-Come, First-Served matches the concept of serving requests in arrival order.

3. Final Answer:

   First-Come, First-Served -> Option B

4. Quick Check:

   FCFS = First-Come, First-Served [OK]

Hint: Remember FCFS means serve in arrival order [OK]

Common Mistakes:

• Confusing FCFS with other scheduling algorithms
• Thinking FCFS means fastest service
• Mixing up the abbreviation letters

2. Which of the following correctly describes the order in which FCFS disk scheduling processes requests?

easy

A. Processes requests in the order they arrive

B. Processes requests based on shortest seek time first

C. Processes requests starting from the outermost track

D. Processes requests based on priority levels

Solution

1. Step 1: Recall FCFS scheduling principle

   FCFS processes disk requests in the exact order they arrive without reordering.

2. Step 2: Compare options with FCFS behavior

   Only Processes requests in the order they arrive matches this behavior exactly.

3. Final Answer:

   Processes requests in the order they arrive -> Option A

4. Quick Check:

   FCFS = order of arrival [OK]

Hint: FCFS means no reordering, just arrival order [OK]

Common Mistakes:

• Choosing shortest seek time instead of arrival order
• Confusing with priority scheduling
• Assuming outermost track first

3. Given the disk queue requests at tracks [55, 58, 60, 70, 18] and the disk head starting at track 50, what is the total head movement using FCFS scheduling?

medium

A. 72

B. 80

C. 98

D. 85

Solution

1. Step 1: Calculate head movements in FCFS order

   Start at 50, move to 55 (5), then 58 (3), then 60 (2), then 70 (10), then 18 (52). Total = 5+3+2+10+52 = 72.

2. Step 2: Verify calculation carefully

   Recalculate: 5 + 3 + 2 + 10 + 52 = 72 confirmed.

3. Final Answer:

   72 -> Option A

4. Quick Check:

   Sum of movements = 72 [OK]

Hint: Add absolute differences in request order [OK]

Common Mistakes:

• Adding distances incorrectly
• Mixing request order
• Forgetting to include last move

4. Identify the error in this FCFS disk scheduling calculation: Starting at track 45, requests are [50, 40, 55]. The total head movement is calculated as |45-50| + |50-55| + |55-40| = 5 + 5 + 15 = 25. What is wrong?

medium

A. Starting track should be included twice

B. Absolute values should not be used

C. The total should be 30, not 25

D. The order of requests is incorrect in calculation

Solution

1. Step 1: Check the request order in calculation

   The requests are [50, 40, 55], so after 50, the head should move to 40, then 55.

2. Step 2: Verify the distances in correct order

   Calculate: |45-50|=5, |50-40|=10, |40-55|=15; total = 5+10+15=30, not 25.

3. Final Answer:

   The order of requests is incorrect in calculation -> Option D

4. Quick Check:

   Correct order matters for total movement [OK]

Hint: Follow request order exactly for distance sums [OK]

Common Mistakes:

• Mixing request order
• Ignoring absolute distance
• Miscounting starting position

5. A disk head starts at track 100. The request queue is [120, 10, 50, 90]. Using FCFS scheduling, what is the total head movement? How does this compare to SSTF (Shortest Seek Time First) scheduling for the same requests?

hard

A. FCFS: 200, SSTF: 90; SSTF reduces movement

B. FCFS: 100, SSTF: 100; Both equal

C. FCFS: 210, SSTF: 150; SSTF reduces movement

D. FCFS: 150, SSTF: 120; FCFS is better

Solution

1. Step 1: Calculate FCFS total head movement

   100->120 (20), 120->10 (110), 10->50 (40), 50->90 (40). Total = 20+110+40+40 = 210.

2. Step 2: Calculate SSTF total head movement

   From 100 closest is 90 (10)->90; closest 120 (30)->120; closest 50 (70)->50; then 10 (40). Total = 10+30+70+40 = 150.

3. Step 3: Compare

   SSTF (150) reduces movement compared to FCFS (210).

4. Final Answer:

   FCFS: 210, SSTF: 150; SSTF reduces movement -> Option C

5. Quick Check:

   SSTF reduces head movement compared to FCFS [OK]

Hint: SSTF picks closest request, reducing movement [OK]

Common Mistakes:

• Mixing request order in FCFS
• Misordering SSTF requests
• Ignoring large jumps in FCFS