A multiprogramming system has a number of jobs (user programs and data) stored in memory.

Each job is allocated a small amount of processing time (time slice) in turn. At the end of the time-slice, an interrupt occurs, and processing passes to a different job.

The scheduler is that part of the operating system which decides which job is to be processed next.

A simple illustration:

Suppose there are 3 jobs which each require three equal time requirements - CPU then use of a peripheral then CPU again...

The top of the diagram shows how the three jobs would be tackled in a simple serial fashion, with each job waiting for the previous job to finish.

(Each square represents a time slice)

It takes 9 time slices to complete the three jobs.

The scheduler could allocate the CPU time so that the three jobs are completed faster:

It now takes only 6 time slices to complete the three jobs.

There are three basic states a job can be in :

1. Running (being processed)
2. Ready (not being processed but waiting)
3. Blocked (the scheduler may flag a process as blocked if it is unable to continue - maybe an error has occurred or it is waiting for I/O to complete. A blocked job will not be selected for processing.)

Whenever there is a break in the execution of a job (eg an interrupt occurs or the job requires use of a peripheral), the scheduler is used to decide which job should continue processing next. The decision is normally based on job priorities, and the scheduler normally maintains a job queue for this purpose. Jobs with high priorities may 'jump' the queue.

A scheduling policy should try to ....

• process as many jobs as possible in as little time as possible.
• balance resource use. Eg if a printer is idle, a high priority could be given to a job that uses the printer.
• avoid pushing low priority jobs to the back of the queue indefinitely. This can be achieved by giving jobs a higher priority based on how long they have been in the queue.
• maximise the number of interactive users receiving acceptable response times (the time between issuing a request to a computer and receiving a response).

Example of a scheduling policy:

Each job is allocated a time slice of processing time in turn (on a first-in-first-out basis).

If the job is not completed during that time slice then processing passes to the next job.

If a job requires use of a peripheral during its time slice then CPU processing is stopped and the next job starts its time slice of processing.

Jobs with short expected run-times receive a high priority.