There is a large body of work from the sixties and seventies in the area of page replacement and paging (see [15] and 1161 for references). Perhaps now it is time to re-examine the basic assumptions of prior studies in light of very large physical memories and multiple page sizes. Perhaps we need to reconsider two of the simplest page replacement algorithms that were dismissed in the past: random replacement and first-in first-out replacement