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