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
المدة: ٢٠ أكتوبر ١٩٩٧٢٢ أكتوبر ١٩٩٧


أدرس بدقة موضوعات البحث “Truly online paging with locality of reference'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا