Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

My big idea: Ancient Brain


CA114      CA170

CA668      CA669      Projects

Processes and Scheduling


In the process state diagram, we assume we only swap waiting/idle processes (e.g. certainly a web browser that has been inactive for more than 30 mins, but also in theory a web browser at just about any point, waiting for user input).

This is the most sensible approach. Because of the overhead, we only swap when absolutely necessary. But if memory is very tight, we may have to start swapping ready processes.

Process Control Block (PCB)

Note that between the time it starts and when it finishes, a process may be in memory or on disk, but it may not be running all the time. If not running, we must keep track of some data about it in the Process Control Block.

Instruction counter is the most obvious piece of data we must keep track of. Otherwise, when it returns to running, how do we know where to pick up?


Long-term Scheduler

Selects which processes are brought into the Ready queue.

UNIX has no long-term scheduler - Every program launched goes straight into memory.

It trusts to human behaviour - As the system slows down, people log off (or try to do less).

Short-term Scheduler

Selects which process in the Ready queue should next get CPU time.

CPU bursts

The diagram tends to hold true whether the program as a whole has a large or small number of instructions.

Long CPU bursts are very rare - Why?

"Long CPU burst" means long period working with memory and registers without any output to screen or any input from user or any input from file or any output to file.

But every program does at least one of these. Even "background" programs are usually reading/writing files.

Calculating π maybe?
- Even then, you're probably writing output to disk file.

Non-preemptive scheduler

When process gets CPU, it keeps it until goes into Wait or terminates.

Preemptive scheduler

Even though process is running happily, it simply gets interrupted by the CPU after some time.

Scheduling Algorithms

What criteria?

  1. CPU as busy as possible.
  2. Throughput - No. of completed processes in period. - Meaningless if don't complete (user interfaces).
  3. Waiting time - Amount of time process is Ready but not Running. Waiting time is good criterion because it works for both batch jobs and user-interface programs.


Very dependent on order they come in:

e.g. P1 has burst time 20, P2 5, P3 5.
If arrive in order P1, P2, P3, the Gantt chart for the schedule is:

WT's of P1, P2, P3 = 0, 20, 25.
AWT = 15.

If arrive in order P2, P3, P1:

WT's of P1, P2, P3 = 10, 0, 5.
AWT = 5.

What is the optimal schedule?

In general, if bursts x1, ..xn, then:

Total Waiting Time = 0 +
x1 +
x1+x2 +
... +

= (n-1) x1 + (n-2) x2 + ... + 1. xn-1

Obviously this sum is reduced if the xi's that are multiplied the most times are the smallest ones.

i.e. In non-preemptive scheduling, "Shortest Job First" (actually Shortest Next CPU burst) is optimal for purposes of minimising Average Waiting Time.

SJF is Optimal

Another way of proving this is:

Consider any 2 processes, one longer than the other, anywhere in the schedule. P1 of length x.
P2 of length x+t.
And we have already waited time T to get to the two of them.
Now, if P1 goes before P2, Total Wait Time = T, T+x.
Swap them, TWT = T, T+x+t.
Wait times of earlier and later processes unchanged no matter how we arrange these 2.

So for any 2 adjacent bursts, swap them so the smaller is at the front. Repeat this process until all sorted in order.

In fact, this only proves SJF is optimal for a number of processes arriving in a different order at the same time. How about processes arriving at different times?

So if SJF is optimal, why not implement it?

Preemptive Scheduling Algorithms

Consider where new process arrives with much shorter burst than remaining burst time of current one running. Do we interrupt current one?

Non-Preemptive SJF

Process   Arrival time   Burst time

P1         0              7
P2         2              4
P3         4              1
P4         5              4

WT's = 0, 6, 3, 7
AWT = 4

Preemptive SJF

P1 waits 2-11 = 9
P2 waits 4-5 = 1
P3 waits 0
P4 waits 5-7 = 2
AWT = 3

Priority Scheduling

SJF is special case where priority is based on burst length.

Immediate problem - Do low-priority ever get to run?

e.g. 1 low-priority and 10 high-priority all running. High-priority go into Wait, low-priority is in smaller and smaller Ready queue, thinks it's about to run, but before it does one of the high-priority always comes back into Ready again, and queue jumps. Low-priority gets queue jumped all day, never gets to run.

Even if preemptive, this idea is still batch-oriented - there could be long waits.

Pre-emptive SJF

Process with long CPU bursts gets constantly interrupted by processes with short CPU bursts, which run whenever they like. Process with long CPU bursts runs at an absolute lower priority (slower, perhaps considerably slower).

Maybe this is alright! Long CPU bursts are probably batch jobs. Short CPU bursts are probably user programs, should be higher priority.

Extreme case - Starvation

Starvation - Ready, but never get to Run.
Solution - Aging - Priority increases as time in Ready queue goes on. Priority decreases every time you get to Run.

Round Robin

Process   Burst time
P1         53
P2         17
P3         68
P4         24

Say time quantum = 20:

Setting the time quantum size

ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.

Wikipedia: Sometimes I link to Wikipedia. I have written something In defence of Wikipedia. It is often a useful starting point but you cannot trust it. Linking to it is like linking to a Google search. A starting point, not a destination. I automatically highlight in red all links to Wikipedia and Google search and other possibly-unreliable user-generated content.