New Results on Fair Multi-threaded Paging
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 sev...
| Autor principal: | |
|---|---|
| Formato: | Articulo |
| Lenguaje: | Inglés |
| Publicado: |
1998
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/135545 https://publicaciones.sadio.org.ar/index.php/EJS/article/view/133 |
| Aporte de: |
| id |
I19-R120-10915-135545 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Ciencias Informáticas Multi-threaded Paging on-line algorithms |
| spellingShingle |
Ciencias Informáticas Multi-threaded Paging on-line algorithms Strejilevich de Loma, Alejandro New Results on Fair Multi-threaded Paging |
| topic_facet |
Ciencias Informáticas Multi-threaded Paging on-line algorithms |
| description |
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". |
| format |
Articulo Articulo |
| author |
Strejilevich de Loma, Alejandro |
| author_facet |
Strejilevich de Loma, Alejandro |
| author_sort |
Strejilevich de Loma, Alejandro |
| title |
New Results on Fair Multi-threaded Paging |
| title_short |
New Results on Fair Multi-threaded Paging |
| title_full |
New Results on Fair Multi-threaded Paging |
| title_fullStr |
New Results on Fair Multi-threaded Paging |
| title_full_unstemmed |
New Results on Fair Multi-threaded Paging |
| title_sort |
new results on fair multi-threaded paging |
| publishDate |
1998 |
| url |
http://sedici.unlp.edu.ar/handle/10915/135545 https://publicaciones.sadio.org.ar/index.php/EJS/article/view/133 |
| work_keys_str_mv |
AT strejilevichdelomaalejandro newresultsonfairmultithreadedpaging |
| bdutipo_str |
Repositorios |
| _version_ |
1764820455457292290 |