Department of Computer Science Course: CS 3725

Variable replacement algorithms

In fixed replacement schemes, two ``anomalies'' can occur -- a program running in a small local region may access only a fraction of the main memory assigned to it, or the program may require much more memory than is assigned to it, in the short term. Both cases are undesirable; the second may cause severe delays in the execution of the program.

In variable replacement algorithms, the amount of memory available to a process varies depending on the locality of the program.

Figure  shows the memory requirements for two separate runs of the same program, using a different data set each time, as a function of time (in clock cycles) as the program progresses.

  
Figure: Memory required for two runs of the same program with different data