En programación concurrente , un monitor es una construcción de sincronización que evita que los subprocesos accedan simultáneamente al estado de un objeto compartido y les permite esperar a que cambie el estado. Proporcionan un mecanismo para que los subprocesos cedan temporalmente el acceso exclusivo para esperar a que se cumpla alguna condición, antes de recuperar el acceso exclusivo y reanudar su tarea. Un monitor consta de un mutex (bloqueo) y al menos una variable de condición . Una variable de condición se "señala" explícitamente cuando se modifica el estado del objeto, pasando temporalmente el mutex a otro hilo "esperando" en la variable condicional.
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 parte de más de un subproceso . La característica que define a un monitor es que sus métodos se ejecutan con exclusión mutua : en cada momento, como máximo un subproceso puede estar ejecutando cualquiera de sus métodos . Al utilizar una o más variables de condición, también puede proporcionar a los subprocesos la capacidad de esperar una determinada condición (utilizando así la definición anterior de "monitor"). Durante 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]
Mientras un subproceso ejecuta un método de un objeto seguro para subprocesos, se dice que ocupa el objeto manteniendo su exclusión mutua (bloqueo) . Los objetos seguros para subprocesos se implementan para hacer cumplir que, en cada momento, como máximo un subproceso pueda ocupar el objeto . El bloqueo, que inicialmente está desbloqueado, se bloquea al inicio 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 comenzar la ejecución de su método. Tenga en cuenta que sin esta exclusión mutua, dos hilos podrían provocar que se pierda o gane dinero sin ningún motivo. Por ejemplo, dos subprocesos que retiran 1000 de la cuenta podrían devolver verdadero, al tiempo que causan que el saldo caiga 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.
Para muchas aplicaciones, la exclusión mutua no es suficiente. Es posible que los subprocesos que intentan una operación deban esperar hasta que alguna condición P sea verdadera. Un circuito de espera ocupado
mientras no ( P ) salta
no funcionará, ya que la exclusión mutua evitará que cualquier otro hilo ingrese al monitor para que la condición sea verdadera. Existen otras "soluciones" , como tener un bucle que desbloquea el monitor, espera un cierto tiempo, bloquea el monitor y comprueba la condición P. En teoría, funciona y no se bloqueará, pero surgen problemas. Es difícil decidir una cantidad adecuada de tiempo de espera: si es demasiado pequeño, el hilo acaparará la CPU; si es demasiado grande, 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).
Un problema de concurrencia clásico es el del productor/consumidor acotado , 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 sacan tareas de la cola. Se supone que la cola no es segura para subprocesos y puede estar vacía, llena o entre vacía y llena. Siempre que la cola está llena de tareas, necesitamos que los subprocesos productores se bloqueen hasta que haya espacio para los subprocesos consumidores que retiran las tareas de la cola. 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 las agregan.
Como la cola es un objeto concurrente compartido entre subprocesos, los accesos a ella deben ser atómicos , porque la cola puede ponerse 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 una sección crítica 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 intercalarse mediante cambios de contexto arbitrarios entre subprocesos en el mismo procesador o mediante subprocesos que se ejecutan simultáneamente en múltiples procesadores, entonces existe el riesgo de exponer estados inconsistentes y causar condiciones de carrera. .
Un enfoque ingenuo es diseñar el código con espera ocupada y sin sincronización, lo que hace que el código esté sujeto a condiciones de carrera:
cola global RingBuffer ; // Un búfer circular de tareas inseguro para subprocesos. // Método que representa el comportamiento de cada subproceso productor: método público productor () { while ( verdadero ) { tarea miTarea = ...; // El productor crea una tarea nueva para agregar. while ( queue . isFull ()) {} // Ocupado-espera hasta que la cola no esté llena. cola . poner en cola ( miTarea ); // Agrega la tarea a la cola. } } // Método que representa el comportamiento de cada hilo de consumidor: método público consumidor () { while ( true ) { while ( queue . isEmpty ()) {} // Ocupado-espera hasta que la cola no esté vacía. miTarea = cola . quitar la cola (); // Sacar una tarea de la cola. hacerCosas ( miTarea ); // Ve y haz algo con la tarea. } } Este código tiene un problema grave porque los accesos a la cola pueden interrumpirse e intercalarse con los accesos de otros subprocesos a la cola. Es probable que los métodos queue.enqueue y queue.dequeue tengan instrucciones para actualizar las variables miembro 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 que los subprocesos de productor/consumidor se intercalen durante las llamadas a poner en cola/quitar de cola, entonces se puede exponer un estado inconsistente de la cola que lleve a condiciones de carrera. Además, si un consumidor deja la cola vacía mientras otro consumidor sale de la espera ocupada y llama a "quitar de la cola", entonces el segundo consumidor intentará quitar la cola de una cola vacía, lo que provocará un error. Del mismo modo, si un productor llena la cola mientras otro productor sale de la espera ocupada y llama a "poner en cola", entonces el segundo productor intentará agregar a una cola llena, lo que provocará un error.
Un enfoque ingenuo para lograr la sincronización, como se mencionó anteriormente, es usar " espera de giro ", en la que se usa un mutex para proteger las secciones críticas del código y se sigue usando la espera de ocupado, adquiriendo y liberando el bloqueo en entre cada comprobación de espera ocupada.
cola global RingBuffer ; // Un búfer circular de tareas inseguro para subprocesos. Bloqueo global de cola ; // Un mutex para el buffer circular de tareas. // Método que representa el comportamiento de cada hilo productor: método público productor () { while ( verdadero ) { tarea miTarea = ...; // El productor crea una tarea nueva para agregar. bloqueo de cola . adquirir (); // Adquirir bloqueo para la comprobación inicial de espera ocupada. while ( queue . isFull ()) { // Ocupado: espera hasta que la cola no esté llena. bloqueo de cola . liberar (); // Quitar el bloqueo temporalmente para dar oportunidad a otros subprocesos // que necesitan queueLock se ejecute para que un consumidor pueda realizar una tarea. bloqueo de cola . adquirir (); // Vuelve a adquirir el bloqueo para la siguiente llamada a "queue.isFull()". } cola . poner en cola ( miTarea ); // Agrega la tarea a la cola. bloqueo de cola . liberar (); // Suelta el bloqueo de la cola hasta que lo necesitemos nuevamente para agregar la siguiente tarea. } } // Método que representa el comportamiento de cada hilo de 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. bloqueo de cola . liberar (); // Elimina el bloqueo temporalmente para dar oportunidad a otros subprocesos // que necesitan queueLock se ejecute para que un productor pueda agregar una tarea. bloqueo de cola . adquirir (); // Vuelve a adquirir el bloqueo para la siguiente llamada a "queue.isEmpty()". } miTarea = cola . quitar la cola (); // Sacar una tarea de la cola. bloqueo de cola . liberar (); // Suelta el bloqueo de la cola hasta que lo necesitemos nuevamente para realizar la siguiente tarea. hacerCosas ( miTarea ); // Ve y haz algo con la tarea. } } Este método garantiza que no se produzca 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 productores no tienen nada que agregar durante mucho tiempo, los subprocesos consumidores siempre están ocupados esperando innecesariamente. Del mismo modo, incluso si los consumidores están bloqueados durante mucho tiempo para procesar sus tareas actuales y la cola está llena, los productores siempre están ocupados esperando. Este es un mecanismo derrochador. Lo que se necesita es una manera de hacer que los subprocesos productores se bloqueen hasta que la cola no esté llena, y una manera de hacer que los subprocesos consumidores se bloqueen hasta que la cola no esté vacía.
(NB: los mutex en sí 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í.)
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 alguna condición se cumpla. Por lo 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 su estado. 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 afirmación P c es verdadera en el estado actual.
Por tanto, existen tres operaciones principales sobre variables de condición:
wait c, m, donde ces una variable de condición y mes un mutex (bloqueo) asociado con el monitor. Esta operación es llamada por un hilo que necesita esperar hasta que la afirmació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:m,cla "cola de espera" (también conocida como "cola de suspensión") de subprocesos, ym.cla cola de espera, el siguiente contador de programa que se ejecutará se encuentra en el paso 2, en medio de la función/ subrutina "espera" . Por lo tanto, el hilo duerme y luego se despierta en medio de la operación de "espera".cla cola de suspensión y haber liberado el mutex, pero se produjo un cambio de subproceso preventivo antes de que el subproceso entrara en suspensión, y otro subproceso Se llama a una operación de señal (ver más abajo) al cmover el primer hilo nuevamente fuera de cla cola. Tan pronto como se vuelva a activar el primer hilo en cuestión, su contador de programa estará en el paso 1c, se suspenderá y no podrá volver a despertarse, violando la invariante de que debería haber estado en cla cola de suspensión cuando durmió. Otras condiciones de carrera dependen del orden de los pasos 1a y 1b, y de dónde se produce un cambio de contexto.signal c, también conocido como notify c, es llamado por un hilo para indicar que la afirmación P c es verdadera. Dependiendo del tipo y la implementación del monitor, esto mueve uno o más subprocesos de cla cola de suspensión a la "cola lista" u otra cola para que se ejecute. Por lo general, se considera una mejor práctica realizar la operación de "señal" antes de liberar el mutex masociado con c, pero siempre que el código esté diseñado adecuadamente para la concurrencia y dependiendo de la implementación del subproceso, a menudo también es aceptable liberar el bloqueo antes. señalización. Dependiendo de la implementación del subproceso, el orden de este puede tener ramificaciones de prioridad de programación. (Algunos autores [ ¿quién? ] en cambio abogan por una preferencia por liberar el bloqueo antes de señalar). Una implementación de subprocesos debe documentar cualquier restricción especial en este orden.broadcast c, también conocido como notifyAll c, es una operación similar que activa 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 predicada está asociada con la misma variable de condición, la aplicación requerirá transmisión en lugar de señal porque un subproceso que espera una condición incorrecta podría despertarse y luego volver inmediatamente a dormir sin despertar un subproceso que espera una condición incorrecta. la condición correcta que acaba de hacerse 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. (Ésta 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 se cambie la condición o que podrían léalo mientras el hilo en cuestión hace que se cambie, pero puede haber diferentes hilos que quieran esperar una condición diferente en la misma variable que requiera el uso del mismo mutex. En el ejemplo de productor-consumidor descrito anteriormente, la cola debe estar protegida por un objeto mutex único, m. Los subprocesos "productores" querrán esperar en un monitor usando un bloqueo my una variable de condición que se bloquea hasta que la cola no esté llena. Los subprocesos "consumidores" querrán esperar en un monitor diferente usando el mismo mutex pero una variable de condición diferente que se bloquea hasta que la cola no esté vacía. (Por lo general) nunca tendría sentido tener diferentes exclusiones mutuas 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 la misma exclusión mutua. Un mutex utilizado por una o más variables de condición (uno o más monitores) también se puede compartir 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 suceden. requerir esperar una determinada condición en los datos concurrentes.m
El uso básico adecuado de un monitor es:
adquirir ( m ); // Adquirir el bloqueo de este monitor. while ( ! p ) { // Mientras la condición/predicado/aserción que estamos esperando no sea cierta... espera ( m , cv ); // Espere el bloqueo y la variable de condición de este monitor. } //... La sección crítica del código va aquí... señal ( cv2 ); // O: transmisión(cv2); // cv2 puede ser igual que cv o diferente. soltar ( 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á pasando:
// ... (código anterior) // A punto de ingresar al monitor. // Adquirir el mutex (bloqueo) de asesoramiento asociado con los // datos simultáneos que se comparten entre subprocesos, // para garantizar que no se puedan entrelazar preventivamente dos subprocesos o // ejecutarse simultáneamente en diferentes núcleos mientras se ejecutan en // secciones críticas que leer o escribir estos mismos datos concurrentes. Si otro // subproceso contiene este mutex, entonces este subproceso se pondrá en suspensión // (bloqueado) y se colocará en la cola de suspensión de m. (Mutex "m" no 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 del bucle while después de // "adquirir" anterior, preguntamos: "¿La condición/predicado/afirmación // que estamos esperando ya es verdadera?"while ( ! p ()) // "p" es cualquier expresión (por ejemplo, variable o // llamada a función) que verifica la condición y // evalúa como booleana. Esta en sí misma es una // sección crítica, por lo que *DEBE* mantener el bloqueo cuando // ejecute esta condición de bucle " while ". // Si esta no es la primera vez que se verifica la condición "mientras", // entonces estamos haciendo la pregunta: "Ahora que otro hilo que usa este // monitor me notificó y me despertó y he estado en contexto- cambiado // de nuevo a, la condición/predicado/afirmación que estamos esperando permaneció // verdadera entre el momento en que me desperté y el momento en que volví a adquirir // el bloqueo dentro de la llamada "espera" en la última iteración de este bucle, o // ¿algún otro hilo provocó que la condición volviera a ser falsa mientras tanto // haciendo de esto una reactivación espuria? { // Si esta es la primera iteración del bucle, entonces la respuesta es // "no": la condición aún no está lista. En caso contrario, la respuesta es: // esta última. Esta fue una activación espuria, algún otro hilo ocurrió // primero y provocó que la condición volviera a ser falsa, y debemos // esperar nuevamente.espera ( m , cv ); // Impedir temporalmente que cualquier otro subproceso en cualquier núcleo realice // operaciones en m o cv. // liberar(m) // Liberar atómicamente el bloqueo "m" para que otro // // código usando estos datos concurrentes // // pueda operar, mueva este hilo a cv // // cola de espera para que sea notificado // // en algún momento cuando la condición se convierta // // en verdadera, y suspenda este hilo. Vuelva a habilitar // // otros subprocesos y núcleos para realizar // // operaciones en m y cv. // // El cambio de contexto se produce en este núcleo. // // En algún momento futuro, la condición que estamos esperando se vuelve // verdadera, y otro subproceso que usa este monitor (m, cv) emite // una señal que activa este subproceso o // una transmisión eso nos despierta, lo que significa que hemos sido sacados // de la cola de espera del 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 permanecer verdadera. // // Este hilo se vuelve a cambiar a algún núcleo. // // adquirir(m) // Se vuelve a adquirir el bloqueo "m". // Finalice esta iteración del bucle y vuelva a comprobar la condición del bucle " while " para asegurarse // de que el predicado sigue siendo verdadero. } // ¡La condición que estamos esperando es verdadera! // Todavía mantenemos el bloqueo, ya sea antes de ingresar al monitor o desde // la última ejecución de "esperar".// La sección crítica del código va aquí, 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 hacer que los // predicados de otras variables de condición sean verdaderos.// Señal de llamada o transmisión, dependiendo de qué variables de condición // 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_signal ) { señal ( cv_x ); // O: transmisión(cv_x); } // Uno o más subprocesos se han despertado pero se bloquearán tan pronto como intenten // adquirir m. // Libera el mutex para que los subprocesos notificados y otros puedan ingresar a sus // secciones críticas. soltar ( m );Habiendo introducido el uso de variables de condición, usémoslo para revisar y resolver el clásico problema acotado de productor/consumidor. 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 inseguro para subprocesos. Bloqueo global de cola ; // Un mutex para el buffer circular de tareas. (No es un bloqueo de giro). cola de CV globalEmptyCV ; // Una variable de condición para los subprocesos de los consumidores que esperan que la cola // deje de estar vacía. Su bloqueo asociado es "queueLock". cola de CV globalFullCV ; // Una variable de condición para los subprocesos productores que esperan que la cola // no esté llena. Su bloqueo asociado también es "queueLock". // Método que representa el comportamiento de cada subproceso productor: método público productor () { while ( verdadero ) { // El productor crea alguna nueva tarea para agregar. tarea miTarea = ...; // Adquirir "queueLock" para la verificación de predicado inicial. bloqueo de cola . adquirir (); // Sección crítica que comprueba si la cola no está llena. while ( queue . isFull ()) { // Libera "queueLock", pone este hilo en cola en "queueFullCV" y duerme este hilo. esperar ( colaLock , colaFullCV ); // Cuando se activa este hilo, vuelve a adquirir "queueLock" para la siguiente verificación de predicado. } // Sección crítica que agrega la tarea a la cola (tenga en cuenta que tenemos "queueLock"). cola . poner en cola ( miTarea ); // Activa uno o todos los subprocesos consumidores que están esperando que la cola no esté vacía // ahora que está garantizada, para que un subproceso consumidor asuma la tarea. señal ( colaEmptyCV ); // O: transmisión(queueEmptyCV); // Fin de las secciones críticas. // Libera "queueLock" hasta que lo necesitemos nuevamente para agregar la siguiente tarea. bloqueo de cola . liberar (); } } // Método que representa el comportamiento de cada hilo de consumidor: método público consumidor () { while ( true ) { // Adquiere "queueLock" para la verificación de predicado inicial. bloqueo de cola . adquirir (); // Sección crítica que comprueba si la cola no está vacía. while ( queue . isEmpty ()) { // Libera "queueLock", pone este hilo en cola en "queueEmptyCV" y duerme este hilo. esperar ( colaLock , colaEmptyCV ); // Cuando se activa este hilo, vuelve a adquirir "queueLock" para la siguiente verificación de predicado. } // Sección crítica que saca una tarea de la cola (tenga en cuenta que estamos manteniendo "queueLock"). miTarea = cola . quitar la cola (); // Activa uno o todos los subprocesos productores que están esperando a que la cola no esté llena // ahora que está garantizada, para que un subproceso productor agregue una tarea. señal ( colaFullCV ); // O: transmisión(queueFullCV); // Fin de las secciones críticas. // Libera "queueLock" hasta que lo necesitemos nuevamente para realizar la siguiente tarea. bloqueo de cola . liberar (); // Ve y haz algo con la tarea. hacerCosas ( miTarea ); } } Esto garantiza la concurrencia entre los subprocesos productores y consumidores 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 antes mencionado usando 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 verifican los subprocesos individuales. La variable de condición representa los subprocesos que están esperando que la cola no esté llena y los que esperan que no esté vacía. Sin embargo, hacer esto requeriría usar transmisión en todos los subprocesos usando la variable de condición y no puede usar una señal regular . Esto se debe a que la señal normal 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ñale 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 dormir. El uso de la transmisión garantiza que algún subproceso del tipo correcto proceda según lo esperado por el planteamiento del problema.
Aquí está la variante que usa solo una variable de condición y transmisión:
cola RingBuffer volátil global ; // Un búfer circular de tareas inseguro para subprocesos. Bloqueo global de cola ; // Un mutex para el buffer circular de tareas. (No es un bloqueo de giro). cola CV globalFullOrEmptyCV ; // Una variable de condición única para cuando la cola no está lista para ningún subproceso // es decir, para los subprocesos productores que esperan que la cola no esté llena // y los subprocesos consumidores que esperan que la cola no esté vacía. // Su bloqueo asociado es "queueLock". // No es seguro utilizar una "señal" normal porque está asociada con // múltiples condiciones de predicado (afirmaciones). // Método que representa el comportamiento de cada subproceso productor: método público productor () { while ( verdadero ) { // El productor crea alguna nueva tarea para agregar. tarea miTarea = ...; // Adquirir "queueLock" para la verificación de predicado inicial. bloqueo de cola . adquirir (); // Sección crítica que comprueba si la cola no está llena. while ( queue . isFull ()) { // Libera "queueLock", pone este hilo en cola en "queueFullOrEmptyCV" y duerme este hilo. esperar ( colaLock , colaFullOrEmptyCV ); // Cuando se activa este hilo, vuelve a adquirir "queueLock" para la siguiente verificación de predicado. } // Sección crítica que agrega la tarea a la cola (tenga en cuenta que tenemos "queueLock"). cola . poner en cola ( miTarea ); // Activa todos los subprocesos productores y consumidores que están esperando que la cola // no esté llena y no vacía respectivamente ahora que esto último está garantizado, de modo que un subproceso consumidor asuma la tarea. transmisión ( colaFullOrEmptyCV ); // No utilices "señal" (ya que podría activar solo otro subproceso productor). // Fin de las secciones críticas. // Libera "queueLock" hasta que lo necesitemos nuevamente para agregar la siguiente tarea. bloqueo de cola . liberar (); } } // Método que representa el comportamiento de cada hilo de consumidor: método público consumidor () { while ( true ) { // Adquiere "queueLock" para la verificación de predicado inicial. bloqueo de cola . adquirir (); // Sección crítica que comprueba si la cola no está vacía. while ( queue . isEmpty ()) { // Libera "queueLock", pone este hilo en cola en "queueFullOrEmptyCV" y duerme este hilo. esperar ( colaLock , colaFullOrEmptyCV ); // Cuando se activa este hilo, vuelve a adquirir "queueLock" para la siguiente verificación de predicado. } // Sección crítica que saca una tarea de la cola (tenga en cuenta que estamos manteniendo "queueLock"). miTarea = cola . quitar la cola (); // Active todos los subprocesos productores y consumidores que están esperando que la cola // no esté llena y no vacía respectivamente ahora que el primero está garantizado, de modo que un subproceso productor agregue una tarea. transmisión ( colaFullOrEmptyCV ); // No utilice "señal" (ya que podría activar sólo otro hilo de consumidor). // Fin de las secciones críticas. // Libera "queueLock" hasta que lo necesitemos nuevamente para realizar la siguiente tarea. bloqueo de cola . liberar (); // Ve y haz algo con la tarea. hacerCosas ( miTarea ); } } Los monitores se implementan utilizando una primitiva atómica de lectura, modificación y escritura y una primitiva de espera. La primitiva de lectura, modificación y escritura (generalmente prueba y configuración o comparación e intercambio) suele tener la forma de una instrucción de bloqueo de memoria proporcionada por ISA , pero también puede estar compuesta de instrucciones sin bloqueo en un solo bloque. dispositivos procesadores cuando las interrupciones están deshabilitadas. La primitiva de espera puede ser un bucle de espera ocupado o una primitiva proporcionada por el sistema operativo que impide que el subproceso se programe hasta que esté listo para continuar.
A continuación se muestra un ejemplo de implementación de pseudocódigo de partes de un sistema de subprocesos y mutex y variables de condición de estilo Mesa, utilizando prueba y configuración y una política de orden de llegada:
// Partes básicas del sistema de subprocesos: // Supongamos que "ThreadQueue" admite acceso aleatorio. ThreadQueue público volátil readyQueue ; // Cola de subprocesos listos no segura para subprocesos. Los elementos son (Subproceso*). Hilo global volátil público * hilo actual ; // Supongamos que esta variable es por núcleo. (Otros se comparten). // 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. público volátil global bool threadingSystemBusy = false ; // Rutina de servicio de interrupción de cambio de contexto (ISR): // En el núcleo de CPU actual, cambie de forma preventiva a otro subproceso. método público contextSwitchISR () { if ( testAndSet ( threadingSystemBusy )) { return ; // No se puede cambiar el 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 programa (PC), necesitaremos la ubicación de las instrucciones // de la etiqueta "reanudar" que aparece a continuación. Obtener los valores de registro depende de la plataforma y puede implicar // leer el marco de pila actual, instrucciones JMP/CALL, etc. (Los detalles están más allá de este alcance). currentThread -> registros = getAllRegisters (); // Almacena los registros en el objeto "currentThread" en la memoria. hilo actual -> registros . CP = currículum ; // Configure la siguiente PC con la etiqueta "reanudar" a continuación en este método. cola lista . poner en cola ( hilo actual ); // Vuelva a colocar este hilo en la cola de listos para su posterior ejecución. Hilo * otro hilo = readyQueue . quitar la cola (); // Eliminar y obtener el siguiente hilo para ejecutar desde la cola lista. hilo actual = otro hilo ; // Reemplace el valor global del puntero del subproceso actual para que esté listo para el siguiente subproceso. // Restaurar los registros de currentThread/otherThread, incluido un salto a la PC almacenada del otro hilo // (en "reanudar" a continuación). Nuevamente, los detalles de cómo se hace esto están más allá de este alcance. restaurarRegistros ( otro hilo . registros ); // *** ¡Ahora ejecutando "otherThread" (que ahora es "currentThread")! El hilo original ahora está "durmiendo". *** resume : // Aquí es donde otra llamada a contextSwitch() necesita configurar la PC al volver a cambiar el contexto aquí. // Regresar a donde lo dejó otherThread. threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar el cambio preventivo en este núcleo. } // Método de suspensión del subproceso: // En el núcleo de la CPU actual, un contexto sincrónico cambia a otro subproceso sin colocar // el subproceso actual en la cola lista. // Debe mantener "threadingSystemBusy" y deshabilitar las interrupciones para que este método // no sea interrumpido por el temporizador de cambio de subproceso que llamaría a contextSwitchISR(). // Después de regresar de este método, debe borrar "threadingSystemBusy". método público threadSleep () { // Obtiene todos los registros del proceso que se está ejecutando actualmente. // Para el contador de programa (PC), necesitaremos la ubicación de las instrucciones // de la etiqueta "reanudar" que aparece a continuación. Obtener los valores de registro depende de la plataforma y puede implicar // leer el marco de pila actual, instrucciones JMP/CALL, etc. (Los detalles están más allá de este alcance). currentThread -> registros = getAllRegisters (); // Almacena los registros en el objeto "currentThread" en la memoria. hilo actual -> registros . CP = currículum ; // Configure la siguiente PC con la etiqueta "reanudar" a continuación en este método. // A diferencia de contextSwitchISR(), no volveremos a colocar currentThread en readyQueue. // En cambio, ya se ha colocado en la cola de una variable de condición o mutex. Hilo * otro hilo = readyQueue . quitar la cola (); // Eliminar y obtener el siguiente hilo para ejecutar desde la cola lista. hilo actual = otro hilo ; // Reemplace el valor global del puntero del subproceso actual para que esté listo para el siguiente subproceso. // Restaurar los registros de currentThread/otherThread, incluido un salto a la PC almacenada del otro hilo // (en "reanudar" a continuación). Nuevamente, los detalles de cómo se hace esto están más allá de este alcance. restaurarRegistros ( otro hilo . registros ); // *** ¡Ahora ejecutando "otherThread" (que ahora es "currentThread")! El hilo original ahora está "durmiendo". *** resume : // Aquí es donde otra llamada a contextSwitch() necesita configurar la PC al volver a cambiar el contexto aquí. // Regresar a donde lo dejó otherThread. }método público esperar ( Mutex m , ConditionVariable c ) { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo acceden a // "held" 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 subprocesos en este núcleo que llamaría a contextSwitchISR(). // Hecho fuera de threadSleep() para mayor eficiencia, de modo que este hilo entre en suspensión // justo después de pasar a la cola de variables de condición. systemCall_disableInterrupts (); afirmar m . sostuvo ; // (Específicamente, este hilo debe ser el que lo sostiene). m . liberar (); C . esperandoHilos . poner en cola ( hilo actual ); hiloSueño (); // 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 (); // Vuelve a activar el cambio preventivo en este núcleo. // Estilo Mesa: // Ahora pueden ocurrir cambios de contexto aquí, haciendo que el predicado del cliente que llama 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 // "held" 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 subprocesos en este núcleo que llamaría a contextSwitchISR(). // Hecho fuera de threadSleep() para mayor eficiencia, de modo que este hilo entre en suspensión // justo después de pasar a la cola de variables de condición. systemCall_disableInterrupts (); if ( ! c . hilos en espera . isEmpty ()) { hilo despertado = c . esperandoHilos . quitar la cola (); cola lista . poner en cola ( hilo despertado ); } threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar el cambio preventivo en este núcleo. // Estilo Mesa: // El hilo despertado no tiene ninguna prioridad. } difusión del método público ( ConditionVariable c ) { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo acceden a // "held" 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 subprocesos en este núcleo que llamaría a contextSwitchISR(). // Hecho fuera de threadSleep() para mayor eficiencia, de modo que este hilo entre en suspensión // justo después de pasar a la cola de variables de condición. systemCall_disableInterrupts (); while ( ! c . hilos en espera . está vacío ()) { hilo despertado = c . esperandoHilos . quitar la cola (); cola lista . poner en cola ( hilo despertado ); } threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar el cambio preventivo en este núcleo. // Estilo Mesa: // Los hilos despertados no tienen ninguna prioridad. } clase Mutex { bool volátil protegido retenido = falso ; Bloqueo de ThreadQueue volátil privadoThreads ; // Cola de subprocesos bloqueados que no es segura para subprocesos. Los elementos son (Subproceso*). método público adquirir () { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo acceden a // "held" 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 subprocesos en este núcleo que llamaría a contextSwitchISR(). // Hecho fuera de threadSleep() para mayor eficiencia, de modo que este hilo entre en suspensión // justo después de pasar a la cola de bloqueo. systemCall_disableInterrupts (); afirmar ! bloqueo de hilos . contiene ( hilo actual ); if ( held ) { // Ponga "currentThread" en la cola de este bloqueo para que // se considere "durmiente" en este bloqueo. // Tenga en cuenta que "currentThread" aún debe ser manejado por threadSleep(). cola lista . eliminar ( hilo actual ); bloqueo de hilos . poner en cola ( hilo actual ); hiloSueño (); // Ahora estamos despertados, lo cual debe ser porque "retenido" se volvió falso. afirmar ! sostuvo ; afirmar ! bloqueo de hilos . contiene ( hilo actual ); } retenido = verdadero ; threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar el cambio preventivo en este núcleo. } lanzamiento de método público () { // Bloqueo de giro interno mientras otros subprocesos en cualquier núcleo acceden a // "held" 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 sostenido ; // (La liberación solo debe realizarse mientras se mantiene el bloqueo). retenido = falso ; if ( ! blockingThreads . isEmpty ()) { Hilo * unblockedThread = blockingThreads . quitar la cola (); cola lista . poner en cola ( hilo desbloqueado ); } threadingSystemBusy = falso ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar el cambio preventivo en este núcleo. } } struct ConditionVariable { volátil ThreadQueue esperandoThreads ; } Las propuestas originales de CAR Hoare y Per Brinch Hansen eran para bloquear variables de condición . Con una variable de condición de bloqueo, el subproceso de señalización debe esperar fuera del monitor (al menos) hasta que el subproceso señalado abandone la ocupación del monitor regresando o esperando nuevamente 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 .
-SU.png/1280px-Monitor_(synchronization)-SU.png)
ay b. Después de Buhr et al.Suponemos que hay dos colas de subprocesos asociados con cada objeto monitor.
ees la cola de entradasEs una cola de hilos que 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 la variable de condición cPor lo general, se garantiza que todas las colas serán justas y, en algunas implementaciones, se puede garantizar que sean las primeras en entrar, primeras en salir .
La implementación de cada operación es la siguiente. (Asumimos 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 al monitor: ingresa el método si el monitor está bloqueado agregar este hilo a e bloquear este hilo demás bloquear el monitordejar el monitor: cronograma regresar del métodoesperac : agregue este hilo a c .q cronograma bloquear este hiloseñal c : si hay un hilo esperando en c .q seleccione y elimine uno de esos hilos t de c .q (se llama "el hilo señalado") agregar este hilo a s reiniciar t (Así que ocupará el monitor a continuación) bloquear este hilocronograma: si hay un hilo en s seleccione y elimine un hilo de s y 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 schedulerutina 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 señalizador debe esperar, pero se le da prioridad sobre los subprocesos en la cola de entrada. Una alternativa es "señalar y esperar", en la que no hay scola y el señalizador espera en la ecola.
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 c y retorno : si hay un hilo esperando en c .q seleccione y elimine uno de esos hilos t de c .q (se llama "el hilo señalado") reiniciar t (Así que ocupará el monitor a continuación) demás cronograma regresar del método
En cualquier caso ("señal y espera urgente" o "señal y espera"), cuando se señala una variable de condición y hay al menos un hilo esperando en la variable de condición, el hilo de señalización entrega la ocupación al hilo señalado sin problemas, por lo que que ningún otro hilo pueda ganar ocupación en el medio. Si P c es verdadero al inicio de cada operación de señal c , será verdadero al final de cada operación de espera c . Esto se resume en los siguientes contratos . En estos contratos, I es la invariante del monitor .
entrar al monitor: poscondición Idejar el monitor: condición previa yoesperar c : condición previa I modifica el estado del monitor condición posterior 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 retorno : condición previa P c y I
En estos contratos, se supone que I y P c no dependen del contenido ni de la longitud de ninguna cola.
(Cuando se puede consultar a la variable de condición sobre el número de subprocesos esperando en su cola, se pueden proporcionar contratos más sofisticados. Por ejemplo, un par de contratos útiles, que permiten pasar la ocupación sin establecer el invariante, es:
esperar c : condición previa I modifica el estado del monitor condición posterior P c La condición previa de la señal c ( no vacía ( c ) y P c ) o (vacía ( c ) y I ) modifica el estado de la poscondición 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 acerca de 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 constante privada : = 10 int privado [capacidad] Un tamaño int privado : = 0 invariante 0 <= tamaño y tamaño <= capacidad condición de bloqueo privada theStackIsNotEmpty /* asociado con 0 < tamaño y tamaño <= capacidad */ privado BlockingCondition theStackIsNotFull /* asociado con 0 <= tamaño y tamaño < capacidad */ push de método público ( valor int ) { si tamaño = capacidad entonces espere theStackIsNotFull afirmar 0 <= tamaño y tamaño <capacidad A[tamaño]:= valor; tamaño := tamaño + 1 afirmar 0 <tamaño y tamaño <= señal de capacidad theStackIsNotEmpty y regresar } método público int pop() { si tamaño = 0 entonces espere theStackIsNotEmpty afirmar 0 <tamaño y tamaño <= capacidad tamaño := tamaño - 1 ; afirmar 0 <= tamaño y tamaño < capacidad 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 simultáneos. La única diferencia es que el ejemplo de productor/consumidor asumió una cola regular no segura para subprocesos y usaba un mutex independiente y variables de condición, sin que estos detalles del monitor se abstraigan como es el caso aquí. En este ejemplo, cuando se llama a la operación "esperar", de alguna manera se le debe proporcionar el mutex de la pila segura para subprocesos, como si la operación "esperar" fuera 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.
Con las variables de condición sin bloqueo (también llamadas variables de condición "estilo Mesa" o variables de condición "señalar y continuar" ), la señalización no hace que el hilo de señalización pierda la ocupación del monitor. En lugar de ello, los subprocesos señalados se mueven a la ecola. No hay necesidad de hacer scola.
-Mesa.png/1280px-Monitor_(synchronization)-Mesa.png)
aybCon variables de condición sin bloqueo, la operación de la señal a menudo se denomina notificación , una terminología que seguiremos aquí. También es común proporcionar una operación de notificación a todos que mueva todos los subprocesos que esperan una variable de condición a la ecola.
Aquí se proporciona el significado de varias operaciones. (Asumimos 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 al monitor: ingresa el método si el monitor está bloqueado agregar este hilo a e bloquear este hilo demás bloquear el monitordejar el monitor: cronograma regresar del métodoesperac : agregue este hilo a c .q cronograma bloquear este hilonotificar c : si hay un hilo esperando en c .q seleccione y elimine un hilo t de c .q (se llama "el hilo notificado") mover t a enotificar a todos c : mover todos los hilos que esperan en 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 variación de este esquema, el hilo notificado puede moverse 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 afirmació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 Pc se conserve desde el momento en que el subproceso notificante abandona la ocupación hasta que se selecciona el subproceso notificado para volver a ingresar al monitor. Entre estos horarios podría haber actividad de otros ocupantes. Por tanto, es común que P c sea simplemente verdadera .wait c
Por este motivo, normalmente es necesario encerrar cada operación de espera en un bucle como este
mientras no ( P ) espera cdonde P es alguna condición más fuerte que P c . Las operaciones y se tratan como "pistas" de que P puede ser verdadera para algún hilo en espera. Cada iteración de dicho bucle después de la primera representa una notificación perdida; por lo tanto, con los monitores sin bloqueo, se debe tener cuidado para garantizar que no se puedan perder demasiadas notificaciones.notify cnotify 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.
cuenta de clase de monitor { saldo int privado : = 0 saldo invariante > = 0 saldo privado de condición sin bloqueoMayBeBigEnough método público retirar ( monto int ) monto de condición previa >= 0 { mientras que el saldo <cantidad espere saldoMayBeBigEnough afirmar el saldo>= cantidad saldo := saldo - monto } depósito de método público ( monto int ) monto de condición previa > = 0 { saldo := saldo + monto notificar todo el saldoMayBeBigEnough }}En este ejemplo, la condición que se espera es función de la cantidad a retirar, por lo que es imposible que un hilo de depósito sepa que dicha condición se cumplió. En este caso tiene sentido permitir que cada hilo en espera entre al monitor (uno a la vez) verifique si su afirmación es verdadera.
-Java.png/1280px-Monitor_(synchronization)-Java.png)
En el lenguaje Java , cada objeto puede usarse 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 como sincronizados . [6]
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. Toda la espera se realiza en esta única cola de espera y todas las operaciones de notificación y notificación se aplican a esta cola. [7] Este enfoque se ha adoptado en otros lenguajes, por ejemplo C# .
Otro enfoque de la señalización es omitir la operación de la señal . Cada vez que un hilo sale del monitor (regresando o esperando), las afirmaciones de todos los hilos en espera se evalúan hasta que se descubre que una es verdadera. En tal sistema, las variables de condición no son necesarias, pero las afirmaciones deben codificarse explícitamente. El contrato de espera es
esperar P : condición previa I modifica el estado del monitor condición posterior P e I
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 . [8] Brinch Hansen publicó la primera notación de monitor, adoptando el concepto de clase de Simula 67 , [1] e inventó un mecanismo de cola. [9] Hoare refinó las reglas de reanudación del proceso. [2] Brinch Hansen creó la primera implementación de monitores, en Concurrent Pascal . [8] Hoare demostró su equivalencia con los semáforos .
Pronto se utilizaron monitores (y Pascal concurrente) para estructurar la sincronización de procesos en el sistema operativo Solo. [10] [11]
Los lenguajes de programación que han admitido monitores incluyen:
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, corresponde al programador marcar explícitamente el inicio y el final del código ejecutado con exclusión mutua. Pthreads es una de esas bibliotecas.