Silberschatz 10a castellano cap6

Vista previa del material en texto

Sincronización de Procesos
Un sistema generalmente consta de varios (quizás cientos o incluso miles) de hilos que se ejecutan simultáneamente o en paralelo. Los Hilos a menudo comparten datos del usuario. Mientras tanto, el sistema operativo actualiza diversas estructuras de datos continuamente para soportar múltiples hilos. Una condición de carrera existe cuando el acceso a los datos compartidos no está controlado, posiblemente resultando en valores de datos corruptos.
La sincronización de procesos implica el uso de herramientas que controlan el acceso a datos compartidos para evitar condiciones de carrera. Estas herramientas deben usarse con cuidado,
ya que su uso incorrecto puede provocar un bajo rendimiento del sistema, que incluye deadlock.
Cap 6
Herramientas de Sincronización
Un proceso cooperativo es aquel que puede afectar o verse afectado por otros procesos.
ejecutando en el sistema. Los procesos cooperativos pueden compartir directamente un
espacio de direcciones lógicas (es decir, código y datos) o se les permite compartir datos solo a través de la memoria compartida o el paso de mensajes. El Acceso concurrente a datos compartidos, sin embargo, pueden resultar en inconsistencia de datos. En este capítulo, discutimos diversos mecanismos para garantizar la ejecución ordenada de los procesos cooperativos que comparten un espacio de direcciones lógicas, de modo que se mantiene la consistencia de los datos.
OBJETIVOS DEL CAPÍTULO
• Describir el problema de la sección crítica e ilustrar una condición de carrera.
• Ilustrar soluciones de hardware para el problema de la sección crítica usando barreras de memoria, operaciones de comparar e intercambiar y variables atómicas.
• Demostrar cómo los bloqueos de mutex, semáforos, monitores y variables de condición pueden usarse para resolver el problema de la sección crítica.
• Evaluar herramientas que resuelvan escenarios del problema de la sección crítica en baja, moderada y de alta contención.
6.1 Antecedentes
Ya hemos visto que los procesos pueden ejecutarse simultáneamente o en paralelo. La Sección 3.2.2 introdujo el papel de la planificación de procesos y describió cómo el planificador de la CPU cambia rápidamente entre procesos para proporcionar una ejecución concurrente. Esto significa que un proceso solo puede completar parcialmente la ejecución antes de que se planifique otro proceso. De hecho, un proceso puede ser interrumpido en cualquier punto en su flujo de instrucciones, y el núcleo de procesamiento puede asignarse a ejecutar instrucciones de otro proceso. Además, se introdujo en la Sección 4.2 la ejecución paralela, en la que dos secuencias de instrucciones (que representan diferentes procesos) se ejecutan simultáneamente en núcleos de procesamiento separados. En este capítulo, explicamos cómo la ejecución simultánea o paralela puede contribuir a los problemas que implica la integridad de los datos compartidos por varios procesos.
Consideremos un ejemplo de cómo puede suceder esto. En el Capítulo 3, desarrollamos un modelo de un sistema que consiste en procesos secuenciales cooperantes o hilos, todos corriendo de forma asíncrona y posiblemente compartiendo datos. Ilustramos este modelo con el problema productor-consumidor, que es un paradigma representativo de muchas funciones del sistema operativo. Específicamente, en la Sección 3.5, nosotros describimos cómo se puede usar un búfer acotado para permitir que los procesos compartan memoria.
Ahora volvemos a nuestra consideración del búfer acotado. Como señalamos, nuestra solución original permitía a lo sumo TAMAÑO DEL BUFFER - 1 elementos en el buffer al mismo tiempo. Supongamos que queremos modificar el algoritmo para remediar esta deficiencia. Una posibilidad es agregar una variable entera, count inicializada en 0. Count se incrementa cada vez que agregamos un nuevo elemento al búfer y se disminuye cada vez que eliminamos un elemento del búfer. El código para el proceso del productor se puede modificar de la siguiente manera:
while (true) {
/* produce an item in next produced */
while (count == BUFFER SIZE)
; /* do nothing */
buffer[in] = next produced;
in = (in + 1) % BUFFER SIZE;
count++;
}
El código para el proceso del consumidor se puede modificar de la siguiente manera:
while (true) {
while (count == 0)
; /* do nothing */
next consumed = buffer[out];
out = (out + 1) % BUFFER SIZE;
count--;
/* consume the item in next consumed */
}
Aunque las rutinas de productor y consumidor que se muestran arriba son correctas por separado, pueden no funcionar correctamente cuando se ejecutan concurrentemente. Como una ilustración, suponga que el valor de la variable count es actualmente 5 y que los procesos productor y consumidor ejecutan simultáneamente las declaraciones "Count ++" y "Count - -". Tras la ejecución de estas dos declaraciones, el valor de la variable count puede ser 4, 5 o 6. El único resultado correcto, sin embargo, es count == 5, que se genera correctamente si el productor y el consumidor ejecutando por separado.
Podemos mostrar que el valor de count puede ser incorrecto, si se ejecuta de la siguiente manera. Note que la declaración "count ++" puede implementarse en lenguaje máquina (en una máquina típica) de la siguiente manera:
register1 = count
register1 = register1 + 1
count = register1
donde register1 es uno de los registros locales de la CPU. Del mismo modo, la declaración "count--"se implementa de la siguiente manera:
register2 = count
register2 = register2 − 1
count = register2
donde register2 es uno de los registros locales de la CPU. A pesar de que registro1 y register2 pueden ser el mismo registro físico, recuerde que el contenido de este registro será guardado y restaurado por el manejador de interrupciones (Sección 1.2.3).
La ejecución concurrente de "count ++" y "count - -" es equivalente a una ejecución secuencial en la cual las declaraciones de bajo nivel presentadas previamente están intercaladas en un orden arbitrario (pero el orden dentro de cada declaración de alto nivel se conserva). Uno de esos intercalados es el siguiente:
T0: producer execute register1 = count {register1 = 5}
T1: producer execute register1 = register1 +1 {register1 = 6}
T2: consumer execute register2 = count {register2 = 5}
T3: consumer execute register2 = register2 −1 {register2 = 4}
T4: producer execute count = register1 {count = 6}
T5: consumer execute count = register2 {count = 4}
Observe que hemos llegado al estado incorrecto "count == 4", lo que indica que los cuatro buffers están llenos, cuando, de hecho, cinco buffers están llenos. Si invertimos el orden de las declaraciones en T4 y T5, llegaríamos al estado incorrecto "count == 6 ". Llegaríamos a este estado incorrecto porque permitimos que ambos procesos manipulen el count variable al mismo tiempo. Una situación como ésta, donde varios procesos acceden y manipulan los mismos datos simultáneamente y el resultado de la ejecución depende del orden particular en el que el acceso
tiene lugar, se llama condición de carrera. Para protegerse contra la condición de la carrera de arriba, debemos asegurarnos de que sólo un proceso pueda manipular a la vez la variable count. Para hacer cumplir con tal garantía, requerimos que los procesos sean sincronizados de alguna manera.
Situaciones como la que acabamos de describir ocurren con frecuencia en los sistemas operativos como cuando diferentes partes del sistema manipulan los recursos. Además, como hemos enfatizado en capítulos anteriores, la importancia de los sistemas multinúcleo ha puesto un mayor énfasis en el desarrollo de aplicaciones multiproceso. En tales aplicaciones, varios hilos, que posiblemente comparten datos: se ejecutan en paralelo en diferentes núcleos de procesamiento. Claramente, nosotros deseamos que los cambios que resulten de tales actividades no interfieran con unos con otros. Debido a la importancia de este problema, dedicamos una gran parte de este capítulo para procesar la sincronización y coordinación entre procesos cooperativos.
6.2 El problemade la sección crítica
Comenzamos nuestra consideración de la sincronización de procesos discutiendo el llamado problema de la sección crítica. Considere un sistema que consta de n procesos {P0, P1, ..., Pn − 1}. Cada proceso tiene un segmento de código, llamado sección crítica, en el que el proceso puede estar accediendo, y actualizando, datos que se comparten con al menos otro proceso. La característica importante del sistema es que, cuando un proceso se ejecuta en su sección crítica, no se permite que ningún otro proceso ejecute en su sección crítica. Es decir, no hay dos procesos ejecutándose en sus secciones críticas al mismo tiempo. El problema de la sección crítica es diseñar
un protocolo que los procesos pueden usar para sincronizar su actividad a fin de compartir cooperativamente los datos. Cada proceso debe solicitar permiso para ingresar en su sección crítica. La sección de código que implementa esta solicitud es la sección de entrada. La sección crítica puede ser seguida por una sección de salida. El código restante es la sección restante. La estructura general de un proceso típico es el que se muestra en la Figura 6.1. La sección de entrada y la sección de salida están encerradas en cuadros para que resalte estos importantes segmentos de código.
Una solución al problema de la sección crítica debe satisfacer los siguientes tres requisitos:
1. Exclusión mutua. Si el proceso Pi se está ejecutando en su sección crítica, entonces no puede haber otros procesos que se ejecuten en sus secciones críticas.
2. Progreso. Si no se está ejecutando ningún proceso en su sección crítica y algunos procesos
desea ingresar a sus secciones críticas, entonces sólo aquellos procesos que no están ejecutando en sus secciones restantes pueden participar en la decisión de quién entrará en su sección crítica a continuación, y esta selección no puede ser pospuesta indefinidamente.
3. Espera acotada. Existe un límite, de número de veces que otros procesos pueden ingresar a sus secciones críticas después de que un proceso ha solicitado ingresar a su sección crítica y antes de que eso ocurra Se le debe conceder la solicitud.
Figura 6.1 Estructura general de un proceso típico
Suponemos que cada proceso se ejecuta a una velocidad distinta de cero. Sin embargo, No podemos
hacer suposiciones sobre la velocidad relativa de los n procesos.
En un momento dado, muchos procesos en modo kernel pueden estar activos en El sistema operativo. Como resultado, el código que implementa un sistema operativo (código del kernel) está sujeto a varias condiciones de carrera posibles. Considere como ejemplo, una estructura de datos del kernel que mantiene una lista de todos los archivos abiertos en el sistema. Esta lista debe modificarse cuando se abre o cierra un nuevo archivo (agregando el archivo a la lista o eliminándolo de la lista). Si dos procesos fueran a abrir archivos simultáneamente, las actualizaciones separadas de esta lista podrían dar lugar a una condición de carrera.
Otro ejemplo se ilustra en la Figura 6.2. En esta situación, dos procesos, P0 y P1, están creando procesos hijos utilizando la llamada al sistema fork (). Recordemos de la Sección 3.3.1 que fork () devuelve el identificador del nuevo proceso, creado para el proceso padre. En este ejemplo, hay una condición de carrera en la variable del kernel next_available_pid que representa El valor del siguiente identificador de proceso disponible. La exclusión mutua debe cumplirse para NO asignar el mismo número de identificador de proceso a dos procesos separados.
Figura 6.2 Condición de carrera al asignar un pid.
Otras estructuras de datos del kernel que son propensas a posibles condiciones de carrera deben incluir estructuras para mantener la asignación de memoria, para mantener las listas de procesos, y para el manejo de interrupciones. Depende de los desarrolladores del kernel asegurarse de que El sistema operativo esté libre de tales condiciones de carrera.
El problema de la sección crítica podría resolverse simplemente en un entorno de un solo núcleo
si pudiéramos evitar que ocurrieran interrupciones mientras una variable compartida está siendo modificada. De esta manera, podríamos estar seguros de que la secuencia actual de las instrucciones se les permitiría ejecutar en orden sin expulsión. No se ejecutarían otras instrucciones, por lo que no se podrían realizar modificaciones inesperadas a la variable compartida.
Desafortunadamente, esta solución no es tan factible en un entorno multiprocesador. Deshabilitar las interrupciones en un multiprocesador puede llevar mucho tiempo, ya que El mensaje se pasa a todos los procesadores. Este mensaje que pasa retrasa la entrada en cada sección crítica, y la eficiencia del sistema disminuye. Considere también el efecto en el reloj de un sistema si el reloj se mantiene actualizado por interrupciones.
Se utilizan dos enfoques generales para manejar secciones críticas en los sistemas operativos: kernels apropiativos y kernels no apropiativos. Un kernel apropiativo permite que un proceso sea expulsado mientras se ejecuta en modo kernel. Un kernel no apropiativo no permite expulsar a un proceso que se ejecuta en modo kernel, sino que habrá que esperar que se bloquee, o voluntariamente cede el control de la CPU.
Obviamente, un kernel no apropiativo está esencialmente libre de condiciones de carrera en estructuras de datos del kernel, ya que solo un proceso está activo en el kernel a la vez. No podemos decir lo mismo sobre los kernels apropiativos, por lo que deben ser cuidadosamente diseñado para garantizar que los datos compartidos del kernel estén libres de condiciones de carrera. Los kernels apropiativos son especialmente difíciles de diseñar para arquitecturas SMP, ya que en estos entornos es posible que se ejecuten dos procesos en modo kernel simultáneamente en diferentes núcleos de CPU.
¿Por qué, entonces, alguien preferiría un kernel apropiativo sobre un no apropiativo? Un kernel apropiativo puede responder mejor, más rápido, ya que hay menos riesgo que un proceso en modo kernel se ejecute durante un período arbitrariamente largo antes de renunciar al procesador y dejar esperando a los procesos. (Por supuesto, este riesgo también puede ser minimizado mediante el diseño de código de kernel que no se comporte de esta manera.) Además, un kernel apropiativo es más adecuado para la planificación en tiempo real, como permitirá que un proceso en tiempo real expulse a un proceso que se ejecuta actualmente en el kernel.
6.3 La solución de Peterson
A continuación, ilustramos una solución clásica basada en software para el problema de la sección crítica, conocida como la solución de Peterson. Por la forma cómo ejecutan las instrucciones básicas de lenguaje de máquina, tales como load y store de la arquitectura de una computadora moderna, no hay garantías de que la solución de Peterson funcione correctamente en tales arquitecturas. Sin embargo, presentamos la solución porque proporciona una buena descripción algorítmica para resolver el problema de la sección crítica e ilustra Algunas de las complejidades involucradas en el diseño de software que aborda los requisitos de exclusión mutua, progreso y espera limitada.
La solución de Peterson está restringida a dos procesos que alternan la ejecución entre sus secciones críticas y las secciones restantes. Los procesos están numerados P0 y P1. Por conveniencia, cuando presentamos Pi, usamos Pj para denotar el otro proceso; es decir, j es igual a 1 - i.
La solución de Peterson requiere que los dos procesos compartan dos elementos de datos:
int turn;
boolean flag[2];
--------------------------------------------------------------------------------------------------------------------------------------
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
;
/* critical section */
flag[i] = false;
/*remainder section */
}
--------------------------------------------------------------------------------------------------------------------------------------
Figura 6.3 Laestructura del proceso Pi en la solución de Peterson.
El turno variable indica de quién es el turno para entrar en su sección crítica. Es decir, si turn == i, entonces el proceso Pi puede ejecutarse en su sección crítica. El vector flag se usa para indicar si un proceso está listo para ingresar a su sección crítica.
Por ejemplo, si flag [i] es verdadero, Pi está listo para ingresar a su sección crítica. Con una explicación completa de estas estructuras de datos, ahora estamos listos para describir el algoritmo que se muestra en la Figura 6.3.
Para ingresar a la sección crítica, el proceso Pi primero establece el indicador [i] como verdadero y
luego establece el turno al valor j, afirmando así que si el otro proceso desea ingresar a la sección crítica, puede hacerlo. Si ambos procesos intentan ingresar al mismo tiempo, el turno se establecerá en i y j aproximadamente al mismo tiempo. Sólo uno de estas tareas lo hará; y el otro lo hará luego y se sobrescribirá de inmediato.
El valor eventual de turno determina cuál de los dos procesos es permitido ingresar primero a su sección crítica.
Ahora demostramos que esta solución es correcta. Necesitamos demostrar que:
1. La exclusión mutua se preserva.
2. Se cumple el requisito de progreso.
3. Se cumple el requisito de espera limitada.
Para probar la propiedad 1, observamos que cada Pi solo ingresa a su sección crítica si se da que cualquiera de las 
flag [j] == false o 
turn == i. 
También tenga en cuenta que, si ambos procesos podrían ejecutarse en sus secciones críticas al mismo tiempo, entonces:
flag [0] == flag [1] == verdadero. 
Estas dos observaciones implican que P0 y P1 no pudieron ejecutar con éxito sus declaraciones while aproximadamente al mismo tiempo, ya que el valor del turno puede ser 0 o 1 pero no puede ser ambos. Por lo tanto, uno de los procesos, por ejemplo, Pj, deben haber ejecutado con éxito la instrucción while, mientras que Pi tuvo que ejecutar al menos una declaración adicional ("turn == j").
Entonces, en ese momento, flag [j] == verdadero y turn == j, y esta condición persistirá mientras Pj esté en su sección crítica; Como resultado, la exclusión mutua es preservada.
Para probar las propiedades 2 y 3, observamos que se puede evitar que un proceso Pi entre en la sección crítica solo si lo atascamos en el ciclo while con la condición flag [j] == true y turn == j; Este bucle es el único posible. 
Si Pj no está listo para ingresar a la sección crítica, entonces flag [j] == falso, y Pi puede ingresar en su sección crítica. 
Si Pj ha establecido la flag [j] en verdadero y luego escribe turn == i.
Si turn == i, entonces Pi ingresará a la sección crítica. 
Si Pi ha establecido la flag [i] en verdadero y luego escribe turn == j 
Si turn == j, entonces Pj ingresará a la sección crítica. 
Sin embargo, una vez que Pj sale de su sección crítica, restablecerá el flag [j] a falso, permitiendo que Pi entre en su sección crítica. 
Si Pj restablece el flag [j] a verdadero, también debe establecer turn en i. Por lo tanto, dado que Pi no cambia el valor de turn mientras se ejecuta en el while, Pi ingresará a la sección crítica (progreso) después de como máximo de una entrada de Pj (espera acotada).
Como se mencionó al comienzo de esta sección, la solución de Peterson no garantiza en arquitecturas modernas de computación ya que, para mejorar el rendimiento del sistema, los procesadores y/o compiladores pueden reordenar operaciones de lectura y escritura que no tienen dependencias. Para una aplicación de un solo hilo, este reordenamiento es irrelevante en cuanto a la corrección del programa, ya que los valores finales son consistentes con lo que se espera. (Esto es similar a equilibrar un talonario de cheques, el orden en el que se ejecutan las operaciones de crédito y el débito no son importantes, porque el saldo final seguirá siendo el mismo.) Pero para una aplicación multihilos con datos compartidos, el reordenamiento de instrucciones puede generar resultados inconsistentes o inesperados.
Como ejemplo, considere los siguientes datos que se comparten entre dos hilos:
boolean flag = false;
int x = 0;
donde el hilo 1 realiza las declaraciones
while (!flag)
;
print x;
y el hilo 2 realiza
x = 100;
flag = true;
El comportamiento esperado es, por supuesto, que el hilo 1 genera el valor 100 para la variable x. Sin embargo, como no hay dependencias de datos entre las variables flag y x, es posible que un procesador pueda reordenar las instrucciones para el Hilo 2 para que flag se asigne verdadero antes de la asignación de x = 100. En esta situación, es posible que el hilo 1 imprima 0 para la variable x. Menos obvio es que el procesador también puede reordenar las declaraciones emitidas por hilo 1 y cargue la variable x antes de cargar el valor de flag. Si esto ocurriera, el hilo 1 imprimiría 0 para la variable x incluso si las instrucciones emitidas por el hilo 2 no fueron reordenadas.
Figura 6.4 Los efectos del reordenamiento de instrucciones en la solución de Peterson.
¿Cómo afecta esto a la solución de Peterson? Considere qué sucede si las asignaciones de las dos primeras declaraciones que aparecen en la sección de entrada de La solución de Peterson en la Figura 6.3 se reordena; es posible que ambos hilos puedan estar activos en sus secciones críticas al mismo tiempo, como se muestra en la Figura 6.4.
Como verá en las siguientes secciones, la única manera de preservar la exclusión es mediante el uso de herramientas de sincronización adecuadas. Nuestra discusión de estas herramientas comienza con primitivas soportadas en hardware y continúa con abstracciones, de alto nivel, APIs basadas en software disponibles tanto para desarrolladores del kernel como programadores de aplicaciones.
6.4 Soporte de hardware para sincronización
Acabamos de describir una solución basada en software para el problema de la sección crítica. (Nos referimos a ella como una solución basada en software porque el algoritmo no tiene soporte especial del sistema operativo o de instrucciones específicas de hardware para garantizar la exclusión mutua.) Sin embargo, como se discutió, las soluciones basadas en software No garantizan que funcionen en arquitecturas informáticas modernas. 
En esta sección, presentamos tres instrucciones de hardware que brindan soporte para resolver el
problema de la sección crítica. Estas operaciones primitivas se pueden usar directamente como
herramientas de sincronización, o pueden usarse para formar la base de otros mecanismos de sincronización abstracta.
6.4.1 Barreras de memoria
En la Sección 6.3, vimos que un sistema puede reordenar instrucciones, una política que puede conducir a estados de datos poco confiables. Una arquitectura de computadora determina el modelo de memoria por el cual la memoria asistirá a un programa de aplicación. Hay dos categorías:
1. Fuertemente ordenado, donde una modificación de memoria en un procesador es Inmediatamente visible para todos los demás procesadores.
2. Débilmente ordenado, donde las modificaciones a la memoria en un procesador pueden no ser inmediatamente visible para otros procesadores.
Los modelos de memoria varían según el tipo de procesador, por lo que los desarrolladores de kernel no pueden hacer ninguna suposición con respecto a la visibilidad de modificaciones a la memoria en un multiprocesador de memoria compartida. Para abordar este problema, arquitecturas de computación proporcionan instrucciones que pueden obligar a propagar cualquier cambio en la memoria a todos los demás procesadores, asegurando así que las modificaciones de memoria sean visibles para los hilos que se ejecutan en otros procesadores. Dichas instrucciones se conocen como barreras de memoria o vallas de memoria. Cuando se realiza una instrucción de barrera de memoria,
el sistema asegura que todas los loads y stores se completen antes que otras operaciones de load o store. Por lo tanto, incluso si las instrucciones fueran reordenadas, la barrera de memoria asegura que las operaciones store se completenen memoria y sea visible para otros procesadores antes de que se realicen futuras operaciones de load o store.
Volvamos a nuestro ejemplo más reciente, en el que reordenamos las instrucciones que podrían haber dado como resultado una salida incorrecta y utilizamos una barrera de memoria para garantizar que obtenemos el resultado esperado.
Si agregamos una operación de barrera de memoria al Hilo 1
while (!flag)
memory barrier();
print x;
garantizamos que el valor de flag se carga antes que el valor de x. 
Del mismo modo, si colocamos una barrera de memoria entre las tareas realizadas por hilo 2
x = 100;
memory barrier();
flag = true;
nos aseguramos de que la asignación a x ocurra antes de la asignación a flag.
Con respecto a la solución de Peterson, podríamos colocar una barrera de memoria entre las dos primeras declaraciones de asignación en la sección de entrada para evitar el reordenamiento de las operaciones que se muestran en la Figura 6.4. Tenga en cuenta que las barreras de memoria son
operaciones de muy bajo nivel y normalmente solo las usa los desarrolladores del kernel al escribir código especializado que garantiza la exclusión mutua.
6.4.2 Instrucciones de hardware
Muchos sistemas informáticos modernos proporcionan instrucciones especiales de hardware que
nos permite probar (test) y modificar (set) el contenido de una palabra o intercambiar los contenidos de dos palabras atómicamente, es decir, como una unidad ininterrumpida. Nosotros podemos usar Estas instrucciones especiales para resolver el problema de la sección crítica de una
manera simple. En lugar de discutir una instrucción específica para una máquina específica, abstraemos los conceptos principales detrás de este tipo de instrucciones describiendo las instrucciones test_and_set () y compare_and_swap ().
boolean test_and_set (boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}
Figura 6.5 La definición de la instrucción atómica test_and_set ().
do {
while (test and set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
Figura 6.6 Implementación de exclusión mutua con test_and_set ().
La instrucción test_and_set () se puede definir como se muestra en la Figura 6.5. La característica importante de esta instrucción es que se ejecuta atómicamente. Por lo tanto, si dos instrucciones test_and_set () se ejecutan simultáneamente (cada uno en un núcleo diferente), se ejecutarán secuencialmente en algún arbitrario orden. Si la máquina admite la instrucción test_and_set (), entonces podemos implementar la exclusión mutua declarando una variable booleana lock, inicializada a falso. La estructura del proceso Pi se muestra en la Figura 6.6.
La instrucción compare_and_swap () (CAS), al igual que la instrucción test_and_set (), opera en dos palabras atómicamente, pero usa un mecanismo diferente y se basa en intercambiar el contenido de dos palabras.
La instrucción CAS opera en tres operandos y se define en la Figura 6.7. El operando value se establece en new_value sólo si la expresión (* value == expected) es cierta. Independientemente, CAS siempre devuelve el valor original del valor variable. La característica importante de esta instrucción es que es ejecutada atómicamente. Por lo tanto, si dos instrucciones CAS se ejecutan simultáneamente (cada uno en un núcleo diferente), se ejecutarán secuencialmente en algún orden arbitrario.
La exclusión mutua con CAS se puede proporcionar de la siguiente manera: una variable global
(lock) se declara y se inicializa a 0. El primer proceso que invoca compare_and_swap () establecerán el lock en 1. Luego ingresará a su sección crítica,
int compare_and_swap(int *value, int expected, int new value) {
int temp = *value;
if (*value == expected)
*value = new value;
return temp;
}
Figura 6.7 La definición de la instrucción atómica compare_and_swap ()
while (true) {
while (compare and swap(&lock, 0, 1) != 0)
; /* do nothing */
/* critical section */
lock = 0;
/* remainder section */
}
Figura 6.8 Exclusión mutua con la instrucción compare_and_swap ()
porque el valor original del lock era igual al valor expected de 0. Posteriores llamadas de compare_and_swap () no tendrán éxito, porque lock ahora no es igual al valor expected de 0. Cuando un proceso sale de su sección crítica, establece de nuevo lock a 0, lo que permite que otro proceso ingrese a su sección crítica. La estructura del proceso Pi se muestra en la Figura 6.8.
Aunque este algoritmo satisface el requisito de exclusión mutua, no cumple el requisito de espera limitada. En la figura 6.9, presentamos otro algoritmo que usa la instrucción compare_and_swap () que satisface todos los requisitos de la sección crítica. Las estructuras de datos comunes son
boolean waiting[n];
int lock;
while (true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key == 1)
key = compare and swap(&lock,0,1);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = 0;
else
waiting[j] = false;
/* remainder section */
}
Figura 6.9 Exclusión mutua de espera acotada con compare_and_swap ().
La instrucción atómica COMPARE_AND_SWAP
En arquitecturas Intel x86, la declaración del lenguaje ensamblador cmpxchg es usada para implementar la instrucción compare_and_swap (). Para hacer cumplir la ejecución atómica, el prefijo lock se utiliza para bloquear el bus mientras el operando destino se está actualizando. La forma general de esta instrucción aparece como:
lock cmpxchg <operando de destino>, <operando de origen>
Los elementos en la matriz de espera se inicializan en falso, y el lock se inicializa a 0. Para demostrar que se cumple el requisito de exclusión mutua, observamos que el proceso Pi puede ingresar a su sección crítica solo si waiting [i] == falso o key == 0. El valor de key puede convertirse en 0 solo si compare_and_swap () se ejecuta. El primer proceso para ejecutar compare_and_swap () encontrará la key== 0; todos los demás deben esperar. La variable waiting[i] puede volverse falsa solo si otro proceso deja su sección crítica; solo un waiting[i] se establece en falso, manteniendo el requisito de exclusión mutua.
Para demostrar que se cumple el requisito de progreso, observamos que los argumentos presentados para exclusión mutua también se aplican aquí, ya que un proceso que sale de la sección crítica establece el lock en 0 o establece la waiting [j] en falso. Ambos permiten un proceso que está esperando ingresar a su sección crítica para continuar.
Para demostrar que se cumple el requisito de espera limitada, observamos que, cuando un proceso deja su sección crítica, escanea la matriz que espera en el ciclo ordenando (i + 1, i + 2, ..., n - 1, 0, ..., i - 1). Designa al primer proceso en este orden que se encuentra en la sección de entrada (waiting [j] == verdadero) como el siguiente para entrar en la sección crítica. Cualquier proceso que esté esperando ingresar a su sección crítica así lo hace dentro de n - 1 turnos.
Detalles que describen la implementación de las instrucciones atómicas test_and_set () y de compare_and_swap () se analizan más a fondo en los libros de arquitectura de computadoras.
6.4.3 Variables atómicas
Normalmente, la instrucción compare_and_swap () no se usa directamente para proporcionar
exclusión mutua. Más bien, se usa como un bloque de construcción básico para construir otras herramientas que resuelven el problema de la sección crítica. Una de esas herramientas es una variable atómica, que proporciona operaciones atómicas en tipos de datos básicos como enteros
y booleanos. Sabemos por la Sección 6.1 que aumentar o disminuir un valor entero puede producir una condición de carrera. Las variables atómicas se pueden usar para garantizar la exclusión mutua en situaciones donde puede haber una carrera de datos en una variable única mientras se actualiza, como cuando se incrementa un contador. La mayoría de los sistemas que admiten variables atómicas proporcionan tipos de datos atómicos especiales,así como funciones para acceder y manipular variables atómicas.
Estas funciones a menudo se implementan mediante operaciones compare_and_swap ().
Como ejemplo, lo siguiente incrementa la variable entera atómica sequence:
increment(&sequence);
donde la función increment () se implementa utilizando la instrucción CAS:
void increment(atomic int *v)
{
int temp;
do {
temp = *v;
}
while (temp != compare_and_swap(v, temp, temp+1));
}
Es importante tener en cuenta que, aunque las variables atómicas proporcionan actualizaciones atómicas, no resuelven por completo las condiciones de carrera en todas las circunstancias. Por ejemplo, en el problema del búfer acotado descrito en la Sección 6.1, podríamos usar un entero atómico para contar (count). Esto aseguraría que las actualizaciones de contar (count) fueran atómicas. Sin embargo, los procesos de productor y consumidor también tienen bucles while cuya condición depende del valor de count. Considere una situación en la que el búfer está actualmente vacío y dos consumidores están en bucle mientras esperan count> 0. Si un productor ingresó un artículo en el búfer, ambos consumidores podrían salir de sus bucles while (ya que el count ya no sería igual a 0) y proceder a consumir, a pesar de que el valor del count solo se estableció en 1.
Las variables atómicas se usan comúnmente en los sistemas operativos, así como en aplicaciones concurrentes, aunque su uso a menudo se limita a actualizaciones individuales de datos compartidos como contadores y generadores de secuencia. En las siguientes secciones, exploramos herramientas más robustas que abordan las condiciones de carrera en situaciones de manera más generalizada.
6.5 Cerraduras (lock) Mutex
Las soluciones basadas en hardware para el problema de la sección crítica presentadas en la Sección 6.4 son complicados y generalmente inaccesibles para los programadores de aplicaciones. En cambio, los diseñadores de sistemas operativos crean herramientas de software de nivel superior para resolver el problema de la sección crítica. La más simple de estas herramientas es la lock mutex. (De hecho, el término mutex es la abreviatura de exclusión mutua). Utilizamos el lock mutex para proteger secciones críticas y así evitar condiciones de carrera. Es decir, un proceso debe adquirir el lock antes de ingresar a una sección crítica; libera el lock cuando sale de la sección crítica. La función adquirir () adquiere el lock, y la función release () libera el lock, como se ilustra en la Figura 6.10.
Un lock de exclusión mutua (mutex) tiene una variable booleana disponible cuyo valor indica si
el lock está disponible o no. Si el lock está disponible, una llamada a adquirir () tiene éxito, y el lock se considera ahora no disponible. Un proceso que intenta adquirir un lock no disponible se bloquea hasta que se libera el lock.
Figura 6.10 Solución al problema de la sección crítica usando mutex lock
La definición de adquirir () es la siguiente:
acquire() {
while (!available)
; /* busy wait */
available = false;
}
La definición de release () es la siguiente:
release() {
available = true;
}
Las llamadas a adquirir () o liberar () deben realizarse atómicamente. Por lo tanto, los locks mutex se pueden implementar utilizando la operación CAS descrita en la Sección 6.4, y dejamos la descripción de esta técnica como un ejercicio.CONTENCION (pelea) DE LOCK
Las locks tendrán contención o no. Una lock se considera con contención si un hilo se bloquea al intentar adquirir el lock. Si hay un lock disponible cuando un hilo intenta adquirirlo, el lock se considera sin contención. Las locks con Contención pueden experimentar una alta contención (un número relativamente grande de hilos que intentan adquirir el lock) o baja contención (un relativamente pequeño número de hilos que intentan adquirir el lock). Como era de esperar, Las altas contenciones de locks tienden a disminuir el rendimiento general de las aplicaciones en concurrencia.
La principal desventaja de la implementación dada aquí es que requiere (busy waiting) espera ocupada. Mientras un proceso está en su sección crítica, cualquier otro proceso que intenta ingresar a su sección crítica debe realizar un bucle continuo en la llamada a adquirir (). Este bucle continuo es claramente un problema en un sistema de multiprogramación real, donde un solo núcleo de CPU se comparte entre muchos procesos. La espera ocupada también desperdicia ciclos de CPU que algún otro proceso podría usar productivamente. (En la Sección 6.6, examinamos una estrategia que evita la espera ocupada temporalmente y pone al proceso que espera a dormir y luego lo despierta una vez que el lock se vuelve disponible.)
El tipo de lock mutex que hemos estado describiendo también se llama spinlock porque el proceso "gira" mientras espera que el lock esté disponible. (Vemos el mismo problema con los ejemplos de código que ilustran la instrucción compare_and_swap ().) Sin embargo, los Spinlocks tienen una ventaja en que no se requiere un cambio de contexto cuando un proceso debe esperar en un lock, y un cambio de contexto puede llevar un tiempo considerable. En ciertas circunstancias en multinúcleo, los spinlocks son, de hecho, la opción preferible para el lock. Si una cerradura es
sostenida por una corta duración, un hilo puede "girar" en un núcleo de procesamiento mientras que otro hilo realiza su sección crítica en otro núcleo. En los sistemas computacionales multinúcleos modernos, los spinlocks se utilizan ampliamente en muchos sistemas operativos.
En el Capítulo 7 examinamos cómo se pueden usar los locks de mutex para resolver los problemas clásicos de sincronización. También discutimos cómo son los locks mutex y los spinlocks utilizados en varios sistemas operativos, así como en Pthreads.
6.6 Semáforos
Los locks Mutex, como mencionamos, generalmente se consideran los más simples de las herramientas de sincronización. En esta sección, examinamos una herramienta más robusta que puede comportarse de manera similar a un lock de exclusión mutua pero también puede proporcionar vías más sofisticadas a los procesos para sincronizar sus actividades.
Un semáforo S es una variable entera que, aparte de la inicialización, se accede solo a través de dos operaciones atómicas estándar: wait () y signal ().
Los semáforos fueron introducidos por el informático holandés Edsger Dijkstra. A la operación wait() él la denominó originalmente P (del holandés proberen, "probar"); y a signal() la llamaba originalmente V (de verhogen, "para incrementar"). 
La definición de wait () es la siguiente:
wait(S) {
while (S <= 0)
; // busy wait
S--;
}
La definición de signal() es la siguiente:
signal(S) {
S++;
}
Todas las modificaciones al valor entero del semáforo en wait() y las operaciones de signal() deben ejecutarse atómicamente. Es decir, cuando un proceso modifica el valor del semáforo, ningún otro proceso puede modificar simultáneamente ese mismo valor de semáforo. Además, en el caso de wait(S), la prueba del valor entero de S (S ≤ 0), así como su posible modificación (S--), debe
ser ejecutado sin interrupción. Veremos cómo pueden ser implementadas estas operaciones en la Sección 6.6.2. Primero, veamos cómo se pueden usar los semáforos.
6.6.1 Uso del semáforo
Los sistemas operativos a menudo distinguen entre semáforos contador y binario El valor de un semáforo contador puede variar sobre un dominio sin restricciones. El valor de un semáforo binario sólo puede variar entre 0 y 1. Por lo tanto, los semáforos binarios se comportan de manera similar a los locks mutex. De hecho, en los sistemas que no proporcionan locks mutex, los semáforos binarios pueden ser utilizado en su lugar para proporcionar exclusión mutua.
Los semáforos contadores se pueden usar para controlar el acceso a un recurso dado que consiste en un número finito de instancias. El semáforo se inicializa a la cantidad de recursos disponibles. Cada proceso que desea utilizar un recurso realiza una operación wait () en el semáforo (disminuyendo así el contador). Cuandoun proceso libera un recurso, realiza una operación de signal() (incrementando el contador). Cuando el contador del semáforo se pone a 0, todos los recursos están siendo utilizados. Después de eso, los procesos que deseen utilizar un recurso deberán bloquearse hasta que el contador sea mayor que 0.
También podemos usar semáforos para resolver varios problemas de sincronización.
Por ejemplo, considere dos procesos que se ejecutan simultáneamente: P1 con una sentencia S1 y P2 con una sentencia S2. Supongamos que requerimos que S2 se ejecute solo después de
S1 ha completado. Podemos implementar este esquema fácilmente dejando que P1 y P2
compartan un semáforo común synch, inicializado en 0. En el proceso P1, insertamos la sentencia
S1;
signal(synch);
En el proceso P2, insertamos la sentencia
wait(synch);
S2;
Debido a que synch se inicializa a 0, P2 ejecutará S2 solo después de que P1 haya invocado
signal(synch), que es después de que se haya ejecutado la instrucción S1.
6.6.2 Implementación de semáforos
Recuerde que la implementación de locks mutex discutidos en la Sección 6.5 sufre de espera ocupada. Las definiciones de las operaciones wait () y signal () de semáforo que acabamos de describir presentan el mismo problema. Para superar este problema, podemos modificar la definición de las operaciones wait () y signal () de la siguiente manera: cuando un proceso ejecuta la operación wait () y encuentra que el valor del semáforo no es positivo, debe esperar. Sin embargo, en lugar de comprometerse en espera ocupada, el proceso puede suspenderse. La operación de suspensión coloca un proceso en una cola de espera asociada con el semáforo y el estado del proceso cambia al estado de espera. Luego el control se transfiere al Planificador de CPU, que selecciona otro proceso para ejecutar.
Un proceso que se suspende, esperando un semáforo S debe reiniciarse cuando algún otro proceso ejecute una operación de signal(). El proceso es reiniciado por una operación wakeup (), que cambia el proceso de estado de espera al estado listo. El proceso se coloca en la cola lista. (La CPU puede o no cambiar el proceso recién llegado a la cola de listos al estado de ejecución, dependiendo del algoritmo de planificación de la CPU).
Para implementar semáforos bajo esta definición, definimos un semáforo como sigue:
typedef struct {
int value;
struct process *list;
} semaphore;
Cada semáforo tiene un valor entero y una lista de procesos. Cuando un proceso debe esperar en un semáforo, se agrega a la lista de procesos. Una operación signal () elimina un proceso de la lista de procesos en espera y despierta ese proceso.
Ahora, la operación de semáforo wait () se puede definir como
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
sleep();
}
}
y la operación del semáforo signal () se puede definir como
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
La operación sleep () suspende el proceso que lo invoca. La operación wakeup (P) despierta y reanuda la ejecución de un proceso P suspendido. Estas dos operaciones son proporcionadas por el sistema operativo como llamadas del sistema.
Tenga en cuenta que en esta implementación, los valores del semáforo pueden ser negativos, mientras que en la definición clásica de semáforos con espera ocupada los valores del semáforo nunca son negativos. Si un valor de semáforo es negativo, su magnitud es la cantidad de procesos que esperan en ese semáforo. Este hecho resulta de cambiar el orden de la resta y la prueba en la implementación de la operación wait ().
La lista de procesos en espera se puede implementar fácilmente mediante un campo de enlace en
cada bloque de control de proceso (PCB). Cada semáforo contiene un valor entero y un puntero a una lista de PCB. Una forma de agregar y eliminar procesos de la lista para asegurar que la espera es acotada es usar una cola FIFO, donde el semáforo contiene punteros de cabeza y al final de la cola. En general, sin embargo, la lista puede usar cualquier estrategia de colas (DIJSTRA). El uso correcto de los semáforos no depende de una estrategia particular de colas para las listas de semáforos.
Como se mencionó, es crítico que las operaciones de semáforos se ejecuten atómicamente. Debemos garantizar que no haya dos procesos que puedan ejecutar operaciones wait () y signal ()
en el mismo semáforo al mismo tiempo. Este es un problema de sección crítica, y ​​en un entorno de procesador único, podemos resolverlo simplemente con la inhibición de interrupciones durante el tiempo que las operaciones wait () y señal () se están ejecutando. Este esquema funciona en un entorno de procesador único porque, una vez que se inhiben las interrupciones, las instrucciones de diferentes procesos no pueden ser intercaladas. Solo el proceso actualmente en ejecución se ejecuta hasta que las interrupciones son rehabilitadas y el planificador pueda recuperar el control.
En un entorno multinúcleo, las interrupciones deberían deshabilitarse en cada núcleo de procesamiento. De lo contrario, las instrucciones de diferentes procesos (que se ejecutan en diferentes núcleos) podrían estar intercaladas de alguna manera arbitraria. Pero Deshabilitar las interrupciones en cada núcleo puede ser una tarea difícil y disminuir seriamente el rendimiento.
Por lo tanto, los sistemas SMP deben proporcionar técnicas alternativas, como compare_and_swap() o spinlocks, para garantizar que se realice wait () y signal () atómicamente
Es importante admitir que no hemos eliminado completamente la espera ocupada con esta definición de las operaciones wait () y signal (). Más bien, hemos movido la espera ocupada desde la sección de entrada a las secciones críticas de las operaciones wait () y signal (). Además, se pierde muy poco esperando a secciones críticas de las operaciones wait () y signal (), y estas secciones, si son cortas (si están codificadas correctamente, no deben tener más de diez instrucciones).
Por lo tanto, la sección crítica casi nunca está ocupada y se produce una espera ocupada raramente, y por poco tiempo. Existe una situación completamente diferente con programas de aplicación cuyas secciones críticas pueden ser largas (minutos o incluso horas) o casi siempre puede estar ocupada. En tales casos, la espera ocupada Es extremadamente ineficiente.
6.7 Monitores
Aunque los semáforos proporcionan un mecanismo conveniente y efectivo para la sincronización de procesos, su uso incorrecto puede dar lugar a errores de tiempo que son difíciles de detectar, ya que estos errores ocurren sólo si ocurren algunas secuencias de ejecución particulares, y estas no siempre ocurren (son poco probables). 
Hemos visto un ejemplo de tales errores en el uso de la variable count en nuestra solución al problema productor-consumidor (Sección 6.1). En ese ejemplo, ocurrió un problema (raramente), e incluso entonces el valor de count pareció ser ​​razonable, solo por 1. Sin embargo, la solución obviamente no es aceptable Es por esta razón que las cerraduras (lock) mutex y los semáforos fueron introducidos.
Desafortunadamente, tales errores de sincronización aún pueden ocurrir cuando se usan locks de mutex o semáforos. Para ilustrar cómo, revisamos la solución de semáforo al problema de la sección crítica. Todos los procesos comparten una variable de semáforo binario o un mutex, que se inicializa en 1. Cada proceso debe ejecutar wait (mutex) antes de entrar en sección crítica y signal (mutex) después de la sección crítica. Si esta secuencia no se la cumple, dos procesos pueden estar en sus secciones críticas simultáneamente. A continuación, enumeramos varias dificultades que pueden ocurrir. Tenga en cuenta que estas dificultades surgen incluso si un solo proceso no se comporta bien. Esta situación puede ser causada por un error de programación bien intencionado o un programador que no coopere.
• Suponga que un programa intercambia el orden en el que wait () y las operaciones de signal () en el semáforo mutex se ejecutan,lo que resulta en la siguiente ejecución:
signal(mutex);
...
critical section
...
wait(mutex);
En esta situación, varios procesos pueden estar ejecutándose en sus secciones críticas simultáneamente, violando el requisito de exclusión mutua. Este error puede descubrirse solo si varios procesos están activos simultáneamente en sus secciones críticas. Tenga en cuenta que esta situación puede no ser siempre reproducible.
• Suponga que un programa reemplaza signal (mutex) con wait (mutex). Es decir, se ejecuta
wait(mutex);
...
critical section
...
wait(mutex);
En este caso, el proceso se bloqueará permanentemente en la segunda llamada a wait (), ya que el semáforo ya no está disponible.
• Suponga que un proceso omite la wait (mutex), o la signal (mutex), o ambos. En este caso, se viola la exclusión mutua o el proceso se bloquea permanente.
Estos ejemplos ilustran que varios tipos de errores pueden generarse fácilmente cuando los programadores usan incorrectamente los semáforos o locks mutex para resolver el problema de la sección crítica. Una estrategia para lidiar con tales errores es incorporar herramientas de sincronización simples como construcciones de lenguaje de alto nivel. En esta sección, describimos una construcción fundamental de sincronización de alto nivel: El tipo monitor.
6.7.1 Uso del monitor
Un tipo de datos abstracto, o ADT, encapsula los datos con un conjunto de funciones para
operar sobre esos datos que son independientes de cualquier implementación específica del ADT. Un tipo de monitor es un ADT que incluye un conjunto de operaciones de programas definidos por el programador que se proporcionan con exclusión mutua dentro del monitor.
El tipo de monitor también declara las variables cuyos valores definen el estado de una instancia de ese tipo, junto con los cuerpos de funciones que operan en esas variables. La sintaxis de un tipo de monitor se muestra en la Figura 6.11. 
monitor monitor name
{
/* shared variable declarations */
function P1 ( . . . ) {
. . .
}
function P2 ( . . . ) {
. . .
}
.
.
.
function Pn ( . . . ) {
. . .
}
initialization code ( . . . ) {
. . .
}
}
Figura 6.11 Sintaxis de pseudocódigo de un monitor.
La representación de un tipo monitor no puede ser utilizado directamente por los diversos procesos.
Por lo tanto, una función definida dentro de un monitor solo puede acceder a esas variables declaradas localmente dentro del monitor y sus parámetros formales. Del mismo modo, sólo se puede acceder a las variables locales de un monitor mediante las funciones locales.
La construcción del monitor asegura que solo un proceso a la vez esté activo dentro del monitor. En consecuencia, el programador no necesita codificar esta restricción de sincronización explícitamente (Figura 6.12). Sin embargo, la construcción monitor, como se ha definido hasta ahora, no es lo suficientemente poderosa para modelar algunos esquemas de sincronización. Para este propósito, necesitamos definir mecanismos de sincronización adicional. Estos mecanismos son proporcionados por la construcción condición. Un programador que necesita escribir una sincronización a medida
El esquema puede definir una o más variables de tipo condición:
condition x, y;
Las únicas operaciones que se pueden invocar en una variable de condición son wait () y signal ().
La operación:
x.wait ();
significa que el proceso que invoca esta operación se suspende hasta que otro invoca el proceso
x.signal ();
Figura 6.12 Vista esquemática de un monitor.
La operación x.signal () reanuda exactamente un proceso suspendido. Si el proceso no se suspende, entonces la operación signal () no tiene efecto; eso es el estado de x es el mismo que si la operación nunca se hubiera ejecutado (Figura 6.13). Contraste esta operación con la operación de signal () asociada con semáforos, que siempre afectan el estado del semáforo.
Ahora suponga que, cuando un proceso P invoca la operación x.signal (), existe un proceso suspendido Q asociado con la condición x. Claramente, Si el proceso suspendido Q puede reanudar su ejecución, el proceso P debe esperar. De lo contrario, tanto P como Q estarían activos simultáneamente dentro del monitor. Tenga en cuenta, sin embargo, que conceptualmente ambos procesos pueden Continuar con su ejecución. Existen dos posibilidades:
1. Señale y espere. P espera hasta que Q abandone el monitor o que espere a otra condición.
2. Señale y continúe. Q espera a que P salga del monitor o espera por otra condición
Existen argumentos razonables a favor de adoptar cualquiera de las opciones. Por un lado, dado que P ya se estaba ejecutando en el monitor, El método señalar y continuar parece más razonable. Por otro lado, si permitimos que el hilo P continúe, para cuando Q se reanude, la condición lógica para la cual Q fue a esperar puede que ya se sostenga. Existe también un compromiso entre estas dos opciones: cuando el hilo P ejecuta la operación señalar, inmediatamente abandona el monitor. Por lo tanto, Q se reanuda inmediatamente.
Figura 6.13 Monitor con variables de condición.
Muchos lenguajes de programación han incorporado la idea del monitor como se describe en esta sección, incluidos Java y C #. Otros idiomas, como Erlang: proporciona soporte de concurrencia utilizando un mecanismo similar.
6.7.2 Implementación de un monitor utilizando semáforos
Ahora consideramos una posible implementación del mecanismo de monitor usando semáforos Para cada monitor, un semáforo binario mutex (inicializado a 1) es proporcionado para garantizar la exclusión mutua. Un proceso debe ejecutar wait (mutex) antes de ingresar al monitor y debe ejecutar signal (mutex) después de salir del monitor.
Utilizaremos el esquema de señalar y esperar en nuestra implementación. Ya que el proceso que señaliza debe esperar hasta que el proceso reanudado se vaya o espere, a continuación, se introduce un semáforo binario adicional, next inicializado a 0. El proceso que señaliza pueden usar next para suspenderse a sí mismo. Una variable entera next_count también se proporciona para contar el número de procesos suspendidos en next. Por lo tanto, cada función externa F se reemplaza por
wait(mutex);
...
body of F
...
if (next count > 0)
signal(next);
else
signal(mutex);
Se garantiza la exclusión mutua dentro de un monitor.
Ahora podemos describir cómo se implementan las variables de condición también.
Para cada condición x, introducimos un semáforo binario x_sem y una variable entera x_count, ambos inicializados a 0. 
La operación x.wait () ahora puede ser implementado como
x_count++;
if (next_count > 0)
signal(next);
else
signal(mutex);
wait(x_sem);
x count--;
La operación x.signal () se puede implementar como
if (x count > 0) {
next_count++;
signal(x_sem);
wait(next);
next_count--;
}
Esta implementación es aplicable a las definiciones de monitores dadas por Hoare y Brinch-Hansen (ver las notas bibliográficas al final del capítulo). En algunos casos, sin embargo, la generalidad de la implementación es innecesaria, y es posible una mejora significativa en la eficiencia este problema para usted en el ejercicio 6.27.
monitor ResourceAllocator
{
boolean busy;
condition x;
void acquire(int time) {
if (busy)
x.wait(time);
busy = true;
}
void release() {
busy = false;
x.signal();
}
initialization code() {
busy = false;
}
}
Figura 6.14 Un monitor para asignar un solo recurso.
6.7.3 Reanudar procesos dentro de un monitor
Pasamos ahora al tema del orden de reanudación de procesos dentro de un monitor. Si varios procesos están suspendidos en la condición x, y una operación x.signal () es ejecutada por algún proceso, entonces, ¿cómo determinamos cuál de los procesos suspendidos se deben reanudar a continuación? Una solución simple es usar un orden (FCFS), de modo que el proceso que ha esperado por más tiempo se reanuda primero. En muchas circunstancias, sin embargo, ese simple
esquema de planificación no es adecuado. En estas circunstancias, la construcción espera condicional puede ser utilizada. Esta construcción tiene la forma:
x.wait (c);
dondec es una expresión entera que se evalúa cuando la operación wait () es ejecutada. El valor de c, que se llama número de prioridad, se almacena con el nombre del proceso que está suspendido. Cuando se ejecuta x.signal () el proceso con el número de prioridad más pequeño se reanuda a continuación.
Para ilustrar este nuevo mecanismo, considere el monitor ResourceAllocator se muestra en la Figura 6.14, que controla la asignación de un solo recurso entre procesos competidores. Cada proceso, al solicitar una asignación de este recurso, especifica el tiempo máximo que planea usar el recurso. El monitor asigna el recurso al proceso que tiene la solicitud de asignación de tiempo más corta. Un proceso que necesita acceder al recurso en cuestión debe observar la siguiente secuencia:
R.acquire(t);
...
access the resource;
...
R.release();
donde R es una instancia de tipo ResourceAllocator.
Desafortunadamente, el concepto de monitor no puede garantizar que lo anterior Se observará la secuencia de acceso. En particular, los siguientes problemas pueden ocurrir:
• Un proceso puede acceder a un recurso sin obtener primero el permiso de acceso al recurso
• Es posible que un proceso nunca libere un recurso una vez que se le ha otorgado acceso al recurso
• Un proceso podría intentar liberar un recurso que nunca solicitó.
• Un proceso puede solicitar el mismo recurso dos veces (sin liberar el primer recurso).
Las mismas dificultades se encuentran con el uso de semáforos, y estas dificultades son similares en naturaleza a las que nos animaron a desarrollar en primer lugar la construcción monitor. Anteriormente, teníamos que preocuparnos por el uso correcto de los semáforos. Ahora, tenemos que preocuparnos por el uso correcto de las operaciones definidas por el programador de nivel superior, con las cuales el compilador no nos puede ayudar.
Una posible solución al problema actual es incluir las operaciones de acceso a los recursos dentro del monitor ResourceAllocator. Sin embargo, usando esta solución significará que la planificación se realiza de acuerdo con el algoritmo de función integrada de planificación-monitor en lugar del que hemos codificado.
Para asegurar que los procesos observen las secuencias apropiadas, debemos inspeccionar todos los programas que hacen uso del monitor ResourceAllocator y la gestión de su recurso. Debemos verificar dos condiciones para establecer la corrección de este sistema. Primero, los procesos de usuario siempre deben hacer sus llamadas en el monitor en una secuencia correcta. En segundo lugar, debemos estar seguros de que un proceso no-cooperativo no ignora simplemente la puerta de enlace de exclusión mutua proporcionada por el supervisor e intentar acceder al recurso compartido directamente, sin usar el protocolo de acceso. Sólo si se pueden garantizar estas dos condiciones podemos garantizar que no ocurrirán errores dependientes del tiempo y que el algoritmo de planificación no fallará.
Aunque esta inspección puede ser posible para un sistema pequeño y estático, No es razonable para un sistema grande o un sistema dinámico. 
Este problema de control de acceso sólo puede resolverse mediante el uso de mecanismos adicionales que se describen en el Capítulo 17.
6.8 vitalidad
Una consecuencia del uso de herramientas de sincronización para coordinar el acceso a secciones críticas es la posibilidad de que un proceso intente ingresar a su sección crítica deberá esperar indefinidamente. Recordemos que en la Sección 6.2, describimos tres criterios que Las soluciones al problema de la sección crítica deben satisfacer. La espera indefinida viola dos de estos: los criterios de: progreso y espera acotada.
La vitalidad se refiere a un conjunto de propiedades que un sistema debe satisfacer para garantizar
que los procesos avanzan durante su ciclo de vida de ejecución. Un proceso que espera indefinidamente bajo las circunstancias recién descritas es un ejemplo de "Fracaso de vitalidad".
Hay muchas formas diferentes de falla de vitalidad; sin embargo, todos son generalmente
caracterizados por un bajo rendimiento y capacidad de respuesta. Un muy simple ejemplo de falla de vida es un bucle infinito. Un bucle de espera ocupado presenta el posibilidad de una falla en la vitalidad, especialmente si un proceso puede repetir largo periodo de tiempo. Los Esfuerzos para proporcionar exclusión mutua utilizando herramientas como Los locks de mutex y los semáforos a menudo pueden conducir a tales fallas en la programación concurrente.
En esta sección, exploramos dos situaciones que pueden conducir a Fallas de vitalidad.
6.8.1 Deadlock
La implementación de un semáforo con una cola de espera puede resultar en una situación en la que dos o más procesos esperan indefinidamente un evento eso solo puede ser causado por uno de los procesos de espera. El evento en cuestión es la ejecución de una operación de signal (). Cuando se alcanza tal estado, Se dice que los procesos están estancados (deadlockead)
Para ilustrar esto, considere un sistema que consta de dos procesos, P0 y P1, cada uno accediendo a dos semáforos, S y Q, establecidos en el valor 1:
P0 				P1
wait(S); 			wait(Q);
wait(Q); 			wait(S);
. 				.
. 				.
. 				.
signal(S); 			signal(Q);
signal(Q); 			signal(S);
Suponga que P0 ejecuta wait (S) y luego P1 ejecuta wait (Q) .Cuando P0 ejecuta wait (Q), debe esperar hasta que P1 ejecute la signal (Q). Del mismo modo, cuando P1 ejecuta la wait (S), debe esperar hasta que P0 ejecute la signal (S). Ya que estos las operaciones de signal () no se pueden ejecutar, P0 y P1 están en deadlockead (trabados).
Decimos que un conjunto de procesos está en un deadlock cuando cada proceso en el conjunto está esperando un evento que solo puede ser causado por otro proceso en el conjunto. Los "eventos" que nos interesan principalmente aquí son la adquisición y liberación de recursos como locks de mutex y semáforos. Otros tipos de eventos pueden provocar deadlock, como mostramos con más detalle en el Capítulo 8. En ese capítulo, describimos varios mecanismos para lidiar con el problema de deadlock, así como otras formas de fallas de vitalidad.
6.8.2 Inversión de prioridad
Un desafío de planificación surge cuando un proceso de mayor prioridad necesita leer o modificar los datos del kernel a los que está accediendo actualmente un proceso de prioridad inferior, o una cadena de procesos de menor prioridad. Dado que los datos del kernel son típicamente protegido con un candado, el proceso de mayor prioridad tendrá que esperar a que uno de menor prioridad termine de usar el recurso. La situación se vuelve más complicada si el proceso de menor prioridad se expulsa a favor de otro proceso de mayor prioridad.
Como ejemplo, supongamos que tenemos tres procesos: L, M y H, cuyas prioridades siguen el orden L <M <H. Suponga que el proceso H requiere un semáforo S con wait(S), el que actualmente se encuentra en posesión del proceso L. Normalmente, el proceso H esperaría a que L termine de usar el recurso S. Sin embargo, ahora suponga ese proceso M se vuelve ejecutable, lo que evita el proceso L. Indirectamente, El proceso con una prioridad más baja (proceso M) ha afectado el tiempo que dura el proceso H debe esperar a que L renuncie al recurso S.
Este problema de vitalidad se conoce como inversión de prioridad, y puede ocurrir solo en sistemas con más de dos prioridades. Típicamente, la inversión de prioridad se trata con un protocolo de herencia prioritario. De acuerdo con este protocolo, todos los procesos que acceden a los recursos necesitan la prioridad más alta, o sea que el proceso deberá heredar la prioridad más alta hasta que termine de usar los recursos en cuestión. Cuando haya terminado, sus prioridades volverán a sus valores originales. En el ejemplo anterior, un protocolo de herencia prioritaria permitiría el proceso L
heredar temporalmente la prioridad del proceso H, evitando así que el proceso M lo expulse antes de completar la ejecución con el recurso. Cuando el proceso L haya terminado de usar el recurso S,
renunciaríaa su prioridad heredada de H y asumiría su prioridad original. Como el recurso S ahora estaría disponible, el proceso H, no M, sería el siguiente que se ejecute.
6.9 Evaluación
Hemos descrito varias herramientas de sincronización diferentes, que pueden usarse para Resolver el problema de la sección crítica. Dada la correcta implementación y uso, estas herramientas se pueden utilizar de manera efectiva para garantizar la exclusión mutua, así como orientar los problemas de vitalidad. Con el crecimiento de los programas concurrentes que aprovechan el
poder de los sistemas de computación multinúcleo modernos, se está viendo el rendimiento de las herramientas de sincronización. Tratando de identificar cuándo usar qué herramienta puede ser un desafío desalentador. En esta sección, presentamos algunas estrategias simples para determinar cuándo usar una herramienta de sincronización específica.
Las soluciones de hardware descritas en la Sección 6.4 se consideran de muy bajo nivel y generalmente se utilizan como bases para construir otra herramienta de sincronización, como locks (cerraduras) mutex. Sin embargo, ha habido un enfoque reciente sobre el uso de la instrucción CAS para construir algoritmos locks libres que proporcionen protección contra condiciones de carrera sin
requerir la sobrecarga del lock. Aunque estas soluciones sin lock están ganando popularidad debido 
a la baja sobrecarga y la capacidad de escalar, los algoritmos en sí mismos son a menudo difíciles de desarrollar y probar. (En los ejercicios al final de este capítulo, le pedimos que evalúe la corrección de una pila de lock libres).
Los enfoques basados ​​en CAS se consideran un enfoque optimista: usted al ser optimista primero actualice una variable y luego use la detección de colisión para ver si otro hilo está actualizando la variable al mismo tiempo. Si es así, repetidamente Vuelva a intentar la operación hasta que se actualice correctamente sin conflicto. El lock de Exclusión mutua, por el contrario, se considera una estrategia pesimista; ya asumes que otro hilo está actualizando simultáneamente la variable, por lo que pesimistamente adquiere el lock antes de realizar cualquier actualización.INVERSIÓN de PRIORIDAD Y EL BUSCADOR DE MARTE
La inversión de prioridad puede ser más que un inconveniente de planificación. En sistemas
con limitaciones de tiempo estrictas, como los sistemas en tiempo real, la inversión de prioridad puede hacer que un proceso tarde más de lo debido para llevar a cabo una tarea. Cuando eso sucede, otras fallas pueden caer en cascada, resultando en fallas del sistema.
Considere el Mars Pathfinder, una sonda espacial de la NASA que posó un robot, el
Rover Sojourner, en Marte en 1997 para realizar experimentos. Poco después que Sojourner empezó a operar, comenzó a experimentar frecuentes reinicios de computadora.
Cada arranque, reinicia todo el hardware y el software, incluidas las comunicaciones.
Si el problema no se hubiera resuelto, Sojourner habría fallado en su misión
El problema fue causado por el hecho de que una tarea de alta prioridad, "bc_dist" estaba tardando más de lo esperado en completar su trabajo. Esta tarea estaba siendo obligada a esperar un recurso compartido que estaba en manos de la Tarea "ASI / MET" de prioridad inferior, que a su vez fue reemplazada por múltiples Tareas de prioridades medias. La tarea "bc_dist" se detendría esperando el recurso compartido, y en última instancia, la tarea "bc_sched" descubriría el problema y realizaría el Reinicio. El Sojourner sufría un caso típico de inversión prioritaria El sistema operativo del Sojourner era el VxWorks un SO de tiempo real, que tenía una variable global para habilitar la herencia prioridad en todos los semáforos Después de la prueba, la variable se estableció en Sojourner (¡en Marte!), y el problema fue resuelto.
Una descripción completa del problema, su detección y su solución fue escrita por el líder del equipo de software y está disponible en http://research.microsoft.com/en-us/um/people/mbj/mars_pathfinder /authorive_account.html
Las siguientes pautas identifican reglas generales relativas al rendimiento de las diferencias entre la sincronización basada en CAS y la sincronización tradicional (como locks de mutex y semáforos) bajo diferentes cargas de contención:
• Sin contención. Aunque ambas opciones son generalmente rápidas, la protección CAS
será algo más rápido que la sincronización tradicional.
• Contención moderada. La protección de CAS será más rápida, posiblemente mucho más rápida
—Que la sincronización tradicional
• Alta contención. Cuando hay mucha pelea por un recurso, la sincronización tradicional finalmente será más rápida que la sincronización basada en CAS.
La contención moderada es particularmente interesante de examinar. En este escenario, la operación CAS tiene éxito la mayor parte del tiempo, y cuando falla, iterará a través del ciclo que se muestra en la Figura 6.8 solo unas pocas veces antes de tener éxito.
En comparación, con el lock de exclusión mutua, cualquier intento de adquirir un lock muy solicitado resultará en un código más complicado ya que requiere mucho tiempo de ejecución, ya que suspende un hilo y lo coloca en una cola de espera, lo que requiere un cambio de contexto a otro hilo.
La elección de un mecanismo que aborde las condiciones de carrera también puede afectar el rendimiento del sistema. Por ejemplo, las variables atómicas son mucho más ligeros peso que las cerraduras tradicionales, y generalmente son más apropiadas que los mutex locks o semáforos para actualizaciones individuales de variables compartidas, como contadores. También vemos esto en el diseño de sistemas operativos donde se usan spinlocks en sistemas multiprocesador cuando las cerraduras se mantienen por períodos cortos. En general, los locks de mutex son más simples y requieren menos sobrecarga que los semáforos y son preferible a los semáforos binarios para proteger el acceso a una sección crítica. Sin embargo, para algunos usos, como controlar el acceso a un número finito de recursos: un semáforo contador es generalmente más apropiado que un Lock de mutex. Del mismo modo, en algunos casos, se puede preferir un lock de lector-escritor sobre
un lock de exclusión mutua, ya que permite un mayor grado de concurrencia (es decir, múltiples
lectores).
El atractivo de las herramientas de nivel superior como monitores y variables de condición se basa en su simplicidad y facilidad de uso. Sin embargo, tales herramientas pueden tener sobrecargas (overhead) significativos y, dependiendo de su implementación, pueden ser probablemente en menor escala en situaciones muy contenciosas.
Afortunadamente, hay mucha investigación actual hacia el desarrollo de Herramientas escalables y eficientes que abordan las demandas de la programación concurrente. Algunos Ejemplos incluyen:
• Diseño de compiladores que generan código más eficiente.
• Desarrollo de lenguajes que brindan soporte para la programación concurrente.
• Mejora del rendimiento de las bibliotecas y API existentes.
En el próximo capítulo, examinamos cómo varios sistemas operativos y APIs disponibles para que los desarrolladores implementen las herramientas de sincronización presentadas en este capítulo.
6.10 Resumen
• Se produce una condición de carrera cuando los procesos tienen acceso concurrente a datos y el resultado final depende del orden particular en el que los accesos ocurren. Las condiciones de carrera pueden resultar en valores corruptos de datos compartidos
• Una sección crítica es una sección de código donde se pueden manipular los datos compartidos.
y una posible condición de carrera puede ocurrir. El problema de la sección crítica es diseñar un protocolo mediante el cual los procesos puedan sincronizar su actividad y compartir cooperativamente los datos.
• Una solución al problema de la sección crítica debe satisfacer los siguientes tres requisitos: 
(1) exclusión mutua, 
(2) progreso y 
(3) espera acotada.
La exclusión mutua asegura que solo un proceso a la vez estéactivo en su sección crítica. 
El progreso asegura que los programas determinarán cooperativamente qué proceso entrará a continuación en su sección crítica.
La espera limitada acota el tiempo que esperará un programa antes de que pueda ingresar a su sección crítica.
• Soluciones de software para el problema de la sección crítica, como la solución de Peterson,
no funcionan bien en arquitecturas informáticas modernas.
• El soporte de hardware para el problema de la sección crítica incluye barreras de memoria;
instrucciones de hardware, como la instrucción de compare_and_swap y variables atómicas
• Un lock mutex proporciona exclusión mutua al requerir que un proceso adquiera un lock antes de entrar en una sección crítica y liberar el lock al salir de la sección crítica.
• Los semáforos, como las cerraduras mutex (locks), se pueden usar para proporcionar exclusión mutua. Sin embargo, mientras que un lock mutex tiene un valor binario que indica si el lock está disponible o no, un semáforo tiene un valor entero y, por lo tanto, puede ser de utilidad para resolver una variedad de problemas de sincronización.
• Un monitor es un tipo de datos abstracto que proporciona una forma de alto nivel de Sincronización de procesos. Un monitor usa variables de condición que permiten a los procesos esperar que ciertas condiciones se cumplan y señalar a otro proceso cuando las condiciones se han cumplido.
• Las soluciones al problema de la sección crítica pueden sufrir problemas de vitalidad (Liveness), incluyendo deadlock.
• Las diversas herramientas que se pueden utilizar para resolver el problema de la sección crítica, así como para sincronizar la actividad de los procesos, se puede evaluar bajo distintos niveles de contención (pelea por los recursos). Algunas herramientas funcionan mejor bajo ciertas contiendas que otros.