Unidad 2 Administración de procesos

2.1 DESCRIPCION Y CONTROL DE PROCESOS EN SISTEMAS OPERATIVOS

En algunos sistemas operativos como en los de tiempo compartido, cada programa que se ejecuta, por ejemplo mediante una orden de EJECUTAR dada por el usuario, se trata como un proceso independiente. Estos procesos generados por el O.S se denominan IMPLÍCITOS. Una vez terminada la ejecución de los mismos, su eliminación también la realiza el propio O.S. Asi mismo, el O.S proporciona en tiempo real los servicios que son necesarios para que el usuario pueda definir procesos de forma explicita. Los programa acceden a estos servicios realizando LLAMADAS AL SISTEMA(SYSTEM CALL). 

Estas llamadas pueden aparecer incrustadas en el código de un programa de usuario o del propio sistema, en cuyo caso, se asemejan a llamadas a procedimientos o funciones que dan lugar a transferencias de rutinas del O.S cuando se invocan en tiempo real. Las llamadas al sistema se realizan tambien, pero de forma indirecta, cuando se dan ordenes al O.S a través de un terminal(ó SHELL)la rutina de monitorización del terminal( que es asu vez un proceso) se encarga de transformar la ordenes en llamadas al sistema. 

De este modo, al comienzo de la ejecución del programa principal de un usuario se inicia la ejecución de un proceso. A su vez el proceso podría crear nuevos procesos. En este caso, el proceso que crea otro nuevo se denomina proceso padre(parent process), y el proceso creado de denomina proceso hijo(child process). Una vez creado un proceso hijo, la ejecución de padre e hijo transcurre de manera concurrente. De esta forma se puede crear una jerarquía arborescente de procesos, en la que un padre puede tener varios hijos y estos pueden tener otros hijos, etc, pero donde cada hijo sólo tiene un padre.

2.2 DEFINICION DE PROCESO

¿Qué es un proceso? 

Un proceso es un programa en ejecución. Un proceso simple tiene un hilo de ejecución, por el momento dejemos esta última definición como un concepto, luego se verá en más detalle el concepto de hilo. Una vez definido que es un proceso nos podríamos preguntar cuál es la diferencia entre un programa y un proceso, y básicamente la diferencia es que un proceso es una actividad de cierto tipo que contiene un programa, entradas salidas y estados. 

Los procesos pueden ser cooperantes o independientes, en el primer caso se entiende que los procesos interactúan entre sí y pertenecen a una misma aplicación. En el caso de procesos independientes en general se debe a que no interactúan y un proceso no requiere información de otros o bien porque son procesos que pertenecen a distintos usuarios.

Estados de los procesos

Un proceso puede estar en cualquiera de los siguientes tres estados: Listo, En ejecución y Bloqueado.

Los procesos en el estado listo son los que pueden pasar a estado de ejecución si el planificador los selecciona. Los procesos en el estado ejecución son los que se están ejecutando en el procesador en ese momento dado. Los procesos que se encuentran en estado bloqueado están esperando la respuesta de algún otro proceso para poder continuar con su ejecución. Por ejemplo operación de E/S.

2.3 ESTADOS DE PROCESOS

Operaciones con procesos

Los sistemas que administran procesos deben ser capaces de realizar ciertas operaciones sobre y con los procesos. Tales operaciones incluyen:

- crear y destruir un proceso

- suspender y reanudar un proceso

- cambiar la prioridad de un proceso

- bloquear y "desbloquear" un proceso

- planificar un proceso (asignarle la CPU)

- permitir que un proceso se comunique con otro (a esto se denomina comunicación entre procesos, y se  estudiará en el tema de procesos concurrentes).

Crear un proceso implica muchas operaciones, tales como:

- buscarle un identificador

- insertarlo en la tabla de procesos

- determinar la prioridad inicial del proceso

- crear el PCB asignar los recursos iniciales al proceso

Un proceso puede crear un nuevo proceso. Si lo hace, el proceso creador se denomina proceso padre, y el proceso creado, proceso hijo. Sólo se necesita un padre para crear un hijo. Tal creación origina una estructura jerárquica de procesos, en la cual cada hijo tiene sólo un padre, pero un padre puede tener muchos hijos. En el sistema operativo UNIX la llamada al sistema ‘fork’ crea un proceso hijo.

Destruir un proceso implica eliminarlo del sistema. Se le borra de las tablas o listas del sistema, sus recursos se devuelven al sistema y su PCB se borra (es decir, el espacio de memoria ocupado por su PCB se devuelve al espacio de memoria disponible). La destrucción de un proceso es más difícil cuando éste ha creado otros procesos. En algunos sistemas un proceso hijo se destruye automáticamente cuando su padre es destruido; en otros sistemas, los procesos creados son independientes de su padre y la destrucción de este último no tiene efecto sobre sus hijos.

Un proceso suspendido o bloqueado no puede proseguir sino hasta que lo reanuda otro proceso. La suspensión es una operación importante, y ha sido puesta en práctica de diferentes formas en diversos sistemas. La suspensión dura por lo normal sólo periodos breves. Muchas veces, el sistema efectúa las suspensiones para eliminar temporalmente ciertos procesos, y así reducir la carga del sistema durante una situación de carga máxima. Cuando hay suspensiones largas se debe liberar los recursos del proceso. La decisión de liberar o no los recursos depende mucho de la naturaleza de cada recurso. La memoria principal debe ser liberada de inmediato cuando se suspenda un proceso; una unidad de cinta puede ser retenida brevemente por un proceso suspendido, pero debe ser liberada si el proceso se suspende por un periodo largo o indefinido. Reanudar (o activar) un proceso implica reiniciarlo a partir del punto en el que se suspendió.

Cambiar la prioridad de un proceso normalmente no implica más que modificar el valor de la prioridad en el PCB.

Suspensión y reanudación

Algunas líneas más arriba se presentaron los conceptos de suspensión y reanudación de un proceso. Estas operaciones son importantes por diversas razones.

Si un sistema está funcionando mal, y es probable que falle, se puede suspender los procesos activos para reanudarlos cuando se haya corregido el problema.

Un usuario que desconfíe de los resultados parciales de un proceso puede suspenderlo (en lugar de abortarlo) hasta que verifique si el proceso funciona correctamente o no.

Algunos procesos se pueden suspender como respuesta a las fluctuaciones (bajas y altas) a corto plazo de la carga del sistema, y reanudarse cuando las cargas vuelvan a niveles normales.

Interpretación de la figura. Como podemos observar en esta figura tenemos una serie de transiciones posibles entre estados de proceso, representados mediante una gama de colores. Estos colores hay que interpretarlos de forma que, el color del borde de los estados representa a dichos estados, los colores dentro de los circulos nos dicen las posibles alternativas de acceso hacia otro estado, y los colores de las flechas nos representan hacia que estado nos dirigimos si seguimos la misma. 

2.4 CONTROL DE PROCESOS

Un sistema de control del proceso puede definirse como un sistema de realimentación de la información en el que hay 4 elementos fundamentales:

Proceso

Por proceso entendemos la combinación global de personas, equipo, materiales utilizados, métodos y medio ambiente, que colaboran en la producción. El comportamiento real del proceso -la calidad de la producción y su eficacia productiva- dependen de la forma en que se diseñó y construyó, y de la forma en que es administrado. El sistema de control del proceso sólo es útil si contribuye a mejorar dicho comportamiento. 

Información Sobre el Comportamiento

El proceso de producción incluye no solo los productos producidos, sino también los “estados” intermedios que definen el estado operativo del proceso tales como temperaturas, duración de los ciclos, etc. Si esta información se recopila e interpreta correctamente, podrá indicar si son necesarias medidas para corregir el proceso o la producción que se acaba de obtener. No obstante, si no se toman las medidas adecuadas y oportunas, todo el trabajo de recogida de información será un trabajo perdido. 

Actuación Sobre el Proceso

Las actuaciones sobre el proceso están orientadas al futuro, ya que se toman en caso necesario para impedir que éste se deteriore. Estas medidas pueden consistir en la modificación de las operaciones (por ejemplo, instrucciones de operarios, cambios en los materiales de entrada, etc) o en los elementos básicos del proceso mismo (por ejemplo, el equipo -que puede necesitar mantenimiento, o el diseño del proceso en su conjunto- que puede ser sensible a los cambios de temperatura o de humedad del taller). Debe llevarse un control sobre el efecto de estas medidas, realizándose ulteriores análisis y tomando las medidas que se estimen necesarias. 

Actuación sobre la Producción 

Las actuaciones sobre la producción están orientadas al pasado, porque la misma implica la detección de productos ya producidos que no se ajustan a las especificaciones.

Si los productos fabricados no satisfacen las especificaciones, será necesario clasificarlos y retirar o reprocesar aquellos no conformes con las especificaciones.

Este procedimiento deberá continuar hasta haberse tomado las medidas correctoras necesarias sobre el proceso y haberse verificado las mismas, o hasta que se modifiquen las especificaciones del producto.

Es obvio que la inspección seguida por la actuación únicamente sobre la producción es un pobre sustituto de un rendimiento eficaz del proceso desde el comienzo. El Control del Proceso centra la atención en la recogida y análisis de información sobre el proceso, a fin de que puedan tomarse medidas para perfeccionar el mismo. 

Hay dos formas diferentes de diseño y análisis de sistemas de control que utilizan herramientas estadísticas : 

• Control Estadístico de Proceso (CEP) del que trata este manual. 

• Control adaptativo, que utiliza lazos de retroalimentación para predecir futuros valores de las variables de proceso. Este control dice cuando hay que corregir para mantener a las variables con oscilaciones mínimas alrededor de los valores objetivos y está basado en el Análisis de series Temporales (Box-Jenkins). 

Este tipo de control puede implementarse mediante sistemas de control automático digital (caso más habitual) o mediante gráficos de control.

En sucesivo nos referiremos únicamente al Control Estadístico del Proceso.

2.5 PROCESOS E HILOS

Unidad mínima de asignación: tarea.

Unidad mínima de expedición: hilo.

Dos hilos de una misma tarea (denominados hilos pares) comparten el segmento de código, el segmento de datos y un espacio de pila, es decir, los recursos asignados a la tarea. 

Podemos captar la funcionalidad de los hilos si comparamos el control de múltiples hilos con el control de múltiples procesos. En el caso de los procesos, cada uno opera independientemente de los otros; cada proceso tiene su propio contador de programa, registro de pila, y espacio de direcciones. Este tipo de organización es muy útil cuando los trabajos que los procesos efectúan no tienen ninguna relación entre si. 

Pero cuando los trabajos a realizar van a necesitar, por ejemplo, la llamada a una misma función o bien, la compartición de una variable en memoria, nos interesará englobarlos en una tarea. Ej: Avion-Torre.

Cuando un hilo está en ejecución, posee el acceso a todos los recursos que tiene asignados la tarea.

Un hilo tendrá lo siguiente:

Estado.

• Contexto del procesador. Punto en el que estamos ejecutando, la instrucción concretamente en la que nos hallamos. Es útil a la hora de reanudar un hilo que fue interrumpido con anterioridad, puesto que al guardar el contexto, guardamos la ultima instrucción que ejecutamos, y así podemos conocer por donde tenemos que continuar la ejecución del hilo.

• Pila de ejecución donde se irá metiendo y sacando instrucciones. (Lugar donde almacenaremos las instrucciones que van a ser ejecutadas).

• Espacio de almacenamiento estático donde almacenará las variables.

• Acceso a los recursos de la tarea, que son compartidos por todos los hilos de la tarea.

Ventajas del uso de hilos.

• Se tarda menos tiempo en crear un hilo de una tarea existente que en crear un nuevo proceso.

• Se tarda menos tiempo en terminar un hilo que en terminar un proceso.

• Se tarda menos tiempo en cambiar entre dos hilos de una misma tarea que en cambiar entre dos procesos (porque los recursos no cambian, por ejemplo)

• Es mas sencillo la comunicación (paso de mensajes por ejemplo) entre hilos de una misma tarea que entre diferentes procesos.

• Cuando se cambia de un proceso a otro, tiene que intervenir el núcleo del sistema operativo para que haya protección. Cuando se cambia de un hilo a otro, puesto que la asignación de recursos es la misma, no hace falta que intervenga el sistema operativo.

2.6 CONCURRENCIA EXCLUSION MUTUA Y SINCRONIZACION

Los temas fundamentales del diseño de sistemas operativos están relacionados con la gestión de procesos e hilos:

• Multiprogramación: consiste en la gestión de varios procesos dentro de un sistema mono-procesador.

• Multiprocesamiento: consiste en la gestión de varios procesos, dentro de un sistema multiprocesador.

• Procesamiento distribuido: consiste en la gestión de varios procesos, ejecutándose en sistemas de computadores múltiples y distribuidos. La reciente proliferación de las agrupaciones es el principal ejemplo de este tipo de sistemas.

La concurrencia es fundamental en todas estas áreas y para el diseño sistemas operativos. La concurrencia comprende un gran número de cuestiones de diseño, incluida la comunicación entre procesos, compartición y competencia por los recursos, sincronización de la ejecución de varios procesos y asignación del tiempo de procesador a los procesos. Se verá que estas cuestiones no solo surgen en entornos de multiprocesadores y proceso distribuido, sino incluso en sistemas multiprogramados con un solo procesador.

La concurrencia puede presentarse en tres contextos diferentes:

• Múltiples aplicaciones: la multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varias aplicaciones activas.

• Aplicaciones estructuradas: como ampliación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.

• Estructura del sistema operativo: las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos o hilos.

2.7 PRINCIPIOS GENERALES DE LA CONCURRENCIA

En un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo aparentando una ejecución simultánea. Aunque no se logra un procesamiento paralelo y produce una sobrecarga en los intercambios de procesos, la ejecución intercalada produce beneficios en la eficiencia del procesamiento y en la estructuración de los programas.

La intercalación y la superposición pueden contemplarse como ejemplos de procesamiento concurrente en un sistema monoprocesador, los problemas son consecuencia de la velocidad de ejecución de los procesos que no pueden predecirse y depende de las actividades de otros procesos, de la forma en que el sistema operativo trata las interrupciones surgen las siguientes dificultades:

1. Compartir recursos globales es riesgoso 

2. Para el sistema operativo es difícil gestionar la asignación óptima de recursos. 

Las dificultades anteriores también se presentan en los sistemas multiprocesador.

El hecho de compartir recursos ocasiona problemas, por esto es necesario proteger a dichos recursos.

Los problemas de concurrencia se producen incluso cuando hay un único procesado

LABORES DEL SISTEMA OPERATIVO 

Elementos de gestión y diseño que surgen por causa de la concurrencia:

1) El sistema operativo debe seguir a los distintos procesos activos 

2) El sistema operativo debe asignar y retirar los distintos recursos a cada proceso activo, entre estos se incluyen:

 Tiempo de procesadorü 

 Memoriaü

 Archivosü 

 Dispositivos de E/Sü

3) El sistema operativo debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos.

4) Los resultados de un proceso deben ser independientes de la velocidad a la que se realiza la ejecución de otros procesos concurrentes.

Para abordar la independencia de la velocidad debemos ver las formas en las que los procesos interactúan.

INTERACCIÓN ENTRE PROCESOS

Se puede clasificar los en que interactúan los procesos en función del nivel de conocimiento que cada proceso tiene de la existencia de los demás. Existen tres niveles de conocimiento:

1) Los procesos no tienen conocimiento de los demás: son procesos independientes que no operan juntos. Ej: la multiprogramación de procesos independientes. Aunque los procesos no trabajen juntos, el sistema operativo se encarga de la "competencia" por los recursos.

2) Los procesos tienen un conocimiento indirecto de los otros: los procesos no conocen a los otros por sus identificadores de proceso, pero muestran cooperación el objeto común. 

3) Los procesos tienen conocimiento directo de los otros: los procesos se comunican por el identificador de proceso y pueden trabajar conjuntamente.

Competencia entre procesos por los recursos

Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso; dos o más procesos necesitan acceder a un recurso durante su ejecución .Cada proceso debe dejar tal y como esté el estado del recurso que utilice.

La ejecución de un proceso puede influir en el comportamiento de los procesos que compiten. Por Ej. Si dos procesos desean acceder a un recurso, el sistema operativo le asignará el recurso a uno y el otro tendrá que esperar.

Cuando hay procesos en competencia, se deben solucionar tres problemas de control: la necesidad de exclusión mutua. Suponiendo que dos procesos quieren acceder a un recurso no compartible. A estos recursos se les llama "recursos críticos" y la parte del programa que los utiliza es la "sección crítica” del programa. Es importante que sólo un programa pueda acceder a su sección crítica en un momento dado.

Hacer que se cumpla la exclusión mutua provoca un interbloqueo.

Otro problema es la inanición si tres procesos necesitan acceder a un recurso, P1 posee al recurso, luego lo abandona y le concede el acceso al siguiente proceso P2, P1 solicita acceso de nuevo y el sistema operativo concede el acceso a P1 YP2 alternativamente, se puede negar indefinidamente a P3 el acceso al recurso.

El control de competencia involucra al sistema operativo, porque es el que asigna los recursos.

• Cooperación entre procesos por compartimiento 

Comprende los procesos que interactúan con otros sin tener conocimiento explícito de ellos. Ej. : Varios procesos pueden tener acceso a variables compartidas.

Los procesos deben cooperar para asegurar que los datos que se comparten se gestionan correctamente. Los mecanismos de control deben garantizar la integridad de los datos compartidos.

• Cooperación entre procesos por comunicación 

Los distintos procesos participan en una labor común que une a todos los procesos.La comunicación sincroniza o coordina las distintas actividades, está formada por mensajes de algún tipo. Las primitivas para enviar y recibir mensajes, vienen dadas como parte del lenguaje de programación o por el núcleo del sistema operativo.

REQUISITOS PARA LA EXCLUSIÓN MUTUA 

1. Sólo un proceso, de todos los que poseen secciones críticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado. 

2. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin interferir con los otros procesos. 

3. Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanición. 

4. Si ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora. 

5. No se debe suponer sobre la velocidad relativa de los procesos o el número de procesadores. 

6. Un proceso permanece en su sección crítica por un tiempo finito.

Una manera de satisfacer los requisitos de exclusión mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda del lenguaje de programación o del sistema operativo. Estos métodos se conocen como soluciones por software.

2.8 EXCLUCION MUTUA: SOLUCIÓN POR HARDWARE Y SOFTWARE

EXCLUSIÓN MUTUA: SOLUCIONES POR SOFTWARE

Pueden implementarse soluciones de software para los procesos concurrentes que se ejecuten en máquinas monoprocesador o multiprocesador con memoria principal compartida.

ALGORITMO DE DEKKER

La solución se desarrolla por etapas. Este método ilustra la mayoría de los errores habituales que se producen en la construcción de programas concurrentes.

Primer intento

Cualquier intento de exclusión mutua debe depender de algunos mecanismos básicos de exclusión en el hardware. El más habitual es que sólo se puede acceder a una posición de memoria en cada instante, teniendo en cuenta esto se reserva una posición de memoria global llamada turno. Un proceso que desea ejecutar su sección crítica primero evalúa el contenido de turno. Si el valor de turno es igual al número del proceso, el proceso puede continuar con su sección crítica. En otro caso el proceso debe esperar. El proceso en espera, lee repetitivamente el valor de turno hasta que puede entrar en su sección crítica. Este procedimiento se llama espera activa.

Después de que un proceso accede a su sección crítica y termina con ella, debe actualizar el valor de turno para el otro proceso.

Segundo intento: 

Cada proceso debe tener su propia llave de la sección crítica para que, si uno de ellos falla, pueda seguir accediendo a su sección crítica; para esto se define un vector booleano señal. Cada proceso puede evaluar el valor de señal del otro, pero no modificarlo. Cuando un proceso desea entrar en su sección crítica, comprueba la variable señal del otro hasta que tiene el valor falso (indica que el otro proceso no está en su sección crítica). Asigna a su propia señal el valor cierto y entra en su sección crítica. Cuando deja su sección crítica asigna falso a su señal.

Si uno de los procesos falla fuera de la sección crítica, incluso el código para dar valor a las variables señal, el otro proceso no se queda bloqueado. El otro proceso puede entrar en su sección crítica tantas veces como quiera, porque la variable señal del otro proceso está siempre en falso. Pero si un proceso falla en su sección crítica o después de haber asignado cierto a su señal, el otro proceso estará bloqueado permanentemente.

Tercer intento

El segundo intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado pero antes de que pueda entrar en su sección crítica.

Si un proceso falla dentro de su sección crítica, incluso el código que da valor a la variable señal que controla el acceso a la sección crítica, el otro proceso se bloquea y si un proceso falla fuera de su sección crítica, el otro proceso no se bloquea.

Si ambos procesos ponen sus variables señal a cierto antes de que ambos hayan ejecutado una sentencia, cada uno pensará que el otro ha entrado en su sección crítica, generando así un interbloqueo.

Cuarto intento

En el tercer intento, un proceso fijaba su estado sin conocer el estado del otro. Se puede arreglar esto haciendo que los procesos activen su señal para indicar que desean entrar en la sección crítica pero deben estar listos para desactivar la variable señal y ceder la preferencia al otro proceso.

Existe una situación llamada bloqueo vital, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los procesos rompería este ciclo y permitiría a uno entrar en la sección crítica. Recordando que el interbloqueo se produce cuando un conjunto de procesos desean entrar en sus secciones críticas, pero ninguno lo consigue. Con el bloqueo vital hay posibles secuencias de ejecución con éxito.

Una solución correcta

Hay que observar el estado de ambos procesos, que está dado por la variable señal, pero es necesario imponer orden en la actividad de los procesos para evitar el problema de "cortesía mutua". La variable turno del primer intento puede usarse en esta labor, indicando que proceso tiene prioridad para exigir la entrada a su sección crítica.

ALGORITMO DE PETERSON

El algoritmo de Deker resuelve el problema de la exclusión mutua pero mediante un programa complejo, difícil de seguir y cuya corrección es difícil de demostrar. Peterson ha desarrollado una solución simple y elegante. Como antes, la variable global señal indica la posición de cada proceso con respecto a la exclusión mutua y la variable global turno resuelve los conflictos de simultaneidad.

Considérese el proceso P0. Una vez que ha puesto señal[0] a cierto, P1 no puede entrar en su sección crítica. Si P1 esta aun en su sección crítica, entonces señal[1] = cierto y P0 está bloqueado en su bucle while. Esto significa que señal[1] es cierto y turno = 1. P0 puede entrar en su sección crítica cuando señal[1] se ponga a falso o cuando turno se ponga a 0. Considérense ahora los siguientes casos exhaustivos:

1. P1 no está interesado en entrar en su sección crítica. Este caso es imposible porque implica que señal[1] = falso. 

2. P1 está esperando entrar en su sección crítica. Este caso es también imposible porque si turno = 1, P1 podría entrar en su sección crítica. 

3. P1 entra en su sección crítica varias veces y monopoliza el acceso a ella. Esto no puede pasar porque P1 está obligado a dar a P0 una oportunidad poniendo turno a 0 antes de cada intento de entrar en su sección crítica. 

Así pues, se tiene una solución posible al problema de la exclusión mutua para dos procesos. Es más, el algoritmo de Peterson se puede generalizar fácilmente al caso de n procesos.

Disciplina de cola

La disciplina de cola mas simple es la de primero en llegar/ primero en salir, pero ésta puede no ser suficiente si algunos mensajes son mas urgentes que otros. Una alternativa es permitir la especificación de prioridades de los mensajes, en función del tipo de mensaje o por designación del emisor. Otra alternativa es permitir al receptor examinar la cola de mensajes y seleccionar el mensaje a recibir a continuación.

Exclusión mutua

Supóngase que se usan primitivas receive bloqueantes y send no bloqueantes. Un conjunto de procesos concurrentes comparten un buzón, exmut, que puede ser usado por todos los procesos para enviar y recibir. El buzón contiene inicialmente un único mensaje, de contenido nulo. Un proceso que desea entrar en su sección crítica intenta primero recibir el mensaje. Si el buzón está vacío, el proceso se bloquea. Una vez que un proceso ha conseguido el mensaje, ejecuta su sección crítica y, después, devuelve el mensaje al buzón. De este modo, el mensaje funciona como testigo que se pasa de un proceso a otro.

Esta técnica supone que si hay más de un proceso ejecutando la acción receive concurrentemente, entonces:

• Si hay un mensaje, se entrega sólo a uno de los procesos y los otros se bloquean. 

• Si el buzón está vacío, todos los procesos se bloquean; cuando haya un mensaje disponible, sólo se activará y tomará el mensaje uno de los procesos bloqueados. 

EXCLUSIÓN MUTUA: SOLUCIONES POR HARDWARE

INHABILITACIÓN DE INTERRUPCIONES 

En una máquina monoprocesador, la ejecución de procesos concurrentes no puede superponerse; los procesos solo pueden intercalarse. Es más, un proceso continuará ejecutándose hasta que solicite un servicio el sistema operativo o hasta que sea interrumpido. Por lo tanto, para garantizar la exclusión mutua, es suficiente con impedir que un proceso sea interrumpido. Esta capacidad puede ofrecerse en forma de primitivas definidas por el núcleo del sistema para habilitar o inhabilitar las interrupciones.

INSTRUCCIONES ESPECIALES DE MAQUINA 

En configuraciones multiprocesador, varios procesadores comparten el acceso a una memoria principal común. En este caso, no hay relación maestro/esclavo, sino que los procesadores funcionan independientemente en una relación de igualdad. No hay un mecanismo de interrupciones entre los procesadores en el que se pueda basar la exclusión mutua.

A nivel de hardware, como se ha mencionado, los accesos a posiciones de memoria excluyen cualquier otro acceso a la misma posición. Con esta base, los diseñadores han propuesto varias instrucciones de máquina que realizan dos acciones atómicamente, tales cono leer y escribir o leer y examinar, sobre una misma posición de memoria en un único ciclo de lectura de instrucción.

Puesto que estas acciones se realizan en un único ciclo de instrucción, no están sujetas a injerencias por parte de otras instrucciones.

2.9 SEMAFOROS

Semáforos es un algoritmo de control de procesos, que tiene solo dos operaciones básicas, las cuales son: 

Wait.- Pregunta a los procesos si su contador es > ó = que cero, en caso de no ser así, los decrementa. El proceso que cambia en este caso a negativo (−1) desde la cola de procesos Listos a ser ejecutados es el que automáticamente toma el control del procesador. 

Signal.- A partir de un tiempo t definido por el despachador se ejecuta, y pregunta a los procesos si su contador es < que cero en caso de que sea afirmativa la respuesta, saca a este proceso de su ejecución y depende de su estado.

La concurrencia puede presentarse en tres contextos diferentes:

• Múltiples aplicaciones: la multiprogramación se creó para permitir que el tiempo de procesador de la máquina fuese compartido dinámicamente entre varias aplicaciones activas.

• Aplicaciones estructuradas: como ampliación de los principios del diseño modular y la programación estructurada, algunas aplicaciones pueden implementarse eficazmente como un conjunto de procesos concurrentes.

• Estructura del sistema operativo: las mismas ventajas de estructuración son aplicables a los programadores de sistemas y se ha comprobado que algunos sistemas operativos están implementados como un conjunto de procesos o hilos.

2.10 MONITORES SISTEMAS OPERATIVOS

Un monitor encapsula el código relativo a un recurso compartido en un solo módulo de programa; ventajas:

 

 Mantenimiento más simple

 Menos errores de programación 

 La interfaz del monitor es un conjunto de funciones que representan las diferentes operaciones que pueden hacerse con el recurso 

 La implementación del monitor garantiza la exclusión mutua

2.11 PASO DE MENSAJES SISTEMAS OPERATIVOS

Paso de mensajes 

El paso de mensajes es una técnica empleada en programación concurrente para aportar sincronización entre procesos y permitir la exclusión mutua, de manera similar a como se hace con los semáforos, monitores, etc. 

Su principal característica es que no precisa de memoria compartida, por lo que es muy importante en la programación para sistemas distribuidos. 

Los elementos principales que intervienen en el paso de mensajes son el proceso que envía, el que recibe y el mensaje.

2.12 CONCURRENCIA E INTERBLOQUEO DEADLOCK 

DEADLOCK

Los procesos no son ejecutados constantemente desde que se inician hasta que son finalizados.

Un proceso puede estar identificado con tres estados diferentes: leyendo (ready), ejecutando (running) o bloqueado (blocked). En el estado de lectura, Un proceso está parado, concediendo que otro proceso sea ejecutado; en el estado de ejecución, un proceso está utilizando algún recurso; y en el estado de bloqueo, el proceso está parado y no se ejecutará mientras algo lo restaure.

Una condición común no deseable es descripta como deadlock, que es cuando dos procesos están en un estado de ejecución, y requieren intercambiar recursos entre sí para continuar. Ambos procesos están esperando por la liberación del recurso requerido, que nunca será realizada; como no hay ningún resultado, tomará un camino que llevará a un estado de deadlock.

Muchos escenarios han sido construidos para ilustrar las condiciones de deadlock, siendo el más popular el Problema de Comida de los Filósofos. Cinco filósofos tienen cinco platos de fideos enfrente suyo y cinco tenedores, uno a cada lado del plato. Los filósofos necesitan ambos tenedores (derecha e izquierda) para comer. Durante la comida realizarán solo dos operaciones mutuamente excluyentes, pensar o comer. El problema es un paralelismo simplista entre procesos (los filósofos) tratando de obtener recursos (tenedores); mientras están en estado de ejecución (comiendo) o de lectura (pensando). Una condición posible de deadlock puede ocurrir, si todos los filósofos quieren coger el tenedor de la derecha y, a la vez, el de la izquierda: la comida terminará en estado de deadlock.

Se dice que dos procesos se encuentran en estado de deadlock (interbloqueo, bloqueo mutuo o abrazo mortal) cuando están esperando por condiciones que nunca se van a cumplir. Se podría hablar de deadlock como el estado permanente de bloqueo de un conjunto de procesos que están compitiendo por recursos del sistema.

2.13 PRINCIPIOS DEL INTERBLOQUEO

Definición: 

El interbloqueo se puede definir como el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros. Un proceso esta interbloqueado si está esperando por un evento determinado que nunca va a ocurrir. No existe una solución eficiente para el caso general. Todos los interbloqueos suponen necesidades contradictorias de recursos por parte de dos o más procesos.

2.14 ACCIONES  REALIZAR UN INTERBLOQUEO PREVENCIÓN, DETECCIÓN, PREDICCIÓN Y EVITAR

CONDICIONES PARA PRODUCIR INTERBLOQUEO 

En la política del sistema operativo, deben darse tres condiciones para que pueda producirse un interbloqueo:

1- Condición de exclusión mutua: Cada recurso esta asignado a un único proceso o esta disponible. 

2- Condición de posesión y espera: Los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos. 

3- Condición de no apropiación: Los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita. 

En la mayoría de los casos, estas condiciones son bastantes necesarias. La exclusión mutua hace falta para asegurar la consistencia de resultados y la integridad de la base de datos. De forma similar, la apropiación no se puede aplicar arbitrariamente y, cuando se encuentran involucrados recursos de datos, debe estar acompañada de un mecanismo de recuperación y reanulación, que devuelva un proceso y sus recursos a un estado previo adecuado, desde el que el proceso puede finalmente repetir sus acciones. 

Puede no existir interbloqueo con solo estas tres condiciones. Para que se produzca interbloqueo, se necesita una cuarta condición: 

4- Condición de espera circular (o circulo vicioso de espera): Debe existir una cadena circular de dos o mas procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. 

Las tres primeras condiciones son necesarias, pero no suficientes, para que exista interbloqueo. La cuarta condición es, en realidad, una consecuencia potencial de las tres primeras. Es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un circulo vicioso de espera irresoluble. El circulo de espera de la condición 4 es irresoluble porque se mantienen las tres primeras condiciones. Las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo. 

PREVENCIÓN DEL INTERBLOQUEO 

La estrategia básica de la prevención del interbloqueo consiste, a grandes rasgos, en diseñar su sistema de manera que esté excluida, a priori, la posibilidad de interbloqueo. 

Los métodos para prevenir el interbloqueo son de dos tipos: 

- Los métodos indirectos que consisten en impedir la aparición de alguna de las tres condiciones necesarias para que se de el interbloqeo. 

- Los métodos directos que consisten en evitar la aparición del circulo vicioso de espera. 

PREDICCIÓN DEL INTERBLOQUEO 

Una forma de resolver el problema del interbloqueo, que se diferencia sutilmente de la prevención, es la predicción del interbloqueo. En la prevención de interbloqueo, se obligaba a las solicitudes de recursos a impedir que sucediera , por lo menos, alguna de las cuatro condiciones de interbloqueo. Esto se hace indirectamente, impidiendo la aparición de una de las tres condiciones necesarias (exclusión mutua, retención y espera, no apropiación) o directamente, impidiendo la aparición de un circulo viciosos de espera. Se llega así a un uso ineficiente de los recursos y una ejecución ineficiente de los procesos. Con predicción del interbloqueo, por otro lado, se pueden alcanzar las tres condiciones necesarias, pero se realizan elecciones acertadas para asegurar que nunca se llega al punto de interbloqueo. La predicción, por lo tanto, permite más concurrencia que la prevención. Con predicción del interbloqueo, se decide dinámicamente si la petición actual de asignación de un recurso podría, de concederse, llevar potencialmente a un interbloqueo. La predicción del interbloqueo necesita, por lo tanto, conocer las peticiones futuras de recursos. Enfoques para la predicción del interbloqueo: - - No iniciar un proceso si sus demandas pueden llevar a interbloqueo. - - No conceder una solicitud de incrementar los recursos de un proceso si esta asignación puede llevar a interbloqueo. 

DETECCIÓN DEL INTERBLOQUEO 

- Las estrategias de prevención de interbloqueo son muy conservadoras; resuelven el problema limitando el acceso a recursos e imponiendo restricciones sobre los procesos. En cambio, las estrategias de detección de interbloqueo, no limitan el acceso a recursos ni restringen las acciones del proceso. Con la detección del interbloqueo, se concederán los recursos que los procesos necesiten siempre que sea posible. Periódicamente, el S. O. ejecuta un algoritmo que permite detectar la condición de circulo vicioso de espera. - La detección del interbloqueo es el proceso de determinar si realmente existe un interbloqueo e identificar los procesos y recursos implicados en él. Una posibilidad detectar un interbloqueo es monitorear cada cierto tiempo el estado de los recursos. Cada vez que se solicita o se devuelve un recurso, se actualiza el estado de los recursos y se hace una verificación para observar si existe algún ciclo. - Este método está basado en suponer que un interbloqueo no se presente y que los recursos del sistema que han sido asignados, se liberarán en el momento que otro proceso lo requiera. 

- Algoritmo de detección del interbloqueo - Una comprobación para interbloqueo puede hacerse con igual o menor frecuencia que cada solicitud de recursos, dependiendo de que tan probable es que ocurra un interbloqueo. Comprobar cada solicitud de recursos tiene dos ventajas: Conduce a la detección temprana y el algoritmo es simple, de manera relativa porque se basa en cambios crecientes al estado del sistema. Además, las comprobaciones frecuentes consumen un tiempo considerable de procesador.