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.
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:
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).
Selects which process in the Ready queue should next get CPU time.
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.
When process gets CPU, it keeps it until goes into Wait or terminates.
Even though process is running happily, it simply gets interrupted by the CPU after some time.
What criteria?
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.
In general, if bursts x1, ..xn, then:
Total Waiting Time = 0 +
x1 +
x1+x2 +
... +
x1+...+xn-1
= (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.
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?
Consider where new process arrives with much shorter burst than remaining burst time of current one running. Do we interrupt current one?
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
P1 waits 2-11 = 9
P2 waits 4-5 = 1
P3 waits 0
P4 waits 5-7 = 2
AWT = 3
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.
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.
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.
Process Burst time P1 53 P2 17 P3 68 P4 24
Say time quantum = 20:
context switch << time slice average CPU burst <= time slice (some, but not too many > time slice)
