Lezione sui Semafori e Mutua Esclusione

Introduzione alla Mutua Esclusione

• Problematica: Concorrenza tra processi
• Definizione: Mutua esclusione è necessaria quando più processi eseguono porzioni di codice in concorrenza.
• Sezioni critiche: Porzioni di codice che devono essere eseguite in modo mutuamente esclusivo.

Attesa nella Sezione Critica

• Attesa attiva: Un processo deve attendere se un altro è nella sezione critica.
• Soluzioni al problema della mutua esclusione:
  • Hardware: Disabilitazione e riabilitazione dell'interrupt.
  • Software: Algoritmo di Peterson.

Problemi delle Soluzioni

• Algoritmo di Peterson:
  • Non facilmente generalizzabile per n processi.
  • Attesa attiva (busy waiting) può essere inefficiente.

Istruzione Test and Set

• Funzione: Carica un valore in un registro e modifica il valore di memoria.
• Uso: Permette di implementare la mutua esclusione via busy waiting.
• Vantaggi:
  • Efficiente e a basso livello.
  • Generalizzabile per n processi.
• Necessità: Hardware con istruzione di tipo Test and Set.

Problemi Aperti

1. Busy Waiting: Come evitare che i programmi consumino CPU in attesa.
2. Equità (Fairness): Garantire che i processi entrino in sezione critica in un tempo ragionevole.
   • Esempio: Ordine di accesso in una sala d'attesa.

Semafori

• Definizione: Variabile speciale per sincronizzazione tra processi.
• Origine: Introdotta da Dijkstra.

Caratteristiche del Semaforo

• Struttura: Composto da:
  • Contatore: Variabile intera (può essere positiva o negativa).
  • Coda di Processi: Processi in attesa di entrare in sezione critica.
• Valore del Contatore:
  • Negativo: Semaforo occupato; valore assoluto indica quanti processi sono in attesa.
  • Zero: Semaforo occupato ma nessun processo in attesa.
  • Positivo: Semaforo libero; indica quanti processi possono passare.

Tipologie di Semafori

• Semaforo Binario: Inizialmente impostato a 1 (accesso libero per un processo).
• Semaforo Contatore: Valore superiore a 1 permette accesso multiplo (es. risorse multiple).

Prossimi Passi

• Nella prossima lezione: Come implementare un semaforo e operazioni associate.