• Author / Uploaded
• Carolina Diaz Alvarez

• Categories
• Poco
• Memoria del ordenador
• Algoritmos
• Programa de computadora
• Puntero (Programación de computadora)

Citation preview

13 problemas resueltos. Tema: GESTION DE MEMORIA. -

¿Cual es la diferencia entre direcciones lógicas y físicas?

Solución El termino reubicable se refiere ala capacidad de cargar y ejecutar un programa determinado en una posición arbitraria de memoria, en contraposición a un conjunto fijo de posiciones especificadas en el momento de traducción del programa. Como durante las diferentes ejecuciones de un mismo programa reubicable se le pueden asignar diferentes direcciones de carga, se puede distinguir entre 

Las direcciones virtuales, que corresponden a las percibidas por el programador, y son identificadores utilizados para referenciar información dentro del espacio de direcciones de un programa y,

Las direcciones físicas en donde el programa y sus datos se almacenan en memoria durante una ejecución determinada es decir, que designan, por lo tanto, las posiciones reales en memoria donde la información se almacena en tiempo de ejecución.

-

Explicar la diferencia fragmentación externa.

entre

la

fragmentación

interna

y la

Solución En general, la fragmentación se refiere a la incapacidad del sistema operativo para asignar porciones de memoria no utilizada. Se distingue entre: 



a) b) c) d)

Fragmentación interna corresponde al espacio interno de una partición que se malgasta cuando el bloque de datos cargado es mas pequeño que la partición. Fragmentación externa tiene lugar cuando una participación disponible no se utiliza porque es muy pequeña para cualquiera de las tareas que esperan cargarse en memoria.

Explicar los algoritmos de asignación: Primero en ajustarse Mejor en ajustarse Peor en ajustarse Siguiente en ajustarse

Solución Son los algoritmos mas habituales para la selección de un área libre de memoria para asignársela aun proceso recién creado o intercambiado.

a) El algoritmo primero en ajustarse es la estrategia mas simple y rápida. En este caso, el gestor de memoria asigna al proceso entrante el primer bloque libre suficiente grande que encuentra al recorrer la lista. b) El algoritmo mejor en ajustarse recorre la lista de memoria libre entera para hallar el bloque libre mas pequeño suficientemente grande para contener al proceso. Resulta lento y tiende a producir bloques de restos libres pequeños que pueden resultar demasiados pequeños para asignaciones posteriores c) El algoritmo peor en ajustarse representa el caso contrario al algoritmo mejor en ajustarse ya que asignan el bloque libre más grande, siempre que el tamaño del bloque exceda al tamaño necesario. Este algoritmo suprime el efecto d particiones muy pequeñas generadas por la estrategia anterior y produce evidentemente los restos mas grandes, pero, sin embargo algunos estudios de simulación indican que este tipo de asignación no es muy efectiva reduciendo la memoria desaprovechada cuando se procesan una serie de peticiones. d) El algoritmo siguiente en ajustarse corresponde a una modificación del primero en ajustarse en donde se añade un puntero a la lista de memoria libre que guarda la dirección de la última asignación y se utiliza para comenzar de él la búsqueda de la asignación siguiente. la idea es reducir la búsqueda evitando examinar los bloques pequeños que a la larga tienden a acumularse al comienzo de la lista de memoria libre como resultado de las asignaciones previas.

Problema: Calcular el porcentaje de tiempo de CPU utilizado para la compactación de la memoria en una maquina de 1Mb de memoria. La compactación se hace cada 0,5 s y se tarda 300 ns en copiar una byte. Los espacios desaprovechados en promedio son del 50% del tamaño de los bloques.

Solución Se entiende por compactación la técnica que permite mover los procesos hacia la parte inferior (o superior) de la memoria de forma que es posible combinar todos los bloques libres en uno grande. Con esta técnica se palia el problema de la fragmentación externa de algunos sistemas de gestión de memoria. La cuestión que se resuelve es la siguiente: La memoria que debe ser asignada a

un proceso nuevo en particular debe ser continua, pero la memoria libre disponible se halla dispersa debido a la fragmentación externa por lo que no se puede usar. En cualquier caso la solución de la compactación resulta ser un método de muy alto coste. El espacio desaprovechado es del 50%, ello indica que se deben trasladar a un extremo de la memoria el 50% de la misma, es decir o.5 Mb. Por lo tanto, el número de bytes que se debe trasladar es: M= (1024*1024)*0.5= 524288 bytes (Conversión de megabytes a bytes) El tiempo total para el traslado es: Tcpu= 524288 * 300 * 10-9= 0,1573sg -9 (1 segundo tiene 10 nanosegundos)

Si cada 0,5 se pasa 0,1573 seg compactando, entonces cada 1 seg estará 0,3146s por lo que el 31´46% del tiempo de CPU se esta desaprovechando en tiempos de compactación. Obsérvese el elevado tiempo que se utiliza para las tareas de compactación como se comentaba al inicio del problema.

PROBLEMA: Considerar un sistema con intercambio en el que la memoria posee huecos libres de tamaño: 1000 Kb, 400Kb, 1800 Kb 700 Kb 900 Kb, 1200 Kb, y 1500 Kb. Estos huecos están dispuestos en el orden dado. Se requieren tres segmentos de tamaños 1200 Kb, 1000 Kb, y 900 Kb. Para los algoritmos primero en ajustarse, mejor en ajustarse, peor en ajustarse, siguiente en ajustarse: a) ¿Qué huecos serán asignados? b) ¿Qué algoritmos aprovecha mejor la memoria? Solución 

El algoritmo primero en ajustarse es la estrategia más simple y rápida. En este caso, el gestor de memoria asigna al proceso entrante el primer bloque libre suficientemente grande que encuentra al recorrer la lista. Para este algoritmo se tiene: Huecos en Kb

1000 400 1800 700 900 1200 1500

Segmento 1200 Kb 1000 Kb 900 Kb

Hueco asignado 1800 1000 900

Fragmentación 600 0 0

El algoritmo mejor en ajustarse recorre la lista de memoria libre entera para hallar el bloque libre más pequeño suficientemente grande para contener al proceso. Resulta lento y tiende a producir bloques de restos libres pequeños que pueden resultar demasiados pequeños para asignaciones posteriores. Para el algoritmo mejor ajustarse: Segmento 1200 Kb 1000 Kb 900 Kb

Hueco asignado 1200 1000 900

Fragmentación 0 0 0

El algoritmo peor en ajustarse representa el caso contrario al algoritmo mejor en ajustarse ya que asignan el bloque libre más grande, siempre que el tamaño del bloque exceda al tamaño necesario. Este algoritmo suprime el efecto de particiones muy pequeñas generadas por la estrategia anterior y produce evidentemente los restos más grandes, pero, sin embargo, algunos estudios de simulación indican que este tipo de asignación no es muy efectiva reduciendo la memoria desaprovechada cuando se procesan una serie de peticiones. Para el algoritmo peor en ajustarse:

Segmento 1200 Kb 1000 Kb 900 Kb

Hueco asignado 1800 1500 1200

Fragmentación 600 500 300

El algoritmo siguiente en ajustarse corresponde a una modificación del primero en ajustarse en donde se añade un puntero a las listas de memoria libre que guarda la dirección de la última asignación y se utiliza para comenzar a partir de él la búsqueda de la asignación siguiente. La idea es reducir la búsqueda evitando examinar los bloques pequeños que a la larga tienden a acumularse al comienzo de la lista de memoria libre como resultado de las asignaciones previas. Para el algoritmo siguiente en ajustarse: Segmento 1200 Kb 1000 Kb 900 Kb

Hueco asignado 1800 1200 1500

Fragmentación 600 200 600



Si las particiones libres dadas se corresponden a una gestión de memoria con participaciones fijas se estará hablando de fragmentación interna no utilizable por ningún otro proceso. En este caso el algoritmo que mejor aprovecha la memoria es el mejor en ajustarse dado que no produce fragmentación interna, después el algoritmo primero en ajustarse con fragmentación interna de 600 y finalmente los otros dos que producen una fragmentación interna de 1400. Sin embargo, si las participaciones libres dadas se corresponden con el estado de la memoria en un instante dado de una gestión de memoria con participaciones variables entonces se estará hablando de fragmentación externa que en este caso puede que no lo sea, dado que los nuevos bloques libres son lo suficientemente grandes para alojar a otros procesos que vengan posteriormente.

En cualquier caso y a la vista de estos resultados se puede concluir que el algoritmo que mejor aprovecha la memoria es el mejor en ajustarse porque se ajusta exactamente a los bloques libres dados y estos impiden que se creen bloques pequeños no utilizables como era de esperar en este tipo de algoritmo.

-

Supóngase un computador cuya instrucción ensamblador tiene la forma: ADD R1, R2, R3

de

suma,

en

Cuyo significado es que se suma el contenido de la dirección R1 con el de R2 y el resultado se sitúa en R3. La instrucción ocupa tres palabras y todos los direccionamientos son directos (es decir, la dirección efectiva es parte de la propia instrucción). ¿Cuál es el número mínimo de marcos de página que esta instrucción requiere para garantizar su ejecución? Explicar la respuesta Solución El tamaño del marco de página puede ser de 4 Kb por lo que un marco puede guardar perfectamente la instrucción y serán necesarios otros tres más para guardar R1, R2 y R3. En total 4 marcos.

PROBLEMA: Un computador tiene un espacio de direcciones de 32 bits y páginas de 8 Kb. La tabla de páginas está realizada físicamente como un conjunto de registros, con una palabra de 32 bits por cada dato. Al iniciar un proceso la tabla de páginas se copia al hardware desde la memoria, con una palabra cada 100 ns (nanosegundos). Si cada proceso se ejecuta durante

100 ms (milisegundos) (incluyendo el tiempo de carga de la tabla de páginas). ¿Cuál es la fracción de tiempo del procesador que se dedica a la carga de la tabla de páginas? Solución Como el tamaño de una página es igual al marco de página, se puede calcular el número de marcos de página que caben en la memoria física y que por lo tanto que se pueden direccionar desde la tabla de páginas. De esta forma se calcula la máxima tabla de páginas posible, es decir aquella que contiene la asociación de páginas con todos los posibles marcos de página:

232 _________

23 * 210

232 =

__________

213

= 219 marcos de página

32

(2 cantidad de memoria direccionada por los 32 bits) 3 * 10 ( 2 2 8 * 1024 conversión de 8K a bits. Cantidad de memoria ocupada por los marcos de página) 19 (2 cantidad de paginas de 8k que caben en el espacio de memoria de 32 bits)

Por cada marco se tiene una palabra en la tabla de páginas por lo tanto, el tiempo que se emplea en cargar las 219 palabras. Tc= 219 * 100 *10 -9 = 52.4 ms Como el tiempo total de ejecución de un proceso es de 100 ms, entonces se ejecuta realmente durante 47,6 ms. Por lo tanto se pasa el 52,4% como máximo cargado la tabla d páginas.

-

Cuando surgió el concepto de la memoria virtual y se implementó por primera vez, las memorias principales eran pequeñas y con frecuencia las aplicaciones eran mayores que la memoria principal. Hoy en día, la tecnología ha cambiado drásticamente y cualquier computador personal tiene varios GIGAbytes. Es de esperar que la capacidad de la memoria siga creciendo y que en el futuro sea normal tener una memoria principal con capacidad de TERAbytes. Pero el tiempo de acceso a los discos no crece de la misma forma. Discutir si con este tipo de situación es rentable disponer de un esquema de gestión de memoria virtual.

Solución

Puesto que esquema de gestión de memoria virtual implica estar trayendo páginas desde disco si tiene lugar un fallo de página y este tipo de acceso no

mejora temporalmente hablando y si por otro lado se tiene suficiente memoria principal para alojar a los procesos que se quieren ejecutar enteros no será rentable mantener este esquema de memoria. Además no es únicamente que se pueda disponer de más memoria sino que ésta está sufriendo un abaratamiento del coste continuo.

PROBLEMA: Se tiene un sistema que utiliza gestión de memoria paginada. El espacio de direccionamiento virtual es de 10 páginas de 1024 palabras ( 1 palabra= 2bytes). La memoria física está dividida en 32 marcos. a) ¿Cuántos bits componen una dirección virtual? b) ¿Cuántos bits componen una dirección física? Solución a) para direccionar una dirección virtual, se tiene que indicar su número de página y su desplazamiento:

N° de pagina ( 10 paginas) 4 bits

Desplazamiento (1024 palabras o 2024 bytes) ( 10 bits o 11 bits)

El número de páginas totales es 10, por lo tanto, para distinguir entre 10 páginas hace falta 4 bits (1111 daría para 15 páginas). El desplazamiento corresponde al tamaño de la pagina, si el desplazamiento se expresa en palabras será necesario poder direccionar 1024 palabras, luego es suficiente con 10 bits, sin embargo si el desplazamiento se expresa en bytes será necesario 11 bits. En total para representar la dirección virtual son necesarios 14 bits si se expresa el desplazamiento en palabra o 15 bits si se expresa en bytes. b) para direccionar una dirección física, es necesario indicar su número de marco de página y su desplazamiento:

N° de pagina ( 32 marcos: de 0 a 31. Binario de 31) (5 bits)

Desplazamiento (1024 palabras o 2048 bytes) (de 0 a 1023: binario de 1023 o De 0 a 2048: binario de 2047) ( 10 bits o 11 bits)

El número de marcos de páginas totales es de 32, por lo tanto, para distinguir entre estos 32 marcos hacen falta 5 bits. El desplazamiento corresponde al tamaño del marco de página, igual al de la página, por lo tanto de 1024 palabras, luego es necesario 10 bits para distinguir entre palabras u 11 bits si el desplazamiento se expresa en bytes. En total para representar la dirección física son necesarios 15 bits si se expresa el desplazamiento en palabra o 16 bits si se expresa en bytes

-

Si una instrucción necesita 1 microsegundo para ejecutarse y un fallo de página tarda n microsegundos adicionales, dar una fórmula que exprese el tiempo promedio de acceso necesario para una instrucción si los fallos de páginas ocurren cada K instrucciones. ( He creado un hipervínculo para la definición de “fallo de página”) Solución El tiempo que transcurre para K instrucciones es el tiempo de ejecución de las K-1 instrucciones anteriores sin fallo de página que es K-1 seg mas el tiempo correspondiente al fallo de página de la K-estima instrucción mas la ejecución de la correspondiente instrucción, n*+1, es decir:

T= (K-1)+ (1+n)= K+n us Por lo tanto en promedio una instrucción tardara: T

-

instrucción=K+n us K

Para un computador que tiene 100 Mb de memoria física, suponer que el tamaño de pagina es de 2 Kb. ¿Cuántas entradas debe de tener una memoria asociativa para implementar una tabla de pagina para la memoria?

Solución Si la memoria tiene 100 Mdirreciones, y cada pág. requiere de 2 Kb, entonces hay 100 Mb/2 Kb=50 Kb marcos de pagina en la memoria. cada marco requiere una entrada, por lo tanto la memoria asociativa debe tener 50 Kb entradas.

PROBLEMA: En un sistema con gestión de memoria virtual por demanda de página con segmentación paginada, las direcciones lógicas tienen la siguiente estructura: 31 N° de segmento

19 Desplazamiento 19 N° de página

0

7 desplazamiento

0

Las tablas de descriptores de segmento y de página son las siguientes ( ver Tabla 4.21): N° segmento ….. 00A 00B 00C 00D …..

Bit validación …….. 07FF 02FF 01FF 03FF …..

Marco de página …….. 0081 00F2 0103 01FA …….

Tabla 4.17: Tabla de descriptores de segmento

N° Pagina Bit validación Marco de página 0 1 3501 1 0 xxxx 2 0 xxxx 3 1 0020 4 1 0137 5 0 xxxx 6 0 xxxx 7 1 0AIF Tabla 4.18: Tabla de páginas del segmento con base en 0081 N° Pagina Bit validación Marco de página 0 1 320F 1 0 xxxx 2 0 xxxx 3 1 33DA Tabla 4.19: Tabla de páginas del segmento con base en 01FA N° Pagina 0 1 2

Bit validación 1 0 1

Marco de página 014D xxxxx F001

Tabla 4.20: Tabla de páginas del segmento con base en 00F2 N° Pagina 0 1

Bit validación

Marco de página 1 AB10 1 0126 Tabla 4.20: Tabla de páginas del segmento con base en 0103

a) Explicar de una forma razonada cuales de las siguientes direcciones lógicas generan un fallo de página y cuales un error de direccionamiento, para las correctas calcular la dirección física que les corresponde: 00A001A4 00D003F1 00A100B2 00C41F20 00A0075F 00D002D b) En este sistema, y suponiendo que se le asigna a cada proceso tantos marcos de páginas como solicite, ¿Cuál es el máximo número de marcos de página que el sistema operativo puede asignara a un proceso?

Nota: todas las direcciones se han dado en hexadecimal. Solución

a) Se sigue el esquema de la Figura 4.16. se verifica si el segmento existe, si es así se verifica si la página esta (para lo cual se ha añadido un bit de validación en las tablas de páginas), si la página esta se verifica que con el desplazamiento dado en la dirección no se viola el tamaño del segmento. Dirección 00A001A4

N° segmento 00A

N° página 001

desplazamiento A4

La base para el segmento 00 A es 0081, al ir a la tabla de páginas de este segmento se observa que la página 001 no se encuentra en memoria, por lo tanto se producirá un fallo de página. Dirección 00D003F1 N° segmento 00D

N° página 003

desplazamiento F1

La base para el segmento 00D es 01FA, en la correspondiente tabla de página se observa que el marco de página para la página 003 es 33 DA, y no se viola el tamaño del segmento, por lo tanto la dirección físicas es: 33DAF1.

Dirección 00A100B2: N° segmento 00A

N° página 100

desplazamiento B2

La base para el segmento 00A es 0081,pero su límite es 07FF, 100B2 supera este límite por lo que se produce una violación del tamaño del segmento o error de direccionamiento. Dirección 00C41F20 N° segmento 00C

N° página 41F

desplazamiento 20

La base para el segmento 00C es 0103, pero sus limite es 01FF, 41F20 supera este límite por lo que se produce una violación del tamaño del segmento o error de direccionamiento. Dirección 00A0075F: N° segmento 00A

N° página 007

desplazamiento 5F

La base para el segmento 00A es 0081, en la correspondiente tabla de página se observa que el marco de página para la página 007 es 0A1F, y no se viola el tamaño del segmento, por lo tanto la dirección física es 0A1F5F.

Dirección 00D0002D: N° segmento 00D

N° página 000

desplazamiento 2D

La base para el segmento 00D es 01FA, en la correspondiente tabla de página se observa que el marco de página para la página 000 es 320F, y no se viola el tamaño del segmento, por lo tanto la dirección física es 320F2D. b) El número de marcos de página que se le puede asignar a un proceso puede estar determinado por el máximo número de páginas que puede direccionar o por el tamaño de la memoria. El numero de páginas que un proceso puede direccionar esta limitado por la dirección lógica. En el caso actual, según el formato de la dirección lógica el máximo numero de páginas que se puede direccionar es:

Páginas= segmentos* 224paginas

-

páginas/seg=212

segmentos

*212

páginas/seg=

En un sistema con gestión de memoria virtual por demanda de páginas, el código reubicable de un programa, después de la complicación, ocupa diez páginas (numeradas de 0 a 9) de 2 Kb cada una. Cuando el programa se carga abra ejecución, se cargan las páginas 3 y 4 en los marcos 5 y2 respectivamente. a) Dibujar la tabla de páginas para esta situación y la parte de la memoria principal correspondiente, (En la tabla de páginas incluir el marco de pagina asignado y un bit de presente/ausente). b) En otro instante de tiempo, la tabla de páginas corresponde a la Tabla 4.15. Indicar a que direcciones físicas de memoria principal corresponden las direcciones lógicas 1000, 3500, 8000 y 19500 (en decimal)

c) Si el sistema de gestión de memoria hace la asignación con solo 4 marcos de página y hace una prepaginación de una pagina. Indicar los fallos de página que se producen para los algoritmos de sustitución FIFO Y LUR con la siguiente cadena de referencia:

192124565656 7 7 5 5 4 4 5 N° de página 0 1 2 3 4 5 6 7 8 9

Marco de página Bit presente/ausente 3 1 4 1 3 0 4 0 1 0 3 0 4 0 8 1 1 0 3 0 Tabla 4.15: Tabla de páginas

Solución a) Sólo se tienen cargadas las páginas 3 y 4, que son las que tienen a 1 el bit de presente/ausente. La tabla de páginas para esta situación es la indicada a continuación:

N° de página 0 1 2 3 4 5 6 7 8 9

Marco de página X X X 5 2 X X X X X

Bit presente/ausente 0 0 I I 0 0 0 0 0 0

Si los marcos están asociados a la memoria principal, de forma que el marco 0 se halla en la dirección 0, la memoria principal queda:

Dirección física

Marco de página 0 1 2 3 4 5 6 7 8 9

0 2048 4096 6144 8192 10240 12288 14336 16384 18432

b) La dirección física viene dada por la expresión: D fisica = n° marco * tamaño + desplazamiento Teniendo en cuenta esto: 

La dirección virtual 1000 se halla en la pagina 0 que se corresponde con el marco 3, por lo tanto: D1000 = 3 * 2048 + 1000 = 7144



La dirección virtual 3500 se halla en la pagina 1 con un desplazamiento de 35000-2048=1452 Entonces la dirección física, teniendo en cuenta que la página 1 le corresponde el marco 4, será:

D1000 = 4 * 2048 + 1452 = 9644 

La dirección virtual 8000 se halla en la página 8000/2048=3 de ,9, es decir, en la página 3 con un desplazamiento de 8000 - (2048*3) = 1856

Pero esta página no tiene ningún asociado como indica su bit de presente/ausente a cero, por lo tanto, no tiene ninguna dirección física asociada. 

La dirección virtual 19500 se halla en la página 19500/2048=9,52, es decir en la pagina 9 con un desplazamiento de 19500 – 18432 = 1068

Pero esta página no tiene ningún marco asociado como indica su bit de presente/ ausente a cero, por lo tanto, no tiene ninguna dirección física asociada.