Optimal Implementation of Two FIFO-Queues in Single-Level Memory

ABSTRACT

This paper presents mathematical models and optimal algorithms of two FIFO-queues control in single-level memory. These models are designed as two-dimensional random walks on the integer lattice in a rectangular area for consecutive implementation and a triangle area for linked list implementation.

This paper presents mathematical models and optimal algorithms of two FIFO-queues control in single-level memory. These models are designed as two-dimensional random walks on the integer lattice in a rectangular area for consecutive implementation and a triangle area for linked list implementation.

KEYWORDS

FIFO-Queues, Random Walks, Markov Chains, Consecutive Implementation, Linked List Implementation, Paged Implementation

FIFO-Queues, Random Walks, Markov Chains, Consecutive Implementation, Linked List Implementation, Paged Implementation

Cite this paper

nullE. Aksenova and A. Sokolov, "Optimal Implementation of Two FIFO-Queues in Single-Level Memory,"*Applied Mathematics*, Vol. 2 No. 10, 2011, pp. 1297-1302. doi: 10.4236/am.2011.210180.

nullE. Aksenova and A. Sokolov, "Optimal Implementation of Two FIFO-Queues in Single-Level Memory,"

References

[1] D. E. Knuth, “The Art of Computer Programming,” Vol. 1, Addison-Wesley, Reading, 2001.

[2] A. V. Sokolov, “About Storage Allocation for Implementing Two Stacks,” Automation of Experiment and Data Processing, Petrozavodsk, 1980, pp. 65-71 (in Russian).

[3] A. C. Yao, “An Analysis of a Memory Allocation Scheme for Implementation of Stacks,” SIAM Journal on Computing, Vol. 10, 1981, pp. 398-403. doi:10.1137/0210029

[4] P. Flajolet, “The Evolution of Two Stacks in Bounded Space and Random Walks in a Triangle,” Lecture Notes in Computer Science, Vol. 233, 1986, pp. 325-340. doi:10.1007/BFb0016257

[5] G. Louchard, R. Schott, M. Tolley and P. Zimmermann, “Random Walks, Heat Equation and Distributed Algorithms,” Journal of Com-putational and Applied Mathema- tics, Vol. 53, No. 2. 1994, pp. 243-274. doi:10.1016/0377-0427(94)90048-5

[6] R. S. Maier, “Colliding Stacks: A Large Deviations Analysis,” Random Structures and Algorithms, Vol. 2, No. 4, 1991, pp. 379-421. doi:10.1002/rsa.3240020404

[7] E. A. Akse-nova, A. A. Lazutina and A. V. Sokolov, “Study of a Non-Markovian Stack Management Model in a Two-Level Memory,” Programming and Computer Software, Vol. 30, No. 1, 2004, pp. 25-33. doi:10.1023/B:PACS.0000013438.25368.b4

[8] E. A. Aksenova and A. V. Sokolov, “Optimal Management of Two Parallel Stacks in Two-Level Memory,” Discrete Mathematics and Applications, Vol. 17, No. 1, 2007, pp. 47-56. doi:10.1515/DMA.2007.006

[9] E. A. Aksenova, A. V. Sokolov and A. V. Tarasuk, “About Optimal Allo-cation of Two FIFO-Queues in the Bounded Area of Memory,” Control Systems and Information Technologies, Vol. 3, No. 22, 2006, pp. 62-68 (in Russian).

[10] J. G. Kemeny and J. L. Snell, “Finite Markov Chains, Van Nostrand,” Princeton, New Jersey, 1960.

[1] D. E. Knuth, “The Art of Computer Programming,” Vol. 1, Addison-Wesley, Reading, 2001.

[2] A. V. Sokolov, “About Storage Allocation for Implementing Two Stacks,” Automation of Experiment and Data Processing, Petrozavodsk, 1980, pp. 65-71 (in Russian).

[3] A. C. Yao, “An Analysis of a Memory Allocation Scheme for Implementation of Stacks,” SIAM Journal on Computing, Vol. 10, 1981, pp. 398-403. doi:10.1137/0210029

[4] P. Flajolet, “The Evolution of Two Stacks in Bounded Space and Random Walks in a Triangle,” Lecture Notes in Computer Science, Vol. 233, 1986, pp. 325-340. doi:10.1007/BFb0016257

[5] G. Louchard, R. Schott, M. Tolley and P. Zimmermann, “Random Walks, Heat Equation and Distributed Algorithms,” Journal of Com-putational and Applied Mathema- tics, Vol. 53, No. 2. 1994, pp. 243-274. doi:10.1016/0377-0427(94)90048-5

[6] R. S. Maier, “Colliding Stacks: A Large Deviations Analysis,” Random Structures and Algorithms, Vol. 2, No. 4, 1991, pp. 379-421. doi:10.1002/rsa.3240020404

[7] E. A. Akse-nova, A. A. Lazutina and A. V. Sokolov, “Study of a Non-Markovian Stack Management Model in a Two-Level Memory,” Programming and Computer Software, Vol. 30, No. 1, 2004, pp. 25-33. doi:10.1023/B:PACS.0000013438.25368.b4

[8] E. A. Aksenova and A. V. Sokolov, “Optimal Management of Two Parallel Stacks in Two-Level Memory,” Discrete Mathematics and Applications, Vol. 17, No. 1, 2007, pp. 47-56. doi:10.1515/DMA.2007.006

[9] E. A. Aksenova, A. V. Sokolov and A. V. Tarasuk, “About Optimal Allo-cation of Two FIFO-Queues in the Bounded Area of Memory,” Control Systems and Information Technologies, Vol. 3, No. 22, 2006, pp. 62-68 (in Russian).

[10] J. G. Kemeny and J. L. Snell, “Finite Markov Chains, Van Nostrand,” Princeton, New Jersey, 1960.