IIC 2332 -- Sistemas Operativos
Apuntes 15
1er Semestre 1996

• Segunda tarea y ayudantía

Tablas de páginas para la memoria virtual (OSC 8.5)

• Además de la traducción entre las páginas y los marcos, se guarda en las entradas de la tabla de páginas si la página está cargada en memoria (el bit válido) y si está modificada (el bit sucio). ¿Cuál es el propósito de éste? Se puede evitar el escribir al disco durante un swap. Otros bits son comunes.
• Un sistema típico tiene un espacio de direcciones de $232$ y un tamaño de página de 4K ($212$). Cada entrada en la tabla de páginas usa 4 bytes. ¡Entonces la tabla de páginas tiene $220$ entradas y usa 4M de memoria!
• Soluciones: Se guarda la longitud de la tabla en un registro y se chequea cada dirección frente esta longitud. También se pagina la tabla de páginas. Por ejemplo, una dirección ahora es 10+10+12=32 (dibujo).
• Otra posibilidad es una tabla invertida de páginas. Hay una entrada para cada marco, que guarda la dirección virtual en el marco. Se usa hashing para colocar la entrada (y entonces el número del marco) dada una dirección virtual. En general este esquema es más complicado ya que se necesitan otras tablas para guardar información especifica de los procesos.

Administración de la memoria virtual (OSC 9.2, 9.3)

• Se usa la memoria virtual en casi todos los sistemas operativos (las excepciones son PCs y sistemas especializados). Normalmente no se usa solamente la segmentación. Así el manejo de la paginación es muy importante. Un objetivo principal es minimizar el número de las fallas de páginas.
• Políticas para determinar cuando se debiera cargar una página en memoria:
  • Paginación por demanda. Cargar una página solamente cuando hay una referencia a la página. ¿Qué pasa cuando un proceso comienza?
  • Prepaginación. También cargar otras páginas distintas a la pedida. Se trata de minimizar el costo de acceso al disco. Por ejemplo, se pueden cargar páginas guardadas contiguamente en el disco con la que se desea.
• Rendimiento de la paginación por demanda:
  • tiempo efectivo de acceso = (1-p)(tiempo de acceso) + p(tiempo de falla de páginas)
  • Una falla de cada mil: (.999)(100ns) + (.001)(25ms) = 2500ns, un factor de 25.
  • Para una degradación de solamente 10% no podemos tener más que una falla de cada 2.500.000 accesos.

Política de reemplazo (OSC 9.4)

• Si una falla de página ocurre, se necesita un marco libre para la página. Si todos los marcos están llenos, tenemos varias alternativas:
  • Swapear un proceso a disco, reduciendo el grado de la multiprogramación y liberando sus marcos
  • Reemplazar una página
  • Comprar más memoria (dibujo de fallas frente a marcos)
• Tenemos que elegir una página que vamos a reemplazar. Factores:
  • Cuantos marcos se debieran asignar a cada proceso
  • Si elegimos la página solamente de las páginas del proceso o de todas las páginas del sistema
  • Que página elegimos en el conjunto bajo consideración. La idea es elegir la página que con la probabilidad menor en el de referirse futuro.
• Ya que el acceso al disco es tan lento, la política de reemplazo es muy importante para el rendimiento del sistema. Si reemplazamos una página, tenemos que hacer dos transferencias de páginas, y se dobla el tiempo de servicio de una falla de página.
  • Con el uso de un bit sucio (bit de modificacíon) podemos evitar (si es posible) el escribir la página que está en memoria en el disco.
• Empezamos con cómo se elige una página de un conjunto.
• Política óptima. Selecciona la página para que el tiempo hasta la próxima referencia sea el más largo.

  No se puede implementar la política óptima, pero produce el número menor de fallas de páginas, y entonces es un punto de referencia para otros algoritmos.

  Ejemplo: Con tres marcos, 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0 1. Nueve fallas.

• Política FIFO. Selecciona la página usando una cola FIFO.
  • Sencillo para implementar.
  • Reemplaza la página mas vieja. ¡No es siempre una buena idea!
  • 15 fallas con el ejemplo.
• Política LRU. La política óptima usa conocemiento del futuro. Se puede aproximar este conocemiento usando el pasado recién. Se selecciona la página menos recientemente usada (least recently used, o LRU).
  • Con el ejemplo, 12 fallas. En general es un buen algoritmo.
  • El problema es la implementación. Podemos mantener un campo con el tiempo de acceso para cada página, o una pila (stack) de páginas, pero tenemos que actualizar esta información para cada acceso a memoria. Como mínimo se necesita apoyo de hardware.