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. In a system where multiple producers and consumers share a fixed-size buffer, which synchronization mechanism best ensures that producers wait when the buffer is full and consumers wait when the buffer is empty?

easy

A. Mutex lock only to protect buffer access

B. Spinlocks to busy-wait until buffer space is available

C. Counting semaphores to track empty and full slots along with a mutex for mutual exclusion

D. Condition variables without any semaphore or mutex

Solution

1. Step 1: Identify synchronization needs

   Producers must wait if the buffer is full; consumers must wait if empty. This requires tracking counts of empty and full slots.

2. Step 2: Role of counting semaphores

   Counting semaphores elegantly track available slots (empty) and filled slots (full), enabling blocking waits without busy-waiting.

3. Step 3: Need for mutual exclusion

   A mutex is required to protect concurrent access to the buffer itself to avoid race conditions.

4. Step 4: Why other options fail

   Mutex alone (A) cannot block producers/consumers based on buffer state; spinlocks (C) waste CPU cycles; condition variables (D) require mutexes and signaling to work correctly in this scenario.

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   Counting semaphores + mutex is the classic producer-consumer solution [OK]

Hint: Counting semaphores track buffer state; mutex protects access

Common Mistakes:

• Assuming mutex alone handles waiting
• Using spinlocks wastes CPU
• Thinking condition variables alone suffice

2. Which of the following is a key limitation of Peterson's algorithm that affects its practical use in modern multiprocessor systems?

medium

A. It allows unbounded waiting, leading to starvation

B. It requires busy waiting, which wastes CPU cycles

C. It depends on hardware atomic instructions to function correctly

D. It cannot guarantee mutual exclusion under any circumstances

Solution

1. Step 1: Identify Peterson's algorithm characteristics

   Peterson's algorithm uses busy waiting (spinlock), which can waste CPU resources.

2. Step 2: Analyze other options

   It cannot guarantee mutual exclusion under any circumstances is false because mutual exclusion is guaranteed. It depends on hardware atomic instructions to function correctly is incorrect since Peterson's algorithm was designed to avoid hardware atomic instructions. It allows unbounded waiting, leading to starvation is wrong because bounded waiting is guaranteed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Busy waiting is a known practical limitation of Peterson's algorithm.

Hint: Peterson's = busy waiting, no hardware locks, bounded waiting

Common Mistakes:

• Assuming Peterson's needs hardware atomic instructions
• Confusing bounded waiting with starvation
• Believing mutual exclusion can fail

3. Which of the following statements about deadlock prevention in the Dining Philosophers problem is INCORRECT?

medium

A. Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation

B. Allowing a philosopher to pick up both forks only if both are available prevents deadlock

C. Imposing a strict ordering on resource acquisition always prevents deadlock

D. Breaking one of the four Coffman conditions is sufficient to prevent deadlock

Solution

1. Step 1: Analyze each statement

   Imposing a strict ordering on resource acquisition always prevents deadlock is correct: ordering resources prevents circular wait; Allowing a philosopher to pick up both forks only if both are available prevents deadlock is correct: atomic acquisition avoids partial hold; Breaking one of the four Coffman conditions is sufficient to prevent deadlock is correct: breaking any Coffman condition prevents deadlock.

2. Step 2: Evaluate Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation

   Asymmetric fork picking prevents deadlock but does not guarantee no starvation, as some philosophers may be repeatedly delayed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only Using asymmetric fork picking (odd philosophers pick left first, even pick right first) guarantees no starvation incorrectly claims starvation is guaranteed prevented.

Hint: Deadlock prevention ≠ starvation prevention [OK]

Common Mistakes:

• Assuming deadlock prevention implies starvation freedom
• Believing asymmetric picking solves all synchronization issues
• Confusing Coffman conditions with starvation conditions

4. 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

5. Which of the following statements about the producer-consumer problem using semaphores is INCORRECT?

medium

A. Mutex is optional if semaphores are used correctly

B. The 'full' semaphore is initialized to zero to track filled slots

C. The 'empty' semaphore is initialized to the buffer size to track available slots

D. Producers and consumers block on semaphores to avoid busy-waiting

Solution

1. Step 1: Initialization of semaphores

   'empty' starts at buffer size; 'full' starts at zero -- both correct.

2. Step 2: Role of mutex

   Mutex is essential to ensure mutual exclusion when accessing the buffer; semaphores alone do not provide this.

3. Step 3: Blocking behavior

   Producers and consumers block on semaphores to avoid busy-waiting, which is correct.

4. Step 4: Why 'Mutex is optional if semaphores are used correctly' is incorrect

   Claiming mutex is optional is a common misconception; without mutex, race conditions occur.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Mutex is mandatory for mutual exclusion [OK]

Hint: Mutex is mandatory; semaphores track counts

Common Mistakes:

• Believing semaphores alone guarantee mutual exclusion
• Misinitializing semaphore counts
• Thinking blocking is done by mutex