Multiprogramming Operating System
The concept of multiprogramming was introduced to minimize the idle time of CPU. it is based on the idea of organizing multiple jobs in a system so that its CPU always has something to execute. How this is done explain below
What is Multiprogramming
In Both manual loading and batch processing, jobs are loaded into a system and processed one at a time.
Once loaded a job remains in main in main memory until its execution is over, and next job is loaded only after the completion of the current job.
A job does not need CPU for the entire duration of its processing because, in addition to computing (for which CPU is needed), it often needs to perform I/O operations (such as reading/writing of data from/to tape/disk, waiting for data input from keyboard/mouse, and printing of results) during the course of its processing.
In fact, depending on CPU utilization during the course of processing, jobs are broadly classified into two types:
These jobs mostly perform computations with little I/O operations. Hence, their CPU utilization is very high.
Programs used for scientific and engineering computations usually fall into this category of jobs.
These jobs mostly perform I/O operations with little computation. Hence, their CPU Utilization is very high.
Programs used for commercial data processing applications usually fall in this category of jobs. In a uniprogramming system, CPU is idle whenever the job being currently processed performs I/O operations.
CPU idle time may not be significant for CPU-bound jobs, but it may be of the order of 80-90% for I/O-bound jobs. Moreover, since I/O devices are slower than CPU by 20 to 100 times, CPU idle time is significant even for CPU-bound jobs.
Multiprogramming is interleaved execution of two or more different and independent programs by a computer fig (a) has already introduced the notation of two programs (operating system and user program) resident simultaneously in the main memory of a computer.
This concept is carried a step further in multiprogramming by enabling two or more user programs to reside simultaneously in the main memory and carrying out their interleaved execution.
With multiple user programs residing simultaneously in the user program area of main memory, whenever a user program that was executing (using CPU) goes to perform I/O operations, CPU is allocated to another user program in main memory that is ready to use CPU, instead of allowing CPU to remain idle.
CPU switches from one program to another almost instantaneously. Hence, in multiprogramming, several user programs share CPU time to keep it busy.
Note that Multiprogramming does not mean execution of instruction form several programs simultaneously.
Rather, it means that multiple programs are available to CPU (stored in main memory) and a portion of one is executed, then a portion of another, and so on.
As a CPU can execute only one instruction at a time, only one of the programs residing in main memory uses the CPU for executing its instructions at any instance of time.
Simultaneous execution of more than one program with a single CPU is impossible. In some multiprogramming systems, only a fixed number of jobs can be processed concurrently (multiprogramming with fixed tasks-MFT), while in others the number of jobs can vary (multiprogramming with variable tasks-MVT).
Fig (b) shows a typical scenario of jobs in a multiprogramming system. At the time instance shown, there are three user jobs(A, B, C ) residing in memory out of job A is performing I/O operation (writing to disk), job B is executing (utilizing CPU time), and job C is waiting for CPU to become free.
Actually, as shown in figure (c), in the case of multiprogramming, all jobs residing in main memory are in one of the following three states:
- Running (it is using CPU)
- Blocked (it is performing I/O operations)
- Ready (it is waiting for CPU to be assigned to it)
In Fig (b) jobs A, B, and C are in blocked, running and ready states, respectively.
As soon as job B relinquishes CPU (its execution is over or it needs to perform some I/O operations), the CPU is giving to job C (because it is in a ready state) and it starts executing.
Meanwhile, if job A completes output operations, its state converts from blocked to ready.
Hence, in multiprogramming, CPU is never idle as long as there is always some job to execute.
Note that although many jobs may be in ready and blocked states, only one job can be running at any instant, because only one CPU is present.
The area occupied by each job residing simultaneously in main memory is known as a memory partition.
The actual number of partitions, and hence jobs, allowed in main memory at any given time depends on the operating system.
Moreover, jobs awaiting entry into main memory are queued on a fast secondary storage device such as magnetic disk.
A job from this queue is loaded into main memory whenever a memory partition becomes free (this job occupying that partition complete its execution).
Requirement of Multiprogramming Systems
Multiprogramming systems have better throughput than uniprogramming system because CPU idle time is reduced drastically.
However, they are more sophisticated because they require the following additional hardware and software features:
Multiprogramming requires large main memory to accommodate a good number of user programs along with an operating system.
Multiprogramming requires a memory protection mechanism to prevent a job (in one memory partition) from changing another jobs program/data (in another memory partition).
A combination of hardware and software protection mechanism is used for this. It prevents one job from addressing beyond the limits of its own allocated memory area.
job Status Preservation
In multiprogramming, when a running job is blocked for I/O processing, CPU is taken away from it and given to another job that is ready for execution.
The blocked job resume its execution sometime later. However, this requires preserving the jobs complete status information when CPU is taken away from it and restoring this information back before CPU is given to it again.
To enable this, the operating system maintains a process control block (PCB) for each loaded process.
Fig (d) shows a typical process control block.
with this arrangement, before taking away CPU from a running process, its status is preserved in its PCB.
The status is restored back before the process resumes execution when CPU is given to it again later.
Hence, the process can continue execution without any problem.
proper job Mix
A proper mix of I/O-Bound and CPU-bound jobs is required to overlap the operations of CPU and I/O devices effectively.
If all loaded job needs I/O at the same time, CPU will again be idle. Hence, jobs resident simultaneously in main memory should contain a good mix of CPU-bound and I/O-bound jobs so that at least one job is always ready to utilize CPU.
In a multiprogramming system, often there are multiple jobs in a ready state (waiting for CPU to be allocated). Hence, when CPU becomes free, an operating system must decide which of these ready jobs should be allocated to CPU for execution.
part of the operating system that takes this decision is called CPU scheduler, and the algorithm it uses for this is called CPU scheduling.
You may like: