Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Marco Lapegna » 2.Lo stallo dei processi – parte prima


Cos’è un deadlock?

In un ambiente multiprogrammato più processi possono entrare in competizione per ottenere un numero finito di risorse.

Deadlock = STALLO — insieme di processi bloccati: ciascun processo “possiede” una risorsa ed attende di acquisire una risorsa allocata ad un altro processo dell’insieme.

Altri esempi

Esempio 1: risorsa hardware

  • Nei primi sistemi batch alcuni sistemi di spooling richiedevano il completamento dell’output prima di cominciare la stampa.
  • Se l’output era maggiore della dimensione del disco il sistema si bloccava.

Esempio 2: risorsa software

  • Semafori A e B, inizializzati a 1:

P0 P1
wait(A); wait(B);
wait(B); wait(A);


Modello di sistema

  • Insieme di processi P1, P2, . . ., Pn
  • Insieme di risorse R1, R2, . . ., Rm

- Fisiche: cpu, memoria, stampanti, dispositivi di I/O
- Logiche: file, semafori, sezioni critiche

  • Ciascun tipo di risorsa Ri può avere Wi istanze.

- Ad es.: in un sistema biprocessore la “risorsa CPU” ha Wi =2 istanze


Modello di sistema

Una tabella nel kernel conserva lo stato di ogni risorsa (se e a chi è assegnata).

Se un processo richiede una risorsa già assegnata, il processo richiedente è inserito in una apposita coda di processi in attesa.

Sequenza di uso della risorsa

Il protocollo di accesso alle risorse da parte dei processi prevede:

  • Richiesta — se la richiesta non può essere soddisfatta immediatamente, il processo richiedente deve attendere fino all’acquisizione della risorsa.
  • Utilizzo – il processo opera sulla risorsa.
  • Rilascio – il processo rilascia la risorsa.

Richiesta/rilascio realizzati con apposite system call: request/release device, open/close file, allocate/free memory.

Caratterizzazione dei deadlock

Teorema: Una situazione di deadlock può verificarsi se e solo se valgono simultaneamente le seguenti condizioni:

  • Mutua esclusione: ogni risorsa è assegnata ad un solo processo oppure è disponibile.
  • Possesso ed attesa: un processo, che possiede almeno una risorsa, attende di acquisire ulteriori risorse possedute da altri processi.
  • Impossibilità di prelazione: una risorsa può essere rilasciata dal processo che la possiede solo volontariamente, al termine del suo compito.
  • Attesa circolare: esiste un insieme { P1, …, Pn } di processi in attesa, tali che P1 è in attesa di una risorsa che è posseduta da P2, P2 è in attesa di una risorsa posseduta da P3, …, Pn–1 è in attesa di una risorsa posseduta da Pn, e Pn è in attesa di una risorsa posseduta da P1.

Come si può rappresentare un deadlock

Un deadlock si puo’ rappresentare mediante un grafo di allocazione risorse:

Un grafo è costituito da un insieme di vertici (o nodi) V variamente connessi per mezzo di un’insieme di archi E.

L’insieme V è partizionato in due sottoinsiemi:

  • P = {P1, P2, …, Pn } è l’insieme costituito da tutti i processi del sistema.
  • R = {R1, R2, …, Rm } è l’insieme di tutti i tipi di risorse del sistema.

L’insieme E consiste di

  • Arco di richiesta: Pi → Rj
  • Arco di assegnazione: Rj → Pi

Grafo di allocazione risorse

  • Processo
  • Tipo di risorsa con 4 istanze
  • Pi richiede un’istanza di Rj
  • Pi possiede un’istanza di Rj

Esempio 1

  • 2 processi
  • 2 risorse

- R1 → W1 = 1 istanza
- R2 → W2 = 1 istanze

  • P1 possiede un’istanza di R1 e attende un’istanza di R2
  • P2 possiede un’istanza di R2 attende un’istanza di R1

Il sistema è in deadlock?


Esempio 2

  • 2 processi
  • 2 risorse

- R1 → W1 = 1 istanza
- R2 → W2 = 2 istanze

  • P1 possiede un’istanza di R1 e un’istanza di R2
  • P2 possiede un’istanza di R2 attende un’istanza di R1

Il sistema è in deadlock?


Esempio 3

  • 3 processi
  • 4 risorse

- R1 → W1 = 1 istanza
- R2 → W2 = 2 istanze
- R3 → W3 = 1 istanza
- R4 → W4 = 3 istanze

  • P1 possiede un’istanza di R2 e attende un’istanza di R1
  • P2 possiede un’istanza di R1 e di R2 e attende un’istanza di R3
  • P3 possiede un’istanza di R3

Il sistema è in deadlock?


Esempio 4

  • 3 processi
  • 4 risorse

- R1 → W1 = 1 istanza
- R2 → W2 = 2 istanze
- R3 → W3 = 1 istanza
- R4 → W4 = 3 istanze

P1 possiede un’istanza di R2 e attende un’istanza di R1
P2 possiede un’istanza di R1 e di R2 e attende un’istanza di R3
P3 attende un’istanza di R3 e attende un’istanza di R2

Il sistema e’ in deadlock?


Esempio 5

  • 4 processi
  • 2 risorse

- R1 → W1 = 2 istanza
- R2 → W2 = 2 istanze

P1 possiede un’istanza di R2 e attende un’istanza di R1
P2 possiede un’istanza di R1
P3 possiede un’istanza di R1 e attende un’istanza di R2
P4 possiede un’istanza di R2

Il sistema e’ in deadlock?


Riassumendo

Ogni risorsa ha solo un’istanza.

La presenza di un ciclo è condizione necessaria e sufficiente per un deadlock (c’è ciclo se e solo se deadlock):

  • se c’e il ciclo nel grafo c’è anche il deadlock (esempio 1);
  • se non c’e’ il ciclo non c’è deadlock (esempio2).

Riassumendo

Qualche risorsa ha piu’ istanze.

La presenza di un ciclo è condizione necessaria ma non sufficiente per un deadlock (deadlock implica ciclo):

  • se non c’e’ ciclo nel grafo non c’e’ deadlock (esempio 3);
  • se c’e’ il ciclo nel grafo:

- può esserci deadlock (esempio 4);
- può non esserci deadlock (esempio 5).

I materiali di supporto della lezione

Silberschatz , Galvin, Gagne – Sistemi Operativi 8a ed.

Capitolo 6

Tanenbaum – Moderni sistemi operativi 3a ed.

Capitolo 7

Deitel, Deitel, Choffnes - Sistemi operativi 3a ed.

Capitolo 5

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion