In paged storage systems, page replacement policies generally depend on a use bit for each page frame. The use bit is automatically turned on when the resident page is referenced. Typically, a page is considered eligible for replacement if its use bit has been scanned and found to be off on μconsecutive occasions, where μis a parameter of the algorithm. This investigation focuses on the dependence of the number of bit-scanning operations on the value of μ and on properties of the string of page references. The number of is a measure of the system such operations overhead incurred while decisions. In particular, making replacement for several the number of scans per reference is, algorithms, shown to be to μ. However, empirical results from approximately proportional single-program that the value of μ has traces show little the miss ratio. Although the miss ratios for the bit-scanning effect on algorithms close to of least recently used (LRU), are those U), itpointed out that increasing value of μ need not bring the bit-scanning policies closer to LRU management. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.