Modeling Multiprogramming

Modeling Multiprogramming

When multiprogramming is used, the CPU utilization can be improved. Crudely put, if the average process computes only 20% of the time it is sitting in memory, with five processes in memory at once, the CPU should be busy all the time. This model is unrealistically hopeful, however, since it tacitly assumes that all five processes will never be waiting for I/O at the same time.

A better model is to look at CPU usage from a probabilistic viewpoint. Assume that a process spends a fraction p of its time waiting for I/O to complete. With n processes in memory at once, the probability that all n processes are waiting for I/O (in which case the CPU will be idle) is pn.  The CPU utilization is then given by the formula

          CPU utilization = 1 - pn

The following figure shows the CPU utilization as a function of n, which is called the degree of multiprogramming.

CPU utilization as a function of the number of processes in memory

From the figure it is clear that if processes spend 80% of their time waiting for I/O, at least 10 processes must be in memory at once to get the CPU waste below 10%. When you understand that an interactive process waiting for a user to type something at a terminal is in I/O wait state, it should be clear that I/O wait times of 80% and more are not abnormal. But even on servers, processes doing a lot of disk I/O will sometimes have this percentage or more.

For the sake of complete correctness, it should be pointed out that the probabilistic model just explained is only an estimate. It absolutely supposes that all n processes are independent, meaning that it is quite acceptable for a system with five processes in memory to have three running and two waiting. But with a single CPU, we cannot have three processes running at once, so a process becoming ready while the CPU is busy will have to wait. Thus the processes are not independent. A more correct model can be constructed using queueing theory, but the point we are making - multiprogramming lets processes use the CPU when it would otherwise become idle - is, of course, still valid, even if the true curves of above figure are somewhat different from those shown in the figure.

Although the model of above figure is simple-minded, it can however be used to make particular, although approximate, predictions about CPU performance. Assume, for instance, that a computer has 512 MB of memory, with the operating system taking up 128 MB and each user program also taking up 128 MB. These sizes allow three user programs to be in memory at once. With an 80% average I/O wait, we have a CPU utilization (ignoring operating system overhead) of 1 - 0.83 or about 49%. Adding another 512 MB of memory allows the system to go from three-way multiprogramming to seven-way multiprogramming, hence raising the CPU utilization to 79%. In other words, the additional 512 MB will raise the throughput by 30%.

Adding yet another 512 MB would only increase CPU utilization from 79% to 91%, hence raising the throughput by only another 12%. Using this model the computer's owner might decide that the first addition is a good investment but that the second is not.


multiprogramming, memory, process