Estudo Dirigido s Captulo 7 Sincronizao de processos Um processo cooperativo pode afetar ou ser afetado pelos outros processos que esto trabalhando com ele no sistema. Por exemplo, caso dois processos cooperativos compartilharem a mesma rea de memria preciso garantir a consistncia dos dados, pois, a ao de um processo sobre eles pode afetar o trabalho do outro. Para procedimentos produtor/consumidor Condio de corrida: quando as threads compartilham acesso ao mesmo dado e que a ordem com que cada uma chega ao dado afeta o resultado final. Para garantir a exatido do resultado final devemos impedir que duas threads acessem o memso dado concorretemente: precisamo de sincronizao. Seo crtica: parte do cdigo de uma thread que est acessando recursos compartilhados com outras threads. A questo : quando uma thread estiver usando sua seo crtica, nenhuma outra thread poder usar sua prpria seo crtica. O problema como escolher um protocolo que os threads possam usar para cooperar. A soluo deve satisfazer: excluso mtua: se uma thread tiver executando sua seo crtica, nenhuma outra thread poder estar executando sua seo crtica. Progresso: se nenhuma thread estiver executando sua seo crtica e houver algumas threads que desejam entrar em suas sees crticas, apenas threads que no estiverem executando a seo crtica podero decidir que executar em seguida espera limitada: existe um limite no nmero de vezes que outros threads podem entrar em suas seoes crticas depois que um thread tiver solicitado para entrar na sua seo crtica. Solues para o problema da seo crtica: introduzir uma flag que permita identificar se uma thread pode ser ou no executada(seo crtica). Instrues de hardware podem faciltar o problema de seo crtica: a soluo em um ambiente monoprocessador tornar o cdigo da seo crtica uma unidade atmica: isto , no pode ser interrompida enquanto est sendo executada. Para multiprocessadores, essa soluo invivel. Deve-se tratar a execuo de uma rea crtica como atmica. Exemplo em java: criamos uma classe lock, as quais as threads terao acesso. Para generalizar a soluo do problema da seo crtica utilizamos semforos. Semforo uma varivel inteira que, alm da inicializao, s acessada atrave de duas operaes padro: P e V. Uso de semforos: sistemas operacionais utilizam dois tipos de semforos: semforo de contagem ou semforos binrios (0,1). O processo vai executar e faz um loop que verificia o semforo. Esse loop executa at o sinal ficar verde. Isto , uma thread est executando sua seo crtica e o semforo fica vermelho para as outras threads. Elas ficam executando um loop, quando o sinal fica verde, ento elas executam e setam o sinal para vermelho para as outras.

Os casos em que a espera fica no loop so chamados spinloks. S so teis caso haja vrios processadores. Para contornar esse problema do spinlok de ficar executando um loop que consome cpu, o processo pode se bloquear, a ele entra em estado de espera e o escalonador de curto prazo (cpu) escolhe outro processo da fila, e ele entra na fila de espera pela cpu novamente. Esse processo deve voltar quando algum processo executar uma operacao que torne o semforo verde. O processo sai do estado de espera e passa ao estado de pronto entrando na fila de processos prontos e fica dependendo do algoritmo de escalonamento da cpu. Implementao do semforo: um inteiro e uma lista de processos. As operaes de setar o semforo devem ser atomicas, isto , quando executadas no podem ser interrompidas. Isso vlida para sistemas monoprocessadores. Para multiprocessadores: a soluo deve ser uma soluo de seo crtica em nvel de software. DeadLock: na implementao de semforos pode ocorrer de um processo A esperar B para ser executado e B esperar A para ser executado. Problemas classicos de sincronizao: quando implementamos uma soluo para a seo crtica ela deve passar nos testes dos problemas clssicos. - O problema do buffer limitado: produtor/consumidor Temos um buffer limitado e varveis cheio e vazio. O produtor s preenche o buffer, com uma operao atmica, se ele estiver vazio, e o consumidor s procede a operao de leitura se o buffer estiver cheio. problema dos leitores-escritores: um leitor quer ler um dado do banco de dados e um escritor quer atualizar um registro. Para contornar o problema os leitores devem ter prioridade de acesso ao banco de dados. Quando um leitor le ele impede um escritor de escrever no banco de dados. O problema do jantar dos filsofos: a mesa tem hashis, quando um filosofo esta com fome ele pega dois hashis. Pode ocorrer deadlock caso todos os filosofos estejam com fome e peguem o hashi da direita por exemplo. Para contornar esse problema: deve-se limitar o nmero de filsofos, intercalar: filosofo par pega o da direita e esquerda, filsofo impar pega o da esquerda e direita. Permitir que o filosofo pegue um hashi somente se houver dois hashis disponiveis. Outra forma de sincronizar os processos com o uso de monitores. Os semforos so falhos em determinados momentos e difceis de detectar erros. Erros de programao e de uso de semforos podem prejudicar a sincronizao de processos e causar deadlocks. Para contornar esse problema desenvolveu-se estruturas de alto nvel: monitores. O tipo monitor um TAD que encapsula seus dados (variaveis) e exibe apenas mtodos publicos. A prpria estrutura do tipo limita a sua utilizao. Se uma thread est executando um mtodo do monitor x, nenhuma outra pode executar tambm. Dessa maneira, a excluso mtua acontece devido a natureza do tipo monitor. Temos basicamente dois metodos:

wait: indica que a thread que executou essa operao ficar suspensa at outra thread chame signal: retorna uma thread. Captulo 8 DeadLocks o deadlock ocorre quando um conjunto de processos que est em estado de espera depende da liberao de um recurso de um dos processos desse conjunto. Modelo de sistema: os sistemas de computador tem um nmero finito de recursos a serem distribuidos a processos concorrentes. preciso organizar o acesso aos recursos para que no haja conflito entre os processos. Em geral o processo faz o pedido do recurso, o recurso usado por este processo e depois liberado. Os processos entram em estado de deadlock quando todos os processos do conjunto esto esperando por um evento que pode ser causado apenas por outro processo desse conjunto. Caracterizao dos deadLocks: preciso que 4 condies existam para haver a possibilidade de ocorrer um deadlock no sistema: Condio 1: excluso mtua: apenas um processo por vez pode usar o recurso. Se outro processo solicitar o recurso o solicitante dever esperar at que o recurso seja liberado. Condio 2: Posse e espera: deve haver um processo que esteja mantendo um recurso alocado enquanto espera obter recursos adicionais que estejam sendo mantidos por outros processos no momento. Condio 3: No prempo: os recursos no podem sofrer preempo, ou seja, o recurso s liberado voluntariamente. Condio 4: Espera circular: p1 espera por p2, p2 espera pn, at q pultimo espera por p1. Os deadlock podem ser descrito atravs de grafos: h um deadlock se h um ciclo em um grafo de processos/recursos. Mtodos para tratar deadlocks Basicamente existem 3 mtodos para tratar deadlocks: 1- podemos usar um protocolo para garantir que o sistema nunca entre em estado de deadlock para garantir que os deadlocks nunca ocorrero o sistema pode utilizar um esquema de preveno de deadlocks. O sistema limita a forma como os pedidos de recursos podem ser feitos. Para tanto, o sistema operacional carece de informaes extras sobre quais recursos o processo utilizar. Preveno de deadlocks: Para que um deadlock ocorra uma das 4 condies deve ocorrer. Para evitar que ele ocorra preciso eliminar ao menos uma das condies: Excluso mtua: exigir excluso mtua apenas para recursos no compartilhveis. Para todos os casos em que for possvel compartilhar o acesso, permitir o acesso. Posse e espera: para garantir que a posse e espera nunca vai ocorrer preciso ter certeza que sempre que um processo solicitar um recurso ele no mantenha outros. Um protocolo que pode ser usado, exige que o processo solicite e receba todos os seus recursos antes de comear a execuo. Um protocolo alternativo permite que um processo solicite recursos apenas quando o processo no tiver nenhum. Assim, ele deve liberar os recursos que aloca antes de galgar um novo. No primeiro caso, o processo fica com recursos alocados que no est utilizando no momento. Caso um processo precise de muitos recursos ele poder ficar paralisado, pois, os recursos

populares sempre estaro alocados em outros processos. No preempo: para garantir que no haja no preempo podemos utilizar o seguinte protocolo: se um processo estiver em posse de alguns recursos e solicitar outros recursos que no so imediatamente alocados a ele e ele tiver que esperar, ento todos os recursos so submetidos a preempo. Assim os recursos estaro disponveis e o processo vai se apossar deles. Como alternativa, se um processo solicitar alguns recursos, primeiro verificamos se eles esto disponveis, caso estejam, so alocados. Se no estiverem, verificamos se esto alocados a algum outro processo que est esperando recursos adicionais. Se for esse o caso, os recursos desejados so arrancados do processo em espera e cedidos ao solicitante. Esse protocolo no pode ser aplicado para recursos como impressoras e drivers de fita magntica. A preempo no pode ser aplicadas a todos os recursos. Espera circular: para impedir a espera circular numeramos os processos e exigimos que um processo s obtenha recursos de algum outro com nmero maior que o seu. Impedimento de deadlocks: os algoritmos de preveno de deadlocks evitam que ele ocorra mas eles so muito caros: causam a baixa utilizao do sistema, pouco trabalho/tempo throughput e potencial paralisao( um processo ficar eternamente esquecido). Um mtodo alternativo o usurio informar quais recursos sero utilizados. Assim o sistema operacional ter informaes a respeito dos processo e decidir como ele ir fornecer os recursos solicitados.

2- podemos permitir que o sistema entre em estado de deadlock e, em seguida, se recupere. Deteco de deadlock: caso o sistema no previna deadlocks ele poder fornecer: um algoritmo que examine o estado do sistema e determine se ocorreu um deadlock um algoritmo para recuperar o sistema do deadlock importante reconhecer que: alm do custo de execuo do algoritmo de deteco e correo do deadlock, depois de recuperado podem haver prejuzos quanto a recuperao. Podemos detectar o deadlock se reconhecermos um ciclo no grafo de espera, uma variante do grafo de alocao de recursos. Este algoritmo requer n operaes. Esse algoritmo deve ser chamado em 40% da utilizao da cpu, indicando uma paralisia do processamento, ou quando uma solicitao de recurso no for atendida: nesse caso, a solicitao pode no ter sido atendida por causa de deadlock. Recuperao de deadlock: para quebrar o deadlock o sistema pode abortar um ou mais processos envolvidos nele, ou fazer a preempo de algum dos recursos. Trmino de processos: Abortar todos os processos: elimina o deadlock mas tem grande custo, pois, perde-se todo o trabalho de computao. Abortar um processo de cada vez: envolve um grande custo, pois, a cada eliminao o algoritmo de deteco de deadlock dever ser executado. preciso avaliar a prioridade do processo a ser abortado, tempo j processado, recursos alocados, quantos recursos mais o processo precisa para concluir. Preempo de recursos fazemos a preempo sucessiva de alguns recursos e conferimos esses recursos a outros processos at quebrar o deadlock. 1 seleo da vtima: escolher o recurso a sofrer preempo Rollback (volta ao passado): se fizermos a preempo de um recurso o que ocorrer com o processo? Devemos pegar esse processo abort-lo e reinici-lo. Starvation (paralisao): como garantir que no haver paralisao? Como garantir que o

processo que sofre a preempo no ser sempre o mesmo? O processo deve sofre um nmero finito de preempes. 3- podemos ignorar o problema e fingir que os deadlocks nunca ocorrem no sistema. A terceira soluo muito usada e cabe ao desenvolvedor escrever programas que no entrem em deadlocks. Um sistema pode implementar um preveno de deadlocks. Caso no implemente uma preveno de deadlocks dever fornecer um meio do sistema reconhecer o deadlock e poder se recuperar depois. Caso o sistema no fornea nada disso, ao ocorrer um deadlock os recursos ficaram alocados diminuindo o desempenho do sistema e causando ainda mais deadlocks, at que ele parar de funcionar e precisar ser reiniciado manualmente.