Sistemas Operacionais - kusumoto.com.br Operacionais Prof. André Y. Kusumoto ... • Cada thread tem um segmento de código, chamado região crítica, no qual o thread pode ... •

Sistemas Operacionais

Prof. André Y. [email protected]

Prof. André Y. Kusumoto – [email protected]

Sincronização de Processos

FundamentosParadigma do produtor-consumidor

• As rotinas produtor e consumidor podem não funcionar corretamente quando forem executadas ao mesmo tempo.

• Porque os threads compartilham a mesma variável count (contador de itens no buffer)

• Ex. O valor atual da variável count seja 5, e que os threads produtor e consumidor executem as instruções ++count e –-count de forma concorrente.

• Após a execução dessas duas intruções, o valor da variável count pode ser 4, 5 ou 6.

Produtor Consumidor

while (count == BUFFER_SIZE); //no-op

//adiciona um item no buffer++count;buffer[in] = item;in = (in + 1) % BUFFER_SIZE;

while (count == 0); //no-op

--count;item = buffer[out];out = (out + 1) % BUFFER_SIZE;

2/14



O problema da seção crítica• Como primeiro método para controlar o acesso a um recurso compartilhado,

declaramos uma seção de código como sendo crítica; em seguida, controlamos o acesso a essa região.

• Considere um sistema que consista em n threads {T0, T1, ....., Tn-1}.

• Cada thread tem um segmento de código, chamado região crítica, no qual o thread pode estar alterando variáveis comuns, atualizando uma tabela, gravando um arquivo, etc.

• Quando um thread estiver executando em sua região crítica, nenhum outro thread terá permissão de executar em sua seção crítica.

• Assim, a execução das seções críticas pelos threads é mutuamente exclusiva no tempo.

3/14



Uma solução ao problema da seção crítica deve satisfazer os três requisitos seguintes:

• Exclusão mútua: se o thread Ti estiver executando em sua seção crítica, nenhum outro thread poderá estar executando em sua respectiva seção crítica.

• Progresso: nenhum processo executando fora da sua seção crítica pode impedir que outro processo entre na sua seção crítica.

• Espera limitada: nenhum processo pode esperar eternamente para entrar na sua seção crítica. Isso evita a starvation de qualquer thread único.

4/14



Semáforos• Um semáforo é uma estrutura de dados que consiste em um número inteiro e em uma fila

• Seu objetivo é coordenar o acesso a uma região crítica

• Um semáforo S é uma variável inteiro positiva sobre a qual os processos podem fazer duas operações primitivas (indivisíveis) - P(S) e V(S).

• P e V têm sua origem das palavras parsen (passar) e e vrygeren (liberar)).

• Cada semáforo tem uma fila associada a ele, onde processos bloqueados nele esperam.

• Quando um processo executa a operação P em um semáforo, o seu valor inteiro é decrementado.

• Caso o novo valor do semáforo seja negativo, o processo é bloqueado e ele vai pro fim da fila.

• Quando um processo executa a operação V, o seu valor inteiro é incrementado.

• Caso exista algum processo bloqueado na fila desse semáforo, o primeiro processo da fila é liberado.

5/14



SemáforosObserve o funcionamento através do semáforo S:

P(S):

S.valor = S.valor - 1;

Se S.valor < 0

Então bloqueia o processo, insere em S.fila

V(S):

S.valor = S.valor + 1;

Se S.fila não está vazia

Então retira processo P de S.fila, acorda P

• Operações P e V devem ser atômicas

• Para cada estrutura de dados compartilhada, deve ser criado um semáforo S inicializado com o valor 1.

• Todo processo, antes de acessar essa estrutura, deve executar um P(S). Ao sair da seção crítica, o processo executa V(S).

6/14



Variações muito comuns de semáforos são as construções mutex ou semáforo binário.

• valores 0 e 1, livre e ocupado, lock e unlock.

lock(x):

Se x está livre

Então -> marca x como ocupado

Senão -> insere processo no fim da fila “x”

unlock(x):

Se fila “x” está vazia

Então -> marca x como livre

Senão -> libera processo do início da fila “x”

7/14


Problemas clássicos de sincronização

Problema dos leitores-escritores

• Um banco de dados deve ser compartilhado entre vários threads concorrentes.

• Alguns desses threads talvez queiram apenas ler o banco de dados, enquanto outros talvez queiram atualiza-lo (ou seja, ler e gravar dados).

• Fazemos a distinção entre esses dois tipos de threads chamando os primeiros de leitores e os últimos de escritores.

• Obviamente, se dois leitores acessarem os dados compartilhados ao mesmo tempoNo entanto, se um escritor e algum outro thread (leitor ou escritor) acessar o banco de dados ao mesmo tempo, poderá haver confusão.

• Para evitar esse tipo de problema, os escritores deverão ter acesso exclusivo ao banco de dados compartilhado. Esse requisito leva ao problema dos leitores-escritores.

8/14



Problema dos leitores-escritores

• Um sistema de reserva de passagens aéreas é um bom exemplo.

• Os leitores são aqueles que apenas lêem as informações, sem alterá-las

• Os escritores são aqueles que desejam reservar um lugar em determinado vôo.

• O sistema não poder permitir que alguém escreva enquanto outra pessoa esteja lendo (ou escrevendo). Portanto, é preciso implementar uma política de exclusão mútua.

• Uma solução trivial para esse problema consistiria em proteger o acesso à área compartilhada com um semáforo inicializado em 1

• Essa solução deixa a desejar em termos de desempenho, porque restringe desnecessariamente o acesso dos leitores à área compartilhada.

• A utilização de priorização de leitores pode resultar no abandono dos escritores, quanto que a priorização de escritores pode resultar no abandono dos leitores.

9/14



• Procurando evitar esse tipo de ocorrência, foi proposta uma combinação de prioridades.

• Assim que um escritor termina, todos os leitores em espera recebem permissão para execução. Em seguida, assim que o grupo de leitores termina, o escritor que está esperando pode começar, e nenhum dos novos leitores que chegaram poderá começar até que o escritor termine.

10/14



Problema do Jantar dos Filósofos• Considere cinco filósofos que passam suas vidas

meditando e comendo. • Os filósofos compartilham uma mesa redonda comum

cercada por cinco cadeiras, cada qual pertence a um filósofo.No centro da mesa, está uma tigela de arroz, e a mesa está posta com cinco pauzinhos (hashi).

• Quando um filósofo medita, não interage com seus colegas. De vez em quando, um dos filósofos fica com fome e tenta pegar os dois pauzinhos mais próximos de si (os pauzinhos que estão entre ele e seus colegas da esquerda e da direita).

• Um filósofo só pode pegar um pauzinho de cada vez. Obviamente, não poderá pegar um que já esteja na mão de um colega. Quando o filósofo com fome está de posse dos dois pauzinhos ao mesmo tempo, ele poderá comer sem soltá-los. Quando termina de comer, o filósofo solta os pauzinhos e volta a meditar.

• O problema do jantar dos filósofos é considerado um problema clássico de sincronização.

11/14



• Uma solução simples consiste em representar cada pauzinho por um semáforo. Um filósofo tenta agarrar o pauzinho executando uma operação P naquele semáforo; o filósofo solta o pauzinho executando a operação V.

• Essa solução deve ser rejeitada porque tem a possibilidade de criar um deadlock - todos os cinco filósofos fiquem com fome ao mesmo tempo, e cada um pegue o pauzinho à sua esquerda. Quando um filósofo tentar pegar o pauzinho a sua direita, ficará esperando para sempre.

• Várias soluções possíveis para o impasse são listadas a seguir. Essas soluções evitam o deadlock, impondo restrições aos filósofos:• Permitir a presença de no máximo quatro filósofos ao mesmo tempo na mesa.

• Permitir que um filósofo pegue o seu pauzinho apenas se os dois pauzinhos estiverem disponíveis.

• Usar uma solução assimétrica; por exemplo, um filósofo impar pega primeiro o pauzinho a sua esquerda e depois o da sua direita, enquanto um filósofo par pega o da direita e depois o da esquerda.

• Qualquer solução satisfatória ao problema do jantar dos filósofos deverá evitar a possibilidade de um dos filósofos morrer de fome (starvation).

12/14



Monitores• Estruturas de sincronização de alto nível. • Parecidos com classes• Um monitor é um conjunto de procedimentos, variáveis e estruturas de dados, todas

agrupadas juntas em um módulo especial.• As implementações existentes de monitores fazem parte de algumas linguagens de

programação.

monitor Regiao_Critica;integer i;PROCEDURE produtor(x);..end;PROCEDURE consumidor(x);..end;

end monitor;

13/14



• Os monitores têm uma propriedade muito importante que os torna úteis na implementação da exclusão mútua: somente um processo pode estar ativo dentro do monitor em um dado instante de tempo.

• Quando um procedimento chama um procedimento de um monitor, as primeiras instruções verificam se algum outro processo está ativo dentro dele. Se isto for verdade, o processo que chamou o procedimento do monitor será suspenso até que o outro processo deixe o monitor. Se não houver nenhum processo ativo dentro do monitor, o processo que chamou o procedimento do monitor poderá entrar e executar o procedimento chamado.

14/14

Documents

Sistemas Operacionais - kusumoto.com.br Operacionais Prof. André Y. Kusumoto ... • Cada thread tem um segmento de código, chamado região crítica, no qual o thread pode ... •