Sincronização entre Processos e Condições de Corrida

Threads Sincronização entre processos Sincronização entre processos Processos cooperantes precisam se comunicar por troca de Mensagens ou variáveis compartilhadas Memória Compartilhada P0 P1 Sincronização entre processos Acessos concorrente a variáveis compartilhadas podem resultar inconsistência de dados Precisamos então de um mecanismo que garanta execução correta dos processos cooperantes que compartilham dados ProdutorConsumidor Condição de corrida Condição de Corrida Quando vários processos acessam o mesmo dado compartilhado concorrentemente e o resultado da execução depende da ordem na qual os acessos ocorrem é chamada de condição de corrida Condição de Corrida Para evitar condições de corrida Somente um processo por vez manipula o dado compartilhado Para isso usamos mecanismos de sincronização de processo Seção crítica Seção crítica Seja um sistema com n processos e cada processo possui um trecho de código em que o processo manipula recursos compartilhados variáveis memória arquivos no disco dispositivo de ES então chamamos essa região de seção crítica Seção crítica Desejase que quando um processo está executando sua seção crítica nenhum outro processo pode estar executando sua seção crítica Isto é desejase que a execução das seções críticas pelos processos seja mutuamente exclusiva no tempo Seção crítica O problema da seção crítica consiste em projetar um protocolo que os processos usem para garantir a exclusão mútua 1 Cada processo antes de entrar na sua seção crítica deve pedir permissão O trecho de código que implementa este pedido é a seção de entrada Seção crítica O problema da seção crítica consiste em projetar um protocolo que os processos usem para garantir a exclusão mútua 1 Cada processo antes de entrar na sua seção crítica deve pedir permissão O trecho de código que implementa este pedido é a seção de entrada 2 Cada processo quando sai da sua seção crítica deve comunicar sua saída O trecho que implementa este comunicado é a seção de saída Seção crítica O problema da seção crítica consiste em projetar um protocolo que os processos usem para garantir a exclusão mútua 1 Cada processo antes de entrar na sua seção crítica deve pedir permissão O trecho de código que implementa este pedido é a seção de entrada 2 Cada processo quando sai da sua seção crítica deve comunicar sua saída O trecho que implementa este comunicado é a seção de saída 3 O restante do código é a seção restante Seção crítica while not fim do seção de entrada seção crítica seção de saída seção restante Requisitos para a solução da seção crítica Requisitos para a solução do problema da seção Crítica Uma solução para o problema da seção crítica deve satisfazer 3 requisitos 1 Exclusão mútua 2 Progresso 3 Espera limitada Exclusão mútua Se Pi está executando na sua seção crítica então nenhum outro processo pode estar executando na seção crítica dele Progresso Se nenhum processo está na seção crítica e existem alguns processos que desejam entrar na seção crítica Então somente aqueles processo que não estão na seção restante podem participar na decisão de qual vai entrar na seção crítica Espera limitada Deve haver um limite no número de vezes que outros processos são permitidos a entrar na seção crítica depois que o processo Pi fez o pedido para entrar na seção crítica até que o pedido seja atendido Atomicidade Assumimos a atomicidade das operações básicas de leitura e escrita na memória Semáforos Semáforos Mecanismos para sincronização de processos Usado para resolver o problema de seção crítica e problemas de sincronização Semáforos Djikstra Semáforo S registro valor inteiro lista lista de processos esperando pelo semáforo S fim Exceto para inicialização um semáforo só pode ser manipulado por 2 operações atômicas wait e signal Semáforos Djikstra waitS Svalor Svalor 1 se Svalor 0 então coloca este processo em Slista bloqueia o processo fim fim signalS Svalor Svalor 1 se Svalor 0 então remova um processo P de Slista desbloqueia o processo fim fim Semáforos Djikstra As operações wait e signal precisam ser atômicas para que as modificações no semáforo sejam feitas com exclusão mútua dado que o semáforo é uma variável compartilhada entre os processos Quando Svalor 0 Svalor é o número de processos bloqueados esperando pelo semáforo S Semáforos Djikstra Podemos resolver o problema da seção crítica n processos usando semáforos Semaforo mutex inicialmente mutexvalor 1 Processo Pi while not fim waitmutex seção de entrada seção crítica signalmutex seção de saída seção restante fim waitmutex seção crítica waitmutex preempção seção crítica signalmutex seção restante P0 preempção seção crítica signalmutex seção restante bloqueado mutex valor 1 0 1 0 1 lista P1 P1 Semáforos Djikstra Requisitos Exclusão mútua Exclusão mútua é atendida pois quando um processo Pi está na seção crítica mutex e outro processo Pj tentar entrar na seção crítica Pj ficará bloqueado no wait waitmutex seção crítica waitmutex preempção seção crítica signalmutex seção restante P0 preempção seção crítica signalmutex seção restante bloqueado mutex valor 1 0 1 2 1 0 lista P1 P2 P2 Semáforos Djikstra P1 waitmutex bloqueado seção crítica signalmutex seção restante seção crítica preempção Exclusão mútua Se 2 ou mais processos tentarem usar o recurso ao mesmo tempo apenas um deles executará o wait por vez logo apenas um entrará na seção crítica e os outros ficarão bloqueados Progresso Progresso é atendido pois quando o processo sai da seção crítica ele executa o signal permitindo que algum outro processo que estivesse bloqueado entre na seção crítica ou colocando o recurso disponível Espera limitada Espera limitada será atendida ou não dependendo da política de escalonamento utilizada na lista do semáforo Dependendo desta política pode haver ou não starvation Espera limitada Espera limitada será atendida ou não dependendo da política de escalonamento utilizada na lista do semáforo Dependendo desta política pode haver ou não starvation Um exemplo para não ocorrer starvation seria usar o algoritmo FCFS para escalonar a lista Outro exemplo Outro exemplo Dois processos P e Q onde P deve executar um comando s1 e Q deve executar um comando S2 mas S2 só pode ser executado depois de S1 ter terminado Sincronização de processos S1 signalsync P waitsync s2 Q Inicialmente syncvalor 0 Deadlock Deadlock Situação em que dois ou mais processos ficam impedidos de continuar suas execuções ou seja ficam bloqueados esperando uns pelos outros DEADLOCK Deadlock waitS waitR signalS signalR P waitR waitS signalR signalS Q Problemas clássicos de Sincronização de processos ProdutorConsumidor com buffer limitado Semáforo mutex exclusão mútua no usa das variáveis compartilhadas vazio conta o número de posições vazias do buffer cheio conta o número de posições cheias do buffer Inicialmente mutexvalor 1 vaziovalor tambuf cheiovalor 0 ProdutorConsumidor com buffer limitado Produtor while not fim produz dado waitvazio waitmutex bufferin dado in in 1 tambuf signalmutex signalcheio end end Consumidor while not fim waitcheio waitmutex dado bufferout out out 1 tambuf signalmutex signalvazio consomedado end end Problemas dos leitores e escritores Problema dos leitores e escritores Um determinado dado é compartilhado entre vários processos Alguns dos processos apenas lêem o dado leitores e outros lêem e escrevem no dado escritores Problema dos leitores e escritores Vários leitores podem acessar o dado ao mesmo tempo mas um escritor precisa acessar o dado exclusivamente para o dado não ficar em um estado inconsistente Problema dos leitores e escritores A Nenhum leitor fica esperando a não ser que um escritor esteja acessando o dado starvation dos escritores Problema dos leitores e escritores A Nenhum leitor fica esperando a não ser que um escritor esteja acessando o dado starvation dos escritores B Quando um escritor quer acessar o dado ele será atendido o mais rápido possível starvation dos leitores Problema dos leitores e escritores A Nenhum leitor fica esperando a não ser que um escritor esteja acessando o dado starvation dos escritores B Quando um escritor quer acessar o dado ele será atendido o mais rápido possível starvation dos leitores C Leitores e escritores são atendidos na ordem em que tentam acessar o dado Problema dos leitores e escritores Variável Compartilhada nleitores inteiro no de leitores que estão acessando o dado ao mesmo tempo inicialmente com 0 Semáforos mutex exclusão mútua no acesso a n leitores inicialmente com 1 acesso controle de acesso ao dado inicialmente com 1 Problema dos leitores e escritores Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei nleitores 0 mutex 1 acesso 1 Bloqueado Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 nleitores 1 mutex 0 acesso 1 Bloqueado Executando L1 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 nleitores 1 mutex 0 acesso 0 Bloqueado Executando L1 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 nleitores 1 mutex 1 acesso 0 Bloqueado Executando L1 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 nleitores 1 mutex 1 acesso 1 Bloqueado E2 Executando E2 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 2 mutex 0 acesso 1 Bloqueado E2 Executando L3 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 2 mutex 0 acesso 1 Bloqueado E2 Executando L3 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 2 mutex 1 acesso 1 Bloqueado E2 Executando L3 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 2 mutex 1 acesso 1 Bloqueado E2 Executando L3 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 2 mutex 0 acesso 1 Bloqueado E2 Executando L3 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 1 mutex 0 acesso 1 Bloqueado E2 Executando L3 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 1 mutex 0 acesso 1 Bloqueado E2 Executando L3 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 1 mutex 1 acesso 1 Bloqueado E2 Executando L3 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 1 mutex 1 acesso 1 Bloqueado E2 Executando L1 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 1 mutex 0 acesso 1 Bloqueado E2 Executando L1 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 0 mutex 0 acesso 0 Bloqueado Executando L1 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 0 mutex 1 acesso 0 Bloqueado Executando L1 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 nleitores 0 mutex 1 acesso 0 Bloqueado Executando E2 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 nleitores 1 mutex 0 acesso 0 Bloqueado Executando L4 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 nleitores 1 mutex 0 acesso 1 Bloqueado L4 Executando L4 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 1 mutex 1 acesso 1 Bloqueado L4 L5 Executando L5 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 1 mutex 1 acesso 0 Bloqueado L5 Executando E2 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 1 mutex 0 acesso 0 Bloqueado Executando L4 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 1 mutex 1 acesso 0 Bloqueado L4 Executando L4 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 2 mutex 1 acesso 0 Bloqueado L4 Executando L5 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 2 mutex 1 acesso 0 Bloqueado L4 Executando L5 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 2 mutex 0 acesso 0 Bloqueado Executando L5 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 2 mutex 1 acesso 0 Bloqueado L5 Executando L5 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 1 mutex 1 acesso 0 Bloqueado L5 Executando L4 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 1 mutex 1 acesso 0 Bloqueado L5 Executando L4 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 1 mutex 1 acesso 0 Bloqueado L5 Executando L4 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 1 mutex 0 acesso 0 Bloqueado Executando L4 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 0 mutex 0 acesso 1 Bloqueado Executando L5 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 0 mutex 1 acesso 1 Bloqueado Executando L5 Leitor waitmutex nleitores nleitores 1 se nleitores 1 então waitacesso fim signalmutex lê dado waitmutex nleitores nleitores 1 se nleitores 0 então signalacesso fim signalmutex fim Escritor waitacesso escreve no dado signalacesso fim Leitor i Li Escritor i Ei L1 E2 L3 L4 L5 nleitores 0 mutex 1 acesso 1 Bloqueado Executando L5 Problema do jantar dos filósofos Problema do jantar dos filósofos Formato da solução Filosofoi while not fim pensa waitgarfoi waitgarfoi 1 mod n come signalgarfoi signalgarfoi 1 mod n fim Fim Problema do jantar dos filósofos Solução intuitiva Semáforos garfo0 n1 controlam exclusão mútua no uso dos garfos Inicialmente garfoivalor 1 Filosofoi while not fim pensa waitgarfoi waitgarfoi 1 mod n come signalgarfoi signalgarfoi 1 mod n fim Fim Problema do jantar dos filósofos Solução intuitiva Semáforos garfo0 n1 controlam exclusão mútua no uso dos garfos Inicialmente garfoivalor 1 Filosofoi while not fim pensa waitgarfoi waitgarfoi 1 mod n come signalgarfoi signalgarfoi 1 mod n fim Fim Problema do jantar dos filósofos Ocorre deadlock se todos os filósofos resolvem comer ao mesmo tempo Filosofoi while not fim pensa waitgarfoi waitgarfoi 1 mod n come signalgarfoi signalgarfoi 1 mod n fim Fim Problema do jantar dos filósofos solução correta Problema do jantar dos filósofos variáveis compartilhadas estado0 n1 estadoi pensando com fome ou comendo semáforos mutex para a exclusão mútua ao estado inicialmente mutexvalor 1 filosofo0 n1 para cada filósofo se bloquear quando quer comer e não pode inicialmente filosofoi 0 Filosofoi while not fim pensa pegagarfoi come devolvegarfoi Fim fim pegagarfoi waitmutex estadoi comfome testai signalmutex waitfilosofoi fim devolvegarfoi waitmutex estadoi pensando testai1 mod n testai1 mod n signalmutex waitfilosofoi fim testai if estadoi comfome and estadoi 1 mod n comendo and estadoi 1 mod n comendo then estadoi comendo signalfilosofoi fim Fim Filósofo1 Pensa pegagarfo1 waitmutex estado1 comfome testa1 if estado1 comfome estado1 comendo signalfilosofo1 fim signalmutex waitfilosofo1 come devolvegarfo1 waitmutex Filósofo2 Pensa pegagarfo2 waitmutex estado2 comfome testa2 if estado2 comfome estado1 comendo false fim signalmutex waitfilosofo2 come