Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 1
Ejer
cici
o 1
Ejer
cici
o 1
Ejercicio 1) Un sistema realiza una gestión de memoria virtual mediante paginación por demanda, con la memoria dividida en cinco marcos de 512 posiciones cada uno. En un momento determinado, se encuentran en el sistema tres procesos, cada uno de ellos con el siguiente esquema de memoria lógica.
Proceso A Proceso B Proceso CA1 B1 C1A2 B2 C2A3 B3 C3
B4 C4C5
Durante la ejecución de dichos procesos, se produce la siguiente secuencia de accesos a páginas, que dan lugar a la ocupación de memoria que se muestra:
¿Qué algoritmo y qué estrategia de sustitución de páginas se ha utilizado. Justificar la respuesta indicando porqué no pueden ser ninguno de los otros algoritmos estudiados
A1 A2 B1 B2 B3 C1 C2 C3 C2 A2 A1 A2 B4 B1A2 A2 A2
B1B4C3C2
B1A2B1B2
A2A2A1A2A2A2A2A2A2B3 B3B2
B3B3B2C1
B2C1C2
B2C3C2
B3B2C3C2
B3B2C3
B3B2C3
C2
B3B2
C2C3
B3
C2
B4C3C2
C5 C4A2B1B4C5C2
t0 A1 A2t1 B1t2 B4t3 C5t4 C4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 2
A1 A2 B1 B2 B3 C1 C2 C3 C2 A2 A1 A2 B4 B1A2 A2 A2
B1B4C3C2
B1A2B1B2
A2A2A1A2A2A2A2A2A2B3 B3B2
B3B3B2C1
B2C1C2
B2C3C2
B3B2C3C2
B3B2C3
B3B2C3
C2
B3B2
C2C3
B3
C2
B4C3C2
C5 C4A2B1B4C5C2
t0 A1 A2t1 B1t2 B4t3 C5t4 C4Ej
erci
cio
1Ej
erci
cio
1
Vemos que los marcos están asignados de forma local a los procesos POLÍTICA DE REEMPLAZO LOCAL
No nos dan suficiente información para evaluar los algoritmos• De la segunda oportunidad o del reloj• Con bits referenciado y modificado
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 3
Ejer
cici
o 1
Ejer
cici
o 1
FIFO: sustituir la que entró primero, con política localProceso A: funciona ya que solo usa un marcoProceso B: funciona, se reemplaza siempre al primero que entróProceso C: La referencia a C5 debería reemplazar a C2. NO CUMPLE
FallosA1 A2 B1 B2 B3 C1 C2 C3 C2 A2 A1 A2 B4 B1
A2 A2 A2B1B4C3C2
B1A2B1B2
A2A2A1A2A2A2A2A2A2B3 B3B2
B3B3B2C1
B2C1C2
B2C3C2
B3B2C3C2
B3B2C3
B3B2C3
C2
B3B2
C2C3
B3
C2
B4C3C2
C5 C4A2B1B4C5C2
t0 A1 A2t1 B1t2 B4t3 C5t4 C4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 4
Ejer
cici
o 1
Ejer
cici
o 1
ÓPTIMO: sustituir el que estará más tiempo sin usarseProceso A: funciona ya que solo usa un marcoProceso B: Al referencia B3 debe sustituir a B2. NO CUMPLEProceso C: Al referencias C5 no puede distinguir si C2 o C3
FallosA1 A2 B1 B2 B3 C1 C2 C3 C2 A2 A1 A2 B4 B1
A2 A2 A2B1B4C3C2
B1A2B1B2
A2A2A1A2A2A2A2A2A2B3 B3B2
B3B3B2C1
B2C1C2
B2C3C2
B3B2C3C2
B3B2C3
B3B2C3
C2
B3B2
C2C3
B3
C2
B4C3C2
C5 C4A2B1B4C5C2
t0 A1 A2t1 B1t2 B4t3 C5t4 C4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 5
Ejer
cici
o 1
Ejer
cici
o 1
LRU: sustituir el que está más tiempo sin usarseProceso A: FUNCIONA ya que solo usa un marcoProceso B: FUNCIONAProceso C: FUNCIONA
Los círculos de igual color corresponden con la página que lleva más tiempo sin usarse
FallosA1 A2 B1 B2 B3 C1 C2 C3 C2 A2 A1 A2 B4 B1
A2 A2 A2B1B4C3C2
B1A2B1B2
A2A2A1A2A2A2A2A2A2B3 B3B2
B3B3B2C1
B2C1C2
B2C3C2
B3B2C3C2
B3B2C3
B3B2C3
C2
B3B2
C2C3
B3
C2
B4C3C2
C5 C4A2B1B4C5C2
t0 A1 A2t1 B1t2 B4t3 C5t4 C4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 6
Ejer
cici
o 2
Ejer
cici
o 2
Ejercicio 2) Un sistema realiza una gestión de memoria virtual mediante paginación por demanda, paginas de 512 posiciones, memoria logica de 16 páginas (0 a 15), memoria física de 4 marcos (0 a 3).
a) Tabla de páginas:PAGÍNA MARCO V/I
5 2 v
10 i
15 i
11 i
12 i
13 i
14 i
6 i
7 i
8 i
9 1 v
0 i
1 3 v
2 i
3 i
4 0 v
Trama contenido0 Pag 41 Pag 92 Pag 53 Pag 1
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 7
Ejer
cici
o 2
Ejer
cici
o 2
2 b) Tabla de páginas tras generar las siguientes direcciones lógicas usando algoritmo óptimo para el reemplazo de páginas:
Hay que calcular las direcciones físicas para conocer en que marco se cargan las páginas, para ello tenemos que saber nº de bits para la página, nº de bits de desplazamiento y para el marco.
Tamaño página= 512 posiciones=2 9 9 bit para el desplazamiento
Memoria lógica= 16 páginas 2 4 4 bits para nº página
Memoria física= 4 marcos (0..3)
D.Lógica Pag desplazamiento (9bits) secuencia de páginas
1) 0458h 0000 0100 0101 1000 Página 2
2) 066Dh 0000 0110 0110 1101 Página 3
3) 0801h 0000 1000 0000 0001 Página 4
4) 026Eh 0000 0010 0110 1110 Página 1
5) 0AD8h 0000 1010 1101 1000 Página 5
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 8
Ejer
cici
o 2
Ejer
cici
o 2
2b) Tabla de páginas:
1) 2) 3) 4) 5)Pg 4 9 5 1 2 3 4 1 5
4 495
44449 35
25
1 151
351
4351
4351
9t0 4t1t2t3
Reemplazo 9
Reemplazo 2
PAGÍNA MARCO V/I
5 2 v
10 i
15 i
11 i
12 i
13 i
14 i
6 i
7 i
8 i
9 1 i
0 i
1 3 v
2 i
3 1 v
4 0 v
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 9
Ejer
cici
o 2
Ejer
cici
o 2
2c) En la situación final del apartado 2b) obtener las direcciones físicas equivalentes a las direcciones lógicas siguientes:
D.Lógica Pag desplazamiento (9bits) secuencia de páginas
6) 065Ch 0000 0110 0101 1100 Página 3
7) 0353h 0000 0011 0101 0011 Página 1
8) 0A8Ch 0000 1010 1000 1100 Página 5
D. Física
6) Pag3- Marco 1 1 0 0101 1100 025Ch
7) Pag1- Marco 3 11 1 0101 0011 0753h
8) Pag5- Marco 2 10 0 1000 1100 048Ch
2d) ¿qué ocurre al referenciar la dirección lógica 0532h?
9) 0532 h 0000 0101 0011 0010 Página 2
Se produce un fallo de página ya que no está en memoria.
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 10
Ejer
cici
o 4
Ejer
cici
o 4
Ejercicio 4) Administración de memoria por paginación por demanda.
Nº max páginas de un proceso=64= 2 6 6 bit para página
Memoria principal= 16 marcos
Tamaño de palabra de memoria o posición memoria= 16 bits= 2bytes
Sabemos tabla de páginas, marco, V/I referenciado y modificado y D.Física
a) D.Lógica y tipo de acceso L, E, cualquiera
b) Tamaño max de un proceso, tamaño memoria principal, tamaño de página y marco
c) ¿se usa algoritmo óptimo?
d) ¿se usa algoritmo con bit referenciado y modificado?. En 1 ¿Qué página lleva más tiempo en memoria 3 o 5?
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 11
Ejer
cici
o 4
Ejer
cici
o 4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 12
Ejer
cici
o 4
Ejer
cici
o 4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 13
D.Física M Pag
1110 7
2
4
2
4
0
3
7
0101
1010
0101
1011
Acceso Pag Desplazam. D.Lógica
0110
1110
1111
1111
0101
0011
1011
0110
0011
0110
1100
L M=0F0001
0100
0011
1010
1011
0101
E M=1
0110
A
5
A
5
3
F
L M=0
ELRM=1
E M=1
0111 F
LE RM=1
L M=0
L M=0
111
10
100
10100
0
11
6) 0635 0000 035h
111
7) 1E66 0001 666h
8) 1FC7 0001 FC7h
1) 1EF1 0001 EF1h
2) 1554 0001 554h
3) 0A33 0000 833h
4) 15BA 0001 5BAh
5) 0B6B 0000 96Bh
4 a) D.Lógica y tipo de acceso L, E, cualquiera
Buscamos que bits corresponden a los marcos de las páginas que se sustituyen.
Mirando las tablas de páginas del enunciado vemos que se usan los marcos:
3, 5, A y F (en binario 11, 101, 1010, 1111)
1) Como máximo empieza por 1111 y como mínimo 11
2) Como máximo empieza por 1010 y como mínimo 101
3) Mirando 2) veo 3) es marco 101 por lo que
Podemos escribir la página mirando las tablas de páginas.
7 bits para marco9 bits desplazamiento
Ejer
cici
o 4
Ejer
cici
o 4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 14
4 b) Tamaño max de un proceso, tamaño memoria principal, tamaño de página y marco
Tenemos nº bits de desplazamiento =9
Tamaño de palabra o posición de memoria=16 bits=2 bytes
(Tamaño de página en bytes)
2 9 =
Tamaño de palabra o posición en bytes
Tamaño de página= 2 9 . 2 1 = 2 10 bytes= 1024 bytes =1 Kbytes=
= Tamaño de marco
Tamaño max proceso=64 pag.Tamaño pag=64.1Kbytes=64Kbytes
Tamaño memoria principal=16marcos.Tamaño marco=16Kbytes
Ejer
cici
o 4
Ejer
cici
o 4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 15
4 c) ¿se usa algoritmo óptimo?
1 2
Óptimo: sustituir el que estará más tiempo sin usarse (no usa RM)
1 2 sustituye a 5 que no se usa (OK)
2 4 sustituye a 3 y debería sustituir a 7 MAL
NO ÓPTIMO
1) 2) 3) 4) 5)2
042
4
7
RM
RM01 010 411
011111
10 1027
6)0 R
M11111110
0427
7)3 R
M11111110
0423
8)7 R
M11111110
0427
Pg 7 RM
2 RM
4 RM
01 0327
0001001
00 1011
42
10 71110
0010
3h 05h 3Ah 5Fh 7
Ejer
cici
o 4
Ejer
cici
o 4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 16
4 d) ¿se usa algoritmo con bits referenciado y modificado?. En 1 ¿Quépágina lleva más tiempo en memoria 3 o 5?
1 2 3 4
Bit referenciado y modificado: orden de sustitución: RM= 00 , 01 , 10 , 11
1 00 Sustituir 3 o 5? 5 lleva más tiempo (a igualdad en RM, FIFO)
2 00 Sustituir pag 3 –OK
3 10 Sustituir pag 7 –OK
4 10 Sustituir pag 3 –OK
ES ALGORITMO DE REFERENCIADO Y MODIFICADO
1) 2) 3) 4) 5)2
042
4
7
RM
RM01 010 411
011111
10 1027
6)0 R
M11111110
0427
7)3 R
M11111110
0423
8)7 R
M11111110
0427
Pg 7 RM
2 RM
4 RM
01 0327
0001001
00 1011
42
10 71110
0010
3h 05h 3Ah 5Fh 7
Ejer
cici
o 4
Ejer
cici
o 4
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 17
Ejer
cici
o 3
Ejer
cici
o 3
Ejercicio 3) Administración de memoria por segmentación paginada con paginación por demanda y política de reemplazo local.
Los 5 segmentos de un procesos son los siguientes (numerados de 0..4)
Inicialmente ninguna página en memoria
Se generan las D. lógicas de la tabla y se conocen sus correspondientes D. Físicas
I
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 18
Ejer
cici
o 3
Ejer
cici
o 3
3a) ¿nº de marcos asignados al proceso y cuáles? ¿Tamaño del marco de memoria? Nº máximo de páginas que puede tener un segmento?¿nº de posiciones máximo que puede tener la memoria?
5 segmentos paginados se necesitan mínimo 3 bits para nº de segmento
Tenemos que ver cuantos bits son para desplazamiento: buscamos hasta donde se repite de atrás hacia delante las D.L y D.F.
Los últimos 9 bits se repiten como máximo hay 9 bits para desplazamiento
Puede que algún bits sea del nº de página, hay que comprobar que números de segmento y páginas son válidos.
D.lógica Seg. Pag. Desplazamiento Marco Desplazamiento D.física
0000 0000 0000 0100 0011
1111 1100
0100
0100
0011
1011
0110
1001
1010
0110
0100
0110
0000
0000
0000
0000
1000
0110
0110
1000
0010 0100 0011
0000
1000
0000
1000
11001111
1011
0110
0100
0100
1001 0011
1) 00043h 0101 5243h
2) 80AFCh 0111 70FCh
3) 606B4h 0101 58B4h
4) 60464h 0111 7064h
5) 80693h 0101 5893h
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 19
Ejer
cici
o 3
Ejer
cici
o 3 Sabemos: álgún bits del nº pag.?
S0 (000) tiene 3 páginas en binario 11
S1 (001) tiene 3 páginas en binario 11 1010 no es una
S2 (010) tiene 5 páginas en binario 101 página válida
S3 (011) tiene 4 páginas en binario 100
S4 (100) tiene 6 páginas en binario 110 máximo número de página
9 bits desplazamiento; 8 bits nº página ; ¿MARCOS USADOS?
3 bits nº segmento; 7 bits nº marco
D.lógica Seg. Pag. Desplazamiento Marco Desplazamiento D.física Marco
0000 0000 0000 0100 0011 5243h
70FCh
58B4h
7064h
1111
5893h
1100
29 h
38 h
1011 2C h
0110 38 h
0100
0100
0011 2C h1001
1010
0110
0100
0110
0000
0000
0000
0000
1000
0110
0110
1000
0010 0100 0011
0000
1000
0000
1000
11001111
1011
0110
0100
0100
1001 0011
1) 00043h 0101
2) 80AFCh 0111
3) 606B4h 0101
4) 60464h 0111
5) 80693h 0101
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 20
Ejer
cici
o 3
Ejer
cici
o 3
Tenemos 7 bits para el número de marco, por lo que los marcos usados han sido:
29 h; 38 h; 2C.
Tamaño página= Tamaño marco; No sabemos el tamaño de una posición en byte
Hay que dar el tamaño en función de posiciones
Tamaño página= Tamaño marco= 2 9 posiciones de memoria
(Tamaño de página en bytes)
2 nº bits desplazamiento =
Tamaño de palabra o posición en bytes
Nº máximo de páginas de un segmento = 2 nº bits para página = 2 8 = 256 páginas
Nº posiciones máximo de memoria= (una dirección física usa 16 bits)= 2 16 posiciones
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 21
Ejer
cici
o 3
Ejer
cici
o 3
3b) Dadas las siguientes direcciones lógicas que se generan posteriormente, si se usa algoritmo de reemplazo con bits referenciado y modificado (SO pone referenciado =0 después de cuatro accesos a memoria), calcular D. Físicas a las que se accede.
Teniamos:
1) Seg 0, pag 0; marco=29 h E
2) Seg 4, pag 5; marco=38 h L
3) Seg 3, pag 3; marco= 2C h L
4) Seg 3, pag 2; marco=38 h L
5) Seg 4, pag 3; marco 2C h E Desplazamiento
6) 40764 h L 0100 0000 0111 0110 0100 Seg 2, pag 3 marco=?
7) 0018C h E 0000 0000 0001 1000 1100 Seg 0, pag 0
8) 806DC h L 1000 0000 0110 1101 1100 Seg 4, pag 3
9) 202C3 h E 0010 0000 0010 1100 0011 Seg 1, pag 1
10) 815C7 h E 1000 0001 0101 1100 0111 Seg 4, pag 10
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 22
1) 2) 3) 4)S3,2 RM
01
00
00
S0,0
S3,2
5)
S3,3
RM
11
10
10
RM
01
00
11
S4,3
S0,0
S3,2
S4,3
6)S2,3 RM
01
10
11
S0,0
S2,3
S4,3
Pg S0,0 RM S4,5 RM S3,3 RM
11 S0,0
S4,5
11S0,011
10 S4,5
S3,3
10
10
29h S0,0
38h2ChEj
erci
cio
3Ej
erci
cio
31) Seg 0, pag 0; marco=29 h E 6) Seg 2, pag 3 L marco 38
2) Seg 4, pag 5; marco=38 h L 7) Seg 0, pag 0 E marco 29
3) Seg 3, pag 3; marco= 2C h L 8) Seg 4, pag 3 L marco 2C
4) Seg 3, pag 2; marco=38 h L 9) Seg 1, pag 1 E marco 38
5) Seg 4, pag 3; marco 2C h E 10) Seg 4, pag 10 E ERROR Direccionamiento
Usaremos la notación: Si,k para indicar segmento i pagina k
7) 8) 9)RM
01
00
S1,1
01
S0,0
RM
01
11S1,1
01S4,3
10)S4,10 RMPg S0,0 RM S4,3 RM
11 S0,0
S2,3
S4,3
10
11
10
11 11
29h S0,0
38h S2,3
2Ch S4,3
Sistemas Operativos (II11) – TEMA 4. Administración de Memoria 23
Ejer
cici
o 3
Ejer
cici
o 3
Dirección Física
6) Marco 38 0111 0001 0110 0100 7164 h
7) Marco 29 0101 0011 1000 1100 538C h
8) Marco 2C 0101 1000 1101 1100 58DC h
9) Marco 38 0111 0000 1100 0011 70C3 h
10) No exite la página 10 error en direccionamiento