#1 posted on Oct 01 2013, 20:44
This paper introduced some replacement algorithms for implementing virtual memory. In order to implement virtual memory, you need to address several problems such as addresses translation, data transferring and the strategy to pull and push data blocks. To analyze the replacement algorithm, the issue of sequence of address reference is mentioned in the first place. Then the author groups replacement algorithms into three major classes according to their use of relevant information, and develops an optimal replacement algorithm for system study purposes.
In most cases, the simulated algorithms generated only two to three times as many replacements as the theoretical minimum. The simulated system was found to be sensitive to changes in block size and memory size. From the viewpoint of replacement efficiency (which disregards the operational effects of external- storage access times), small block sizes appear to be preferable.
The results of the study suggest that a good algorithm is one that strikes a balance between the simplicity of randomness and the complexity inherent in cumulative information. In some cases, too much reliance on cumulative information actually resulted in lower efficiency.