En este capítulo vamos a intentar explicar los conceptos básicos necesarios para entender el significado de los hilos y la programación multihilo. Se explican, de forma genérica, los conceptos de sistema operativo, proceso, paralelismo, concurrencia y comunicación y sincronización de procesos. Para una explicación más detallada se puede consultar cualquier libro sobre conceptos de sistemas operativos como puede ser [TAN93].
La definición de sistema operativo es complicada, aunque todos los usuarios de computadoras tienen cierta experiencia con él. Su definición se basa en las dos funciones principales que realiza :
Los sistema operativos han ido evolucionando a lo largo de los años. La evolución de los sistemas operativos ha estado ligada con la arquitectura de las máquinas en las que se ejecutan :
La organización de los sistemas operativos ha ido evolucionando también, al igual que lo ha ido haciendo el hardware. Se pueden distinguir una serie de organizaciones muy relacionadas con la época de cada sistema operativo :
1) Estructura monolítica : Los primeros sistemas operativos tenían una organización o estructura monolítica. No poseían estructura alguna. El sistema operativo constaba de una serie de procedimientos., cada uno de los cuales puede llamar al resto cuando sea necesario. Cada procedimiento del sistema tiene una interfaz bien definida. Los servicios que proporciona el sistema operativo se solicitan colocando los parámetros en lugares bien definidos (registros o pila), para después ejecutar una instrucción especial de trampa, una llamada al núcleo o una llamada al supervisor. Esta instrucción cambia la máquina del modo usuario al modo supervisor (o modo kernel), y transfiere el control al sistema operativo.
Así una estructura simple para un sistema monolítico sería la siguiente :
a) Un programa principal que realiza una llamada al procedimiento de servicio solicitado.
b) Un conjunto de procedimientos de servicio que realizan las llamadas al sistema.
c) Un conjunto de procedimientos de utilidad que ayudan al procedimiento de servicio.
2) Estructura en capas : Es una generalización
del modelo mostrado en la figura anterior. Se trata de organizar
el sistema operativo como una jerarquía de capas, cada
una construida sobre la anterior. Un ejemplo de esta estructura
es el sistema operativo THE, desarrollado en Holanda por E.W.
Dijkstra y un grupo de estudiantes en 1968.
5 | El operador |
4 | Programas de usuario |
3 | Gestión de entrada/salida |
2 | Comunicaciones operador/proceso |
1 | Gestión de memoria y disco |
0 | Asignación del procesador y multiprogramación |
Una generalización avanzada del concepto de capas se realizó en el sistema operativo MULTICS, que se organizó en anillos concéntricos. Los anillos interiores son los de mayores privilegios.
3) Estructura de máquinas virtuales : El origen de esta estructura se encuentra en el sistema operativo CP/CMS, que después se llamó VM/370, diseñado para el sistema 360/370 de IBM. Es un sistema de tiempo compartido que proporciona multiprogramación y una máquina extendida con una interfaz más agradable que el propio hardware, separando estas dos funciones de forma clara.
El sistema posee un monitor de máquina virtual que se ejecuta en el hardware y realiza la multiprogramación, proporcionando varias máquinas virtuales, no como máquinas extendidas, sino como copias exactas del hardware simple, con su estructura de modo núcleo y modo usuario, sus interrupciones, etc. al igual que la máquina real. De esta forma cada máquina virtual, por ser idéntica a la real, puede ejecutar cualquier sistema operativo que funcione directamente sobre el hardware, pudiendo tener varios sistemas operativos funcionando al mismo tiempo. CMS (Conversational Monitor System) es un sistema interactivo monousuario que solía ejecutarse sobre cada máquina virtual.
Al emplear este tipo de organización se logra una mayor sencillez de diseño, flexibilidad y facilidad de mantenimiento.
4) Estructura Cliente/Servidor : La tendencia actual en el diseño de sistemas operativos es la de mover la mayor cantidad de código posible hacia capas superiores, con el objetivo de conseguir un núcleo reducido del sistema operativo, un micronúcleo o microkernel. Se trata de implementar la mayoría de las funciones del sistema en procesos de usuario, lo que descarga al núcleo y aumenta la seguridad del sistema. Se implementa un modelo cliente/servidor para la resolución de las llamadas al sistema. Así, si un proceso de usuario (proceso cliente) desea leer un bloque de archivo, envía una solicitud a un proceso servidor que realiza la tarea y devuelve la respuesta. El núcleo sólo se encarga de la comunicación entre cliente y servidor.
El modelo cliente/servidor es también muy utilizado en el diseño de los nuevos sistemas operativos distribuidos, ya que los mensajes que se envían entre procesos pueden ser locales o remotos, pero la abstracción para el cliente es la misma, pues él no conoce el tipo de llamada, sólo sabe que envía una solicitud y recibe un respuesta.
El concepto central de todo sistema operativo es el proceso: abstracción de un programa en ejecución. Todo lo demás se organiza en relación a este concepto.
Los ordenadores modernos realizan varias tareas al mismo tiempo. Por ejemplo, mientras se ejecuta un programa de usuario, el ordenador puede estar leyendo del disco e imprimiendo un documento en la impresora. En un sistema de multiprogramación, la CPU alterna de un programa a otro, ejecutando cada uno durante milisegundos, y conmutando a otro inmediatamente, de tal forma que al usuario se le proporciona cierta sensación de ejecución paralela, como si el ordenador realizase varias tareas al mismo tiempo. Aunque, estrictamente, la CPU ejecuta en un determinado instante un solo programa, durante un segundo puede haber trabajado con varios de ellos, dando una apariencia de paralelismo. Es en estos casos cuando se tiende a hablar de seudoparalelismo, indicando la rápida conmutación entre los programas en la CPU, distinguiéndolo del paralelismo real de hardware, donde se realizan cálculos en la CPU a la vez que operan los dispositivos de E/S. Ya que es complicado controlar las distintas actividades paralelas, los diseñadores de sistemas emplean el modelo de procesos para facilitar la utilización del paralelismo.
Según este modelo, todo el software de la computadora se organiza en procesos secuenciales, o simplemente procesos. Un proceso es un programa en ejecución, incluyendo los valores del contador de programa (PC), registros y variables del programa. Conceptualmente, cada proceso tiene su propia CPU virtual. En realidad, lo que sucede es que la CPU física alterna entre los distintos procesos. Esta alternancia rápida es lo que se llama multiprogramación.
Si la CPU conmuta entre procesos, no es probable que un proceso que se vuelva ejecutar lo haga en las mismas condiciones en que lo hizo anteriormente. Por lo tanto, los procesos no se pueden programar con hipótesis implícitas a cerca del tiempo. El resultado de un proceso debe ser independiente de la velocidad de cálculo y del entorno en que se encuentre, de tal forma que sea reproducible.
La diferencia entre proceso y programa es sutil, pero crucial. El programa es el algoritmo expresado en una determinada notación, mientras que el proceso es la actividad, que tiene un programa, entrada, salida y estado. Una CPU puede compartirse entre varios procesos empleando un algoritmo de planificación, que determina cuando se debe detener un proceso en ejecución para dar servicio a otro distinto.
Normalmente los sistemas operativos modernos diseñados
con una filosofía de kernel, y que emplean el concepto
de proceso, ofrecen alguna forma de crear y destruir los procesos
dinámicamente. En UNIX la creación de procesos se
realiza mediante la llamada al sistema fork, la cual crea
una copia idéntica del proceso que hace la llamada (proceso
padre), tras la cual el proceso hijo sigue su ejecución
en paralelo con el proceso padre. El padre puede crear nuevos
hijos, al igual que el propio hijo, que puede crear nuevos hijos
convirtiéndose en padre en relación a ellos. Se
establece así una relación jerárquica de
dependencia padre-hijo (árbol de procesos).
Cada proceso es una entidad independiente, con su contador de programa y su estado interno. Los 3 estados básicos en que puede encontrarse un proceso son:
1) En ejecución (RUNNING): El proceso está utilizando la CPU en el instante dado.
2) Listo (READY): El programa está en condición de ser ejecutado (pasar al estado En Ejecución) pero no lo está ya que se está ejecutando otro proceso temporalmente en la CPU.
3) Bloqueado (SUSPEND): El proceso no se puede ejecutar ya que se encuentra a la espera de un evento externo, incluso aunque la CPU se encuentre libre.
En el modelo de procesos conviven procesos de usuario con procesos del sistema. La parte del sistema operativo encarga de realizar la conmutación entre procesos, y de esta forma repartir la utilización de la CPU, es el planificador, el cual tiene una enorme importancia en el funcionamiento óptimo del sistema.
El modelo de procesos se implementa en el sistema
operativo mediante una tabla de procesos, con una entrada
por cada proceso. Cada entrada contiene información sobre
el estado del proceso, el contador de programa (PC), el puntero
de pila (SP), la asignación de memoria, el estado de los
archivos abiertos, información contable, información
sobre la planificación del proceso, y otros datos a conservar
al producirse el cambio de contexto de proceso. En general son
datos sobre la administración del proceso, la administración
de memoria y la administración de archivos.
A continuación se presentan los campos más
habituales que suelen encontrarse en la tabla de procesos en el
núcleo de un sistema operativo ([BAC86] y [TAN93]) :
Administración de Procesos | Administración de Memoria | Administración de Archivos |
- Identificador de proceso | - Puntero a segmento de texto | - Máscara de archivos |
- Contador de programa (PC) | - Puntero a segmento de datos | - Directorio raíz |
- Palabra de estado | - Puntero a segmento de pila | - Directorio de trabajo |
- Puntero de Pila (SP) | - Estado de salida | - Descriptores de archivo |
- Registros generales | - Identificador de proceso | - Identificador usuario efectivo |
- Estado del Proceso | - Proceso padre | - Identificador grupo efectivo |
- Máscara de señales pendientes | - Grupo de procesos | - Parámetros llamadas al sistema |
- Tiempo de inicio del proceso | - Identificador usuario real | - Máscara de señales |
- Tiempo de utilización de CPU | - Identificador usuario efectivo | |
- Tiempo de CPU del hijo | - Identificador grupo real | |
- Puntero a la cola de mensajes | - Identificador grupo efectivo |
La ilusión de varios procesos ejecutándose concurrentemente en una sola CPU con varios dispositivos de E/S se realiza de la siguiente forma :
- Cada clase de dispositivo (discos duros, discos flexibles, reloj, terminal) tiene asociado una zona de memoria que se llama vector de interrupción, la cual contiene la dirección del procedimiento de servicio de la interrupción. Cuando se produce una interrupción, el contador de programa y la palabra de estado del proceso actual en ejecución son enviados a la pila por el hardware de la interrupción. Entonces, la máquina salta a la dirección indicada en el vector de interrupción correspondiente. Esto es lo que realiza el hardware.
- El procedimiento de servicio de la interrupción guarda los registros en la entrada de la tabla de procesos correspondiente al proceso activo, se elimina la información depositada por el hardware en la pila y se llama a la rutina que procesa la interrupción.
- Después se debe encontrar el proceso que inició la solicitud y que estará a la espera de la interrupción. Normalmente dicho proceso estará en estado de bloqueado, por lo que debe ser despertado, para lo cual se pasa al estado listo, y a continuación se llama al planificador.
- El planificador se encargará de decidir qué proceso pasa a ejecutarse a continuación según el algoritmo de planificación implementado.
- Se inicia el proceso activo seleccionado por el planificador.
Estas acciones se realizan constantemente en el sistema, así pues, se debe intentar optimizar al máximo y reducir el tiempo empleado en esta tarea. Otras veces el cambio de proceso activo se debe a una interrupción temporal, ya que normalmente un proceso activo tiene un quantum de tiempo asignado, de tal forma que tras haber consumido ese tiempo de ejecución, el proceso es desalojado de forma similar a la explicada para el manejo de una interrupción. En realidad, lo que se produce es una interrupción del reloj (que es periódica).
Al proceso explicado se le suele llamar cambio de contexto o context-switch, ya que lo que en realidad ocurre es que se pasa de ejecutar un proceso a ejecutar otro, todo de una forma transparente y rápida.
Parece claro que a pesar de los avances tecnológicos conseguidos en los últimos años, la tecnología del silicio está llegando a su límite. Si se quieren resolver problemas más complejos y de mayores dimensiones se deben buscar nuevas alternativas tecnológicas. Una de estas alternativas en desarrollo es el paralelismo. Mediante el paralelismo se pretende conseguir la distribución del trabajo entre las diversas CPU disponibles en el sistema de forma que realicen el trabajo simultáneamente, con el objetivo de aumentar considerablemente el rendimiento total.
Para que dos programas se puedan ejecutar en paralelo se deben verificar ciertas condiciones, que se presentan a continuación :
- Sea Ii el conjunto de todas las variables de entrada necesarias para ejecutar el proceso Pi.
- Sea Oi el conjunto de todas las variables de salida generadas por el proceso Pi.
Las condiciones de Bernstein para dos procesos P1 y P2 son las siguientes :
Si se cumplen las tres condiciones entonces se dice que P1 y P2 pueden ser ejecutados en paralelo y se denota como P1 || P2. Esta relación de paralelismo es conmutativa (P1 || P2 ==> P2 || P1) pero no es transitiva (P1 || P2 y P2 || P3 =/=> P1 || P3).
Las condiciones de Bernstein aunque definidas para procesos son extrapolables al nivel de instrucciones.
Para conseguir un buen nivel de paralelismo es necesario que el hardware y el software se diseñen conjuntamente.
Existen dos visiones del paralelismo :
- Paralelismo hardware : Es el paralelismo definido por la arquitectura de la máquina.
- Paralelismo software : Es el paralelismo definido por la estructura del programa. Se manifiesta en las instrucciones que no tienen interdependencias.
El paralelismo se presenta, a su vez, en dos formas :
- Paralelismo de control : Se pueden realizar dos o más operaciones simultáneamente. Se presenta en los pipelines y las múltiples unidades funcionales. El programa no necesita preocuparse de este paralelismo, pues se realiza a nivel hardware.
- Paralelismo de datos : Una misma operación se puede realizar sobre varios elementos simultáneamente.
En relación al paralelismo hardware, Michael Flynn realizó la siguiente clasificación de arquitecturas de computadores :
Existen ocasiones en las que se confunde el término concurrencia con el término paralelismo. La concurrencia se refiere a un paralelismo potencial, que puede o no darse. Existen dos formas de concurrencia :
- Concurrencia implícita : Es la concurrencia interna al programa, por ejemplo cuando un programa contiene instrucciones independientes que se pueden realizar en paralelo, o existen operaciones de E/S que se pueden realizar en paralelo con otros programas en ejecución. Está relacionada con el paralelismo hardware.
- Concurrencia explícita : Es la concurrencia que existe cuando el comportamiento concurrente es especificado por el diseñador del programa. Está relacionada con el paralelismo software.
Es habitual encontrar en la bibliografía el término de programa concurrente en el mismo contexto que el de programa paralelo o distribuido. Existen diferencias sutiles entre estos conceptos :
- Programa concurrente : Es aquél que define acciones que pueden realizarse simultáneamente.
- Programa paralelo : Es un programa concurrente diseñado para su ejecución en un hardware paralelo.
- Programa distribuido : Es un programa paralelo diseñado para su ejecución en una red de procesadores autónomos que no comparten la memoria.
El término concurrente es aplicable a cualquier programa que presente un comportamiento paralelo actual o potencial. En cambio el término paralelo o distribuido es aplicable a aquel programa diseñado para su ejecución en un entorno específico.
Cuando se emplea un solo procesador para la ejecución de programas concurrentes se habla de seudoparalelismo.
Programación concurrente es el nombre dado a las notaciones y técnicas empleadas para expresar el paralelismo potencial y para resolver los problemas de comunicación y sincronización resultantes. La programación concurrente proporciona una abstracción sobre la que estudiar el paralelismo sin tener en cuenta los detalles de implementación. Esta abstracción ha demostrado ser muy útil en la escritura de programas claros y correctos empleando las facilidades de los lenguajes de programación modernos.
El problema básico en la escritura de un programa concurrente es identificar qué actividades pueden realizarse concurrentemente. Además la programación concurrente es mucho más difícil que la programación secuencial clásica por la dificultad de asegurar que el programa concurrente es correcto.
Los procesos concurrentes tienen las siguientes características [BEN82] :
- Los procesos que comparten recursos y compiten por el acceso a los mismos.
- Los procesos que se comunican entre sí para intercambiar datos.
En ambas situaciones se necesita que los procesos sincronicen su ejecución, para evitar conflictos o establecer contacto para el intercambio de datos. La interacción entre procesos se logra mediante variables compartidas o bien mediante el paso de mensajes. Además la interacción puede ser explícita, si aparece en la descripción del programa, o implícita, si aparece durante la ejecución del programa.
Los programas concurrentes a diferencia de los programas secuenciales tienen una serie de problemas muy particulares derivados de las características de la concurrencia :
En muchas ocasiones es necesario que dos procesos se comuniquen entre sí, o bien sincronicen su ejecución de tal forma que uno espere por el otro. La comunicación entre procesos se denota como IPC (InterProcess Communication).
A veces los procesos comparten un espacio de almacenamiento común (un fichero, una zona de memoria, etc.) en la que cada uno puede leer o escribir. Los problemas surgen cuando el acceso a dicha zona no está organizado, sino que es más o menos aleatorio o más bien dependiente de las condiciones de la máquina. A estas situaciones se las denomina condiciones de competencia. Se deben solucionar las condiciones de competencia, esto es, garantizar que sólo accede un proceso al mismo tiempo a la zona compartida. El objetivo es garantizar la exclusión mutua, una forma de garantizar que si un proceso utiliza una variable, archivo compartido o cualquier otro objeto compartido, los demás procesos no pueden utilizarlo.
Otra forma más abstracta de plantear el problema es pensar que normalmente un proceso realiza su tarea independientemente, pero a veces necesita acceder a una serie de recursos compartidos con otros procesos o bien debe llevar a cabo acciones críticas que pueden llevar a conflictos. A esta parte del programa se la llama sección crítica. Se debe evitar, pues, que dos procesos se encuentren en su sección crítica al mismo tiempo.
La condición de la exclusión mutua, no es suficiente para evitar todos los conflictos que se pueden producir entre procesos paralelos que cooperan y emplean datos compartidos. Existen cuatro condiciones que se deben cumplir para obtener una buena solución :
Existen varias soluciones para garantizar estos principios. Así para garantizar la exclusión mutua tenemos las siguientes opciones :
- El algoritmo de Dekker
- El algoritmo de Peterson
- La instrucción hardware TSL : Test & Set Lock.
Las soluciones de Dekker, Peterson y TSL son correctas pero emplean espera ocupada. Básicamente lo que realizan es que cuando un proceso desea entrar en su sección crítica comprueba si está permitida la entrada o no. Si no está permitida, el proceso se queda en un bucle de espera hasta que se consigue el permiso de acceso. Esto produce un gran desperdicio de tiempo de CPU, pero pueden aparecer otros problema como la espera indefinida.
Una solución más adecuada es la de bloquear o dormir el proceso (SLEEP) cuando está a la espera de un determinado evento, y despertarlo (WAKEUP) cuando se produce dicho evento. Esta idea es la que emplean las siguientes soluciones :
En los sistemas operativos tradicionales al crear un nuevo proceso (llamada fork en UNIX), lo que en realidad suele hacer el sistema es realizar una copia exacta del padre en el hijo (operación de clonación). Tenemos, entonces, dos procesos iguales.
La ineficiencia aparece cuando el proceso padre es
de un tamaño considerable, y el proceso hijo sólo
se crea para realizar una pequeña tarea y después
finalizar su ejecución, ya que es necesario volcar todo
el contenido del proceso padre en el proceso hijo. Además,
como padre e hijo son dos procesos totalmente independientes (salvo
esa relación padre-hijo), su comunicación o compartición
de datos es complicada y poco eficiente. Por último, cuando
se produce el cambio de contexto entre padre e hijo, la mayoría
de los datos no cambian, con lo que otro tipo de gestión
podría optimizar este tipo concreto de cambio de contexto.
Los hilos se emplean, en parte, para resolver y optimizar este
tipo de situaciones.