Process Queues

When more processes are ready to run than the CPU can run at once, the operating system keeps the waiting ones in a data structure, usually a first in, first out waiting line. The process that has waited longest sits at the front and gets the CPU next.

Each turn on the CPU is a time slice. If a process finishes within its slice, it is removed and does not return. If it does not finish, the operating system takes the CPU away and returns the process to the back of the waiting line to wait for another turn. This stops one long process from hogging the CPU, so every waiting process makes progress.

Ordering by priority

The waiting line can be ordered by priority, so a process that matters more is placed ahead of lower-priority ones and runs sooner. A low-priority process can be pushed back several times before it gets a turn. For example, in a school results system, the process that works out grades could have a higher priority than a process that tidies up old log files, so the important job is not kept waiting behind the tidy-up. When an unfinished process rejoins a priority-ordered waiting line, it goes in at the position that matches its priority rather than straight to the end.

Keeping waiting processes in a data structure makes this practical: the operating system can quickly add a process, take the next one from the front, and reorder the line by priority.

Worked example

Three processes, P, Q and R, all have the same priority and each gets a time slice of 3 units. P needs 8 units, Q needs 4 and R needs 2.

If Q had a higher priority than the others, it would be placed at the front, so it would finish sooner.