Sistemi Operativi: comunicazione inter-processo e sincronizzazione

UNIVERSITÀ DEGLI STUDI DI MILANO

Sistemi Operativi

JDI ST ME AS ER UNI ANENSIS STUDIORUM MET IPC: Inter-Process Communication Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025 ERSIT MEDIOLANECompetizione per le risorse (Race Condition)

Spooler directory

4 abc out = 4 Process A 5 prog.c 6 prog.n 7 Process B in = 7 Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Regioni critiche

1. No two processes may be simultaneously inside their critical regions
2. No assumptions may be made about speeds or the number of CPUs
3. No process running outside its critical region may block any process
4. No process should have to wait forever to enter its critical region

Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Accesso a una regione critica

A enters critical region A leaves critical region Process A I B attempts to enter critical region B enters critical region I B leaves critical region I Process B I I I I 1 1 B blocked 1 T 1 T. 2 T. 3 T 4 Time Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Mutua esclusione con Busy Waiting

• Disabilitazione degli interrupt
• Variabili di lock
• TSL
• Alternanza stretta
• Algoritmo di Peterson

while (TRUE) { while (turn != 0) /* loop */; critical_region(); turn = 1; noncritical_region(); } while (TRUE) { while (turn != 1) /* loop */; critical_region(); turn = 0; noncritical_region(); (a) (b) Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Algoritmo di Peterson

#define FALSE 0 #define TRUE 1 #define N 2 int turn; int interested[N]; /* number of processes */ /* whose turn is it? * / /* all values initially 0 (FALSE) */ void enter_region(int process); /* process is 0 or 1 */ int other; /* number of the other process */ other = 1 - process; /* the opposite of process */ /* show that you are interested */ /* set flag */ interested[process] = TRUE; turn = process; while (turn == process && interested[other] == TRUE) /* null statement */ ; void leave_region(int process) { } /* process: who is leaving */ interested[process] = FALSE; /* indicate departure from critical region */ Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Peterson for dummies

Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025 while (TRUE) { while (turn != 0) critical_region(); turn = 1; noncritical_region(); /* loop */; } while (true) { enter_region (0); critical_region (); leave_region (0); noncritical_region (); } interested[process] = TRUE; turn = process; /* show that you are interested */ /* set flag */ while (turn == process && interested[other] == TRUE) /* null statement */ ; Se non interviene lo scheduler, mi blocco qui PER SEMPRE La condizione non è più verificata (tocca a me) quando: 1. L'altro processo tenta di entrare (turn = other in enter_region) 2. L'altro processo esce (interested[other] = false in exit_region)

Sleep and Wait

• Fare busy waiting non è mai un buon approccio - Uso inutile di CPU - Priority inversion - Assunzioni sulla struttura del sistema
• È invece decisamente preferibile avere a disposizione uno strumento per aspettare che una risorsa sia disponibile

Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Produttore e consumatore

Producer Consumer Problem P1 C1 Data Buffer P2 C2 P3 C3 Producer Threads Consumer Threads Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Soluzione SBAGLIATA

#define N 100 int count = 0; /* number of slots in the buffer */ /* number of items in the buffer */ void producer(void) { int item; while (TRUE) { item = produce_item(); if (count == N) sleep(); insert_item(item); count = count + 1; if (count == 1) wakeup(consumer); } /* repeat forever */ /* generate next item */ /* if buffer is full, go to sleep */ /* put item in buffer */ /* increment count of items in buffer */ /* was buffer empty? * / } void consumer(void) { int item; while (TRUE) { if (count == 0) sleep(); item = remove_item(); count = count - 1; if (count == N - 1) wakeup(producer); consume_item(item); } /* repeat forever */ /* if buffer is empty, got to sleep */ /* take item out of buffer */ /* decrement count of items in buffer */ /* was buffer full? * / /* print item */ } Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Strutture dati complesse

• Semafori (mutex)
• Monitor monitor example integer i; condition c; procedure producer(); . . end; procedure consumer(); end; end monitor;

Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Soluzione con semafori (questa funziona)

#define N 100 typedef int semaphore; semaphore mutex = 1; semaphore empty = N; semaphore full = 0; /* number of slots in the buffer */ /* semaphores are a special kind of int */ /* controls access to critical region */ /* counts empty buffer slots */ /* counts full buffer slots */ void producer(void) { int item; while (TRUE) { item = produce_item(); down(&empty); down(&mutex); insert_item(item); up(&mutex); up(&full); /* TRUE is the constant 1 */ /* generate something to put in buffer */ /* decrement empty count */ /* enter critical region */ /* put new item in buffer */ /* leave critical region */ /* increment count of full slots */ } } void consumer(void) { int item; while (TRUE) { down(&full); down(&mutex); item = remove_item(); up(&mutex); up(&empty); consume_item(item); } /* infinite loop */ /* decrement full count */ /* enter critical region */ /* take item from buffer */ /* leave critical region */ /* increment count of empty slots */ /* do something with the item */ } Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Barriere

A Process B. Barrier Barrier Barrier C D. D D Time Time Time (a) (b) (c) Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Il problema del 5 filosofi

A A B B C C Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025

UNIVERSITÀ DEGLI STUDI DI MILANO

Sul libro

• Capitolo 2 - 2.3
• Della TSL sappiate che cosa è, ma ignorate gli esempi in pseudo-assembler
• Tranne la parte di implementazione dei Mutex
• Tranne "Mutexes in Pthreads"
• Tranne 2.3.8 e 2.3.10

Dario Maggiorini (dario@di.unimi.it) Sistemi Operativi - A.A. 2024 - 2025