Loading...
Please wait, while we are loading the content...
Similar Documents
Truly online paging with locality of reference (1997).
| Content Provider | CiteSeerX |
|---|---|
| Author | Fiat, Amos Mendel, Manor |
| Abstract | The competitive analysis fails to model locality of reference in the online paging problem. To deal with it, Borodin et. al. introduced the access graph model for the paging problem, which attempts to capture the locality of reference. However, the access graph model has a number of troubling aspects. The access graph has to be known in advance to the paging algorithm and the memory required to represent the access graph itself may be very large. In this paper we present truly online strongly competitive paging algorithms in the access graph model that do not have any prior information on the access sequence. We present both deterministic and randomized algorithms. The algorithms need only O(k log n) bits of memory, where k is the number of page slots available and n is the size of the virtual address space. I.e., asymptotically no more memory than needed to store the virtual address translation table. In fact, it can be reduced to O(k log k) bits using appropriate probabil... |
| File Format | |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Access Graph Model Randomized Algorithm Virtual Address Space Paging Algorithm Competitive Analysis Appropriate Probabil Virtual Address Translation Table Access Sequence Access Graph Prior Information Paging Problem Page Slot Online Paging Problem |
| Content Type | Text |
| Resource Type | Article |
