Aula04SO

Disciplina:Sistemas Operacionais6.431 materiais158.618 seguidores
Pré-visualização2 páginas
Aula 4 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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(“Eu sou o filho\n”);
	else {
		printf(“Eu sou o pai\n”);
		wait(0);		
	}
}

Aula 4 – Concorrência
*
Sistemas Operacionais – 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 “aparente” (concorrência): máquinas monoprocessadoras
Execução simultânea versus estar “em estado de execução simultaneamente

Aula 4 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – Jorge Luiz de Castro e Silva

Programação Concorrente (2)
Desvantagens da programação concorrente
Programação complexa
Aos erros “comuns”se 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 – Concorrência
*
Sistemas Operacionais – Jorge Luiz de Castro e Silva

Programação Concorrente (3)
Aplicações concorrentes
Sincronização e comunicação entre processos

Aula 4 – Concorrência
*
Sistemas Operacionais – Jorge Luiz de Castro e Silva

Como expressar paralelismo (1)

Aula 4 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 “impressões”
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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas Operacionais – 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 – Concorrência
*
Sistemas