Processes and Scheduling

Swapping

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?

PCB:

State (Ready, Waiting, etc.)
Instruction Counter
(copy of) CPU registers when it was interrupted
Scheduling info (priority)
Memory info (base and limit)
Accounting info (generally obsolete now)
I/O status (list of open files, devices)

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.

Can work on hardware which has no timer mechanism.
Can work for a multi-process system, but only for a single-user multi-process system. (Why?)
This is what Windows 3 (just before Windows 95) did. The user controlled the switching. When you switched focus of the window, background process was frozen.

Preemptive scheduler

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

UNIX, Windows 95 onwards.
Needs timer hardware.
Need to be careful that program can be interrupted and then resumed in consistent state. (Are files open? Is I/O in progress?)

Scheduling Algorithms

What criteria?

CPU as busy as possible.
Throughput - No. of completed processes in period. - Meaningless if don't complete (user interfaces).
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.

FIFO / FCFS

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 x₁, ..x_n, then:

Total Waiting Time = 0 +
x₁ +
x₁+x₂ +
... +
x₁+...+x_n-1

= (n-1) x₁ + (n-2) x₂ + ... + 1. x_n-1

Obviously this sum is reduced if the x_i'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. P₁ of length x.
P₂ of length x+t.
And we have already waited time T to get to the two of them.
Now, if P₁ goes before P₂, 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?

Well first, it's only the optimal non-preemptive one. Still batch oriented. Could still be long waits.
Second, what is the next CPU burst time? Same issue as Halting Problem. Can't calculate it. Can only estimate based on recent history.

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

Preemptive - Interrupt if Ready process arrives with higher priority than Running process.
Nonpreemptive - Running not interrupted, but Ready queue sorted by priority.

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

Each process gets a small unit of CPU time (time quantum). Then put back in Ready queue.
Preemptive. Timer interrupts. When interrupted, go to end of FIFO queue.
Good for multi-user time-sharing - fast response time.
Sometimes, OS just says "carry on" (only 1 Ready process, but keep interrupting, to keep OS in control).
Sometimes don't even need 1 time quantum since process leaves voluntarily.

Example:

Process   Burst time
P1         53
P2         17
P3         68
P4         24

Say time quantum = 20:

Setting the time quantum size

If quantum too small, too much admin, not enough work.
As quantum goes to infinity, this goes to straight FIFO non-preemptive.

Want:

context switch << time slice
average CPU burst <= time slice 
(some, but not too many > time slice)

Also perhaps relate quantum to how quickly a user interface needs to respond to be usable.