TECNICAS DE ADMINISTRACION DE RECURSOS EN LOS SISTEMAS OPERATIVOS BIBLIOTECA DE LA UNIVERSIDAD DEL VALLE DE GUATEMALA UNIVERSIDAD DEL VALLE DE GUATEMALA Facultad de Ciencias y Humanidades TECNICAS DE ADMINISTRACION DE RECURSOS EN'LOS SISTEMAS OPERATIVOS LISSETTE DE CARMEN GALVEZ BAIZA Modelo de trabo profesional presentado para optar al grado académico de: Licenciado en Ciencias de la Computación GUATEMALA 1984 (f) Vo. Bo.: (f) • \ Lice~1W.71i1 Pira Asesor Tribunal: (e) --1/2-41 /9 7 '2 c--¿,-7 Fecha de Aprobación: I I A mis queridos padres, Manuel Gálvez Ruiz Gilda Baiza de Gálvez a mis tíos Federico Castellanos Alarcón Catalina Baiza de Castellanos y a mis hermanos Manuel, Aída, Edgar y Livia. PREFACIO La descomposición del sistema operativo en administrado- res de recursos, permite estudiar cada parte del sistema de manera relativamente aislada; dejando de lado los proble- mas de comunicación entre sus diferentes procesos. Esto quiere decir que tanto si estos últimos funcionan de forma estrictamente secuencia] o si lo hacen realmente de forma concurrente entre ellos, las funciones a realizar son las mismas. En este trabajo se ha puesto énfasis en la descripción de cada administrador y de sus elementos más caracterizados sir preocuparse demasiado de la jerarquía de organización y de comunicación entre ellos. También es preciso decir que en un estudio panorámico de este tipo, las descripciones son obli- gadamente breves y que cada elemento del sistema operativo se puede llegar a estudiar con toda la profundidad que se desee. Han quedado fuera de este trabajo partes importantes de los sistemas operativos tales como los monitores de comuni- cación, sistemas de control de rendimiento, soporte o gestión. de Base de Datos y otras; en definitiva, se ha descrito el ix núcleo de los sistemas operativos y se ha considerado que estas partes citadas últimamente, forman una segunda capa de aplicaciones montadas de forma muy estrecha sobre el núcleo del sistema. Tampoco se habla de sistemas operativos concretos ni de conceptos avanzados: máquinas virtuales,' sistemas dirigidos al tratamiento de "objetos", sistemas operativos para sistemas multiprocesadores, etc. Una vez descrito el núcleo riel sistema operativo sería necesario continuar con: - El estudio detallado de los elementos de éste núcleo, enfocando los conceptos mencionados y sus características. - La organización jerárquica, comunicación y concurrencia entre ellos, - Las aplicaciones de segundo nivel enlazadas muy estrechamente a ese núcleo, - Los nuevos conceptos que requieren sistemas operativos con nuevas funciones y/o estructuras. El presente trabajo podrá utilizarse como referencia en los cursos universitarios de sistemas operativos, lo que podría solucionar el problema de un texto adecuado en idioma español. En el apéndice A, se incluye la implementación de un sistema para control del tamaño promedio de particiones, programa que podría utilizarse como base para investigaciones futuras sobre tamaño óptimo de particiones de memoria. En el apéndice E, se enfoca la configuración simulada de un sistema de 'hardware' pequeño, sobre el cual se emula un sistema operativo de tiempo compartido. Todos los progra- mas desarrollados no fueron incluidos, con el objeto de dar solamente los lineamientos y metodología utilizada en el desarrollo del proyecto. Será muy satisfactorio el que este trabajo sea de alguna ayuda para las personas que deseen ahondar en el estudio de los sistemas operativos. xi Deseo agradecer enormemente, al tic. Fabián Pira por sus certeras apreciaciones, I su interés e incondicional ayuda; al Tic. Marcel Reichenbach, por su tiempo y enorme colaboración 1 para la conclu- sión de este trabajo; muy especialmente, a Jaime Hazard, por su invalorable ayuda y apoyo; a Edwin Acevedo y a todas aquellas personas que, en una u otra, forma ayudaron a la realización de este estu- dio. i CONTENIDO Páginas PREFACIO vii I. SISTEMAS OPERATIVOS 1 A. Introducción a sistemas operativos 1 1. Sistemas operativos de procesamiento en lotes. 3 2. Sistemas operativos de tiempo compartido 3 3. Sistemas operativos de tiempo real 4 B. Panorama general y componentes 5 1. 'Hardware' 5 2. 'Software' 11 2.1 CompartiMiento de recur- sos 12 2.2 Otras facilidades de 'software' 14 C. Administrador de recursos 17 1. Funciones. 17 2. Asignación y recuperación de recursos 19 TECNICAS DE ASIGNACION DE PERIFERICOS 21 A. Monitor o supervisor 21 B. Programación de entrada/salida Administrador de Periféricos 22 1. Controlador del tráfico de entrada/salida. 23 Asignación de dispositivos 25 Y 2. 3. Planificador de entpada/salida 4. Activación contínua de los procesos-de entradaYsalida 5. Despachador de la éntrada/sa- lida Páginas 274. 27 31 C. Estructura del ensamblador e instrucciones privilegiadas. 32 1. Papel de los manejadores y pro- gramas de canal 32 3. Rutinas de sorvicio[en la en- trada/salida e instrucciones privilegiadas 34 D. Interrupciones de entrada/salida 38 E. Manejadores y programas' de canal 40 III. TECNICAS DE ADMINISTRACION DE MEMORIA 47 A. Asignación contigua simple 47 1. Conceptos 47 2. Soporte de 'hardware' 48 3. Soporte de 'software' 48 4. Ventajas 49 5. Desventajas 49 B. Introducción a multiprogramación 50 C. Asignación fraccionada 50 1. Conceptos 50 2. Soporte de 'hardware' 52 xív PágiLas 3. Soporte de software 52 - Partición estática 52 - Partición dinámica 53 4. El problema de la fragmentación 57 5. Ventajas 58 6. Desventajas 59 D. Memoria fraccionada relocalizable 60 1. Conceptos 60 2. Soporte de 'hardware' 61 3. Soporte de 'software' 62 4. Ventajas 5. Desventajas 63 E. Paginación 64 1. Implementación de paginación 68 2. Acceso a páginas 70 3. Tamaño de página y fragmentación 72 F. Segmentación 74 G. 'Swapping' y relocalización 76 1. Traslapes 82 IV. ADMINISTRADOR DE PROCESOS 85 A. Definición 85 B. Elementos del administrador de procesos 86 XV Páginas C. Estados fundamentales y transiciones entre procesos. 87 1. Estrategias de selección de procesos 91 D. Comunicación de procesos 93 E. Exclusión mutua. El problema de las secciones críticas. 95 F. Sincronización. Semáforos. 98 V. CONCLUSIONES 101 VI. GLOSARIO DE TERMINOS 103 VII. BIBLIOGRAFIA 109 VIII. APENDICES A. Un sistema de control de rendimiento 111 B. Lineamientos de un Sistema Operativo de tiempo compartido. 133 xvi LISTA DE TABLAS Y FIGURAS Nombre de tabla o figura Página 1.1 Procesador central 6 1.2 'Hardware' básico 9 1.3 Niveles del 'software' 12 2.1 Tabla de nombres simbólicos 25 2.2 Despachador de procesos 29 2.3 Transiciones de los procesos de entrada/salida 30 3.1 Asignación de memoria contigua simple 47 3.2 Asignación particionada de memoria 51 3.3 Comportamiento de la memoria con particiones dinámicas 54 3.4 Memoria particionada relocalizable 61 3.5 'Hardware' de localización dinámica 62 3.6 'Software' de localización dinámica 63 3.7 Direccionamiento de Memoria 65 3.8 División de un espacio de direccionamiento de 64 K 69 3.9 Memoria Virtual de 15 Bits 70 3.10 Mapeo de la memoria para demanda de páginas 72 3.11 Manejo de memoria por traslapes 83 3.12 Asignación de segmentos de traslapes 84 4.1 Estados fundamentales y transiciones entre procesos 89 xvii I. SISTEMAS OPERATIVOS A. Introducción a sistemas operativos La era de la computación electrónica se ha caracterizado por las diferencias en la tecnología de la máquina física ('hardware'), marcando con ello las llamadas 'generaciones'. Actualmente, los avances en conjunto de la máquina física ('hardware'), así como los de los algoritmos diseñados para hacer trabajar ésta ('software'), son los que marcan la actual vertiginosa evolución de las computadoras. El desarrollo de sistemas complejos de 'software', no empezó sino hasta la tercera generación de computadoras. Esto ha sido' motivado por las investigaciones teóricas sobre la asignación adecuada de los elementos del sistema que tienen entidad propia y pueden usarse para un trabajo específico. La organización, protección y control de acceso y uso de estos elementos o recursos del sistema, es uno de los objetivos principales de un sistema operativo. Esta es una colección de algoritmos que trabajan sobre estructuras de datos, para dar al usuario un conjunto de facilidades que simplifiquen los trabajos de diseño, codificación, puesta a punto y mantenimiento de programas. La función principal del sistema operativo es controlar los recursos con el fin de que los usuarios los puedan compartir. Compartir es una idea central en todos los sistemas operativos: compartir implica en muchos casos, 'competir' por el uso de un recurso determinado. Como consecuencia de esto, pueden haber interferencias no deseadas entre las demandas de los usuarios. El sistema operativo protege a usuarios y recursos contra este tipo de interacciones. Por otra parte, compartir también permite en muchos casos, cooperar para hacer un trabajo. El sistema operativo controla esta cooperación, evitando que se trans- forme en interferencia no deseada. De cualquier forma, se puede decir que el sistema operativo es el árbitro que solu- ciona los conflictos que se puedan producir como consecuencia de la competencia y/o la cooperación. Existen diferentes tipos de sistema operativos orientados a aplicaciones específicas, lo que viene a aumentar el rendi- miento del sistema operativo frente a las demandas de servi- cio: A) sistemas operativos orientados a trabajos 'por lotes' ('batch'). B) sistemas operativos orientados a tiempo compartido. C) sistemas operativos orientados a tiempo real. 3 Sin embargo, esta clasificación es, actualmente, más apa- rente que real, ya que hay sistemas operativos en los que se pueden encontrar mezcladas, las características de los tres mencionados anteriormente. 1. Sistemas operativos de procesamiento en lotes: Es una modalidad en donde los trabajos del usuario son sometidos como lotes secuenciales en los dispositivos de entrada y no hay interacción entre un usuario y su trabajo durante el procesamiento. El usuario está completamente aislado de su trabajo y como resultado, el sistema responde con el tiempo delimitante del mismo trabajo. Consecuentemente, el sistema operativo puede seguir una política de administración ('scheduling') relativamente flexi- ble. 2. Sistemas operativos de tiempo compartido: Son sistemas que proveen servicios computacionales para muchos usuarios en línea, concurrentemente; permitiendo a cada usuario interactuar con sus procesos. Este acceso simultáneo es iniciado por el tiempo de procesador y otros recursos 4 compartidos entre varios usuarios, en una forma que garantice alguna respuesta de cada comando del usuario en poces segun- dos. El uso del computador, es asignado a cada proceso del u- suario por un pequeño período de tiiempo (tajada de tiempo), 1 normalmente en un rango de milésimas de segundo; si el proceso su tuno en 1 no ha sido finalizado al final tiempo, éste es interrumpido y permitiendo a otros procesos pequeño período de una cola de espera, la máquina. dei este pueSto en En el apéndice B, se encuentra'la implementación del goritmo principal para la optimización de administración de recursos dentro de un sistema operativo de tiempo compartido. Esta implementación podrá ayudar a la mejor comprensión de los fundamentos de trabajo dentro de un sistema operativo de este tipo en específico. 3. Sistemas operativos de tiempo real: Estos sistemas sirven para manejar procesos externos en línea, que tienen un tiempo estricto de respuesta. Las señales de interrupción provocadas por las órdenes de los procesos externos, producen la atención del sistema; si no son atendidas con prontitud (en microsegundos, milisegundos, o segundos, dependiendo del proceso), el proceso externo es degradado seriamente. 5 Estos sistemas son utilizados para aplicaciones particula- res, por ejemplo, control de procesos. B. Panorama general y componentes La mayoría de los sistemas modernos de cómputo, consisten de una interconección complicada de muchos dispositivos de 'hardware', como procesadores centrales, almacenamiento en disco y unidades de cinta, impresoras, lectoras de tarjeta, etc. Para cubrir la complejidad del manejo de todos estos dispositivos, el sistema proporciona programas, o 'software', que hacen del sistema de 'hardware' un uso más conveniente. Es importante conocer las características básicas de los componentes de un sistema de cómputo, es decir las caracterís- ticas del 'hardware' y del 'software'. 1. 'Hardware' El 'hardware' de un sistema de cómputo está compuesto de una o más unidades de procesamiento central, generalmente llamadas unidades centrales de procesamiento (UCP) o procesadores, las cualés pueden ejecutar instrucciones en len- guaje de máquina; la memoria direccionable del procesador (llamada memoria principal ); y los dispositivos periféricos (llamados comúnmente periféricos o dispositivos de 6 entrada/salida), las cuales proporcionan las facilidades de entrada y salida del sistema y espacio para almacenamiento secundario de información. El procesador consiste de varios registros de longitud fija, para almacenamiento temporal de datos e instrucciones; una unidad de aritmética y de lógica, que ejecuta las instrucciones, una unidad de control y la memoria interna o principal. Registros de longitud fija: registro tem- poral de alma- cenamiento, registro de direcciona- miento de memoria, etc. R l R 2 R 3 R n 1 UNIDAD LOGICA ARITMETICA ■ UNIDAD DE CONTROL MEMORIA PRINCIPAL Figura 1.1 Procesador central 'La memoria principal está dividida en bloques de bits 7 de longitud fija, llamados palabras, generalmente de la misma longitud de los registros. Para cada palabra en memoria, se asigna un nombre, que se conoce como su dirección o localización. Las palabras pueden contener tanto instruc- ciones como datos. Uno de los registros del procesador, el registro de la dirección de instrucciones, contiene la dirección de la próxima instrucción que la unidad de control debe interpretar. Las instrucciones son ejecutadas generalmente en forma secuencial, atendiendo al incremento de las direcciones hasta que una instrucción provoca algún salto a una nueva localización, por medio de la alteración del contenido del registro de la próxima dirección. Los dispositivos periféricos, mueven información entre la memoria principal y algún tipo de almacenamiento o medio de salida, tal como la lectora de tarjetas, discos magnéticos cintas, o impresoras. Los dispositivos difieren según la forma dé almacenar información y el método y velocidad con que los datos van a ser utilizados. Algunos dispositivos, como unidades de cinta magnética y lectoras de tarjetas, son estrictamente secuenciales. Los datos pueden ser procesados solamente como un simple vector, en orden del 'primero que entra, es el primero que sale' (PEPS); así, si por ejemplo queremos usar el décimo 'ítem' de una lista de veinte, 8 deberemos pasar. antes por los nueve primeros. Otros dispositivos de almacenamiento proveen un uso más directo de datos, conocidos también como dispositivos de localización directa. Los tambores y discos magnéticos están organizados como un conjunto de pistas; de tal forma que, si se quisiera accesar una parte de los datos, como el n-ésimo elemento de la m-ésima pista, debido a que las cabezas de los discos pueden cambiarse relativamente rápido de una pista a otra, el promedio de tiempo requerido para localizar un elemento o ítem de datos es considerablemente menor que en el caso secuencial. En todos los dispositivos magnéticos, el promedio de tiempo en que una parte de los datos puede ser movido, una vez estos son localizados (llamado tiempo promedio de transferencia), es substancialmente más rápido que el tiem- po de localización. Esta propiedad de los dispositivos, los hace ventajosos para mover información en grandes bloques. Así, si almacenamos diez palabras en un disco, es mucho más rápido hacerlo en un solo bloque en un solo paso, que el hacerlo a la vez. Para bloques pequeños de datos, el tiempo de transferencia es comparable con el tiempo de localización; el mover las palabras una a la vez es aproximadamente cien veces más lento que moverlas todas a la vez. procesa- dor de ent/sal. (can l) procesa- dor de ent/sal. (canal) unidad de control unidad de control disco impr // lect oro de tor e tos cinta MEMORIA PRINCIPAL } unidad central de proceso procesa- dor de ent/sal. (naral) 9 El rango de velocidad entre los diferentes tipos de dispositivos y su conexión al sistema de cómputo es relativamente uniforme. Las unidades periféricas se conectan a la unidad central de procesamiento, mediante unos dispositivos especiales llamados canales o procesadores de entrada/salida que tienen su propio lenguaje. Figura 1.2 'Hardware' básico La conexión entre el periférico y el canal, se 10 efectúa mediante una unidad de control de dispositivos. Esta unidad es un dispositivo electrónico que acepta órdenes de un canal y provoca que el dispositivo opere en alguna forma, recibiendo de o emitiendo datos al canal; esto es leer o escribir. Cuando un programa inicia una operación de entrada/salida, el sistema recibe el requerimiento, genera el programa de canal necesario y lo envía. Usando la información contenida en el programa de entrada/salida, el canal selecciona el dispositivo y provoca la acción adecuada; por ejemplo, leer de o escribir en un medio de almacenamiento. Después de que la operación de entrada/salida se completa, el canal debe notificar al sistema sobre la finalización del trabajo. Esta notificación se realiza a través de una interrupción de entrada/salida del thardwarei. Una interrupción, es una transferencia forzada del control para atender alguna condición externa al programa que se está ejecutando. La posibilidad de interpretar interrupciones es proporcionada por bits de interrupción especiales localizados en el procesador. Cuando se acepta una interrupción, el procesador central interrumpe lo que está haciendo y salta a la localización de memoria principal que atiende la condición que originó la terrupción. Esta rutina examina, los registros de interrupción para averiguar la razón de la misma. 11 Por ejemplo, una interrupción puede provocarse porque un dispositivo ha terminado su ejecución o porque trató de ejecutar una instrucción ilegal. Entonces se desarrolla la acción adecuada, tal como enviar otra orden al canal o detener el programa. Los canales y el procesador central pueden ejecutar procesos o instrucciones, concurrentemente. En la mayoría de las máquinas, la unidad central de procesamiento es la encargada de decir al canal lo que tiene que hacer. Y las interrupciones son usadas para sincronizar la operación de estos dispositivos independientes. 2. 'Software' El 'hardware' no provee exactamente todas aquellos servicios que son necesarios para los usuarios de sistemas de cómputo. Así, es prácticamente imposible para los usuarios, utilizar eficientemente el sistema sin la ayuda del 'software'. Se puede definir como 'software' el conjunto de programas y datos que almacena un computador y que ponen en uso los servicios del 'hardware'. En él se incluyen programas que no están diseñados para resolver problemas específicos de procesamiento de datos. Son programas que son utilizados para 12 incrementar la producción y mantenimiento de otros programas. USUARIOS programas de aplicación y programas de utilidad facilidades de depuración y editores de textos cargadores(loaders), assemblers y compiladores 1 SISTEMA OPERATIVO máquina física Figura 1.3 Niveles del 'software' 2.1 Compartimiento de recursos Un recurso es cualquier objeto que pueda ser localizado dentro del sistema. Los recursos de 'hardware' son raramente compartidos, en el sentido de que los programas puedan utilizar el mismo recurso simultáneamente. 13 Por el contrario, se dice que está compartido, si varios programas están ejerciendo control sobre el recurso, en un subintervalo de un período de tiempo para cada programa. Por ejemplo, cinco programas pueden compartir igualmente un procesador si a cada programa se le permite ejecutar 1 de cada 5 segundos. Todos los dispositivos de 'hardware' son compartidos en esta forma; sin embargo, la escala de tiempos bajo la cual los programas pueden ejercer control sobre un dispositivo determinado, varía considerablemente. Por ejem- plo, un programa puede utilizar parte de la memoria principal por varios minutos, pero nunca puede ejercer control sobre el procesador por más de un segundo a la vez. Básicamente, existen dos formas de implementar los sistemas compartidos. El primero, es el método descentralizado, en el cual si varios programas quieren compartir un recurso, y si saben de la existencia de cada uno de los demás, entonces pueden cooperar pasándose el recurso entre ellos. En la mayoría de los sistemas, los usuarios no se preocupan de comunicarse con los demás. El segundo, es el método centralizado en el que se carga un programa separado para controlar la utilización de los recursos equitativa eficientemente; así, esos programas no necesitarán cooperar más entre sí, para obtener el recurso que 14 demandan. Cuando esto sucede, el programa requiere únicamente el servicio del asignador de recursos. Las nociones de la asignación de recursos y de los recursos compartidos, son el concepto central de un sistema operativo. 2.2 Otras facilidades de 'software' Los dispositivos periféricos mueven datos a velocidades que son substancialmente más lentas que la velocidad a la que el UCP puede procesarlos. Para evitar que la unidad central tenga que esperar, el dispositivo podría mover los datos a la Memoria principal antes que el UCP los necesite explícitiamente. Cuando la UCP inicia el procesamiento de daos de la memoria principal, el dispositivo va a estar listo para empezar y mantener al procesador ocupado halta que tenga que parar o esperar. En inglés, esta actividad es llamada 'buffering', y el área donde el dispositivo almacena la información avanzada, es llamado 'buffer' o memoria compensadora. e Una técnica muy común de 'buffering' en sistemas de cómputo, es llamada 'spooling'. Generalmente, el procesador obtiene bastante información de la entrada de datos desde una lectora de tarjeltas, pero la lectora es muchísimo más 15 lenta que el procesador. Para compensar esto, las tarjetas son movidas a un pequeño buffer de memoria en disco. De tal forma, el disco actúa como una memoria intermedia o temporal entre el UCP y la lectora de tarjetas, haciendo que el UCP lea las tarjetas del disco. Una técnica similar, puede ser usada para la impresora, utilizando un buffer de salida. El progra- ma que implementa el spooling de datos es una de las partes más complejas que integran un sistema de cómputo. Una de las facilidades más importantes, ofrecidas por un sistema de cómputo, es la traducción de lenguajes por medio de compiladores o traductores, ensambladores e intérpretes. Como otras facilidades de 'software', los traductores de lenguajes pueden interactuar con el sistema cuando están ejecutando. El medio por el cual interactúan el sistema y el traductbr, se llama 'interfaz'. Este requiere un diseño muy cuidadoso. Por ejemplo, el traductor necesita obtener determinados recursos del sistema, tal como un archivo de almacenamiento o una terminal de pantalla. Esto implica que el traductor debe comunicarse con la parte del sistema, que gobierna la asignacion de recursos. Similarmente, si el traductor genera el código de máquina, ese código podría requerir las convenciones del 16 sistema, tal como las reglas para encadenar programas. En conclusión, el interfaz puede ser tan simple y flexible que permita la conexión de una gran variedad de traductores. El área de traducción ha recibido una atención especial de tal forma que este campo ha progresado al punto en que se puede comprar un traductor en la misma forma que los dispositivos de s hardwarel. Una segunda facilidad muy importante provista por los sistemas de cómputo, es la habilidad para manejar una gran cantidad de datos. Los datos son organizados en unidades lógicas llamadas archivos y después almacenados en una for- ma que esté relacionada con su uso. Los elementos que se en- cuentran dentro de un archivo son usualmente llamados regis- tros, los que pueden ser localizados con distintas técnicas dependiendo de cómo están estructurados los archivos. Por ej- emplo, en un archivo estructurado secuencialmente, los regis- tros son localizados en el mismo orden en que fueron almace- nados inicialmente. Un ejemplo de esto podría ser un archivo en cinta magnética. La capacidad de almacenar grandes bloques de datos estructurados, dentro del sistema y por largos perío- dos de tiempo, es de gran utilidad. Los archivos son coloca- dos en almacenamiento secundario y no en memoria principal. 17 Los sistemas de archivos hacen más fácil el compartir los da- tos y, si ellos están bien estructurados, pueden brindar una gran ventaja en la rapidez del tiempo de localización de un elemento arbitrario. El sistema de archivos requiere del uso de los recursos del sistema de cómputo, por lo que éste debe interactuar con el sistema a fin de obtener dispositivos periféricos, almace- namiento en memoria principal y tiempo de procesamiento. Así, el interfaz entre el sistema de archivos y el sistema de cóm- puto requiere el mismo cuidado en el diseño, como el discuti- do en los traductores. Hay una gran cantidad de facilidades de'softwarel que son ofrecidas en los sistemas de cómputo. Los paquetes de subru- tinas matemáticas, las librerías de subrutinas estadísticas y librerías de programas utilitarios como los clasificadores, son agregados para facilitar la conveniente explotación del sistema por muchos usuarios. C. Administrador de Recursos 1.. Funciones Tal como ya se ha dicho en la introducción, un adminis- trador de recursos, a) ha de saber en tOdo momento si dispone del recurso y en 18 que cantidad. b) ha de decidir quién toma un recurso, cuándo conviene que lo haga y qué cantidad toma de él. c) ha de llevar a cabo la asignación del recurso a un proceso que lo pida. d) ha de recuperar el recurso y el proceso lo deja libre. El punto a) lleva a hablar de las estructuras de datos del sistema; tablas, vectores, listas, punteros, colas, etc. El punto b) diseña la estrategia de asignación y utilización del recurso. Los puntos c) y d) llevan a cabo las asignacio- nes decididas én b). Los elementos de b), c) y d) son pues, módulos del siste- ma, implementados con algoritmos que trabajan sobre los datos de las estructuras de a), creándolas, borrándolas o destru- yéndolas, actualizándolas, enlazándolas, y recuperándolas. Estos procesos se activan en diferentes momentos cómo res- puesta a las demandas de servicio de otros procesos del sistema o como respuesta a señales externas (interrupciones). Así los procesos de un administrador pueden trabajar concu- rrentemente con cualquier otro proceso del sistema o del usua- rio. 19 En lo sucesivo, se tratarán las partes o módulos funda- mentales de un sistema operativo, en base a esta descomposi- ción. Se hablará pues de los administradores de procesos, de memoria y de entrada/salida. Es necesario hacer notar que el administrador de procesos tratará de los problemas de los pro- cesos que se asignan a la UCP (procesos de cálculo) dejando que el administrador de entrada/salida maneje los problemas de los procesos especificados. Para una mejor comprensión del trabajo de un administrador de recursos, refiérase al apéndice B. 2. Asignación y recuperación de recursos Mientras se está ejecutando un proceso, hace uso de los recursos del sistema. Conviene identificar tres momentos o situaciones diferentes en los que puede encontrarse un proceso durante su ejecución: - la asignación inicial de un recurso por parte del adminis- trador. - la recuperción final del recurso al acabar el proceso o programa. - la demanda y asignación dinámica de recursos que piden los 20 procesos mientras ejecutan. Los recursos, por razón de su naturaleza, se dividen en dos grupos: 1. aquellos, de uso concurrente que una vez asignados, pueden ser recuperados en cualquier momento por el administrador, que los puede asignar a otro proceso que los haya pedido, recupe- rando después la asignación inicial. Por ejemplo, un disco, una memoria o una unidad central de proceso. 2. aquellos de uso secuencial que una vez asignados a un pro- ceso, el administrador no puede recuperarlos sino hasta que el proceso que los tiene asignados los libera. Por ejemplo una cinta magnética o una impresora. En este último caso, la asignación inicial permanece hasta que se hace la recuperación final. La demanda y la asignación dinámica, permiten una mejor utilización del recurso, pero introducen un grado más de com- plejidad en el diseño de los algoritmos del administrador, por razón de la ya mencionada competencia entre procesos. II. TECNICAS DE ADMINISTRACION DE PERIFERICOS A. Monitor o Supervisor Un sistema operativo típico, tiene un conjunto de programas colectivamente conocidos como 'Su- pervisor ', cuya función es la de proveer los servicios necesarios para supervisar la ejecución de un número de programas del usuario. El control se transfiere al supervisor cada vez que el flujo normal de procesamiento es interrumpido por cualquier cambio. El propósito de una llamada al supervisor es el de proveer un mecanismo que permita al programa, interrumpir el flujo normal de procesamiento y requerir al supervisor el adoptar las medidas necesarias para tratar la condición que dió origen a la interrupción. Las interrupciones al supersivor más comunes, son las de entrada y salida. En un sistema de multiprogramación es esencial tener un sistema de control de dispositivos de entrada/salida, especialmente de aquellos dispositivos compartidos por un determinado • número de programas. B. Programación de entrada/salida y Administración de Periféricos Las funciones básicas del administrador de dispositivos y de entrada/salida son: a.- Conocer el estado de todos los dispositivos del subsistema de entrada/salida; conocer cómo es- tán relacionados y si hay uno o más caminos libres que unan a lbs elementos entre sí, función reali- zada por el controlador del tráfico de entrada/sa- lida. b.- Decidir qué proceso puede utilizar al, dispositivo en función de su clase: dedicado, compartible o virtual; hacer el tratamiento de un tipo concreto de dispositivos, función que rea- liza el manejador del dispositivo. Y de las de- mandas de operación de los programas, las que con- trola el planificador de la entrada/salida. c.- Hacer la asignación de un dispositivo a un proceso o trabajo. 22 d.- Hacer la recuperación del dispositivo. Es preciso explicar qué se entiende por clase de dispositivo: a.- Un dispositivo dedicado es un dispositivo que se asigna a un trabajo mientras dura; por ejemplo una cinta, una impresora, etc. b.- Un dispositivo compartido es un dispositivo que puede ser utilizado concurrentemente por más de un proceso; por ejemplo un disco. c.- Un dispositivo virtual es un dispositivo que se implementa sobre otro a nivel de software. Por ejemplo un dispositivo determinado puede convertirse en virtual, implementándolo sobre disco, como sucedería con impresoras y lectoras de tarjetas virtuales. 1. Controlador del tráfico de entrada/salida Si desde un proceso se pide realizar una ope- ración de entrada/salida sobre un dispositivo, tiene que existir necesariamente un camino a 23 24 través del subsistema de entrada/salida para lle- gar a él, en el sentido de que el dispositivo tiene que estar conectado a una unidad de control. Esta a su vez, deberá estar conectada directamente a memoria a través de una línea para transmitir datos o bus de datos; o bien a través de un proce- sador especializado de entrada/salida, canal. El controlador de tráfico por tanto tiene que saber: - Si hay un camino libre para servir al requerimiento de entrada/salida. - Si no existe el camino, saber si hay alguno alternativo. El controlador del tráfico mantiene actualizadas las tablas, los punteros y los bloques de control necesarios de la unidades que gobierna. En cualquier momento los procesos del planificador de entrada/salida y los manejado- res de dispositivos, tienen que poder consultar a estas tablas t En la Figura 2.1, se indica cómo están forma- dos los bloques de control por punteros a otros bloques y por punteros a colas de procesos de en- E; l ú L.1 07-1 7- C A DE LA UNIVERSIDAD DEL VALLE DE GUATEMALI 25 trada/salida que están esperando la terminación de la operación que tiene ocupado a algún elemento del subsistema de entrada/salida. El planificador de entrada/salida trabaja sobre estas colas. "NOMBRE" Tabla de nom- bres simbólicos Identificador del dispositivo • Estado del dis- positivo Lista de unidades de control conec- tadas Lista de proce- sos de E/S espe- rando el dispo- sitivo Tabla de bloques de control Identificador de la unidad de control Estado de la unidad de control Lista de dispositi- vos conectados Lista de procesado- res conectados Lista de procesos esperando la unidad de control Conjunto de blo- ques de control de las unidades de control Identificador del procesador Estado del proce- sador Lista de las uni- dades de control conectadas Lista de procesos de E/S esperando a que el procesador esté libre Conjunto de blo- ques, de control de lou procesa- dores especializa- dos de E/S Figura 2.1 Tabla de nombres. simbólicos 2. Asignación de dispositivos El hecho de asignar una unidad lógica o simbólica definida por el programador, a una unidad física, no es nada más que hacer corresponder el nombre simbólico con el bloque de control del dispositivo concreto; tal como se indica en la figura anterior. La asignación de unidades simbólicas a unidades físicas se hace normalmente al empezar un trabajo, y es cuando las rutinas de asignación: - Comprueban si existe un camino hasta el dispositivo. - Intentan hacerlo con un dispositivo del mismo tipo'que esté libre, en caso se quisiera hacer la asignación de un dispositivo dedicado, que ya está ocupado, porJ ejemplo, otra cinta, o bien, si no se consigue,¡abortan o suspenden la ejecución del programa. Una vez hecha la asignación, una orden de en- trada/salidaldirigida a un dispositivo concreto sigue el camino definido por los punteros de los 1 bloques de cOntrol. 26 27 3. Planificador de entrada / salida Si imaginamos que todos los requerimientos de entrada/salida se sitúan en una cola, el primer trabajo del planificador es ordenarla y hacer la gestión de las nuevas órdenes que llegan y de las que se han de borrar una vez atendidas. En los sistemas con múltiples caminos, el pla- nificador trabaja con la información del controla- dor de tráfico para decidir el camino del requeri- miento de entrada/salida. Una vez decidido, el planificador puede pasar el requerimiento a las colas de los elementos que lo forman. Desde un punto de vista conceptual, el planificador ha creado el entorno de datos del proceso de entra- da/salida. 4. Activación contínua de los procesos de entrada/salida Ya se ha mencionado el hecho de que los procesos de entrada/salida son concurrentes con los de cálculo. En definitiva podemos tener un proceso de cálculo asignado a la UCP , y diferentes procesos de entrada/salida trabajando para diferentes procesos de cálculo que están es- perando ser ejecutados. Para mantener el máximo grado de paralelismo, se han de ejecutar tantos procesos de entrada/salida como sea posible. Desde un punto de vista global, se tiene que intentar que el sistema operativo mantenga la máxima actividad de los procesos de entrada/sali- da, mientras haya requerimientos en la cola. El administrador de entrada/salida y de dispositivos ha de intentar servir los requerimientos, despa- chando los procesos de entrada/salida correspon- dientes, tan pronto y tan frecuentemente como les sea posible. El funcionamiento es el siguiente: después de situar el requerimiento en la cola, se intenta despachar el proceso de entrada/salida asociado. Tanto si se puede hacer como si no, porque el ca- mino está ocupado, se devuelve el control. Esta estrategia justifica el ejemplo en el que una vez cálculo jando: solicitada la entrada/salida el proceso de que la ha pedido, puede continuar traba- 28 proceso de cálculo en espera hacia el proceso de cálculo que ha pedi- do la e/s 29 Figura 2.2 Despachador de procesos • La bifurcación de la transición 6 indica el hecho de que se intenta despachar el proceso de entrada / salida y, tanto si se puede como si no, se retorna el control directamente al proceso de cálculo del usuario. La terminación de la operación provoca una serial que hace que se pase el control al administrador de entrada y salida. Este borra el requerimiento ya satisfecho de la cola ( destruye el proceso ), provoca la transición 3, da servicio al próximo requerimiento de la cola y pasa el control al planificador de procesos. Para clarificar lo anterior podemos observar el siguiente gráfico: 30 acabado final del trabajo ; rocesos le els e espera 5 el requerimiento hacia el de e/s se pone en proceso la cola de cálcu- lo asocia- do a la e/s planificador de e/s interrupción: final de la e/s se saca de la cola el próximo reque- rimiento de e/s y se ejecuta el pro- ceso correspondiente 6 proceso e/s en ejecución EJECUCION 2 planifica- dor de procesos preparado se pone el pro- ceso en la cola de espe?z, ¡espera.' se saca el pro- ceso de l'a' cola de espera Figura 2.3 Transiciones de los procesos de entrada/salida 5. Despachador de la entrada/salida El trabajo del despachador de entrada/salida es iniciar el subsistema de entrada/salida. Esto lo hace cargando los registros 'hardware' de los procesadores de entrada/salida con datos del pro- ceso de entrada/salida que quiere iniciar o bien cuando se trata de un sistema que utiliza canales, cargando la dirección de inicio, al programa de canal como se verá más adelante, al tratar sobre manejadores y programas de canal. En cualquier caso se pasa la información siguiente: - Dirección del área de entrada/salida - Número de bytes a leer o escribir - Tipo de Lperaci• ón (lectura, escritura o control). 31 - Información de control. Si la op¿ración se inicia correctamente de- • vuelve el control de entrada/salida o de lo con- trario realiza el análisis y el tratamiento de error. C. Estructura del Ensamblador e instrucciones privilegiadas 1. Papel de los manejadores y programas de canal En secciones anteriores se ha hablado de órdenes de entrada/salida que llegan al sistema operativo desde procesos de cálculo, diciendo sencillamente que se pedía servicio al sistema operativo para ejecutarlas. Desde el punto de vista del programador que está programando entra- da/salida en un lenguaje de bajo nivel, ésto se traduce en reservar espacio para bloques de con- trol, de preparar secuencias de órdenes de opera- ción, para después pedir servicio al sistema ope- rativo con el objeto de realizar las secuencias de operaciones deseadas. Las secuencias de operaciones descritas anteriormente, constituyen un 'programa' en el sentido de que los procesadores especializados de entrada/salida aceptan e interpretan adecuadamen- 32 33 te esta secuencia de órdenes. En el caso de sis- temas con canales, la secuencia de órdenes se co- noce con el nombre de 'Programa de Canal'. Cualquier orden de operación lleva asociada información de: - El tipo de operación a realizar (leer, escribir, de control). - La unidad lógica en la que se realizará la ope- ración. - La variable de control asociada a la terminacion de la operación. - La dirección del área de datos. - La longitud de bytes a transferir. - La dirección de un bloque de control donde se recoge la información obtenida por el proceso de entrada/salida. Una terminada la operación, el programador ¡tiene que preparar rutinas para 34 hacer el análisis y el tratamiento de las condiciones producidas. En resumen, la obtención de un registro de datos se tiene que programar con una secuencia de órdenes de entrada/salida y de instrucciones que constituyan el método de acceso correspondiente a la estructura de datos del archivo. Para una mis- ma aplicación, donde los parámetros de los datos (longitud, formato, etc.) son idénticos,éstas se- cuencias se pueden agrupar, lo cual constituye los fundamentos de las rutinas de servicio de entrada /salida. 2. Rutinas de servicio en la entrada/salida e instruc- ciones privilegiadas Si trabajan con un tipo determinado de estructuras de datos, es evidente que los algoritmos de ingreso al archivo que los contiene serán siempre los mismos; es decir, dada la de leer, necesidad un archivo, correspondientes los mismos. ' La parámetros tales escribir, localizar y extender los algoritmos de acceso a una misma organización, serán única diferencia será debida a como la longitud del registro, el 35 factor de bloqueo, el formato, etc. Las rutinas de servicio a la entrada/salida forman parte del 'software' proveído por el fabricante de la má- quina; en su núcleo central preparan secuencias de órdenes de entrada/salida y hacen el análisis y el tratamiento de algunas de las condiciones de terminación de una operación. Estas secuencias corresponden a algoritmos concretos de acceso a datos estructurados según una determinada organi- zación: secuencial, al azar, por niveles deíndice, etc. Sin querer ser exhaustiva, dan servicio para: - Agrupar y desagrupar registros en bloques. - Facilitar el acceso a registros lógicos independientemente del tamaño del registro físico: - Implementar los algoritmos de acceso en datos organizados dentro de índices. - Añadir mantener información de control necesaria para implementar diferente formato de datos( fijo, variable, etc.). , - Implementar la entrada/salida sobre áreas alternas o doble área de entrada/salida. - Preparar y modificar secuencias de órdenes de entrada/salida y pedir servicio al supervisor para hacerlas. - Implementar acciones concretas en caso de errores. - Llevar control del número de registro, leídos o grabados. - Añadir, sacar o interpretar caracteres de control. La información que utilizan las rutinas de servicio en la entrada/salida está relacionada con la definición' de la estructura del archivo y de las características del dispositivo que los__ contiene. Asfi, las rutinas de servicio citadas trabajan con' la información de un bloque de control o bloque de definición del archivo que tiene información de: 36 - El tipo de, registro (fijo, variable, etc.). 37 - La longitud del registro (número de bytes). - El factor de agrupamiento. - El tipo de organización del archivo. - Los parámetros y las estructuras necesarias para localizar a los registros de datos: áreas de índices, claves, etc. - Las direcciones de rutinas de tratamiento de casos especiales. - La unidad lógica y el nombre simbólico del archivo. - El número de áreas de entrada/salida que se utilizan. El tipo de ingreso al archivo ( secuencial, al azar, etc..). - Los derechos de ingreso al archivo: claves de protección y forma de llegar a ellas. - La posición de principio del archivo dentro del volúmen. - La posición del bloque físico dentro del archivo. - Los códigos especiales dependientes del dispositivo. - Las características físicas del dispositivo. La mayoría de estos datos se fijan al momento de programación; esto quiere decir que un programa quede preparado para trabajar con archivos con características bien definidas. En ciertos sistemas operativos, se permite que el usuario defina o modifique algunos parámetros del archivo en el momento de la asignación inicial o que pueda definir y utilizar archivos independien- tes del dispositivo que los contiene. D. Interrupciones de entrada/salida Un procesador de entrada/salida comunica a la UCP que ha terminado su trabajo, provocando una interrupción. Las diferentes unidades del sub- sistema de entrada/salida no terminan la operación simultáneamente; en una arquitectura con canales, 38 39 esto permite liberar el canal y/o la unidad de control mientras todavía trabaja el dispositivo de entrada/salida, permitiéndo una mejor utiliza- ción de los elementos físicos del subsistema. Los algoritmos de tratamiento de la entrada/salida son, en estos casos, muy dependientes de la arquitectu- ra de entrada/salida. En sistemas con canales, cualquier interrup- ción, retorna al administrador del canal, que es el elemento de software que se encarga de las par- ticularidades del funcionamiento de cada tipo de canal concreto (multiplexor, selector, canales es- pecializados para cinta, etc.), y que aplica la mejor estrategia de servicio del canal a los dis- positivos que están conectados a él. En cualquier caso, tanto en una arquitectura como en la otra, los manejadores de canal o de dispositivo se tienen que preocupar de cumplir con la premisa general que se ha dicho antes, e iniciar otra operación de entrada/salida tan pronto como haya libre un camino. Por eso, una vez atendida la interrupción, piden al planifica- dor de entráda/salida la siguiente operación y despachan elproceso de entrada/salida correspon- diente. E. Manejadores y Programas de Canal El organizador de dispositivos ('driver' o 'device handler') generalmente se refiere al módulo del sistema operativo que se encarga de controlar un dispositivo específico de entrada/ salida. El administrador recibe las direcciones y los punteros correspondientes a las estructuras de datos que pertenecen al proceso de entrada/salida a ejecutar. En sistemas con canales, el manejador de dispositivos trabaja a un nivel más alto que el de canal. En este punto, conviene definir un término que se relaciona estrechamente con los manejado- res de dispositivos, los dispositivos virtuales. Este concepto se utiliza para referirse a aque- llos recursos que aparentan existir pero que real- mente no exilten. Tal es la aplicación para los dispositivos de los que se simula su existencia. 40 Las funciones de un manejador de dispositivos se podrían resumir en: - Traducción e interpretación de las órdenes los parámetros de la entrada/salida (preparando un programa de canal en el caso de arquitecturas que los posean). - Traducción e interpretación de los caracteres de controles enviados (espaciado, tabulación, saltos de páginas, etc.) - Optimización del acceso al dispositivo. Por ejemplo el organizador de disco puede reordenar la cola de mandos de entrada/salida en función de diferentes estrategias: minimización de la distan- cia que ha dé desplazarse el brazo, movimiento li- neal y constante del brazo hacia adelante, mini- mización de rotaciones desaprovechadas con la ayuda de dispositivos físicos de identificación de la posición rotacional, ,duplicación de registros de datos en diferentes lugares del disco, etc. - Encadenamiento de órdenes sucesivas para obtener, de Hin dispositivo, un número de bytes mayor que su, unidad básica de grabación (por ejemplo sectores de 256 o 512 bytes); para leer una cierta Cantidad de bytes, el sistema tendrá 41 y que leer uno o más sectores. Este tipo de organización simplifica el diseño de las unidades de control, pero introduce una complicación en el'software'. Otras arquitecturas permiten una lectura de todos los sectores como sea preciso sin intervención del 'software' entre cada lectura de sectores. - La implementación de dispositivos virtuales cambiando el proceso de entrada/salida sobre el dispositivo a virtualizar por un proceso equiva- lente sobre un dispositivo compartible. El siste- ma operativo prepara el retorno de datos de entra- da/salida de manera que el manejador del disposi- tivo compartible pueda arrancar el proceso de entrada/salida correspondiente (por ejemplo, la direcCión del disco donde escribir una línea o leer una tarjeta). Este concepto se utiliza para hacer la operacíon simultánea de dispositivos donde hay cuatro procesos: uno de lectura de tar- jetas y lectura y escritura en disco; uno de lec- tura de disco y escritura de líneas sobre im- presora; uno de conversión de una demanda de lec- tura (sobre lectora) en' una demanda de lectura sobre la correspondiente lectora virtual en disco 42 43 y uno de conversión de una demanda de escritura de una línea de impresora sobre la impresora físi- ca a una escritura sobre una impresora virtual, simulada sobre disco. Los dos primeros procesos son los encargados de preparar los datos para las lectoras virtuales y para sacar los resultados de las impresoras virtuales. La simulación es com- pletamente inadvertida para el programa y para el programador. - El tratamiento y la recuperación de errores del dispositivo, pasando la información 1 correspondiente a los bloques de estado del dispositivo. - Pasar información al usuario para indicar la terminación Ae la operación de entrada/salida o condiciones del dispositivo; final de tarjetas, registro no encontrado, error no recuperable, etc. servicio de preservar lo más posible la integridad y . 1 coherencia dé los archivos. Esto puede implicar el escribir directorios o no emprender ninguna acción, dependiendo del tipo de dispositivo.1 - Dar en caso de fallo de potencia a fin - Tratar la condición de "operación no atendida" al cabo de un cierto período de tiempo. La acción del organizador puede ser avisar continuamente al operador del sistema o abortar el trabajo. En el caso de arquitecturas de entrada/salida sin canales, los organizadores, ademas, hacen: - El 'software' de multiplexor para dispositivos lentos a base de transferir cada vez un byte de datos desde los registros'hardware'de la interfase a las areas de entrada/salida del usuario. - El, tratamiento de interrupciones una vez enmascaradas éstas, (a base de aumentar la prioridad de la UCP frente a la de interrupciones de dispositivos ), y hecho el tratamiento correspondiente, el manejador baja su prioridad, se constituye en un proceso de sistema y se pone a la cola junto con otros procesos del mismo tipo. Todos ellos se ejecutarán de forma estrictamente serial, pero serán prioritarios frente a los procesos del usuario. 44 - Despachar la operación de entrada/salida a 45 base de preparar los registros correspondientes de la interfaz con el 'hardware'. Para poder realizar: todas estas funciones, los manejadores usan rutinas de servicio del ejecutivo para hacer cosas tales como: - Comprobar qué áreas de entrada/salida pertene- cen al espacio de direcciones del programa que ha pedido la entrada/salida. Hacer la traducción de direcciones virtuales a direcciones físicas, Hacer un primer tratamiento de una interrupción de fin de la entrada/salida, Asociar una interrupción a un proceso, - Sacar una demanda de entrada/salida de la cola (pidiendo servicio al planificador de entrada/sa- lida), - Mover un byte desde la interfaz 'hardware al área del usuario, - Transferir información desde el S.O. al espacio de direcciones del programa. III. TECNICAS DE ADMINISTRACION DE MEMORIA. A. Asignación contigua simple 1. Conceptos: La asignación contigua simple es una técnica usada en minicomputadores con un sistema operativo simple, donde no existe multiprogra- mación, y existe una correspondencia uno a uno entre un usuario, un trabajo, un paso de un trabajo y un proceso. sistema operativo disponible para el trabajo del usuario Ien P uso libre ara asi- gna- dein Figura 3.1. Asignación de memoria, contigua simple 2. Soporte de 'hardware' Esta técnica de manejo de memoria no requiere un 'hardware' especial. Podría requerir únicamente un sistema de protecciones para evitar el acceso al • sistema operativo. 3. Soporte de 'software' Es necesario un 'software' muy sencillo con el objeto de asignar la memoria. Este proceso es llevado a cabo por un algoritmo llamado por el 'planificador' de trabajos del administrador de procesos, que tiene la estructura siguiente: ALGORITMO: 1. [ verificación de espacio ] es el tamaño del trábajo ±= que el espacio disponible en memoria principal ? si ° 2 no ° 4 2. [ asignación de espacio ] Asigne la memoria al trabajo . 48 49 Cargue y ejecute el trabajo. 3. [ fin de proceso ] al finalizar el trabajo desasigne la memoria y encuentre otro trabajo a correr. Regrese a paso 1. 4. [ mensaje de error imprima ' el trabajo no puede correr 5. [ fin STOP 4. Ventajas - No hay necesidad de mantener un direccionamiento de la memoria ya que toda ella es asignada a un solo trabajo. - Simplicidad en el sistema operativo, lo que implica poco uso de la memoria principal. - Fácil entendimiento del uso del sistema. - No hay problema de planificación de traba- jos. 5. Desventajas 50 - La memoria no es totalmente utilizada. - Un gran porcentaje de tiempo del UCP espera por algún requerimiento de entrada/salida, lo que hace que se degraden, tanto el procesador, como la memoria. - Poca flexibilidad en cuanto a la relación de los programas con el tamaño de la memoria principal disponible. B. Introducción a la multiprogramación El operar más de un trabajo a la vez y distribuir los recursos entre estos trabajos, es en lo que consiste la multiprogramación. Esta en sí es un técnica que permite la ejecución de dos o Más procesos concurrentes. El tiempo de espera de entrada/salida se reduce, in- crementando el grado de multiprogramación. C. Asignación particionada 1. Conceptos En la asignación particionada la memoria principal es dividida en regiones separadas de memoria o particiones de memoria. A cada 51 partición se la puede asignar un trabajo diferente. Con esta técnica se debe mantener el estado de cada partición, cuáles están libres y cuáles ocupadas, quién tiene cada partición (esto es manejado por el planificador de trabajos). { { { sistema operativo } trabajo 1 I trabajo 2 trabajo 3 parti- ción 1 parti- ción 2 parti- ción 3 7 M Figura 3.2 Asignación particionada de memoria Un problema específico de la asignación particionada de memoria, es tratado en el apéndice A de este trabajo. Allí se enfoca el caso particular del tamaño óptimo de las par- ticiones de memoria. 2. Soporte de 'hardware' Se requiere un mecanismo de protecciones para prevenir que un trabajo caiga sobre el sistema operativo o sobre otros trabajos. 3.3.3 Soporte de 'software' Partición estática: En esta particiones, de algún forma la memoria está dividida en antes de cualquier procesamiento trabajo. Así, cada trabajo debe especificar la mayor cantidad de memoria que necesitará. La partición que pueda contener el trabajo, le es asignada. 52 es apropiada cuando el Esta técnica 53 tamaño y la frecuencia de los trabajos es conocida. De esta manera, el tamaño de las particiones corresponden a los tamaños más comunes de los trabajos. Sin embargo, esta técnica no es aplicable cuando el tamaño y la frecuencia de los trabajos se desconoce o es muy diversa. Partición dinámica: En esta modalidad, las particiones son creadas durante el procesamiento de un trabajo, haciendo corresponder el tamaño de la partición al tamaño, del trabajo. Se crea una tabla para mantener el estado' de las particiones libres o no asignadas y otra para mantener el estado de las particiohes ocupadas con sus respectivas localizaciones y longitudes. En la siguiente gráfica podemos observar el comportamiento de la memoria trabajando con particióh dinámica: 54 O K 312 K 328 K 376 K 408 K 536 K 1024 K sistema operativo trabajo 1 (16 K) trabajo 2 (48 K) libre (32 K) trabajo 3 (128 K) libre (483 K) O K 312 K 328 K 376 K 400 K 408 K 536 K 664-K 920 K 1024K sistema operativo trabalo 1 trabajo 2 trabajo 4 libre trabajo 3 (128 K) trabajo 5 (128 K) trabajo 6 (256 K) libre (104 K) O K 312 K 328 K 376 K 400 K 536 664 920 1024 sistema operativo trabajo 1 (16 K) libre (48 K) trabajo 4 (24 K) libre (136 K) trabajo 5 (128 K) trabajo 6 (256 K) libre (104 K) Figura 3.3. Comportamiento de las memorias_ con particiones dinámicas. Se observa en a) que existen 2 espacios disponibles, los cuales son asignados en b), a un trabajo 4, sobrando 8k de memoria 55 disponible y a los trabajos 5 y 6, sobrando 104K de memoria disponible. Cuando porciones de memoria son desasignadas, sucede lo que se observa en c): las particiones libres contiguas se unen. Para' la asignación de particiones en la forma dinámica, existen 2 algoritmos principales: a) La primera que encaja ('first fit') b) La que mejor encaja ('best.fit') a) La primera que encala ('first fit') En este algoritmo la tabla de particiones libres es ordenada según la localización en memoria, de las particio- nes libres. Así, al querer asignar una partición, se observan las áreas libres que se encuentran en las localizaciones más bajas de memoria y se va observando en las siguientes, hasta encontrar la primer área libre, lo suficientemene grande para encajar con la partición requerida. 56 Ventajas: 1. Generalmente es suficiente buscar en la mitad de la tabla la partición adecuada. 2. Utiliza las áreas libres localizadas en las direcciones más bajas de memoria, siempre que sea posible. b) La mejor que encaja ( 'best fit' ) Esta técnica ordena la tabla de áreas libres por el tamaño de las particiones. De esta forma la primer área encontrada, cuyo largo¡ es lo suficientemente grande para la partición deseada, será la que mejor encaja. Ventajas: 1. En promedio, el área libre que mejor encaja puede ser encontrada buscando en la mitad de la tabla solamente. • 2. Si existe un área libre de exactamente el tamaño requerido, ésta será seleccionada, lo cUal no sucede necesariamente en la técnica de la primera 57 que encaja. 3. Si no existe un área libre de exactamente el tamaño deseado, la partición es colocada en el área libre mas pequeña y no destruye algún área libre muy grande que pudiera ser requerida posteriormente. Desventajas: 1. El mayor problema con el algoritmo de mejor encaje es que, generalmente el tamaño del área libre asignada, no es exactamente del tamaño requerido y es necesario dividirla en dos partes. Debido al criterio de mejor encaje, el área libre resultante es a menudo tan pequeña que generalmente ya no puede ser utilizada. En consecuencia, al utilizar esta política, se obtiene un gran número de áreas libres muy pequeñas en lugar de un área libre grande, 4. El problema de la fragmentación La fragmentación es el desarrollo de un gran número de pequeñas áreas libres separadas. Un método que podría ayudar a minimizar el problema de la fragmentación, en la asignación particionada de memoria, sería la cuidadadosa selección del algoritmo a utilizar. Para cada uno de los algoritmos discutidos (partición estática, dinámica 'first fit' y dinámica 'best fit') existen situaciones en donde su uso va a ser más apropiado y otras en donde lo será menos. De tal manera, una situación particular será considerada como mala para un algoritmo dado, si no puede satisfacer un requerimiento inmediatamente. Otro método que puede decrementar el problema de la fragmentación, es la asignación múltiple de particíones. En este m¿todd, un trabajo consiste de varias porciones de memoria separadas, que pueden ser subrutinas y arreglos de datos. Cada porción individual va a estar lógicamente contígua a la anterior, pero su localización física en memoria, no será necesariamente contigua. 58 5. Ventajas 59 1. Facilita la multiprogramación, pues hace más eficiente la utilización del procesador y de los dispositivos de entrada/salida. 2. No requiere un 'hardware' especial costoso. 3. Los algoritmos usados son simples y fáciles de implementar. 6. Desventajas 1. La existencia de la fragmentación. 2. Si la memoria no se fragmenta, las áreas libres' podrían no ser lo suficientemente largas para una partición. 3. Requiere mucho más memoria que el sistema de asignación contigua simple. 4. La partición de un trabajo, está limitada al tamaño físico de la memoria. D. Memoria particionada relocalizable 1. Conceptos: Una solución obvia para el problema de la fragmentación es combinar periódicamente todas las, áreas libres en áreas contíguas. Esto podría ser hecho, moviendo los contenidos de todas las particiones asignadas, para que permanezcan contiguas. Este proceso es conocido como compactación o recompactación, si en un proceso es hecho varias veces. Es muy difícil mantener un programa corriendo correctamente después de la compactación, pues existen varios parámetros de dirección que deben ser alterados, como los registros base, las instrucciones de referencia a memoria, listas de parámetros y las estructuras de datos que utilizan apuntadores de dirección. Es por ello que se utilizan los mapas dé memoria que mantienen el espacio de dirección de un trabajo, que no será el mismo de las direcciones físicas de memoria utilizadas. 60 61 O K 312 K 344 K 408 K 424 K 552 K O'K 312 K 344 K 400 K 464 K 496 K 512 K 1024 K sistema operativo trabajo 1 (32 K) libre (56 K) trabajo 4 (64 K) libre (32 K) trabajo 5 (16 K) libre (512 K) estado inicial sistema operativo trabajo 1 (32 K) trabajo 4 (64 K) trabajo 5 (16 K) libre (600 K) sistema operativo trabajo 1 (32 K) trabajo 4 (64 K) trabajo 5 (16 K) trabajo 6 (128 K) libre (472 K) O 312 I 344 K 408 424 1024 1024 K despues de la despues de asignar compactación una partición al trabajo 6 Figura 3.4. Memoria particionada relocalizable. 2. Soporte de 'hardware' Se requiere un soporte especial de 'hardware'. Para efectuar una compactación adecuada, se podrián requerir 2 bits más por cada palabra de memoria, con el objeto de especificar el tipo de dato que se almacena. Sin embargo, esto aumentaría el tiempo de compactación pues se tendrían que examinar los 2 bits de cada palabra. Otra forma de implementación del 'hardware', podría dirección efectiva 320 K registro base de relocali- zación 352 K partición TRABAJO X. 015571 376 K espacio de direccionamiento de TRABAJO X. memoria física 62 ser el utilizar la localización dinámica, que consiste en agregarle a la dirección relativa, el contenido de un registro base de relocalización. Este último registro contendría el desplazamiento que han sufrido los datos, después de una compactación, en relación a su posición inicial. 3. Soporte de 'software' El soporte de 'software' radica en algoritmos tan sencillos como el que se ejemplifica a continuación. se requiere asignar una partición de tamaño XK no es posible asignar una partición en este momento existe a.11una áreá libre tamaño es 1a suma de` todas árlas librs XK se asigna la parti- ción y se actuali- zan las tablas, .„1,1 compactación de memoria y actualización de tablas correspondiente- mente 63 regreso número de partición Figura 3.6. 'Software' de localización dinámica 4. Ventajas - Elimina la fragmentación y hace posible asignar más particiones. - Permite un alto grado de multiprogramación que provoca un incremento en la utilización del procesador y de la memoria. 5. Desventajas 64 - La implementación de 'hardware' para la relocalización, puede disminuir la velocidad y aumentar el costo del computador. - El tiempo de compactación puede ser substancial. - Parte de la memoria puede seguir desperdiciándose si la cantidad de área libre es menor que el tama- ño de la partición requerida. - La. memoria puede contener información que nunca va \ a ser utilizada. E. Paginación Una. idea para ayudar a eliminar la fragmentación, fue la de separar los conceptos de espacio de dirección y las localizaciones de memoria. Si consideramos • como ejemplo, una computadora con un campo de dirección de 16 bits en sus instrucciones y 4096 palabras de memoria, un prdgrama en esta computadora podría dirigirse a 65,536 palabras de memoria; la razón es que 65,536 direcciones existen. El número de direcciones de las palabras de un computador, depende solamente del número de bits de que dispone el registro de dirección y puede no estar relacionado con el número de palabras disponibles en memoria principal. memoria principal 4095 direc- ciones 65 La, idea de separar el espacio de direcciones y las direcciones de la memoria propiamente dichas, se podría plantear como sigue: En cualquier instante del tiempo, 4,096 palabras de memoria pueden ser directamente localizadas, pero no necesariamente deben responder a las direcciones O a 4,095. Se podría, por ejemplo decir a la computadora que a partir de la dirección 4,096 en adelante, utilizará de la dirección O en forma ascendente, de tal forma que cuando la dirección 8,191 fuera referida, se utilizaría la palabra de memoria 4,095; en otras palabras hemos equiparado el espacio de direcciones a las direcciones de memoria rea- les. espacio de direcciones. Figura 3.7. Direccionamiento de memoria 66 En términos de este dibujo de direcciones trazadas, del espacio de direcciones a las localizaciones de memoria reales, una máquina de 4 k sin memoria virtual, simplemente tiene un diagrama arreglado entre las direcciones O a 4,095 y las 4,096 palabras de memoria. Una pregunta interesante es: qué pasa si un programa salta a una dirección entre 8,1:92 y 12,287 ?. En una máquina sin memoria virtual, el programa provocaría un error que imprimiría un mensaje de 'MEMORIA REFERIDA INEXISTENTE' y terminaría el programa. En una máquina con memoria virtual, la siguiente secuencia de pasos ocurriría: 1. Los contenidos de la memoria principal serían salvados en la memoria secundaria. 2. Las palabras 8,192 a 12,287 serían localizadas en memoria secundaria. 3. Las palabras 8,192 a 12,287 serían cargadas a la memoria principal. 4. El mapa de direcciones sería cambiado a un mapa de direcciones 8,192 a 12,287 sobre las localizaciónes de memoria O a 4,095. 5. La ejecución continuaría como si nada raro hubiese sucedido. Esta técnica es llamada PAGINACIÓN y los trozos de programas leídos en la memoria secundaria son 67 denominados páginas. También es posible encontrar direcciones reales del es- pacio de direcciones, de una forma más compleja. Para enfa- tizar, llamaremos a las direcciones que el ; programa pueda referir, como el espacio virtual de direcciones,;y al ccn- junto de direcciones reales de memoria, el espacio físico de direccionamiento. Un mapa de memoria podría relacionar las direcciones virtuales con las direcciones físicas, asumiendo que hay suficiente espacio en la memoria Secundaria( en un tambor o disco ), para almacenar el programa completo y su información. Los programas se escriben como si hubiera suficiente memoria principal, aunque no sea este el caso. Estos se pueden cargar desde o almacenar, en cualquier palabra del esPació virtual:de direcciones, o saltar a cual- quier instrucción localizada en el mismo, sin - considerar que actualmente no hay suficiente memoria física. En realidad, el programador puede escribir sus programas sin estar consciente que la memoria virtual existe; él simplemente piensa que la máquina tiene una memoria muy grande. 68 Este punto - es crucial y será contrastado mas tarde con segmentación, donde el programador debe estar consciente de la existencia de segmentos. La paginación le da al programador, la ilusión de una larga, continua y lineal memoria principal. El mismo tamaño del espacio de direcciones existe cuando en efecto, la memoria principal disponible puede ser más pequeña que el espacio de direccio- -,. nes. La simulación de esta gran memoria principal por pagi- nación, no puede ser detectada por el programa. De tal forma, el programador puede trabajar como si la paginación no existiera y se dice que este fenómeno es transparente para el usuario. 1. IMplementación de paginación Un requisito esencial para una memoria virtual es una memoria secundaria en la cual se guarda el programa completo. Es conceptualmente más simple, si uno piensa en la copia del programa, en la memoria secundaria como el original y las piezas traídas dentro de la memoria principal como copias. Naturalmente es importante guardar el original actualizado, pues cuando se han hecho cambios a la copia en la memoria principal, deberán ser reflejados en el original 4 K 15 direcciones virtuales 69 también. El espacio virtual de direccionamiento es dividido dentro de un número de páginas igualmente clasificadas, según el tamaño, sabiendo que los tamaños de las mismas son siempre un múltiplo de 2. El espacio físico de direccionamiento es dividido en pedazos en una forma similar; cada pieza tiene el mismo tamaño, así que cada una es capaz de mantener exactamente uná página. Estos pedazos de memoria principal dentro de los cuales van las páginas, son llamados estructura de páginas o bloques. 0 4096 8192 12288 16384 20480 24576 28677 32760 36866 40960 45056 49152 53248 57344 6144o o 4096 8192 12288 16384 20480 24576 28677 direcciones de memoria principal Fig. 3.8. División de un espacio de direccionamiento de 64 K La memoria virtual de la figura, sería implementada COMO significado de una tabla que contiene 16 palabras. Cuando el programa trata de referenciar su memoria ya sea 70 para tener información almacenada, traer instrucciones o saltar, generaría primero una dirección de 16 bits correspondientes a una dirección virtual entre 0 y 65,535, En este ejemplo, la dirección (16 bits) se toma como un número virtual de página (4 bits) y una dirección (12 bits) dentro dula página seleccionada. 2. Acceso a páginas En la siguiente figura la dirección de 16 bits es 12,310 lo cual considerado como dirección 22 de la página 3. La relación entre páginas y memoria virtual se muestra tabular- mente. página dirección virtual memoria virtual. (16 bits) WOICÁCtla[4111-13 4 bits 12 bits página direcciones virtual dentro de = 3 una página virtual .= 22 0-4095 —1096-8191 2 8192-12287 3 12288-16383 .4 1 b 555- 20479 5 . , 6 . 7 . 8 . 9 . . le 11 12 ' 13 14 . 15 61440L65535 Fi?. 3.9. Memoria Virtual de 16 Bits. donde debe tomarse en cuenta, el estado de la selección del lugar donde se va página y la Pá9i- a cargar o guardar una 71 Cuando se determina que la página virtual 3 es necesa- ria, el sistema operativo debe encontrar donde está locali- zada. Existen 9 posibilidades: 8 estructuras de página en la memoria prinCipal o algún lugar de la memoria secundaria. Para descubrir cuál detestas posibilidades • es, el sistema operativo ve en las tablas de páginas, cuál tiene una entrada para cada una de las 16 páginas virtuales. La decisión de restringir todos los' segmentos de información de tamaños uniformes, provoda un impacto significante en el manejo de la memoria. Si una página no es accesible, el control es transferido a un procedimiento de errores el cual hace la página accesi- ble. Este método es llamado 'demanda de paginacion', en na. Inicialmente y después que una página ha sido borrada, su descriptor esta en estado vacío, es así como el referen- ciarla sería un error. Un comando de carga puede. ser puesto a la cola mientras es servido. Durante este tiempo la situación en la memoria principal puede cambiar, y aparecer espacios libres, es por esto que hay que esperar a que el comando de carga sea colocado en el'buffer'. 2 i 1 { - nuIssche> P7‘cji4A o YRk0Jcx 1 INA t C -PAN,no 2 PIcinA r1INsato 21 iN A. O 72 loop I- I r - - - - - 3Cco Tr+MM-10 1 5 Zoo° 3ono L_ N ". X 1 3104 -_i .1 -1-- 1 N. \ / 1‘ 1, .,, q \14coo Viiieleno 3 N ` \ v %, , \ / •,i \\ \rsco 1', \ .- i ‘`.... ‘k / \ 'ton Y 3 -__/ . 'acrio 1120 Oosen?.. Y -.____ 1-. ----HOU, WOO L_- i - N ---h? ima, r,,nr1 - - -- 3 - N _ +? _- alzo a 1 -4 _ -- --- -I ,-- -- tablas de scw on zoco L_ _ 1 .,--- I 1 L. mapeo de páginas . espacios de direccionamiento • / • zloo \ J - _ Y 8 O L— I 100 f LOAD_ vazo_ 1.....____ 10.4 iii1 /4 DD1,24 SO I ._ -- -- -- I -- tobo — memoria física Fig. 3.10. Marie° de la memoria para demanda de páginas. 3. Tamaño de Eágina y fragmentación. Si el usuario del- programa y la información accidentalmente llenan un número de páginas exactamente, 73 no habrá espacio perdido cuando estén en la memoria. Si por 1 el contrario, no se llena un número exacto de páginas, habrá un espacio sin uso en la última página:. Por ejemplo, si el programa y la información necesitan 26,000 palabras por página, las primeras 6 páginas estarán llenas y la última contendrá 1,424 palabras, desperdiciando 2,672. 'Cuando la séptima página está presente en la memoria, las palabras sobrantes se cargarán pero tendrá una función inútil. El problema de estas palabras desperdiciadas se llama fragmentación de paginación. Si el tamaño de página es de 'n' palabras, la cantidad de espacio promedio desperdiciado en la última página de un programa será de n/2 palabras. Esta situación sugiere un tamaño pequeño de página para minimizar el desperdicio, aunque esta solución acarrearía un mayor número de páginas y una' tabla grande; si la tabla está mantenida en el hardware, significa que son más registros para almacenar, hecho que aumenta el costo del computador. Además será necesario más tiempo para cargar y resguardar estos registros cuando un proceso ha iniciado o finalizado. Si se consideran páginas pequeñas harán ineficiente el uso de la memoria secundaria. Otro método que puede 74 decrementar el problema de fragmentación, es la asignación múltiple de, particiones. En este método un trabajo consiste de varias porciones de memoria sepa- radas, cada porción individual va a estar lógicamente contigua al anterior, pero su localización física, no. Por una parte facilita la multiprogramación,, pues hace más eficiente la utilización del procesador y de los dispositivos de entrada/salida; no requiere un hardware cos- toso, los algoritmos usados son simples y fáciles de imple- mentar, Por otro lado, aunque la memoria no se fragmenta, las áreas libres podrían no ser io suficientemente largas para una partición y ésta estaría limitada al tamaño físico de la memoria. Para una mejor comprensión del tamaño ópti- mo de páginas, refiérase a]. Apéndice A. Existe una partición estática, en la cual se divide la memoria antes de cualquier procesamiento de algún trabajo; esta técnica es apropiada cuando el tamaño y la frecuencia de los trabajos. es conocida. La partición dinámica, es a- quella en que las particiones creadas durante el procesamien- to de un trabajo, hacen corresponder el tamaño de la parti- ción al tamaño del trabajo. F. Segmentación La idea básica de segmentación es que no es necesario 75 cargar un programa y sus respectivos datos en un área contigua de la memoria; se puede cargar la sección del programa y la sección de datos en dos áreas separadas, teniendo la obvia ventaja de una más flexible locali- zación de memoria. Cuando un espacie es continuamente localizado es más difícil encontrar un área contigua para una larga pieza de información que dos pequeñas áreas individuales. Particionando la información entre muchos segmentos de programas y muchos segmentos de datos, no solo facilita el poner la información en memoria primaria sino también perfeccionar su uso en otras formas. La segmentación hace que sea innecesario para toda la información de un proceso a ser cargado en memoria antes que el proceso pueda correr. Es suficiente cargar el segmento de programa entre cada contador de programas de un proceso. Esto permite que el proceso esté listo para correr estando parcialmente cargado; la segmentación permite que el tamaño requerido de un proceso sea mucho menor que el tamaño total de la información. Obviamente, hay algo envuelto por encima yendo de un segmento a otro. Así, el propósito es minimizar el número de movimiento de segmentos. Este propósito puede en parte, ser conseguido sí instrucciones o items de datos 76 con el mismo lugar de control son puestos en un segmento. El lugar natural de control para instrucciones es un bloque de programas, un procesamiento, o un 'subrutina; si una instrucción de alguna subrutina es ejeOutada, es más probable que otra instrucción sea mejor ejecutada que una instrucción fuera de la rutina. Observando los datos, la unidad natural es una estructura de datos como' arreglos o astas. El programa y los datos de un proceso son pafticionados entre un conjunto de segmentos, los cuales, son puestos aleatoriamente en memoria. G. 'Swa ping' y relocalización En una máquina con multiprogramación puede ser que algunos programas estén listos para correr, mientras otros están esperando por la completación de la transmisión de datos. El tiempo de espera es generalmente largo. La transmisión de datos a través de dispositivos lentos como una lectora de tarjetas o un teletipo toma de 0.1 a 1 Segundo; idealmente, la memoria principal solo contendría los procesos que estén listos para correr. Este objetivo puede ser llevado a cabO de varias 77 formas. Una de ellas es el método 1 swaping,. El principio de este método es que los programas y los datos de un proceso en espera son cambiados de la memória principal y son guardados en un área de almacenamiento de copias. Cuando el período de espera finaliza y el proceso está otra vez listo para correr, es colocado en la lista de traslados. Cuando ha llegado a la cabeza de la lista dei traslados, el proceso es trasladado a la memoria principal: tan pronto como haya suficiente espacio. Primero diseñamos los procedimientos del sistema para cambiar programas y datoS de la memoria principal. Luego discutimos los procesos del sistema que controlan la memoria de copias y repartirnos el espacio de memoria principal a los programas que pueden correr. Finalmente, veremos un caso especial de sistema de multiprogramación de tiempo compartido. Este es una extensión del sistema de tiempo compartido que no tiene multiprogramación. Primero, un asunto de diseño de la - estrategia, no se seguirá la inconveniente práctica de repartición de ventanillas, la cual es comiin en bancos y oficinas de correos. Alli un cliente debe decidirse y escoger una ventanilla cuando entra, y debe permanecer en esa ventanilla no importando cuánto tenga que esperar. La gente que 78 entra después en ocasiones es atendida mucho antes que él. Lo correcto sería asignar al cliente una ventanilla cuándo , llegue su turno de recibir el servicio. Analogamente, un proceso en un sistema de multiprogramación no debe ser atado a un área particular en la memoria principal; un proceso completo en turno para correr sería cargado dentro de la primera área de memoria lo suficientemente grande disponible. Esto sin embargo implica que un: proceso que fue trasladado, pueda ser cargado a la memoria principal\ más que un proceso que fue previamente corrido. Así las referencias a los items de datos o lugares en un programa no serían expresados en términos de localizaciones físicas de memoria principal, pero sí en términos de posiciones relativas al principio del área en la memoria principal repartida para el proceso. Tales referencias en un programa son expresadas como direcciones virtuales, el programa es llamado un programa relocalizable. La traducción de direcciones virtuales a direcciones físicas puede ser fácilmente ejecutada. La exacta 'localización es derivada sumando los contenidos de un registro base o registro de relocalizacien a una dirección virtual. El valor de este registro es la localización inicial del área en memoria principal en la que el programa relocalizable y sus datos son cargados. Así, la regla de traducCión de direcciones aplicada es: LOCALIZACION = BASE + DIRECCION VIRTUAL Un prOgrama corre en un bloque contiguo de espacio de memoria principal cuyo límite inferior es determinado por el registro de relocalización. De esta forma ,hay muchos programas en la memoria principal al mismo tiempo, se necesita estar seguro de que un programa nO accese las localidades del límite inferior del espacio repartido. El hardware de muchas máquinas es diseñado para ejecutar un simple chequeo de direcciones. Además la localización inicial, ya sea el tamaño o el máximo del área repartida en. memoria principal es guardado en un registró. Cuando una dirección virtual es traducida en una localidad, el hardware chequea si el resultado está dentro del área' repartida. Si el chequeo falla, las operaciones probadas resultan con un error de dirección. Este simple chequeo asegura que un programa no pueda accesar información fuera de su área, y protege un programa y sus datos contra errores o acciones maliciosas de otros programas. Por supuesto, no será posible para un programa violar la protección asignando un valor arbitrario al registro conteniendo la base, el tamaño o el máximo. Asumiendo que las áreas en memoria principal, en las 75 que un programa y sus datos son colocados, son todas del 80 mismo tamaño. Un bloque contiguo de espacio de memoria principal en uso por un procesador Pi es movido de la memoria principal y guardado en el almacenamiento de copias por un procedimiento especial llamado SWAPOUT(i). Un bloque contiguo es movido. de la memoria de copias por un procedimiento especial llamado SVAPIN(i), donde i es el pro- ceso 'indizado'. La función SWAPOUT(i) guarda la información en dispositivos de memoria secundaria (por ejemplo, un disco). Esto es activado colocando un mensaje en el dispositivo de cola. Si la cola está vacía el mandato es también colocado en un buffer; de otro modo simplemente se reparte la cola. El mandato consiste de la base y el máximo del área de memoria principal, la base del área en el almacenamiento de copias donde el contenido sería guardado, y una indicación de que ésta es una orden de guardar la información. Se asume que el almacenamiento de 'copias es lo suficientemente grande y que un área libre puede ser encontrada siempre. El sistema 'swaping' mantiene una cola 'swap-in'la cual contiene el proceso listo para regresar al almacenamiento de copias. Si un proceso es colocado en una cola de 'swap-in' vacía y hay lugar en la memoria principal, el proceso es 81 inmediatamente trasladado; de otro modo es atado a la cola. de traslados.. Similar* a 1 swapouts, la función 'swapin' prepara y envía un mensaje a la cola del dispositivo de memoria secundaria, pero envía un orden de carga en lugar de' una, orden de grabación. 'Swapin' y 'swapout' insertan un mensaje dentro de la cola de copias sin esperar hasta que , la transferencia sea completada. Esto tiene muchas consecuencias, en primer lugar, el área en .1a memoria principal, ocupada por un proceso el cual es cambiado, no puede ser usada como espacio libre en 'swapout' hasta que la información sea guardada. En segundo lugar, esto es posible para un proceso que todavía no esta completamente trasladado cuando una respuesta llega y swapin decide como cambiar este proceso de regreso. Esto no causa un probleMa real, porque la orden de carga es colocada en la .cola más que la orden de grabación. Así, por el tiempo en que la orden de carga es ejecutada, la orden de grabación ha sido procesada. Finalmente la completación de una transferencia en ambas direcciones debe ser 'notificada por el proceso de control del dispositivo de almacenamiento • de copias. llama BSC ('Back Storage Control') al proceso que 82 controla ef almacenamiento de copias. El proceso BSC es activado cuando el dispositivo ha completado la transferencia. El trabajo primario es borrar la orden común y enviar el siguiente mensaje al dispositivo. Si una orden de grabación ha sido completada, el estado de almacenamiento primario es actualizado, porque el área en el almacenamiento primario, ocupada por el proceso de grabación, está realmente libre. El espacio libre es dado al primer proceso en la cola de cambios, o si la cola está vacía esto es grabado como libre. El espacio libre'es enteramente controlado por el proceso BSC. 1. TRASLAPES Es una forma más refinada de 'swapping'i la cual tras- lada únicamente porciones del espacio de dirección de tra- bajos y es llamada manejo de traslapes. A continuación se ilustra la relación entre los proce- dimientos en un espacio de 'dirección de trabajos. 83 Fig. 3.11. Manejo de memoria por traslapes. Asignando direcciones de procedimientos como se muestra en la figura siguiente, en lugar de usar 190 K bytes para mantener el espacio de direccionamiento de trabajos en memoria, un máximo de 100 k bytes son necesarios. 20Kr 20 K 20K 50 K 50K- 70K- 70 K 0 20 K 50 K 100K memoria física 70 K 100 K 90 K 84 Fig. 3.12. Asignación de segmentos de traslape. IV. ADMINISTRADOR DE PROCESOS A. Definición Habitualmente se utiliza el término proceso, sin precisarlo debidamente y se deja a la intuición de cada quién la comprensión de su significado. En general, se acepta como definición de proceso o tarea secuencial, la actividad resultante de ejecutar un programa con sus datos en un procesador secuencial. No puede asociarse esta idea a la de procesador o a la de programa aisladamente, sino debe hablarse de un par (procesador,, programa) en ejecución y entender por programa, una colección de instrucciones que describen un proceso. Si no es esta la concepción del último tér- mino, podrá darse el caso de que una única tarea, co- rresponda a la ejecución de varios programas. También podrá ocurrir que más de un proceso o tarea, se creen sobre un mismo conjunto de instrucciones en un momento determinado. Este caso, sería un ejemplo de ejecución en multitarea. El número de procesos existentes en un sistema, es independiente de el número de procesadores; una muestra inmediata de tal independencia, la tenemos al trabajar con un solo procesador o unidad central de proceso (UCP) 86 en la modalidad de multiprogramación. El administrador de procesos es un elemento del sistema operativo que controla la asignación y el uso del procesador (UCP) por parte de los procesos de cálcu- lo. los mecanismos de selección y control y de comunicación y paso de información entre ellos. El problema de planificar trabajos, se incluye también como labor de este administrador. B. Elementos del Administrador de procesos. Los elementos más significativos del administrador de procesos son: Identificador del proceso: es una estructura de datos donde hay información del proceso: nombre, estado, prio- ridad, derechos, acceso, punteros, etc. Si imaginamos que el identificador es una estructura, el hecho de llenarla es equivalente a "crear un proceso". Listas de procesos: los identificadores de procesos se pueden encadenar (con punteros) para formar diferen- tes listas ordenadas (por ejemplo una cola); cada una de ellas representa una situación idéntica para los procesos encadenados a la misma lista ( p.e. lista de espera de un recurso determinado). Planificador de procesos: implementa la búsqueda de un nuevo proceso dentro de las diferentes listas de procesos. La ordenación de la lista, y por lo tanto la búsqueda, puede ser por prioridad, clase, prioridad dentro de la clase, balance entre tiempo de cálculo y de entrada/salida, primer, llegado primer salido, etc. Despachador de procesos: realiza la carga de los regis- tros del procesador con la pareja de instrucciones y da- tos direccionables del proceso seleccionado por el pla- nificador. También carga los registros de trabajo y otra información de control desde las áreas de trabajo. C. Estados fundamentales y transiciones entre procesos. Para cada proceso podemos definir tres estados bá- sicos por los que va pasando, mientras se .ejecuta: 1. Ejecución: los reg-itros del procesador han sido cargados con la pareja de instrucciones y datos direccionables del proceso y por lo tanto se ejecuta una secuencia de instrucciones con los datos del entorno correspondiente. 87 88 2. Espera: la pareja de instrucciones y datos direc- cionables del proceso ha sido descargado: no se eje- cuta ninguna instrucción del proceso. La pareja de instruccciones, permanece guardada y el i- dentificador del proceso queda encadenado a la lista de procesos en estado de espera de una ocurrencia determinada. El concepto "esperar una ocurrencia" es completamen- te general: el proceso puede decidir esperar hasta que se cumpla una determinada condición: i) final de entrada/salida ii) señal de otro proceso iii) final de un intervalo de tiempo 3. Preparado: El identificador del proceso permanece relacionado a una lista de procesos preparados a fin de ser seleccionados para pasar al estado de ejecución. En este estado, los procesos tienen asignados todos los recursos que necesitan, excepto el recurso UCP. • Los estados y las transacciones citadas se pueden representar con la figura siguiente: EJECUCION PREPARADO Fig. 4.1. Estados fundamentales y transiciones 89 entre procesos. Asi pues, entendiendo que en un programa los pro- cesos de cálculo y de entrada/salida cooperan a través de llenar y usar respectivamente el recurso "área de en- trada/salida", la secuencia clásica de ejecución: pro- ceso de cálculo, procesos de entrada/salida, proceso de cálculo, proceso de entrada/salida..., es debido a que el proceso .de cálculo espera hasta que el proceso de en- trada/salida señale la teminación de su trabajo. Mien- tras tanto, el proceso de cálculo de un segundo programa puede estar en estado de ejecución: la multiprogramación es su resultado. Generalizando este último concepto. Sobre un sis- tema pueden trabajar diferentes procesos independientes 90 o relacionados.a través de compartir un recurso. En es- te último caso, es necesario establecer una sincroniza- ción entre ellos en el sentido de autorizar solo a uno de ellos a ceder al recurso; los demás han de esperar. El concepto de esperar en una cola hasta que el recurso quede libre es una consecuencia del razonamiento ante- rior. También lo es el avisar a los que esperan en cola de que el recurso ha quedado libre. La transición 2 de la figura representa el hecho de "ponerse en cola y esperar", mientras que la tran- sacción 3 representa que la condición ha sido satisfe- cha y el proceso vuelve a estar preparado para la eje- cución. Resumiendo las transiciones de la figura anterior son: Transición 1: el planificador de procesos elige uno de la lista de procesos peoparados y el despachador asigna la - pareja instrucciones - datos direccionables a los registros de la unidad central. La elección la realiza el plani- ficador de procesos en base a la estrategia que implemente y que se indicará en la seccion C.1. El resultado es que la UCP 91 ejecutará las instrucciones del proceso. Transición 2: El proceso de cálculo. pide esperar. Esto fuerza a una transición 1 y por lo tanto a la acción del despachador y planificador de procesos. Transición 3: El administrador del recurso que hacía espe- rar al proCeso es el encargadb de señalar que el recurso ya esta libre yl de agregar el proceso en la lista de procesos preparados. Transicion 4: Se produce cuando en función de su estrate- gia, el planificador de procesos decide asignar el recurso UCP a otro proceso provo- cando la correspondiente transición 1. 1. Estrategias de selección de procesos Las estrategias de selección de procesos pueden ser diferentes según que el sistema haya sido pensando para dar uno u otro tipo de servicio. Según el sistema, el administrador de procesos puede escoger el proceso a ejecutar por: 92 - 'Round-robin': se asigna un quantum de tiempo 'q' de UCP a cada proceso de la lista de preparados. Una vez el proceso que tiene el procesador agota su quantum de tiempo vuelve a la lista de preparados ( transicion 4 de la figura )y volvera a tener procesador cuando le toque. - 'Round-robin' modificado: Parecido a la estrategia ante- ---rior pero teniendo en cuenta que si un proceso no ha agotado su quantum 'q' porque ha pasado al estado de espera por cualquier razón, cuando vuelva a tener el procesador ( transiciones 3+1 de la figura ) lo hará durante un tiempo q'+q. - ''Feedback queue': Al llegar un nuevo procesa, recibe tantas veces 'q' tiempo como lo han recibido los que ya llevan rato bajo control del administrador de procesos. al llegar a nivel de los otros' procesos el administrador asigna 'q' a cada proceso (Round robin) - Prioridad: Los procesos llevan asociada una prioridad. El adminisdor de procesos escoge entre los de la lista de preparados el que tiene prioridad más alta. Prioridades dinámicas: Estrategia parecida a la anterior con la diferencia que cada vez que un proceso hace una transición 4 su prioridad es modificada por el 93 administrador de procesos. Balanceo del sistema: El administrador de procesos pretende que haya una carga sesiblemente igual de procesos de. cálculo y de procesos de entrada/salida para optimizar el uso global del sistema. Hay otras estrategias más especializadas que se implementan por separado o formando combinaciones, de manera que el administrador 'puede responder a un conjunto más amplio de situaciones de forma más flexible y eficiente. Los procesos del sistema operativo pueden ser tratados como procesos generales en competencia con los del usuario se pueden declarar privilegiados. En este caso, el proceso tendrá la más alta prioridad del procesador y por lo tanto se ejecutará sin posibilidad de que otros procesos del usuario de entrada/salida le interrumpan. D. Comunicación de Procesos. Para aumentar la eficiencia, las distintas tareas comparten tanto el software, como el hardware del 94 sistema. Por ello, tendrán necesidad de intercambiar información e introducir mecanismos que permitan el intercambio. Los problemas a resolver cuando existe concurrencia, podrían identificarse dentro de los siguientes puntos: - Determinismo. - Exclusión mutua. - Sincronización. - Deadlock (bloque mutuo entre tareas) Cuando un conjunto de tareas pueden ser ejecutadas en paralelo, interesa a veces asegurar la unicidad de los resultados pese a las variaciones de velocidad de ejecución de cada una y su orden de ejecución. Es decir, que el sistema de tareas o procesos que satisfa- ga esta propiedad, se dice que es funcional, dependiendo de la velocidad de terminado. Procesos concurrentes que operan sobre conjuntos disjuntos de variables, se llaman disjuntos o no - interactivos. La no - interactividad, es una condición suficiente para el comportamiento indepen diente del tiempo de lo's procesos. Si hay interactivida- dad, cuando una variable es referenciada por una tarea 95 y existe una segunda que cambia su valor; el resultado de la primera dependerá del momento en que se produzca el cambio. Sí se. cumplen determinados requisitos, los programas pueden ser incondicionalmente funcionales y para ellos, se cumple la siguiente propiedad: cualquier propiedad:cualquier interconexión de un número finito de programas incondicionalmente funcionaleS, es incondi- cionalmente funcion