A study of replacement algorithms for a virtual-storage computer

IBM Systems Journal, Volume 5, Issue 2, pp. 78-101 (1966).

Belady's paper presents a comprehensive study of virtual-memory replacement algorithms. The study discovered that replacement algorithms which favor recently used blocks (pages) performed better than other algorithms. The paper defines what came to be known as Belady's Min algorithm, a replacement algorithm that always discards the block (page) that will not be needed for the longest time in the future. Although the Min algorithm is not realizable because we cannot predict when the page will be needed, it is used to gauge the effectiveness of other algorithms. The paper also describes the property of locality for program behavior according to which consecutive references to memory are likely to be in the same block. Because Belady's study of replacement algorithms was the first of its kind, papers related to memory management cite it to this day—it is one of the most cited papers of the IBM Technical Journals.