Queuing

The queuing issue is one of “in what order job should be handled” versus “central processing unit (CPU) and memory utilisation” with the objective being to process the queue as efficiently (quickly) as possible (assuming of course that all jobs are processed properly) or to maximise throughput.

In a FIFO system, or indeed any singular system in which the handling order is dictated by a processing rule based on the order in the queue (e.g. LIFO), the number of processes (utilisation of CPU and memory) is dictated by the makeup of the queue; this utilisation may or may not be efficient. Many real-life systems operate on FIFO queuing (but not all are singular queues – i.e. more than one processing point); supermarket checkouts, stock control, banks and hotel receptions all operate on dealing with the next job or customer before dealing with the following one and a great deal of research has been done into how to more efficiently increase throughput in such operations.

In this situation, throughput is not only subject to the size of the total memory and how much of it is available (some memory will be taken by other processes such as the operating system) but also the makeup of the available memory.
For example, if we have the following available chunks of memory 100k, 30k, 50k, 100k and 80k and the queue is in the order 110k, 100k, 60k and 30k.

The FIFO method of queue processing would first consider the 110k in the queue and would not process it until there was sufficient memory available. Only after this would it move on to consider the 30k that it second in the queue and so on. Throughput could be increased greatly if the system were allowed to consider all items in the queue and decide which items could be processed, based on available memory, to process to avoid “dead” waiting time. The second item in the example queue could have been processed immediately before considering the queue again against available resources. However this system has its issues also because it only takes size v available resources into account and does not consider the priority of the job in the queue; job 1 may not fit with available resources but it relatively more important than anything else in the queue so it is better that we wait for the resources to process it rather than use available resources to process something else and job 1’s completion is delayed by something of lesser importance with the possibility that job 1 could be delayed indefinitely (known as “starvation” in queuing terms).

Complex multi-algorithm queuing systems that consider different priorities and limitations will therefore produce increased throughput as they allow jobs that are better matched to available resources to be considered first based on priority (size, importance or other factors).

References

Glenn, J. (2009) Computer Science: An Overview. 10th ed. Boston: Pearson Education.

Wikipedia: FIFO (computing) [Online]. Available at: http://en.wikipedia.org/wiki/FIFO (Accessed 15 November 2009).

Wikipedia: Multilevel feedback queue [Online]. Available at: http://en.wikipedia.org/wiki/Multilevel_feedback_queue (Accessed 15 November 2009).