On a batch or multiprogramming system, there is usually a queue of processes blocked waiting for I/O, and a queue of processes waiting to run. There is only ever 0 or 1 processes actually running.
Switching between processes takes the OS some time, thus wasting resources that could be used by user processes.
Operating systems schedule processes in order to try and achieve certain goals:
a) Fairness: each process gets a fair share of the CPU.
b) Efficiency: keep the CPU as busy as possible.
c) Response time: minimise response time for interactive users.
d) Turnaround time: maximise the number of jobs processed per hour.
Not all of these can be satisfied. The CPU is a finite resource.
For example, to satisfy d), you would process only batch jobs, thus violates c).
Some schedulers use run to block/completion scheduling: wait until a process blocks or dies before rescheduling. Only useful on batch systems -- the process may not block for days.
Others use pre-emptive scheduling, and suspend the running process after a period of time known as the process' quantum or timeslice.
This allows other processes to run, even if the original process hadn't blocked. Needed for interactive systems.
First Come First Served/ Round Robin Shortest Job First
Created processes are put on the tail of the ready queue. When the running process blocks, move it to the blocked pool. Move the process at the head of the ready queue to the running state. As each process unblocks, place it at the tail of the ready queue.
Easy to implement.
Big disadvantage: one CPU-bound process will hog the CPU, thus reducing the overall throughput.
Small I/O bound processes must wait for the CPU-bound one to give up the CPU.
Schedule the process with the shortest CPU-burst next.
With a good interactive/non-interactive job mix, the spread of burst lengths looks as follows:
This is impossible to predict, so pick the one with the smallest average CPU-burst, i.e. order the ready queue according to the length of the average CPU-burst.
This gives I/O bound processes priority, when they are ready to run. But it can starve CPU-bound process, as they may be left on the end of the queue.
The average is usually weighted to the last CPU-burst:
[tabbing180]
If [tex2html_wrap413], the scheduling system is a static one. A priority [tex2html_wrap415] can be allocated to the process when it is created.
This can lead to starvation. It is rumoured that when MIT shut down its 7094 in 1973, there was still a low-priority job from 1967 on the machine.
First Come First Served/ Round Robin -- as per batch systems Timeslice Priority Multiple Priority Queues Long Term Schedulers
Give a process a timeslice according to a static priority.
For example, lecturers have priority 3, tutors 2 and students 1.
The OS looks up the priority in a table, e.g
[tabular189]
This doesn't lead to starvation, as all processes get some CPU-time.
Have several ready queues:
Schedule the process from the highest priority non-empty queue.
This can lead to starvation of lower priorities if one queue has many CPU bound processes, as the lower queues only get the CPU time when the upper queues are empty (no processes or processes blocked).
So far we have only discussed short-term schedulers. These must be very fast. High-level ones can collect data and change priorities and timeslice over a period of time. This, for example, may ``age'' a process down through the priority queues if the system is an interactive one and the process is CPU-bound.
This depends heavily on the type of system, and the types of processes running on the system.
It can be selected by gathering data on the current scheduling algorithm, simulating new algorithms, developing analytic models and testing the new algorithms out.
What does the CPU do when there are no processes in the ready queue?
Here the OS schedules an idle process, which is a CPU-bound process built into the OS.
The idle process is given the lowest priority possible, so it is not executed if there are any ready processes in the system.