Aula09a

Sistemas Operacionais

Programação Concorrente
Impasses

Edson Moreno [e-mail] http://www.inf.pucrs.br/~emoreno

Sumário
 Princípios de Deadlock

 Técnicas de solução do problema
 Prevenir a ocorrência de deadlock
 Evitar a possibilidade de ocorrência de deadlock

 Detecção a ocorrência de deadlock e recuperar

Deadlock
 Um conjunto de processo está em deadlock se
 Cada processo do conjunto está bloqueado
 Se o bloqueio está ocorrendo pelo aguarde de um evento
 Se este evento somente pode ser disparado por outro processo
 Se este outro processo também está bloqueado
 Tipicamente envolve processos competindo pelo mesmo recurso

Deadlock em potencial
Precisa dos quadrantes C eD Precisa dos quadrantes D eA Precisa dos quadrantes B eC Precisa dos quadrantes A eB Deadlock real
Trava até que
D esteja livre

Trava até que
A esteja livre

Trava até que
C esteja livre

Trava até que
B esteja livre

Deadlock real

Dados dois processos P e Q
 Dados os process P e Q
 Cada qual precisa acessar a um

recurso A e B por um tempo determinado Diagrama de deadlock

Lógica alternativa
 Suponha que P
 Não necessite de ambos recursos ao mesmo tempo
 Assim, os processo podem ser construídos da seguinte forma...

Diagrama lógico alternativo

Exemplo
 Situação
 Há um espaço de 200Kbytes para ser alocado
 A seguinte seqüência de eventos ocorre
P1

P2

...

...

Request 80 Kbytes;

Request 70 Kbytes;

Request 60 Kbytes;

Request 80 Kbytes;

...

...

 Deadlock ocorre se ambos processos progredirem para sua

segunda requisição

Grafo de alocação de recurso
 Grafo dirigido
 Detalha um estado de um recurso ou processo

Alocação de recursos - Grafo de deadlock

Condições de um possível Deadlock
 Exclusão mútua
 Apenas um processo pode usar o recurso por vez

 Segurar e esperar
 Um processo pode conter recursos alocados enquanto aguarda a

atribuição de outros
 Sem preempção
 Nenhum recurso pode ser forçosamente removido de um

processo