CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 2 of 6 · 3 min read

Process states

Think of a bank with one clerk. The customer at the desk is being served. Others stand in line, ready to be served as soon as the clerk is free. A customer who must fetch a document from home steps out of the line, and rejoins it when back. The analogy stops at one point: the clerk (the processor) is taken from a process by force when its turn runs out, which a bank clerk would never do.

A process is always in one of these states:

State Meaning
New The process is being created
Ready It could run, and is waiting for a processor
Running Its instructions are being executed on a processor now
Waiting (blocked) It cannot continue until an event, such as a disk read finishing, happens
Terminated It has finished

In plain words: The names vary between systems, but every system has the same ideas. With one processor, at most one process is running at any moment. With four processors, at most four. Many processes can be ready or waiting.

The arrows between states are the heart of the picture:

Arrow Cause
New → Ready The kernel finishes setting the process up (it is "admitted")
Ready → Running The scheduler picks it (the "dispatch")
Running → Ready Its time slice ends, a timer interrupt (Level 0, page 5)
Running → Waiting It asks for something slow, such as a read, or sleeps
Waiting → Ready The event it waited for happens, such as an I/O interrupt
Running → Terminated It calls exit or is killed

There is no arrow from Waiting straight to Running. A process whose wait is over must first become ready and then be picked by the scheduler. There is also no arrow from Ready to Waiting: a process waits only because of something it did itself.

Here is a trace with one processor and two processes, A and B. A reads from a disk, which takes a while.

Time slot A B What happened
1 Running Ready A starts
2 Waiting Running A asked for a disk read, so B gets the processor
3 Waiting Running The disk is still working
4 Ready Running The disk finished, so A is ready, but B still holds the processor
5 Running Ready B's slice ended, and A is dispatched

The processor was busy in every slot. That is the value of keeping several processes: while one waits, another runs (Level 0, page 1).

Process state

A process state is the value, kept in the process control block, that says what a process is currently doing with respect to the processor: new, ready (waiting for a processor), running (executing on one), waiting (blocked until an event happens) or terminated. The scheduler uses the state to know which processes it may choose.

Example: a process that has asked the disk for data and has not got it yet is in the waiting state, and the scheduler will not choose it.

Check yourself: 1. Can a waiting process go straight to running? 2. What causes a process to move from running to ready? 3. With 8 processors and 20 runnable processes, how many can be running at once?