Comunicação entre Processos e Sincronização em Sistemas Operacionais

SISTEMAS OPERACIONAIS COMUNICAÇÃO ENTRE PROCESSOS E SINCRONIZAÇÃO Parte 07 Professor Eduardo Xavier DEFINIÇÃO Uma situação bastante comum no sistema operacional é haver dois ou mais processos precisando se comunicar para funcionar corretamente Exemplo processos que controlam a interface gráfica do Windows precisam interagir com processos que controlam o mouse e o teclado além de trocar informações com os processos de cada programa que está sendo executado do contrário o usuário não consegue trabalhar Esta comunicação é chamada de IPC Interprocess Communication Comunicação entre Processos e tem como objetivo promover a cooperação entre processos Existem duas maneiras desta comunicação acontecer Por meio do compartilhamento de recursos Por meio de troca de mensagens DEFINIÇÃO Na maioria dos casos a comunicação ocorre por meio da utilização de recursos comuns aos processos envolvidos na comunicação Exemplo a memória principal do sistema ou arquivos compartilhados Porém existem casos em que os processos que necessitam se comunicar não compartilham memória ou arquivos mas ainda precisam trocar informações Nestes casos a solução é fazer com que os processos troquem mensagens entre si Por se tratarem de mensagens estas podem ser trocadas até entre processos que estão em máquinas diferentes Chamamos a este método de RPC Remote Procedure Call Chamada de Procedimento Remoto e ele ocorre de forma transparente para o processo PROTOCOLOS Processos e threads interagem para trabalhar conjuntamente em um sistema Trocam dados mensagens Utilizam os serviços de comunicação fornecidos pela máquina e pelo SO Seguem protocolos de comunicação para que possam entender uns aos outros Protocolos Estabelecem caminhos virtuais de comunicação entre processos threads Duas entidades precisam usar os mesmos protocolos para trocar informações PROTOCOLOS COMUNICAÇÃO ENTRE PROCESSOSTHREADS Características dos serviços de comunicação entre processosthreads Abrangência local ou remota Participantes 1 1 1 N M N Tamanho das mensagens Fixo ou variável Limitado ou não Sincronismo Comunicação síncrona Comunicação assíncrona Comunicação semisíncrona COMUNICAÇÃO ENTRE PROCESSOSTHREADS APIs de comunicação Permitem que aplicações troquem dados Fornecem primitivas de comunicação que podem ser chamadas a partir do código Proveem acesso aos serviços de comunicação que podem assim ser usados pelas aplicações COMUNICAÇÃO ENTRE PROCESSOSTHREADS APIs de comunicação de Sistemas Operacionais Mecanismos fornecidos pelos SOs permitem enviar mensagens trechos de memória de um processo a outro Alguns SOs permitem que sejam criadas áreas de memória compartilhadas entre dois ou mais processos COMUNICAÇÃO ENTRE PROCESSOSTHREADS Exemplos de APIs de comunicação Pipes Canais de comunicação locais Sockets Portas de comunicação locais ou de rede Versão segura SSL Suportes de RPC Remote Procedure Call Permitem chamar procedimentosmétodos remotamente Ex RMI CORBA COM Canais de eventos Permitem notificar threads e processos dos eventos ocorridos no sistema Ex JMS CORBA Notification Service SINCRONIZAÇÃO ENTRE PROCESSOS A sincronização entre processos é a tarefa de organizar o acesso de vários processos concorrentes para que possam compartilhar recursos sem causar quaisquer conflitos Os recursos compartilhados mais frequentemente são endereços de memória compartilhamento de dados e periféricos de entrada e saída A sincronização entre processos pode ser dividida em duas subcategorias Sincronização entre processos concorrentes Sincronização entre processos cooperantes SINCRONIZAÇÃO ENTRE PROCESSOS Sincronização entre processos concorrentes Vários processos podem competir pela posse uso exclusivo de algum recurso compartilhado A utilização desses recursos é feita pela execução de conjuntos de instruções que muitas vezes não devem ser executadas simultaneamente por processos diferentes A esses conjuntos de instruções chamamos de seções críticas ou regiões críticas Tais seções críticas devem ser protegidas contra a execução simultânea em processos concorrentes e a isso chamamos de exclusão mútua O foco é Evitar a execução concorrente de regiões críticas de processos diferentes e consequentemente erros de comunicação ex processos querendo utilizar a mesma área de memória de forma concorrente SINCRONIZAÇÃO ENTRE PROCESSOS Sincronização entre processos cooperantes Alguns processos precisam avisar a outros processos do seu progresso para que resultados comuns possam ser passados adiante O problema produtorconsumidor é um exemplo de processos cooperantes em que alguns processos necessitam de informações para poderem prosseguir a sua execução enquanto outros processos têm a função de produzir essas informações É preciso avisar aos processos consumidores quando existem informações prontas para serem consumidas ao mesmo tempo em que é preciso avisar aos processos produtores quando estes devem produzir informações O foco é garantir o sequenciamento adequado quando há cooperação entre processos se o processo A produz dados e o processo B os imprime o sistema operacional deve esperar que o processo A seja finalizado corretamente e só depois iniciar o processo B SINCRONIZAÇÃO ENTRE PROCESSOS Condições de Corrida Uma condição de corrida é uma situação onde a execução de vários processos concorrentemente poderá resultar em resultados diferentes a depender da ordem em que esses processos sejam escalonados no processador Como a ordem de escalonamento de processos diferentes geralmente não é especificada a alteração na ordem de execução das instruções dos diferentes processos que manipulam um mesmo recurso pode provocar alteração no resultado desse recurso Portanto escalonamentos diferentes podem gerar resultados diferentes SINCRONIZAÇÃO ENTRE PROCESSOS Condições de Corrida Exemplo Fila de Impressão Imagine uma fila de impressão única para todo o sistema onde cada vaga na fila é numerada de forma crescente vaga n o 1 vaga n o 2 vaga n o 3 Para conseguir imprimir cada processo verifica qual o próximo lugar vago na fila e preenche este lugar com seu arquivo Dois processos A e B estão enviando arquivos diferentes para serem impressos nesta mesma fila O processo A verifica que o próximo lugar vago na fila é a vaga n o 4 mas sua fatia de tempo acaba antes que ele a preencha com seu arquivo ou seja o processo vai para a fila de prontos e a vaga n o 4 da fila de impressão fica vazia O processo B que não sabe a situação do processo A descobre que a próxima vaga vazia da fila de impressão é a vaga n o 4 e coloca lá seu arquivo para imprimir O processo A volta a ser executado sem saber que a vaga n o 4 foi usada pelo processo B e coloca sua impressão na mesma vaga perdendo a impressão que B pretendia fazer SINCRONIZAÇÃO ENTRE PROCESSOS Exclusão Mútua Para evitar condições de corrida os sistemas operacionais devem garantir que os recursos compartilhados por vários processos sejam manipulados por apenas um processo de cada vez Para isso o SO usa a Exclusão Mútua que é uma forma de garantir que um processo usando determinado recurso compartilhado impede os demais processos de fazer o mesmo Quem está usando o recurso exclui a possibilidade de uso pelos demais interessados Quem for excluído deve aguardar a liberação do recurso A exclusão mútua também serve para evitar deadlocks Existem duas formas de um processo bloqueado por exclusão mútua aguardar a liberação do recurso compartilhado Espera Ocupada O processo pode fazer uso da CPU para outras atividades enquanto aguarda Espera Bloqueada O processo não utiliza a CPU enquanto aguarda ou seja não disputa pelo uso do processador SINCRONIZAÇÃO ENTRE PROCESSOS Regiões Críticas É como são chamadas as partes de cada processo trechos de código que acessam recursos compartilhados Uma forma bastante eficiente de garantir a exclusão mútua é assegurar que dois processos nunca entrem em suas regiões críticas ao mesmo tempo As regiões críticas devem obedecer as seguintes restrições Dois processos não podem executar suas regiões criticas para o mesmo recurso compartilhado ao mesmo tempo garantia de exclusão mútua Isso deve acontecer sempre independente da velocidade ou quantidade de CPUs envolvidas Nenhum processo executando trechos de código que não sejam região crítica pode bloquear outro processo Nenhum processo deve esperar indefinidamente para entrar em sua região crítica SOLUÇÕES PARA EXCLUSÃO MÚTUA Exclusão Mútua com espera ativa ou espera ocupada Os primeiros algoritmos desenvolvidos com a finalidade de implementar exclusão mútua utilizavam espera ocupada Isso significa que quando um processo não for capaz de entrar na sua região crítica ele deverá aguardar ativamente até que seja autorizado a prosseguir na sua execução Em geral essa espera era realizada por um loop de controle feito apenas com a intenção de aguardar gastando o tempo necessário Embora algoritmos que utilizem espera ocupada sejam na sua maioria fáceis de compreender e implementar eles não fazem bom uso do processador ocupando este com instruções inúteis com o único propósito de gastar tempo É importante lembrarmos que enquanto um processo estiver desperdiçando tempo de processador realizando espera ocupada outros processos podem estar aguardando para serem executados no estado de pronto SOLUÇÕES PARA EXCLUSÃO MÚTUA Variáveis de Bloqueio Essa é uma solução com espera ocupada Utiliza variáveis como um mecanismo de bloqueio Normalmente usado em sistemas com múltiplos processadores Variáveis de bloqueio apenas utilizam um loop espera ocupada até que o recurso aguardado se torne disponível A lógica aqui é que pode ser mais rápido o desperdício de alguns ciclos de processador do que ir para o estado de bloqueado e aguardar que o bloqueio se desfaça Cria se uma variável compartilhada chamada LOCK inicialmente igual a zero Quando o processo deseja entrar em sua região crítica ele primeiro testa o LOCK Se for igual a zero o processo modifica para o valor 1 e executa o que quer que seja na sua região crítica Se a variável LOCK tiver o valor 1 então esse processo sabe que existe um outro processo fazendo algo na sua região crítica e espera Embora pareça uma boa solução o que irá ocorrer se os processos testam uma variável de valor zero ao mesmo tempo SOLUÇÕES PARA EXCLUSÃO MÚTUA Alternância Estrita Usase uma variável indica qual o processo que estará autorizado a executar o código da sua região crítica devendo os demais aguardarem a sua vez Em outras palavras os processos estritamente se alternam no uso do recurso compartilhado É uma solução de espera ocupada Esse método de exclusão mútua só deve ser utilizado quando os processos envolvidos utilizam o recurso compartilhado com frequências semelhantes Caso contrário os processos terão a sua velocidade de execução limitada pelo processo que utilizar o recurso compartilhado com a menor frequência SOLUÇÕES PARA EXCLUSÃO MÚTUA Alternância Estrita funcionamento Os processos são numerados em ordem crescente iniciando do processo zero Define se uma variável TURN inicialmente igual a zero Suponha a existência de três processos 0 1 e 2 concorrentes Se TURN for igual a 0 os processos 1 e 2 devem esperar que o processo 0 execute o código da sua região crítica Se TURN for igual a 1 os processos 0 e 2 devem esperar que o processo 1 execute o código da sua região crítica Se TURN for igual a 2 os processos 0 e 1 devem esperar que o processo 2 execute o código da sua região crítica Quando o processo sai da região crítica ele deve incrementar o valor da variável TURN habilitando o próximo processo a executar o código da sua respectiva região crítica Quando o último processo terminar de executar a sua região crítica ele deve atribuir o valor 0 à variável TURN habilitando o processo zero a executar a sua região crítica e reiniciando o mesmo ciclo SOLUÇÕES PARA EXCLUSÃO MÚTUA Solução de Peterson O Algoritmo de Peterson não só é simples mas também é muito elegante Um processo que deseja executar a sua região crítica não só informa aos demais processos que deseja executar a sua região crítica mas também diz que se algum outro processo também quiser entrar na sua região crítica ele pode fazê lo primeiro Isso não só é educado mas não vai lhe custar mais do que apenas uma curta espera para executar a sua região crítica Por quê Porque todos os processos também fazem o mesmo Se um processo quer entrar em sua RC Região Crítica deve informar a seus concorrentes O processo só pode entrar em sua RC quando for a vez dele Se ninguém mais quiser entrar em RC é automaticamente a vez dele Caso haja mais interessados o processo cede sua vez para eles mesmo querendo usar Como os outros processos farão a mesma coisa quem ceder a vez primeiro passa na frente dos demais SOLUÇÕES PARA EXCLUSÃO MÚTUA Instruções TSL Essa proposta utiliza variáveis LOCK em hardware através das instruções do tipo TSL Test and Set Locked A micro instrução TSL é usada para implementar exclusão mútua em ambientes com um ou mais processadores A ideia principal é transformar o ciclo de avaliação de uma variável de travamento leitura avaliação atualização em uma única instrução sobre uma variável de travamento Se a resposta à instrução TSL for que a variável já estava travada o processo pode realizar um laço de espera ocupada e voltar a tentar novamente mais tarde Entretanto se a resposta for que a variável não estava travada a própria instrução TSL já terá efetuado o travamento da variável não sendo necessário que o processo faça mais nada e possa prosseguir na execução da sua região crítica SOLUÇÕES PARA EXCLUSÃO MÚTUA Bloqueio de Interrupções Normalmente os controladores de dispositivo existentes na máquina geram interrupções na CPU quando um dispositivo encerra seu trabalho A CPU reage a essa interrupção acionando uma rotina de tratamento adequada Para garantir a exclusão mútua o sistema operacional bloqueia as interrupções de um dispositivo durante a execução de uma região crítica que afete este dispositivo Não havendo interrupções o processo corrente não será substituído por nenhum outro Este tipo de solução é muito usada em nível de sistema operacional Não é tão eficiente em nível de usuário Nem sempre interrupções de dispositivos podem ser ignoradas Processos que não estão relacionados com a região crítica também são penalizados Dá poder demais ao usuário SOLUÇÕES PARA EXCLUSÃO MÚTUA Bloqueio de Interrupções SOLUÇÕES PARA EXCLUSÃO MÚTUA Exclusão Mútua com espera bloqueada Nesse tipo de exclusão mútua os processos são bloqueados quando tentam executar uma região crítica já ocupada por outro processo São mais eficientes que as estratégias que utilizam espera ocupada uma vez que os processos bloqueados não competem pelo processador SOLUÇÕES PARA EXCLUSÃO MÚTUA Dormir e Acordar SLEEP e WAKEUP SLEEP é uma system call que muda o estado de um processo em execução para bloqueado Para que este processo bloqueado volte a ser ativo é necessária a utilização de outra system call denominada WAKE UP Esse método apresenta a mesma filosofia que as instruções TSL porém quando a variável LOCK apresenta valor 1 o processo executa um SLEEP O processo que se encontra na região crítica é responsável por executar um WAKE UP para ativar o processo bloqueado Importante existe risco da solução gerar um deadlock SOLUÇÕES PARA EXCLUSÃO MÚTUA Problema do ProdutorConsumidor Considere que existe Uma área compartilhada buffer com um tamanho limitado Um processo que alimenta o buffer produtor Outro processo que usa o conteúdo desse buffer consumidor Quando o buffer está cheio o processo produtor não tem como continuar a alimentar o mesmo Para evitar o desperdício de CPU ao manter este processo funcionando ele é colocado para dormir Sleep Assim que o processo consumidor usa parte do conteúdo do buffer emite um Wakeup para acordar o produtor Quando o buffer está vazio o processo consumidor não tem nada a fazer por isso é colocado para dormir Sleep Assim que o processo produtor coloca algum conteúdo no buffer emite um Wake up para acordar o consumidor SOLUÇÕES PARA EXCLUSÃO MÚTUA Problema do ProdutorConsumidor continuação Para saber se o buffer do exemplo anterior está cheio ou vazio é preciso testar o conteúdo de uma variável qualquer que indique isso um contador Agora imagine a seguinte situação O buffer do exemplo está vazio logo a variável deve ter um valor que indique isso O consumidor testa o valor da variável e nota que o buffer está vazio mas antes de ir dormir seu tempo de CPU acaba O produtor entra em execução logo em seguida alimenta o buffer altera o valor da variável e envia o sinal de acordar para o consumidor O consumidor volta a ser executado na CPU e retoma a tarefa em que parou ou seja vai dormir O produtor julgando que seu se sinal de acordar foi recebido na verdade esse sinal se perdeu continua a povoar o buffer até enchêlo e aí vai dormir Resultado tanto o produtor quanto o consumidor dormirão eternamente z O sinal de wakeup do produtor foi perdido não teve efeito pois o consumidor ainda não estava logicamente adormecido SOLUÇÕES PARA EXCLUSÃO MÚTUA Problema do ProdutorConsumidor continuação Resolvendo o problema do ProdutorConsumidor Uma solução possível seria armazenar o sinal de Wakeup para uso posterior Melhor ainda armazenar em um contador qualquer quantos sinais de acordar que estão pendentes anda não foram atendidos Principais implementações de solução Semáforos também chamados de Semáforos Contadores Semáforos Mutex Monitores SOLUÇÕES PARA EXCLUSÃO MÚTUA Semáforos Um semáforo é um objeto de software compartilhado por processos que desejam utilizar um recurso compartilhado O valor de um semáforo indica quantos processos ou threads podem ter acesso a um recurso compartilhado As principais operações sobre semáforos são Inicialização Recebe um valor inteiro indicando a quantidade de processos que podem acessar um determinado recurso Operação DOWN ou P Verifica se o semáforo tem valor positivo maior que zero Em caso afirmativo decrementa o valor do semáforo em uma unidade Em caso negativo igual a zero o processo é posto para dormir SLEEP Operação UP ou V Incrementa o valor do semáforo em uma unidade Se houver processos inativos dormindo um deles é ativado WAKEUP SOLUÇÕES PARA EXCLUSÃO MÚTUA Semáforos Mutex É um tipo particular e mais simples de semáforo apelidado de semáforo binário Um semáforo mutex é inicializado com o valor 1 e é utilizado para a implementação da exclusão mútua entre vários processos Duas operações são definidas DOWN decremento executada no início da região crítica UP incremento executada na saída da região crítica Os semáforos mutex consistem em contadores iniciados em 1 e uma lista de processos aguardando liberação para entrar na região crítica protegida por um semáforo A operação DOWN decrementa o contador do semáforo de uma unidade e verifica seu valor Se após uma operação DOWN o valor do mutex for menor que zero a operação DOWN não é realizada e o processo que a executou será bloqueado e adicionado à lista de processos bloqueados A operação UP incrementa o valor do semáforo Se um ou mais processos estiverem bloqueados sob aquele semáforo um dos processos será escolhido na lista para executar a sua operação DOWN SOLUÇÕES PARA EXCLUSÃO MÚTUA Monitores Semáforos tornam simples a proteção de recursos compartilhados No entanto caso ocorra uma inversão na ordem da chamada dessas operações pode provocar uma situação de impasse infinito deadlock Os monitores são uma solução para uma sincronização de alto nível São mais elegantes e estáveis que os semáforos Em alguns aspectos se parecem com objetos da programação OO Um monitor é uma coleção de procedimentos variáveis e estruturas de dados agrupados em um bloco de código Os processos acessam os procedimentos de um monitor mas não as suas estruturas internas Somente um processo pode estar ativo no monitor por vez Esse conceito já vem incorporado nos compiladores de alto nível como JAVA através da palavra synchronized ATIVIDADE EXTRACLASSE Leitura Tanenbaum Sistemas Operacionais Modernos capítulo 2 Processos e Threads Pesquisa Problemas clássicos de comunicação e sincronização de processos O Jantar dos Filósofos O Barbeiro Adormecido