Simulação de Concorrência com Threads

Processos e Threads Introdução Computadores realizam várias tarefas de forma pseudoparalela Processos e threads possibilitam realizar diversas operações de forma concorrente Uma única CPU transformada em múltiplas CPUs virtuais Os chips atuais são muitas vezes multicore Para fins didáticos consideremos apenas uma CPU um processo executado por vez Introdução A CPU alterna rapidamente entre processos Cada processo executa por um curto intervalo de tempo milissegundos Em um dado instante a CPU está executando apenas um processo Ao longo de 1s ela pode trabalhar em vários deles dando a ilusão do paralelismo pseudoparalelismo paralelismo de hardware paralelismo real com duas ou mais CPUs compartilhando a mesma memória física Processo Uma abstraçãoinstância de um programa em execução Processos O Modelo de Processo Nesse modelo todos os softwares executáveis no computador incluindo o SO são organizados em uma série de processos sequenciais Processos incluem os valores atuais do contador do programa Program Counter PC registradores e variáveis Conceitualmente cada processo tem sua própria CPU virtual A CPU real troca a todo momento de processo em processo multiprogramação Processos O Modelo de Processo Multiprogramação de quatro programas Modelo conceitual de quatro processos sequenciais independentes quatro contadores de programa lógico um contador físico Apenas um programa está ativo de cada vez Processos Processo X Programa Analogia 1 Imagine uma pessoa preparando um bolo Receita programa Pessoa processador CPU Ingredientes dados de entrada O processo é a atividade consistindo na leitura da receita busca de ingredientes e preparo do bolo Processos Processo X Programa Analogia Analogia 2 Uma pessoa cujo filho pessoa sofreu uma picada de abelha A pessoa registra onde estava na receita salva o estado do processo pega um livro de primeiros socorros e começa a seguir as orientações O processador troca de um processo preparo do bolo para outro mais prioritário prestar cuidado médico Cada processo possui um programa diferente receita versus livro de primeiros socorros Quando a picada tiver sido cuidada a pessoa volta para o bolo continuando de onde havia parado Processos Processo X Programa Um programa pode ser armazenado em disco sem fazer nada Um processo é uma atividade de algum tipo Possui um programa uma entrada uma saída e um estado Um único processador pode ser compartilhado entre vários processos Algoritmo de escalonamento determina quando parar o trabalho em um processo e servir outro Um programa executado duas vezes conta como dois processos distintos O SO pode compartilhar o código de maneira que apenas uma cópia esteja na memória Processos Criação de Processos Um processo é criado por outro já existente executando uma chamada de sistema de criação de processo A chamada diz ao SO para criar um novo processo e indica qual programa executar nele Quatro eventos principais fazem com que processos sejam criados 1 Inicialização do sistema Daemons Processos que ficam lidando com atividades em segundo plano 2 Chamada de sistema de criação de processo 3 Solicitação de um usuário para criar um novo processo 4 Início de uma tarefa em lote Processos Término de Processos Uma vez iniciada a execução cedo ou tarde o processo terminará normalmente devido a uma das condições a seguir 1 Saída normal voluntária 2 Erro fatal involuntário 3 Saída por erro voluntária 4 Morto por outro processo involuntário Processos Hierarquias de Processos Em alguns sistemas quando um processo cria outro os processos pai e filho continuam a ser associados de certas maneiras O processo filho pode em si criar mais processos hierarquia de processos Um processo tem apenas um pai mas zero um dois ou mais filhos Processos Estados de Processos Processos muitas vezes precisam interagir entre si Um processo pode gerar uma saída que outro processo usa como entrada Algumas condições que podem causar o bloqueio de um processo pronto para executar O processo está aguardando uma entrada ainda não disponível O sistema operacional alocou a CPU para outro processo por um tempo Processos Estados de Processos Diagrama Transições 1 O processo é bloqueado aguardando uma entrada 2 O escalonador seleciona outro processo 3 O escalonador seleciona esse processo 4 A entrada tornase disponível Estados 1 Em execução usando a CPU naquele instante 2 Pronto executável temporariamente parado para deixar outro processo ser executado 3 Bloqueado incapaz de ser executado até que algum evento externo aconteça Processos Estados de Processos O nível mais baixo de um sistema operacional estruturado em processos controla interrupções e escalonamento Acima desse nível estão processos sequenciais Poucos sistemas reais são tão bem estruturados como esse O modelo de processos é baseado em dois conceitos independentes Agrupamento de recursos um processo é um modo de agrupar recursos relacionados para gerenciálos com mais facilidade Alguns exemplos de recursos são espaço de endereçamento contendo o código e os dados do programa arquivos abertos processos filhos alarmes pendentes tratadores de sinais informação sobre contabilidade O modelo de processos é baseado em dois conceitos independentes cont Linhas de execução threads entidade escalonada para execução na CPU Miniprocessos que executam dentro de um processo às vezes chamados de processos leves Possuem algumas das propriedades dos processos Possui um contador de programa registradores e uma pilha com uma estrutura para cada rotina chamada mas ainda não retornada Permitem que ocorram múltiplas execuções no mesmo ambiente com um alto grau de independência uma da outra Threads Algumas razões para a existência de Threads 1 Em muitas aplicações múltiplas atividades estão ocorrendo simultaneamente e algumas delas podem bloquear de tempos em tempos Decompor essas aplicações em múltiplos threads sequenciais executados em quase paralelo simplifica o modelo de programação 2 São mais leves do que os processos e mais fáceis e rápidos para criar e destruir Útil quando o número necessário de threads muda dinâmica e rapidamente 3 Desempenho Quando há computação substancial e também ES substancial threads permitem sobreposição de atividades acelerando a aplicação Não resultam em um ganho de desempenho quando todas as tarefas são limitadas pela CPU 4 São úteis em sistemas com múltiplas CPUs onde o paralelismo real é possível Threads Utilização de Threads Exemplo um servidor web multithread Lê requisições que chegam da rede e as repassa a um operário Multithreading Em SOs tradicionais cada processo possui um espaço de endereçamento e um único thread de controle Multithread situação onde múltiplos threads executam no mesmo processo espaço de endereçamento compartilhado execução em quase paralelo como se fossem quase processos separados algumas CPUs têm suporte de hardware direto para multithread Threads O modelo de thread clássico Múltiplos threads executando em paralelo em um processo Threads compartilham um espaço de endereçamento e outros recursos Múltiplos processos executando em paralelo em um computador Processos compartilham memórias físicas discos impressoras e outros recursos Três processos cada um com um thread Um processo com três threads Threads O modelo de thread clássico A primeira coluna lista alguns itens compartilhados por todos os threads em um processo A segunda lista alguns itens específicos a cada thread Threads O modelo de thread clássico Normalmente em multithreading os processos começam com um único thread capaz de criar novos Às vezes threads são hierárquicos relação paifilho Às vezes são todos iguais Rotinas para manipulação de threads Threadcreate criação de threads Não é necessário ou possível especificar o espaço de endereçamento ele automaticamente é executado no espaço de endereçamento do thread em criação Threadexit chamada quando uma thread encerra sua tarefa Threadjoin empregada para bloquear uma thread até que outro thread específico termine uma saída Threadyield permite que um thread abra mão voluntariamente da CPU para deixar outro thread ser executado Threads Há dois lugares principais para implementar threads No espaço do usuário No núcleo Threads No espaço do usuário Pacote de threads inteiramente no espaço do usuário Cada processo possui um sistema de tempo de execução rotinas que gerenciam as threads e uma tabela de threads privada Até onde o núcleo sabe ele está gerenciando processos comuns de um único thread Threads No núcleo O núcleo sabe sobre os threads e os gerencia O núcleo tem uma tabela que controla todos os threads no sistema Quando um thread quer criar um novo ou destruir um existente ele faz uma chamada de núcleo Threads Uma implementação híbrida também é possível Multiplexação de threads de usuário em threads de núcleo Threads Convertendo código de um thread em código multithread Muitos programas foram concebidos para processos monothread Algumas complicações na conversão para multithreading Variáveis que são globais para um thread mas não globais para o programa inteiro Rotinas não projetadas para ter uma segunda chamada feita enquanto uma anterior ainda não tiver sido concluída Alguns sinais são logicamente específicos a threads enquanto outros não Gerenciamento de pilha Threads Algumas complicações na conversão para multithreading Variáveis que são globais para um thread mas não globais para o programa inteiro procedimentos dentro do thread as usam mas outros threads devem ignorálas Possíveis soluções Proibir variáveis globais designar a cada thread suas próprias variáveis globais privadas Conflitos entre threads sobre o uso de uma variável global Muitas rotinas não foram projetadas para ter uma segunda chamada feita enquanto uma anterior ainda não tiver sido concluída Ex o envio de uma mensagem via rede pode ser programado com a montagem da mensagem em um buffer fixo dentro da biblioteca O que acontece se um thread montou a sua mensagem no buffer e uma interrupção de relógio força um chaveamento para um segundo thread que sobrescreve o buffer com sua própria mensagem Possível solução fornecer a cada rotina uma proteção que altera um bit para indicar que a biblioteca está sendo usada Diminui muito o paralelismo em potencial Threads Algumas complicações na conversão para multithreading Alguns sinais são logicamente específicos a threads enquanto outros não Sinais já são difíceis de gerenciar em um ambiente de um thread único Ex se um thread chama alarm faz sentido para o sinal resultante ir até o thread que fez a chamada Quando threads são implementados inteiramente no espaço de usuário o núcleo mal pode dirigir o sinal para o thread certo Threads Convertendo código de um thread em código multithread Gerenciamento de pilha Em muitos sistemas quando a pilha de um processo transborda o núcleo fornece automaticamente mais pilha a ele Quando um processo tem múltiplos threads ele também tem múltiplas pilhas Se o núcleo não tem ciência de todas as pilhas não pode fazêlas crescer automaticamente ou mesmo se dar conta de que uma falha de memória está relacionada com o crescimento da pilha de algum thread Threads Convertendo código de um thread em código multithread Comunicação entre processos Interprocess Communication IPC Comunicação entre processos Processos quase sempre precisam comunicarse entre si Ex um pipeline onde a saída de um processo tem de ser passada para o seguinte Em alguns SOs processos podem compartilhar de alguma memória comum que cada um pode ler e escrever Comunicação entre processos Algumas questões relacionadas à comunicação entre processos como um processo pode passar informações para outro certificarse de que dois ou mais processos não se atrapalhem Ex dois processos em um sistema de reserva de uma companhia aérea cada um tentando ficar com o último assento em um avião para um cliente diferente sequenciamento adequado quando dependências estão presentes se o processo A produz dados e o processo B os imprime B tem de esperar até que A tenha produzido alguns dados antes de começar a imprimir Comunicação entre Processos Condições de corrida Race Conditions Podem ser comuns com o incremento do paralelismo pelo maior número de núcleos Situação em que dois ou mais processos estão lendo ou escrevendo dados compartilhados e o resultado final depende de quem executa precisamente e quando De maneira mais ou menos simultânea os processos A e B decidem acessar a memória compartilhada e colocar um arquivo na fila Vagas vazias arquivos já foram impressos Comunicação entre Processos Condições de corrida Race Conditions Exemplo de comunicação entre processos spool de impressão Quando um processo quer imprimir um arquivo ele entra com o nome do arquivo em um diretório de spool O diretório de spool contém vagas numeradas que podem conter nomes de arquivos Variáveis compartilhadas entre os processos out aponta para o próximo arquivo a ser impresso in aponta para a próxima vaga livre no diretório Outro processo o daemon de impressão confere periodicamente para ver se há arquivos a serem impressos se houver ele os imprime e remove seus nomes do diretório Comunicação entre Processos Condições de corrida Race Conditions Imagine a seguinte situação 1 O processo A lê in e armazena o valor 7 em uma variável local chamada nextfreeslot 2 Uma interrupção de relógio ocorre e a CPU decide que o processo A executou por tempo suficiente então ele troca para o processo B 3 O processo B também lê in 7 e armazena o valor em sua variável local nextfreeslot 4 Nesse instante A e B acreditam que a próxima vaga disponível é 7 5 O processo B continua a execução armazena o nome do seu arquivo na vaga 7 e atualiza in para 8 A seguir segue suas atividades 6 O processo A continua a execução de onde parou Olha para seu nextfreeslot encontra 7 e escreve seu nome de arquivo na vaga 7 sobrescrevendo o valor que B colocou lá 7 O processo A calcula nextfreeslot 1 que é 8 e atualiza in com esse valor Como evitar condições de corrida A chave para evitar problemas em situações de compartilhamento de memória arquivos e alguns outros recursos é proibir mais de um processo de ler e escrever os dados compartilhados ao mesmo tempo A escolha de operações primitivas apropriadas para alcançar a exclusão mútua é uma questão de projeto fundamental em sistemas operacionais Exclusão mútua Certificação de que se um processo está usando um arquivo ou variável compartilhados os outros serão impedidos de realizar a mesma coisa Comunicação entre Processos Regiões críticas Partes do programa em que um processo tem de acessar uma memória compartilhada ou arquivos ou realizar outras tarefas críticas que podem levar a disputas Se dois processos nunca estiverem em suas regiões críticas ao mesmo tempo poderíamos evitar as condições de corrida Isso não é suficiente para garantir que processos em paralelo cooperem de modo correto e eficiente usando dados compartilhados Comunicação entre Processos Regiões críticas Partes do programa em que um processo tem de acessar uma memória compartilhada ou arquivos ou realizar outras tarefas críticas que podem levar a disputas Quatro condições para uma boa solução 1 Dois processos jamais podem estar simultaneamente dentro de suas regiões críticas 2 Nenhuma suposição pode ser feita a respeito de velocidades ou do número de CPUs 3 Nenhum processo executando fora de sua região crítica pode bloquear qualquer processo 4 Nenhum processo deve ser obrigado a esperar eternamente para entrar em sua região crítica Comunicação entre Processos Regiões críticas Exclusão mútua usando regiões críticas Comunicação entre Processos Exclusão mútua com espera ocupada Espera ocupada Quando um processo quer entrar em sua região crítica ele confere para ver se a entrada é permitida Ex teste de uma variável em loop Algumas propostas para exclusão mútua Desabilitando interrupções Variáveis do tipo trava Alternância explícita Solução de Peterson A instrução TSL Comunicação entre Processos Exclusão mútua com espera ocupada Desabilitar interrupções ao entrar na região crítica e reabilitar antes de sair Solução simples para sistemas com um único processador Abordagem pouco atraente Não é prudente dar a processos de usuário o poder de desligar interrupções Em sistemas multiprocessador desabilitar interrupções afeta somente a CPU que executou a instrução disable As outras continuarão executando e podem acessar a memória compartilhada Em consequência esquemas mais sofisticados são necessários Por outro lado pode ser conveniente para o próprio núcleo desabilitar interrupções por algumas instruções enquanto atualiza variáveis ou listas de processos Conclusão desabilitar interrupções pode ser útil dentro do SO mas não é apropriada para exclusão mútua Comunicação entre Processos Exclusão mútua com espera ocupada Variáveis do tipo trava Solução de software Considere ter uma única variável de trava compartilhada inicialmente 0 Quando um processo quer entrar na região crítica ele primeiro testa a trava Trava 0 nenhum processo está na região crítica o processo a configura para 1 e entra na região crítica Trava 1 algum processo está em sua região crítica o processo apenas espera até que ela se torne 0 Problema vide exemplo do diretório de spool Comunicação entre Processos Exclusão mútua com espera ocupada Processo 0 Processo 1 Alternância explícita turn variável que controla de quem é a vez de entrar na região crítica Valor inicial 0 Uma trava que usa a espera ocupada é chamada de trava giratória spin lock Problemas Desperdiça tempo da CPU Apenas quando há uma expectativa razoável de que a espera será curta a espera ocupada é usada Pode não ser uma boa ideia quando um dos processos é muito mais lento que o outro Viola a condição 3 Um processo pode estar sendo bloqueado por um que não está em sua região crítica Comunicação entre Processos Exclusão mútua com espera ocupada Solução de Peterson Solução de software que não exige alternância explícita Antes de entrar na região crítica cada processo chama enterregion com seu próprio número de processo como parâmetro espera até que seja seguro entrar Após terminar com as variáveis compartilhadas o processo chama leaveregion para indicar que terminou e permitir que outros processos entrem na região crítica Comunicação entre Processos Exclusão mútua com espera ocupada A instrução TSL Test and Set Lock teste e configure trava Exige ajuda do hardware Alguns computadores possuem uma instrução TSL RXLOCK Funcionamento variável de bloqueio lock associada ao endereço de memória LOCK que pode receber 0 ou 1 Se lock 0 Leia o valor armazenado no endereço LOCK para o registrador RX Configure lock para 1 Realize as operações na memória compartilhada Quando terminar o processo configura lock de volta para 0 Se lock 1 o processo espera até que esteja livre Comunicação entre Processos Exclusão mútua com espera ocupada A instrução TSL Test and Set Lock teste e configure trava Diferente de desabilitar interrupções A CPU executando a instrução TSL impede o acesso ao barramento de memória nenhum outro processador pode acessar a palavra na memória até que a instrução tenha terminado travar o barramento exige hardware especial basicamente uma linha de barramento que assegura que o barramento está travado e indisponível para outros processadores fora aquele que o travar Comunicação entre Processos Exclusão mútua com espera ocupada Entrando e saindo de uma região crítica usando a instrução TSL Comunicação entre Processos Problemas na espera ocupada Desperdício de tempo da CPU Efeitos inesperados Ex Considere dois processos H alta prioridade e L baixa prioridade H é executado sempre que ele estiver em um estado pronto Em um certo momento com L em sua região crítica H fica pronto para executar ex completa uma operação de ES H agora começa a espera ocupada Como L nunca é escalonado enquanto H estiver executando jamais tem a chance de executar leaveregion e deixar a região crítica H segue em um laço infinito Essa situação às vezes é referida como problema da inversão de prioridade Comunicação entre Processos O problema do produtorconsumidor Exemplo clássico usado para ilustrar a sincronizaçãocomunicação entre processosthreads Descrição Dois processos compartilham um buffer de tamanho fixo comum O produtor insere informações no buffer e o consumidor as retira É possível generalizar o problema para ter m produtores e n consumidores Variáveis count variável que controla o número de itens no buffer N número máximo de itens no buffer Comunicação entre Processos Dormir e acordar Sleep and Wakeup Primitivas de comunicação entre processos que bloqueiam ficam suspensos em vez de desperdiçar tempo da CPU quando eles não são autorizados a entrar nas suas regiões críticas sleep chamada de sistema que faz com que o processo que a chamou bloqueie até que outro processo o desperte wakeup desperta o processo O problema do produtorconsumidor com uma condição de corrida fatal O acesso a count não é restrito O buffer está vazio e o consumidor acabou de ler count 0 O escalonador para de executar o consumidor e começar a executar o produtor O produtor insere um item no buffer e incrementa count para 1 Como count era 0 o consumidor deve estar dormindo o produtor chama wakeupconsumer O consumidor ainda não está logicamente dormindo então o sinal de despertar é perdido Quando o consumidor executa em seguida testará o valor de count que leu antes 0 e irá dormir Cedo ou tarde o produtor preencherá o buffer e vai dormir também Ambos dormirão para sempre Semáforos duas operações down e up generalizações de sleep e wakeup Down valor 0 decrementa o valor gasta um sinal de acordar armazenado e apenas continua Valor 0 o processo é colocado para dormir sem completar o down para o momento Up incrementa o valor de um determinado semáforo Se um ou mais processos estiverem dormindo naquele semáforo incapaz de completar uma operação down anterior um deles é escolhido pelo sistema e autorizado a completar seu down Desse modo após um up com processos dormindo em um semáforo ele ainda estará em 0 mas haverá menos processos dormindo nele Variável inteira para contar o número de sinais de acordar salvos para uso futuro Semáforos Solucionando o problema produtorconsumidor usando semáforos Semáforos solucionam o problema do sinal de acordar perdido Devem ser implementados de uma maneira atômica o processo não pode ser bloqueado durante sua execução ex chamadas de sistema com o SO desabilitando as interrupções enquanto testa o semáforo atualizao e coloca o processo para dormir se necessário Solucionando o problema produtorconsumidor usando semáforos Se cada processo realiza um down um pouco antes de entrar em sua região crítica e um up logo depois de deixála a exclusão mútua é garantida mutex se certifica de que o produtor e o consumidor não acessem o buffer ao mesmo tempo Mutexes Versão simplificada de semáforos Usados quando a capacidade do semáforo de fazer contagem não é necessária são bons somente para gerenciar a exclusão mútua de algum recurso ou trecho de código compartilhados fáceis e eficientes de implementar Variável compartilhada que pode estar em um de dois estados destravado ou travado Duas rotinas mutexlock e mutexunlock Mutexes mutexlock invocada quando um thread ou processo precisa de acesso a uma região crítica Se o mutex estiver destravado região crítica disponível o thread que chamou poderá entrar na região crítica Se o mutex estiver travado o thread que chamou será bloqueado até que o thread na região crítica tenha concluído mutexunlock quando o thread concluiu o uso da região crítica e deseja sair A thread que estiver bloqueada no mutex pode adquirir a trava Se múltiplos threads estiverem bloqueados um deles será escolhido ao acaso Mutexes Implementação de mutexlock e mutexunlock Semáforos e mutexes facilitam a comunicação entre processos Entretanto necessitam de implementação cautelosa dos ups e downs para evitar impasses Monitores Primitiva de sincronização de nível mais alto consistem de uma coleção de rotinas variáveis e estruturas de dados reunidas em um tipo especial de módulo ou pacote são uma construção da linguagem de programação o compilador lida com chamadas para rotinas de monitor diferentemente de outras chamadas de rotina Processos podem chamar as rotinas em um monitor mas não podem acessar diretamente as suas estruturas de dados internas a partir de rotinas declaradas fora dele Exclusão mútua apenas um processo ativo em um monitor em qualquer dado instante Monitores O desenvolvedor não precisa implementar a exclusão mútua Cabe ao compilador implementar a exclusão mútua Basta saber que ao transformar as regiões críticas em rotinas de monitores dois processos jamais executarão suas regiões críticas ao mesmo tempo menos provável que algo dê errado um monitor escrito em uma linguagem imaginária Pidgin Pascal Um esqueleto do problema produtorconsumidor com monitores Somente uma rotina do monitor está ativa por vez O buffer tem N vagas Monitores Problemas A maioria das linguagens de programação não têm monitores Tampouco têm semáforos mas acrescentar semáforos é mais fácil Projeto pensado para uma ou mais CPUs todas com acesso a uma memória comum Em sistema distribuídos múltiplas CPUs cada uma com sua própria memória conectadas via rede essas primitivas tornamse inaplicáveis Conclusão semáforos são de um nível baixo demais monitores são utilizáveis em algumas poucas linguagens de programação nenhuma das primitivas permite a troca de informações entre máquinas Algo mais é necessário Troca de mensagens Método de comunicação entre processos com duas primitivas senddestination message envia uma mensagem para determinado destino receivesource message recebe uma mensagem de uma dada fonte ou de ANY qualquer se o receptor não se importar Se nenhuma mensagem estiver disponível o receptor pode bloquear até que uma chegue Alternativamente pode retornar imediatamente com um código de erro Ambas são chamadas de sistema em vez de construções de linguagem Troca de mensagens Questões de projeto para sistemas de troca de mensagens Mensagens podem ser perdidas pela rede o emissor e o receptor podem combinar que tão logo uma mensagem tenha sido recebida o receptor enviará uma confirmação de recebimento Se o emissor não receber a confirmação em dado intervalo ele retransmite a mensagem A mensagem é recebida corretamente mas a confirmação de recebimento foi perdida O emissor retransmitirá a mensagem assim o receptor a receberá duas vezes O receptor deve distinguir uma nova mensagem da retransmissão de uma antiga Troca de mensagens Questões de projeto para sistemas de troca de mensagens Sistemas de mensagens devem lidar com a questão de como processos são nomeados o processo especificado na chamada não pode ser ambíguo Autenticação como saber se está se comunicando com o servidor real e não com um impostor Questões de projeto para emissor e o receptor na mesma máquina Desempenho Copiar mensagens de um processo para o outro é sempre algo mais lento do que realizar uma operação de semáforo ou entrar em um monitor O problema produtorconsumidor com N mensagens Barreiras Mecanismo de sincronização dirigido a grupos de processos Algumas aplicações são divididas em fases e têm como regra que nenhum processo deve prosseguir para a fase seguinte até que todos os processos estejam prontos para isso Tal comportamento pode ser conseguido colocando uma barreira no fim de cada fase Quando um processo atinge a barreira ele é bloqueado até que todos os processos tenham atingido a barreira Isso permite que grupos de processos sincronizem Barreiras Uso de uma barreira Processos aproximandose de uma barreira Todos os processos exceto um bloqueados na barreira Quando o último processo chega à barreira todos podem passar Evitando travas leituracópiaatualização Não se pode permitir acessos de leitura e escrita concorrentes a estruturas de dados compartilhados sem usar travas Em alguns casos podese permitir que um processo escritor atualize uma estrutura de dados mesmo que outros processos ainda a estejam usando O truque é assegurar que cada leitor leia a versão anterior dos dados ou a nova mas não alguma combinação esquisita da anterior e da nova inserindo um nó na árvore e então removendo um galho tudo sem travas Atividade Simulação de Concorrência com Threads Objetivo Aplicar conceitos de concorrência e sincronização usando threads Desenvolvam um programa em uma linguagem de programação que suporte multithreading Cada thread representará uma entidade que precisa acessar e realizar operações em recursos compartilhados a serem definidos por vocês Ex variáveis estruturas de dados O programa deverá simular uma situação de concorrência com várias threads Sincronizem as threads identifiquem e tratem eventuais condições de corrida mecanismo de sincronização de sua preferência Ex semáforos mutexes etc Entrega Código fonte relatório descrevendo o programa e conceitos aplicados Apresentação em sala de aula 10 minutos por grupo Grupos de cinco pessoas Prazo A definir AGORA Problemas Clássicos de IPC Interprocess Communication O problema do jantar dos filósofos Cinco filósofos estão sentados em torno de uma mesa circular Cada filósofo tem um prato de espaguete O espaguete é escorregadio Um filósofo precisa de dois garfos para comêlo Entre cada par de pratos há um garfo A vida do filósofo consiste em alternar períodos de alimentação e pensamento Quando um filósofo fica suficientemente faminto ele tenta pegar seus garfos à esquerda e à direita um de cada vez não importa a ordem Se conseguir pegar dois garfos ele come por um tempo então larga os garfos e continua a pensar Questão fundamental Escrever um programa para que cada filósofo faça o que deve fazer e jamais fique travado Formulado e solucionado por Dijkstra em 1965 e utilizado desde então na demonstração de primitivas de sincronização Útil para modelar processos que competem pelo acesso exclusivo a um número limitado de recursos O problema do jantar dos filósofos Problemas Clássicos de IPC O problema do jantar dos filósofos Uma não solução para o problema do jantar dos filósofos O problema do jantar dos filósofos Suponha que todos os cinco filósofos peguem seus garfos esquerdos simultaneamente Nenhum será capaz de pegar seus garfos direitos O problema do jantar dos filósofos Modificando o programa Após pegar o garfo esquerdo o programa confere para ver se o garfo direito está disponível Se não estiver o filósofo coloca de volta o esquerdo sobre a mesa espera por um tempo e repete todo o processo Essa proposta também pode fracassar O problema do jantar dos filósofos Modificando o programa Pior caso Todos os filósofos pegam seus garfos esquerdos simultaneamente Todos vêem que os garfos direitos não estão disponíveis e devolvem os esquerdos à mesa Todos pegam seus garfos esquerdos novamente ao mesmo tempo assim por diante para sempre Starvation Inanição Situação na qual todos os programas continuam a executar indefinidamente mas fracassam em realizar qualquer progresso O problema do jantar dos filósofos Modificando o programa de novo E se os filósofos simplesmente esperassem um tempo aleatório em vez de ao mesmo tempo fracassarem em conseguir o garfo direito Diminui bastante a chance de tudo continuar em um impasse Em quase todas as aplicações tentar mais tarde não é um problema No entanto em algumas aplicações é preferível uma solução funcione SEMPRE e não falhe por uma série improvável de vezes aleatórias Uma solução para o problema do jantar dos filósofos Processo principal do filósofo Uma solução para o problema do jantar dos filósofos Rotinas do filósofo O problema dos leitores e escritores Modela o acesso a um banco de dados Imagine um sistema de reservas de uma companhia aérea com muitos processos competindo entre si desejando ler e escrever É aceitável ter múltiplos processos lendo o banco de dados ao mesmo tempo mas se um processo está atualizando escrevendo o banco de dados nenhum outro pode ter acesso nem mesmo os leitores Questão como programar leitores e escritores Uma solução para o problema dos leitores e escritores Uma solução para o problema dos leitores e escritores