Scheduling

First Come, First Served (or "run to completion")

This is the technique used in the pimeval OS sludge of batch jobs and punched cards. The basic approach is to run the first job to completion (even if it occasionally blocks, waiting for I/O), then when it is finished, run the next job, then the next one... and so on.

Not used much these days, but it is not as useless as it may first seem. (though it is 'unfair' and increases turnaround and provides lousy response time)

A useful variation of 'run to completion', is 'run until BLOCKED'. The first job in the RUNNING queue runs until it becomes blocked, waiting on I/O, or on a semaphore, then the next process runs 'til it becomes blocked, then the next... and so on.

* Essentially when typing commands to a UNIX shell, the shell executes the commands one after the other, first come, first served.

* Cooperative multitasking systems use this mechanism, essentially. E.g. Macintosh toolbox sends UI event to an application, the application processes the event in its entirity (without being preempted), and returns control to the OS. With single-user machine, this may be a low-overhead way to provide good performance on a slow machine.

* Very high priority tasks, e.g. triggered by interrupts and dealing with hardware, may need to do only a very little processing before blocking again. FCFS makes sence.

shortest job first

gives highest priority to shortest job. Improves turnaround. Impossible to predict in general.


last updated 29 April 1998