Semafori — Esercizi | Prof. Nicola Palmeri

ES. 1 Interleaving fra due processi con semafori — quante stringhe possibili?

Il seguente programma concorrente, a seconda dell'interleaving fra i due processi, può stampare una o più stringhe. Indicare quante sono le possibilità e visualizzarle.
Nota: tutti i semafori sono generali e inizializzati a 0.

Pro1

s1.V();
print("F");
s2.V();
s1.P();
print("C");

Pro2

print("G");
s2.P();
print("D");
s1.V();

Simulazione interleaving

0 / 8

Premi Avanti per simulare l'esecuzione passo per passo.

Pro1

Pro2

s1=0

s2=0

Output:

Tutte le possibili uscite:

ES. 2 Cosa fa questo programma concorrente? (s1, s2 inizializzati a 0)

Analizza il comportamento dei due processi P e Q con s1, s2 semafori inizializzati a 0. Cosa stampano e in che ordine?

s1.V();
s2.P();
print("O");
s2.P();
print("D");
s1.V();

s1.P();
print("L");
s2.V();
s2.V();
s1.P();
print("E");

Simulazione passo per passo

0 / 10

Premi Avanti per simulare.

s1=0

s2=0

Output:

ES. 3 Modifica i processi per stampare PERSE e PERES usando semafori

Dati i processi P (stampa P, E, E) e Q (stampa R, S), modificali aggiungendo semafori in modo che stampino le parole PERSE e PERES.

P (originale)

print("P");
print("E");
print("E");

Q (originale)

print("R");
print("S");

Seleziona la parola da ottenere:

ES. 4 Valori di val e possibilità di deadlock

Dati: val=0, sp=new Semaphore(2), sq=new Semaphore(1), mutex=new Semaphore(1).
P esegue il ciclo kp=2 volte, Q il ciclo kq=3 volte.
a) Quali sono i valori possibili di val al termine?
b) È possibile che P o Q restino bloccati indefinitamente?

P (kp=2)

while (kp > 0) {
  sp.P();
  mutex.P();
  val = val+1;
  sq.V();
  kp--;
  mutex.V();
}

Q (kq=3)

while (kq > 0) {
  sq.P();
  mutex.P();
  val = val*2;
  sp.V();
  kq--;
  mutex.V();
}

Simulazione interattiva

0 / 9

Premi Avanti per simulare l'esecuzione.

P (kp=2)

Q (kq=3)

sp=2

sq=1

mutex=1

val=0

Rispondi alle domande:

a) Qual è il valore finale di val?

Il mutex garantisce che val venga modificato da un solo processo per volta. Le operazioni (+1 e *2) si alternano in modo fisso grazie ai semafori sp e sq, dando sempre lo stesso risultato finale.

b) È possibile che P o Q restino bloccati indefinitamente?

sp e sq formano un "ping pong": P fa sp.P() poi sq.V(), Q fa sq.P() poi sp.V(). Il sistema non può bloccarsi perché ogni passo di uno sblocca l'altro.

ES. 5 Pro1 / Pro2 — Analisi interleaving e codice Java

Due processi concorrenti usano i semafori s1 e s2, entrambi inizializzati a 0. Analizza le possibili uscite e studia il corrispondente codice Java con Semaphore.
Nota: V() = release() | P() = acquire() | semafori generali init a 0.

Pro1

s1.V();  // s1: 0→1
print("F");
s2.V();  // s2: 0→1
s1.P();  // attende s1
print("C");

Pro2

print("G");
s2.P(); // attende s2
print("D");
s1.V(); // s1: ?→?+1

Simulazione passo per passo — interleaving GFDC

0 / 8

Premi Avanti per simulare l'esecuzione passo per passo.

Pro1

Pro2

s1=0

s2=0

Output:

Analisi: tutte le uscite possibili

Vincoli imposti dai semafori:
• s2.P() in Pro2 aspetta s2.V() in Pro1 → D viene sempre dopo F
• s1.P() in Pro1 aspetta s1.V() in Pro2 → C viene sempre dopo D
• G è prima di s2.P() in Pro2 → G viene sempre prima di D
• L'unica libertà: G può uscire prima o dopo F

GFDC

Pro2 stampa G prima di F

FGDC

Pro1 stampa F prima di G

Solo 2 uscite possibili — D e C sono sempre in quest'ordine, e sempre dopo G e F. Impossibile avere GFCD, FDGC, DCGF ecc.

Tabella di esecuzione (interleaving GFDC)

Step	Processo	Operazione	s1	s2	Note	Output
1	Pro1	s1.V()	0→1	0	s1 segnalato
2	Pro2	print("G")	1	0	—	G
3	Pro1	print("F")	1	0	—	GF
4	Pro1	s2.V()	1	0→1	s2 segnalato	GF
5	Pro2	s2.P()	1	1→0	sbloccato ✓	GF
6	Pro1	s1.P()	1→0	0	Pro1 attende s1	GF
7	Pro2	print("D")	0	0	—	GFD
8	Pro2	s1.V()	0→1	0	Pro1 sbloccato ✓	GFD
9	Pro1	print("C")	0	0	✅ Fine	GFDC

Implementazione Java

Java ProSemafori.java

import java.util.concurrent.Semaphore;

public class ProSemafori {

// Semafori statici condivisi, inizializzati a 0 static Semaphore s1 = new Semaphore(0); static Semaphore s2 = new Semaphore(0);
public static void main(String[] args) {
// ===== PRO1 ===== Thread pro1 = new Thread(() -> { try { s1.release(); // s1.V() — segnala s1 System.out.print("F"); // print("F") s2.release(); // s2.V() — segnala s2, sblocca Pro2 s1.acquire(); // s1.P() — attende Pro2 System.out.print("C"); // print("C") } catch (InterruptedException e) { Thread.currentThread().interrupt(); } });
// ===== PRO2 ===== Thread pro2 = new Thread(() -> { try { System.out.print("G"); // print("G") s2.acquire(); // s2.P() — attende Pro1 System.out.print("D"); // print("D") s1.release(); // s1.V() — sblocca Pro1 per "C" } catch (InterruptedException e) { Thread.currentThread().interrupt(); } });
// Avvia entrambi i thread pro1.start(); pro2.start(); } }

Verifica la comprensione:

1) Quante uscite distinte sono possibili?

Esatto! Solo la posizione di G rispetto a F è libera. D viene sempre dopo F (grazie a s2), e C viene sempre dopo D (grazie a s1). Le uniche uscite valide sono GFDC e FGDC.

2) Cosa succede se in Pro2 rimuoviamo s2.P()?

Corretto! Senza s2.P() in Pro2, il vincolo "D dopo F" salta. Pro2 potrebbe stampare G e D prima che Pro1 stampi F, generando uscite come GDFC, DGFC ecc.

3) In Java, quale metodo corrisponde a V() (segnala)?

Giusto! In java.util.concurrent.Semaphore: release() corrisponde a V() (segnala/incrementa), acquire() corrisponde a P() (attendi/decrementa).