Truly online paging with locality of reference

Amos Fiat, Manor Mendel

פרסום מחקרי: פרסום בכתב עתמאמר מכנסביקורת עמיתים


The access graph model for paging, defined by [3] are studied in [3, 7, 4] 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 extended abstract we present a truly online strongly competitive paging algorithm in the access graph model that does not have any prior information on the access sequence. We give both strongly competitive deterministic and strongly competitive randomized algorithms. Our 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., no more memory than needed to store the virtual translation tables for pages in memory. In fact, we can reduce this to O(k log k) bits using appropriate probabilistic data structures. We also extend the locality of reference concept captured by the access graph model to allow changes in the behavior of the underlying process. We formalize this by introducing the concept of an `extended access graph'. We consider a graph parameter Δ that captures the degree of change allowed. We study this new model and give algorithms that are strongly competitive for the (unknown) extended access graph. We can do so for almost all values of Δ for which it is possible.

שפה מקוריתאנגלית
עמודים (מ-עד)326-335
מספר עמודים10
כתב עתAnnual Symposium on Foundations of Computer Science - Proceedings
סטטוס פרסוםפורסם - 1997
פורסם באופן חיצוניכן
אירועProceedings of the 1997 38th IEEE Annual Symposium on Foundations of Computer Science - Miami Beach, FL, USA
משך הזמן: 20 אוק׳ 199722 אוק׳ 1997

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Truly online paging with locality of reference'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי