Stacks in a two-level store

Abstract

The total number of stack pushing operations that occur for each stack size in the set of all stack histories when compiling or evaluating an expression of size n is calculated. The expected fraction of operations that use the slow store when implementing a stack in a two-level store is then obtained. Two different paging strategies are then examined, and the fraction of stack pushing operations that are paging operations is obtained for both cases. The results are an application of the techniques of P. Flajolet, J. Françon, and J. Vuillemin for analyzing data structures that are subjected to sequences of operations. © 1981.