Monitor (sincronizzazione) - Monitor (synchronization)

Nella programmazione concorrente (nota anche come programmazione parallela), un monitor è un costrutto di sincronizzazione che consente ai thread di avere sia l'esclusione reciproca sia la capacità di attendere (bloccare) che una determinata condizione diventi falsa. I monitor hanno anche un meccanismo per segnalare ad altri thread che la loro condizione è stata soddisfatta. Un monitor è costituito da un oggetto mutex (lock) e da variabili di condizione . Una variabile di condizione è essenzialmente un contenitore di thread in attesa di una determinata condizione. I monitor forniscono un meccanismo per consentire ai thread di rinunciare temporaneamente all'accesso esclusivo per attendere che venga soddisfatta una condizione, prima di riottenere l'accesso esclusivo e riprendere il proprio compito.

Un'altra definizione di monitor è una classe , un oggetto o un modulo thread-safe che avvolge un mutex per consentire in modo sicuro l'accesso a un metodo o variabile da più di un thread . La caratteristica distintiva di un monitor è che i suoi metodi vengono eseguiti con mutua esclusione : in ogni momento, al massimo un thread può eseguire uno dei suoi metodi . Utilizzando una o più variabili di condizione può anche fornire la possibilità per i thread di attendere una determinata condizione (utilizzando quindi la definizione precedente di "monitor"). Per il resto di questo articolo, questo senso di "monitor" verrà indicato come "oggetto/classe/modulo thread-safe".

I monitor sono stati inventati da Per Brinch Hansen e CAR Hoare e sono stati implementati per la prima volta nel linguaggio Concurrent Pascal di Brinch Hansen .

Esclusione reciproca

Come semplice esempio, si consideri un oggetto thread-safe per l'esecuzione di transazioni su un conto bancario: 

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
    }
}

Mentre un thread esegue un metodo di un oggetto thread-safe, si dice che occupi l'oggetto, tenendo premuto il suo mutex (lock) . Gli oggetti thread-safe sono implementati per imporre che in ogni momento, al massimo un thread possa occupare l'oggetto . Il blocco, che è inizialmente sbloccato, è bloccato all'inizio di ogni metodo pubblico e viene sbloccato a ogni ritorno da ogni metodo pubblico.

Dopo aver chiamato uno dei metodi, un thread deve attendere che nessun altro thread esegua uno dei metodi dell'oggetto thread-safe prima di avviare l'esecuzione del suo metodo. Si noti che senza questa mutua esclusione, nel presente esempio, due thread potrebbero causare la perdita o il guadagno di denaro senza motivo. Ad esempio, due thread che prelevano 1000 dal conto potrebbero entrambi restituire vero, mentre fanno diminuire il saldo solo di 1000, come segue: in primo luogo, entrambi i thread recuperano il saldo corrente, lo trovano maggiore di 1000 e ne sottraggono 1000; quindi, entrambi i thread memorizzano il saldo e restituiscono.

La "classe monitor" dello zucchero sintattico nell'esempio sopra sta implementando la seguente rappresentazione di base del codice, avvolgendo l'esecuzione di ogni funzione in mutex: 

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()
        }
    }
}

Variabili di condizione

Dichiarazione problema

Per molte applicazioni, l'esclusione reciproca non è sufficiente. I thread che tentano un'operazione potrebbero dover attendere fino a quando una condizione P non è vera. Un ciclo di attesa occupato

while not( P ) do skip

non funzionerà, poiché l'esclusione reciproca impedirà a qualsiasi altro thread di entrare nel monitor per rendere vera la condizione. Esistono altre "soluzioni" come avere un loop che sblocca il monitor, attende un certo periodo di tempo, blocca il monitor e verifica la condizione P . In teoria, funziona e non si blocca, ma sorgono problemi. È difficile decidere un tempo di attesa appropriato, troppo piccolo e il thread occuperà la CPU, troppo grande e apparentemente non risponderà. Ciò che serve è un modo per segnalare al thread quando la condizione P è vera (o potrebbe essere vera).

Caso di studio: classico problema produttore/consumatore limitato

Un classico problema di concorrenza è quello del produttore/consumatore limitato , in cui esiste una coda o buffer circolare di attività con una dimensione massima, con uno o più thread che sono thread "produttori" che aggiungono attività alla coda e uno o più altri thread sono thread "consumatori" che eliminano le attività dalla coda. Si presume che la coda sia essa stessa non thread-safe e può essere vuota, piena o tra vuota e piena. Ogni volta che la coda è piena di attività, è necessario che i thread del produttore si blocchino finché non c'è spazio per le attività di rimozione della coda dei thread del consumatore. D'altra parte, ogni volta che la coda è vuota, è necessario che i thread del consumatore si blocchino fino a quando non sono disponibili più attività a causa dei thread del produttore che li aggiungono.

Poiché la coda è un oggetto simultaneo condiviso tra thread, gli accessi ad essa devono essere resi atomici , poiché la coda può essere messa in uno stato incoerente durante il corso dell'accesso alla coda che non dovrebbe mai essere esposto tra i thread. Pertanto, qualsiasi codice che accede alla coda costituisce una sezione critica che deve essere sincronizzata per mutua esclusione. Se le istruzioni del codice e del processore nelle sezioni critiche del codice che accedono alla coda possono essere intercalate da cambi di contesto arbitrari tra thread sullo stesso processore o dall'esecuzione simultanea di thread su più processori, esiste il rischio di esporre uno stato incoerente e causare condizioni di competizione .

Errato senza sincronizzazione

Un approccio ingenuo consiste nel progettare il codice con un'attesa intensa e senza sincronizzazione, rendendo il codice soggetto a condizioni di competizione: 

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.
    }
}

Questo codice ha un problema serio in quanto gli accessi alla coda possono essere interrotti e interlacciati con gli accessi di altri thread alla coda. I metodi queue.enqueue e queue.dequeue probabilmente hanno istruzioni per aggiornare le variabili dei membri della coda come la sua dimensione, le posizioni di inizio e fine, l'assegnazione e l'allocazione degli elementi della coda, ecc. Inoltre, queue.isEmpty() e queue.isFull () i metodi leggono anche questo stato condiviso. Se i thread produttore/consumatore possono essere interlacciati durante le chiamate per accodare/rimuovere dalla coda, è possibile che uno stato incoerente della coda possa essere esposto a condizioni di competizione. Inoltre, se un consumatore svuota la coda tra l'uscita di un altro consumatore dall'attesa di occupato e chiama "rimuovi dalla coda", il secondo consumatore tenterà di rimuovere la coda da una coda vuota causando un errore. Allo stesso modo, se un produttore riempie la coda tra l'uscita di un altro produttore dall'attesa di occupato e chiamando "accoda", il secondo produttore tenterà di aggiungere a una coda piena causando un errore.

Aspettando di girare

Un approccio ingenuo per ottenere la sincronizzazione, come accennato in precedenza, consiste nell'utilizzare " spin-waiting ", in cui viene utilizzato un mutex per proteggere le sezioni critiche del codice e viene ancora utilizzato l'impegnato attesa, con il blocco acquisito e rilasciato in tra ogni controllo di occupato. 

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.
    }
}

Questo metodo assicura che non si verifichi uno stato incoerente, ma spreca risorse della CPU a causa dell'inutile attesa. Anche se la coda è vuota e i thread producer non hanno nulla da aggiungere per molto tempo, i thread consumer sono sempre occupati ad aspettare inutilmente. Allo stesso modo, anche se i consumatori sono bloccati per lungo tempo nell'elaborazione delle loro attività correnti e la coda è piena, i produttori sono sempre in attesa. Questo è un meccanismo dispendioso. Ciò che serve è un modo per bloccare i thread del produttore finché la coda non è piena e un modo per bloccare i thread del consumatore finché la coda non è vuota.

(NB: i mutex stessi possono anche essere spin-lock che comportano un'attesa occupata per ottenere il blocco, ma per risolvere questo problema di risorse della CPU sprecate, assumiamo che queueLock non sia uno spin-lock e utilizzi correttamente un blocco bloccare la coda stessa.)

Variabili di condizione

La soluzione è usare le variabili di condizione . Concettualmente una variabile di condizione è una coda di thread, associata a un mutex, su cui un thread può attendere che una condizione diventi vera. Quindi ogni variabile di condizione c è associata a un'asserzione P c . Mentre un thread è in attesa di una variabile di condizione, non si considera che quel thread occupi il monitor e quindi altri thread possono entrare nel monitor per modificare lo stato del monitor. Nella maggior parte dei tipi di monitor, questi altri thread possono segnalare la variabile di condizione c per indicare che l'asserzione P c è vera nello stato corrente.

Quindi ci sono tre operazioni principali sulle variabili di condizione:

  • wait c, m, dove cè una variabile di condizione ed mè un mutex (blocco) associato al monitor. Questa operazione è chiamata da un filo che deve attendere finché l'asserzione P c è vero prima di procedere. Mentre il thread è in attesa, non occupa il monitor. La funzione, e contratto fondamentale, dell'operazione di "attesa", consiste nel compiere i seguenti passi:
    1. Atomicamente :
      1. rilasciare il mutex m,
      2. sposta questo thread da "in esecuzione" a c"coda di attesa" (nota anche come "coda di sospensione") dei thread e
      3. dormi questo thread. (Il contesto viene ceduto in modo sincrono a un altro thread.)
    2. Una volta che questo thread viene successivamente notificato/segnalato (vedi sotto) e ripreso, riacquisire automaticamente il mutex m.
    I passaggi 1a e 1b possono verificarsi in entrambi gli ordini, con 1c che di solito si verifica dopo di essi. Mentre il thread è in sospensione e nella ccoda di attesa, il prossimo contatore di programma da eseguire è al passaggio 2, nel mezzo della funzione/ subroutine "attesa" . Pertanto, il thread dorme e successivamente si sveglia nel mezzo dell'operazione di "attesa".
    L'atomicità delle operazioni all'interno del passaggio 1 è importante per evitare condizioni di competizione che sarebbero causate da un passaggio di thread preventivo tra di esse. Una modalità di errore che potrebbe verificarsi se questi non fossero atomici è un mancato risveglio , in cui il thread potrebbe essere nella ccoda di sospensione di e aver rilasciato il mutex, ma si è verificato un cambio di thread preventivo prima che il thread andasse in sospensione e un altro thread chiamato un'operazione di segnalazione/notifica (vedi sotto) sullo cspostamento del primo thread fuori dalla ccoda di . Non appena il primo thread in questione viene ripristinato, il suo contatore di programma sarà al passaggio 1c e dormirà e non potrà essere riattivato, violando l'invariante che avrebbe dovuto essere nella ccoda di sospensione di quando dormiva. Altre race condition dipendono dall'ordine dei passaggi 1a e 1b e dipendono da dove si verifica un cambio di contesto.
  • signal c, noto anche come notify c, viene chiamato da un thread per indicare che l'asserzione P c è vera. A seconda del tipo e dell'implementazione del monitor, questo sposta uno o più thread dalla ccoda di sospensione di 's alla "coda di pronto" o ad un'altra coda per l'esecuzione. Di solito è considerata una best practice eseguire l'operazione "segnale"/"notifica" prima di rilasciare il mutex massociato a c, ma finché il codice è progettato correttamente per la concorrenza e in base all'implementazione del threading, è spesso accettabile anche rilasciare la serratura prima di segnalare. A seconda dell'implementazione del threading, l'ordine di questo può avere ramificazioni di priorità di pianificazione. (Alcuni autori sostengono invece una preferenza per il rilascio del blocco prima della segnalazione.) Un'implementazione di threading dovrebbe documentare qualsiasi vincolo speciale su questo ordinamento.
  • broadcast c, noto anche come notifyAll c, è un'operazione simile che attiva tutti i thread nella coda di attesa di c. Questo svuota la coda di attesa. In genere, quando più di una condizione del predicato è associata alla stessa variabile di condizione, l'applicazione richiederà la trasmissione anziché il segnale perché un thread in attesa della condizione errata potrebbe essere riattivato e quindi tornare immediatamente a dormire senza riattivare un thread in attesa di la condizione corretta che si è appena avverata. Altrimenti, se la condizione del predicato è uno a uno con la variabile di condizione ad essa associata, il segnale potrebbe essere più efficiente di broadcast .

Come regola di progettazione, più variabili di condizione possono essere associate allo stesso mutex, ma non viceversa. (Questa è una corrispondenza uno-a-molti .) Questo perché il predicato P c è lo stesso per tutti i thread che utilizzano il monitor e deve essere protetto con mutua esclusione da tutti gli altri thread che potrebbero causare la modifica della condizione o che potrebbero leggerlo mentre il thread in questione ne provoca la modifica, ma potrebbero esserci diversi thread che desiderano attendere una condizione diversa sulla stessa variabile che richiede l'utilizzo dello stesso mutex. Nell'esempio produttore-consumatore descritto sopra , la coda deve essere protetta da un oggetto mutex univoco, m. I thread "produttore" vorranno attendere su un monitor utilizzando il blocco me una variabile di condizione che si blocca fino a quando la coda non è piena. I thread "consumatori" vorranno attendere su un monitor diverso utilizzando lo stesso mutex ma una variabile di condizione diversa che si blocca finché la coda non è vuota. (di solito) non avrebbe mai senso avere mutex diversi per la stessa variabile di condizione, ma questo esempio classico mostra perché spesso ha sicuramente senso avere più variabili di condizione che utilizzano lo stesso mutex. Un mutex utilizzato da una o più variabili di condizione (uno o più monitor) può essere condiviso anche con codice che non utilizza variabili di condizione (e che semplicemente lo acquisisce/rilascia senza alcuna operazione di attesa/segnale), se quelle sezioni critiche non si verificano richiedere l'attesa di una determinata condizione sui dati concorrenti. m

Monitora l'utilizzo

L'utilizzo di base corretto di un 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.

Per essere più precisi, questo è lo stesso pseudocodice ma con commenti più dettagliati per spiegare meglio cosa sta succedendo: 

// ... (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);

Risolvere il problema del produttore/consumatore limitato

Avendo introdotto l'uso delle variabili di condizione, usiamolo per rivisitare e risolvere il classico problema produttore/consumatore limitato. La soluzione classica consiste nell'utilizzare due monitor, comprendenti due variabili di condizione che condividono un blocco sulla coda: 

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.
    }
}

Ciò garantisce la concorrenza tra i thread del produttore e del consumatore che condividono la coda delle attività e blocca i thread che non hanno nulla a che fare piuttosto che in attesa, come mostrato nell'approccio sopra menzionato che utilizza gli spin-lock.

Una variante di questa soluzione potrebbe utilizzare una singola variabile di condizione sia per i produttori che per i consumatori, forse denominata "queueFullOrEmptyCV" o "queueSizeChangedCV". In questo caso, più di una condizione è associata alla variabile di condizione, in modo che la variabile di condizione rappresenti una condizione più debole rispetto alle condizioni verificate dai singoli thread. La variabile di condizione rappresenta i thread in attesa che la coda non sia piena e quelli in attesa che non sia vuota. Tuttavia, ciò richiederebbe l'utilizzo di notifyAll in tutti i thread che utilizzano la variabile di condizione e non è possibile utilizzare un segnale normale . Questo perché il segnale normale potrebbe riattivare un thread del tipo sbagliato la cui condizione non è stata ancora soddisfatta e quel thread tornerebbe a dormire senza che un thread del tipo corretto venga segnalato. Ad esempio, un produttore potrebbe riempire la coda e svegliare un altro produttore invece di un consumatore e il produttore svegliato tornerebbe a dormire. Nel caso complementare, un consumatore potrebbe svuotare la coda e svegliare un altro consumatore invece di un produttore, e il consumatore tornerebbe a dormire. L'utilizzo di notifyAll garantisce che alcuni thread del tipo corretto procedano come previsto dall'istruzione del problema.

Ecco la variante che utilizza una sola variabile di condizione e notifyAll: 

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.
    }
}

Primitive di sincronizzazione

L'implementazione di mutex e variabili di condizione richiede un qualche tipo di primitiva di sincronizzazione fornita dal supporto hardware che fornisce l' atomicità . I blocchi e le variabili di condizione sono astrazioni di livello superiore su queste primitive di sincronizzazione. Su un monoprocessore, disabilitare e abilitare gli interrupt è un modo per implementare i monitor impedendo i cambi di contesto durante le sezioni critiche dei blocchi e delle variabili di condizione, ma questo non è sufficiente su un multiprocessore. Su un multiprocessore, di solito vengono utilizzate speciali istruzioni atomiche di lettura-modifica-scrittura sulla memoria come test-and-set , compare-and-swap , ecc., a seconda di ciò che fornisce l' ISA . Questi di solito richiedono il rinvio al blocco dello spin per lo stato di blocco interno stesso, ma questo blocco è molto breve. A seconda dell'implementazione, le istruzioni atomiche di lettura, modifica e scrittura possono bloccare il bus dagli accessi di altri core e/o impedire il riordino delle istruzioni nella CPU. Ecco un esempio di implementazione di pseudocodice di parti di un sistema di threading e mutex e variabili di condizione in stile Mesa, utilizzando test-and-set e una politica first come, first-served. Questo sorvola la maggior parte di come funziona un sistema di threading, ma mostra le parti relative ai mutex e alle variabili di condizione:

Esempio di implementazione del monitor Mesa con 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;
}

Semaforo

Ad esempio, si consideri una classe thread-safe che implementa un semaforo . Esistono metodi per incrementare (V) e decrementare (P) un intero privato s. Tuttavia, l'intero non deve mai essere decrementato al di sotto di 0; quindi un thread che tenta di decrementare deve attendere che l'intero sia positivo. Usiamo una variabile di condizione sIsPositivecon un'asserzione associata di . 

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
    }
}

Implementato mostrando tutta la sincronizzazione (rimuovendo il presupposto di una classe thread-safe e mostrando il 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 implementato utilizzando i semafori

Viceversa, i lock e le variabili di condizione possono essere derivati ​​anche dai semafori, rendendo così monitor e semafori riducibili l'uno all'altro:

L'implementazione qui fornita non è corretta. Se un thread chiama wait() dopo che broadcast() è stato chiamato, un thread originale potrebbe essere bloccato a tempo indeterminato, poiché broadcast() incrementa il semaforo solo il numero sufficiente di volte per i thread già in attesa. 

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 si verifica un segnale su una variabile di condizione su cui è in attesa almeno un altro thread, ci sono almeno due thread che potrebbero occupare il monitor: il thread che segnala e uno qualsiasi dei thread in attesa. Affinché al massimo un thread alla volta occupi il monitor, è necessario effettuare una scelta. Esistono due scuole di pensiero sul modo migliore per risolvere questa scelta. Questo porta a due tipi di variabili di condizione che verranno esaminate in seguito:

  • Le variabili di condizione di blocco danno la priorità a un thread segnalato.
  • Le variabili di condizione non bloccanti danno la priorità al thread di segnalazione.

Variabili di condizione di blocco

Le proposte originali di CAR Hoare e Per Brinch Hansen erano per il blocco delle variabili di condizione . Con una variabile di condizione di blocco, il thread di segnalazione deve attendere all'esterno del monitor (almeno) finché il thread di segnalazione non abbandona l'occupazione del monitor ritornando o attendendo nuovamente su una variabile di condizione. I monitor che utilizzano variabili di condizione di blocco sono spesso chiamati monitor in stile Hoare o monitor di segnale e attesa urgente .

Image
Un monitor in stile Hoare con due variabili di condizione ae b. Dopo Buhr et al.

Supponiamo che ci siano due code di thread associate a ciascun oggetto monitor

  • e è la coda d'ingresso
  • s è una coda di thread che hanno segnalato.

Inoltre assumiamo che per ogni variabile di condizione c , ci sia una coda

  • c.q, che è una coda per i thread in attesa sulla variabile di condizione c

Tutte le code sono generalmente garantite come eque e, in alcune implementazioni, possono essere garantite come first in first out .

L'implementazione di ciascuna operazione è la seguente. (Supponiamo che ogni operazione venga eseguita in mutua esclusione rispetto alle altre, quindi i thread riavviati non iniziano l'esecuzione fino al completamento dell'operazione.) 

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)

La scheduleroutine seleziona il thread successivo per occupare il monitor o, in assenza di thread candidati, sblocca il monitor.

La disciplina di segnalazione risultante è nota come "segnale e attesa urgente", poiché il segnalatore deve attendere, ma ha la priorità sui thread nella coda di ingresso. Un'alternativa è "segnala e aspetta", in cui non c'è scoda e il segnalatore attende invece sulla ecoda.

Alcune implementazioni forniscono un'operazione di segnalazione e ritorno che combina la segnalazione con il ritorno da una procedura. 

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

In entrambi i casi ("segnale e attesa urgente" o "segnale e attesa"), quando viene segnalata una variabile di condizione e c'è almeno un thread in attesa sulla variabile di condizione, il thread di segnalazione passa l'occupazione al thread segnalato senza soluzione di continuità, quindi che nessun altro thread può occupare in mezzo. Se P c è vero all'inizio di ogni operazione di segnale c , sarà vero alla fine di ogni operazione di attesa c . Ciò è riassunto dai seguenti contratti . In questi contratti, I è l' invariante del 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

In questi contratti si assume che I e P c non dipendano dal contenuto o dalla lunghezza di eventuali code.

(Quando è possibile interrogare la variabile di condizione sul numero di thread in attesa sulla sua coda, è possibile fornire contratti più sofisticati. Ad esempio, una coppia di contratti utile, che consente di passare l'occupazione senza stabilire l'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

(Vedi Howard e Buhr et al. per ulteriori informazioni.)

È importante notare qui che l'asserzione P c spetta interamente al programmatore; lui o lei deve semplicemente essere coerente su ciò che è.

Concludiamo questa sezione con un esempio di una classe thread-safe che utilizza un monitor di blocco che implementa uno stack thread-safe limitato . 

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]
    }
}

Si noti che, in questo esempio, lo stack thread-safe fornisce internamente un mutex che, come nel precedente esempio produttore/consumatore, è condiviso da entrambe le variabili di condizione, che controllano condizioni diverse sugli stessi dati simultanei. L'unica differenza è che l'esempio produttore/consumatore presupponeva una normale coda non thread-safe e utilizzava un mutex autonomo e variabili di condizione, senza che questi dettagli del monitor venissero sottratti come nel caso qui. In questo esempio, quando viene chiamata l'operazione "wait", deve in qualche modo essere fornita con il mutex dello stack thread-safe, ad esempio se l'operazione "wait" è una parte integrata della "classe monitor". A parte questo tipo di funzionalità astratta, quando viene utilizzato un monitor "grezzo", dovrà sempre includere un mutex e una variabile di condizione, con un mutex univoco per ogni variabile di condizione.

Variabili di condizione non bloccanti

Con le variabili di condizione non bloccanti (chiamate anche variabili di condizione "stile Mesa" o variabili di condizione "segnala e continua" ), la segnalazione non fa sì che il thread di segnalazione perda l'occupazione del monitor. Invece i thread segnalati vengono spostati nella ecoda. Non c'è bisogno della scoda.

Image
Un monitor in stile Mesa con due variabili di condizione aeb

Con le variabili di condizione non bloccanti, l' operazione del segnale viene spesso chiamata notifica , una terminologia che seguiremo qui. È anche comune fornire un'operazione di notifica a tutti che sposta nella ecoda tutti i thread in attesa di una variabile di condizione .

Il significato delle varie operazioni è dato qui. (Supponiamo che ogni operazione venga eseguita in mutua esclusione rispetto alle altre, quindi i thread riavviati non iniziano l'esecuzione fino al completamento dell'operazione.) 

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

Come variazione a questo schema, il thread notificato può essere spostato in una coda chiamata w, che ha priorità su e. Vedi Howard e Buhr et al. per ulteriore discussione.

È possibile associare un'asserzione P c a ciascuna variabile di condizione c tale che P c sia sicuramente vera al ritorno da . Tuttavia, si deve garantire che P c è preservata dal momento in cui il comunicano filo ing cede occupazione fino a selezionare il filo notificato rientrare il monitor. Tra questi tempi potrebbero esserci attività da parte di altri occupanti. Quindi è comune che P c sia semplicemente vero . wait c

Per questo motivo, di solito è necessario racchiudere ogni operazione di attesa in un ciclo come questo 

while not( P ) do
    wait c

dove P è una condizione più forte di P c . Le operazioni e sono trattate come "suggerimenti" che P potrebbe essere vero per qualche thread in attesa. Ogni iterazione di un tale ciclo oltre il primo rappresenta una notifica persa; pertanto, con i monitor non bloccanti, è necessario prestare attenzione per garantire che non si possano perdere troppe notifiche. notify cnotify all c

Come esempio di "suggerimento", considera un conto bancario in cui un thread di prelievo attenderà che il conto abbia fondi sufficienti prima di procedere 

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
    }
}

In questo esempio, la condizione attesa è una funzione dell'importo da prelevare, quindi è impossibile per un thread di deposito sapere che ha reso tale condizione vera. Ha senso in questo caso consentire a ciascun thread in attesa nel monitor (uno alla volta) di verificare se la sua affermazione è vera.

Monitor di variabili di condizione implicite

Image
Un monitor in stile Java

Nel linguaggio Java , ogni oggetto può essere utilizzato come monitor. I metodi che richiedono l'esclusione reciproca devono essere contrassegnati in modo esplicito con la parola chiave sincronizzata . I blocchi di codice possono anche essere contrassegnati da sincronizzato .

Anziché avere variabili di condizione esplicite, ogni monitor (ovvero oggetto) è dotato di un'unica coda di attesa in aggiunta alla sua coda di ingresso. Tutti in attesa è fatto su questa singola coda di attesa e tutto notifica e notifyAll operazioni si applicano a questa coda. Questo approccio è stato adottato in altri linguaggi, ad esempio C# .

Segnalazione implicita

Un altro approccio alla segnalazione consiste nell'omettere l' operazione di segnalazione . Ogni volta che un thread lascia il monitor (restituendo o attendendo), le asserzioni di tutti i thread in attesa vengono valutate finché uno non viene trovato vero. In un tale sistema, le variabili di condizione non sono necessarie, ma le asserzioni devono essere codificate in modo esplicito. Il contratto di attesa è 

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

Storia

Brinch Hansen e Hoare hanno sviluppato il concetto di monitor nei primi anni '70, sulla base di idee precedenti proprie e di Edsger Dijkstra . Brinch Hansen pubblicò la prima notazione monitor, adottando il concetto di classe di Simula 67 e inventò un meccanismo di accodamento. Hoare ha affinato le regole di ripresa del processo. Brinch Hansen ha creato la prima implementazione di monitor, in Concurrent Pascal . Hoare ha dimostrato la loro equivalenza ai semafori .

I monitor (e il Concurrent Pascal) furono presto utilizzati per strutturare la sincronizzazione dei processi nel sistema operativo Solo .

I linguaggi di programmazione che hanno monitor supportati includono:

Sono state scritte numerose librerie che consentono di costruire monitor in linguaggi che non li supportano in modo nativo. Quando vengono utilizzate le chiamate di libreria, spetta al programmatore contrassegnare esplicitamente l'inizio e la fine del codice eseguito con mutua esclusione. Pthreads è una di queste librerie.

Guarda anche

Appunti

Ulteriori letture

link esterno