Conf- 06 Procesos Concurrentes.pdf

Sistemas Operativos. Tema 2. Conferencia # 6. Procesos. Procesos...

Sistemas Operativos. Tema 2. Conferencia # 6. Procesos. Procesos concurrentes. Contenido 1 Introducción..................................................................................................................1 2 Concepto de proceso....................................................................................................1 3 Modelo de procesos.....................................................................................................2 4 Jerarquía de procesos...................................................................................................3 5 Estados de un proceso..................................................................................................3 6 Implantación de procesos.............................................................................................4 7 Hilos..............................................................................................................................5 7.1 Estados de un hilo.................................................................................................7 8 Competencia entre los procesos..................................................................................7 8.1 Requisitos para la exclusión mutua.......................................................................8 9 Conclusiones.................................................................................................................8 1 Introducción Hasta el momento hemos mencionado, e incluso conceptualizado de forma muy breve a el proceso. Pregunta: De lo visto hasta ahora ¿qué entendemos por un proceso? Hemos trabajado en la consola, pero ¿hemos manipulado o intervenido en el funcionamiento de algún proceso? El concepto central de cualquier SO es el de proceso. Un proceso es básicamente la abstracción de un programa en ejecución. Todo lo demás todo se articula en torno a este concepto. Todas las computadoras modernas, e incluso muchos equipos aparentemente más simples, como muchos teléfonos celulares modernos, hacen varias cosas al mismo tiempo. 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 la apariencia de paralelismo. Sucede que el concepto de procesos es un poco más complicado y, en sí, encierra dos conceptos, uno que guarda relación con la propiedad de los recursos y otro que se asocia a la ejecución, de esta forma un proceso se puede ver como:  Una unidad propietaria de recursos (Proceso). El proceso posee un espacio de memoria virtual, se le asigna la CPU y otros recursos cuando los necesita y se pueda hacer tal asignación.  Una unidad de despacho (Hilo). Un proceso es un camino de ejecución y por tal motivo su vida transcurre por varios estados. En esta conferencia definiremos qué es un proceso y veremos sus características en un sistema multitarea. 2 Concepto de proceso Un proceso es simplemente una instancia de un programa en ejecución, lo que significa que el proceso incluye los valores actuales del contador de programa, los registros de la CPU, las tablas de asignación de memoria y muchas otras cosas, en fin todo lo que permite que pueda ser interrumpido en un punto dado para después reanudar la ejecución. Asociado a cada proceso hay una serie de atributos que utiliza el sistema operativo para el control del proceso. Estos atributos se recogen en una estructura de datos que se conoce como bloque de control de proceso (Process Control Block, PCB) o descriptor de proceso. A esta colección de programa, datos, pila y atributos se le llama imagen o entorno del proceso. Se puede afirmar que cada proceso tiene su CPU virtual en el sentido que siempre tiene una copia de ella.  Cada vez que un proceso entre en el estado de ejecución esa copia virtual se usará para cargar desde ella la CPU con los valores que permiten continuar el proceso exactamente donde fue detenido.  Cada vez que un proceso sea detenido por cualquier cosa, se tomarán los valores de la CPU para guardarlos en la copia CPU virtual de la CPU del proceso. Debido a que los procesos corresponden a un programa en ejecución, estos no deben ser confundidos con el programa que ellos corren, pues, muchos procesos pueden correr de un mismo programa, por ejemplo, muchos usuarios pueden tener cada uno una instancia del mismo editor abierta.  Un programa es un ente pasivo, o sea, es solo un algoritmo escrito en un lenguaje dado que no tiene “vida” ni nada asociado.  Un proceso es un ente activo, es el propio programa pero ahora tiene recursos asignados (incluida la CPU) y datos que son procesados y, por tanto, se van a producir resultados a partir de ellos. 3 Modelo de procesos Sabemos que en los sistemas operativos actuales múltiples procesos pueden ser ejecutados al mismo tiempo y que, potencialmente, pueden interactuar entre sí. Esta propiedad de los sistemas es denominada concurrencia. Los procesos concurrentes pueden ser ejecutados realmente de forma simultánea o paralela, sólo cuando cada uno es ejecutado en diferentes procesadores (multiprocesamiento). En cambio, la concurrencia es simulada si sólo existe un procesador encargado de ejecutar los procesos concurrentes, ocupándose de forma alternada en uno y otro proceso a pequeñísimos intervalos de tiempo. De esta manera simula que se están ejecutando a la vez, o en forma seudoparalela (multiprogramación). Hemos visto tres concepciones dentro de los sistemas operativos:  Multiprogramación. Consiste en el manejo de múltiples procesos dentro de un sistema con un solo procesador.  Multiprocesamiento. Consiste en el manejo de sistemas con varios procesadores.  Procesamiento distribuido. Es el manejo de múltiples procesadores en diferentes sistemas de cómputos. La concurrencia abarca un conjunto de actividades dentro de un SO: la comunicación entre procesos, la competencia y el compartimiento de recursos, la sincronización de las actividades de múltiples procesos y la asignación de tiempo del procesador a los procesos. La concurrencia se puede ver en diferentes contextos:  Aplicaciones múltiples. La multiprogramación se ideó para permitir que el tiempo del procesador se pudiera compartir entre diferentes actividades.  Aplicaciones estructuradas. Como una extensión de los principios del diseño modular y de la programación estructurada, algunas aplicaciones se pueden programar como un conjunto de procesos concurrentes.   Sistemas Operativos estructurados. Las mismas ventajas de la estructuración se aplican a los programas de sistemas, así podemos ver que muchos SO se implementan como un conjunto de procesos. En un sistema multiprogramado no se puede programar haciendo suposiciones acerca de la velocidad de ejecución, ya que no todos los procesos ejecutan sus cálculos a igual velocidad e incluso, en el caso que se ejecuten varias veces, cada vez no tienen que comportarse igual. Fig. 1. (a) Multiprogram ación de 4 program as. (b) Modelo conceptual de 4 procesos secuenciales diferentes. (c) Solo un program a esta activo cada instante de tiempo. 4 Jerarquía de procesos Los SO que pretendan manejar procesos deben ofrecer la forma de crear todos los procesos necesarios. En sistemas muy simples es posible que todos los procesos necesarios sean cargados una vez que este se inicia y estén presentes hasta el final. En sistemas más complejos, como cualquier PC de escritorio donde los usuarios no tengan predefinido, no solo que hacer en un día, sino que hacer en toda la vida de la PC, es necesario destruir los procesos que no se van a usar más por el momento para poder crear otros nuevos en el mismo espacio de memoria. Los Sistemas Operativos cuentan con mecanismos para crear procesos, en UNIX, Linux, y Minix, en fin en todos los Sistemas Operativos de la familia UNIX y sus “parientes” se usa la llamada al sistema operativo fork, lo que permite crear árboles de procesos con toda la complejidad que deseemos. 5 Estados de un proceso El estado de un proceso está determinado por su actividad actual.  Listo. Un proceso que está esperando por la CPU  Corriendo. Un proceso que tiene la CPU asignada  Bloqueado. En espera de algún evento externo Al estado bloqueado se puede llegar automáticamente o por una solicitud explícita dependiendo del Sistema Operativo. En el gráfico siguiente, las transiciones 2 y 3 son provocadas por el planificador de la CPU o de procesos. La transición 4 ocurre cuando sucede el evento externo por el cual estaba esperando el proceso, como es de esperarse el proceso no puede ir directamente hacia la CPU porque es posible que haya otros procesos en el estado de listo y el proceso desbloqueado tendrá que esperar pacientemente a que le toque el turno.  Fig. 2. Los procesos pueden estar corriendo, bloque ados o listos. Las posibles transiciones entre estos estados se muestran en la figura. Dependiendo del sistema operativo, pueden existir diferentes estados con otros nombres, pero la idea central es mantener alguna estructura de datos que permita conocer el estado en que está el proceso y que ese estado tenga un significado para la acción que va a tomar el SO sobre el proceso. 6 Implantación de procesos El sistema operativo usa una estructura de datos Estado del proceso Puntero denominada bloque de control de proceso (PCB del inglés) y una tabla de procesos de forma que Identificación del proceso cada entrada en la tabla se refiera a un PCB. Copia de los registros El PCB (figura 3) contiene toda la información que … necesita el sistema operativo para poder planificar los procesos (asignarle la CPU y Limites de la memoria desalojarlos), Esa estructura de datos es la que denominamos anteriormente CPU virtual en ella Lista de archivos abiertos están todos los valores que tenía la CPU en el Fig. 3. Bloque de control de proceso momento en que se interrumpió el proceso y hay información adicional (PCB) que ayuda a la planificación. Estos bloques son leídos y/o modificados por casi todos los módulos de un sistema operativo, incluyendo aquellos que tienen que ver con la planificación, la asignación de recursos, el tratamiento de interrupciones y el análisis y supervisión del rendimiento. Puede decirse que el conjunto de los bloques de control de procesos definen el estado del sistema operativo. El conjunto de todos los PCB’s se guarda en una estructura del sistema operativo llamada tabla de procesos, la cual se puede implementar como un vector o un lista enlazada. La tabla de procesos reside en memoria principal, debido a su alta frecuencia de consulta. Con respecto a la identificación del proceso, en casi todos los s istemas operativos se le asigna a cada proceso un identificador numérico único (ID). Este identificador nos servirá para localizarlo dentro de la tabla de procesos. Cuando se permite que los procesos creen otros procesos, se utilizan identificadores para s eñalar al padre y a los descendientes de cada proceso. Además de estos, un proceso también puede tener asignado un identificador de usuario que indica a quién pertenece el proceso (UID). El siguiente conjunto de información es la información de estado del procesador. Básicamente, está formada por el contenido de los registros del procesador. Por supuesto, mientras el proceso está ejecutándose, la información está en los registros. Cuando se interrumpe el proceso, toda la información de los registros debe salvarse de forma que pueda restaurarse cuando el proceso reanude su ejecución. La naturaleza y número de registros involucrados depende del diseño del procesador. Normalmente, en el conjunto de registros se incluyen los registros visibles para el usuario, los registros de control y de estado (contador de programa y palabra de estado) y los punteros a pila. A la tercera categoría general de información del bloque de control de proceso se le podría llamar información de control del proceso. Esta es la informa ción adicional necesaria para que el sistema operativo controle y coordine los diferentes procesos activos. Como, por ejemplo, información de planificación y estado (estado del proceso, su prioridad, información de planificación, suceso), apuntadores (punteros) a estructuras de datos (los procesos que esperan en un semáforo), punteros a zonas de memoria del proceso, recursos controlados por el proceso (ficheros abiertos), etc. Así pues, el PCB es la entidad que define un proceso en el sistema operativo. Dado que los PCB necesitan ser manejados con eficiencia por el sistema operativo, muchos ordenadores tienen un registro hardware que siempre apunta hacia el PCB del proceso que se está ejecutando. A menudo existen instrucciones hardware que cargan en el PCB información sobre su entorno, y la recuperan con rapidez. 7 Hilos Como vimos desde la introducción los procesos cuentan con una unidad de despacho que se conoce como hilo. Los sistemas operativos pueden trabajar como: Sistema de hilo-simple. En este modelo de sistemas operativos, no hay distinción entre hilo y proceso, ambos conceptos son equivalentes. La representación de un proceso, en este caso incluye:  Un bloque de control de proceso.  Su espacio de direcciones.  La pila (stack) del núcleo (kernel).  La pila (stack) del usuario. Un sistema operativo como MS-DOS soporta un solo proceso con un solo hilo (en realidad no existe distinción), por otra parte un sistema operativo como UNIX soporta múltiples procesos, pero solo un hilo por cada proceso. Sistema multihilo. En este modelo también existe un bloque de control de proceso y un espacio de direcciones asociado con el proceso, pero existen pilas separadas para cada hilo y bloques de control de proceso de los hilos. Cada proceso puede crear tantos hilos como se permita de acuerdo a otras restricciones (memoria, por ejemplo). Sistemas operativos que permiten esta visión son: Windows, Solaris, Mach y OS/2. En un medio multihilo, un proceso se define como una unidad de protección y de asignación de recursos. A los procesos se asocia:  Un espacio de memoria virtual.  Protección de acceso a los procesadores.  Archivos.  Recursos de entrada salida (canales y manipuladores). Dentro de cada proceso pueden existir uno o más hilos, cada uno de ellos posee la siguiente información:  El estado de ejecución del hilo (corriendo, ejecutando, etc.).  Un contexto para guardar cuando no esté corriendo (permite volver a darle el control en un futuro).  Una pila de ejecución.  Capacidad de almacenamiento estático para variables locales.  Acceso a la memoria y recursos de su proceso que comparte con otros hilos del mismo proceso. En un sistema de hilo simple la representación del proceso incluye su PCB y el espacio de direcciones del usuario, la pila de usuario y del núcleo. El proceso que está corriendo controla los registros del procesador, guardando el contenido de dichos registros (en el PCB) cuando se interrumpe. Los sistemas multihilo, poseen un PCB para cada proceso, pero cada hilo de ese proceso tiene un bloque de control del hilo, cada uno de esos bloques contiene una imagen de los registros, su prioridad y en general información referente al hilo. En un sistema multihilo, todos los hilos de un proceso, comparten el estado y los recursos del proceso, ellos residen en el mismo espacio de direcciones y tienen acceso a los mismos datos, de esa forma cuando un hilo altera algo en la memoria, los demás hilos pueden percatarse de esa alteración. Si, por ejemplo, un hilo abre un archivo con permiso de lectura, los demás hilos del mismo proceso pueden leer ese archivo. El principal beneficio de todo esto es el rendimiento ya que toma menos tiempo crear un hilo de un mismo proceso que crear un nuevo proceso como rama de otro, también toma menos tiempo el cambio entre hilos y menos tiempo para terminar. La conclusión es fácil, si hay una tarea que puede dividirse en diferentes unidades de ejecución, será más eficiente hacerlo como una colección de hilos que como una colección de procesos separados. Un servidor de archivos puede ser un buen ejemplo donde es beneficioso usar múltiples hilos. Cada requerimiento de archivo nuevo se puede tratar como un hilo nuevo, si el servidor tuviera múltiples procesadores, las cosas irían mejor ya que varios hilos de un solo proceso pudieran estar ejecutándose en paralelo realmente. Una ventaja adicional para los hilos de un mismo proceso es que se pueden comunicar entre si (sin intervención del núcleo) ya que comparten la memoria. Básicamente la planificación y el despacho de trabajos para la CPU se hacen al nivel de hilo, por ese motivo la estructura de datos asociada a los hilos es la que mantiene la información básica para estas tareas. No obstante algunas acciones afectan a todos lo hilos de un proceso y por ese motivo el SO las maneja a ese nivel, por ejemplo suspender un proceso para hacer un intercambio (swapping) de memoria da por resultado suspender a todos los hilos de ese proceso ya que ellos comparten una memoria común, la terminación de un proceso también provoca la terminación de sus hilos. Los hilos deben exhibir una funcionalidad igual a la de los procesos, ellos sincronizan su ejecución con los demás hilos y pasan por diferentes estados cuando están en el sistema (corriendo, bloqueado, listo, etc.) al igual que los procesos. No obstante, algunos estados se pueden ver en el ámbito del proceso, por ejemplo si un proceso se lleva totalmente hacia la memoria secundaria, el proceso queda suspendido y por supuesto todos sus hilos ya que ellos comparten la misma memoria, en ese caso es mejor hablar de un cambio de estado del proceso y no de los hilos. Queda claro que si un proceso está suspendido, los hilos “contenidos en él” están suspendidos también. 7.1 Estados de un hilo Al igual que los procesos, los hilos tienen tres estados principales: Corriendo, Listo y Bloqueado, existen cuatro operaciones básicas asociadas con el cambio de estado de los hilos:  Creación. Típicamente cuando se crea un nuevo proceso también se crea un nuevo hilo que es en sí el mismo proceso.  Bloqueado. Cuando un hilo necesita esperar por un evento, se bloquea.  Listo. Cuando ocurre el evento por el que estaba esperando, el hilo pasa al estado de listo.  Finalización. Cuando un hilo termina, se liberan sus registros y su pila. 8 Competencia entre los procesos Los recursos de un sistema pueden clasificarse como compartibles, lo que significa que pueden ser utilizados por varios procesos de forma concurrente, o no compartibles, lo que equivale a que su uso se restrinja a un sólo proceso a la vez. El hecho de que un recurso no sea compartible deriva de una de las dos razones siguientes:  La naturaleza física del recurso hace que sea imposible compartirlo. Un ejemplo lo constituye una impresora, si una impresora fuera utilizada por varios procesos simultáneamente sus salidas se entremezclarían en el papel.  El recurso es tal que si es usado por varios procesos de forma concurrente la acción de uno de ellos puede interferir con la de otro. Un ejemplo común lo constituye un fichero que contiene unos datos accesibles desde más de un proceso, y modificables al menos por uno de ellos. Para ilustrar mejor la segunda situación supongamos un fichero que contiene registros de saldo y clave, que es información sobre una cuenta bancaria. Supongamos también dos procesos que se ejecutan concurrentemente y que actualizan una misma cuenta, el proceso P1 añade al saldo el valor de la nómina y el proceso P2 descuenta del saldo una factura domiciliada. El código de los procesos es el siguiente: P1 P2 Cálculos Cálculos a1: leer registro b1: leer registro a2: saldo  saldo + nómina b2: saldo  saldo - factura a3: escribir registro b3: escribir registro Cálculos Cálculos El resultado final de la ejecución de los dos procesos debería actualizar el saldo añadiéndole la nómina, y descontándole la factura. Sin embargo, la secuencia de ejecución en el procesador de las instrucciones a1|b1|b2|b3|a2|a3, que puede darse debido a un cambio de proceso, hace que no se descuente la factura. Dentro de la categoría de recursos no compartibles se incluirán la mayoría de los periféricos (los discos no), los ficheros de escritura y las zonas de memoria sujetas a modificación. Los recursos compartibles incluirán la CPU (en los temas previos vimos cómo compartir la CPU entre los procesos introduciendo el concepto de PCB), los ficheros de lectura, y las zonas de memoria que contengan rutinas puras o bien datos que no están sujetos a modificación. 8.1 Requisitos para la exclusión mutua Los recursos no compartibles, ya sean periféricos, ficheros, o datos en memoria, pueden protegerse del acceso simultáneo por parte de varios procesos evitando que éstos ejecuten de forma concurrente sus fragmentos de código a través de los cuales llevan a cabo este acceso. Estos trozos de código reciben el nombre de secciones o regiones críticas, pudiéndose asimilar el concepto de exclusión mutua en el uso de estos recursos a la idea de exclusión mutua en la ejecución de las secciones críticas. Así, por ejemplo, puede implementarse la exclusión mutua de varios procesos en el acceso a una tabla de datos mediante el recurso de que todas las rutinas que lean o actualicen la tabla se escriban como secciones críticas, de forma que sólo pueda ejecutarse una de ellas a la vez. En el ejemplo previo de la cuenta bancaria los fragmentos de código a1|a2|a3 y b1|b2|b3 constituyen dos secciones críticas mutuamente excluyentes, esto significa que una vez que se ha comenzado la ejecución de una sección crítica, no se puede entrar en otra sección crítica mutuamente excluyente. Idear soluciones que garanticen la exclusión mutua es uno de los problemas fundamentales de la programación concurrente. Muchas son las alternativas y tipos de mecanismos que se pueden adoptar. A lo largo de este tema veremos diferentes soluciones de software y hardware. Unas serán sencillas y otras complejas, algunas requieren la cooperación voluntaria de los procesos y otras que exigen un estricto ajuste a rígidos protocolos. La selección de las operaciones primitivas adecuadas para garantizar la exclusión mutua de las secciones críticas es una decisión primordial en el diseño de un sistema operativo. Al menos, una solución apropiada debería cumplir las cuatro condiciones siguientes: 1. Que no haya en ningún momento dos procesos dentro de sus respectivas secciones críticas. 2. Que no hagan suposiciones a priori sobre las velocidades relativas de los procesos o el número de procesadores disponibles. 3. Que ningún proceso que esté fuera de su sección crítica pueda bloquear a otros. 4. Que ningún proceso tenga que esperar un intervalo de tiempo arbitrariamente grande para entrar en su sección crítica. 9 Conclusiones Los sistemas operativos modernos permiten que se ejecuten varios procesos en paralelo, lo que viene dado por el concepto de multiprogramación (previamente estudiado) o el multiprocesamiento (que sólo hemos mencionado someramente). Un hilo es una unidad de despacho, los sistemas de hilo simple no distinguen entre hilo y proceso mientras los sistemas multihilo hacen una distinción que tiene que ver, incluso, con las estructuras de datos más importantes que controlan a los hilos. El hecho de que los procesos o los hilos compartan estructuras de datos y ejecuten en paralelo (concurrencia) hace que surjan nuevos problemas que tienen que ser tratados por el sistema operativo. Cuando varios procesos tienen la posibilidad de trabajar en paralelo, excepto en determinados segmentos de código (regularmente pequeños conocidos como sección crítica) en donde no se cumplen las condiciones de Berstein se tienen que tomar cuidados especiales para no violar la concurrencia. Bibliografía  Operating System Concepts, James Peterson.  Operating System Design and Implementation, Andrews S. Tanebaum  Sistemas Operativos Modernos, Andrews S. Tanebaum