A Self-biased Replacement Algorithm using the Characteristics of Markovean Program Model

Abstract

In this paper a self-biased replacement algorithm is developed. The algorithm is mostly suited for allocating system programs and library programs under multiprogramming and/or time-sharing environment. With biasing, the system performance is improved. It is also proved that the algorithm is optimal on macroscopic viewpoint. Since each reference string behaves a static referencing pattern, so it is feasible that the algorithm makes the optimal choice in selecting the candidate for replacement by using the characteristics of Markovean program model. And since in the present time and in the future time , system programs and library programs constitute dorminant part of software system, so it is worthy to develop a replacement algorithm using the characteristics of Markovean program model, although pre-runnings of programs are required.