SOP 02 ExclusaoMutua02

1Pearson Education Sistemas Operacionais Modernos – 2ª Edição

Processos e Processos e ThreadsThreads

Sistemas Operacionais (SOP-Sistemas Operacionais (SOP-BCC)BCC)

BB

De: De: Andrew S. Tanenbaum Andrew S. Tanenbaum Tradução: Tradução: Ronaldo A.L. GonçalvesRonaldo A.L. Gonçalves

Luís A. ConsuladoLuís A. Consulado

Responsável pela disciplina:Responsável pela disciplina: Prof. Dr. Maurício Aronne PillonProf. Dr. Maurício Aronne Pillon

Curso de Ciência da ComputaçãoCurso de Ciência da Computação


Exclusão Mútua com diretivas sleep e wakeup


Dormir e Acordar

• Não baseia-se no princípio da

espera ociosa.

– Gasto de CPU

– Efeitos inesperados (problema da

inversão de prioridade)

i

• Princípio do bloqueio (sleep e

wakeup).


Problema do produtorconsumidor (c/ Sleep/Wakeup)

c

• Dois ou mais processos compartilham um

buffer comum e de tamanho fixo;

• Produtor põe informação no buffer;

• Consumidor retira informação do buffer;

• O que fazer quando:

– o produtor quiser colocar mais informações e

o buffer estiver cheio?

– o consumidor quiser retirar mais informações e

o buffer estiver vazio?


Problema do produtorconsumidor (c/ Sleep/Wakeup)

c

• Condição de disputa no count;

– Buffer esta vazio;

– Consumidor lê o buffer e verifica o valor 0, é

interrompido;

– Produtor executa, incrementa o count;

– Produtor dispara sinal de wakeup (count esta

em 0);

– Consumidor ainda não esta adormecido,

portanto sinal é perdido.

• Bit de espera pelo sinal de acordar.


Dormir e Acordar

Problema do produtorconsumidor com uma condição de disputa fatal


Semáforos• Uma variável que conta o número de sinais de

acordar (0 se não houver; caso contrário valor

positivo)

p

• As operações do semáforos são como ação

atômica:

• Down (P): verifica se o valor é maior que 0;

– Se for o caso, decrementa de 1 e prossegue;

– Senão ele é posto para dormir sem terminar o down.

• Up (V): incrementa o valor de um semáforo;

Caso haja mais de um processo dormindo, o

sistema escolheria um deles para acordar

(prosseguir).


Implementando

Semáforos• Implementação de forma indivisível

– Desabilitando as instruções

– Variável de Impedimento com o

auxílio de instruções TSL p/ múltiplas

CPUs;


Produtor-Consumidor c/

semáforos• Full – conta o número de lugares preenchidos;

• Empty – conta o número de lugares vazios;

• Mutex – garante que o produtor e consumidor não

terão acesso ao buffer ao mesmo tempo;

– Valores iniciais: Full = 0; Empty = nMax; mutex

= 1;

– Semáforos que iniciam em 1 e são usados por

dois ou mais processos são chamados de

semáforos binários;


Semáforos

O problema do produtorconsumidor usando semáforos


Exercício• Considere o conjunto de execução de três processos

conforme descrito abaixo que compartilham duas variáveis do tipo semáforo:

» semaphore U = 3; semaphore V = 0;

» [Process 1] [Process 2] [Process 3]

» L1:down(U) L2:down(V) L3:down(V)

L

» Printf ("C") printf("A") printf("D")

P

» up(V) printf("B") goto L3

» goto L1 up(V)

g

» goto L2


Exercício - Responda

(1)Quantas vezes a letra C aparecerá na tela? Explique.

(2)Quantas vezes a letra D aparecerá na tela?

Explique.

(3)Qual o menor número de vezes que a letra A

poderá ser escrita na tela? Explique.

(4)A seguinte seqüência de letras é uma saída

possível - CABABDDCABCABD?


Mutexes• É uma versão simplificada do semáforo;

• Úteis em pacotes de threads implementados

em espaço usuário;

• Mutex – variável que pode ocupar dois

estados: desimpedido (valor 0) e impedido;

– mutex_lock e mutex_unlock


Mutexes• Facilmente implementado caso haja instrução TSL

disponível;

• Mais eficiente do que enter_region/leave_region

pois não trabalha com espera ocupada.

• Quando falha em verificar a variável de

impedimento mutex_lock chama thread_yield;

• Não necessita de chamada ao núcleo;


Mutexes

Implementação de mutex_lock e mutex_unlock


Monitores• No problema do produtor-consumidor

implementado com semáforo: inverter down

mutex com down empty; (Deadlock)

• Monitor: unidade básica de sincronização de

alto nível.

• Compilador implementa a exclusão mútua

(mutex ou semáforo) para os procedimentos

declarados no monitor.


Monitores

• Princípio básico para o desenvolvedor: converter

todas as regiões críticas em procedimentos no

monitor;

• Como bloquear processos com monitores?

– Variáveis condicionais (wait e signal):

• Produtor c/ buffer cheio (wait full)

• Consumidor retira um produto (produtor em

wait), então signal full;


Monitores

• Proposta de Brinch Hansen: o processo que

lançar o Signal deve imediatamente sair do

monitor;

• A diferença entre Sleep/Wakup e monitor é que

monitor garante um processo só pode estar em

um estado (dormindo ou acordado).

• Synchronized monitor em Java


Monitores (1)

M

Exemplo de um monitor


Monitores (2)

M

• Delineamento do problema do produtorconsumidor com monitores• somente um procedimento está ativo por vez no monitor

– o buffer tem N lugares


Monitores (3)

M


Troca de Mensagens

• Métodos de sincronização vistos até agora

funcionam para máquinas com memória

compartilhada;

• Baseia-se em duas diretivas (chamadas ao

sistema): send e receive.


Troca de Mensagens

• Problema: mensagens perdidas na rede;

• Sugestão: confirmação de recebimento;

– Problema: recebimento duplicado;

– Solução: número de controle na mensagem;

• O servidor/cliente não é um impostor?

(autenticação)

• Send/Receive na mesma máquina: desempenho;


Troca de Mensagens

O problema do produtorconsumidor com N mensagens


Barreiras

• Uso de uma barreiraa) processos se aproximando de uma

barreirab) todos os processos, exceto um,

bloqueados pela barreirac) último processo chega, todos passam

Documents

SOP 02 ExclusaoMutua02