 Applied Mathematics, 2011, 2, 1297-1302 doi:10.4236/am.2011.210180 Published Online October 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. 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: aksenova@krc.karelia.ru, avs@krc.karelia.ru 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 . 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 . 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 . 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  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  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 . 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 kkkkzz kk kkkk kkABCQABCA1, where  11,zs nskns  the submatrixes have the structures: 22222,kkrqpArqprq 11,kkqBq 11,kkpCp the submatrix kkA has the same structure as kkA, 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, Copyright © 2011 SciRes. AM 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. 1mmx1mmx12 1mxxmx 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: 11122 21121 2,kkkk kzkABCA BQCABCrqq  12zn n 2, Copyright © 2011 SciRes. AM E. A. AKSENOVA ET AL. 1300 kwhere the submatrixes have the dimensions kkAA, , and the structures: 1kkkBB1kkkCC21=krqrArrq, 111 2Arq q, 1212=,kqqBqq 1212=,kppCpp 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 x and x 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 , 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 2 Copyright © 2011 SciRes. AM E. A. AKSENOVA ET AL. Copyright © 2011 SciRes. AM 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 A2 A3 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