Particiones Fijas y Variables 2

Administracin de Memoria.
Sistemas Operativos Tema 4.
Sistemas Operativos (IS11) Tema 4
Administracin de memoria.
Jerarqua de memoria:
Registros CPU del procesador Cach (memoria rpida) Memoria principal RAM Almacenamiento secundario (memoria virtual)
Al bajar en la jerarqua ms capacidad pero ms lento es el dispositivo y ms barato. Administrador de memoria:

Parte del S.O. que gestiona la memoria: Control de que partes de la memoria estn utilizadas o libres. Asignar memoria a procesos y liberarla cuando terminan. Administrar intercambio entre memoria y disco (Memoria Virtual).
Sistemas Operativos (IS11) Tema 4 2
Administracin de memoria.
Proceso de Compilacin y Carga de un Programa:
Programa Fuente Mdulo Objeto Otros Modulos Objeto Contenido de la memoria en binario Editor de Enlaces Carga Ejecucin
Compilacin y Ensamblador
Ejemplo: (enlace de direcciones) Programa ensamblador con salto a una etiqueta: ETIQ --jmp ETIQ
Proceso de Compilacin y Carga de Programas. En que momento se realiza el enlace o traduccin de direcciones?
Compilacin: Generando cdigo absoluto, en el momento de compilacin se sabe donde residir el programa en memoria. Carga (Reubicacin esttica): El compilador genera cdigo relocalizable. Se crean direcciones de memoria absolutas cuando se carga el programa en memoria. Ejecucin (Reubicacin dinmica) : Durante la ejecucin puede moverse el cdigo de un proceso. Necesita apoyo del hardware:
Direcciones Logicas 0 1 . . . 100 Registro Base + MEMORIA FISICA
CPU
Administracin en sistemas Monoprogramados.

En sistemas monoprogramados generalmente la memoria principal dividida en dos particiones:
Una para el usuario: Un proceso con su cdigo. Direccin a partir de la que se cargan programas de usuario. Otra para el sistema operativo residente (memoria baja).
00000 0FFFF Usuario Sistema Operativo
Es necesario proteger las particiones entre s.
Administracin en sistemas Monoprogramados.

A veces el tamao del S.O. desea variarse:
Ej.: Manejadores de dispositivos que no se usan. Se puede realizar una reubicacion dinmica del espacio.
Direccin Logica= 346 Registro Base= 14000 + Direccin Fsica= 14346 MEMORIA FISICA
CPU
Tambin, cargar los procesos de usuario en memoria alta.

00000 FFFFF Sistema Operativo Libre Proceso Usuario
Administracin en sistemas Multiprogramados.

Es deseable que haya varios procesos en memoria para su ejecucin concurrente. Se debe compartir la memoria entre varios procesos que esperan asignacin de la misma. Esquemas de asignacin de memoria:
Contigua: particiones fijas y variables Intercambio (swapping) Paginacin Segmentacin Segmentacin paginada
Administracin en sistemas Multiprogramados.

Primer esquema de asignacin de memoria: Particiones
La memoria est dividida de antemano en espacios (Particiones). Un proceso necesita ejecutarse -> Se le asigna uno de dichos espacios (Particin). Cada particin puede contener un nico proceso. Pueden ser: Particiones Fijas:
Todas el mismo tamao. Con diferentes Tamaos.
Particiones Variables.
Particiones Fijas.
Particiones de igual tamao:
00000 0FFFF 1FFFF 2FFFF NFFFF Particin N
Sistema Operativo
Particin 1 Particin 2
...
Nivel de multiprogramacin limitado por nmero de particiones. Hay una cola con procesos que quieren utilizar memoria y ejecutarse. Hay una tabla para indicar particiones ocupadas y libres.
Particiones Fijas.
Particiones con diferentes tamaos:
00000 0FFFF Particin 1 3FFFF 40FFF E1FFF FFFFF Sistema Operativo Particin 2
...
Particin N
Para procesos que quieren utilizar memoria para ejecutarse: 00000

Podemos tener varias colas: Cada proceso se asigna a una cola en funcin de su tamao.
Sistema Operativo
Proceso 6 Proceso 5 Proceso 1 Proceso 3 Proceso 4
Particin 1
Particin 2
... ...
Proceso 2 FFFFF Particin N
Podemos tener una nica cola: Cuando se libera una particin -> se asigna al primer proceso que cabe en ella. 00000
Sistema Operativo Particin 1
Proceso 3 Proceso 2 Proceso 1
...
Particin 2
FFFFF
...
Particin N
10
Particiones Fijas.
Problemas que presenta este tipo de asignacin de memoria:
Debe proporcionarse reubicacin: En que particin entrar el proceso?. Existe Fragmentacin Interna y Externa: Interna: Externa:
Una particin asignada y no ocupada totalmente por el proceso. Un proceso quiere ejecutarse, hay una particin libre, pero de menor tamao que el proceso.
Necesidad de proteccin: (en sistemas multiprogramados) Un proceso no acceda al rea de memoria del otro. Si la reubicacin es dinmica puede usarse registros base-lmite.
Registro Lmite= 1000 Direccin Logica= 346 Registro Base= 14000 +
CPU
Es menor ? NO
SI
Direccin Fsica= 14346
MEMORIA FISICA
Interrupcin Hardware interna al S.O.
11
Funcionamiento:
Inicialmente: Toda la memoria (salvo particin del S.O.) disponible para procesos, como si fuese un gran hueco. Llega un proceso: Se introduce en un hueco libre. El espacio no ocupado ser un nuevo hueco. Cada zona de memoria ocupada -> una particin. Proceso termina: Libera su zona de memoria. Se convierte en un hueco. Dicho hueco se fusiona con los adyacentes. Se conserva una tabla de partes de memoria ocupadas y libres y la cola de entrada de procesos en memoria.
Un ejemplo:los procesos se cargan en memoria, compiten por la CPU y al acabar liberan la memoria
Proceso P1 P2 P3 Memoria Requerida 600 K 1000 K 300 K S.O. Proceso P1
2160K 1560K
Memoria Proceso Requerida 700 K P4 500 K P5
S.O. 400K 900K 1000K
S.O. Proceso P1 Proceso P2

560K
S.O. Proceso P1 Proceso P2 Proceso P3

260K
S.O. Proceso P1
1000K
S.O. Proceso P1 Proceso P4 300K Proceso P3

260K
S.O. 600K Proceso P4 300K Proceso P3

260K
S.O. Proceso P5 Proceso P4 300K Proceso P3

260K
1700K 2000K 2300K 2560K
Proceso P3
260K
13
Fragmentacin de Particiones Variables:
Externa: SI. (memoria dividida en huecos pequeos) Suma del espacio libre en memoria suficiente para el nuevo proceso. Pero no hay huecos suficientemente grandes para l. El nuevo proceso no se carga en memoria. Interna: NO. Las particiones se crean con el tamao solicitado por el proceso.
14
Esta asignacin de memoria se denomina: Asignacin dinmica de almacenamiento Como elegir un hueco cuando llega un nuevo proceso de tamao N? Estrategas:
Primer Ajuste: Escoge el primer hueco libre de tamao suficiente. Mejor Ajuste: Hueco ms pequeo con tamao suficiente (requiere ver toda la lista si no est ordenada). Peor Ajuste: Hueco ms grande: Pretende conseguir que los huecos que queden sean grandes (requiere ver toda la lista si no ordenada).
Cul es el mejor?
Simulaciones y Estadsticas: Criterio tiempo (reduccin) y utilizacin de memoria (aprovechamiento):
Primer Ajuste y Mejor Ajuste son mejores que Peor Ajuste.
Regla del 50%: un anlisis estadstico refleja que

Con Primer Ajuste por cada N bloques de memoria asignados se pierden 0,5 N bloques por fragmentacin externa (1/3 memoria inutilizada).
16
Proteccin de Memoria: se utiliza cdigo reubicable
Si cdigo reubicable -> se pueden usar registros base y lmite.
Registro Lmite= 500 Direccin Logica= 346 S.O. Registro Base= 1400 + Proceso P5 Proceso P4
Es menor ? NO
SI
Direccin 1400K Fsica= 1746
CPU
Interrupcin Hardware interna al S.O.
1900K Proceso P3
17
Compactacin: intenta solucionar fragmentacin ext.
Consiste en desplazar las particiones ocupadas para que estn juntas en memoria: Queda un solo hueco libre de mayor tamao. Es una solucin al problema de fragmentacin externa. Slo es posible si la reubicacin es dinmica (en ejecucin). Ejemplo: S.O. S.O. 400K 400K Proceso Proceso 100+300+260= P5 P5 900K 900K Hueco de 660k 1000K
Proceso P4 1700K 2000K 2300K 2560K Proceso P3 Proceso P4 1600K 1900K 2560K Proceso P3
18
Problemas de la Compactacin:
Consume tiempo: Desplazar zonas de memoria. Difcil seleccionar una estrategia de compactacin ptima.
(1) S.O. P1 200K 500K P2 100K 600K 800K 1000K 1200K 1500K P4 400K 1900K 2100K P3 200K 300K P1 200K P2 100K P3 200K P4 400K P1 200K P2 100K P4 400K P3 200K P1 200K P2 100K (2) (3)
Cul es la mejor?
Paginacin.
Paginacin: (solucin a fragmentacin externa)
Permite que la memoria de un proceso no sea contigua. Hay una distincin entre direcciones lgicas y fsicas. La memoria fsica la dividimos en bloques de tamao fijo: marcos. La memoria lgica: La dividimos en bloques llamados: pginas. De igual tamao que el marco. Las pginas de un proceso se cargan en los marcos de la memoria principal que estn disponibles: Tenemos trozos del proceso all donde la memoria est disponible.
Paginacin.
Hardware de paginacin: para traduccin de direcciones
Direccin Lgica CPU Tabla de Pginas P D 0 1 2 P M D Direccin Fsica
...
M
La direccin lgica generada consta de dos partes: Nmero de Pagina (P). Desplazamiento dentro de la pgina (D). La tabla de pginas: (contiene la direccin base en memoria fsica) Permite establecer una correspondencia entre el nmero de pgina y un nmero de marco de memoria fsica. La direccin fsica es el nmero de marco y el desplazamiento.
Paginacin.
Ejemplos:
Memoria Lgica Pagina 0 Pagina 1 Pagina 2 Pagina 3 0 1 2 3 Tabla de Pginas 1 4 3 7 0 1 2 3 4 5 6 7 Pagina 3 Pagina 2 Pagina 1 Pagina 0 Memoria Fsica
Memoria Lgica 0 Pagina 0 1 2 3 4 Pagina 1 5 6 7 8 Pagina 2 9 10 11 12 Pagina 3 13 14 15 a b c d e f g h i j k l m n o p 0 1 2 3
Tabla de Pginas 5 6 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Memoria Fsica 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
i j k l m n o p
a b c d e f g h
22
Paginacin.
Tamao de pginas y marcos definidos por Hardware. Normalmente se escoge un tamao de pgina potencia de 2:
Ya que es ms fcil la traduccin de direcciones lgicas a fsicas.
Direccin Lgica CPU Tabla de Pginas 0010 000000 0 1 2 3 4 5 6 7 8 010 001 110 011 110 000000 Direccin Fsica
011
Tamao memoria lgica 2 n tamao pgina 2 (bytes o palabras) P ndice en tabla de pginas D desplazamiento
...
M-n bits altos de la direccin lgica= P n bits bajos de la direccin lgica = D
23
Paginacin.
El SO traduce direcciones usando una copia de la tabla pginas en memoria Implementacin Hardware de la Tabla de Pginas:
1) Un conjunto de registros (circuitos lgicos de alta velocidad): Habr que cargar estos registros en un cambio de contexto. Se usa para pocas entradas (unas 256) 2) Tabla en memoria principal y registro base cuyo contenido apunta a la tabla de pginas: Para cambiar de tabla de pginas -> Basta cambiar de registro base. Menor tiempo de cambio de contexto pero mayor de acceso a memoria
Accedemos dos veces a memoria para obtener un dato en memoria.
Para tablas grandes (millones de entradas)

Paginacin.
3) Registros Asociativos (TLB): (pequea cach de acceso rpido), (translation look-aside buffers) Los registros contienen solo unas pocas entradas de una T.pginas 2 partes en cada registro:
Una clave (nmero de pgina). Y un valor (nmero de Marco). Si la clave est: Proporciona el nmero de marco asociado. Si no est: Se accede a la tabla de pginas de memoria.
Direccin Lgica CPU P D TLB clave M
0 1 2 P
Compara el valor de la pgina deseada con todas las claves.

Direccin Fsica
Tabla de Pginas
...
M
25
Paginacin.
Ventaja: Pginas Compartidas:
La paginacin permite compartir cdigo comn entre varios procesos: Slo si el cdigo es reentrante (no se modifica durante ejecucin). El rea de datos de los procesos sera diferente. Ejemplo: varios procesos ejecutan el mismo editor de textos
PROCESO 1 Memoria Lgica Editor 1 Editor 2 Editor 3 Datos 1 0 1 2 3 Tabla de Pginas 3 1 4 6 1 PROCESO 3 Memoria Lgica Editor 1 Editor 2 Editor 3 Datos 3 0 1 2 3 Tabla de Pginas 3 1 4 6 2 0 1 2 3 4 5 6 Memoria Lgica Editor 1 Editor 2 Editor 3 Datos 2 0 1 2 3 Tabla de Pginas 3 1 4 6 7 7 8 9 10 11 12 Editor 3 Datos 2 Datos 1 Datos 3 Editor 1 Editor 2 Memoria Fsica
Una nica copia Del editor en Memoria fsica
PROCESO 2
26
Paginacin.
Proteccin de memoria en entorno con paginacin:
En la tabla de pginas pueden encontrarse unos bits de proteccin asociados a cada marco indican si la pgina es de slo lectura o lectura y escritura. Cuando se consulta el nmero de marco, se consultan adems los bits de proteccin. Se debe controlar que el nmero de pgina no supere el total de pginas usadas por el proceso (sera una direccin incorrecta).
27
Segmentacin.
Otro esquema de asignacin memoria: Segmentacin
El espacio de direcciones lgicas se compone de un conjunto de segmentos: Cada uno tiene un nombre y una longitud. Para el usuario las direcciones especifican el nombre del segmento y el desplazamiento dentro de l. El nombre del segmento se numera (es un nmero). <nmero segmento, desplazamiento> El procesador Intel 8086 usa segmentacin, los programas se separan en: Segmento de Cdigo. Segmento de Datos. Segmento de Pila. Hay una divisin lgica del proceso en diferentes segmentos.
Segmentacin.
Hardware de segmentacin mediante Tabla de segmentos:
Establece la correspondencia entre direcciones fsicas y lgicas. Se busca en la tabla de acuerdo con el nmero de segmento. Cada entrada 2 registros:
base (dir. Fsica inicial del segmento en memoria) lmite de segmento (longitud del segmento)
Se compara lmite del segmento con desplazamiento. Si desplazamiento vlido, se suma a la direccin el registro base.
Direccin Lgica CPU Tabla de Segmentos S d 0 1 2
S Limite Base
...
Direccin Fsica = Base + d +
Limite >d? NO
SI Interrupcin Error de direccionamiento
29
Segmentacin.
Ejemplo: sean 5 segmentos en memoria fsica
1400 Limite Datos Subrrutina 1 Segmento 0 Segmento 4 Programa Principal Segmento 2 Segmento 3 Pila 5700 6300 6700 0 1 2 3 4 1000 400 400 1100 1000 Base 1400 6300 4300 3200 4700 Segmento 3 4300 4700 Segmento 2 Segmento 4 2400 3200 Segmento 0
Subrrutina 2 Segmento 1
Segmento 1
Acceso a byte 1200 del segmento 0 da error direccionamiento

Segmentacin.
Implementacin Hardware de la tabla de segmentos:
Puede ubicarse en registros rpidos o memoria (como paginacin). Si est en memoria: Un registro base STBR (segment table base register) indica inicio de la tabla de segmentos en memoria. Un registro lmite indica longitud de la tabla de segmentos. Bits de proteccin: Segmento de slo lectura o lectura y escritura. Se consultan antes de acceder al segmento. Puede realizarse a nivel de segmento (cdigo o datos). Cada proceso tendr una tabla de segmentos. Compartir un segmento significa que una entrada de la tabla de segmentos coincide en varios procesos (igual posicin fsica).
Proteccin:
Comparticin de cdigo:
Segmentacin.
Ejemplo comparticin editor:
Editor Segmento 0 Datos 1 Segmento 1 Memoria Lgica Proceso P1 68348 Tabla de Segmentos Proceso P2 72773 Limite Base 0 1 25286 8550 43062 90003 90003 98553 Datos 2 Datos 1 Tabla de Segmentos Proceso P1 Limite 0 1 25286 4425 Base 43062 68348 43062 Editor Memoria Fsica
Editor Segmento 0 Datos 2 Segmento 1 Memoria Lgica Proceso P2
Si compartimos un segmento todos los procesos que lo comparten deben definir dicho segmento con el mismo cdigo. Direccin ( S , desplazamiento )
Segmentacin.
Fragmentacin:
Los segmentos son de tamao variable: Puede haber fragmentacin externa. Bloques de memoria demasiado pequeos para contener un segmento. Solucin: Se puede compactar la memoria (segmentacin usa reubicacin dinmica). Problema de fragmentacin, casos extremos: Cada proceso un segmento, igual esquema que en particiones variables. Cada palabra (byte) un segmento:
No habra fragmentacin externa. Necesitamos una tabla de segmentos del tamao de la memoria.
Segmentacin Paginada.
Otro esquema de asignacin de memoria es: Segmentacin paginada
La Memoria lgica est dividida en bloque llamados segmentos que contienen las regiones de un proceso. Direccin lgica=<n segmento, desplazamiento>=<S,d> Los segmento estn divididos en pginas de igual tamao que los marcos (potencias de 2). Las pginas de un proceso se cargan en marcos de la memoria principal. Cada segmento tiene asociada una tabla de pginas Se usa un registro lmite y base de la tabla de pginas para cada segmento
34
Segmentacin Paginada.
Esquema de traduccin de direcciones
Direccin lgica=<n segmento, desplazamiento>=<S,d> S= entrada de la tabla de segmentos: Tabla de Segmentos Contiene el lmite 0 del segmento Tabla de Pginas 1 Direccin Contiene la del Segmento S Lgica direccin base ... Limite Base Tabla S d + m de una tabla de S de Pginas pginas. CPU Habr una tabla Direccin de pginas por SI Fsica Limite m d' P d' cada segmento. >d? El desplazamiento d es: Interrupcin NO Error de Un nmero de pgina P. direccionamiento Un nuevo desplazamiento dentro de la pgina d.
Memoria virtual.
Recordemos que queremos: Memoria Virtual:
Mantener simultneamente varios procesos en memoria para permitir multiprogramacin.
La memoria virtual puede implementarse sobre Paginacin o Segmentacin paginada: se transfieren pginas. La transferencia suele ser bajo demanda.
Permite separar la memoria lgica del usuario de la memoria fsica. Un proceso en ejecucin no tiene porque encontrarse totalmente en memoria principal (slo parte). Ahora un proceso puede ser mayor que la memoria fsica. Permite transferencia de informacin entre memoria principal y secundaria (2 niveles consecutivos de la jerarqua de memoria). Usa un dispositivo de almacenamiento secundario (disco) como dispositivo de intercambio.
36
Paginacin por demanda.

Paginacin por demanda:
Los procesos estn divididos en pginas. Inicialmente: una serie de pginas del proceso cargadas en memoria principal (MP), las que se usan. El resto en almacenamiento secundario. Necesario un bit de presencia en tabla de paginas: Bit vlido-invlido 1, pgina cargada en MP (v). Disco Tabla de Memoria Memoria 0, pgina no cargada (i). Pginas
Lgica A B C D E F 0 1 2 3 4 5 0 1 2 3 4 5 6 7 9 6 4 v i v i i v i i Fsica 0 1 2 3 4 A 5 6 C 7 8 9 F 10 A B D E F C
Si el proceso accede a pginas residentes en memoria (bit de presencia vlido): la ejecucin prosigue normalmente Si accede a una pgina no residente (bit presencia invlido)
Ocurre una interrupcin o fallo de pgina , Control al SO
37

Gestin de un Fallo de pgina
1. 2. 3. 4. Se detecta que la pgina no est en memoria Se produce una interrupcin Se busca la pgina en almacenamiento secundario (disco) Se busca un marco libre, se lee la pgina de almacenamiento secundario y se copia en el marco seleccionado pgina est en 5. Se actualiza la tabla de pginas Interrupcin 2 Sistema La almacenamiento Operativo 6. Reiniciamos en la instruccin 3 auxiliar. Tabla de Pginas interrumpida Disco
Cargar M 0 1 M corresponde 1 a una pgina que no est 2 en memoria. 3 4 v i 6 v i A B D E F i 9 v i 4 Cargar la pgina en memoria. C Memoria Fsica 0 1 2 A 3 4 B 5 6 C 7 8 9 F 10
...
M 6 Reiniciar la instruccin M+1 M+2
Actualizar la tabla de pginas.
38

Hardware de apoyo a la paginacin por demanda:
Capacidad de marcar en la tabla de pginas una entrada como vlida o invalida (bit valido-invalido). Unidad de almacenamiento secundario:
La seccin de disco empleado para este fin se denomina: espacio de intercambio o almacenamiento auxiliar.
Paginacin por demanda pura:

Caso extremo: comenzamos la ejecucin de un proceso sin ninguna pgina cargada en memoria. Se irn produciendo fallos de pginas sucesivamente y cargando las pginas necesarias.
39
Segmentacin Paginada con Paginacin por Demanda.

No todas las pginas de todos los segmentos estaran en memoria. Usamos tambin bits de valido-invalido para la tabla de pginas asociada a cada segmento. El funcionamiento es igual que paginacin por demanda.
40
Reemplazo de pginas.
Utilizando Memoria Virtual:
Los procesos tienen parte de sus pginas cargadas en memoria. En un instante, la totalidad de los marcos de memoria estn ocupados.
Qu ocurre si ante un fallo de pgina no existe un marco libre en memoria principal? Posibles soluciones que aplicara el S.O. :
Abortar el proceso de usuario (no es una buena solucin). Descargar otro proceso y llevarlo a almacenamiento secundario liberando sus marcos (se puede hacer). Reemplazar pginas:
Encontramos un marco que no se est utilizando y lo liberamos.
Fallo de pgina con reemplazo de pginas:
Se busca la pgina deseada en almacenamiento secundario. Se busca un marco libre.
LO HAY: lo utilizamos. NO LO HAY: reemplazo de pgina
usar un algoritmo de reemplazo de pginas para seleccionar un marco vctima que genere el menor nmero de fallos de pgina Pasamos el contenido del marco a almacenamiento secundario. Actualizamos la tabla de pginas.
Ya disponemos de un marco libre. Se lee la pgina de almacenamiento secundario y se copia en el marco libre. Se actualiza la tabla de pginas. Se reinicia la instruccin interrumpida.
Rendimiento
Frecuencia de Fallo de pgina
Sea p la probabilidad de que una referencia a memoria provoque un fallo de pgina (0<p<1)
Si p=0, nunca hay fallos de pgina Si p=1, hay fallo de pgina en todas las referencias
Sea tm el tiempo de acceso a memoria principal Sea tfp el tiempo para resolver un fallo de pgina, que depende de:
Tiempo de transferencia entre almacenamiento secundario y memoria Tiempo de actualizacin de tablas de pginas Tiempo de reinicio de la ejecucin del proceso
El tiempo efectivo de acceso a memoria TEAM vendr dado por: TEAM=(1-p).tm + p.tfp
Objetivo de cualquier algoritmo de reemplazo:

Obtener la menor tasa de fallos de pgina posible
Reduccin del tiempo para resolver los fallos de pgina
Fallo de pgina: dos accesos a almacenamiento secundario Uno para guardar la pgina vctima Otro para cargar la nueva pgina Usar bit de modificado en la tabla de pginas Al cargar la pgina, desde almacenamiento secundario a memoria, el bit modificado se pone a 0 (no modificada) Si se escribe en la pgina el bit pasa a 1 (modificado) Si la pgina es elegida como vctima se mira su bit de modificado Si la pgina no ha sido modificada (bit a cero) no habr que salvarla Si la pgina ha sido modificada (bit a uno) se salvar El uso de bit modificado reduce el tiempo tfp
La tasa de fallos de pgina (p) depender de:
Nmero de pginas de los procesos Nmero de procesos en memoria Nmero de marcos disponibles Del algoritmo de reemplazo de pginas que se utilice
Hay que usar aquel que conlleve menor nmero de fallos
Para poder implementar un sistema de memoria virtual nos queda por responder a dos preguntas:
Cmo reemplazar las pginas?
Es necesario escoger un algoritmo de reemplazo de pginas
Cmo decidir cuantos marcos de cada proceso tenemos en memoria?

Algoritmos de reemplazo de pgina.

Clasificacin de estrategias de reemplazo:
Reemplazo Global Utilizan los algoritmos de reemplazo de pginas actuando sobre las pginas de todos los procesos Reemplazo Local Usa los algoritmos slo entre las pginas del proceso que necesita un reemplazo de pgina
Algoritmos de reemplazo de pginas: FIFO ptimo LRU (Last Recently Used) De la segunda oportunidad o del reloj Con bits referenciado y modificado
Algoritmos FIFO.
Se reemplaza la pgina que lleva ms tiempo en memoria El SO mantiene una lista de las pginas Se reemplaza la pgina cabecera de la lista y se inserta al final El rendimiento no siempre es bueno, pueden sustituirse pginas muy usadas Puede presentarse la anomala de Belady: ms marcos en memoria no implica que hayan menos fallos de pgina Ejemplo: Sea la secuencia: 7, 0, 1, 2, 7, 0, 5, 7, 0, 1, 2, 5
Con 3 marcos, 9 fallos de pgina, con 4 hay 10 fallos
Secuencia pginas 7 0 1 2 7 0 5 7 7 7 2 2 3 Marcos 0 0 0 7 1 1 1 Fallos de pgina 2 5 7 7 0 0 7 5 7 0 0 5 7 0 1 2 5 5 5 5 1 1 1 0 2 2
Anomala de Belady
7 0 1 2 7 7 7 7 0 0 0 1 1 2 7 7 0 1 2 0 7 0 1 2 5 5 0 1 2 7 5 7 1 2 0 5 7 0 2 1 5 7 0 1 2 5 2 7 2 5
0 0 1 1

47
Algoritmos ptimo.
El algoritmo ptimo tiene la menor tasa de fallos Reemplazar la pgina que no se va a usar durante ms tiempo Es irrealizable ya que no se conoce a priori la utilizacin de memoria de instrucciones futuras Ejemplo: En los fallos 1 y 2 hay que decidir la pgina: 1 entre la 0 , 1 y 7 la 7 2 entre la 0 , 1 y 2 la 1 1 2
Secuencia pginas 3 Marcos Fallos de pgina 7 7 0 7 0 1 7 0 1 2 2 0 1 1
2 2 1 3 2 0 3 2 2 0 3 1 2 ? ? 2 ? ? ?
48
0 2 0 1
3 2 0 3 2
0 2 0 3

Algoritmos LRU (Last Recently Used).

Sustituye la pgina que ms tiempo lleva sin ser usada Implantacin mediante un contador:
Cada vez que accedemos a memoria se incrementa su valor Se copia el valor del contador en la tabla de pginas asociado a la pgina a la que hemos accedido Se elimina la pgina que tiene el valor del contador ms bajo
Implementacin mediante pila:

En la base, la pgina que lleva ms tiempo, en la cima la ms nueva Ejemplo:
Secuencia pginas 7 7 3 Marcos 1 0 7 0 1 2 1 7 0 1 Fallos de pgina 2 1 2 2 0 3 1 4 2 3 0 2 0 1 4 5 3 3 2 0 3 0 4 2 5 0 6 3 4 7 6 3 2 0 3 4 7 8 2 2 0 3 9 7 8 1 2 1 3 49 9 10 8 2 2 11 1 10 3 8
Algoritmos de la segunda oportunidad o del reloj.

Utiliza un bit de referencia asociado a cada pgina
Inicialmente estn a cero Cambia a 1 cuando se accede a la pgina para leer o escribir El SO pone peridicamente todos a cero
0 1 1 0
Funciona como FIFO pero:

Selecciona una pgina y examina su bit referenciado Est a cero, reemplazamos la pgina Est a uno, se da una segunda oportunidad a la pgina
Se pone el bit referenciado a cero Buscamos la siguiente vctima
Cmo implementarlo?
Se usa una cola circular de las pginas residentes en memoria Un puntero indica la siguiente pgina a reemplazar de la cola Si bit referenciado = 1, lo ponemos a cero y avanzamos el puntero Si bit referenciado =0, sustituimos esa pgina
50
Algoritmos con bits referenciado y modificado.

Utiliza en cada pgina un bit referenciado (1 indica pgina accedida) y un bit modificado (1 indica acceso de escritura) Las pginas agrupadas en cuatro clases:
Referenciado = 0, Modificado = 0 Referenciado = 0, Modificado = 1 Referenciado = 1, Modificado = 0 Referenciado = 1, Modificado = 1

Se reemplazar la pgina de la clase inferior (nmero ms bajo) no vaca
Si hay varias en esa clase se utilizar FIFO para la seleccin
El SO pone peridicamente a cero el bit referenciado

Polticas de asignacin de marcos.

Cuntos marcos se asignan a cada proceso en un sistema multiprogramado? Estrategias de asignacin
Asignacin fija Los marcos de memoria existentes se dividen:
Equitativamente: n marcos/n procesos Proporcionalmente: se asignan ms marcos a procesos ms grandes
Suele estar asociada a una estrategia de reemplazo local Asignacin dinmica La cantidad de marcos de cada proceso vara dinmicamente segn la necesidades del mismo Puede aplicarse a:
reemplazo local, cada proceso varia la cantidad de marcos que utiliza reemplazo global, los procesos compiten por el uso de memoria
52
Hiperpaginacin.
Hiperpaginacin (thrashing)
Nmero de fallos de pgina elevado debido a que el n de marcos asignados al proceso no es suficiente para almacenar las pginas referenciadas por el mismo Ms tiempo en la cola de servicio de paginacin que en CPU El rendimiento de la CPU decrece
Grfica de utilizacin de CPU en funcin del grado de multiprogramacin Solucin:

Descargar las pginas de uno o varios procesos a almacenamiento secundario liberando marcos de memoria
Tiempo accesoefec t = (1 p ) t m + p t fp t m = tiempo de acceso a memoria . t fp = tiempo de fallo de pagina . p = probabilid ad de fallo de pagina .

Particiones Fijas y Variables 2

Cargado por

Copyright:

Formatos disponibles

Particiones Fijas y Variables 2

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Particiones Fijas y Variables 2

Cargado por

Copyright:

Formatos disponibles

Administracin de Memoria.

Sistemas Operativos Tema 4.

Sistemas Operativos (IS11) Tema 4

Al bajar en la jerarqua ms capacidad pero ms lento es el dispositivo y ms barato. Administrador de memoria:

Sistemas Operativos (IS11) Tema 4

Administracin en sistemas Monoprogramados.

Es necesario proteger las particiones entre s.

Sistemas Operativos (IS11) Tema 4

Administracin en sistemas Monoprogramados.

Tambin, cargar los procesos de usuario en memoria alta.

Sistemas Operativos (IS11) Tema 4

Administracin en sistemas Multiprogramados.

Sistemas Operativos (IS11) Tema 4

Administracin en sistemas Multiprogramados.

Sistemas Operativos (IS11) Tema 4

Sistemas Operativos (IS11) Tema 4

Para procesos que quieren utilizar memoria para ejecutarse: 00000

Proceso 6 Proceso 5 Proceso 1 Proceso 3 Proceso 4

Proceso 2 FFFFF Particin N

Proceso 3 Proceso 2 Proceso 1

Sistemas Operativos (IS11) Tema 4

Direccin Fsica= 14346

Interrupcin Hardware interna al S.O.

Sistemas Operativos (IS11) Tema 4

Memoria Proceso Requerida 700 K P4 500 K P5

S.O. 400K 900K 1000K

S.O. Proceso P1 Proceso P2

S.O. Proceso P1 Proceso P2 Proceso P3

S.O. Proceso P1 Proceso P4 300K Proceso P3

S.O. 600K Proceso P4 300K Proceso P3

S.O. Proceso P5 Proceso P4 300K Proceso P3

1700K 2000K 2300K 2560K

Sistemas Operativos (IS11) Tema 4

Sistemas Operativos (IS11) Tema 4

Regla del 50%: un anlisis estadstico refleja que

Sistemas Operativos (IS11) Tema 4

Direccin 1400K Fsica= 1746

Interrupcin Hardware interna al S.O.

Sistemas Operativos (IS11) Tema 4

Sistemas Operativos (IS11) Tema 4

Memoria Lgica 0 Pagina 0 1 2 3 4 Pagina 1 5 6 7 8 Pagina 2 9 10 11 12 Pagina 3 13 14 15 a b c d e f g h i j k l m n o p 0 1 2 3

Sistemas Operativos (IS11) Tema 4

Sistemas Operativos (IS11) Tema 4

Para tablas grandes (millones de entradas)

Compara el valor de la pgina deseada con todas las claves.

Sistemas Operativos (IS11) Tema 4

Una nica copia Del editor en Memoria fsica

Sistemas Operativos (IS11) Tema 4

Sistemas Operativos (IS11) Tema 4

Direccin Fsica = Base + d +

SI Interrupcin Error de direccionamiento

Sistemas Operativos (IS11) Tema 4

Acceso a byte 1200 del segmento 0 da error direccionamiento

Editor Segmento 0 Datos 2 Segmento 1 Memoria Lgica Proceso P2

Sistemas Operativos (IS11) Tema 4

Paginacin por demanda.

Sistemas Operativos (IS11) Tema 4

Paginacin por demanda.

M 6 Reiniciar la instruccin M+1 M+2

Actualizar la tabla de pginas.