SISTEMAS OPERATIVOS - PARTE II

PRACTICA de ADMINISTRACION DE MEMORIA

Ejercicios cuya realizacin se recomienda: 5, 6, 9, 11, 12,19, 20, 22, 23 y 24.
1) Diagramacin del algoritmo "la mejor zona que encuentre" para el mtodo de administracin de memoria de
particiones variables.
a)- Diagrame una rutina que dada una longitud de memoria asigne una particin de la longitud requerida
devolviendo la direccin de comienzo de la particin. Si no encuentra una particin como la solicitada
devolver una direccin de comienzo negativa.
b)- Diagrame una rutina que dada la direccin de comienzo de una particin la convierta en zona
disponible.
2) Cmo se modifican las rutinas diagramadas en el ej) 1 para que pueda ser utilizada en el mtodo de particiones
reubicables? Indicar de qu forma se modifican. Diagramarlo.
3) Dados los dos siguientes mtodos de administracin de memoria:
* Particionada variable y no reubicable
* Particionada variable y reubicable
Se pregunta:
a)- Al cabo de un tiempo de haber comenzado los trabajos del da, en cul de los dos hay ms trabajos en
memoria, y por qu?
b)- Qu parmetros utilizara Ud. para decidir que no vale la pena compactar.
c)- Si su trabajo comparte con otros la memoria, y debe entrar un nuevo trabajo, en cul de los dos
mtodos de administracin propuestos tardara ms en terminar su ejecucin.
d)- Cmo influye el tiempo de E/S en el mtodo de administracin particionada variable y reubicable.
e)- En qu momento es aconsejable la compactacin ?
4) Se han discutido dos algoritmos de administracin de memoria con particiones variables, la mejor y la primer
zona libre que se encuentre. Se propone un tercer algoritmo: "la peor zona libre que encuentre". Este siempre
asigna al trabajo la zona libre ms grande que encuentra.
a)- Comente su implementacin.
b)- Anticipe el rendimiento
c)- Muestre una secuencia de trabajos para la cual este algoritmo sea mejor a los otros dos.
d)- Muestre una secuencia de trabajos en la cual sea peor.
5) Dado un sistema con una Administracin de memoria Paginada sin demanda con 64K de memoria real, 20
bits de capacidad de direccionamiento y pginas de 4 K. Se pide:
a) Tamao mximo posible de un programa a ejecutar en este sistema (Escriba en binario la mxima
direccin ejecutable en el mismo)
b) Una instruccin del programa A (que tiene 20 pginas) direcciona a la pgina virtual 8 desplazamiento
X`400'. Explique claramente si tal instruccin es ejecutable o no en este sistema.
6) Suponga un esquema de memoria paginada con Memoria Virtual. Se estn ejecutando tres programas A, B y C
con longitudes de 2K, 1.5K, y 3K caracteres respectivamente. La longitud de la pgina es de 0.5K caracteres.
a)- Cul es la cantidad mxima de pginas que puede tener un programa si las instrucciones tienen
direcciones de 16 bits ?
b)- Disee la base de datos del sistema suponiendo que la mquina tiene una memoria de 64K.
c)- Determine el contenido de dichas tablas para los programas A, B y C. Los bloques 0 a 8 de la memoria
contienen las pginas A-0, B-0, C-5, A-1, A-2, C-3, C-1, B-2 y C-4.
d)- En la direccin X`0280' del programa A hay una instruccin de bifurcacin incondicional. Utilizando las
tablas definidas en c) determine la direccin de la memoria en la cual est la instruccin. Indique ahora
cmo acta el sistema, utilizando las tablas si es necesario, si en la instruccin se bifurca a la X`029A', a
la X`00BA' y a la X`0708'.
7) a) Disee todas las tablas necesarias para un sistema de administracin de Memoria Paginada por Demanda
que permita la eficiente remocin de pginas de cualquier programa en funcin de las necesidades de uno dado.
b) Diagrame la rutina de atencin de interrupciones por falla de pgina y remocin de pginas para el caso
anterior.
c) Discuta la ubicacin de la informacin necesaria para los puntos a) y b) en la BCP, TDP y TDB.
8) En un sistema de administracin de Memoria de Paginacin por Demanda :
[Link]

1er Cuat/2003

Pgina 1 de 5

a) Cul es el tamao mximo posible de un programa, despreciando la porcin de Sistema Operativo

residente, que ejecuta en un sistema de capacidad de direccionamiento de 16 bits, de 8 bits para nmero
de pgina y de una memoria real de 32 Kbytes ?
b) Cul es el tamao si la capacidad en disco para pginas es de 64 pginas ?
9) Tenemos un sistema de computacin con M1 pginas de memoria central y una memoria auxiliar (disco) con
capacidad para M2 pginas que llamaremos a, b, c, d, etc.
El "trazado" de un programa es la enumeracin de las pginas que ese programa referencia a medida que
se ejecuta. Supongamos que el "trazado" de un programa es P = abacabdbacd.
Para cada referencia del "trazado" puede determinarse:
* Si debe traerse o no una pgina de memoria auxiliar a memoria central.
* Cul pgina de memoria central es desalojada de acuerdo al algoritmo de reemplazo elegido : FIFO,
LRU, etc.
* Cul es el contenido de las M1 pginas de la memoria central.
* La siguiente relacin :
f = nro. de pginas tradas / nro. de referencias del trazado
se denomina Indice de Hallazgos a s = 1 - f
Se pide:
a) Para M1 = 2 utilizando un algoritmo FIFO, cul es el ndice de hallazgos ?
b) Idem a) para un algoritmo LRU.
c) Explicar brevemente por que hubo un reemplazo ms para el algoritmo FIFO. Cul es la caracterstica
del "trazado" suministrado que motiv que LRU fuese ms eficiente que FIFO ?
d) Repetir a) y b) para M1 = 4. Explique brevemente qu sucede. Especficamente, qu efecto tiene el
tamao de la memoria en s ?. Puede este resultado generalizarse ? Qu efecto tendra un cambio en el
tamao de la memoria auxiliar M2 ?
e) FIFO y LRU parecen intuitivamente ser mtodos aceptables. Un algoritmo de reemplazo de la pgina
ms utilizada recientemente parecera, en cambio, ser intuitivamente malo. Repita a) para un algoritmo de
este tipo y verifique esa afirmacin.
10) Los canales requieren direcciones reales fsicas para poder realizar la E/S. Si se usa una memoria paginada
sin realizar modificaciones al hardware de los canales se tropieza con un problema cuando se realiza una
operacin de E/S sobre una pgina y en la mitad de la operacin la pgina es elegida para ser removida. Existen
dos posibles soluciones :
* Mantener las pginas que contienen el "buffer" en memoria real, impidiendo temporariamente que sean
removidas. Debe modificarse adems el programa de canal correspondiente para que se refleje las
direcciones reales afectadas por la E/S.
* Asignar un "buffer" temporario en una zona no paginada reservada por el Sistema Operativo para
maniobra. Cuando la operacin de E/S ha terminado, mover la informacin del "buffer" temporario a la
pgina en cuestin.
Se pregunta :
a) Cmo implementara la primer solucin ? Qu tablas tendra que modificar ? Cmo determinara qu
pginas deben ser inmovilizadas ?
b) Si el buffer referenciado cruza el lmite entre dos pginas que no estn ubicadas en memoria en forma
contigua, cmo efectuara Ud. la E/S ? (siempre bajo el primer esquema).
c) Bajo el segundo esquema, si ocurre que un programa solicita E/S y no hay memoria disponible en la
zona temporaria de memoria reservada para tal fin, debe el programa esperar que alguna porcin de
memoria se libere ?, o puede el sistema operativo agrandar el rea de maniobra tomando memoria de la
zona paginada ?. En este ltimo caso, qu problemas podran presentarse ?
d) Qu factor determinara cul es el mejor esquema ? Indique una ventaja y una desventaja de cada uno.
e) Constate para ambos esquemas las simplificaciones que se introduciran si cada canal pudiera ejecutar
programas de canal directamente direccionando memoria virtual.
11) En qu modo de ejecucin no se utiliza la TDP para traducir direcciones ?
12) Dado el siguiente sistema :
* Subsistema de discos :
4000 RPM - 10 Sectores por pista - 2K por sector
Tiempo de posicionamiento medio 25 mseg
* Computador :
Memoria Real 2048K - Acceso a memoria 1 msg.
Direccionamiento de 32 bits, 20 bits para nro. de pgina
Operacin en procesador = Tiempo despreciable
* Sistema Operativo :
Administracin de Memoria : Paginacin por Demanda
[Link]

1er Cuat/2003

Pgina 2 de 5

Tiempo de proceso mdulo de pginacin 10 mseg (promedio)

Se pregunta :
a) Tamao mximo posible de un programa a ejecutar en este sistema.
b) Tamao de las pginas
c) Cunto tarda una operacin de paginacin promedio :
i) Carga de pgina
ii) Remocin y carga de pgina
d) Cuanto demora el acceso a una direccin de memoria real si:
i) TDP en memoria real. (direccin cargada en registro del procesador)
ii) TDP en memoria asociada del procesador (Cache)
e) Si se carga un programa que pone unos a la diagonal de una matriz de 1024 x 1024 elementos, donde
cada elemento es un entero X 4, y luego de completar esta operacin se coloca en cero toda la diagonal.
Indique cul es el ndice de hallazgos S. (Se deprecia el espacio ocupado por las instrucciones del
programa y se supone toda la memoria real dedicada para esta matriz).
f) Cmo modificara al sistema (no al programa) para que el ndice de hallazgos S sea 1/2.
13) Suponga un sistema de administracin de memoria por Paginacin con demanda que tiene TDP en el
procesador.
Una operacin de falta de pgina tarda 8 mseg si no hay remocin y 20 mseg si hay remocin.
La velocidad de acceso a memoria es 1 microseg. Se sabe que el 70 % de las operaciones de falta de
pgina implican remocin.
Se pide :
a) Cul es el mximo aceptable de paginacin (pginas/segundo) si se desea que el sistema no incurra en
thrashing ?
b) Y si se desea que el sistema por lo menos dedique el 60 % de su tiempo a procesar trabajos ?
14) Diagrame la rutina que dada una operacin de E/S (proceso, Direccin, Longitud) asegure al Supervisor de
E/S que todas las pginas que se necesitan para esa operacin estn en condiciones de poder realizarla.
15) Qu inconveniente trae tener la direccin del archivo de Memoria Virtual en la TBCP ? (Una nica direccin)
16) Disee todas las tablas necesarias para un sistema de administracin de memoria por Segmentacin y
Memoria Virtual.
17) Considere un sistema que no posee memoria virtual y tiene registros Base y Longitud. Es necesario
implementar algn tipo de Memoria Virtual. Cul implementara, Paginacin o Segmentacin ? Cul es ms fcil ?
Explique la implementacin elegida.
18) Implemente un sistema de administracin de memoria Paginada que permita compartir pginas entre distintos
procesos.
19) En un sistema de administracin de memoria segmentada :
a) Cmo tendra que ser el segmento que contiene a la rutina SENO ?
b) Cmo se resuelve el problema de un buffer que cruza el lmite entre 2 segmentos ?
20) Supongase un sistema de procesamiento con las siguientes caractersticas :
- Tamao de memoria real : 32 K
- Tamao del S.O. : 14 K (ya includos en los 32 K anteriores)
- Tamao del bloque de memoria : 2 K
- Longitud de la palabra de direccionamiento : 16 bits
- Administracin de memoria : Paginado por demanda
- Administracin del procesador : Round-Robin multinivel
- Algoritmo de remocin de pginas : LRU
La tabla de bloques del sistema contiene la siguiente informacin :
DIRECCION DE
ASIGNADO A
PAGINA DEL
TIENE
COMIENZO
PROGRAMA
PROCESO
E/S?
14
B
5
SI
16
C
2
SI
18
B
7
SI
20
---22
C
3
SI
24
---26
---[Link]

1er Cuat/2003

CAMBIO?
-SI
-----Pgina 3 de 5

28
30

B
--

6
--

SI
--

SI
--

Se pide :
a) Tamao posible de un programa a ejecutar en este sistema, tamao de las pginas y cantidad mxima de pginas de un programa.
b) Se tiene un programa A de 36 K de longitud que se desea ejecutar en esta instalacin. Suponiendo
que la traza del programa es de la siguiente forma :
TRAZA : 0120817
Arme la tabla de distribucin de bloques luego de la finalizacin del programa.
c) Calcule el ndice de fracasos del programa A y explique qu sucede al referenciarse la pgina 7.
d)En el programa A en la direccin X"0857" se encuentra la siguiente instruccion : BIFURCAR A
X"A01C"
i)- Calcule las direcciones reales de ambas (utilice la informacin de la traza dada)
ii)- Qu sucede cuando se ejecuta esta instruccin bifurcacin ?
21) En la tabla anexa se listan los mtodos de administracin de memoria estudiados en orden creciente de
complejidad. Para cada uno de los mtodos indique qu problema resuelve con respecto al mtodo que tiene
arriba en la lista y qu caractersticas hardware y software (si hubiere) los diferencian.
METODO DE
ADMINISTRA-CION DE
MEMORIA

PROBLEMAS
RESUELTOS

HUEVO HARDWARE
NECESITADO

NUEVO SOFTWARE
NECESITADO

SIMPLE CONTIGUA
PARTICIONADA
PARTICIONADA
REUBICABLE
PAGINACION CON
MEMORIA VIRTUAL
SEGMENTACION
22) Suponga un esquema de memoria paginada con Memoria Virtual. Se estn ejecutando tres programas A, B y
C con longitudes de 2K, 1.5K, y 3K caracteres respectivamente. La longitud de la pgina es de 0.5K caracteres.
a)- Cul es la cantidad mxima de pginas que puede tener un programa si las instrucciones tienen
direcciones de 16 bits ?
b)- Disee la base de datos del sistema suponiendo que la mquina tiene una memoria de 20K.
c)- Determine el contenido de dichas tablas para los programas A, B y C. Los bloques 0 a 8 de la memoria
contienen las pginas A-0, B-0, C-5, A-1, A-2, C-3, C-1, B-2 y C-4.
d)- En la direccin X`0481' del programa A hay una instruccin de bifurcacin incondicional. Utilizando las
tablas definidas en c) determine la direccin de la memoria en la cual est la instruccin. Indique ahora
cmo acta el sistema, utilizando las tablas si es necesario, si en la instruccin se bifurca a la X00FF,
X`061F' y a la X`08ED'.
23) Una instalacin se encuentra implementando una nueva poltica de administracin de memoria paginada
por demanda. La instalacin cuenta con 16 bits de capacidad de direccionamiento y bloques de 128
bytes. Sin embargo se ha limitado la cantidad de pginas de los procesos utilizando solamente 3 bits.
Se pide:
a)- Indique el mximo tamao de un programa a ejecutar en esta instalacin. Escriba la mxima direccin en binario.
b)- Indique el tamao mximo de un programa en esta instalacin cuando la misma se encuentre totalmente funcional y permita la utilizacin completa de su capacidad de direccionamiento.
c)- Indique (en el caso a) qu ocurre cuando el proceso Z que posee 7 pginas y cuyas pginas 0, 1, 5
y 6 se encuentran cargadas en memoria real, trata de acceder a cada una de las siguientes direcciones:
i) X 080B
ii) X 03F5
iii) X 0203
d)- Qu componente del sistema operativo detecta cuando un proceso intenta acceder a una pgina
que no existe? Justifique.
[Link]

1er Cuat/2003

Pgina 4 de 5

24) Dado el siguiente programa en una administracin de Memoria Paginada por demanda en el cual se indican
como han quedado conformadas las distintas pginas del mismo :
Pgina a

A=4
*(A) *(4)
I=1
*(I) *(1)
------------------------------------------------------------------------------Pgina b
501
K=2*A
*(K) *(2)
Print K
------------------------------------------------------------------------------Pgina c
If I > 1
Then STOP
I=I+1
------------------------------------------------------------------------------Pgina d
GO TO 501
El smbolo *(n) indica que en ese lugar del programa objeto se ha almacenado la variable "n"
Se pide :
a) Construya la traza de ejecucin de este programa
b) Calcule el ndice de hallazgos y de fracasos suponiendo que existen 3 bloques en memoria real y el
algoritmo de remocin es LRU.
c) Cuntos bloques de memoria debera contener el sistema para ejecutar este programa si la administracin fuera Paginada Sin Demanda ? Justifique.

[Link]

1er Cuat/2003

Pgina 5 de 5