Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
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