Monitor (sincronización)

Para muchas aplicaciones, la exclusión mutua no es suficiente. Los hilos que intentan realizar una operación pueden necesitar esperar hasta que se cumpla alguna condición P. Un bucle de espera activa .

mientras no ( P ) hacer saltar

No funcionará, ya que la exclusión mutua impedirá que cualquier otro hilo acceda al monitor para que la condición sea verdadera. Existen otras "soluciones", como un bucle que desbloquee el monitor, espere un tiempo determinado, lo bloquee y compruebe la condición P. En teoría, funciona y no provoca interbloqueos, pero surgen problemas. Es difícil determinar un tiempo de espera adecuado: si es demasiado corto, el hilo acaparará la CPU; si es demasiado largo, aparentemente no responderá. Lo que se necesita es una forma de indicar al hilo cuándo la condición P es verdadera (o podría serlo).

Un problema clásico de concurrencia es el del productor/consumidor limitado , en el que existe una cola o búfer circular de tareas con un tamaño máximo. Uno o más hilos actúan como "productores" que añaden tareas a la cola, y otros uno o más hilos actúan como "consumidores" que las extraen. Se supone que la cola no es segura para hilos y puede estar vacía, llena o en un estado intermedio. Cuando la cola está llena, los hilos productores deben bloquearse hasta que haya espacio disponible debido a que los hilos consumidores extraen tareas. Por otro lado, cuando la cola está vacía, los hilos consumidores deben bloquearse hasta que haya más tareas disponibles gracias a que los hilos productores las añaden.

Dado que la cola es un objeto concurrente compartido entre hilos, los accesos a ella deben ser atómicos , ya que la cola puede quedar en un estado inconsistente durante el acceso, el cual nunca debe quedar expuesto entre hilos. Por lo tanto, cualquier código que acceda a la cola constituye una sección crítica que debe sincronizarse mediante exclusión mutua. Si el código y las instrucciones del procesador en secciones críticas que acceden a la cola pudieran intercalarse mediante cambios de contexto arbitrarios entre hilos en el mismo procesador o mediante hilos que se ejecutan simultáneamente en varios procesadores, existe el riesgo de exponer un estado inconsistente y provocar condiciones de carrera .

global RingBuffer queue ; // Un búfer circular de tareas que no es seguro para subprocesos.// Método que representa el comportamiento de cada hilo productor: public method producer () { while ( true ) { task myTask = ...; // El productor crea una nueva tarea para agregar. while ( queue . isFull ()) {} // Espera activa hasta que la cola no esté llena. queue . enqueue ( myTask ); // Agrega la tarea a la cola. } }// Método que representa el comportamiento de cada hilo consumidor: public method consumer () { while ( true ) { while ( queue . isEmpty ()) {} // Espera activa hasta que la cola no esté vacía. myTask = queue . dequeue (); // Toma una tarea de la cola. doStuff ( myTask ); // Realiza alguna acción con la tarea. } }

global RingBuffer queue ; // Un búfer circular de tareas no seguro para subprocesos. global Lock queueLock ; // Un mutex para el búfer circular de tareas.// Método que representa el comportamiento de cada hilo productor: public method producer () { while ( true ) { task myTask = ...; // El productor crea una nueva tarea para agregar.queueLock.acquire (); // Adquiere el bloqueo para la comprobación inicial de espera activa. while ( queue.isFull ( )) { // Espera activa hasta que la cola no esté llena. queueLock.release ( ) ; // Libera el bloqueo temporalmente para permitir que otros hilos // que necesiten queueLock se ejecuten y así un consumidor pueda tomar una tarea. queueLock.acquire ( ); // Vuelve a adquirir el bloqueo para la siguiente llamada a "queue.isFull()" . }cola.enqueue ( myTask ); // Agrega la tarea a la cola. queueLock.release ( ); // Libera el bloqueo de la cola hasta que lo necesitemos de nuevo para agregar la siguiente tarea. } }// Método que representa el comportamiento de cada hilo consumidor: public method consumer () { while ( true ) { queueLock . acquire (); // Adquiere el bloqueo para la comprobación inicial de espera activa. while ( queue . isEmpty ()) { // Espera activa hasta que la cola no esté vacía. queueLock . release (); // Libera el bloqueo temporalmente para permitir que otros hilos // que necesiten queueLock se ejecuten para que un productor pueda agregar una tarea. queueLock . acquire (); // Vuelve a adquirir el bloqueo para la siguiente llamada a "queue.isEmpty()". } myTask = queue . dequeue (); // Toma una tarea de la cola. queueLock . release (); // Libera el bloqueo de la cola hasta que lo necesitemos de nuevo para tomar la siguiente tarea. doStuff ( myTask ); // Realiza alguna acción con la tarea. } }

La solución consiste en utilizar variables de condición . Conceptualmente, una variable de condición es una cola de hilos, asociada a un mutex, en la que un hilo puede esperar a que se cumpla una condición. Así, cada variable de condición c se asocia a una aserción P _c . Mientras un hilo espera en una variable de condición, no se considera que ocupe el monitor, por lo que otros hilos pueden acceder a él para modificar su estado. En la mayoría de los tipos de monitores, estos otros hilos pueden enviar señales a la variable de condición c para indicar que la aserción P _c es verdadera en el estado actual.

Por lo tanto, existen tres operaciones principales sobre las variables de condición:

• wait c, mdonde ces una variable de condición y mes un mutex (bloqueo) asociado al monitor. Esta operación es llamada por un hilo 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 el contrato fundamental, de la operación "esperar" consiste en realizar los siguientes pasos:
  1. Atómicamente :

     1. liberar el mutex m,
     2. mover este hilo de la "en ejecución" a cla "cola de espera" (también conocida como "cola de suspensión") de hilos, y
     3. Este hilo se pone en pausa. (El contexto se transfiere sincrónicamente a otro hilo).

  2. Una vez que este hilo sea posteriormente notificado/señalizado (ver más abajo) y se reanude, entonces vuelva a adquirir automáticamente el mutex m.

  Los pasos 1a y 1b pueden ocurrir en cualquier orden, y el paso 1c suele ocurrir después. Mientras el hilo está inactivo y en 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 "wait" . Por lo tanto, el hilo se inactiva y luego se activa en medio de la operación "wait".

  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 fallo que podría ocurrir si estas no fueran atómicas es una pérdida de activación , en la que el hilo podría estar en cla cola de suspensión de y haber liberado el mutex, pero un cambio de hilo preventivo ocurrió antes de que el hilo entrara en suspensión, y otro hilo llamó a una operación de señal (ver más abajo) al cmover el primer hilo de vuelta fuera de cla cola de. Tan pronto como el primer hilo en cuestión vuelva a, su contador de programa estará en el paso 1c, y entrará en suspensión y no podrá ser despertado de nuevo, violando la invariante de que debería haber estado en cla cola de suspensión cuando entró en suspensión. Otras condiciones de carrera dependen del orden de los pasos 1a y 1b, y dependen de dónde ocurre un cambio de contexto .

• signal c, también conocido como notify c, es llamado por un hilo para indicar que la aserción P _c es verdadera. Dependiendo del tipo e implementación del monitor, esto mueve uno o más hilos de cla cola de suspensión de a la "cola lista" u otra cola para que se ejecute. Por lo general, se considera una buena práctica realizar la operación de "señalización" antes de liberar el mutex masociado con c, pero siempre que el código esté correctamente diseñado para la concurrencia y dependiendo de la implementación de hilos, a menudo también es aceptable liberar el bloqueo antes de señalizar. Dependiendo de la implementación de hilos, el orden de esto puede tener ramificaciones en la prioridad de planificación. (Algunos autores abogan en cambio por una preferencia por liberar el bloqueo antes de señalizar). Una implementación de hilos debe documentar cualquier restricción especial sobre este orden.
• broadcast c, también conocido como notifyAll c, es una operación similar que despierta a todos los hilos 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á difusión en lugar de señal porque un hilo que espera la condición incorrecta podría despertarse y luego volver a dormirse inmediatamente sin despertar a un hilo que espera la condición correcta que acaba de volverse verdadera. De lo contrario, si la condición de predicado es uno a uno con la variable de condición asociada a ella, entonces señal puede ser más eficiente que difusión .

Como regla de diseño, se pueden asociar varias variables de condición al 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 hilos que usan el monitor y debe estar protegido con exclusión mutua de todos los demás hilos que podrían causar que la condición cambie o que podrían leerla mientras el hilo en cuestión la cambia, pero puede haber diferentes hilos que quieran esperar una condición diferente en la misma variable, lo que requiere que se use el mismo mutex. En el ejemplo productor-consumidor descrito anteriormente , la cola debe estar protegida por un objeto mutex único m. Los hilos "productores" querrán esperar en un monitor usando un bloqueo my una variable de condición.${\displaystyle c_{full}}$que se bloquea hasta que la cola no esté llena. Los hilos "consumidores" querrán esperar en un monitor diferente usando el mismo mutex mpero una variable de condición diferente.${\displaystyle c_{empty}}$que se bloquea hasta que la cola no esté vacía. Normalmente no tendría sentido tener diferentes mutex para la misma variable de condición, pero este ejemplo clásico muestra por qué a menudo sí tiene sentido tener varias variables de condición que utilicen el mismo mutex. Un mutex utilizado por una o más variables de condición (uno o más monitores) también puede compartirse con código que no utiliza variables de condición (y que simplemente lo adquiere/libera sin ninguna operación de espera/señalización), si esas secciones críticas no requieren esperar a que se cumpla una determinada condición en los datos concurrentes.

El uso básico adecuado de un monitor es:

adquirir ( m ); // Adquiere el bloqueo de este monitor. mientras ( ! p ) { // Mientras la condición/predicado/aserción que estamos esperando no sea verdadera... esperar ( m , cv ); // Espera en el bloqueo de este monitor y la variable de condición. } // ... La sección crítica del código va aquí ... señal ( cv2 ); // O: difusión(cv2); // cv2 puede ser igual que cv o diferente. liberar ( m ); // Libera el bloqueo de este monitor.

A continuación se muestra el mismo pseudocódigo , pero con comentarios más detallados para explicar mejor lo que sucede:

// ... (código anterior) // A punto de entrar en el monitor. // Adquirir el mutex (bloqueo) consultivo asociado con los datos concurrentes // que se comparten entre hilos, // para asegurar que no se puedan intercalar dos hilos de forma preventiva o // ejecutar simultáneamente en diferentes núcleos mientras se ejecutan en secciones críticas // que leen o escriben estos mismos datos concurrentes. Si otro // hilo está manteniendo este mutex, entonces este hilo se pondrá en espera // (bloqueado) y se colocará en la cola de espera de m. (El mutex "m" no debe ser // un spin-lock). adquirir ( m ); // Ahora, estamos manteniendo el bloqueo y podemos comprobar la condición por // primera vez.// La primera vez que ejecutamos la condición del bucle while después de la llamada anterior // "adquirir", nos preguntamos: "¿La condición/predicado/aserción // que estamos esperando ya es verdadera?"while ( ! p ()) // "p" es cualquier expresión (por ejemplo, variable o // llamada a función) que comprueba la condición y // se evalúa como booleana. Esta es una sección crítica, // por lo que *DEBE* mantener el bloqueo cuando // ejecute esta condición del bucle "while". // Si esta no es la primera vez que se comprueba la condición "while", // entonces nos preguntamos: "Ahora que otro hilo que usa este // monitor me ha notificado y me ha despertado, y he vuelto al contexto // cambiado, ¿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 "wait" en la última iteración de este bucle, o // algún otro hilo hizo que la condición volviera a ser falsa mientras tanto, lo que convierte esto en un despertar espurio?{ // Si esta es la primera iteración del bucle, entonces la respuesta es // "no" -- la condición aún no está lista. De lo contrario, la respuesta es: // la segunda. Esto fue un despertar espurio, algún otro hilo ocurrió // primero y provocó que la condición volviera a ser falsa, y debemos // esperar de nuevo.wait ( m , cv ); // Impide temporalmente que cualquier otro hilo en cualquier núcleo realice // operaciones en m o cv. // release(m) // Libera atómicamente el bloqueo "m" para que otro // // código que utilice estos datos concurrentes // // pueda operar, mueve este hilo a la // // cola de espera de cv para que se le notifique // // en algún momento cuando la condición se vuelva // // verdadera, y duerme este hilo. Vuelve a habilitar // // otros hilos y núcleos para realizar // // operaciones en m y cv. // // Se produce un cambio de contexto en este núcleo. // // En algún momento futuro, la condición que estamos esperando se vuelve // ​​verdadera, y otro hilo que utiliza este monitor (m, cv) hace // una señal que despierta a este hilo, o una // difusión que nos despierta, lo que significa que hemos sido sacados // de la cola de espera de cv. // // Durante este tiempo, otros hilos pueden hacer que la condición // vuelva a ser falsa, o la condición puede alternar una o más // veces, o puede que permanezca verdadera. // // Este hilo vuelve a activarse en algún núcleo. // // acquire(m) // Se vuelve a adquirir el bloqueo "m". // Finaliza esta iteración del bucle y vuelve 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 desde antes de entrar al monitor o desde // la última ejecución de "wait".// Aquí va la sección crítica del código, que tiene una precondición de que nuestro predicado // debe ser verdadero. // Este código podría 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 difusión, dependiendo de qué predicados de las variables de condición // (que comparten el mutex m) se hayan hecho verdaderos o puedan haberse hecho verdaderos, // y del tipo semántico del monitor que se esté utilizando.para ( cv_x en cvs_to_signal ) { señal ( cv_x ); // O: difusión(cv_x); } // Uno o más hilos se han despertado pero se bloquearán tan pronto como intenten // adquirir m.// Libera el mutex para que los hilos notificados y otros puedan entrar en sus secciones críticas. release ( m );

global volatile RingBuffer queue ; // Un búfer circular de tareas no seguro para subprocesos. global Lock queueLock ; // Un mutex para el búfer circular de tareas. (No es un spin-lock). global CV queueEmptyCV ; // Una variable de condición para los subprocesos consumidores que esperan a que la cola // deje de estar vacía. Su bloqueo asociado es "queueLock". global CV queueFullCV ; // Una variable de condición para los subprocesos productores que esperan a que la cola // deje de estar llena. Su bloqueo asociado también es "queueLock".// Método que representa el comportamiento de cada hilo productor: public method producer () { while ( true ) { // El productor crea una nueva tarea para agregar. task myTask = ...;// Adquirir " queueLock " para la comprobación inicial del predicado. queueLock.acquire ( );// Sección crítica que comprueba si la cola no está llena. while ( queue.isFull ( )) { // Libera "queueLock", encola este hilo en "queueFullCV" y suspende este hilo. wait ( queueLock , queueFullCV ); // Cuando este hilo se despierte, vuelve a adquirir "queueLock" para la siguiente comprobación del predicado. }// Sección crítica que agrega la tarea a la cola (tenga en cuenta que estamos manteniendo "queueLock"). cola.enqueue ( myTask ) ;// Despierta a uno o a todos los hilos consumidores que están esperando a que la cola no esté vacía // ahora que está garantizado, para que un hilo consumidor tome la tarea. signal ( queueEmptyCV ); // O: broadcast(queueEmptyCV); // Fin de las secciones críticas.// Libera "queueLock" hasta que lo necesitemos de nuevo para añadir la siguiente tarea. queueLock.release ( ); } }// Método que representa el comportamiento de cada hilo consumidor: public method consumer () { while ( true ) { // Adquirir "queueLock" para la comprobación inicial del predicado. queueLock . acquire ();// Sección crítica que comprueba si la cola no está vacía. while ( queue.isEmpty ()) { // Libera "queueLock", encola este hilo en "queueEmptyCV" y suspende este hilo. wait ( queueLock , queueEmptyCV ); // Cuando este hilo se despierte, vuelve a adquirir "queueLock" para la siguiente comprobación del predicado. }// Sección crítica que toma una tarea de la cola (tenga en cuenta que estamos manteniendo "queueLock"). myTask = queue . dequeue ();// Despierta uno o todos los hilos productores que están esperando a que la cola no esté llena // ahora que está garantizado, para que un hilo productor agregue una tarea. signal ( queueFullCV ); // O: broadcast(queueFullCV); // Fin de las secciones críticas.// Libera "queueLock" hasta que lo necesitemos de nuevo para tomar la siguiente tarea. queueLock.release ( );// Ve y haz algo con la tarea. doStuff ( myTask ); } }

global volatile RingBuffer queue ; // Un búfer circular de tareas no seguro para subprocesos. global Lock queueLock ; // Un mutex para el búfer circular de tareas. (No es un spin-lock). global CV queueFullOrEmptyCV ; // Una única variable de condición para cuando la cola no está lista para ningún subproceso // es decir, para subprocesos productores que esperan a que la cola no esté llena // y subprocesos consumidores que esperan a 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: public method producer () { while ( true ) { // El productor crea una nueva tarea para agregar. task myTask = ...;// Adquirir " queueLock " para la comprobación inicial del predicado. queueLock.acquire ( );// Sección crítica que comprueba si la cola no está llena. while ( queue.isFull ()) { // Libera "queueLock", encola este hilo en "queueFullOrEmptyCV" y suspende este hilo. wait ( queueLock , queueFullOrEmptyCV ); // Cuando este hilo se despierte, vuelve a adquirir "queueLock" para la siguiente comprobación del predicado. }// Sección crítica que agrega la tarea a la cola (tenga en cuenta que estamos manteniendo "queueLock"). cola.enqueue ( myTask ) ;// Despierta a todos los hilos productores y consumidores que estén esperando a que la cola esté respectivamente // no llena y no vacía ahora que esto último está garantizado, para que un hilo consumidor tome la tarea. broadcast ( queueFullOrEmptyCV ); // No uses "signal" (ya que podría despertar solo a otro hilo productor). // Fin de las secciones críticas.// Libera "queueLock" hasta que lo necesitemos de nuevo para añadir la siguiente tarea. queueLock.release ( ); } }// Método que representa el comportamiento de cada hilo consumidor: public method consumer () { while ( true ) { // Adquirir "queueLock" para la comprobación inicial del predicado. queueLock . acquire ();// Sección crítica que comprueba si la cola no está vacía. while ( queue.isEmpty ()) { // Libera "queueLock", encola este hilo en "queueFullOrEmptyCV" y suspende este hilo. wait ( queueLock , queueFullOrEmptyCV ); // Cuando este hilo se despierte, vuelve a adquirir "queueLock" para la siguiente comprobación del predicado. }// Sección crítica que toma una tarea de la cola (tenga en cuenta que estamos manteniendo "queueLock"). myTask = queue . dequeue ();// Despierta a todos los hilos productores y consumidores que estén esperando a que la cola esté respectivamente // no llena y no vacía ahora que lo primero está garantizado, para que un hilo productor agregue una tarea. broadcast ( queueFullOrEmptyCV ); // No uses "signal" (ya que podría despertar solo a otro hilo consumidor). // Fin de las secciones críticas.// Libera "queueLock" hasta que lo necesitemos de nuevo para tomar la siguiente tarea. queueLock.release ( );// Ve y haz algo con la tarea. doStuff ( myTask ); } }

Los monitores se implementan mediante una primitiva atómica de lectura-modificación-escritura y una primitiva de espera. La primitiva de lectura-modificación-escritura (generalmente de prueba y establecimiento o de comparación e intercambio ) suele ser una instrucción de bloqueo de memoria proporcionada por el conjunto de instrucciones ( ISA) , pero también puede estar compuesta por instrucciones sin bloqueo en dispositivos de un solo procesador cuando las interrupciones están deshabilitadas. La primitiva de espera puede ser un bucle de espera activa o una primitiva proporcionada por el sistema operativo que impide que el hilo se programe hasta que esté listo para continuar.

Aquí se muestra un ejemplo de implementación en pseudocódigo de partes de un sistema de subprocesos, mutexes y variables de condición al estilo Mesa, utilizando la técnica de prueba y establecimiento y una política de primero en llegar, primero en ser atendido:

// Partes básicas del sistema de subprocesos: // Supongamos que "ThreadQueue" admite acceso aleatorio. public volatile ThreadQueue readyQueue ; // Cola de subprocesos listos que no es segura para subprocesos. Los elementos son (Thread*). public volatile global Thread * currentThread ; // Supongamos que esta variable es por núcleo. (Las demás son compartidas).// Implementa un bloqueo de giro solo en el estado sincronizado del propio sistema de subprocesos. // Esto se utiliza con test-and-set como primitiva de sincronización. public volatile global bool threadingSystemBusy = false ;// Rutina de servicio de interrupción de cambio de contexto (ISR): // En el núcleo de CPU actual, cambia de forma preventiva a otro hilo. public method contextSwitchISR () { if ( testAndSet ( threadingSystemBusy )) { return ; // No se puede cambiar de contexto ahora mismo. }// Asegurarse de que esta interrupción no pueda volver a ocurrir, ya que alteraría el cambio de contexto: systemCall_disableInterrupts ();// Obtener todos los registros del proceso que se está ejecutando actualmente. // Para el contador de programa (PC), necesitaremos la ubicación de la instrucción de // la etiqueta "resume" a continuación. Obtener los valores de los registros depende de la plataforma y puede implicar // leer el marco de pila actual, instrucciones JMP/CALL, etc. (Los detalles están fuera del alcance de este método). currentThread -> registers = getAllRegisters (); // Almacenar los registros en el objeto "currentThread" en memoria. currentThread -> registers . PC = resume ; // Establecer el siguiente PC a la etiqueta "resume" a continuación en este método.readyQueue . enqueue ( currentThread ); // Vuelve a poner este hilo en la cola de listos para su posterior ejecución. Thread * otherThread = readyQueue . dequeue (); // Elimina y obtén el siguiente hilo para ejecutar de la cola de listos. currentThread = otherThread ; // Reemplaza el valor del puntero global current-thread para que esté listo para el siguiente hilo.// Restaura los registros del hilo actual/otro hilo, incluyendo un salto al PC almacenado del otro hilo // (en "resume" más abajo). Nuevamente, los detalles de cómo se hace esto están fuera del alcance de este documento. restoreRegisters ( otherThread . registers );// *** ¡Ahora se está ejecutando "otherThread" (que ahora es "currentThread")! El hilo original ahora está "durmiendo". ***resumen : // Aquí es donde otra llamada a contextSwitch() necesita establecer PC al cambiar el contexto de vuelta aquí.// Regresar al punto donde se quedó otherThread.threadingSystemBusy = false ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar la conmutación preventiva en este núcleo. }// Método de suspensión de subprocesos: // En el núcleo de CPU actual, un cambio de contexto síncrono a otro subproceso sin poner // el subproceso actual en la cola de listos. // Debe mantener "threadingSystemBusy" y las interrupciones deshabilitadas para que este método // no sea interrumpido por el temporizador de cambio de subprocesos que llamaría a contextSwitchISR(). // Después de regresar de este método, debe borrar "threadingSystemBusy". public method threadSleep () { // Obtener todos los registros del proceso que se está ejecutando actualmente. // Para el contador de programa (PC), necesitaremos la ubicación de la instrucción de // la etiqueta "resume" a continuación. Obtener los valores de los registros depende de la plataforma y puede implicar // leer el marco de pila actual, instrucciones JMP/CALL, etc. (Los detalles están fuera del alcance de este método). currentThread -> registers = getAllRegisters (); // Almacenar los registros en el objeto "currentThread" en la memoria. currentThread -> registers . PC = resume ; // Establecer el siguiente PC a la etiqueta "resume" 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 un mutex o variable de condición. Thread * otherThread = readyQueue . dequeue (); // Eliminar y obtener el siguiente hilo que se ejecutará de la cola ready. currentThread = otherThread ; // Reemplazar el valor del puntero global current-thread para que esté listo para el siguiente hilo.// Restaura los registros del hilo actual/otro hilo, incluyendo un salto al PC almacenado del otro hilo // (en "resume" más abajo). Nuevamente, los detalles de cómo se hace esto están fuera del alcance de este documento. restoreRegisters ( otherThread . registers );// *** ¡Ahora se está ejecutando "otherThread" (que ahora es "currentThread")! El hilo original ahora está "durmiendo". ***resumen : // Aquí es donde otra llamada a contextSwitch() necesita establecer PC al cambiar el contexto de vuelta aquí.// Regresar al punto donde se quedó otherThread. }public method wait ( Mutex m , ConditionVariable c ) { // Bloqueo 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 para que este subproceso se duerma // justo después de entrar en la cola de variables de condición. systemCall_disableInterrupts (); assert m . held ; // (Específicamente, este subproceso debe ser el que lo sostiene.) m . release (); c . waitingThreads . enqueue ( currentThread ); threadSleep (); // El hilo se duerme... El hilo se despierta por una señal/difusión. threadingSystemBusy = false ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar la conmutación preventiva en este núcleo. // Estilo Mesa: // Ahora pueden ocurrir cambios de contexto aquí, lo que hace que el predicado del cliente que llama sea falso. m.acquire (); }public method signal ( ConditionVariable c ) { // Bloqueo 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 para que este subproceso se duerma // justo después de entrar en la cola de variables de condición. systemCall_disableInterrupts (); if ( ! c . waitingThreads . isEmpty ()) { wokenThread = c . waitingThreads . dequeue (); readyQueue . enqueue ( wokenThread ); } threadingSystemBusy = false ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar la conmutación preventiva en este núcleo. // Estilo Mesa: // Al hilo despertado no se le da ninguna prioridad. }public method broadcast ( ConditionVariable c ) { // Bloqueo 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 subproceso se dormirá // justo después de entrar en la cola de variables de condición. systemCall_disableInterrupts (); while ( ! c . waitingThreads . isEmpty ()) { wokenThread = c . waitingThreads . dequeue (); readyQueue . enqueue ( wokenThread ); } threadingSystemBusy = false ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar la conmutación preventiva en este núcleo. // Estilo Mesa: // A los hilos despertados no se les da ninguna prioridad. }clase Mutex { protected volatile bool held = false ; private volatile ThreadQueue blockingThreads ; // Cola no segura para subprocesos de subprocesos bloqueados. Los elementos son (Thread*). public method acquire () { // 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 para que este subproceso se duerma // justo después de entrar en la cola de bloqueo. systemCall_disableInterrupts ();afirmar ! blockingThreads . contains ( currentThread );if ( held ) { // Coloca "currentThread" en la cola de este bloqueo para que se // considere "durmiendo" en este bloqueo. // Ten en cuenta que "currentThread" todavía necesita ser manejado por threadSleep(). readyQueue . remove ( currentThread ); blockingThreads . enqueue ( currentThread ); threadSleep (); // Ahora nos despertamos, lo que debe ser porque "held" se volvió falso. assert ! held ; assert ! blockingThreads . contains ( currentThread ); } held = true ; threadingSystemBusy = false ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar la conmutación preventiva en este núcleo. } public method release () { // Bloqueo de giro interno mientras otros hilos en cualquier núcleo están accediendo a este objeto // "held" y "threadQueue", o "readyQueue". while ( testAndSet ( threadingSystemBusy )) {} // Nota: "threadingSystemBusy" ahora es verdadero. // Llamada al sistema para deshabilitar las interrupciones en este núcleo para mayor eficiencia. systemCall_disableInterrupts (); assert held ; // (La liberación solo debe realizarse mientras el bloqueo esté mantenido).held = false ; if ( ! blockingThreads.isEmpty ( ) ) { Thread * unblockedThread = blockingThreads.dequeue (); readyQueue.enqueue ( unblockedThread ) ; } threadingSystemBusy = false ; // Debe ser una asignación atómica. systemCall_enableInterrupts (); // Vuelve a activar la conmutación preventiva en este núcleo . } }struct ConditionVariable { volatile ThreadQueue waitingThreads ; }

Las propuestas originales de CAR Hoare y Per Brinch Hansen se basaban en variables de condición de bloqueo . Con una variable de condición de bloqueo, el hilo que envía la señal debe esperar fuera del monitor (al menos) hasta que el hilo señalado libere la ocupación del monitor, ya sea regresando o esperando nuevamente a que se cumpla una variable de condición. Los monitores que utilizan variables de condición de bloqueo suelen denominarse monitores de estilo Hoare o monitores de señal y espera urgente .

Suponemos que hay dos colas de hilos asociadas a cada objeto monitor.

• ees la cola de entrada
• ses una cola de hilos que han enviado señales.

Además, asumimos que para cada variable de condición c , existe una cola.

• c.q, que es una cola para hilos que esperan en la variable de condición c

Por lo general, se garantiza que todas las colas sean justas y, en algunas implementaciones, se puede garantizar que sean de primero en entrar, primero en salir .

La implementación de cada operación es la siguiente. (Suponemos que cada operación se ejecuta de forma excluyente con respecto a las demás; por lo tanto, los hilos reiniciados no comienzan a ejecutarse hasta que la operación haya finalizado).

Ingrese al monitor: Introduzca el método si el monitor está bloqueado agregar este hilo a e Bloquear este hilo demás bloquear el monitor Salir del monitor: cronograma regresar del método espera c : agregar este hilo a c .q cronograma Bloquear este hilo señal c : si hay un hilo esperando en c.q Seleccione y elimine uno de esos hilos t de c.q (Se denomina "hilo señalado") agregar este hilo a s reiniciar t (por lo tanto, t ocupará el monitor a continuación) Bloquear este hilo cronograma: 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 hilo que ocupará el monitor o, en ausencia de hilos candidatos, desbloquea el monitor.

La disciplina de señalización resultante se conoce como "señalización y espera urgente", ya que el emisor debe esperar, pero tiene prioridad sobre los hilos en la cola de entrada. Una alternativa es "señalización y espera", en la que no hay scola y el emisor espera en eella.

Algunas implementaciones proporcionan una operación de señal y retorno que combina la señalización con el retorno desde 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 denomina "hilo señalado") reiniciar t (por lo tanto, t ocupará el monitor a continuación) demás cronograma regresar del método

En ambos casos ("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 que señala transfiere la ocupación al hilo señalado sin interrupciones, de modo que ningún otro hilo puede obtener ocupación entretanto. Si P _c es verdadero al comienzo 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 el invariante del monitor .

Ingrese al monitor: postcondición I Salir del monitor: precondición Iesperar c : la precondición I modifica el estado del monitor, la postcondición P c e Iseñal c : precondición P c e I modifica el estado del monitor postcondición Iseñal c y retorno : precondicionar P c e 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 la variable de condición para conocer el número de hilos que esperan 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 : la precondición I modifica el estado del monitor; la postcondición P cseñal c precondición ( no vacío( c ) y P c ) o ( vacío( c ) e I ) modifica el estado del monitor postcondición I

(Para más información, véanse Howard ^{[ 4 ]} y Buhr et al. ^{[ 5 ]} ).

La afirmación P _c depende enteramente del programador; simplemente necesita ser coherente sobre lo que representa.

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 monitor SharedStack { private const capacity := 10 private int [capacity] A private int size := 0 invariant 0 <= size and size <= capacity private BlockingCondition theStackIsNotEmpty /* asociado con 0 < size and size <= capacity */ private BlockingCondition theStackIsNotFull /* asociado con 0 <= size and size < capacity */método público push( int valor) { Si size = capacity , entonces esperar theStackIsNotFull afirmar que 0 <= size y size < capacity A[tamaño] := valor; tamaño := tamaño + 1 afirmar que 0 < tamaño y tamaño <= capacidad señaliza que la pila no está vacía y devuelve } método público int pop() { Si size = 0, entonces esperar theStackIsNotEmpty afirmar que 0 < size y size <= capacity tamaño := tamaño - 1 ; afirmar 0 <= tamaño y tamaño < capacidad señal theStackIsNotFull y devolver A[tamaño] } }

Nótese que, en este ejemplo, la pila segura para subprocesos proporciona internamente un mutex, que, al igual que en el ejemplo anterior de productor/consumidor, es compartido por ambas variables de condición, las cuales verifican diferentes condiciones sobre los mismos datos concurrentes. La única diferencia radica en que el ejemplo de productor/consumidor asumía una cola regular no segura para subprocesos y utilizaba un mutex y variables de condición independientes, sin abstraer estos detalles del monitor, como ocurre aquí. En este ejemplo, cuando se llama a la operación "wait", esta debe recibir de alguna manera el mutex de la pila segura para subprocesos, por ejemplo, si la operación "wait" forma parte integral de la "clase monitor". Aparte de este tipo de funcionalidad abstracta, cuando se utiliza un monitor "en bruto", siempre deberá 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 no bloqueantes (también llamadas variables de condición de "estilo Mesa" o variables de condición de "señalización y continuación" ), la señalización no provoca que el hilo que la realiza pierda el control del monitor. En cambio, los hilos señalizados se mueven a la ecola. No hay necesidad de la scola.

Con variables de condición no bloqueantes, la operación de señal se suele denominar "notificar" ( notificación), terminología que seguiremos aquí. También es común proporcionar una operación de "notificar a todos" que mueve a la cola a todos los subprocesos que esperan una variable de condición e.

Aquí se explica el significado de las distintas operaciones. (Suponemos que cada operación se ejecuta de forma excluyente con respecto a las demás; por lo tanto, los hilos reiniciados no comienzan a ejecutarse hasta que la operación haya finalizado).

Ingrese al monitor: Introduzca el método si el monitor está bloqueado agregar este hilo a e Bloquear este hilo demás bloquear el monitor Salir del monitor: cronograma regresar del método espera c : agregar este hilo a c .q cronograma Bloquear este hilo notificar c : si hay un hilo esperando en c .q Seleccione y elimine un hilo t de c.q (Se denomina "hilo notificado") mover t a e notificar a todos c : mover todos los hilos que esperan en c .q a e cronograma : si hay un hilo en e Seleccione y elimine un hilo de e y reinícielo. De lo contrario, desbloquee el monitor.

Como una variación de este esquema, el hilo notificado puede ser movido a una cola llamada w, que tiene prioridad sobre e. Véanse Howard ^{[ 4 ]} y Buhr et al. ^{[ 5 ]} para más detalles.

Es posible asociar una aserción P _c con cada variable de condición c de tal manera que P _c sea segura al regresar de . Sin embargo, se debe asegurar que P _c se conserve desde el momento en que el hilo notificante cede la ocupación hasta que el hilo notificado es seleccionado para volver a entrar en el monitor. Entre estos momentos, podría haber actividad de otros ocupantes. Por lo tanto, es común que P _c sea simplemente verdadera .waitc

Por esta razón, normalmente es necesario encerrar cada operación de espera en un bucle como este.

mientras no ( P ) hacer esperar c

donde P es alguna condición más fuerte que P _c . Las operaciones y se tratan como "sugerencias" de que P puede ser verdadera para algún hilo en espera. Cada iteración de dicho bucle más allá de la primera representa una notificación perdida; por lo tanto, con monitores no bloqueantes, hay que tener cuidado de asegurar que no se pierdan demasiadas notificaciones.notifycnotify allc

Como ejemplo de "insinuación", consideremos una cuenta bancaria en la que un hilo de retiro esperará hasta que la cuenta tenga fondos suficientes antes de proceder.

clase de monitor Cuenta { int privado balance := 0 invariante balance >= 0 condición no bloqueante privada balanceMayBeBigEnoughmétodo público retirar( int cantidad) precondición cantidad >= 0 { mientras saldo < cantidad hacer esperar balanceMaybeBigEnough afirmar saldo >= cantidad saldo := saldo - cantidad } método público deposit( int cantidad) precondición cantidad >= 0 { saldo := saldo + cantidad notificar a todos balanceMayBeBigEnough } }

En este ejemplo, la condición que se espera depende de la cantidad a retirar, por lo que es imposible que un hilo que realiza el depósito sepa si ha cumplido dicha condición. En este caso, tiene sentido permitir que cada hilo en espera acceda al monitor (uno a la vez) para comprobar si su aserción es verdadera.

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 synchronized . Los bloques de código también pueden marcarse con synchronized . ^{[ 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 notify y notifyAll se aplican a esta cola. ^{[ 7 ]} Este enfoque se ha adoptado en otros lenguajes, por ejemplo C# .

Otro enfoque para la señalización es omitir la operación de señalización . Siempre que un hilo abandona el monitor (al regresar o esperar), las aserciones de todos los hilos en espera se evalúan hasta que se encuentra una que sea verdadera. En un sistema así, no se necesitan variables de condición, pero las aserciones deben codificarse explícitamente. El contrato para la espera es

esperar P : la precondición I modifica el estado del monitor, la postcondición P e I.