The act of determining which process runs next on the processor.
Since processors are extremely single-minded this is necessary in
every system that does multitasking (i.e. every current-day system)
to give the user the illusion that the computer does several things
(e.g. printing, sending data to the modem, playing mp3 and editing a
text) at the same time. The scheduler has to determine the next process each time a process ends, blocks (e.g. waiting for I/O), gives
up the processor or has exceeded its time slice.
There exists several strategies for process scheduling which give
different results with respect to some optimality criteria. Among
those are: Throughput (maximize the amount of work done), response
time (minimize the average time a user has to wait for an answer),
efficiency (keep processor and I/O system busy). Furthermore
strategies can be distinguished by the fact if they require
preemption or not. If a non-preemptive scheduler is used, processes
must give up the processor voluntarily to keep up the impression of
simultaneous process execution (called cooperative multitasking).
Strategies:
- FIFO(First in, first out)
-
non-preemptive;The first job submitted to the scheduler will be
executed until it ends, blocks, or yields the processor (sometimes
even blocking and yielding do not give up the processor). This
causes few overhead and therefore optimizes throughput.
-
SJF (Shortest Job First)
-
non-preemptive; The scheduler chooses the job which needs the least
amount of work to be done (under the unrealistic assumption that
this amount is known in advance). This optimizes response time.
-
Shortest remaining processing time
-
preemptive version of SJF
-
Round Robin
-
preemptive; Maintains a circular list of all processes and gives
each one its time slice. Easy to implement but in this easy form
neither fair nor efficient.
-
priority-based scheduling:
-
Jobs have a static or dynamic priority. The job with the highest
priority is chosen. Variations of this (e.g. coupled with round
robin) are used by most modern operating systems.
Sometimes (e.g. on the Amiga :) process dispatching is
distinguished from scheduling. The task of the dispatcher is to
switch process with as few overhead as possible according to some
information provided by the scheduler. The scheduler only
wakes up sometimes to reorganize this information (e.g. giving
processes which used up their whole time slice a lower priority).