Aula04SO

Aula04SO


DisciplinaSistemas Operacionais I7.677 materiais168.599 seguidores
Pré-visualização2 páginas
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Universidade Estadual do Ceará
Curso de Ciência da Computação
Sistemas Operacionais
Prof. Dr. Jorge Luiz de Castro e Silva
Aula 4
Concorrência
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Sumário
Introdução
Aplicações concorrentes
Especificação de concorrência em programas
Problemas de compartilhamento de recursos
Exclusão mútua
Sincronização condicional
Semáforos
Monitores
Troca de mensagens
Deadlock
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Como criar processos no Linux?
#include <stdio.h>
#include <unistd.h>
int main() {
	int pid;
	pid = fork();
	if (pid == 0) // processo filho
		printf(\u201cEu sou o filho\n\u201d);
	else {
		printf(\u201cEu sou o pai\n\u201d);
		wait(0);		
	}
}
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Concorrência (1) 
Programa executado por apenas um processo é dito ser um programa sequencial
Existe apenas um fluxo de controle
Programa concorrente é executado por diversos processos que cooperam entre si para realizaçào de uma tarefa (aplicação)
Existem vários fluxos de controle
Necessidade de interação para troca de informações (sincronização)
Emprego de termos
Paralelismo real: só ocorre em máquina multiprocessadoras
Paralelismo \u201caparente\u201d (concorrência): máquinas monoprocessadoras
Execução simultânea versus estar \u201cem estado de execução simultaneamente 
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Concorrência (2) 
 Paralelismo
execução simultânea em mais
de um processador
Concorrência
disputa pelo uso do processador
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Programação Concorrente (1) 
Composta por um conjunto de processos seqüenciais que se executam concorrentemente
Processos disputam recursos comuns
P.ex. variáveis, periféricos, etc.
Um processo é dito ser cooperante quando é capaz de afetar, ou ser afetado, pela execução do outro
Motivação da programação concorrente
Aumento de desempenho
Permite a exploração do paralelismo real disponível em máquinas multiprocessadoras
Sobreposição de operações de E/S com processamento
Facilidade de desenvolvimento de aplicações que possuem um paralelismo intrínsico
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Programação Concorrente (2) 
Desvantagens da programação concorrente
Programação complexa
Aos erros \u201ccomuns\u201dse adicionam erros próprios ao modelo
Diferenças de velocidade relativas de execução dos processos
Aspecto não-determinístico
Difícil depuração
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Programação Concorrente (3)
Aplicações concorrentes
Sincronização e comunicação entre processos
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Como expressar paralelismo (1) 
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Como expressar paralelismo (2) 
Foi criada por dijkstra. É uma construção de mais alto nível que fork e mais fácil de ser usada. 
A primitiva parend funciona como um ponto de sincronização (barreira)
 
Processo A
parbegin;
tarefa B;
tarefa C;
parend
Processo B
Processo C
bloqueado
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Como expressar paralelismo (3) 
O programa usa comando concorrente para fazer uma cópia de um arquivo f para um arquivo g. 
 
FILE f, g;
char buffer0[4096];
char buffer1[4096];
int i, j, k;
void main() {
	i = read(f, &buffer0, 4096); 
	while (I > 0) {
		for (j=0; j<4096; j++)
 			buffer1[j] = buffer0[j];
		parbegin
			k = write(g, &buffer1, 4096);
			i = read(f, &buffer0, 4096);
		parend;
	}
}
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Prob. de Compartilhamento 
de Recursos (1)
PROGRAM Conta_Corrente;
 .
 .
 READ (Arq_Contas, Reg_Cliente);
 READLN (Valor_Dep_Ret);
 Reg_Cliente.Saldo := 
 Reg_Cliente.Saldo + Valor_Dep_Ret;
 WRITE (Arq_Contas, Reg_Cliente);
 .
 .
END.
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Prob. de Compartilhamento 
de Recursos (2)
 
Processo A Processo B
X := X + 1; X := X - 1;
Processo A Processo B 
LOAD x,Ra LOAD x,Rb
ADD 1,Ra SUB 1,Rb
STORE Ra,x STORE Rb,x
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Conceitos
Condição de corrida (race condition)
Situação que ocorre quando vários processos manipulam o mesmo conjunto de dados concorrentemente e o resultado depende da ordem em que os acessos são feitos
 Região ou Seção Crítica
Segmento de código que implementa o acesso a um recurso compartilhado, ou seja, parte do código no qual um processo realiza a alteração de um recurso compartilhado
Exclusão mútua
Mecanismo que impede o uso simultâneo de um recurso compartilhado
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Exclusão mútua
Somente um processo por vez pode executar uma região crítica
Um processo interrompido fora da RC não pode impedir o acesso por outro processo
Não pode haver nem deadlock nem starvation
Quando não há processo executando uma RC, qualquer processo que solicitar acesso deve obtê-lo imediatamente
Um processo deve permanecer na RC por tempo finito
Não podemos fazer previsões com base na velocidade relativa dos processos
		
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Problema produtor-consumidor (1) 
Relação produtor-consumidor é uma situação bastante comum em Sistemas Operacionais
Servidor de impressão:
Processos usuários produzem \u201cimpressões\u201d
Impressões são organizadas em uma fila a partir da qual um processo (consumidor) os lê e envia para a impressora
P1
Pn
P2
Pc
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Problema produtor-consumidor (2) 
Suposições:
Fila de impressão é um buffer circular
Existência de um ponteiro (in) que aponta uma posição onde a impressão é inserida para aguardar o momento de ser efetivamente impressa
Existência de um ponteiro (out) que aponta para a impressão que está sendo realizada
5
4
3
2
1
P1
P2
Pc
in
out
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Problema produtor-consumidor (3) 
Seqüência de operações:
P1 vai imprimir; lê o valor de in (5); perde processador
P2 ganha processador; lê o valor de in (5); insere arquivo; atualiza in (6)
P1 ganha processador; insere arquivo (5); atualiza in (7)
Estado incorreto
Impressão de P1 é perdida
Na posição 6 não há uma solicitação válida de impressão
7
6
5
4
3
2
1
P1
P2
Pc
in
out
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Exclusão Mútua
Abordagem de Hardware
Instruções TSL
Inabilitar interrupções
2.	Abordagem de Software
Algoritmos de espera ocupada
	
3. Através do Sistema Operacional/Linguagens
Semáforos
Monitores
Troca de mensagens
FORMA GERAL
 ENTRA _RC
	<R.C.>
 SAI_RC
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Inibir interrupções
 Impede que o processo seja interrompido
Não funciona em sistemas multiprocessados
Problemas com a integridade do sistema
EXEMPLO: 	CLI
		 <RC>
		STI
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Instruções TSL
Instruções especiais
Execução atômica
Simples de utilizar
Utiliza espera ocupada
Possibilidade de starvation; 
seleção arbitrária
Exclusividade no uso do barramento para multiprocessadores
ENTRA_RC
 
	TSL RX,LOCK
	CMP RX , #0
	JNE ENTRA_RC
 
	RET
 
 
SAI_RC
 
	MOV LOCK , #0
	RET
Aula 4 \u2013 Concorrência
*
Sistemas Operacionais \u2013 Jorge Luiz de Castro e Silva
Algoritmo de Dekker
 Problemas
estrita alternância
viola característica 2 de um mecanismo de exclusão mútua
Aula 4 \u2013 Concorrência
*
Sistemas