Computer Multitasking Multiprogramming Cooperative Multitasking

At any point in time only one task is said to be running, meaning that the CPU is actively executing instructions for that task. Multitasking solves the problem by scheduling which task may be the one running at any given time, and when another waiting task gets a turn. The act of reassigning a CPU from one task to another one is called a context switch. When context switches occur frequently enough the illusion of concurrency is achieved. Even on computers with more than one CPU (called multiprocessor machines), multitasking allows many more tasks to be run than there are CPUs.

Operating systems may adopt one of many different scheduling strategies, which generally fall into the following categories:

Nowadays, the term time-sharing is seldom used, being replaced by simply multitasking.

1 Multiprogramming

In the early days of computing, CPU time was expensive, and peripherals very slow. When the computer ran a program that needed access to a peripheral, the CPU would have to stop executing program instructions while the peripheral processed the data. This was deemed very inefficient.

The first efforts to create multiprogramming systems took place in the 1960s. Several different programs were loaded in the computer memory, and the first one began to run. When the first program reached an instruction waiting for a peripheral, the context of this program was stored away, and the second program in memory was given a chance to run. The process continued until all programs finished running.

Multiprogramming doesn't give any guarantee that a program will run in a timely manner. Indeed, the very first program may very well run for hours without needing access to a peripheral. As there were no users waiting at an interactive terminal, this was no problem : users handed a deck of punched cards to an operator, and came back a few hours later for printed results. Multiprogramming greatly reduced the waiting.

2 Cooperative multitasking

When computer usage evolved from batch mode to interactive mode, multiprogramming was no longer a suitable approach. Each user wanted to see his program running as if it was the only program in the computer. Time sharing had to be used.

Early multitasking systems consisted of suites of related applications that voluntarily ceded time to each other. This approach, which was eventually supported by many computer operating systems, is today known as cooperative multitasking. Although it is rarely used in larger systems, Microsoft Windows prior to Windows 95, and MacOS prior to OS X both used cooperative multitasking to enable the running of multiple applications simultaneously.

Cooperative multitasking has many shortcomings. For one, a cooperatively multitasked system must rely on each process to regularly give time to other processes on the system. A poorly designed program, or a "hung" process, can effectively bring the system to a halt. The design requirements of a cooperatively multitasked program can also be onerous for some purposes, and may result in irregular (or inefficient) use of system resources.

3 Preemptive multitasking

To remedy this situation, most time-sharing systems quickly evolved a more advanced approach known as preemptive multitasking. On a such a system, a hardware system (not included on many early machines) can "interrupt" a running process, and direct the processor to execute a different piece of code. A system designed to take advantage of this feature need not rely on the voluntary ceding of processor time by individual processes. Instead, the hardware interrupt system can be set to "preempt" a running process and give control back to the operating system software, which can later restore the preempted process at exactly the point where it was interrupted. Programs "preempted" in such a manner need not explicitly give time to other processes; as far as a programmer is concerned, software programs can be written as though granted uninterrupted access to the CPU, except for some uncertainty about exactly when the program will complete.

Preemptive multitasking allows the computer system to more reliably guarantee each process a regular "slice" of operating time. It also allows the system to rapidly deal with important external events like incoming data, which might require the immediate attention of one or another process.

At any specific time, processes can be grouped into two categories: those that are waiting for input or output (called " I/O boundIO bound refers to a condition in which the time it takes to complete a computation is determined principally by the speed of IO operations. Compare to Compute bound. This circumstance arises whenever the amount of data necessary to the computation is muc"), and those that are fully utilizing the CPU (" CPU boundCPU bound refers to a condition where the time to complete a computation is determined principally by the speed of the central processor and main memory. More literally, it means that the computation is keeping the processor utilization high, and that the"). In early systems, processes would often "poll", or "busywait" while waiting for requested input (such as disk, keyboard or network input). During this time, the process was not performing useful work, but still maintained complete control of the CPU. With the advent of interrupts and preemptive multitasking, these I/O bound processes could be "blocked", or put on hold, pending the arrival of the necessary data, allowing other processes to utilize the CPU. As the arrival of the requested data would generate an interrupt, blocked processes could be guaranteed a timely return to execution.

Although multitasking techniques were originally developed to allow multiple users to share a single machine, it soon became apparent that multitasking was useful regardless of the number of users. Many operating systems, for mainframes down to single-user personal computers, have recognized the usefulness of multitasking support for a variety of reasons. Multitasking makes it possible for a single user to run multiple applications at the same time, or to run "background" processes while retaining control of the computer.

4 Real time

Another reason for multitasking was in the design of real-timeAn operation within a larger dynamic system is called a real-time operation if the combined reaction- and operation-time of a task is shorter than the maximum delay that is allowed, in view of circumstances outside the operation. The task must also occur computing systems, where a number of possibly unrelated external activities needed to be controlled by a single processor system. In such systems a hierarchical interrupt system was coupled with process prioritization to ensure that key activities were given a greater share of available process time.

5 Multithreading

With the introduction of virtual memory it became useful to distinguish between multitasking of processes and threads. Tasks which share the same virtual memory space are called threads. Threads are described as lightweight because switching between threads does not involve changing the virtual memory context. Processes were distinguished by the fact that each had its own virtual memory space, so that it appeared to have the entire memory to itself, and could contain multiple threads running in that memory. Operating system functions are typically mapped into each virtual address space and interrupt handling typically runs in whichever memory context is in place when the interrupt occurs, so programs are still vulnerable to malfunctioning system code.

6 Memory protection

When multiple programs are present in memory, an ill-behaved program may (inadvertently or deliberately) overwrite memory belonging to another program, or even to the operating system itself.

The operating system therefore restricts the memory accessible to the running program. A program trying to access memory outside its allowed range is immediately stopped before it can do any change to memory belonging to some other process.

Another key innovation was the idea of privilege levels. Low privilege tasks are not allowed some kinds of memory access and are not allowed to perform certain instructions. When a task tries to perform an unprivileged operation an interrupt occurs and a supervisory program running at a higher level is allowed to decide how to respond. This created the possibility of virtualizing the entire system, including virtual peripheral devices. Such a simulation is called a virtual machine operating system. Early virtual machine systems did not have virtual memory, but both are common today.

7 Programming in a multitasking environment

Processes that are entirely independent are not much trouble to program. Most of the complexity in multitasking systems comes from the need to share computer resources between tasks and to synchronize the operation of co-operating tasks.

Large computer systems were sometimes built with a central processor and some number of I/O processors, a kind of asymmetric multiprocessing. One use for interrupts is to allow a simpler processor to simulate the dedicated I/O processors that it did not have.

Over the years, multitasking systems have been refined. Modern operating systems generally include detailed mechanisms for prioritizing processes, while symmetric multi-processing has introduced new complexities and capabilities.

<Hide>

Home > Computer multitasking