Process states (new, ready, running, waiting, terminated) in Operating Systems - Time & Space Complexity

Time Complexity: Process states (new, ready, running, waiting, terminated)

O(n)

Understanding Time Complexity

We want to understand how the time spent by a process changes as it moves through different states in an operating system.

How does the number of steps or transitions grow as the process runs?

Scenario Under Consideration

Analyze the time complexity of the following process state transitions.

// Pseudocode for process state transitions
state = "new"
while state != "terminated":
    if state == "new":
        state = "ready"
    else if state == "ready":
        state = "running"
    else if state == "running":
        if needs_io:
            state = "waiting"
        else:
            state = "terminated"
    else if state == "waiting":
        state = "ready"
    // repeat until terminated

This code models how a process moves through states until it finishes.

Identify Repeating Operations

Look for loops or repeated steps in the process state changes.

• Primary operation: The loop that changes the process state repeatedly.
• How many times: Depends on how many times the process needs CPU and I/O before termination.

How Execution Grows With Input

The number of state transitions grows with how many CPU bursts and I/O waits the process has.

Input Size (n)	Approx. Operations
10 (few I/O)	About 20 state changes
100 (moderate I/O)	About 200 state changes
1000 (many I/O)	About 2000 state changes

Pattern observation: The total steps increase roughly in direct proportion to the number of CPU and I/O cycles.

Final Time Complexity

Time Complexity: O(n)

This means the total number of state transitions grows linearly with the number of CPU and I/O cycles the process performs.

Common Mistake

[X] Wrong: "The process state changes happen instantly and do not add up."

[OK] Correct: Each state change takes time and the total time depends on how many times the process switches states before finishing.

Interview Connect

Understanding how process states change and how that affects execution time helps you explain how operating systems manage tasks efficiently.

Self-Check

"What if the process never needs I/O and runs straight to termination? How would the time complexity change?"

Practice

1. Which process state indicates that a process is ready to use the CPU but is not currently running?

easy

A. Ready

B. Running

C. Waiting

D. New

Solution

1. Step 1: Understand the meaning of the Ready state

   The Ready state means the process has all resources except the CPU and is waiting to be assigned the CPU.

2. Step 2: Compare with other states

   Running means the process is using the CPU; Waiting means it is waiting for an event; New means it is being created.

3. Final Answer:

   Ready -> Option A

4. Quick Check:

   Ready = waiting for CPU [OK]

Hint: Ready means waiting for CPU, not running yet [OK]

Common Mistakes:

• Confusing Ready with Running
• Thinking Waiting means ready
• Mixing New with Ready

2. Which of the following correctly lists the process states in the order a process typically goes through from start to finish?

easy

A. New -> Ready -> Running -> Waiting -> Terminated

B. New -> Running -> Ready -> Waiting -> Terminated

C. New -> Ready -> Waiting -> Running -> Terminated

D. New -> Waiting -> Ready -> Running -> Terminated

Solution

1. Step 1: Recall the typical process lifecycle

   A process starts as New, then moves to Ready when prepared to run, then Running when executing.

2. Step 2: Understand transitions to Waiting and Terminated

   While running, it may wait for I/O (Waiting), then return to Ready or finish (Terminated).

3. Final Answer:

   New -> Ready -> Running -> Waiting -> Terminated -> Option A

4. Quick Check:

   Correct lifecycle order = New -> Ready -> Running -> Waiting -> Terminated [OK]

Hint: Process starts New, then Ready, then Running [OK]

Common Mistakes:

• Swapping Ready and Running order
• Putting Waiting before Ready
• Skipping New state

3. Consider a process that is currently in the Waiting state. What will happen next when the event it is waiting for occurs?

medium

A. It moves to the Terminated state immediately.

B. It moves directly to Running state.

C. It stays in Waiting until manually terminated.

D. It moves to the Ready state to wait for CPU allocation.

Solution

1. Step 1: Understand the Waiting state

   Waiting means the process is paused, waiting for an event like I/O completion.

2. Step 2: What happens after the event?

   When the event occurs, the process becomes Ready to run but must wait for CPU scheduling.

3. Final Answer:

   It moves to the Ready state to wait for CPU allocation. -> Option D

4. Quick Check:

   Waiting ends -> Ready state [OK]

Hint: Waiting ends, process goes to Ready, not Running directly [OK]

Common Mistakes:

• Thinking Waiting goes directly to Running
• Assuming immediate termination
• Believing process stays Waiting forever

4. A process is stuck in the Running state and never moves to Waiting or Terminated. What is the most likely cause?

medium

A. The process has just been created and is initializing.

B. The process is waiting for CPU allocation.

C. The process is in an infinite loop without I/O or exit.

D. The process has completed and is terminated.

Solution

1. Step 1: Analyze the Running state behavior

   Running means the process is executing instructions on the CPU.

2. Step 2: Understand why it never leaves Running

   If it never moves to Waiting or Terminated, it likely loops endlessly without I/O or exit calls.

3. Final Answer:

   The process is in an infinite loop without I/O or exit. -> Option C

4. Quick Check:

   Infinite loop causes stuck Running [OK]

Hint: Infinite loop keeps process Running endlessly [OK]

Common Mistakes:

• Confusing Running with Ready
• Thinking process is terminated
• Assuming process is waiting for CPU

5. A process moves from Ready to Running, then to Waiting, and back to Ready multiple times before termination. What does this pattern indicate about the process's behavior?

hard

A. The process is stuck in an infinite loop without I/O.

B. The process frequently waits for I/O or external events during execution.

C. The process is terminated and restarted repeatedly.

D. The process is never scheduled to run on the CPU.

Solution

1. Step 1: Understand state transitions

   Moving from Running to Waiting means the process pauses for I/O or events.

2. Step 2: Returning to Ready means it resumes waiting for CPU after I/O completes.

   This cycle repeats until the process finishes and terminates.

3. Final Answer:

   The process frequently waits for I/O or external events during execution. -> Option B

4. Quick Check:

   Running -> Waiting -> Ready cycle = I/O waits [OK]

Hint: Running to Waiting means I/O wait, then Ready to run again [OK]

Common Mistakes:

• Thinking process restarts after termination
• Assuming infinite loop
• Believing process never runs