h a n g e Vi h a n g e Vi

XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
SISTEMAS OPERATIVOS (2011-12)
k

k
lic

lic
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k

Grupo D
Ejercicios – 2

1. Considere un sistema con un espacio lógico de memoria de 128K páginas con 8 KB cada una, una
memoria física de 64 MB y direccionamiento al nivel de byte. ¿Cuántos bits hay en la dirección lógica?
¿Y en la física?

2. Sitúese en un sistema paginado con memoria virtual, en donde:

- la memoria real tiene un tamaño de 16 Mbytes
- una dirección virtual ocupa 32 bits, de los cuales los 22 de la izquierda constituyen el número de
página, y los 10 de la derecha el desplazamiento dentro de la página.

Según lo anterior,
a) ¿Qué tamaño tiene cada página?
b) ¿Cuál es el tamaño del espacio de direccionamiento virtual?
c) ¿En cuántos marcos de página se divide la memoria física?
d) ¿Qué tamaño deberá tener el campo Número de Marco de la Tabla de Páginas?
e) Además de dicho campo, suponga que la Tabla de Páginas tiene los siguientes campos con los
siguientes valores:
* Presencia: 1 bit (1= Presente en memoria fisica, 0= ausente)
* Modificación: 1 bit (1= Ha sufrido modificación desde que se cargó en memoria)
* Protección: 1 bit (1= Sólo se permite leer; 0= Cualquier tipo de acceso).
f) ¿Cuál es el tamaño de la Tabla de Páginas para un proceso cuyo espacio de memoria virtual es
de 103K bytes?

3. Sea un sistema de memoria virtual paginada con direcciones lógicas de 32 bits que proporciona un
espacio virtual de 220 páginas y con una memoria física de 32 Mbytes ¿cuánta memoria requiere en
total un proceso que tenga 453Kbytes, incluida su tabla de páginas cuyas entradas son de 32 bits?

4. Un ordenador tiene 4 marcos de página. En la siguiente tabla se muestran: el tiempo de carga, el

tiempo del último acceso y los bits R y M para cada página (los tiempos están en tics de reloj).
Responda a las siguientes cuestiones justificando su respuesta.

Tiempo Tiempo ultima Bit de Bit de

Página
de carga Referencia Referencia Modificación
0 126 279 1 0
1 230 235 1 0
2 120 272 1 1
3 160 200 1 1

a) ¿ Qué página se sustituye si se usa el algoritmo FIFO?

b) ¿ Qué página se sustituye si se usa el algoritmo LRU?
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
5. ¿Depende el tamaño del conjunto de trabajo de un proceso directamente del tamaño del programa e
k

k
lic

lic
C

C
w

w
m

m
w w
w

jecutable asociado a él? Justifique su respuesta.

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k

6. ¿Por qué una cache (o la TLB) que se accede con direcciones virtuales puede producir incoherencias
y requiere que el sistema operativo la invalide en cada cambio de contexto y, en cambio, una que se
accede con direcciones físicas no lo requiere?

7. Un ordenador proporciona un espacio de direccionamiento lógico (virtual) a cada proceso de 65.536

bytes de espacio dividido en páginas de 4096 bytes. Cierto programa tiene un tamaño de región de
texto de 32768 bytes, un tamaño de región de datos de 16386 bytes y tamaño de región de pila de
15878. ¿Cabría este programa en el espacio de direcciones? (Una página no puede ser utilizada por
regiones distintas). Si no es así, ¿cómo podríamos conseguirlo, dentro del esquema de paginación?

8. Analice qué puede ocurrir en un sistema que usa paginación por demanda si se recompila un
programa mientras se está ejecutando. Proponga soluciones a los problemas que pueden surgir en esta
situación.

9. Para cada uno de los siguientes campos de la tabla de páginas, se debe explicar si es la MMU o el
sistema quién los lee y escribe (en éste último caso si se activa o desactiva), y en qué momentos:
a) Número de marco.
b) Bit de presencia
c) Bit de protección
d) Bit de modificación
e) Bit de referencia

10. Suponga que la tabla de páginas para el proceso actual se parece a la de la figura. Todos los números
son decimales, la numeración comienza en todos los casos desde cero, y todas las direcciones de
memoria son direcciones en bytes. El tamaño de página es de 1024 bytes.

Número de Bit de validez Bit de Bit de Número de

página virtual o presencia referencia modificación marco de página
0 0 1 0 4
1 1 1 1 7
2 1 0 0 1
3 1 0 0 2
4 0 0 0 -
5 1 0 1 0
¿Qué direcciones físicas, si existen, corresponderán con cada una de las siguientes direcciones
virtuales? (no intente manejar ninguna falta de página, si las hubiese)
a) 999
b) 2121
c) 5400

11. Sea la siguiente secuencia de números de página referenciados: 1,2,3,4,1,2,5,1,2,3,4,5

Calcula el número de faltas de página que se producen utilizando el algoritmo FIFO y considerando
que el número de marcos de página de que disfruta nuestro proceso es de
a) 3 marcos
b) 4 marcos
¿Se corresponde esto con el comportamiento intuitivo de que disminuirá el número de faltas de
página al aumentar el tamaño de memoria de que disfruta el proceso?
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
k

k
lic

lic
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k

12. ¿Qué tipo de fragmentación se produce en un sistema de gestión de memoria virtual paginado? ¿Qué
decisiones de diseño se pueden tomar para minimizar dicho problema, y cómo afectan estas decisiones al
comportamiento del sistema?

13. Suponga que un proceso emite una dirección lógica igual a 2453 y que se utiliza la técnica de
paginación, con páginas de 1024 palabras
a) Indique el par de valores (número de página, desplazamiento) que corresponde a dicha
dirección.
b) ¿Es posible que dicha dirección lógica se traduzca en la dirección física 9322? Razónelo.

14. El tiempo medio de ejecución de una instrucción en un procesador es de 30 nsg. Tras diversas
medidas se ha comprobado que:
a) El 0.001% de las instrucciones producen falta de página.
b) El 30% de las ocasiones en que se produce la falta de página, la página que hay que
sustituir está “sucia”.
c) La velocidad de transferencia al dispositivo de disco es de 2MB/sg. El tamaño de cada
página es de 4 KB.
Calcule el tiempo efectivo de una instrucción (el tº que tarda en ejecutarse).

15. Suponga que tenemos 3 procesos ejecutándose concurrentemente en un determinado instante y que
todas sus páginas deben estar en memoria principal. El sistema operativo utiliza un sistema de memoria
con paginación. Se dispone de una memoria física de 131072 bytes (128K). Sabemos que nuestros
procesos al ser ejecutados tienen los siguientes parámetros:
Los datos indican el tamaño en bytes de
cada uno de los segmentos que forman
Proceso código pila datos
parte de la imagen del proceso. Sabiendo
A 20480 14288 10240 que una página no puede contener partes
B 16384 8200 8192 de dos segmentos diferentes (pila, código
o C 18432 13288 9216 datos), hemos de determinar el tamaño de
página que debería utilizar nuestro sistema y se barajan dos opciones: páginas de 4096 bytes (4K) o
páginas de 512 bytes (1/2K). Se pide:
a) ¿Cuál sería la opción más apropiada, 4096 bytes o 512 bytes?. Justifica totalmente la
respuesta mostrando todos los cálculos que has necesitado para llegar a dicha conclusión.
b) ¿Cuál es el formato de cada entrada de la Tabla de Páginas con el tamaño de página
elegido? Justifica el tamaño de los campos con direcciones. Puedes añadir los bits que
consideres necesarios para el buen funcionamiento del sistema indicando para que van a
ser utilizados.
c) ¿Cuántas Tablas de Páginas habrá en este sistema?¿Cuántas entradas hay en cada tabla
de páginas (filas)?

16. En la gestión de memoria en un sistema paginado, ¿qué estructura/s de datos necesitará mantener el
Sistema Operativo para administrar el espacio libre?

17. Situándonos en un sistema paginado, donde cada proceso tiene asignado un número fijo de marcos
de páginas. Supongamos la siguiente situación: existe un proceso con 7 páginas y tiene asignados 5
marcos de página. Indica el contenido de la memoria después de cada referencia a una página si como
algoritmo de sustitución de página utilizamos el LRU (la página no referenciada hace más tiempo). La
secuencia de referencias es la indicada en la figura.
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
k

k
lic

lic
Referencias 2 1 3 4 1 5 6 4 5 7 4 2
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k

Marcos de
página

¿Cuantas faltas de página se producen? _______

18. Supongamos que tenemos un proceso ejecutándose en un sistema paginado, con gestión de
memoria basada en el algoritmo de sustitución frecuencia de faltas de página. El proceso tiene 5
páginas ( 0, 1, 2, 3, 4 ). Represente el contenido de la memoria real para ese proceso (es decir, indique
que páginas tiene cargadas en cada momento) y cuándo se produce una falta de página. Suponga que,
inicialmente, está cargada la página 2, el resto de páginas están en memoria secundaria y que no hay
restricciones en cuanto al número de marcos de página disponibles. La cadena de referencias a página
es: 0 3 1 1 1 3 4 4 2 2 4 0 0 0 0 3 y el parámetro es τ=3.

19. Describa el funcionamiento del algoritmo de sustitución basado en la frecuencia de faltas de

página, con los siguientes datos: 4 marcos de página, en t = 0 la memoria contiene a la página 2. El
tamaño de la ventana es τ= 3 y se produce la secuencia de referencias de páginas, 1 4 2 2 2 4 5 5
3 3 5 1 1 1 1 4

20. Describa el funcionamiento del algoritmo de sustitución global basado en el algoritmo basado en el
modelo del conjunto de trabajo, con los siguientes datos: 4 marcos de página, en t= 0 la memoria
contiene a la página 2 que se referenció en dicho instante de tiempo. El tamaño de la ventana es τ= 3 y
se produce la secuencia de referencias de páginas, 1 4 4 4 2 4 1 1 3 3 5 5 5 5 1 4

21. Una computadora con memoria virtual paginada tiene un bit U por página virtual, que se pone
automáticamente a 1 cuando se realiza un acceso a la página. Existe una instrucción limpiar_U
(dir_base_tabla) que permite poner a 0 el conjunto de los bits U de todas las páginas de la tabla de
páginas cuya dirección de comienzo pasamos como argumento. Explica cómo puede utilizarse este
mecanismo para la implementación de un algoritmo de sustitución basado en el modelo del conjunto de
trabajo.
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
k

k
lic

lic
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k

22. Un Sistema Operativo con memoria virtual paginada tiene el mecanismo fijar_página(np) cuyo efecto
es proteger contra la sustitución al marco de página en que se ubica la página virtual np. El mecanismo
des_fijar (np) suprime esta protección.

a) ¿Qué estructura/s de datos son necesarias para la realización de estos mecanismos?

b) ¿En qué caso puede ser de utilidad estas primitivas?
c) ¿Qué riesgos presentan y qué restricciones deben aportarse a su empleo?

23. Implemente la política de sustitución global basada en la medida de la tasa de faltas de página de un
proceso; es decir, dé respuestas a las siguientes cuestiones:

a) ¿Qué parte del Sistema Operativo deberá tomar parte?

b) ¿Cuándo entra en ejecución dicho módulo del S.O.?
c) ¿Qué estructuras de datos será necesario mantener?
d) ¿Qué decisiones podría adoptar?

24. Disponemos de un ordenador que cuenta con las siguientes características: tiene una memoria
RAM de 4KBytes, permite usar memoria virtual paginada, las páginas son de 1KBytes de tamaño y las
direcciones virtuales son de 16 bits. El primer marco de página (marco 0) se usa únicamente por el
Kernel y los demás marcos están disponibles para su uso por los procesos que se ejecutan en el
sistema. Supongamos que tenemos sólo dos procesos, P1 y P2, y que utilizan las siguientes
direcciones de memoria virtual y en el siguiente orden:

Proceso Direcciones virtuales

P1 0-99
P2 0-500
P1 100-500
P2 501-1500
P1 3500-3700
P2 1501-2100
P1 501-600

a) ¿Cuántos marcos de página tiene la memoria RAM de este ordenador?

b) ¿Cuántos bits necesitamos para identificar los marcos de página?
c) Describe los fallos de página que tendrán lugar para cada intervalo de ejecución de los
procesos, si la política de sustitución de páginas utilizada es LRU. Suponga que se dicho
algoritmo es de asignación variable y sustitución global.

25. Estamos trabajando con un sistema operativo que emplea una gestión de memoria paginada sin
memoria virtual. Cada página tiene un tamaño de 2.048 bytes. La memoria física disponible para los
procesos es de 8 MBytes. Suponga que primero llega un proceso que necesita 31.566 posiciones de
memoria (o bytes) y, después, llega otro proceso que consume 18.432 posiciones cuando se carga en
memoria. Se pide:
a) ¿Qué fragmentación interna provoca cada proceso?
b) ¿Qué fragmentación externa provoca cada proceso?

26. Suponga un sistema que utiliza paginación a dos niveles. Las direcciones son de 8 bits con la
siguiente estructura: 2 bits en la tabla de páginas de primer nivel, 2 bits en la tabla de páginas de
segundo nivel y 4 bits para el desplazamiento). El espacio de direccionamiento virtual de un proceso
tiene la estructura del dibujo. Represente gráficamente las tablas de páginas y sus contenidos,
suponiendo que cada entrada de la tabla de páginas ocupa 8 bits y que todas las páginas están
cargadas en memoria principal (elige tú mismo la ubicación en memoria principal de dichas páginas,
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
suponiendo que la memoria principal es de 160 Bytes). Dada esa asignación traduce la dirección virtual
k

k
lic

lic
C

C
w

w
m

m
w w
w

47.

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k

27. Considere la siguiente tabla de segmentos:

Segmento Presencia o validez dirección base longitud

0 0 219 600
1 1 2300 14
2 1 90 100
3 0 1327 580
4 1 1952 96

¿Qué direcciones físicas corresponden a las direcciones lógicas (nº_segmento, desplazamiento)

siguientes? Si no puede traducir alguna dirección lógica a física, explique el por qué.
a) 0, 430 b) 1, 10
c) 3, 400 d) 4, 112

28. Considérese un sistema con memoria virtual en el que el procesador tiene una tasa de utilización
del 15% y el dispositivo de paginación está ocupado el 97% del tiempo, ¿qué indican estas medidas?
¿Y si con el mismo porcentaje de uso del procesador el porcentaje de uso del dispositivo de paginación
fuera del 15%?
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
k

k
lic

lic
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
k

k
lic

lic
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
k

k
lic

lic
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
k

k
lic

lic
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k
 h a n g e Vi h a n g e Vi
XC e XC e
F- w F- w
PD

PD
er

er
!

!
W

W
O

O
N

N
y

y
bu

bu
to

to
k

k
lic

lic
C

C
w

w
m

m
w w
w

w
o

o
.d o .c .d o .c
c u -tr a c k c u -tr a c k