G53OPS - Operating Systems

This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)

Modelling Multiprogramming

We assume (and have stated) that multiprogramming can improve the utilisation of the CPU. And, intuitively, this is the case. If we have five processes that use the processor twenty percent of the time (spending eighty percent doing I/O) then we should be able to achieve one hundred percent CPU utilisation. Of course, in reality, this will not happen as there may be times when all five processes are waiting for I/O. However, it seems reasonable that we will achieve better than twenty percent utilisation that we would achieve with monoprogramming.

But, can we model this?

We can build a model from a probabilistic viewpoint.

Assume that that a process spends p percent of its time waiting for I/O. With n processes in memory the probability that all n processes are waiting for I/O (meaning the CPU is idle) is pn.

The CPU utilisation is then given by

CPU Utlisation = 1 - pn

The following graph shows this formula being used (the spreadsheet that produced this graph is available from the web site for this course).


You can see that with an I/O wait time of 20%, almost 100% CPU utilisation can be achieved with four processes.

If the I/O wait time is 90% then with ten processes, we only achieve just above 60% utilisation.

The important point is that, as we introduce more processes the CPU utilisation rises.

The model is a little contrived as it assumes that all the processes are independent in that processes could be running at the same time. This (on a single processor machine) is obviously not possible.

More complex models could be built using queuing theory but we can still use this simplistic model to make approximate predictions.

Assume a computer with one megabyte of memory. The operating system takes up 200K, leaving room for four 200K processes. If we have an I/O wait time of 80% then we will achieve just under 60% CPU utilisation.

If we add another megabyte, it allows us to run another five processes (nine in all). We can now achieve about 86% CPU utilisation. You might now consider adding another megabyte of memory, allowing fourteen processes to run. If we extend the above graph, we will find that the CPU utilisation will increase to about 96%.

Adding the second megabyte allowed us to go from 59% to 86%. The third megabyte only took us from 86% to 96%. It is a commercial decision if the expense of the third megabyte is worth it.

Last Page Back to Main Index Next Page

 

 

 Last Updated : 23/01/2002