Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sincronismo de Processos e Threads - Coggle Diagram
Sincronismo de Processos e Threads
Antecedentes
O Problema do Produtor/Consumidor
é um paradigma comum para os processos cooperativos
Um processo produtor produz informações
que são consumidas por um processo consumidor
Suponha uma região de memória
compartilhada (um buffer)
onde o produtor
deposita os itens produzidos
a fim de que o consumidor consuma esses itens
Um produtor pode produzir enquanto um
consumidor está consumindo
mas é preciso
haver uma sincronização
para que o consumidor não tente consumir um item que ainda não foi produzido
Suponha um buffer de tamanho limitado
o produtor precisa esperar se o buffer já
estiver cheio
e o consumidor precisa esperar caso
o buffer esteja vazio
Solução para um problema que
preencha todo o buffer
um contador inteiro que acompanha o número de
buffers cheios
o contador é definido
como 0
Ele é incrementado pelo produtor depois
de produzir um novo buffer
e é decrementado pelo consumidor depois de consumir um buffer
Condição de Corrida (Race Condition)
situação em que vários processos acessam e manipulam os mesmos dados concorrentemente
e o resultado da execução depende da ordem específica em que ocorre o acesso
O Problema da Seção Crítica
é projetar um protocolo que processos possam utilizar para a cooperação
Seção crítica (SC) ou região crítica (RC)
Um segmento de código que pode alterar
dados comuns a vários processos/threads
Só se pode garantir a consistência dos dados
compartilhados
se apenas um processo por
vez adentrar a sua seção crítica
Um processo precisa solicitar
permissão para entrar em sua seção crítica
Seção de entrada
Seção de código que implementa essa solicitação
Seção de saída
A seção crítica pode ser seguida por uma seção de saída
Seção remanescente
O código restante
Três requisitos obrigatórios de uma boa solução
Exclusão Mútua
Enquanto um processo estiver executando sua RC, outros processos não poderão executar suas RCs. É sempre UM por VEZ.
Progresso
se um processo está na seção remanescente é porque ele já executou sua RC e/ou não tem intenção de entrar novamente
esse processo não poderá bloquear outro
processo de entrar na RC
Espera limitada
nenhum processo pode ter que esperar eternamente para entrar em sua seção crítica ou lá ficar eternamente
Kernel COM ou SEM Preempção?
Kernels com preempção (preemptive kernels)
permite que um processo seja interceptado enquanto está sendo executado em modalidade de kernel
Kernels sem preempção (nonpreemptive kernels)
não permite que um processo sendo executado em modalidade de kernel seja interceptado
Vantagens
Livre de condições de corrida!
Desvantagens
Não tem as vantagens de um kernel com preempção
(a questão do
tempo de resposta)
Soluções para o Problema da Seção Crítica
A questão do busy wait
Busy wait = espera ativa ou espera ocupada
Tipos de Soluções
Soluções de Hardware
Inibição de interrupções
Usa um par de instruções do tipo DI / EI
DI = Disable Interrupt
EI = Enable Interrupt
O processo desativa todas as interrupções
imediatamente antes de entrar na sua RC
reativando-as imediatamente depois de sair dela
Com as interrupções desativadas, nenhum processo que está na sua RC pode ser interrompido
o que garante o acesso exclusivo
aos dados compartilhados
Problemas da Solução DI/DE
É desaconselhável dar aos processos de usuário o poder de desabilitar interrupções
Não funciona com vários processadores
Inibir interrupções por um longo período de tempo pode ter consequências danosas
Instrução TSL (apresenta busy wait)
TSL = “Test and Set Lock”
Solução de hardware para o problema da exclusão
mútua em ambiente com vários processadores
O processador que executa a TSL bloqueia o
barramento de memória
impedindo que outras CPUs acessem a MP até que a instrução tenha terminado
A instrução TSL faz o seguinte
Lê o conteúdo de um endereço de memória
para um registrador e armazena um valor diferente de zero
Se lock = 0 ⇒ RC livre
Se lock = 1 ⇒ RC ocupada
A instrução TSL é executada de forma atômica.
indivisíveis, sem interrupção
Vantagens da TSL
Simplicidade de uso
Não dá aos processos de usuário o poder de desabilitar interrupções
Presente em quase todos os processadores atuais
Funciona em máquinas com vários processadores
Desvantagens
Espera ocupada (busy wait)
Possibilidade de postergação infinita (starvation)
Soluções de software com busy wait
Algoritmo de Peterson
O truque do algoritmo consiste no seguinte
Ao marcar a sua intenção de entrar, o processo já indica (para o caso de empate) que a vez é do outro
atende aos três requisitos para uma boa solução
Soluções de software com bloqueio
Primitivas Sleep/Wakeup
A ideia desta abordagem é bloquear a execução dos processos quando a eles não é permitido entrar em suas regiões críticas
Isto evita o desperdício de tempo de CPU, como nas soluções com busy wait
sleep()
Bloqueia o processo e espera por uma sinalização
suspende a execução do processo que fez a
chamada até que um outro o acorde
wakeup()
Sinaliza (acorda) o processo anteriormente bloqueado por sleep().
O Problema do Produtor e Consumidor c/ Buffer
Limitado
Uma Condição de Corrida
Semáforos
Ferramenta de sincronismo que não exige espera ocupada
Semáforo S – variável inteira
Duas operações padrão modificam S
acquire()
Também chamada de wait(), P() ou down()
Decrementa a variável, indicando a “ocupação do semáforo”
release()
Também chamada de signal(), V() ou up()
Incrementa a variável, indicando a “liberação do semáforo”
Menos complicado
Só pode ser acessado por duas operações indivisíveis
Mutex (mutual exclusion) ou semáforos binários
Quanto um semáforo só pode assumir os valores 0 ou 1
lock(mutex)
unlock(mutex).
Monitores
Algumas situações que necessitam de monitores
Troca da ordem em que são executadas as
operações de wait() e signal() num mutex
Substituição de signal() por wait()
Omissão de um wait() ou signal(), ou ambos
Tornar obrigatória a exclusão mútua
Codificar as seções críticas como procedimentos do monitor
Resultado: o código da seção crítica não é mais duplicado em cada processo
Problemas Clássicos de Sincronismo
Problema dos Leitores e Escritores
Os leitores podem ter acesso simultâneo aos
dados compartilhados
Os escritores podem apenas ter acesso
exclusivo aos dados compartilhados
um escritor só escreve se não houver nenhum
leitor lendo ou escritor escrevendo
Problema dos Filósofos Glutões
Considere cinco filósofos que passam
a vida a comer e a pensar
Eles compartilham uma mesa
circular, com um prato de arroz ao centro
Na mesa existem cinco pauzinhos,
colocados um de cada lado do filósofo
Quando um filósofo fica com fome
ele pega os dois pauzinhos mais próximos
um de cada vez, e come
até ficar saciado
Quando acaba de comer, ele repousa os pauzinhos e volta a pensar
Introdução
Processo cooperativo
Pode afetar ou ser afetado
por outros processos em execução no sistema