Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this paper we extend the Paging Problem to the case in which each request specifies a set of pages that must be present in fast memory to serve it. The interest on this extension is motivated by many applications in which the execution of each task may require the presence of more than one page in fast memory. We introduce three different cost models that can be applied in this framework, namely the Full, Uniform and Constant cost models, and study lower and upper bounds for each one of them, using competitive analysis techniques.

Registro:

Documento: Artículo
Título:Paging more than one page
Autor:Feuerstein, E.
Filiación:Depto. Comp.-FCEyNUBA, Pabellon I, Ciudad Universitaria, 1414 Buenos Aires, Argentina
Palabras clave:Mathematical models; Problem solving; Paging problem; Storage allocation (computer)
Año:1997
Volumen:181
Número:1
Página de inicio:75
Página de fin:90
DOI: http://dx.doi.org/10.1016/S0304-3975(97)89513-8
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v181_n1_p75_Feuerstein.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v181_n1_p75_Feuerstein

Referencias:

  • Aggarwal, A., Alpern, B., Chandra, A.K., Snir, M., A model for hierarchical memory (1987) Proc. 19th Ann. ACM Symp. on Theory of Computing, pp. 305-314
  • Aggarwal, A., Chandra, A.K., Virtual memory algorithms (1988) Proc. 20th Ann. ACM Symp. on Theory of Computing, pp. 173-185
  • Aggarwal, A., Chandra, A.K., Snir, M., Hierarchical memory with block transfer (1987) Proc. 28th Ann. Symp. on Foundations of Computer Science, pp. 204-216
  • Albers, S., The influence of lookahead in competitive paging algorithms (1993) Lecture Notes in Computer Science, 726, pp. 1-12. , Proc. 1st Ann. European Symp. on Algorithms, Springer, Berlin
  • Belady, L.A., A study of replacement algorithms for virtual storage computers (1966) IBM System J., 5, pp. 78-101
  • Borodin, A., Irani, S., Raghavan, P., Schieber, B., Competitive paging with locality of reference (1991) Proc. 23rd Ann. ACM Symp. on Theory of Computing, pp. 249-259
  • Borodin, A., Linial, N., Saks, M., An optimal online algorithm for metrical task systems (1987) Proc. 19th Ann. ACM Symp. on Theory of Computing, pp. 373-382
  • Feuerstein, E., Marchetti-Spaccamela, A., Memory paging for connectivity and path problems in graphs (1993) Lecture Notes in Computer Science, 762, pp. 416-425. , Proc. 4th Ann. Symp. on Algorithms and Computation, Springer, Berlin
  • Fiat, A., Karp, R.M., Luby, M., McGeoch, L.A., Sleator, D.D., Young, N.E., Competitive paging algorithms (1991) J. Algorithms, 12, pp. 685-699
  • Karlin, A., Manasse, M., Rudolph, L., Sleator, D., Competitive snoopy caching (1988) Algorithmica, 3, pp. 79-119
  • Manasse, M.S., McGeoch, L.A., Sleator, D., Competitive algorithms for server problems (1990) J. Algorithms, 11, pp. 208-230
  • McGeoch, L.A., Sleator, D., A strongly competitive randomized paging algorithm (1989) Algorithmica, 6, pp. 816-825
  • Nodine, M., Goodrich, M., Vitter, J.S., Blocking for external Graph Searching (1992) Technical Report CS-92-44, , Brown University
  • Raghavan, P., Snir, M., Memory versus randomization in on-line algorithms (1990) IBM Research Report RC, p. 15622
  • Sleator, D., Tarjan, R.E., Amortized efficiency of list update and paging algorithms (1985) Comm. ACM, 28, pp. 202-208

Citas:

---------- APA ----------
(1997) . Paging more than one page. Theoretical Computer Science, 181(1), 75-90.
http://dx.doi.org/10.1016/S0304-3975(97)89513-8
---------- CHICAGO ----------
Feuerstein, E. "Paging more than one page" . Theoretical Computer Science 181, no. 1 (1997) : 75-90.
http://dx.doi.org/10.1016/S0304-3975(97)89513-8
---------- MLA ----------
Feuerstein, E. "Paging more than one page" . Theoretical Computer Science, vol. 181, no. 1, 1997, pp. 75-90.
http://dx.doi.org/10.1016/S0304-3975(97)89513-8
---------- VANCOUVER ----------
Feuerstein, E. Paging more than one page. Theor Comput Sci. 1997;181(1):75-90.
http://dx.doi.org/10.1016/S0304-3975(97)89513-8