The optimal implementation of n FIFO-queues in single-level memory

In many applications there is a problem of allocation of multiple FIFO-queues in single-level memory. Earlier in other papers some models and algorithms of optimal allocation of these data structures have been proposed. In this paper we consider more general models and algorithms.

There are two fundamentally different ways of organizing work with queues - consecutive and linked allocation. For sequential presentation each of them should be allocated in its own part of memory. In this case we will have losses of memory when any queue overflow and other queues don't overflow. The linked list implementation is the second method. In this view the data structure is stored as a list. In this case any number of elements of the lists can coexist in the memory area until the free memory is exhausted. But on the other hand, this approach requires an additional link field for each element. As the criterion we considered the part of lost elements. It is reasonably to minimize this value when the overflow of queue is not the emergency situation. I.e. when the queue takes all allocated memory all the elements will be lost until then the free memory will appear (I.e. until then the expulsion of the element from queue). Such state of the queue is named the state of "reset tail". This scheme is used for example in the routers. In this paper we considered linked and sequential presentation of queues, calculated the part of time which the system is situated in the state of "reset tail", and found the optimal partition of memory in the case of sequential presentation.