ESCUELA DE PREPARACIÓN DE OPOSITORES E. P. O. Cl. La Merced, 8 - Bajo A Telf.: 968 24 85 54 30001 MURCIA INF16-SAl16 Sistemas operativos: gestión de procesos. Esquema. , 1 INTRODUCCION 2 2 EL MODELO DE PROCESOS 2 2.1 JERARQUÍAS DE PROCESOS 2 2.2 ESTADOS DE UN PROCESO 3 , 3 IMPLEMENT ACION DE LOS PROCESOS 4 4 COMUNICACIÓN ENTRE PROCESOS (IPC) 5 4.1 SECCIONES CRÍTICAS Y EXCLUSIÓN MUTUA 5 4.2 MECANISMOS DE COMUNICACIÓN 6 4.2.1 Semáforos 6 4.2.2 Monitores 7 4.2.3 Transferenciade mensajes 7 , 5 PLANIFICA ClON DE PROCESOS 8 5.1 PLANIFICACIÓN TIPO ROUND ROBIN 9 5 .2 PLANIFICACJÓN POR PRIORIDAD I O 5.3 COLAS MÚLTIPLES I O 5.4 PRIMERO EL TRABAJO MÁS CORTO 11 5.5 PLANIFICACIÓN GARANTIZADA 12 5.6 POLÍTICA VS. MECANISMO 12 5.7 PLANIFICACIÓN DE DOS NIVELES 12 6 HILOS 13 6.1 MULTIHIL0 13 6.2 FUNCIONALIDAD DE LOS HILOS 15 6.2.1 Cambio de estado de un hilo 15 6.2.2 Sincronización de hilos 15 '7 l.Jl'JI~ 1~ 7.1 PROCESOS ENUNIX 15 7.2 IMPLEMENTACIÓN DE PROCESOS EN UNIX 17 ~ l\11~-I:>~~ 1~ 8 .1 PROCESOS EN MS-DOS 18 8.2 IMPLEMENTACIÓN DE PROCESOS ENMS-DOS 19 9 PROCESOS EN WINDOWS 2000 19 9.1 CONCEPTOSFUNDAMENTALES 19 9.2 PLANIFICACIÓN 21 10 CONCL.USIONES 22 Escuela de Preparación de Opositores E.P.O. v05 INF16- SAI16. Página 2 1 Introducción. El concepto central de cualquier sistema operativo es el proceso, una abstracción de un programa en ejecución. Todas las computadoras modernas hacen varias cosas al mismo tiempo. A la vez que se ejecuta un programa de usuario, una computadora puede leer de un disco e imprimir en una terminal o impresora. En un sistema multiprogramado, la CPU alterna de programa en programa, ejecutando cada uno de ellos por decenas o cientos de milisegundos. Aunque, en sentido estricto, la CPU ejecuta en cierto instante un solo programa, durante un segundo puede trabajar con varios de ellos, lo que da una apariencia de paralelismo. Este paralelismo origina condiciones de competencia y secciones críticas entre los procesos, que se solucionan mediante técnicas como semáforos, monitores, y transferencia de mensajes. Para implementar la alternancia entre los procesos es necesario que un planificador seleccione el proceso que debe ejecutar la CPU. En este tema estudiaremos las principales técnicas para realizar la planificación de procesos. Veremos también como ejemplo la gestión de procesos en UNIX, puesto que tiene un método sencillo pero poderoso para el control de los procesos. A continuación, examinaremos las diferencias existentes entre UNIX, MS-DOS y Windows 2000. 2 El modelo de procesos. En este modelo, todo el software ejecutable de la computadora, incluido el sistema operativo, se organiza en varios procesos. Un proceso es un programa en ejecución, lo que incluye los valores activos del contador, registros y variables del programa. De manera conceptual, cada proceso tiene su propia CPU virtual aunque la realidad es que la verdadera CPU alterna entre los procesos. Esta rápida alternancia se denomina multiprogramación. Si la CPU alterna entre los procesos, la velocidad a la que se ejecuta un proceso no será uniforme y es probable que no se pueda reproducir si los mismos procesos se ejecutan de nuevo. Así, los procesos no deben programarse con hipótesis implícitas acerca del tiempo. Sin embargo, lo normal es que la mayoría de los procesos no sean afectados por la multiprogramación de la CPU o las velocidades relativas de procesos distintos. La idea clave es que un proceso es una actividad de cierto tipo. Tiene un programa, entrada, salida y estado. Un solo procesador puede ser compartido entre varios procesos, con cierto algoritmo de planificación, que se utiliza para determinar cuando detener el trabajo en un proceso y dar servicio a otro distinto. 2.1 Jerarquías deprocesos. Los sistemas operativos que soportan el concepto de proceso deben ofrecer cierta forma de crear todos los procesos necesarios. En los sistemas demasiado sencillos, o en los sistemas diseñados para la ejecución de un solo programa, es posible que todos los procesos que podrían ser necesarios en algún momento puedan estar presentes durante la inicialización del sistema. Sin embargo, en la mayoría de los sistemas, es necesaria una forma de crear y destruir procesos cuando se requiera durante la operación. Escuela de Preparación de Opositores E.P.O. v05 INFl6- SAI16. Página 3 En UNIX, los procesos se crean mediante la llamada al sistema FORK, la cual crea una copia idéntica del proceso que hace la llamada. Después de la llamada FORK, el padre sigue su ejecución, en paralelo con el hijo. Tanto el padre como el hijo pueden dar lugar enton.ces a más hijos, por lo que es posible obtener todo un árbol de procesos, de profundidad arbitraria. En MS-DOS, existe una llamada al sistema que carga un archivo binario dado en la memoria y lo ejecuta como un proceso hijo. En contraste con UNIX, en MS-DOS esta llamada suspende al padre hasta que el hijo ha finalizado su ejecución, de forma que el hijo y el padre no se ejecuten en paralelo. 2.2 Estados de un proceso. Aunque cada proceso es una entidad independiente, con su propio contador de programa y estado interno, es frecuente que los procesos deban interactuar con otros. Un proceso podría generar cierta salida que fuera utilizada por otro. Según las velocidades relativas de los dos procesos, podría ocurrir que el segundo estuviera listo para ser ejecutado, pero que no hubiera datos esperando por él. Debe entonces bloquearse hasta disponer de ciertos datos. Cuando un proceso se bloquea, lo hace porque desde el punto de vista lógico no puede continuar; esto ocurre, por lo general, porque espera ciertos datos que no están disponibles todavía. También es posible que se detenga un proceso que esté listo y se pueda ejecutar, debido a que el sistema operativo ha decidido asignar la CPU a otro proceso. En la figura vemos un diagrama de estados que muestra los estados de un proceso: En e·ecución 4 Bloqueado 1. En ejecución (utiliza la CPU en el instante dado). 2. Listo (ejecutable, se detiene en forma temporal para que se ejecute otro proceso). 3. Bloqueado (no se puede ejecutar debido a la ocurrencia de algún evento externo). Desde el punto de vista lógico, los dos primeros estados son similares. En ambos casos, el proceso desea ejecutarse, sólo que en el segundo caso, no existe CPU disponible para él. El tercer estado es distinto de los otros, puesto que el proceso no se puede ejecutar, incluso aunque la CPU no tenga labores que realizar. Son posibles cuatro transiciones entre estos estados. La transición I ocurre cuando un proceso descubre que no puede continuar. En ciertos sistemas, el proceso debe ejecutar una llamada al sistema, BLOCK, para pasar al estado de bloqueo. Lo más frecuente es que un proceso lea de una tubería o archivo especial y que no existan datos disponibles, por lo que el proceso se bloquea de forma automática. Las transiciones 2 y 3 se deben al planificador del proceso, sin que el proceso sepa de ellas. La transición 2 ocurre cuando el planificador decide que el proceso en ejecución ya ha sido ejecutado el tiempo suficiente y que es hora de que otro proceso tenga tiempo de CPU. La transición 3 ocurre cuando los demás procesos han tenido su parte y es tiempo de que el primer proceso vuelva a ejecutarse. La transición 4 aparece cuando ocurre el evento externo por el que espera un proceso. Si no existe otro proceso en ejecución en ese momento, se Escuela de Preparación de Opositores E.P.O. v05 INF16- SAI16. Página 4 produce la transición 3 y el proceso comienza su ejecución. En caso contrario, tendría que esperar en estado listo, hasta que la CPU esté disponible. En el modelo de procesos, es más fácil pensar qué está ocurriendo dentro del sistema. Algunos de los procesos ejecutan programas que llevan a cabo comandos escritos por un usuario. Otros son parte del sistema y controlan tareas tales como solicitar servicios de archivo o manejar los detalles de ejecución de un disco. Cuando ocurre una interrupción de disco, el sistema toma la decisión de detener la ejecución del proceso activo y ejecutar el proceso del disco bloqueado en espera de dicha interrupción. Así, en vez de pensar en interrupciones, podemos pensar en procesos de usuario, procesos de disco, etc., los cuales se bloquean en espera de que algo ocurra. Cuando se lee un bloque de disco, el proceso que lo espera elimina el bloqueo y queda listo de nuevo para su ejecución. Este punto de vista da lugar al modelo que se muestra en la siguiente figura. Aquí, el nivel inferior del sistema operativo es el planificador, con varios procesos por encima de él. El control de interrupciones y los detalles del inicio y parada de los procesos están ocultos en el planificador, que en realidad es muy pequeño. El resto del sistema operativo queda estructurado en forma de proceso. o 1 ... n-2 n-I Planificador 3 Implementación de los procesos. Para implementar el modelo de procesos, el sistema operativo utiliza una tabla, llamada la tabla de procesos, con un dato por proceso. Este dato contiene la información relativa al estado del proceso, el contador del programa, al puntero a la pila, asignación de memoria, el estado de los archivos abiertos, su información de contabilidad y planificación, así como todos los datos relativos al proceso que deben guardarse cuando el proceso alterna entre los estados en ejecución y listo, de forma que pueda volver a iniciar más adelante como si nunca se hubiera detenido. Aunque los campos exactos contenidos en la tabla de procesos son distintos de sistema en sistema, en general, algunos tienen que ver con la administración del proceso, mientras que otros trabajan con la administración de la memoria y unos más con el sistema de archivos. Veamos ahora la forma en que se mantiene la ilusión de varios procesos secuenciales en una máquina con una sola CPU y varios dispositivos de E/S. A cada clase de dispositivo de E/S se le asocia un vector de interrupción, que contiene la dirección del procedimiento de servicio a las interrupciones. Supongamos que el proceso del usuario 3 está en ejecución cuando ocurre una interrupción del disco. El contador del programa, la palabra de estado del programa y, tal vez uno o más registros son enviados a la pila por el hardware de la interrupción. Es entonces cuando la computadora pasa a la dirección dada por el vector de interrupción de disco. Eso es todo lo que hace el hardware. De aquí en adelante, todo queda en manos del software. El procedimiento de servicio a la interrupción comienza guardando todos los registros en los datos de la tabla de procesos correspondientes al proceso activo. El número de proceso activo y un puntero a este dato se mantienen como variables globales para su rápida localización. Después, la información depositada por la interrupción se elimina de la pila, y el puntero de ésta apunta a una pila temporal, la cual utiliza el controlador del proceso. Escuela de Preparación de Opositores E.P.O. v05 INF 16 - SAI 16. Página 5 El siguiente paso consiste en determinar el proceso que inició la solicitud al disco. Por lo general, este proceso se habrá ido a dormir después de iniciar la solicitud, por lo que deberá ser despertado. El estado de este proceso cambia de bloqueado a listo y se llama al planificador. El hecho de que ese proceso se ejecute a continuación depende del algoritmo de planificación. Sabemos que al menos dos procesos están listos: el proceso que inició la EIS del disco y el que fue interrumpido. La elección depende del planificador. Por ejemplo, en UNIX, un proceso en espera de E/S tiene mayor prioridad que un proceso con restricciones en la CPU, por lo que puede obtener su siguiente solicitud de E/S con rapidez. Esta estrategia maximiza la cantidad de paralelismo, lo cual mantiene ocupados al disco y la CPU. Sin embargo, otros sistemas utilizan distintos esquemas. Para regresar al proceso recién seleccionado, se carga los registros y el mapa de memoria para el proceso que ahora está activo e inicia su ejecución. 4 Comunicación entre procesos (IPC). Para examinar la forma en que la comunicación entre procesos se lleva a cabo en la práctica, consideremos por ejemplo un spooler de impresión. Cuando un proceso desea imprimir un archivo, escribe el nombre del archivo en un directorio spooler particular. Otro proceso, verifica de forma periódica si existen archivos por imprimir y, en caso afirmativo, los imprime para después eliminar sus nombres de dicho directorio. Imaginemos que el directorio spooler tiene un enorme número de entradas, numeradas O, 1, 2, ... , cada una de las cuales puede almacenar el nombre de un archivo. Imaginemos también que existen dos variables compartidas: out, que apunta hacia el siguiente archivo por imprimir, e in, que apunta hacia la siguiente entrada libre dentro del directorio. En cierto instante, las entradas del O al 3 están vacías (los archivos ya se imprimieron) y las entradas del 4 al 6 están ocupadas (con los nombres de los archivos que esperan tumo para la impresión). De forma más o menos simultánea, los procesos A y B deciden colocar un archivo en la cola de impresión. Podría ocurrir lo siguiente: el proceso A lee in y almacena su valor, 7, en una variable local. Entonces ocurre una interrupción del reloj y la CPU decide que el proceso A ya ha estado en ejecución el tiempo suficiente, por lo que alterna con el proceso B. El proceso B también lee in, y también obtiene un 7, por lo que almacena el nombre de su archivo en el espacio 7 y actualiza in como 8. Después sale y hace otras cosas. En cierto momento, el proceso A vuelve a ejecutarse, a partir del momento en que se abandonó. Revisa su variable local y encuentra un valor de 7 y escribe el nombre de archivo en el espacio 7, con lo cual elimina el nombre que el proceso B acaba de colocar. Después da a in el valor de 8. El directorio spooler tiene consistencia interna, por lo que el demonio de impresión no observará nada raro; sin embargo, el proceso B nunca tendrá algún resultado. Las situaciones como ésta, en las que dos o más procesos leen o escriben en ciertos datos compartidos y el resultado final depende de quién ejecuta qué y en qué momento, reciben el nombre de condiciones de competencia. 4.1 Secciones críticasy exclusión mutua. La clave para evitar los problemas en las condiciones de competencia y otras situaciones relacionadas con la memoria compartida, archivos compartidos y cualquier otra cosa compartida, es determinar una forma de prohibir que más de algún proceso lea o escriba en los datos compartidos a la vez. En otras palabras, lo que necesitamos es la Escuela de Preparación de Opositores E.P.O. v05 INF16- SAI16. Página 6 exclusión mutua (una forma de garantizar que si un proceso utiliza una variable o archivo compartidos, los demás procesos no puedan utilizarlos). La parte del programa, en la cual se tiene acceso a memoria compartida se llama sección crítica. Si podemos arreglar las cosas de forma que no ocurra que dos procesos estén al mismo tiempo en su sección critica, podremos evitar las condiciones de competencia. Aunque esta condición evita los conflictos, no es suficiente para que los procesos paralelos cooperen de forma correcta y usen de modo eficaz los datos compartidos. Necesitamos cuatro condiciones para poder obtener una buena solución: 1. Dos procesos no deben encontrarse al mismo tiempo dentro de sus secciones, criticas. 2. No se deben hacer hipótesis sobre la velocidad o el número de CPU. 3. Ninguno de los procesos que estén en ejecución fuera de su sección crítica puede bloquear a otros procesos. 4. Ningún proceso debe esperar eternamente para entrar a su sección critica. 4.2 Mecanismos de comunicación. 4.2.1 Semáforos. Dijkstra sugirió el uso de una variable entera denominada semáforo, y dos operaciones, Py V. La operación P verifica si el valor de un semáforo es mayor que O. En ese caso, decrementa el valor y continúa. Si el valor es O, el proceso se va a dormir. La verificación y modificación del valor, así como la posibilidad de irse a dormir se realiza en conjunto, como una sola e indivisible acción atómica. Se garantiza que al iniciar una operación con un semáforo, ningún otro proceso puede tener acceso al semáforo hasta que la operación termine o se bloquee. Esta atomicidad es absolutamente esencial para resolver los problemas de sincronización y evitar condiciones de competencia. La operación V incrementa el valor del semáforo correspondiente. Si uno o más procesos dormían en ese semáforo y no podían completar una operación P anterior, el sistema elige alguno de ellos y se le permite terminar P. Así, después de un V en un semáforo con procesos durmiendo, el semáforo seguirá con valor O, pero habrá un menor número de procesos durmiendo. La operación de incremento del semáforo y despertar de un proceso también es indivisible. Ningún proceso llega a bloquear mediante una operación V. En un sistema que utilice semáforos, la forma natural de esconder a las interrupciones es tener un semáforo, con valor inicial de O, asociado a cada dispositivo de E/S. Justo después de iniciar un dispositivo, el proceso de administración ejecuta P en el semáforo asociado, con lo cual lo bloquea de forma inmediata. Cuando ocurre la interrupción, el controlador de ésta ejecuta V en el semáforo asociado, lo que provoca que el proceso relevante esté listo para reanudar su ejecución. Por supuesto, si están listos varios procesos, el planificador deberá optar por ejecutar a continuación un proceso más importante. Escuela de Preparación de Opositores E.P .O. v05 INFl 6 - SAI 16. Página 7 4.2.2 Monitores. Implementar la comunicación entre procesos con semáforos es complicado. Un pequeño error y todo se vendría abajo, puesto que los errores son condiciones de competencia, bloqueos y otras formas de comportamiento impredecible e irreproducible. Para facilitar la escritura de programas correctos, existe una primitiva de sincronización de alto nivel, llamada monitor. Un monitor es una colección de procedimientos, variables y estructuras de datos que se agrupan, en cierto tipo particular de módulo o paquete. Los procesos pueden llamar a los procedimientos de un monitor cuando lo deseen, pero no tienen acceso directo a las estructuras de datos internas del monitor desde los procedimientos declarados fuera de él. Sólo uno de Ios procesos puede estar activo en un monitor en cada momento. Por lo general, cuando un proceso llama a un procedimiento de monitor, las primeras instrucciones de éste verificarán si hay otro proceso activo dentro del monitor. En caso afirmativo, el proceso quedará bloqueado hasta que el otro proceso salga del monitor. Si no hay otro proceso que esté utilizando el monitor, el que hace la llamada podrá entrar. El compilador tiene la tarea de implantar la exclusión mutua sobre los datos del monitor, pero una forma usual de conseguir esto es mediante un semáforo binario. Puesto que es el compilador, y no el programador, el que ordena las cosas para la exclusión mutua, es menos probable que ocurra algún error. 4.2.3 Transferencia de mensajes. Este método de comunicación entre procesos utiliza dos primitivas, SEND y RECEIVE, las cuales, al igual que los semáforos, son llamadas al sistema. Como tales, se pueden colocar con facilidad en procedimientos de librería, como por ejemplo, send(destino,&mensaje) y receive(fuente,&mensaje). EI primer procedimiento envía un mensaje a un destino dado y el segundo recibe un mensaje desde cierto origen (o desde cualquier origen, si al receptor no le importa este punto). Si no hay mensajes disponibles, el receptor se puede bloquear hasta que llegue alguno. Los sistemas con transferencia de mensajes pueden tener grandes retos y aspectos de diseño que no surgen en los casos de semáforos, en particular si los procesos en comunicación se encuentran en máquinas distintas unidas mediante una red. Por ejemplo, los mensajes se pueden perder en la red. Como protección contra la pérdida de mensajes, el emisor y el receptor pueden convenir en que tan pronto se reciba el mensaje, el receptor envíe un mensaje especial de confirmación. Si el emisor no ha recibido una confirmación después de cierto tiempo, retransmite el mensaje. Consideremos lo que ocurre si el propio mensaje se recibe de forma correcta, pero la confirmación se pierde. El emisor retransmitirá el mensaje, de forma que el receptor lo tendrá duplicado. Es esencial que el receptor pueda distinguir entre un nuevo mensaje y la retransmisión de uno anterior. Por lo general, este problema se resuelve con números consecutivos en cada mensaje original. Si el receptor obtiene un mensaje con el mismo número de secuencia que el mensaje anterior, determinará que el mensaje es un duplicado que puede ignorarse. La autenticación es otro aspecto de los sistemas con mensajes. En este punto, puede ser de utilidad el cifrado de mensajes con una clave que sólo conozcan los usuarios autorizados. Una forma de establecer las direcciones de los mensajes consiste en asignar a cada proceso una dirección única y que las direcciones de los mensajes estén ligadas a Escuela de Preparación de Opositores E.P.O. v05 INF16- SAI16. Página 8 procesos. Otra alternativa es inventar una nueva estructura de datos, llamada buzón. Un buzón es un lugar donde almacenar un número determinado de mensajes, los cuales se especifican al crear el buzón. Al utilizar los buzones, los parámetros de dirección en las llamadas SEND y RECEIVE son buzones, no procesos. Cuando un proceso intente enviar un mensaje a un buzón completamente ocupado, se suspende hasta que se elimina un mensaje de dicho buzón. El caso opuesto al uso de buzones es la eliminación del almacenamiento. Desde este punto de vista, si se ejecuta SEND antes de RECEIVE, el proceso emisor se bloquea hasta la ejecución de RECEIVE, momento en que el mensaje se puede copiar de forma directa del emisor al receptor sin almacenamiento intermedio. De forma análoga si se ejecuta primero RECEIVE, el receptor se bloquea hasta que se ejecute un SEND. Esta estrategia se conoce como rendezvous. Es más fácil de implementar que el esquema de mensajes almacenados; pero es menos flexible, puesto que el emisor y receptor se ven forzados a ejecutarse al mismo paso. La comunicación entre procesos del usuario en UNIX se lleva a cabo mediante tuberías opipes, que en realidad son buzones. La única diferencia real entre un sistema de mensajes con buzones y el mecanismo de tuberías es que éstos no preservan las fronteras de los mensajes. 5 Planificación de procesos. Cuando más de un proceso es ejecutable, el sistema operativo debe decidir cuál de ellos debe ejecutarse. La parte del sistema operativo que lleva a cabo esa decisión se llama planificador y el algoritmo que utiliza algoritmo de planificación. En los sistemas multiusuario de tiempo compartido existen varios usuarios en espera de servicio y pueden existir también otros trabajos para ser procesados en lote. Incluso en el caso de los sistemas puros de tiempo compartido existen con frecuencia trabajos colaterales, como el sistema de correo electrónico, que a menudo se ejecuta todo el tiempo para enviar o recibir correo o noticias. Antes de analizar algoritmos de planificación específicos, debemos pensar en lo que el planificador intenta conseguir. Algunas de las posibilidades más obvias son: 1. Equidad: garantizar que cada proceso obtiene su proporción justa de CPU. 2. Eficacia: mantener ocupada la CPU el 100% del tiempo. 3. Tiempo de respuesta: minimizar el tiempo de respuesta para los usuarios interactivos. 4. Tiempo de regreso: minimizar el tiempo que deben esperar los usuarios por lotes para obtener sus resultados 5. Rendimiento: maximizar el número de tareas procesadas por hora. Algunas de estas metas son contradictorias. Por ejemplo, para minimizar el tiempo de respuesta para los usuarios interactivos, el planificador no debería jamás ejecutar las tareas de procesamiento por lotes. Es probable que a los usuarios por lotes no les guste este algoritmo; esto viola el criterio 4. Se puede demostrar que cualquier algoritmo de planificación que favorezca algún tipo de tareas afecta a otro. Después de todo, la cantidad de tiempo disponible en CPU es finita. Para darle más a un usuario hay que darle menos a otro. Escuela de Preparación de Opositores E.P.O. v05 INF16- SAI16. Página 9 Una complicación a la que se deben enfrentar los planificadores es que cada proceso es único e impredecible. Algunos de los procesos utilizan una gran cantidad de tiempo en espera del archivo de E/S, mientras que otros utilizan la CPU durante varias horas consecutivas si tienen la oportunidad. Cuando el planificador comienza a ejecutar algún proceso, nunca sabe a ciencia cierta cuánto tiempo transcurrirá hasta que el proceso se bloquee, ya sea para E/S, o debido a un semáforo, o por alguna otra razón. Para garantizar que ningún proceso se ejecute un tiempo excesivo, casi todas las computadoras tienen un cronómetro electrónico o un reloj incluido, que provoca una interrupción de forma periódica. Una frecuencia de 50 a 60 veces un segundo (50 ó 60 Hz) es la común, pero en muchas de las computadoras el sistema operativo puede establecer la frecuencia del cronómetro en cualquier valor determinado. En cada interrupción del reloj, el sistema operativo logra ejecutarse y decidir si el proceso que se ejecuta en ese momento tiene permiso de continuar o si tiene el tiempo suficiente en la CPU por el momento, para después suspenderlo para que otro proceso utilice la CPU. La estrategia de permitir que procesos ejecutables sean suspendidos temporalmente se llama planificación apropiativa, en contraste, con el método de ejecución hasta terminar, que recibe el nombre de planificación no apropiativa. Un proceso se puede suspender en cualquier instante, sin advertencia, de forma que se pueda ejecutar otro proceso. Esto conduce a condiciones de competencia y requiere de semáforos, mensajes, o cualquier otro método sofisticado para evitar esto. Así, aunque los algoritmos de planificación no apropiativa son sencillos y fáciles de implementar, por lo general, no son adecuados para los sistemas de propósito general con varios usuarios en competencia. Por otro lado, para un sistema delicado, como por ejemplo un sistema de base de datos, sería razonable que el proceso maestro iniciara un proceso hijo que trabaje con base a una solicitud y que se ejecute hasta que termine. La diferencia con el sistema de propósito general es que todos los procesos del sistema de base de datos están bajo un solo control maestro, el cual sabe lo que va a hacer cada hijo y el tiempo que invertirá en dicha tarea. 5.1 Planificación tipo round robin Uno de los algoritmos de planificación más antiguos, sencillo, justo y de uso más amplio es round robin. Cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado quantum. Si el proceso continúa en ejecución al final de su quantum, otro proceso se apropia de la CPU. Si el proceso está bloqueado o ha terminado antes de consumir su quantum, se alterna el uso de la CPU. Round robin es muy fácil de implementar. Todo lo que necesita el planificador es mantener una lista de procesos ejecutables. Cuando el quantum de un proceso se consume, se le coloca al final de la lista. El único aspecto interesante de round robin es la longitud del quantum. La alternancia entre un proceso y otro necesita cierta cantidad de tiempo para administración (resguardo y carga de registros y mapas de memoria, actualización de varias tablas y, listas, etc.). Si el quantum es muy corto, se alternan demasiados procesos, lo que reduce la eficacia de la CPU; pero si es muy largo, puede causar una respuesta lenta a las solicitudes interactivas breves. Un quantum cercano a 1 OO mseg es con frecuencia un compromiso razonable. Escuela de Preparación de Opositores E.P.O. v05 INF16-SAI16. Página 10 5.2 Planificación porprioridad. Una hipótesis implícita de la planificación round robin es que todos los procesos tienen la misma importancia. La necesidad de tomar en cuenta los factores externos lleva a la planificación por prioridades. La idea fundamental es directa: cada proceso tiene asociada una prioridad y el proceso ejecutable con máxima prioridad es el que tiene el permiso de ejecución. Para evitar que los procesos de alta prioridad se ejecuten indefinidamente, el planificador puede disminuir la prioridad del proceso en ejecución en cada instante (en cada interrupción del reloj). Si esto hace que su prioridad sea menor que el siguiente proceso con alta prioridad, se alternan los procesos. Se pueden asignar prioridades de forma estática. El sistema UNIX tiene un comando, nice, que permite a un usuario reducir de forma voluntaria la prioridad de su proceso. Las prioridades también pueden ser asignadas de forma dinámica por el sistema con el fin de lograr ciertas metas del mismo. Por ejemplo, ciertos procesos tienen grandes limitaciones de E/S y ocupan la mayor parte de su tiempo en espera de ellas. Cada vez que uno de esos procesos desee utilizar la CPU, se le debe asignar la CPU inmediatamente, para que pueda iniciar su siguiente solicitud de E/S, la cual puede desarrollarse en paralelo con otro proceso que realice labores de cómputo. Si el proceso limitado de E/S espera demasiado tiempo a la CPU, lo que ocurre es que está ocupando memoria por un tiempo innecesario. Un algoritmo sencillo que le da un buen servicio a los procesos con limitaciones en la E/S es establecer que la prioridad sea VJ, donde fes la fracción del último quantum utilizado por el proceso. Un proceso que sólo utilice 2 mseg su quantum de 100 mseg tendrá prioridad 50, mientras que un proceso que se ejecutó 50 mseg antes del bloqueo tendría prioridad 2; un proceso que utilice todo el quantum tendría prioridad I. Con frecuencia, es conveniente agrupar los procesos en clases de prioridad y utilizar la planificación con prioridades entre las clases, pero con round robin dentro de cada clase. 5.3 Colas múltiples. Uno .de los primeros planificadores con prioridad era el de CTSS. CTSS tenía el problema de que la alternancia entre procesos era muy lenta. Los diseñadores de CTSS se dieron cuenta de que era más eficaz dar de una vez a los procesos con limitaciones de CPU un quantum más grande, que darles pequeños quantum con frecuencia. Por otro lado, si se les daba a los procesos un quantum muy grande se tendría un tiempo de respuesta pobre, como ya hemos visto. La solución fue el establecimiento de clases de prioridad. Los procesos en la clase de mayor prioridad se ejecutaban en un quantum. Los procesos de la siguiente clase se ejecutaban en dos quantum, los de la siguiente clase en cuatro quantum, etc. Cuando un proceso consumiera todos los quantum asignados a él, se le movía a la siguiente clase. Se adoptó la siguiente política para evitar que un proceso que requería una ejecución larga al iniciar, pero que posteriormente funcionara de forma interactiva, fuera penalizado para siempre. Siempre que se tecleara la tecla Enter, el proceso asociado pasaba a la clase de máxima prioridad partiendo de la hipótesis de que se convertía en interactivo. Cierto día, algún usuario con un proceso con serias limitaciones de uso de la CPU, descubrió que tras escribir retornos de carro de forma aleatoria durante varios segundos mejoró su tiempo de respuesta. Escuela de Preparación de Opositores E.P.O. v05 INF16 - SAI 16. Página 11 Se han utilizado muchos algoritmos para la asignación de procesos a clase de prioridad. Por ejemplo, el XDS 940, sistema construido en Berkeley y que ejerció una gran influencia, tenía cuatro clases de prioridad, llamadas terminal, E/S, quantum corto y quantum largo. Cuando un proceso en espera de una entrada de terminal despertaba, pasaba a la clase de máxima prioridad (terminal). Cuando un proceso en espera de un bloque de disco estuviera listo, pasaba a la segunda clase. Cuando un proceso en ejecución agotaba su quantum, se le colocaba en primera instancia en la tercera clase. Sin embargo, si un proceso agotaba su quantum demasiadas veces seguidas sin bloqueo de terminal o E/S, pasaba a la cola inferior. Muchos otros sistemas utilizan algo similar para favorecer a los usuarios interactivos. 5.4 Primero el trabajo más corto. Es un algoritmo más apropiado para las tareas por lotes, en las cuales los tiempos de ejecución se conocen de antemano. Cuando varios trabajos de igual importancia esperan en la lista de entrada para iniciar, el planificador deberá utilizar el criterio de ejecutar primero el trabajo más corto. Por ejemplo, cuatro tareas A, B, Cy D, cuyos tiempos de ejecución son de 8, 4, 4 y 4 minutos respectivamente. Al ejecutarlos en ese orden, el tiempo de regreso para A es 8 minutos, para B es 12 minutos, para C es 16 minutos y para D es 20 minutos, con un promedio de 14 minutos. Consideremos ahora la ejecución del trabajo más corto en primer lugar. Los tiempos de regreso son ahora 4, 8, 12 y 20 minutos con un promedio de 11 minutos. Se puede demostrar que este algoritmo es el óptimo. Puesto que el algoritmo de primero el trabajo más corto produce el promedio mínimo de tiempo de respuesta, sería bueno poderlo usar también para los procesos interactivos. Los procesos interactivos siguen, por lo general, el patrón de espera de comando, ejecución de comando, espera, ejecución, etc. Si consideramos la ejecución de cada comando como una "tarea" independiente, entonces podríamos minimizar el tiempo general de respuesta, al ejecutar en primer lugar el más corto. El único problema es poder imaginar cuál de los procesos en ejecución sería el más corto. Una forma de analizar este problema es hacer estimaciones del comportamiento pasado y ejecutar el proceso con el menor tiempo estimado. Supongamos que el tiempo estimado por comando, en cierta terminal, es To. Supongamos que el tiempo medido de la siguiente ejecución es T1. Podemos actualizar la estimación mediante una suma de estos números, cada uno con un cierto peso; es decir, aTo+(l-a)T1. Por medio de a podemos decidir si queremos que la estimación olvide con rapidez las ejecuciones anteriores o que las recuerde por un largo tiempo. La técnica de estimación del siguiente valor mediante una serie tomando el promedio con pesos del valor actual y la estimación anterior se conoce a veces como maduración (aging). Se puede aplicar a muchas situaciones, en las que hay que hacer una predicción con base en los valores anteriores. Este método es particularmente fácil de implementar cuando a=1/2. Todo lo que hay que hacer es añadir el nuevo valor a la estimación actual y dividir la suma entre 2 (desplazando el número a la derecha 1 bit). Es importante recalcar que el algoritmo sólo es óptimo cuando se dispone de todas las tareas de forma simultánea. Como contraejemplo, consideremos cinco tareas, desde A hasta E, con tiempos de ejecución de 2, 4, 1, 1 y 1 respectivamente. Sus tiempos de llegada son O, O, 3, 3 y 3. Primero se dispone de A y B, puesto que las demás tareas no han llegado todavía. Con el algoritmo, las ejecutaríamos en orden A, B, C, D, Escuela de Preparación de Opositores E.P.O. v05 INF16- SAI 16. Página 12 y E, con una espera promedio de 4'6. Sin embargo, al ejecutarlas en orden B, C, D, E y A se tiene un promedio de espera de 4'4. 5.5 Planificación garantizada. Un punto de vista totalmente distinto de la planificación es establecer verdaderos compromisos de rendimiento con el usuario y sujetarse a ellos. Una promesa fácil de cumplir y de sujetarse a ella es: si existen n usuarios dentro del sistema, cada usuario recibirá cerca de lin de la potencia de la CPU. Para mantener esa promesa, el sistema debe tener un registro del tiempo de CPU que cada usuario ha tenido desde su entrada al sistema, así como del tiempo transcurrido desde esa entrada. Calcula entonces la cantidad de tiempo en CPU prometida al usuario, es decir, el tiempo transcurrido desde la entrada, dividido entre n. Puesto que también se conoce la cantidad de tiempo en CPU realmente utilizada por el usuario, mediante un cálculo directo se obtiene la proporción del tiempo de CPU real entre el tiempo de CPU prometido. Una proporción de 0'5 indica que un proceso sólo ha dispuesto de la mitad del tiempo debido, mientras que una proporción de 2 indica que un proceso ha utilizado el doble de lo que debería. El algoritmo ejecuta entonces proceso con la menor proporción, hasta que ésta se acerque a la de su competidor más cercano. Una idea análoga es aplicable a los sistemas de tiempo real, en los que existen plazos absolutos por cumplir. En este caso, hay que fijarse en los procesos con mayor peligro o que esté por expirar su plazo y ejecutarlos. Un proceso que deba concluir en 1 O segundos tiene mayor prioridad que uno que deba terminar en 1 O minutos. 5.6 Política vs. mecanismo. Hasta ahora, hemos supuesto en forma tácita que todos los procesos en el sistema pertenecen a diversos usuarios y que, por tanto, compiten por la CPU. Sin embargo, a veces ocurre que un proceso tiene muchos hijos ejecutándose bajo su control. Es completamente posible que el proceso principal tenga una idea excelente de cuáles de sus hijos son los más importantes (o críticos respecto al tiempo) y cuáles menos. Ninguno de los planificadores analizados antes acepta datos de los procesos del usuario relativos a decisiones de planificación. Como resultado, el planificador pocas veces hace la mejor elección. La solución a este problema es separar el mecanismo de planificación de la política de planificación. Es decir, el algoritmo de planificación queda parametrizado de alguna manera, pero los parámetros pueden ser determinados por medio de procesos del usuario. De esta forma, el padre puede controlar con detalle la forma de planificar sus hijos, incluso aunque él mismo no realice la planificación. En este caso, el mecanismo está en el núcleo pero la política queda establecida por un proceso del usuario. 5. 7 Planificación de dos niveles. Hasta ahora, hemos supuesto de alguna manera que todos los procesos ejecutables se encuentran en la memoria principal. Si no se dispone de suficiente memoria principal, será necesario que algunos de los procesos ejecutables se mantengan en el disco. Esta situación tiene importantes implicaciones para la planificación, puesto que el tiempo de alternancia entre procesos para traer y procesar un proceso del disco es considerablemente mayor que el tiempo para un proceso que ya se encuentra en la memoria principal. Escuela de Preparación de Opositores E.P.O. v05 INFl6- SAI16. Página 13 Una forma más práctica de trabajar con el intercambio de los procesos es por medio de un planificador de dos niveles. Primero se carga en la memoria principal cierto subconjunto de los procesos ejecutables. El planificador se restringe entonces a ese subconjunto durante cierto tiempo. De forma periódica, se llama a un planificador de nivel superior para eliminar de la memoria los procesos que hayan permanecido en ella el tiempo suficiente y cargar a memoria los procesos que hayan estado en disco demasiado tiempo. Una vez hecho el cambio, el planificador de nivel inferior se restringe de nuevo a los procesos ejecutables que se encuentren en la memoria. Así, el planificador de nivel inferior se encarga de elegir de entre los procesos ejecutables que están en memoria en ese momento, mientras que el planificador de nivel superior se encarga de desplazar los procesos de memoria a disco y viceversa. Entre los criterios que podría utilizar el planificador de nivel superior para tomar sus decisiones están: 1. ¿Cuánto tiempo ha transcurrido desde el último intercambio del proceso? 2. ¿Cuánto tiempo de CPU ha utilizado recientemente el proceso? 3. ¿Cómo de grande es el proceso? (Los procesos pequeños no causan problemas) 4. ¿Cuál es la prioridad del proceso? Aquí podríamos utilizar de nuevo round robin, planificación por prioridad o cualquiera de los demás métodos. 6 Hilos. El concepto de proceso es más complejo que lo presentado hasta el momento e incluye dos conceptos distintos: uno relacionado con la propiedad de recursos y otro relacionado con la ejecución. Esta distinción ha llevado, en algunos sistemas operativos, al desarrollo de un constructor llamado hilo (thread). Hasta ahora, hemos presentado el concepto de proceso incluyendo: • Unidad de propiedad de los recursos: Un proceso incluye un espacio de direcciones virtuales para mantener la imagen del proceso y, de cuando en cuando, al proceso se le puede asignar el control o la propiedad de recursos tales como la memoria principal, canales de EIS, dispositivos de E/S y archivos. • Unidad de expedición: La ejecución de un proceso sigue un 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 y una prioridad; y además es la unidad planificada y expedida por el sistema operativo. Para distinguir estas dos características, la unidad de expedición se conoce como hilo o proceso ligero (lightweight process), mientras que a la unidad de propiedad de los recursos se le suele llamar proceso o tarea. 6.1 Multihilo. El término multihilo hace referencia a la capacidad de un sistema operativo para mantener varios hilos de ejecución dentro de un mismo proceso. El enfoque tradicional con un solo hilo de ejecución por proceso se denomina técnica monohilo. Un ejemplo Escuela de Preparación de Opositores E.P .O. v05 INF 16 - SAil 6. Página 14 de sistema operativo que soporta un solo proceso de usuario y un solo hilo es MS-DOS. Otros sistemas operativos, corno algunas de las versiones de UNIX, soportan múltiples procesos de usuario, pero sólo un hilo por proceso. Sistemas operativos con múltiples procesos, cada uno de ellos formado por múltiples hilos, son Windows 2000, Solaris y Linux entre otros. En un entorno rnultihilo, un proceso se define corno la unidad de protección y unidad de asignación de recursos. A los procesos se les asocian: • Un espacio de direcciones virtuales, que contiene la imagen del proceso . • Acceso protegido a los procesadores, otros procesos (para la comunicación entre procesos), archivos y recursos de E/S (dispositivos y canales). En un proceso puede haber uno o más hilos, cada uno con: • El estado del hilo. • El contexto del procesador, que se salva cuando no está ejecutando; una forma de ver el hilo es corno un contador de programa independiente operando dentro de un proceso. • Una pila de ejecucion. • Almacenamiento estático para las variables locales. • Acceso a la memoria y a los recursos del proceso, compartidos con todos los otros hilos del mismo. En un modelo de proceso monohilo la representación de un proceso incluye su bloque de control de proceso y un espacio de direcciones de usuario, así como las pilas de usuario y núcleo para gestionar la secuencia de llamadas/retornos durante la ejecución del proceso. Mientras se está ejecutando un proceso, los registros del procesador están controlados por ese proceso y, cuando el proceso no se está ejecutando, se salva el contenido de esos registros. En un entorno multihilo continúa existiendo un solo bloque de control de proceso y un espacio de direcciones de usuario asociados al proceso, pero ahora hay pilas separadas para cada hilo, así como distintos bloques de control para cada hilo, que contienen los valores de los registros, prioridad y otras informaciones relativas al estado de los hilos. Así pues, todos los hilos de un proceso comparten el estado y los recursos del proceso. Residen en el mismo espacio de direcciones y tienen acceso a los mismos datos. Cuando un hilo modifica un dato en memoria, los otros hilos utilizan el resultado cuando acceden al dato. Si un hilo abre un archivo con permisos de lectura, el resto de los hilos del mismo proceso también pueden leer de él. Los beneficios de los hilos se derivan del rendimiento: 1. Se tarda mucho menos tiempo en crear un nuevo hilo en un proceso existente que en crear un nuevo proceso. 2. Se tarda mucho menos tiempo en terminar un hilo que un proceso. 3. Se tarda mucho menos tiempo en cambiar entre dos hilos de un mismo proceso. 4. Los hilos aumentan la eficiencia de Ia comunicación entre programas en ejecución. En la mayoría de los sistemas operativos, la comunicación entre procesos independientes requiere la intervención del núcleo para ofrecer Escuela de Preparación de Opositores E.P.O. v05 INF16- SAil6. Página 15 protección y para proporcionar los mecanismos necesarios para la comunicación. Sin embargo, puesto que los hilos de un mismo proceso comparten memoria y archivos, pueden comunicarse entre sí sin invocar al núcleo. Por lo tanto, si hay una aplicación o una función que pueda implementarse como un conjunto de unidades de ejecución relacionadas, es más eficiente hacerlo con una colección de hilos que con una colección de procesos separados. La planificación se lleva a cabo con los hilos; por lo tanto, la mayor parte de la información de estado relacionada con la ejecución se mantiene en estructuras de datos de los hilos. Sin embargo, hay varias acciones que afectan a todos lo hilos de un proceso y que el sistema operativo debe gestionar con los procesos. Por ejemplo, la terminación de un proceso supone terminar con todos los hilos dentro de dicho proceso. 6.2 Funcionalidad de los hilos. Al igual que los procesos, los hilos poseen un estado de ejecución y pueden sincronizarse entre ellos. Estudiaremos estos dos aspectos de la funcionalidad de los hilos en orden. 6.2.1 Cambio de estado de un hilo. Hay cuatro operaciones básicas relacionadas con el cambio de estado en hilos: • Creación: normalmente, cuando se crea un nuevo proceso, también se crea un hilo para ese proceso. Posteriormente, un hilo de un proceso puede crear otros hilos dentro del mismo proceso, proporcionando un puntero de instrucción y los argumentos del nuevo hilo. El nuevo hilo tendrá su propio contexto y su propio espacio de pila, y pasará al estado listo. • Bloqueo: cuando un hilo necesita esperar por un suceso, se bloquea (salvando sus registros de usuario, contador de programa y punteros de pila). Ahora, el procesador podrá pasar a ejecutar otro hilo listo. • Desbloqueo: cuando se produce el suceso por el que un hilo se bloqueó, el hilo pasa a listo. • Terminación: cuando un hilo finaliza, se libera su contexto y sus pilas. 6.2.2 Sincronización de hilos. Todos los hilos de un proceso comparten el mismo espacio de direcciones y otros recursos, corno los archivos abiertos. Cualquier modificación de un recurso desde un hilo afecta al entorno del resto de los hilos del mismo proceso. Por lo tanto, es necesario sincronizar la actividad de los distintos hilos para que no interfieran unos con otros. Las técnicas empleadas en la sincronización de hilos son, en general, las mismas que para la sincronización de procesos. 7 UNIX. 7.1 Procesos en UNIX Las entidades activas en UNIX son los procesos. Cada proceso ejecuta un solo programa y tiene un único hilo de control. En otras palabras, tiene un contador de programa, el cual mantiene un registro de la siguiente instrucción por ejecutar. Escuela de Preparación de Opositores E.P .O. v05 INF16- SAI16. Página 16 UNIX es un sistema multiprogramado, por lo que se pueden ejecutar varios procesos independientes al mismo tiempo. Cada usuario puede tener varios procesos activos a la vez, por lo que pueden existir cientos o incluso miles de procesos en . . ' eJeCUClOn. Los procesos en UNIX se crean mediante la llamada al sistema FORK que crea una copia exacta del proceso original. El proceso original recibe entonces el nombre de proceso padre. El nuevo proceso se llama proceso hijo. El padre y el hijo tienen sus propias imágenes privadas en la memoria. Si el padre cambia más adelante algunas de sus variables, los cambios no son visibles para el hijo y viceversa. Los archivos abiertos se comparten entre el padre y el hijo. Es decir, si cierto archivo es abierto por el padre antes de FORK, continuará abierto tanto en el padre como en el hijo después de FORK. Los cambios hechos en el archivo por cualquiera de ellos serán visibles para el otro. Los procesos se nombran mediante su PID que puede utilizarse de varias formas. Por ejemplo, al terminar un hijo, el padre obtiene el PID del hijo que ha concluido. Esto puede ser importante, puesto que un padre puede tener muchos hijos. Puesto que los hijos también pueden tener hijos, un proceso original puede tener un árbol completo de hijos, nietos y otros descendientes. Esta habilidad para crear un árbol de procesos es la clave del funcionamiento del tiempo compartido en UNIX. Al arrancar el sistema, el núcleo crea un proceso llamado init. Este proceso lee un archivo /etc/ttys para indicar el número de terminales de que dispone el sistema y proporciona cierta información que describe a cada uno, init inicia entonces un proceso hijo para cada terminal y se bloquea hasta que uno de los hijos termina. Cada hijo ejecuta el programa login, el cual intenta leer el nombre del usuario del teclado. Cuando alguien se sienta frente al terminal y proporciona un nombre de entrada, login pregunta entonces una contraseña, la cifra y la verifica con la contraseña cifrada almacenada en el archivo de contraseñas /etc/password. Si es correcta, login se cubre a sí mismo con el shell del usuario, el cual espera entonces el primer comando. Si es incorrecto, login sólo pide otro nombre de usuario. Los procesos en UNIX se pueden comunicar entre sí mediante una forma de transferencia de mensajes. Es posible crear un canal entre dos procesos en el que un proceso pueda escribir un flujo de bytes para que el otro lo lea. Estos canales se llaman tuberías. Es posible la sincronización, puesto que cuando un proceso intenta leer de una tubería vacía se bloquea hasta disponer de los datos. Los procesos también se pueden comunicar mediante interrupciones software. Un proceso puede enviar lo que se conoce como una señal a otro proceso. Los procesos pueden indicar al sistema lo que desean que ocurra al llegar una señal. Las opciones son ignorarla, atraparla, o dejar que la señal aniquile al proceso (valor predefinido). Si un proceso opta por atrapar las señales enviadas a él, debe especificar un procedimiento para el manejo de las señales. Al llegar una señal, el control pasa de manera abrupta al manejador. Cuando el manejador termina, devuelve el control de donde vino, de forma análoga a las interrupciones de E/S del hardware. Cada usuario se identifica mediante un entero llamado UID (identificación del usuario) contenido en el archivo de contraseñas. Estas son asignadas por el administrador del sistema. Cada proceso adquiere de forma automática la UID de la persona que lo creó. Escuela de Preparación de Opositores E.P.O. v05 INF16-SAI16. Página 17 El usuario con UID O es especial y se llama el superusuario (o root). Tiene el poder de leer y escribir en todos los archivos del sistema. Los procesos con UID O también tienen la capacidad de hacer un pequeño número de llamadas al sistema protegidas, negadas a los usuarios ordinarios. El poder del superusuario se explota de forma inteligente, para permitir a los usuarios que realicen cosas que podrían ser peligrosas de modo controlado. Por ejemplo, muchos sistemas UNIX tienen programas que permiten a los usuarios preguntar por el espacio libre en el disco. Esta información se almacena en el bloque O de cada disco, pero lo usual es que los discos estén protegidos de forma que los usuarios comunes sólo lean los bytes sin poder interpretar la información. UNIX tiene un bit asociado con cada programa ejecutable, llamado SETUID. Este bit es parte de la palabra del modo de protección (la parte de protección sólo utiliza 9 bits, por lo que sobran algunos para otros fines). Cuando se ejecuta un programa con el bit SETUID activo, el UID efectivo de ese proceso se convierte en el UID del propietario del archivo ejecutable, en vez del UID del usuario que lo llamó. Al hacer que el programa que informa del espacio en disco sea poseído por el superusuario, pero con el bit SETUID activado, cualquier, usuario lo puede ejecutar y obtener los privilegios del superusuario sólo para ese proceso. De esta forma, es posible que el superusuario ponga a disposición de los usuarios comunes un conjunto de programas que hacen uso del poder del superusuario de forma controlada y limitada. La ejecución del programa que informa del espacio en disco permite a todos que tengan un proceso del superusuario, pero no permite que el usuario lea archivos protegidos, puesto que esa no es una de las opciones que ofrece el informador del espacio en disco. Sólo informa del espacio en disco y después termina. El mecanismo UID se utiliza en UNIX para evitar una masa de llamadas al sistema de propósito especial, tales como una que permita a los usuarios leer el bloque O. 7.2 Implementación deprocesos en UNIX Puesto que UNIX es un sistema de tiempo compartido, su algoritmo de planificación está diseñado para dar una buena respuesta a los procesos interactivos. Es un algoritmo de dos niveles. El algoritmo de bajo nivel elige dentro del conjunto de procesos de memoria y listos para ejecutarse el proceso a ejecutar a continuación. Para ello, utiliza varias colas de forma que cada cola está asociada a un valor de prioridad. El algoritmo de alto nivel desplaza los procesos entre la memoria y el disco, de forma que todos los procesos tengan oportunidad en la memoria y ejecutarse. Al ejecutar el planificador (de bajo nivel), éste busca las colas que comienzan en la máxima prioridad, hasta que encuentra una cola con algún proceso. Elige entonces el primer proceso de esa cola y lo inicia. Permite su ejecución durante un máximo de un quantum, que, por lo general, es de I OO mseg o hasta que se bloquea. Un quantum ocupa por lo general de 5 a 6 marcas de reloj. En cada marca del reloj, el contador del uso del CPU, ubicado en la entrada de la tabla de procesos correspondiente al proceso en ejecución, se incrementa en I. Este contador se añade de forma automática a la prioridad del proceso, moviéndolo a una cola de menor prioridad. Si un proceso agota su quantum, se le coloca al final de su cola y se vuelve a ejecutar el algoritmo de planificación. Así, los procesos con igual prioridad comparten CPU con un algoritmo round robin. Cada segundo, se vuelven a calcular las prioridades de los procesos. En primer lugar, se dividen entre 2 los contadores de uso de CPU de forma que los procesos no Escuela de Preparación de Opositores E.P.O. v05 INF16- SAI16. Página 18 tengan un castigo eterno por un uso anterior de la CPU. Después se calcula la prioridad de cada proceso según la fórmula nueva prioridad = base + uso de la CPU. Por lo general, la base es O, pero un usuario que prefiera un servicio peor que el normal puede usar aquí un valor positivo mediante la llamada al sistema NICE. Sólo el superusuario podría pedir un servicio mejor que el normal. 8 MS-DOS. 8.1 Procesos en MS-DOS. MS-DOS no es un sistema multiprogramado como UNIX y no puede soportar varios procesos independientes en ejecución simultánea en la misma máquina. Por otro lado, tampoco es un sistema monoprogramado. Es algo intermedio. Al arrancar el sistema, un proceso, command.com se inicia y espera una entrada. Al escribir una línea, command.com inicia un nuevo proceso, le transfiere el control y espera a que éste termine. La diferencia con UNIX es que en UNIX, cualquier usuario es libre de escribir un shell que no deba esperar, sino que muestre el indicador de manera inmediata. Además, con el shell estándar, si el usuario coloca un & después del comando, el shell no espera. En todo caso, en UNIX, después de iniciar un proceso hijo, el padre no tiene que esperar a que él termine y continuar su cálculo en paralelo con el hijo. En MS-DOS, el padre y el hijo no pueden ejecutarse en paralelo. Cuando un proceso produce un hijo, el padre se suspende de manera automática hasta que el hijo hace una salida. Nada de lo que pueda hacer el padre puede evitar esto. Así, en cualquier momento puede existir un número arbitrario de procesos dentro de la memoria, pero sólo uno de ellos estar activo. El resto se suspende en espera de que un hijo termine. Por esta razón, aunque MS-DOS permite la existencia de varios procesos a la vez, no es un verdadero sistema multiprogramado. Si11 embargo, es posible lograr un limitado grado de multiprogramación mediante el manejo directo de las estructuras de datos del sistema operativo debido a que MS-DOS se ejecuta en máquinas sin protección memoria. Cuando un proceso termina se reclama su memoria y desaparece para siempre. Sin embargo, MS-DOS tiene una alternativa para un proceso que concluye, donde se indica al sistema que no recupere su memoria sino que considere que hizo su salida. Esta característica, se conoce como software TSR (siglas en inglés de terminar y permanecer residente) o software residente en memoria. A primera vista, el hecho de tener un proceso muerto alrededor del cual no se puede activar algo no suena muy atractivo. Sin embargo, los procesos en MS-DOS pueden instalar sus propios manejadores de interrupciones. En particular, un proceso puede instalar un nuevo manejador del teclado, el cual se llama en cada interrupción del teclado. El manejador examina rápidamente la combinación de teclas, para ver si es la tecla especial o combinación de teclas llamada tecla de activación, que activa el código TSR. Si este no es el caso, el carácter se coloca en la cola de entrada de caracteres del sistema operativo y el programa TSR regresa de la interrupción al programa de la aplicación. Si es la tecla de activación, el programa TSR vuelve a la vida y realiza lo que se supone deba hacer. La escritura de un programa TSR tiene ciertos trucos. Lo peor es que debe realizar su trabajo sin llamar al MS-DOS, puesto que éste podría estar activo al momento de la interrupción. MS-DOS no es reentrante, lo que significa que no puede Escuela de Preparación de Opositores E.P .O. v05 INF16 - SAI16. Página 19 manejar una segunda llamada hasta terminar con la primera. Entre otras cosas, el programa TSR no puede utilizar MS-DOS para leer nuevos datos mediante el teclado y no lo puede utilizar para escribir en pantalla. Tampoco lo puede utilizar para tener acceso a archivos. Así, el programa TSR debe realizar su propia EIS. 8.2 Implementación deprocesos en MS-DOS. La administración de los procesos en MS-DOS es directa, puesto que no existe multiprogramación. Cuando un proceso crea un nuevo proceso hijo, se realizan los siguientes pasos: 1. Encuentra un bloque de memoria lo bastante grande como para contener al proceso hijo. 2. Construye el PSP (prefijo de segmento de programa) en los primeros 256 bytes de la memoria asignada. PSP contiene el tamaño del programa, un puntero al bloque de entorno, la dirección del manejador CTRL-C, la cadena del comando, un puntero al PSP del padre, la tabla de descriptores de archivo, etc. Parte de la información proviene del PSP del padre, mientras que otra parte, como la línea de comandos, es exclusiva de este proceso. 3. Carga el archivo ejecutable en binario en la memoria asignada, a partir del primer byte arriba del PSP. 4. Inicia el programa. Los PSP juegan un papel importante en MS-DOS. Una variable global dentro del sistema apunta al PSP del proceso activo. El PSP contiene toda la información de estado necesaria para ejecutar el proceso. Puesto que cada PSP contiene un puntero al proceso activo, MS-DOS puede seguir la cadena de regreso hasta commandcom y localizar todos los procesos (suspendidos) en el sistema. El PSP también contiene la dirección a la cual regresar después de terminar un proceso. La planificación de la CPU es trivial. Puesto que sólo existe un proceso activo, éste se ejecuta todo el tiempo, excepto cuando un programa TSR toma el control. 9 Procesos en windows 2000. 9.1 Conceptosfundamentales. Windows 2000 maneja procesos, capaces de comunicarse y sincronizarse entre sí. Cada proceso contiene por lo menos un subproceso, que a su vez contiene al menos un hilo. Además, los procesos pueden unirse en trabajos. Un trabajo es una colección de uno o más procesos que se administran corno una unidad. En particular, hay cuotas y límites de recursos que se almacenan en el trabajo correspondiente. Las cuotas incluyen el número máximo de procesos, el tiempo total de CPU disponible para cada proceso individual y para todos los procesos combinados, y el consumo máximo de memoria, también por proceso y total. Además, los trabajos pueden imponer restricciones de seguridad a los procesos que contienen, como no poder adquirir facultades de administrador, ni siquiera con la contraseña correcta. Los procesos son contenedores de recursos. Cada proceso tiene un espacio de direcciones de 4 GB, un identificador de proceso, uno o más subprocesos, una lista de identificador y una ficha de acceso que contiene su información de seguridad. Escuela de Preparación de Opositores E.P .O. v05 INF16- SAI16. Página 20 Todo proceso empieza con un subproceso, pero pueden crearse dinámicamente r nuevos subprocesos. Estos constituyen la base de la planificación de la CPU, pues el sistema operativo siempre escoge el subproceso que se ejecutará, no un proceso. Por consiguiente, cada subproceso tiene un estado, mientras que los procesos no tienen estado. Cada subproceso tiene un identificador, que se toma del mismo espacio que el identificador de proceso, de modo que un identificador dado nunca puede usarse para un subproceso y para un proceso al mismo tiempo. Los subprocesos normalmente se ejecutan en modo usuario, pero cuando emiten una llamada al sistema cambian a modo kernel y se siguen ejecutando con el mismo identificador, propiedades y límites que tenían en el modo usuario. Cada subproceso tiene dos pilas, una para usarla en modo usuario y otra para usarla en modo kernel. Además, cada subproceso tiene un contexto, un área privada para sus propias variables locales y tal vez su propia ficha de acceso. Si el subproceso tiene su propia ficha de acceso, ésta sobrescribe a la ficha de acceso del proceso para que los subprocesos cliente puedan pasar sus derechos de acceso a subprocesos servidores que están trabajando para ellos. Cuando un subproceso termina de ejecutarse, puede salir. Cuando sale el último subproceso que estaba activo en un proceso, éste termina. Los subprocesos son un concepto de planificación, no de posesión de recursos. Cualquier subproceso puede tener acceso a todos los objetos que pertenecen a su proceso. No hay restricciones en cuanto a que un subproceso no puede tener acceso a un objeto porque éste fue creado o abierto por un subproceso distinto. Una vez que un identificador de objeto se ha colocado en la tabla de identificadores de un proceso, podrá usarlo cualquier subproceso del proceso. Además, Windows 2000 tiene varios subprocesos demonios que sólo se ejecutan en modo kernel y no están asociados con ningún proceso de usuario. La conmutación de subprocesos es costosa porque requiere pasar a modo kernel y salir después de él. Para solucionar esto Windows 2000 proporciona hilos. Cada subproceso puede tener varios hilos, así como un proceso puede tener varios subprocesos, excepto que cuando un hilo se bloquea, se coloca a sí mismo en la cola de hilos bloqueados y selecciona otro hilo para que se ejecute en el contexto de su subproceso. El sistema operativo no es consciente de tal transición porque el subproceso sigue ejecutándose, aunque primero esté ejecutando un hilo y después otro. E'INIC1k>de A aactoMs.,.. / I' • \ \ ' ..... ', --..._.... <, I -...-Pa •*'ProclfJMWl•ftCldo••• ŒI lillil··--·- ficlta de ICC? 7¢ ___...fijliJ IE Escuela de Preparación de Opositores E.P.O. v05 INFl 6 - SAI 16. Página 21 9.2 Planificación. Windows 2000 no tiene un subproceso planificador central. En vez de eso, cuando un subproceso ya no puede seguir ejecutándose, ingresa en modo kernel y ejecuta el planificador. El sistema tiene 32 prioridades, numeradas del O al 31 que se calculan a partir de Ia clase de prioridad del proceso y la prioridad relativa del subproceso. La clase de prioridad se establece para todos los subprocesos del proceso. Los valores permitidos son: tiempo real, alta, mayor que la normal, normal, menor que la normal e inactiva. La prioridad relativa del subproceso es en comparación con los demás subprocesos de su proceso. Los valores permitidos son: tiempo crítico, más alta, mayor que la normal, normal, menor que la normal, más baja e inactiva. Se establece una correspondencia entre las combinaciones y las clases de prioridad para determinar la prioridad base del subproceso. Además, cada subproceso tiene una prioridad actual que podría ser más alta (pero no más baja) que la prioridad base. Para planificar con base en estas prioridades, el sistema mantiene un array con 32 entradas. Cada entrada apunta a la cabeza de una lista de subprocesos listos con la prioridad correspondiente. El algoritmo de planificación básico consiste en explorar el array desde la prioridad 31 hasta la O. Tan pronto como se halla una ranura no vacía, se selecciona el subproceso que está a la cabeza de la cola y se ejecuta durante un quantum. Sì el quantum expira, el subproceso se coloca al final de la cola correspondiente a su nivel de prioridad y a continuación se escoge el subproceso que ahora está al frente de la cola. Dicho de otro modo, cuando hay varios subprocesos listos en el nivel de prioridad más alto, se ejecutan por tumo circular (round robin) durante un quantum cada uno. Sì ningún subproceso está listo, se ejecuta el subproceso inactivo. Cabe señalar que la planificación se efectúa escogiendo un subproceso sin importar a qué proceso pertenezca. Por tanto, el planificador no escoge primero un proceso y luego un subproceso de ese proceso; sólo examina los subprocesos. El planificador ni siquiera sabe qué subproceso pertenece a qué proceso. La siguiente figura muestra que en realidad hay cuatro categorías de prioridades: tiempo real, usuario, cero y espera inactiva, que de hecho es -1. Las prioridades 16-31 se caracterizan como de tiempo real, pero no lo son. No se ofrecen garantías ni se cumplen plazos. Tan sólo son prioridades más altas que las 0-15. No obstante se reservan para el sistema en sí y para los subprocesos a los que el administrador del sistema asigna de manera explícita esas prioridades. Escuela de Preparación de Opositores E.P.O. v05 INF16-SAI16. Página 22 _J----- .......... SubpoeetO pãt,iias• 6t::::::=:::1~ ~ Wl8Cho .,,- Los subprocesos de usuario se ejecutan con prioridades entre 1 y 15. Al establecer las prioridades de proceso y de subproceso, el usuario puede determinar qué subprocesos tienen preferencia. El subproceso cero se ejecuta en segundo plano y consume el tiempo de CPU que nadie más quiere. Su tarea consiste en llenar de ceros las páginas que asignará el administrador de memoria. Si no hay nada que hacer, ni siquiera llenar páginas de ceros, se ejecuta el subproceso inactivo. En ciertas condiciones específicas, el sistema operativo puede elevar la prioridad actual de un subproceso de usuario por encima de la prioridad base, pero nunca más allá de la prioridad 15. Por ejemplo, cuando termina una operación de E/S y libera un subproceso que estaba en espera, la prioridad se eleva para que el subproceso tenga la oportunidad de volver a ejecutarse pronto e iniciar más operaciones de E/S. El grado de elevación depende del dispositivo de E/S, y suele ser 1 en el caso de un disco, 2 para una línea serie, 6 para el teclado y 8 para la tarjeta de sonido. Puesto que el array de la figura se basa en la prioridad actual, un cambio en esta prioridad afecta la planificación. Nunca se efectúan ajustes a los subprocesos que se ejecutan con prioridad 15 o superior. Una última modificación al algoritmo de planificación hace que, si una ventana nueva se convierte en la ventana de primer plano, el quantum de todos sus subprocesos aumente en una cantidad que se toma del Registro. Este cambio les otorga más tiempo de CPU, lo que se traduce en un mejor servicio para la ventana que acaba de pasar al primer plano. 1O Conclusiones. Para ocultar los efectos de las interrupciones, los sistemas operativos proporcionan un modelo conceptual, consistente en procesos secuenciales ejecutados en paralelo. Cada proceso tiene su propio estado y se puede pensar que se ejecuta en su propio procesador virtual. La interacción entre procesos puede derivar en condiciones de competencia, situaciones en las que la perfecta sincronización determina el resultado. Para evitar las condiciones de competencia, se introdujo el concepto de sección crítica, que es una sección de código en la que un proceso realiza algo con el estado compartido y no desea que otros procesos trabajen ahí también. Las secciones críticas proporcionan la exclusión mutua. Existen varias primitivas de la comunicación entre procesos. Entre éstas están los semáforos, los monitores, y la transferencia de mensajes. Escuela de Preparación de Opositores E.P .O. v05 INF16 - SAI 16. Página 23 Se conocen muchos algoritmos de planificación. La labor de un algoritmo de planificación es determinar el proceso que debe ejecutarse a continuación, tomando en cuenta factores tales como el tiempo de respuesta, la eficacia y la equidad. Entre los algoritmos de planificación más conocidos están el round robin, planificación por prioridades, colas de varios niveles, primero el trabajo más corto y la planificación garantizada. En algunos sistemas, el mecanismo de planificación y la política de planificación se dividen, lo que permite una mayor flexibilidad. Algunos sistemas operativos hacen una distinción entre los conceptos de proceso e hilo, el primero se refiere a la propiedad de los recursos y el segundo se refiere a la ejecución de programas. Este enfoque puede conducir a una mejora de la eficiencia y hacer más cómoda la programación. En un sistema rnultihilo, dentro de un único proceso se pueden definir múltiples hilos. UNIX es un sistema multiprogramación que posee un método sencillo pero poderoso para el control de los procesos. Los procesos pueden producir subprocesos, lo cual lleva a un árbol de procesos. La administración de los procesos en UNIX utiliza dos estructuras de datos básicas, la tabla de procesos y la estructura del usuario. La primera siempre está en la memoria, pero la segunda se puede intercambiar con el disco o paginarse fuera de la memoria. Un proceso se crea al duplicar la entrada de la tabla de procesos y la imagen de la memoria. La planificación se lleva a cabo mediante un algoritmo con base en la prioridad que favorece a los usuarios interactivos. Aunque MS-DOS permite la existencia de varios procesos a la vez, no es un verdadero sistema multiprogramación. Sólo puede estar activo un proceso a la vez, pero un proceso puede crear y ejecutar un proceso hijo. Sin embargo, esto suspende al padre hasta que el hijo termina. Los programas que terminan y permanecen residentes siguen existiendo incluso después de hacer su salida.