aula 7

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
Sistemas Operacionais
PROCESSOS
Propostas Para Obtenção de Exclusão Mútua
Algumas propostas para que a exclusão mútua seja obtida serão analisadas nesta seção. A primeira delas está associada a um buffer compartilhado por dois processos.
Buffers e Operações de Sleep e Wakeup
Existem algumas primitivas (rotinas) de comunicação entre processos que se caracterizam por bloquear o processo quando a este não é permitido entrar na sua seção crítica. Umas das mais simples são sleep (system call SLEEP) e wakeup (system call WAKEUP). SLEEP faz com que o processo que a chama seja bloqueado,
ou seja, seja suspenso até que outro processo o acorde. WAKEUP é uma system call que possui um parâmetro: o processo que deve ser acordado. Para exemplificar como estas primitivas são usadas, será abordado o problema do Produtor-Consumidor.
*
Sistemas Operacionais
PROCESSOS
No problema do Produtor-Consumidor, existem dois processos que compartilham um buffer, uma área de dados de tamanho fixo que se comporta como um reservatório temporário. Se Produtor e Consumidor são processos que executam em seqüência, a solução do problema é simples, mas se estes são processos que executam paralelamente passa existir a situação de concorrência. O processo Produtor coloca informações no buffer enquanto o Consumidor as retira de lá. Existem casos onde podem existir múltiplos Produtores ou múltiplos Consumidores, mas basicamente o problema encontrado é o mesmo. Estes são problemas clássicos de comunicação entre processos, tais como os problemas do jantar dos filósofos e
do barbeiro dorminhoco, discutidos em detalhes por Tanenbaum um um dos livros textos desta disciplina. O exemplo mostrado anteriormente, onde processos colocavam os nomes dos arquivos que eles desejavam que fossem impressos em um diretório (área) de spooler e um processo de gerenciamento de impressão imprimia os arquivos e os removia do diretório, é um exemplo do problema do Produtor-Consumidor. 
*
Sistemas Operacionais
PROCESSOS
No caso mais geral, tendo em mente que o diretório de spooler é finito, onde existem vários processos desejando imprimir (Produtores) e várias impressoras (Consumidores), as velocidades dos diversos processos que desejam imprimir podem ser consideravelmente diferentes das velocidades das impressoras.
Um outro exemplo pode ocorrer quando diversos processos utilizam uma placa de rede para realizar a transmissão de dados para outros computadores. Os vários processos aparecem como Produtores, enquanto o hardware da placa e seu código representam o Consumidor. Em função do tipo de rede e do tráfego, existe uma forte limitação com que a placa consegue consumir (transmitir) os dados produzidos pelos programas e colocados no buffer de transmissão. A Figura s seguir mostra a situação do problema do Produtor-Consumidor.
*
Sistemas Operacionais
PROCESSOS
*
Sistemas Operacionais
PROCESSOS
Tanto o buffer como a variável que controla a quantidade de dados do buffer, contador, são seções críticas e, portanto, deveriam ter seu acesso limitado por meio de primitivas de exclusão mútua, desde que isso não impusesse esperas demasiadas aos processos envolvidos.
Problemas ocorrem quando o Produtor deseja colocar uma nova informação (item) no buffer, mas este está cheio. A solução, do ponto de vista do Produtor, é este adormecer (rotina sleep . system call SLEEP) e ser acordado pelo Consumidor (rotina wakeup . system call WAKEUP) quando ele, Consumidor, remover um ou mais itens do buffer. De forma similar, se o Consumidor deseja remover um item do buffer e observa que o buffer está vazio, o Consumidor adormece até que o produtor coloque um ou mais itens no buffer e o acorde.
*
Sistemas Operacionais
PROCESSOS
Se a variável contador informa quantos itens existem atualmente no buffer, o Produtor deve verificar se contador é igual a N, onde N é o valor máximo de itens que o buffer pode comportar. Caso isto seja verdadeiro, o Produtor deve adormecer; caso contrário, o Produtor adicionará um item no buffer e incrementará contador. Do ponto de vista do Consumidor,primeiramente verifica-se se contador é igual a 0. Se isto for verdadeiro, então o Consumidor deve adormecer; senão, o Consumidor deve remover um item e decrementar contador. A Figura a seguir mostra os códigos-fonte do Produtor e Consumidor escritos em linguagem C.
*
Sistemas Operacionais
PROCESSOS
*
Sistemas Operacionais
PROCESSOS
Tentativa 1: Variável global: em_uso: boolean initial false;
A variável global indica se alguma região crítica está em uso ou não.
Código de um processo:
. . .
loop
	exit when ¬em_uso
endloop;
em_uso:=true;
REGIÃO CRÍTICA;
em_uso:= false;
. . .
A solução não é correta, pois os processos podem chegar à conclusão “simultaneamente”
que a entrada está livre (em_uso=false). Isto é, os dois processos podem ler (testar) o valor de em_uso antes que essa variável seja feita igual a true por um deles.
*
Sistemas Operacionais
OBSERVAÇÃO: Para os próximos algoritmos, supõe-se que os processos tenham duas variáveis locais, eu e outro. Para o processo 1, eu=1 e outro=2; para o processo 2, eu=2 e outro=1. Os códigos dos processos são iguais, mas cada processo usa suas variáveis privativas eu e outro.
Tentativa 2: Variável global: vez: integer initial 1; Esta variável indica de quem é a vez, na hora de entrar na região crítica.
Código de um processo:
. . .
loop
exit when vez=eu
endloop;
REGIÃO CRÍTICA;
vez:= outro;
. . .
 Este algoritmo garante exclusão mútua, mas obriga a alternância na execução das regiões críticas (isto é, primeiro entra P1, depois P2, depois P1, etc). Não é possível um mesmo processo entrar duas vezes consecutivamente. Se P2 desejar entrar primeiro na sua região crítica, ele não poderá fazê-lo, pois P1 deve ser o primeiro. Se um processo terminar, o outro não poderá mais entrar na sua região crítica. Não é aceitável que um processo tranque a entrada de outro sem necessidade.
*
Sistemas Operacionais
Tentativa 3: Variável global: quer: array[2] of boolean initial false;
Se quer[i] é true, isto indica que o processo Pi (i∈{1,2}) quer entrar na sua região crítica. Observe que o valor inicial especificado para um array (vetor ou matriz) se aplica a todos os elementos desse array. 
Código de um processo:
. . .
loop
	exit when ¬quer[outro]
endloop;
quer[eu]:=true;
REGIÃO CRÍTICA;
quer[eu]:=false;
. . .
A solução não assegura exclusão mútua. Repete-se aqui o mesmo problema da tentativa
1, pois cada processo pode chegar à conclusão que o outro não quer entrar e assim entrarem.
*
Sistemas Operacionais
Tentativa 4: Variável global: quer: array[2] of boolean initial false;
É o mesmo algoritmo anterior, porém marcando a intenção de entrar, antes de testar a intenção do outro processo.
Código de um processo:
. . .
quer[eu]:=true;
loop
	exit when ¬quer[outro]
endloop;
REGIÃO CRÍTICA;
quer[eu]:=false;
. . .
Com este algoritmo a exclusão mútua é garantida, mas, infelizmente, os processos podem
entrar em um loop eterno. Isto porque ambos os processos podem marcar “simultaneamente” a intenção de entrar (antes que um deles consiga testar, dentro do loop, se o outro quer entrar ou não). Nesse caso, depois de entrarem no loop, os processos não vão sair mais de lá.
*
Sistemas Operacionais
Tentativa 5: Variável global: quer: array[2] of boolean initial false;
É semelhante ao algoritmo anterior, porém o processo dá a vez para o outro no caso do outro querer entrar.
Código de um processo:
. . .
início: quer[eu]:=true;
	if quer[outro] then
	{ quer[eu]:=false;
goto inicio
};
REGIÃO CRÍTICA;
quer[eu]:=false;
. . .
A exclusão mútua continua garantida, mas pode acontecer dos processos ficarem dando a
vez um para o outro indefinidamente. Embora essa “sincronização” dos processos seja difícil de acontecer na prática, ela não deixa de ser teoricamente possível. 
*
Sistemas Operacionais
O algoritmo seguinte soluciona
definitivamente o problema, usando uma variável adicional vez para resolver as situações de empate. Esta variável só é usada quando os dois processos querem entrar simultaneamente nas regiões críticas. 
Esta solução foi proposta pelo matemático holandês T. Dekker e discutida por Dijkstra. Trata-se da primeira solução completa para o problema. Conforme já referido, é similar ao algoritmo anterior. A diferença está no uso da variável vez, para realizar o desempate (tie-break). No caso em que os dois processos entram no bloco entre chaves, só um deles (decidido pelo valor da variável vez) dá a vez para o outro.
*
Sistemas Operacionais
Solução de Dekker: Variáveis globais: quer: array[2] of boolean initial false;
vez: integer initial 1;
Código de um processo:
. . .
início: quer[eu]:=true;
denovo: if quer[outro] then
	{ if vez=eu then goto denovo;
		quer[eu]:=false;
		loop
			exit when vez=eu
		endloop;
		goto início
		};
		REGIÃO CRÍTICA;
		quer[eu]:=false;
	vez:=outro;
	. . .
*
Sistemas Operacionais
Solução de Dekker: O algoritmo satisfaz todas as exigências para a solução ser considerada correta, quaisquer que sejam as velocidades relativas dos processos. Por exemplo, não acontece de um processo ficar eternamente tentando entrar na sua região crítica enquanto o outro, mais veloz, entra e sai repetidamente da sua região crítica.
Várias outras soluções forma apresentadas ao longo do tempo. Ressaltaremos aqui o uso de semáforos
*
Sistemas Operacionais
PROCESSOS
Semáforos
Dentro do contexto apresentado no tópico anterior, Dijkstra propôs em 1965 a utilização de variáveis inteiras para controlar o número de sinais wakeup para uso futuro. Na proposta apresentada por ele, um novo tipo de variável, denominada semáforo, foi introduzido. Um semáforo poderia ter um valor 0, indicando que nenhum wakeup foi salvo, ou algum valor positivo se um ou mais sinais wakeup estão pendentes.
Duas operações foram estabelecidas para atuar sobre as variáveis do tipo semáforo: P (conhecida também como down . System call DOWN) e V (conhecida também como up . system call UP), que são generalizações de sleep e wakeup, respectivamente. O funcionamento de DOWN e UP é descrito na Figura a seguir
*
Sistemas Operacionais
PROCESSOS
*
Sistemas Operacionais
PROCESSOS
Ambas as operações devem ser realizadas como ações atômicas, ou seja, de forma indivisível. Deste modo, garante-se que, uma vez que uma operação de semáforo foi iniciada, nenhum outro processo pode acessar o semáforo até que a operação tenha sido completada ou bloqueada. A maneira usual de fazer isto é implementar DOWN e UP como chamadas ao sistema, com o SO desabilitando todas as interrupções enquanto está testando o semáforo, atualizando-o e colocando o processo para dormir, se for necessário. Todas estas ações consomem apenas umas poucas instruções, não ocasionando maiores problemas ao desabilitar as interrupções. Portanto, para o caso de DOWN, verificar o valor do semáforo, modificá-lo e possivelmente colocar o processo para dormir é feito de forma indivisível. Para o caso de UP, incrementar o semáforo e, possivelmente, acordar um processo é feito de maneira indivisível. Nenhum processo se bloqueia realizando um UP, assim como nenhum processo se bloqueia realizando um WAKEUP no modelo anterior.
*
Sistemas Operacionais
PROCESSOS
*
Sistemas Operacionais
PROCESSOS
*
Sistemas Operacionais
PROCESSOS
A solução apresentada usa três semáforos. O semáforo cheio conta o número de slots que estão cheios no buffer, o semáforo vazio conta o número de slots vazios no buffer enquanto o semáforo mutex assegura que o Produtor e o Consumidor não acessam o buffer ao mesmo tempo. O semáforo cheio está 0 inicialmente, enquanto vazio inicia com valor igual ao número de slots no buffer e mutex inicialmente vale 1. Semáforos que são iniciados com 1 e que são usados por dois ou mais processos para assegurar que somente um deles possa entrar na sua seção crítica por vez são chamados de semáforos binários. Se cada processo realizar um DOWN imediatamente antes de entrar na sua seção crítica e um UP logo após sair dela, a exclusão mútua está garantida.
*
Sistemas Operacionais
PROCESSOS
Na Figura apresentada semáforos foram usados de duas maneiras distintas. O semáforo mutex foi usado para exclusão mútua. O objetivo dele é garantir que somente um processo por vez possa ler do ou escrever no buffer e variáveis associadas. O outro uso de semáforos é para sincronização. Os semáforos cheio e vazio são necessários para garantir que certas seqüências de eventos possam ou não ocorrer. Neste caso, eles asseguram que o Produtor pára de executar se o buffer estiver cheio, e o Consumidor pára de executar quando o buffer estiver vazio. Este uso é diferente do caso de exclusão mútua. A utilização de semáforos permite, portanto, a sincronização de vários processos. Em outras palavras, em um ambiente onde existem vários processos concorrendo por recursos, semáforos podem ser usados para garantir o uso exclusivo de um recurso por um processo
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*