Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Solución ejercicio 1 memoria virtual

2013-08-28T17:40:08Z

Vicramde: /* NRU con 2º oportunidad */

= FIFO =
accesos a páginas
-------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
---------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | = | = | 1 | = | = | = |
--------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | = | = | 2 | = | = |
---------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | = | 3 | = |
---------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | X | X |
página -------------------------------------------------------------------------

tiempo ->

9
talla de fallos de página = ------ = 0.75
12

= NRU =

En caso de empate, se emplea LRU.
accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | = | = | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | 1 | 0 | = | = | 1 | 1 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | 1 | 0 | = | = | = | = | 1 | 0 | = | = | = | = | = | = | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | 3 | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | | | 1 | 0 | = | = | = | = | = | = | 1 | 1 | = | = | = | = |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | | X | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

7
talla de fallos de página = ------ = 0.583
12

= NRU con 2º oportunidad =

accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | 1 | = | = | = | = | = | 1 | = | = | = | = | 1 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 2 | = | 1 | = | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | 1 | = | = | 0 | = | 1 | = | = | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | 3 | 3 | = | 3 | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | 0 | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | 1 | = | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------------------------------
contenido | 1 | 1 | 1 | 1-2 | 1-2-3 |1-2-3-4|2-3-4-5|2-3-4-5|3-4-5-1|5-1-3-2|5-1-3-2|1-3-2-4|
de la cola -------------------------------------------------------------------------------------------------

tiempo ->

8
talla de fallos de página = ------
12

Creo que es asi, pero no me lo tomeis a pies juntillas que no estoy muy seguro.

Por favor que alguien explique bien este criterio, que en cada ejercicio se aplica de una forma diferente.Gracias

Explicación:

El criterio se basa en combinar el NRU (sin bit M) con FIFO. En la cola se van añadiendo las páginas según se cargan con su respectivo valor del bit R. A la hora de sustituir se mira el candidato de la cabecera de la cola. Si su R=1, se le da una segunda oportunidad desplazándolo al final de la cola y poniendo su bit R=0. Si hubiera tenido el R=0, se hubiera tomada esa página como víctima. Eso es lo que sucede cuando llega la página 5. En ese momento la cola es 1 2 3 4 con su bit R=1 en todas las páginas. Se va mirando el candidato si tiene el bit R=0 como no es así, pasa al final de la cola. Llega un momento en el que la página 1 vuelve a la cabecera(en este caso con R=0),por lo que ahora si es sustituida por la página 5.[[Usuario:Jherrera|Jherrera]]

Una Dudilla : la FIFO es por orden de carga o por orden de acceso?¿ Según veo en el ejercicio lo hace por orden de acceso --[[Usuario:DvS 013|DvS 013]]
--
Respuesta : La fifo almacena el tiempo que una página lleva cargada en memoria, por lo que es por orden de carga. [[Usuario : JCGarrido|JCGarrido]]

He puesto el orden de la cola para que se vea más claro. Cuando el candidato tiene R=1 se pone a 0 y se inserta al final. Es por eso que cuando se accede por última vez a la página 2, al estar 3 la primera, se pone su bit R a 0 se inserta al final (no estaba en la solución anterior) y la siguiente (4, con R=0) es la página víctima.--[[Usuario:Alexrdp|Alexrdp]] 09:37 14 jun 2011 (UTC)

Entonces, sería asi:

accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | 5 | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | 1 | = | = | = | = | = | 1 | = | 0 | = | = | 1 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 2 | = | 1 | 1 | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | 1 | = | = | 0 | = | 1 | 0 | = | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | 3 | 3 | 3 | 2 | 2 | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | 0 | 1 | 0 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | = | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | X | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

9
talla de fallos de página = ------
12

Esta segunda solución creo que no está del todo correcta.
Cuando llega el cuarto acceso a 1 (donde se produce el sexto fallo de página), el contenido de la cola es el siguiente:

2 (R=0) - 3 (R=1) - 4 (R=0) - 5 (R=1)

Con lo cual, la víctima es el 2, pero sin poner a 0 el resto de los bits R, ya que el primer elemento de la cola tiene el bit R=0 y no hace falta seguir iterando sobre ésta.

De acuerdo a este último comentario, quedaría de la siguiente manera:

accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | 1 | = | = | = | = | = | 1 | = | = | = | = | 1 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 2 | = | 1 | = | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | 1 | = | = | 0 | = | 1 | = | = | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | 3 | 3 | = | = | = | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | = | = | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | 1 | = | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------------------------------

talla de fallos de página = 8 / 12

= LRU =

accesos a páginas
-------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
---------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | = | = | 1 | = | = | = |
--------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | = |
---------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------

tiempo ->

8
talla de fallos de página = ------
12

= LFU =

accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 1 | = | = | = | = | = | 1 | = | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | 1 | 2 | 3 | = | = | = | = | = | 4 | = | = | 4 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | 1 | = | = | 1 | = | = | = | = | 1 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | 3 | = | = | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | | 1 | = | = | 2 | = | = | 3 | 3 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | | | 1 | = | = | = | 1 | = | 1 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | | X | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

7
talla de fallos de página = ------
12

Observación: al quitar un elemento se resetea su contador

= Sustitución por envejecimiento =
Periodo de 4, registro R de 3 bits, desempate: FIFO (por orden de carga)

_________________accesos a página__________________
|_1_|_1_|_1_|_2_||_3_|_4_|_5_|_3_||_1_|_2_|_3_|_4_|
======================================================
1 | 1 | = | = | = || 1 | = | 5 | = || 5 | = | = | 4 |
|100| = | = | = ||010| = |100| = ||010| = | = |100|
m---|---|---|---|---||---|---|---|---||---|---|---|---|
a 2 | | | | 2 || 2 | = | = | = || 1 | = | = | = |
r | | | |100||010| = | = | = ||100| = | = | = |
c---|---|---|---|---||---|---|---|---||---|---|---|---|
o 3 | | | | || 3 | = | = | = || 3 | 2 | = | = |
s | | | | ||100| = | = | = ||010|100| = | = |
---|---|---|---|---||---|---|---|---||---|---|---|---|
4 | | | | || | 4 | = | = || 4 | = | 3 | = |
| | | | || |100| = | = ||010| = |100| = |
--------------------------------------------------------> t
x x x x x x x x x

9
tasa fallos pág = ----
12

Solución ejercicio 1 memoria virtual

2013-08-28T17:38:59Z

Vicramde: /* NRU con 2º oportunidad */ Añadida solución final

Memoria virtual con multiprogramacion

2013-08-28T10:21:20Z

Vicramde: /* Criterios locales y globales */

Cuando se aplican métodos de memoria virtual en sistemas multiprogramados, surgen nuevos problemas o elecciones de diseño.
==Criterios locales y globales==
A la hora de elegir página víctima, podemos elegirla entre las asignadas al proceso (criterio local), o entre todas las páginas del sistema (Criterio global).
*'''Criterio local:''' Mantiene constante el número de páginas de un proceso cargadas en memoria, y es más eficiente, al operar sólo con las páginas del proceso. Se plantea el problema de determinar el número inicial de marcos.
*'''Criterio global:''' La asignación dinámica de marcos se adapta a las necesidades de los procesos. Se plantea el problema de que el criterio de sustitución favorece al proceso activo, ya que un proceso inactivo puede encontrarse que cuando le llegue el turno, se encuentre sus páginas movidas a memoria.
*'''Criterio mixto:''' Tiene las ventajas de ambos criterios, ya que ante una sustitución, se aplica un criterio local, de manera que el algoritmo de sustitución opera sobre un conjunto menor de marcos, y de forma dinámica, se equilibra el número de marcos entre procesos.

==Modelo del conjunto de trabajo==
Es un modelo que sigue un criterio híbrido y define como conjunto de trabajo el rango de páginas con las que opera un proceso durante una fase de su ejecución. Por ejemplo, puede que al iniciarse un proceso, necesite un rango de 10 o 20 páginas, y que pasado un tiempo, se estabilice, usando únicamente 3 o 4. Su conjunto de trabajo es un rango de páginas que cambia a lo largo del tiempo.

El objetivo es evitar la hiperpaginación, es decir, la sobrecarga debida a un aumento de la frecuencia de fallos de página hasta que se produzca un fallo de página cada pocas instrucciones.

La estrategia tener como máxima la de no retirarle nunca a un proceso una página perteneciente a su conjunto de trabajo.
==Aplicación de frecuencia de fallos de páginas==
Ya que el sistema operativo no puede saber cuál es el conjunto de trabajo de un proceso, se sigue una estrategia aproximada: Asignar dinámicamente el número de marcos en función de la frecuencia de fallos de página, que se limita superior e inferiormente.

Así, nunca habrá procesos con un número excesivo de marcos (Aprovechamiento) ni con menos de los necesarios (Posible hiperpaginación)
==Métodos de reserva==
Una posible decisión de diseño es la de mantener siempre una lista de marcos libres, ya que la memoria virtual funciona mejor si hay marcos libres cuando se produce un fallo de página.

Un demonio de paginación se ejecuta periódicamente, para descargar páginas que no estén en uso aplicando algún criterio de sustitución.

Esta decisión de diseño es discutible en sistemas interactivos, ya que tras periodos de inactividad por parte del usuario, este se puede encontrar con una sobrecarga añadida en la reanudación, al haber muchos procesos cuyas páginas han sido descargadas.
==Carga de páginas por anticipado==
Para evitar fallos de página, se pueden cargar páginas antes de que hagan falta, aplicando criterios de:
*Localidad espacial: Al transferir una página, se transfieren también sus adyacentes.
*Conjuntos de trabajo: En caso de bloqueo, se anotan las páginas que supuestamente pertenecen al conjunto de trabajo, para que al reactivarlo, se carguen todas esas páginas. El sistema operativo Android es un ejemplo de administrador de memoria que aplica esta técnica.

Usuario:Vicramde

2012-09-01T09:59:56Z

Vicramde: Página creada con 'Víctor Ramírez de la Corte, también conocido en la red como Virako.'

Víctor Ramírez de la Corte, también conocido en la red como Virako.

Gestión de Entrada/Salida

2012-09-01T09:58:18Z

Vicramde: /* Gestión de E/S híbrida */

El sistema operativo puede gobernar el dispositivo E/S a través del gestor de dispositivos de tres maneras posibles:

* Gestión de E/S por programas.
* Gestión de E/S por interrupciones.
* Gestión híbrida de E/S.

= Gestión de E/S por programas =

El gestor de dispositivo periódicamente comprueba el estado del dispositivo. Para ello comprueba mediante los registros de estado del puerto de E/S si hay datos provenientes del dispositivo que deben ser tratados.

= Gestión de E/S por interrupciones =

Una interrupción por hardware es una señal proveniente de un dispositivo de E/S para notificar al procesador de un cierto evento que debe ser tratado. Por ejemplo, un proceso hace uso de la llamada al sistema ''read'' para solicitar información que se encuentra en disco magnético. Una vez que la información está disponible, la interrupción es empleada para que se ejecute el gestor de dispositivos y obtenga los datos para dicho proceso, que ya están disponibles.

Las interrupciones son un mecanismo que ofrece la arquitectura para conectar los dispositivos de E/S con el procesador. No obstante, los datos provenientes del dispositivo de E/S se obtienen a través del bus.

El dispositivo de E/S emplea una de las líneas de interrupción que conectan al dispositivo con el procesador. Cada una de estas líneas corresponden con un cierto dispositivo o una familia de dispositivos de naturaleza similar. La signación de líneas y dispositivo es estática y sucede en tiempo de arranque, por tanto, no cambia a lo largo del tiempo. En caso de que haya datos a tratar en el dispositivo, se notifica al procesador mediante la línea de interrupción. Ante esto, el planificador debe apartar el proceso que esté en estado activo para conmutar al gestor de dispositivo, el cual realizará el tratamiento de la interrupción, obteniendo los datos del dispositivo de E/S que están pendientes de ser tratados.

Por tanto, por cada interrupción se debe [[Conmutación_de_procesos|conmutar]] al gestor de dispositivos.

Las interrupciones no son reentrantes, esto quiere decir que cuando se está realizando el tratamiento de una interrupción se desactiva temporalmente la notificación por interrupciones. Por tanto, una interrupción se ejecuta hasta fin de tratamiento, y en ningún caso es interrumpida por otra interrupción.

= Gestión de E/S híbrida =

Esta aproximación consiste en emplear una combinación de las soluciones anteriores. Básicamente, tras recibir una interrupción, se comprueba de nuevo si hay datos en el dispositivo a ser tratado. En caso afirmativo, se realiza de nuevo el tratamiento de dichos datos. De esta manera, se reduce el número de conmutaciones.