FCFS Scheduling - Convoy Effect & Waiting Time

▶

Steps

setup

Initialize Processes and Ready Queue

All processes are created with their arrival and burst times. The ready queue is empty initially because only P1 has arrived at time 0.

💡 Initialization sets the stage for scheduling by defining process attributes and starting conditions.

Line:

processes = [P1, P2, P3, P4]
current_time = 0
ready_queue = []

💡 Processes have arrival times and burst times; scheduling starts at time 0 with processes that have arrived.

traverse

Start Running P1

CPU starts executing process P1, which arrived first and is ready. P1 runs from time 0 to 5 (its full burst).

💡 FCFS runs the first arrived process fully before moving on, so P1 runs uninterrupted.

Line:

running_pid = ready_queue.pop(0)
current_time += processes[running_pid].burst_remaining

💡 FCFS scheduling picks the earliest arrived ready process to run to completion.

traverse

Advance Time to 5, P1 Completes

P1 finishes at time 5. Meanwhile, P2, P3, and P4 have arrived and are moved to the ready queue.

💡 Time advances by P1's burst; other processes arrive during this time and wait in ready queue.

Line:

current_time = 5
ready_queue.extend([P2, P3, P4])

💡 Processes arriving during execution wait in the ready queue; CPU is busy until current process finishes.

traverse

Start Running P2

Next, P2 is dequeued and starts running at time 5. It will run for its full burst of 3 units.

💡 FCFS picks the next process in arrival order from the ready queue to run next.

Line:

running_pid = ready_queue.pop(0)
current_time += processes[running_pid].burst_remaining

💡 Processes run in strict arrival order; no preemption occurs.

traverse

Advance Time to 8, P2 Completes

P2 finishes at time 8. P3 and P4 remain in the ready queue waiting for CPU.

💡 CPU time advances by P2's burst; other processes wait their turn.

Line:

current_time = 8

💡 Processes wait in queue until CPU is free; no process can interrupt the running one.

traverse

Start Running P3

P3 starts running at time 8 and will run for its full burst of 8 units.

💡 FCFS continues to run processes in arrival order without interruption.

Line:

running_pid = ready_queue.pop(0)
current_time += processes[running_pid].burst_remaining

💡 Long burst times cause later processes to wait longer, illustrating convoy effect.

traverse

Advance Time to 16, P3 Completes

P3 finishes at time 16. P4 remains in ready queue waiting for CPU.

💡 Long burst of P3 causes P4 to wait longer, demonstrating convoy effect.

Line:

current_time = 16

💡 Long running processes delay all subsequent processes in FCFS.

traverse

Start Running P4

P4 starts running at time 16 and will run for its full burst of 6 units.

💡 P4 must wait for all previous processes to finish, showing waiting time accumulation.

Line:

running_pid = ready_queue.pop(0)
current_time += processes[running_pid].burst_remaining

💡 Processes arriving earlier but with shorter bursts do not get priority in FCFS.

traverse

Advance Time to 22, P4 Completes

P4 finishes at time 22. All processes have now completed execution.

💡 CPU is idle after all processes finish; scheduling is complete.

Line:

current_time = 22

💡 Total elapsed time equals sum of all burst times plus waiting times.

reconstruct

Calculate Waiting and Turnaround Times

Calculate waiting time and turnaround time for each process based on completion and arrival times.

💡 These metrics quantify the convoy effect and overall scheduling efficiency.

Line:

waiting_time = start_time - arrival_time
turnaround_time = completion_time - arrival_time

💡 Waiting time accumulates for later processes due to earlier long bursts.

reconstruct

Display Final Average Waiting and Turnaround Times

Compute and display average waiting time (6.5) and average turnaround time (13.5) for all processes.

💡 These averages summarize the overall scheduling performance and convoy effect impact.

Line:

avg_waiting_time = sum(waiting_times) / n
avg_turnaround_time = sum(turnaround_times) / n

💡 Convoy effect causes higher average waiting time in FCFS scheduling.

class Process:
    def __init__(self, pid, arrival, burst):
        self.pid = pid
        self.arrival = arrival
        self.burst = burst
        self.remaining = burst
        self.state = 'new'

processes = [Process('P1',0,5), Process('P2',1,3), Process('P3',2,8), Process('P4',3,6)]
current_time = 0
ready_queue = []
completed = []

# STEP 1: Initialize ready queue with processes arrived at time 0
for p in processes:
    if p.arrival <= current_time:
        p.state = 'ready'
        ready_queue.append(p)

while ready_queue:
    # STEP 2: Pick first process in ready queue
    current = ready_queue.pop(0)
    current.state = 'running'
    # STEP 3: Run process to completion
    current_time = max(current_time, current.arrival) + current.burst
    current.remaining = 0
    current.state = 'terminated'
    completed.append(current)
    # STEP 4: Add newly arrived processes to ready queue
    for p in processes:
        if p.state == 'new' and p.arrival <= current_time:
            p.state = 'ready'
            ready_queue.append(p)

# STEP 5: Calculate waiting and turnaround times
waiting_times = []
turnaround_times = []
start_time = 0
for p in completed:
    wait = start_time - p.arrival
    if wait < 0:
        wait = 0
    turnaround = wait + p.burst
    waiting_times.append(wait)
    turnaround_times.append(turnaround)
    start_time += p.burst

avg_waiting_time = sum(waiting_times) / len(waiting_times)
avg_turnaround_time = sum(turnaround_times) / len(turnaround_times)

# STEP 6: Output results
print(f"Average Waiting Time = {avg_waiting_time}")
print(f"Average Turnaround Time = {avg_turnaround_time}")

📊

FCFS Scheduling - Convoy Effect & Waiting Time - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how process order and burst times affect waiting times, which is hard to grasp from code alone.

Transition new → ready pid:P1 - arrival at time 0

P1

ready

burst: 5

P2

new

burst: 3

P3

new

burst: 8

P4

new

burst: 6

Ready Queue

P1

Waiting Queue

P2 (arrival_time)P3 (arrival_time)P4 (arrival_time)

🖥CPUidlet=0

Transition ready → running pid:P1 - start execution

P1

running

burst: 5

P2

new

burst: 3

P3

new

burst: 8

P4

new

burst: 6

Ready Queue

empty

Waiting Queue

P2 (arrival_time)P3 (arrival_time)P4 (arrival_time)

🖥CPUP1t=0

Transition running → terminated pid:P1 - burst complete

P1

terminated

burst: 0

P2

ready

burst: 3

P3

ready

burst: 8

P4

ready

burst: 6

Ready Queue

P2P3P4

Waiting Queue

empty

🖥CPUidlet=5

P1

Transition ready → running pid:P2 - start execution

P2

running

burst: 3

P3

ready

burst: 8

P4

ready

burst: 6

Ready Queue

P3P4

Waiting Queue

empty

🖥CPUP2t=5

P1

Transition running → terminated pid:P2 - burst complete

P2

terminated

burst: 0

P3

ready

burst: 8

P4

ready

burst: 6

Ready Queue

P3P4

Waiting Queue

empty

🖥CPUidlet=8

P1

P2

Transition ready → running pid:P3 - start execution

P3

running

burst: 8

P4

ready

burst: 6

Ready Queue

P4

Waiting Queue

empty

🖥CPUP3t=8

P1

P2

Transition running → terminated pid:P3 - burst complete

P3

terminated

burst: 0

P4

ready

burst: 6

Ready Queue

P4

Waiting Queue

empty

🖥CPUidlet=16

P1

P2

P3

Transition ready → running pid:P4 - start execution

P4

running

burst: 6

Ready Queue

empty

Waiting Queue

empty

🖥CPUP4t=16

P1

P2

P3

Transition running → terminated pid:P4 - burst complete

P4

terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=22

P1

P2

P3

P4

P1

terminated

burst: 0

P2

terminated

burst: 0

P3

terminated

burst: 0

P4

terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=22

P1

P2

P3

P4

P1

terminated

burst: 0

P2

terminated

burst: 0

P3

terminated

burst: 0

P4

terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=22

P1

P2

P3

P4

Key Takeaways

✓ FCFS scheduling runs processes in strict arrival order without preemption, causing long processes to delay all subsequent ones.

This convoy effect is difficult to visualize from code alone but becomes clear when watching the Gantt chart build step-by-step.

✓ Waiting time accumulates for later processes because they must wait for all earlier processes to finish, regardless of their own burst times.

Seeing the ready queue and CPU state at each step helps understand how waiting time builds up.

✓ The Gantt chart visually shows how CPU time is allocated sequentially, making it easy to identify bottlenecks caused by long bursts.

This visual insight clarifies why average waiting time can be high even if some processes arrive early.

Practice

1. Trace the steps of address translation in a paging system when a process accesses a virtual address. Which sequence correctly describes the translation?

easy

A. Extract page number -> consult segment table -> get frame number -> add offset

B. Extract page number -> consult page table -> get frame number -> add offset

C. Extract segment number -> consult page table -> get frame number -> add offset

D. Extract segment number -> consult segment table -> get frame number -> add offset

Solution

1. Step 1: Identify paging address structure

   Paging virtual address splits into page number and offset.

2. Step 2: Consult page table

   Page number indexes into the page table to find the frame number.

3. Step 3: Calculate physical address

   Physical address = frame number concatenated with offset.

4. Step 4: Analyze options

   Extract page number -> consult page table -> get frame number -> add offset matches this sequence exactly.

5. Step 5: Why others are wrong

   Options B, C, and D incorrectly involve segment tables or segment numbers, which are not part of pure paging address translation.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Paging uses page tables, not segment tables, for translation.

Hint: Paging = page table; Segmentation = segment table

Common Mistakes:

• Confusing segment and page tables
• Mixing segment number with page table lookup
• Assuming segment tables are consulted in paging

2. Trace the sequence of state transitions for a process that requests I/O while running and then completes the I/O operation. What is the correct order of states the process goes through?

easy

A. Running -> Waiting -> Ready -> Running

B. Running -> Ready -> Waiting -> Running

C. Running -> Waiting -> Running -> Ready

D. Running -> Ready -> Running -> Waiting

Solution

1. Step 1: Identify the event

   The process requests I/O while Running, so it must wait for I/O completion.

2. Step 2: State transition on I/O request

   Process moves from Running to Waiting state to wait for I/O.

3. Step 3: After I/O completes

   Process moves from Waiting to Ready state, waiting for CPU scheduling.

4. Step 4: CPU scheduling

   Process moves from Ready to Running when CPU is allocated.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Running -> Waiting (I/O request), Waiting -> Ready (I/O done), Ready -> Running (CPU assigned) [OK]

Hint: I/O request moves process Running -> Waiting, then Waiting -> Ready after I/O completes [OK]

Common Mistakes:

• Confusing Ready and Waiting states order
• Assuming process goes directly from Waiting to Running
• Skipping the Ready state after I/O completion

3. Trace the sequence of events when a process exceeds its working set size causing thrashing. What happens step-by-step inside the system?

easy

A. The process generates page faults, the OS increases its frame allocation, and thrashing stops immediately

B. The process generates page faults, the OS swaps out pages not in the working set, but thrashing continues due to insufficient frames

C. The process generates page faults, the OS ignores them, and the process continues without delay

D. The process generates page faults, the OS reduces the number of processes to free frames, preventing thrashing

Solution

1. Step 1: Identify what happens when working set is exceeded

   The process causes frequent page faults because its active pages exceed allocated frames.

2. Step 2: OS response

   The OS attempts to swap out pages not in the working set to free frames, but if frames are insufficient, thrashing persists.

3. Step 3: Analyze options

   A is incorrect because OS cannot always increase frames immediately; thrashing may continue.
   B is correct as it describes the OS swapping out pages but thrashing continuing due to frame shortage.
   C is incorrect because OS does not ignore page faults.
   D is incorrect because load control (reducing processes) is a prevention technique but not an immediate response to page faults.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Thrashing occurs when working set exceeds frames; OS tries to swap but may fail if frames are insufficient.

Hint: Thrashing = page faults + insufficient frames despite swapping

Common Mistakes:

• Assuming OS can instantly allocate more frames
• Believing OS ignores page faults
• Confusing immediate load control with page fault handling

4. Which of the following statements about inodes is INCORRECT?

medium

A. Inodes store pointers to data blocks that hold the file's actual content.

B. An inode contains the file's name and its metadata such as permissions and timestamps.

C. Multiple directory entries can point to the same inode, enabling hard links.

D. Inodes are fixed-size structures that do not store file names.

Solution

1. Step 1: Clarify inode contents

   Inodes store metadata (permissions, timestamps, size) and pointers, but NOT file names.

2. Step 2: Confirm pointer role

   Inodes contain direct and indirect pointers to data blocks.

3. Step 3: Understand hard links

   Multiple directory entries can reference the same inode, enabling hard links.

4. Step 4: Recognize inode size

   Inodes are fixed-size and do not store variable-length file names.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   File names are stored in directory entries, not inodes [OK]

Hint: Inode = metadata + pointers; directory entry = file name + inode number

Common Mistakes:

• Assuming inodes store file names
• Confusing directory entries with inodes
• Believing inode size varies with file name length

5. Which of the following statements about segmentation is INCORRECT?

medium

A. Segmentation completely eliminates fragmentation issues

B. Segments can vary in size and represent logical units of a program

C. Segment tables store base and limit for each segment

D. Segmentation allows sharing of segments between processes

Solution

1. Step 1: Analyze Segments can vary in size and represent logical units of a program

   Segments are variable-sized logical units; this is correct.

2. Step 2: Analyze Segmentation completely eliminates fragmentation issues

   Segmentation does not eliminate fragmentation; it can cause external fragmentation.

3. Step 3: Analyze Segment tables store base and limit for each segment

   Segment tables store base and limit addresses; this is correct.

4. Step 4: Analyze Segmentation allows sharing of segments between processes

   Segmentation supports sharing segments like code segments; this is correct.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Fragmentation remains a problem in segmentation due to variable sizes.

Hint: Segmentation = variable size -> external fragmentation possible

Common Mistakes:

• Believing segmentation removes all fragmentation
• Confusing segment tables with page tables
• Assuming segments cannot be shared