MEMORY
MANAGEMENT-1
Cátedra: Sistemas Operativos
UTN-FRSF
NADA que la CPU toma esta en disco, solo
Introducción tiene memoria y puertos de E/S.
Si el programa esta en disco, primero lo que
hace Linux toma el archivo, lo interpreta y
vuelca en la memoria el código y los datos, por
lo que la CPU desconoce completamente al
disco.
•La memoria es un recurso muy importante
que debe ser cuidadosamente manejado.
(Ya que la mayoría de los datos y codigo se obtiene de la memoria)
•La ley de Parkinson dice:
”Los Programas se expanden hasta llenar toda
la memoria disponible para contenerlos”
•Lo que todo programador quiere es una
memoria ilimitada y rápida.
Gestión de Memoria
➢Rendimiento al Asignar Memoria
➢Rendimiento al Liberar Memoria
➢Complejidad del Algoritmo
➢Aprovechamiento de la Memoria
➢Reubicación
➢Complejidad para la Protección de Memoria
➢Complejidad para Compartir Memoria
Gestión de Memoria El programa tiene una dirección cero
donde comenzara a ejecutarse, pero
yo no se en que parte de la memoria
esta.
Poner a ejecutar el 2 instancias del mismo programa
tendrán direcciones cero (de inicio)
proceso en cualquier
direccion sin cambiar el
codigo del procesos
Reubicación diferentes en memoria.
Cuando uno hace el programa, no
decide donde ubicarlo en la memoria,
el SO se encarga de ubicarlo.
• Los programadores no saben efectivamente en que
lugar de la memoria serán ejecutados sus
programas Las referencias a memoria del proceso son siempre RELATIVAS
• Un proceso puede ser reubicado varias veces en
memoria principal por swapping
• Las referencias a memoria tanto en código como en
Datos deben ser traducidas a las direcciones físicas
en la que se encuentra el programa ElestoSOpueda
le da datos al HW para que
ocurrir
Gestión de Memoria
Protección
• Los procesos no deberían poder referenciar a
direcciones de memoria de otros procesos sin
permisos
• Es imposible chequear ésto en tiempo de
compilación ya que los programas pueden ser
reubicados
• Las referencias a memoria deben chequearse en
tiempo de ejecución (hardware)
UNICO que puede verificar los permisos de acceso a
memoria de un proceso, ni siquiera lo puede hacer el SO.
Gestión de Memoria
Compartición
• Se debe permitir que los procesos tengan porciones
comunes de memoria sin comprometer la
protección.
• Los procesos cooperativos necesitan acceder a
estructuras de datos comunes.
• Mejor aprovechamiento de memoria al compartir
código de programas.
Se ejecuta un solo programa en mi sistema
Monoprogramación
No tenia drives para las controladoras, solo usaba la controladoras que estaban en la ROM-BIOS.
Ya que mientras mas chico el SO mas espacio para el usuario, es por esto que se reutilizaban los controladores.
•Sólo hay un proceso en memoria, que se comparte únicamente con
el Sistema Operativo, que puede estar en ROM o RAM.
•Se pueden dar distintas configuraciones:
Memoria Libre
en
Grado de Multiprogramación
Si un proceso P tiene la probabilidad p de estar bloqueado
realizando una E/S, entonces cuando lo n procesos se encuentren
simultáneamente realizando operaciones de E/S, la CPU estará
Osea, todos bloqueados Si tengo un proceso que tiene una
libre. probabilidad de 0,4 de estar haciendo una
E/S (de estar bloqueado) entonces hay
pcpu_ocupada = 1 - pn una probabilidades de 1-0.4 = o,6 de que
este usando la CPU.
Esto incrementa exponencialmente dependiendo la
Poca E/S cantidad "n" de procesos que haya
Cuanto mas E/S uso, la curva es mas baja
Si la probabilidad de que estén bloqueado es
baja, entonces es alta que estén usando la CPU
Si quiero tener mi CPU ocupada, debo tener un alto grado de multiprogramación
Grado de Multiprogramación
Grado de Multiprogramación
Con mas memoria, puedo almacenar
Ejemplo: Si se tiene una computadora con: mas procesos, incrementando la
posibilidad de que la CPU este
• 1 Mb de memoria ocupada.
Mientras mas memoria agrego, el
• Cada proceso ocupa 500 Kb rendimiento incrementara cada vez en
porcentajes mas bajos debido al
• Cada proceso tiene p = 0,6 comportamiento exponencial que
posee.
Para esta configuración el rendimiento es de 64%
Si adquirimos 1 Mb adicional el rendimiento se eleva a 87%
El rendimiento incremental (87-64) = 23%
Si adquirimos 1 Mb adicional más el rendimiento se eleva 95%
El rendimiento incremental del segundo Mb es de (95-87) = 8 %
Grado de Multiprogramación
Ejecutar rapidamente varias veces el programa gradomp
nessus:/home/so# ./gradomp &
nessus:/home/so# ./gradomp &
nessus:/home/so# ./gradomp &
nessus:/home/so# ./gradomp &
LUEGO ver %id en top
Ir matando procesos desde top con K
Para TERMINAR #killall gradomp
CPU libre
Cpu(s): 85.7%us, 14.3%sy, 0.0%ni, 0.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
Mem: 1034952k total, 382780k used, 652172k free, 14364k buffers
Swap: 409616k total, 0k used, 409616k free, 219816k cached
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
2982 root 20 0 1532 348 292 R 20.6 0.0 0:03.94 gradomp
2984 root 20 0 1532 352 292 R 20.6 0.0 0:02.91 gradomp
2986 root 20 0 1532 348 292 R 20.0 0.0 0:02.68 gradomp
2983 root 20 0 1532 348 292 R 19.6 0.0 0:02.93 gradomp
2985 root 20 0 1532 344 292 R 18.6 0.0 0:02.67 gradomp
1 root 20 0 2028 720 624 S 0.0 0.1 0:01.31 init
Aprox 100% uso de CPU entre los 5 procesos
Grado de Multiprogramación
CAMBIAR EL PROGRAMA gradomp con distintas combinaciones
De uso de CPU y de E/S
#define MAXLOOP 100000L
#define USO_CPU 10L
#define NSECS 900000L
Cpu(s): 81.0%us, 15.0%sy, 0.0%ni, 3.7%id, 0.0%wa, 0.0%hi, 0.3%si, 0.0%st
Mem: 1034952k total, 383128k used, 651824k free, 14460k buffers
Swap: 409616k total, 0k used, 409616k free, 220292k cached
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
3003 root 20 0 1532 344 292 R 48.9 0.0 0:25.88 gradomp
3006 root 20 0 1532 352 292 R 46.5 0.0 0:25.28 gradomp
2255 root 20 0 9188 3644 2560 S 0.3 0.4 0:10.26 sshd
A medida que salen y entran nuevos
Particiones Fijas procesos, van dejando pequeños huecos
en memoria que no se pueden
aprovechar, bajando el rendimiento y el
nivel de multiprog.
•Las particiones pueden ser
de tamaño fijo, definidas
(p.ej.) por el usuario al
Adm del
inicio de la sesión. sistema, no
el usuario
•Limita el grado de final
multiprogramación
•El control de memoria se
reduce a asignar una
partición a cada proceso Forma de adm de
particiones: El SO hace
entrante, reasignar una lista o una tabla,
donde coloca en cada
direcciones (cuando sea elemento, cual es la
base (donde empieza),
cual es el limite (donde
necesario) y a proteger termina) y si esta
ocupada o libre.
unos procesos de los otros. El SO le dice a la CPU
donde es que empieza la
Puedo tener tantas particiones quiera en particion, y el tamaño de
funcion de la memoria que se dispone esta
Particiones Fijas: Asignación
La asignación pude ser con
múltiples colas (asignación
41
determinada por el tamaño (50)
del proceso entrante)
Problemas:
Se desperdicia memoria ya que generalmente se
suele asignarle a un proceso una partición
mucho mas grande que la que necesita, por lo
que si posteriormente viene un proceso que
requiere mas memoria que el que ya esta no se
le va a poder dar asignar una partición apropiada (20)
ya que seguramente habrá un proceso con
menos memoria ocupando la partición, por lo
que no va a poder ejecutarse.
Por ejemplo, el proceso que requiere 41 7
9 5 (10)
unidades entra solo en la partición N, pero si al
proceso que ocupa 9 unidades le asigno esa
partición, el proceso de 41 unidades no podrá
ejecutarse hasta que el otro termine, además de
que estoy desperdiciando mucha memoria. Cola de procesos que esperan una
asignación de memoria con las
unidades que requieren (5 7 9)
FRAGMENTACION INTERNA: Memoria que
sobrante que se obtiene al asignarle a un
proceso una partición. Por ejemplo, la partición
de 50 al asignarle el proceso de 41, la partición
interna seria de 9 (50-41)
Particiones Fijas: Asignación
•Con una única cola
(asignación secuencial o
planificada -en
detrimento de los (50)
trabajos más pequeños-)
(5)
Problemas:
En este caso, la asignación de
memoria es secuencial, osea que el 41 6 7
proceso de 7 va a la partición 1, el 13
de 13 a la 2, el de 6 como no entra (13)
en la de 5, va a la N.
Pero al llegar a la de 41, esta solo
entra en la partición N, por lo que
tendrá que esperar que el proceso 6 (10)
(con una gran fragmentación
interna) termine para poder
asignarle la memoria, trabando o
impidiendo que los procesos
posteriores a el puedan ejecutarse.
Fragmentación Interna
•Es el desperdicio de memoria que se produce al asignar a un
proceso más memoria de la que solicita (por conveniencia o
simplicidad en la asignación)
•Solución: Compactación
oSe ‘funden’ todas los huecos libres para crear un único hueco grande.
oSólo es posible si las direcciones son reubicables dinámicamente
Muy difícil se usa ya que
tendría que recorrer todo el
Reubicación código, identificar en que
lugar hay direcciones y
alterarlas con las nuevas.
•Estática: La asignación de direcciones de memoria puede
realizarse en tiempo de carga (sumando a todas las direcciones la
dirección base de de la partición asignada)
•Dinámica: En en tiempo de ejecución (a través de un registro de
reubicación o reasignación)
A la CPU se le debe Dirección que
decir la base de la aparece en el
partición y la BUS de
conversión se hace direcciones,
en tiempo de es la real.
ejecución
Dirección que
menciona el
programa, es
relativa a este.
El SO carga la dirección de la base (que lo saca de la PCB del
Reubicación proceso) en el registro para que la CPU luego pueda reubicar y del
limite para colocarlo en el "registro limite'' que efectúa la siguiente
comparacion: Si la dirección es mayor al limite, hay un fallo, sino no.
•La protección de memoria se puede realizar utilizando dos registros
(base=reasiganción y límite) que controlan el acceso a la memoria
física. ElSoloSOcarga
no controla que si el proceso sale por fuera de la partición, es la CPU.
la base y el limite en el registro
Reubicación
Particiones Variables
•Otra posibilidad es que los procesos tengan acceso a toda la
memoria, en cuyo caso el planificador decide qué proceso entra en
memoria y el manejador de memoria decide dónde puede ese
proceso ser ubicado.
•El SO crea y mantiene una cola de procesos pendientes para entrar
en memoria, así como una tabla que indica qué partes de la
memoria están ocupadas y que parte están libres.
Particiones Variables
Única partición libre
A medida que entran y salen procesos,
Particiones Variables van quedando huecos/particiones de
tamaño tan chicos que es poco
probable que un proceso entre allí.
(Fragmentación Externa)
Libre Libre Libre Libre Libre
Libre Libre Libre
Libre
Libre
Libre
Fragmentación Externa
La fragmentación externa de la memoria ocurre cuando existen
múltiples huecos ‘pequeños’ no conectados (insuficientes para
contener a un proceso en cola de entrada) que suman un total
que sería suficiente para contener a un proceso en la cola de
entrada
Individualmente
estos huecos no
pueden contener al
proceso P46, pero
si lo sumamos, la
partición total si.
Cada elemento del mapa, representa 1Mb
(otra de lasa formas de manejar las particiones variables) 0: Libre
Mapas de bits 1: Ocupado
Si viene un proceso y necesita 8 Mb, pone en 1
a los primeros 8 0s que encuentra, luego cuando
muere, los vuelve a poner en 0.
La memoria está dividida en unidades de asignación que se
corresponden con un bit en un mapa de bits de la memoria:
Compromiso entre el tamaño del mapa y la optimización de las
asignaciones. VENTAJA: Algoritmo rapido LIBERANDO MEMORIA, ya que la fusion de las particiones
libres es autómatica, ya que los ceros se fusionan con los que ya estaban a s izq y der.
DESVENTAJA: Tiempo de asignacion lento debido a que se debe encontrar una X cantidad de ceros consecutivos
La asignacion de K unidades de
memoria es LENTO porque hay que
buscar K ceros contiguos.
GRANULARIDAD: La cantidad de Mb que representa un bit en el mapa
La liberación de memoria es muy
RAPIDA, solo se ponen en cero los
bits liberados.
Listas Enlazadas
La memoria está representada por una lista enlazada de zonas
de memoria ocupadas (P) y libres (H). Las posiciones de memoria se organizan de forma secuencial
Esta forma organiza la lista en funcion de las posiciones de memoria de cada una de las
particiones.
(H: Hueco)
Listas Enlazadas
La búsqueda de huecos es más rápida, puesto que cada
elemento de la lista contiene el tamaño del mismo
Hay que reorganizar la lista al liberar espacio.
Aqui un proceso muere, por lo que
se genera un hueco y como tengo
tanto un hueco a la der como a la
izq, los funciono
6+5+4
Asignación
•Primer ajuste: Se asigna el primer hueco libre que pueda
contener al proceso entrante. Rápido.
•Siguiente en ajustarse: Igual anterior, pero la búsqueda se
comienza donde se termino la última búsqueda. Ligeramente más
rápido.
•Mejor ajuste: Se asigna el hueco más pequeño que pueda
contener al proceso, una vez recorrida toda la lista. Lento, y
menos eficaz (desperdicia más memoria) que los dos anteriores
por problemas de fragmentación (deja múltiples huecos pequeños
-inutilizables-).
•Peor ajuste: Se asigna el hueco más grande. Lento y poco eficaz
•Ajuste rápido: Mantiene listas de huecos independientes para
tamaños de memoria que se pidan frecuentemente. Agiliza la
asignación pero ralentiza mucho la fusión de huecos.
Necesito 13k, y el primero que encontre
es de 16k, como es el 1ro en el que
entra, se lo asigno, habiendo un
Asignacion en
desperdicio de 3k
este sentido
Tengo que recorrer toda la lista para buscar
el que mejor se ajusta al tamaño del
proceso, en este caso una vez recorrida, se
concluye que el que mejor calza es el de
14K, minimizando el desperdicio de meomria
La busqueda parte en la ultima osicion donde
se asigno memoria. Por ejemplo se la ultima
asignacion se realizao en laparticion d-e,
comoenco a buscar desde ahi, y la 1er
particion donde cabe el proceso, es donde se
realizara la asignacion
Ultima asignacion. Desde aqui se
comienza a buscar la siguiente particion
para el proximo proceso
1ra particion donde
cabe el proceso, se
realiza la asignacion
aqui
Utilizado en Linux para asiganar memoria vrtual
Sistema Compañero/Asociado
Si me dan en un ejercicio un sistema que empieza con 768k libres, tengo que buscar la potencia de 2 mas cercana, que en este caso en
1M, y de ahi empiezo a particionar hasta que entren los 768K, luego determino el tamaño max de proceso
Utiliza particiones de tamaño 2k, con k=1,2,3,...,N.
Sistema de particiones variables, donde la memoria que se le da al
proceso es la potencia de 2 mas cercana al tamaño del proceso.
A este proceso se le asignara 64K, porque la potencia de 2 mas cercana es 2^16=64, siendo el N=16
(1)
(1) El tamaño maximo de proceso que tolera el
sistema compañero en este estado, es de 512K
Sistema Compañero/Asociado
•Si se comienza con un bloque de 2N, entonces habrá N
listas, una por cada tamaño de partición Es decir, si N=20 (1M), habra 20 listas,
una para 2^20, otra para 2^19, otra para
2^18 y asi hasta 2^1.
•Cuando se hace una petición de memoria de tamaño S:
for(i = N; !( 2(i-1) < S 2(i) ); i--)
Divida en 2 particiones compañeras
de tamaño 2(i-1);
asigne una partición compañera de tamaño 2(i-2)
•Dos particiones compañeras se pueden unir cuando
ambas están libres. Aquellas las cuales son adyacentes y
tienen el mismo tamaño, esto hace
que si las dos estan libres se puedan
fusionar, solo si iuna termana en una
posicion par y la otra en impar
Sistema Compañero/Asociado
•Dos Huecos se dicen compañeros y pueden fusionarse
si:
• Ambos tiene el mismo tamaño 2H
• La dirección de comienzo del primer Hueco es (k * 2H+1)
• La dirección de comienzo del primer Hueco es (k * 2H+1) + 2H
Sistema Compañero/Asociado
•Rápida Asignación: basta buscar la partición mas pequeña
suficiente para el proceso.
•Rápida Liberación: Cuando 2 huecos son compañeros difieren
solo en el bit del tamaño de la partición, con lo cual se funden en
un solo hueco del doble de tamaño. Para que 2 particiones sean compañeras, estas deben diferir en
solo 2 bits en su representacion binaria. Pra determinar esto se
utiliza la comparacion XOR.
Esto es para determinar si se pueden fusionar una vez que
amas estan libres
Comparemos 3 particiones
de 256 Kb:
256, 512 y 768. BIT 256K
I ni ci o Represent aci ón Bi nari a
256 K " 01000000000000000000"
512 K " 10000000000000000000"
768 K " 11000000000000000000"
Sistema Compañero/Asociado
http://web.informatik.uni-
bonn.de/I/GeomLab/Online/BS/Speichervergabe/Speichervergabe_built_in.html
Sistema Compañero/Asociado
# ./buddy
B U D D Y S Y S T E M R E Q U I R E M E N T S
* Enter the Size of the memory : 512
M E M O R Y A L L O C A T I O N* Enter the Process size : 44
M E M O R Y A L L O C A T I O N* Enter the Process size : 110
M E M O R Y A L L O C A T I O N* Enter the Process size : 222
M E M O R Y A L L O C A T I O N M A P
512 ---> Divided
256 ---> Divided
128 ---> Divided
64 ---> Allocated 44
64 ---> Free
128 ---> Allocated 110
256 ---> Allocated 222
B U D D Y S Y S T E M
* 1) Locate the process into the Memory
* 2) Remove the process from Memory
* 3) Tree structure for Memory allocation Map
* 4) Exit
