Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact


CA170      CA216      CA249      CA318      CA651

w2mind.computing.dcu.ie      w2mind.org

Processes and Scheduling


Process - An instance of the program running.
1 user with 2 instances of text editor running - 1 program, 2 processes, each with their own memory space.
100 users with 100 instances of web browser running, all running the same copy from /usr/bin/firefox - 1 program, 100 processes.

Process State

READY to RUNNING - Short-term (CPU) scheduler.
RUNNING to WAITING - I/O or event wait.
WAITING to READY - I/O or event completion.

RUNNING to READY - Why stop a process that is happily running?
To allow the OS do something with the CPU. Including to allow the OS give some CPU time to someone else for a while. Even if process running, still periodic timer interrupts.


In the 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.

Most processes look like:

Short period of calculation (short "CPU burst")
Long period of I/O
Short period of calculation 
Long period of I/O
i.e. Most processes regularly "vote themselves" off the Running list anyway. - We don't have to force them to go.

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.


2 (or more) flows of control in the same process. 2 (or more) instruction counters. Same memory (same data and code space).

e.g. Web server - Each request is a separate thread, all running in parallel until request completed. Web browser - multiple windows downloading at same time. Each is a separate thread in same process.

Up to program designer to make sure threads don't interfere with each other (or at least, only interfere in the ways he intends).

Maybe nice to have OS protect us against incompetent thread design, but how can it? Note OS does not (can not) protect against lots of types of incompetence, e.g. infinite loop.

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

Feeds      HumphrysFamilyTree.com

Bookmark and Share           On Internet since 1987.