BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-77-139
       ENTRY:: December 01, 1994
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: PROPERTIES AND APPLICATIONS OF THE LEAST-RECENTLY-USED STACK
               MODEL
        TYPE:: Technical Report
      AUTHOR:: Rau, B. Ramakrishna
        DATE:: May 1977
       PAGES:: 42
    ABSTRACT:: The Least-Recently-Used Stack Model (LRUSM) is known to be a
               good model of temporal locality. Yet, little analysis of this
               model has been performed and documented. Certain properties
               of the LRUSM are developed here. In particular, the concept
               of the Stack Working Set is introduced and expressions are
               derived for the forward recurrence time to the next reference
               to a page, for the time that a page spends in a cache of a
               given size and for the time from last reference to the page
               being replaced. The fault stream out of a cache memory is
               modelled and it is shown how this can be used to partially
               analyze a multilevel memory hierarchy. In addition, the Set
               Associative Buffer is analyzed and a necessary and sufficient
               condition for the optimality of the LRU replacement algorithm
               is advanced.
       NOTES:: [Adminitrivia V1/Prg/19941201]
         END:: STAN//CSL-TR-77-139