New Results on Fair Multi-threaded Paging

Abstract

The Multi-threaded Paging problem (MTP) was introduced as a generalization of Paging for the case where there are many threads of requests. This models situations in which the requests come from more than one independent source. At each step it is necessary to decide which request to serve among several possibilities, and also (as in normal Paging) which page of fast memory to remove on a page fault. In the fair version of the problem any algorithm must guarantee that the next request of each thread will be served within a predetermined finite time.

In this paper we reduce the existing gaps between the known lower and upper bounds for the competitiveness of on-line algorithms for the fair version of MTP. We treat some particular situations, with finite and infinite input sequences. We prove higher lower bounds and present a new on-line algorithm. We close the gap for the case in which the cache can hold only one page; surprisingly, we obtain different bounds for even and odd number of sequences; we prove that any lazy algorithm achieves the on-line lower bound when the number of sequences is odd.

Research supported in part by EC project DYNDATA under program KIT, and by UBACyT projects ``Algoritmos Eficientes para Problemas On-line con Aplicaciones'' and ``Modelos y Técnicas de Optimización Combinatoria".