1 Aula 9 Concorrência Universidade do Vale do Rio dos Sinos barbosa barbosa@exatas.unisinos.br

1

Aula 9Aula 9ConcorrênciaConcorrência

Universidade do Vale do Rio dos Sinos

< Página da Disciplina >

www.inf.unisinos.br/~barbosawww.inf.unisinos.br/~barbosa

<Endereço do Professor >

barbosa@exatas.unisinos.brbarbosa@exatas.unisinos.br

2

1 – Introdução

SumárioSumário

3

1 – Introdução2 – Concorrência no nível de subprograma

SumárioSumário

4

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos

SumárioSumário

5

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores

SumárioSumário

6

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens

SumárioSumário

7

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens6 – Concorrência em ADA

SumárioSumário

8

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens6 – Concorrência em ADA7 – Threads em Java

SumárioSumário

9

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens6 – Concorrência em ADA7 – Threads em Java8 – Concorrência no nível de comando

SumárioSumário

10

1 – Introdução - Tipos

SumárioSumário

11

1 – Introdução - Tipos - Instrução - Comando - Unidade - Programa

SumárioSumário

12

1 – Introdução - Tipos - Instrução - Comando - Unidade - Programa

SumárioSumário

Linguagens de Programação

13

1 – Introdução - Tipos - Gênese da concorrência: Sistemas Operacionais

SumárioSumário

14

1 – Introdução - Tipos - Gênese da concorrência: Sistemas Operacionais - Arquiteturas de Multiproc.: SIMD e MIMD

SumárioSumário

15

1 – Introdução - Tipos - Gênese da concorrência: Sistemas Operacionais - Arquiteturas de Multiproc.: SIMD e MIMD - Categorias de concorrência

SumárioSumário

16

1 – Introdução - Tipos - Gênese da concorrência: Sistemas Operacionais - Arquiteturas de Multiproc.: SIMD e MIMD - Categorias de concorrência

SumárioSumário

CooperaçãoCompetição

17

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa

SumárioSumário

18

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta

SumárioSumário

19

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização

SumárioSumário

20

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização

SumárioSumário

21

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização

SumárioSumário

Cooperação

Competição

22

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização

SumárioSumário

Cooperação

CompetiçãoConcorrência em Buffers

23

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização

SumárioSumário

Cooperação

CompetiçãoConcorrência em Buffers

Exclusão Mútua

24

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização - Mecanismos de sincronização

SumárioSumário

25

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização - Mecanismos de sincronização

SumárioSumário

SemáforosMonitoresMensagens

26

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização - Mecanismos de sincronização - Vivência / deadlock

SumárioSumário

27

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização - Mecanismos de sincronização - Vivência / deadlock - Questões de projeto

SumárioSumário

28

1 – Introdução2 – Concorrência no nível de subprograma - Tarefa - Tarefa disjunta - Sincronização - Tipos de sincronização - Mecanismos de sincronização - Vivência / deadlock - Questões de projeto

SumárioSumário

29

Questões de projetoQuestões de projeto

- Como a sincronização de cooperação é fornecida ?

30

Questões de projetoQuestões de projeto

- Como a sincronização de cooperação é fornecida ? - Como a sincronização de competição é fornecida ?

31

Questões de projetoQuestões de projeto

- Como a sincronização de cooperação é fornecida ? - Como a sincronização de competição é fornecida ?

- Como e quando as tarefas iniciam e encerram a execução ?

32

Questões de projetoQuestões de projeto

- Como a sincronização de cooperação é fornecida ? - Como a sincronização de competição é fornecida ?

- Como e quando as tarefas iniciam e encerram a execução ?

- As tarefas são estática ou dinamicamente criadas ?

33

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos

SumárioSumário

34

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos

SumárioSumário

35

SemáforosSemáforos- Dijkstra, 1965 1) Variável inteira 2) Duas operações P e V 3) P e V são atômicas 4) P e V são suportadas pelo S. O.

36

SemáforosSemáforos- Dijkstra, 1965 1) Variável inteira 2) Duas operações P e V 3) P e V são atômicas 4) P e V são suportadas pelo S. O. P se sem > 0 então sem = sem – 1 senão suspende o processo

37

SemáforosSemáforos- Dijkstra, 1965 1) Variável inteira 2) Duas operações P e V 3) P e V são atômicas 4) P e V são suportadas pelo S. O. P V se sem > 0 então se um processo estiver suspenso sem = sem – 1 devido a P(sem) então senão reative-o suspende o processo senão sem = sem + 1

38

SemáforosSemáforos- Sincronização de cooperação

39

SemáforosSemáforos- Sincronização de cooperação

PRODUTOR CONSUMIDORBUFFER

40

SemáforosSemáforos- Sincronização de cooperação

PRODUTOR CONSUMIDORBUFFER

var sem : semaforo = 0;

41

SemáforosSemáforos- Sincronização de cooperação

PRODUTOR CONSUMIDORBUFFER

...

...

ARMAZENA DADO NO BUFFER;

V(sem);

...

...

var sem : semaforo = 0;

42

SemáforosSemáforos- Sincronização de cooperação

PRODUTOR CONSUMIDORBUFFER

...

...

ARMAZENA DADO NO BUFFER;

V(sem);

...

...

...

...

P(sem);

CONSOME DADO DO BUFFER;

...

...

var sem : semaforo = 0;

43

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

program exemplo;

var x : integer;

procedure soma; begin x := x + 1; end;

procedure diminui; begin x := x –1; end;

begin x := 0; soma; diminui; write(x); end.

44

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

program exemplo;

var x : integer;

procedure soma; begin x := x + 1; end;

procedure diminui; begin x := x –1; end;

begin x := 0; soma; diminui; write(x); end.

PARBEGIN

PAREND

45

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

program exemplo;

var x : integer;

procedure soma; begin x := x + 1; end;

procedure diminui; begin x := x –1; end;

begin x := 0; soma; diminui; write(x); end.

PARBEGIN

PAREND Dijkstra

46

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

program exemplo;

var x : integer;

procedure soma; begin x := x + 1; end;

procedure diminui; begin x := x –1; end;

begin x := 0; soma; diminui; write(x); end.

PARBEGIN

PAREND Dijkstra

LOAD R,[X]INC RLOAD [X],R

47

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

var sem : semaforo = 1;

48

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

...

...

P(sem);

SEÇÃO CRÍTICA;

V(sem);

...

...

var sem : semaforo = 1;

49

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

...

...

P(sem);

SEÇÃO CRÍTICA;

V(sem);

...

...

...

...

P(sem);

SEÇÃO CRÍTICA;

V(sem);

...

...

var sem : semaforo = 1;

50

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

program exemplo;

var x : integer;

procedure soma; begin x := x + 1; end;

procedure diminui; begin x := x –1; end;

begin x := 0; soma; diminui; write(x); end.

PARBEGIN

PAREND Dijkstra

51

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

program exemplo;

var x : integer;

procedure soma; begin x := x + 1; end;

procedure diminui; begin x := x –1; end;

begin x := 0; soma; diminui; write(x); end.

PARBEGIN

PAREND Dijkstra

sem : semaphore = 1;

52

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

program exemplo;

var x : integer;

procedure soma; begin x := x + 1; end;

procedure diminui; begin x := x –1; end;

begin x := 0; soma; diminui; write(x); end.

PARBEGIN

PAREND Dijkstra

sem : semaphore = 1;

P(sem);

V(sem);

53

SemáforosSemáforos- Sincronização de competição (exclusão mútua)

program exemplo;

var x : integer;

procedure soma; begin x := x + 1; end;

procedure diminui; begin x := x –1; end;

begin x := 0; soma; diminui; write(x); end.

PARBEGIN

PAREND Dijkstra

sem : semaphore = 1;

P(sem);

V(sem);

P(sem);

V(sem);

54

Semáforos em SR (Semáforos em SR (Synchronizing ResourcesSynchronizing Resources))

55

Semáforos em SR (Semáforos em SR (Synchronizing ResourcesSynchronizing Resources))

Gregory R. Andrews (década de 80)

56

Semáforos em SR (Semáforos em SR (Synchronizing ResourcesSynchronizing Resources))

resource CS()

const N := 20

var x := 0

sem mutex := 1

process p (i := 1 to N) ... ... P(mutex) x := x + 1 V(mutex) ... ... end end

57

Semáforos em SR (Semáforos em SR (Synchronizing ResourcesSynchronizing Resources))

resource CS()

const N := 20

var x := 0

sem mutex := 1

process p (i := 1 to N) ... ... P(mutex) x := x + 1 V(mutex) ... ... end end

58

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores

SumárioSumário

59

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores

SumárioSumário

60

MonitoresMonitores- Hoare, 1974

61

MonitoresMonitores- Hoare, 1974 1) “O semáforo é uma ferramenta de sincronização elegante para o programador ideal que jamais comete erro.” ( Per Hansen, 1973)

62

MonitoresMonitores- Hoare, 1974 1) “O semáforo é uma ferramenta de sincronização elegante para o programador ideal que jamais comete erro.” ( Per Hansen, 1973) 2) Concurrent Pascal (Hansen, 1975)

63

MonitoresMonitores- Hoare, 1974 1) “O semáforo é uma ferramenta de sincronização elegante para o programador ideal que jamais comete erro.” ( Per Hansen, 1973) 2) Concurrent Pascal (Hansen, 1975) 3) Baseado em TADs

64

MonitoresMonitores- Hoare, 1974 1) “O semáforo é uma ferramenta de sincronização elegante para o programador ideal que jamais comete erro.” ( Per Hansen, 1973) 2) Concurrent Pascal (Hansen, 1975) 3) Baseado em TADs 4) Estrutura:

Variáveis Globais

Procedimentos

Código de inicialização

65

MonitoresMonitores- Sincronização de competição (exclusão mútua)

program exemplo;

monitor regiao_critica; var x : integer; procedure soma; begin x := x + 1; end; procedure diminui; begin x := x –1; end; begin x := 0; end; begin parbegin; regiao_critica.soma; regiao_critica.diminui; parend; end.

66

MonitoresMonitores- Sincronização de competição (exclusão mútua)

program exemplo;

monitor regiao_critica; var x : integer; procedure soma; begin x := x + 1; end; procedure diminui; begin x := x –1; end; begin x := 0; end; begin parbegin regiao_critica.soma; regiao_critica.diminui; parend end.

67

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens

SumárioSumário

68

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens

SumárioSumário

69

MensagensMensagens- Hansen (1978) e Hoare (1978)

70

MensagensMensagens- Hansen (1978) e Hoare (1978) 1) Semáforos e monitores em memória compartilhada

71

MensagensMensagens- Hansen (1978) e Hoare (1978) 1) Semáforos e monitores em memória compartilhada 2) Sistemas distribuídos?

72

MensagensMensagens- Hansen (1978) e Hoare (1978) 1) Semáforos e monitores em memória compartilhada 2) Sistemas distribuídos? 3) Mensagens síncronas e assíncronas

73

MensagensMensagens- Hansen (1978) e Hoare (1978) 1) Semáforos e monitores em memória compartilhada 2) Sistemas distribuídos? 3) Mensagens síncronas e assíncronas 4) Envio e recebimento devem possuir um modelo de sincronismo

74

MensagensMensagens- Hansen (1978) e Hoare (1978) 1) Semáforos e monitores em memória compartilhada 2) Sistemas distribuídos? 3) Mensagens síncronas e assíncronas 4) Envio e recebimento devem possuir um modelo de sincronismo 5) Linguagem deve suportar o modelo proposto

75

MensagensMensagens- Hansen (1978) e Hoare (1978) 1) Semáforos e monitores em memória compartilhada 2) Sistemas distribuídos? 3) Mensagens síncronas e assíncronas 4) Envio e recebimento devem possuir um modelo de sincronismo 5) Linguagem deve suportar o modelo proposto 6) Modelo do SR

76

MensagensMensagens- Hansen (1978) e Hoare (1978) 1) Semáforos e monitores em memória compartilhada 2) Sistemas distribuídos? 3) Mensagens síncronas e assíncronas 4) Envio e recebimento devem possuir um modelo de sincronismo 5) Linguagem deve suportar o modelo proposto 6) Modelo do SR

77

Modelo de Mensagens em SRModelo de Mensagens em SR

INVOCAÇÃO SERVIÇO EFEITO

call proc Chamada de procedimento call in rendezvous

send proc Criação de processo dinâmica

send in Passagem de mensagem assíncrona

78

Modelo de Mensagens em SRModelo de Mensagens em SR

INVOCAÇÃO SERVIÇO EFEITO

call proc Chamada de procedimento

... ... CALL

... ...

PROC ... ... END

79

Modelo de Mensagens em SRModelo de Mensagens em SR

INVOCAÇÃO SERVIÇO EFEITO

call proc Chamada de procedimento call in rendezvous

... ... CALL

... ...

... ... IN ... ... NI ... ...

80

Modelo de Mensagens em SRModelo de Mensagens em SR

INVOCAÇÃO SERVIÇO EFEITO

call proc Chamada de procedimento call in rendezvous

send proc Criação de processo dinâmica

... ... SEND ... ... ... ... ...

PROC ... ... END

81

Modelo de Mensagens em SRModelo de Mensagens em SR

INVOCAÇÃO SERVIÇO EFEITO

call proc Chamada de procedimento call in rendezvous

send proc Criação de processo dinâmica

send in Passagem de mensagem assíncrona ...

... SEND ... ... ... ... ...

... ... IN ... ... NI ... ...

82

Exemplo de Exemplo de rendezvousrendezvous em SR em SRresource main() op f(x:int), g(u:real) returns v:real process p1 var y : int ... call f(y) ... end process p2 var w : real w := g(3.8) ... ... end process q var z : int in f(x) -> z := z + x [] g(u) returns v -> v := u * u – 9.3 ni ... ... endend

83

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens6 – Concorrência em ADA

SumárioSumário

84

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens6 – Concorrência em ADA7 – Threads em Java

SumárioSumário

85

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens6 – Concorrência em ADA7 – Threads em Java - Classe Thread - Prioridades - Sincronização de competição (synchronized) - Sincronização de colaboração (Métodos wait/notify)

SumárioSumário

86

1 – Introdução2 – Concorrência no nível de subprograma3 – Semáforos4 – Monitores5 – Passagem de mensagens6 – Concorrência em ADA7 – Threads em Java8 – Concorrência no nível de comando

SumárioSumário