Abbiamo introdotto il problema delle corse critiche nel capitolo dedicato alla comunicazione tra processi (che potete trovare a questo indirizzo). Nel paragrafo dedicato alla memoria condivisa abbiamo riportato: “La comunicazione tra processi può andare incontro a problematiche connesse con i problemi delle corse critiche (race condition), ovvero quelle situazioni in cui due o più processi tentano di accedere simultaneamente alla stessa risorsa (ad esempio un’area di memoria comune)”. In questo capitolo descriveremo cosa sono le corse critiche e spiegheremo come esse possano essere evitate.

Una corsa critica si verifica generalmente quando due o più processi leggono o scrivono una stessa variabile nello stesso momento. In questi casi il risultato finale delle loro operazioni dipenderà unicamente dall’ordine con cui vengono eseguite le istruzioni appartenenti ai vari processi. Due processi impegnati in una race condition sono detti concorrenti, questo perché la loro esecuzione è sovrapposta nel tempo.

In un sistema multi-programmato esistono più attività concorrenti, per questo motivo occorre garantire che i risultati delle diverse operazioni non dipendano dall’ordine casuale di esecuzione dei processi.

La Regione Critica e la Mutua Esclusione

I meccanismi di mutua esclusione nascono per garantire che le corse condizionali e i relativi errori non si verifichino. In sintesi il sistema gestisce la corsa critica facendo attendere le entità interessate ad entrare nella regione critica se quest’ultima è già occupata.
I principi di mutua esclusione si basano su quattro assunzioni:

  • Nessuna coppia di processi può trovarsi contemporaneamente in una regione critica condivisa;
  • L’accesso alla regione critica non può essere regolato da alcuna assunzione temporale;
  • L’accesso alla regione critica non può essere bloccato da un’entità che non si trova all’interno di quest’ultima;
  • L’attesa non può essere eterna.

Esistono diversi meccanismi di mutua esclusione, implementati in modi differenti:

  • Disabilitazione degli interrupt;
  • Uso di variabili lock;
  • Alternanza stretta;
  • Uso di istruzioni speciali monoatomiche;
  • Uso di funzioni sleep e wakeup;
  • Uso di semafori;
  • Algoritmo di Peterson.

Disabilitazione degli interrupt

Nei sistemi mono-processore può essere comodo disabilitare gli interrupt della CPU non appena un processo entra nella regione critica. La disabilitazione degli interrupt impedisce alla CPU di saltare (schedulare) ad un nuovo processo fino a che il processo in esecuzione non esce dalla regione critica, e quindi riabilita gli interrupt. Questo sistema può però essere pericoloso, in quanto si consegna ai processi in user level la possibilità di disattivare gli interrupt della CPU (clock-interrupt), questi potrebbero dimenticasi di riattivarli.

Nei sistemi multi-processori questo sistema risulta comunque inutile perché si andrebbe ad intervenire solo su uno dei processori. Non è infatti possibile, per ragioni di sicurezza, la disabilitazione degli interrupt di un core da parte di secondo core.

Uso di variabili “lock”

Una soluzione alternativa prevede l’utilizzo di una variabile condivisa “lock” per gestire gli accessi alla memoria condivisa. Se la variabile è impostata a ‘0’ il processo può settarla ad ‘1’ ed entrare nella regione critica. In caso contrario il processo è obbligato a mettersi in attesa.

Questo sistema è però a sua volta soggetto alla corsa critica, che in questa caso si genera sulla variabile condivisa “lock”. Supponiamo che un processo voglia entrare nella regione critica, esso legge la variabile “lock”, che è impostata a ‘0’ e decide di procedere. Prima che il processo possa settare la variabile a ‘1’ esso viene messo in attesa dallo scheduler, che decide di eseguire un secondo processo. Anche il secondo processo deve entrare nella regione critica, per farlo, legge la variabile (che è ancora impostata a ‘0’), la setta ad ‘1’ ed entra nella regione critica. Successivamente il primo processo ritorna in esecuzione, setta la variabile a ‘1’ ed entra nella regione critica.

Nello stesso momento abbiamo due processi nella stessa regione critica. Per risolvere questo problema dobbiamo introdurre le istruzioni speciali monoatomiche. Le istruzioni monoatomiche sono particolari istruzione che vengono eseguite in un solo ciclo di di CPU.

Alternanza stretta

Questa meccanismo è concettualmente simile al precedente, in questo caso due o più processi si alternano l’uso della regione critica, autorizzandosi a vicenda in modo circolare.

Processo 1:

while(true) {
  while(turn != 0);       // il processo attende il suo turno

  critical_region();      // il processo entra nella regione critica
    /*Operazioni da svolgere nella regione critica*/
    turn = 1;             // il processo autorizza il compagno
  noncritical_regione();  // il processo esce dalla regione critica
}

Processo 2:

while(true) {
  while(turn != 1);      // il processo attende il suo turno

  critical_region();     // il processo entra nella regione critica
    /*Operazioni da svolgere nella regione critica*/
    turn = 0;            // il processo autorizza il compagno
  noncritical_region();  // il processo esce dalla regione critica
}

Questo sistema necessità però che i processi accedano alla regione critica in sequenza. Ad ogni processo non è consentito accedere alla stessa regione critica consecutivamente. Inoltre questa soluzione funzione efficientemente solo l’accesso alla regione critica avviene per breve periodi. L’azione di testare continuamente una variabile è detta busy-waiting, tale azione andrebbe evitata perché consuma numerosi cicli di CPU.