Automata which realize replacement algorithms. Nonparametric theory

A hierarchical class of replacement algorithms for use in paged memories is developed. The well-known page replacement algorithms FIFO, LRU and CLIMB are extremal members of this class. The performance of the algorithms is evaluated by simulation and analytical methods. A technique for implementing this class of replacement algorithms with the existing digital hardware is also presented. Under the assumption that the sequence of page requests is statistically independent complete theoretical analysis of these algorithms is provided.