Come funziona il segnale del semaforo

1

Sembra che abbia problemi a capire l'implementazione del semaforo. Q = coda.

Wait(Process P) {
    value = value -1; 
    if (value <0) {
       add P to Q;
       P->block();
}

Signal() {
    value = value +1;
    if (value <=0) {
      remove P from Q;
      wakeup(P);
}

Non capisco perché il segnale rimuova P da Q se il valore è negativo. Consideriamo questo scenario.

Il valore del semaforo è 0;

Thread A Calls  _sempahore.Wait ();

// Ora il valore del semaforo è -1 e il thread A è in coda di attesa.

Thread B Calls:  _sempahore.Wait ();

// Ora il valore del semaforo è -2 e il thread B si trova nella coda di attesa.

Thread C Calls:  _sempaore.Signal ()

** // Ora il valore del semaforo è -1 e il thread A viene rimosso dalla coda e inserito nella coda pronta ?! Perché? **

    
posta MasterOfPuppets 13.07.2017 - 09:09
fonte

2 risposte

4

Semplice: se il valore è 0, allora ogni attesa () consecutiva mette un thread nella coda di attesa e ogni segnale consecutivo () rimuove un thread dalla coda di attesa. aspetta e il segnale dovrebbe venire in coppia, ogni thread chiama wait () andando in coda finché non c'è un segnale corrispondente ().

Per spiegare il comportamento quando il valore è > 0: Normalmente, si usa wait / signal in questo modo: si avvia un thread indipendente per fare un po 'di lavoro. Si chiama wait () per attendere il termine del thread. Il thread chiama signal () per segnalare che ha fatto il suo lavoro. E ti aspetteresti che wait () sia chiamato prima di signal (), quindi tutto funziona come descritto sopra.

Ma cosa succede se il thread è molto veloce e riesce a finire prima di aspettare che finisca? Chiama signal () ma non c'è ancora il thread matching wait (), quindi aumenta semplicemente il valore. Quindi il thread in attesa chiama wait (). Il valore era positivo, perché signal () è stato chiamato prima di wait (), quindi il thread in attesa può continuare a essere eseguito immediatamente.

    
risposta data 13.07.2017 - 17:39
fonte
-1

I don't understand why the signal remove P from Q if the value is negative.

if (value <=0) {
  remove P from Q;

Se il valore è negativo, value <= 0 è true e P sarà rimosso.

Se osservi altre implementazioni, ad esempio la descrizione su link rispetto alla descrizione al link quindi ci sono differenze, ad esempio nell'implementazione di Windows il conteggio non può essere inferiore a zero e le risorse sono disponibili se il conteggio è maggiore di zero:

A semaphore object is a synchronization object that maintains a count between zero and a specified maximum value. The count is decremented each time a thread completes a wait for the semaphore object and incremented each time a thread releases the semaphore. When the count reaches zero, no more threads can successfully wait for the semaphore object state to become signaled. The state of a semaphore is set to signaled when its count is greater than zero, and nonsignaled when its count is zero.

Each time one of the wait functions returns because the state of a semaphore was set to signaled, the count of the semaphore is decreased by one. The ReleaseSemaphore function increases a semaphore's count by a specified amount. The count can never be less than zero or greater than the maximum value.

Questa implementazione sembra funzionare in senso inverso, qualcosa come

Wait(Process P)
    if (value == 0)
        add P to Q;
        P->block();
    else
        value = value -1; 

Release(count) 
    value = value + count
    if value > max_count
        value = max_count

    while (value > 0 and Q is not empty ) 
      value = value - 1
      remove P from Q
      P->wakeup()

La differenza tra questo comportamento e quello dei semafori descritto al link è che 'valore' è l'unico in assoluto il numero di risorse disponibili, piuttosto che diventare negativo se ci sono processi in attesa.

    
risposta data 13.07.2017 - 15:15
fonte

Leggi altre domande sui tag