Processes, process states and scheduling algorithms

Processes and states

A process is a program that is being executed, together with its current state (registers, memory, open files). The OS keeps details in a process control block.

Process states:

• New: being created.
• Ready: loaded in memory, waiting for CPU time.
• Running: currently being executed by the CPU.
• Blocked (waiting): cannot continue until an event happens, such as input arriving.
• Terminated: finished.

Transitions: ready to running (chosen by the scheduler); running to ready (time slice ends or a higher priority process arrives); running to blocked (waits for I/O); blocked to ready (the event happens). A blocked process never goes straight to running.

Scheduling algorithms

• First-come, first-served (FCFS): run processes to completion in arrival order. Simple and fair in order, but a long job makes short ones wait (poor average waiting time).
• Shortest job first (SJF): run the ready process with the shortest burst time next. Gives the lowest average waiting time, but burst times must be known or estimated, and long jobs can be delayed indefinitely (starvation).
• Round robin (RR): each process runs for at most one time slice (quantum), then goes to the back of the ready queue. Responsive and fair; no starvation; but many context switches, and performance depends on the quantum.
• Multi-level queue: processes are put into separate queues by type or priority (for example system, interactive, batch). Each queue can use its own algorithm (for example RR for interactive, FCFS for batch). Higher queues are served first, so lower queues can starve.

Working out waiting times

Waiting time = finish time - burst time (when every process arrives at time 0). Jobs A 8, B 4, C 2, D 6 ms arrive at time 0 in that order:

Worked example

Processes P (5 ms), Q (3 ms) and R (1 ms) arrive together in that order. Use round robin with a 2 ms quantum. Find when each finishes.

1. Timeline: P 0 to 2, Q 2 to 4, R 4 to 5, P 5 to 7, Q 7 to 8, P 8 to 9
2. Finish times: P at 9, Q at 8, R at 5 ms

Answer: R finishes at 5 ms, Q at 8 ms and P at 9 ms.

Check yourself

1. Jobs A 8 ms, B 4 ms, C 2 ms and D 6 ms arrive at time 0 in that order. Using FCFS, what is D's waiting time in ms?
   Show answer

   14 ms. D starts after A, B and C: 8 + 4 + 2 = 14 ms.

2. The same four jobs (A 8, B 4, C 2, D 6 ms) are scheduled using SJF. What is the average waiting time in ms?
   Show answer

   5 ms. Order C, B, D, A; waits 0, 2, 6, 12; average = 20 / 4 = 5.0 ms.

3. Using round robin with a 3 ms quantum on A 8, B 4, C 2, D 6 ms (queue order A, B, C, D), at what time does B finish?
   Show answer

   15 ms. Timeline: A 0 to 3, B 3 to 6, C 6 to 8, D 8 to 11, A 11 to 14, B 14 to 15, D 15 to 18, A 18 to 20. B finishes at 15 ms.

4. A running process requests data from a disk. Which state does it move to?
   • Ready
   • Terminated
   • New
   • Blocked
   Show answer

   Blocked. It cannot continue until the data arrives, so it is blocked (waiting).

5. Which transition is not possible in the process state model?
   • Ready to running
   • Blocked to running
   • Running to ready
   • Blocked to ready
   Show answer

   Blocked to running. When its event happens a blocked process goes to ready and must wait to be scheduled.

6. Which algorithm can cause a long job to wait indefinitely if short jobs keep arriving?
   • Round robin
   • First-come, first-served
   • A single queue served in arrival order
   • Shortest job first
   Show answer

   Shortest job first. SJF always prefers short jobs, so a long job can starve.

7. What is a feature of multi-level queue scheduling?
   • Every process gets exactly the same time slice in one queue
   • Processes are placed in separate queues by type or priority, each with its own algorithm
   • Jobs always run in the order they arrive
   • The shortest job always runs first, whatever its type
   Show answer

   Processes are placed in separate queues by type or priority, each with its own algorithm. Separate queues let interactive and batch work be treated differently.

8. Explain the effect of making the round robin quantum very small.
   Show answer

   There are many more context switches, so more CPU time is wasted on switching overhead, although the system is very responsive.. Small quantum: responsive but high overhead. Very large quantum: behaves like FCFS.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification (2026)

Last updated 8 November 2026. Spotted a mistake? Tell us.