Computer Science 789 Online Algorithms
Fall 1999
Handout 7
Almost trackless almost memoryless
Barely random optimal paging algorithms
Refer to the
textbook
for a definition of the paging problem.
A number of paging algorithms, such as Partition and Equitable, mark
pages in slow memory. Others, such as MARK, mark pages in the cache.
A mark to a page in slow memory must be implemented by
some kind of identifier
that permits the algorithm to determine whether a page fault is to
that particular page.
We refer to that identifier as a bookmark.
We say that an algorithm is trackless if it has no bookmarks.
We say that an algorithm is almost trackless if it has
O(1) bookmarks.
We say that an algorithm is almost memoryless if it uses
O(1) memory.
We say that an algorithm is barely random if it is a finite
entropy distribution of deterministic algorithms.
Almost trackless almost memoryless barely random algorithms for
the paging problem for k = 2.
Almost trackless almost memoryless barely random algorithms for
the paging problem for k = 3.

Back to
Course Page