display | more...

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).

Log in or register to write something here or to contact authors.