Truly online paging with locality of reference

摘要: The access graph model for paging, defined by (Borodin et al., 1991) and studied in (Irani 1992) has a number of troubling aspects. to be known advance the paging algorithm memory required represent itself may very large. We present truly online strongly competitive that does not have any prior information on sequence. give both deterministic randomized algorithms. Our algorithms need only O(k log n) bits memory, where k is page slots available n size virtual address space, i.e., no more than needed store translation tables pages memory. In fact, we can reduce this k) using appropriate probabilistic data structures. also extend locality reference concept captured allow changes behavior underlying process. formalize introducing an "extended graph". consider parameter /spl Delta/ captures degree change allowed. study new are (unknown) extended graph. do so almost all values which it possible.