Early computer systems were extremely expensive to purchase and to operate. Unfortunately they often sat idle as their human operators tended to their duties at a humans pace. Even a group of highly trained computer operators could not work fast enough to keep even the earliest tape-fed batch systems CPU busy. The advent of multiprogramming broke through the utilization barrier by removing most of the human factor in CPU utilization.
In a multiprogramming-capable system, jobs to be executed are loaded into a pool. Some number of those jobs are loaded into main memory, and one is selected from the pool for execution by the CPU. If at some point the program in progress terminates or requires the services of a peripheral device, the control of the CPU is given to the next job in the pool. As programs terminate, more jobs are loaded into memory for execution, and CPU control is switched to another job in memory. In this way the CPU is always executing some program or some portion thereof, instead of waiting for a printer, tape drive, or console input [1].
An important concept in multiprogramming is the degree of multiprogramming. The degree of multiprogramming describes the maximum number of processes that a single-processor system can accommodate efficiently[2]. The primary factor affecting the degree of multiprogramming is the amount of memory available to be allocated to executing processes. If the amount of memory is too limited, the degree of multiprogramming will be limited because fewer processes will fit in memory. A factor inherent in the operating system itself is the means by which resources are allocated to processes. If the operating system can not allocate resources to executing processes in a fair and orderly fashion, the system will waste time in reallocation, or process execution could enter into a deadlock state as programs wait for allocated resources to be freed by other blocked processes. Other factors affecting the degree of multiprogramming are program I/O needs, program CPU needs, and memory and disk access speed[3].
Processes maintained in the computers main memory are considered to be executing concurrently even though the CPU is (usually) capable of executing only one instruction at a time. The number of processes that can be held in memory is dependent on the amount of memory available to the system. That amount may be any combination of real or virtual memory, virtual memory being a portion of on-line mass-storage allocated to hold code in the process of being executed which can not fit into available real memory. If a process is too large to fit into the memory allocated to it, portions of its code may be stored temporarily on disk. When this code is required the operating system will load the code into memory and execution will continue. The management process by which this code is swapped into and out of memory is referred to a paging. A similar system can be used to manage data-segment memory[3] [1].
As the number of processes (degree of multiprogramming) increases in a system that supports paging, the amount of memory available to execute processes in decreases and the number of paging operations required increases. At some point the amount of time the CPU spends paging code and data will drag system performance down. This phenomenon, called "thrashing," is a manifestation of exceeding the degree of multiprogramming for a system [2][3][1].
In contrast to a multiprogramming system, a batch system executes its jobs sequentially, and might be referred to as a "monoprogramming" system (though certain batch systems have monitor programs, which might classify them loosely as multiprogramming systems). Batch systems were developed prior to multiprogramming as a means of increasing efficiency of computer time use. In a batch system, jobs with similar requirements (ie. compiler) are collected together and loaded into the system. Each job is taken sequentially, and the next jobs execution starts after the previous ones stops.
The batch system is not as efficient as the multiprogrammed system due to the fact that the CPU must sit idle while waiting on I/O devices or human input. Unlike a multiprogrammed system, the program in progress always has the ability to fully utilize the CPU and its resources. Enhancements to early batch systems included copying all punch-cards to tape and placing all output onto tape for later printing, both operations having been done on a separate system dedicated to those purposes [1]
Efficient use of computer time was the impetus for the development of multiprogramming systems. Multiprogramming freed the CPU from relying on the inherent slowness of the operator, and permitted it to work while waiting on peripheral devices. Every computer system has a limit to the degree of multiprogramming it will support. This limit is primarily based on the amount of main memory available to the system and the efficiency of the operating systems resource allocation algorithms.
[1] Silberschatz, Abraham and Galvin, Peter B. Operating System Concepts.
pp13-15,330-332,7-13, 1995.
[2]Multiprogramming, http://www.cne.gmu.edu/modules/vm/green/multip.html, Last Visited: Sept. 11,
1997
[3] Madnick and Donovan, J. Operating Systems. pp 506,498-506,1974.
Timesharing, also called "time slicing" or "time division multiplexing", or even "multitasking", is a system whereby system focus is switched between each of its users. Ideally, users of a timesharing system will not be aware that they are sharing the computer with one or more users.
Timesharing came about as an extension of multiprogramming. Old batch systems, including multiprogramming batch systems, were usually isolated from their end-users. Due to this isolation, programmers were required to plan for every contingency in designing the input for their code. Many times a programmer would receive an output printout or a memory dump of their program. Interaction with the computer system was not possible due to the inefficiency introduced by extensive human interaction [1].
Timesharing provided a means by which system users could interact with the computer and the computer could direct its idle time toward other users or other processes. Now programmers could write programs that interacted with the user; they even had the opportunity to debug their code in a live environment rather than a stack of paper printout [1].
To provide service to individual users and maintain their operating environment, timesharing systems employ some means of context switching. In context switching, a users execution environment is loaded into memory, some operation is performed, and then the environment is placed back into temporary storage until the CPU comes back to service the next request [2].
Timeshare systems allowed multiple users access to the same system, so protection must be provided for each users environment and for the operating system itself. Also, timeshare systems had to provide the illusion of immediate system interaction in order to be practical and attractive to users demanding real-time interaction.
To achieve effective user interaction, processes were executed in a defined order, and were only given a certain amount of CPU time. This way everyone gets the CPUs attention at some point, and no one can take complete control. Two common schemes are FIFO and round robin. The FIFO scheme processes requests in the order in which they are received. Unfortunately FIFO is not conducive to interactive processing because it permits jobs to run to completion. Thus short jobs wait for long jobs, and job priority can not be defined [3]
On the other hand, round-robin scheduling is a preemptive method of allocating CPU time. In this scheme, processes gain CPU control in a FIFO method, but after a certain amount of time are stopped, or preempted, and placed back into the queue. It is in this scheme that context switching becomes a central issue. Efficiency in setup and clean up for processes determines the overhead introduced by the system. TSS, the time sharing system for the IBM System 360/67, used a scheduling scheme similar to a combination FIFO/round-robin. [2]
Compared to a timeshare system, the scheduling policy of a batch system is a hybrid of round-robin and FIFO, but with more emphasis on FIFO. Earlier systems relied entirely on a FIFO scheme; one job was loaded into the system and ran to completion before another could start. Later batch systems improved on this theme to provide one job with the CPU for as long as it could execute without requesting an I/O device. Upon such a request, the CPU switched execution to the next job in the queue [1].
To make them practical, timesharing systems usually supported some sort of on-line central file system and a means of organizing it. MUTLICS, Multiplexed Information and Computing Service, was the first timesharing system to support a centralized file system organized hierarchically [4].
Timesharing systems, the evolution of multiprogrammed systems, brought the computer to the user. Utilizing process scheduling and queuing schemes, individual users were provided the illusion of being sole user of the system, unlike batch systems where jobs had the opportunity to capture the attention of the CPU from other users. These systems typically incorporated a shared file system where user code and data could be maintained and developed. The timesharing system leveraged the computing investment and at the same time increased the level of service to the end user.
[1] Silberschatz, Abraham and Galvin, Peter B. Operating System Concepts.
pp15-17,13-15, 1995.
[2] Fister, C. "Timesharing". Encyclopedia of Computer Science.
pp1423-1426, 1969.
[3] Deitel, Harvey M.,. An Introduction to Operating Systems. p 254, 1984.
[4] MULTICS
Features, http://www.best.com/~thvv/features.html, Last Visited: Sept.
11, 1997.