Sistema operativo
Se encarga de controlar todos los recursos del computador y proporcionar el soporte necesario para escribir los programas de aplicación.
Conceptos básicos
La interfaz entre el sistema operativo y los programas de usuario viene definida por el
conjunto de “instrucciones virtuales” que el sistema operativo ofrece. Estas
instrucciones se denomina llamadas al sistema. Las llamadas al sistema cambian entre
los distintos sistemas operativos.
Las llamadas al sistema se clasifican en groso modo en categorías: las que se ocupan de
los procesos y las que se encargan del sistema de ficheros.
Procesos:
Se puede definir un proceso como un programa en ejecución. Consiste
básicamente en un código ejecutable del programa, los datos y la pila del
programa, el contador del programa, el puntero de pila y otros registros, y toda la
información necesaria para ejecutar el programa.
Periódicamente el sistema decide parar la ejecución de un proceso y arrancar la de
otro, a esto se le denomina sistemas en tiempo compartido.
Cuando se suspende temporalmente la ejecución de un programa debe arrancarse
posteriormente el mismo estado en el que se encontraba cuando se paro. Esto
implica que toda la información referente al proceso debe almacenarse
explícitamente en alguna parte durante su suspensión. En muchos sistemas
operativos toda la información relativa a un proceso que no sea el contenido de su
propio espacio de direcciones se almacena en una tabla del sistema operativo
llamada tabla de procesos que se implementa como un vector de registros, con un
elemento por cada proceso que exista en el sistema.
De esta forma un proceso suspendido consta de un espacio de direcciones, añ que
se suele llamar imagen de memoria, y su entrada en la tabla de procesos, que
contiene, ente otras cosas, el valor de sus registros.
Las llamadas mas importantes para la gestión de procesos son las relacionadas con
la creación y terminación de los mismos.
Si un proceso crea varios procesos (llamados procesos hijos ), y estos crean a su
vez mas procesos hijos, se puede llegar fácilmente a la situación del grafico.
Existe otras llamadas al sistema relacionadas con procesos, como por ejemplo
para solicitar mas memoria o devolverla, para esperar la terminación de un
proceso hijo o para sustituir el programa que se esta ejecutando por otro diferente.
Ficheros:
El otro grupo de llamadas al sistema se ocupa de la gestión del sistema de
ficheros. Una de las funciones principales del sistema operativo es la de ocultar
los detalles del funcionamiento del disco y otros dispositivos de E/S, y ofrecer al
programador una abstracción clara y sencilla del ficheros independientes del
dispositivo. Obviamente se necesitan llamadas al sistema para crear ficheros,
borrarlos, leer y escribir en ellos. Dado que antes de empezar a leer un fichero es
necesario abrirlo e igualmente, una vez que se ha terminado de leer del mismo
cerrarlo, existen llamas al sistema para realizar estas operaciones.
Con objeto de proporcionar un lugar donde se puedan guardar ficheros, se ofrece
el concepto de directorio , que permite agrupar varios ficheros. Se precisan
llamadas al sistema que creen y borren directorios, igualmente se necesitan
llamadas que permitan poner en un directorio un fichero ya existente o quitarlo
del mismo. En un directorio se pueden almacenar ficheros como otros directorios.
Las jerarquías de procesos y ficheros poseen ambas una estructura en árbol, pero
este es todo el parecido que se puede encontrar. Las jerarquías de procesos no
suelen tener muchos niveles (es raro encontrar mas de tres), mientras que son
frecuentes las jerarquías de ficheros con cuatro, cinco o mas niveles.
Normalmente solo el proceso padre puede controlar o incluso acceder a un
proceso hijo, mientras que es común la existencia de mecanismos para que un
fichero pueda ser leído por un grupo de usuarios y no solo por su propietario.
Monoprogramación vs Multiprogramación La monoprogramación se usa a veces en computadores pequeños, pero rara vez en los
grandes sistemas con múltiples usuarios. Los motivos de usar multiprogramación son:
• Simplificar la programación de una aplicación al poder disociarla en dos o mas
procesos.
• Otro motivo es que los grandes computadores ofrece a menudo servicio
interactivo a varias personas a la vez, lo que obliga a que sea posible tener
simultáneamente mas de un proceso en memoria principal si se quiere conseguir
prestaciones razonables.
• Otra razón para utilizar multiprogramación en los computadores es que la
mayoría de los procesos emplean un porcentaje apreciable de su tiempo
esperando que terminen operaciones de E/S a disco.
La multiprogramación permite mejorar la utilización del procesador. A grandes rasgos
si un proceso utiliza el procesador un 20%, si tenemos cinco procesos en memoria el
procesador estará ocupado un 100%, suponiendo que los cinco procesos no realizan
operaciones de E/S simultáneamente
Procesos
Definición:
Un proceso es un programa en ejecución que comprende el valor actual del
contador de programa, los registros y de las variables, Conceptualmente ablando
cada proceso tiene su propio procesador virtual.
La idea básica es que los procesos ejecutan actividades diversas. Cada proceso
consta de un programa, su entrada, su salida y su estado. Se puede compartir un
procesador entre varios procesos utilizado un algoritmo de planificación que
decida cuando interrumpir la labor de un proceso y pasar a otro diferente.
Comunicación entre procesos:
Habitualmente se necesita que los procesos se comuniquen entre si a ser posible
con un mecanismo bien estructurado y no por medio de interrupciones. Los
puntos siguientes presentan algunas de las cuestiones y problemas relativos a la
comunicación entre procesos o IPC.
Condiciones de Carrera:
En algunos sistemas operativos, los procesos que cooperan entre si suelen
compartir un área común de la que leen o en la que escriben. Esta puede
estar en memoria o puede ser un fichero compartido. La ubicación de esta
área compartida no cambia el carácter de la comunicación ni sus problemas
asociados.
Estas situaciones en las que dos o mas procesos leen o escriben en un área
compartida y el resultado final depende de los instances de ejecución de
cada uno, se denomina condiciones de carrera.
Secciones criticas:
¿Cómo evitar que se produzcan situaciones de carrera?. El problema se
resuelve igual que en otras situaciones en que se comparte memoria,
ficheros o cualquier otra cosa, sin mas que impedir que haya mas de un
proceso leyendo o escribiendo simultáneamente los datos compartidos.
Dicho de otra forma, lo que necesitamos es exclusión mutua, que no es sino
una forma de garantizar que mientras un proceso este usando un variable o
fichero compartido, los otros procesos no podrán hacerlo.
La parte del programa que accede a la memoria compartida se denomina
sección critica. Si pudiéramos arreglar las cosas de manera que no hubiera
nunca dos procesos dentro de sus secciones criticas, se podrían evitar las
situaciones de carrera.
Una solución apropiada deberá cumplir las cuatro condiciones siguientes:
1.- Que no haya en ningún momento dos procesos dentro de sus respectivas
secciones criticas.
2.- Que no se hagan suposiciones a priori sobre las velocidades relativas de
los procesos o el numero de procesadores disponibles.
3.- Que ningún proceso que este fuera de su sección critica pueda bloquear a
otros.
4.- Que ningún proceso tenga que esperar un intervalo de tiempo
arbitrariamente grande para estar en su sección critica.
Exclusión mutua.
Vamos a ver varios mecanismos para garantizar la exclusión mutua.
1.- Prohibición de las interrupciones
La solución mas sencilla es que cada proceso prohíba todas las
interrupciones justo antes de entrar en su situación critica y las
permita de nuevo antes de salir. Con las interrupciones prohibidas no
se servirá ni la interrupción del reloj ni ninguna otra. Dado que la
asignación del procesador a los diferentes procesos solo cambia como
consecuencia de una interrupción , sea de reloj o de cualquier otra
clase, el prohibir interrupciones hace que no pueda conmutarse el
procesador a otro proceso.
Esta solución no es muy atrayente porque le da a los del usuario la
capacidad de prohibir las interrupciones, y si este programa no las
restaura seria el fin del sistema, y si fuera un sistema multiprocesador
solo pararía el procesador que ha ejecutado la instrucción.
Sin embargo a veces es interesantes que el núcleo prohíba las
interrupciones.
2.- Variables cerrojo:
Intenta una solución software, estableciendo una variable compartida
cuyo valor inicial es 0 poniendo su valor a 1 cuando esta en su sección
critica, comprobando antes su valor y si este es 1 tendrá que esperar
hasta que sea 0.
Este sistema tiene el error garrafal que ya vimos, si un proceso le la
variable y su valor es 0 y cuando va a cambiar su valor, se detiene el
proceso y otro entra en sección critica, al restaurarse el primero
también entraría.
3.- Alternancia estricta:
Consiste en tener una variable entera, turno, con el valor inicial 0, que
lleva la cuenta de a quien le toca el turno de estar en la región critica y
utilizar la memoria compartida. Al principio, el proceso 0 lee turno, ve
que sale 0 y entra en la sección critica. El proceso 1 también ve que
turno vale 0, así que se mete en un bucle donde comprueba
continuamente el valor del turno hasta que valga 1.
Repartir turnos no es muy buena idea si uno de los procesos es mucho
mas lento que el otro.
4.- La solución de Peterson:
El matemático holandés T.Dekker ideo una solución por software que
no requiere una alternancia estricta, pero la solución era demasiado
compleja para implementarla.
En 1981, Peterson descubrió una forma mucho mas simple de
conseguir exclusión mutua.
Antes de utilizar las variables compartidas un proceso llama a
entrar_en_region, pasándole como parámetro el numero de proceso, si
hace falta esta llamada bloqueara el proceso hasta que no hayan
problemas para entrar el al sección critica. Una vez que un proceso
sale de la sección critica, llama a salir_de_region, lo que permite a
otros procesos acceder a las variables comunes.
5.- La instrucción TSL
Veremos ahora un propuesta que requiere un poco de hardware.
Muchos computadores, especialmente los que incorporan varios
procesadores, tienen una misma instrucción que se denomina Test and
Set Lock o TSL; lee en un registro el contenido de la palabra de una
dirección de memoria y carga en esta un valor distinto de cero. El
hardware garantiza que ambas operaciones, i.e., leer el valor de la
palabra y almacenar en la misma, son indivisibles, es decir que ningún
otro procesador puede acceder a la palabra hasta que la instrucción
haya terminado. El procesador que ejecuta la instrucción TSL bloquea
las rutas de la comunicación con la memoria para que ningún otro
procesador pueda acceder a esta hasta que la instrucción haya
terminado.
Dormir y Despertar:
Tanto la solución de peterson como la que emplea al instrucción TSL son
correctas pero adolecen del defecto de tener que utilizar espera activa.
En este método lo que hacemos es utilizar dos primitivas, DORMIR (sleep),
y DESPERTAR (wakeup), de forma que cuando dos procesos necesitan
utilizar un buffer, cuando uno acceda al buffer mandara dormir al otro, y
cuando deje de utilizar el buffer, lo mandara despertar.
Semáforos:
En 1965 a E. W. Dijkstra se le ocurrió utilizar una variable entera para
contar el numero de señales puestas “en conserva” para su uso futuro.
Propuso para ello un nuevo tipo de variable. Llamada semáforo. Esta podría
tener el valor 0, en caso de que no hubiera ningún despertar en conserva, o
algún valor positivo si hubiera uno o mas pendientes.
Dijkstra propuso dos operaciones, BAJAR y SUBIR, que eran
generalizaciones de DORMIR y DESPERTAR, respectivamente. La
operación BAJAR aplicada a un semáforo comprueba que el valor del
mismo; si es mayor que 0 decrementa su valor (consume una de las señales
de despertar en conserva) y continua la ejecución; si el valor del semáforo es
0, el proceso se pone a dormir. Las operaciones de comprobar el valor,
alterarlo y, quizás, ir a dormir se realizan todas como una acción automática,
invisible. Se garantiza que una vez que ha comenzado una operación en un
semáforo, ningún otro proceso podrá acceder al mismo hasta que la
operación haya terminado o se haya bloqueado.
La operación SUBIR incrementa al valor del semáforo correspondiente. Si
hubiera uno o mas procesos dormidos esperando el semáforo, el sistema
escogerá uno y le permitirá acabar la operación de BAJAR. Así después de
una operación de SUBIR sobre un semáforo que tenga procesos durmiendo,
el semáforo todavía valdrá 0, pero habrá un proceso menos durmiendo en el.
Planificación de procesos.
Cuando hay dos o mas procesos listos para ejecución, el sistema deberá decidir
cual se ha de ejecutar primero. La parte del sistema operativo encargada de tomar
esta decisión es le planificador , y el algoritmo que utiliza se llama algoritmo
planificador .
A la hora de juzgar si un algoritmo planificador e bueno, se pueden aplicar varios
conceptos:
1.- Equidad: Que se asigne el procesador a cada proceso de forma equitativa.
2.- Eficiencia: Que se mantenga ocupado el procesador el 100 por cien del tiempo.
3.- Tiempo de respuesta: Que se minimice el tiempo de respuesta para usuarios
interactivos.
4.- Tiempo de proceso global: Que se minimice el tiempo que han de esperar para
poder obtener resultados.
5.- Rendimiento: Que se maximice el numero de trabajos procesados en cada
unidad de tiempo.
Para asegurarse de que ningún proceso monopoliza el procesador durante mucho
tiempo, casi todos los ordenadores tienen un temporizador hardware, o reloj que
produce interrupciones periódicas. Este suele tener una frecuencia de 60 ciclos por
segundo o Hz. Con cada interrupción el sistema operativo recupera el control y
decide si debe dejar que el proceso actual continué ejecutándose, o si, por el
contrario, este ya ha utilizado el procesador durante un tiempo suficientemente
lago y, por tanto, es el momento de suspender su ejecución y ceder el uso del
procesador a otro proceso.
Este mecanismo de suspensión de la ejecución de procesos que lógicamente
podrían seguir ejecutándose se llama planificación expulsiva, a diferencia del
método de ejecución hasta terminación.
1.- Planificación por turno rotatorio.
Uno de los algoritmos mas veteranos, sencillos, equitativos y ampliamente
utilizándose el algoritmo del turno rotatorio. A cada proceso se le asigna un
intervalo de tiempo llamado su cuanto durante el cual puede ejecutarse. Si
el proceso todavía esta ejecutándose al final del cuanto, se le expulsa del
procesador, que se concede a otro proceso. Por supuesto si antes de que
expire el cuanto el proceso ya esta bloqueado o ha terminado, el procesador
se conmuta en el momento del bloqueo.
La conmutación entre procesos lleva algo de tiempo porque deben realizarse
varias funciones, como cargar y salvar los registros y mapas de memoria,
actualizar las diversas tablas y listas, etc. A este proceso se le llama cambio
de proceso o cambio de contexto.
2.- Planificación por prioridad.
La planificación por prioridad deriva de que no todos los procesos tienen la
misma importancia. La idea básica es asignar a una prioridad, de forma que
siempre se concede el procesador al proceso con prioridad mas alta.
Para evitar que los procesos de mas alta prioridad se ejecuten por tiempo
indefinido, el planificador puede decrementar la prioridad del proceso que
se esta ejecutándose en cada momento con cada pulso del reloj. Cuando su
prioridad llegue a ser menor que la del proceso que le sigue, se realizar un
cambio de proceso.
3.- Listas de espera múltiples.
Dado que los primeros ordenadores (7094) no podían almacenas mas de un
proceso en memoria y debían de transferir los datos a disco y este proceso
era muy lento, los diseñadores se dieron cuenta que para reducir el numero
de transferencias, era mas eficiente dar pocas veces cuantos mayores a los
procesos con mucho calculo, que darles muchas veces cuantos pequeños.
Por otro lado ya hemos visto que darle a todos los procesos cuantos grandes
se empobrece el tiempo de respuesta. La solución adoptada consistió en
establecer diversas categorías de prioridad. Los procesos en categoría
superior se ejecutaran durante un cuanto. Los procesos de la siguiente
categoría se ejecutaran durante dos cuantos, los de la siguiente durante
cuatro, y así sucesivamente. Cada vez que un proceso consumía los cuantos
que le correspondían se pasaba a la categoría inmediatamente inferior.
4.- Prioridad al mas corto.
En este sistema se conoce el tiempo de ejecución de antemano, de manera
que a la hora de establecer que proceso se ejecutara primero se le concede
prioridad al mas corto de esa forma ordenaremos los procesos a ejecutar por
tiempo de ejecución.
La planificación por prioridad al mas corto solo es optima cuando todos los
procesos están disponibles a la vez.
5.- Planificación determinada por el comportamiento.
Un enfoque totalmente distinto para abordar el problema es hacer promesas
al usuario sobre las prestaciones que dará el sistema y después tratar de
cumplirlas. Una promesa fácil de cumplir es: si hay n usuarios utilizando un
sistema, cada uno recibirá aproximadamente 1/n de la potencia del
procesador.
Para poder cumplir esta promesa el sistema debe llevar la cuenta del tiempo
de procesador consumido por todos los procesos de un usuario desde que
entro al sistema y el tiempo que lleva este en el sistema. Después calcular la
cantidad de tiempo de procesador que cada usuario tiene derecho a
consumir, que es igual al tiempo transcurrido desde que le usuario entro al
sistema dividido por n. Dado que el sistema lleva al cuenta del procesador
consumido, es relativamente sencillo calcular el cociente entre el tiempo de
procesador consumido y el tiempo de procesador que tiene derecho.
El algoritmo consistirá entonces en ejecutar el proceso que tuviera este
cociente mas bajo.
6.- Planificación a dos niveles.
Cuando no hay espacio suficiente en memoria para almacenar todos los
procesos es necesario almacenar parte de ellos en el disco, siendo entonces
necesario un tiempo mucho mayor para cargar estos.
Una forma de planificar la ejecución de los procesos que residan en el disco
es el empleo de un planificador de dos niveles. Para ello se carga primero en
memoria un subconjunto determinado de los procesos ejecutables. Durante
un intervalo de tiempo, el planificador seleccionara únicamente los procesos
de este subconjunto. Periódicamente se invocara a un planificador de nivel
superior, que saca de memoria los procesos que llevan mas tiempo allí y
carga nuevos procesos que llevan mucho tiempo en disco. Una vez realizado
el cambio el planificador de bajo nivel continuara realizando su selección
entre los procesos que se encuentran cargados en memoria.
Gestión de la memoria
La parte del sistema operativo encargado de la memoria se llama gestor de memoria,
Para poder asignar memoria a los procesos y recuperarla cuando estos terminan, el
gestor de memoria debe llevar la cuenta de que las partes de la misma se están usando y
cuales no. Esto también es necesario para gestionar el intercambio entre el disco y la
memoria cuando esta no es suficientemente grande para mantener todos los procesos.
Gestión de la memoria.
Los sistemas de gestión de memoria se pueden dividir en dos clases: los que
durante la ejecución intercambian procesos entre la memoria principal y el disco,
y los que no. Dado que estos últimos son los mas sencillos empezaremos por
ellos.
Monoprogramación:
El método mas sencillo de gestión de memoria consiste en tener, en cada
instante un solo proceso en memoria principal al que se le permite utilizar la
memoria completa. El usuario carga desde un disco un programa que ocupa
toda la memoria y toma el control de la maquina. Aunque este método se
utilizo comúnmente hasta 1960, ya no se emplea ni siquiera en
computadores personales, principalmente porque obliga a que cada proceso
contenga un manejador de dispositivo por cada dispositivo de E/S que
utilice.
Programa
de
Usuario
SSOO en RAM
Estas son las técnicas mas empleadas en microcomputadores, la memoria se
divide en un solo proceso de usuario. El sistema operativo podría situarse al
principio de la memoria RAM o bien podría estar en ROM al final de la
memoria. Se presenta otra posibilidad, tener los manejadores de los
dispositivos en ROM, al final de la memoria, y el resto del sistema operativo
en RAM al principio de la memoria. El IBM PC, por ejemplo, utiliza el
tercero, estando situada la ROM de los manejadores de dispositivos en el
bloque de 8 Kbs. Superiores del espacio de direcciones de 1 Mbs. Este
programa en la ROM se llama BIOS (Basic Input Output System, Sistema
básico de E/S).
El uso de esta estructura obliga a ejecutar los programas de uno en uno. El
usuario teclea un comando en el terminal y el sistema operativo carga en
memoria el programa correspondiente del disco y lo ejecuta. Cuando el
proceso termina, el sistema operativo escribe un carácter de atención en el
terminal y se queda a la espera de que el usuario teclee otro comando para
cargar otro procesó encima del primero.
Multiprogramación con particiones fijas.
La forma mas sencilla de organizar la memoria para compartirla entre varios
procesos consiste simplemente en dividirlas en n particiones, quizás de
SSOO en ROM
Programa
de
Usuario
Manejadores Disp. En ROM
Programas de
Usuario
SSOO en RAM
tamaños diferentes. La división la puede realizar manualmente la el
operador al arrancar el sistema.
El sistema puede dejar los trabajos que vayan llegando en la cola de entrada
da la partición mas pequeña en la que quepan. Al ser particiones de tamaño
fijo, el espacio que no use el trabajo cargado en una partición se desperdicia.
El problema de tener que ordenar los trabajos de entrada en colas separadas
se ve claramente cuando se llega a tener vacía la cola de una partición
grande, estando llena la cola de una partición pequeña. Como alternativa se
puede tener una sola cola.
Para minimizar el espacio desperdiciado al cargar un trabajo pequeño en una
partición grande, se puede realizar una búsqueda en toda la cola de entrada y
escoger el trabajo de mayor tamaño que quepa en una partición recién
desocupada.
Reubicación y protección.
La multiprogramación introduce dos problemas esenciales que se han de
resolver: la reubicación y protección, de lo planteado anteriormente se
deduce que los trabajos se ejecutan en direcciones diferentes. El montador
de enlaces (encargado de combinar en un solo espacio de direcciones el
programa principal, los procedimientos escritos por el usuario y los
procedimiento de biblioteca) debe saber la dirección de comienzo del
programa en memoria.
Por ejemplo supongamos que la primera instrucción es una llamada a un
procedimiento con dirección relativa 100 dentro del fichero ejecutable
producido por el montador. Si el programa se carga en la partición 1, esa
instrucción saltaría a la dirección absoluta 100, que esta dentro del sistema
operativo. Lo que en realidad se necesita es una llamada a la dirección 100K
+ 100. Si el programa se carga en la partición 2 la instrucción debería ser
una llamada a la dirección 200K + 100, y así sucesivamente, este
mecanismo se conoce como reubicación.
Una posible solución consiste en modificar las instrucciones en el momento
de cargar el programa en memoria, a las direcciones de los programas
cargados en la partición 1 se les sumara 100K, a los programas de la
partición 2 se les sumara 200K, y así sucesivamente.
La reubicación en el momento de la carga no soluciona el problema de la
protección . los programas malintencionados pueden siempre generar una
nueva instrucción, saltar a ella y ejecutarla. Debido a que los programas en
los sistemas emplean direcciones de memoria absolutas en vez de relativas a
un registro, no hay manera de impedir que un programa forme una
instrucción capaz de leer o escribir en cualquier palabra de memoria.
La solución elegida por IBM para proteger la memoria del 360 fue dividirla
en bloques de 2Kb. y asignar un código de protección de 4 bits a cada
bloque. La palabra de estado contenía una clave de 4 bits. El hardware del
360 capturaba cualquier intento de un proceso de acceder a memoria cuyo
código de protección fuera diferente a al palabra clave en la palabra de
estado. Dado que solo el sistema operativo podía cambiar los códigos de
protección y la clave, se imposibilitaba que los procesos de usuario
interfieran unos con otros o con el propio sistema operativo.
Intercambio.
En los sistemas de tiempo compartido suele haber mas usuarios que memoria para
todos sus procesos, así que se han de mantener en el disco los procesos que no
quepan. Desde luego para ejecutar estos procesos se han de cargar en memoria.
Esta operación de mover procesos entre la memoria principal y el disco se le
llama intercambio (swapping).
Multiprogramación con particiones variables.
En teoría, un sistema con intercambio podría basarse en particiones fijas.
Cada vez que se bloquease un proceso, se podría mandar a disco y cargar en
la partición del primero a otro proceso desde el disco. En la practica, las
particiones fijas no resultan muy interesantes en sistemas con escasa
memoria, porque malgasta mucha de esa memoria con programas que son
menores que las particiones donde residen. Por esta razón se utilizan
algoritmos de gestión de la memoria distinto, conocido como de particiones
variables
Cuando se usan particiones variables, el numero y el tamaño de los procesos
varían dinámicamente durante el funcionamiento del sistema.
La diferencia principal entre las particiones fijas y las particiones variables
es que en este ultimo caso, el numero, tamaño y posición de las particiones
varían dinámicamente al entrar y salir procesos de la memoria, mientras que
en el primer caso son fijos. La flexibilidad que da el no tener particiones de
tamaño fijo, que pueden ser demasiado grandes o demasiado pequeñas,
mejora la utilización de la memoria, pero también complica la asignación y
desocupación de la misma, y el seguimiento del estado en que se encuentra.
Se pueden reunir todos los huecos libres de la memoria en uno solo si se
mueven los procesos todo lo que se pueda a las posiciones inferiores, esta
técnica se denomina compactación de la memoria.
Memoria virtual.
Su idea básica es permitir que le tamaño conjunto del programa, sus datos y su pila
puedan ser mayor que la cantidad de memoria física disponible. El sistema operativo
dejara en memoria principal las partes del programa que se están usando, y el resto lo
tiene en disco.
Paginación
La mayoría de los sistemas que utilizan memoria virtual emplean una técnica
llamada paginación, que consiste en: En todo computador hay un conjunto de
direcciones de memoria que los programas pueden generar. Cuando un programa
usa una instrucción como MOVE REG, 1000, esta moviendo el contenido de la
dirección de memoria 1000 a REG (o viceversa dependiendo del computador).
Las direcciones generadas por los programas se llaman direcciones virtuales, y
forman el espacio de direcciones virtuales. En los computadores sin memoria
virtual, las direcciones virtuales se mandan directamente a la ruta (bus) de
direcciones de memoria, de manera que acaba accediendo a la posición de
memoria física que tiene la misma dirección. Si hay memoria virtual, las
direcciones no se mandan directamente a la ruta de direcciones de memoria, sino a
una unidad de gestión de memoria virtual o MMU, que es un dispositivo, o un
conjunto de dispositivos, que se encargan de traducir dinámicamente las
direcciones de virtuales a direcciones físicas,
Procesador
Memoria
Controlador De
Disco
Unidad de gestión de memoria
Bus
El espacio de direcciones virtuales se divide en unidades llamadas paginas. Las
unidades correspondientes en la memoria física se llaman marcos de pagina. Las
paginas y los marcos de paginas tienen idéntico tamaño.
Cuando el programa intenta acceder a una dirección de memoria virtual, el MMU
lo redirección al marco de pagina que le corresponde, si el programa intenta
acceder a una dirección virtual sin correspondencia, se produce un fallo de pagina
trap. El sistema seleccionará un marco de pagina que se haya usado poco y
escribe su contenido en el disco. A continuación, se carga la pagina que se acaba
de necesitar en este marco de pagina, cambia la tabla de traducción y ejecuta de
nuevo la instrucción interrumpida.
Segmentación. La paginación es una técnica que permite implementar un gran espacio lineal de
disposiciones en una memoria física de tamaño reducido. En la mayoría de las
aplicaciones es mas adecuado tener un espacio de direcciones bidimensional.
La idea de la memoria segmentada ha vivido hasta nuestros días. Se puede
encontrar en forma muy simplificada en muchos microcomputadores basados en
68000. las implementaciones típicas admiten en el hardware hasta 16 procesos,
cada uno con 1024 paginas de 2K o 4K. Limitándonos a paginas de 4K para este
ejemplo cada proceso tendría un espacio de direcciones virtual de 4M, formado
por 1024 paginas de 4K.
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5
Pagina Virtual
Marco de pagina
Este esquema se podría implementar dotando a cada proceso de su propia tabla
de paginas que contuviera 1024 números de marco de paginas, Sin embargo, no
se suele hacer así sino que el hardware de la MMU contiene una tabla dividida
en 16 partes, correspondientes a 16 procesos. Cada parte tiene 64 descriptores de
segmento, de forma que el espacio de direcciones de 4M de cada proceso se
divide en un máximo de 64 segmentos con 16 paginas cada uno. Cada descriptor
de segmento contiene la longitud del segmento (de 0 a 16 paginas); los bits de
protección, que indican si el segmento se puede leer y/o escribir; y un puntero a
la tabla de paginas. Esta tiene 16 elementos, cada uno de los cuales apunta a un
marco de pagina en memoria.
Al arrancar un proceso el sistema operativo carga un numero de proceso de 4
bits en un registro hardware especial. Cada vez que un proceso hace una
referencia a memoria la MMU traduce la dirección virtual de la siguiente forma:
los 4 bits del numero de proceso y los 6 bits superiores de la dirección virtual de
22 bits (necesarios para direccionar 4M) forma un numero de 10 bits con el que
indexa al tabla de segmentos para encontrar el descriptor de segmento
apropiado. A continuación comprueba los bits de protección en el descriptor del
segmento para ver si esta permitido el tipo de acceso solicitado. En caso
afirmativo, la MMU se asegura de que el segmento tiene tamaño suficiente
comprobando el numero de pagina extraído de la dirección virtual con el campo
longitud del segmento contenido en el descriptor del mismo. Si es así, el numero
de pagina se usa como índice en la tabla de paginas, cuya dirección se obtiene
del descriptor del segmento. Una vez obtenido el numero de marco de pagina, se
combina con el campo de posición en la pagina de la dirección virtual, con lo
que se forma la dirección física, usada para direccional la memoria.
Una de las ventajas de este diseño es que cuando el sistema operativo hace un
cambio de proceso, todo lo que necesita es cambiar el registro de numero de
proceso de 4 bits.
Algoritmos de sustitución de las paginas.
Cuando sucede un fallo de pagina, el sistema operativo ha de escoger la pagina
que debe sacar de memoria para hacer sitio a la que se necesita. Si la que ha de
sacarse ha sido modificada, la copia en el disco debe actualizarse.
Aunque seria posible escoger una pagina al azar, seria conveniente escoger una
pagina que no se utilice con frecuencia.
Sustitución optima de paginas.
El mejor algoritmo posible de sustitución de paginas es fácil de describir,
pero imposible de implementar. Funciona de la siguiente manera: cuando
sucede un fallo de pagina, residen en memoria un conjunto de paginas. Hay
una pagina a la que se hará referencia en al siguiente instrucción. Otras
paginas se podrán necesitar 10, 100 o quizás 1000 instrucciones mas
adelante. Se pueden etiquetar cada pagina con un numero igual al de las
instrucciones que quedan por ejecutarse antes de que se haga referencia a
esa pagina.
El algoritmo de sustitución optimo seria el que sustituyera la pagina de
etiqueta mayor. Si hay una pagina que no se va ha usar hasta dentro de 8
millones de instrucciones y otra a la que no se hará referencia hasta dentro
de 6 millones de instrucciones, sustituir la primera retardara lo mas posible
el fallo de pagina que hará volver a dicha pagina a memoria.
El único problema es que este algoritmo es imposible, ya que el sistema es
incapaz de saber cual serán las siguientes paginas a las que se harán
referencia.
Sustitución de la pagina no usada recientemente ( MRU ).
Para que el sistema operativo pueda recoger los datos estadísticos de cuales
se han utilizado recientemente y cuales no, se tiene dos bits asociados a cada
pagina: el primero es el bit R, el cual pone a 1 el ordenador cada vez que se
lee o se escribe en la pagina, el segundo es el M, que se pone a 1 cada vez
que se escribe algo. Con lo que se construye la siguiente clasificación.
Grupo 0: no referenciada, no modificada.
Grupo 1: no referenciada, modificada.
Grupo 2: referenciada, no modificada.
Grupo 3: referenciada, modificada.
Aunque el grupo 1 parezca imposible, puede presentarse cuando una
interrupción del reloj pone a 0 el bit R de una pagina del grupo 3. Las
interrupciones no ponen M a 0 para saber que se ha de grabar en disco.
El algoritmo escogerá una pagina del grupo 1 al azar, o en su ausencia del
grupo mas bajo que este disponible.
Sustitución de paginas primera en entrar primera en salir ( FIFO ).
El algoritmo de paginación que requiere poco procesamiento es el de
primera en entrar, primera en salir, o FIFO , el sistema operativo tiene
una lista de todas las paginas que hay en memoria, estando a la cabeza de la
lista la pagina que lleva mas tiempo, y al final la pagina que acaba de entrar.
Al producirse un fallo de pagina se quitara la que este a la cabeza de la lista,
y se añade la nueva al final.
Sustitución de la pagina usada hace mas tiempo ( LRU ).
Existe una buena aproximación al algoritmo optimo, que se basa en la
observación de que paginas que se han utilizado mucho en las ultimas
instrucciones se usaran probablemente mucho en las siguientes.
Recíprocamente, las paginas que no se han usado en las ultimas
instrucciones es probable que permanezcan largo tiempo sin ser utilizadas.
Aunque LRU sea teóricamente realizable su implementación es costosa, por
lo que es necesario tener una lista enlazada de todas las paginas en memoria,
con la que se haya utilizado mas recientemente al principio y la que lleva
mas tiempo sin utilizarse al final. El problema es que esta lista ha de
actualizarse por cada referencia a memoria.