En la programación concurrente (también conocida como programación paralela), un monitor es una construcción de sincronización que permite que los subprocesos tengan exclusión mutua y la capacidad de esperar (bloquear) a que una determinada condición se vuelva falsa. Los monitores también tienen un mecanismo para señalar a otros subprocesos que su condición se ha cumplido. Un monitor consta de un objeto mutex (bloqueo) y variables de condición . Una variable de condiciónBásicamente es un contenedor de hilos que esperan una determinada condición. Los monitores proporcionan un mecanismo para que los subprocesos cedan temporalmente el acceso exclusivo a fin de esperar a que se cumpla alguna condición, antes de recuperar el acceso exclusivo y reanudar su tarea.
Otra definición de monitor es una clase , objeto o módulo seguro para subprocesos que envuelve un mutex para permitir de forma segura el acceso a un método o variable por más de un subproceso . La característica definitoria de un monitor es que sus métodos se ejecutan con exclusión mutua : en cada momento, como máximo un hilo puede estar ejecutando cualquiera de sus métodos . Al usar una o más variables de condición, también puede proporcionar la capacidad de que los subprocesos esperen en una condición determinada (por lo tanto, se usa la definición anterior de "monitor"). En el resto de este artículo, este sentido de "monitor" se denominará "objeto / clase / módulo seguro para subprocesos".
Los monitores fueron inventados por Per Brinch Hansen [1] y CAR Hoare , [2] y se implementaron por primera vez en el lenguaje Concurrent Pascal de Brinch Hansen . [3]
Exclusión mutua
Como ejemplo simple, considere un objeto seguro para subprocesos para realizar transacciones en una cuenta bancaria:
clase de monitor Cuenta { saldo int privado : = 0 saldo invariante > = 0 método público booleano retirar ( cantidad int ) condición previa cantidad> = 0 { if balancereturn false } else { saldo: = saldo - monto volver verdadero } } depósito de método público ( cantidad int ) cantidad de condición previa > = 0 { saldo: = saldo + monto }}
Mientras un subproceso está ejecutando un método de un objeto seguro para subprocesos, se dice que ocupa el objeto, manteniendo su mutex (bloqueo) . Los objetos seguros para subprocesos se implementan para hacer cumplir que en cada momento, como máximo un subproceso puede ocupar el objeto . El bloqueo, que inicialmente está desbloqueado, se bloquea al comienzo de cada método público y se desbloquea en cada retorno de cada método público.
Al llamar a uno de los métodos, un subproceso debe esperar hasta que ningún otro subproceso esté ejecutando ninguno de los métodos del objeto seguro para subprocesos antes de iniciar la ejecución de su método. Tenga en cuenta que sin esta exclusión mutua, en el ejemplo presente, dos subprocesos podrían hacer que se pierda o se gane dinero sin ningún motivo. Por ejemplo, dos subprocesos que retiran 1000 de la cuenta podrían devolver el resultado verdadero, mientras que el saldo se redujo solo en 1000, de la siguiente manera: primero, ambos subprocesos obtienen el saldo actual, lo encuentran mayor que 1000 y le restan 1000; luego, ambos hilos almacenan el saldo y regresan.
La "clase de monitor" de azúcar sintáctica en el ejemplo anterior está implementando la siguiente representación básica del código, envolviendo la ejecución de cada función en mutexes:
class Account { bloqueo privado myLock saldo int privado : = 0 saldo invariante > = 0 método público booleano retirar ( cantidad int ) condición previa cantidad> = 0 { myLock.acquire () intente { si el saldodevolver falso } si no { saldo: = saldo - monto volver verdadero } } finalmente { myLock.release () } } depósito de método público ( cantidad int ) cantidad de condición previa > = 0 { myLock.acquire () prueba { saldo: = saldo + monto } finalmente { myLock.release () } }}
Variables de condición
Planteamiento del problema
Para muchas aplicaciones, la exclusión mutua no es suficiente. Es posible que los subprocesos que intenten realizar una operación deban esperar hasta que se cumpla alguna condición P. Un bucle de espera ocupado
mientras que no ( P ) no omitir
no funcionará, ya que la exclusión mutua evitará que cualquier otro hilo ingrese al monitor para que la condición sea verdadera. Existen tales Otros "soluciones" como teniendo un bucle que desbloquea el monitor, espera una cierta cantidad de tiempo, se bloquea el monitor y controles para la condición P . Teóricamente, funciona y no se bloqueará, pero surgen problemas. Es difícil decidir una cantidad adecuada de tiempo de espera, demasiado pequeño y el hilo acaparará la CPU, demasiado grande y aparentemente no responderá. Lo que se necesita es una forma de señalar al hilo cuando la condición P es verdadera (o podría ser verdadera).
Estudio de caso: problema clásico del productor / consumidor acotado
Un problema clásico de concurrencia es el del productor / consumidor limitado , en el que hay una cola o búfer en anillo de tareas con un tamaño máximo, con uno o más subprocesos que son subprocesos "productores" que agregan tareas a la cola, y uno o más otros subprocesos son subprocesos "consumidores" que eliminan tareas de la cola. Se supone que la cola no es segura para subprocesos en sí misma y puede estar vacía, llena o entre vacía y llena. Siempre que la cola esté llena de tareas, necesitamos que los subprocesos del productor se bloqueen hasta que haya espacio para las tareas de eliminación de los subprocesos del consumidor. Por otro lado, siempre que la cola está vacía, necesitamos que los subprocesos del consumidor se bloqueen hasta que haya más tareas disponibles debido a que los subprocesos del productor los agregan.
Como la cola es un objeto concurrente compartido entre subprocesos, los accesos a ella deben hacerse atómicos , porque la cola se puede poner en un estado inconsistente durante el transcurso del acceso a la cola que nunca debe exponerse entre subprocesos. Así, cualquier código que acceda a la cola constituye un tramo crítico que debe sincronizarse por exclusión mutua. Si el código y las instrucciones del procesador en secciones críticas de código que acceden a la cola pueden ser intercaladas por cambios de contexto arbitrarios entre subprocesos en el mismo procesador o por subprocesos que se ejecutan simultáneamente en múltiples procesadores, entonces existe el riesgo de exponer un estado inconsistente y causar condiciones de carrera. .
Incorrecto sin sincronización
Un enfoque ingenuo es diseñar el código con espera ocupada y sin sincronización, haciendo que el código esté sujeto a condiciones de carrera:
cola RingBuffer global ; // Un búfer circular de tareas que no es seguro para subprocesos. // Método que representa el comportamiento de cada hilo productor: método público productor () { while ( verdadero ) { tarea myTask = ...; // El productor realiza una nueva tarea para agregar. while ( queue . isFull ()) {} // Ocupado: espera hasta que la cola no esté llena. cola . poner en cola ( myTask ); // Agrega la tarea a la cola. } } // Método que representa el comportamiento de cada hilo consumidor: método público consumidor () { while ( true ) { while ( queue . IsEmpty ()) {} // Ocupado: espera hasta que la cola no esté vacía. myTask = cola . dequeue (); // Saque una tarea de la cola. hacerCosas ( myTask ); // Ve y haz algo con la tarea. } }
Este código tiene un grave problema en el sentido de que los accesos a la cola pueden interrumpirse e intercalar con los accesos de otros subprocesos a la cola. Los métodos queue.enqueue y queue.dequeue probablemente tengan instrucciones para actualizar las variables de los miembros de la cola, como su tamaño, posiciones inicial y final, asignación y asignación de elementos de la cola, etc. Además, queue.isEmpty () y queue.isFull Los métodos () también leen este estado compartido. Si se permite intercalar subprocesos de productor / consumidor durante las llamadas para poner en cola / sacar de cola, entonces se puede exponer un estado inconsistente de la cola, lo que da lugar a condiciones de carrera. Además, si un consumidor hace que la cola esté vacía entre la salida de otro consumidor de la espera ocupada y la llamada "sacar de cola", entonces el segundo consumidor intentará salir de la cola de una cola vacía, lo que provocará un error. Del mismo modo, si un productor llena la cola entre la salida de la espera ocupada y la llamada de otro productor a "enqueue", el segundo productor intentará agregar a una cola completa, lo que provocará un error.
Spin-esperando
Un enfoque ingenuo para lograr la sincronización, como se mencionó anteriormente, es usar la " espera de giro ", en la que se usa un mutex para proteger las secciones críticas del código y la espera de ocupado todavía se usa, con el bloqueo adquirido y liberado en entre cada verificación de espera ocupada.
cola RingBuffer global ; // Un búfer circular de tareas que no es seguro para subprocesos. global Lock queueLock ; // Un mutex para el búfer de anillo de tareas. // Método que representa el comportamiento de cada hilo productor: método público productor () { while ( verdadero ) { tarea myTask = ...; // El productor realiza una nueva tarea para agregar. queueLock . adquirir (); // Adquirir bloqueo para la comprobación inicial de espera ocupada. while ( queue . isFull ()) { // Ocupado: espera hasta que la cola no esté llena. queueLock . liberación (); // Elimine el bloqueo temporalmente para permitir la posibilidad de que otros subprocesos // necesiten que se ejecute queueLock para que un consumidor pueda realizar una tarea. queueLock . adquirir (); // Vuelva a adquirir el bloqueo para la próxima llamada a "queue.isFull ()". } cola . poner en cola ( myTask ); // Agrega la tarea a la cola. queueLock . liberación (); // Elimina el bloqueo de la cola hasta que lo necesitemos nuevamente para agregar la siguiente tarea. } }// Método que representa el comportamiento de cada hilo consumidor: método público consumidor () { while ( verdadero ) { queueLock . adquirir (); // Adquirir bloqueo para la comprobación inicial de espera ocupada. while ( queue . isEmpty ()) { // Ocupado-espera hasta que la cola no esté vacía. queueLock . liberación (); // Elimine el bloqueo temporalmente para permitir la posibilidad de que otros subprocesos // necesiten que se ejecute queueLock para que un productor pueda agregar una tarea. queueLock . adquirir (); // Vuelva a adquirir el bloqueo para la próxima llamada a "queue.isEmpty ()". } myTask = cola . dequeue (); // Saque una tarea de la cola. queueLock . liberación (); // Elimina el bloqueo de la cola hasta que lo necesitemos de nuevo para realizar la siguiente tarea. hacerCosas ( myTask ); // Ve y haz algo con la tarea. } }
Este método asegura que no ocurra un estado inconsistente, pero desperdicia recursos de la CPU debido a la espera ocupada innecesaria. Incluso si la cola está vacía y los subprocesos del productor no tienen nada que agregar durante mucho tiempo, los subprocesos del consumidor siempre están ocupados esperando innecesariamente. Del mismo modo, incluso si los consumidores están bloqueados durante mucho tiempo al procesar sus tareas actuales y la cola está llena, los productores siempre están ocupados esperando. Este es un mecanismo inútil. Lo que se necesita es una forma de hacer que los subprocesos del productor se bloqueen hasta que la cola no esté llena, y una forma de hacer que los subprocesos del consumidor se bloqueen hasta que la cola no esté vacía.
(NB: Los mutex en sí mismos también pueden ser bloqueos de giro que implican una espera ocupada para obtener el bloqueo, pero para resolver este problema de recursos de CPU desperdiciados, asumimos que queueLock no es un bloqueo de giro y utiliza correctamente un bloqueo bloquear la cola en sí.)
Variables de condición
La solución es utilizar variables de condición . Conceptualmente, una variable de condición es una cola de subprocesos, asociada con un mutex, en la que un subproceso puede esperar a que se cumpla alguna condición. Por tanto, cada variable de condición c está asociada con una afirmación P c . Mientras un subproceso espera una variable de condición, no se considera que ese subproceso ocupe el monitor, por lo que otros subprocesos pueden ingresar al monitor para cambiar el estado del monitor. En la mayoría de los tipos de monitores, estos otros subprocesos pueden señalar la variable de condición c para indicar que la aserción P c es verdadera en el estado actual.
Por tanto, hay tres operaciones principales sobre variables de condición:
wait c, m
, dondec
es una variable de condición ym
es un mutex (bloqueo) asociado con el monitor. Esta operación es llamada por un subproceso que necesita esperar hasta que la aserción P c sea verdadera antes de continuar. Mientras el hilo espera, no ocupa el monitor. La función, y contrato fundamental, de la operación "esperar", es realizar los siguientes pasos:- Atómicamente :
- suelte el mutex
m
, - mover este hilo de "en ejecución" a
c
la "cola de espera" (también conocida como "cola de espera") de hilos, y - Duerme este hilo. (El contexto se cede de forma sincrónica a otro hilo).
- suelte el mutex
- Una vez que este hilo sea posteriormente notificado / señalado (ver más abajo) y reanudado, vuelva a adquirir automáticamente el mutex
m
.
- Los pasos 1a y 1b pueden ocurrir en cualquier orden, y generalmente 1c ocurre después de ellos. Mientras el hilo está durmiendo y en
c
la cola de espera, el siguiente contador de programa que se ejecutará está en el paso 2, en el medio de la función / subrutina "esperar" . Por lo tanto, el hilo duerme y luego se despierta en medio de la operación de "espera". - La atomicidad de las operaciones dentro del paso 1 es importante para evitar condiciones de carrera que serían causadas por un cambio de hilo preventivo entre ellas. Un modo de falla que podría ocurrir si estos no fueran atómicos es una activación perdida , en la que el hilo podría estar en
c
la cola de suspensión y haber liberado el mutex, pero se produjo un cambio de hilo preventivo antes de que el hilo se durmiera, y otro hilo llamada operación de señal / notificación (ver más abajo) alc
mover el primer hilo fuera dec
la cola de '. Tan pronto como el primer hilo en cuestión se vuelva a cambiar, su contador de programa estará en el paso 1c, y estará inactivo y no podrá ser despertado de nuevo, violando el invariante que debería haber estado enc
la cola de reposo cuando durmió. Otras condiciones de carrera dependen del orden de los pasos 1a y 1b, y dependen de dónde se produzca un cambio de contexto.
- Atómicamente :
signal c
, también conocido comonotify c
, es llamado por un hilo para indicar que la aserción P c es verdadera. Dependiendo del tipo y la implementación del monitor, esto mueve uno o más subprocesos dec
la cola de suspensión a la "cola lista" u otras colas para que se ejecuten. Por lo general, se considera una mejor práctica realizar la operación de "señal" / "notificación" antes de liberar el mutexm
que está asociadoc
, pero siempre que el código esté diseñado correctamente para la concurrencia y dependiendo de la implementación del subproceso, a menudo también es aceptable suelte la cerradura antes de señalar. Dependiendo de la implementación del subproceso, el orden de esto puede tener ramificaciones de prioridad de programación. (Algunos autores [ ¿quién? ] En cambio abogan por una preferencia por liberar el bloqueo antes de la señalización.) Una implementación de subprocesos debería documentar cualquier restricción especial en este orden.broadcast c
, también conocida comonotifyAll c
, es una operación similar que despierta todos los subprocesos en la cola de espera de c. Esto vacía la cola de espera. Generalmente, cuando más de una condición de predicado está asociada con la misma variable de condición, la aplicación requerirá la transmisión en lugar de la señal porque un hilo que espera la condición incorrecta puede despertarse y luego volver inmediatamente a dormir sin despertar un hilo que espera. la condición correcta que acaba de convertirse en realidad. De lo contrario, si la condición de predicado es uno a uno con la variable de condición asociada a ella, entonces la señal puede ser más eficiente que la transmisión .
Como regla de diseño, se pueden asociar múltiples variables de condición con el mismo mutex, pero no al revés. (Esta es una correspondencia de uno a muchos ). Esto se debe a que el predicado P c es el mismo para todos los subprocesos que utilizan el monitor y debe protegerse con exclusión mutua de todos los demás subprocesos que podrían causar que la condición se modifique o que léalo mientras el subproceso en cuestión hace que se cambie, pero puede haber diferentes subprocesos que quieran esperar una condición diferente en la misma variable que requiera que se use el mismo mutex. En el ejemplo de productor-consumidor descrito anteriormente , la cola debe ser protegido por un objeto mutex único, m
. Los hilos del "productor" querrán esperar en un monitor usando un bloqueo m
y una variable de condiciónque bloquea hasta que la cola no está llena. Los subprocesos del "consumidor" querrán esperar en un monitor diferente usando el mismo mutex m
pero una variable de condición diferenteque bloquea hasta que la cola no está vacía. (Normalmente) nunca tendría sentido tener diferentes mutex para la misma variable de condición, pero este ejemplo clásico muestra por qué a menudo tiene sentido tener múltiples variables de condición usando el mismo mutex. Un mutex usado por una o más variables de condición (uno o más monitores) también puede compartirse con código que no usa variables de condición (y que simplemente lo adquiere / libera sin ninguna operación de espera / señal), si esas secciones críticas no ocurren para requerir la espera de una determinada condición en los datos concurrentes.
Monitorear el uso
El uso básico adecuado de un monitor es:
adquirir ( m ); // Adquirir el bloqueo de este monitor. while ( ! p ) { // Mientras que la condición / predicado / aserción que estamos esperando no es verdadera ... esperar ( m , cv ); // Espere el bloqueo y la variable de condición de este monitor. } // ... Aquí va la sección crítica del código ... signal ( cv2 ); - O - notificar a todos ( cv2 ); // cv2 puede ser igual que cv o diferente. liberación ( m ); // Libera el bloqueo de este monitor.
Para ser más precisos, este es el mismo pseudocódigo pero con comentarios más detallados para explicar mejor lo que está sucediendo:
// ... (código anterior) // A punto de entrar al monitor. // Adquirir el mutex consultivo (bloqueo) asociado con los // datos concurrentes que se comparten entre subprocesos, // para garantizar que no se puedan intercalar de forma preventiva dos subprocesos o // ejecutar simultáneamente en diferentes núcleos mientras se ejecutan en secciones // críticas que leer o escribir estos mismos datos concurrentes. Si otro // subproceso tiene este mutex, entonces este subproceso se pondrá en suspensión // (bloqueado) y se colocará en la cola de suspensión de m. (El mutex "m" no debe ser // un bloqueo de giro). Adquirir ( m ); // Ahora, mantenemos el candado y podemos verificar la condición por // primera vez.// La primera vez que ejecutamos la condición de bucle while después de // "adquirir" anterior, nos preguntamos, "¿La condición / predicado / aserción // que estamos esperando resulta que ya es verdadera?"while ( ! p ()) // "p" es cualquier expresión (por ejemplo, variable o // llamada a función) que verifica la condición y // se evalúa como booleana. Esto en sí mismo es una sección // crítica , por lo que * DEBE * mantener el bloqueo cuando // ejecuta esta condición de bucle "while".// Si esta no es la primera vez que se verifica la condición "while", // entonces estamos haciendo la pregunta, "Ahora que otro hilo que usa este // monitor me ha notificado y me ha despertado y he sido contextual- cambió // de nuevo a, ¿la condición / predicado / aserción que estamos esperando se mantuvo // verdadera entre el momento en que me despertaron y el momento en que volví a adquirir // el bloqueo dentro de la llamada "espera" en el último iteración de este bucle, o // ¿algún otro hilo provocó que la condición volviera a ser falsa en el // entretanto, lo que hace que esto sea un despertar espurio?{ // Si esta es la primera iteración del ciclo, entonces la respuesta es // "no" - la condición aún no está lista. De lo contrario, la respuesta es: // este último. Esta fue una activación falsa, se produjo algún otro hilo // primero y provocó que la condición se volviera falsa nuevamente, y debemos // esperar de nuevo.esperar ( m , cv ); // Evite temporalmente que cualquier otro hilo en cualquier núcleo realice // operaciones en mo cv. // liberar (m) // Liberar atómicamente el bloqueo "m" para que otro // // código que use estos datos concurrentes // // pueda operar, mueva este hilo a la // // cola de espera de cv para que sea notificado // // en algún momento en que la condición se // // verdadera, y duerme este hilo. Vuelva a habilitar // // otros subprocesos y núcleos para realizar // // operaciones en my cv. // // El cambio de contexto ocurre en este núcleo. // // En algún momento futuro, la condición que estamos esperando se vuelve // verdadera, y otro hilo que usa este monitor (m, cv) hace // una señal / notifica que activa este hilo, o una / / notifyAll eso nos despierta, lo que significa que nos han sacado // de la cola de espera de cv. // // Durante este tiempo, otros subprocesos pueden hacer que la condición // vuelva a ser falsa, o la condición puede alternar una o más // veces, o puede suceder que permanezca verdadera. // // Este hilo se cambia de nuevo a algún núcleo. // // adquirir (m) // Se vuelve a adquirir el bloqueo "m".// Finalice esta iteración del ciclo y vuelva a comprobar la condición del ciclo "while" para // asegurarse de que el predicado sigue siendo verdadero.}// ¡La condición que estamos esperando es verdadera! // Seguimos manteniendo el bloqueo, ya sea desde antes de entrar al monitor o desde // la última ejecución de "esperar".// Aquí va la sección crítica del código, que tiene la condición previa de que nuestro predicado // debe ser verdadero. // Este código puede hacer que la condición de cv sea falsa y / o que otros predicados de las variables de condición // sean verdaderos.// Llamar a señal / notificar o notificar a todos, según las variables de condición, // los predicados (que comparten mutex m) se han hecho verdaderos o pueden haberse hecho verdaderos, // y el tipo semántico del monitor que se está utilizando.para ( cv_x en cvs_to_notify ) { notificar ( cv_x ); - O - notificar a todos ( cv_x ); } // Uno o más subprocesos se han despertado pero se bloquearán tan pronto como intenten // adquirir m.// Suelte el mutex para que los hilos notificados y otros puedan entrar en sus // secciones críticas . liberación ( m );
Resolviendo el problema limitado del productor / consumidor
Habiendo introducido el uso de variables de condición, usémoslo para revisar y resolver el clásico problema del productor / consumidor acotado. La solución clásica es utilizar dos monitores, que comprenden dos variables de condición que comparten un bloqueo en la cola:
cola RingBuffer volátil global ; // Un búfer circular de tareas que no es seguro para subprocesos. global Lock queueLock ; // Un mutex para el búfer de anillo de tareas. (No es un bloqueo de giro.) Global CV queueEmptyCV ; // Una variable de condición para los subprocesos consumidores que esperan a que la cola // se vuelva no vacía. // Su bloqueo asociado es "queueLock". global CV queueFullCV ; // Una variable de condición para los subprocesos del productor que esperan a que la cola // no esté llena. Su bloqueo asociado también es "queueLock". // Método que representa el comportamiento de cada hilo productor: método público productor () { while ( verdadero ) { tarea myTask = ...; // El productor realiza una nueva tarea para agregar. queueLock . adquirir (); // Adquirir bloqueo para comprobación de predicado inicial. while ( queue . isFull ()) { // Comprueba si la cola no está llena. // Hacer que el sistema de subprocesos libere atómicamente queueLock, // ponga este hilo en cola en queueFullCV y duerma este hilo. esperar ( queueLock , queueFullCV ); // Luego, "wait" vuelve a adquirir automáticamente "queueLock" para volver a verificar // la condición del predicado. } // Sección crítica que requiere que la cola no esté llena. // NB: Tenemos queueLock. cola . poner en cola ( myTask ); // Agrega la tarea a la cola. // Ahora se garantiza que la cola no estará vacía, así que señalice un hilo consumidor // o todos los hilos consumidores que podrían estar bloqueados esperando que la cola no esté vacía: señal ( queueEmptyCV ); - O BIEN - notificar a todos ( queueEmptyCV ); // Fin de las secciones críticas relacionadas con la cola. queueLock . liberación (); // Elimina el bloqueo de la cola hasta que lo necesitemos nuevamente para agregar la siguiente tarea. } }// Método que representa el comportamiento de cada hilo consumidor: método público consumidor () { while ( verdadero ) { queueLock . adquirir (); // Adquirir bloqueo para comprobación de predicado inicial. while ( queue . isEmpty ()) { // Comprueba si la cola no está vacía. // Haga que el sistema de subprocesos libere atómicamente queueLock, // ponga este subproceso en cola en queueEmptyCV y duerma este subproceso. esperar ( queueLock , queueEmptyCV ); // Luego, "wait" vuelve a adquirir automáticamente "queueLock" para volver a verificar // la condición del predicado. } // Sección crítica que requiere que la cola no esté vacía. // NB: Tenemos queueLock. myTask = cola . dequeue (); // Saque una tarea de la cola. // Ahora se garantiza que la cola no estará llena, así que señalice un hilo de productor // o todos los hilos de productor que podrían estar bloqueados esperando que la cola no esté llena: señal ( queueFullCV ); - O BIEN - notificar a todos ( queueFullCV ); // Fin de las secciones críticas relacionadas con la cola. queueLock . liberación (); // Elimina el bloqueo de la cola hasta que lo necesitemos de nuevo para realizar la siguiente tarea. hacerCosas ( myTask ); // Ve y haz algo con la tarea. } }
Esto asegura la concurrencia entre los subprocesos del productor y del consumidor que comparten la cola de tareas y bloquea los subprocesos que no tienen nada que hacer en lugar de estar ocupados esperando, como se muestra en el enfoque mencionado anteriormente utilizando bloqueos de giro.
Una variante de esta solución podría utilizar una única variable de condición tanto para productores como para consumidores, quizás denominada "queueFullOrEmptyCV" o "queueSizeChangedCV". En este caso, más de una condición está asociada con la variable de condición, de modo que la variable de condición representa una condición más débil que las condiciones que están verificando los subprocesos individuales. La variable de condición representa los subprocesos que esperan que la cola no esté llena y los que esperan que no esté vacía. Sin embargo, hacer esto requeriría el uso de notifyAll en todos los hilos que usan la variable de condición y no puede usar una señal regular . Esto se debe a que la señal regular podría despertar un subproceso del tipo incorrecto cuya condición aún no se ha cumplido, y ese subproceso volvería a dormir sin que se señalizara un subproceso del tipo correcto. Por ejemplo, un productor podría llenar la cola y despertar a otro productor en lugar de a un consumidor, y el productor despertado volvería a dormir. En el caso complementario, un consumidor podría vaciar la cola y despertar a otro consumidor en lugar de a un productor, y el consumidor volvería a dormirse. El uso de notifyAll asegura que algún subproceso del tipo correcto procederá según lo esperado por la declaración del problema.
Aquí está la variante que usa solo una variable de condición y notifyAll:
cola RingBuffer volátil global ; // Un búfer circular de tareas que no es seguro para subprocesos. global Lock queueLock ; // Un mutex para el búfer de anillo de tareas. (No es un bloqueo de giro.) Global CV queueFullOrEmptyCV ; // Una única variable de condición para cuando la cola no está lista para ningún hilo // - es decir, para los hilos productores que esperan que la cola no esté llena // y los hilos consumidores que esperan que la cola no esté vacía. // Su bloqueo asociado es "queueLock". // No es seguro usar una "señal" regular porque está asociada con // múltiples condiciones de predicado (aserciones). // Método que representa el comportamiento de cada hilo productor: método público productor () { while ( verdadero ) { tarea myTask = ...; // El productor realiza una nueva tarea para agregar. queueLock . adquirir (); // Adquirir bloqueo para comprobación de predicado inicial. while ( queue . isFull ()) { // Comprueba si la cola no está llena. // Hacer que el sistema de subprocesos libere atómicamente queueLock, // ponga en cola este hilo en el CV y duerma este hilo. esperar ( queueLock , queueFullOrEmptyCV ); // Luego, "wait" vuelve a adquirir automáticamente "queueLock" para volver a verificar // la condición del predicado. } // Sección crítica que requiere que la cola no esté llena. // NB: Tenemos queueLock. cola . poner en cola ( myTask ); // Agrega la tarea a la cola. // Ahora se garantiza que la cola no estará vacía, así que señalice todos los subprocesos bloqueados // para que un subproceso consumidor tome una tarea: notificar a todos ( queueFullOrEmptyCV ); // No use "señal" (ya que podría despertar a otro productor). // Fin de las secciones críticas relacionadas con la cola. queueLock . liberación (); // Elimina el bloqueo de la cola hasta que lo necesitemos nuevamente para agregar la siguiente tarea. } }// Método que representa el comportamiento de cada hilo consumidor: método público consumidor () { while ( verdadero ) { queueLock . adquirir (); // Adquirir bloqueo para comprobación de predicado inicial. while ( queue . isEmpty ()) { // Comprueba si la cola no está vacía. // Hacer que el sistema de subprocesos libere atómicamente queueLock, // ponga en cola este hilo en el CV y duerma este hilo. esperar ( queueLock , queueFullOrEmptyCV ); // Luego, "wait" vuelve a adquirir automáticamente "queueLock" para volver a verificar // la condición del predicado. } // Sección crítica que requiere que la cola no esté llena. // NB: Tenemos queueLock. myTask = cola . dequeue (); // Saque una tarea de la cola. // Ahora se garantiza que la cola no estará llena, así que señalice todos los subprocesos bloqueados // para que un subproceso productor tome una tarea: notifyAll ( queueFullOrEmptyCV ); // No use "señal" (ya que podría despertar a otro consumidor). // Fin de las secciones críticas relacionadas con la cola. queueLock . liberación (); // Elimina el bloqueo de la cola hasta que lo necesitemos de nuevo para realizar la siguiente tarea. hacerCosas ( myTask ); // Ve y haz algo con la tarea. } }
Primitivas de sincronización
La implementación de mutex y variables de condición requiere algún tipo de primitiva de sincronización proporcionada por el soporte de hardware que proporciona atomicidad . Los bloqueos y las variables de condición son abstracciones de nivel superior sobre estas primitivas de sincronización. En un monoprocesador, deshabilitar y habilitar interrupciones es una forma de implementar monitores al evitar cambios de contexto durante las secciones críticas de los bloqueos y las variables de condición, pero esto no es suficiente en un multiprocesador. En un multiprocesador, generalmente se utilizan instrucciones atómicas especiales de lectura, modificación y escritura en la memoria, como probar y configurar , comparar e intercambiar , etc., según lo que proporcione la ISA . Por lo general, estos requieren diferir el bloqueo de giro para el estado de bloqueo interno en sí, pero este bloqueo es muy breve. Dependiendo de la implementación, las instrucciones atómicas de lectura-modificación-escritura pueden bloquear el bus de los accesos de otros núcleos y / o prevenir el reordenamiento de las instrucciones en la CPU. A continuación se muestra un ejemplo de implementación de pseudocódigo de partes de un sistema de subprocesos y mutexes y variables de condición de estilo Mesa, usando prueba y configuración y una política de primero en llegar, primero en ser atendido. Esto pasa por alto la mayor parte de cómo funciona un sistema de subprocesos, pero muestra las partes relevantes para las mutex y las variables de condición:
Ejemplo de implementación de Mesa-monitor con Test-and-Set
// Partes básicas del sistema de subprocesos: // Suponga que "ThreadQueue" admite el acceso aleatorio. público volátil ThreadQueue readyQueue ; // Cola de subprocesos no segura de subprocesos listos. Los elementos son (Hilo *). subproceso global volátil público * currentThread ; // Suponga que esta variable es por núcleo. (Otros son compartidos). // Implementa un bloqueo de giro solo en el estado sincronizado del propio sistema de subprocesos. // Esto se usa con test-and-set como primitiva de sincronización. public volátil global bool threadingSystemBusy = false ;// Rutina de servicio de interrupción de cambio de contexto (ISR): // En el núcleo de la CPU actual, cambie de forma preventiva a otro subproceso. método público contextSwitchISR () { if ( testAndSet ( threadingSystemBusy )) { return ; // No se puede cambiar de contexto en este momento. } // Asegúrese de que esta interrupción no pueda volver a ocurrir, lo que estropearía el cambio de contexto: systemCall_disableInterrupts (); // Obtiene todos los registros del proceso que se está ejecutando actualmente. // Para el Contador de programas (PC), necesitaremos la ubicación de la instrucción // de la etiqueta "reanudar" a continuación. Obtener los valores de registro depende de la plataforma y puede implicar // leer el marco de pila actual, las instrucciones JMP / CALL, etc. (Los detalles están más allá de este alcance). CurrentThread -> registers = getAllRegisters (); // Almacena los registros en el objeto "currentThread" en la memoria. currentThread -> registros . PC = reanudar ; // Configure la siguiente PC con la etiqueta "reanudar" a continuación en este método. readyQueue . poner en cola ( currentThread ); // Vuelve a poner este hilo en la cola lista para su posterior ejecución. Subproceso * otherThread = readyQueue . dequeue (); // Eliminar y hacer que el siguiente hilo se ejecute desde la cola lista. currentThread = otherThread ; // Reemplaza el valor del puntero del hilo actual global para que esté listo para el siguiente hilo. // Restaura los registros de currentThread / otherThread, incluido un salto a la PC almacenada del otro hilo // (en "resume" a continuación). Nuevamente, los detalles de cómo se hace esto están más allá de este alcance. restoreRegisters ( otherThread . registros ); // *** ¡Ahora ejecuta "otherThread" (que ahora es "currentThread")! El hilo original ahora está "durmiendo". *** resume : // Aquí es donde otra llamada contextSwitch () necesita configurar la PC al cambiar de contexto aquí. // Regresa a donde lo dejó otherThread. threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelva a activar la conmutación preventiva en este núcleo. }// Método de suspensión del hilo: // En el núcleo de la CPU actual, un contexto sincrónico cambia a otro hilo sin // poner el hilo actual en la cola lista. // Debe contener "threadingSystemBusy" e interrupciones deshabilitadas para que este método // no sea interrumpido por el temporizador de cambio de hilo que llamaría a contextSwitchISR (). // Después de regresar de este método, debe borrar "threadingSystemBusy". public method threadSleep () { // Obtiene todos los registros del proceso actualmente en ejecución. // Para el Contador de programas (PC), necesitaremos la ubicación de la instrucción // de la etiqueta "reanudar" a continuación. Obtener los valores de registro depende de la plataforma y puede implicar // leer el marco de pila actual, las instrucciones JMP / CALL, etc. (Los detalles están más allá de este alcance). CurrentThread -> registers = getAllRegisters (); // Almacena los registros en el objeto "currentThread" en la memoria. currentThread -> registros . PC = reanudar ; // Configure la siguiente PC con la etiqueta "reanudar" a continuación en este método. // A diferencia de contextSwitchISR (), no colocaremos currentThread de nuevo en readyQueue. // En cambio, ya se ha colocado en una cola de variable de condición o mutex. Subproceso * otherThread = readyQueue . dequeue (); // Eliminar y hacer que el siguiente hilo se ejecute desde la cola lista. currentThread = otherThread ; // Reemplaza el valor del puntero del hilo actual global para que esté listo para el siguiente hilo. // Restaura los registros de currentThread / otherThread, incluido un salto a la PC almacenada del otro hilo // (en "resume" a continuación). Nuevamente, los detalles de cómo se hace esto están más allá de este alcance. restoreRegisters ( otherThread . registros ); // *** ¡Ahora ejecuta "otherThread" (que ahora es "currentThread")! El hilo original ahora está "durmiendo". *** resume : // Aquí es donde otra llamada contextSwitch () necesita configurar la PC al cambiar de contexto aquí. // Regresa a donde lo dejó otherThread. }public method wait ( Mutex m , ConditionVariable c ) { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo acceden a los // "retenidos" y "threadQueue" o "readyQueue" de este objeto. while ( testAndSet ( threadingSystemBusy )) {} // NB: "threadingSystemBusy" ahora es verdadero. // Llamada al sistema para deshabilitar las interrupciones en este núcleo para que threadSleep () no sea interrumpido por // el temporizador de cambio de hilo en este núcleo que llamaría a contextSwitchISR (). // Hecho fuera de threadSleep () para una mayor eficiencia de modo que este hilo se suspenda // justo después de pasar a la cola de variable de condición. systemCall_disableInterrupts (); afirmar m . retenido ; // (Específicamente, este hilo debe ser el que lo sostenga). m . liberación (); c . esperandoThreads . poner en cola ( currentThread ); threadSleep (); // El hilo duerme ... El hilo se despierta a partir de una señal / transmisión. threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelva a activar la conmutación preventiva en este núcleo. // Estilo Mesa: // Los cambios de contexto ahora pueden ocurrir aquí, haciendo que el predicado del llamador del cliente sea falso. m . adquirir (); } señal de método público ( ConditionVariable c ) { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo acceden a los // "retenidos" y "threadQueue" o "readyQueue" de este objeto. while ( testAndSet ( threadingSystemBusy )) {} // NB: "threadingSystemBusy" ahora es verdadero. // Llamada al sistema para deshabilitar las interrupciones en este núcleo para que threadSleep () no sea interrumpido por // el temporizador de cambio de hilo en este núcleo que llamaría a contextSwitchISR (). // Hecho fuera de threadSleep () para una mayor eficiencia de modo que este hilo se suspenda // justo después de pasar a la cola de variable de condición. systemCall_disableInterrupts (); if ( ! c . waitThreads . isEmpty ()) { wokenThread = c . esperandoThreads . dequeue (); readyQueue . poner en cola ( wokenThread ); } threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelva a activar la conmutación preventiva en este núcleo. // Estilo Mesa: // No se le da prioridad al hilo despertado. } difusión del método público ( ConditionVariable c ) { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo están accediendo a // "retenido" y "threadQueue" o "readyQueue" de este objeto. while ( testAndSet ( threadingSystemBusy )) {} // NB: "threadingSystemBusy" ahora es verdadero. // Llamada al sistema para deshabilitar las interrupciones en este núcleo para que threadSleep () no sea interrumpido por // el temporizador de cambio de hilo en este núcleo que llamaría a contextSwitchISR (). // Hecho fuera de threadSleep () para una mayor eficiencia de modo que este hilo se suspenda // justo después de pasar a la cola de variable de condición. systemCall_disableInterrupts (); while ( ! c . waitThreads . isEmpty ()) { wokenThread = c . esperandoThreads . dequeue (); readyQueue . poner en cola ( wokenThread ); } threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelva a activar la conmutación preventiva en este núcleo. // Estilo Mesa: // Los hilos activados no tienen prioridad. }class Mutex { bool volátil protegido retenido = falso ; privadas volátiles ThreadQueue blockingThreads ; // Cola de subprocesos bloqueados que no es segura. Los elementos son (Hilo *). método público adquirido () { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo acceden a los // "retenidos" y "threadQueue" o "readyQueue" de este objeto. while ( testAndSet ( threadingSystemBusy )) {} // NB: "threadingSystemBusy" ahora es verdadero. // Llamada al sistema para deshabilitar las interrupciones en este núcleo para que threadSleep () no sea interrumpido por // el temporizador de cambio de hilo en este núcleo que llamaría a contextSwitchISR (). // Hecho fuera de threadSleep () para una mayor eficiencia de modo que este hilo se suspenda // justo después de pasar a la cola de bloqueo. systemCall_disableInterrupts (); afirmar ! blockThreads . contiene ( currentThread ); if ( retenido ) { // Coloca "currentThread" en la cola de este bloqueo para que sea // considerado "durmiendo" en este bloqueo. // Note que "currentThread" aún necesita ser manejado por threadSleep (). readyQueue . eliminar ( currentThread ); blockThreads . poner en cola ( currentThread ); threadSleep (); // Ahora estamos despiertos, lo cual debe ser porque "sostenido" se volvió falso. afirmar ! retenido ; afirmar ! blockThreads . contiene ( currentThread ); } sostenido = verdadero ; threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelva a activar la conmutación preventiva en este núcleo. } public method release () { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo acceden a los // "retenidos" y "threadQueue" o "readyQueue" de este objeto. while ( testAndSet ( threadingSystemBusy )) {} // NB: "threadingSystemBusy" ahora es verdadero. // Llamada al sistema para deshabilitar las interrupciones en este núcleo para mayor eficiencia. systemCall_disableInterrupts (); afirmar celebrado ; // (La liberación solo debe realizarse mientras se mantiene el bloqueo). sostenido = falso ; si ( ! blockingThreads . isEmpty ()) { Thread * unblockedThread = blockingThreads . dequeue (); readyQueue . enqueue ( unblockedThread ); } threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelva a activar la conmutación preventiva en este núcleo. } }struct ConditionVariable { ThreadQueue esperandoThreads volátiles ; }
Semáforo
Como ejemplo, considere una clase segura para subprocesos que implementa un semáforo . Existen métodos para incrementar (V) y disminuir (P) un entero privado s
. Sin embargo, el número entero nunca debe decrementarse por debajo de 0; por lo tanto, un hilo que intenta disminuir debe esperar hasta que el número entero sea positivo. Usamos una variable de condición sIsPositive
con una aserción asociada de.
clase de monitor Semaphore{ privado int s: = 0 invariante s> = 0 privado Condición sIsPositive / * asociado con s> 0 * / método público P () { while s = 0: esperar sIsPositive aseverar s> 0 s: = s - 1 } método público V () { s: = s + 1 afirmar s> 0 señal sIsPositive }}
Implementado mostrando toda la sincronización (eliminando la suposición de una clase segura para subprocesos y mostrando el mutex):
clase semáforo{ private volatile int s: = 0 invariante s> = 0 private ConditionVariable sIsPositive / * asociado con s> 0 * / private Mutex myLock / * Bloqueo en "s" * / método público P () { myLock.acquire () while s = 0: esperar (myLock, sIsPositive) afirmar s> 0 s: = s - 1 myLock.release () } método público V () { myLock.acquire () s: = s + 1 afirmar s> 0 señal sIsPositive myLock.release () }}
Monitor implementado usando semáforos
Por el contrario, los bloqueos y las variables de condición también se pueden derivar de los semáforos, por lo que los monitores y los semáforos se pueden reducir entre sí:
La implementación dada aquí es incorrecta. Si un hilo llama a wait () después de que se haya llamado a broadcast (), un hilo original puede quedar bloqueado indefinidamente, ya que broadcast () incrementa el semáforo solo las veces necesarias para los hilos que ya están esperando.
espera del método público ( Mutex m , ConditionVariable c ) { aseverar m . retenido ; c . internalMutex . adquirir (); c . numWaiters ++ ; m . liberación (); // Puede ir antes / después de las líneas vecinas. c . internalMutex . liberación (); // Otro hilo podría indicar aquí, pero eso está bien debido a cómo // cuentan los semáforos. Si el número de c.sem se convierte en 1, no tendremos // tiempo de espera. c . sem . Proberen (); // Bloquear en el CV. // Despertó m . adquirir (); // Vuelva a adquirir el mutex. } señal de método público ( ConditionVariable c ) { c . internalMutex . adquirir (); if ( c . numWaiters > 0 ) { c . numWaiters - ; c . sem . Verhogen (); // (no tiene que ser protegido por c.internalMutex.) } C . internalMutex . liberación (); } difusión de método público ( ConditionVariable c ) { c . internalMutex . adquirir (); while ( c . numWaiters > 0 ) { c . numWaiters - ; c . sem . Verhogen (); // (no tiene que ser protegido por c.internalMutex.) } C . internalMutex . liberación (); } class Mutex { booleano protegido retenido = falso ; // Solo para aserciones, para asegurarse de que el número de sem nunca vaya> 1. protected Semaphore sem = Semaphore ( 1 ); // El número siempre será como máximo 1. // No se mantiene <--> 1; retenido <--> 0. método público adquirir () { sem . Proberen (); afirmar ! retenido ; sostenido = verdadero ; } liberación de método público () { aseveración sostenida ; // Asegúrate de que nunca Verhogen sem por encima de 1. Eso sería malo. sostenido = falso ; sem . Verhogen (); } } class ConditionVariable { protegido int numWaiters = 0 ; // Realiza un seguimiento aproximado del número de camareros bloqueados en sem. // (el estado interno del semáforo es necesariamente privado.) Protegido semáforo sem = Semáforo ( 0 ); // Proporciona la cola de espera. protegido Mutex internalMutex ; // (Realmente otro semáforo. Protege "numWaiters".) }
Cuando ocurre una señal en una variable de condición que al menos otro subproceso está esperando, hay al menos dos subprocesos que podrían ocupar el monitor: el subproceso que señala y cualquiera de los subprocesos que está esperando. Para que como máximo un hilo ocupe el monitor en cada momento, se debe hacer una elección. Existen dos escuelas de pensamiento sobre la mejor manera de resolver esta elección. Esto conduce a dos tipos de variables de condición que se examinarán a continuación:
- Las variables de condición de bloqueo dan prioridad a un hilo señalado.
- Las variables de condición de no bloqueo dan prioridad al hilo de señalización.
Variables de condición de bloqueo
Las propuestas originales de CAR Hoare y Per Brinch Hansen eran para bloquear las variables de condición . Con una variable de condición de bloqueo, el hilo de señalización debe esperar fuera del monitor (al menos) hasta que el hilo señalado abandone la ocupación del monitor ya sea regresando o esperando de nuevo en una variable de condición. Los monitores que utilizan variables de condición de bloqueo a menudo se denominan monitores de estilo Hoare o monitores de señal y espera urgente .
Suponemos que hay dos colas de subprocesos asociados con cada objeto de monitor
e
es la cola de entradas
es una cola de subprocesos que se han señalado.
Además, asumimos que para cada variable de condición c , hay una cola
c.q
, que es una cola para subprocesos que esperan en la variable de condición c
Por lo general, se garantiza que todas las colas son justas y, en algunas implementaciones, se puede garantizar que sean las primeras en entrar, las primeras en salir .
La implementación de cada operación es la siguiente. (Suponemos que cada operación se ejecuta en exclusión mutua de las demás; por lo tanto, los subprocesos reiniciados no comienzan a ejecutarse hasta que se completa la operación).
entrar en el monitor: ingrese el método si el monitor está bloqueado agregue este hilo a e bloquear este hilo demás bloquear el monitordejar el monitor: calendario volver del métodoespera c : agregue este hilo a c .q calendario bloquear este hiloseñal c : si hay un hilo esperando en c .q seleccione y elimine uno de esos hilos t de c .q (t se llama "el hilo señalado") agregar este hilo a s reiniciar t (por lo que ocupará el monitor a continuación) bloquear este hilocronograma: si hay un hilo en s seleccione y elimine un hilo de sy reinícielo (este hilo ocupará el monitor a continuación) de lo contrario, si hay un hilo en e seleccione y elimine un hilo de e y reinícielo (este hilo ocupará el monitor a continuación) demás desbloquear el monitor (el monitor quedará desocupado)
La schedule
rutina selecciona el siguiente subproceso para ocupar el monitor o, en ausencia de subprocesos candidatos, desbloquea el monitor.
La disciplina de señalización resultante se conoce como "señal y espera urgente", ya que el comunicante debe esperar, pero se le da prioridad sobre los subprocesos en la cola de entrada. Una alternativa es "señal y espera", en la que no hay s
cola y el comunicador espera en la e
cola.
Algunas implementaciones proporcionan una operación de señal y retorno que combina la señalización con el retorno de un procedimiento.
señal cy retorno : si hay un hilo esperando en c .q seleccione y elimine uno de esos hilos t de c .q (t se llama "el hilo señalado") reiniciar t (por lo que ocupará el monitor a continuación) demás calendario volver del método
En cualquier caso ("señal y espera urgente" o "señal y espera"), cuando se señaliza una variable de condición y hay al menos un subproceso esperando en la variable de condición, el subproceso de señalización entrega la ocupación al subproceso señalado sin problemas, por lo que que ningún otro hilo puede ganar ocupación en el medio. Si P c es verdadera al comienzo de cada operación de la señal c , será verdadera al final de cada operación de espera c . Esto se resume en los siguientes contratos . En estos contratos, I es el invariante del monitor .
entrar en el monitor: postcondición Idejar el monitor: condición previa Iesperar c : condición previa que modifica el estado del monitor postcondition P c y Iseñal c : condición previa P c e I modifica el estado del monitor condición posterior Iseñal c y el retorno : condición previa P c y I
En estos contratos, se supone que I y P c no dependen del contenido o la longitud de las colas.
(Cuando se puede consultar la variable de condición en cuanto al número de subprocesos en espera en su cola, se pueden otorgar contratos más sofisticados. Por ejemplo, un par de contratos útil, que permite pasar la ocupación sin establecer el invariante, es:
esperar c : condición previa que modifica el estado del monitor postcondition P cla señal c condición previa ( no vacío ( c ) y P c ) o (vacío ( c ) e I ) modifica el estado de la condición posterior del monitor I
(Ver Howard [4] y Buhr et al. [5] para más información).
Es importante señalar aquí que la afirmación P c depende totalmente del programador; él o ella simplemente necesita ser coherente sobre lo que es.
Concluimos esta sección con un ejemplo de una clase segura para subprocesos que utiliza un monitor de bloqueo que implementa una pila limitada y segura para subprocesos .
clase de monitor SharedStack { capacidad const privada : = 10 int privado [capacidad] Un int privado tamaño: = 0 invariante 0 <= tamaño y tamaño <= capacidad privado BlockingCondition theStackIsNotEmpty / * asociado con 0ño>y tamaño <= capacidad * / privado Condición de bloqueo theStackIsNotFull / * asociada con 0 <= tamaño y tamaño push de método público ( valor int ) { si size = capacidad luego esperar theStackIsNotFull aserción 0 <= tamaño y tamaño A [tamaño]: = valor; tamaño: = tamaño + 1 afirmar 0 ño>y tamaño <= capacidad señal theStackIsNotEmpty y regresar } método público int pop () { si size = 0 entonces espere theStackIsNotEmpty aserción 0 ño>y tamaño de <= capacidad tamaño: = tamaño - 1; afirmar 0 <= tamaño y tamaño señal theStackIsNotFull y devolver A [tamaño] }}
Tenga en cuenta que, en este ejemplo, la pila segura para subprocesos proporciona internamente un mutex, que, como en el ejemplo anterior de productor / consumidor, es compartido por ambas variables de condición, que verifican diferentes condiciones en los mismos datos concurrentes. La única diferencia es que el ejemplo de productor / consumidor asumió una cola regular no segura para subprocesos y estaba usando un mutex independiente y variables de condición, sin estos detalles del monitor abstraídos como es el caso aquí. En este ejemplo, cuando se llama a la operación "esperar", de alguna manera se debe suministrar con el mutex de la pila segura para subprocesos, como si la operación "esperar" es una parte integrada de la "clase de monitor". Aparte de este tipo de funcionalidad abstracta, cuando se utiliza un monitor "sin formato", siempre tendrá que incluir un mutex y una variable de condición, con un mutex único para cada variable de condición.
Variables de condición de no bloqueo
Con las variables de condición sin bloqueo (también llamadas variables de condición de "estilo Mesa" o variables de condición de "señal y continuar" ), la señalización no hace que el hilo de señalización pierda la ocupación del monitor. En su lugar, los subprocesos señalados se mueven a la e
cola. No es necesario hacer s
cola.
Con las variables de condición sin bloqueo, la operación de la señal a menudo se llama notificar , una terminología que seguiremos aquí. También es común proporcionar una operación de notificación de todos que mueve todos los subprocesos que esperan en una variable de condición a la e
cola.
Aquí se da el significado de varias operaciones. (Suponemos que cada operación se ejecuta en exclusión mutua de las demás; por lo tanto, los subprocesos reiniciados no comienzan a ejecutarse hasta que se completa la operación).
entrar en el monitor: ingrese el método si el monitor está bloqueado agregue este hilo a e bloquear este hilo demás bloquear el monitordejar el monitor: calendario volver del métodoespera c : agregue este hilo a c .q calendario bloquear este hilonotificar c : si hay un hilo esperando en c .q seleccionar y eliminar un hilo t de c .q (t se llama "el hilo notificado") mover de t a enotificar a todos c : mover todos los hilos en espera de c .q a ecronograma : si hay un hilo en e seleccione y elimine un hilo de e y reinícielo demás desbloquear el monitor
Como una variación de este esquema, el hilo notificado se puede mover a una cola llamada w
, que tiene prioridad sobre e
. Véase Howard [4] y Buhr et al. [5] para mayor discusión.
Es posible asociar una aserción P c con cada variable de condición c de modo que P c sea cierto al regresar de . Sin embargo, uno debe asegurarse de que P c se conserve desde el momento en que el hilo de notificación abandona la ocupación hasta que se selecciona el hilo de notificación para volver a ingresar al monitor. Entre estos momentos podría haber actividad por parte de otros ocupantes. Por lo tanto, es común que P c sea simplemente cierto .wait c
Por esta razón, generalmente es necesario encerrar cada operación de espera en un bucle como este
mientras que no ( P ) hacer espera c
donde P es alguna condición más fuerte que P c . Las operaciones y se tratan como "pistas" de que P puede ser cierto para algún subproceso en espera. Cada iteración de un ciclo de este tipo más allá del primero representa una notificación perdida; por lo tanto, con monitores que no bloquean, se debe tener cuidado de asegurarse de que no se pierdan demasiadas notificaciones.notify c
notify all c
Como ejemplo de "insinuación", considere una cuenta bancaria en la que un hilo de retiro esperará hasta que la cuenta tenga fondos suficientes antes de continuar.
clase de monitor Cuenta { saldo int privado : = 0 saldo invariante > = 0 saldo privado NonblockingConditionMayBeBigEnough método público retirar ( cantidad int ) cantidad de condición previa > = 0 { mientras que el equilibriodo espera balanceMayBeBigEnough afirman equilibrio> = cantidad saldo: = saldo - monto } depósito de método público ( cantidad int ) cantidad de condición previa > = 0 { saldo: = saldo + monto notificar a todos balanceMayBeBigEnough }}
En este ejemplo, la condición que se espera es una función de la cantidad a retirar, por lo que es imposible que un hilo de depósito sepa que hizo que dicha condición sea verdadera. En este caso, tiene sentido permitir que cada hilo en espera en el monitor (uno a la vez) verifique si su afirmación es verdadera.
Monitores de variables de condición implícitas
En el lenguaje Java , cada objeto se puede utilizar como monitor. Los métodos que requieren exclusión mutua deben marcarse explícitamente con la palabra clave sincronizada . Los bloques de código también pueden marcarse sincronizados .
En lugar de tener variables de condición explícitas, cada monitor (es decir, objeto) está equipado con una única cola de espera además de su cola de entrada. Todo se hace de espera en esta cola de espera única y todos notificar y notifyAll operaciones se aplican a esta cola. Este enfoque se ha adoptado en otros lenguajes, por ejemplo, C # .
Señalización implícita
Otro enfoque para la señalización es omitir la operación de señal . Siempre que un hilo sale del monitor (regresando o esperando), las afirmaciones de todos los hilos en espera se evalúan hasta que se determina que uno es verdadero. En tal sistema, las variables de condición no son necesarias, pero las aserciones deben codificarse explícitamente. El contrato de espera es
espere P : precondición que modifica el estado del monitor de condición posterior P y I
Historia
Brinch Hansen y Hoare desarrollaron el concepto de monitor a principios de la década de 1970, basándose en ideas anteriores propias y de Edsger Dijkstra . [6] Brinch Hansen publicó la primera notación de monitor, adoptando el concepto de clase de Simula 67 , [1] e inventó un mecanismo de cola. [7] Hoare perfeccionó las reglas de reanudación del proceso. [2] Brinch Hansen creó la primera implementación de monitores, en Concurrent Pascal . [6] Hoare demostró su equivalencia con los semáforos .
Los monitores (y Concurrent Pascal) pronto se utilizaron para estructurar la sincronización de procesos en el sistema operativo Solo . [8] [9]
Los lenguajes de programación que tienen monitores compatibles incluyen:
- Ada desde Ada 95 (como objetos protegidos)
- C # (y otros lenguajes que usan .NET Framework )
- Euclides concurrente
- Pascal concurrente
- D
- Delphi (Delphi 2009 y superior, a través de TObject.Monitor)
- Java (a través de los métodos de espera y notificación)
- Ir
- Colina baja
- Modula-3
- Python (a través del objeto threading.Condition )
- Rubí
- Chillido Smalltalk
- Turing , Turing + y Turing orientado a objetos
- µC ++
- Prólogo visual
Se han escrito varias bibliotecas que permiten construir monitores en lenguajes que no los admiten de forma nativa. Cuando se utilizan llamadas a la biblioteca, depende del programador marcar explícitamente el inicio y el final del código ejecutado con exclusión mutua. Pthreads es una de esas bibliotecas.
Ver también
- Exclusión mutua
- Comunicación de procesos secuenciales : un desarrollo posterior de monitores por CAR Hoare
- Semáforo (programación)
Notas
- ↑ a b Brinch Hansen, Per (1973). "7.2 Concepto de clase" (PDF) . Principios del sistema operativo . Prentice Hall. ISBN 978-0-13-637843-3.
- ^ a b Hoare, CAR (octubre de 1974). "Monitores: un concepto de estructuración de un sistema operativo". Comm. ACM . 17 (10): 549–557. CiteSeerX 10.1.1.24.6394 . doi : 10.1145 / 355620.361161 . S2CID 1005769 .
- ^ Hansen, PB (junio de 1975). "El lenguaje de programación Concurrent Pascal" (PDF) . IEEE Trans. Softw. Ing. SE-1 (2): 199–207. doi : 10.1109 / TSE.1975.6312840 . S2CID 2000388 .
- ^ a b Howard, John H. (1976). "Señalización en monitores" . ICSE '76 Actas de la 2ª conferencia internacional sobre ingeniería de software . Congreso Internacional de Ingeniería de Software. Los Alamitos, CA, EE.UU .: IEEE Computer Society Press. págs. 47–52.
- ^ a b Buhr, Peter A .; Fortier, Michel; Coffin, Michael H. (marzo de 1995). "Clasificación del monitor". Encuestas de computación ACM . 27 (1): 63–107. doi : 10.1145 / 214037.214100 . S2CID 207193134 .
- ^ a b Hansen, Per Brinch (1993). "Monitores y Pascal concurrentes: una historia personal". HOPL-II: La segunda conferencia ACM SIGPLAN sobre Historia de los lenguajes de programación . Historia de los lenguajes de programación. Nueva York, NY, EE.UU .: ACM . págs. 1-35. doi : 10.1145 / 155360.155361 . ISBN 0-89791-570-4.
- ^ Brinch Hansen, Per (julio de 1972). "Multiprogramación estructurada (Trabajo invitado)". Comunicaciones de la ACM . 15 (7): 574–578. doi : 10.1145 / 361454.361473 . S2CID 14125530 .
- ^ Brinch Hansen, Per (abril de 1976). "El sistema operativo Solo: un programa Pascal concurrente" (PDF) . Software: práctica y experiencia .
- ^ Brinch Hansen, Per (1977). La arquitectura de programas concurrentes . Prentice Hall. ISBN 978-0-13-044628-2.
Otras lecturas
- Monitores: un concepto de estructuración del sistema operativo, CAR Hoare - Comunicaciones del ACM , v.17 n.10, p. 549-557, octubre de 1974 [1]
- Clasificación del monitor PA Buhr, M. Fortier, MH Coffin - Encuestas de computación ACM , 1995 [2]
enlaces externos
- Monitores Java (explicación lúcida)
- " Monitores: un concepto de estructuración del sistema operativo " por CAR Hoare
- " Señalización en monitores " por John H. Howard (informático)
- " Proving Monitors " por John H. Howard (informático)
- " Experiencia con procesos y monitores en Mesa " por Butler W. Lampson y David D. Redell
- pthread_cond_wait : descripción de las especificaciones básicas del grupo abierto, edición 6, IEEE Std 1003.1
- " Bloque en una variable de condición " por Dave Marshall (informático)
- " Estrategias para implementar variables de condición POSIX en Win32 " por Douglas C. Schmidt e Irfan Pyarali
- Rutinas de variables de condición de la biblioteca de tiempo de ejecución portátil de Apache
- wx Descripción de la condición
- Referencia de variables de condición de impulso
- Referencia de clase de condición ZThread
- Tramas :: Referencia de clase de condición
- Referencia de plantilla de clase ACE_Condition
- Referencia de clase QWaitCondition
- Referencia común de clases condicionales de C ++
- at :: ConditionalMutex Class Reference
- threads :: shared - Extensión de Perl para compartir estructuras de datos entre subprocesos
- http://msdn.microsoft.com/en-us/library/ms682052(VS.85).aspx
- Monitores en Visual Prolog .