An approximate analysis of the LRU and FIFO buffer replacement schemes

ABSTRACT

In this paper, we develop approximate analytical models for predicting the buffer hit probability under the Least Recently Used (LRU) and First In First Out (FIFO) buffer replacement policies under the independent reference model. In the case of the analysis of the LRU policy, the computational complexity for estimating the buffer hit probability is O(KB) where B is the size of the buffer and K denotes the number of items having distinct access probabilities. In the case of the FIFO policy, the solution algorithm is iterative and the computational complexity of each iteration is O(K). Results from these models are compared to exact results for models originally developed by King [KING71] for small values of the buffer size, B, and the total number of items sharing the buffer, D. Results are also compared with results from a simulation for large values of B and D. In most cases, the error is extremely small (less than 0.1%) for both LRU and FIFO, and a maximum error of 3% is observed for very small buffer size (less than 5) when the access probabilities are extremely skewed. To demonstrate the usefulness of the model, we consider two applications. In our first application, we compare the LRU and FIFO policies to an optimal static buffer allocation policy for a database consisting of two classes of data items. We observe that the performance of LRU is close to that of the optimal allocation. As the optimal allocation requires knowledge of the access probabilities, the LRU policy is preferred when this information is unavailable. We also observe that the LRU policy always performs better than the FIFO policy in our experiments. In our second application, we show that if multiple independent reference streams on mutually disjoint sets of data compete for the same buffer, it is better to partition the buffer using an optimal allocation policy than to share a common buffer.

REFERENCES

• AVEN76: Aven, O.I., L.B. Boguslavsky, and ~. A. Kogan, "Some Results on Distribution-Free Analysis of Paging Algorithms," IEEE Transactions on Computers, Vol. C-25, No. 7, pp. 737-745, July 1976.
• BABA83: Babaoglu, O. and D. Ferrari, "Two-Level Replacement Decisions in Paging Stores," IEEE Transacgions on Computers, Vol. C- 32, No. 12, pp. 1151-1159, December 1983.
• COFF73: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• DAN89: Dan, A., D. Dias and P. S. Yu, "Buffer Model under Skewed Data Access for a Data Sharing Environment" (Work in progress).
• FLAJ87: Flajolet, P., D. Gardy and L. Thimonier, "Birthday Paradox, Coupon Collectors, Caching Algorithms and Self-organizing Search", Tech Rep. 720 INRIA, Domaine Voluceau, Rocquencourt, BP 105 78153 Le Chesnay Cedex (France), August 1987.
• FOX66: Fox, B.,"Discrete Optimization via Marginal Analysis," Managemen$ Science, Vol. 13, pp. 210-216, November 1966.
• FRAN74: P. A. Franaszek , T. J. Wagner, Some Distribution-Free Aspects of Paging Algorithm Performance, Journal of the ACM (JACM), v.21 n.1, p.31-39, Jan. 1974 [doi>10.1145/321796.321800]
• KEAR89: J. P. Kearns , S. DeFazio, Diversity in database reference behavior, ACM SIGMETRICS Performance Evaluation Review, v.17 n.1, p.11-19, May 1989
• KING71: King, W. F., "Analysis of Paging Algorithms," In Proc. IFIP Congress, pages 485- 490, Ljublanjana, Yugoslavia, aug 1971.
• LANG77: Tomás Lang , Christopher Wood , Eduardo B. Fernández, Database buffer paging in virtual storage systems, ACM Transactions on Database Systems (TODS), v.2 n.4, p.339-351, Dec. 1977 [doi>10.1145/320576.320585]
• RAO78: Gururaj S. Rao, Performance Analysis of Cache Memories, Journal of the ACM (JACM), v.25 n.3, p.378-395, July 1978 [doi>10.1145/322077.322081]
• SACC87: Giovanni Maria Sacco, Index Access with a Finite Buffer, Proceedings of the 13th International Conference on Very Large Data Bases, p.301-309, September 01-04, 1987
• SMIT82: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• STON89: Stone, H. S., .}. L. Wolf, and J. Turek, Optimal Partitioning of Cache Memory, Research Report RC14444 (64697), IBM, March 1989.
• TENG84: Teng, J. Z. and R. A. Gumaer, "Managing IBM Database 2 Buffers to Maximize Performance, "IBM System Journal, Vol. 23, No. 2, pp. 211-218, t984.
• VAN89: J.L. van den Berg, private communication, November 1989.
• VERK85: A. Inkeri Verkamo, Empirical results on locality in database referencing, Proceedings of the 1985 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.49-58, August 1985, Austin, Texas, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling
      D.4.8 Performance
          Subjects: Modeling and prediction

  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Design, Measurement, Performance