Context Switch - Cost & Causes

▶

Steps

setup

Initialize Processes and Ready Queue

The scheduler initializes three processes P1, P2, and P3 with their CPU burst times and priorities. All processes start in the ready state, waiting to be scheduled.

💡 Initialization sets up the environment so we can observe how the scheduler manages multiple processes and triggers context switches.

Line:

processes = [P1, P2, P3]
ready_queue = [P1, P2, P3]
active_pid = null

💡 The scheduler starts with all processes ready but none running yet.

setup

Schedule First Process (P1) to Run

The scheduler selects the highest priority process P1 to run first. P1 state changes from ready to running, and it is removed from the ready queue.

💡 This step shows how the scheduler picks the first process to run based on priority.

Line:

active_pid = ready_queue.pop(0)
processes[active_pid].state = 'running'

💡 The scheduler always picks the highest priority ready process to run next.

traverse

P1 Executes for 2 Time Units

Process P1 runs on the CPU for 2 time units, reducing its remaining burst time from 5 to 3.

💡 This step shows CPU time passing and how the running process's burst time decreases.

Line:

processes[active_pid].burst_remaining -= 2
cpu_register.time_elapsed += 2

💡 Running a process consumes CPU time and reduces its remaining burst.

compare

Context Switch: Preempt P1 for Higher Priority P2

Process P2's priority is increased to 4, higher than P1's priority of 3, triggering a context switch. P1 is moved back to ready, and P2 is scheduled to run.

💡 This step highlights a preemptive context switch caused by a higher priority process becoming ready.

Line:

if processes['P2'].priority > processes[active_pid].priority:
    context_switch()

💡 Context switches occur when a higher priority process arrives, forcing the CPU to switch tasks.

expand

Context Switch Overhead Consumes 1 Time Unit

The CPU spends 1 time unit performing the context switch, during which no process runs. This overhead reduces CPU efficiency.

💡 Context switches are not free; they consume CPU time and cause delays.

Line:

cpu_register.time_elapsed += 1  # context switch overhead

💡 Context switch overhead adds latency and reduces effective CPU time for processes.

traverse

P2 Executes for 3 Time Units

Process P2 runs for its full remaining burst of 3 time units, completing its execution.

💡 This step shows a process running to completion after a context switch.

Line:

processes[active_pid].burst_remaining -= 3
cpu_register.time_elapsed += 3

💡 Processes run until completion or preemption; here P2 completes.

insert

Schedule Next Process (P1) to Run

With P2 terminated, the scheduler selects P1 again to run since it has the highest priority among ready processes.

💡 This step shows how the scheduler picks the next process after one finishes.

Line:

active_pid = ready_queue.pop(0)
processes[active_pid].state = 'running'

💡 Scheduler picks next process from ready queue after termination.

expand

Context Switch Overhead for Switching to P1

The CPU spends 1 time unit performing the context switch to P1, during which no process runs.

💡 Every context switch incurs overhead, even when switching to a previously running process.

Line:

cpu_register.time_elapsed += 1  # context switch overhead

💡 Context switch overhead is a constant cost for switching processes.

traverse

P1 Executes Remaining 3 Time Units

Process P1 runs for its remaining 3 time units, completing its execution.

💡 This step shows process completion after resuming from preemption.

Line:

processes[active_pid].burst_remaining -= 3
cpu_register.time_elapsed += 3

💡 Processes can be preempted and later resumed to finish execution.

insert

Schedule Last Process (P3) to Run

With P1 and P2 terminated, the scheduler selects the last remaining process P3 to run.

💡 This step shows the scheduler handling the last process in the queue.

Line:

active_pid = ready_queue.pop(0)
processes[active_pid].state = 'running'

💡 Scheduler continues until all processes terminate.

expand

Context Switch Overhead for Switching to P3

The CPU spends 1 time unit performing the context switch to P3, causing idle CPU time.

💡 Even switching to the last process incurs overhead.

Line:

cpu_register.time_elapsed += 1  # context switch overhead

💡 Context switch overhead accumulates with each switch.

traverse

P3 Executes for 4 Time Units and Completes

Process P3 runs for its full burst time of 4 units and terminates.

💡 This final step shows the last process completing execution.

Line:

processes[active_pid].burst_remaining -= 4
cpu_register.time_elapsed += 4
processes[active_pid].state = 'terminated'

💡 All processes have now completed, ending the scheduling cycle.

processes = {
    'P1': {'priority': 3, 'burst_remaining': 5, 'state': 'ready'},  # STEP 1
    'P2': {'priority': 2, 'burst_remaining': 3, 'state': 'ready'},
    'P3': {'priority': 1, 'burst_remaining': 4, 'state': 'ready'}
}
ready_queue = ['P1', 'P2', 'P3']
active_pid = None
cpu_register = {'running_pid': None, 'time_elapsed': 0}

def context_switch(new_pid):  # STEP 4,5,8,11
    global active_pid
    # Save current process state
    if active_pid is not None and processes[active_pid]['state'] == 'running':
        processes[active_pid]['state'] = 'ready'
        ready_queue.append(active_pid)
    # Context switch overhead
    cpu_register['time_elapsed'] += 1
    # Switch to new process
    active_pid = new_pid
    processes[active_pid]['state'] = 'running'
    ready_queue.remove(active_pid)
    cpu_register['running_pid'] = active_pid

# STEP 2
active_pid = ready_queue.pop(0)
processes[active_pid]['state'] = 'running'
cpu_register['running_pid'] = active_pid

# STEP 3
processes[active_pid]['burst_remaining'] -= 2
cpu_register['time_elapsed'] += 2

# STEP 4
# Simulate P2 priority increase to 4 to cause preemption
processes['P2']['priority'] = 4
if processes['P2']['priority'] > processes[active_pid]['priority']:
    context_switch('P2')

# STEP 6
processes[active_pid]['burst_remaining'] -= 3
cpu_register['time_elapsed'] += 3
processes[active_pid]['state'] = 'terminated'

# STEP 7
if ready_queue:
    next_pid = ready_queue[0]
    context_switch(next_pid)

# STEP 9
processes[active_pid]['burst_remaining'] -= 3
cpu_register['time_elapsed'] += 3
processes[active_pid]['state'] = 'terminated'

# STEP 10
if ready_queue:
    next_pid = ready_queue[0]
    context_switch(next_pid)

# STEP 12
processes[active_pid]['burst_remaining'] -= 4
cpu_register['time_elapsed'] += 4
processes[active_pid]['state'] = 'terminated'

📊

Context Switch - Cost & Causes - Watch the Algorithm Execute, Step by Step

Watching this step-by-step helps you understand how and why context switches happen, what triggers them, and how they impact CPU utilization.

P1

ready

burst: 5

P2

ready

burst: 3

P3

ready

burst: 4

Ready Queue

P1P2P3

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:P1 - highest priority selected

P1

running

burst: 5

P2

ready

burst: 3

P3

ready

burst: 4

Ready Queue

P2P3

Waiting Queue

empty

🖥CPUP1t=0

P1

running

burst: 3

P2

ready

burst: 3

P3

ready

burst: 4

Ready Queue

P2P3

Waiting Queue

empty

🖥CPUP1t=2

P1

Transition running → ready pid:P1 - preempted by higher priority P2

P1

ready

burst: 3

P2

running

burst: 3

P3

ready

burst: 4

Ready Queue

P1P3

Waiting Queue

empty

🖥CPUP2t=2

P1

P1

ready

burst: 3

P2

running

burst: 3

P3

ready

burst: 4

Ready Queue

P1P3

Waiting Queue

empty

🖥CPUP2t=3

P1

idle

P1

ready

burst: 3

P2

terminated

burst: 0

P3

ready

burst: 4

Ready Queue

P1P3

Waiting Queue

empty

🖥CPUP2t=6

P1

idle

P2

Transition ready → running pid:P1 - next highest priority

P1

running

burst: 3

P2

terminated

burst: 0

P3

ready

burst: 4

Ready Queue

P3

Waiting Queue

empty

🖥CPUP1t=6

P1

idle

P2

P1

running

burst: 3

P2

terminated

burst: 0

P3

ready

burst: 4

Ready Queue

P3

Waiting Queue

empty

🖥CPUP1t=7

P1

idle

P2

idle

P1

terminated

burst: 0

P2

terminated

burst: 0

P3

ready

burst: 4

Ready Queue

P3

Waiting Queue

empty

🖥CPUP1t=10

P1

idle

P2

idle

P1

Transition ready → running pid:P3 - last process

P1

terminated

burst: 0

P2

terminated

burst: 0

P3

running

burst: 4

Ready Queue

empty

Waiting Queue

empty

🖥CPUP3t=10

P1

idle

P2

idle

P1

P1

terminated

burst: 0

P2

terminated

burst: 0

P3

running

burst: 4

Ready Queue

empty

Waiting Queue

empty

🖥CPUP3t=11

P1

idle

P2

idle

P1

idle

P1

terminated

burst: 0

P2

terminated

burst: 0

P3

terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUP3t=15

P1

idle

P2

idle

P1

idle

P3

Key Takeaways

✓ Context switches occur when a higher priority process arrives or a running process completes.

This is hard to see from code alone because the timing and priority changes are dynamic and interleaved.

✓ Each context switch incurs a fixed overhead time during which no process runs, reducing CPU efficiency.

Visualizing the idle time during switches makes the cost of context switching concrete.

✓ Processes can be preempted and later resumed, showing how the scheduler manages multiple processes fairly.

Seeing the burst times decrease and states change stepwise clarifies preemption mechanics.

Practice

1. Which of the following statements about the 'Mutual Exclusion' condition in deadlock is INCORRECT?

medium

A. Mutual exclusion means that at least one resource must be held in a non-shareable mode.

B. Mutual exclusion can be eliminated for all resources to prevent deadlock.

C. Mutual exclusion is necessary for deadlock but not sufficient alone.

D. Mutual exclusion applies only to resources that cannot be simultaneously used by multiple processes.

Solution

1. Step 1: Understand mutual exclusion

   It requires that some resources be non-shareable, meaning only one process can use them at a time.

2. Step 2: Analyze why eliminating mutual exclusion for all resources is impractical

   Eliminating mutual exclusion for all resources is impossible because some resources (like printers) inherently cannot be shared.

3. Step 3: Evaluate other options

   Mutual exclusion means that at least one resource must be held in a non-shareable mode correctly defines mutual exclusion. Mutual exclusion is necessary for deadlock but not sufficient alone correctly states it is necessary but not sufficient. Mutual exclusion applies only to resources that cannot be simultaneously used by multiple processes correctly limits mutual exclusion to non-shareable resources.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Mutual exclusion cannot be eliminated for all resources; some must be exclusive.

Hint: Mutual exclusion is about non-shareable resources, which can't all be made shareable [OK]

Common Mistakes:

• Thinking mutual exclusion can be removed entirely
• Confusing necessity with sufficiency
• Misapplying mutual exclusion to shareable resources

2. Which of the following statements about the convoy effect in FCFS scheduling is INCORRECT?

medium

A. The convoy effect occurs when a long process delays all subsequent shorter processes

B. The convoy effect can be mitigated by introducing preemption in the scheduling algorithm

C. The convoy effect causes the average waiting time to always be minimal in FCFS

D. The convoy effect leads to poor CPU utilization and increased waiting times

Solution

1. Step 1: Analyze each statement

   A is correct; long processes delaying short ones is the convoy effect.
   B is correct; preemption can reduce the convoy effect.
   C is incorrect; the convoy effect increases average waiting time, not minimizes it.
   D is correct; convoy effect can cause poor CPU utilization and longer waits.

2. Step 2: Identify the incorrect statement

   Only The convoy effect causes the average waiting time to always be minimal in FCFS falsely claims minimal average waiting time due to the convoy effect.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Convoy effect worsens waiting time, not improves it.

Hint: Convoy effect -> longer waits, not shorter

Common Mistakes:

• Assuming convoy effect improves waiting time
• Ignoring preemption as a mitigation
• Misunderstanding convoy effect impact on CPU utilization

3. Which of the following statements about thrashing and the working set model is INCORRECT?

medium

A. Thrashing occurs when the sum of all processes' working sets exceeds total available frames

B. The working set model dynamically adjusts the number of frames allocated to each process based on recent page usage

C. Increasing the total number of processes always reduces thrashing by distributing memory pressure

D. Load control can be used alongside the working set model to prevent thrashing by limiting the number of active processes

Solution

1. Step 1: Analyze each statement

   A is correct: thrashing happens when total working sets exceed memory.
   B is correct: working set model adjusts frames dynamically.
   C is incorrect: increasing processes usually increases memory pressure, worsening thrashing.
   D is correct: load control limits active processes to prevent thrashing.

2. Final Answer:

   Option C -> Option C

3. Quick Check:

   More processes usually increase thrashing risk, not reduce it.

Hint: More processes -> more memory pressure -> more thrashing

Common Mistakes:

• Believing more processes reduce thrashing
• Confusing load control with working set adjustments
• Ignoring total memory constraints

4. If a process requests resources that would keep the system in a safe state but the system is currently in an unsafe state, what does the Banker's Algorithm do and why?

hard

A. It denies the request because the system must always remain in a safe state, and starting from an unsafe state invalidates the algorithm's assumptions.

B. It restarts the system to reset resource allocations and ensure safety.

C. It preempts resources from other processes to restore a safe state before granting the request.

D. It grants the request because the immediate allocation is safe, ignoring the current unsafe state.

Solution

1. Step 1: Recall Banker's Algorithm assumptions

   The algorithm assumes the system starts in a safe state to guarantee deadlock avoidance.

2. Step 2: Analyze the scenario

   If the system is already unsafe, granting requests--even if individually safe--cannot guarantee overall safety.

3. Step 3: Evaluate options

   A ignores the unsafe starting state.
   B and C describe actions outside the algorithm's scope.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Banker's Algorithm cannot recover from unsafe states; it only avoids entering them.

Hint: Banker's Algorithm requires starting safe state to function correctly [OK]

Common Mistakes:

• Assuming safe requests can fix unsafe states
• Believing the algorithm preempts resources
• Thinking system restarts are part of the algorithm

5. If a system uses preemptive SJF scheduling but the burst times of processes are not known in advance and must be estimated, which challenge is most likely to affect scheduling accuracy?

hard

A. Incorrect burst time estimates can cause frequent unnecessary preemptions

B. The scheduler will always pick the wrong process due to estimation errors

C. Non-preemptive scheduling must be used instead to avoid errors

D. Starvation is eliminated because estimates prevent preemption

Solution

1. Step 1: Understand burst time estimation impact

   Estimations can be inaccurate, causing the scheduler to preempt based on wrong assumptions.

2. Step 2: Analyze consequences

   Frequent unnecessary preemptions increase overhead and reduce efficiency.

3. Step 3: Why other options are incorrect

   B: Scheduler won't always pick wrong process; estimates can be close.
   C: Non-preemptive scheduling is a design choice, not forced by estimation.
   D: Starvation is not eliminated by estimates; it depends on scheduling policy.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Estimation errors cause scheduling inefficiency via unnecessary preemptions.

Hint: Bad burst time estimates cause too many preemptions in preemptive SJF [OK]

Common Mistakes:

• Assuming estimates always cause wrong scheduling
• Believing estimation removes starvation