Multiprogramming

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.

Timesharing
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.

Multiprogramming

Multiprogramming is a rudimentary form of parallel processing in which several programs are run at the same time on a uniprocessor. Since there is only one processor, there can be no true simultaneous execution of different programs. Instead, the operating system executes part of one program, then part of another, and so on. To the user it appears that all programs are executing at the same time.
If the machine has the capability of causing an interrupt after a specified time interval, then the operating system will execute each program for a given length of time, regain control, and then execute another program for a given length of time, and so on. In the absence of this mechanism, the operating system has no choice but to begin to execute a program with the expectation, but not the certainty, that the program will eventually return control to the operating system.
If the machine has the capability of protecting memory, then a bug in one program is less likely to interfere with the execution of other programs. In a system without memory protection, one program can change the contents of storage assigned to other programs or even the storage assigned to the operating system. The resulting system crashes are not only disruptive, they may be very difficult to debug since it may not be obvious which of several programs is at fault.

Multiprogramming
Early computers ran one process at a time. While the process waited for servicing by another device, the CPU was idle. In an I/O intensive process, the CPU could be idle as much as 80% of the time. Advancements in operating systems led to computers that load several independent processes into memory and switch the CPU from one job to another when the first becomes blocked while waiting for servicing by another device. This idea of multiprogramming reduces the idle time of the CPU. Multiprogramming accelerates the throughput of the system by efficiently using the CPU time.
Programs in a multiprogrammed environment appear to run at the same time. Processes running in a multiprogrammed environment are called concurrent processes. In actuality, the CPU processes one instruction at a time, but can execute instructions from any active process.

As the illustration shows,  CPU utilization of a system can be improved by using multiprogramming. Let P be the fraction of time that a process spends away from the CPU. If there is one process in memory, the CPU utilization is (1-P). If there are N processes in memory, the probability of N processes waiting for an I/O is P*P...*P (N times). The CPU utilization is ( 1 - P^N ) where N is called the multiprogramming level (MPL) or the degree of multiprogramming. As N increases, the CPU utilization increases. While this equation indicates that a CPU continues to work more efficiently as more and more processes are added, logically, this cannot be true. Once the system passes the point of optimal CPU utilization, it thrashes.
(For more on performance issues of OS, refer to Operating System Performance Module )
In order to use the multiprogramming concept, processes must be loaded into independent sections or partitions of memory. So, main memory is divided into fixed-sized or variable-sized partitions. Since a partition may not be large enough for the entire process, virtual memory is implemented to keep the processes executing. The answers to several questions are important to implementing an efficient virtual memory system in a multiprogrammed environment.