Conceptos sobre almacenamiento.

• Los procesos necesitan espacio para el código asociado

• Los procesos realizan operaciones de E/S que hacen uso de buffers

MEMORIA:

• Soporte para retener información, sujeta a posibles recuperaciones

• Se divide en un conjunto finito de elementos, denominados posiciones, que pueden agruparse o no para su direccionamiento

• Hay distintos tipos de memoria, en función de distintos parámetros:

• Velocidad de acceso

• Capacidad de almacenamiento

• Coste

1.1. JERARQUÍA DE MEMORIA:

Para lograr un buen rendimiento, se organizan los distintos tipos de memoria de forma jerárquica:

1.2. OBJETIVO DEL GESTOR DE MEMORIA:

• Controlar la jerarquía como si fuera un todo

• Se basa en un esquema de almacenamiento

Esquema de almacenamiento:

Organización de la Memoria

+

Gestión de Memoria

1.2.1.Organización de la Memoria:

• La Organización de la memoria, implica cierto soporte Hardware

• Es el CÓMO de percibe la memoria:

• Si se trata de una memoria en la que puede haber uno o varios programas

• Si los bloques de memoria son fijos o cambian con el tiempo

• Si existe posibilidad de reubicar programas

• ...

ORGANIZACIONES POSIBLES:

Sistemas de Memoria Real:

• Sistemas Dedicados: Un solo usuario

• Sistemas Multiprogramados:

• Sistemas con Particiones Fijas: REGIONES

• Absolutas

• Reubicantes

• Sistemas con Particiones Variables

Sistemas de Memoria Virtual: Sistemas Multiprogramados

• Segmentados

• Paginados

• Combinados

1.2.2. Gestión de la Memoria:

• Se hace por Software y por Hardware

• Es un conjunto de estrategias aplicado sobre una organización de memoria para aumentar su rendimiento

1.2.2.1 ESTRATEGIAS FETCH o DE BÚSQUEDA:

Determinan cuándo coger un bloque de código o datos para pasarlo a Memoria Principal.

Hay dos tipos:

Búsqueda por demanda:

• Se localiza y se pasa un bloque a memoria cuando la UCP lo pide o referencia

• Es poco efectiva, porque la UCP espera

Búsqueda por demanda anticipada:

• Se lleva a memoria más bloques de los referenciados (los contiguos)

• Se persigue que estén en memoria para cuando sean refernciados

• Es muy costoso, pero aumenta el rendimiento

ESTRATEGIAS DE UBICACIÓN o GESTIÓN DEL ESPACIO LIBRE:

Estudia dónde situar en memoria, el siguiente bloque de programa o datos

Hay tres tipos:

Estrategias de gestión de huecos de tamaño fijo: BUDDY SYSTEMS

Estrategias de encadenamiento de zonas libres:

• BEST FIT

• FIRST FIT

• WORST FIT

Estrategias de zonas de magnitudes predefinidas

En los distintos niveles de la jerarquía, suele haber distintas estrategias de ubicación.

ESTRATEGIAS DE REEMPLAZAMIENTO:

Determinan qué bloque de los que hay en memoria (cuando ésta está llena) debe reemplazarse por uno nuevo.

Algoritmos que se utilizan:

• FIFO

• ÓPTIMO

• LRU

• LFU

• MRU

• MFU

Sistemas dedicados a un usuario.

La Memoria Principal, se divide en dos:

• Una parte para el Sistema Operativo

• Otra parte para el usuario

Generalmente, la zona del Sistema Operativo, se suele encontrar a partir de las posiciones más bajas, pero en algunos Sistemas Operativos, se suele encontrar a partir de la más alta. Depende de qué posiciones de memoria están reservadas para el vector de interrupciones.

La parte del Sistema Operativo se puede encontrar a su vez, dividida en otras dos partes:

• Parte Residente: SIEMPRE debe estar en Memoria

• Zona de Rutinas Transitorias

Como el Sistema Operativo ya ocupa un cierto espacio, y si se añade algo (drivers, ...) al sistema, se debería modificar el límite de zonas de memoria ocupadas.

Para todas aquellas rutinas del Sistema Operativo que se usan habitualmente, se diseñó la parte RESIDENTE.

El resto, en lugar de guardarlas en memoria, están aparte, en memoria auxiliar, que se cargará la rutina del servicio y en el momento en el que necesita el servicio correspondiente, en el momento en que se pide, el Sistema Operativo se encargará de cargar la rutina en la posición correspondiente.

En estos sistemas, por cada dirección generada durante la ejecución de un proceso de usuario, se tiene que comprobar si es correcta o no.

El Sistema Operativo no tiene restricciones de acceso a ninguna parte de la memoria, pero los procesos de usuario sí tienen.

La dirección será válida, si la posición de memoria referenciada, está en la Zona de Usuario. La comprobación, se puede hacer por Hardware o por Software, aunque si la hacemos por Software, el rendimiento baja mucho, y por eso:

! LA PROTECCIÓN DE MEMORIA SIEMPRE SE HACE POR HARDWARE

Se necesitará un registro máquina, conocido como: REGISTRO FENCE

(frontera, barrera)

Este registro, contendrá la dirección de la zona de usuario. Mediante una instrucción reservada del Sistema Operativo, se podrá modificar el contenido del registro FENCE.

Un proceso de usuario, al ejecutarse, va generando direcciones. La dirección generada, se compara con el contenido del registro FENCE (dirección de protección), y con esa comprobación, se decide si se permite el acceso a memoria o hay error.

En caso de ERROR lo que se hace es:

• Llamar al Hardware d interrupciones

• Matar el proceso

• Volcar la memoria

Cuando codificamos un programa, su inicio es la dirección 0. Si se pone el programa en memoria, no se puede poner la dirección 0, porque ahí está el Sistema Operativo. Hay que realizar una operación de BIND. Es decir, hay que establecer la correspondencia entre instrucciones y datos y direcciones de Memoria Principal. Esta operación, la BIND, se puede hacer:

• En tiempo de Compilación

• En tiempo de Carga

• En tiempo de Ejecución

• Si se realiza la BIND en compilación, y se modifica el contenido del registro FENCE, habrá que volver a compilar todos los programas

• Cuanto más tarde se haga la operación BIND, mayor flexibilidad.

• Si se realiza la BIND en tiempo de ejecución, las direcciones generadas, son, en un principio lógicas, por lo que hay que convertirlas en direcciones físicas, sumándoles el contenido del registro FENCE o registro BASE, cuyo contenido se denomina DIRECCIÓN BASE.

Si se realiza la BIND en tiempo de ejecución, el gráfico quedaría de la siguiente manera:

Para aumentar el rendimiento en los Sistemas Monoprogramados, se utilizan los Sistemas con Intercambio o Swapping.

Sistemas con intercambio o SWAPPING.

En estos sistemas, se trata de conmutar la memoria entre diferentes procesos.

A cada proceso se le asigna una cantidad de tiempo de utilización del sistema, en concreto, de la memoria. A este tiempo se le denomina QUANTUM.

Cuando se le acaba el tiempo de utilización de la memoria, su imagen se vuelca sobre memoria auxiliar.

Luego, habrá que elegir otro proceso al que dar paso y cargar su imagen en Memoria Principal.

• Se necesita un DAAD (Dispositivo de Acceso Directo) con capacidad suficiente como para contener todas las imágenes de memoria de todos nuestros procesos.

• El Sistema Operativo, tendrá una lista de todas las imágenes de los procesos de usuario que tiene en memoria auxiliar, junto con su dirección en ella.

• Conmutar la memoria, implica como mínimo, dos operaciones de E/S, lo que conlleva TIEMPO.

EJERCICIO:

Sea un DAAD con tiempo de acceso de 8 msg

Un Ratio de transferencia de 250 Kw/sg

Para transferir 20 KW, calcularr el TIEMPO DE SWAPPING

250 Kw ! 1 sg

20 Kw ! x sg

Tiempo_SWAP-OUT = 8msg +

Tiempo_SWAP-IN = Tiempo_SWAP-OUT = 88 msg

TIEMPO DE SWAPPING = 176 MSG

• El tiempo de asignación del procesador a cada proceso (QUANTUM), debe ser bastante mayor que el tiempo de SWAPPING

Problema:

• El tiempo invertido en el swapping es elevado

Soluciones:

2.1. SOLUCIÓN HARDWARE:

Consiste en utilizar dispositivos de Swapping:

• Más rápidos

• Con menor tiempo de acceso

• Con mayores ratios de transferencia

EJEMPLO:

- TSS Q-32

! Tiempo de Acceso = 10msg

! Ratio de Transferencia = 363.000 w/s

! Tiempo de SWAP-IN = Tiempo de SWAP-OUT = 130'2 sg

- ECS

! Tiempo de Acceso = 3 sg

! Ratio de Transferencia = 10.000.000 w/s

! Tiempo de SWAP-IN = Tiempo de SWAP-OUT = 4.006 sg

2.2. SOLUCIÓN NO HARDWARE:

2.2.1.Transferir la zona ocupada de la Zona de Usuario:

Consiste en, en vez de transferir toda la zona de usuario, transferir sólo la zona ocupada.

Para ello, el Sistema Operativo debe conocer la cantidad de memoria que usa cada proceso.

2.2.2. SWAPPING con Solapamiento:

Solapan las operaciones de swapping con la ejecución de instrucciones por parte de la UCP.

La zona de memoria ocupada por el Sistema Operativo, se extiende para poder albergar también dos imágenes de proceso de usuario.

FUNCIONAMIENTO:

Ejecución del proceso 1

! Proceso 1 en Zona de Usuario

Mientras tanto, se carga mediante Swapping, la imagen de otro proceso de usuario en uno de los buffers

Al acabar el Quantum del proceso 1, su imagen de memoria pasa al otro buffer, y la imagen del proceso recientemente transferido al primer buffer, se pasa a la Zona de Usuario

Ejecución de este nuevo proceso

Mientras se ejecuta el nuevo proceso, se realiza el SWAP-OUT del proceso que se acaba de retirar de Zona de Usuario, y se lleva a cabo también, el SWAP-IN de un nuevo proceso

Problema:

• Si un proceso solicita un servicio al Sistema Operativo, se le acaba el Quantum, y se le saca de memoria antes de que se atienda su petición: ¿Qué se hace con lo que ha pedido cuando se le atienda?

Soluciones:

• No conmutar la memoria hasta no haberse completado los servicios pedidos por el proceso que la ocupa

• Definir en la zona de memoria del Sistema Operativo, unos buffers especiales para depositar el resultado de las peticiones.

Cuando el proceso vuelve a memoria, se le pasan esos datos

! Se complica el Sistema Operativo

3.Sistemas Multiprogramados o

Sistemas con Multiprogramación.

Los problemas del Swapping, se resolverían si no hubiera que sacar de memoria las imágenes de los procesos.

La solución, pasa por tener en la Zona de Usuario varios procesos:

• Se define una Zona para el Sistema Operativo, y también se define una Zona de Ususario dividida en bloques, de manera que en cada bloque puede haber un programa de usuario

Nivel de Multiprogramación: Es el número máximo de programas de usuario que

puede haber en la Zona de Usuario, que será igual al número de bloques en que se divide la Zona de Usuario.

• A estos sistemas, se les puede añadir SWAPPING

Hay dos tipos de Sistemas Multiprogramados:

MFT

MVT

SISTEMAS MFT:

• Multiprogramación com número fijo de tareas

La Zona de Usuario, se divide en regiones, que por definición, no varían: Número Fijo de Regiones. Es decir, al generar el Sistema Operativo, al arrancar la máquina, se define el número y tamaño de las regiones. Esto permanece invariante hasta que se vuelva a generar el Sistema Operativo.

SISTEMAS MVT:

• Multiprogramación con un número variables de tareas

Estos sistemas, se caracterizan porque las particiones de la Zona de Usuario varían dinámicamente ! Se asigna Memoria según van llegandolos procesos

En todos los Sistemas Multiprogramados, hay que prestar especial atención a la Protección de Memoria.

Protección de Memoria: Hay que proteger el Sistema Operativo y cada fragmento, es

decir, cada proceso de usuario sólo debe poder acceder a la zona dememoria que tiene asignada.

Solución:

1. REGISTROS LÍMITE: Los Registros Límite son tres:

Registros de Zona Activa: Indica el número de región, partición o fragmento en

que está cargado el programa del proceso en curso

Sólo se usa en MFT (por lo que hablaremos de

regiones en vez de particiones o fragmentos), y no

siempre. No tiene sentido cuando las particiones son

dinámicas.

Registro Límite Superior: Registro que contiene la dirección límite superior de

esa región o partición

Registro Límite Inferior: Registro que contiene la dirección límite inferior de

esa región o partición

Circuito de Protección de Memoria con Registros Límite:

• R.L.I Y R.L.S. son valores de cada proceso

• El contenido de los tres registros, (R.L.I., R.L.D. Y Registro de ZONA ACTIVA si lo hay) es información propia del proceso que se está ejecutando

Esta información, (el contenido de los tres registros), se guarda en el PCB:

• El valor del Registro de Zona Activa, cuando existe: Existe una tabla en el Sistema Operativo, que permite obtener las direcciones de límite de cada zona a partir de su identificativo

ó

• La dirección de comienzo y fin de la memoria asignada a ese proceso

FUNCIONAMIENTO:

Cuando el Dispatcher cede el control del procesador a un proceso, vuelca la información de su PCB en los registros máquina, de manera que si el PCB tiene el identificativo de Zona Activa, lo vuelca sobre el registro correspondiente. A partir de ese dato, calcula los valores de los registros Límite (Superior e Inferior), y los vuelca sobre ellos.

Si el PCB ya tiene el contenido de los registros Límite, el Dispatcher lo vuelca sobre los registros correspondientes.

Problema:

• Sólo funciona cuando la ubicación es estática

2. REGISTROS DE BASE Y LÍMITE:

Se usa cuando la reubicación es dinámica.

• El Registro BASE, es la dirección de comienzao de la zona de memoria asignada al proceso: R.L.I.

• El Registro LÍMITE, es el resultado de:

DIRECCIÓN LÍMITE SUPERIOR - DIRECCIÓN LÍMITE INFERIOR

Circuito de Protección de Memoria con Registros Base y Límite:

3.1. SISTEMAS MFT:

• La Zona de Usuario se divide en bloques de tamaño fijo, que vamos a llamar REGIONES

• Todas las regiones no tienen por qué tener el mismo tamaño

• La dirección de la Zona de Usuario se hace en tiempo de generación del sistema, y permanece hasta que se regenere

• En cada región sólo puede haber un programa d usuario

• Cuando se somete un trabajo a ejecución, el Planificador de Alto Nivel, es decir, el Gestor de Trabajos, trata de asignar memoria al programa correspondiente al paso de trabajo indicado

Si puede ubicarlo, le pide al cargador que lo cargue en la región designada

Una vez que se ha cargado el programa en memoria, se crea el proceso correspondiente (estado READY)

UBICAR = ASIGNAR

¿CÓMO SE HACE LA ASIGNACIÓN DE MEMORIA?

Para hacer la asignación de memoria, se usan algoritmos o estrategias de ubicación o asignación:

3.1.1. Primera Aproximación:

• Se define una cola de trabajos por cada región de distinto tamaño

Al llegar un trabajo, el Gestor de Trabajos hace lo siguiente:

1º) Lo divide en pasos de trabajo (programas)

2º) Sitúa una región correspondiente a cada proceso de trabajo, en la cola

correspondiente a la región que con tamaño suficiente cubra sus necesidades de

memoria con un desperdicio mínimo

3º) Al acabar el proceso, se libera la memoria que tenía asignada, y el Planificador de

Trabajos pide al cargador que cargue en la región que ha quedado libre el

programa correspondiente al paso de trabajo cuyo registro está en la cabecera de la

cola asociada

Problema:

Si suponemos:

J1: 2K

J2: 1K

J3: 4K

J4: 3 ½ K

! Todos se colocarán en Q2, lo que supone desperdiciar 16K

Si en el ejemplo, los pasos de trabajo tienen necesidades menores de 4K, todos quedan en la cola Q2, por lo que de los 20K disponibles, se desperdician 16K.

3.1.2. Segunda Aproximación:

• Sólo hay una cola de trabajos en el sistema

• En este caso, un programa se cargará solamente en la región en que se despedicie menos espacio

• Se puede añadir también la limitación: First Come First Served (FCFS) (FIFO)

Problema:

• Si se libera la zona de 10K, con la limitación FCFS, J1 no se cargará en memoria, pues será más adecuado la región de 6K (no se carga ninguno: FIFO)

• Si se permite la restricción FIFO, se recorre la cola, pero si sólo llegan trabajos con requerimiento de memoria pequeña, también se quedaría el sistema parado: Y encima recorrería toda la cola!!!

Los problemas se deben a que la restricción FIFO, es decir, a la estrategia de ubicación, a cargar cada paso de trabajo sólo en la región en que menos espacio se desperdicie. Esta estrategia se llama: Best - Fit Only (BFO)

Solución:

• Cambiar de estrategia: Usar la estrategia Best Available Fit:

! Cargar el paso de trabajo en la zona de memoria que menos

memoria desperdicie de entre los disponibles

Problema de ubicación:

¿Qué pasa cuando un proceso se está ejecutando, necesita más memoria, pero el Sistema Operativo no puede concederle más?

Hay tres posibilidades:

Terminar anormalmente el proceso, indicando que no hay memoria suficiente, para que cuando el usuario relance el trabajo, indique que va a necesitar más memoria.

Mandar un mensaje al proceso, indicando que no hay más memoria disponible. El proceso decide si continuar o no.

Sacar la imagen de ese proceso a memoria auxiliar y cargarlo en una región de mayor tamaño si la hay.

• Esta solución sólo vale cuando hay una región de mayor tamaño

• Esta solución sólo vale cuando la reubicación es dinámica

Para aumentar el rendimiento de los Sistemas MFT, suelen combinarse dos técnicas:

SWAPPING: Asociar a cada proceso un tiempo de uso del Sistema

ROLLING: Conmutar los procesos en base a la prioridad

¿EN CUÁNTAS REGIONES SE DIVIDE LA ZONA DE USUARIO? ¿DE QUÉ

TAMAÑO?

• Se hace una primera división que recoge las necesidades de los procesos que se van a ejecutar en la instalación

• Tras llegar a una división correcta, se genera el sistema, se pone operativo, y se recogen datos sobre el rendimiento del sistema con esa división

• Si tras analizar los datos, el rendimiento no es adecuado, se redenera el sistema con una nueva división: TUNNING

Problema:

• Si el conjunto de trabajos a ejecutar es dinámico, es decir, varía con el tiempo, es muy difícil lograr un división adecuada

Solución:

• Poder variar el tamaño de las regiones dinámicamente ! MVT

EJEMPLO:

Supongamos que se ha generado el siguiente sistema:

¿Será bueno el rendimiento del sistema con estos supuestos?

Para ver si el rendimiento es bueno en un sistema, hay que calcular la fragmentación:

• A un proceso que necesita una zona de memoria de tamaño M, se le asigna un espacio de memoria de tamaño N, de manera que siempre:

M " N

• Se conoce como FRAGMENTACIÓN INTERNA:

N - M

• Se conoce como FRAGMENTACIÓN INTERNA TOTAL:

 Ni - Mi

• Se conoce como FRAGMENTACIÓN EXTERNA, al sumatorio de los tamaños de las regiones libres. Sólo se calcula cuando hay procesos en espera

• La FRAGMENTACIÓN o FRAGMENTACIÓN TOTAL, es:

Fragmentación INTERNA + Fragmentación EXTERNA

• El rendimiento será mejor cuanto menor sea la fragmentación

• El rendimiento es pésimo, ya que la zona de usuario cuenta con 22 K, y se desperdician 12 K

Si suponemos que se ha generado el siguiente sistema:

3.2. PARTICIONES VARIABLES: SISTEMAS MVT:

Inicialmente, la Zona de Usuario no está dividida.

Al llegar un trabajo, se le asigna la parte de memoria que necesita, y el resto pasa a ser un nuevo hueco.

Se continúa así sucesivamente, hasta no poder dar servicio a nadie más.

El sistema, necesita conocer la situación de memoria, es decir:

• Qué huecos hay

• De qué tamaño son

• Dirección de comienzo de cada una

• ...

Esta información, se guarda en la TABLA DE SITUACIÓN DE MEMORIA, que debe ser mantenida dinámicamente.

Problema:

En ocasiones, el trabajo necesario para mantener en la Tabla de Situación de Memoria (TSM) un hueco, no compensa, al ser muy pequeño el tamaño del hueco.

! Se define un tamaño mínimo de hueco, y sólo se representan en una tabla, los

huecos de tamaño mayor o igual a ese mínimo.

Los huecos de menor tamaño, pueden quedar libres y sin representar. A estos huecos, se les denomina MIGAS. De echo, cada cierto tiempo, se lanza un proceso llamado `RECOGE MIGAS' para recuperar ese espacio.

EJEMPLO:

Sea una Memoria Principal de 256 K, donde:

• Sistema Operativo: 40 Kw

• Zona de Usuario: 216 Kw

La cola se recorre en orden FCFS (FIFO)

Sea la siguiente cola de trabajos:

ID	Necesidad de Memoria	...
J1	60 K
J2	100 K
J3	30 K
J4	70 K
J5	50 K

El procesador sigue una estrategia de planificación llamada ROUND-ROBIN:

• Se cede el control del procesador durante un espacio de tiempo a los procesos de la Lista READY, que por tanto, van rotando por el procesador

El QUANTUM, es una unidad de tiempo, y es un tiempo mucho mayor al que se tarda en asignar memoria a un trabajo y la carga de su programa, es decir, que el tiempo que se tarda en asignar memoria a un trabajo, y cargar su programa, es despreciable.

Con estos datos, se pide:

• Ir dibujando la Lista READY, la Tabla de Situación de Memoria y la Zona de Usuario

SITUACIÓN INICIAL:

1ER QUANTUM:

Llega J1:

Llegan J2, J3, ..., a la vez que se le asigna el procesador a J1

Al llegar J2: Al llegar J3:

2º QUANTUM:

J1 ha acabado su Quantum:

3er QUANTUM:

J1 ha acabado su Quantum:

Y se sigue así hasta que se acabe de ejecutar algún proceso. Para ello, elaboramos un cuadro de resumen de tiempos:

J1	1	4	7	10	13
J2	2	5	8	11	14//
J3	3	6	9	12	15

Al acabar el quantum nº 14:

15º QUANTUM:

J1	13	16	19	22	25	28//
J2	14
J3	15	18	21	24	27
J4		17	20	23	26

Al acabar el quantum nº 28:

29º QUANTUM:

J1	28//
J2
J3	30	33	36
J4	29	32	35	38//
J5	31	34	37

3.3. ESTRATEGIAS DE UBICACIÓN O SISTEMAS DE ASIGNACIÓN:

• Son válidas para:

• MFT

• MVT

• Memoria Virtual

• Memoria Secundaria

• Estas estrategias, se usan para calcular dónde ubicar el siguiente programa, conjunto de datos, ... en memoria. Se trata en definitiva, de localizar un hueco de tamaño suficiente

• Los tipos de estrategias de ubicación son:

Zonas Libres Encadenadas:

! best - fit

! worst - fit

! first - fit

`BUDDY SYSTEMS'

ZONAS DE MAGNITUDES PREDEFINIDAS

3.3.1. Zonas Libres Encadenadas:

• A cada zona libre se asocia un descriptor con:

• Su dirección de origen o de comienzo

• Su tamaño o magnitud

• Los eslabones de encadenamiento o punteros

• El descriptor, está dentro de la propia zona de memoria.

• Al liberarse una zona de memoria, se reinserta en la lista, siendo objeto de fusión con los posibles huecos contiguos

• La TSM (Tabla de Situación de Memoria), está implementada como una lista doblemente enlazada de zonas libres o huecos

3.3.1.1. ESTRATEGIA BEST - FIT

• Consiste en asignar el hueco mínimo con tamaño suficiente

• Al llegar JN con necesidad de 13 K, hay que buscar el hueco en el que menos memoria se desperdicie

Inconveniente:

• Hay que recorrer todos los huecos para escoger el mínimo con capacidad suficiente

Solución:

• Mantener siempre ordenada la lista en ascendente por tamaño de hueco o zona libre

Problema:

• Al tratar de desperdiciar el mínimo hueco en cada zona, puede producir migas, huecos muy pequeños que no tienen capacidad para albergar nada.

• De cualquier manera, el rendimiento de esta estrategia es bueno

3.3.1.2. ESTRATEGIA WORST - FIT

• Consiste en asignar el hueco mayor con tamaño suficiente, es decir, el hueco en e que más espacio se desperdicie

Inconveniente:

• Hay que recorrer todos los huecos para escoger el más grande

Solución:

• Mantener siempre ordenada la lista en descendente por tamaño de hueco o zona libre

Ventaja:

• Sólo hay que consultar el primer hueco, porque si no cabe en el primero, no cabe en ningún otro

• No se generan migas, al menos hasta muy tarde

3.3.1.3. ESTRATEGIA FIRST - FIT

• Consiste en asignar el primer hueco (en orden de dirección) con tamaño suficiente

• El objetivo, es, acelerar la búsqueda al máximo, de forma que no haya que recorrer la Lista de Zonas Libres

• La lista está ordenada por orden de dirección de comienzo

• En principio, la estrategia de FIRST - FIT es la más rápida, sobre todo cuanto más dispersas son las magnitudes solicitadas

• WORST - FIT es la que menos compensa, porque los huecos que desperdicia son muy grandes

3.3.2. `BUDDY SYSTEMS':

Las magnitudes de las zonas de memoria están cuantificadas (determinadas) siguiendo un algoritmo recursivo, y se expresan en múltiplos de una determinada unidad de asignación.

Se usan reglas de recursividad, dadas por:

• El Sistema Binario: 1, 2, 4, 8, 16, ...

• El Sistema Fibonacci: 1, 1, 2, 3, 5, 8, 13, ...

Cuando se necesita un bloque de magnitud Si, si no hay ninguno libre, se subdivide un bloque de magnitud Si+1, usando la relación de recursividad.

			32	K
	16	K			16	K
8	K	8	K		16	K
4K		8	K		16	K

• Sólo se fusionan huecos adyacentes si suman lo que deben sumar

• Todo bloque de tamaño mayor que 1, es la concatenación de los 2 bloques en que puede dividirse. A estos bloques se les denomina “buddies”

En los Buddy Systems, las posibles direcciones de comienzo de los bloques están predefinidas:

Ventajas:

• Sólo se obtienen ventajas cuando las demandas coinciden con los posibles tamaños de los bloques:

• La búsqueda de un bloque es muy rápida

• La fusión de bloques que se liberan, es prácticamente instantánea

3.3.3. Zonas de Magnitudes Predefinidas

Estas estrategias se usan cuando la demanda de bloques se realiza sobre un conjunto de magnitudes definidas.

En el VM 1370 de IBM, se demuestra que el 95% de las demandas, se realizan sobe bloques de 10 tamaños distintos:

• Se definen 10 zonas de memoria, es decir, una por cada uno de esos tamaños, más otra zona con todo lo que queda libre

• Se utiliza una cola de trabajos por cada zona de memoria, de manera que las demandas de cada una de las 10 magnitudes van a la cola del resto de memoria

• Ese resto de memoria, puede usar cualquiera de las políticas de asignación vistas

¿Cuándo se usan las políticas de asignación?

Las estrategias de asignación se utilizan:

• Al asignar Memoria a los trabajos

• Al crear procesos

• Al reservar buffers de E/S

• ...

Las estrategias de asignación se utilizan por parte de los programas de aplicación, a través de llamadas al sistema para asignar o liberar memoria:

P.e. :

* malloc (En C)

* free (En C)

3.4. PROBLEMA DE COMPACTACIÓN:

Supongamos:

! J5 no cabe en ninguno de los huecos, pero sí cabría si todo el espacio libre formara

un hueco (76 K)

Solución:

• Reorganizar el contenido de la memoria, para que haya un único hueco. A esto se le llama REALIZAR UNA OPERACIÓN DE COMPACTACIÓN: Compactar la memoria consiste en mover los contenidos de la misma, de forma que la memoria libre, quede formando un único hueco

Inconvenientes:

• Consume recursos que podrían usar los procesos

• Los procesos en ejecución, deben parase durante la compactación:

• Los tiempos de respuesta serán variables

• No es aplicable a Sistemas de Tiempo real

Conclusión:

• Hay que estudiar en cada sistema, la forma más adecuada de implementar la compactación, y cada cuánto tiempo debe realizarse

Formas de implementar la operación de COMPACTACIÓN:

Con operaciones de memoria a memoria (por bloques)

Mediante un canal de E/S, es decir, se sacan los bloques usados a Memoria Auxiliar, y luego se vuelven a pasar a Memoria Principal, sin dejar hueco entre ellos (Es la que más se usa)

Con dos canales trabajando en paralelo: Uno saca la información a Memoria Auxiliar, y el otro la va volviendo a pasar a Memoria Principal

El Kernel.

Definición: En cualquier Sistema Operativo por niveles, cada nivel se `extiende' con

las demás primitivas de los niveles inferiores.

Cada nivel es capaz de llevar a cabo las funciones implementadas en él

mismo, más las funciones implementadas en todos los niveles

inferiores.

VENTAJAS:

• Tienen un diseño modular

• Existe la posibilidad de diseñarlos mediante lenguajes de alto nivel

( UNIX está hecho en C )

• Las partes ligadas al Hardware, deberán desarrollarse en ensamblador o lenguaje máquina, o microprogramarlo

En definitiva, llegamos a la conclusión de que estos Sistemas Operativos son:

• Más fiables

• Más fáciles de mantener

• Más fáciles de extender

NÚCLEO MÍNIMO DE UN SISTEMA OPERATIVO: (De propósito general)

• En el núcleo, debe estar la parte más usada por los procesos

• El núcleo, será la parte que no estará programada en alto nivel, en definitiva, será la parte que mayor rendimiento tenga

• La misión del Kernel, será crear un entorno adecuado para que los procesos puedan desarrollarse y ejecutarse correctamente.

• El núcleo, tiene que hacer posible que existan procesos en el sistema

Como mínimo, en el núcleo tiene que haber:

El GESTOR DE INTERRUPCIONES DE PRIMER NIVEL: FLIH

(First Level Interruption Handler): `Algo' que gestione las interrupciones

El DISPATCHER o PLANIFICADOR DE BAJO NIVEL o CONMUTADOR DE CONTEXTO: Elemento que decide quién se va a ejecutar en cada momento

Mecanismo de comunicación entre procesos

El núcleo, está instalado sobre un Hardware, un Hardware mínimo.

SOPORTE HARDWARE MÍNIMO:

• Tiene que tener un Hardware de interrupciones que como mínimo salva el valor del PC

• Tiene que haber un Hardware de protección de memoria

• Tiene que haber instrucciones reservadas para uso por parte del Sistema Operativo

• Tiene que haber un reloj, es decir, un contador

Cuando hablamos de instrucciones reservadas, nos referimos al firmware, que está entre el Núcleo y el Hardware, es decir, son una serie de instrucciones dentro de un chip.

2.Componentes del núcleo.

2.1. EL CONTROLADOR DE INTERRUPCIONES DE PRIMER NIVEL: EL FLIH

En principio, una señal es una indicación por la que se altera la secuencia de ejecución. Hay varios tipos de interrupción, que se clasifican en función de su origen:

! EXTERNAS: Se producen fuera del procesador

! INTERNAS: Se producen dentro del procesador

Si precisamos más:

Las interrupciones EXTERNAS, las denominamos:

• INTERRUPCIONES

Las interrupciones INTERNAS, pueden ser:

• EXTRACÓDIGOS: Operaciones que manipulan elementos internos del

procesador

• TRAPS o EXCEPCIONES

La misión del FLIH, está en el núcleo, para dar una respuesta a cualquier tipo de señal que se produce en el sistema.

Al producirse una señal, la atrapa el Hardware de interrupciones, que como mínimo, salva el contenido del PC en el PCB del proceso. Además, puede que también salve el resto del entorno volátil (también en el PCB). También direcciona al FLIH, es decir, pone en el PC la dirección del FLIH.

Por lo tanto, podemos decir, que el FLIH es un elemento software, es un proceso.

Ya hemos dicho que el FLIH es Software, pues se trata de un sencillo programa definido sobre un área de memoria dedicada a él, un área de memoria específica; es decir, el FLIH siempre está en la misma parte de la memoria.

El FLIH hace dos cosas:

1º) Determina el origen de la interrupción

(Averigua qué interrupción se ha producido)

2º) Direcciona la rutina que trata esa interrupción

Si el FLIH es un programa, necesita parte del entorno volátil: PC, ACC, ... Por ello, debe salvarse el entorno volátil del proceso interrumpido. El entorno volátil del proceso interrumpido, se puede salvar en dos momentos:

Puede salvarlo el Hardware de interrupciones

Si no lo salva el Hardware de interrupciones, será lo primero que haga el FLIH, antes incluso de determinar el origen de la interrupción

NOTA:

Hay sistemas que definen unos registros máquina para uso exclusivo por parte del Sistema Operativo, para evitar tener que estar salvando y restaurando el contenido del entorno volátil.

2.1.1. Formas de determinar el origen de una interrupción:

2.1.1.1. MEDIANTE SOFTWARE:

Mediante una cadena de saltos o IFs (o con una CASE)

El FLIH, tiene un único punto de entrada:

Ventaja: ! Es muy sencillo

Desventaja: ! Rendimiento muy pobre (Cuantas más interrupciones, peor

rendimiento)

Posible solución:

• Poner al principio de la cadena de saltos las comprobaciones de las

interrupciones más frecuentes.

2.1.1.2. MEDIANTE HARDWARE:

Mediante el uso de un comparador simultáneo, incluido en el Hardware de interrupciones.

El origen de la interrupción, no lo va a detectar el FLIH, lo va a detectar el Hardware de interrupciones.

El FLIH, tiene N puntos de entrada, siendo N el número de interrupciones que reconoce el sistema.

Ventaja: ! Es casi simultáneo, mucho más rápido que la secuencia de IFs

Desventaja: ! Coste Elevado: Un comparador para muchas interrupciones es

muy caro

2.1.1.3. COMBINANDO SOFTWARE Y HARDWARE:

El comparador distingue los TIPOS de interrupción.

Las interrupciones se agrupan por tipos.

EL Hardware de interrupciones:

1º) Salva el contenido del entorno volátil

2º) Mediante un comparador simultáneo, determina el tipo al que pertenece la

interrupción producida

3º) Se direcciona al FLIH, donde una pequeña cadena de saltos determina la

interrupción en concreto que se ha producido

Si N es el número de tipos de interrupciones, el FLIH tiene N puntos de entrada.

Cuando el FLIH está atendiendo una interrupción, pueden producirse otras.

¿Qué hacemos con esas otras interrupciones que se producen?

• Inhibir (ignorar) el resto de interrupciones mientras se atiende una. Pero esto no puede hacerse siempre

• Las interrupciones más prioritarias deben tratarse nada más producirse

Posible solución:

• Definir niveles de prioridad entre las interrupciones, de forma que si

se está atendiendo una interrupción, quedarán pendientes (o

inhibidas) las de menor o igual prioridad.

Problema:

• Si se produce una interrupción más prioritaria que la que se está atendiendo, debe dejarse de atender la que se estaba atendiendo para atender la más prioritaria. Por lo tanto, debe guardarse el entorno volátil de la interrupción que estaba atendiendo. La interrupción que pasa a ser atendida, también puede tener que dejarse, al llegar otra de mayor prioridad ... Por tanto, es necesario un lugar a para almacenar entornos volátiles, es decir, un PCB, por cada prioridad de interrupción - 1.

2.1.2. Inicio del servicio de una interrupción:

Las interrupciones no pueden estar inhibidas mucho tiempo, es decir, el tiempo de tratamiento del FLIH debe ser corto.

Problema:

• Hay interrupciones cuyo tratamiento lleva mucho tiempo. En ese caso, el FLIH, sólo inicia su tratamiento, y luego, lama a otra rutina ajena o externa a él, que realiza el resto del tratamiento.

Una interrupción puede implicar cambio(s) de estado en algún(os) proceso(s).

TIPOS DE INTERRUPCIONES:

• Interrupciones que provocan cambios de estado del proceso en ejecución

• Algunos extracódigos: Peticiones de E/S

• Señales de error para suspensión

• Interrupciones de reloj: Interrupciones por expiración del temporizador

• Interrupciones que provocan cambios de estado en procesos que no están en ejecución

• Interrupciones de E/S

2.2. EL PLANIFICADOR DE BAJO NIVEL: EL DISPATCHER

¿Cuándo se direcciona al dispatcher?

• Por uniformidad, se direcciona siempre tras atender una interrupción:

Siempre que se ejecute el FLIH, se ejecuta después el dispatcher

• Al quedar libre la CPU

• Cuando el proceso en ejecución no sea el más adecuado para estar ejecutándose

El proceso en ejecución no es el más adecuado para estar ejecutándose, cuando se trabajo con lo que se denomina `PRIORIDAD CON REQUISAMIENTO'.

Prioridad con Requisamiento: Si se está ejecutando un proceso y llega otro de mayor

prioridad a la lista READY, se requisa el procesador sl

proceso en ejecución, y se comienza a ejecutar el más

prioritario.

NOTA:

No siempre que se da una interrupción se llamará al dispatcher, pero aunque no tenga nada que hacer, se le suele llamar.

MISIÓN DEL DISPATCHER:

La misión del dispatcher es, realizar operaciones de conmutación de contexto.

ORGANIGRAMA DEL FUNCIONAMIENTO DEL DISPATCHER:

NOTAS:

• La LISTA READY está ordenada por prioridad

• Para saber si hay proceso en curso, se consulta a la Tabla Central.

• Para saber si sigue habiendo proceso en curso, hay que mirar la prioridad del proceso RUNNING (PCB) y compararlo con la prioridad del proceso cuyo PCB está en la cabecera de la LISTA READY

• Cuando quitamos el procesador al proceso en curso, podemos anular el dato `Proceso en curso' o no anularlo, porque de todas formas se machacará posteriormente aunque no lo anulemos

TABLA CENTRAL:

La tabla central, es, el medio de acceso a todas las estructuras del sistema, y el continente de informaciones generales del sistema.

NUMERO - VERSIÓN

FECHA

..........

ESTRUCTURA DE PROCESOS

LISTA_READY

LISTA_BLOCKED

....

2.3. IMPLEMENTACIÓN DE LAS PRIMITIVAS DE COMUNICACIÓNES ENTRE

PROCESOS:

Las primitivas de comunicación entre procesos, son necesarias porque a veces un proceso tiene que sincronizarse con otros.

Las primitivas de comunicación entre procesos, deben estar accesibles para todos los procesos:

• Tanto procesos de usuario

• Como procesos del sistema

Cuando un proceso se bloquea, cambia de estado; pasa de RUNNING a BLOCKED. Es decir, deja de haber proceso en curso, por lo que hay que invocar al dispatcher.

La primitiva de bloqueo, debe poder llamar al dispatcher.

De forma análoga, cuando tras una interrupción se desbloquea un proceso, debe llamarse a la primitiva de desbloqueo desde el tratamiento de interrupciones.

! La primitiva de desbloqueo y el tratamiento de interrupciones, deben implementarse al mismo nivel

! Las primitivas de bloqueo y de desbloqueo, deben implementarse en el núcleo para que sean accesibles desde todos los niveles

EJEMPLO DE UTILIZACIÓN:

WAIT (S) ! IF S.E NOT > 0

THEN Bloquear (S.C)

ELSE S.E := S.E - 1;

SIGNAL (S) ! IF S.C.CABEZA NOT NULL AND

S.C.COLA NOT NULL

THEN Desbloquear (S.C)

ELSE S.E := S.E + 1;

`Bloquear' y `Desbloquear', son las primitivas que se usan en distintos procesos.

Si implementamos una rutina de `Bloqueo'

Proceso_en _curso = NULL

Modificar su estado en el PCB ! BLOCKED

Insertar su PCB en:

• La LISTA BLOCKED

• La Cola del Semáforo

Si implementamos una rutina de `Desbloqueo'

Sacar el PCB de:

• La Cola del Semáforo

• La LISTA BLOCKED

Modificar su estado en el PCB ! READY o RUNNING

Insertar su PCB en la LISTA READY

! Para meter/sacar procesos en/de la cola de un semáforo:

• Para añadir o extraer un PCB en la cola del semáforo, es necesario conocer su implementación y/o organización

• Distintos semáforos pueden usa colas con distintas organizaciones o implementaciones

Solución:

• Implementar junto con el semáforo, rutinas de manejo de sus estructuras de datos, para ser invocadas por las rutinas de bloqueo/desbloqueo.

TYPE SEMAFORO RECORD

E: INTEGER;

COLA: ---;

ORGANIZACIÓN: ^RUTINA DE MANEJO DE LA COLA;

END

La organización, es una llamada a la rutina; no se implementa

directamente, porque no se tienen datos para hacerlo.

La ejecución de un WAIT/SIGNAL sobre un semáforo, puede implicar un cambio de estado en algún proceso. Por ello, se direcciona al dispatcher después de cualquier WAIT o después de cualquier SIGNAL. Se direcciona SIEMPRE, aunque no haga nada.

EJEMPLO DE UNA WAIT:

INDIVISIBILIDAD:

• Las rutinas de bloqueo y desbloqueo, deben implementarse como indivisibles

• Las tareas que tienen que hacer estas primitivas, no pueden hacerse en una instrucción

• Para que sean indivisibles, se consideran como una Sección Crítica, con su protocolo de entrada y su protocolo de salida, con lo que además garantizamos la Exclusión Mutua. Estos protocolos se construyen con espera activa mediante instrucciones Hardware, porque en el núcleo no hay nada más disponible.

En los Sistemas Monoprocesador:

• No hay que garantizar la Exclusión Mutua, sólo habrá un proceso ejecutándose en cada momento

• Hay que mantener la indivisibilidad, no se puede interrumpir una primitiva

En los Sistemas Monoprocesador, sólo se interrumpe un proceso mediante una interrupción.

Los protocolos se construyen inhibiendo y desinhibiendo las interrupciones:

PROTOCOLO DE ENTRADA Inhibir interrupciones

SECCIÓN CRÍTICA Primitiva de (des)bloqueo

PROTOCOLO DE SALIDA BLOQUEO/DESBLOQUEO

	WAIT / SIGNAL	BLOQUEO / DESBLOQUEO
PROPÓSITO	SINCRONIZACIÓN GENERAL ENTRE PROCESOS	EXCLUSIÓN MUTUA DE PROCESOS: INIT_SEM WAIT SIGNAL
NIVEL DE IMPLEMENTACIÓN	SOFTWARE	SOFTWARE + HARDWARE
MECANISMO DE RETARDO	COLA	ESPERA ACTIVA / INHIBICIÓN DE INTERRUPCIONES
TIEMPO DE RETARDO	VARIOS SEGUNDOS	VARIOS SEGUNDOS

Estrategias de Reemplazamiento.

El objetivo de estas estrategias, es, seleccionar un bloque de los que están en Memoria Principal, para reemplazarlo por otro (evidentemente, si hay que reemplazarlo por otro, es porque este otro ha sido recientemente referenciado) logrando un buen rendimiento.

Para evaluar el rendimiento de estas estrategias, se ejecutan contra una cadena de referencias, que es una secuencia de referencias a memoria.

Las cadenas de referencias pueden generarse:

De forma artificial

A partir de las trazas de los programas, olvidándose de los desplazamientos

Traza de un programa: Conjunto de direcciones por las cuales va pasando

un programa.

Una cadena de referencias, sólo tendrá números de páginas, no

Desplazamientos.

Hay que eliminar referencias sucesivas al mismo bloque.

Para hacer una simulación, además de la cadena de referencias, se necesita saber la cantidad de Memoria Real disponible para la ejecución, es decir, para saber cuántos fallos de bloque va a referenciar, está bien saber la Memoria Real de la que se dispone.

Podemos representarlo mediante la siguiente gráfica:

También se suelen utilizar otros tipos de gráficas:

Cuando estas curvas no son descendentes, nos encontramos ante la ANOMALÍA DE BELADY.

Para evitar que se produzca esta anomalía, debe cumplirse que:

Si (w, m) " Si (w, m+1)

Donde:

Si (w, m): Es el conjunto de bloques que están cargados en una memoria de m

celdas en la i-ésima referencia de la cadena w

ESTRATEGIA DE REEMPLAZAMIENTO FIFO(FIRST INPUT FIRST OUTPUT):

Elige para ser reemplazado al bloque que lleva más tiempo cargado en Memoria.

Para poder implementar esto, cada bloque, debe tener asociado el instante de reloj en que fue cargado en memoria.

Una forma sencilla de implementarlo, es, mediante una estructura FIFO, es decir, una cola FIFO.

Ventaja:

• Es muy fácil de implementar

Problema:

• Se puede producir la anomalía de BELADY

EJEMPLO:

Dada la cadena de referencias:

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Probar para FIFO con 2, 3, 4 y 5 celdas.

¿Cuántos fallos de bloque se producen?

2 CELDAS

Descargar

1

2

3

4

1

2

5

1

2

3

4

Enviado por:	Carlos Seisdedos
Idioma:	castellano
País:	España