TEMA 4: Gestión de la Memoria.

1. - Introducción.

Para que un programa pueda ser ejecutado sus instrucciones tienen que estar cargadas en la memoria principal (ya sean todos sus módulos o sólo los que se van a ejecutar).

La memoria es un conjunto de “celdas” en las que se puede almacenar una palabra (unidad básica de información de la memoria, normalmente 1 Byte).

Cada celda de memoria tiene una `dirección de memoria' propia y única, que se usará para acceder a los datos que contiene. Existen direcciones físicas y lógicas. Las lógicas son las usadas dentro de un programa para indicar la posición relativa de los datos a los que necesita acceder. Las direcciones físicas son las direcciones reales, usadas por el procesador, la memoria, etc., obtenidas a partir de las direcciones lógicas (que son enviadas al procesador por los programas) mediante un proceso de conversión.

Para acceder a la información de una celda de memoria, el procesador envía su dirección física por el Bus de direcciones, que es una serie de `hilos' o `cables' paralelos, que transportan cada uno de los bits que forman la dirección. El ancho del bus de direcciones indica el nº de hilos que lo forman (la longitud en bits de una dirección física); este ancho determina también la cantidad de memoria principal que va a ser capaz de gestionar un sistema, que no puede ser superior a 2n (siendo n el ancho del bus de direcciones).

El gestor de la memoria es un módulo del S.o. que se encarga de:

- Contabilizar la memoria libre y ocupada.

- Asignar memoria a los procesos.

- Decidir que procesos se mantienen en memoria y cuales se suspenden (se vuelcan al disco).

1.1 - Criterios para la elección de un gestor de memoria:

Para elegir un gestor de memoria adecuado hay que tener en cuenta los siguientes puntos:

Reubicación.

Consiste en volver a colocar un proceso en la memoria. Cuando un proceso ha sido suspendido y se va a continuar con su ejecución, debe volver a la memoria principal, por lo que el S.o. debe decidir si se vuelve a cargar en la región de la memoria donde estaba almacenado antes de ser suspendido o si se le asigna un nuevo lugar; también puede ser necesaria la reubicación para cambiar de lugar un proceso que se encuentre en la memoria, normalmente debido a una compactación de la memoria libre. Al cambiar la posición de un proceso en la memoria hay que tener cuidado a la hora de transformar las direcciones lógicas en físicas ya que, dependiendo del método utilizado pueden producirse errores.

Protección.

Se deben proteger las zonas de memoria asignadas a cada proceso para evitar que los procesos invadan las zonas destinadas a otros procesos o al S.o.

Compartición.

Si hay varios programas que requieran el acceso a la misma información, puede interesar almacenar dicha información en una zona de la memoria común a la que puedan acceder todos los programas que lo soliciten.

Capacidad de minimizar la memoria desaprovechada.

Consiste en evitar la fragmentación interna (se asigna a un proceso más memoria de la que necesita) y la fragmentación externa (entre varios procesos pueden quedar huecos libres tan pequeños que no puedan albergar datos u otro programa). Para evitar la fragmentación externa se pueden emplear técnicas de compactación de la memoria, consistente en reubicar las zonas de memoria asignadas a cada programa de manera que queden agrupadas sin dejar espacios libres entre ellas y quedando todo el espacio libre formando un solo bloque.

Complejidad en el tiempo.

Los algoritmos que componen el gestor de la memoria deberían ser sencillos y de ejecución breve.

Minimizar los procesos suplementarios.

Hay procesos del gestor de memoria que no son obligatorios y que consumen mucho tiempo de proceso, tales como la reubicación de procesos y la compactación de la memoria libre, por lo que se debe evitar su ejecución siempre que no sea estrictamente necesaria.

2. - Mecanismos de gestión de la memoria.

La asignación de memoria a los procesos puede ser de dos tipos: contigua (todos los espacios de memoria usados por un proceso deben ser contiguos, formando un solo bloque) y no contigua o segmentada (los distintos módulos de un programa se pueden ubicar separados en distintas áreas de la memoria alejadas entre sí).

Overlays o Particionamiento

Es un método importante para la carga de programas en la memoria que consiste en dividir dichos programas en módulos funcionales, de manera que sólo se carguen en memoria los bloques del programa que van a ser usados en cada momento; al cargar un programa en memoria se almacena en ella la parte principal o residente del programa y esta va ordenando la carga y/o descarga de los distintos módulos del programa.

2.1 - Métodos de asignación Contigua.

Máquina desnuda.

Es el método más sencillo, usado por los primeros ordenadores que existieron. En él toda la memoria está disponible para los procesos del usuario.

No existe ningún tipo de gestores de memoria, disco, procesos, etc. (no existe el S.o.)., por lo que todas las acciones que se deban realizar deben estar soportadas por el programa (éste debe incluir las rutinas de control de todos los dispositivos que vaya a necesitar usar).

Monitor Residente.

Como todos los programas necesitaban ejecutar rutinas de E/S y para evitar tener que incluirlas en cada programa, estas se almacenaron permanentemente en un área de la memoria, de manera que cualquier programa pudiera ejecutarlas cuando fuese necesario. Al principio a estas rutinas se las llamó IOCS (Input-Output Control System), pero según fueron evolucionando, pasó a llamarse Monitor, que fue el embrión de los primeros Sistemas operativos; además comenzó a utilizar las técnicas de protección de memoria y reubicación de procesos.

- Protección: Es necesario que se proteja el área destinada al Monitor para que otros programas no lo invadan, lo cual se consigue mediante el borde de la memoria, que los programas no pueden atravesar.

Esto consiste en una dirección de memoria límite para el área de las aplicaciones que se almacena en uno de los registros del procesador, de manera que cada vez que un programa intenta acceder a la memoria, el gestor de memoria compara la dirección que el programa ha indicado con la dirección del borde de la memoria, permitiendo el acceso o la ejecución de la instrucción si la dirección especificada se encuentra en el lado apropiado del borde (en el área de aplicaciones, ya esté en la parte alta o en la baja de la memoria).

El valor del borde de la memoria puede ser fijo (borde estático) o variable (borde dinámico); además el borde dinámico puede ser `invariable' (no se puede modificar durante la ejecución de un programa) o `variable' (se puede modificar en cualquier momento).

Los bordes dinámicos pueden provocar operaciones de reubicación, ya que si estos se aumentan e invaden el área destinada a un programa, este programa deberá ser reubicado para dejar espacio al Monitor (al nuevo borde de la memoria).

- Reubicación: Se debe tener en cuenta al transformar las direcciones lógicas en físicas. La transformación puede realizarse en los siguientes momentos:

- Durante la compilación del programa: Es necesario conocer de antemano el borde de la memoria y se utiliza sumando dicha dirección a las direcciones lógicas del programa para obtener las direcciones físicas.

- Cuando el programa se carga en memoria: Al compilar el programa se establece la dirección lógica como [dirección + borde], quedando el borde indefinido, de manera que la suma que se hacía durante la compilación en el caso anterior, ahora se hace al pasar a memoria. De esta manera se crean programas de código reubicable.

- En el caso de bordes dinámicos: Se pueden tomar dos opciones:

· Almacenar el programa en la parte de la memoria contraria al Monitor, de manera que la parte central quede libre para poder variar el borde de la memoria sin tener que reubicar los programas.

· Retrasar la creación de las direcciones físicas (suma del borde) hasta el momento de la ejecución, para que estas se creen en función del valor actual del Borde.

Intercambio o Swapping.

Mediante este método el gestor de la memoria usa la memoria secundaria (más abundante que la principal) para volcar (suspender) los procesos o datos que no sean necesarios en la memoria principal. Es conveniente que estos intercambios se realicen rápidamente para no disminuir el rendimiento del sistema, lo que plantea el problema de la gran lentitud de la memoria secundaria respecto a la principal y al resto del sistema.

Dado un quanto de tiempo asignado a los procesos para su ejecución, una operación de intercambio debería durar menos que dicho quanto para que, mientras se está ejecutando un proceso se pueda ir cargando otro en memoria para que la cpu no esté inactiva, y mientras se ejecuta el 2º programa, descargar el 1º si es necesario y cargar uno nuevo.

Para aumentar la velocidad de estos intercambios se utiliza la técnica del doble búfer o del intercambio solapado, que consiste en designar dos búferes (uno de entrada y otro de salida) de manera que mientras se ejecuta un proceso se carga otro en el búfer de entrada, cuando el 1º termina pasa al búfer de salida y se carga y ejecuta el 2º proceso, y mientras se ejecuta el 2º proceso se vacía el búfer de salida y se carga un nuevo proceso en el búfer de entrada.

Particionamiento fijo o estático (MFT - Multiple Fixed Task).

Es una forma sencilla de gestionar la memoria, dividiéndola en bloques llamados particiones, que pueden ser de distinto tamaño. Esta división se produce en la carga inicial del sistema.

En estas particiones sólo se pueden cargar procesos de igual o menor tamaño que ellas, por lo que si el programa es demasiado grande para caber íntegramente en cualquiera de las particiones libres, éste no se podrá cargar en memoria y ejecutar a menos que se use la técnica del particionamiento (overlays).

En éste método de gestión de memoria también se usa la técnica del swapping.

Usando este método se produce mucha fragmentación interna ya que el espacio de una partición que no es usado por un programa (por ser más pequeño que ella) no se puede aprovechar para almacenar otro programa o datos que no pertenezcan al programa dueño de la partición.

Usar particiones de distintos tamaños tiene las siguientes ventajas:

· Posibilita que grandes programas se carguen en una partición sin usar swapping u overlays.

· Evita o reduce la fragmentación interna (particiones pequeñas para procesos pequeños y viceversa).

En el caso de que existan particiones fijas de distintos tamaños, éstas e pueden gestionar de dos maneras:

- Utilizar una cola de espera para cada partición: Los procesos, según llegan, se van incorporando a la cola de espera de la partición que el gestor de procesos asigne a dicho proceso. De esta manera no se hace un uso eficiente de la memoria ya que mientras algunas de las colas pueden estar llenas, puede que algunas de las particiones de la memoria estén vacías porque no haya ningún proceso que se ajuste a dicha partición siguiendo los criterios del gestor de procesos. Sin embargo este método aumenta el rendimiento del sistema porque el gestor a corto plazo debe tomar menos decisiones (en que cola se debe situar, etc.).

- Utilizar una única cola de espera para todas las particiones: Este método plantea el problema de que el planificador debe decidir, cada vez que se carga un programa, en que partición debe ser cargado cada proceso (aunque sólo en el caso de que la partición de destino del programa no esté preasignada).

Los problemas de usar el particionamiento fijo son que al dividir la memoria en un nº fijo de particiones se limita la cantidad de procesos que pueden almacenarse simultáneamente en la memoria principal. Además los procesos pequeños generan mucha fragmentación interna. No existe la fragmentación externa.

El sistema usará una tdp (Tabla de Descripción de Particiones) para almacenar la información de todas las particiones, como la dirección inicial, el tamaño, el estado (libre/ ocupada), etc. Esta tabla se deberá consultar cada vez que se deba cargar un proceso en memoria principal.

Particionamiento dinámico (MVT - Multiple Variable Task).

Usando este método la memoria no se divide inicialmente en particiones, sino que cuando un programa se carga en memoria se le asignará el espacio que necesite, por lo que no se creará fragmentación interna, aunque con el tiempo se va creando fragmentación externa al cargar y descargar programas de distintos tamaños, que se ajustan a los huecos libres dejando espacios entre ellos.

Para solucionar el problema de la fragmentación externa se puede recurrir a técnicas de compactación, pero el sistema debe poseer la capacidad de la reubicación dinámica, que permite que al mover un proceso dentro de la memoria no se generen direcciones físicas erróneas (hay que tener en cuenta este desplazamiento al transformar las direcciones lógicas).

Para seleccionar en cual de los posibles huecos libres de la memoria se va a cargar un nuevo programa se usan los mismos cuatro algoritmos que se usan para la gestión de asignación contigua de ficheros en el disco:

- Primer ajuste: Se consiguen tiempos de respuesta aceptables y se suele generar fragmentación externa en la parte baja de la memoria, por lo que es necesaria la compactación.

- Segundo ajuste: Los resultados generales son peores que con el primer ajuste, pero la fragmentación externa se genera en la parte alta de la memoria, por lo que la compactación es más rápida.

- Mejor ajuste y peor ajuste: Estos dos métodos son los peores porque crean fragmentación externa repartida por toda la memoria.

2.2 - Métodos de asignación Segmentada.

En los métodos de asignación de memoria anteriores, la ubicación de un proceso en la memoria debe ser contigua. Todos los métodos que se verán a continuación posibilitarán o usarán la asignación segmentada.

Paginación Simple.

En este método la memoria se divide en marcos o marcos de página en el momento de arranque del sistema, y su tamaño puede estar fijado por la unidad de gestión de memoria del sistema (mmu - memory manager unit; como Intel, que especifica un tamaño de marco de 4Kb.) o puede ser establecido mediante Microprogramación (como los Power Pc).

Los procesos también se dividen en fragmentos llamados páginas, que son del mismo tamaño que los marcos de la memoria.

De esta manera, al cargar un proceso, éste se divide en páginas, almacenándose cada una en un marco libre de la memoria y sin estar necesariamente organizadas de manera secuencial, por lo que se evita la fragmentación externa: aunque haya muchos marcos libres en la memoria muy separados entre sí, si un proceso posee menos páginas que los marcos disponibles, éste se podrá cargar en la memoria sin importar la ubicación de cada una de sus partes y sin la necesidad de emplear técnicas de compactación y reubicación.

Sin embargo la paginación genera casi siempre (es raro que no ocurra) fragmentación interna al final de la última página de cada proceso, ya que en una página sólo puede almacenarse parte de un solo proceso y por ello, como es raro que un programa llene completamente su última página, el resto de bytes libres queda sin usar.

Diferencias entre paginación y particionamiento estático:

- El tamaño de las páginas suele ser más pequeño que el de las particiones.

- Un programa puede ocupar más de una página, pero sólo una partición.

Para la gestión de las páginas de cada proceso se usará una lista o tabla de páginas donde se registran los marcos en los que están ubicadas cada una de las páginas del proceso. Además existirá una tabla de marcos libres para registrar los marcos de memoria disponibles.

Para localizar cualquier dato en memoria los programas utilizan direcciones lógicas, que están compuestas por el nº de la página del programa en el que se encuentran y por el desplazamiento en Bytes del dato respecto del inicio de dicha página: [pagina | desplazamiento].

Para convertir una dirección lógica en una física (la que usa el procesador para obtener los datos que el programa le ha pedido) se debe consultar la tabla de páginas del proceso para saber cual es el marco en el que está almacenada la página solicitada, y el desplazamiento se mantiene igual; después, para hallar la dirección de memoria final (en binario), se calcula la dirección inicial del marco especificado y se le suma el desplazamiento. Cuando el tamaño de los marcos es una potencia exacta de 2, éste último paso es muy sencillo, porque basta con poner la cadena de bits (en binario) correspondiente al desplazamiento a continuación de la correspondiente al marco, siendo el resultado de esta concatenación la dirección de memoria donde está el dato; sin embargo cuando el tamaño del marco no es potencia exacta de 2 no se puede realizar este `atajo', y es necesario calcular la dirección física por el otro método (`a pelo').

Formas para implementar las tablas de páginas:

- Almacenarlas en registros del procesador: Es una solución muy buena por ser de acceso muy rápido, pero la cantidad de registros disponibles es escasa y éstos son muy caros.

- Almacenarlas en la memoria principal: El sistema es más lento al necesitar dos accesos a memoria para leer un dato (uno para consultar la tabla y otro para acceder al dato). En este método la dirección base de la tabla de páginas de un proceso (su dirección inicial) se almacena en su PCB; cuando se carga el PCB del proceso para su ejecución esta dirección se almacena en el rbtp (registro base de la tabla de páginas), que es un registro del procesador, para así poder acceder rápidamente a la tabla.

- Usar las `memorias asociativas' (caché): En este tipo de memorias se almacenan referencias a los últimos accesos a memoria y, al ser más rápidas que la memoria principal se acelera la consulta de las tablas de páginas en el caso de que la tabla buscada se halle almacenada en ella.

Estas memorias se engloban en la mmu, y en Intel se llaman TLB (Translation Lookaside Buffer).

T = ( (Pa + Ta) + (Pf + Tf) ) / 2

T: Tiempo medio de acceso.

Pa: Porcentaje de aciertos (posibilidad de que la tabla esté en el tlb).

Ta: Tiempo de acceso con acierto (tabla en el tlb): 1 acceso al tlb y 1 acceso a la memoria (dato).

Pf: Porcentaje de fallos (la tabla no está en el tlb).

Tf: Tiempo de acceso con fallo: 1 acceso al tlb (ver si está) y 2 accesos a memoria (tabla y dato).

segmentación.

La memoria no se divide en partes al inicio del sistema sino que es el programador el que diseña programas divididos en segmentos, que pueden ser de tamaño y número variable. Los segmentos se van colocando en memoria en los huecos libres que haya, llamándose en memoria también “segmentos”, que son cualquiera de las divisiones de la memoria, estén libres u ocupadas y sea cual sea su tamaño.

Existirá una tabla de segmentos por cada proceso que funciona igual que las tablas de páginas (sirve para saber donde están ubicados todos los segmentos de un proceso).

Usando la segmentación se produce fragmentación externa y hay que usar la compactación, por lo que es necesario que el sistema soporte la reubicación dinámica.

Además de haber una tabla de segmentos por cada proceso existe una tabla extra que controla la posición de los segmentos o bloques de memoria libres. En las tablas de segmentos se almacena la dirección base de cada segmento, además de su tamaño y otra información acerca del mismo como por ejemplo los atributos (grado de compartibilidad y los permisos de acceso).

Para asignar espacio libre a un nuevo segmento se pueden usar cualquiera de los cuatro algoritmos de asignación contigua (1º ajuste, 2º ajuste, mejor ajuste y peor ajuste).

Las direcciones lógicas se referencian igual que en la paginación: nº de segmento + desplazamiento; y para convertirlas a direcciones físicas se suma la dirección base del segmento en memoria al desplazamiento relativo del dato buscado. También es necesario comprobar al transformar direcciones lógicas a físicas que el desplazamiento no sea mayor que el tamaño del segmento, ya que en ese caso se produciría una interrupción para indicar el error.

A la hora de gestionar las tablas de segmentos se pueden utilizar los tres métodos usados en la paginación (registros, memoria principal y tlb).

Para conseguir la compartición de datos en la segmentación se almacenan los datos requeridos en un segmento aparte y se introduce la información del nuevo segmento en las tablas de segmentos de todos los procesos que requieran el uso de dichos datos, de manera que puedan acceder a ellos como si tuviesen el uso exclusivo del segmento compartido.

segmentación paginada.

Sirve para dar a cada uno lo que quiere, ya que los programadores prefieren basarse en la división de los programas en segmentos, mientras que a un ordenador le resulta mucho más fácil trabajar usando la paginación sobre todo por evitar la fragmentación externa y, con ella, la compactación y la reubicación dinámica; por lo que este método permite que los programadores creen segmentos, pero a la hora de manejarlos, el ordenador divide los segmentos en páginas individualmente. El único inconveniente es el mismo que en la paginación: se produce fragmentación interna en la última página de cada segmento ya que aunque sean del mismo proceso, no puede haber partes de más de 1 segmento en cada página, por lo que todos los segmentos de un proceso crean fragmentación interna en su última página. La fragmentación externa y la compactación se evitan debido a que, aunque se haga paginación segmento a segmento, se siguen usando páginas independientes, todas del mismo tamaño, almacenadas en marcos contiguos, por lo que todos los huecos libres pueden ser aprovechados.

Cada proceso usará una tabla de segmentos que, en lugar de almacenar información sobre los segmentos del proceso, hará referencia a las tablas de páginas de cada segmento del proceso indicando su dirección inicial y tamaño (nº de entradas o páginas).

La dirección lógica viene dada por el nº de segmento y el desplazamiento respecto a éste, aunque este desplazamiento a veces se puede indicar como el nº de página de dicho segmento y el desplazamiento en esa página. En ambos casos se consulta primero la tabla de segmentos para localizar la tabla de particiones de dicho segmento y después se consulta dicha tabla. En el primer caso es necesario transformar el desplazamiento del segmento en el nº de página y el nuevo desplazamiento de la página, pero en segundo no es necesario ya que esa información ya está indicada; después se transforma la dirección igual que en la paginación: dir. inicial de la pagina + desplazamiento.

La dirección de comienzo de la tabla de segmentos se guarda en el pcb, y al iniciar la ejecución de un proceso se almacena en el rbtp o rbts.

paginación segmentada.

Este método de gestión de la memoria se usó solo en el ordenador IBM - S34, y su uso fue debido sólo a que los procesos eran enormes, y por lo tanto las tablas de páginas también lo eran, por lo que era necesario segmentarlas para poder ubicar en memoria el segmento que se fuese a utilizar (no cabían enteras en memoria). Es un sistema muy malo y no se ha usado en ningún otro sistema.

2.3 - Memoria virtual.

Antes era necesario cargar en memoria un programa entero para poder ejecutarlo; ahora basta con cargar solamente los módulos de dicho programa que se van a utilizar o que quepan en la memoria principal. Debido a esto es necesario realizar intercambios con el disco duro para descargar de la memoria módulos que no se usen, dejando así hueco libre para cargar otros módulos que sean necesarios.

Con la memoria virtual se soluciona el problema de la capacidad de la memoria principal, ya que si un programa es muy grande para cargarlo en la memoria, sólo se cargan los módulos que sean necesarios inicialmente.

A los bloques de un programa se les llama bloques virtuales y las zonas de memoria en las que se almacenan se llaman bloques.

Las direcciones lógicas o virtuales son las direcciones de memoria que contiene y usa un programa; y al rango total de direcciones a las que un programa puede acceder se le llama espacio de direcciones virtuales.

Las direcciones disponibles en el sistema debido a la cantidad de memoria instalada se llaman direcciones reales y al conjunto de todas ellas, se le llama espacio de direcciones reales, que no coincide con el espacio de direcciones virtuales.

Las direcciones virtuales se deben convertir en direcciones reales antes de poder ser usadas por el sistema, para lo cual se usa un mecanismo de Traducción Dinámica de Dirección (DAT - dynamic adress translation).

Cuando un programa hace referencia o solicita un dato contenido en una página que no está cargada en memoria se dice que se ha producido un fallo de página iniciándose a continuación la siguiente secuencia:

- El S.o. coloca al proceso que ha generado el fallo de página en estado Bloqueado.

- Se inicia la carga de la página solicitada en memoria, emitiendo el S.o. una solicitud de lectura en disco al subsistema de E/S.

- Mientras se produce la carga en memoria de la página solicitada el S.o. puede atender la ejecución de otros procesos.

- Cuando se ha terminado de cargar la página en memoria el S.o. vuelve a poner al proceso que había generado el fallo de página en estado de Listo en espera de continuar con su ejecución.

Las direcciones virtuales consecutivas no tienen porque ser direcciones reales consecutivas.

Para llevar el control de las posiciones o marcos en los que se ha cargado cada página se hace uso de las tablas.

Cuestiones relativas al tamaño de los bloqes.

Cuanto mayor sea el tamaño de los bloques en los que se dividen los programas, menor será el nº de bloques que compondrán cada programa y, por tanto, menor será el tamaño de las tablas de control de bloques necesarias para su gestión; sin embargo llevarán mucho más tiempo las operaciones de transferencia de dichos bloques entre el disco y la memoria.

Si los bloques son pequeños ocurre lo contrario (más bloques por programa, tablas mayores, accesos más rápidos al disco), además de que caben muchos más programas en memoria si, como caben más bloques en memoria, se cargan sólo los indispensables para cada programa. A la cantidad de programas que pueden almacenarse en la memoria se la llama grado de multiprogramación.

Si todos los bloques que forman un programa son del mismo tamaño el sistema estará basado en la paginación y si los bloques pueden ser distintos la memoria se gestionará por segmentación. La memoria virtual también puede estar basada en los sistemas combinados (segmentación paginada y paginación segmentada).

Si se requieren constantemente páginas que no se encuentran en la memoria principal se necesitan numerosos intercambios y accesos al disco, por lo que puede ocurrir que el sistema dedique más tiempo a realizar dichos intercambios que a ejecutar los programas, caso que se conoce como Hiperpaginación.

Para evitar la Hiperpaginación o intentar disminuirla se recurre a la historia más reciente del uso de las páginas para intentar adivinar el posible uso de las páginas en un futuro próximo: esta solución se llama principio de cercanía. Según él los accesos a datos y/o programas tienden a agruparse de manera que si se accede a un dato es muy posible que se acceda en breve al/os dato/s siguiente/s.

Memoria Virtual Paginada.

Se basa en la misma técnica que la paginación simple pero teniendo en cuenta que se diferencia principalmente en que ya no es necesario cargar todo el programa en la memoria, sino sólo las partes que vayan a ser necesarias. A las páginas que están cargadas en memoria principal se las llamará activas o residentes.

Al igual que en la paginación simple, aquí se produce fragmentación interna (espacio desaprovechado en el último marco de cada programa), que también se soluciona reduciendo el tamaño de los marcos.

Cada proceso tendrá una tabla de páginas que indica en que marco está cargada cada página, aunque se diferencia de las tablas usadas en la paginación simple porque además cada elemento de la tabla (cada página) tendrá:

- un bit de presencia: para saber si dicha página está cargada en la memoria

- un bit de Modificado: para saber si el contenido de la página ha cambiado desde que se cargó en memoria; de esta manera no es necesario volcar al disco las páginas que no hayan sido modificadas porque ya se encuentran en él, por lo que directamente se sobreescriben en memoria con páginas nuevas, ahorrando así el tiempo de un acceso innecesario al disco.

Para la gestión de las tablas de páginas se puede usar cualquiera de los 3 métodos de la paginación simple (registros, memoria principal ó tlb).

Puede ser que un proceso ocupe mucha memoria y, por lo tanto, su tabla de páginas también será grande. Para este problema puede haber varias soluciones:

- Tratar la tabla como un proceso, dividiéndola en páginas y cargando en memoria sólo las partes necesarias, aunque esto supondría el problema de tener que implementar una nueva tabla para gestionar las páginas de la primera tabla.

- Usar tablas de páginas a dos niveles, siendo el 1º un directorio de tablas y el segundo las tablas en sí.

- tabla de páginas invertida: Existirá una sola tabla para gestionar todos los procesos activos y los marcos libres, en la que cada registro de la tabla representa a uno de los marcos de la memoria, almacenando la información sobre qué página y de que proceso está almacenada en cada marco. Para pasar de la dirección lógica a física evitando tener que recorrer toda la tabla de manera secuencial se transforma el nº de página de la dirección lógica mediante una función hash que genera un nº que debería corresponderse con el nº de marco en el que está almacenada y tras esto se comprueba en la tabla si esto es cierto. También se usa la función hash al cargar páginas en la memoria, y si se produce una colisión se puede optar por suspender la página vieja, por reubicar la nueva página usando otra vez el hash hasta encontrar un hueco libre o por reubicar la nueva página en cualquier marco enlazándolo con el inicial mediante punteros (si hay varias colisiones se puede formar una cadena de punteros -lista-).

Memoria Virtual Segmentada.

Funciona igual que la segmentación normal pero teniendo en cuenta que ya no es necesario cargar todo el programa en memoria, sino que sólo se cargan los segmentos necesarios.

Otra diferencia es que la tabla de segmentos de cada proceso también contiene los bits de `Pertenencia' y `Modificado', con el mismo uso que en la Memoria Virtual Paginada. Para gestionar estas tablas también se puede hacer uso de los tres métodos anteriores (registros, memoria principal y Caché o tlb).

Para cargar los segmentos en memoria se usa un algoritmo de asignación contigua (1º, 2º, mejor y peor ajuste).

Memoria Virtual con Segmentación Paginada.

Es exactamente igual que la segmentación paginada sin memoria virtual, añadiendo el uso de los bits de `Pertenencia' y `Modificado'.

3 - Algoritmos Software para la gestión de memoria virtual.

3.1 - Políticas de Lectura.

Paginación por Demanda.

Implica que una página será cargada en memoria justo en el momento en el que sea requerida, cargándose sólo ella. Tiene el inconveniente de que se puede producir Hiperpaginación cuando un proceso usa información almacenada en múltiples y diferentes páginas.

Paginación Previa.

Cuando se produce una lectura en disco se carga en memoria un registro físico completo que contiene a la página solicitada, cargándose así el resto de las páginas que contiene dicho registro. De esta manera si se cumple el principio de cercanía se consigue reducir el nº de accesos a disco.

3.2 - Políticas de Ubicación.

Tienen que ver con el lugar o espacio libre (página o segmento) en el que se va a cargar un determinado proceso.

En la paginación no es necesario seleccionar un hueco determinado debido a que todos son iguales.

En la segmentación sí es necesario el uso de uno de los cuatro algoritmos de asignación contigua, ya que si no se gestiona la segmentación de manera eficiente se produce fragmentación externa.

3.3 - Políticas de Reemplazo.

Cuando hay que cargar una página en memoria pero no hay espacio libre es necesario suspender alguna de las páginas inactivas que estén en memoria, por lo que hay que seleccionar la que debe ser reemplazada, para lo que hay que tener en cuenta (3.4 - Gestión del conjunto residente):

- Nº de marcos de página que se asignarán a un proceso.

- ¿Qué páginas pueden ser reemplazadas? Las asignadas al proceso que desea cargar la nueva o cualquier página de la memoria.

La finalidad es seleccionar la página que tenga menos probabilidad de ser utilizada en un futuro cercano. Para ello la mayoría de las políticas intentan predecir el comportamiento futuro en función del comportamiento pasado y del principio de cercanía.

Estos algoritmos no deben ser complejos porque se ejecutan con frecuencia y podrían sobrecargar el Hardware y disminuir el rendimiento del sistema.

Hay que tener en cuenta que algunos marcos pueden estar en estado bloqueado, por lo que estos no podrán ser reemplazados (se implementa con una tabla de marcos que contenga 1 bit para cada marco indicando su estado); estos son paginas y rutinas del S.o. y pcbs que deben estar siempre en memoria.

3.3.1 - Algoritmos.

optimo:

Se basa en “consultar el futuro”, seleccionando para su reemplazo, de las que están en memoria, la página que no se vaya a utilizar en un futuro próximo o la que se vaya a usar más tarde de todas.

Este algoritmo no se puede implementar realmente, salvo para procesos cíclicos o sistemas batch ya que en sistemas interactivos resulta imposible determinar que caminos elegirá el usuario al ejecutar un programa. Debido a esto sólo se suele usar para comparar sus resultados con los de otros algoritmos.

LRU:

Selecciona para su reemplazo la página que fue usada hace más tiempo, basándose en el principio de cercanía. Da buenos resultados pero su implementación no es sencilla.

FIFO:

Se selecciona la página que fué cargada en memoria hace más tiempo por suponer que es muy posible que ya no se esté usando, lo cual no siempre es cierto. Es un algoritmo muy fácil de implementar pero no da buenos resultados.

Reloj Simple:

Es una variante del LRU. Se usa un bit de utilización para cada marco, implementado mediante una lista o tabla de marcos (array de 1 bit): si el bit es `1' la página se ha usado recientemente y viceversa.

Al producirse un intercambio se recorre la tabla de marcos para seleccionar la página a reemplazar, para lo que se usa un puntero que busca el primer marco que tenga el bit de utilización a `0', el cual es el seleccionado para el reemplazo; durante el recorrido del puntero, todos los marcos por los que vaya pasando y que tengan el bit a `1', se ponen a `0' para poder ser seleccionados en la siguiente vuelta del puntero.

Cuando se encuentra un marco con el bit a `0', se reemplaza y el puntero queda apuntando al siguiente marco, de manera que la búsqueda comience por él en el siguiente intercambio. Si en la primera búsqueda no se encuentra ningún marco con el bit a `0', se vuelve a recorrer la lista y, como los bits se han ido poniendo a `0' según pasaba por ellos el puntero, ahora todos los marcos están disponibles para el reemplazo.

El bit se pone a 1 a partir de la 2ª vez que se usa la página: se carga la pagina en memoria (bit = `0'), se usa la página 1 o más veces (bit = `1'), pasa el puntero por el marco (bit = `0'), etc.

Reloj con Bit de Modificado:

A cada marco se le asocia un bit más, que se pondrá a `0' cuando se cargue la página y a `1' cuando su contenido sea modificado; esto se hace para evitar bajar al disco las páginas que no han sido modificadas cuando estas tengan que ser reemplazadas, ya que su contenido ya está almacenado en el disco. De esta manera en lugar de suspender la página, se sobreescribe con la nueva, evitando el tiempo de una operación de escritura en disco.

Para buscar la página a reemplazar hay 3 fases (bits: “util., mod.”):

- Se recorre la tabla de marcos como en el reloj simple, buscando páginas con los bits `0, 0' y se selecciona la 1ª.

- Si no se encuentra en la 1ª fase, se hace una 2ª vuelta buscando los bits a `0, 1' y se ponen a `0' los bits de utilizado que estén a `1' por los que se vaya pasando.

- Si se sigue sin encontrar un marco disponible se repiten los dos procesos anteriores (sólo una vez más).

Anomalía de Belady.

Es obvio que al aumentar el nº de marcos disponibles para un proceso se reduce el nº de fallos de página. Sin embargo esto no siempre se cumple, y a este efecto se le llama anomalía de Belady.

3.4 - Gestión del Conjunto Residente.

Está formado por todos los componentes de un proceso que se encuentran cargados en la memoria principal en un determinado instante.

Políticas en cuanto al Tamaño del Conjunto Residente.

Cuanto menor sea la cantidad de memoria asignada a un proceso, más procesos cabrán en memoria (mayor grado de multiprogramación: nº de procesos que pueden estar en memoria al mismo tiempo). También será mayor la probabilidad de que haya algún proceso en estado Listo.

Cuanto menor sea el nº de páginas de un proceso cargadas en memoria, mayor es la probabilidad de que se produzca un fallo de página; aunque, por la anomalía de Belady, aumentar el nº de páginas de un proceso no disminuye necesariamente el nº de fallos de página.

Respecto al tamaño del conjunto residente normalmente existen dos políticas:

- Asignación Fija: A cada proceso se le asigna un nº fijo de marcos, que se determina en el momento inicial de la carga del mismo. Cuando se haga un reemplazo habrá que hacerlo de manera que el nº de páginas en memoria de dicho proceso sea siempre el mismo.

- Asignación Variable: Permite que el nº de marcos asignados a un proceso pueda cambiar; pueden ocurrir dos cosas: que se produzcan muchos fallos de página por no cumplirse el principio de cercanía, debiéndose aumentar el nº de marcos disponibles, y que el nº de fallos de página sea reducido, por lo que se puede intentar reducir el nº de marcos asignados (pero sólo si al hacerlo no aumenta el nº de fallos de página).

Políticas en cuanto al Alcance del Reemplazo.

Estudian qué páginas podrán ser reemplazadas; también existen dos políticas:

- Reemplazo Local: Las páginas candidatas a ser reemplazadas serán las del proceso que provocó el fallo de página.

- Reemplazo Global: Se podrá reemplazar cualquier página de la memoria, perteneciente a cualquier proceso.

Asignación Fija y Alcance Local.

Combinación de las políticas anteriores: A un proceso se le asigna un nº determinado de marcos y, al reemplazar, sólo se pueden seleccionar sus páginas (páginas locales).

Se puede usar cualquier algoritmo de reemplazo.

Si se asigna mucha memoria a un proceso se pueden cargar muy pocos programas en memoria (frecuentes intercambios de página para poder ejecutar nuevos procesos).

Si se asigna poca memoria a un proceso, se generarán frecuentes fallos de página durante su ejecución.

Asignación Variable y Alcance Global.

El nº de páginas asignadas a un proceso puede variar y se puede reemplazar cualquier página de la memoria. Al reemplazar una página que no pertenece al proceso, aumenta el nº de marcos disponibles para dicho proceso.

Lo usan varios sistemas operativos porque es fácil de implementar, aunque la dificultad radica en la selección de la página a ser reemplazada. Se puede usar memoria caché (de disco) para almacenar la página descargada por si fuese necesario usarla de nuevo y así cargarla rápidamente en memoria.

Asignación Variable y alcance Local.

Puede variar el nº de marcos asignados a un proceso, pero sólo se pueden reemplazar las páginas del mismo proceso. Cuando se carga el proceso se le asigna un nº de marcos y cuando se produzca un fallo de página se seleccionará una de sus páginas locales para su reemplazo.

Cada cierto tiempo se evalúa el nº de marcos asignados al proceso para estudiar si interesa variar su número (aumentar o disminuir el conjunto residente) en función de la cantidad de fallos de página.

Conjunto de Trabajo.

Es el conjunto de las páginas de un proceso que han sido utilizadas en un intervalo de tiempo y permite la modificación del nº de marcos asignados a un proceso consultando las páginas a las que se ha accedido durante ese intervalo. Se designa como W (t, Δ) - t: instante final del intervalo, Δ: duración del intervalo (tiempo total).

El intervalo de tiempo usado en la medición se llama intervalo de tiempo virtual o de ejecución, ya que este sólo se cuenta cuando el programa está en ejecución.

Cuanto menor sea el conjunto de trabajo menor probabilidad hay de encontrar fallos de página (en su intervalo).

El conjunto de trabajo puede aumentar hasta abarcar a todas las páginas del proceso, pero es en casos extremos.

Durante la ejecución de un proceso hay intervalos estables (se hace referencia a las mismas páginas) e intervalos de transición (se usan diferentes páginas de manera consecutiva); los estados transitorios suelen encontrarse entre estados estables. En los intervalos estables se producen menos fallos de página.

El uso del conjunto de trabajo puede generar las siguientes tareas:

- Supervisar el conjunto de trabajo de cada proceso.

- Eliminar periódicamente las páginas del cjto. residente que no se encuentren en el cjto. de trabajo.

- Conociendo el cjto. de trabajo se puede variar el nº de marcos disponibles de un proceso para disminuir el nº de fallos de página o para liberar memoria que no esté siendo utilizada por el proceso.

inconvenientes del Cjto. de Trabajo: Se basa en el Principio de Cercanía, que no siempre se cumple y además es impracticable el control completo de todas las referencias a páginas que genera cada proceso. El intervalo Δ usado para calcular el cjto. de trabajo puede variar, pero se desconoce su valor óptimo.

Algoritmo PFF

Se basa en el control de los fallos de página, estableciendo un valor llamado umbral. Cada página en memoria tendrá un bit de utilización que al cargarla se pone a `0' y al volver a usarla se pone a `1'. Al producirse un fallo de página se consulta el tiempo virtual entre este fallo y el anterior respecto del valor umbral:

- Tiempo < Umbral: Se están produciendo muchos fallos de página y para evitarlo se añade la página que ha provocado este último fallo como un marco nuevo para el conjunto residente del proceso.

- Tiempo ≥ Umbral: Hay páginas en memoria que no están siendo utilizadas y se descargan todas las páginas del proceso con el bit de utilización a `0', reduciendo el tamaño del cjto. residente; también se pone a `0' el bit de utilización del resto de las páginas y se carga la página que provocó el fallo en un marco nuevo.

No se retira una página de la memoria antes de que haya transcurrido un tiempo virtual mayor o igual que el umbral desde su última referencia. Cuando la ejecución está en fase transitoria aumenta el tamaño del cjto. residente y en períodos estables ocurre lo contrario. Este algoritmo se puede modificar usando dos umbrales: uno inferior para disminuir el nº de páginas y otro superior para aumentarlo.

También existe el algoritmo VSWS (Conjunto de trabajo muestreado en intervalos variables) para la gestión del conjunto residente.

3.5 - Políticas de Vaciado.

Estudian en que instante merece la pena que una página que está en memoria se guarde al disco

- Vaciado por Demanda: Las páginas se vuelcan al disco en el instante en el que son seleccionadas para su reemplazo. Después se carga en memoria la página que provocó el fallo y se continúa la ejecución. Tiene que transcurrir el tiempo de una operación de escritura y una de lectura para continuar la ejecución.

- Vaciado Previo: Las páginas en memoria se vuelcan al disco sin esperar a ser seleccionadas, de manera que al producirse el fallo no hay que esperar a que la página se transfiera al disco porque ya está en él y sólo hace falta leer la nueva página del disco y cargarla sobre la anterior (sólo una operación de disco).

Una solución intermedia es el uso de las memorias caché de manera que al suspender una página, en lugar de ir directamente al disco, va a la memoria caché para ser descargada o utilizada más tarde.

3.6 - Control de Carga.

Grado de Multiprogramación.

Indica el nº de procesos que pueden estar cargados en memoria al mismo tiempo. Si hay pocos, es posible que estos queden bloqueados y sea necesario suspenderlos (bajarlos al disco) para poder cargar procesos nuevos que estén listos para su ejecución. Si hay muchos, cada proceso tiene pocos marcos y se producen muchos fallos de página. Esto suele estar controlado por los algoritmos pff y vsws que suelen ajustarse al grado óptimo de multiprogramación.

El grado óptimo de multiprogramación se obtiene cuando el tiempo medio entre fallos de página es igual al tiempo necesario para la gestión de un fallo de página (selección, reemplazo, etc. de páginas).

Suspensión de Procesos.

Si se reduce el grado de multiprogramación habrá que suspender procesos y para seleccionar cual de ellos va a ser suspendido se pueden usar estos métodos de selección:

- Suspender el proceso con la prioridad más baja.

- Suspender el proceso con más fallos de página.

- Suspender el último proceso cargado.

- Suspender el proceso con el conjunto residente más pequeño.

- Suspender el proceso con el conjunto residente más grande.

- Suspender el proceso con mayor tiempo de ejecución restante.

- Etc.

Tema 5: Gestión de Entrada/ Salida.

El sistema de e/s es la parte del S.o. encargada de la gestión de los dispositivos periféricos.

Debido a la gran variedad de periféricos existente es difícil tener una solución única que permita la gestión de todos ellos, por lo que existen los `controladores de dispositivos'.

Una operación de e/s es una transferencia de información entra la memoria o la cpu y un dispositivo de e/s.

Existe Hardware y Software de e/s que ocultan los detalles propios del dispositivo al usuario y al S.o., que son las controladoras y los controladores de dispositivos.

Los dispositivos de e/s se pueden clasificar en: legibles o utilizables directamente por el ser humano (pantalla, impresora, etc.), legibles o utilizables por la máquina (discos, etc.) y dispositivos de comunicación (módems, tarjetas de red, etc.). Existe una serie de características que pueden diferenciar dos dispositivos:

- Velocidad de transmisión de datos.

- Aplicaciones o Software que necesitan acceder al dispositivo.

- Complejidad del control (difícil: hdd; fácil: prn).

- La unidad de transferencia: flujos de bytes (monitores) o bloques de bytes (hdd).

- La representación de los datos.

- Condiciones de error (errores que surgen, modo de comunicarlos, sus consecuencias y sus posibles soluciones).

1 - Planificación de la entrada/salida en disco.

Es importante que la gestión sea ágil y rápida porque es un dispositivo al que se necesita acceder frecuentemente. Para mejorar los accesos habrá que planificar las operaciones de e/s en el disco.

El tiempo de acceso es el `Tposicionamiento' + `Tlatencia' + `Ttransferencia'.

Cuando un proceso requiere un acceso a disco emite una llamada al S.o. para que se realice dicha solicitud, en la que se puede incluir la información:

- Si la operación es de entrada o de salida.

- Cual es la dirección a la que se quiere acceder.

- Dirección de memoria de origen o destino de los datos.

- Cantidad de información que se va a transferir.

Si la controladora de disco y el disco están disponibles se atenderá la solicitud. Todas las solicitudes que llegan a un dispositivo se almacenan en una cola de espera, desde la que se atienden cuando el dispositivo está disponible.

Para una buena gestión del disco será necesario tener en cuenta la proximidad entre las posiciones de disco a las que se quiere acceder.

1.1 - Algoritmos de Planificación de Acceso a Discos de cabezas móviles.

FCFS (fifo).

Se atienden las solicitudes por orden estricto de llegada. No es muy útil porque si dos o más solicitudes de acceso consecutivas quieren acceder a pistas distintas el cabezal debería desplazarse mucho y muy bruscamente. Da malos tiempos de acceso pero es fácil de implementar.

SSTF.

Se atiende primero a la solicitud con menor tiempo de posicionamiento: se accede a la pista más cercana a la posición actual de las cabezas de entre las solicitudes que hay en la lista de espera. Da mejores resultados que el fifo pero no se considera óptimo. Se plantea el problema de posibles inaniciones u olvidos de las solicitudes lejanas.

Scan ó Rastreo.

Se recorren las pistas del disco de un extremo al otro, atendiendo las solicitudes correspondientes a la pista por la que va pasando el cabezal; cuando llega al final del disco se invierte el sentido de movimiento del cabezal, repitiendo el proceso hasta llegar al inicio, donde vuelve a empezar.

C-Scan.

Es similar al Scan pero solamente atiende solicitudes en un sentido: cuando el cabezal, atendiendo solicitudes, llega al final del disco, vuelve al inicio sin detenerse ni atender solicitudes, donde vuelve a comenzar el proceso.

Look.

Igual que el Scan pero al llegar a la última solicitud en su dirección (no al final del disco) invierte el sentido.

C-Look.

Igual que el C-Scan pero el sentido se invierte al atender la última solicitud, no en el final del disco.

Criterios para la Selección

Hay que tener en cuenta:

- Ubicación de los directorios: Si se usan con mucha frecuencia puede interesar almacenarlos en la parte media del volumen, pero si el volumen es muy grande y está casi vacío es mejor tenerlos al principio del mismo.

- Escribir un módulo que pueda ser reemplazable para poder seleccionar un algoritmo diferente cuando sea necesario o rentable.

1.2 Algoritmos de Acceso a Discos de cabezas fijas (Tambores).

Los tambores están formados por varios platos, al igual que los discos duros, pero por cada cara útil de los platos, en lugar de una cabeza de lectura/escritura, tienen una serie de cabezas, una por cada pista, de manera que éstas no se tienen que desplazar (para leer en una u otra pista se selecciona la cabeza correspondiente). El tiempo de acceso sólo es el `Tlatencia' + `Ttransferencia', ya que no hay tiempo de posicionamiento.

Colas por Sectores.

Planifica las solicitudes de acceso colocando en una cola todas las solicitudes de acceso a una determinada pista, por lo que hay tantas colas de espera como pistas en cada cara del tambor.

Tema 6: Técnicas de comunicación de Entrada/ Salida.

En las operaciones de e/s se plantean los siguientes problemas:

Asincronismo.

No se sabe cuando van a surgir, ya que no siguen una secuencia determinada, lo que puede provocar que se intente acceder a una información que aún no está disponible porque no se sabe cuanto va a tardar la operación de e/s.

Diferencia de velocidad.

El tiempo medio de acceso a la memoria es muy rápido en comparación con el tiempo de acceso a los dispositivos. La cpu es aún más rápida, lo que puede provocar un colapso en el dispositivo que debe recibir la información si esta se le envía antes de que éste pueda procesarla.

Representación diferente de la información.

Cada dispositivo debe traducir la información para almacenarla en su propio formato. También un proceso puede solicitar y enviar datos a muchos dispositivos distintos, cuyas rutinas de acceso son imposibles de implementar dentro de cada programa, por lo que se accede a ellos de una manera estándar, que es gestionada y diferenciada sólo por el S.o., que es el encargado de que las operaciones de e/s sean transparentes para el programa.

La parte del S.o. que permite esta transparencia es el gestor de e/s. En éste no se incluyen las rutinas de acceso a todos los tipos y modelos de dispositivos, por lo que es necesaria la creación de un software específico para cada uno de ellos llamado driver o controlador de dispositivo, que incluye todas las rutinas de acceso al dispositivo al que pertenece para que el S.o. pueda usarlas y acceder y controlar así el dispositivo: son extensiones o ampliaciones del gestor de e/s.

Los Drivers son los encargados de planificar el acceso a los dispositivos, y las instrucciones de éstos que se ejecuten lo harán en modo núcleo para tener acceso completo al sistema.

La planificación de la e/s tiene dos objetivos:

- Atender de forma equilibrada los accesos a los dispositivos por parte de los procesos.

- Aumentar el rendimiento de acceso a los dispositivos y, por tanto, el rendimiento global del sistema.

Los dispositivos no están conectados directamente con la cpu, sino que están conectados a las controladoras de dispositivos (hardware), que son las que hacen de interfaz entre ellos, los buses y la cpu.

Las tarjetas controladoras controlan el estado del dispositivo, controlan los motores (si los hay), realizan comprobaciones de datos, conocen el formato del medio, mueven los brazos, etc. También son las que reciben peticiones de lectura, escritura, etc. de la cpu y se encargan de aceptarlas o rechazarlas.

Las controladoras y la cpu se comunican a través de una serie de registros que posee la controladora (registros de estado, búferes de datos, etc.).

Las controladoras de dispositivos no tienen porqué ser tarjetas añadidas al sistema, sino que hoy en día la mayoría ya vienen integradas en la placa base (controladoras de teclado, discos, puertos, e incluso gráficas); las controladoras suelen soportar el manejo de varios dispositivos simultáneamente (una controladora ide normalmente soporta 4 discos duros o cd-rom).

estructura general de una controladora

1 - Interfaz del Bus: Está en contacto con los buses del sistema (Abus, Dbus y Cbus). También se llama lógica de direcciones y controla el espacio de direcciones de la controladora y su relación con el espacio de direcciones de la memoria principal.

2 - Conjunto de registros: Es la parte genérica del dispositivo o la controladora, también llamado puerto de E/S, que tiene los siguientes tipos de registros:

- De entrada: Memoria intermedia que guarda información precedente del dispositivo hasta que la cpu pueda acceder a ella.

- De salida: Almacenan temporalmente información recibida desde la cpu hasta que el dispositivo pueda admitirla.

- De órdenes: Existen de dos tipos:

· De configuración o designación de modo: Almacenan información de configuración de la controladora (tipo de protocolo, longitud del carácter, tipo de control de paridad, etc.). Se configura su contenido en el proceso de inicio de la controladora.

· De operación: Usados para la gestión de órdenes que llevan a cabo una operación de E/S.

- De estado: Proporcionan información a la cpu sobre el estado del dispositivo (ocupado o disponible, etc.).

3 - Interfaz del dispositivo: Es la parte específica del dispositivo, está conectado directamente a él y está adaptado a la estructura del mismo. Se encarga de transformar las señales que llegan a la controladora en órdenes a realizar por el dispositivo y comprensibles por él.

1 - Entrada/ salida programada.

El software de E/S está escrito de manera que la cpu controla exclusivamente el proceso de E/S sin dedicarse a otros procesos. La ventaja es que no se requiere mucho hardware específico para ello, pero el inconveniente es que no da un buen rendimiento al tener que estar la cpu constantemente pendiente del proceso de E/S.

En una operación de E/S se realizan varias transferencias de palabras desde la memoria al dispositivo o viceversa, siendo la palabra la unidad de información.

Para saber si la operación de E/S en curso ha terminado el gestor de E/S estará constantemente consultando los registros de estado del dispositivo. El gestor de E/S será el encargado de iniciar, vigilar y terminar todas las operaciones de E/S.

Será responsabilidad de la unidad de control el realizar las transferencias de datos en ambos sentidos entre los registros y la memoria principal.

Una operación de E/S comienza cuando un proceso solicita al S.o. que se inicie una operación de E/S.

algoritmo de entrada desde un disco

Repetir

Orden de lectura;

Repetir

Leer el estado de la controladora;

Si se produce un error

Finalizar el proceso;

Hasta que la controladora esté lista;

Leer la palabra del registro de entrada;

Escribir la palabra en memoria;

Hasta que la operación esté completa.

La unida de control, la memoria y las controladoras están comunicadas mediante los buses Abus y Dbus y las señales Rd (lectura), Wr (escritura), MemRq (selección de la memoria -de cpu a la memoria-) e IoRq (selección de la controladora de E/S -de la cpu a la controladora-).

Para realizar la operación de E/S podrán darse dos casos:

- No existen MemRq ni IoRq: La cpu coloca en el Abus la dirección que identifica a cada dispositivo para seleccionarlo.

- Si existen ambas señales: La cpu activa la señal correspondiente de estas dos para indicar a la memoria o a la controladora que se va a hacer uso de ella.

En el caso de que haya varias controladoras con varios dispositivos conectados a ellas, la búsqueda de dispositivos listos se realizará entre todos los dispositivos existentes. A esta técnica de búsqueda se le llama pooling y tiene dos variedades:

- Que no haya prioridades: Se consultan los dispositivos uno por uno.

- Que haya prioridades: Las comprobaciones de estado se realizan por orden de prioridad. Cuando se encuentra un dispositivo disponible y se le asigna una tarea, en lugar de continuar la búsqueda, ésta vuelve a comenzar desde el primer dispositivo.

Tiempo de latencia: Es el tiempo transcurrido desde que un dispositivo indica que está preparado para la ejecución de una operación pendiente hasta que ésta se termina de ejecutar.

2 - Entrada/ salida con interrupciones.

Una Interrupción es un suceso que hace que la unidad de control de la cpu interrumpa el proceso en ejecución para ejecutar la rutina de servicio de dicha interrupción (rsi). Pueden ser hardware (generadas por un dispositivo físico del sistema) o software (generadas por un programa durante su ejecución para acceder a procesos especiales del sistema).

Cuando la cpu atiende una interrupción que ha recibido, es necesario enviar un acuse de recibo al emisor de dicha interrupción para que deje de enviar señales a la cpu; en las interrupciones hardware esto se puede realizar enviando una señal por una línea de control o puede estar implícito en la rsi mediante el acceso al dispositivo que generó la interrupción.

Cuando se interrumpe la ejecución de un programa mediante una interrupción es necesario salvar el contexto del programa para poder continuar con su ejecución más adelante. El proceso de cambio de contexto puede estar implementado en la rsi que se ejecuta, producido automáticamente por el hardware (la cpu guarda automáticamente el contenido de sus registros), o ser una mezcla de ambos (la cpu guarda algunos registros y el guardado del resto está implementado en la rsi). Se suele tender a crear sistemas que admitan las tres posibilidades anteriores de manera que sea el programa interrumpido o el dispositivo que interrumpe el que decida cual es el método que mejor le conviene. En cualquiera de los tres casos los registros se guardan siempre en la pila del sistema.

El uso de las interrupciones con respecto a la E/S programada presenta dos diferencias principales:

- El cambio de contexto puede estar implementado directamente en la rsi.

- No se necesita esperar constantemente a que el dispositivo indique que está listo, pudiendo mientras tanto continuar con la ejecución de otros programas, ya que cuando se produce una interrupción el sistema no necesita preguntar si el dispositivo ya está listo porque la interrupción lleva implícito este hecho.

El uso de E/S con interrupciones suele generar varias interrupciones durante un proceso de E/S.

En el uso de interrupciones hay que tener en cuenta tres puntos:

Anidación de interrupciones.

Cuando se está ejecutando la rsi de una interrupción puede ocurrir que lleguen otras nuevas, pudiendo optar entre dos opciones:

- No permitir la anidación: Los contextos de los procesos interrumpidos se guardan siempre en la misma posición, por lo que no se puede almacenar más de uno. Lo que ocurre es que cuando es comienza a ejecutar una rsi se deshabilita el uso de las interrupciones, por lo que las nuevas interrupciones que se produzcan tienen que esperar a que termine de ejecutarse la primera.

- Permitir anidaciones: Los contextos de los procesos o rsis interrumpidos se guardan en posiciones consecutivas de la memoria, por lo que una rsi en ejecución puede ser detenida por una nueva interrupción, generando un nuevo cambio de contexto. Hay que tener en cuanta que cuando se está ejecutando una rsi no se debe admitir cualquier interrupción, sino sólo aquellas que sean de una prioridad mayor que la actual.

Determinación del emisor de una interrupción.

Cuando se genera una interrupción la cpu debe saber que dispositivo la ha generado para ejecutar la rsi correspondiente. Existen dos métodos para averiguar el origen de las interrupciones:

- Pooling: Significa escrutinio o encuesta; en él el gestor de interrupciones va consultando una por una cual es la controladora que ha generado la interrupción. La diferencia con la E/S programada está en que antes el programa de escrutinio se ejecutaba cada cierto tiempo para saber que dispositivos estaban disponibles, pero ahora ya se tiene la certeza de que hay un dispositivo disponible, sólo hay que preguntar cual es.

- Vectorización o Interrupciones vectorizadas: Cuando una controladora genera una interrupción coloca en el bus de datos un código de identificación llamado `vector de interrupciones' o `vector de interrupción de la controladora'; este vector identifica a la controladora que ha generado la interrupción, así como la rsi que la controladora desea que se ejecute. Esta información es usada en algunos sistemas para consultar en memoria donde se encuentra la rsi que se tiene que ejecutar, usando el vector como una dirección de memoria de una `lista', el `vector de interrupciones del sistema', donde consultar la posición de inicio de cada rsi; en otros sistemas este vector identifica directamente donde se encuentra el inicio de la rsi, sin necesitar consultarlo en una `lista'.

Los ordenadores basados en Intel y Motorola utilizan el primer método usando una `tabla de vectores de interrupción' para transformar el vector en la dirección de memoria adecuada. El uso de este método facilita que se pueda cambiar la rsi que se asociará a cada interrupción puesto que simplemente hay que cambiar la dirección de la rsi que tiene asignada en esta tabla por la dirección nueva.

Prioridad de ejecución de las interrupciones.

Esto concierne a la prioridad de los dispositivos. Para decidir qué interrupción se atiende hay que tener en cuenta el método que se ha utilizado para determinar qué controladora generó la interrupción:

- Si se ha usado pooling: La prioridad queda establecida mediante el orden en el que se consultan los dispositivos, siendo los primeros los de mayor prioridad.

- Si se ha usado vectorización: Existen dos soluciones:

· Basándose en que todos los dispositivos utilizan una misma línea de interrupción para informar a la cpu de una interrupción. Cuando la cpu recibe una señal por la línea int (interrupción) y la admite, envía una señal por la línea IntAck que está conectada a la controladora más prioritaria; de ella, esta línea está conectada en cascada a las demás controladoras por orden de prioridad, de manera que la señal va siendo transmitida de controladora en controladora hasta que llega a la que ha generado la interrupción, la cual bloquea la transmisión de la señal y coloca el vector en el bus de datos.

· Si hay varias líneas de interrupción, cada controladora dispone de una línea Int e IntAck propia. Si estas líneas están todas conectadas a la cpu, esta será la encargada de determinar la prioridad; pero si la cpu sólo admite la entrada de una interrupción será necesario usar un módulo `Gestor de interrupciones', al que llegan todas las líneas de interrupción y encargándose de seleccionar cual de ellas será la que se envíe a la cpu. Para aumentar el nº de controladoras que pueden usar interrupciones puede haber varios `gestores de interrupciones' conectados en cascada.

El nº máximo de controladoras que pueden usar las interrupciones será igual al nº de líneas int disponibles en el sistema. Para evitar esta limitación se pueden conectar varias controladoras a la misma línea int, conectándose entre ellas en cascada como en el método anterior.

Los gestores de interrupciones deberán tener un mecanismo que determine si se debe atender o no una interrupción, para lo cual deberán contar con un registro con un bit para cada línea de interrupción de manera que cuando éste esté a `1' se permita la selección de su interrupción y viceversa; de esta manera cuando no hay ninguna rsi en ejecución todos los bits están a `1', pero cuando hay alguna rsi activa, si no se permite anidamiento todos los bits estarán a `0', y si se permite anidamiento, se pondrán a `0' los bits de las líneas con una prioridad menor que la de la rsi actual y a `1' los demás.

3 - Entrada/ salida con acceso directo a memoria (dma).

Se basa en el uso del dmac o Controladora de dma, que es un dispositivo encargado de gestionar este tipo de E/S y que puede estar o no integrado en la propia controladora de dispositivo.

Usando el dma el dispositivo tiene un acceso o uso directo de los buses del sistema, pudiendo generar direcciones de memoria y transferir datos sin la intervención de la cpu. La controladora de dma tiene dos registros:

- De direcciones: Posición de memoria desde o hacia la cual se va a efectuar la transferencia; su valor va aumentando de 1 en 1 según va avanzando la transferencia de datos.

- Contador: Nº de bytes que se van a leer o escribir en la memoria principal; su nº se va decrementando según se va realizando la transferencia hasta llegar a 0, finalizando entonces la operación.

Cuando la dmac realice una operación de transferencia de datos requerirá l uso exclusivo de los buses Abus y Dbus, para lo que debe solicitarlos a la cpu; para ello la dmac activará la línea de control BusRq que informa a la cpu de que el dma requiere el uso de los buses, y cuando la cpu conceda el uso de los buses (lo que no ocurrirá antes de que finalice un ciclo de cpu -no de instrucción-) ésta activarla la señal BusAck, que informará a la dmac de que puede comenzar la operación de E/S.

Cuando la operación de dma finalice (de manera normal o por un error) envía una señal por la línea Int que hace que la cpu recupere el control de los buses y continúe con la tarea anterior.

Existen tres métodos para transferir información entre la memoria y los dispositivos usando dma:

- Por bloques: La dmac realiza transferencias de datos bloque a bloque, que no tienen por que ser del mismo tamaño que los datos a transferir. Su tamaño está determinado por el tamaño del búfer de la memoria o de la controladora de dispositivo del que se van a extraer los datos.

- Por demanda: La transferencia puede ser interrumpida en cualquier momento, cuando el dispositivo no admite o envía más datos, para evitar el bloqueo innecesario de los buses. La transferencia durará mientras se mantenga la señal BusRq y cuando la operación se interrumpa el valor de los registros del dmac se mantendrán para poder continuar con la operación más tarde.

- Por robo de ciclos: Cada vez que un dispositivo envía una señal BusRq se producirá un ciclo de dma durante el cual se transferirá información entre la memoria y el dmac, devolviéndose a continuación el uso de los buses a la cpu. Si al finalizar el ciclo de dma la operación de E/S no ha finalizado, la controladora volverá a activar la señal BusRq para volver a solicitar un ciclo de dma, repitiendo el proceso hasta que se terminen de transferir los datos. De esta manera se consigue que la cpu y la dmac utilicen los buses de manera concurrente.

La cantidad de controladoras de dispositivo que pueden usar el dma viene determinada por el nº de canales de comunicación que tenga el dmac. Para aumentar esta cantidad se pueden conectar varios dmac en cascada mediante estos canales.

4 - Entrada / Salida controlada por procesadores.

Algunas controladoras de dispositivo tienen circuitos llamados iop (Procesadores de Entrada/Salida), que aportan un juego de instrucciones de E/S diferente del de la cpu. Un iop va a ejecutar un programa que la cpu habrá colocado en la memoria principal, el cual va a ser el encargado de gestionar la operación de E/S (la cpu solamente inicia la operación)

Los iop deben tener la capacidad para ejecutar pequeños programas, así como para manejar el uso de interrupciones y dma.

La ventaja respecto al uso del dma es que la dmac sólo puede acceder a direcciones consecutivas de memoria, mientras que el iop puede generar direcciones aleatorias de memoria, lo cual es muy útil, por ejemplo, en el uso de la memoria paginada cuando una transferencia debe quedar dividida entre el final de una página y el principio de otra no consecutiva.

SISTEMAS OPERATIVOS I - upsam (1999-2000) - EM Segundo Cuatrimestre

4

1