Sistemi operativi - Appunti

Esempi di sincronizzazione dei processi

• Pi esegue la sua SC prima di Pj
• SC di Pi va eseguita prima della SC di Pi

pag. 66 Sistemi Operativi - Emmanuel Messina

4) Vogliamo ora ottenere un grafo cobegin-coend ovvero questo sotto illustrato. Questo è il caso più generale perché P0 deve partire prima e dovrà svegliare tutti che andranno in parallelo e una volta terminati, si sveglieranno. Tutti i processi intermedi sono rappresentati nel codice centrale. P0 per svegliare gli altri avrà un ciclo while di signal in quanto tutti gli altri avranno una wait iniziale che

11.4 Errori nell'uso dei semafori

1. Signal a caso

   Nel caso in cui avessimo una init(S,1), considerare init(S,1) anche negli esempi dopo, la signal del P1 incrementerebbe ulteriormente S e consentirebbe a P2 e P3 di entrare in SC. Avremmo quindi un eccesso di processi entranti in SC. Per risolvere dovremmo semmai scambiare la wait e la signal nel P1 di posizione.

   pag. 67 Sistemi Operativi - Emmanuel Messina

2. Eccesso di wait

   In caso di uso eccessivo di wait, nel primo a sinistra si ha una wait in più, si assorbe più di un valore semaforico. Quando il processo 1 fa la wait infatti sta compiendo una wait bloccante perché appunto blocca gli altri e si ha una situazione di deadlock. Abbiamo quello che si dice, un processo

1. Eccesso di signal

Il caso duale è un eccesso di signal. In questo caso è un processo produttore e si hanno errori computazionali. Si verifica la situazione analoga nel errore 1 citato prima ovvero che viene permessa l'entrata di tutti gli altri processi nella SC.

2. Bilanciamento di codici diversi

Si nota subito che il numero di wait e di signal è lo stesso e quindi si ha un bilanciamento. Cosa non va? Nel caso in cui il processo 1 (consumatore) fosse il più veloce, esso sarà bloccante mentre se fosse il processo 3 (produttore) farà entrare tutti. pag. 68 Sistemi Operativi - Emmanuel Messina

3. Diversa velocità

Si considerano ora due semafori inizializzati a init(S,1) e init(Q,1) e i seguenti codici: I due possono accedere in quanto S e Q=1. Ma dopo le wait S e Q=0. I due processi nella seconda wait non possono più proseguire e si crea una situazione di deadlock.

Esercizi

1. Siano dati i semafori e i processi indicati, qual

è l’ordine di esecuzione?La signal di P1 può toccare le due wait nei processi 2 e 3. Nel processo 3 la signal(S1) può toccare la wait(S1)nel processo 1. Nel processo 2 abbiamo per S2 sia una wait e una signal, immaginiamo che P2 tocchi sestesso. Collegando il tutto quindi abbiamo: pag. 69Sistemi Operativi-Emmanuel Messina2)Partendo dal grafo di precedenza cerchiamo di ottenerlo dal codiceSeguiamo ora due step:

• Step 1: Vedere se il grafo fa un ciclo, in questo caso si
• Step 2:Definire quanti sono i semafori. Tra P1 e P2 c’è sicuramente un semaforo così come tra P2 eP3 e tra P3 e P1. Per entrare in P1 si usa un semaforo inizializzato a 1 e che sarà lo stesso a quellousato tra S3 e S1.Tenendo a mente le entrate e le uscite possiamo scrivere il seguente pseudocodice:

3) Si realizzi mediante semafori il seguente grafo di precedenzaSi andranno a utilizzare due semafori S1 e S2. Per gestirli, nel codice diP1 si useranno due

signal(S1) mentre i P2 e P3 avranno per speculareuna wait a testa e una signal(S2) a testa. P4 raccoglierà gli input da P2 eP3 con due wait(S2). pag. 70Sistemi Operativi-Emmanuel Messina

Nel caso in cui si considerasse l’esercizio analogo ma nel caso ciclico sidovrà tenere presente che proprio per questo tutti i processidovranno essere ciclici.

Proprio perché sono dei processi ciclici non si usa lo stesso semaforo per attivare P2 e P3 perché uno deidue potrebbe essere più veloce dell’altro e fa rimanere l’altro bloccato. Questo che segue è infatti il casosbagliato:11.5 Implementazione di un semaforo

I semafori vanno implementati senza ricorrere all’attesa attiva busy waiting. Si definisce semaforo unastruttura C munita di contatore e di una lista di processi.

Le funzioni precedentemente introdotte diventano: pag. 71Sistemi Operativi-Emmanuel Messina

La init alloca il semaforo e inizializza i parametri. La destroy va a fare

l'operazione opposta, fa la free eriporta il contatore a 0. La wait effettua un decremento del contatore che può diventare negativo e il processo viene inserito nella coda del semaforo e il processo viene bloccato. La signal effettua un incremento e se il contatore è <=0 si effettua una pop del primo in lista risvegliando il processo. L'implementazione permette valori negativi e il valore assoluto indica il numero di processi in coda sul semaforo. Esistono varie implementazioni:

Data una pipe il contatore è realizzato tramite il concetto di token. La signal è effettuata tramite una write mentre la wait tramite una read.

semaforeInit() : inizializza il semaforo pag. 72 Sistemi Operativi-Emmanuel Messina

semaphoreSignal(s) : rivece il puntatore al vettore S di dimensione 2 e scrive un carattere (qualsiasi).

semaphoreWait(s): legge un carattere dalla pipe

Esempio: pag. 73 Sistemi Operativi-Emmanuel Messina

L'altra implementazione è quella

• Una semaforo è una variabile sem_t
• Tutte le funzioni sono denominate sem_ e in caso di errore ritornano -1

semaforo e ritorna -1 se è utilizzato da un altro processo. pag. 75Sistemi Operativi-Emmanuel Messina

CAPITOLO 12Deadlock

12.1 Stallo (Deadlock)

Il deadlock è una condizione di stallo. Un P richiede una risorsa non disponibile e si blocca. Un deadlock implica una starvation ma non è vero il contrario.

Le condizioni affinché si verifichi un deadlock sono:

• Deve esserci almeno una risorsa non condivisibile
• Un processo mantiene almeno una risorsa e attende per acquisire almeno un'altra risorsa
• Non esiste diritto di prelazione per almeno una risorsa. Almeno una risorsa non può essere sottratta ma solo rilasciata da chi la utilizza.
• Esiste un insieme di processi {P1,P2,...,Pn} tale che P1 attende una risorsa da P2 che attende una risorsa tenuta da P3 e così via con Pn che attende una risorsa tenuta da P1.

Sono condizioni necessarie ma non sufficienti e devono verificarsi contemporaneamente.

12.2 Modellizzazione

Consideriamo

Ci possono essere deadlock ma se ci sono allora è possibile. Esempio:

• Come processi abbiamo: P1, P2, P3
• Come risorse: R1 e R2 aventi un'istanza
• Abbiamo in questo caso un ciclo, la condizione di stallo è generata dal fatto che mentre P1 attende P2, P2 attende P1.

I principali algoritmi si differenziano per la quantità e il tipo di informazioni richieste. In genere provocano una minore efficienza del sistema e si basano sul concetto di stato sicuro e sequenza sicura.

Si dice stato sicuro quando il sistema è in grado di allocare le risorse richieste a tutti i processi in esecuzione, impedire lo stallo e trovare una sequenza sicura. Una sequenza sicura è una sequenza di schedulazione dei processi tale che per ogni Pi le richieste che esso può ancora effettuare possono essere soddisfatte impiegando le risorse disponibili più quelle liberate dai processi. pag. 77

Sistemi Operativi - Emmanuel Messina

12.3 Algoritmo del banchiere