Operating Systems : Overview of Concurrent Processing

The term "timesharing" has (in the past) sometimes been used to mean "concurrent processing". However, "timesharing" has also been used to mean several other things including "interactive processing". For this reason, the "timesharing" term will be avoided in this material.

Sharing Time in a Computer

• Optimizing Use Of Time

  • A processor performs instructions at a rate thousands of times faster than external devices and millions of times faster than human beings respond.
  • A processor involved in executing instructions which require input from or output to external devices (or humans), therefore spends most of its time "idle". From an economic perspective, this means that computer owners have paid for something that most of the time is doing nothing.
  • Optimizing use of the processor, therefore, means finding something (useful) for it to do while it would otherwise be "idle" waiting for I/O

• Can "Idle" Time Be Used?

  • In theory, a single program might be able to somehow "look ahead" and request input before the actual input was needed for processing; this would allow the program to continue processing while I/O was occurring. In practice, except for very special cases, this situation does not happen and, in fact, most systems do not provide the ability for application programs to continue processing during I/O.
  • The only alternative, then, is to permit some other program to process while the first is waiting for I/O.
  • In general, this means that (in addition to the Operating System) at least two programs will need to be in memory at the same time. Each program must be confined to its own area of memory and no program can be dependant upon being loaded into memory at any specific location.
  • Without some facility to meet these requirements, the sharing of otherwise idle processor time by two or more programs is not possible.

• Interacting Programs

  • Sometimes programs may be "packaged" so that at various points during its execution one program may require data produced by another program. The first program could (theoretically) do the work itself, but if a second program already exists and is known to work properly, there is no point. A typical "second" program in this environment might be a database engine, a text editor, or a spreadsheet manager.
  • In current MicroSoft Windows environments, this is commonly referred to as Object Linking and Embedding (OLE's).
  • While not always the case, such packages of programs generally do not compete for processor time. The originating program will normally become inactive until the evoked program has completed its processing.

• Occasionally Programs Need To Wait For Their Turns

  • In most cases (excluding the OLE-type situation) the objective is to use time that would otherwise have been wasted while a program is waiting for I/O. In a Utopian environment, the processor would never be idle and no program would need to wait for the processor to become available once its I/O requirements were satisfied.
  • Unfortunately, there is no way that is can be achieved. The processor will become idle sometimes when all programs in memory are waiting for I/O and, at other times, all or most of the programs will have completed any current I/O requirements and be waiting for processor time.

"Batched" Systems

• The Concept of "Batched Tasks"

  • All input required for a program is collected (as a "batch") prior to requesting program execution. Once execution has begun, there is no need to for the very lengthy waits for human interaction and the I/O wait time is reduced significantly. In turn, this means that the amount of otherwise idle processor time used for other programs is also greatly reduced.
  • With large volumes of input data, sorting the data and sequential processing further increase the effective processor use by the "batched" input program and reduce the available time for other processes.

• Scheduling

  • Because there is no need for human or real-time interaction, programs are normally loaded into memory and remain there until their processing has been completed.
  • With limited memory, this means that occasionally (and sometimes, often) when execution of a program is requested, there will not be enough memory available to load it and it will have to wait.
  • The Operating System needs to keep track of what programs are waiting to execute and what programs are currently using which areas of memory.
  • As individual programs complete execution, the Operating System must decide which of possibly several waiting programs should be loaded next and thus get turns executing with others which are still active. This process by the Operating System is call "scheduling".

• Dispatching

  • Whenever the Operating System gains control, once it has completed whatever tasks are required of it, it must decide which of the programs currently loaded in memory should be given control of the processor next.
  • This process of selecting among loaded programs, the next to execute is called "dispatching".
  • Obviously, there is no point in the Operating System dispatching a program which is still waiting for Input or Output, since such a program is not ready to make use of the processor. Therefore, the Operating System must keep track of the state of each program currently loaded.

• The Operating System Needs "Its Turn"

  • In order to manage "scheduling" and "dispatching" (as well as other tasks which might not yet be obvious), the Operating System will need access to processor time, the same as any "application" program.

• How the Operating System Gets "Its Turn"

  • The Operating System is written so as to give control of the processor to other programs (by "Jumping" to instructions within those programs) at appropriate times. Other programs are NOT written to give up control of the processor to the Operating System, or to any other program.
  • Whenever, an application program makes use of one of the Operating System service subroutines, however, the application program losses control of the processor. Although the service subroutine was called to perform some specific function, the Operating System is not compelled to give control back to the calling application program as soon as that function is completed; the Operating System may, in fact, choose to give control to some other application program.
  • Also, whenever a hardware device generates an interrupt signal, this effectively calls an Operating System service routine. The same situation applies as when the currently active application invoked a service subroutine. Once the Operating System gets control, it is free to continue with whatever processing it determines is appropriate (regardless of the purpose for which it was given control). To ensure the Operating System gets control on a regular basis, a special hardware element, called a timer, is normally included in every computer system; the only purpose of such a timer is to generate interrupts.

Interactive Systems

• Human Response Time Factors

  • The I/O delay while waiting for human interaction is much longer than for any other hardware I/O requirement. Therefore, the processor has more time to process other programs while waiting for human interactive responses.
  • Conversely, compared to batched input systems, humans are unwilling to wait for extended periods of time for their program to respond. Scheduling must happen, effectively, "on demand".

• Active vs. Suspended Activities

  • A single user may start one interactive program and then startup and switch to a second program with the intent of eventually returning to the first one.
  • The program the user is currently working with is "active"; it is actively processing instructions for the user at this point in time.
  • The other program typically has no processing tasks to perform until the user "returns" to it; its execution is said to have been "suspended". From the Operating System's perspective, suspended programs should not ever be "dispatched"; they may continue to use memory space, but should the memory be needed for other purposes, they can safely be "swapped out" to disk and only reloaded when the user decides to return to them.

• Foreground vs. Background Activities

  • Sometimes one (or more) secondary programs can be left "running" while the user interacts with (what the user sees as) a primary program.
  • This primary or "foreground" program has priority in access to the processor. Unless the foreground program is waiting for user input, the Operating System will always dispatch to it.
  • Secondary or "background" programs are only dispatched when the foreground program is waiting for human response. Fortunately, in a typical interactive environment, this is most of the time. Background programs basically get their processing done "for free" in time that would otherwise be wasted waiting for interaction.
  • Note that making a batched input program a foreground program and an interactive program a background program would be disasterous.

Security and Program Protection

• Protection Against "Time-Hogging" Programs

  • If the Operating System relied upon gaining control (in order to dispatch to alternate programs for example) upon a program giving up control voluntarily, the program could become involved in a lengthy computation process or possibly even an infinite loop and block any other program from getting its turn at processing within a reasonable amount of time.
  • A hardware "timer" which generates an interrupt signal (as already discussed) is therefore a requirement of any computer system which is to practice concurrent program execution.

• Protection Against Programs That Don't "Play In Their Own Yard"

  • If there is only one program in memory, it is free to access and modify any part of memory it wishes (although if it modifies the Operating System routines, the system may "crash"; but nothing else is harmed except the program itself.
  • When there is more than one program in memory, some method is required to prevent one program from modifying (and thus altering the execution of or possibly causing the "abort" of) another program.
  • Hardware features are required that automatically verify that any address output on the Address Bus is an address within the range of valid addresses for the current program. Any address outside the current program's valid range should be blocked and should cause an interrupt signal, summoning the Operating System to terminate the offending program.

• Some Devices Aren't Meant To Be Concurrently Shared

  • Direct access to I/O devices by application programs also needs to be prevented in a concurrent programming environment.
  • For example, consider the case of two programs which both want to print reports on the same printer. Imagine the output produced if they individually accessed the printer, so that every other character printed was from a different program!
  • As a second example, consider a typical disk record input sequence of operations. The read/write heads of the disk drive are positioned at the correct physical location to read a record and then a record is read; for a second record, the read/write head is assumed to have remained in the same location and a second read operation can often take place without moving the read/write head. If a second program requiring disk activity gains control of the disk drive between the first and second read operations, it will most likely move the read/write head to a new location. The original program will have no way of knowing that this move has occurred and will read its second record (which will turn out to be "garbage") from an unintended location on disk.
  • For these reasons all I/O operations most be forced to go through the Operating System which can keep track of multiple I/O streams (and in the case of printed output, for example, "spool" the output to a disk file for later printing). Prevention of I/O by application programs means that special hardware must exist which permits certain instructions ("Input" and "Output" in this case) only to be executed by the Operating System. As a derived condition, this means that hardware must be able to determine if the current program executing for any instruction is the Operating System.

  
  
  

  ---