Buscar

04Threads e soluções de concorrência 20171

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 38 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 38 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 38 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

SISTEMAS OPERACIONAIS 
• REVISÃO SOBRE PROCESSOS 
• THREADS 
• CONCORRÊNCIA: 
 CONDIÇÃO DE CORRIDA 
 REGIÃO CRÍTICA 
 EXCLUSÃO MÚTUA 
 
Prof. Luiz di Marcello 
Segundas, 18:50h às 22:20h 
 
 
CONCEITO DE PROCESSO: REVISÃO 
• Instância de um 
programa em 
execução 
 
• É a unidade de 
carga e alocação de 
uma tarefa 
 
• Um programa é 
carregado para a 
memória onde aloca 
uma determinada 
área para código e 
dados 
NOVO 
Admissão 
Ocorrência 
do evento 
Dispatch 
Liberação 
Time-out 
Espera do 
evento 
PRONTO EXECUÇÃO 
SAÍDA 
BLOQUEADO 
MODELO DE 5 ESTADOS 
ESTADOS DE UM PROCESSO: REVISÃO 
THREADS: O QUE SÃO? 
• São fluxos de execução distintos dentro de um mesmo 
processo 
• São representadas graficamente da seguinte forma: 
Um processo 
Um thread 
Múltiplos processos 
Um thread por processo 
Um processo 
múltiplos threads 
Multiplos processos 
Múltiplos threads por processo 
THREADS: CARACTERÍSTICAS 
• Dentro de um mesmo 
processo, threads 
compartilham o mesmo 
contexto de software* e 
espaço de endereçamento 
com os demais, porém cada 
thread possui seu contexto 
de hardware 
• O TCB (Thread Control 
Block) armazena o contexto 
 
de hardware e algumas informações exclusivas* ao thread (prioridade, 
estado e bits de estado) 
 
THREADS: PARA QUE SERVEM? 
• Concorrência de forma mais eficiente (com partes 
diferentes de um processo) 
 
• Utilização de Múltiplos Processadores 
 
• Comunicação entre threads não envolve 
mecanismos lentos de intercomunicação entre 
processos (compartilham o mesmo espaço de 
endereçamento) => diminuição do overhead 
 
• Economia de tempo de gerenciamento 
 
 
• Implementadas pela aplicação e não 
pelo sistema operacional, que suporta 
apenas processos convencionais (com 
thread única) 
 
• As threads de usuário facilitam 
aspectos de portabilidade e são 
criadas e gerenciadas por uma 
biblioteca no nível do usuário 
THREADS EM MODO USUÁRIO (TMU) 
• O kernel não enxerga essas threads e, por esse motivo, não podem ser 
gerenciadas individualmente: se um thread utiliza uma chamada ao 
sistema que a coloca em estado de espera (operação de entrada), todo o 
processo é bloqueado; múltiplos threads em um processo não podem ser 
executados por processadores diferentes simultaneamente 
THREADS EM MODO KERNEL (TMK) 
• As threads de kernel são criadas e 
gerenciadas pelo kernel do sistema 
operacional, através de chamadas 
a rotinas do sistema 
 
• O sistema operacional reconhece 
a existência de cada thread e pode 
escaloná-las individualmente (com 
múltiplos processadores, execução 
simultânea) 
 
• Ocorrem muitas mudanças no 
modo de acesso, o que pode gerar 
queda no desempenho 
 
 P 
PROCESSOS LEVES 
 
 
• A combinação entre os dois 
tipos de threads promove 
uma associação entre 
threads de usuário (TMU) e 
de kernel (TMK), porém, a 
forma de associação 
depende do sistema 
operacional 
 
• Esta é a solução mais 
utilizada nos sistemas 
modernos 
 
 
int x = 10; 
 
int main () 
{ 
 int y; 
 y=soma(); 
 x = x+1; 
 cout << “x=” << x <<”\n”; 
} 
 
int soma () 
{ 
 x=x+1; 
 return x; 
} 
 
VARIÁVEL GLOBAL 
FUNÇÃO PRINCIPAL 
FUNÇÃO SOMA 
Resultado: x = 12 
PARA ENTENDER SEM DECORAR... 
 Thread 1 Thread2 
Linha 1 A= A * 2 B= B + 1 
Linha 2 B= B * 2 A= A + 1 
 
Caso 1: Thread 1 linha 1 e linha 2, thread 2 linha 1 e linha 2 
 Resultado final: A =3 B = 3 
Caso 2: Thread 2 linha 1 e linha 2, thread 1 linha 1 e linha 2: 
 Resultado final: A = 4 B= 4 
Caso3: Thread1 linha1, thread 2 linha1 e linha 2, thread1 linha 2 
 Resultado final: A = 3 B = 4 
 
ATENÇÃO: VEJA O QUE ACONTECE 
MAS, ATENÇÃO !!! 
 Thread 1 Thread2 
Linha 1 A= A * 2 B= B + 1 
Linha 2 B= B * 2 A= A + 1 
 
Caso 1: Thread 1 linha 1 e linha 2, thread 2 linha 1 e linha 2 
 Resultado final: A =3 B = 3 
Caso 2: Thread 2 linha 1 e linha 2, thread 1 linha 1 e linha 2: 
 Resultado final: A = 4 B= 4 
Caso3: Thread1 linha1, thread 2 linha1 e linha 2, thread1 linha 2 
 Resultado final: A = 3 B = 4 
 
O RESULTADO DEPENDE DA ORDEM DE EXECUÇÃO 
PROBLEMAS DA CONCORRÊNCIA!!!! 
EXCLUSÃO MÚTUA 
• Somente um processo por vez pode executar uma região 
crítica 
• Um processo interrompido fora de uma região crítica não 
pode impedir que outro processo tenha acesso a esta 
região crítica 
• Não pode haver nem deadlock nem starvation 
• Quando não houver processo executando uma região 
crítica qualquer processo que solicitar acesso deverá obtê-
lo imediatamente 
• Um processo deve permanecer executando uma região 
crítica por tempo finito 
• Nada pode ser assumido sobre a velocidade relativa e dos 
processos nem o número de processadores 
 
ERRO É ERRO ! 
Erro “intermitente” do sistema operacional? 
• Não existe erro intermitente de software 
• Não existe “mau contato” dentro de um programa . 
• Erro é erro e fim de papo. 
 
Motivos para este equívoco: 
• Estas situações podem se repetir ou não com 
frequência 
• Repetição do contexto é muito difícil 
 
CONCEITOS FUNDAMENTAIS 
• Condição de corrida 
 Eventos que geram resultados não determinísticos 
 
• Região crítica 
 Parte do código que utiliza recursos compartilhados 
 
• Exclusão Mútua 
 Mecanismo de proteção a uma região crítica 
 
CONCEITOS FUNDAMENTAIS 
• Condição de corrida 
 Eventos que geram resultados não determinísticos 
 
• Região crítica 
 Parte do código que utiliza recursos compartilhados 
 
• Exclusão Mútua 
 Mecanismo de proteção a uma região crítica 
 ENTRAR_RC() 
 Código da região crítica 
SAIR_RC() 
COMO FUNCIONA 
 
 
 ENTRAR_RC() Espera ocupada 
 OU 
 bloqueio 
 Código da região crítica 
 
 
 SAIR_RC() Liberação do recurso 
 
NA VIDA REAL  
Processo 1 
1 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
NA VIDA REAL  
Processo 1 
1 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
COMPARTILHADO 
NA VIDA REAL  
Processo 1 
1 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
(1) 
NA VIDA REAL  
Processo 1 
1 
PROC 1 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
(2) 
NA VIDA REAL  
Processo 1 
2 
PROC 1 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
(3) 
NA VIDA (mais) REAL  
Processo 1 
1 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
(1) 
Processo 2 
Processo 1 
1 
PROC 1 
PROC 0Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
(2) 
NA VIDA (mais) REAL  
Processo 2 
Processo 1 
1 
PROC 1 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
(2) 
NA VIDA (mais) REAL  
Processo 2 
TROCA DE CONTEXTO! 
Processo 1 
1 PROC 1 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
NA VIDA (mais) REAL  
Processo 2 
(1) 
Processo 1 
1 PROC 2 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
NA VIDA (mais) REAL  
Processo 2 
(1) 
(2) 
Processo 1 
2 PROC 2 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
NA VIDA (mais) REAL  
Processo 2 
(1) 
(2) 
(3) 
Processo 1 
2 
PROC 2 
PROC 0 
Para imprimir: 
(1) Ler posição livre da fila 
(2) Incluir o arquivo na posição indicada 
(3) Atualizar próxima posição livre 
 
3 
 
2 
 
1 
 
0 
PRÓXIMA LIVRE 
(3) 
NA VIDA (mais) REAL  
Processo 2 
O que aconteceu? 
– PROC2 imprimiu 
– Para o sistema operacional não houve erro 
– Para o PROC1 também não houve erro mas... 
 
NÃO IMPRIMIU! 
NA VIDA (mais) REAL  
 
CADÊ O PAPEL? 
 
SOLUÇÃO 
 
ENTRAR_RC() 
 Ler posição livre da fila 
 Incluir o arquivo na posição indicada 
 Atualizar próxima posição livre 
SAIR_RC() 
 ENTRAR_RC() 
 Código da região crítica 
SAIR_RC() 
EXCLUSÃO MÚTUA 
• Somente um processo por vez pode executar uma região 
crítica 
• Um processo interrompido fora de uma região crítica não 
pode impedir que outro processo tenha acesso a esta 
região crítica 
• Não pode haver nem deadlock nem starvation 
• Quando não houver processo executando uma região 
crítica qualquer processo que solicitar acesso deverá obtê-
lo imediatamente 
• Um processo deve permanecer executando uma região 
crítica por tempo finito 
• Nada pode ser assumido sobre a velocidade relativa e dos 
processos nem o número de processadores 
 
EFEITOS COLATERAIS 
• Deadlock : Impasse 
 
 
 
 
 
• Starvation 
 
P2 
P1 
R1 
R2 
Situação em que dois ou mais processos entram em um impasse 
aguardando um recurso que nunca estará disponível. Esta situação 
só é desfeita por um agente externo (que interrompe um dos 
processos) 
EFEITOS COLATERAIS 
• Deadlock 
 
• Starvation: Adiamento 
 
P1 P2 
R1 
P3 
Condição em que não há garantia 
de execução de um processo. A 
execução pode ser adiada por um 
tempo indeterminado 
EFEITOS COLATERAIS 
• Deadlock 
 
• Starvation: Adiamento 
 
P1 P2 
R1 
P3 
EFEITOS COLATERAIS 
• Deadlock 
 
• Starvation: Adiamento 
 
P1 P2 
R1 
P3 
EFEITOS COLATERAIS 
• Deadlock 
 
• Starvation: Adiamento 
 
P1 P2 
R1 
P3 
EFEITOS COLATERAIS 
• Deadlock 
 
• Starvation: Adiamento 
 
P1 P2 
R1 
P3

Outros materiais