1302 E. A. AKSENOVA ET AL.

time for paged implementation. So for some probabilistic

characteristics of the queues the linked list implementa-

tion can be better than the page implementation.

Comparing the average time of the random walk for

consecutive and paged implementations, notice that the

average time for consecutive implementation is basically

less than the upper estimate Tmax for paged implementa-

tion. However, for some probabilistic characteristics of

the queues the average time for consecutive implementa-

tion is greater than the upper estimate Tmax for paged

implementation. Also, for practice it can be interesting to

analyze the consecutive implementation of the queues,

when the memory isn’t divided optimum depending on

probabilistic characteristics of the queues, but simply—

fifty-fifty. It is logically, when we don’t know probabil-

istic characteristics of the queues beforehand. Then as a

mathematical model we have two-dimensional random

walk on the integer lattice in the square 0 ≤ x1 < m/2, 0 ≤

x2 < m/2, but for the linked list implementation we have

two-dimensional random walk on the integer lattice in the

triangular area 0 ≤ x1 + x2 <m/2 + 1. As can be seen from

comparison of the lines with numbers 3, 8, 9, 15 in the

Table 1 and in the Ta ble 2, the consecutive implementa-

tion can be worse than linked.

Though greater part of the triangular area lies inside the

square and only two states (m/2, 0) and (0, m/2) are ab-

sorbing for the square, but nonrecurring for the triangle,

for some probabilistic characteristics of the queues it is

enough that the average time of the random walk in the

triangle became greater than in the square. For example,

in line 3 we have a situation, when the insertion in the first

queue occurs with high probability p1 = 0.6, but all rest

probabilities is alike. In this case the consecutive imple-

mentation is worse than linked. Obviously, this occurs

because greater part of the random walk paths is absorbed

in the point, which lies outside of absorbing borders of the

square, but is absorbing state for the triangle.

8. References

[1] D. E. Knuth, “The Art of Computer Programming,” Vol.

1, Addison-Wesley, Reading, 2001.

[2] A. V. Sokolov, “About Storage Allocation for Imple-

menting Two Stacks,” Automation of Experiment and

Data Processing, Petrozavodsk, 1980, pp. 65-71 (in Rus-

sian).

[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 Algori-

thms,” Journal of Computational 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. Aksenova, 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 Manage-

ment 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 Allocation of Two FIFO-Queues in the

Bounded Area of Memory,” Control Systems and Infor-

mation 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.

Copyright © 2011 SciRes. AM