The evolution of two stacks in bounded space and random walks in a triangle. (English) Zbl 0602.68029

Mathematical foundations of computer science, Proc. 12th Symp., Bratislava/Czech. 1986, Lect. Notes Comput. Sci. 233, 325-340 (1986).
[For the entire collection see Zbl 0596.00021.]
We analyse a simple storage allocation scheme in which two stacks grow and shrink inside a shared memory area. To that purpose, we provide analytic expressions for the number of two-dimensional random walks in a triangle with two reflecting barriers and one absorbing barrier.
We obtain probability distributions and expectations of characteristic parameters of that shared memory scheme, namely the sizes of the stacks and the time until the system runs out of memory. This provides a complete solution to an open problem posed by D. E. Knuth in ”The art of computer programming”, Vol. 1 (London) (1968; Zbl 0191.179).


68N25 Theory of operating systems