Management Model for Two Parallel FIFO Queues Moving One after Another in Shared Memor
Abstract
Introduction: FIFO queue is a popular data structure in hardware and software applications. Various network devices and embedded operating systems use several FIFO queues located in a shared memory space. There are also multi-core processor architectures where two FIFO queues are allocated for each core. Software and hardware applications used to solve the described problems should improve the device reliability, reducing the average portion of the queue elements lost by overflow. Purpose: The goal is to construct and analyze a mathematical model of operating two FIFO queues moving one after another in a circle in the shared memory. On an odd step, elements are inserted into one of the queues. On an even step, elements are deleted. Both serial and parallel execution of the operations are possible. Results: A mathematical and a simulation models of this process for two queues were constructed, and numerical experiments based on theoretical data were performed. The mathematical model is built as a random walk on an integer pyramid with reflecting screens. An algorithm was proposed for the numbering of states; the form of the matrix of transition states for the obtained regular Markov chain was established; and the corresponding propositions were proved. Another algorithm and software were developed for calculating the average portion of queue elements lost by overflow. The peculiarity of this research is a specific execution of operations with queues: insertion and deletion of elements occur depending on the step (some amendments were made to maintain the homogeneity and regularity of the chain). The operations can be executed in parallel. Practical relevance: The model, algorithm and software complex proposed for the analysis of "One after another" queue movement method can be used in the design of network devices, such as routers, chips with multiple FIFO queues and other software or hardware devices where element loss is permitted but unwanted. Using this model, with given probabilities of the queues, you can choose the best queue representation method, for example, between the classical serial cyclic method and "One after another" method.Published
2016-02-22
How to Cite
Barkovsky, E., & Sokolov, A. (2016). Management Model for Two Parallel FIFO Queues Moving One after Another in Shared Memor. Information and Control Systems, (1), 65-73. https://doi.org/10.15217/issn1684-8853.2016.1.65
Issue
Section
System and process modeling