Sistemas Operativos

Transcript

Sistemas Operativos Prólogo Las presentes notas son recopilaciones de diferentes libros básicos que se recomiendan a los estudiantes de nivel licenciatura para la materia de Sistemas Operativos, así como artículos, y manuales de programación que ayudan a ampliar la información. Se presentan también códigos básicos tomados de los libros base, así como algunas mejoras que se han llevado a cabo a lo largo de los cursos en los cuales he impartido la materia. Se recomienda tomar como punto de partida para la exploración el sistema operativo GNU/Linux, la distribución que considere pertinente, hago notar que los códigos presentados fueron probados bajo una distribución de Ubuntu. Nada de esto es comercial ni mucho menos para sacar un peso de algún lado, como les repito son recopilaciones de libros básicos como Sistemas Operativos de W. Stallings, Sistemas Operativos de M. Deitel, Sistemas Operativos de A. Tanenbaum, Sistemas Distribuidos de G. Coulouris, Sistemas Distribuidos de A. Tanenbaum, Sistemas Distribuidos de Mullender, Unix de C. Brown, Unix de F. M. Marquez, Unix de Robbins. Estas notas, digamos para colocarle un número de versión, son las 0.01, faltan demasiados detalles que pulir, figuras que colocar y tablas que actualizar, solo para justificar su primera liberación, diré a mi favor: necesito colocar estas notas para que las lean mis estudiantes, y no tengan excusa de no encontrar los libros en la biblioteca, pero si motivo de venir a verme y decirme que algo anda mal en estas páginas. Espero sea de utilidad! Hay golpes en la vida, tan fuertes... Yo no sé. Golpes como del odio de Dios; como si ante ellos, la resaca de todo lo sufrido se empozara en el alma... Yo no sé. Los heraldos negros. César Vallejo. 1 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 1 Introducción a los Sistemas Operativos Un sistema operativo (SO) se encarga de controlar y administrar los recursos con los que cuenta un dispositivo de comunicación, brindando con una interfaz para comunicar al usuario con el hardware. 1.1 Sistema Operativo Veamos primero algunas definiciones de algunos autores sobre qué es un sistema operativo, para comprender mejor lo necesario que es un sistema operativo para que un hardware puede ser utilizable. Definiciones 1. El software que controla el hardware. 2. Es un programa de aplicación que controla la ejecución de los programas de aplicación y que actúa como interfaz entre el usuario de una computadora y el hardware de la misma. 3. Es un administrador de recursos del dispositivo, tales como, los procesadores, los medios de almacenamiento, los dispositivos de entrada/salida, los medios de comunicación y los datos; y proporciona la interfaz con el usuario. Aunque podemos decir que en la definición 1, actualmente existe una tendencia significativa a la transferencia de las funciones del software al firmware, es decir, colocar un microcódigo incrustado en el hardware. Un sistema operativo tiene tres objetivos: 1. Comodidad. Hace que una computadora sea más cómoda de utilizar. 2. Eficiencia. Permite que los recursos de un sistema de computo se aprovechen más eficientemente. 3. Capacidad de evolución. Debe construirse de modo que permita el desarrollo efectivo, la verificación y la introducción de nuevas funciones en el sistema y, a la vez, no interferir en los servicios que brinda. 2 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Jerarquía de elementos en una computadora El hardware y el software que se utilizan para proveer de aplicaciones a los usuarios pueden contemplarse de forma jerárquica (Figura 1-1). Usuario Final Aplicaciones Utilerías Sistema Operativo Hardware Figura 1-1. Jerarquía en el Sistema de Computo. Un sistema operativo ofrece servicios en las áreas siguientes: • • • • • • • Creación de programas. Ofrece un conjunto de programas que no forman parte del S.O. pero son accesibles a través de él como son: los editores y los depuradores. Ejecución de programas. Se encarga de administrar las instrucciones y los datos que se deben cargar en la memoria principal, los archivos y los dispositivos de E/ S. Acceso a los dispositivos de E/S. Cada dispositivo de E/S requiere un conjunto propio y peculiar de instrucciones o de señales de control para su funcionamiento. El S.O. tiene en cuenta estos detalles de modo que el programador solo piensa en forma de lecturas y escrituras simples. Acceso controlado a los archivos. El S.O. se encarga de los detalles del control del dispositivo de E/S y en el caso de sistemas con varios usuarios trabajando simultáneamente, el S.O. brinda los mecanismos de control para el acceso a los archivos. Acceso al sistema. Las funciones de acceso al sistema brindan protección a los recursos y a los datos, ante usuarios no autorizados y debe resolver los conflictos en la propiedad de los recursos. Detección y respuesta a errores. El S.O. debe dar una respuesta que elimine la condición de error con el menor impacto posible sobre las aplicaciones que están en ejecución. La respuesta puede ser desde terminar el programa que produjo el error, hasta reintentar la operación o, simplemente informar del error a la aplicación. Contabilidad. Un buen sistema operativo debe recoger estadística de utilización de los diversos recursos y supervisar los parámetros de rendimiento tales como el tiempo de respuesta. 3 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 1.3 Clasificación de los sistemas operativos Con el paso del tiempo, los sistemas operativos fueron clasificándose de diferentes maneras, dependiendo del uso o de la aplicación que se les da. Hoy en día los sistemas los podemos clasificar en dos grandes grupos, los sistemas operativos para computadoras (ya sea para uno o varios procesadores) y los sistemas operativos para dispositivos móviles. A continuación se muestran una clasificación para los sistemas operativos de computadoras, y algunas de sus características. Sistemas Operativos por Lotes Los Sistemas Operativos por lotes, procesan una gran cantidad de trabajos con poca o ninguna interacción entre los usuarios y los programas en ejecución. Se reúnen todos los trabajos comunes para realizarlos al mismo tiempo, evitando la espera de dos o más trabajos como sucede en el procesamiento en serie. Estos sistemas son de los más tradicionales y antiguos, y fueron introducidos alrededor de 1956 para aumentar la capacidad de procesamiento de los programas. Cuando estos sistemas son bien planeados, pueden tener un tiempo de ejecución muy alto, porque el procesador es mejor utilizado y pueden ser simples, debido a la secuenciabilidad de la ejecución de los trabajos. Algunos ejemplos de Sistemas Operativos por lotes exitosos son el SCOPE, del DC6600, el cual está orientado a procesamiento científico pesado, y el EXEC II para el UNIVAC 1107, orientado a procesamiento académico. Algunas otras características son: • Requiere que el programa, datos y órdenes al sistema sean remitidos todos juntos en forma de lote. • Permiten poca o ninguna interacción usuario/programa en ejecución. • Mayor potencial de utilización de recursos que procesamiento serial simple en sistemas multiusuarios. • No conveniente para desarrollo de programas por bajo tiempo de retorno y depuración fuera de línea. • Conveniente para programas de largos tiempos de ejecución. • Se encuentra en muchos computadores personales combinados con procesamiento serial. • Planificación del procesador sencilla, típicamente procesados en orden de llegada. • Planificación de memoria sencilla, generalmente se divide en dos: parte residente del S.O. y programas transitorios. • No requieren gestión crítica de dispositivos en el tiempo. • Suelen proporcionar gestión sencilla de manejo de archivos: se requiere poca protección y ningún control de concurrencia para el acceso. Sistemas Operativos de Tiempo Real Los Sistemas Operativos de tiempo real son aquellos en los cuales no tiene importancia el usuario, sino los procesos. Por lo general, están subutilizados sus recursos con la finalidad de prestar atención a los procesos en el momento que lo requieran. Se utilizan en entornos donde son procesados un gran número de sucesos o eventos. Muchos Sistemas Operativos de tiempo real son construidos para aplicaciones muy específicas como control de tráfico aéreo, bolsas de valores, control de refinerías, control 4 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos de laminadores. También en el ramo automovilístico y de la electrónica de consumo. Otros campos de aplicación de los Sistemas Operativos de tiempo real son los siguientes: • Control de trenes. • Telecomunicaciones. • Sistemas de fabricación integrada. • Producción y distribución de energía eléctrica. • Control de edificios. • Sistemas multimedia. Algunos ejemplos de Sistemas Operativos de tiempo real son: VxWorks, Solaris, Lyns OS, Spectra, RTLinux. Los Sistemas Operativos de tiempo real, cuentan con las siguientes características: • Se dan en entornos en donde deben ser aceptados y procesados gran cantidad de sucesos, la mayoría externos al sistema computacional, en breve tiempo o dentro de ciertos plazos. • Se utilizan en control industrial, conmutación telefónica, control de vuelo, simulaciones en tiempo real, aplicaciones militares, etc. • Procesa ráfagas de miles de interrupciones por segundo sin perder un solo suceso. • Proceso se activa tras ocurrencia de suceso, mediante interrupción. • Proceso de mayor prioridad expropia recursos. • Por tanto generalmente se utiliza planificación expropiativa basada en prioridades. • Administración de memoria menos exigente que tiempo compartido, usualmente procesos son residentes permanentes en memoria. • Población de procesos estática en gran medida. • Poco movimiento de programas entre almacenamiento secundario y memoria. Sistemas Operativos de multiprogramación ( Multitarea) Se distinguen por sus habilidades para poder soportar la ejecución de dos o más trabajos activos al mismo tiempo. Esto trae como resultado que la Unidad Central de Procesamiento siempre tenga alguna tarea que ejecutar, aprovechando al máximo su utilización. Su objetivo es tener a varias tareas en la memoria principal, de manera que cada uno está usando el procesador, o un procesador distinto, es decir, involucra máquinas con más de una CPU. Todos los sistemas operativos actuales soportan multitareas. UNIX, MACOS, LINUX, Windows, solo por mencionar los más conocidos. Las características de un Sistema Operativo de multiprogramación o multitarea son las siguientes: • Mejora productividad del sistema y utilización de recursos. • Multiplexa recursos entre varios programas. • Generalmente soportan múltiples usuarios (multiusuarios). 5 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • Proporcionan facilidades para mantener el entorno de usuarios individuales. • Requieren validación de usuario para seguridad y protección. • Proporcionan contabilidad del uso de los recursos por parte de los usuarios. Sistemas Operativos Distribuidos. Permiten distribuir trabajos, tareas o procesos, entre un conjunto de procesadores. Puede ser que este conjunto de procesadores esté en un equipo o en diferentes, en este caso es trasparente para el usuario. Existen dos esquemas básicos de éstos. Un sistema fuertemente acoplado es a es aquel que comparte la memoria y un reloj global, cuyos tiempos de acceso son similares para todos los procesadores. En un sistema débilmente acoplado los procesadores no comparten ni memoria ni reloj, ya que cada uno cuenta con su memoria local. Los sistemas distribuidos deben de ser muy confiables, ya que si un componente del sistema se compone otro componente debe de ser capaz de reemplazarlo. Entre los diferentes Sistemas Operativos distribuidos que existen tenemos los siguientes: Sprite, Solaris-MC, Mach, Chorus, Spring, Amoeba, Taos, etc. Características de los Sistemas Operativos distribuidos: • Colección de sistemas autónomos capaces de comunicación y cooperación mediante interconexiones hardware y software . • Transparentes. • Generalmente proporcionan medios para la compartición global de recursos. • Servicios añadidos: denominación global, sistemas de archivos distribuidos, facilidades para distribución de cálculos. Sistemas Operativos de Red Son aquellos sistemas que mantienen a dos o más computadoras unidas a través de algún medio de comunicación (físico o no), con el objetivo primordial de poder compartir los diferentes recursos y la información del sistema. Sistemas Operativos Paralelos En estos tipos de Sistemas Operativos se pretende que cuando existan dos o más procesos que compitan por algún recurso se puedan realizar o ejecutar al mismo tiempo. En UNIX existe también la posibilidad de ejecutar programas sin tener que atenderlos en forma interactiva, simulando paralelismo (es decir, atender de manera concurrente varios procesos de un mismo usuario). Así, en lugar de esperar a que el proceso termine de ejecutarse (como lo haría normalmente), regresa a atender al usuario inmediatamente después de haber creado el proceso. 6 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 1.4 Sistemas Operativos para dispositivos móviles Por otra parte, se tiene actualmente los sistemas operativos de los dispositivos móviles, como son: Android, Iphone OS, BlackBerry OS, Symbian, PalmOS, aunque los dos últimos y han dejado de estar presente dado que fueron absorbidos por los tres primeros. Symbian Symbian es un SO que estaba incorporado en los celulares Nokia, su Core es común a todos los dispositivos, cuenta con: kernel, servidor de archivos, administración de memoria, y manejadores de drives. Cuenta con una capa de sistema de comunicación como: TCP/IP, IMAP4, SMS y un administrador de base de datos; Software para la interfaz con el usuario y un conjunto de aplicaciones. En Symbian cada proceso se ejecuta en un espacio de dirección protegido, así como también el kernel tiene su propio espacio protegido. Por lo cual permite que varios procesos sean ejecutados en forma concurrentes. Symbian está escrito en C++, así que es natural el desarrollo de aplicaciones en este lenguaje, aunque también admite el desarrollo en Java. El sistema es multitarea, y cuenta con un hilo principal, el cual se encarga de desprender nuevos hilos para las diferentes actividades a realizar. iPhone iPhone fue creado a partir del Mac OS X, para ser el sistema operativo nativo de los smartphone iPhone, dispositivos touch iPod, y después para las tables iPad. La arquitectura del model de iPhone está formada por los siguientes elementos: • Capa de aplicaciones, formada por las aplicaciones nativas (calendario, fotos, camara, etc..) y aplicaciones instaladas por el cliente, desarrolladas por un tercero. • Capa de Middleware, formada por tres subcapas o Cocoa Touch, este es un framework que proporciona infraestructura necesaria para los desarrolladores o Media, formada por aplicaciones graficas, framework de audio y video para crear aplicaciones multimedias. o Core Services, proporciona el sistema de servicio fundamental que todas las aplicaciones usan de forma directa o indirecta vía un framework de nivel alto. Los framework de address book, core data SQLite library, y Core Location son algunos de los componentes de esta capa. • Kernel, formado entre otras cosas por los drivers, framework de seguridad, CFNetwork. 7 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos BlackBerry El SO BlackBerry es una plataforma de software desarrollada por Research In Motion (RIM) para sus dispositivos smartphone liberados en 1999. El SO cuenta con las siguientes caracteisticas: • • • • Es multitareas, El kernel está basado en Java, Utiliza una arquitectura ARM, El administrador de memoria divide está en tres secciones: Memoria para aplicaciones, Memoria del dispositivo, Memoria de la tarjeta (opcional) Android Android es otro sistema operativo para dispositivos mooviles, el cual tiene las siguientes características: • Almacenamiento, usa SQLite para el alacenamiento de datos. • Conectividad, soporta GSM/EDGE, IDEN, CDMA, UMTS, Bluetooth, Wifi, LTE, WiMax. • Web Browser, Basado en WebKit open-source. • Media, incluye soporte de: H.263, H.264, MPEG-4 SP, AMR, AMR-WB, AAC, HE-AAC, MP3, MIDI, Ogg Vorbis, WAV, JPEG, PNG, GIF y BMP. • Soporte de Hardware, Sensor acelerometro, camara, brújula digital, sensor de aproximación, y GPS • Multi touch, pantalla multi touch • Multitareas, soporta aplicaciones multitareas. • Tethering o pasarela • En runtime contiene librerias Core y la máquina virtual Dalvik • En el kernel que es Linux contiene: Driver Display, Driver de Camara, Driver de Memoria Flash, Driver binder (IPC), Driver Keypad, Driver Wifi, Driver de Audio, Administrador de energía Android está basado en Linux, cuenta con un administrador de memoria, administrador de procesos, mecanismos IPC. En 2005 Google para entrar en la competencia de moviles, propone Androind, sistema operativo basado en una versión modificada de Linux, colocando así a Android como un sistema abierto y libre. Por lo que Android es liberado con una licencia Apache Open-Source. 8 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 1.5 Partes claves de los sistemas operativos • • • • • Los procesos La gestión de memoria La seguridad y la protección de la información La planificación y la gestión de recursos La estructura del sistema Los errores frecuentes en los procesos son: • • • • Sincronización incorrecta: Es frecuente el caso en el que una rutina debe ser suspendida a la espera de un suceso en cualquier lugar del sistema. Por ejemplo, un programa inicia una lectura de E/S y debe esperar hasta que los datos están disponibles en un buffer antes de continuar. En tales casos se requiere alguna señal proveniente de alguna otra rutina. Fallos de exclusión mutua: Es habitual el caso en que más de un usuario o programa intenta a la vez hacer uso de un recurso compartido. Por ejemplo, en un sistema de reservas de líneas aéreas. Si no se controlan estos accesos, puede producirse un error. Debe existir algún tipo de mecanismo de exclusión mutua que permita que sólo una rutina a la vez pueda realizar una transacción sobre una determinada parte de los datos. Funcionamiento no determinista del programa: Los resultados de un programa en particular deben depender normalmente sólo de la entrada del programa y no de las actividades de otros programas en un sistema compartido. Pero cuando los programas comparten memoria y sus ejecuciones son intercaladas por el procesador, entonces pueden interferir con otros, sobre escribiendo zonas comunes de memoria de forma incierta. Así pues, el orden en que se organiza la ejecución de varios programas puede influir en los resultados de un programa en particular. Interbloqueos: Es posible que dos o más programas estén suspendidos a la espera uno del otro. El S.O. tiene cinco responsabilidades principales en la administración de almacenamiento: • • • • • Aislamiento del proceso: El sistema operativo debe procurar que cada proceso independiente no interfiera con los datos y la memoria de ningún otro. Asignación y gestión automática: A los programas se les debe asignar memoria dinámicamente en la jerarquía de memoria, según la vayan necesitando. Este proceso debe ser transparente para el programador. Soporte para la programación modular: Los programadores deben ser capaces de definir módulos de programa y de crear, destruir y alterar el tamaño de los módulos dinámicamente. Protección y control de acceso: El s.o. debe permitir que las secciones de memoria estén accesibles de varias maneras para los diversos usuarios. Almacenamiento a largo plazo: Muchos usuarios y aplicaciones necesitan medios para almacenar información por largos periodos de tiempo. Normalmente, los s.o. satisfacen estos requisitos mediante la memoria virtual y los servicios del sistema de archivos. La memoria virtual es un servicio que permite a los programas direccionar la memoria desde un punto de vista lógico, sin depender del tamaño de la memoria principal física disponible. 9 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos El crecimiento de la utilización de los sistemas de tiempo compartido y, las redes de computadoras ha traído consigo un aumento en las preocupaciones de seguridad y protección de información. Se han identificado cuatro clases de políticas generales de protección, en orden creciente de dificultad: • • • • • • • No compartición: Los procesos están completamente aislados uno del otro y cada proceso tiene control exclusivo sobre los recursos que le fueron asignados estática o dinámicamente. Con esta política, los procesos suelen compartir los programas o archivos de datos haciendo copias y pasándolas a su propia memoria virtual. Compartiendo los originales de los programas o archivos de datos: Una única copia física de un programa puede aparecer en varios espacios de memoria virtual como archivos de sólo lectura. Subsistemas confinados o sin memoria: En este caso, los procesos se agrupan en subsistemas para cumplir una política de protección en particular. Por ejemplo, un proceso “cliente” llama a un proceso “servidor” para llevar a cabo cierta tarea con los datos. El servidor se protegerá de que el cliente descubra el algoritmo con el cual se lleva a cabo su trabajo y el cliente se protegerá de que el servidor retenga alguna información sobre el trabajo que está llevando a cabo. Diseminación controlada de la información: A los usuarios y a las aplicaciones se les dan credenciales de seguridad de un cierto nivel, mientras que a los datos y a otros recursos (p.e. los dispositivos de E/S) se les dota de clasificaciones de seguridad. La política de seguridad hace cumplir las restricciones relativas a qué usuarios tiene acceso a qué clasificaciones. Control de acceso: Tiene que ver con la regulación del acceso del usuario al sistema completo, a los subsistemas y a los datos, así como a regular el acceso de los procesos a los recursos y objetos del sistema. Control del flujo de información: Regula el flujo de datos dentro del sistema y su distribución a los usuarios. Certificación: Es relativa a la demostración de que el acceso y los mecanismos de control del flujo se llevan a cabo de acuerdo a las especificaciones y a que estas cumplen las políticas de protección y seguridad deseadas. Una tarea clave del s.o. es administrar los recursos que tiene disponibles y planificar su utilización por parte de los diferentes procesos activos. Cualquier política de planificación y administración de recursos cuenta con los tres factores siguientes: • • • Equidad: Sería conveniente que a todos los procesos que compitan por el uso de un recurso se les otorgue un acceso igualitario y equitativo, especialmente si estos procesos pertenecen a la misma clase. Sensibilidades diferenciales: El sistema operativo debe intentar tomar decisiones de asignación y planificación que satisfagan la totalidad de los requisitos. El s.o. debe contemplar estas decisiones dinámicamente. Por ejemplo, si un proceso está esperando por el uso de un dispositivo de E/S, el s.o. puede querer planificar la ejecución de dicho proceso tan pronto como sea posible y así tener disponible al dispositivo para las demandas de otros procesos. Eficiencia: El s.o. debe intentar maximizar la productividad, minimizar el tiempo de respuesta y, en el caso de tiempo compartido, alojar a tantos usuarios como sea posible. 10 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos La tarea de planificación y gestión de recursos es básicamente un problema de investigación operativa, así que se pueden aplicar los resultados matemáticos de esta disciplina. Hablemos ahora de la parte clave de un sistema operativo, la Estructura del sistema. El tamaño de un sistema operativo completo y la dificultad de las tareas que lleva a cabo plantean tres problemas desafortunados pero demasiado habituales: • Los sistemas operativos cuando se entregan ya están cronológicamente retrasados. Esto conduce a nuevos sistemas operativos y actualizaciones de los anteriores. • Los sistemas tienen fallos latentes que se manifiestan en el terreno y que deben ser detectados y corregidos. • Su rendimiento no es a menudo el que se esperaba. Tabla 1-1. Jerarquía del Diseño de un Sistema Operativo. Nivel Nombre Objetos Ejemplos de operaciones 13 Shell 12 11 Procesos de usuario Directorios 10 Dispositivos 9 8 Sistema de archivos Comunicaciones 7 Memoria virtual 6 Almacenamiento secundario local Procesos primitivos. 5 4 Interrupciones 3 Procedimientos. 2 Conjunto de instrucciones 1 Circuitos electrónicos Entorno de programación Sentencias de un lenguaje de del usuario. shell Procesos de usuario. Salir, eliminar, suspender, reanudar. Directorios. Crear, destruir, conectar, desconectar, buscar, listar Dispositivos externos Crear, destruir, abrir, cerrar, tales como impresoras, leer, escribir pantallas y teclados. Archivos. Crear, destruir, abrir, cerrar, leer, escribir Tubos (pipes). Crear, destruir, abrir, cerrar, leer, escribir Segmentos, páginas. Leer, escribir, traer (fech) Bloques de datos, Leer, escribir, asignar, liberar canales de dispositivos. Procesos primitivos, Suspender, reanudar, esperar, semáforos, colas de señalizar. procesos listos. Programas de tratamiento Invocar, enmascarar, de interrupciones. desenmascarar, reintentar. Procedimientos, pila de Marcar la pila, llamar, retornar. llamadas, visualización. Evaluación de la pila, Cargar, almacenar, sumar, intérprete de restar, bifurcar. microprogramas, vectores de datos y escalares. Registros, puertas, buses, Borrar, transferir, activar, etc. completar. 11 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 2 Procesos e Hilos Un proceso es una entidad en ejecución que tiene asociada un identificador para poder ser identificado. En el sistema se cuenta con procesos pesados, llamados hijos, y procesos ligeros, llamados hilos. 2.1 PROCESOS Todos los sistemas de multiprogramación están construidos en torno al concepto de procesos. El modelo más sencillo que puede construirse tiene en cuenta que, en un momento dado, un proceso puede estar ejecutándose en el procesador o no. Así pues, un proceso puede estar en uno de dos estados: Ejecución o No ejecución (Figura 2-1). Figura 2-1. Diagrama de transición de estados. Aún en este modelo tan simple se puede apreciar algunos de los elementos del diseño del sistema operativo, cada proceso debe representarse de forma que el sistema operativo pueda seguirle la pista. Esto es, debe haber información relativa a cada proceso, incluyendo su estado actual y su posición en memoria. Aquellos procesos que no están ejecutándose tiene que guardarse en algún tipo de cola, para que esperen su turno de ejecución (Figura 2-2). La vida de un proceso está limitada por su creación y su terminación. 12 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Figura 2-2. Diagrama de colas. Creación de procesos Cuando se añade un proceso a los que ya está administrando el sistema operativo hay que construir las estructuras de datos que se utilizan para administrar el proceso y asignar el espacio de direcciones que va a utilizar el proceso. Existen cuatro sucesos comunes que llevan a la creación de un proceso: • • • • En un entorno de trabajo por lotes, un proceso se crea como respuesta a la remisión de un trabajo. En un entorno interactivo, se crea un proceso cuando un nuevo usuario intenta conectarse. Proceso generado por un proceso existente. Creado por el S.O. para dar un servicio. Cuando un proceso genera otro, el proceso generador se conoce como proceso padre y el proceso generado es el proceso hijo. Normalmente, estos procesos “emparentados” necesitarán comunicarse y cooperar entre sí. Terminación de procesos En cualquier sistema, debe haber alguna forma de que un proceso pueda indicar que ha terminado (vea Tabla 2-1). Tabla 2-1. Terminación de proceso. Razones para terminación de un proceso Terminación normal Tiempo límite excedido No hay memoria disponible. Violación de límites. Error de protección. Error aritmético. El proceso ejecuta una llamada a un servicio del SO que indica que ha terminado de ejecutarse. El proceso se ha ejecutado por más del límite especificado. El proceso necesita más memoria de la que el sistema le puede proporcionar. El proceso trata de acceder a una posición de memoria a la que no le está permitido. El proceso intenta utilizar un recurso o un archivo que no le está permitido utilizar, o trata de utilizarlo de forma incorrecta, como escribir en un archivo que es sólo de lectura. El proceso intenta hacer un cálculo prohibido, o trata de almacenar un número mayor del que el hardware acepta. 13 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Tiempo máximo de espera rebasado. Fallo de E/S Instrucción privilegiada. Intervención del operador o del SO. Terminación del padre. Solicitud del padre. El proceso ha esperado más allá del tiempo máximo especificado para que se produzca cierto suceso. Se produce un error en la entrada o la salida, tal como no encontrar un archivo, un fallo de lectura o escritura después de un número máximo de intentos. El proceso intenta usar una instrucción reservada para el SO. Por alguna razón el operador o el sistema operativo terminan con el proceso. Cuando un proceso padre finaliza, el SO. Puede diseñarse para terminar automáticamente con todos sus descendientes. Un proceso padre tiene normalmente la autorización de terminar con cualquiera de sus descendientes. Identificadores de procesos Todo proceso tiene asociado un identificador (número positivo PID) y un padre con su respectivo identificador (número de proceso que ha creado al proceso actual PPID). Para obtener estos valores se utilizan los llamados getpid y getppid, respectivamente. Los procesos pueden estar agrupados en conjuntos que tienen alguna característica en común, como ejemplo el mismo padre. Para determinar a que grupo pertenece un proceso, se utiliza getpgrp, y para cambiar a un proceso como líder de un grupo se hace uso del llamado setpgrp. PROTOTIPO DE LA FUNCIÓN ! #include #include ! ! pid_t getpgrp(void); pid_t setpgrp(void); Se debe tener en consideración que cuando el proceso padre llega a morir antes que los hijos, el PPID del proceso hijo toma el valor de 1, que es el proceso init. Estado de un proceso (modelo de cinco estados) Si todos los procesos estuvieran siempre listos para ejecutar, entonces la disciplina de cola propuesta anteriormente sería eficaz, sin embargo, aún en el simple ejemplo que se ha descrito, esta implementación no es adecuada: algunos procesos en el estado de No Ejecución están listos para ejecutar, mientras que otros están bloqueados, esperando a que termine una operación de E/S. Así pues, utilizando una cola sencilla, el distribuidor podría no seleccionar exactamente el proceso que está en el extremo más antiguo de la 14 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos cola. Más bien, el distribuidor tendría que recorrer la lista buscando el proceso que no esté “no bloqueado” y que lleve más tiempo en la cola. Una forma más natural de afrontar esta situación es dividir el estado de No Ejecución en dos estados: Listo y Bloqueado. De esta forma contamos ahora con cinco estados (Figura 2-3): • • • • • Ejecución. Proceso que está actualmente en ejecución. Listo. Proceso que está preparado para ejecutar, en cuanto se le dé la oportunidad. Bloqueado. Proceso que no puede ejecutarse hasta que se produzca cierto suceso, como la terminación de una operación de E/S. Nuevo. Proceso que se acaba de crear, pero que aún no ha sido admitido por el sistema operativo en el grupo de procesos ejecutables. Terminado. Proceso que ha sido excluido del grupo de procesos ejecutables, bien porque se detuvo o porque fue abandonado por alguna razón. Seleccionado para ejecución Proceso creado Nuevo Listo Tiempo terminado E/S completa Terminación normal/anormal Ejecutado Solicitud de E/S Hecho Bloqueado Figura 2-3. Diagrama de estado para un sistema operativo sencillo. Un proceso puede moverse voluntariamente al estado bloqueado haciendo una llamada a una función como sleep. _________________________________________________________________________ EJERCICIO PROPUESTO _________________________________________________________________________ jueves 27 de junio de 2013 1. Investigue los procesos activos en su sistema. a) ¿Que instrucción le permite visualizarlos? b) ¿Qué parámetros son utilizados con dicha instrucción? 2. En el sistema Linux, investigue el uso del comando ps, y del comando top a) ¿Cuál es la diferencia entre ellos? b) ¿Cuál es el proceso 1? 15 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos c) ¿Quién es el padre del proceso 1? _________________________________________________________________________ Creación de procesos en Linux Linux crea los procesos a través de una llamada fork al sistema, copiado la imagen en memoria que tiene el proceso padre. El nuevo proceso recibe una copia del espacio de direcciones del padre. Los procesos continúan su ejecución en la instrucción que está después del fork. PROTOTIPO DE LA FUNCIÓN ! ! ! #include #include pid_t fork(void); La creación de dos procesos totalmente idénticos no es algo muy útil. El valor devuelto por fork es la característica distintiva, importante, que permite que el padre y el hijo ejecuten código distinto. El fork devuelve 0 al hijo y el ID del hijo al padre. EJEMPLO. En el siguiente fragmento de código tanto el padre como el hijo ejecutan la instrucción de asignación x =1 después del regreso de fork. #include #include x = 0; fork(); x = 1; fork crea procesos nuevos haciendo una copia de la imagen del padre en la memoria. El hijo hereda la mayor parte de los atributos del padre, incluyendo el ambiente y los privilegios. El hijo también hereda algunos de los recursos del padre, tales como los archivos y dispositivos abiertos. No todos los atributos o recursos del padre son heredados por el hijo. Este último tiene un ID de proceso nuevo y, claro que es diferente del ID del padre. Los tiempos del hijo para el uso del CPU son iniciados a 0. El hijo no obtiene los 16 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos bloqueos que el padre mantiene. Si el padre ha colocado una alarma, el hijo no recibe notificación alguna del momento en que ésta expira. El hijo comienza sin señales pendientes, aunque el padre las tenga en el momento en que se ejecuta el fork. Aunque el hijo hereda la prioridad del padre y los atributos de la administración de procesos, tiene que competir con otros procesos, como entidad aparte, por el tiempo del procesador. El identificador del proceso se recupera por medio de la instrucción getpid(), y el identificador del proceso que es su padre por medio de la instrucción getppid(). Los prototipos de estas instrucciones son las siguientes. PROTOTIPO DE LA FUNCIÓN ! ! #include #include pid_t getpid(void); PROTOTIPO DE LA FUNCIÓN ! ! #include #include pid_t getppid(void); El tipo de dato pid_t representa el ID del proceso. De esta manera se puede obtener el ID del proceso invocando getpid; y la función getppid retorna el ID del proceso padre del proceso actual. El tipo de dato pid_t es un tipo entero con signo el cual representa el ID del proceso. En la librería GNU C, esto es un int. EJEMPLO. En el siguiente ejemplo después de la llamada fork, los procesos padre e hijo imprimen sus identificadores. #include #include #include 17 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos pid_t hijo; void main (void) { if ( (hijo = fork ( )) = = 0) { fprintf (stderr, “soy el hijo, ID= %ld\n”, (long)getpid()); /* Aquí coloca el código que deseas que realice el proceso hijo */ } else if (hijo > 0) { fprintf (stderr, “soy el padre, ID = %ld\n”, (long)getpid()); /* Aquí coloca el código que deseas que realice el proceso padre */ } } EJEMPLO. Con el siguiente fragmento de código se crea una cadena de n procesos. #include #include #include int i, n; pid_t hijo; void main (void) { for (i = 1; i < n; i++) { if (hijo = fork()) break; /* mientras no sea diferente de cero , es decir, no exista error */ fprintf (stderr, “Este es el proceso %ld con padre %ld \n”, (long)getpid(), (long)getppid()); } } EJEMPLO. El siguiente fragmento de código crea un abanico de procesos. #include #include #include int i, n; pid_t hijo; void main (void) { for (i = 1; i < n; i++) { if (hijo = fork() <=0) break; /* después de crear un proceso, el proceso creador termina */ fprintf (stderr, “Este es el proceso %ld con padre %ld \n”, (long)getpid(), (long)getppid()); } } 18 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos El sistema de llamada wait () ¿Qué sucede con el proceso padre después de que éste crea un hijo? Tanto el padre como el hijo continúan la ejecución desde el punto donde se hace la llamada a fork. Si el padre desea esperar hasta que el hijo termine, entonces debe ejecutar una llamada a wait o a waitpid. PROTOTIPO DE LA FUNCIÓN #include #include pid_t wait (int *stat_loc) La llamada al sistema wait detiene el proceso que llama hasta que un hijo de éste termine o se detenga, o hasta que el proceso que la invocó reciba una señal. wait regresa de inmediato si el proceso no tiene hijos o si el hijo termina o se detiene y aún no se ha solicitado la espera. Si wait regresa debido a la terminación de un hijo, el valor devuelto es positivo e igual al ID de proceso de dicho hijo. De lo contrario, wait devuelve –1 y pone un valor en errno. Si errno es igual a ECHILD, indica que no existen procesos hijos a los cuales hay que esperar. Si errno es igual a EINTR, la llamada fue interrumpida por una señal. stat_loc es un apuntador a una variable entera. Después del llamado a wait, el estado de la información almacenada en la localidad apuntada por stat_loc puede ser analizada aplicando los siguiente macros: WIFEXITED (*stat_loc). Si en la evaluación el valor no es cero (true) entonces el proceso hijo termino normal. WEXITSTATUS (*stat_loc). Si el proceso hijo termina normalmente, este macro evalúa los 8 bits mas bajos del valor pasado por la función exit , _exit o return desde la función main. WIFSIGNALED (*stat_loc). Si en la evaluación el valor no es cero (true) el proceso hijo termino porque recibió una señal no controlada. WTERMSIG (*stat_loc). Si el proceso hijo finaliza por una señal que no fue capturada, este macro evalúa el número de la señal. El hijo regresa su estado llamando a exit, _exit o return. Por otra parte cuando se necesite esperar que un proceso especifico termine, se debe utilizar la función waitpid la cual suspende la ejecución del proceso en curso hasta que el hijo especificado por el argumento pid ha terminado, o hasta que se produce una señal 19 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos cuya acción es finalizar el proceso actual o llamar a la función manejadora de la señal. PROTOTIPO DE LA FUNCIÓN #include #include pid_t waitpid (pid_t pid, int *status, int options) *status es la localidad en la cual se devuelve la información del estado de terminación del hijo, pid contiene un valor que puede ser, -1 para indicar que espera a cualquier hijo, positivo indica que debe esperar al proceso cuyo PID sea ese número, 0 para indicar que espere a cualquier hijo cuyo Process Group ID sea igual al del proceso que invoco el llamado, negativo indica que espere a cualquier proceso cuyo Process Group ID sea igual al valor absoluto de PID. En options se coloca una combinación de las siguientes banderas: WEXITED que espera por hijos que hayan terminado, WSTOPPED que espera por hijos que hayan sido parados por recibir una señal, WNOHANG que no espera por un hijo que esta en ejecución, WNOWAIT deja al hijo sin modificar ni marcar en la tabla de procesos, tal que una posterior llamada se comportaría como si no hubiésemos hecho wait por dicho hijo, WUNTRACED que no esperar si el hijo está parado a no ser que este siendo trazado, WCONTINUED volver si un hijo ha continuado ejecutándose tras mandarle la señal SIGCONT. Las banderas WUNTRACED y WCONTINUED solo son efectivas si SA_NOCLDSTOP no ha sido establecida para la señal SIGCHLD. Terminación de procesos Como se ha visto el proceso debe terminar de alguna manera, es decir, de forma normal o anormal. Lo que se desea es una terminación normal, en el mejor de los casos, para esto el proceso debe hacer un llamado a la función exit. Esta función se encarga de retirar los recursos que está utilizando el proceso, así como dejarlo preparado para su eliminación, quitarlo del planificador e indicar su terminación a su padre, por medio de la señal SIGCHLD. Para pasar de un estado a otro se define un estado transitorio que en el sistema se le llama zombie. En linux si el proceso que termina no tuviera padre, ya que este acabó antes que él, se eliminaría directamente del planificador en la llamada exit, y es adoptado por el proceso 1 (init). 20 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROTOTIPO DE LA FUNCIÓN #include void exit (int status) El llamado a exit () termina la ejecución del proceso y devuelve el valor de estatus al proceso padre. Desde el sistema en Linux se puede consultar lo que devuelve el último proceso que finaliza por medio de la variable de entorno “?”. Ejemplo. Programa que muestra el empleo de wait. #include #include #include #include main() { pid_t hijo; int estado; if ( (hijo=fork()) == -1) { perror ("fallo el fork"); exit (1); } else if (hijo == 0) fprintf (stderr, "soy el hijo con pid = %ld \n", (long) getpid()); else if (wait(&estado) !=hijo) fprintf (stderr, "una señal debio interrumpir la espera \n"); else fprintf (stderr, "soy el padre con pid = %ld e hijo con pid = %ld\n", (long)getpid(),(long)hijo); exit(0); } Descripción de procesos El Sistema Operativo es el controlador de los sucesos que se producen en un sistema de computo. Es el Sistema Operativo el que planifica y expide a los procesos para su ejecución en el procesador, el que asigna los recursos a los procesos y el que 21 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos responde a las solicitudes de servicios básicos realizadas por los programas de usuario. Este concepto queda ilustrado en la Figura 2-4. Imagen del proceso Tabla de memoria Proceso 1 Tabla de E/S Memoria Dispositivos Tabla de archivos Archivos Procesos Tabla de procesos proceso 1 proceso 2 proceso 3 .. . Imagen del proceso Proceso n proceso n Figura 2-4. Procesos y recursos. 2.2 Estructuras de control del sistema operativo Si el Sistema Operativo va a administrar los procesos y los recursos, entonces tiene que disponer de información sobre el estado actual de cada proceso y de cada recurso. El método universal para obtener esta información es sencillo: el sistema operativo construye y mantiene tablas de información sobre cada entidad que esté administrando. P1 P2 Pn Memoria Virtual Recursos Procesador E/S E/S E/S Memoria Principal Figura 2-5. Procesos y recursos. Debemos tener claro que las tablas deben estar enlazadas o disponer de referencias cruzadas de alguna manera. La memoria, la E/S y los archivos son administrados en nombre de los procesos, por lo que debe haber alguna referencia directa o indirecta a estos recursos en la tablas de procesos. Los archivos que son referidos en las tablas de archivos son accesibles a través de un dispositivo de E/S y, algunas veces, estarán en memoria principal o en memoria virtual (Figura 2-5). 22 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Operaciones sobre procesos Los sistemas que administran procesos deben ser capaces de realizar ciertas operaciones sobre los procesos y con ellos. Tales operaciones incluyen: • • • • • • • • • Crear un proceso Destruir un proceso Suspender un proceso Reanudar un proceso Cambiar la prioridad de un proceso Bloquear un proceso Despertar un proceso Despachar un proceso Permitir que un proceso se comunique con otro (comunicación entre procesos) Crear un proceso implica operaciones tales como: • • • • • Dar un nombre al proceso Insertarlo en la lista de procesos conocidos del sistema (o tabla de procesos) Determinar la prioridad inicial del proceso Crear el bloque de control de proceso Asignar los recursos iniciales al proceso. 2.3 Sistema de llamada exec La llamada fork al sistema crea una copia del proceso que la llama. Muchas aplicaciones requieren que el proceso hijo ejecute un código diferente del de su padre. La familia exec de llamadas al sistema proporciona una característica que permite traslapar al proceso que llama con un módulo ejecutable nuevo. La manera tradicional de utilizar la combinación fork-exec es dejar que el hijo ejecute el exec para el nuevo programa mientras el padre continúa con la ejecución del código original. Existen seis variaciones de la llamada exec al sistema, las cuales se distinguen por la forma en que son pasados los argumentos de la línea de comando y el ambiente, y por si es necesario proporcionar la ruta de acceso y el nombre del archivo ejecutable. execl (execl, execlp y execle). Pasan los argumentos de la línea de comando como una lista y son útiles si se conoce el número de argumentos de la línea de comando en el momento de la compilación. 23 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROTOTIPO DE LA FUNCIÓN #include int execl (const char *path, const char *arg0, … , const char *argn, char * / *NULL*/); int execle (const char *path, const char *arg0, … , const char *argn, char * /*NULL*/, const char *envp[]); int execlp (const char *file, const char *arg0, … ,const char *argn, char */*NULL*/); execv (execv, execvp y execve). Pasan los argumentos de la línea de comando en un arreglo de argumentos. PROTOTIPO DE LA FUNCIÓN #include int execv (const char *path, const char *argv[]); int execvp (const char *file, const char *argv[]); int execve (const char *’path, const char *argv[], const char *envp[]); EJEMPLO. Programa que crea un proceso para ejecutar ls –l. #include #include #include #include #include main( ) { pid_t hijo; int estado; if (( hijo = fork( )) = = -1) { perror (“Error al ejecutar fork”); exit (1); } 24 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos else if (hijo = = 0) { if (execl (“/usr/bin/ls”, “ls”, “-l”, NULL) < 0) { perror (“Falla en la ejecución de ls”); exit (1); } } else if (hijo ! = wait (&estado)) perror (“Se presento una señal antes de la terminación del hijo”); exit (0); } NOTA. La función perror muestra un mensaje con el error estándar seguido por el de la última llamada al sistema o la biblioteca que lo produjo. PROTOTIPO DE LA FUNCIÓN #include int perror ( const char *s) El DIAGRAMA de estado para los procesos de UNIX es bastante complejo. • • • • • • • • • El proceso se está ejecutando en modo usuario. El proceso se está ejecutando en modo kernel. El proceso no se está ejecutando, pero está listo para ejecutarse tan pronto como el kernel lo ordene. El proceso está durmiendo cargado en memoria. El proceso está listo para ejecutarse, pero el swapper (proceso 0) debe cargar el proceso en memoria antes de que el kernel pueda ordenar que pase a ejecutarse. El proceso está durmiendo y el swappper ha descargado el proceso hacia una memoria secundaria (área de swap del disco) para crear espacio en la memoria principal donde poder cargar otros procesos. El proceso está volviendo del modo kernel al modo usuario, pero el kernel se apropia del proceso y hace un cambio de contexto, pasando otro proceso a ejecutarse en modo usuario. El proceso acaba de ser creado y está en un estado de transición; el proceso existe, pero ni está preparado para ejecutarse (estado 3), ni durmiendo (estado 4). Este estado es el inicial para todos los procesos, excepto el proceso 0. El proceso ejecuta la llamada exit y pasa al estado zombi. El proceso ya no existe, pero deja para su proceso padre un registro que contiene el código de salida y 25 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos algunos datos estadísticos tales como los tiempos de ejecución. El estado zombi es el estado final de un proceso. // Colocar figura de estados de los procesos en UNIX 2.4. Hilos Los hilos representan una manera de trabajar con diferentes procesos no emparentados. Para utilizarlos se necesita contar con la librería pthreads que es un estándar de POSIX (Portable Operating System Interface). Para los sistemas UNIX, un estándar de programación C para interface de programación de hilos se encuentra especificada por el estándar IEEE POSIX 1003.1c. Las implementaciones que se basan en este estándar son referenciados como POSIX threads o Pthreads. La diferencia entre un hilo y un proceso es que los procesos no comparten la misma memoria, mientras que los hilos sí comparten totalmente la memoria entre ellos. Para la creación de los hilos se usan las funciones de la librería pthread o de cualquier otra que soporte threads mientras que para crear procesos usaremos la llamada al sistema fork(). Para compilar programas que hagan uso de la librería pthread, usando GNU cc o GNU Compiler Collection gcc ejecutamos la orden: cc programa_con_pthreads.c -o programa_con_pthreads -lpthread o gcc programa_con_pthreads.c -o programa_con_pthreads -lpthread Tabla 2-2. Lista de llamados en POSIX 1.c. Descripción POSIX Gestión de hilos pthread_create pthread_exit pthread_kill pthread_join pthread_self Exclusión mutua pthread_mutex_init pthread_mutex_destroy pthread_mutex_lock pthread_mutex_trylock pthread_mutex_unlock 26 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos variables de condición pthread_cond_init pthread_cond_destroy pthread_cond_wait pthread_cond_timedwait pthread_cond_signal pthread_cond_broadcast Creación de hilos La función pthread_create es usada para crear un hilo, con ciertos atributos, y esté ejecutará una determinada función o subrutina con los argumentos que se le indique. PROTOTIPO DE LA FUNCIÓN #include int pthread_create (pthread_t *thread, const pthread_attr_t *attr, void* (*start_routine) (void *), void *arg) Los atributos para un proceso son especificados en attr, si attr es NULL, el atributo por omisión es usado. Si la función se realiza con éxito, se almacena el ID del hilo en la localidad referenciada por thread. El hilo que está creado ejecuta la función o rutina start_routine con arg como su argumento. Si necesitamos pasar o devolver más de un parámetro a la vez, se puede crear una estructura y colocar ahí los campos necesarios. Luego se pasa o se devuelve la dirección de esta estructura como único parámetro. Cuando finaliza start_routine se llama implícitamente a pthread_exit() o su equivalente. El estado de las señales del nuevo hilo será: • Se heredará la máscara de señales del hilo creador • El conjunto de señales pendientes del nuevo hilo estará vacío. Un hilo termina si: • Se llama a pthread_exit(), especificando un valor de estado final que es disponible para otros hilos en el mismo proceso llamando a pthread_join() • Realiza un return desde start_routine que es equivalente a pthread_exit() • Es cancelado pthread_cancel() • El hilo principal ejecuta un return desde main. Causando la terminación de todos los hilos. 27 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos pthread_create retorna 0 en caso de éxito, o un número de error en otro caso, y el contenido de *thread se indefine. Los errores que pueden retornados en errno son: • EAGAIN. Insuficiente recursos para crear un hilo, o el límite de los hilos del sistema fueron alcanzados (en Linux vea /proc/sys/kernel/threads-max) • EINVAL. Inválido el atributo. • EPERM. Política de planificación no permitida y los parámetros de attr. Terminación de un hilo La función pthread_exit() terminará la ejecución del hilo que haga su invocación y hará disponible el valor value_ptr para cualquier join con éxito con el hilo que hace la llamada. PROTOTIPO DE LA FUNCIÓN #include int pthread_exit (void *value_ptr) Atributos de un hilo La función pthread_attr_init () se encarga de inicializar el objeto de atributos attr del hilo con los valores por defecto utilizado en una implementación. PROTOTIPO DE LA FUNCIÓN #include int pthread_attr_init ( pthread_attr_t *attr) Destrucción de los atributos de un hilo La función pthread_attr_destroy () se encarga de destruir el objeto de atributos attr del hilo con valores no definidos en una implementación. Un objeto de atributos destruido con función podrá ser inicializado posteriormente con la función pthread_attr_init(). 28 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROTOTIPO DE LA FUNCIÓN #include int pthread_attr_destroy (pthread_attr_t *attr) Espera la terminación de un hilo creado La función pthread_join() suspenderá la ejecución del hilo que hace la llamada, hasta que el hilo destino termine. Esta función es un mecanismo que permite la sincronización de hilos. PROTOTIPO DE LA FUNCIÓN #include int pthread_join ( pthread_t thread, void **value_ptr) El valor que pase el thread destino con la función pthread_exit() estará disponible en la localidad de memoria a la que hace referencia value_ptr. La función espera hasta que termine el hilo especificado en thread. La función retorna 0 en caso de éxito o el número de error en otro caso. Los errores pueden ser: • EDEADLK. Un deadlock fue detectado, es decir, dos hilos esperan uno del otro. • EINVAL. thread no está unido a otro hilo. • ESRCH. El hilo con ID thread no fue encontrado. Hilo Origen Creando hilo pthread_create() Esperando pthread_join () Hilo Creado (en ejecución) Hilo Terminando pthread_exit() Hilo Origen Figura 2-6. Sincronización de hilos. 29 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos EJEMPLO. El siguiente código muestra la creación de un par de hilos. #include #include #include void *funcionmensaje(void *ptr); int main (void) { pthread_t hilo1, hilo2; char *mensaje1= "hilo 1"; char *mensaje2= "hilo 2"; int uno,dos; uno= pthread_create (&hilo1, NULL, funcionmensaje, (void *)mensaje1); dos= pthread_create (&hilo2, NULL, funcionmensaje, (void *)mensaje2); pthread_join (hilo1,NULL); pthread_join (hilo2,NULL); printf ("Hilo 1 retorna: %d\n",uno); printf ("Hilo 2 retorna: %d\n",dos); return(0); } void *funcionmensaje (void *ptr) { char *mensaje; } mensaje= (char *)ptr; printf("%s\n",mensaje); Referencia [1] Posix Threads Programming. https://computing.llnl.gov/tutorials/pthreads/ [2] K. A. Robbins, S. Robbins, UNIX Programación Práctica, Prentice Hall, Primera Edición, 1997. 30 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 3 Administración de procesos Un proceso es una entidad en ejecución que tiene asociada un identificador para poder ser identificado. En el sistema se cuenta con procesos pesados, llamados hijos, y procesos ligeros, llamados hilos. 3.1 Concurrencia: Exclusión mutua y Sincronización Los puntos clave en los que se basan los Sistemas Operativos son los procesos. Todos los procesos cuentan con las siguientes dos características: • • Unidad de propiedad de los recursos: A cada proceso se le asigna un espacio de direcciones virtuales para almacenar la imagen del proceso, se le asigna memoria virtual y otros recursos, tales como canales de E/S, dispositivos de E/S y archivos. A esto se le suele llamar tarea. Unidad de expedición: Un proceso es una camino de ejecución a través de uno o más programas. Esta ejecución puede ser intercalada con la de otros procesos. De este modo, un proceso tiene un estado de ejecución (Ejecución, listo, etc.) y una prioridad de expedición. Cuando los procesos obtienen acceso a datos compartidos modificables, se debe poner en práctica una acción llamada exclusión mutua, y sólo cuando los procesos realizan operaciones que no entran en conflicto con otras, debe permitirse que procedan concurrentemente. Cuando n proceso obtiene acceso a datos compartidos modificables, se dice que se encuentran en una sección crítica (o región crítica). Es evidente que, para evitar problemas, los demás procesos (o al menos los que tengan acceso a los datos compartidos) no puedan entrar a sus propias secciones críticas. Las secciones críticas deben ejecutarse tan rápido como sea posible; un proceso no se debe bloquear dentro de su propia sección crítica y las secciones críticas deben codificarse con mucho cuidado (para evitar, por ejemplo, la posibilidad de ciclos infinitos). Si un proceso de una sección crítica termina, ya sea voluntaria o involuntariamente, el Sistema Operativo, al realizar su mantenimiento de terminaciones, debe liberar la exclusión mutua de manera que otros procesos puedan entrar en sus regiones críticas. 31 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Requisitos para la exclusión mutua El uso adecuado de la concurrencia entre procesos exige la capacidad de definir secciones críticas y hacer cumplir la exclusión mutua. Esto es fundamental para cualquier esquema de proceso concurrente. Cualquier servicio o capacidad que dé soporte para la exclusión mutua debe cumplir los requisitos siguientes: • • • • Los procesos que se encuentran fuera de su sección crítica no pueden impedir que otros procesos entren en sus propias secciones críticas. Un proceso permanece en su sección crítica sólo por un tiempo finito. No se pueden hacer suposiciones sobre la velocidad relativa de los procesos o su número. No se debe postergar indefinidamente la entrada de un proceso a su sección crítica. Típicamente en la teoría de sistemas operativos se tratan en primer lugar los algoritmos de Dekker y de Peterson, esto para mostrar al estudiante la manera que se ha intentado resolver el problema de que dos o mas procesos compartan un determinado recurso, y pongan en practica la exclusión mutua. Así que veamos primero los intentos de Dekker, de mostrar al lector la exclusión mutua con dos procesos concurrentes, y el algoritmo de Peterson para solucionar también la exclusión mutua de dos procesos. 32 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 3.1 Algoritmos de DEKKER Primer intento: Especifica el código que permite poner en práctica la exclusión mutua en el contexto de un programa concurrente con dos procesos /* Variable global compartida */ int numero_proceso; /**** Inicia principal ***/ numero_proceso = 1; /** Inicia concurrente */ PROCESO_UNO ( ); PROCESO_DOS ( ); /** termina concurrencia ***/ /*** Termina principal ****/ Procesos Concurrentes PROCESO_UNO while true { while (numero_proceso == 2); < sección crítica uno > numero_proceso = 2; /* salir de la exclusión mutua */ otras_tareas_uno; } PROCESO_DOS while true { while (numero_proceso == 1); < sección crítica dos > numero_proceso = 1; /* salir de la exclusión mutua */ otras_tareas_dos; } NOTAS. • • • Como el procesador está en uso mientras PROCESO_DOS no hace nada (excepto verificar el valor de número_proceso), esto se conoce como espera activa. La espera activa se considera una técnica aceptable cuando las esperas anticipadas son cortas; de lo contrario, la espera activa puede resultar costosa. Los procesos deben entrar y salir de sus secciones críticas de manera estrictamente alternada. Si uno de los procesos necesita hacerlo con mucha mayor frecuencia que el otro, se verá restringido a operar con una velocidad mucho menor que la requerida. Un problema mucho más serio es que si un proceso falla, el otro proceso se bloquea permanentemente. 33 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Segundo intento /* Variable global compartida */ p1adentro, p2adentro: boolean; /**** Inicia principal ***/ p1adentro = false; p2adentro = false; /** Inicia concurrente */ PROCESO_UNO ( ); PROCESO_DOS ( ); /** termina concurrencia ***/ /*** Termina principal ****/ Procesos Concurrentes PROCESO_UNO while true { while (p2adentro); p1adentro = true; < sección crítica uno > p1adentro = false; /* salir de la exclusión mutua */ otras_tareas_uno; } PROCESO_DOS while true { while (p1adentro); p2adentro = true; < sección crítica dos > p2adentro = false; /* salir de la exclusión mutua */ otras_tareas_dos; } NOTAS. El problema que existe en esta versión es que ni siquiera se garantiza la exclusión mutua. Este problema se debe a que, entre el momento en que un proceso determina mediante la condición while que puede seguir adelante y el momento en que asigna el valor cierto a una bandera para indicar que se encuentra en su sección crítica, hay tiempo suficiente para que el otro proceso verifique su bandera y entre en su sección crítica. Por lo tanto, en el momento en que un proceso realiza su verificación deberá estar seguro de que el otro proceso no podrá pasar su verificación. El segundo intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado pero antes de que pueda entrar en su sección crítica. Quizá se pueda arreglar este problema con un simple intercambio de dos líneas. 34 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Tercer intento /* Variable global compartida */ p1deseaentrar, p2deseaentrar: boolean; /**** Inicia principal ***/ p1deseaentrar = false; p2deseaentrar = false; /** Inicia concurrente */ PROCESO_UNO ( ); PROCESO_DOS ( ); /** termina concurrencia ***/ /*** Termina principal ****/ Procesos Concurrentes PROCESO_UNO PROCESO_DOS while true while true { { p1deseaentrar = true; p2deseaentrar = true; while (p2deseaentrar); while (p1deseaentrar); < sección crítica uno > < sección crítica dos > p1deseaentrar = false; /* salir de la p2deseaentrar = false; /* salir de la exclusión mutua */ exclusión mutua */ otras_tareas_uno; otras_tareas_dos; } } NOTAS. Esta solución garantiza la exclusión mutua, pero origina un problema más. Si ambos procesos ponen sus señales a “true” antes de que ambos hayan ejecutado la sentencia while, cada uno pensará que el otro ha entrado en su sección crítica. El resultado es un interbloqueo. En el tercer intento, un proceso fijaba su estado sin conocer el estado del otro. El interbloqueo se produce porque cada proceso puede insistir en su derecho para entrar en la sección crítica; no hay opción para volver atrás desde esta situación. Se puede intentar arreglar esto haciendo que los procesos sean más educados: deben activar su señal para indicar que desean entrar en la sección crítica, pero deben estar listos para desactivar la señal y ceder la preferencia al otro proceso. 35 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Cuarto intento /* Variable global compartida */ p1deseaentrar, p2deseaentrar: boolean; /**** Inicia principal ***/ p1deseaentrar = false; p2deseaentrar = false; /** Inicia concurrente */ PROCESO_UNO ( ); PROCESO_DOS ( ); /** termina concurrencia ***/ /*** Termina principal ****/ Procesos Concurrentes PROCESO_UNO PROCESO_DOS while true while true { { p1deseaentrar = true; p2deseaentrar = true; while (p2deseaentrar) while (p1deseaentrar) { { p1deseaentrar = false; p2deseaentrar = false; retraso (aleatorio, algunosciclos); retraso (aleatorio, algunosciclos); p1deseaentrar = true; p2deseaentrar = true; } } < sección crítica uno > < sección crítica dos > p1deseaentrar = false; /* salir de la p2deseaentrar = false; /* salir de la exclusión mutua */ exclusión mutua */ otras_tareas_uno; otras_tareas_dos; } } NOTAS. La exclusión mutua está garantizada y no se puede producir un bloqueo mutuo, pero puede originarse otro problema potencialmente grave: un aplazamiento indefinido. Todo puede ocurrir porque, dado que no suponemos nada acerca de las velocidades relativas de los procesos concurrentes asíncronos, han de considerarse todas las posibles secuencias de ejecución. Los procesos podrían ejecutarse en tándem (realizar la acción en forma común), por ejemplo: cada proceso puede asignar el valor “true” a su bandera, realizar la verificación, entrar en el cuerpo del ciclo while, asignar el valor “false” a su bandera, asignar el valor cierto a su bandera y después repetir la secuencia comenzando con la verificación. Mientras ocurre esto, las condiciones verificadas se siguen cumpliendo. Esta situación tiene pocas probabilidades de ocurrir, pero podría darse el caso. Si un sistema que usara este tipo de exclusión mutua se empleara para controlar un vuelo espacial, un marcapasos o un sistema de control de tráfico aéreo, estarían latente la posibilidad de un aplazamiento indefinido y la consiguiente falla del sistema. 36 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos A continuación se muestra el algoritmo de DEKKER que maneja la exclusión mutua entre dos procesos, sin ninguna instrucción especial de hardware. Algoritmo de DEKKER /* Variable global compartida */ p1deseaentrar, p2deseaentrar: boolean; proceso_favorecido /**** Inicia principal ***/ p1deseaentrar = false; p2deseaentrar = false; proceso_favorecido = primero; /** Inicia concurrente */ PROCESO_UNO ( ); PROCESO_DOS ( ); /** termina concurrencia ***/ /*** Termina principal ****/ Procesos Concurrentes PROCESO_UNO while true { p1deseaentrar = true; while (p2deseaentrar) if (proceso_favorecido == segundo ) { p1deseaentrar = false; while (proceso_favorecido == segundo) ; p1deseaentrar = true; } < sección crítica uno > proceso_favorecido = segundo; p1deseaentrar = false; /* salir de la exclusión mutua */ otras_tareas_uno; } PROCESO_DOS while true { p2deseaentrar = true; while (p1deseaentrar) if (proceso_favorecido == primero ) { p2deseaentrar = false; while (proceso_favorecido == primero) ; p2deseaentrar = true; } < sección crítica dos > proceso_favorecido = primero; p2deseaentrar = false; /* salir de la exclusión mutua */ otras_tareas_dos; } 37 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 3.3 ALGORITMO DE PETERSON En 1981, G.L. Peterson publicó un algoritmo mucho más sencillo para manejar una exclusión mutua de dos procesos con espera activa. Algoritmo de PETERSON /* Variable global compartida */ p1deseaentrar, p2deseaentrar: boolean; proceso_favorecido /**** Inicia principal ***/ p1deseaentrar = false; p2deseaentrar = false; proceso_favorecido = primero; /** Inicia concurrente */ PROCESO_UNO ( ); PROCESO_DOS ( ); /** termina concurrencia ***/ /*** Termina principal ****/ Procesos Concurrentes PROCESO_UNO while true { p1deseaentrar = true; proceso_favorecido = segundo while (p2deseaentrar && proceso_favorecido == segundo ); < sección crítica uno > p1deseaentrar = false; /* salir de la exclusión mutua */ otras_tareas_uno; } PROCESO_DOS while true { p2deseaentrar = true; proceso_favorecido = primero while (p1deseaentrar && proceso_favorecido == primero ); < sección crítica dos > p2deseaentrar = false; /* salir de la exclusión mutua */ otras_tareas_dos; } 3.4 Exclusión mutua de N procesos Existen varios algunos para solucionar por software la exclusión mutua de n procesos entre los que se encuentran: • • • • Algoritmo desarrollado por Dijkstra. Publicado en: ”Solution of a problem in concurrent programming control” Algoritmo desarrollado por Knuth. Publicado en: “Additional comments on a problem in concurrent programming control” Algoritmo desarrollado por Eisenberg y McGuire. Publicado en : “Further comments on Dijkstra’s concurrent programming control problem” Algoritmo desarrollado por Lamport (Lamport´s Bakery Algorithm). Publicado en : “A new solution to Dijkstra’s concurrent programming problem”. 38 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • • • Algoritmo desarrollado por Brich Hansen. Publicado en: “Distributed processes – a concurrent programming concept”. Algoritmo desarrollado por Burns. Publicado en : “ Data requeriments for implementation of n-process mtual exclusión using a single shared variable” Algoritmo desarrollado por Carvalho y Roucairol. Publicado en: “On mutual exclusión in computer networks”. 3.5 Exclusión Mutua: Soluciones por hardware En una máquina monoprocesador, la ejecución de procesos concurrentes no puede superponerse; los procesos sólo pueden intercalarse. Es más, un proceso continuará ejecutándose hasta que solicite un servicio del sistema operativo o hasta que sea interrumpido. Por lo tanto, para garantizar la exclusión mutua, es suficiente con impedir que un proceso sea interrumpido. Esta capacidad puede ofrecerse en forma de primitivas definidas por el núcleo del sistema para habilitar o inhabilitar las interrupciones. /***** Programa Principal ******/ ***** Concurrentes ***** P(1); P(2); ...... P(n); ***** Termina concurrentes ***** P (int i) While (true) do { entrada a region critica; salida de región crítica; otras operaciones } Puesto que la sección crítica no puede ser interrumpida, la exclusión mutua está garantizada. Sin embargo, el precio de esta solución es alta. La eficiencia de la ejecución puede verse notablemente degradada debido a que se limita la capacidad del procesador para intercalar programas. Instrucciones especiales de la máquina. A nivel de hardware, como se ha mencionado los accesos a posiciones de memoria excluyen cualquier otro acceso a la misma posición. Con esta base, los diseñadores han propuesto varias instrucciones de máquina que realizan dos acciones atómicamente, tales como leer y escribir o leer y examinar, sobre una misma posición de memoria en un único ciclo de lectura de instrucción. Puesto que estas acciones se realizan en un único ciclo de instrucción, no están sujetas a injerencias por parte de otras instrucciones. 39 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos /************ Esto maneja Stallings ********/ Dos instrucciones implementadas más habitualmente son: Comparar y Fijar. La instrucción Comparar y Fijar (TS, Test and Set) puede definirse de la siguiente forma: Booleano TS (int i) { if (i==0) { I=1; TS = true; } else TS = false; } La función Comparar y Fijar se ejecuta en su totalidad, es decir, no está sujeta a interrupciones. /************************************************/ La clave del éxito aquí es contar con una sola instrucción de hardware que lea una variable, almacene su valor en un área segura y asigne a la variable cierto valor. Una vez que se inicia, esta instrucción, llamada frecuentemente probar y fijar (test and set), realizará todas esta funciones sin interrupción. Probaryfijar ( a, b ) a!b b ! true /** Variable global ***/ booleano : activo ; /** principal ****/ activo = false; /** Concurrente **/ PROCESO_UNO( ); PROCESO_DOS( ); /**** termina principal ****/ PROCESO_UNO { while true { uno_no_puede_entrar = true; while uno_no_puede_entrar activo = false; otras_tareas_uno; } } probaryfijar (uno_no_puede_entrar, activo) 40 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROCESO_DOS { while true { dos_no_puede_entrar = true; while dos_no_puede_entrar activo = false; otras_tareas_dos; } } probaryfijar (dos_no_puede_entrar, activo) Esta solución puede adolecer de aplazamiento indefinido, pero la probabilidad de que ocurra es muy pequeña, sobre todo si existen varios procesadores. En el instante en que un proceso abandona su sección crítica y asigna falso a activo, es muy probable que el otro proceso, al ejecutar probaryfijar “se apodere” de activo (asignándole el valor cierto) antes de que el primer proceso pueda repetir el ciclo y asigne el valor cierto. Propiedades de las soluciones con instrucciones de máquina. El uso de instrucciones especiales e la máquina para hacer cumplir la exclusión mutua tiene varias ventajas: • • • Es aplicable a cualquier número de procesos en sistemas con memoria compartida, tanto de monoprocesador como de multiprocesador. Es simple y fácil de verificar. Puede usarse para disponer de varias secciones crítica; cada sección crítica puede definirse con su propia variable. Algunas desventajas importantes son las siguientes: • • • Se emplea espera activa. Así, mientras un proceso está esperando para acceder a la sección crítica, continúa consumiendo tiempo del procesador. Puede producir inanición. Cuando un proceso abandona la sección crítica y hay más de un proceso esperando, la selección es arbitraria. Así, se podría denegar el acceso a algún proceso indefinidamente. Puede producir interbloqueo. Debido a estos inconvenientes tanto de las soluciones por software como por hardware, es necesario buscar otros mecanismos. 41 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 3.6 Teoría de Semáforos El primer gran avance en la resolución de los problemas de procesos concurrentes llegó en 1965, con el tratado de Dijkstra sobre la cooperación entre procesos secuenciales [Cooperating Sequential Processes]. Dijkstra estaba interesado en el diseño de un sistema operativo como un conjunto de procesos secuenciales cooperantes y en el desarrollo de mecanismos eficientes y fiables para dar soporte a la cooperación. Los procesos de usuario podrán utilizar estos mecanismos en tanto que el procesador y el sistema operativo los hagan disponibles. El principio fundamental es el siguiente: dos o más procesos pueden cooperar por medio de simples señales, de forma que se pueda obligar a detenerse a un proceso en una posición determinada hasta que reciba una señal específica. Cualquier requisito complicado de coordinación puede satisfacerse por medio de la estructura de señales adecuada. Para la señalización, se usan variables especiales llamadas semáforos. Para transmitir una señal por el semáforo s, los procesos ejecutan la primitiva signal(s). Para recibir una señal del semáforo s, los procesos ejecutan la primitiva wait(s); si la señal correspondiente aún no se ha transmitido, el proceso es suspendido hasta que tenga lugar su transmisión. En el artículo original de Dijkstra y en gran parte de la bibliografía, se emplea la letra P para wait y la letra V para signal; estas son las iniciales de las palabras holandesas que significan comprobar (proberen) e incrementar (verhogen). Para lograr el efecto deseado, se pueden contemplar los semáforos como variables que tienen un valor entero sobre el que se definen las tres operaciones siguientes: 1. Un semáforo puede inicializarse con un valor no negativo. 2. La operación wait decrementa el valor del semáforo. Si el valor se hace negativo, el proceso que ejecuta el wait se bloquea. P(s) Si S > 0 Entonces S = S –1 Si no (esperar S) 3. La operación signal incrementa el valor del semáforo. Si el valor no es positivo, se desbloquea a un proceso bloqueado por una operación wait. V(s) Si (uno o más procesos esperan S) Entonces (dejar que prosiga uno de esos procesos) Si no S = S + 1 Un semáforo es una variable protegida cuyo valor sólo puede ser leído y alterado mediante las operaciones P- wait, y V – signal y una operación de asignación de valores iniciales que llamaremos inicia_semáforo. 42 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Uso de un semáforo y de las primitivas P y V para asegurar la exclusión mutua Muestra cómo pueden utilizarse los semáforos para implantar la exclusión mutua. Ahí P (activo) equivale a entrar a la exclusión mutua y V(activo) equivale a salir de la exclusión mutua. Versión del libro de Deitel { /* principal */ inicia_semáforo (activo, 1); /* en concurrentes */ proceso_uno; proceso_dos; } /* fin de principal */ Procesos Concurrentes proceso_uno { while true do { tareas_preliminares_uno; P (activo); Sección crítica uno; V (activo); Otras tareas uno; } } proceso_dos { while true do { tareas_preliminares_dos; P (activo); Sección crítica dos; V (activo); Otras tareas dos; } } Definición de las primitivas de los semáforos binarios (versión del libro de William Stalling) Versión del libro de William Stalling Type semáforo binario = record Valor : (0, 1); Cola : list of proceso; End; var s: semaforo binario; Procesos Concurrentes 43 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Versión del libro de William Stalling waitB (s): if s.valor = 1 then s.valor = 0; else begin poner este proceso en s.cola; bloquera este proceso; end; signal (s): if s.cola está vacia then s.valor = 1; else begin quitar un proceso P de s.cola; poner el proceso P en la cola de listos end; Tanto en los semáforos como en los semáforos binarios se emplea una cola para mantener los procesos esperando en el semáforo. La definición no dicta el orden en el que se quitan los procesos de dicha cola. La política más equitativa es FIFO: el proceso que ha estado bloqueado durante más tiempo se libera de la cola. La única exigencia estricta es que un proceso no debe quedar retenido en la cola de un semáforo indefinidamente porque otros procesos tengan preferencia. 3.7 Problema del productor-consumidor Problema del Productor-Consumidor var int buffer_número; semáforo número_depositado; semáforo número_recuperado; /* Principal */ inicia_semáforo (número_depositado, 0); inicia_semáforo (número_recuperado, 1); /* forma concurrente */ proceso_productor; proceso_consumidor; /* fin de concurrente */ /* fin principal */ Procesos Concurrentes proceso_productor while true { calcular_siguiente_resultado; P(número_recuperado); Buffer_número = siguiente_resultado; V (número_deposita); } proceso_consumidor while true { P(número_depositado); siguiente_resultado = buffer_número; V (número_recuperado); Escribir (siguiente_resultado); } El anterior programa concurrente utiliza operaciones de semáforo para poner en práctica una relación productor-consumidor. 44 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Se han empleado dos semáforos: el productor indica número_depositado (con V) y el consumidor lo verifica (con P); el consumidor no puede proseguir en tanto no se deposite un número en buffer_número. El consumidor indica número_recuperado con una operación V y el productor lo verifica con una operación P; el productor no puede proseguir hasta que se haya recuperado un número de buffer_número. Los valores inciales de los semáforos obligan al productor a depositar un valor en buffer_número antes de que el consumidor pueda proseguir. Obsérvese que el uso de los semáforos en este programa impone una sincronización en tándem; esto es aceptable porque existe solamente una variable compartida. En las relaciones productor-consumidor es muy común tener un buffer con espacio para varias variables. Con una disposición así no es necesario que el productor y el consumidor se ejecuten “a la misma velocidad” en la sincronización en tándem. Aunque, un productor rápido puede depositar muchos valores mientras el consumidor está inactivo y un consumidor rápido puede recuperar otros tantos mientras el productor está inactivo. Semáforos contadores. Los semáforos contadores son particularmente útiles cuando hay que asignar un recurso a partir de un banco de recursos idénticos. El semáforo tiene como valor inicial el número de recursos contenidos en el banco. Cada operación P decrementa en uno el semáforo, indicando que se ha retirado un recurso del banco y que lo está utilizando algún proceso. Cada operación V incrementa en uno el semáforo, lo que indica la devolución de un recurso al banco y que el recurso puede ser asignado a otro proceso. Si se intenta una operación P cuando el semáforo tiene un valor 0, el proceso deberá esperar hasta que se devuelva un recurso al banco mediante una operación V. Los semáforos pueden servir para llevar a la práctica un mecanismo de sincronización bloquear/despertar: un proceso se bloquea a sí mismo mediante P(S), con S = 0 inicialmente, para esperar que ocurra un evento; otro proceso detecta el evento y despierta al proceso bloqueado mediante V(S). En una relación productor-consumidor, un proceso, el productor genera información que utiliza un segundo proceso, el consumidor. Esto es un ejemplo de comunicación entre procesos. Si estos procesos se comunican por medio de un buffer compartido, el productor no debe producir cuando el buffer está lleno y el consumidor no debe consumir cuando el buffer está vacío. La implantación de estas restricciones es un ejemplo de la sincronización de procesos. Los semáforos contadores son particularmente útiles cuando un recurso debe asignarse a partir de un banco de recursos idénticos. Cada operación P indica que se ha asignado un recurso; cada operación V indica que se ha devuelto al banco un recurso. Las operaciones de semáforos pueden llevarse a la práctica con espera activa, pero hacerlo puede ser un desperdicio. Las operaciones de semáforos pueden incluirse en el núcleo para evitar la espera activa. En un sistema con un solo procesador, la indivisibilidad de P y V pueden asegurarse inhabilitando las interrupciones mientras P y V manipulan semáforos. En un sistema de múltiples procesadores, puede asignarse a un procesador la tarea de controlar a los demás y asegurar así la exclusión mutua. Esta técnica puede usarse también en sistemas distribuidos, pero es más común que cada procesador de un sistema distribuido tenga su propio núcleo. 45 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Desventajas • • • • Si se omite P, no se obtiene la exclusión mutua. Si se omite V, las tareas que están esperando por causa de operaciones P podrían quedar en bloqueo permanente. Una vez que comienza una operación P, el usuario no puede arrepentirse y seguir otro curso de acción mientras el semáforo esté en uso. Una tarea sólo puede esperar un semáforo a la vez. 3.8 Semáforos programación practica POSIX.1b Un semáforo es un número entero variable con dos operaciones atómicas: wait y signal. En la terminología de POSIX.1b, estas operaciones son llamadas cerrojo de semáforo y apertura de semáforo. A lo largo de esta sección de utilizan semáforos variables del tipo semaphore_t, los cuales siempre contienen un número entero variable que un proceso siempre está en posibilidad de probar, incrementar o reducir, a través de las operaciones asociadas de semáforo. void wait (semaphore_t *sp) { while (*sp <=0); (*sp)--; } void signal (semaphore_t *sp) { (*sp)++; } Ejemplo. El siguiente código protege una sección critica si el semáforo variable S es iniciado a 1. wait (&s) signal (&s) Los procesos que utilizan semáforos deben cooperar para asegurar que se obtenga una independencia exclusiva. El código anterior protege a una sección crítica siempre y cuando todos los procesos ejecuten wait(&s) antes de entrar a sus respectivas secciones críticas, y siempre y cuando ejecuten la signal(&s) al salir. Ejemplo. ¿Qué sucedería si en el ejemplo anterior S inicialmente tuviera un valor de 0? ¿qué pasaría si S tuviera un valor inicial de 8? Respuesta: Si S inicialmente tuviera un valor de 0, entonces cada wait (&s) sería bloqueado y se establecería una espera indefinida (deadlock), a menos que algún otro proceso inicializara S a 1. Si S inicialmente tuviera un valor de 8, entonces sólo un máximo de ocho procesos se ejecutarían concurrentemente en sus secciones críticas. 46 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Ejemplo. ¿Qué sucedería si en el siguiente pseudocódigo los semáforos S y Q tuvieran inicialmente el valor de 1? Process 1 executes: for ( ; ; ) { wait (&S); a; signal (&Q); } Process 2 executes: for ( ; ; ) { wait (&Q); a; signal (&S); } Respuesta: Cualquiera de ambos procesos puede ejecutar su orden wait primero. Los semáforos se encargan de que cualquier proceso específico no éste más delante de una iteración que el otro proceso. Si un semáforo está inicialmente en 1 y el otro está en 0, los procesos procederán a ejecutarse en forma estrictamente alterna. Si los dos semáforos están inicialmente en 0, entonces ocurre una espera infinita (deadlock). Ejercicio. ¿Qué sucedería si S estuviera iniciado a 8 y Q a 0? Respuesta: El proceso uno siempre estará entre cero y ocho iteraciones adelante del proceso dos. Si el valor de S representa ranuras vacías y el valor de Q representa elementos en esas ranuras, el proceso uno adquiere ranuras y produce elementos, mientras que el proceso dos adquiere elementos y produce ranuras vacías. Esta generalización sincroniza el acceso a un almacenamiento temporal que puede acomodar no más de ocho elementos. Ejercicio. ¿Qué pasaría con el siguiente pseudocódigo si los semáforos S y Q tuvieran un valor inicial de 1? Process 1 executes: for (; ;) { wait (&Q); wait (&S); a; signal (&S); signal (&Q); } 47 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Process 2 executes: for (; ;) { wait (&S); wait (&Q); a; signal (&Q); signal (&S); } Respuesta: El resultado dependería del orden en que los procesos llegaran a la CPU. Este código debería trabajar la mayor parte del tiempo, pero si el proceso uno pierde a la CPU después de la ejecución del wait(&Q) y el proceso dos logra entrar, ambos procesos se bloquean en un segundo wait y ocurre una espera infinita (deadlock). 3.9 Monitores Un monitor es una construcción para concurrencia que contiene los datos y los procedimientos necesarios para asignar un recurso compartido específico reutilizable en serie o un grupo de estos recursos. El concepto de monitor fue propuesto por Dijkstra, luego por Brich Hansen y después fue mejorado por Hoare. Para ejecutar una función de asignación de recursos, un proceso debe llamar a una entrada del monitor específica. Algunas característica de los monitores son: • • • • • • • Muchos procesos pueden desear entrar en el monitor en diversos momentos, pero la exclusión mutua se mantiene, sólo se permite la entrada de un proceso a la vez. Los procesos que desean entrar en el monitor cuando ya está en uso deben esperar. Un monitor controla automáticamente la espera de los procesos. Desarrollo de la técnica ocultación de la información: los datos dentro del monitor pueden ser globales con respecto de todos los procedimientos del monitor o locales con respecto de un procedimiento específico. Si un proceso que está llamando a la entrada del monitor encuentra que el recurso requerido, ya ha sido asignado, el procedimiento monitor llama a la función “esperar”, y aguarda fuera del monitor hasta que se libere el recurso. El proceso que tiene un recurso llamará a una entrada del monitor para devolver el recurso al sistema, después de esto la entrada del monitor invoca a la función “señalar” para permitir que uno de los procesos en espera adquiera el recurso. La asignación del recurso se realiza por prioridad, el de mayor prioridad es el que tiene más tiempo esperando el recurso, esto para evitar el aplazamiento indefinido. Se asocia una variable condicional a cada una de las diversas razones por las que un proceso puede verse obligado a esperar. Así tenemos:  Esperar (nombre de la variable condicional)  Señalar (nombre de la variable condicional) Hagamos notar que a cada variable condicional que se crea se le asocia una cola. 48 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Asignación simple de recursos mediante monitores Monitor asignador_de_recursos recurso_en_uso : bolean; recurso_libre : condition: { recurso_en_uso = false; } /* El siguiente procedimiento es similar al procedimiento P para semáforos */ obtener_recurso { if recurso_en_uso esperar (recurso_libre); recurso_en_uso = true; } /* El siguiente procedimiento es similar al procedimiento V para semáforos */ devolver_recurso { recurso_en_uso = false; señalar (recurso_libre); } Ejemplo de monitor: el buffer circular Un mecanismo de buffer circular es adecuado para implantar el control de spool en los sistemas operativos. Un spooler es un proceso que produce líneas, y un despooler es un proceso que lee las líneas del buffer circular y las escribe en la impresora, este proceso trabaja a una velocidad de la impresora. Monitor monitor_buffer_circular variables buffer_circular /* arreglo de 0 a casilla-1 */ casilla_ene_uso /* de 0 a casilla */ siguiente_casilla_por_llenar /* de 0 a casilla-1 */ siguiente_casilla_por_vaciar /* de 0 a casilla-1 */ buffer_circular_tiene_datos : condition; buffer_circular_tiene_espacios : condition; { casilla_en_uso = 0; siguiente_casilla_por_llenar = 0; siguiente_casilla_por_vaciar = 0; } llenar_una_casilla { if casilla_en_uso == casillas esperar (buffer_circular_tiene_espacio) 49 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos buffer_circular [siguiente_casilla_por_llenar] = datos_casilla; casillas_en_uso ++; siguiente_casilla_por_llenar = (siguiente_casilla_por_llenar +1 ) mod casillas; señalar (buffer_circular_tiene_datos); } vaciar_una_casilla { if casilla_en_uso == 0 esperar (buffer_circular_tiene_datos); datos_casilla = buffer_circular [siguiente_casilla_por_vaciar]; casillas_en_uso--; siguiente_casilla_por_vaciar = (siguiente_casilla_por_vaciar +1 ) mod casillas; señalar (buffer_circular_tiene_espacio); } Ejemplo de monitor: lectores y escritores • • Los lectores no alteran el contenido de la base de datos, muchos de ellos pueden obtener acceso a la base de datos al mismo tiempo. Un escritor puede modificar los datos, por lo cual debe tener acceso exclusivo. Monitor lectores_y_escritores int lectores; bolean alguien_escribe; condition lectura_permitida, escritura_permitida; { lectores = 0; alguien_escribe = false; } comenzar_escribir { if lectores > 0 || alguien_escribe esperar (escritura_permitida); alguien_escribe = true; } escritura_terminada { alguien_escribe = false; if en_cola (lectura_permitida) señalar (lectura_permitida); else señalar (escritura_permitida); } comenzar_lectura { if alguien_escribe || en_cola (escritura_permitida) 50 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos esperar (lectura_permitida); lectores++; señalar (lectura_permitida); } lectura_terminada { lectores--; if lectores ==0 señalar (escritura_permitida); } • Es posible que un sistema que utilice monitores permita a los procedimientos de un monitor llamar a procedimientos que estén en otro, con lo que se originan llamadas anidadas en los monitores. 3.9. Buzones y Puertos Las comunicaciones a base de mensajes se pueden establecer directamente entre un transmisor y un receptor, o pueden utilizarse colas intermedias. Cuando se utiliza la cola intermedia el transmisor y el receptor especifican cual será la cola (en lugar del proceso) con que se van a comunicar. Un buzón es una cola de mensajes que puede ser utilizada por múltiples transmisores y receptores. En un sistema distribuidor, los receptores pueden estar situados en muchas computadoras, por lo cual requieren dos transmisiones para la mayor parte de los mensajes: una del transmisor al buzón y otra del buzón al receptor. El problema se resuelve dando a cada receptor un puerto. Un puerto se define como un buzón utilizado por múltiples transmisores y un solo receptor. _________________________________________________________________________ EJERCICIO PROPUESTO _________________________________________________________________________ 1. Investigue en los números de puertos en alguna distribución de GNU/Linux. a) ¿ Para qué se utilizan los puertos estáticos? b) ¿ Por qué se generan los puertos dinámicos? 2. ¿Cómo cerramos los puertos? 3. ¿ Es lo mismo un puerto y un servicio? _________________________________________________________________________ 51 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 4 Mecanismos de IPC Los procesos necesitan en ocasiones comunicarse entre ellos, ya sean que sean parientes o entidades sin parentesco. Para esto el sistema brinda formas básicas de comunicación, como son las tuberías, con nombre o sin nombres, y además mecanismos implementados como unidades que necesitan una llave para poder proteger el acceso a los recursos que los procesos necesiten compartir. 4.1. Comunicación mediante tuberías La comunicación entre procesos es fundamental para que estos intercambien datos y se puedan sincronizar. Hay que tener en consideración en primer lugar si los procesos está comunicándose en la misma máquina, y estos estas emparentados o no, y segundo si estos están comunicándose en máquinas diferentes. A continuación se muestra los mecanismos clásicos de comunicación entre dos o más procesos como son las tuberías, basándonos en las facilidades IPC de los sistemas UNIX System V y derivados Tuberías sin nombre - PIPE Los pipes son viejas formas de IPC en UNIX y son proporcionados por todos los sistemas UNIX. Estos tiene dos limitaciones: 1. Los datos fluyen un una dirección. 2. Pueden usarse solo entre procesos que tienen un ancestro en común. Normalmente un pipe es creado por un proceso que llama a un fork, y el pipe es usado entre el padre y el hijo. Un pipe se crea llamando a la función pipe. 52 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROTOTIPO DE LA FUNCIÓN #include int pipe (int filedes[2]) El valor retornado es 0 se todo esta bien y –1 si existe un error. Los dos descriptores son retornado a través del argumento filedes: Pipe filedes[0] es abierto para lectura filedes[1] es abierto para escritura La salida de filedes[1] es la entrada para filedes[0] Proceso de usuario Un pipe se crea llamando a la función pipe. fd[0] fd[1] ude pe (int filedes[2]); Proceso de usuario or retornado es 0 se todo esta bien y -1 si existe un error. fd[0] fd[1] os descriptores son retornado a través del argumento filedes: pipe s[0] es abierto para lectura s [1] es abierto para escritura kernel lida de filedes[1] es la entrada para filedes[0] Figura 4-1. Dos forma de ver a un pipe de UNIX. Padre fd[0] fork fd[1] Hijo fd[0] fd[1] pipe Kernel Figura 4-2. Un pipe half-duplex después de un fork. 53 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Padre Hijo fd[1] fd[0] pipe Kernel Figura 4-3. Pipe entre un padre y un hijo. Ejemplo. Programa que muestra el código para crear un pipe desde el padre al hijo, y envía datos hacia abajo del pipe. #include #include #include #include main () { int n, fd[2]; pid_t hijo; char linea [MAXLINEA] if (pipe(fd) < 0) fprintf (stderr,”error de pipe”); if ( (hijo = fork() ) < 0) fprintf (stderr, “error de fork”); else if (hijo> 0) { /* padre */ close (fd[0]); write (fd[1], “hola mundo\n”,12); } else { close (fd[1]); n = read (fd[0], linea, MAXLINEA); write (STDOUT_FILENO, linea, n); } exit (0); } Algunas veces el padre se ejecuta más rápido que el hijo, lo que podemos hacer entre muchas cosas es cambiar el orden. 54 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos #include #include #include #include #define MAXLINE 80 main () { int n, fd[2]; pid_t hijo; char linea[MAXLINE]; int estado; if (pipe(fd) < 0) fprintf (stderr,"error de tuberia"); if ( (hijo=fork()) == 0) { close (fd[0]); write (fd[1], "hola mundo \n",12); } else { /* if (wait (&estado)==hijo) {*/ close (fd[1]); n = read (fd[0], linea, MAXLINE); write (STDOUT_FILENO, linea, n); printf("numero de lineas %d \n",n); /* }*/ close (fd[1]); n = read (fd[0], linea, MAXLINE); write (STDOUT_FILENO, linea, n); printf("numero de lineas %d \n",n); /* }*/ } exit (0); } 4.2. Mecanismos IPC El paquete de comunicación entre procesos de los sistema UNIX System V y derivados como Linux se compone de tres mecanismos: 1. Los semáforos, que van a permitir sincronizar procesos; 2. La memoria compartida, que va a permitir que los procesos compartan su espacio de direcciones virtuales; y 3. Las colas de mensajes, que posibilitan el intercambio de datos con un formato determinado. Estos mecanismos están implementados como una unidad y comparten características comunes, entre las que se encuentran: 55 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • Cada mecanismo tiene una tabla cuyas entradas describen el uso que se hace del mismo. • Cada entrada de la tabla tiene una llave numérica elegida por el usuario. • Cada mecanismo dispone de una llamada “get” para crear una entrada nueva o recuperar alguna ya existente. Dentro de los parámetros de esta llamada se incluye una llave y una máscara de indicadores. El núcleo busca dentro de la tabla alguna entrada que se ajuste a la llave suministrada. • Cada entrada de la tabla tiene un registro de permisos que incluye: ID del usuario y grupo del proceso que ha reservado la entrada. • Cada entrada contiene información de estado, en la que se incluye el identificador del último proceso que ha utilizado la entrada. • Cada IPC tiene una llamada de “control” que permite leer y modificar el estado de una entrada reservada y también permite liberarla. Tabla 4-1. Resumen de los llamados IPC. Semafóros Memoria compartida Cola de mensajes Cabecera de archivo llamado para crear o abrir semget shmget msgget Llamado para operaciones de control semctl shmctl msgctl Llamado para operaciones IPC semop shmat, shmdt msgsnd, msgrcv Llaves Una llave es una variable o constante del tipo key_t que se usa para acceder a los mecanismos IPC previamente reservados o para reservar otros nuevos. Los mecanismos que están siendo utilizados como parte de un mismo proyecto comparten la misma llave. En GNU C se crean las llaves utilizando la función ftok. PROTOTIPO DE LA FUNCIÓN #include #include key_t ftok (char *path, int id); 56 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 4.2.1 SEMÁFOROS El concepto de semáforo nace de la necesidad que en el sistema se pueda contar con procesos que trabajen de manera cooperativa, y para esto deben de coordinarse. No es un mecanismo de comunicación sino de sincronización y son utilizados para controlar el acceso a los recursos. Dijkstra (colocar referencia) define un semáforo como un objeto de tipo entero sobre el que se puede realizar dos operaciones atómicas, es decir, sin interrupción, llamadas: P y V. Espera (P): Se usa cuando un proceso quiere acceder a un recurso compartido y puede ocurrir: o Si la variable entera es positiva, adquiere el recurso y decrementa el valor. o En caso de que el valor sea nulo el proceso se duerme y espera a ser despertado. Liberar (V): Se utiliza para indicar que el recurso compartido esta libre y despierta a los procesos que estén esperando por el recurso. Los semáforos resuelven principalmente los problemas de: Exclusión mutua, y Sincronización. Crear o Acceder a un semáforo Mediante semget se puede crear o accesar a un conjunto de semáforos unidos bajo un identificador común. PROTOTIPO DE LA FUNCIÓN #include #include #include int semget (key_t key, int numsems, int semflg); Si se ejecuta correctamente retorna el ID para accesar a los semáforos, y en caso de error -1 y en errno el código del error producido. En este caso, la variable errno toma uno de los valores siguientes: • EACCES: Existe un grupo de semáforos para la clave, pero el proceso no tiene todos los derechos necesarios para acceder al grupo. 57 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • EEXIST: Existe un grupo de semáforos para la clave, pero están activadas las operaciones IPC_CREAT e IPC_EXCL. • EIDRM: El grupo de semáforos ha sido borrado. • ENOENT: El grupo de semáforos no existe y no está activada la opción IPC_CREAT. • ENOMEN: El semáforo podría crearse pero el sistema no tiene más memoria para almacenar la estructura. • ENOSPC: El semáforo podría crearse pero se sobrepasarían los límites para el número máximo de grupos (SEMMNI) de semáforos o el número de semáforos (SEMMNS). key indica a qué grupo de semáforos se va a accesar. El núcleo busca dentro de la tabla alguna entrada que se ajuste a la llave suministrada. Si la llave suministrada toma el valor IPC_PRIVATE, el núcleo ocupa la primera entrada que se encuentra libre y ninguna otra llamada “semget” podrá devolver esta entrada hasta que la liberemos. Si dentro de la máscara de indicadores está activo el bit IPC_CREAT, el núcleo crea una nueva entrada en caso de que no haya ninguna que responda a la llave suministrada. Si la llave suministrada tiene activados IPC_CREAT e IPC_EXL devolverá error si ya existe la clave suministrada. Retorna un descriptor de semáforo. Si no existe el descriptor y se especifica IPC_CREAT creará uno. numsems es el total de semáforos que van a estar agrupados bajo el identificador devuelto. semflg es una máscara de bits para indicar el modo de adquisición del identificador. Esta formado por dos campos separados por un el simbolo (|). Los campos son: CAMPO I: IPC_CREAT, IPC_EXCL CAMPO II: 00X00 usuario, 000X0 grupo, 0000x otro if ( (llave=ftok (“auxiliar”, `k`)) == (ket_t) -1) { if ( (semid = semget ( llave, 4, IPC_CREATE| 0600))== -1) { ....... ....... } } 58 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Semop (operaciones sobre los semáforos) Para realizar las operaciones sobre los semáforos que hay asociados bajo un identificador (incremento, decremento o espera de nulidad). PROTOTIPO DE LA FUNCIÓN #include #include #include int semop (int semid, struct sembuf *sops, unsigned nsops); • semid: Identificador del semáforo (grupo sobre el cual las operaciones tendrán lugar). • sops: Puntero a un vector de operaciones (arreglo de estructuras que indica las operaciones a llevar a cabo sobre los semáforos). • nsops: Número de operaciones a realizar en esta llamada (en realidad, tamaño de elementos que tiene el arreglo de operaciones). Estructura sembuf La estructura involucrada en el llamado a semop es sembuf. Cada dato de este tipo especifica una operación a realizar sobre un semáforo particular dentro del conjunto. Este semáforo en particular es el especificado en sem_num. Este semáforo se puede Incrementar, decrementar o esperar un valor nulo. struct sembuf { ushort short short } sem_num; sem_op; /* operación */ sem_flg; Si sem_op es negativo, el valor del semáforo se decrementará sem_op, si no es es posible entonces bloquea el proceso. Si el valor alcanzado es cero entonces despierta a los procesos correspondientes. Si sem_op es positivo, el valor del semáforo se incrementará sem_op, y tiene como efecto el despertar de todos los procesos que esperan a que este valor aumente a dicho valor. Si sem_op es 0, no hay alteración sobre el semáforo. Si es Nulo se bloquea el proceso. 59 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Todas las operaciones deben efectuarse de manera atómica. En los casos en que esto no sea posible, o bien el proceso se suspende hasta que sea posible, o bien, si el identificador IPC_NOWAIT está activado (campo sem_flg de la estructura sembuf) por una de las operaciones, la llamada al sistema se interrumpe sin que se realice ninguna operación. Por cada operación efectuada, el sistema controla si el indicador SEM_UNDO está posicionado. Si es así, crea una estructura para conservar el rastro de esa operación y poder anularla y finalizar la ejecución del proceso. Si la llamada al sistema se desarrolla correctamente el valor devuelto es 0, si el proceso debe bloquearse devuelve 1, si no es –1 y errno toma uno de los valores siguientes: • E2BIG: El argumento nsops es mayor que SEMOPM, y se sobrepasa el número máximo de operaciones autorizadas para una llamada. • EACCES: El proceso que llama no tiene los derechos de acceso a uno de los semáforos especificados en una de las operaciones. • EAGAIN: El indicador IPC_NOWAIT está activado y las operaciones no han podido realizarse inmediatamente. • EFAULT: La dirección especificada por el campo sops no es válida. • EFBIG: El número del semáforo (campo sem_num) es incorrecto para una de las operaciones (negativo o superior al número de semáforos en el grupo). • EIDRM: El semáforo no existe. • EINTR: El proceso ha recibido una señal cuando esperaba el acceso a un semáforo. • EINVAL: O el grupo del semáforo solicitado no existe(argumento semid), o bien el número de operaciones a realizar es negativo o nulo(argumento nsops). • ENOMEN: El indicador SEM_UNDO está activado y el sistema no puede asignar memoria para almacenar la estructura de anulación. • ERANGE: El valor añadido al contador del semáforo sobrepasa el valor máximo autorizado para el contador SEMVMX. Semctl ( Información administrativa y de control de los semáforos) Esta función permite la consulta, modificación y eliminación de un grupo de semáforos. También permite inicializar los semáforos y obtener información sobre el número de semáforos. 60 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROTOTIPO DE LA FUNCIÓN #include #include #include int semctl (int semid, int semnum, int cmd, union semun arg); semid: Identificador de semáforo válido. Semnum: Representa el número de semáforos. cmd: Indica la operación a realizar. Según los valores de cmd se realizarán diferentes casos: • IPC_STAT. Permite obtener las informaciones respecto a un grupo de semáforo. Semmun se ignora, arg es un puntero a la zona que contiene las informaciones. El proceso debe tener derechos de lectura para realizar la operación. • IPC_SET. Permite modificar ciertos valores de la estructura del grupo de semáforos. Los campos modificables son sem_perm.uid, sem_perm.gid y sem_perm.mode. El campo sem_ctime se actualiza automáticamente. El proceso debe ser el creador o bien el propietario del grupo, o bien el superusuario. • IPC_RMID. Le indica al núcleo que debe borrar el conjunto de semáforos agrupados bajo el identificador semid. La operación de borrado no tendrá efecto mientras haya algún proceso que esté usando los semáforos. • GETPID: Permite devolver el PID del último proceso que actuó sobre el semáforo. El proceso debe tener derechos de acceso en lectura sobre el grupo. • GETNCNT. Permite leer el número de procesos que esperan que el contador del semáforo se incremente. El proceso debe tener el derecho de acceso en lectura sobre el grupo. • GETZCNT. Permite leer el número de procesos que esperan a que el semáforo tome el valor de 0. Este número es calculado por la función count_semzcnt(). • GETVAL. Se utiliza para leer el valor de un semáforo. El valor se retorna a través de la función. • GETALL. Permite leer el valor de todos los semáforos asociados al identificador semid. Estos valores se almacenan en arg. 61 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • SETVAL. Permite inicializar un semáforo a un valor determinado que se especifica en arg. • SETALL. Inicializa el valor de todos los semáforos asociados al identificador semid. Los valores de inicialización deben estar en arg. Para arg se utiliza la estructura semun, la cual es una unión, se utilizada para almacenar o recuperar informaciones sobre los semáforos. union semun { int val; /* Valor para SETVAL */ struct semid_ds *buf; /* Memoria de datos para IPC_STAT e IPC_SET */ ushort *array; /* Tabla para GETALL y SETALL */ struct seminfo *_buf; /* Memoria de datos para IPC_INFO*/ } arg; La Estructura semid_ds, se trata de una estructura de control asociada a cada uno de los distintos conjuntos de semáforos existentes en el sistema. Contiene información del sistema, punteros a las operaciones a realizar sobre el grupo, y un puntero hacia las estructuras sem que se almacenan en el núcleo y contienen información de cada semáforo. Esta estructura está en desuso actualmente y ha sido sustituida por sem_array solo se utiliza para compatibilidades. La Estructura seminfo permite conocer los valores límite o actuales del sistema mediante una llamada a semctl. Estas llamadas no se realizan generalmente en modo directo, sino que están reservadas a las utilidades del sistema como el mandato ipcs. Si la llamada a semctl se realiza con éxito, la función devuelve un número cuyo significado dependerá del valor de cmd. Si el llamado falla devuelve -1 y errno tendrá el código de error: • EACCES: El proceso que llama no tiene derechos de acceso necesarios para realizar la operación. • EFAULT: La dirección especificada por arg.buf o arg.array no es válida. • EIDRM: El grupo de semáforos ha sido borrado. • EINVAL:El valor de semid o de cmd es incorrecto. • EPERM: El proceso no tiene los derechos necesarios para la operación (mandato IPC_SET o IPC_RMID). • ERANGE: cmd tiene el valor SETALL o SETVAL y el valor del contador de uno de los semáforos a modificar es inferior o superior a SEMVMX. EJEMPLO. Sincronización de procesos 62 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos /**** Programa para mostrar el uso de semáforos en la sincronización de procesos, tomado de la página 389 del libro de: UNIX Programación Avanzada. F.M. Márquez *******/ #include #include #include #include #define SEM_HIJO 0 #define SEM_PADRE 1 main (int argc, char *argv[]) { int i=0, semid, pid; struct sembuf operacion; key_t llave; llave= ftok (argv[0], `k`); if ( (semid = semget (llave,2,IPC_CREAT| 0600))==-1) { perror (“semget”); exit (-1); } semctl (semid, SEM_HIJO, SETVAL, 0); semctl (semid, SEM_PADRE, SETVAL, 1); if ( (pid = fork())==-1) { perror (“fork”); exit (-1); } else if (pid==0) { while (1) { /* Cerramos el semáforo del proceso hijo */ operacion.sem_num = SEM_HIJO; operacion.sem_op = -1; operacion.sem_flg = 0; semop (semid, &operacion, 1); 63 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos printf (“Proceso hijo:%d\n”, i--); /* Abrimos el semáforo del proceso padre */ operacion.sem_num = SEM_PADRE; operacion.sem_op = 1; semop (semid, &operacion, 1); } /* Borramos el semáforo*/ semctl (semid, 0, IPC_RMID,0); } else { while (1) { /* Cerramos el semáforo del proceso padre */ operacion.sem_num = SEM_PADRE; operacion.sem_op = -1; operacion.sem_flg = 0; semop (semid, &operacion, 1); printf (“Proceso padre:%d\n”, i--); /* Abrimos el semáforo del proceso hijo */ operacion.sem_num = SEM_HIJO; operacion.sem_op = 1; semop (semid, &operacion, 1); } /* Borramos el semáforo*/ semctl (semid, 0, IPC_RMID,0); } } 4.2.2 MEMORIA COMPARTIDA La forma más rápida para comunicar dos procesos es hacer que compartan una zona de memoria. shmget Crea una zona de memoria compartida o habilita el acceso a una ya creada. 64 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROTOTIPO DE LA FUNCIÓN #include #include #include int shmget ( key_t key, int size, int shmflg); Donde key. Es una llave para crear el mecanismo IPC. size. Es el tamaño en bytes de la zona de memoria a crear. shmflg. Es una máscara de bits. La llamada a shmget devuelve un ID asociado a la zona de memoria (entero), en otro caso retorna -1, y en errno el código del error. if ( ( shmid = shmget (IPC_PRIVATE, 4096, IPC_CREAT | 0600)) == -1) { ......... TRATAMIENTO DEL ERROR ........ } shmctl Esta función realiza operaciones de control sobre una zona de memoria previamente creada. PROTOTIPO DE LA FUNCIÓN #include #include #include int shmctl (int shmid, int cmd, struct shmid_ds *buf); Donde: shmid. Es el identificador válido devuelto por shmget. 65 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos cmd. Es el tipo de operación de control a reazliar, sus posibles valores son: IPC_STAT. Lee el estado de la estructura de control de la memoria y lo devuelve a través de la zona de memoria apuntada por buf. IPC_SET. Inicializa algunos de los campos de la estructura de control de la memoria compartida. Los valores los toma de buf. IPC_RMID. Borra del sistema la zona de memoria compartida identificada por shmid. Está debe estar liberada por todos los procesos. SHM_LOCK. Bloquea en memoria el segmento identificado por shmid. SHM_UNLOCK. Desbloquea el segmento de memoria compartido. La estructura shmid_ds se define struct shmid_ds { struct ipc_per shm_per; /* permisos */ int shm_segsz; /* tamaño del área de memoria compartida */ ushort shm_lpid; /* PID del último proceso que hizo la última operación con este segmento de memoria */ ushort shm_cpid; /* PID del proceso creador del segmento */ ushort shm_nattach; /* número de procesos unidos al seg. de memoria*/ time_t shm_atime; /* Fecha de la última unión al seg. de memoria */ time_t shm_dtime; /* Fecha de la última separación del seg. de memoria*/ time_t shm_ctime; /* Fecha del último cambio en el seg. de memoria*/ } La estructura ipc_perm (permisos) es la siguiente struct ipc_perm { ushort uid; ushort gid; ushort cuid; ushort cgid; ushort mode; ushort seg; keyt_t key; } /* ID del usuario propietario */ /* ID del grupo */ /* ID del usuario creador */ /* ID del grupo creador */ /* Modos de acceso */ /* Número de secuencia */ /* Llave */ Para borrar del sistema la zona de memoria compartida debemos escribir shmctl (shmid, IPC_RMID, 0); 66 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Operaciones shmat y shmdt Para unirse/atarse a un espacio de direcciones virtuales (segmento de memoria compartida) del proceso se utiliza shmat y para desatarse shmdt. PROTOTIPO DE LA FUNCIÓN #include #include #include char *shmat (int shmid, char *shmaddr, int shmflg); int shmdt (char *shmaddr); El llamado shmat retorna la dirección inicial del segmento de memoria compartida. Las reglas para determinar estas direcciones son: • Si el argumento shmaddr es cero, el sistema selecciona la dirección para el llamado. • Si el argumento shmaddr no es cero, retorna la dirección dependiendo del valor de SHM_RND para el argumento shmflg: • Si el valor SHM_RND no es especificado, el segmento de memoria compartida es unida a la dirección especificada como argumento en shmaddr. • Si el valor de SHM_RND es especificado, el segmento de memoria compartida es unida a la dirección especificada como argumento en shmaddr, redondeando hacia abajo por la constante SHMLBA (lower boundary address) Referencia [1] F. M. Márquez, UNIX Programación Avanzada, AlfaOmega , Segunda Edición, 2001. 67 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 5 Interbloqueo e Inanición Un proceso es una entidad en ejecución que tiene asociada un identificador para poder ser identificado. En el sistema se cuenta con procesos pesados, llamados hijos, y procesos ligeros, llamados hilos. Interbloqueo: [MAEKAMA] Se define como el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros. Tabla 5-1. Resumen de los enfoques de detección, prevención y predicción del interbloqueo en los Sistemas Operativos 68 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Principio Política de reparto Esquemas de recursos Prevención Conservadora; los Solicitud de recursos están todos los poco ocupados recursos a la vez. Ventajas Desventajas • Funciona bien con procesos que realizan una sola ráfaga de actividad. • No es necesaria la apropiación. • Conveniente cuando se aplica a recursos cuyo Apropiación estado se puede salvar y restaurar fácilmente. • Aplicación factible Ordenación de por medio de recursos chequeos durante la compilación. • No hace falta procesamiento durante la ejecución, pues el problema se resuelve durante el diseño del sistema. Detección Muy liberal; los Comprobación • Nunca retrasa el recursos periódica del inicio de un solicitados se interbloqueo. proceso. • Facilita el manejo conceden cuando es posible. en línea. • Predicción A medio del Manipulación No es necesaria camino entre la para encontrar la apropiación. detección y la al menos un pevención. camino seguro. • Ineficiencia. • Retrasos en el inicio de los procesos. • Apropia más habitualmente de lo necesario. • Sujeto a reinicios cíclicos. • No permite las solicitudes incrementales de recursos. • Poco uso de la apropiación. • Pérdidas inherentes a la apropiación. • Deben conocerse las demandas futuras de recursos. • Los procesos pueden bloquearse durante largos periodos. Inanición, aplazamiento indefinido, bloqueo indefinido. Cuando un proceso, aún cuando no esté bloqueado, esta esperando un evento que quizá nunca ocurra debido a ciertas tendencias en las políticas de asignación de recursos del sistema. En cualquier sistema que mantenga los procesos en espera mientras se les asigna un recurso o se toman decisiones de planificación, la programación de un proceso puede postergarse indefinidamente mientras otro recibe la atención del sistema. 69 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Recurso A Solicitud P1 Retenido por P2 Retenido por Recurso B Solicitud Figura 5-1. Espera circular. Cuatro condiciones necesarias para que se produzca un bloqueo mutuo (interbloqueo) 1. Exclusión mutua. Sólo un proceso puede usar un recurso simultáneamente. 2. Retención y espera. Un proceso puede retener unos recursos asignados mientras espera que se le asignen otros. 3. No apropiación. Ningún proceso puede ser forzado a abandonar un recurso que retenga. 4. Espera circular. Existe una cadena cerrada de procesos, cada uno de los cuales retiene, al menos, un recurso que necesita el siguiente proceso de la cadena. (Figura 5-1) Las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo. Prevención del bloqueo mutuo Definitivamente la técnica empleada con más frecuencia por los diseñadores para tratar el problema del bloqueo mutuo es la prevención. Havender, J. W. llegó a la conclusión de que si falta una de las cuatro condiciones necesarias no puede haber bloqueo mutuo, él sugiere las siguientes estrategias para negar varias de estas condiciones: • Cada proceso deberá pedir todos sus recursos al mismo tiempo y no podrá seguir la ejecución hasta haberlos recibido todos. 70 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • Si a un proceso que tiene ciertos recursos se le niegan los demás, ese proceso deberá liberar sus recursos y, en caso necesario, pedirlos de nuevo junto con los recursos adicionales. • Se impondrá un ordenamiento lineal de los tipos de recursos en todos los procesos; es decir, si a un proceso le han sido asignados recursos de un tipo específico, en lo sucesivo sólo podrá pedir aquellos recursos que siguen en el ordenamiento (Figura 5-2). .. . R8 P1 P2 R7 P1 R6 R5 P1 El proceso P1 tiene los recursos R3, R4, R6 y R7, y pide el recurso R8 (línea punteada). No puede haber espera circular porque todas las flechas deben apuntar hacia arriba. R4 P2 P1 R3 R2 R1 Figura 5.2. Ordenamiento lineal. 71 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 5.2 Algoritmo del banquero El algoritmo más famoso para evitar un bloqueo mutuo es el algoritmo del banquero de Dijkstra, cuyo interesante nombre se debe a que atañe de un banquero que otorga préstamos y recibe pagos a partir de una determinada fuente de capital. Ejemplo de estado seguro. Supóngase que un sistema tiene doce unidades de cinta y tres usuarios que las comparten, como en el Estado I. Estado I Préstamo actual Usuario (1) Usuario (2) Usuario (3) Necesidad máxima 1 4 5 Disponibles 4 6 8 2 Este es un estado “seguro” porque aún es posible que terminen los tres usuarios. De esta forma, la clave para que un estado sea seguro es que exista al menos una forma de que terminen todos los usuarios. Ejemplo de estado inseguro. Supóngase que las doce unidades de cinta de un sistema están asignadas como en el Estado II. Estado II Usuario (1) Usuario (2) Usuario (3) Disponibles Préstamo actual Necesidad máxima 8 2 1 10 5 3 1 Aquí, once de las doce unidades de cinta del sistema se encuentran en uso y solamente una está disponible para asignación. En este momento, sin importar cuál de los usuarios pida la unidad disponible, no se puede garantizar que terminen los tres usuarios. Es importante señalar que un estado inseguro no implica la existencia, ni siquiera eventual, de un bloqueo mutuo. Lo que sí implica un estado inseguro es simplemente que alguna secuencia desafortunada de eventos podría llevar al bloqueo mutuo. Ejemplo de transición de estado seguro a estado inseguro Saber que un estado es seguro no implica que serán seguros todos los estados futuros. La política de asignación de recursos debe considerar cuidadosamente todas las 72 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos peticiones antes de satisfacerlas. Por ejemplo, supóngase que el estado actual de un sistema como se muestra en el Estado III. Estado III Usuario (1) Usuario (2) Usuario (3) Préstamo actual Necesidad máxima 1 4 5 Disponibles 4 6 8 2 Ahora supóngase que el Usuario (3) pide un recurso más. Si el sistema satisface esta petición, el nuevo estado será el Estado IV. Estado IV Usuario (1) Usuario (2) Usuario (3) Préstamo actual Necesidad máxima 1 4 6 Disponibles 4 6 8 1 Ciertamente, el Estado IV no está necesariamente bloqueado, pero ha pasado de un estado seguro a uno inseguro. El estado IV caracteriza a un sistema en el cual no puede garantizarse la terminación de todos los procesos. Solamente hay un recurso disponible, pero deben estar disponibles al menos dos recursos para asegurar que Usuario(2) o Usuario(3) puedan terminar, devolver sus recursos al sistema y permitir que los otros usuarios terminen. Nota en el algoritmo del banquero se presenta los siguientes términos: • • • • • • • Están permitidas las condiciones de “espera circular”, “espera”, y “no apropiación”, pero los procesos sí exigen el uso exclusivo de los recursos que requieren. Los procesos pueden conservar recursos mientras piden y esperan recursos adicionales. Los recursos no pueden arrebatarse a los procesos que los tienen. Los usuarios facilitan el trabajo al sistema pidiendo un solo recurso a la vez. El sistema puede satisfacer o rechazar una petición. Si una petición es rechazada, el usuario conserva los recursos que ya tenga asignados y espera un tiempo finito a que se satisfaga la petición. El sistema sólo satisface peticiones que llevan a estados seguros. Defectos del algoritmos del banquero. • • El algoritmo requiere un número fijo de recursos asignables. El algoritmo requiere una población de usuarios constante. 73 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • • • El algoritmo requiere que el banquero satisfaga todas las peticiones en un tiempo finito. El algoritmo requiere que los clientes salden todos sus préstamos en un tiempo finito. El algoritmo requiere que los usuarios declaren por anticipado sus necesidades máximas. Detección del boqueo mutuo La detección del bloqueo mutuo es el proceso de determinar si realmente existe un bloqueo mutuo e identificar los procesos y recursos implicados en él. Los algoritmos de detección de bloqueos mutuos determinan por lo general si existe una espera circular. En control del interbloqueo puede llevarse a cabo tan frecuentemente como las solicitudes de recursos o con una frecuencia menor, dependiendo de la probabilidad de que se produzca el interbloqueo. La comprobación en cada solicitud de recurso tiene dos ventajas: 1. Conduce a una pronta detección, y 2. El algoritmos es relativamente simple, puesto que está basado en cambios incrementales del estado del sistema. Por otra parte, las frecuentes comprobaciones consume un tiempo de procesador considerable. Una vez detectado el interbloqueo, hace falta alguna estrategia de recuperación. 1. Abandonar todos los procesos bloqueados. Es la más común en los sistemas operativos. 2. Retroceder cada proceso interbloqueado hasta algún punto de control definido previamente y volver a ejecutar todos los procesos. El riesgo de esta solución radica en que puede repetirse el interbloqueo original. Sin embargo, el no determinismo del procesamiento concurrente asegura, en general, que esto no va a pasar. 3. Abandonar sucesivamente los procesos bloqueados hasta que deje de haber interbloqueo. El orden en el que se seleccionan los procesos a abandonar seguirá un criterio de mínimo coste. Después de abandonar cada proceso, se debe ejecutar de nuevo el algoritmo de detección para ver si todavía existe bloqueo. 4. Apropiarse de recursos sucesivamente hasta que deje de haber interbloqueo. Un proceso que pierde un recurso por apropiación debe retroceder hasta el momento anterior a la adquisición de ese recurso. Para los puntos 3 y 4, el criterio de selección del proceso podría ser uno de los siguientes: • • • • • Escoger el proceso con la menor cantidad de tiempo de procesador consumido. Escoger el proceso con el menor número de líneas de salida producidas. Escoger el proceso con el mayor tiempo restante. Escoger el proceso con el menor número total de recursos asignados. Escoger el proceso con la prioridad más baja. 74 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Predicción del interbloqueo La predicción del interbloqueo necesita conocer las peticiones futuras de los recursos. Para realizar la predicción del interbloqueo se deben tener en cuenta los siguientes dos enfoques: • • No iniciar un proceso si sus demandas pueden llevar a interbloqueo. No conceder una solicitud de incrementar los recursos de un proceso si esta asignación puede llevar a interbloqueo. 75 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 6 Administración de memoria Un proceso es una entidad en ejecución que tiene asociada un identificador para poder ser identificado. En el sistema se cuenta con procesos pesados, llamados hijos, y procesos ligeros, llamados hilos. Introducción Una de las tareas más importantes y complejas de un sistema operativo es la gestión de memoria. La administración de memoria implica tratar la memoria principal como un recurso para asignar y compartir entre varios procesos activos. Para un uso eficiente del procesador y de los servicios de E/S, resulta interesante mantener en memoria principal tantos procesos como sea posible. Además, es deseable poder liberar a los programadores de las limitaciones de tamaño en el desarrollo de los programas. Las herramientas básicas de la gestión de memoria son la paginación y la segmentación. En la paginación, cada proceso se divide en páginas de tamaño constante y relativamente pequeño. La segmentación permite el uso de partes de tamaño variable. También es posible combinar la segmentación y la paginación en un único esquema de gestión de memoria. La parte del sistema operativo que administra la memoria se llama administrador de memoria. Su labor consiste en llevar un registro de las partes de memoria que se estén utilizando y aquellas que no, con el fin de asignar espacio en memoria a los procesos cuando estos la necesiten y liberarlo cuando terminen, así como administrar el intercambio entre la memoria principal y el disco, en los casos en que la memoria principal no pueda albergar a todos los procesos. Para realizar lo anterior se pueden utilizar diferentes esquemas de administración de memoria, desde los muy sencillos hasta los más sofisticados. 76 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Administración de memoria sin intercambio o paginación. Los sistemas de administración de la memoria se pueden clasificar en dos tipos: Los que desplazan los procesos de la memoria principal al disco y viceversa durante la ejecución, y aquellos que no los desplazan. El esquema más sencillo de administración de la memoria es aquel en el que sólo se tiene un proceso en memoria en cada instante. El usuario carga toda la memoria con un programa del disco y utiliza la máquina. 0xFF... Programa del usuario Sistema Operativo en RAM Sistema Operativo en ROM Programa del usuario Controladores de dispositivos en ROM Programa del usuario Sistema Operativo en RAM Figura 6-1. Propuestas de organizar la memoria, con un sistema operativo y un proceso de usuario. Modelos de multiprogramación El uso de la CPU se puede mejorar mediante la multiprogramación. En teoría, si el proceso promedio hace cálculos sólo durante 20% del tiempo que permanece en la memoria y tiene cinco procesos al mismo tiempo en memoria, la CPU debería estar ocupada todo el tiempo. Sin embargo, esto es un optimismo irreal, puesto que supone que los cinco procesos nunca esperan la E/S al mismo tiempo. Un mejor modelo consiste en analizar el uso de la CPU desde un punto de vista probabilístico. Supongamos que un proceso ocupa una fracción p de su tiempo en el estado de espera de E/S. Si n procesos se encuentran en la memoria al mismo tiempo, la probabilidad de que los n procesos esperen por E/S (en cuyo caso la CPU estaría inactiva) sería pn. El uso de la CPU está dado entonces por la fórmula Uso de la CPU = 1 - pn Figura 6-2. Gráfica de rendimiento Análisis del rendimiento de un sistema con multiprogramación Figura 6-3. (a) Arribo y requerimientos de trabajo de cuatro tareas. (b) El uso del CPU de 1 a 4 trabajos con 80% de espera por E/S. (c) Secuencia de eventos. 77 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Multiprogramación con particiones fijas Hasta este momento nos hemos dado cuenta de la utilidad de tener más de un proceso en la memoria, pero ¿cómo debemos organizar la memoria para poder lograr esto?. La forma más sencilla es dividir la memoria en n partes (que podrían ser de tamaños distintos). En la figura 6.4 (a) vemos este sistema de particiones fijas y colas de entrada independientes. La desventaja del ordenamiento de las tareas que llegan a la memoria en colas independientes es evidente cuando la cola de una partición grande está vacía, la cola de una partición pequeña está completamente ocupada. (b). Otro tipo de ordenamiento es el que mantiene una sola cola, como en la figura 6.4 Cada vez que se libere una partición, se podría cargar y ejecutar en ella la tarea más cercana al frente de la cola que se ajuste a dicha partición. Puesto que no es deseable que se desperdicie una partición de gran tamaño con una tarea pequeña, otra estrategia consiste en buscar en toda la cola de entrada el trabajo más grande que se ajuste a la partición recién liberada. Observe que este último algoritmo discrimina a las tareas pequeñas, negándoles la importancia suficiente como para disponer de toda una partición, mientras que lo recomendable es que se les dé a las tareas pequeñas el mejor servicio y no el peor. Una forma de salir del problema es tener siempre una pequeña partición por ahí. Tal partición permitiría la ejecución de las tareas pequeñas sin tener que asignarles una partición de gran tamaño. Otro punto de vista es obedecer como regla que un trabajo elegible para su ejecución no sea excluido más de k veces. Cada vez que se le excluya, obtiene un punto. Cuando adquiera k puntos, ya no podrá ser excluido de nuevo. Varias colas de entrada Partición 4 Partición 4 8 GB Partición 3 Una cola de entrada Partición 3 5 GB Partición 2 Partición 2 3 GB Partición 1 Partición 1 2 GB Sistema Operativo Sistema Operativo 0 GB (a) (b) Figura 6-4. (a) Colas de entradas independientes, (b) Ordenamiento en una cola. 78 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Reasignación y protección La multiprogramación presenta dos problemas esenciales por resolver: la reasignación y la protección. Observe la figura 3-4. Ahí es evidente que las diversas tareas se ejecutarán en direcciones distintas. Cuando un programa se liga, el ligador debe conocer la dirección donde comienza el programa en memoria. Por ejemplo, supongamos que la primera instrucción es una llamada a un procedimiento que se encuentra en la dirección relativa 100, dentro del archivo en binario generado por el ligador. Si este programa se carga en la partición 1, esa instrucción saltará a la dirección absoluta 100, la cual está dentro del sistema operativo. Lo que se necesita es hacer una llamada a 100k + 100. Si el programa se carga en la partición 2, debe llevarse a cabo como una llamada a 200k + 100, etc. Este problema se conoce como el problema de reasignación. La reasignación durante el proceso de cargado no resuelve el problema de la protección. Una alternativa para resolver este problema es la de utilizar dos registros especiales de hardware, llamados el registro base y el registro límite. Cuando se planifica la ejecución de un proceso, el registro base se carga con la dirección del inicio de la partición, mientras que el registro límite se carga con al longitud de la partición. A cada dirección de memoria generada en forma automática se le añade el contenido del registro base antes de ser enviado a memoria. Así, si el registro base tiene un valor de 100k, una instrucción CALL 100 se interpreta como una instrucción CALL 100k + 100, sin que la propia instrucción de vea modificada. También se verifican las direcciones, con el fin de no rebasar el registro límite y se dirijan a una parte de la memoria fuera de la partición activa. Intercambio A diferencia de un sistema por lotes en un sistema de tiempo compartido por lo general existen más usuarios de los que puede mantener la memoria, por lo que es necesario mantener el exceso de los procesos en el disco. El traslado de los procesos de la memoria principal al disco y viceversa se llama intercambio. En principio, las particiones fijas se podrían utilizar para un sistema con intercambio. Cada vez que se bloqueara un proceso, se podría trasladar al disco y llevar otro proceso a la partición ocupada por el primero. En la práctica, las particiones fijas no son muy atractivas si se dispone de poca memoria, puesto que la mayor parte de ésta se desperdicia con programas menores que sus particiones. En vez de esto, se utiliza otro algoritmo de administración de la memoria conocido como particiones variables. El hecho de no estar sujeto a un número fijo de particiones que pudieran ser muy grandes o demasiados pequeñas mejora el uso de la memoria pero también hace más compleja la asignación y reasignación de la memoria, así como también complica el mantener un registro de esto. Es posible combinar todos los huecos en uno grande, si se mueven todos los procesos hacia la parte inferior, mientras sea posible. Esta técnica se conoce como compactación de la memoria. Por lo general, no se lleva a cabo, porque consume mucho tiempo de CPU. Otra forma de asignación de memoria, es dándole a cada proceso un espacio mayor para permitirle crecer cuando sea necesario. 79 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Figura 6-5. (a) Asignación de espacio a un segmento creciente de datos. (b) Asignación de espacio a una pila y un segmento de datos crecientes. En términos generales, existen tres formas utilizadas por los sistemas operativos para llevar un registro del uso de la memoria: mapas de bits, listas y sistemas amigables. Administración de la memoria con mapas de bits Con un mapa de bits, la memoria se divide en unidades de asignación, las cuales pueden ser tan pequeñas como unas cuantas palabras o tan grandes como varios kilobytes. A cada unidad de asignación le corresponde un bit en el mapa de bits, el cual toma el valor de 0 si la unidad está libre y 1 si está ocupada (o viceversa). Figura 6-6. Mapa de bits El tamaño de la unidad de asignación es un aspecto importante del diseño. Mientras más pequeña sea esta unidad, más grande será el mapa de bits. Una memoria de 32n bits utilizará n bits del mapa, de forma que dicho mapa sólo ocupa 1/33 de la memoria. Si la unidad de asignación es grande el mapa de bits será pequeño, pero se podría desperdiciar una parte valiosa de la memoria en la última unidad si el tamaño del proceso no es un múltiplo exacto de la unidad de asignación. Un mapa de bits es una forma sencilla para llevar un registro de las palabras de la memoria en una cantidad fija de memoria, puesto que el tamaño del mapa sólo depende del tamaño de la memoria y del tamaño de la unidad de asignación. El problema principal de esto es que, cuando se decide traer a la memoria un proceso de k unidades, el administrador de la memoria debe buscar en el mapa una cadena de k ceros consecutivos. La búsqueda en un mapa de bits de ciertas cadenas es una operación lenta, por lo que los mapas no se utilizan con frecuencia. Administración de la memoria con listas ligadas Cada entrada de la lista especifica un hueco (H) o un proceso (P), la dirección donde comienza, su longitud y un apuntador a la siguiente entrada. La lista de segmentos está ordenada por direcciones. Este orden tiene la ventaja de que al terminar o intercambiar un proceso, la actualización de la lista es directa. Cuando los procesos y los huecos se mantienen en una lista ordenada por direcciones, se pueden utilizar diversos algoritmos para asignar la memoria para un proceso de reciente creación o intercambio Algoritmo primero en ajustarse. El administrador de la memoria revisa toda la lista de segmentos hasta encontrar un espacio lo suficientemente grande. El espacio se divide entonces en dos partes, una para el proceso y otra para la memoria no utilizada, excepto por el caso poco probable de un ajuste exacto. Este algoritmo es rápido, puesto que busca lo menos posible. 80 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Cabe hacer nota que este método es el que utiliza UNIX para la asignación de memoria. Algoritmo el siguiente en ajustarse. Funciona de la misma forma que el anterior, con la diferencia de que mantiene un registro del lugar donde encuentra un hueco adecuado. La siguiente vez que se le llama, comienza a buscar desde el punto donde se detuvo, en vez de comenzar siempre desde el principio, como el caso del algoritmo anterior. Algoritmo del mejor ajuste. El cual busca en toda la lista y toma el mínimo hueco adecuado. En vez de asignar un hueco grande que podría necesitarse más adelante, el mejor en ajustarse intenta encontrar un hueco más cercano al tamaño real necesario. Algoritmo del peor ajuste. Este método toma siempre el hueco más grande disponible, de forma que el hueco obtenido sea suficientemente grande para ser útil. Este algoritmo da la vuelta de encontrar un ajuste casi exacto en un proceso y un hueco demasiado pequeño. Estos cuatro algoritmos pueden agilizarse si se tienen dos listas independientes, una para los procesos y otra para los huecos. De esta forma, todos ellos pueden dedicarse a inspeccionar los huecos, no los procesos. El precio que se paga por ese aumento de velocidad al momento de asignar la memoria es la complejidad adicional y disminución de la velocidad al liberar la memoria, puesto que un segmento liberado debe ser eliminado de la lista de procesos e insertarse en la lista de huecos. Memoria virtual La idea fundamental detrás de la memoria virtual es que el tamaño combinado del programa, los datos y la pila puede exceder la cantidad de memoria física disponible para él. El S.O. mantiene aquellas partes del programa que se utilicen en cada momento en la memoria principal y el resto permanece en el disco. La mayoría de los sistemas con memoria virtual utilizan una técnica llamada paginación. En las computadoras que no tienen memoria virtual, la dirección virtual se coloca en forma directa dentro del bus de la memoria, lo cual hace que se pueda leer o escribir en la palabra de la memoria física que tenga la misma dirección. Al utilizar la memoria virtual, las direcciones virtuales (direcciones generadas por los programas) no pasan de forma directa al bus de la memoria, sino que van a una unidad de administración de la memoria (MMU), un chip o conjunto de chips que asocian las direcciones virtuales con las direcciones de la memoria física. Figura 6-7. Memoria Virtual. Los huecos de direcciones virtuales se dividen en unidades llamadas páginas. Las unidades correspondientes en la memoria física se llaman marcos para página. Las páginas y los marcos tienen siempre el mismo tamaño. Las transferencias entre la memoria y el disco son siempre por unidades de página. Figura 6-8. Marco de página. 81 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Por ejemplo, cuando el programa intenta tener acceso a la dirección 0, mediante la instrucción: MOV REG, 0 La dirección virtual 0 se envía a la MMU. La MMU ve que esta dirección virtual cae dentro de la página 0 (o a 4095), la cual, de acuerdo con su regla de correspondencia, está en el marco 2 (8192, 12287). Transforma entonces la dirección en 8192 y sólo ve una solicitud de lectura o escritura de la dirección 8192, a la que da paso. Así, la MMU ha asociado todas las direcciones virtuales entre 0 y 4095 con las direcciones físicas 8192 a 12287. En forma análoga, la instrucción MOV REG, 8192 se transforma en MOV REG, 24576 Puesto que la dirección virtual 8192 está en la página virtual 2 y esta página está asociada con el marco físico 6 (direcciones físicas 24576 a 28671). Tabla 6-1. Ejemplos de tamaños de página. Computadora Atlas Tamaño de página 512 Honeywell-Multics 1024 Familia IBM 370 2048 ó 4096 Palabra de 48 bits Palabra de 36 bits 8 bits IBM 370/XA y 370/ESA 4096 8 bits Familia VAX 512 8 bits IBM AS/400 512 8 bits Intel 486 (IBM PC) 4096 8 bits 6 8 0 4 0 4096 8 bits Motorola (Macintosh) Unidad Figura 6-9. Traducción de direcciones en un sistema de paginación. 82 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 7 Arquitectura del sistema de archivos Un proceso es una entidad en ejecución que tiene asociada un identificador para poder ser identificado. En el sistema se cuenta con procesos pesados, llamados hijos, y procesos ligeros, llamados hilos. Las características que posee el sistema de archivos de UNIX son las siguientes: • • • • • • Posee una estructura jerárquica. Realiza un tratamiento consistente de los datos de los archivos. Puede crear y borrar archivos Permite el crecimiento dinámico de los archivos Protege los datos de los archivos. Trata los dispositivos y periféricos (terminales, unidades de cinta, etc.) como si fuesen archivos El kernel del sistema trabaja con el sistema de archivos a un nivel lógico y no trata directamente con los discos a nivel físico. Cada dispositivo es considerado como un dispositivo lógico que tiene asociados unos números de dispositivo (minor number y major number). Estos números se utilizan para indexar dentro de una tabla de funciones, los cuales tenemos que emplear para manejar el driver del disco. El driver del disco se va a encargar de transformar las direcciones lógicas del sistema de archivos a direcciones físicas del disco. Estructura del sistema de archivos Bloque de boot superbloque lista de inodes bloque de datos 1. Bloque de boot. Se localiza típicamente en el primer sector, y puede contener el código de boot o de arranque. Este código es un pequeño programa que se encarga de buscar el sistema operativo y cargarlo en memoria para inicializarlo. 83 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 2. Superbloque. Describe el estado del sistema de archivos. Contiene información acerca de su tamaño, total de archivos que puede contener, qué espacio queda libre, etc. 3. Lista de nodos índice (inodes). Esta lista tienen una entrada por cada archivo, donde se guarda una descripción del mismo; situación del archivo en el disco, propietario, permisos de acceso, fecha de actualización, etc. 4. Bloque de datos. Ocupa el resto del sistema de archivos. En esta zona es donde se encuentra situado el contenido de los archivos a los que hace referencia la lista de inodes. El superbloque El superbloque contiene, entre otras cosas, la siguiente información: • • • • • • • • • Tamaño del sistema de archivos. Lista de bloques libres disponibles. Índice del siguiente bloque libre en la lista de bloques libres. Tamaño de la lista de inodes. Total de inodes libres. Lista de inodes libres. Índice del siguiente inode libre en la lista de inodes libres. Campos de bloqueo de elementos de las listas de bloques libres y de inodes libres. Estos campos se emplean cuando se realiza una petición de bloqueo o de inode libre. Flag para indicar si el superbloque ha sido modificado o no. En la memoria del sistema se cuenta que una copia del superbloque y de la lista de inodes, para realizar de forma eficiente el acceso a disco. Existe un demonio (syncer) que se encarga de realizar la actualización en disco de los datos de administración que se encuentran en memoria, este demonio se levanta al iniciar el sistema. Naturalmente antes de apagar el sistema también hay que acualizar el superbloque y las tablas de inodes del disco, el encargado de llevar a cabo lo anterior es el programa shutdown. Nodos índices (inodes) Cada archivo en un sistema UNIX tiene asociado un inode. El inode contiene información necesaria para que un proceso pueda acceder al archivo. Esta información incluye: propietario, derechos de acceso, tamaño, localización en el sistema de archivos, etc. La lista de inodes se encuentra situada en los bloques que hay a continuación del superbloque. Durante el proceso de arranque del sistema, el kernel lee la lista de inodes del disco y carga una copia en memoria, conocida como tabla de inodes. Las manipulaciones que haga el subsistema de archivos sobre los archivos van a involucrar a la tabal de inodes pero no a la lista de archivos, ya que la tabla de inodes está cargada siempre en memoria. La actualización periódica de la lista de inodes del disco la realiza un demonio del sistema. Los campos que componen un inode son los siguientes: • Identificador del propietario del archivo. La posesión se divide entre un propietario individual y un grupo de propietarios y define el conjunto de usuarios 84 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • • • • • que tienen derecho de acceso al fichero. El superusuario tiene derecho de acceso a todos los ficheros del sistema. Tipo de archivo. Los archivos pueden ser ordinarios de datos, directorios, especiales de dispositivos y tuberías. Tipo de acceso al archivo. Da información sobre la fecha de la última modificación del archivo, la última vez que se accedió a él y la última vez que se modificaron los datos de su inode. Número de enlaces del archivo. Representa el total de los nombres que el archivo tiene en la jerarquía de directorios. Entradas para los bloques de dirección de los datos de un archivo. Si bien los usuarios tratan los datos de un archivo como si fuesen una secuencia de bytes contiguos, el kernel puede almacenarlos en bloques que no tienen por qué ser contiguos. En los bloques de dirección es donde se especifican los bloques de disco que contienen los datos del archivo. Tamaño del archivo. Los bytes de un archivo se pueden direccionar indicando un offset a partir de la dirección de inicio del archivo (offset 0) . Hay que hacer notar lo siguiente: 1. El nombre el archivo no queda especificado en su inode. 2. Existe una diferencia entre escribir el contenido de un inode en disco y escribir el contenido del archivo. El contenido del archivo (sus datos) cambia sólo cuando se escribe en él. El contenido de un inode cambia cuando se modifican los datos del archivo o la situación administrativa del mismo (propietario, permisos, enlaces, etc.). La tabla de inode contiene la misma información que la lista de inodes, además de la siguiente información: • • • • • El estado del inode, que indica o Si el inode está bloqueado; o Si hay algún proceso esperando a que el inode quede desbloqueado; o Si la copia del inode que hay en memoria difiere de la que hay en el disco; o Si la copia de los datos del archivo que hay en memoria difieren de los datos que hay en el disco (caso de la escritura en el archivo a través del buffer caché). El número de dispositivo lógico del sistema de archivos que contiene al archivo. El número de inode. Punteros a otros inodes cargados en memoria. El kernel enlaza los inodes sobre una cola hash y sobre una lista libre. Un contador que indica el número de copias del inode que están activas (por ejemplo, porque el archivo está abierto por varios procesos). Figura 7-1. Tabla de direcciones de bloque de un inodo. Tipos de archivos en UNIX En UNIX existen cuatro tipos de archivos: • Archivos ordinarios, también llamados archivos regulares o de datos. 85 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos • • • Directorios Archivos de dispositivos, conocidos también como archivos especiales Archivos de comunicación, tales como tuberías o pipes Archivos ordinarios Los archivos ordinarios contienen bytes de datos organizados como un arreglo lineal. Las operaciones que se pueden hacer sobre los datos de uno de estos archivos son: • Leer o escribir cualquier byte de este archivo. • Añadir bytes al final del archivo, aumentando su tamaño. • Truncar el tamaño de un archivo a cero bytes, esto es como si borrásemos el contenido del archivo. Las operaciones siguientes no están permitidas: • • • Insertar bytes en un archivo, excepto al final. Borrar bytes de un archivo, excepto el borrado de bytes con la puesta a cero de los que ya existen. Truncar el tamaño de un archivo a un valor distinto de cero. Los archivos ordinarios, como tales, no tienen nombre y el acceso a ellos se realiza a través de los inodes. Directorios Los directorios son los archivos que nos permiten darle una estructura jerárquica a los sistemas de archivos de UNIX. Su función fundamental consiste en establecer la relación que existe entre el nombre de un archivo y su inode correspondiente. En algunas versiones de UNIX, un directorio es un archivo cuyos datos están organizados como una secuencia de entradas, cada una de las cuales contiene un número de inode y el nombre de un archivo que pertenece al directorio. Al par inode-nombre de archivo se le conoce como enlace (link). Offset 0 inode nombre del archivo 16 32 48 64 .... ...... ....... Figura. Ejemplo de estructura del directorio /etc para UNIX System V El kernel maneja los datos de un directorio con los mismos procedimientos con que se manejan los datos de los archivos ordinarios, usando la estructura inode y los bloques de acceso directo e indirectos. 86 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Los procesos pueden leer el contenido de un directorio como si se tratase de un archivo de datos, sin embargo no pueden modificarlos. El derecho de escritura en un directorio está reservado al kernel. Los permisos de acceso a un directorio tiene los siguientes significados: • • • Permiso de lectura. Permite que un proceso pueda leer ese directorio. Permiso de escritura. Permite a un proceso crear una nueva entrada en el directorio o borrar alguna ya existente. Esto se puede realizar a través de las llamadas: creat, mknod, link o unlink. Permiso de ejecución. Autoriza a un proceso para buscar el nombre de un archivo dentro del directorio. Desde el punto de vista del usuario, vamos a referenciar los archivos mediante su path name. El kernel es quien se encarga de transformar el path name de un archivo a su inode correspondiente. Archivos especiales Los archivos especiales o archivos de dispositivos permiten a los procesos comunicarse con los dispositivos periféricos (discos, cintas, impresoras, terminales, redes, etc.). Existen dos tipos de archivos de dispositivos: archivos de dispositivos modo bloque y archivos de dispositivos modo carácter. Los archivos de dispositivos modo bloque se ajustan a un modelo concreto: el dispositivo contiene un arreglo de bloques de tamaño fijo (generalmente múltiplo de 512 bytes) y el kernel gestiona un buffer caché (implementado vía software) que acelera la velocidad de transferencia de los datos; ejemplos típicos de estos dispositivos son: los discos y las unidades de cinta. En los archivos de dispositivos modo carácter la información es vista por el kernel o por el usuario como una secuencia lineal de bytes; la velocidad de transferencia de los datos entre el kernek y el dispositivo se realiza a baja velocidad, dado que no se involucra al buffer caché; ejemplos típicos de estos dispositivos son: las terminales serie y las líneas de impresora. Los módulos del kernel que gestionan la comunicación con los dispositivos se conocen como drivers de dispositivos (device drivers). El sistema también puede soportar dispositivos software (o seudo dispositivos) que no tienen asociados un dispositivo físico. Por ejemplo, si una parte de la memoria del sistema se gestiona como un dispositivo, los procesos que quieran acceder a esa zona de memoria tendrán que usar las mismas llamadas al sistema que hay para el manejo de archivos, pero sobre el archivo de dispositivo /dev/mem (archivo de dispositivo genérico para acceder a memoria). En esta situación, la memoria es tratada como un periférico más. Como ya hemos visto anteriormente, los archivos de dispositivos, al igual que el resto de los archivos, tienen asociado un inode. En el caso de los archivos ordinarios o de los directorios, el inode nos indica los bloques donde se encuentran los datos de los archivos, pero en el caso de los archivos de dispositivos no hay datos a los que refernciar. En su lugar, el inode contiene dos números conocidos como major number y minor number. El major number indica el tipo de dispositivo de que se trata (disco, cinta, terminal, etc.) y el 87 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos minor number indica el número de unidad dentro del dispositivo. En realidad, estos números los utiliza el kernel para buscar dentro de unas tablas una colección de rutinas que permiten manejar el dispositivo. Esta colección de rutinas constituyen realmente el driver del dispositivo. Archivos de comunicación (tubería o pipe) Un pipe es un archivo con una estructura similar a la de un archivo ordinario. La diferencia principal con éstos es que los datos de un fifo son transitorios. Los fifos se utilizan para comunicar dos procesos. Lo normal es que un proceso abra el fifo para escribir en él y otro para leer de él. Los datos escritos en el fifo se leen en el mismo orden en el que fueron escritos (de ahí su nombre fifo – first in first out). La sincronización del acceso al fifo es algo de lo que se encarga el kernel. El almacenamiento de los datos en un fifo se realiza de la misma forma que en un archivo ordinario, excepto que el kernel sólo utiliza entradas directas de la tabla de direcciones de bloque del inode del fifo. Por lo tanto, un fifo podrá almacenar 10 Kbytes a lo más. 88 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Lectura de directorios Veamos primero algunas funciones que necesitaremos para programar, basados en el Manual del Programador de Linux. PROTOTIPO DE LA FUNCIÓN #include #include DIR *opendir(const char *nombre); La función opendir() proporciona un identificador de bloque al directorio utilizado por las demás funciones de directorio. Devuelve un apuntador al flujo de directorio o NULL si ocurre un error. El flujo se sitúa en la primera entrada del directorio. ERRORES EACCES Permiso denegado. EMFILE El proceso está usando demasiados descriptores de fichero. ENFILE Hay demasiados ficheros abiertos en el sistema. ENOENT El directorio no existe o nombre es una cadena vacía. ENOMEM Memoria insuficiente para completar la operación. ENOTDIR El nombre no es un directorio. PROTOTIPO DE LA FUNCIÓN #include #include struct direct *readdir (DIR *dirp) Cada llamada subsecuente a readdir devuelve un apuntador a una estructura que contiene información sobre la siguiente entrada del directorio. La función readdir devuelve NULL cuando llega al final del directorio. Se debe utilizar rewinddirpara volver a empezar, o closedir para terminar. La estructura dirent se declara como sigue: struct dirent 89 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos { } long d_ino; /* número de nodo-i */ off_t d_off; /* ajuste hasta el dirent */ unsigned short d_reclen; /* longitud del d_name */ char d_name [NAME_MAX+1]; /* nombre fichero (acabado en nulo) */ d_ino es un número de nodo-i. d_off es la distancia desde el principio del directorio hasta este dirent. d_reclen es el tamaño de d_name, sin contar el carácter nulo del final. d_name es un nombre de fichero, una cadena de caracteres terminada en nulo. Ejemplo. Programa para imprimir la lista de archivos contenidos en un directorio. #include #include #include #include #include void main (int argc, char *argv[ ]) { DIR *directorio; struct dirent *entradadir; if (argc !=2 ) { fprintf (stderr, “Use: %s nombre_directorio \n”, argv[0]); exit (1); } if ( (directorio = opendir (argv[1]) )== NULL) { fprintf (stderr, “No puedo abrir el directorio %s. Error %s\n”, argv[1], strerror(errno)); exit(1); } while ( (entrada_dir = readdir (directorio) ) ! = NULL) printf (“%s\n”, entradadir ->d_name); } closedir (directorio); exit(0); 90 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Acceso a archivos especiales Entrada/salida sobre terminales Los terminales son dispositivos especiales que trabajan en modo carácter. Todo programa que se ejecuta en UNIX tiene asociados 3 descriptores de archivo que le dan acceso a su terminal de control. Estos descriptores son: 0 para la entrada estándar, 1 para la salida estándar y 2 para la salida estándar de errores. El archivo de dispositivo que permite a un proceso acceder a su terminal de control es dev/tty. Si el sistema no reservase de forma automática los descriptores anteriores, podríamos hacerlo nosotros mediante las siguientes llamadas: close (O); open ("/dev/tty", O_RDONLY); /* Reserva del descriptor 0. */ close (l); open ("/dev/tty", O_WRONLY); /* Reserva del descriptor 1. */ close (2); open ("/dev/tty", O_WRONLY); /* Reserva del descriptor 2. */ En el sistema hay un terminal especial llamado consola (dispositivo /dev/console) que es empleado durante el arranque para sacar los mensajes relativos a este proceso. Cada usuario que inicia una sesión de trabajo interactiva, lo hace a través de un terminal. Este terminal tiene asociado un archivo de dispositivo que localmente se puede abrir como /dev/tty, pero que visto por otros usuarios tiene la forma /dev/ttyXX, donde XX representa dos dígitos. Como ejemplo para ilustrar el acceso a terminales, vamos a escribir una versión simplificada de la orden write. Esta orden se emplea para enviar mensajes a los usuarios que hay conectados al sistema. Su forma de uso es: $ write usuario Línea de texto 1 Línea de texto 2 . . Línea de texto n ^D [Fin de archivo] Esta secuencia hará que usuario reciba, a través de su terminal, las n líneas de texto que le enviamos. Para poder enviar el mensaje, tenemos que saber si el usuario existe y si tiene iniciada sesión de trabajo. También hay que conocer cuál es el archivo de dispositivo que tiene asociado su terminal. Para obtener respuesta a estas dos preguntas, hay que consultar el archivo /etc/utmp. Este archivo es gestionado por el sistema y contiene información administrativa de los procesos que hay ejecutándose en un instante determinado. Para hacer la lectura de utmp independiente de su estructura, vamos a emplear la función estándar getutent. Su declaración es: 91 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROTOTIPO DE LA FUNCIÓN #include #include struct utmp *getutent ( ) Con cada llamada a getutent se lee un registro del archivo /etc/utmp. Si el archivo no está abierto, la llamada se encarga de abrirlo. Después de leer un registro, la función devuelve un puntero a una estructura del tipo utmp, definida en el archivo de cabecera . Cuando getutent llega al final del archivo, devuelve un puntero NULL. La definición de la estructura utmp es la siguiente: struct utmp { char char char pid_t short ut_user[8]; /* Nombre del usuario. */ ut_id[4]; /* Identificador de /etc/inittab. ut-line[12], /* Nombre delarchivo de dispositivo asociado (console, ttyXX, lnNXX, etc ... ) */ ut_pid /*ldentificador del proceso. */ ut_type; /* Tipo de entrada: EMPTY RUN_LVL BOOT TIME OLD_TIME NE W_TIME IN1T_PROCESS LOGIN_PROCESS USER_PROCESS DEAD_PROCESS ACCOUNTING */ struct exit_status { short e_terminatio; /*Estado de terminación del proceso.*/ short e_exit; /*Estado de salida del proceso. */ }ut_time; /* Se aplica a las entradas cuyo tipo es DEAD_PROCESS.*/ unsigned short ut_reserved1; /* Reservada para usos futuros.*/ char ut_host[16]; /* Nombre del host. */ unsigned long ut_addr; /* Dirección internet del host. */ }; La forma de averiguar si un usuario está o no conectado al sistema, es buscar una entrada del archivo utmp cuyo campo ut_user coincida con el nombre del usuario que buscamos. Para saber 92 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos cuál es el archivo de dispositivo que tiene asociado su terminal, tenemos que utilizar el campo ut_line. A continuación mostrarnos el código del programa mensaje_para, que es equivalente a la orden estándar write. EJEMPLO. Envío de mensajes a un usuario (mensaje_para.c). #include #include #include main (int argc, char *argv[ ]) int tty; char terminal [20], mensaje [256], *logname; struct utmp *utmp, *getutent( ); if (argc != 2) { fprintf (stderr, "Forma de uso: %s usuario\n", argv[0]); exit (-1); } /* Consultamos si el usuario está en sesión. */ while (( utmp = getutent ( )) != NULL && strncmp (utmp->ut_user, argv[1], 8) != 0); if (utmp = = NULL) { printf ("EL USUARIO %s NO ESTÁ EN SESIÓN.\n", argv[0]); exit (0); } /* Apertura del terminal del usuario. */ sprintf (terminal, "/dev/%s", utmp->ut_line); if ((tty = open (terminal, O_WRONLY))= = -1) { perror (terminal); exit (-1); } /* Lectura de nuestro nombre de usuario. */ logname = getenv ("LOGNAME"); /* Aviso al usuario que va a recibir nuestro mensaje. */ sprintf (mensaje, "\n\t\tMENSAJE PROCEDENTE DEL USUARIO %s\07\07\07\n", logname); write (tty, mensaje, strlen (mensaje)); /* Envío del mensaje.*/ 93 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos while (gets (mensaje) != NULL) { write (tty, mensaje, strlen (mensaje)); sprintf (mensaje, "\n"); write (tty, mensaje, strlen (mensaje)); } sprintf (mensaje, "\n\n"); write (tty, mensaje, strlen (mensaje)); close (tty); exit (0); } 94 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 8 Entrada y Salida Un proceso es una entidad en ejecución que tiene asociada un identificador para poder ser identificado. En el sistema se cuenta con procesos pesados, llamados hijos, y procesos ligeros, llamados hilos. Entrada/Salida a disco En los últimos años, el crecimiento en la velocidad de los procesadores y de la memoria principal ha dejado muy atrás la velocidad de acceso a disco. Como el rendimiento del disco está estrechamente relacionado con las cuestiones de diseño, analicemos el por qué de estas bajas velocidades y veamos las políticas de planificación de los discos. Parámetros de rendimiento de discos Los detalles reales de las operaciones de E/S con los discos dependen de la computadora, el sistema operativo y la naturaleza del canal de E/S y del hardware que controla el disco. Cuando la unidad de disco está operando, el disco gira a una velocidad constante. Para leer o escribir, la cabeza debe posicionarse en la pista deseada, al comienzo del sector pertinente. Si el sistema es de cabezas móviles, hay que mover la cabeza para elegir la pista. Si el sistema es de cabezas fijas, habrá que seleccionar electrónicamente una de ellas. En un sistema de cabezas móviles, el tiempo que se tarda en ubicar la cabeza en la pista se llama tiempo de búsqueda. En cualquier caso, una vez que se ha seleccionado la pista, el controlador del disco esperará hasta que el sector apropiado se alinee con la cabeza en su rotación. El tiempo que tarda el comienzo del sector en llagar hasta la cabeza se conoce como retardo de giro, o latancia de giro. La suma del tiempo de búsqueda y el retardo de giro es el tiempo de acceso, es decir, el tiempo que se tarda en llegar a la posición de lectura o escritura. Una vez que la cabeza está ubicada, se puede llevar a cabo la operación de Lectura o Escritura a medida que el sector se mueve bajo la cabeza; está es la parte de transferencia real de datos de la operación. Además del tiempo de acceso y del tiempo de transferencia, en una operación de E/S intervienen algunos retardos. Cuando un proceso emite una petición de E/S, primero debe esperar en una cola a que el dispositivo esté disponible. En este momento, el dispositivo queda asignado al proceso. Si el dispositivo comparte un único canal de E/S o un conjunto de canales con otras unidades de disco, puede producirse una espera adicional 95 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos hasta que el canal esté disponible. En este punto se realizará la búsqueda con que comienza el acceso al disco. En algunos sistemas grandes se emplea una técnica conocida como detección posicional de giro (RPS). Esta técnica funciona de la siguiente forma: Cuando se ejecuta la orden de búsqueda, se libera el canal para que pueda realizar otras operaciones de E/S. Cuando la búsqueda termine, el dispositivo debe averiguar el instante en que los datos van a pasar bajo la cabeza. A medida que el sector se aproxima a la cabeza, el dispositivo intenta restablecer la vía de comunicación con la computadora central. Si la unidad de control o el canal están ocupados con otra operación de E/S, el intento de reconexión no tendrá éxito y el dispositivo debe dar una vuelta completa antes de intentar la reconexión, lo que se denomina una falta de RPS. Espera de Dispositivo Espera de Canal Búsqueda Retardo de Giro Transferencia de Datos Dispositivo Ocupado Tiempo de búsqueda El tiempo de búsqueda es el tiempo necesario para mover el brazo del disco hasta la pista solicitada. El tiempo de búsqueda depende de dos componentes claves: el tiempo de arranque inicial y el tiempo que se tarda en recorrer los cilindros. Por desgracia, este tiempo de recorrido no es lineal, pero nos podemos aproximar por medio de la fórmula: Donde Ts = m × n + s T = tiempo de búsqueda estimada. n = número de pistas recorridas. m = constante que depende de la unidad de disco. s = tiempo de arranque. Tiempo de transferencia El tiempo de transferencia con el disco depende de la velocidad de rotación de la forma siguiente: T = b / (rN) Donde T = tiempo de transferencia. b = número de bytes a transferir. N = número de bytes por pista. r = velocidad de rotación en revoluciones por segundo. Por lo tanto, el tiempo medio de acceso total puede expresarse como Ta= Ts + (1 / 2r) + (b/ rN) 96 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Donde Ts es el tiempo medio de búsqueda. Políticas de planificación de Discos. Como podemos observar la razón de la diferencia en el rendimiento puede encontrarse en el tiempo de búsqueda, entonces se queremos mejorar debemos reducir el tiempo medio gastado en las búsquedas. FIFO La planificación más sencilla de planificación es la de “Primero en entrar, primero en salir” (FIFO). Esta estrategia tiene la ventaja de ser justa porque las peticiones son servidas en el orden en que llegaron. Prioridad Con un sistema de prioridad (PRI), el control de la planificación queda aislado del control del software gestor del disco. Los trabajos por lotes que sean cortos y los trabajos interactivos reciben frecuentemente una prioridad más alta que trabajos mayores que realizan largas operaciones. Esta práctica permite que el sistema haga salir más rápidamente a muchos trabajos cortos y pueda proporcionar un buen tiempo de respuesta interactiva, sin embargo, los trabajos mayores pueden tener que esperar excesivamente. Este tipo de política tiende a ser poco favorable para sistemas de bases de datos. LIFO En los sistemas de proceso de transacciones, conceder el dispositivo al último usuario acarrea pocos o nulos movimientos del brazo al recorrer un archivo secuencial. El provecho de etsa cercanía mejora la productividad y reduce la longitud de las colas. A medida que un trabajo utiliza de forma activa el sistema de archivos, va procesándose tan rápido como es posible. Sin embargo, si el disco está ocupado con una carga de trabajo larga, existe la posibilidad inconfundible de inanición. Una vez que un trabajo ha lanzado una petición de E/S a la cola y haya abandonado la cabeza, no podrá volver a ganar la cabeza a menos que se vayan todos los que estén por delante. La política FIFO, la de prioridades y el esquema LIFO se basan únicamente en las propiedades de la cola o del proceso demandante. Si la posición de la pista actual es conocida por el planificador, puede emplearse una planificación en función del elemento demandado. Primero el más corto La política de “primero el más corto” (SSTF) es elegir la solicitud de E/S a disco que requiera el menor movimiento posible del brazo del disco desde su posición actual. De este modo, siempre se elige procurando el mínimo tiempo de búsqueda. SCAN El algoritmo SCAN es una alternativa que previene la inanición, con el SCAN, el brazo sólo se puede mover en un sentido, resolviendo todas las peticiones pendientes de su ruta, hasta que alcance la última pista o hasta que no haya más peticiones en esa dirección. Se cambia entonces la dirección de servicio y el rastreo sigue en sentido opuesto, volviendo a recoger todas las peticiones en orden. 97 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos C-SCAN La política del C-SCAN restringe el rastreo a una sola dirección. Así cuando se haya visitado la última pista en un sentido, el brazo vuelve al extremo opuesto del disco y comienza a recorrerlo de nuevo, lo que reduce el retardo máximo sufrido por las nuevas peticiones. Con el SCAN, si t es el tiempo esperado de un recorrido desde la pista más interior a la más exterior, entonces el intervalo de servicio esperado para los sectores de los extremos es de 2t. Con el C-SCAN, el intervalo es de orden de t + Smax, donde Smax es el tiempo de búsqueda máximo. SCAN de N pasos y FSCAN La política del SCAN de N pasos divide la cola de peticiones del disco en subcolas de longitud N. Las subcolas se procesan una a una mediante un SCAN. Mientras se procesa una cola, se añadirán nuevas peticiones a las otras. SI hay menos de N peticiones disponibles al final del rastreo, entonces todas serán procesadas en el siguiente recorrido. Para valores grandes de N, el rendimiento del SCAN de N pasos se aproxima al del SCAN; con un valor de N = 1, se está adoptando la política de FIFO. La política de FSCAN emplea dos subcolas. Cuando comienza un rastreo, todas las peticiones están en una de las colas y la otra permanece vacía. Durante el recorrido, todas las peticiones nuevas se colocan en la cola que inicialmente estaba vacía. De este modo, el servicio de nuevas peticiones se retrasará hasta que se hayan procesado las viejas. Nombre Tabla 8-1. Algoritmos de planificación de discos. Descripción Comentarios Selección en función del demandante: RSS Planificación aleatoria Para análisis y simulación. FIFO Primero en entrar, primero El más justo de todos. en salir PRI Prioridad del proceso El control se lleva aparte de la gestión de la cola del disco LIFO Último en entrar, primero en Maximiza la utilización de salir recursos y aprovecha la cercanía. Selección en función del elemento solicitado: SSTF Primero el más corto Gran aprovechamiento y colas pequeñas. SCAN Recorrer el disco de un lado Mejor distribución del servicio. a otro. C-SCAN Recorrer el disco en un solo M e n o r v a r i a b i l i d a d e n e l sentido. servicio. SCAN de N pasos SCAN de N registros a la Garantía de servicio. vez. FSCAN SCAN de N pasos, con N = Sensible a la carga. longitud de la cola al comienzo del ciclo del SCAN. 98 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 9 Señales Las señales son interrupciones de software que pueden ser enviadas a un proceso para informarle de algún evento asíncrono o situación especial. El término señal se emplea también para referirse al evento Introducción Los procesos pueden enviarse señales unos a otros a través de la llamada kill y es frecuente que durante su ejecución, un proceso reciba señales procedentes del kernel. Cuando un proceso recibe una señal, puede proceder de tres diferentes formas (Figura 9-1): 1. Ignorar la señal, con la cual es inmune a la misma. 2. Invocar a la rutina de tratamiento por defecto. Esta rutina no la codifica el programador, sino que la aporta el kernel. Según el tipo de señal, la rutina de tratamiento por defecto va a realizar una acción u otra. Por lo general, suele provocar la terminación del proceso mediante una llamada a exit. Algunas señales no sólo provocan la terminación del proceso, sino que además hacen que el kernel genere en el directorio actual del proceso un archivo llamado core que contiene un volcado de memoria del contexto del proceso. Este mecanismos es muy útil a la hora de depurar programas que contienen errores de manejo de los números en coma flotante, instrucciones ilegales, acceso a direcciones fuera de rango, etc. 3. Invocar a una rutina propia que se encarga de tratar la señal. Esta rutina es invocada por el kernel en si esta se encuentra montada y es responsabilidad del programador codificarla para que tome las acciones pertinentes. 99 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Figura 9-1. Tratamiento de una señal. Tipos de señales Cada señal tiene asociado un número entero positivo, que es el intercambiado cuando uno de ellos envía una señal a otro. En UNIX System V hay definidas 19 señales, y en el 4.3BSD, 30. Las señales las podemos clasificar en los siguientes grupos: • • • • • • Señales relacionadas con la terminación de procesos. Señales relacionadas con las excepciones inducidas por los procesos. Por ejemplo, el intento de acceder fuera del espacio de direcciones virtuales, los errores producidos al manejar números en coma flotante, etc. Señales relacionadas con los errores irrecuperables originados en el transcurso de una llamada al sistema. Señales originadas desde un proceso que se está ejecutando en modo usuario. Por ejemplo, cuando un proceso envía una señal a otro vía kill, cuando un proceso activa un temporizador y se queda en espera de la señal de alarma, etc. Señales relacionadas con la interacción con la terminal. Por ejemplo, pulsar la tecla break. Señales para ejecutar un programa paso a paso. En el archivo de cabecera están definidas las señales que puede manejar el sistema y sus nombres. Las 19 señales del UNIX System V son: SIGHUP (1) SIGINT (2) SIGQUIT (3) Hangup. Es enviada cuando un terminal se desconecta de todo proceso del que es terminal de control. También se envía a todos los procesos de un grupo cuando el líder del grupo termina su ejecución. La acción por defecto de esta señal es terminar la ejecución del proceso que la recibe. Interrupción. Se envía a todo proceso asociado con un terminal de control cuando se pulsa la tecla de interrupción. Su acción por defecto es terminar la ejecución del proceso que la recibe. Salir. Similar a SIGINT, pero es generada al pulsar la tecla de salida (Control-\). Su acción por defecto es generar un archivo core y terminar el proceso. 100 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos SIGILL (4) SIGTRAP (5) SIGIOT (6) SIGMT (7) SIGFPE (8) SIGKILL (9) SIGBUS (10) SIGSEGV (11) SIGSYS (12) SIGPIPE (13) SIGALRM (14) SIGTERM (15) SIGUSR1 (16) SIGUSR2 (17) SIGCLD (18) SIGPWR (19) Instrucción ilegal. Es enviada cuando el hardware detecta una instrucción ilegal. Los programas que manejan punteros a funciones que no han sido correctamente inicializados producen este tipo de error. Su acción por defecto es generar un archivo core y terminar el proceso. Trace trap. Es enviada después de ejecutar cada instrucción, cuando el proceso se está ejecutando paso a paso. Su acción por defecto es generar un archivo core y terminar el proceso. I/O trap instruction. Se envía cuando se da un fallo de hardware. La naturaleza de este fallo depende de la máquina, aquí también se genera un archivo core. Emulator trap instruction. También indica un fallo de hardware. Raras veces se utiliza. Su acción por defecto es generar un archivo core y terminar el proceso. Error en coma flotante. Es enviado por el hardware cuando detecta un error en coma flotante, como el uso de número en coma flotante con unformato desconocido, errores de overflow o underflow, etc. Su acción por defecto es generar un archivo core y terminar el proceso. Kill. Esta señal provoca irremediablemente la terminación del proceso. Genera un archivo core y termina el proceso. Bus error. Se produce cuando se da un error de acceso a memoria. Las dos situaciones típicas que la provocan son: intentar acceder a una dirección que físicamente no existe o intentar acceder a una dirección impar. Su acción por defecto es generar un archivo core y terminar el proceso. Violación de segmento. Es enviada a un proceso cuando intenta acceder a datos que se encuentran fuera de su segmento de datos. Su acción por defecto es generar un archivo core y terminar el proceso. Argumento erróneo en una llamada al sistema. No se usa. Intento de escritura en una tubería de la que no hay nadie leyendo. Esto suele ocurrir cuando el proceso de lectura termina de una forma anormal. Su acción por defecto es terminar el proceso. Alarm clock. Es enviada a un proceso cuando alguno de sus temporizadores descendentes llega a cero. Su acción por defecto es terminar el proceso. Finalización software. Es la señal utilizada para indicarle a un proceso que debe terminar su ejecución. Esta señal no es tajante como SIGKILL y puede ser ignorada. Esta señal es enviada a todos los procesos durante el shutdown. Su acción por defecto es terminar el proceso. Señal número 1 de usuario. Esta señal esta reservada para uso del programador. Su acción por defecto es terminar el proceso. Señal número 1 de usuario. Su significado es idéntico al de SIGUSR1. Muerte del proceso hijo. Es enviada al proceso padre cuando alguno de sus procesos hijos termina. Esta señal es ignorada por defecto. Fallo de alimentación. 101 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Tabla 9-1. Señales generales. Acción por defecto Nombre Número Generar core Terminar Ignorar SIGHUP 01 * SIGINT 02 * SIGQUIT 03 * * SIGILL 04 * * SIGTRAP 05 * * SIGIOT 06 * * SIGEMT 07 * * SIGFPE 08 * * SIGKILL 09 SIGBUS 10 * * SIGSEGV 11 * * SIGSYS 12 * * SIGPIPE 13 * SIGALRM 14 * SIGTERM 15 * SIGUSR1 16 * SIGUSR2 17 * SIGCLD 18 * SIGPWR 19 * * En Linux, se pueden encontrar las señales en el archivo /usr/include/asm-generic/signal.h, Nombre Número Tabla 9-2. Señales en Linux. Descripción SIGHUP 01 Termina el proceso líder SIGINT 02 Tecla Ctrl C pulsada SIGQUIT 03 Tecla Ctrl \ pulsada termina terminal SIGILL 04 Instrucción Ilegal SIGTRAP 05 Traza de los programas S I G A B R T / 06 SIGIOT SIGBUS 07 Terminación anormal SIGFPE 08 Error de aritmético, coma flotante SIGKILL 09 Elimar procesos incondicionalmente SIGUSR1 10 Señal definida por el usuario Error de bus 102 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos SIGSEGV 11 Violación de segmento SIGUSR2 12 Señal definida por el usuario SIGPIPE 13 Escritura de pipe sin lectores SIGALRM 14 SIGTERM 15 Señal enviada por el kernel cuando es fin del reloj ITIMER_REAL Señal de terminación del software SIGTKFLT 16 Desbordamiento de coprocesador matemático SIGCHLD 17 SIGCONT 18 SIGSTOP 19 Señal enviada por el núcleo a un padre cuando este hace un wait, para avisarle que un hijo ha terminado con un exit. Señal cuando el proceso se lleva a segundo o primer plano Suspensión de un proceso SIGTSTP 20 Suspensión debido a Ctrl Z SIGTTIN 21 SIGTTOU 22 Suspensión de un proceso en segundo plano que trata de leer en la terminal Suspensión de un proceso en segundo plano que trata de escribir en la terminal Datos urgentes para los sockets Sobre pasado el límite de tiempo en el CPU Sobre pasado el tamaño del archivo Fin del temporizador ITIMER_VIRTUAL SIGURG 23 SIGXCPU 24 SIGXFSZ 25 SIGVTALAR 26 M SIGPROF 27 SIGWICH 28 SIGIO 29 SIGPWR 30 S I G S Y S / 31 SIGUNUSED SIGRTMIN 32 Fin del temporizador ITIMER_PROF Cambio de tamaño de una ventana usado por X11 Datos disponibles para una entrada/salida Fallo de alimentación Error de argumento en una llamada Marca el límite de señales en tiempo real 103 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Señales en Linux Para enviar una señal desde un proceso a otro o a un grupo de procesos, se emplea la llamada a kill. Su declaración es: PROTOTIPO DE LA FUNCIÓN #include int kill (pid, sig) pid_t pid; Pid identifica al conjunto de procesos que queremos enviarle la señal. Pid es un número entero y los distintos valores que puede tomar tienen los siguientes significados: Pid > 0 Es el PID del proceso al que le enviamos la señal. Pid = 0 La señal es enviada a todos los procesos que pertenecen al mismo grupo que el proceso que la envía. Pid = -1 La señal es enviada a todos aquellos procesos cuyo ID real es igual al ID efectivo del proceso que la envía. Si el proceso que la envía tiene ID efectivo de superusuario, la señal es enviada a todos los procesos, excepto al proceso 0 (swapper) y al proceso 1 (INIT). Pid < -1 La señal es enviada a todos los procesos cuyo ID de grupo coincide con el valor absoluto de pid. En todos los casos, si el ID efectivo del proceso no es el del superusuario o si el proceso que envía la señal no tiene privilegios sobre el proceso que la va a recibir, la llamada a kill falla. Sig es el número de la señal que queremos enviar. Si el envío se realiza satisfactoriamente, kill devuelve 0; en caso contrario, devuelve –1 y en errno estará el código del error producido. Tratamiento de señales. Para especificar qué tratamiento debe realizar un proceso al recibir una señal, se emplea la llamada signal. Su declaración es la siguiente: 104 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos PROTOTIPO DE LA FUNCIÓN #include void *signal (sig, accion) (); int sig; void (*accion) ( ); Sig es el número de la señal sobre la que queremos especificar la forma de tratamiento. Accion es la acción que queremos que se inicie cuando se reciba la señal. Accion puede tomar tres tipos de valores: SIG_DFL SIG_IGN Dirección Indica que la acción a realizar cuando se recibe la señal es la acción por defecto asociada a la señal. Indica que la señal se debe ignorar. Es la dirección de la rutina de tratamiento de la señal. La declaración de esta función debe ajustarse a: PROTOTIPO DE LA FUNCIÓN #include void handler (sig [, code, scp]) int sig, code; struct sigcontext *scp; Cuando se recibe la señal sig, el kernel se encarga de llamar a la rutina hndler pasándo los parámetros sig, code y scp. Sig es el número de la señal, code contiene información sobre el hardwar en el momento de invocar a handler y scp contiene información de contexto definida en . code y scp son opcionales. La llamada a la rutina handler es asíncrona, es decir, que pude darse en cualquier instante de la ejecución del programa. #include #include #include void sigint_handler (); int main () { if (signal (SIGINT, sigint_handler) = = SIG_ERR) 105 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos { } perror (“señal”); exit (-1); while (1) { printf (“En espera de Ctrl-C \n”); sleep (99); } } void sigint_handler (int sig) { static cont = 0; printf (“señal número %d recibida \n”, sig); if (cont < 20) printf (“Contador = %d\n”, cont++); else exit (0); if (signal (SIGINT, sigint_handler) == SIG_ERR) { perror (“Señal”); exit (-1); } } Saltos globales. Setjmp y longjmp La rutina de tratamiento de una señal puede hacer que el proceso vuelva a alguno de los estados por los que ha pasado con anterioridad. Esto no sólo es aplicable a las rutinas de tratamiento de señales sino que se puede extender a cualquier función. Para realizar esto nos valemos de las funciones estándar de librería setjmp y longjmp. PROTOTIPO DE LA FUNCIÓN #include int setjmp (jmp_buf env); void longjmp (jmp_buf env, int val); Setjmp guarda el entorno de pila en env para su uso posterior de longjmp. Setjmp devuelve el valor 0 en su primera llamada. Longjmp restaura el entorno guardado en env por una llamada previa a setjmp. Después de haberse ejecutado la llamada a longjmp, el flujo de la ejecución del programa vuelve al punto donde se hizo la llamada a setjmp, pero en este caso setjmp devuelve el valor val que hemos pasado mediante longjmp. Esta es la forma de saber si setjmp está saliendo 106 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos de una llamada para guardar el entorno 0 de una llamada de longjmp. Longjmp no puede hacer que setjmp devuelva 0, ya que en el caso de que val valga 0, setjmp va a devolver 1. jmp_buf entorno; int valor; .... .... .... valor = setjmp (entorno); (valor = 0) (valor =10) longjmp (entorno, 10); /*** Programa de ejemplo del uso de las funciones setjmo y longjmp forma de uso: $ salta & kill –10 pid Cada vez que le enviemos la señal SIGUSR1, el proceso va a reanudar su ejecución en un punto de fallback. *****/ #include #include #include #include jmp_buf env; void sigusr1_handler ( ); int main ( ) { int i; signal (SIGUSR1, sigusr1_handler); for (i=0 ; i < 100; i++) { if (setjmp (env) = =0) printf (“Punto de regreso en el estado %d\n”,i); else /* esta parte se ejecuta cuando se efectúa una llamada a longjmp */ printf (“Regreso al punto de fallback del estado %d\n”,i); 107 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos sleep (10); } exit (0); } void sigusr1_handler (int sig) { signal (SIGUSR1, sigusr1_handler); longjmp (env, 1); } REFERENCIA 1. UNIX Programación Avanzada. F. M. Marquez. Alfaomega 2. Lección 4. Señales. http://sopa.dis.ulpgc.es/ii-dso/leclinux/interrupciones/senales/ lec4_senales.pdf 108 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Capítulo 10 Sistema Distribuido Las señales son interrupciones de software que pueden ser enviadas a un proceso para informarle de algún evento asíncrono o situación especial. El término señal se emplea también para referirse al evento. 1. Introducción a los sistemas distribuidos Los sistemas de cómputo han sufrido y están sufriendo una revolución, todo esto debido a dos avances tecnológicos, el primero de ellos fue el desarrollo de poderosos microprocesadores, y el segundo fue la creación de redes de área local (LAN). El resultado de estas tecnologías hace posible reunir sistemas de cómputo compuestos por un gran número de CPU, conectados mediante una red de alta velocidad, que recibe el nombre genérico de sistemas distribuidos. En base a esto podemos dar nuestra primera definición de sistema distribuido: Un sistema distribuido es una colección de computadoras independientes, que trabajan como una única computadora. Cabe observar que construir sistemas distribuidos, no significa necesariamente una buena idea se necesita analizar las ventajas o desventajas que el sistema presentara en comparación con los sistemas centralizados (sistemas con sólo un procesador). Ventajas 1. Económicas. Permite compartir dispositivos. 2. Velocidad. Un sistema distribuido puede tener mayor poder de cómputo, difundiendo la carga de trabajo entre las máquinas en forma eficiente. 3. Distribución inherente. Algunas aplicaciones utilizan máquinas que están separadas a cierta distancia, permitiendo que varios usuarios tengan acceso a una base de datos común. 4. Confiabilidad. Si una máquina se descompone, el sistema puede sobrevivir como un todo. 5. Crecimiento por incrementos. Se puede añadir poder de cómputo en pequeños incrementos. Desventajas 1. Redes. Las redes se pueden saturar o pueden perder mensajes. 2. Seguridad. Personas no autorizadas pueden ganar acceso a recursos no autorizados. 109 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos 1.1 Conceptos de Hardware Aunque todos los sistemas distribuidos constan de varios CPU, existen diversas formas de organizar la interconexión y la comunicación. La taxonomía más citada para llevar a cabo lo anterior es la taxonomía de Flynn (1972). Flynn, clasifico las arquitecturas de acuerdo a los flujos de datos y a los flujos de instrucciones. El concepto de flujos de datos se refiere al número de operandos que se pueden procesar en un tiempo y el de flujos de instrucciones se refiere a cuantos programas se pueden ejecutar en un tiempo. De acuerdo a su clasificación existen cuatro tipos de computadoras: SISD, SIMD, MISD y MIMD (Tabla 10-1). En la figura 10-1 se muestran las tres categorías aplicadas en la industria. Figura 10-1. Categoría de Flynn utilizadas en la industria. Tabla 10-1. Taxonomía de Flynn. Categoría SISD (Single instruction stream, single data stream) SIMD (Single instruction stream, multiple data stream MISD (Multiple instruction stream, single data stream) MIMD (Multiple instruction stream, multiple data stream) Un solo flujo de instrucciones y un solo flujo de datos. Un solo flujo de instrucciones y varios flujos de datos. Varios flujos de instrucciones y un solo flujo de datos. Varios flujos de instrucciones y varios flujos de datos. La primera categoría (SISD) se refiere a las maquinas de arquitectura Von Newmann como las computadoras personales (PC’s) que manejamos comúnmente, como sabemos este tipo de maquinas tienen limites físicos que limitan su capacidad de procesamiento; 110 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos esto motivó la investigación de maquinas de arquitectura en paralelo para obtener un mayor rendimiento. La máquina SIMD se conoce como procesador de arreglos, dispositivo que realiza en esencia la misma operación simultáneamente en cada elemento de un arreglo. En esta categoría se incluyen los procesadores vectoriales y los procesadores de canalización. Los procesadores de arreglos ejecutan la misma instrucción en forma simultánea sobre todos los elementos de un arreglo. Los procesadores de arreglos no son útiles en los ambientes de cómputo de propósito general, caracterizados por la necesidad de realizar tareas independientes en paralelo. Uno de los primeros procesadores de arreglos fue IILIAC IV, desarrollado en la University of Illinois. El procesador en paralelo a gran escala MPP (Massive Parallel Processor) es una máquina SIMD con 16 384 procesadores. Puede realizar más de 6 mil millones de operación de 8 bits segundo, fue diseñado para la NASA por Goodyear Aerospace para realizar tareas de procesamiento de imágenes. Esta máquina ha sido superada por la máquina de conexión CM (Conecction Machine) de 65 536 procesadores, un procesador de arreglos construido por Thinking Machines Corp. La canalización es una técnica para mejorar el rendimiento que permite que varias instrucciones en lenguaje de máquina estén en diferentes etapas de ejecución al mismo tiempo. Los sistemas con canalización comienzan a trabajar con la siguiente instrucción o con varias de las siguientes instrucciones, mientras se está ejecutando la instrucción actual. El procesamiento vectorial requiere específicamente instrucciones con vectores en lenguaje de máquina. Una instrucción vectorial indica la operación que se va a realizar y especifica la lista de operandos (denominada vector) sobre la que se operará. Cuando se ejecuta una operación vectorial, se alimentan los elementos del vector a la canalización apropiada uno a la vez, retrasados por el tiempo que toma completar una etapa en la canalización. Los compiladores “vectorizan” los programas para que se ejecuten eficientemente en los procesadores de vectores. El procesador de vectores Cray-1 tiene 13 canalizaciones que pueden trabajar en paralelo; están dedicados a operaciones tales como suma de punto flotante, multiplicación de punto flotante, aproximación recíproca, suma de punto fijo, etc. La categoría MIMD se dividen en dos grupos: aquellas que tienen memoria compartida, generalmente llamadas multiprocesadores, y las que cuentan con memoria privada, llamadas multicomputadoras. Cada uno de estos grupos se divide en dos categorías: bus (ejemplos estaciones de trabajo en una LAN) y conmutador (ejemplos Ultracomputadora RP3, transputer). En la figura 10-2 se describe estas dos categorías. En la categoría de sistemas de bus existe una red, cable u otro medio que conecta todas las máquinas, y los sistemas con conmutador cuentan con cables individuales para unir las máquinas y diferentes patrones de cableado. Los mensajes se mueven a través de los cables y se toma una decisión explícita de conmutación en cada etapa, para dirigir el mensaje a lo largo de uno de los cables de salida. 111 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Taxonomía de S. D. y Paralelos Sistemas Operativos MIMD Computadoras paralelas y distribuidas Débilmente acopladas Fuertemente acopladas Multiprocesadores (memoria compartida) Bus Secuencia, repetición Multiprocesadores (memoria privada) Con conmutador Ultracomputadora, RP3 Con conmutador Bus Estación de trabajo en una LAN Hipercubo, Transputer Figura 10-2. Una taxonomía de los sistemas de cómputo paralelos y distribuidos. Las computadoras paralelas y distribuidas forman un sistema es fuertemente acoplado, cuando el retraso que se experimenta al enviar un mensaje de una computadora a otra es corto y la tasa de transmisión es alta; y un sistema débilmente acoplado cuando el retraso de los mensajes entre las máquinas es grande y la tasa de transmisión de los datos es baja. Uno de los atractivos de los sistemas de multiprocesamiento consiste en que si falla un procesador, casi siempre pueden continuar trabajando los procesadores restantes. Los sistemas multiprocesadores tienden a utilizarse como sistemas paralelos, y los sistemas multicomputadoras como sistemas distribuidos, aunque esto no siempre es cierto. 1.2 Esquemas de interconexión de procesadores. Uno de los problemas fundamentales en el diseño de los sistemas de multiprocesamiento es determinar la forma de conectar los múltiples procesadores y los procesadores de entrada/salida con las unidades de almacenamiento. Algunos de estos esquemas son: ducto compartido o basado en bus, matriz de conmutadores cruzados o conmutador de punto de cruce e hipercubo. Ducto compartido Esta organización de multiprocesadores, la cual se muestra en la figura 10-3, utiliza una sola trayectoria de comunicación entre todos los procesadores, las unidades de almacenamiento y los procesadores de E/S. El esquema de red de área local Ethernet utiliza un ducto compartido. El procesador o procesadores de E/S que desee transferir datos debe comprobar primero la disponibilidad del ducto y de la unidad de destino, e iniciar después la transferencia de datos. Las unidades receptoras deben ser capaces de reconocer los mensajes del ducto 112 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos destinados a ellas y deben interpretar y reconocer las señales de control que se reciban de la unidad transmisora. Ventajas Desventajas     Facilita la adición de nuevas unidades El ducto sólo puede manejar una transmisión a la vez. El sistema entero falla si el ducto falla. La velocidad está limitada por la velocidad de transmisión del ducto. Puede bajar el rendimiento si el ducto es muy utilizado. Interconexión de procesadores  Procesador Procesador Memoria Memoria Procesador E/S Procesador E/S Ducto Memoria Procesador E/S Memoria Procesador E/S Procesador Procesador Canal compartido Figura 10-3. Organización de multiprocesadores con ducto compartido. Ventajas Desventajas Facilita la adición de El canal sólo puede manejar una transmisión a la vez. Matriz de conmutadores cruzados. nuevas unidades El sistema entero falla si el canal falla. La velocidad estáde limitada por la hasta velocidad de Si se aumenta el número de ductos en un sistema ducto compartido igualar el transmisión número de unidades de almacenamiento, se del creacanal. una organización de multiprocesadores denominada matriz de conmutadores cruzados, en la cual sihay una trayectoria distinta Puede bajar el rendimiento el canal es muy utilizado. ! ! ! ! ! hacia cada unidad de almacenamiento. Sistemas Distribuidos M.C. Gabriel Gerónimo Castillo Ventajas  Desventajas   Puede manejar transmisiones simultáneas a todas las unidades de almacenamiento. Hardware muy complejo, debe ser capaz de resolver conflictos de acceso a la misma unidad de almacenamiento. El costo del conmutador crece en proporción al producto del número de unidades funcionales por el número de unidades de memoria. Figura 10-4. Organización de multiprocesadores con matriz de conmutadores cruzados. Hipercubo La red de interconexión hipercubo hace posible conectar un gran número de procesadores. Un hipercubo de dos dimensiones no es más que un cuadrado; un 113 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos hipercubo de tres dimensiones se forma conectando los elementos correspondientes de dos hipercubos bidimensionales. Un hipercubo de cuatro dimensiones se forma conectando los elementos correspondientes de dos hipercubos tridimensionales, y así sucesivamente. La máquina de conexión (CM) utiliza un esquema de conexión de hipercubo de 16 dimensiones para conectar entre sí 65 536 procesadores. Figura 10-5. Redes de interconexión de hipercubo. 1.3 Sistemas débilmente acoplados y Sistemas fuertemente acoplados. El multiprocesamiento débilmente acoplado implica conectar dos o más sistemas de cómputo independientes mediante un enlace de comunicación (Figura 10-6). Cada sistema tiene su propio sistema operativo y su almacenamiento. Los sistemas pueden funcionar en forma independiente y se pueden comunicar entre sí. Los sistemas individuales pueden tener acceso a los archivos de otros por medio del enlace de comunicación, y en algunos casos los sistemas pueden enviar tareas a los procesadores que no estén muy cargados para equilibrar la carga de trabajo. La comunicación entre los procesadores se realiza por medio de transferencia de mensajes o de llamadas a procedimientos remotos. Sistema débilmente acoplado Almacenamiento Almacenamiento Enlace de comunicación Procesador Procesador E/S E/S Figura 10-6. Multiprocesamiento débilmente acoplado. El multiprocesamiento fuertemente acoplado utiliza un almacenamiento único compartido por los diferentes procesadores y un solo sistema operativo que controla todos los procesadores y el hardware del sistema (Figura 10-7). La comunicación se realiza mediante memoria compartida. El BBN Butterfly y el IBM 3090 son ejemplos de sistemas fuertemente acoplados. 114 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos Procesador E/S Almacenamiento Procesador E/S Figura10-7. Multiprocesamiento fuertemente acoplado. 1.4 Organizaciones de los sistemas operativos para multiprocesadores. Una de las diferencias principales entre los sistemas operativos para multiprocesadores y los de un solo procesador es la organización y la estructura del sistema. Las organizaciones básicas de los sistemas operativos para los multiprocesadores son maestro/esclavo, ejecutivos individuales y simétrico. 1.4.1 Maestro/esclavo. En la organización de múltiples procesadores maestro/esclavo, un procesador se designa como maestro o amo y los otros son los esclavos. Los esclavos pueden ejecutar eficientemente los trabajos limitados por un CPU, pero los trabajos limitados por E/S que se ejecuten en los esclavos ocasionarán llamados frecuentes a servicios que sólo puede realizar el maestro. Desde un punto de vista de confiabilidad, si falla un esclavo se pierde parte de la capacidad de cómputo, pero puede seguir el sistema funcionando, pero si falla el maestro, el sistema no podrá realizar operaciones de E/S. La desventaja principal de esta organización es la asimetría del hardware. Sólo el maestro puede ejecutar el sistema operativo. Un procesador esclavo sólo puede ejecutar programas de usuario. 1.4.2 Ejecutivos individuales. En la organización de ejecutivos individuales cada procesador tiene su propio sistema operativo y responde a las interrupciones de los usuarios que estén ejecutando sus procesos en ese procesador. Un proceso asignado para ejecutarse en un procesador específico se ejecuta hasta terminar en ese procesador. La organización de ejecutivos individuales es más confiable que la organización maestro/ esclavo; es poco probable que la falla de un solo procesador cause una falla catastrófica al sistema. Cada procesador controla sus propios recursos dedicados, como archivos y dispositivos de E/S. Existe una contención mínima por los datos del sistema operativo porque los datos están distribuidos entre los sistemas operativos individuales para su propio uso. Los procesadores no cooperan en la ejecución de un proceso individual. 115 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos La desventaja que presenta esta organización es que algunos procesadores pueden permanecer sin trabajo mientras otro ejecuta un proceso muy largo. 1.5 Organización simétrica. El multiprocesamiento simétrico es la organización más compleja al llevarla a cabo, pero su tarea es recompensaba al ser la más confiable; una falla en un procesador hace que el sistema operativo expulse el procesador de su conjunto procesadores disponibles y tome nota del problema. El sistema puede seguir funcionando a niveles menores (es decir, una degradación paulatina) mientras se realizan las reparaciones. Todos los procesadores son idénticos, así el sistema operativo puede utilizar cualquiera de ellos para controlar cualquier dispositivo de E/S o para hacer referencia a cualquier unidad de almacenamiento. Como muchos procesadores pueden estar ejecutando el sistema operativo al mismo tiempo, se requiere código reentrante y exclusión mutua. Debido a la simetría, es posible equilibrar la carga de trabajo con mayor precisión que con otras organizaciones. El hardware y el software juegan un papel importante para resolver los conflictos que se presenten, como por ejemplo el hardware se encarga de resolver el conflicto entre los procesadores que intentan obtener acceso a la misma zona de almacenamiento al mismo tiempo, y el software soluciona los conflictos relacionados con el acceso a los datos de todo el sistema en general. Un proceso que se ejecute en un multiprocesador simétrico puede ser ejecutado en diferentes ocasiones por cualquiera de los procesadores equivalentes: el sistema operativo flota de un procesador a otro. El procesador encargado en un momento dado de los datos y funciones del sistema se denomina procesador ejecutivo, y sólo un procesador puede ser ejecutivo a la vez, con lo cual se evitan conflictos sobre la información global del sistema. Los problemas de contención pueden ser graves, sobre todo porque varios procesadores pueden estar al mismo tiempo en el estado supervisor. El diseño cuidadoso de las estructuras de datos del sistema resulta esencial para evitar una excesiva exclusión por bloqueo. Una forma reducir la contención es dividir las estructuras de datos del sistema en entidades individuales e independientes que se puedan bloquear en forma individual. 1.6 Aspectos en el diseño de un sistema operativo distribuido. En las secciones siguientes se muestran los aspectos claves que se deben tener presente cuando se contruyen sistemas operativos distribuidos. 1.6.1 Transparencia. El aspecto de transparencia se refiere al hecho de que los usuarios del sistema distribuido piensen que toda la colección de máquinas que forman al sistema, es solo un sistema de tiempo compartido de un procesador. La transparencia se aplica a varios aspectos de un sistema distribuido como son: localización, migración, réplica, concurrencia y paralelismo. La transparencia de localización se refiere al hecho de que los usuarios no deben indicar la localización de los recursos de hardware y software, como los CPU, impresoras, archivos y bases de datos. 116 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos La transparencia de migración significa que los recursos se pueden mover a voluntad del usuario sin cambiar sus nombres, por ejemplo los directorios servidores se podrán montar en los lugares que el usuario desee dentro de la jerarquía de sus directorios. La transparencia por réplica se refiere al hecho de que el sistema operativo es libre de fabricar copias adicionales de los archivos y otros recursos sin que lo noten los usuarios. En la transparencia con respecto a la concurrencia los usuarios pueden compartir de forma automática los recursos del sistema. Por último tenemos la más difícil, la transparencia con respecto al paralelismo esta transparencia permite que las actividades puedan ocurrir en paralelo sin que el usuario se entere. 1.6.2 Flexibilidad. Antes de hablar de flexibilidad, primero veamos las dos formas de estructurar los sistemas distribuidos, la primera de ellas es por medio de un núcleo monolítico, el cual dice que cada máquina debe ejecutar un núcleo tradicional que proporcione la mayoría de los servicios, y que aumente su poder con las capacidades de red y la integración de servicios remotos; el segundo modelo es el micronúcleo, el cual sostiene que el núcleo debe proporcionar lo menos posible de servicios y que el grueso de los servicios del sistema operativo se obtenga a partir de los servicios a nivel de usuario. En el núcleo monolítico las llamadas al sistema se realizan mediante señalamientos al núcleo, en donde se realiza el trabajo, para que después el núcleo regrese el resultado deseado al proceso de usuario, esta es la única ventaja potencial de este núcleo su rendimiento, ya que los señalamientos al núcleo y la realización de todo el trabajo puede ser más rápido que el envío de mensajes a los servidores remotos, aunque estudios han demostrado que en la practica esta ventaja no existe. En los sistemas micronúcleo para buscar un nombre, leer un archivo u obtener algún otro servicio, el usuario envía un mensaje al servidor apropiado, el cual realiza el trabajo y regresa el resultado. La ventaja de este método es que es altamente modular, existe una interfaz definida con cada servicio y cada servicio es igual de accesible para todos los clientes. Además es fácil implantar, instalar y depurar nuevos servicios, puesto que la adición o modificación de un servicio no requiere el alto total del sistema y el arranque de un nuevo núcleo, como en el caso del núcleo monolítico, otro punto a su favor es que los usuarios que no estén satisfechos con alguno de los serviciso oficiales son libres de escribir su propio servicio. Es precisamente esta capacidad de añadir, eliminar y modificar servicios lo que da al micronúcleo su flexibilidad. 1.6.3 Confiabilidad. La confiabilidad involucra disponibilidad, consistencia, seguridad y tolerancia a fallas; la disponibilidad se refiere a la fracción de tiempo en la cual se puede utilizar el sistema, una manera de mejorar la disponibilidda es la redundancia, se pueden duplicar piezas de hardware y de software, de modo que si una falla, las otras pueden llenar su hueco, pero aquí entra el segundo aspecto, la consistencia, si los archivos se almacenan de manera redundante en varios servidores, todas las copias deben ser consistentes. Aspecto de seguridad se debe considerar para que los archivos y los recursos sean protegidos contra acceso o uso no autorizado, otro aspecto relacionado con la confiabilidad es la tolerancia 117 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos a fallas, por ejemplo si el servidor falla y vuelve a arrancar de manera súbita, este debe recuperar todas las actividades que estaban en proceso. 1.6.4 Desempeño. Cuando se ejecuta una aplicación en un sistema distribuido, esta no debe parecer peor que su ejecución en un procesador. En el desempeño se pueden analizar diferentes métricas entre las cuales se encuentran: el tiempo de respuesta, el rendimiento (número de trabajos por hora) y el uso del sistema. El problema del desempeño se complica por el hecho de que la comunicación, factor esencial en un sistema distribuido (y ausente en un sistema con un procesador) es algo lenta por lo general. El envío y la obtención de un mensaje en una LAN tarda unos milisegundos, debido a los protocolos de comunicación entre el emisor y el receptor, más el tiempo que tardan los bits en el cable de red. Así, para optimizar el desempeño, con frecuencia se minimizar el número de mensajes. La dificultad con esta estrategia es que la mejor forma de mejorar el desempeño es tener muchas actividades en paralelo, pero la desventaja es que esto requiere el envío de muchos mensajes. Una posible solución a esta desventaja es verificar el tamaño de grano de todos los cálculos; los trabajos que implican gran número de pequeños cálculos, en particular aquellos que interactúan en gran medida con otros, pueden ser la causa de algunos problemas en los sistemas distribuidos con una comunicación lenta. Se dice que tales trabajos exhiben un paralelismo de grano fino. Por otro lado, los trabajos que implican grandes cálculos y bajas tasas de interacción, así como pocos datos, muestran un paralelismo de grano grueso, y estos son los que ayudan a resolver esta desventaja. La tolerancia a fallas también tiene su precio. Algunas veces, una buena confiabilidad se logra mejor con varios servidores que cooperen en forma cercana en una solicitud. Por ejemplo, si una solicitud llega a un servidor, éste podría enviar de manera inmediata una copia del mensaje a uno de sus colegas, de forma que si falla antes de terminar, el colega se puede encargar de la solicitud, y si concluye con esta, debe informar al colega que ha terminado el trabajo, lo que representa otro mensaje. Así, tenemos al menos dos mensajes adicionales, que en el caso normal, cuestan tiempo y capacidad de red, y no producen una ganancia notable. 118 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos DEFINICIONES Concurrencia. La concurrencia se refiere al hecho de compartir recursos en el mismo marco de tiempo. Esto por lo común significa que varios procesos comparten la misma CPU o la memoria o un dispositivo de E/S. Paralelismo. Consiste en la distribución de la carga de trabajo entre varios procesadores. De esta manera se consigue un aumento de velocidad notable en procesos que no son suficientemente rápidos. Multiprogramación. Es la gestión de varios procesos dentro de un sistema monoprocesador. Multiproceso. Es la gestión de varios procesos dentro de un sistema multiprocesador. Proceso distribuido. Es la gestión de varios procesos que se ejecutan en sistemas de computadoras múltiples y remotas. Proceso. Es una entidad activa. Es una instancia de un programa cuya ejecución aún no ha terminado. Un programa se convertir en un proceso si se tiene lo siguientes: a) el sistema operativo le asigna memoria a la imagen del programa, b) le asigna un ID (identificar de proceso) para distinguir entre varios procesos, el estado del proceso indica el estado de ejecución, c) el sistema operativo mantiene una lista de los ID de los procesos así como de los estados correspondientes, y utiliza esta información para asignar y administrar los recursos del sistema, también mantiene una lista de la memoria ocupada por los procesos y de la que está disponible (administrador de memoria), d) cuando el sistema operativo agrega la información apropiada en las estructuras de datos del núcleo (kernel) y asigna los recursos necesarios para ejecutar el código del programa , éste se convierte entonces en un proceso. Sistema Operativo de red. Es la configuración en la cual existe una red de máquinas de aplicación, generalmente puestos de trabajo (workstations) monousuario y una o más máquinas “servidoras”. Los servidores ofrecen servicios de red o aplicaciones, como almacenamiento de archivos y gestión de impresoras. Cada computadora posee su propio sistema operativo. El sistema operativo de red es simplemente un añadido al sistema operativo local que permite a las máquinas de aplicación interactuar con los servidores. El usuario siempre esta consciente de que existen múltiples computadoras independientes y que opera con ellas explícitamente. Sistema operativo distribuido. Es un sistema operativo común compartido por una red de computadoras. Aparece ante los usuarios como un sistema operativo centralizado ordinario pero que ofrece al usuario un acceso transparente a los recursos de un conjunto de máquinas. Un sistema operativo distribuido puede descansar sobre una arquitectura de comunicaciones para las funciones básicas de comunicación; es más frecuente que se extraiga un conjunto de las funciones de comunicación y se incorporen al sistema operativo para darle mayor eficacia. 119 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo Sistemas Operativos BIBLIOGRAFÍA [1] Sistemas Operativos Modernos; A. S. Tanenbaum; Pearson; ISBN-10: 6074420467. [2] Sistemas Operativos; William Stallings; Pearson;ISBN-10: 8420544620. [3] Distributed Systems: Concepts and Design; George F. Coulouris, Jean Dollimore; Addison-Wesley; 2 edition; ISBN-10: 0273760599. [4] Distributed Systems, Sape Mullender, Segunda Edición, Addison-Wesley. [5] Distributed Systems: Principles and Paradigms; Andrew S. Tanenbaum; Prentice Hall; 2 edition (October 12, 2006);ISBN-10: 0132392275; ISBN-13: 978-0132392273. [6] Sistemas Operativos; H.M. Deitel; Addison-Wesley; Segunda Edición. [7] UNIX. Distributed Programming; Chris Brown; Prentice-Hall; Primera Edición. [8] UNIX Programación Avanzada; F. M. Márquez; Alfaomega; Segunda Edición. [9] UNIX Programación Práctica; K. A. Robbins, S. Robbins; Prentice Hall; Primera Edición. 120 ________________________________________________________________________________________ M.C. Gabriel Gerónimo Castillo