Monitorar (sincronização) - Monitor (synchronization)

Na programação simultânea (também conhecida como programação paralela), um monitor é uma construção de sincronização que permite que os encadeamentos tenham exclusão mútua e a capacidade de esperar (bloquear) que uma determinada condição se torne falsa. Os monitores também têm um mecanismo para sinalizar a outros threads que sua condição foi atendida. Um monitor consiste em um objeto mutex (bloqueio) e variáveis ​​de condição . Uma variável de condição é essencialmente um contêiner de threads que estão esperando por uma determinada condição. Os monitores fornecem um mecanismo para que os encadeamentos desistam temporariamente do acesso exclusivo a fim de esperar que alguma condição seja atendida, antes de recuperar o acesso exclusivo e retomar sua tarefa.

Outra definição de monitor é uma classe , objeto ou módulo thread-safe que envolve um mutex para permitir o acesso seguro a um método ou variável por mais de um thread . A característica definidora de um monitor é que seus métodos são executados com exclusão mútua : em cada ponto no tempo, no máximo um thread pode estar executando qualquer um de seus métodos . Ao usar uma ou mais variáveis ​​de condição, ele também pode fornecer a capacidade dos threads de esperar em uma determinada condição (usando, portanto, a definição acima de um "monitor"). No restante deste artigo, esse sentido de "monitor" será referido como um "objeto / classe / módulo thread-safe".

Os monitores foram inventados por Per Brinch Hansen e CAR Hoare , e foram implementados pela primeira vez na linguagem Concurrent Pascal de Brinch Hansen .

Exclusão mútua

Como um exemplo simples, considere um objeto thread-safe para realizar transações em uma conta bancária:

monitor class Account {
    private int balance := 0
    invariant balance >= 0

    public method boolean withdraw(int amount)
        precondition amount >= 0
    {
        if balance < amount {
            return false
        } else {
            balance := balance - amount
            return true
        }
    }

    public method deposit(int amount)
        precondition amount >= 0
    {
        balance := balance + amount
    }
}

Enquanto uma thread está executando um método de um objeto thread-safe, diz-se que ela ocupa o objeto, mantendo seu mutex (bloqueio) . Objetos thread-safe são implementados para garantir que, em cada ponto no tempo, no máximo um thread possa ocupar o objeto . O bloqueio, que é inicialmente desbloqueado, é bloqueado no início de cada método público e é desbloqueado a cada retorno de cada método público.

Ao chamar um dos métodos, um thread deve esperar até que nenhum outro thread esteja executando qualquer um dos métodos do objeto thread-safe antes de iniciar a execução de seu método. Observe que, sem essa exclusão mútua, no presente exemplo, dois threads podem fazer com que dinheiro seja perdido ou ganho sem motivo. Por exemplo, dois threads retirando 1000 da conta podem retornar true, enquanto fazem com que o saldo caia apenas 1000, como segue: primeiro, ambos os threads buscam o saldo atual, acham-no maior que 1000 e subtraem 1000 dele; então, ambos os threads armazenam o equilíbrio e o retorno.

O açúcar sintático "classe de monitor" no exemplo acima está implementando a seguinte representação básica do código, envolvendo a execução de cada função em mutexes:

class Account {
    private lock myLock

    private int balance := 0
    invariant balance >= 0

    public method boolean withdraw(int amount)
       precondition amount >= 0
    {
        myLock.acquire()
        try {
            if balance < amount {
                return false
            } else {
                balance := balance - amount
                return true
            }
        } finally {
            myLock.release()
        }
    }

    public method deposit(int amount)
       precondition amount >= 0
    {
        myLock.acquire()
        try {
            balance := balance + amount
        } finally {
            myLock.release()
        }
    }
}

Variáveis ​​de condição

Declaração do problema

Para muitas aplicações, a exclusão mútua não é suficiente. Os threads que tentam uma operação podem precisar esperar até que alguma condição P seja verdadeira. Um ciclo de espera ocupado

while not( P ) do skip

não funcionará, pois a exclusão mútua impedirá que qualquer outro thread entre no monitor para tornar a condição verdadeira. Outros "soluções" existir como tendo um circuito que desbloqueia o monitor, espera uma certa quantidade de tempo, bloqueia o monitor e controlos para a condição de P . Teoricamente, funciona e não entrará em conflito, mas surgem problemas. É difícil decidir uma quantidade apropriada de tempo de espera, muito pequeno e o encadeamento irá monopolizar a CPU, muito grande e aparentemente não responderá. O que é necessário é uma forma de sinalizar a thread quando a condição P é verdadeira (ou poderia ser verdadeira).

Estudo de caso: problema clássico limitado produtor / consumidor

Um problema clássico de simultaneidade é aquele do produtor / consumidor limitado , no qual há uma fila ou buffer de anel de tarefas com um tamanho máximo, com um ou mais threads sendo threads "produtores" que adicionam tarefas à fila, e um ou mais outros encadeamentos sendo encadeamentos "consumidores" que retiram tarefas da fila. A própria fila é considerada não segura para thread e pode estar vazia, cheia ou entre vazia e cheia. Sempre que a fila estiver cheia de tarefas, precisamos que os encadeamentos do produtor sejam bloqueados até que haja espaço para as tarefas de desenfileiramento dos encadeamentos do consumidor. Por outro lado, sempre que a fila está vazia, precisamos que os encadeamentos do consumidor sejam bloqueados até que mais tarefas estejam disponíveis devido aos encadeamentos do produtor que os adicionam.

Como a fila é um objeto simultâneo compartilhado entre os encadeamentos, os acessos a ela devem ser atômicos , pois a fila pode ser colocada em um estado inconsistente durante o curso do acesso à fila que nunca deve ser exposto entre os encadeamentos. Assim, qualquer código que acesse a fila constitui uma seção crítica que deve ser sincronizada por exclusão mútua. Se o código e as instruções do processador em seções críticas do código que acessam a fila puderem ser intercaladas por alternâncias arbitrárias de contexto entre threads no mesmo processador ou por threads em execução simultânea em vários processadores, haverá o risco de expor o estado inconsistente e causar condições de corrida .

Incorreto sem sincronização

Uma abordagem ingênua é projetar o código com espera ocupada e sem sincronização, tornando o código sujeito a condições de corrida:

global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.
        while (queue.isFull()) {} // Busy-wait until the queue is non-full.
        queue.enqueue(myTask); // Add the task to the queue.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        while (queue.isEmpty()) {} // Busy-wait until the queue is non-empty.
        myTask = queue.dequeue(); // Take a task off of the queue.
        doStuff(myTask); // Go off and do something with the task.
    }
}

Esse código tem um problema sério, pois os acessos à fila podem ser interrompidos e intercalados com os acessos de outros threads à fila. Os queue.enqueue e queue.dequeue métodos provavelmente terá instruções para atualizar variáveis de membro da fila, como seu tamanho, começando e terminando posições, atribuição e alocação de elementos de fila, etc. Além disso, o queue.isEmpty () e queue.isFull Os métodos () também leem esse estado compartilhado. Se os encadeamentos de produtor / consumidor puderem ser intercalados durante as chamadas para enfileirar / retirar da fila, o estado inconsistente da fila pode ser exposto, levando a condições de corrida. Além disso, se um consumidor esvaziar a fila entre a saída de outro consumidor da espera ocupada e a chamada de "desenfileirar", o segundo consumidor tentará desenfilar de uma fila vazia, levando a um erro. Da mesma forma, se um produtor deixa a fila cheia entre a saída de outro produtor da espera ocupada e a chamada de "enfileiramento", o segundo produtor tentará adicionar uma fila cheia, levando a um erro.

Espera de giro

Uma abordagem ingênua para alcançar a sincronização, como aludido acima, é usar " espera de rotação ", em que um mutex é usado para proteger as seções críticas do código e espera ocupada ainda é usado, com o bloqueio sendo adquirido e liberado em entre cada verificação de espera ocupada.

global RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock; // A mutex for the ring-buffer of tasks.

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isFull()) { // Busy-wait until the queue is non-full.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a consumer might take a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isFull()".
        }

        queue.enqueue(myTask); // Add the task to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial busy-wait check.
        while (queue.isEmpty()) { // Busy-wait until the queue is non-empty.
            queueLock.release();
            // Drop the lock temporarily to allow a chance for other threads
            // needing queueLock to run so that a producer might add a task.
            queueLock.acquire(); // Re-acquire the lock for the next call to "queue.isEmpty()".
        }
        myTask = queue.dequeue(); // Take a task off of the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.
        doStuff(myTask); // Go off and do something with the task.
    }
}

Este método garante que um estado inconsistente não ocorra, mas desperdiça recursos da CPU devido à espera ocupada desnecessária. Mesmo se a fila estiver vazia e os encadeamentos do produtor não tiverem nada a acrescentar por um longo tempo, os encadeamentos do consumidor estarão sempre ocupados esperando desnecessariamente. Da mesma forma, mesmo que os consumidores fiquem bloqueados por um longo tempo no processamento de suas tarefas atuais e a fila esteja cheia, os produtores estão sempre ocupados esperando. Este é um mecanismo de desperdício. O que é necessário é uma maneira de fazer com que os encadeamentos do produtor sejam bloqueados até que a fila não esteja cheia e uma maneira de fazer com que os encadeamentos do consumidor sejam bloqueados até que a fila não fique vazia.

(NB: Mutexes em si também podem ser spin-locks que envolvem ocupado-espera para obter o bloqueio, mas para resolver este problema de desperdício de recursos da CPU, assumimos que queueLock não é um spin-lock e usa corretamente um bloqueio bloquear a própria fila.)

Variáveis ​​de condição

A solução é usar variáveis ​​de condição . Conceitualmente, uma variável de condição é uma fila de threads, associada a um mutex, na qual uma thread pode esperar que alguma condição se torne verdadeira. Assim, cada variável de condição c está associada a uma asserção P _c . Enquanto um encadeamento está aguardando uma variável de condição, esse encadeamento não é considerado para ocupar o monitor e, portanto, outros encadeamentos podem entrar no monitor para alterar o estado do monitor. Na maioria dos tipos de monitores, esses outros threads podem sinalizar a variável de condição c para indicar que a asserção P _c é verdadeira no estado atual.

Portanto, existem três operações principais nas variáveis ​​de condição:

• wait c, m, onde cé uma variável de condição e mé um mutex (bloqueio) associado ao monitor. Essa operação é chamada por uma thread que precisa esperar até que a asserção P _c seja verdadeira antes de continuar. Enquanto a linha está esperando, ela não ocupa o monitor. A função, e contrato fundamental, da operação de "espera" é realizar as seguintes etapas:
  1. Atomicamente :

     1. libere o mutex m,
     2. mover este tópico da "em execução" para ca "fila de espera" (também conhecida como "fila de espera") de tópicos, e
     3. dormir este tópico. (O contexto é gerado de forma síncrona para outro encadeamento.)

  2. Uma vez que este tópico é subsequentemente notificado / sinalizado (veja abaixo) e retomado, então readquira automaticamente o mutex m.

  As etapas 1a e 1b podem ocorrer em qualquer ordem, com 1c geralmente ocorrendo depois delas. Enquanto a thread está em hibernação e na cfila de espera, o próximo contador de programa a ser executado está na etapa 2, no meio da função / sub-rotina de "espera" . Assim, o thread dorme e mais tarde acorda no meio da operação de "espera".

  A atomicidade das operações na etapa 1 é importante para evitar condições de corrida que seriam causadas por uma troca de thread preemptiva entre elas. Um modo de falha que poderia ocorrer se eles não fossem atômicos é um despertar perdido , no qual o thread poderia estar na cfila de espera e ter liberado o mutex, mas uma troca de thread preemptiva ocorreu antes de o thread entrar em espera, e outro thread chamada de operação sinalizar / notificar (veja abaixo) ao cmover o primeiro encadeamento de volta para fora da cfila de. Assim que o primeiro encadeamento em questão for alternado de volta, seu contador de programa estará na etapa 1c, e ele entrará em hibernação e não poderá ser acordado novamente, violando a invariante de que deveria estar na cfila de hibernação quando ele dormiu. Outras condições de corrida dependem da ordem das etapas 1a e 1b e dependem de onde ocorre uma troca de contexto.

• signal c, também conhecido como notify c, é chamado por um thread para indicar que a asserção P _c é verdadeira. Dependendo do tipo e implementação do monitor, ele move um ou mais threads da cfila de espera para a "fila pronta" ou outras filas para que seja executado. É geralmente considerado uma prática recomendada executar a operação "sinalizar" / "notificar" antes de liberar o mutex mque está associado c, mas desde que o código seja devidamente projetado para simultaneidade e dependendo da implementação do threading, muitas vezes também é aceitável libere o bloqueio antes de sinalizar. Dependendo da implementação do threading, a ordenação disso pode ter ramificações de prioridade de agendamento. (Alguns autores, em vez disso, defendem uma preferência por liberar o bloqueio antes da sinalização.) Uma implementação de threading deve documentar quaisquer restrições especiais nessa ordem.
• broadcast c, também conhecido como notifyAll c, é uma operação semelhante que ativa todos os threads na fila de espera de c. Isso esvazia a fila de espera. Geralmente, quando mais de uma condição de predicado está associada à mesma variável de condição, o aplicativo exigirá transmissão em vez de sinal, porque um encadeamento esperando pela condição errada pode ser ativado e imediatamente voltar a dormir sem despertar um encadeamento esperando por a condição correta que acabou de se tornar verdadeira. Caso contrário, se a condição do predicado for um para um com a variável de condição associada a ela, então o sinal pode ser mais eficiente do que a transmissão .

Como regra de design, várias variáveis ​​de condição podem ser associadas ao mesmo mutex, mas não vice-versa. (Esta é uma correspondência de um para muitos .) Isso ocorre porque o predicado P _c é o mesmo para todos os encadeamentos que usam o monitor e deve ser protegido com exclusão mútua de todos os outros encadeamentos que podem causar a alteração da condição ou que podem leia-o enquanto o encadeamento em questão faz com que ele seja alterado, mas pode haver encadeamentos diferentes que desejam esperar por uma condição diferente na mesma variável, exigindo que o mesmo mutex seja usado. No exemplo produtor-consumidor descrito acima , a fila deve ser protegida por um objeto mutex exclusivo m,. Os encadeamentos "produtores" vão querer esperar em um monitor usando bloqueio me uma variável de condição que bloqueia até que a fila não esteja cheia. Os encadeamentos do "consumidor" vão querer esperar em um monitor diferente usando o mesmo mutex, mas uma variável de condição diferente que bloqueia até que a fila não esteja vazia. (Normalmente) nunca faria sentido ter mutexes diferentes para a mesma variável de condição, mas este exemplo clássico mostra por que muitas vezes certamente faz sentido ter várias variáveis ​​de condição usando o mesmo mutex. Um mutex usado por uma ou mais variáveis ​​de condição (um ou mais monitores) também pode ser compartilhado com o código que não usa variáveis ​​de condição (e que simplesmente o adquire / libera sem qualquer operação de espera / sinal), se essas seções críticas não acontecerem para exigir a espera de uma determinada condição nos dados simultâneos. ${\ displaystyle c_ {full}}$m${\ displaystyle c_ {vazio}}$

Monitore o uso

O uso básico adequado de um monitor é:

acquire(m); // Acquire this monitor's lock.
while (!p) { // While the condition/predicate/assertion that we are waiting for is not true...
	wait(m, cv); // Wait on this monitor's lock and condition variable.
}
// ... Critical section of code goes here ...
signal(cv2); -- OR -- notifyAll(cv2); // cv2 might be the same as cv or different.
release(m); // Release this monitor's lock.

Para ser mais preciso, este é o mesmo pseudocódigo, mas com comentários mais detalhados para explicar melhor o que está acontecendo:

// ... (previous code)
// About to enter the monitor.
// Acquire the advisory mutex (lock) associated with the concurrent
// data that is shared between threads, 
// to ensure that no two threads can be preemptively interleaved or
// run simultaneously on different cores while executing in critical
// sections that read or write this same concurrent data. If another
// thread is holding this mutex, then this thread will be put to sleep
// (blocked) and placed on m's sleep queue.  (Mutex "m" shall not be
// a spin-lock.)
acquire(m);
// Now, we are holding the lock and can check the condition for the
// first time.

// The first time we execute the while loop condition after the above
// "acquire", we are asking, "Does the condition/predicate/assertion
// we are waiting for happen to already be true?"

while (!p()) 	// "p" is any expression (e.g. variable or 
		// function-call) that checks the condition and
		// evaluates to boolean.  This itself is a critical
		// section, so you *MUST* be holding the lock when
		// executing this "while" loop condition!
				
// If this is not the first time the "while" condition is being checked,
// then we are asking the question, "Now that another thread using this
// monitor has notified me and woken me up and I have been context-switched
// back to, did the condition/predicate/assertion we are waiting on stay
// true between the time that I was woken up and the time that I re-acquired
// the lock inside the "wait" call in the last iteration of this loop, or
// did some other thread cause the condition to become false again in the
// meantime thus making this a spurious wakeup?

{
	// If this is the first iteration of the loop, then the answer is
	// "no" -- the condition is not ready yet. Otherwise, the answer is:
	// the latter.  This was a spurious wakeup, some other thread occurred
	// first and caused the condition to become false again, and we must
	// wait again.

	wait(m, cv);
		// Temporarily prevent any other thread on any core from doing
		// operations on m or cv.
		// release(m) 		// Atomically release lock "m" so other
		//			// code using this concurrent data
		// 			// can operate, move this thread to cv's
		//			// wait-queue so that it will be notified
		//			// sometime when the condition becomes
		// 			// true, and sleep this thread. Re-enable
		//			// other threads and cores to do 
		//			// operations on m and cv.
		//
		// Context switch occurs on this core.
		//
		// At some future time, the condition we are waiting for becomes
		// true, and another thread using this monitor (m, cv) does either
		// a signal/notify that happens to wake this thread up, or a
		// notifyAll that wakes us up, meaning that we have been taken out
		// of cv's wait-queue.
		//
		// During this time, other threads may cause the condition to
		// become false again, or the condition may toggle one or more
		// times, or it may happen to stay true.
		//
		// This thread is switched back to on some core.
		//
		// acquire(m)		// Lock "m" is re-acquired.
		
	// End this loop iteration and re-check the "while" loop condition to make
	// sure the predicate is still true.
	
}

// The condition we are waiting for is true!
// We are still holding the lock, either from before entering the monitor or from
// the last execution of "wait".

// Critical section of code goes here, which has a precondition that our predicate
// must be true.
// This code might make cv's condition false, and/or make other condition variables'
// predicates true.

// Call signal/notify or notifyAll, depending on which condition variables'
// predicates (who share mutex m) have been made true or may have been made true,
// and the monitor semantic type being used.

for (cv_x in cvs_to_notify) {
	notify(cv_x); -- OR -- notifyAll(cv_x);
}
// One or more threads have been woken up but will block as soon as they try
// to acquire m.

// Release the mutex so that notified thread(s) and others can enter their critical
// sections.
release(m);

Resolvendo o problema limitado produtor / consumidor

Tendo introduzido o uso de variáveis ​​de condição, vamos usá-lo para revisitar e resolver o problema clássico produtor / consumidor limitado. A solução clássica é usar dois monitores, compreendendo duas variáveis ​​de condição que compartilham um bloqueio na fila:

global volatile RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock;  	// A mutex for the ring-buffer of tasks. (Not a spin-lock.)
global CV queueEmptyCV; 	// A condition variable for consumer threads waiting for the queue to 
				// become non-empty.
                        	// Its associated lock is "queueLock".
global CV queueFullCV; 		// A condition variable for producer threads waiting for the queue 
				// to become non-full. Its associated lock is also "queueLock".

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isFull()) { // Check if the queue is non-full.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto queueFullCV, and sleep this thread.
            wait(queueLock, queueFullCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        queue.enqueue(myTask); // Add the task to the queue.

        // Now the queue is guaranteed to be non-empty, so signal a consumer thread
        // or all consumer threads that might be blocked waiting for the queue to be non-empty:
        signal(queueEmptyCV); -- OR -- notifyAll(queueEmptyCV);
        
        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isEmpty()) { // Check if the queue is non-empty.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto queueEmptyCV, and sleep this thread.
            wait(queueLock, queueEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        // Critical section that requires the queue to be non-empty.
        // N.B.: We are holding queueLock.
        myTask = queue.dequeue(); // Take a task off of the queue.
        // Now the queue is guaranteed to be non-full, so signal a producer thread
        // or all producer threads that might be blocked waiting for the queue to be non-full:
        signal(queueFullCV); -- OR -- notifyAll(queueFullCV);

        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.

        doStuff(myTask); // Go off and do something with the task.
    }
}

Isso garante a simultaneidade entre os encadeamentos produtor e consumidor que compartilham a fila de tarefas e bloqueia os encadeamentos que não têm nada a fazer em vez de espera ocupada, conforme mostrado na abordagem mencionada usando spin-locks.

Uma variante dessa solução poderia usar uma única variável de condição para produtores e consumidores, talvez denominada "queueFullOrEmptyCV" ou "queueSizeChangedCV". Nesse caso, mais de uma condição está associada à variável de condição, de forma que a variável de condição represente uma condição mais fraca do que as condições que estão sendo verificadas por threads individuais. A variável de condição representa threads que estão esperando que a fila não esteja cheia e aqueles que estão esperando que ela não fique vazia. No entanto, fazer isso exigiria o uso de notificar tudo em todos os encadeamentos que usam a variável de condição e não pode usar um sinal regular . Isso ocorre porque o sinal regular pode despertar um encadeamento do tipo errado cuja condição ainda não foi atendida, e esse encadeamento voltaria a hibernar sem que um encadeamento do tipo correto fosse sinalizado. Por exemplo, um produtor pode deixar a fila cheia e acordar outro produtor em vez de um consumidor, e o produtor acordado volta a dormir. No caso complementar, um consumidor poderia esvaziar a fila e acordar outro consumidor em vez de um produtor, e o consumidor voltaria a dormir. O uso de notificarAll garante que algum encadeamento do tipo correto continuará conforme o esperado pela declaração do problema.

Aqui está a variante usando apenas uma variável de condição e NoticeAll:

global volatile RingBuffer queue; // A thread-unsafe ring-buffer of tasks.
global Lock queueLock; // A mutex for the ring-buffer of tasks.  (Not a spin-lock.)
global CV queueFullOrEmptyCV; // A single condition variable for when the queue is not ready for any thread
                              // -- i.e., for producer threads waiting for the queue to become non-full 
                              // and consumer threads waiting for the queue to become non-empty.
                              // Its associated lock is "queueLock".
                              // Not safe to use regular "signal" because it is associated with
                              // multiple predicate conditions (assertions).

// Method representing each producer thread's behavior:
public method producer() {
    while (true) {
        task myTask = ...; // Producer makes some new task to be added.

        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isFull()) { // Check if the queue is non-full.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto the CV, and sleep this thread.
            wait(queueLock, queueFullOrEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        queue.enqueue(myTask); // Add the task to the queue.

        // Now the queue is guaranteed to be non-empty, so signal all blocked threads
        // so that a consumer thread will take a task:
        notifyAll(queueFullOrEmptyCV); // Do not use "signal" (as it might wake up another producer instead).
        
        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to add the next task.
    }
}

// Method representing each consumer thread's behavior:
public method consumer() {
    while (true) {
        queueLock.acquire(); // Acquire lock for initial predicate check.
        while (queue.isEmpty()) { // Check if the queue is non-empty.
            // Make the threading system atomically release queueLock,
            // enqueue this thread onto the CV, and sleep this thread.
            wait(queueLock, queueFullOrEmptyCV);
            // Then, "wait" automatically re-acquires "queueLock" for re-checking
            // the predicate condition.
        }
        // Critical section that requires the queue to be non-full.
        // N.B.: We are holding queueLock.
        myTask = queue.dequeue(); // Take a task off of the queue.

        // Now the queue is guaranteed to be non-full, so signal all blocked threads
        // so that a producer thread will take a task:
        notifyAll(queueFullOrEmptyCV); // Do not use "signal" (as it might wake up another consumer instead).

        // End of critical sections related to the queue.
        queueLock.release(); // Drop the queue lock until we need it again to take off the next task.

        doStuff(myTask); // Go off and do something with the task.
    }
}

Primitivas de sincronização

A implementação de mutexes e variáveis ​​de condição requer algum tipo de primitiva de sincronização fornecida pelo suporte de hardware que fornece atomicidade . Bloqueios e variáveis ​​de condição são abstrações de nível superior sobre essas primitivas de sincronização. Em um uniprocessador, desabilitar e habilitar interrupções é uma maneira de implementar monitores, evitando trocas de contexto durante as seções críticas dos bloqueios e variáveis ​​de condição, mas isso não é suficiente em um multiprocessador. Em um multiprocessador, geralmente são usadas instruções atômicas especiais de leitura-modificação-gravação na memória, como teste e ajuste , comparação e troca , etc., dependendo do que o ISA fornece. Geralmente, é necessário adiar o bloqueio de rotação para o próprio estado de bloqueio interno, mas esse bloqueio é muito breve. Dependendo da implementação, as instruções atômicas de leitura-modificação-gravação podem bloquear o barramento de acessos de outros núcleos e / ou impedir o reordenamento de instruções na CPU. Aqui está um exemplo de implementação de pseudocódigo de partes de um sistema de threading e mutexes e variáveis ​​de condição no estilo Mesa, usando test-and-set e uma política de ordem de chegada. Isso encobre a maior parte de como um sistema de threading funciona, mas mostra as partes relevantes para mutexes e variáveis ​​de condição:

Exemplo de implementação de monitor Mesa com Test-and-Set

// Basic parts of threading system:
// Assume "ThreadQueue" supports random access.
public volatile ThreadQueue readyQueue; // Thread-unsafe queue of ready threads.  Elements are (Thread*).
public volatile global Thread* currentThread; // Assume this variable is per-core.  (Others are shared.)

// Implements a spin-lock on just the synchronized state of the threading system itself.
// This is used with test-and-set as the synchronization primitive.
public volatile global bool threadingSystemBusy = false;

// Context-switch interrupt service routine (ISR):
// On the current CPU core, preemptively switch to another thread.
public method contextSwitchISR() {
    if (testAndSet(threadingSystemBusy)) {
        return; // Can't switch context right now.
    }

    // Ensure this interrupt can't happen again which would foul up the context switch:
    systemCall_disableInterrupts();

    // Get all of the registers of the currently-running process.
    // For Program Counter (PC), we will need the instruction location of
    // the "resume" label below.  Getting the register values is platform-dependent and may involve
    // reading the current stack frame, JMP/CALL instructions, etc.  (The details are beyond this scope.)
    currentThread->registers = getAllRegisters(); // Store the registers in the "currentThread" object in memory.
    currentThread->registers.PC = resume; // Set the next PC to the "resume" label below in this method.

    readyQueue.enqueue(currentThread); // Put this thread back onto the ready queue for later execution.
    
    Thread* otherThread = readyQueue.dequeue(); // Remove and get the next thread to run from the ready queue.
    
    currentThread = otherThread; // Replace the global current-thread pointer value so it is ready for the next thread.

    // Restore the registers from currentThread/otherThread, including a jump to the stored PC of the other thread
    // (at "resume" below).  Again, the details of how this is done are beyond this scope.
    restoreRegisters(otherThread.registers);

    // *** Now running "otherThread" (which is now "currentThread")!  The original thread is now "sleeping". ***

    resume: // This is where another contextSwitch() call needs to set PC to when switching context back here.

    // Return to where otherThread left off.

    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
}

// Thread sleep method:
// On current CPU core, a synchronous context switch to another thread without putting
// the current thread on the ready queue.
// Must be holding "threadingSystemBusy" and disabled interrupts so that this method
// doesn't get interrupted by the thread-switching timer which would call contextSwitchISR().
// After returning from this method, must clear "threadingSystemBusy".
public method threadSleep() {
    // Get all of the registers of the currently-running process.
    // For Program Counter (PC), we will need the instruction location of
    // the "resume" label below.  Getting the register values is platform-dependent and may involve
    // reading the current stack frame, JMP/CALL instructions, etc.  (The details are beyond this scope.)
    currentThread->registers = getAllRegisters(); // Store the registers in the "currentThread" object in memory.
    currentThread->registers.PC = resume; // Set the next PC to the "resume" label below in this method.

    // Unlike contextSwitchISR(), we will not place currentThread back into readyQueue.
    // Instead, it has already been placed onto a mutex's or condition variable's queue.
    
    Thread* otherThread = readyQueue.dequeue(); // Remove and get the next thread to run from the ready queue.
    
    currentThread = otherThread; // Replace the global current-thread pointer value so it is ready for the next thread.

    // Restore the registers from currentThread/otherThread, including a jump to the stored PC of the other thread
    // (at "resume" below).  Again, the details of how this is done are beyond this scope.
    restoreRegisters(otherThread.registers);

    // *** Now running "otherThread" (which is now "currentThread")!  The original thread is now "sleeping". ***

    resume: // This is where another contextSwitch() call needs to set PC to when switching context back here.

    // Return to where otherThread left off.
}

public method wait(Mutex m, ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
 
    assert m.held; // (Specifically, this thread must be the one holding it.)
    
    m.release();
    c.waitingThreads.enqueue(currentThread);
    
    threadSleep();
    
    // Thread sleeps ... Thread gets woken up from a signal/broadcast.
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // Context switches may now occur here, making the client caller's predicate false.
    
    m.acquire();
}

public method signal(ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
    
    if (!c.waitingThreads.isEmpty()) {
        wokenThread = c.waitingThreads.dequeue();
        readyQueue.enqueue(wokenThread);
    }
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // The woken thread is not given any priority.
}

public method broadcast(ConditionVariable c) {
    // Internal spin-lock while other threads on any core are accessing this object's
    // "held" and "threadQueue", or "readyQueue".
    while (testAndSet(threadingSystemBusy)) {}
    // N.B.: "threadingSystemBusy" is now true.
    
    // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
    // the thread-switching timer on this core which would call contextSwitchISR().
    // Done outside threadSleep() for more efficiency so that this thread will be sleeped
    // right after going on the condition-variable queue.
    systemCall_disableInterrupts();
    
    while (!c.waitingThreads.isEmpty()) {
        wokenThread = c.waitingThreads.dequeue();
        readyQueue.enqueue(wokenThread);
    }
    
    threadingSystemBusy = false; // Must be an atomic assignment.
    systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    
    // Mesa style:
    // The woken threads are not given any priority.
}

class Mutex {
    protected volatile bool held = false;
    private volatile ThreadQueue blockingThreads; // Thread-unsafe queue of blocked threads.  Elements are (Thread*).
    
    public method acquire() {
        // Internal spin-lock while other threads on any core are accessing this object's
        // "held" and "threadQueue", or "readyQueue".
        while (testAndSet(threadingSystemBusy)) {}
        // N.B.: "threadingSystemBusy" is now true.
        
        // System call to disable interrupts on this core so that threadSleep() doesn't get interrupted by
        // the thread-switching timer on this core which would call contextSwitchISR().
        // Done outside threadSleep() for more efficiency so that this thread will be sleeped
        // right after going on the lock queue.
        systemCall_disableInterrupts();

        assert !blockingThreads.contains(currentThread);

        if (held) {
            // Put "currentThread" on this lock's queue so that it will be
            // considered "sleeping" on this lock.
            // Note that "currentThread" still needs to be handled by threadSleep().
            readyQueue.remove(currentThread);
            blockingThreads.enqueue(currentThread);
            threadSleep();
            
            // Now we are woken up, which must be because "held" became false.
            assert !held;
            assert !blockingThreads.contains(currentThread);
        }
        
        held = true;
        
        threadingSystemBusy = false; // Must be an atomic assignment.
        systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    }        
        
    public method release() {
        // Internal spin-lock while other threads on any core are accessing this object's
        // "held" and "threadQueue", or "readyQueue".
        while (testAndSet(threadingSystemBusy)) {}
        // N.B.: "threadingSystemBusy" is now true.
        
        // System call to disable interrupts on this core for efficiency.
        systemCall_disableInterrupts();
        
        assert held; // (Release should only be performed while the lock is held.)

        held = false;
        
        if (!blockingThreads.isEmpty()) {
            Thread* unblockedThread = blockingThreads.dequeue();
            readyQueue.enqueue(unblockedThread);
        }
        
        threadingSystemBusy = false; // Must be an atomic assignment.
        systemCall_enableInterrupts(); // Turn pre-emptive switching back on on this core.
    }
}

struct ConditionVariable {
    volatile ThreadQueue waitingThreads;
}

Semáforo

Como exemplo, considere uma classe thread-safe que implementa um semáforo . Existem métodos para incrementar (V) e decrementar (P) um inteiro privado s. No entanto, o número inteiro nunca deve ser diminuído abaixo de 0; portanto, uma thread que tenta decrementar deve esperar até que o inteiro seja positivo. Usamos uma variável de condição sIsPositivecom uma asserção associada de . ${\ displaystyle P _ {\ mathtt {sIsPositive}} = (s> 0)}$

monitor class Semaphore
{
    private int s := 0
    invariant s >= 0
    private Condition sIsPositive /* associated with s > 0 */

    public method P()
    {
        while s = 0:
            wait sIsPositive
        assert s > 0
        s := s - 1
    }

    public method V()
    {
        s := s + 1
        assert s > 0
        signal sIsPositive
    }
}

Implementado mostrando toda a sincronização (removendo a suposição de uma classe thread-safe e mostrando o mutex):

class Semaphore
{
    private volatile int s := 0
    invariant s >= 0
    private ConditionVariable sIsPositive /* associated with s > 0 */
    private Mutex myLock /* Lock on "s" */

    public method P()
    {
        myLock.acquire()
        while s = 0:
            wait(myLock, sIsPositive)
        assert s > 0
        s := s - 1
        myLock.release()
    }

    public method V()
    {
        myLock.acquire()
        s := s + 1
        assert s > 0
        signal sIsPositive
        myLock.release()
    }
}

Monitor implementado usando semáforos

Por outro lado, bloqueios e variáveis ​​de condição também podem ser derivados de semáforos, tornando os monitores e semáforos redutíveis uns aos outros:

A implementação fornecida aqui está incorreta. Se uma thread chamar wait () após broadcast () ter sido chamada, uma thread original pode ficar paralisada indefinidamente, uma vez que broadcast () incrementa o semáforo apenas o suficiente para threads já esperando.

public method wait(Mutex m, ConditionVariable c) {
    assert m.held;

    c.internalMutex.acquire();
    
    c.numWaiters++;
    m.release(); // Can go before/after the neighboring lines.
    c.internalMutex.release();

    // Another thread could signal here, but that's OK because of how
    // semaphores count.  If c.sem's number becomes 1, we'll have no
    // waiting time.
    c.sem.Proberen(); // Block on the CV.
    // Woken
    m.acquire(); // Re-acquire the mutex.
}

public method signal(ConditionVariable c) {
    c.internalMutex.acquire();
    if (c.numWaiters > 0) {
        c.numWaiters--;
        c.sem.Verhogen(); // (Doesn't need to be protected by c.internalMutex.)
    }
    c.internalMutex.release();
}

public method broadcast(ConditionVariable c) {
    c.internalMutex.acquire();
    while (c.numWaiters > 0) {
        c.numWaiters--;
        c.sem.Verhogen(); // (Doesn't need to be protected by c.internalMutex.)
    }
    c.internalMutex.release();
}

class Mutex {
    protected boolean held = false; // For assertions only, to make sure sem's number never goes > 1.
    protected Semaphore sem = Semaphore(1); // The number shall always be at most 1.
                                          // Not held <--> 1; held <--> 0.

    public method acquire() {
        sem.Proberen();
        assert !held;
        held = true;
    }
    
    public method release() {
        assert held; // Make sure we never Verhogen sem above 1.  That would be bad.
        held = false;
        sem.Verhogen();
    }
}

class ConditionVariable {
    protected int numWaiters = 0; // Roughly tracks the number of waiters blocked in sem.
                                // (The semaphore's internal state is necessarily private.)
    protected Semaphore sem = Semaphore(0); // Provides the wait queue.
    protected Mutex internalMutex; // (Really another Semaphore.  Protects "numWaiters".)
}

Quando um sinal acontece em uma variável de condição que pelo menos um outro encadeamento está esperando, há pelo menos dois encadeamentos que podem ocupar o monitor: o encadeamento que sinaliza e qualquer um dos encadeamentos que está esperando. Para que no máximo um thread ocupe o monitor de cada vez, uma escolha deve ser feita. Existem duas escolas de pensamento sobre a melhor forma de resolver essa escolha. Isso leva a dois tipos de variáveis ​​de condição que serão examinadas a seguir:

• As variáveis ​​de condição de bloqueio dão prioridade a uma thread sinalizada.
• Variáveis ​​de condição não bloqueadoras dão prioridade ao thread de sinalização.

Variáveis ​​de condição de bloqueio

As propostas originais de CAR Hoare e Per Brinch Hansen eram para variáveis ​​de condição de bloqueio . Com uma variável de condição de bloqueio, o encadeamento de sinalização deve esperar fora do monitor (pelo menos) até que o encadeamento sinalizado libere a ocupação do monitor retornando ou aguardando novamente em uma variável de condição. Os monitores que usam variáveis ​​de condição de bloqueio são freqüentemente chamados de monitores do estilo Hoare ou monitores de espera de sinal e urgência .

Um monitor do estilo Hoare com duas variáveis ​​de condição ae b. Depois de Buhr et al.

Assumimos que há duas filas de threads associadas a cada objeto de monitor

• e é a fila de entrada
• s é uma fila de threads que foram sinalizados.

Além disso, assumimos que para cada variável de condição c , há uma fila

• c.q, que é uma fila para threads esperando na variável de condição c

Todas as filas são normalmente garantidas como justas e, em algumas implementações, podem ser garantidas as primeiras a entrar , primeiro a sair .

A implementação de cada operação é a seguinte. (Presumimos que cada operação é executada em exclusão mútua com as outras; portanto, os threads reiniciados não começam a ser executados até que a operação seja concluída.)

enter the monitor:
    enter the method
    if the monitor is locked
        add this thread to e
        block this thread
    else
        lock the monitor

leave the monitor:
    schedule
    return from the method

wait c:
    add this thread to c.q
    schedule
    block this thread

signal c:
    if there is a thread waiting on c.q
        select and remove one such thread t from c.q
        (t is called "the signaled thread")
        add this thread to s
        restart t
        (so t will occupy the monitor next)
        block this thread

schedule:
    if there is a thread on s
        select and remove one thread from s and restart it
        (this thread will occupy the monitor next)
    else if there is a thread on e
        select and remove one thread from e and restart it
        (this thread will occupy the monitor next)
    else
        unlock the monitor
        (the monitor will become unoccupied)

A schedulerotina seleciona o próximo encadeamento para ocupar o monitor ou, na ausência de qualquer encadeamento candidato, desbloqueia o monitor.

A disciplina de sinalização resultante é conhecida como "sinal e espera urgente", pois o sinalizador deve esperar, mas tem prioridade sobre os threads na fila de entrada. Uma alternativa é "sinalizar e esperar", em que não há sfila e o sinalizador espera na efila.

Algumas implementações fornecem uma operação de sinal e retorno que combina sinalização com retorno de um procedimento.

signal c and return:
    if there is a thread waiting on c.q
        select and remove one such thread t from c.q
        (t is called "the signaled thread")
        restart t
        (so t will occupy the monitor next)
    else
        schedule
    return from the method

Em ambos os casos ("sinalizar e esperar urgente" ou "sinalizar e esperar"), quando uma variável de condição é sinalizada e há pelo menos um segmento esperando pela variável de condição, o segmento de sinalização transfere a ocupação para o segmento sinalizado perfeitamente, então que nenhum outro segmento pode ganhar ocupação no meio. Se P _c for verdadeiro no início de cada operação de sinal c , será verdadeiro no final de cada operação de espera c . Isso é resumido pelos seguintes contratos . Nesses contratos, I é o invariante do monitor .

enter the monitor:
    postcondition I

leave the monitor:
    precondition I

wait c:
    precondition I
    modifies the state of the monitor
    postcondition Pc and I

signal c:
    precondition Pc and I
    modifies the state of the monitor
    postcondition I

signal c and return:
    precondition Pc and I

Nestes contratos, pressupõe-se que I e P _c não dependem do conteúdo ou da duração das filas.

(Quando a variável de condição pode ser consultada quanto ao número de threads esperando em sua fila, contratos mais sofisticados podem ser fornecidos. Por exemplo, um par útil de contratos, permitindo que a ocupação seja passada sem estabelecer o invariante, é:

wait c:
    precondition I
    modifies the state of the monitor
    postcondition Pc

signal c
    precondition (not empty(c) and Pc) or (empty(c) and I)
    modifies the state of the monitor
    postcondition I

(Veja Howard e Buhr et al. Para mais.)

É importante notar aqui que a afirmação P _c depende inteiramente do programador; ele ou ela simplesmente precisa ser consistente sobre o que é.

Concluímos esta seção com um exemplo de classe thread-safe usando um monitor de bloqueio que implementa uma pilha limitada e thread-safe .

monitor class SharedStack {
    private const capacity := 10
    private int[capacity] A
    private int size := 0
    invariant 0 <= size and size <= capacity
    private BlockingCondition theStackIsNotEmpty /* associated with 0 < size and size <= capacity */
    private BlockingCondition theStackIsNotFull /* associated with 0 <= size and size < capacity */

    public method push(int value)
    {
        if size = capacity then wait theStackIsNotFull
        assert 0 <= size and size < capacity
        A[size] := value ; size := size + 1
        assert 0 < size and size <= capacity
        signal theStackIsNotEmpty and return
    }

    public method int pop()
    {
        if size = 0 then wait theStackIsNotEmpty
        assert 0 < size and size <= capacity
        size := size - 1 ;
        assert 0 <= size and size < capacity
        signal theStackIsNotFull and return A[size]
    }
}

Observe que, neste exemplo, a pilha thread-safe está fornecendo internamente um mutex, que, como no exemplo anterior do produtor / consumidor, é compartilhado por ambas as variáveis ​​de condição, que estão verificando diferentes condições nos mesmos dados simultâneos. A única diferença é que o exemplo do produtor / consumidor assumiu uma fila regular não segura para thread e estava usando um mutex independente e variáveis ​​de condição, sem esses detalhes do monitor abstraídos como é o caso aqui. Neste exemplo, quando a operação "wait" é chamada, ela deve de alguma forma ser fornecida com o mutex da pilha thread-safe, como se a operação "wait" fosse uma parte integrada da "classe monitor". Além desse tipo de funcionalidade abstraída, quando um monitor "bruto" é usado, ele sempre terá que incluir um mutex e uma variável de condição, com um mutex exclusivo para cada variável de condição.

Variáveis ​​de condição não bloqueadora

Com variáveis ​​de condição não bloqueadoras (também chamadas de variáveis ​​de condição "estilo Mesa" ou variáveis ​​de condição "sinalizar e continuar" ), a sinalização não faz com que o segmento de sinalização perca a ocupação do monitor. Em vez disso, os threads sinalizados são movidos para a efila. Não há necessidade de sfila.

Um monitor estilo Mesa com duas variáveis ​​de condição aeb

Com variáveis ​​de condição não bloqueadoras, a operação do sinal é freqüentemente chamada de notificação - uma terminologia que seguiremos aqui. Também é comum fornecer uma operação de notificação de todas as que move todos os threads que aguardam uma variável de condição para a efila.

O significado de várias operações é fornecido aqui. (Presumimos que cada operação é executada em exclusão mútua com as outras; portanto, os threads reiniciados não começam a ser executados até que a operação seja concluída.)

enter the monitor:
    enter the method
    if the monitor is locked
        add this thread to e
        block this thread
    else
        lock the monitor

leave the monitor:
    schedule
    return from the method

wait c:
    add this thread to c.q
    schedule
    block this thread

notify c:
    if there is a thread waiting on c.q
        select and remove one thread t from c.q
        (t is called "the notified thread")
        move t to e

notify all c:
    move all threads waiting on c.q to e

schedule :
    if there is a thread on e
        select and remove one thread from e and restart it
    else
        unlock the monitor

Como uma variação desse esquema, o thread notificado pode ser movido para uma fila chamada w, que tem prioridade sobre e. Ver Howard e Buhr et al. para uma discussão mais aprofundada.

É possível associar uma asserção P _c a cada variável de condição c, de modo que P _c seja verdade ao retornar de . No entanto, deve-se assegurar que P _c seja preservado a partir do momento em que o thread de notificação desiste de ocupação até que o thread notificado seja selecionado para entrar novamente no monitor. Entre esses horários, pode haver atividade de outros ocupantes. Portanto, é comum que P _c seja simplesmente verdadeiro . wait c

Por esse motivo, geralmente é necessário encerrar cada operação de espera em um loop como este

while not( P ) do
    wait c

onde P é alguma condição mais forte do que P _c . As operações e são tratadas como "dicas" de que P pode ser verdadeiro para algum segmento em espera. Cada iteração de tal loop após a primeira representa uma notificação perdida; portanto, com monitores não bloqueadores, deve-se ter cuidado para garantir que muitas notificações não sejam perdidas. notify cnotify all c

Como um exemplo de "sugestão", considere uma conta bancária na qual uma linha de retirada esperará até que a conta tenha fundos suficientes antes de prosseguir

monitor class Account {
    private int balance := 0
    invariant balance >= 0
    private NonblockingCondition balanceMayBeBigEnough

    public method withdraw(int amount)
        precondition amount >= 0
    {
        while balance < amount do wait balanceMayBeBigEnough
        assert balance >= amount
        balance := balance - amount
    }

    public method deposit(int amount)
        precondition amount >= 0
    {
        balance := balance + amount
        notify all balanceMayBeBigEnough
    }
}

Neste exemplo, a condição sendo esperada é uma função da quantia a ser sacada, portanto, é impossível para um thread de depósito saber que tornou tal condição verdadeira. Nesse caso, faz sentido permitir que cada thread em espera no monitor (um de cada vez) verifique se sua afirmação é verdadeira.

Monitores de variável de condição implícita

Um monitor estilo Java

Na linguagem Java , cada objeto pode ser usado como um monitor. Os métodos que requerem exclusão mútua devem ser marcados explicitamente com a palavra - chave synchronized . Os blocos de código também podem ser marcados como sincronizados .

Em vez de ter variáveis ​​de condição explícitas, cada monitor (ou seja, objeto) é equipado com uma única fila de espera além de sua fila de entrada. Todos espera é feito neste única fila de espera e todos notificar e notifyAll operações aplicam-se a essa fila. Essa abordagem foi adotada em outras linguagens, por exemplo C # .

Sinalização implícita

Outra abordagem para a sinalização é omitir a operação do sinal . Sempre que um encadeamento sai do monitor (retornando ou esperando), as asserções de todos os encadeamentos em espera são avaliadas até que uma seja considerada verdadeira. Nesse sistema, as variáveis ​​de condição não são necessárias, mas as asserções devem ser codificadas explicitamente. O contrato de espera é

wait P:
    precondition I
    modifies the state of the monitor
    postcondition P and I

História

Brinch Hansen e Hoare desenvolveram o conceito de monitor no início dos anos 1970, com base em ideias anteriores próprias e de Edsger Dijkstra . Brinch Hansen publicou a primeira notação de monitor, adotando o conceito de classe do Simula 67 , e inventou um mecanismo de enfileiramento. Hoare refinou as regras de retomada do processo. Brinch Hansen criou a primeira implementação de monitores, em Concurrent Pascal . Hoare demonstrou sua equivalência aos semáforos .

Monitores (e Pascal simultâneo) logo foram usados ​​para estruturar a sincronização de processos no sistema operacional Solo .

As linguagens de programação que têm monitores compatíveis incluem:

• Ada desde Ada 95 (como objetos protegidos)
• C # (e outras linguagens que usam o .NET Framework )
• Euclides simultâneos
• Pascal simultâneo
• D
• Delphi (Delphi 2009 e superior, via TObject.Monitor)
• Java (por meio dos métodos de espera e notificação)
• Vai
• Mesa
• Modula-3
• Python (via objeto threading.Condition )
• Rubi
• Squeak Smalltalk
• Turing , Turing + e Turing Orientado a Objetos
• µC ++
• Visual Prolog

Várias bibliotecas foram escritas para permitir que monitores sejam construídos em linguagens que não os suportam nativamente. Quando são utilizadas chamadas de biblioteca, cabe ao programador marcar explicitamente o início e o fim do código executado com exclusão mútua. Pthreads é uma dessas bibliotecas.

Veja também

• Exclusão mútua
• Comunicação de processos sequenciais - um desenvolvimento posterior de monitores por CAR Hoare
• Semáforo (programação)

Notas

Leitura adicional

• Monitores: um conceito de estruturação de sistema operacional, CAR Hoare - Communications of the ACM , v.17 n.10, p. 549-557, outubro de 1974 [1]
• Classificação de monitor PA Buhr, M. Fortier, MH Coffin - ACM Computing Surveys , 1995 [2]

links externos

• Monitores Java (explicação lúcida)
• " Monitores: Um Conceito de Estruturação de Sistema Operacional " por CAR Hoare
• " Sinalização em monitores ", de John H. Howard (cientista da computação)
• " Proving Monitors ", de John H. Howard (cientista da computação)
• " Experiência com Processos e Monitores em Mesa " por Butler W. Lampson e David D. Redell
• pthread_cond_wait - descrição das Especificações da Base do Grupo Aberto, Edição 6, IEEE Std 1003.1
• " Block on a Condition Variable ", de Dave Marshall (cientista da computação)
• " Strategies for Implementing POSIX Condition Variables on Win32 ", de Douglas C. Schmidt e Irfan Pyarali
• Rotinas de variável de condição da Apache Portable Runtime Library
• descrição da condição wx
• Referência de variáveis ​​de condição de reforço
• Referência de classe de condição ZThread
• Wefts :: Referência de classe de condição
• Referência de modelo de classe ACE_Condition
• Referência de classe QWaitCondition
• Referência de classe condicional C ++ comum
• em :: Referência de classe ConditionalMutex
• threads :: shared - extensão Perl para compartilhar estruturas de dados entre threads
• http://msdn.microsoft.com/en-us/library/ms682052(VS.85).aspx
• Monitores em Visual Prolog .