Process State Machine - Five-State Model

▶

Steps

setup

Process Created and Added to New State

The process is created and enters the New state, preparing to be admitted to the system.

💡 Initialization is crucial to understand where a process starts before it can be scheduled.

Line:

process.state = 'New'  # STEP 1

💡 Processes begin in the New state before admission to the ready queue.

expand

Process Admitted to Ready State

The process moves from New to Ready, indicating it is prepared to run and waiting for CPU allocation.

💡 Admission moves the process into the ready queue, making it eligible for CPU scheduling.

Line:

process.state = 'Ready'
ready_queue.append(process)  # STEP 2

💡 Ready state means the process is waiting in line for CPU time.

traverse

Scheduler Dispatches Process to Running

The scheduler selects the process from the ready queue and dispatches it to the CPU, changing its state to Running.

💡 Dispatching is the key step where the CPU starts executing the process.

Line:

running_process = ready_queue.pop(0)
running_process.state = 'Running'  # STEP 3

💡 Running state means the process is actively executing on the CPU.

expand

Process Executes CPU Burst

The process executes one unit of CPU burst, reducing its remaining burst time.

💡 Tracking burst time shows how long a process needs CPU before it may wait or terminate.

Line:

running_process.burst_remaining -= 1  # STEP 4

💡 CPU burst time decreases as the process runs.

prune

Process Requests I/O and Moves to Waiting

The process requests I/O, causing it to move from Running to Waiting state, and the CPU becomes idle.

💡 Processes often wait for I/O, which frees the CPU for other processes.

Line:

running_process.state = 'Waiting'
waiting_queue.append(running_process)
running_process = None  # STEP 5

💡 Waiting state means the process is blocked, waiting for I/O completion.

expand

I/O Completes, Process Moves to Ready

The I/O completes, so the process moves from Waiting back to Ready, rejoining the ready queue.

💡 I/O completion allows the process to become eligible for CPU again.

Line:

waiting_queue.remove(process)
process.state = 'Ready'
ready_queue.append(process)  # STEP 6

💡 Processes cycle between Waiting and Ready depending on I/O status.

traverse

Scheduler Dispatches Process to Running Again

The scheduler selects the process from the ready queue again and dispatches it to the CPU to continue execution.

💡 Processes may run multiple times, interleaved with waiting periods.

Line:

running_process = ready_queue.pop(0)
running_process.state = 'Running'  # STEP 7

💡 Running state resumes after waiting and ready states.

expand

Process Executes Remaining CPU Burst

The process continues executing on the CPU, decrementing its remaining burst time.

💡 CPU burst execution continues until the process finishes or waits again.

Line:

running_process.burst_remaining -= 1  # STEP 8

💡 Burst time counts down with each CPU unit executed.

delete

Process Completes CPU Burst and Terminates

The process finishes its CPU burst and moves to the Terminated state, releasing the CPU.

💡 Termination marks the end of the process lifecycle.

Line:

if running_process.burst_remaining == 0:
    running_process.state = 'Terminated'
    running_process = None  # STEP 9

💡 Terminated state means the process is finished and removed from scheduling.

shrink

CPU Idle After Process Termination

With no processes left to run, the CPU remains idle, and the system is idle.

💡 Idle CPU indicates no runnable processes remain.

Line:

if not ready_queue and not running_process:
    cpu_register.running_pid = null  # STEP 10

💡 CPU idle state occurs when no processes are ready or running.

class Process:
    def __init__(self, pid):
        self.pid = pid
        self.state = 'New'  # STEP 1
        self.burst_remaining = 5

ready_queue = []
waiting_queue = []
running_process = None
cpu_time = 0

# STEP 2: Admit process
p = Process(1)
p.state = 'Ready'
ready_queue.append(p)

# STEP 3: Dispatch
running_process = ready_queue.pop(0)
running_process.state = 'Running'
cpu_time += 1

# STEP 4: Execute CPU burst
running_process.burst_remaining -= 1
cpu_time += 1

# STEP 5: I/O request
running_process.state = 'Waiting'
waiting_queue.append(running_process)
running_process = None
cpu_time += 1

# STEP 6: I/O complete
waiting_queue.remove(p)
p.state = 'Ready'
ready_queue.append(p)
cpu_time += 1

# STEP 7: Dispatch again
running_process = ready_queue.pop(0)
running_process.state = 'Running'
cpu_time += 1

# STEP 8: Execute CPU burst
running_process.burst_remaining -= 1
cpu_time += 1

# STEP 9: Terminate if done
if running_process.burst_remaining == 0:
    running_process.state = 'Terminated'
    running_process = None
    cpu_time += 1

# STEP 10: CPU idle
if not ready_queue and not running_process:
    running_process = None
    cpu_time += 1

📊

Process State Machine - Five-State Model - Watch the Algorithm Execute, Step by Step

Watching the process state transitions and queue movements step-by-step reveals how operating systems manage process lifecycles and CPU allocation.

Transition none → New pid:1 - Process created

1

New

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=0

Transition New → Ready pid:1 - Process admitted to ready queue

1

Ready

burst: 5

Ready Queue

1

Waiting Queue

empty

🖥CPUidlet=0

Transition Ready → Running pid:1 - Scheduler dispatched process to CPU

1

Running

burst: 5

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=1

Transition Running → Running pid:1 - Process executed one CPU unit

1

Running

burst: 4

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=2

Transition Running → Waiting pid:1 - Process requested I/O

1

Waiting

burst: 4

Ready Queue

empty

Waiting Queue

1 (I/O)

🖥CPUidlet=3

1

Transition Waiting → Ready pid:1 - I/O completed

1

Ready

burst: 4

Ready Queue

1

Waiting Queue

empty

🖥CPUidlet=4

1

Transition Ready → Running pid:1 - Scheduler dispatched process to CPU again

1

Running

burst: 4

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=5

1

Transition Running → Running pid:1 - Process executed one CPU unit

1

Running

burst: 3

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=6

1

Transition Running → Terminated pid:1 - Process completed execution

1

Terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=7

1

Transition Terminated → Idle - No processes left to run

1

Terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=8

1

idle

Key Takeaways

✓ Processes transition through distinct states: New, Ready, Running, Waiting, and Terminated.

This lifecycle is fundamental but often abstract; seeing it step-by-step clarifies the flow.

✓ The ready queue holds processes waiting for CPU, and the waiting queue holds those blocked on I/O.

Understanding these queues visually helps grasp scheduling and blocking concepts.

✓ CPU scheduling decisions move processes between Ready and Running, while I/O requests cause transitions to Waiting.

Watching these decisions unfold shows how the OS manages CPU and I/O resources dynamically.

Practice

1. Which of the following statements about the C-SCAN disk scheduling algorithm is INCORRECT?

medium

A. C-SCAN services requests in one direction only and jumps back to the beginning without servicing requests on the return trip.

B. C-SCAN eliminates starvation by always servicing the closest request next.

C. C-SCAN can cause longer average seek times than SSTF because it ignores the closest requests on the return path.

D. C-SCAN provides a more uniform wait time compared to SCAN by treating the disk as a circular list.

Solution

1. Step 1: Review C-SCAN behavior

   C-SCAN moves the head in one direction, servicing requests, then jumps back to the start without servicing requests on the return.

2. Step 2: Understand fairness and wait times

   This approach provides uniform wait times and avoids starvation.

3. Step 3: Analyze each option

   C-SCAN eliminates starvation by always servicing the closest request next. is incorrect because C-SCAN does not always service the closest request next; it ignores requests on the return jump.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   C-SCAN eliminates starvation by always servicing the closest request next. is the only incorrect statement about C-SCAN.

Hint: C-SCAN jumps back without servicing requests, so closest next request isn't guaranteed

Common Mistakes:

• Assuming C-SCAN always picks the closest request next
• Confusing C-SCAN with SCAN regarding servicing on return
• Believing C-SCAN causes starvation

2. In a system with multiple CPUs (multi-core), how does context switching overhead differ compared to a single-core system, and what additional factors must be considered?

hard

A. Context switching overhead per CPU remains the same, but inter-CPU cache coherence and synchronization add extra overhead

B. Context switching overhead is eliminated because each CPU runs its own process independently

C. Context switching overhead doubles because each CPU must save and restore registers twice

D. Context switching overhead is reduced because the scheduler can switch processes faster across CPUs

Solution

1. Step 1: Per-CPU context switch cost

   Each CPU still saves/restores registers during context switches, so overhead per CPU is similar to single-core.

2. Step 2: Additional multi-core factors

   Multi-core systems require cache coherence protocols and synchronization mechanisms, adding overhead beyond single-core context switching.

3. Step 3: Misconceptions

   Context switching is not eliminated; CPUs do not save/restore registers twice per switch; scheduler speedup is not guaranteed.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Multi-core adds complexity beyond per-CPU context switch overhead.

Hint: Multi-core = same per-CPU cost + extra sync overhead [OK]

Common Mistakes:

• Thinking multi-core removes context switch overhead
• Assuming overhead doubles incorrectly
• Believing scheduler is always faster on multi-core

3. If a file system uses triple indirect pointers in its inode structure, what is a potential downside when accessing a small file that fits entirely within direct blocks?

hard

A. The inode size increases significantly, wasting space for small files.

B. Accessing small files becomes slower due to unnecessary traversal of indirect pointers.

C. The file system must allocate indirect blocks even if the file is small.

D. There is no downside; triple indirect pointers do not affect small file access.

Solution

1. Step 1: Understand inode fixed size

   Inodes have a fixed size that includes space for direct and indirect pointers, regardless of file size.

2. Step 2: Analyze impact on small files

   Including triple indirect pointers increases inode size, which can waste space when storing many small files.

3. Step 3: Clarify access speed for small files

   Accessing small files uses direct pointers only; indirect pointers are not traversed, so no speed penalty.

4. Step 4: Confirm allocation behavior

   Indirect blocks are allocated only when needed; small files do not allocate them.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Fixed inode size with many pointers wastes space for small files [OK]

Hint: Fixed inode size -> wasted space for small files with many pointers

Common Mistakes:

• Assuming indirect pointers slow down small file access
• Believing indirect blocks are allocated for small files
• Thinking triple indirect pointers have no impact on inode size

4. If the buffer size in a producer-consumer system is increased dynamically at runtime, which challenge arises that the classic semaphore-based solution does NOT handle well?

hard

A. Consumers must signal the 'empty' semaphore twice per consumed item

B. The 'empty' semaphore count must be adjusted atomically to reflect new buffer slots

C. Producers will never block because buffer is always large enough

D. Mutex locks become ineffective with dynamic buffer sizes

Solution

1. Step 1: Classic solution assumes fixed buffer size

   Semaphore 'empty' initialized once to buffer size; dynamic resizing breaks this assumption.

2. Step 2: Adjusting semaphore counts

   When buffer grows, 'empty' semaphore must be incremented atomically to reflect new slots; otherwise, producers may block unnecessarily.

3. Step 3: Why other options are incorrect

   Consumers must signal the 'empty' semaphore twice per consumed item is false; consumers do not signal 'empty' twice. Mutex locks become ineffective with dynamic buffer sizes is false; mutex still protects critical section regardless of size. Producers will never block because buffer is always large enough is false; producers can still block if buffer is full.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Dynamic buffer size requires careful semaphore count updates [OK]

Hint: Dynamic buffer size requires dynamic semaphore adjustment

Common Mistakes:

• Assuming fixed semaphore counts suffice for dynamic buffers
• Thinking mutex depends on buffer size
• Misunderstanding producer blocking conditions

5. If a system call is invoked from an interrupt handler already running in kernel mode, what is the expected behavior regarding mode switching and privilege checks?

hard

A. The system call is deferred until the interrupt handler finishes and user mode resumes.

B. The CPU switches to user mode before executing the system call to prevent privilege escalation.

C. The system call executes immediately without a mode switch since already in kernel mode.

D. The system call triggers a nested mode switch to a higher privilege level.

Solution

1. Step 1: Understand current mode

   Interrupt handlers run in kernel mode with full privileges.

2. Step 2: System call invoked in kernel mode

   Since already in kernel mode, no mode switch is needed; system call executes directly.

3. Step 3: Why other options are incorrect

   The CPU switches to user mode before executing the system call to prevent privilege escalation. is incorrect; switching to user mode would reduce privileges improperly. The system call is deferred until the interrupt handler finishes and user mode resumes. is wrong; system calls are not deferred. The system call triggers a nested mode switch to a higher privilege level. is false; kernel mode is the highest privilege level, no nested switch occurs.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   System call in kernel mode -> no mode switch -> immediate execution [OK]

Hint: No mode switch if already in kernel mode

Common Mistakes:

• Assuming mode switch always occurs on system call
• Thinking system calls are deferred inside kernel
• Believing nested privilege levels exist beyond kernel mode