UNIDAD IX

Procesos y Subprocesos

PROCESOS

Definición de Proceso.

El principal concepto en cualquier sistema operativo es el de proceso.

Un proceso es un programa en ejecución, incluyendo el valor del program counter, los registros y las variables.

Conceptualmente, cada proceso tiene un hilo (thread) de ejecución que es visto como un CPU virtual.

El recurso procesador es alternado entre los diferentes procesos que existan en el sistema, dando la idea de que ejecutan en paralelo (multiprogramación).

Modelo de procesos.

El sistema operativo para permitir la multiprogramación y la concurrencia requiere de un modelo de procesos que ofrezca el soporte necesario para proveerla.

Multiprogramación: la CPU alterna de programa en programa, en un esquema de seudo-paralelismo (Paralelismo virtual).

Paralelismo real de hardware: Cuando se ejecutan las instrucciones de un programa con más de un procesador.

El modelo de procesos sirve para aumentar el paralelismo en la ejecución. Está compuesto básicamente por PCB (Process Control Block), Tabla de Procesos, Estados y transiciones de los procesos.

Creación de procesos

Los procesos de un sistema son creados a partir de otro proceso. Al creado se le denomina padre y al nuevo proceso hijo. Esto genera una jerarquía de procesos en el sistema.

En el diseño del sistema operativo se debe decidir, en el momento de creación de un nuevo proceso, cuales recursos compartirán el proceso padre e hijo. Las opciones son que compartan todo, algo o nada.

Una vez creado el nuevo proceso tendrán un hilo (pc) de ejecución propia. El sistema genera un nuevo PCB para el proceso creado.

Hay cuatro sucesos principales que causan la creación de un proceso:

1. Inicialización de un sistema.
2. ejecución de una llamada al sistema para crear procesos por parte de un proceso en ejecución.
3. Solicitud de un usuario para crear un proceso.
4. Inicio de un trabajo por lotes.

Cuando se arranca un sistema operativo, se crean varios procesos, algunos de primer plano, es decir que interactúan con usuarios y trabajan para ellos; otros de segundo plano que no están asociados con un usuario en particular, sino que tiene una función especifica, a los que se denominan demonios (daemons).

También es posible crear procesos posteriormente, emitiendo llamadas al sistema para crear unos o mas procesos que le ayuden a su labor; siendo muy útiles cuando el trabajo a realizar puede formularse con facilidad a partir de varios procesos relacionados, pero independientes, que interactúan entre si.

Terminación de Procesos

Un proceso puede terminar por varias razones:

• Terminación normal (voluntaria): ya termino su trabajo.
  UNIX exit, Win32 ExitProcess.
• Terminación por error (voluntaria): se descubre un error fatal. También usando esas llamadas al sistema, pero devolviendo un código de error indicando el fallo.
• Error fatal (involuntaria): error causado por el proceso, a menudo debido a un defecto de programa.
• Terminado por otro proceso (involuntaria): otro proceso ejecuta una llamada para pedir al SO que termine el proceso en cuestión.
  UNIX kill, Win32 TerminateProcess.

Jerarquía de procesos

Cuando un proceso crea a otro el proceso padre y el hijo mantienen cierta asociación, donde este puede crear mas procesos; y asi crear una jerarquía de procesos.

En Windows no hay jerarquía, todos los procesos son iguales.

En Unix se crea una jerarquía de árbol y los procesos padres no pueden desheredar a los hijos.

Estados de los procesos

El estado de un proceso es definido por la actividad corriente en que se encuentra.

Los 3 estados principales (ejecutando, Listo y bloqueado) proveen una forma sistemática de modelar el comportamiento, y muchos sistemas de operación utilizan solo estos 3 estados, hay sistemas de operación que añaden dos mas como lo es el caso de Unix.

• Nuevo (new): Cuando el proceso es creado.
• Ejecutando (running): El proceso tiene asignado un procesador y está ejecutando sus instrucciones.
• Bloqueado (waiting): El proceso está esperando por un evento (que se complete un pedido de E/S o una señal).
• Listo (ready): El proceso está listo para ejecutar, solo necesita del recurso procesador.
• Finalizado (terminated): El proceso finalizó su ejecución.

Implementación de procesos

Para implementar el modelo de procesos, el sistema operativo mantiene una tabla de procesos, con una entrada por procesos, la cual contiene información acerca del estado del proceso, su contador de programa, apuntador de pila, asignación de memoria, estado de sus archivos abiertos, información contable y de calendarización y demás cosas que se guardan cuando el proceso pasa de estado en ejecución a bloqueado.

La ilusión de múltiples procesos secuenciales en una maquina con una CPU y muchos dispositivos de E/S: cada clase de dispositivo de E/S esta asociado a una posición de memoria llamada vector de interrupción. Resumido a continuación:

• El hardware mete el contador de programa en la pila. Etc.
• Carga un nuevo contador de programa tomándolo del vector de interrupción.
• Un procedimiento en ensamblador guarda registros.
• Un procedimiento en ensamblador crea la nueva pila.
• Se ejecuta el servicio de interrupción C.
• El calendarizador decide que programa ejecutara ahora.
• El procedimiento en C regresa al código en ensamblador.
• Un procedimiento en ensamblador arranca el nuevo proceso actual.

Los detalles varían de un sistema a otro.

SUBPROCESOS

Los sistemas operativos utilizan procesos para independizar las diferentes aplicaciones que ejecutan. Los subprocesos son la unidad básica a la que el sistema operativo asigna tiempo de procesador. Puede que haya más de un subproceso ejecutando código dentro del proceso. Cada subproceso mantiene controladores de excepciones, una prioridad de programación y un conjunto de estructuras que el sistema utiliza para guardar el contexto del subproceso hasta que se programe. El contexto del subproceso incluye, en el espacio de direcciones del proceso host del subproceso, toda la información que necesita éste para reanudar sin problemas la ejecución.

Se subdivide un proceso de sistema operativo en uno o varios subprocesos administrados (representado por System.AppDomain) en uno o varios denominados dominios de aplicación. Aunque cada dominio de aplicación se inicia con un único subproceso, su código puede crear otros dominios de aplicación y subprocesos adicionales. El resultado es que un subproceso administrado puede moverse libremente entre dominios de aplicación dentro del mismo proceso administrado; podría tener sólo un subproceso que se moviera entre varios dominios de aplicación.

Un sistema operativo que admita multitareas prioritarias crea el efecto de ejecución simultánea de varios subprocesos desde varios procesos. Para ello, se divide el tiempo de procesador disponible entre los subprocesos que lo necesitan y se asigna un espacio de tiempo de procesador a cada subproceso, uno tras otro. Cuando trascurre su espacio de tiempo, el subproceso que se esté ejecutando actualmente se suspende y otro subproceso reanuda su ejecución

El espacio de tiempo asignado depende del sistema operativo y del procesador. Puesto que cada espacio de tiempo es pequeño, parece que se ejecutan varios subprocesos a la vez, incluso si hay un único procesador. De hecho, éste es el caso en sistemas multiprocesador, donde los subprocesos ejecutables se distribuyen entre los procesadores disponibles.

Implementación de subprocesos en espacio de usuario.

Puede implementarse un sistema de subprocesos en el nivel de usuario en un sistema operativo que no maneje subprocesos.

Cada proceso necesita su propia tabla de subprocesos privada para dar seguimiento a sus subprocesos. La tabla es administrada por el sistema de tiempo de ejecución. Cuando un subprocesos pasa al estado listo o al desbloqueado, en la tabla de subprocesos se guarda la información necesaria para reiniciarlo

También permite que cada proceso tenga su propio algoritmo de calendarización personalizado. En algunas aplicaciones, como las que tiene un subproceso recolector de basura, es una ventaja no tener que preocuparse porque un subproceso vaya a detenerse en un momento no conveniente. Además, es más fácil aumentar se escala, pues los procesos de kernel siempre requieren espacio de tabla y de pila de kernel, y esto puede ser problemático si hay un gran número de ellos.

A pesar de su buen desempeño, los sistemas de subprocesos en el nivel de usuario tienen problemas importantes.

El principal es la manera en que se implementan las llamadas bloqueadoras al sistema. Supongamos que algún subproceso lee del teclado antes de que se oprima alguna tecla. No es posible permitirle al subproceso que emite en realidad la llamada al sistema, pues eso detentría a todos los subprocesos. Uno de los principales objetivos de tener subprocesos es precisamente que todos puedan usar llamadas bloqueadoras, pero sin afectarse entre sì.

Otro problema es el de fallos de página. Las computadoras pueden organizarse de tal manera que no todo el programa esté en memoria principal a la vez. Si el programa salta a una instrucción que no está en la memoria, ocurre un fallo de página y el sistema operativo. trae la instrucción faltante del disco. El proceso se bloquea mientras se localiza la instrucción necesaria.

Otro problema es que si un subproceso comienza a ejecutarse, ningún otro subproceso de ese proceso podrá ejecutarse si el primero no cede de manera voluntaria la CPU. Dentro de un procesos sado no hay interrupciones de reloj.

Implementación de subprocesos en el kernel.

En este caso el kernel esta enterado de la existencia de subprocesos y los puede administrar. No se necesita un sistema de tiempo de ejecución en cada uno. Cuando un subproceso quiere crear o destruir otro subproceso, emite una llamada al kernel, que se encarga de crearlo o destruirlo de su tabla de subprocesos.

La tabla de subprocesos del kernel contiene los registros, el estado, e información de cada subproceso.

Todas las llamadas que podrían bloquear a un subproceso se implementan como llamadas al sistema y tienen un costo mucho mayor que las llamadas a procedimientos de un sistema de tiempo de ejecución. Cuando un subproceso se bloquea, el kernel a criterio propio, puede ejecutar otro subproceso del mismo proceso (si hay uno listo) o alguno de otro proceso.

Debido al costo mayor de crear y destruir subprocesos en el kernel, algunos sistemas adoptan un enfoque de reciclado de subprocesos. Cuando un subproceso se destruye, se marca como no ejecutable, pero sus estructuras de datos en el kernel se mantienen.

Cuando es necesario crear un subproceso, se reactiva uno antiguo, ahorrando algo de procesamiento extra.

Si un subproceso de un proceso causa un fallo de página, el kernel puede verificar con facilidad si el proceso tiene algún otro subproceso ejecutable, y en su caso, ejecutar uno de ellos mientras espera que la página necesaria llegue al disco.

Su principal desventaja es el costo elevado de una llamada al sistema.

Si las operaciones de subprocesos (creación, terminación, etc.) son usuales, se requerirá mucho procesamiento extra.

Flavia Delgado, Magali Pintos, Celestina Goi, Valeria Verajones

COMUNICACIÓN ENTRE PROCESOS

Con frecuencia, los procesos necesitan comunicarse con otros procesos. Por ejemplo, en una canalización de shell, la salida del primer proceso debe transferirse al segundo, y así hasta el final. Por tanto, es necesaria la comunicación entre procesos, de preferencia con un mecanismo bien estructurado que no utilice interrupciones. En las siguientes secciones examinaremos algunos aspectos de esta comunicación entre procesos (IPC; InterProcess Communication).

En pocas palabras, hay tres aspectos que cuidar. Ya hicimos alusión al primero: cómo puede un proceso pasar información a otro. El segundo tiene que ver con asegurarse de que dos o más procesos no se estorben al realizar actividades cruciales (supongamos que dos procesos tratan de apoderarse del último megabyte de memoria). El tercero tiene que ver con el ordenamiento correcto cuando existen dependencias: si el proceso A produce datos y el proceso B los imprime, B tendrá que esperar hasta que A haya producido algunos datos antes de comenzar a imprimir. Examinaremos estos tres aspectos a partir de la próxima sección. 

Es importante mencionar que dos de estos aspectos también se aplican a los subprocesos. El primero –la transferencia de información- es fácil para los subprocesos porque comparten un solo espacio de direcciones (los subprocesos en espacios de direcciones distintos que necesitan comunicarse se tratan como procesos en comunicación). Sin embargo, los otros dos se presentan los mismos problemas y pueden usar las mismas soluciones. A continuación analizaremos el problema en el contexto de los procesos, pero debe tener presente que los mismos problemas y soluciones se aplican a los subprocesos.

 - Condiciones de competencia

En algunos sistemas operativos, procesos que están colaborando podrían compartir un área de almacenamiento que ambos pueden leer y escribir. El almacenamiento compartido podría estar en la memoria principal (tal vez en una estructura de datos del kernel), o bien, ser un archivo compartido; la ubicación de la memoria compartida no altera la naturaleza de la comunicación ni los problemas que se presentan. Para ver cómo funciona en la práctica la comunicación entre procesos, consideremos un ejemplo sencillo pero común: el spooler de impresión. Cuando un proceso quiere imprimir un archivo, coloca su nombre en un directorio de spooler especial. Otro proceso, el demonio de impresora, ve en forma periódica si hay algún archivo por imprimir y, si lo hay, lo imprime y borra su nombre del directorio. Imaginemos que nuestro directorio de spooler tiene un gran número de ranuras, numeradas 0, 1, 2,…., cada una de las cuales puede contener un nombre de archivo. Asimismo, imaginemos que hay dos variables compartidas: out, que apunta al siguiente archivo que se imprimirá, e in, que apunta a la siguiente ranura desocupada del directorio. Estas dos variables bien podrían guardarse en un archivo de dos palabras, accesible para todos los procesos. En un momento determinado, las ranuras 0 a 3 están vacías (los archivos ya se imprimieron) y las ranuras 4 a 6 están ocupadas (con los nombres de archivos en cola para imprimirse). De forma casi simultánea, los procesos A y B deciden que quieren mandar un archivo a impresión. Esta situación se muestra en la figura 2-18.

En jurisdicciones donde impera la ley de Murphy, podría suceder lo siguiente. El proceso A lee in y guarda su valor, 7, en una variable local llamada siguiente_ranura_desocupada. Justo en ese momento hay una interrupción de reloj y la CPU decide que el proceso A ya se ejecutó durante suficiente tiempo, así que cambia al proceso B. Éste también lee in, y también obtiene un 7, valor que almacena en su variable local siguiente_ranura_desocupada. En este momento, ambos procesos creen que la siguiente ranura disponible es la 7.

Ahora el proceso B continúa su ejecución. Coloca el nombre de su archivo en la ranura 7 y actualiza in a 8. Luego se pone a hacer otras cosas. 

En algún momento, el proceso A se ejecuta otra vez, a partir del punto en donde se quedó. A continuación examina siguiente_ranura_desocupada, encuentra un 7 y escribe su nombre de archivo en la ranura 7, borrando el nombre que el proceso B acaba de poner. Después calcula siguiente_ranura_desocupada + 1, que es 8, y establece in a 8. Ahora el directorio de spooler es internamente consistente, así que el demonio de impresión no notará nada raro, pero el proceso B nunca obtendrá su salida impresa. El usuario B permanecerá en el cuarto de impresoras durante años, alimentando la esperanza de recibir una salida que nunca llegará. Situaciones como ésta, en la que dos o más procesos están leyendo o escribiendo datos compartidos y el resultado final depende de quién se ejecuta y precisamente cuándo, se denominan condiciones de competencia. No es nada divertido depurar programas que contienen condiciones de competencia. Los resultados de casi todas las pruebas son perfectos, pero de vez en cuando sucede algo raro e inexplicable.

 - Regiones críticas:
¿Cómo evitamos las condiciones de competencia? La clave para evitar problemas aquí, y en muchas otras situaciones en las que se comparte memoria, archivos o cualquier otra cosa, es hallar alguna forma de impedir que dos o más procesos lean o escriban los datos compartidos al mismo tiempo. En otras palabras, lo que necesitamos es exclusión mutua, es decir, alguna forma de asegurarnos de que si un proceso está utilizando una variable compartida o un archi­vo compartido, los demás procesos no podrán hacer lo mismo. El problema anterior se presen­tó porque el proceso B comenzó a usar una de las variables compartidas antes de que el proceso A terminara de usarla. La decisión de qué operaciones primitivas son apropiadas para lograr la exclusión mutua es una importante cuestión de diseño en cualquier sistema operativo, y es un tema que examinaremos con mucho detenimiento en las siguientes secciones.
El problema de evitar condiciones de competencia también puede formularse de manera abstracta. Una parte del tiempo, los procesos están ocupados realizando cálculos internos y otras cosas que no dan pie a condiciones de competencia. No obstante, hay ocasiones en que un proceso tiene que acceder a memoria o archivos compartidos, o realizar otras tareas críticas que pueden generar competencia. La parte del programa en la que se tiene acceso a la memo­ria compartida se denomina región crítica o sección crítica. Si pudiéramos organizar las co­sas de modo que dos procesos nunca estuvieran en sus regiones críticas al mismo tiempo, podríamos evitar las competencias.

Aunque este requisito evita las condiciones de competencia, no basta para que procesos paralelos cooperen de forma correcta y eficiente empleando datos compartidos. Necesitamos que se cumplan cuatro condiciones para tener una buena solución: 

1. Dos procesos no pueden estar al mismo tiempo dentro de sus regiones críticas.
2. No pueden hacerse suposiciones sobre las velocidades ni el número de las CPUs.
3. Ningún proceso que se esté ejecutando afuera de su región crítica puede bloquear a otros procesos.
4. Ningún proceso deberá tener que esperar de manera indefinida para entrar en su región crítica. 

En un sentido abstracto, el comportamiento que necesitamos se muestra en la figura 2-19. Aquí el proceso A entra en su región crítica en el tiempo T1. Un poco después, en el tiempo T2, el proceso B intenta ingresar en su región crítica pero no lo logra porque otro proceso ya está en su región crítica, y sólo permitimos uno a la vez. Por tanto, B se suspende en forma tempo­ral hasta el tiempo T3, cuando A sale de su región crítica y permite que B entre de inmediato. En algún momento (T4), B saldrá y estaremos de nuevo en la situación original en la que ningún proceso está en su región crítica.

3.Exclusión mutua con espera activa:

En esta sección examinaremos diversas propuestas para lograr la exclusión mutua, de modo que mientras un proceso está actualizando la memoria compartida en su región crítica, ningún otro proceso entre en su propia región crítica y cause problemas.

 - Inhabilitación de interrupciones:

La solución más sencilla es hacer que cada proceso inhabilite todas las interrupciones inmedia­tamente después de ingresar en su región crítica y las vuelva a habilitar justo antes de salir de ella. Con las interrupciones inhabilitadas, no puede haber interrupciones de reloj. Después de todo, la CPU sólo se conmuta de un proceso a otro como resultado de interrupciones de reloj o de otro tipo, y con las interrupciones desactivadas la CPU no se cambiará a otro proceso. Así una vez que un proceso haya inhabilitado las interrupciones, podrá examinar y actualizar la memoria compartida sin temor a la intromisión de otro proceso.

Por lo general este enfoque es poco atractivo porque no es prudente conferir a los proce­sos de usuario la capacidad de inhabilitar todas las interrupciones. Supongamos que uno de ellos lo hace, y nunca vuelve a activarlas: eso podría acabar con el sistema. Además, si el sis­tema es un multiprocesador, con dos o más CPUs, la inhabilitación de interrupciones sólo afec­tará a la CPU que ejecutó la instrucción disable. Las demás seguirán operando en forma normal y podrán tener acceso a la memoria compartida.

Por otra parte, muchas veces es conveniente que el kernel mismo inhabilite las interrupciones durante unas cuantas instrucciones, mientras actualiza variables o listas. Por ejemplo, si ocurriera una interrupción en un momento en que la lista de procesos listos se encuentra en un estado in consistente, podrían presentarse condiciones de competencia. La conclusión es: inhabilitar las interrupciones a menudo es una técnica útil dentro del sistema operativo mismo, pero no es apropiada como mecanismo general de exclusión mutua para procesos de usuario.

 - Variables de bloqueo

Como segundo intento, examinemos una solución en software. Consideremos el uso de una sola variable compartida (de bloqueo) que inicialmente es 0. Cuando un proceso quiere entrar en su región crítica, primero prueba el bloqueo. Si éste es 0, el proceso lo establece a 1 y entra en la región crítica. Si el bloqueo ya es 1, el proceso espera hasta que cambie a 0. Por lo tanto, un 0 indica que ningún proceso está en su región crítica, y un 1 indica que algún proceso está en su región crítica.

Por desgracia, esta idea contiene exactamente el mismo defecto que vimos en el directorio de spooler. Supongamos que un proceso lee el bloqueo y ve que es 0. Antes de que pueda establecerlo a 1, se calendariza otro proceso, el cual se ejecuta y establece a 1 el bloqueo. Cuando el primer proceso vuelve a ejecutarse, también establecerá a 1 el bloqueo, y dos procesos estarán en su región crítica al mismo tiempo.

Usted podría pensar que este problema puede resolverse si primero se lee el valor del blo­queo y luego vuelve a verificarse, inmediatamente antes de almacenarlo, pero eso de nada sir­ve. La competencia se presenta ahora si el segundo proceso modifica el bloqueo justo después de que el primero termina su segunda verificación.

 - Alternancia estricta

Un tercer enfoque para atacar el problema de la exclusión mutua se muestra en la figura 2-20. Este fragmento de programa, al igual que casi todos los que se presentan en el libro, está escri­to en C. Escogimos este lenguaje porque casi todos los sistemas operativos reales están escritos en él (o a veces en C++), pero casi nunca en lenguajes como Java, Modula 3 o Pascal. C es po­tente, eficiente y predecible, características cruciales para escribir sistemas operativos. Java, por ejemplo, no es predecible porque podría quedarse sin memoria en un punto crítico y tener que invocar al recolector de basura en un momento muy inoportuno. Esto no puede suceder en C porque ahí no hay recolección de basura. En Prechelt (2000) se hace una comparación cuantita­tiva de C, C++, Java y otros cuatro lenguajes.

En la figura 2-20 la variable entera turno, que al principio es 0, indica a quién le corres­ponde entrar en la región crítica y examinar o actualizar la memoria compartida. Al principio, el proceso 0 examina turno, ve que es 0 y, por lo tanto, entra en su región crítica. El proceso 1 también ve que es 0 y, por lo tanto, da vueltas en un ciclo corto, probando en forma continua turno para detectar cuando cambie a 1. La prueba continua de una variable hasta que adquiere algún valor se denomina espera activa, y en general debe evitarse porque desperdicia tiempo de CPU. Sólo se usa cuando es razonable suponer que la espera será corta. Un bloqueo que uti­liza espera activa se denomina bloqueo giratorio.

Cuando el proceso 0 sale de la región crítica, establece turno a 1, y ello permite al proce­so 1 entrar en su región crítica. Supongamos que el proceso 1 termina rápido su región crítica, de modo que ambos procesos están en sus regiones no críticas y turno es 0. Ahora el proceso 0 ejecuta rápido todo su ciclo, sale de su región crítica y establece turno a 1. En este momen­to, turno es 1 y ambos procesos se están ejecutando en sus regiones no críticas.

De repente, el proceso 0 termina su región no crítica y vuelve al principio de su ciclo. Desafortunadamente, no se le permite entrar en su región crítica porque tumo es 1, y el proce­so 1 está ocupado con su región no crítica. El proceso 0 sigue dando vueltas en su ciclo while hasta que el proceso 1 establece turno a 0. Visto así, turnarse no es buena idea cuando uno de los procesos es mucho más lento que el otro.

Esta situación viola la condición 3 de una buena solución: el proceso 0 está siendo bloqueado por un proceso que no está en su región crítica. Volviendo al ejemplo del directorio de spooler, si ahora asociamos la región crítica a la lectura y escritura del directorio de spooler, no se permi­tiría al proceso 0 imprimir otro archivo, porque el proceso 1 está haciendo otra cosa.

De hecho, esta solución requiere que los dos procesos se alternen estrictamente para ingre­sar en su región crítica. Por ejemplo, en el spool de archivos, no se permitiría que dos proce­sos mandaran a spool dos archivos seguidos. Aunque este algoritmo evita todas las competencias, no es un buen candidato de solución porque viola la condición 3.

 - Solución de Peterson

Combinando la idea de turnarse con la idea de variables de bloqueo y variables de advertencia, un matemático holandés, T. Dekker, fue el primero en idear una solución en software para el problema de la exclusión mutua que no requiere alternancia estricta. Puede hallarse un análi­sis del algoritmo de Dekker en Dijkstra (1965).

En 1981, G. L. Peterson descubrió una forma mucho más sencilla de lograr exclusión mu­tua, lo que volvió obsoleta la solución de Dekker. El algoritmo de Peterson se muestra en la fi­gura 2-21. Consta de dos procedimientos escritos en ANSI C, lo que implica que es preciso incluir prototipos para todas las funciones que se definan y usen. Sin embargo, a fin de ahorrar espacio, no mostraremos los prototipos en este ejemplo ni en los subsiguientes.

Antes de usar las variables compartidas (es decir, antes de entrar en su región crítica, cada proceso invoca a entrar_region con su propio número de proceso, 0 o 1, como parámetro. Es­ta llamada lo hará que espere, si es necesario, hasta que pueda entrar sin peligro. Una vez que haya terminado de usar las variables compartidas, el proceso invocará a salir_region para indi­car que ya terminó y permitir al otro proceso que entre, si lo desea.

Veamos cómo funciona esta solución. En un principio ninguno de los procesos está en su región crítica. Ahora el proceso 0 llama a entrar_region e indica su interés, activando su ele­mento del arreglo y estableciendo turno a 0. Puesto que el proceso 1 no está interesado, entrar_region regresa de inmediato. Si ahora el proceso 1 llama a entrar_region, dará vueltas ahí has­ta que interesado[0] cambie a FALSE, algo que sólo sucede cuando el proceso 0 invoca salir_region para salir de su región crítica.

Ahora consideremos el caso en el que ambos procesos invoquen a entrar_region casi en forma simultánea. Los dos colocarán su número de proceso en turno. El último valor que se coloque ahí será el que cuente; el primero se sobrescribe y se pierde. Supongamos que el pro­ceso 1 es el último que guarda su número de proceso, así que turno contiene 1. Cuando los procesos llegan a su instrucción while, el proceso 0 la ejecuta cero veces y entra en su región crítica. El proceso 1 da vueltas y no ingresa en su región crítica sino hasta que el proceso 0 sa­le de la suya.

 - La instrucción TSL

Ahora examinemos una propuesta que requiere un poco de ayuda del hardware. Muchas compu­tadoras, sobre todo las diseñadas pensando en múltiples procesadores, tienen una instrucción

          TSL RX,BLOQUEO

(Test and Set Lock, probar y establecer bloqueo) que funciona como sigue: lee el contenido de la palabra de memoria bloqueo, lo coloca en el registro RX y luego guarda un valor distinto de ce­ro en la dirección de memoria bloqueo. Se garantiza que las operaciones de leer la palabra y escribir en ella son indivisibles: ningún otro procesador puede tener acceso a la palabra de me­moria antes de que haya terminado de ejecutarse la instrucción. La CPU que ejecuta la instruc­ción TSL cierra el bus de memoria para impedir que otras CPUs tengan acceso a la memoria antes de que termine.

Para usar la instrucción TSL, nos valdremos de una variable compartida, bloqueo, para coordinar el acceso a la memoria compartida. Cuando bloqueo es 0, cualquier proceso puede establecerla a 1 utilizando la instrucción TSL y luego leer o escribir en la memoria comparti­da. Cuando termina, el proceso vuelve a establecer a 0 dicha variable utilizando una instruc­ción move ordinaria.

¿Cómo puede esta instrucción evitar que dos procesos ingresen al mismo tiempo en su re­gión crítica? La solución se da en la figura 2-22, donde se muestra una subrutina de cuatro ins­trucciones en un lenguaje ensamblador ficticio (aunque representativo). La primera instrucción copia el valor antiguo de bloqueo en el registro y luego establece bloqueo a 1. A continuación, el valor antiguo se compara con 0. Si es distinto de cero, quiere decir que el bloqueo ya estaba establecido, así que el programa tan sólo vuelve al principio para probarlo otra vez. Tarde o temprano el bloqueo será 0 (cuando el proceso que actualmente está en su región crítica salga de ella) y la subrutina terminará, con el bloqueo establecido. Quitar el bloqueo es sencillo. El programa sólo coloca un 0 en bloqueo; no se requieren instrucciones especiales.

Ahora una de las soluciones del problema de la región crítica es sencilla. Antes de entrar en su región crítica, un proceso invoca a entrar_region, que efectúa una espera activa hasta que el bloqueo esté libre; luego adquiere el bloqueo y termina. Después de la región crítica, el pro­ceso invoca a salir_region, que coloca un 0 en bloqueo. Al igual que con todas las soluciones basadas en regiones críticas, los procesos deben invocar a entrar_region y salir_region en los momentos correctos para que el método funcione. Si un proceso hace trampa, la exclusión mu­tua fracasará.

4.Activar y desactivar:

Tanto la solución de Peterson como la que usa TSL son correctas, pero ambas tienen el defec­to de que requieren espera activa. En esencia, lo que estas soluciones hacen es lo siguiente: cuando un proceso quiere entrar en su región crítica, verifica si tal ingreso está permitido. Si no está permitido, el proceso entra en un ciclo corto para esperar hasta que lo esté.

Este enfoque no sólo desperdicia tiempo de CPU, sino que puede tener efectos inesperados. Consideremos una computadora con dos procesos; A, que es prioritario, y B, que no lo es. Las reglas de calendarización son de tal forma que A se ejecuta siempre que está en estado listo. En cierto momento, cuando B está en su región crítica, A queda listo para ejecutarse (es decir, ter­mina una operación de E/S). Ahora A inicia una espera activa, pero dado que B nunca se calendariza mientras A se está ejecutando, B nunca tendrá oportunidad de salir de su región crítica, y A seguirá dando vueltas en forma indefinida. Esta situación se conoce como problema de in­versión de prioridad.

Ahora veamos algunas primitivas de comunicación entre procesos que se bloquean, en lu­gar de desperdiciar tiempo de CPU, cuando no se les permite entrar en su región crítica. Una de las más sencillas es el par sleep y wakeup. Sleep es una llamada al sistema que hace que el invocador se bloquee, es decir, quede suspendido hasta que otro proceso lo active. La llama­da wakeup tiene un parámetro, el proceso por activar. De manera alternativa, tanto sleep co­mo wakeup tienen un parámetro: una dirección de memoria que sirve para relacionar llamadas sleep con llamadas wakeup.

 - El problema del productor-consumidor

Como ejemplo del uso de estas primitivas, consideremos el problema del productor-consu­midor (también conocido como problema del búfer acotado). Dos procesos comparten un búfer de tamaño fijo. Uno de ellos, el productor, coloca información allí y el otro, el consumidor, la saca. (También es posible generalizar el problema a m productores y n consumidores, pero sólo consideraremos el caso de un productor y un consumidor porque eso simplifica las solu­ciones.)

Los problemas surgen cuando el productor quiere colocar un nuevo elemento en el búfer pero éste ya está lleno. La solución es que el productor se desactive y se vuelva a activar cuan­do el consumidor haya sacado uno o más elementos. Asimismo, si el consumidor quiere sacar un elemento del búfer y ve que está vacío, se desactiva hasta que el productor coloca algo allí y lo activa.

Este enfoque parece sencillo, pero da pie a condiciones de competencia como las que vi­mos antes con el directorio de spooler. Para determinar cuántos elementos hay en el búfer, ne­cesitaremos una variable, cuenta. Si el búfer puede contener N elementos como máximo, el código del productor determinará primero si cuenta es N. Si lo es, el productor se desactivará; si no lo es, añadirá un elemento e incrementará cuenta.

El código del consumidor es similar: primero prueba cuenta para ver si es 0. Si lo es, se desactiva: si no lo es, saca un elemento y decrece cuenta. Además, cada proceso determi­na si el otro debe activarse o no y, en su caso, lo activa. El código del productor y el del con­sumidor se muestran en la figura 2-23.

Para expresar llamadas al sistema del tipo de sleep y wakeup en C, las mostraremos co­mo llamadas a rutinas de biblioteca. No forman parte de la biblioteca estándar de C, pero es de suponer que estarán disponibles en cualquier sistema que tenga tales llamadas al sistema. Los procedimientos insertar_elem y sacar_elem, que no se muestran, se encargan de los pormeno­res de colocar elementos en el búfer y sacarlos de él.

Ahora volvamos a la condición de competencia. Puede presentarse porque el acceso a cuenta no está restringido. Podría darse la siguiente situación: el búfer está vacío y el consu­midor acaba de leer cuenta para ver si es 0. En ese instante, el calendarizador decide dejar de ejecutar el consumidor por el momento y comienza a ejecutar el productor. Éste inserta un ele­mento en el búfer, incrementa cuenta y observa que ahora tiene el valor 1. Eso implica que an­tes cuenta era 0, así que el consumidor debe estar inactivo; por lo tanto, el productor llama a wakeup para activarlo.

Por desgracia, éste todavía no está inactivo lógicamente, por lo que la señal de activar se pierde. La siguiente vez que se ejecute el consumidor, probará el valor de cuenta que ya había leído, verá que es 0, y se desactivará. Tarde o temprano el productor llenará el búfer hasta el tope y se desactivará. Ambos estarán inactivos por siempre.

La esencia del problema es que se pierde una señal de activar enviada a un proceso que no está inactivo (todavía). Si no se perdiera, todo funcionaría. Una solución rápida es modificar las reglas y añadir un bit de espera para activar. Cuando se intenta activar un proceso que está acti­vo, se establece este bit. Después, cuando el proceso quiera desactivarse, si el bit de espera está encendido, se apagará, pero el proceso seguirá activo. El bit de espera para activar es una espe­cie de alcancía para señales de activar.

Aunque el bit de espera para activar nos salva en este sencillo ejemplo, es fácil idear ejem­plos con tres o más procesos en los que un bit de espera no basta. Podríamos añadir un segun­do bit de espera, o quizá ocho o 32, pero en principio el problema persiste.

5.Semáforos:

Ésta era la situación en 1965, cuando E. W. Dijkstra (1965) sugirió el uso de una variable en­tera para contar el número de llamadas wakeup guardadas para uso futuro. En su propuesta introdujo un nuevo tipo de variable llamada semáforo. Un semáforo puede tener el valor 0, que indica que no se guardaron llamadas wakeup, o algún valor positivo si hay llamadas pen­dientes.

Dijkstra propuso tener dos operaciones: down y up (generalizaciones de sleep y wakeup, respectivamente). La operación down aplicada a un semáforo determina si su valor es mayor que 0. En tal caso, decrece el valor (es decir, gasta un despertar almacenado) y simplemen­te continúa. Si el valor es 0, el proceso se desactiva sin terminar la operación down por el mo­mento. Verificar el valor, modificarlo y desactivarse (en su caso) se efectúan como una sola acción atómica (es decir, indivisible). Se garantiza que una vez iniciada una operación de se­máforo, ningún otro proceso podrá tener acceso al semáforo antes de que la operación haya ter­minado o se haya bloqueado. Esta atomicidad es indispensable para resolver problemas de sincronización y evitar condiciones de competencia.

La operación up incrementa el valor del semáforo indicado. Si uno o más procesos esta­ban inactivos en espera de ese semáforo, sin haber podido terminar una operación down pre­via, el sistema escoge uno de ellos (quizá al azar) y le permite terminar dicha operación. Así, después de un up con un semáforo con procesos inactivos, el semáforo seguirá siendo 0, pero habrá un proceso inactivo menos esperándolo. La operación de incrementar el semáforo y acti­var un proceso también es indivisible. Ningún proceso se bloquea jamás ejecutando up, así como ninguno se bloqueaba ejecutando wakeup en el modelo anterior.

Por cierto, en su artículo original Dijkstra usó los nombres P y V en vez de down y up, respectivamente, pero dado que no tienen connotaciones mnemónicas para quienes no hablan holandés (y no muchas para quienes sí lo hablan), preferimos usar los términos down y up, que se introdujeron por primera vez en Algol 68.

 - Resolución del problema del productor-consumidor empleando semáforos

Los semáforos resuelven el problema del despertar perdido, como se muestra en la figura 2-24. Es indispensable que se implementen de manera indivisible. El procedimiento normal es implementar down y up como llamadas al sistema y que el sistema operativo inhabilite en forma breve todas las interrupciones, mientras está probando y actualizando el semáforo, así como poniendo el proceso a dormir, si es necesario. Dado que todas estas acciones sólo requieren unas cuantas instrucciones, la inhabilitación de las interrupciones no es perjudicial. Si se están utilizando múltiples CPUs, cada semáforo deberá protegerse con una variable de bloqueo, uti­lizándose la instrucción TSL para garantizar que sólo una CPU a la vez examine el semáforo. Debe entender que el uso de TSL para evitar que varias CPUs tengan acceso simultáneo al se­máforo es muy distinto de la espera activa del productor o el consumidor para que el otro vacíe o llene el búfer. La operación de semáforo apenas tardará unos cuantos microsegundos, mien­tras que el productor o el consumidor podrían tardar un tiempo arbitrario.

Esta solución utiliza tres semáforos: uno llamado llenas, para contar el número de ranuras ocupadas, otro llamado vacias, para contar el número de ranuras desocupadas, y el último lla­mado mutex, para asegurar que el productor y el consumidor no tengan acceso al búfer al mis­mo tiempo. En un principio, llenas es 0, vacias es igual al número de ranuras del búfer y mutex es 1. Los semáforos a los que se asigna el valor inicial 1 y que son utilizados por dos o más procesos para garantizar que sólo uno de ellos pueda estar en su región crítica en un momento dado, se denominan semáforos binarios. Si cada proceso ejecuta down justo antes de entrar en su región crítica y up justo después de salir de ella, la exclusión mutua estará garantizada.

Ahora que contamos con una buena primitiva de comunicación entre procesos, examine­mos otra vez la sucesión de interrupciones de la figura 2-5. En un sistema que usa semáforos, la forma natural de ocultar las interrupciones es tener un semáforo, con valor inicial 0, asocia­do con cada dispositivo de E/S. Inmediatamente después de poner en marcha un dispositivo de E/S, el proceso administrador ejecuta down en el semáforo correspondiente y se bloquea de inmediato. Cuando llega la interrupción, el manejador de interrupciones ejecuta up en el se­máforo correspondiente, lo que pone al proceso en cuestión en condiciones de ejecutarse de nuevo. En este modelo, el paso 5 de la figura 2-5 consiste en ejecutar up en el semáforo del dispositivo, de modo que en el paso 6 el calendarizador pueda ejecutar al administrador del dis­positivo. Desde luego, si ahora hay varios procesos listos, el calendarizador podría optar por ejecutar a continuación otro aún más importante. En una sección posterior del capítulo exami­naremos algunos de los algoritmos empleados para calendarizar.

En el ejemplo de la figura 2-24 utilizamos los semáforos de dos maneras distintas. Esta di­ferencia es lo bastante importante como para destacarla. El semáforo mutex sirve para exclu­sión mutua: está diseñado para garantizar que sólo un proceso estará leyendo o escribiendo en el búfer y las variables asociadas en un momento dado. Esta exclusión mutua es necesaria pa­ra evitar el caos. En la siguiente sección estudiaremos más a fondo la exclusión mutua y cómo lograrla.

El otro uso de los semáforos es para sincronización. Los semáforos llenas y vacias se ne­cesitan para garantizar que ciertas secuencias de sucesos se presenten o no. En este caso, cui­dan que el productor deje de ejecutarse cuando el búfer. está lleno, y que el consumidor deje de ejecutarse cuando el búfer está vacío. Este uso es distinto de la exclusión mutua.

6.Mutexes:

Cuando no se necesita la capacidad de contar del semáforo, suele utilizarse una versión sim­plificada del semáforo, llamada mutex (abreviatura de "exclusión mutua", en inglés). Las mu­texes sólo sirven para administrar la exclusión mutua respecto a algún recurso o fragmento de código compartido. Su implementación es sencilla y eficiente, por lo que son útiles sobre todo en los sistemas de subprocesos que se implementan por completo en espacio de usuario.

Una mutex es una variable que puede estar en uno de dos estados: desbloqueado o bloquea­do. Por ello, sólo se necesita un bit para representarlo, aunque en la práctica es común que se use un entero, de tal modo que 0 signifique desbloqueado y todos los demás valores signifiquen bloqueado. Se usan dos procedimientos con mutexes. Cuando un subproceso (o proceso) nece­sita obtener acceso a una región crítica, invoca a mutex_lock. Si la mutex está desbloqueada (o sea que la región crítica está disponible), la llamada procede y el subproceso invocador puede entrar en la región crítica.

En cambio, si la mutex ya estaba bloqueada, el subproceso invocador se bloqueará hasta que el subproceso que está en la región crítica termine e invoque a mutex_unlock. Si hay varios subprocesos bloqueados en espera de la mutex, se escoge uno de ellos al azar y se le permite ad­quirir el bloqueo.

Por su sencillez, es fácil implementar las mutexes en espacio de usuario, si se cuenta con una instrucción TSL. En la figura 2-25 se muestra el código para mutex_lock y mutex_unlock que se usaría en un sistema de subprocesos en el nivel de usuario.

El código de mutex_lock es similar al de entrar_region de la figura 2-22 pero con una di­ferencia crucial. Cuando entrar_region no logra entrar en la región crítica, sigue probando el bloqueo una y otra vez (espera activa). En algún momento llegará una interrupción de reloj y se calendarizará otro proceso para ejecutarse. Tarde o temprano, el proceso que tiene el blo­queo podrá ejecutarse y lo liberará.

En el caso de los subprocesos la situación es diferente, porque no hay un reloj que deten­ga a los que se han ejecutado durante demasiado tiempo. Por lo tanto, un subproceso que trate de adquirir un bloqueo mediante espera activa dará vueltas en forma indefinida y nunca lo ten­drá porque nunca permitirá que otro subproceso se ejecute y suelte el bloqueo.

Es aquí donde se encuentra la diferencia entre entrar_region y mutex_lock. Cuando esta úl­tima fracasa en su intento por adquirir un bloqueo, invoca a thread_yield para ceder la CPU a otro subproceso. Por lo tanto, no hay espera activa. La siguiente vez que se ejecute el subpro­ceso, volverá a probar el bloqueo.

Puesto que thread_yield no es más que una llamada al calendarizador de subprocesos en espacio de usuario, es muy rápido. Por ello, ni mute_lock ni mutex_unlock requieren llamadas al kernel. Con estos procedimientos que sólo requieren un puñado de instrucciones, los sub­procesos en el nivel de usuario pueden sincronizarse cabalmente en espacio de usuario.

El sistema de mutexes que acabamos de describir no es más que un conjunto de llamadas. En todo software siempre se exigen más funciones, y las primitivas de sincronización no son la ex­cepción. Por ejemplo, hay sistemas de subprocesos que ofrecen una llamada mutex_trylock que ad­quiere el bloqueo, o bien, devuelve un código de fracaso, pero no se bloquea. Esta llamada permite al subproceso decidir qué hará a continuación, si es que existen alternativas a la simple espera.

Hasta aquí hemos pasado por alto un aspecto que vale la pena analizar. En un sistema de subprocesos en espacio de usuario no hay problema si varios subprocesos tienen acceso a la mis­ma mutex porque todos operan en el mismo espacio de direcciones. Sin embargo, en casi to­das las soluciones anteriores, como en el algoritmo de Peterson y los semáforos, existe la suposición de que múltiples procesos tienen acceso a, por lo menos, cierta memoria comparti­da, que podría ser una sola palabra, o más. Si los procesos tienen espacios de direcciones dis­tintos por completo, como hemos dicho siempre, ¿cómo pueden compartir la variable turno en el algoritmo de Peterson, o los semáforos, o un búfer común?

Hay dos respuestas. Primera, algunas de las estructuras de datos compartidas, como los se­máforos, pueden almacenarse en el kernel y el acceso a ellas puede ser exclusivamente median­te llamadas al sistema. Este enfoque elimina el problema. Segunda, casi todos los sistemas operativos modernos (incluidos UNIX y Windows) ofrecen un mecanismo para que los proce­sos compartan una parte de su espacio de direcciones con otros procesos. De esta forma, pue­den compartirse los búferes y otras estructuras de datos. En el peor de los casos, si no existe otra posibilidad, puede utilizarse un archivo compartido.

Si dos o más procesos comparten la mayor parte de su espacio de direcciones, o todo, la distinción entre procesos y subprocesos se borra un poco, aunque no deja de existir. Dos pro­cesos que comparten un espacio de direcciones siguen teniendo archivos abiertos, temporizadores de alarma y otras propiedades de proceso distintas, mientras que los subprocesos de un mismo proceso los comparten. Además, cuando varios procesos comparten un mismo espacio de direcciones nunca son tan eficientes como los subprocesos en el nivel de usuario, pues el kernel participa intensamente en su administración.

7.Monitores:

Con semáforos, la comunicación entre procesos parece fácil, ¿no? De ninguna manera. Exami­nemos con detenimiento en la figura 2-24 el orden de los down antes de insertar o sacar ele­mentos del búfer. Supongamos que se invierte el orden de los dos down del código del productor, de modo que mutex se disminuya antes que vacias, no después. Si el búfer estuvie­ra lleno por completo, el productor se bloquearía y mutex se establecería a 0. Por lo tanto, la siguiente vez que el consumidor tratara de tener acceso al búfer ejecutaría down con mutex, que es 0, y también se bloquearía. Ambos procesos seguirían bloqueados de manera indefini­da y ya no se efectuaría más trabajo. Esta lamentable situación se denomina bloqueo irre­versible. Estudiaremos este tipo de bloqueos con detalle en el capítulo 3.

Señalamos el problema para subrayar el cuidado que hay que tener al usar semáforos. Un sutil error y todo se paralizará. Es como programar en lenguaje ensamblador, sólo que peor, porque los errores son condiciones de competencia, bloqueos irreversible y otras formas de comportamiento impredecibles e irreproducibles.

A fin de facilitar la escritura de programas correctos, Hoare (1974) y Brinch Hansen (1975) propusieron una primitiva de sincronización de más alto nivel llamada monitor. Sus propuestas presentan pequeñas diferencias, como describimos a continuación. Un monitor es una colección de procedimientos, variables y estructuras de datos que se agrupan en un tipo especial de módu­lo o paquete. Los procesos pueden invocar a los procedimientos de un monitor cuando lo deseen, pero no pueden acceder en forma directa a sus estructuras de datos internas desde procedimien­tos declarados fuera de dicho monitor. La figura 2-26 ilustra un monitor escrito en un lenguaje imaginario, Pascal Simple.

Los monitores tienen una propiedad importante que los hace útiles para lograr exclusión mutua: sólo un proceso puede estar activo en un monitor a la vez. Los monitores son una cons­trucción del lenguaje de programación, así que el compilador sabe que son especiales y pue­de manejar las llamadas a los procedimientos de monitor, de manera distinta de como mane­ja otras llamadas a procedimientos. Por lo regular, cuando un proceso llama a un procedimiento de monitor, las primeras instrucciones de éste verifican si algún otro proceso está activo dentro del monitor. Si es así, el proceso invocador se suspenderá hasta que el otro proceso haya salido del monitor. Si ningún otro proceso lo está usando, el proceso invocador puede entrar.

El compilador debe implementar la exclusión mutua en los ingresos a un monitor, pero es posible utilizar una mutex o un semáforo binario. Puesto que es el compilador, no el progra­mador, quien ”tramita” la exclusión mutua, es mucho menos probable que algo salga mal. En todo caso, quien escribe el monitor no tiene que saber la manera en que el compilador mane­ja la exclusión mutua. Basta con saber que convirtiendo todas las regiones críticas en proce­dimientos de monitor, dos procesos nunca podrán ejecutar sus regiones críticas al mismo tiempo.

Aunque los monitores facilitan la exclusión mutua, como acabamos de ver, no es suficiente. También necesitamos que los procesos puedan bloquearse cuando les sea imposible continuar. En el problema del productor-consumidor no es muy difícil colocar en procedimientos de monitor todas las pruebas para determinar si el búfer está lleno o vacío, pero ¿cómo debe bloquearse el productor si se encuentra con que el búfer está lleno?

La solución radica en la introducción de variables de condición, junto con dos operacio­nes que las manipulan: wait y signal. Cuando un procedimiento de monitor descubre que no puede continuar (por ejemplo, el productor ve que el búfer está lleno), ejecuta wait con algu­na variable de condición, digamos lleno. Esta acción hace que el proceso invocador se blo­quee, y también permite la entrada de otro proceso al que antes se le había impedido entrar en el monitor.

Este otro proceso, que podría ser el consumidor, puede activar a su compañero inactivo eje­cutando signal con la variable de condición que su compañero está esperando. Para evitar que haya dos procesos activos en el monitor al mismo tiempo, necesitamos una regla que nos diga qué sucede después de signal. Hoare propone dejar que el proceso recién activado se ejecute, suspendiendo el otro. Brinch Hansen propuso solucionar el problema exigiendo que un proce­so que ejecute signal salga del monitor de inmediato. Dicho de otro modo, una instrucción sig­nal sólo puede aparecer como instrucción final en un procedimiento de monitor. Adoptaremos la propuesta de Brinch Hansen porque es más sencilla en lo conceptual y también más fácil de implementar. Si se ejecuta signal con una variable de condición que varios procesos están es­perando, sólo uno de ellos, a elección del calendarizador del sistema, será revivido.

Por cierto, existe una tercera solución que no propusieron ni Hoare ni Brinch Hansen: de­jar que quien emite la señal se siga ejecutando y permitir que el proceso en espera comience a ejecutarse sólo después de que el emisor de la señal haya salido del monitor.

Las variables de condición no son contadores; no acumulan señales para usarlas después como hacen los semáforos. Por lo tanto, si una variable de condición recibe una señal y nadie está esperando esa variable, la señal se perderá sin remedio. Dicho de otro modo, wait debe ve­nir antes de signal. Esta regla simplifica mucho la implementación. En la práctica no hay pro­blema porque es fácil mantenerse al tanto del estado de cada proceso con variables, si es preciso. Un proceso, que de otra manera ejecutaría signal, puede ver que tal operación no es necesaria mediante la examinación de las variables.

En la figura 2-27 se presenta un bosquejo del problema del productor-consumidor con mo­nitores, escrito en un lenguaje imaginario, Pascal Simple. La ventaja de usar Pascal Simple aquí es que es puro y sencillo, y sigue con exactitud el modelo de Hoare/Brinch Hansen.

Tal vez usted está pensando que las operaciones wait y signal se parecen a sleep y wakeup, y ya vimos que éstas tienen condiciones de competencia fatales. Sí son muy similares, pero con una diferencia crucial: sleep y wakeup fallaron porque mientras un proceso estaba tratando de desactivarse, otro estaba tratando de activarlo. Con los monitores, eso no puede suceder. La ex­clusión mutua automática en los procedimientos de monitor garantiza que si el productor, por ejemplo, está en un procedimiento de monitor y descubre que el búfer está lleno, podrá terminar la operación wait sin tener que preocuparse por la posibilidad de que el calendarizador conmute hacia el consumidor justo antes de que wait termine. El consumidor ni siquiera podrá entrar en el monitor antes de que wait termine y que el productor se haya marcado como no ejecutable pro­visionalmente.

Aunque Pascal Simple es un lenguaje imaginario, algunos lenguajes de programación rea­les manejan monitores, aunque no siempre en la forma diseñada por Hoare y Brinch Hansen. Uno de esos lenguajes es Java, que es un lenguaje orientado a objetos que maneja subprocesos en el nivel de usuario y también permite agrupar métodos (procedimientos) en clases. Si agre­ga la palabra clave synchronized a una declaración de método, Java garantiza que una vez que un subproceso haya comenzado a ejecutar ese método, no se permitirá a ningún otro subproceso comenzar a ejecutar ningún otro método synchronized de esa clase.

En la figura 2-28 se presenta una solución del problema del productor-consumidor utilizan­do monitores en Java. La solución consiste en cuatro clases. La clase exterior, ProductorConsumidor, crea y pone en marcha dos subprocesos, p y c. La segunda y tercera clase, productor y consumidor, contienen el código del productor y el del consumidor. Por último, la clase mi_monitor es el monitor, con dos subprocesos sincronizados que sirven para insertar y sacar elemen­tos del búfer compartido. A diferencia de los ejemplos anteriores, aquí sí mostramos el código completo para insertar y quitar

Los subprocesos productor y consumidor son funcionalmente idénticos a sus contrapartes en todos nuestros ejemplos anteriores. El productor tiene un ciclo infinito que genera datos y los coloca en el búfer común. El consumidor tiene un ciclo infinito igual que saca datos del búfer común y hace algo divertido con ellos.

La parte interesante de este programa es la clase mi_monitor, que contiene el búfer, las va­riables de administración y dos métodos sincronizados. Cuando el productor está activo dentro de insertar, tiene la certeza de que el consumidor no puede estar activo dentro de quitar, y puede ac­tualizar las variables y el búfer sin temor a que se presenten condiciones de competencia. La va­riable cuenta lleva la cuenta del número de elementos que hay en el búfer, y puede adoptar cualquier valor a partir de 0, incluyendo N - 1. La variable baja es el índice de la ranura del búfer de la cual se obtendrá el siguiente elemento. Asimismo, alta es el índice de la ranura donde se co­locará el siguiente elemento. Está permitido que baja = alta, lo que implica que hay 0, o bien, N elementos en el búfer; el valor de cuenta indica de cuál de los dos casos se trata.

Los métodos sincronizados de Java difieren de los monitores clásicos en un aspecto fun­damental: Java no maneja variables de condición. En vez de eso. ofrece dos procedimientos, wait y notify, que son el equivalente de sleep y wakeup sólo que cuando se usan dentro de mé­todos sincronizados, no están sujetos a condiciones de competencia. En teoría, el método wait puede interrumpirse, y es de eso precisamente de lo que se trata el código que lo rodea. Java exige que el manejo de excepciones sea explícito.

Al volver automática la exclusión mutua de las regiones críticas, los monitores hacen que la programación paralela sea mucho menos propensa a errores que con semáforos. No obstante, tienen algunas desventajas. No es casualidad que nuestros dos ejemplos de monitores hayan estado en Pascal Simple y en Java en lugar de C, como los demás ejemplos de este libro. Como ya se­ñalamos, los monitores son un concepto del lenguaje de programación. El compilador debe reco­nocerlos y. de alguna manera, tramitar la exclusión mutua. C, Pascal y casi todos los demás lenguajes carecen de monitores, por lo que no sería razonable esperar que sus compiladores hagan cumplir reglas de exclusión mutua. De hecho, ¿cómo podría el compilador saber siquiera cuáles procedimientos están en monitores y cuáles no?

Esos mismos lenguajes también carecen de semáforos, pero es fácil añadirlos: lo único que necesita es incluir en la biblioteca dos rutinas cortas en lenguaje ensamblador para emitir las llamadas al sistema up y down. Los compiladores ni siquiera tienen que saber que existen. Desde luego, los sistemas operativos sí necesitan tener conocimiento de los semáforos, pero si usted tiene un sistema operativo basado en semáforos, de todos modos podrá escribir progra­mas de usuario para él en C o C++ (o incluso lenguaje ensamblador, si se es lo bastante masoquista). Para usar monitores necesita un lenguaje que ya los tenga integrados.

Otro problema con los monitores, y también con los semáforos, es que fueron diseñados pa­ra resolver el problema de la exclusión mutua en una o más CPUs, las cuales tienen acceso a una memoria común. Al colocar los semáforos en la memoria compartida y protegerlos con ins­trucciones TSL, podemos evitar las competencias. Cuando pasamos a un sistema distribuido que consta de varias CPUs, cada una con su propia memoria privada y conectadas por una red local, ya no pueden usarse estas primitivas. La conclusión es que los semáforos son de nivel demasia­do bajo y los monitores con muy pocos lenguajes de programación. Además, ninguna de estas primitivas considera el intercambio de información entre máquinas. Necesitamos algo más.

8.Transferencia de mensajes:

Ése algo más es la transferencia de mensajes. Este método de comunicación entre procesos utiliza dos primitivas, send y receive, que, al igual que los semáforos y a diferencia de los monitores, son llamadas al sistema, no construcciones del lenguaje. Como tales, pueden in­cluirse con facilidad en procedimientos de biblioteca como

send(destino, &mensaje);

y

receive(origen, &mensaje);

La primera llamada envía un mensaje a un destino dado y la segunda recibe un mensaje de un origen dado

(o de ANY –cualquiera–, si al receptor no le importa el origen). Si no hay men­sajes disponibles, el receptor puede bloquearse hasta que llegue uno, o bien, regresar de inme­diato con un código de error.

- Aspectos de diseño de sistemas con transferencia de mensajes

Los sistemas con transferencia de mensajes presentan muchos problemas y cuestiones de dise­ño difíciles que no existen con los semáforos ni con los monitores, sobre todo si los procesos en comunicación están en máquinas distintas conectadas por una red. Por ejemplo, cabe la po­sibilidad de que en la red se pierdan mensajes. Para protegerse contra tal pérdida, el emisor y el receptor pueden convenir en que tan pronto como el receptor reciba un mensaje, devolverá un mensaje especial de acuse. Si el emisor no recibe tal acuse dentro de cierto plazo, retrans­mitirá el mensaje.

Ahora consideremos lo que sucede si el mensaje se recibe en forma correcta, pero el acu­se se pierde. El emisor retransmitirá el mensaje y el receptor lo obtendrá dos veces. Es indis­pensable que el receptor pueda distinguir entre un mensaje nuevo y la retransmisión de uno antiguo. Por lo regular, este problema se resuelve anexando números de sucesión consecutivos a cada mensaje original. Si el receptor recibe un mensaje con el mismo número de sucesión que el mensaje anterior, sabrá que está repetido y puede ignorarlo. Lograr la comunicación pese a la falta de fiabilidad de la transferencia de mensajes es una parte importante del estudio de las redes de computadoras. Para más información, consulte Tanenbaum (1996).

Los sistemas de mensajes también deben resolver el problema de cómo nombrar los proce­sos de modo que las llamadas send o receive no sean ambiguas. Otro aspecto importante de los sistemas de mensajes es la autenticación: ¿cómo sabe el cliente que se está comunicando con el verdadero servidor de archivos y no con un impostor?

En el otro extremo del espectro, hay cuestiones de diseño que son importantes cuando el emisor y el receptor están en la misma máquina. Una de ellas es el desempeño. Copiar men­sajes de un proceso a otro siempre lleva más tiempo que efectuar una operación de semáforo o entrar en un monitor. Se ha trabajado mucho en aumentar la eficiencia de la transferencia de mensajes. Por ejemplo, Cheriton (1984) después sugirió limitar el tamaño de los mensajes a lo que cabría en los registros de la máquina, y efectuar la transferencia de mensajes em­pleando los registros.

- El problema del productor-consumidor con transferencia de mensajes

Ahora veamos cómo puede resolverse el problema del productor-consumidor con transferen­cia de mensajes y sin compartir memoria. En la figura 2-29 se presenta una solución. Damos por hecho que todos los mensajes tienen el mismo tamaño y que el sistema operativo coloca en forma automática en un búfer los mensajes que se enviaron pero aún no se han recibido. En es­ta solución usamos un total de N mensajes, que es análogo al uso de N ranuras en el búfer de memoria compartida. Lo primero que hace el consumidor es enviar N mensajes vacíos al pro­ductor. Cada vez que éste tiene un elemento que entregar al consumidor, toma un mensaje va­cío y devuelve uno lleno. Así, el número total de mensajes en el sistema se mantiene constante con el paso del tiempo, y dichos mensajes pueden guardarse en una cantidad de memoria da­da, que se conoce con antelación.

Si el productor trabaja más rápido que el consumidor, todos los mensajes se llenarán y es­tarán esperando al consumidor; el productor se bloqueará, en espera de la devolución de un men­saje vacío. Si el consumidor trabaja a mayor velocidad, ocurrirá lo contrario: todos los mensajes estarán vacíos en espera de que el productor los llene; el consumidor se bloqueará esperando un mensaje lleno.

Puede haber muchas variantes de la transferencia de mensajes. Para empezar, veamos có­mo se dirigen los mensajes. Una posibilidad es asignar a cada proceso una dirección única y dirigir los mensajes a procesos. Otra es inventar una nueva estructura de datos llamada buzón, que es un búfer con capacidad para almacenar cierto número de mensajes, que por lo general se especifica cuando se crea. Cuando se usan buzones, los parámetros de dirección de las lla­madas send y receive son buzones, no procesos. Cuando un proceso intenta enviar un men­saje a un buzón que está lleno, se suspende hasta que se saca un mensaje de ese buzón y se crea espacio para uno nuevo.

En el caso del problema del productor-consumidor, tanto el productor como el consumidor crearían buzones lo bastante grandes como para contener N mensajes. El productor enviaría mensajes con datos al buzón del consumidor, y éste enviaría mensajes vacíos al buzón del pro­ductor. Cuando se usan buzones, el mecanismo de búfer es obvio: el buzón de destino contie­ne mensajes que se han enviado al proceso destinatario pero todavía no se aceptan.

Lo opuesto a tener buzones es no usar búferes en absoluto. Cuando se adopta este enfoque, si send se ejecuta antes que receive, el proceso emisor se bloquea hasta que se efectúa el receive, y entonces podrá copiarse el mensaje en forma directa del emisor al receptor, sin búfer intermedio. De forma análoga, si se ejecuta primero receive, el receptor se bloqueará hasta que se efectúe un send. Tal estrategia se conoce como cita (rendezvous). Es más fácil de implementar que un esquema de mensajes en búfer pero es menos flexible, pues obliga al emisor y al receptor a operar en sincronía.

La transferencia de mensajes se usa mucho en sistemas de programación paralela. Un sis­tema de transferencia de mensajes muy conocido es la interfaz de transferencia de mensajes (MPI; message-passing interface) que se utiliza de manera amplia en computación científica. Si desea más información al respecto, puede ver Gropp et al. (1994) y Snir et al. (1996).

9.Barreras:

Nuestro último mecanismo de sincronización está pensado para grupos de procesos más que pa­ra situaciones tipo productor-consumidor en las que sólo hay dos procesos. Algunas aplicacio­nes se dividen en fases y tienen la regla de que ningún proceso puede pasar a la siguiente fase antes de que todos los procesos estén listos para hacerlo. Este comportamiento puede lograrse colocando una barrera al final de cada fase. Cuando un proceso llega a la barrera, se bloquea hasta que todos los procesos han llegado a ella. El funcionamiento de una barrera se ilustra en la figura 2-30.

En la figura 2-30a vemos cuatro procesos que se aproximan a una barrera. Esto implica que están computando y que todavía no han llegado al final de la fase actual. Después de un tiem­po, el primer proceso termina todos los cálculos que se le pidió efectuar durante la primera fa­se, y ejecuta la primitiva barrier, por lo regular, invocando a un procedimiento de biblioteca. El proceso queda suspendido. Poco después, un segundo, y luego un tercer proceso, termina la pri­mera fase y también ejecuta la primitiva barrier. Esta situación se ilustra en la figura 2-30b. Al final, cuando el último proceso, C, llega a la barrera, todos los procesos se liberan, como se muestra en la figura 2-30c.

Como ejemplo de un problema que requiere barreras, consideremos un problema de rela­jación típico en física o ingeniería. Por lo regular, hay una matriz que contiene algunos valores iniciales, que representan temperaturas en diversos puntos de una lámina metálica. La finali­dad podría ser calcular el tiempo que tarda el efecto de una flama colocada en la esquina para propagarse por toda la lámina.

Partiendo de los valores actuales, se aplica una transformación a la matriz para obtener su se­gunda versión, por ejemplo, aplicando las leyes de la termodinámica para determinar cuáles serán todas las temperaturas AT después. A continuación el proceso se repite una y otra vez, dan­do las temperaturas en los puntos de muestreo en función del tiempo a medida que la lámina se calienta. Así, el algoritmo va produciendo una serie de matrices.

Ahora imaginemos que la matriz es muy grande (digamos, de un millón por un millón), por lo que se necesitan procesos paralelos (quizá en un multiprocesador) para acelerar el cálculo. Di­ferentes procesos trabajan con diferentes partes de la matriz, calculando los nuevos elementos de ésta a partir de los anteriores, con base en las leyes de la física. Sin embargo, ningún proceso puede iniciar la iteración n + 1 antes de que termine la iteración n, es decir, antes de que todos los procesos hayan terminado su trabajo actual. Para lograr este objetivo, se programa cada pro­ceso de modo que ejecute una operación barrier al terminar su parte de la iteración en curso. Cuando todos los procesos terminan, la nueva matriz (las entradas de la siguiente iteración) es­tará completa, y todos los procesos se liberarán en forma simultánea para iniciar la siguiente iteración.

Alberto Diaz

LOS PROBLEMAS CLÁSICOS DE COMUNICACIÓN ENTRE LOS PROCESOS

Problema de la cena de los filósofos

El problema de los filósofos cenando es un problema clásico de las ciencias de la computación propuesto por Edsger Dijkstra en 1965 para representar el problema de la sincronización de procesos en un sistema operativo. Cabe aclarar que la interpretación está basada en pensadores chinos, quienes comían con dos palillos, donde es más lógico que se necesite el del comensal que se siente al lado para poder comer.

Enunciado del problema

Cinco filósofos se sientan alrededor de una mesa y pasan su vida cenando y pensando. Cada filósofo tiene un plato de fideos y un tenedor a la izquierda de su plato. Para comer los fideos son necesarios dos tenedores y cada filósofo sólo puede tomar los que están a su izquierda y derecha. Si cualquier filósofo coge un tenedor y el otro está ocupado, se quedará esperando, con el tenedor en la mano, hasta que pueda coger el otro tenedor, para luego empezar a comer.

Si dos filósofos adyacentes intentan tomar el mismo tenedor a una vez, se produce una condición de carrera: ambos compiten por tomar el mismo tenedor, y uno de ellos se queda sin comer.

Si todos los filósofos cogen el tenedor que está a su derecha al mismo tiempo, entonces todos se quedarán esperando eternamente, porque alguien debe liberar el tenedor que les falta. Nadie lo hará porque todos se encuentran en la misma situación (esperando que alguno deje sus tenedores). Entonces los filósofos se morirán de hambre. Este bloqueo mutuo se denomina interbloqueo o deadlock.

El problema consiste en encontrar un algoritmo que permita que los filósofos nunca se mueran de hambre.

Algunas posibles soluciones

·         Por turno cíclico

Se empieza por un filósofo, que si quiere puede comer y después pasa su turno al de la derecha. Cada filósofo sólo puede comer en su turno. Problema: si el número de filósofos es muy alto, uno puede morir de hambre antes de su turno.

·         Varios turnos

Se establecen varios turnos. Para hacerlo más claro supongamos que cada filósofo que puede comer (es su turno) tiene una ficha que después pasa a la derecha. Si por ejemplo hay 7 comensales podemos poner 3 fichas en posiciones alternas (entre dos de las fichas quedarían dos filósofos).

Se establecen turnos de tiempo fijo. Por ejemplo cada 5 minutos se pasan las fichas (y los turnos) a la derecha.

En base al tiempo que suelen tardar los filósofos en comer y en volver a tener hambre, el tiempo de turno establecido puede hacer que sea peor solución que la anterior. Si el tiempo de turno se aproxima al tiempo medio que tarda un filósofo en comer esta variante da muy buenos resultados. Si además el tiempo medio de comer es similar al tiempo medio en volver a tener hambre la solución se aproxima al óptimo.

·         Colas de tenedores

Cuando un filósofo quiere comer se pone en la cola de los dos tenedores que necesita. Cuando un tenedor está libre lo toma. Cuando toma los dos tenedores, come y deja libre los tenedores.

Visto desde el otro lado, cada tenedor sólo puede tener dos filósofos en cola, siempre los mismos.

Esto crea el problema comentado de que si todos quieren comer a la vez y todos empiezan tomando el tenedor de su derecha se bloquea el sistema (deadlock).

·         Resolución de conflictos en colas de tenedores

Cada vez que un filósofo tiene un tenedor espera un tiempo aleatorio para conseguir el segundo tenedor. Si en ese tiempo no queda libre el segundo tenedor, suelta el que tiene y vuelve a ponerse en cola para sus dos tenedores.

Si un filósofo A suelta un tenedor (porque ha comido o porque ha esperado demasiado tiempo con el tenedor en la mano) pero todavía desea comer, vuelve a ponerse en cola para ese tenedor. Si el filósofo adyacente B está ya en esa cola de tenedor (tiene hambre) lo toma y si no vuelve a cogerlo A.

Es importante que el tiempo de espera sea aleatorio o se mantendrá el bloqueo del sistema.

·         El portero del comedor

Se indica a los filósofos que abandonen la mesa cuando no tengan hambre y que no regresen a ella hasta que vuelvan a estar hambrientos (cada filósofo siempre se sienta en la misma silla). La misión del portero es controlar el número de filósofos en la sala, limitando su número a n-1, pues si hay n-1 comensales seguro que al menos uno puede comer con los dos tenedores.

·         Turno Por Velocidad

Los dos filósofos anteriores

Bibliografia: http://es.wikipedia.org/wiki/Problema_de_la_cena_de_los_fil%C3%B3sofos

Problema de los lectores y escritores

Se trata de un problema de acceso a un objeto compartido a la vez por parte de dos tipos de procesos: los escritores (modifican el contenido del objeto) y los lectores (no modifican el objeto). Condiciones de ejecución:

• Múltiples lectores pueden acceder simultáneamente al objeto compartido.
• Si ha y un proceso escritor accediendo al objeto compartido, ningún otro proceso puede acceder.

Dos enfoques: prioridad lectores o prioridad escritores

• Prioridad lectores: Un lector solo debe esperar si un escritor ya ha obtenido permiso para escribir
• Prioridad escritores: Si un escritor está esperando para acceder al objeto, ningún lector debe empezar a leer

Problema de los lectores y escritores, prioridad lectores

Un lector solo debe esperar si un escritor ya ha obtenido permiso para escribir

Bibliografia: http://www.dc.fi.udc.es/ai/~soto/sist_oper/Sol_prob_clas_sem.htm

PRIORIDAD A LOS LECTORES

Es una solución que utiliza semáforos para respetar la exclusión mutua. Se permite el acceso a varios lectores, pero mientras que un escritor está accediendo a los datos compartidos, no se permite acceder a ningún escritor o lector.

El primer lector que intenta acceder debe esperar en el semáforo, Cuando haya al menos un lector, los lectores siguientes no necesitan esperar para entrar, se les da prioridad. El problema es que un escritor estará esperando mientras que haya al menos un lector leyendo, que luego podría dar paso a otro lector, en este caso el lector estará sujeto a inanición.

PRIORIDAD A LOS ESCRITORES

Esta solución garantiza que no se permitirá acceder a los datos a ningún nuevo lector una vez que, al menos, un escritor haya declarado su deseo de escribir.

Bibliografia: cindyrella83.galeon.com/lec_esc.doc 

Problema del barbero durmiente

En ciencias de la computación, el problema del barbero durmiente es un problema de sincronización. El problema consiste en una barbería en la que trabaja un barbero que tiene un único sillón de barbero y varias sillas para esperar. Cuando no hay clientes, el barbero se sienta en una silla y se duerme. Cuando llega un nuevo cliente, éste o bien despierta al barbero o —si el barbero está afeitando a otro cliente— se sienta en una silla (o se va si todas las sillas están ocupadas por clientes esperando). El problema consiste en realizar la actividad del barbero sin que ocurran condiciones de carrera. La solución implica el uso de semáforos y objetos de exclusión mutua para proteger la sección crítica.

Un semáforo es una variable protegida (o tipo abstracto de datos) que constituye el método clásico para restringir o permitir el acceso a recursos compartidos (por ejemplo, un recurso de almacenamiento) en un entorno de multiprocesamiento. Fueron inventados por Edsger Dijkstra y se usaron por primera vez en el sistema operativo THEOS.

En electrónica y en programación concurrente, se conoce como condición de carrera al error que se produce en programas o circuitos lógicos que no se han construido adecuadamente para su ejecución simultánea con otros procesos.

Bilbiografia: http://es.wikipedia.org/wiki/Problema_del_barbero_durmiente

Bibliografia.

http://msdn.microsoft.com/es-es/library/6kac2kdh.aspx

http://fi.uaemex.mx/rmarcial/Sistemas_Operativos/Clase2.pdf

Luz Maran, Marcos Franzoi, Pablo Diaz