Introducción a los Sistemas Operativos
Trabajo Práctico Nº 5
Administración de la Memoria Principal
1.- Explique a que hacen referencia los siguientes términos:
Dirección Lógica o Virtual
Dirección Física
2.- En la técnica de Particiones Múltiples, la memoria es divida en varias particiones y los
procesos son ubicados en estas, siempre que el tamaño del mismo sea menor o igual que el
tamaño de la partición.
Al trabajar con particiones se pueden considerar 2 métodos (independientes entre si):
Particiones Fijas
Particiones Dinámicas
a) Explique como trabajan estos 2 métodos. Cite diferencias, ventajas y desventajas.
b) ¿Qué información debe disponer el SO para poder administrar la memoria con estos
métodos?
c) Realice un gráfico indicado como realiza el SO la transformación de direcciones
lógicas a direcciones físicas.
3.- Al trabajar con particiones fijas, los tamaños de las mismas se pueden considerar:
Particiones de igual tamaño.
Particiones de diferente tamaño.
Cite ventajas y desventajas de estos 2 métodos.
4.- Fragmentación
Ambos métodos de particiones presentan el problema de la fragmentación:
Fragmentación Interna (Para el caso de Particiones Fijas)
Fragmentación Externa (Para el caso de Particiones Dinámicas)
a) Explique a que hacen referencia estos 2 problemas
b) El problema de la Fragmentación Externa es posible de subsanar. Explique una
técnica que evite este problema.
5.- Paginación
a) Explique como trabaja este método de asignación de memoria.
b) ¿Qué estructuras adicionales debe poseer el SO para llevar a cabo su
implementación?
c) Explique, utilizando gráficos, como son transformadas las direcciones lógicas en
físicas.
d) En este esquema: ¿Se puede producir fragmentación (interna y/o externa)?
6.- Cite similitudes y diferencias entre la técnica de paginación y la de particiones fijas.
7.- Suponga un sistema donde la memoria es administrada mediante la técnica de
paginación, y donde:
El tamaño de la página es de 512 bytes
Cada dirección de memoria referencia 1 byte.
Los marcos en memoria principal de encuentran desde la dirección física 0.
Suponga además un proceso con un tamaño 2000 bytes y con la siguiente tabla de páginas:
Página Marco
0 3
1 5
2 2
3 6
Introducción a los Sistemas Operativos
a) Realice los gráficos necesarios (de la memoria, proceso y tabla de paginas) en el que
reflejen el estado descripto.
b) Indicar si las siguientes direcciones lógicas son correctas y en caso afirmativo indicar
la dirección física a la que corresponden:
i) 35 iv) 0
ii) 512 v) 1325
iii) 2051 vi) 602
c) Indicar, en caso de ser posible, las direcciones lógicas del proceso que se
corresponden si las siguientes direcciones físicas:
i) 509 iv) 3215
ii) 1500 v) 1024
iii) 0 vi) 2000
d) ¿Indique, en caso que se produzca, la fragmentación (interna y/o externa)?
8.- Considere un espacio lógico de 8 paginas de 1024 bytes cada una, mapeadas en una
memoria física de 32 marcos.
a) ¿Cuantos bits son necesarios para representar una dirección lógica?
b) ¿Cuantos bits son necesarios para representar una dirección física?
9.- Segmentación
a) Explique como trabaja este método de asignación de memoria.
b) ¿Qué estructuras adicionales debe poseer el SO para llevar a cabo su
implementación?
c) Explique, utilizando gráficos, como son transformadas las direcciones lógicas en
físicas.
d) En este esquema: ¿Se puede producir fragmentación (interna y/o externa)?
10.- Cite similitudes y diferencias entre la técnica de segmentación y la de particiones
dinámicas.
11.- Cite similitudes y diferencias entre la técnica de paginación y segmentación.
12.- Dado un S.O. que administra la memoria por medio de segmentación paginada, y
teniéndose disponibles las siguientes tablas:
Tabla de Segmentos Tabla de Páginas
Nro. Dir. Nro. Nro. Dir.
Segmento Base Segmento Pagina Base
1 500 1 40
2 1500 1 2 80
3 60
3 5000 1 20
2 2 25
3 0
1 120
3
2 150
Indicar las direcciones físicas correspondientes a las siguientes direcciones lógicas
(segmento,pagina,desplazamiento):
i) (2,1,1) iii) (3,1,10)
ii) (1,3,15) iv) (2,3,5)
Introducción a los Sistemas Operativos
13.- Memoria Virtual
a) Describa que beneficios introduce este esquema de administración de la memoria.
b) ¿En que se debe apoyar el SO para su implementación?
c) Al implementar está técnica utilizando paginación por demanda, las tablas de paginas
de un proceso deben contar con información adicional además del marco donde se
encuentra la página. ¿Cuál es está información? ¿ Porque es necesaria?
14.- Fallos de Página (Page Faults):
a) ¿Cuándo se producen?
b) ¿Quién es responsable de detectar un fallo de página?
c) Describa las acciones que emprende el SO cando se produce un fallo de página.
15.- Direcciones:
a) Si se dispone de una espacio de direcciones virtuales de 32 bits, donde cada dirección
referencia 1 byte:
i) ¿Cuál es el tamaño máximo de un proceso (recordar “espacio virtual”)?
ii) Si el tamaño de pagina es de 512Kb. ¿Cuál es el número máximo de paginas que
puede tener un proceso?
iii) Si el tamaño de pagina es de 512Kb. y se disponen de 256 Mb. de memoria real
¿Cuál es el número de marcos que puede haber?
iv) Si se utilizaran 2 Kb. para cada entrada en la tabla de páginas de un proceso:
¿Cuál seria el tamaño máximo de la tabla de páginas de cada proceso?
16.- Como se vio en el ejercicio anterior, la tabla de páginas de un proceso puede alcanzar
un tamaño considerablemente grande, que incluso, no podría almacenarse de manera
completa en la memoria real. Es por esto que el SO también realiza paginación sobre las
tablas de paginas.
Existen varios enfoques para administrar las tablas de páginas:
Tablas de páginas de 1 nivel.
Tablas de páginas de 2 niveles.
Tablas de páginas invertidas.
Explique brevemente como trabajan estos enfoques e indique como se realiza la
transformación de la dirección virtual en dirección física.
17.- Tamaño de la Página:
La selección del tamaño de la página influye de manera directa sobre el funcionamiento de
la memoria virtual. Compare las siguientes situaciones con respecto al tamaño de página,
indicando ventajas y desventajas:
Un tamaño de página pequeño.
Un tamaño de página grande.
18.- Asignación de marcos a un proceso (Conjunto de trabajo o Working Set):
Con la memoria virtual paginada, no se requiere que todas las páginas de un proceso se
encuentren en memoria. El SO debe controlar cuantas páginas de un proceso puede tener
en la memoria principal. Existen 2 políticas que se pueden utilizar:
Asignación Fija
Asignación Dinámica.
a) Describa como trabajan estas 2 políticas.
b) Dada la siguiente tabla de procesos y las paginas que ellos ocupan, y teniéndose 40
marcos en la memoria principal, cuantos marcos le corresponderían a cada proceso si se
usa la técnica de Asignación Fija:
i) Reparto Equitativo
ii) Reparto Proporcional
Introducción a los Sistemas Operativos
Proceso Total de Paginas Usadas
1 15
2 20
3 20
4 8
c) ¿Cual de los 2 repartos usados en b) resulto mas eficiente? ¿Por qué?
19.- Reemplazo de páginas (selección de una victima):
¿Qué sucede cuando todos los marcos en la memoria principal están usados por las
páginas de los procesos y se produce en fallo de página? El SO debe seleccionar una de
las páginas que se encuentra en memoria como victima, y ser reemplazada por la nueva
página que produjo el fallo.
Considere los siguientes algoritmos de selección de victimas básicos:
LRU
FIFO
OPT (Optimo)
Segunda Chance
a) Clasifique estos algoritmos de malo a bueno de acuerdo a la tasa de fallos de página
que se obtienen al utilizarlos.
b) Analice su funcionamiento. ¿Como los implementaría?
c) Sabemos que la pagina a ser reemplaza puede estar modificada. ¿Qué acciones debe
llevar el SO cuando se encuentra ante esta situación?
20.- Alcance del reemplazo
Al momento de tener que seleccionar una pagina víctima, el SO puede optar por 2 políticas
a utilizar:
Reemplazo local
Reemplazo global
a) Describa como trabajan estas 2 políticas.
b) ¿Es posible utilizar la política de “Asignación Fija” de marcos junto con la política de
“Reemplazo Global? Justifique.
21.- Considere la siguiente secuencia de referencias de páginas:
1, 2, 15, 4, 6, 2, 1, 5, 6, 10, 4, 6, 7, 9, 1, 6, 12, 11, 12, 2, 3, 1, 8, 1, 13, 14, 15, 3, 8
a) Si se disponen de 5 marcos. ¿Cuántos fallos de página se producirán si se utilizan las
siguientes técnicas de selección de víctima? (Considere una política de Asignación
Dinámica y Reemplazo Global)
i) Segunda Chance
ii) FIFO
iii) LRU
iv) OPT
b) Suponiendo que cada atención de un fallo se pagina requiere de 0,1 seg. Calcular el
tiempo consumido por atención a los fallos de páginas para los algoritmos de a).
22.- Sean los procesos A, B y C tales que necesitan para su ejecución las siguientes
páginas:
A: 1, 3, 1, 2, 4, 1, 5, 1, 4, 7, 9, 4
B: 2, 4, 6, 2, 4, 1, 8, 3, 1, 8
C: 1, 2, 4, 8, 6, 1, 4, 1
Si la secuencia de ejecución es tal que los procesos se ejecutan en la siguiente secuencia:
Introducción a los Sistemas Operativos
1. B demanda 2 páginas 8. C demanda 4 páginas
2. A demanda 3 páginas 9. A demanda 3 páginas
3. C demanda 2 páginas 10. B demanda 3 páginas
4. B demanda 3 páginas 11. C termina
5. A demanda 3 páginas 12. A demanda 3 páginas
6. C demanda 2 páginas 13. B termina
7. B demanda 2 páginas 14. A termina
a) Considerando una política de Asignación Dinámica y Reemplazo Global y
disponiéndose de 7 marcos. ¿Cuántos fallos de página se producirán si se utiliza la
técnica de selección de victimas:
i) LRU ii) Segunda Chance
b) Considerando una política de Asignación Fija con reparto equitativo y Reemplazo
Local y disponiéndose de 9 marcos. ¿Cuántos fallos de página se producirán si se utiliza
la técnica de selección de victimas:
i) LRU ii) Segunda Chance
23.- Sean los procesos A, B y C tales que necesitan para su ejecución las siguientes
páginas:
A: 1, 2, 1, 7, 2, 7, 3, 2
B: 1, 2, 5, 2, 1, 4, 5
C: 1, 3, 5, 1, 4, 2, 3
Si la secuencia de ejecución es tal que los procesos se ejecutan en la siguiente
manera:
1. C demanda 1 página 12. B demanda 2 páginas
2. A demanda 2 páginas 13. A demanda 1 página
3. C demanda 1 página 14. B demanda 2 páginas
4. B demanda 1 página 15. C demanda 2 páginas
5. A demanda 1 página 16. C demanda 1 página
6. C modifica la página 1 17. A demanda 1 página
7. B demanda 2 páginas 18. B termina
8. A demanda 1 página 19. A demanda 2 páginas
9. C demanda 1 página 20. C demanda 1 página
10. B modifica la página 2 21. A termina
11. A modifica la página 2 22. C termina
Considerando una política de Asignación Dinámica y Reemplazo Global y disponiéndose de
7 marcos, debiéndose guardar 1 marco para la gestión de descarga asincrónica de paginas
modificadas ¿Cuántos fallos de página se producirán si se utiliza la técnica de selección de
victima:
a) Segunda Chance
b) FIFO
c) LRU
24.- Considere un sistema cuya memoria principal se administra mediante la técnica de
paginación por demanda que utiliza un dispositivo de paginación, algoritmo de reemplazo
global LRU y una política de asignación que reparte marcos equitativamente entre los
procesos. El nivel de multiprogramación es actualmente, de 4.
Ante las siguientes mediciones:
a) Uso de CPU del 13%, uso del dispositivo de paginación del 97%.
b) Uso de CPU del 87%, uso del dispositivo de paginación del 3%.
c) Uso de CPU del 13%, uso del dispositivo de paginación del 3%.
Introducción a los Sistemas Operativos
Analizar:
¿Qué sucede en cada caso?
¿Puede incrementarse el nivel de multiprogramación para aumentar el uso de la
CPU?
¿La paginación está siendo útil para mejorar el rendimiento del sistema?
25.- Considere un sistema cuya memoria principal se administra mediante la técnica de
paginación por demanda. Considere las siguientes medidas de utilización:
Utilización del procesador: 20%
Utilización del dispositivo de paginación: 97,7%
Utilización de otros dispositivos de E/S: 5%
Cuales de las siguientes acciones pueden mejorar la utilización del procesador:
a) Instalar un procesador mas rápido
b) Instalar un dispositivo de paginación mayor
c) Incrementar el grado de multiprogramación
d) Instalar mas memoria principal
e) Decrementar el quantum para cada proceso
26.- La siguiente formula describe el tiempo de acceso efectivo a la memoria al utilizar
paginación para la implementación de la memoria virtual:
TAE At (1 p) * Am p * (Tf Am)
Donde:
TAE = tiempo de acceso efectivo
p = taza de fallo de pagina (0 <= p <=1)
Am = tiempo de acceso a la memoria real
Tf = tiempo se atención de una fallo de pagina
At = tiempo de acceso a la tabla de paginas. Es igual al tiempo de acceso a la
memoria (Am) si la entrada de la tabla de páginas no se encuentra en la TLB.
Suponga que tenemos una memoria virtual paginada, con tabla de paginas de 1 nivel, y
donde la tabla de páginas se encuentra completamente en la memoria.
Servir una falla de página tarda 300 nanosegundos si hay disponible un marco vacío o si la
página reemplazada no se ha modificado, y 500 nanosegundos si se ha modificado. El
tiempo de acceso a memoria es de 20 nanosegundos y el de acceso a la TLB es de 1
nanosegundo
a) Si suponemos una taza de fallos de página de 0,3 y que siempre contamos con un
marco libre para atender el fallo ¿Cual será el TAE si el 50% de las veces la entrada
de la tabla de páginas se encuentra en la TLB (hit)?
b) Si suponemos una taza de fallos de página de 0,3; que el 70% de las ocasiones la
pagina a reemplazar se encuentra modificada. ¿Cual será el TAE si el 60% de las
veces la entrada de la tabla de páginas se encuentra en la TLB (hit)?
c) Si suponemos que el 60% de las veces la pagina a reemplazar esta modificada, el
100% de las veces la entrada de la tabla de páginas requerida se encuentra en la
TLB (hit) y se espera un TAE menor a 200 nanosegundos. ¿Cuál es la máxima tasa
aceptable de fallas de página?
27.- Considere el siguiente programa:
#define Size 64
int A[Size; Size], B[Size; Size], C[Size; Size];
int register i, j;
for (j = 0; j < Size; j ++)
for (i = 0; i < Size; i++)
C[i; j] = A[i; j] + B[i; j];
Introducción a los Sistemas Operativos
Si asumimos que el programa se ejecuta en un sistema que utiliza paginación por demanda
para administrar la memoria, donde cada pagina es de 1Kb. Cada número entero (int) ocupa
4 bytes. Es claro que cada matriz requiere de 16 páginas para almacenarse. Por ejemplo:
A[0,0]..A[0,63], A[1,0]..A[1,63], A[2,0]..A[2,63] y
A[3,0]..A[3,63] se almacenara en la primer pagina.
Asumamos que el sistema utiliza un working set de 4 marcos para este proceso. Uno de los
4 marcos es utilizado por el programa y los otros 3 se utilizan para datos (las matrices).
También asumamos que para los índices “i” y “j” se utilizan 2 registros, por lo que no es
necesario el acceso a la memoria para estas 2 variables.
a) Analizar cuantos fallos de paginas ocurren al ejecutar el programa (considere las
veces que se ejecuta C[i,j] = A[i,j] + B[i,j])
b) Puede ser modificado el programa para minimizar el número de fallos de páginas. En
caso de ser posible indicar la cantidad de fallos de fallos de páginas que ocurren.
28.- Considere las siguientes secuencias de referencias a páginas de los procesos A y B,
donde se muestra en instante de tiempo en el que ocurrió cada una (1 a 78):
a) Considerando una ventana Δ=5, indique cual seria el conjunto de trabajo de los
procesos A y B en el instante 24 (WSA(24) y WSB(24))
b) Considerando una ventana Δ=5, indique cual seria el conjunto de trabajo de los
procesos A y B en el instante 60 (WSA(60) y WSB(60))
c) Para el los WS obtenidos en el inciso a), si contamos con 8 frames en el sistema ¿Se
puede indicar que estamos ante una situación de trashing? ¿Y si contáramos con 6
frames?
d) Considerando únicamente el proceso A, y suponiendo que al mismo se le asignaron
inicialmente 4 marcos, donde el de reemplazo de paginas es realizado considerando
el algoritmo FIFO. ¿Cuál será la taza de fallos en el instante 38 de páginas
suponiendo que la misma se calcula contando los fallos de páginas que ocurrieron
en las últimas 10 unidades de tiempo?
e) Para el valor obtenido en el inciso d), si suponemos que el S.O. utiliza como limites
superior e inferior de taza de fallos de paginas los valores 2 y 5 respectivamente
¿Qué acción podría tomar el S.O. respecto a la cantidad de marcos asignados al
proceso?
