Threads e Concorrência em Sistemas Operacionais

Prévia do material em texto

*
*
SISTEMAS OPERACIONAIS
SIMONE MARKENSON
Rio de Janeiro, maio de 2011
CONTEÚDO DA AULA
*
REVISÃO: THREADS
São fluxos de execução distintos dentro de um mesmo processo.
É a unidade de execução de um sistema com suporte a threads.
Threads de um mesmo processo compartilham espaço de endereçamento mas possuem contextos de hardware distintos.
Podem ser consideradas funções “com vida própria”.
*
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
*
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!!!!
*
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
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
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
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
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
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
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
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
*
Processo 1
1
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
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
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
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
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
*
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
*
DEADLOCK OU STARVATION?
*
SOLUÇÕES? 
NA PRÓXIMA AULA !
*