1 Aula 9 Concorrência Universidade do Vale do Rio dos Sinos barbosa [email protected]

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 >

[email protected]@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


SumárioSumário

Cooperação

Competição

22


SumárioSumário

Cooperação

CompetiçãoConcorrência em Buffers

23


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


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

31



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

32



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

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

33


SumárioSumário

34


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


PRODUTOR CONSUMIDORBUFFER

40



var sem : semaforo = 0;

41



...

...

ARMAZENA DADO NO BUFFER;

V(sem);

...

...


42



...

...

ARMAZENA DADO NO BUFFER;

V(sem);

...

...

...

...

P(sem);

CONSOME DADO DO BUFFER;

...

...


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


program exemplo;

var x : integer;




PARBEGIN

PAREND

45


program exemplo;

var x : integer;




PARBEGIN

PAREND Dijkstra

46


program exemplo;

var x : integer;




PARBEGIN

PAREND Dijkstra

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

47



48


...

...

P(sem);

SEÇÃO CRÍTICA;

V(sem);

...

...


49


...

...

P(sem);

SEÇÃO CRÍTICA;

V(sem);

...

...

...

...

P(sem);

SEÇÃO CRÍTICA;

V(sem);

...

...


50


program exemplo;

var x : integer;




PARBEGIN

PAREND Dijkstra

51


program exemplo;

var x : integer;




PARBEGIN

PAREND Dijkstra

sem : semaphore = 1;

52


program exemplo;

var x : integer;




PARBEGIN

PAREND Dijkstra


P(sem);

V(sem);

53


program exemplo;

var x : integer;




PARBEGIN

PAREND Dijkstra


P(sem);

V(sem);

P(sem);

V(sem);

54

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

55


Gregory R. Andrews (década de 80)

56


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


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


SumárioSumário

59


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


SumárioSumário

68


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



call proc Chamada de procedimento

... ... CALL

... ...

PROC ... ... END

79




... ... CALL

... ...

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

80





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

PROC ... ... END

81





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

Documents

1 Aula 9 Concorrência Universidade do Vale do Rio dos Sinos barbosa [email protected]