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

doi:10.4236/am.2011.210180

Paper Menu >>

Journal Menu >>

Applied Mathematics, 2011, 2, 1297-1302

doi:10.4236/am.2011.210180 Published Online October 2011 (http://www.SciRP.org/journal/am)

Optimal Implem entation of Two FIFO-Queues in

Single-Level Memory

Elena A. Aksenova, Andrew V. Sokolov

Institute of Applied Mathematical Research, Karelian Research Center,

Russian Academy of Sciences, Petrozavodsk, Russia

E-mail: [email protected], [email protected]

Received November 19, 2010; revised January 11, 2011; accepted January 18, 2011

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.

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

Implementation, Paged Implementation

1. Introduction

Let two stacks grow towards each other in the shared

memory of size m. D. Knuth set the task of constructing a

mathematical model of this process [1]. In [2-6] a mathe-

matical model of the process was constructed as two-

dimensional random walk in a triangle with two reflecting

and one absorbing barriers. In [7-8] we consider the

problem of one and two stacks managing in two-level

memory. This paper proposes mathematical models and

optimal algorithms of two FIFO-queues control [9]. These

data structures are often used in control and automation

systems.

In the case of single-level memory, several allocation

methods of FIFO-queues in the memory may be used [1].

The first method (Garvic’s algorithm) is the consecutive

allocation of one queue after another. In this case we have

memory losses due to the fact that when any queue over-

flow, other queue can have free memory units. The linked

list implementation is the second method. In this case any

number of lists can coexist inside a shared area of memory

until the list of free memory isn’t exhausted. On the other

hand, this method requires an additional link field for each

element. The third method is storage of elements in the

linked lists of fixed size pages. In this case we have

memory losses of the first and the second types.

On the basis of proposed models the methods of queues

implementation are compared, the optimality criterion—

maximizing of the average number of operations, per-

formed with queues until memory overflow. Execution

time of each operation is constant and it isn’t included in

the optimality criterion. However, it is important to take

into account the specific of hardware and software in the

queues implementation methods. In [1] provides such

time assessment of element insertion in the stack. When

consecutive implementation is used, it equals 12 cycles,

and when linked list—it equals 17 cycles. For the opera-

tion of element deletion this assessments are equal ap-

proximately.

2. Consecutive Implementation of Two

FIFO-Queues

Assume that we want to work with two consecutive cir-

cular FIFO-queues in the single-level memory of size m.

Denote the insertion and deletion probabilities of the

elements in the first queue by p1 and q1, in the second

queue—by p2 and q2, the probability of operation which

doesn’t change the queue length (for example only read-

ing)—by r, where p1 + q1 + p2 + q2 + r = 1. Denote the

current lengths of queues by x1 and x2, the length of

memory, separated to the first queue—by s, to the second

queue—by n-s (Figure 1). The value n = m – 2 is the total

maximal size of two queues, because one memory ele-

ment remains free [1] for the circular realization of FIFO-

queue.

As a mathematical model we have two-dimensional

random walk on the integer lattice in the bounded area

0 ≤ x1 < s + 1, 0 ≤ x2 < n – s + 1 (Figure 2) with the tran-

sition probabilities : p1—to the right, q1—to the left, p2—

1298 E. A. AKSENOVA ET AL.

Figure 1. Consecutive allocation.

Figure 2. Random walk area.

upward, q2—downward, r—to remain on the place. The

random walk begins at the state x1 = x2 = 0, where the

lines x1 = –1 and x2 = –1 are reflecting barriers, the lines

x1 = s + 1 and x2 = n – s + 1—absorbing barriers. The

problem is to choose the value s so that the expectation of

the random walk time, until the absorption occurs, would

be maximal. Number the points of walk area top-down

and right to left beginning by 0. These points correspond

to the nonrecurring states of the Markov chain [10]. We

have (s + 1) (n – s + 1) such states.

The tasks are solved with the apparatus of absorbing

Markov chains. The proposed algorithm of states num-

bering makes possible to estimate the transition matrix,

corresponding to the Markov chain.

Theorem 2.1 At the given states numbering, memory

size m and value s the matrix Q has the structure:

kk kk

zz kk kk

kk kk

QAB





























where

 

11,zs nskns 

the submatrixes have the structures:

Arq

prq















































the submatrix kk





has the same structure as kk



, but

value q1 is added to the each element of the main diago-

nal.

The Proof is based on the mathematical induction me-

thod.

3. Linked List Implementation of Two

FIFO-Queues

For linked list implementation it is enough to have one-

linked list of elements (Figure 3). Each queue element

consists of two memory units of the same size. The first

unit contains stored information and the second unit

contains a pointer to the following element of list.

Denote the current lengths of queues by x1 and x2, the

pointers to the first queue elements—by F1 and F2, the

pointers to the last queue elements—by R1 and R2. As-

sume that m is divisible by 2. In such queue implementa-

tion m/2 memory units are spent for the pointers, m/2

memory units are spent for the stored information. As a

mathematical model we have two-dimensional random

walk on the integer lattice in the region 0 ≤ x1 + x2 < m/2

+ 1, where the border x1 + x2 = m/2+1 is an absorbing

barrier (it means that the overflow of some queue occurs),

the borders x1 = –1 and x2 = –1—are reflecting barriers (it

means that the underflow of some queue occurs) (Figure

4).

The random walk begins at the state x1 = x2 = 0. Nec-

essary to find an average time of random walk until the

absorption occurs. It is denoted by T. Then we should

compare it with the average time of consecutive and

paged implementation.

4. Paged Implementation of Two Queues

In this way the queues are implemented as a linked list of

the same size pages. The page size equals x memory units.

Assume that m is divisible by x, and then the number of

pages equals m/x. The number of pointers equals m/x,

E. A. AKSENOVA ET AL.

1299

Figure 3. Linked list implementation.

Figure 4. Random walk area.

x – 1 memory units of each page are used for the infor-

mation storing and one unit is used for the pointer storing

(Figure 5). Also, assume that a control algorithm of free

page list exists. The algorithm gives new page to the

overflowing queue. If the page, which contains a queue

beginning, becomes empty, that this page returns to the

free page list. If the free page list is empty and the tail

page of some queue overflows, the queue overflow occurs.

Notice, if x = 2, it is the linked list implementation, i.e.

possible to consider the linked list implementation of

queues as a special case of the paged implementation.

Denote the current lengths of queues by x1 and x2, the

pointers to the first queue elements—by F1 and F2, the

pointers to the last queue elements—by R1 and R2. As a

mathematical model we have two-dimensional random

walk on the integer lattice in the region 0 ≤ x1 + x2 < m –

m/x + 1, where the border x1 + x2 = m – m/x + 1 is an

absorbing barrier, the borders x1 = –1 and x2 = –1 – are

reflecting barriers (Figure 6). The random walk begins at

the state x1 = x2 = 0.

The task is to find an average time of random walk.

Examine the process of random walk as a finite uniform

Markov chain. Let’s number the nonrecurring states so

like it is presented on the picture below (Figure 7), i.e.

bottom-up, from the left to the right. Determine the

scheme of random walk with the probabilities of transi-

tions so: p1—to the right, q1—to the left, p2—upward,

q2—downward, r – to remain on the place. The number of

memory units without pointers equals n = m – m/x. Then

the number of the nonrecurring states of Markov chain

Figure 5. Paged implementation.







12 1

xxmx



Figure 6. Random walk area.

Figure 7. Random walk area.

equals (n + 1) (n + 2)/2.

Examine the transition probability matrix Q, describing

transitions from the nonrecurring states to the nonrecur-

ring ones. At the given numbering the matrix Q has a

block structure. Obviously, that the matrix structure of the

linked list implementation coincides with the matrix

structure of the page implementation.

Theorem 4.1 At the given states numbering, memory

size m and value s the matrix Q has the structure:

22 21

121 2

kk k

CA B

Crqq



























 

12zn n 2,

E. A. AKSENOVA ET AL.

1300

where the submatrixes have the dimensions kk





, and the structures:



kkk







kkk















,









111 2

rq q

,

















1,,, 3,2.kn n 

The Proof is based on the mathematical induction me-

thod.

Denote by F(x) the average number of memory units,

which actually used for stored data, if overflow occurs.

Let’s suppose that pages stored the queue beginning and

the queue end, are half-filled, if the overflow occurs. The

number of these pages equals 3. Then F(x) = m – m/x –

3(x – 1)/2, m > 0, x > 0. Lets find a maximum of F(x). The

derivative F'(x) =m/x2 – 3/2=0, the root x* = 6m/3.

The second derivative F''(x) = –2m/x3 < 0, m > 0, x > 0,

then x* is the maximum of F(x). Consider the values











and







a optimal page size, because the mathe-

matical model is discrete.

s an

5. Decision of the Task

For decision of the task we shall find the fundamental

matrix N = (I – Q)–1 [10], where I is an unitary matrix. In

the cases of linked list and page implementations we work

with the general resource of the memory. It implies that

when the overflow of some queue occurs, all memory

units are filled. Indeed, page, which contains the queue

beginning, can’t be filled fully. In this case another queue

can’t use this page, but pages, which contains its begin-

ning and end, are not filled fully too. The overflowed

queue can’t use these pages. Actually the random walk

occurs in smaller volume of the memory. So the calcu-

lated average time is the upper estimate for real random

walk time. It is denoted by Tmax. Also, possible to compute

the lower estimate of real random walk time if consider

that when the overflow of some queue occurs, pages,

which contain the beginning of the overflowed queue and

the beginning and the end of another queue, are stored on

one unit.

Then consider the random walk in triangular area 0 ≤ x1

+ x2 < m – m/x + 1 for the upper estimate, and 0 ≤ x1 + x2

< m – m/x – 3(x – 2) + 1 for the lower estimate, where the

summand 3(x – 2) is three pages, which stored on one unit.

Notice that the linked list implementation hasn’t such

losses. For any memory size m we define when the ran-

dom walk area for the linked list implementation is less

than the random walk area for the page implementation in

the case of lower estimate of the average time. Consider

the inequality m – m/x – 3(x – 2)> m/2, m > 0, x > 2.

If x is an arbitrary page size, get 2 < x < m/6, i.e. the

random walk area in the case of linked list implementation

is always less than the random walk area in the case of

paged implementation for lower estimate, if x satisfies the

inequality above. Therefore, if 2 < x < m/6, the average

time of random walk until absorption in the case of linked

list implementation is less than in the case of paged im-

plementation for the lower estimate.

If x = 6m/3, then m – 36m + 12 > 0. Get 24 < m <

∞, i.e. for m > 24 at x = 6m/3 the random walk area in

the case of linked list implementation is always less than

the random walk area in the case of paged implementation

for lower estimate. Therefore, for m > 24 at x = 6m/3

the average time of random walk until absorption in the

case of linked list implementation is less than in the case

of paged implementation for the lower estimate.

6. Results of Numerical Experiments

For this problems solution the algorithms and computa-

tional programs in C++ were developed. Numerical re-

sults are presented in Tables 1-2. The average time of the

random walk is presented in Table 1 for memory size m =

12 in the case, when each consecutive circular FIFO-

queue has the same size of memory. In Table 2 the av-

erage time is presented for different queues implementa-

tions. In the case of consecutive implementation the

memory is divided optimally depending on queues

probabilities. In the first five columns there are the queues

probabilities, in the following three columns there is the

average time of the random walk for A1—consecutive

implementation, A2—paged implementation, A3—linked

list implementation. The column s is the memory size,

assigned to the first queue in the case of consecutive im-

plementation. The column, corresponding to the paged

implementation, contains the optimal page size x and the

average time of random walk. Obviously that at the page

size x = 2 the average time of random walk for the page

implementation is the same as one for the linked list im-

plementation. The column A contains the upper estimate

E. A. AKSENOVA ET AL.

1301

Table 1. The average time for a consecutive implementation of the queues, when the memory is divided equally.

p1 q1 p2 q2 r s T

0.5 0 0.5 0 0 5 9.29

0.2 0.2 0.2 0.2 0.2 5 61.34

0.6 0.1 0.1 0.1 0.1 5 11.59

0.5 0.1 0.3 0.1 0 5 13.1

0.4 0.1 0.4 0.1 0 5 13.8

0.4 0.19 0.4 0.01 0 5 13.28

0.3 0.2 0.2 0.3 0 5 38.77

0.01 0.5 0.19 0.3 0 5 304.85

0.19 0.5 0.01 0.3 0 5 1703.45

0.3 0.3 0.2 0.2 0 5 48.93

0.4 0.4 0.1 0.1 0 5 47.52

0.45 0.45 0.05 0.05 0 5 45.64

0.3 0.3 0.25 0.1 0.05 5 29.16

0.3 0.3 0.1 0.25 0.05 5 68.92

0.45 0.05 0.1 0.4 0 5 14.17

Table 2. The average time for different methods of implementation of queues.

A1 A

2 A

p1 q1 p2 q2 r s T x Tmax Tmin T

0.5 0 0.5 0 0 5 9.29 3 9.0 6.0 7.0

2 0.2 0.2 0.2 0.2 5 61.34 3 73.33 35.76 46.81

0.6 0.1 0.1 0.1 0.1 8 16.31 3 15.57 10.12 11.92

0.5 0.1 0.3 0.1 0 6 13.81 3 13.84 8.93 10.56

0.4 0.1 0.4 0.1 0 5 13.8 3 13.91 8.97 10.61

0.4 0.19 0.4 0.01 0 4 13.44 3 13.65 8.8 10.41

0.3 0.1 0.2 0.3 0.1 6 42.87 3 32.84 25.998 23.94

0.01 0.5 0.19 0.3 0 1 1590.33 1353.63292.27 497.81

0.19 0.5 0.01 0.3 0 8 23720.143 28498.54 1541.23 4091.91

0.3 0.3 0.2 0.2 0 5 48.93 3 59.13 28.83 37.74

0.4 0.4 0.1 0.1 0 7 55.16 3 63.61 30.96 40.57

0.45 0.45 0.05 0.05 0 7 65.5 3 69.51 33.72 44.25

0.3 0.3 0.25 0.1 0.05 4 29.2 3 32.38 18.8 23.15

0.3 0.3 0.1 0.25 0.05 7 97.46 3 113.8849.31 67.5

0.45 0.05 0.1 0.4 0 8 21.46 3 20.86 13.45 15.91

Tmax and the lower estimate Tmin for the average time of

random walk.

7. Conclusions

It is possible to draw a conclusion from numerical results,

that for linked implementation of the queues, when size of

the page x = 2, the average time of random walk before

overflowing of the memory always less than average time

of random walk for consecutive implementation. Also, it

is seen that average time for linked list implementation

lies between the estimates Tmin and Tmax of the average

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.