Program Execution Management

The Job Queue

• The Command Processor portion of the Operating System reads user requests to run particular programs.
• Program which has been requested is added to a list of programs waiting to be loaded into memory for execution. This list is called the "Job Queue".
• Depending upon the program's resource requirements and the currently free resources, a program may be run right away or may need to wait in the Job Queue until the required resources become available.

Scheduling

• The Scheduler portion of the Operating System, compares free/available system resources with resource requirements of programs in the Job Queue.
• When all required resources (including memory space) become available, the Scheduler copies the program into memory and adds it to the list of programs waiting to use the processor, the "Dispatch Queue".

Dispatching

• Whenever the Operating System gains control of the processor because the application program which was using the processor has given it up (either voluntarilly or non-volunarilly), a portion of the Operating System called the Dispatcher selects a program which is waiting in the Dispatch Queue and passes control of the processor to that program.
• Selection of which program is to be "dispatched" is typically based on First In - First Out (i.e. whichever program has been waiting the longest gets run next), however various priority schemes for alternate selection may be used. One very simple alternative dispatch system is to classify programs as either "foreground" or "background"; background programs only get dispatched when there are no foreground programs waiting in the Dispatch Queue.
• Dispatching a program involves restoring all registers and flags to the values they contained when the program last stopped executing (or simply setting the Program Counter register to the address of the first instruction the first time a program is dispatched).

How an Application Program Loses Control

A program can lose control of the processor (i.e. the processor will stop executing instructions within that program) in basically one of two ways:
• Voluntarilly - The program makes an Operating System service request (via a software interrupt for example). The most common form of this would occur when the program requests Input or Output.
• Non-Voluntarilly - Various hardware devices generate interrupt signals which cause control to pass to Operating System service functions. Specifically, a interval timer is built in to almost every computer system which will generate a hardware interrupt after an Operating System set interval of time. In this way, the Operating System can limit the amount of time any application program can control the processor without having control return to the Operating System.

The Waiting Service List

• Programs which are waiting for Input/Output (or similar services) are placed by an Operating System routine into a list of Programs Waiting Service Completion.
Such programs can not be placed in the Dispatch Queue until the service they requested has been completed. Until the service has been completed, there is no useful work they can do with the processor (or at least that is the assumption made by the Operating System).
• Programs are typically moved off this list and on to the Dispatch Queue as the result of devices generating interrupt signals indicating the completion of an I/O operation.

Example of Process Status Flow

In order to get a "feel" for how control is managed for programs within amultiprogramming environment, assume that we have the following (not entirely realistic) situation:
• Four programs have been scheduled, with the following process-I/O requirements:
  • Program A : 40 minutes of processing followed by 1 I/O operation.
  • Program B : a processing cycle: 5 msec of processing followed by 1 I/O operation, repeated 500 times.
  • Program C : a processing cycle: 12 msec of processing followed by 1 I/O operation, repeated 20 times.
  • Program D : a processing cycle: 9 msec of processing followed by 1 I/O operation, repeated 100 times.
• Each I/O request takes 6 msec. to process.
• The interrupt timer is always set/re-set to produce an interrupt signal after 10 msec.
• The Operating System service routines take no significant amount of time.
• Dispatching is done on a strict FIFO basis.

Process State Progression

Time (msec.)	Activity
00	A is dispatched Dispatch Queue: (B,C,D)
10	Timer runout A to end of D.Q. B is dispatched Dispatch Queue: (C,D,A)
15	B requests I/O (to be completed at 21 msec) Timer is reset C is dispatched Dispatch Queue: (D,A)
21	B's I/O is complete B is added to the D.Q. Dispatch Queue: (D,A,B) Control returned to C (timer not reset)
25	Timer runout C to end of D.Q. D is dispatched Dispatch Queue: (A,B,C)