Capítulo 7 - Fundamentos de sistemas operacionais

Prévia do material em texto

Exercícios Práticos 
1. Liste três exemplos de deadlocks que não estejam relacionados com um ambiente de sistema de 
computação. 
● Dois carros atravessando uma ponte deihigjihcxkkblnlllnlocbvv mão única vindos de direções 
opostas. 
● Uma pessoa descendo uma escada de mão enquanto outra pessoa está subindo pela escada de mão. 
● Dois trens seguindo um em direção ao outro no mesmo trilho. 
2. Suponha que um sistema esteja em um estado inseguro. Mostre que é possível que os processos 
completem sua execução sem entrar em estado de deadlock. 
Um estado inseguro não necessariamente leva ao deadlock, ele apenas indica que não podemos 
garantir que o deadlock não ocorrerá. Porém, é possível que um sistema em um estado inseguro ainda 
possa permitir que todos os processos terminem sem que ocorra o deadlock. Considere a situação em que 
um sistema possui 12 recursos alocados entre os processos P0, P1 e P2. Os recursos são alocados de acordo 
com a seguinte política: 
 
 Máximo Atual Necessário 
P0 10 5 5 
P1 4 2 2 
P2 9 3 6 
 
 
Atualmente, existem dois recursos disponíveis. Esse sistema está em um estado inseguro porque o 
processo P1 poderia completar, liberando assim um total de quatro recursos. Mas não podemos garantir 
que os processos P0 e P2 podem completar. Porém, é possível que um processo possa liberar recursos antes 
de requisitar algum outro. Por exemplo, o processo P2 poderia liberar um recurso, aumentando assim o 
número total de recursos para cinco. Isso faz com que o processo P0 conclua, o que liberaria um total de 
nove recursos, permitindo assim que o processo P2 também conclua. 
 
3. Considere o seguinte instantâneo de um sistema: 
 Alocação Max Disponível 
 A B C D A B C D A B C D 
P​0 0 0 1 2 0 0 1 2 1 5 2 0 
P​1 1 0 0 0 1 7 5 0 
P​2 1 3 5 4 2 3 5 6 
P​3 0 6 3 2 0 6 5 2 
P​4 0 0 1 4 0 6 5 6 
Responda as perguntas a seguir usando o algoritmo do banqueiro: 
a. Qual é o conteúdo da matriz ​Necessidade​? 
A Matrix de necessidade é obtida subtraindo Max-Alocação: 
0012-0012 = 0000 
1750-1000 = 0750 
2356-1354 = 1002 
0652-0632 = 0020 
0656-0014 = 0642 
Os valores de Necessário para os processos de P0 a P4, respectivamente, são (0, 0, 0, 0), (0, 7, 5, 0), (1, 0, 0, 
2), (0, 0, 2, 0) e (0, 6, 4, 2). 
b. O sistema está em um estado seguro? 
Sim. Com Disponível sendo igual a (1, 5, 2, 0), o processo P0 ou P3 poderia ser executado. Quando o 
processo P3 é executado, ele libera seus recursos, o que permite que todos os outros processos existentes 
sejam executados. 
c. Se uma solicitação do processo ​P​1​ chega para (0,4,2,0), ela poderá ser atendida imediatamente? 
Sim, poderá. Isso resulta no valor de Disponível sendo (1520)-(0420) =(1, 1, 0, 0).Uma ordenação dos 
processos que podem terminar é P0, P2, P3, P1 e P4. 
 
4. Um método possível para a prevenção de deadlocks é o uso de um recurso único de ordem superior que 
deve ser solicitado antes de qualquer outro recurso. Por exemplo, se vários threads tentarem acessar os 
objetos de sincronização ​A​… ​E​, pode ocorrer um deadlock. (Esses objetos de sincronização podem 
incluir mutexes, semáforos, variáveis de condição, e assemelhados.) Podemos prevenir o deadlock 
adicionando um sexto objeto ​F​. Sempre que um thread quiser adquirir o lock de sincronização de 
qualquer objeto ​A​… ​E​, deverá primeiro adquirir o lock para o objeto ​F​. Essa solução é conhecida como 
contenção​: os locks para os objetos ​A​… ​E estão contidos dentro do lock para o objeto ​F​. Compare esse 
esquema com o esquema de espera circular da ​Seção 7.4.4​. 
Provavelmente não é uma boa solução, porque produz um alcance muito grande. É melhor definir uma 
política de bloqueio com um alcance tão estreito quanto possível 
 
5. Prove que o algoritmo de segurança apresentado na ​Seção 7.5.3​ requer uma ordem de ​m​ × ​n​2 ​operações. 
 
Como podemos ver, os loops externos aninhados – ambos repetindo n vezes – oferecem o desempenho n2. 
Dentro desses loops externos existem dois loops seqüenciais internos, que se repetem m vezes. A grande 
ordem desse algoritmo é, portanto, O(m × n2). 
 
6. Considere um sistema de computação que executa 5.000 jobs por mês e não tem esquema que previna ou 
evite deadlocks. Os deadlocks ocorrem aproximadamente duas vezes por mês e o operador deve encerrar 
e reexecutar cerca de 10 jobs por deadlock. Cada job custa cerca de – dólares (em tempo de CPU) e os 
jobs encerrados costumam chegar até o meio e então são abortados. 
Um programador de sistemas estimou que um algoritmo para evitar deadlocks (como o algoritmo do 
banqueiro) poderia ser instalado no sistema com um aumento de cerca de 10% no tempo médio de 
execução por job. Já que no momento a máquina tem 30% do tempo ocioso, todos os 5.000 jobs por mês 
poderiam ainda estar em execução, embora o tempo de turnaround aumentasse em média cerca de 20%. 
a. Quais são os argumentos para a instalação do algoritmo que evita a ocorrência de deadlocks? 
Um argumento para instalar uma forma de evitar deadlock no sistema é que poderíamos garantir que o 
deadlock nunca ocorreria. Além disso, apesar do aumento do tempo de retorno, todas as 5.000 tarefas 
ainda poderiam ser executadas. 
b. Quais são os argumentos contra a instalação do algoritmo que evita a ocorrência de deadlocks? 
Um argumento contra a instalação do software para evitar deadlocks é que eles ocorrem com pouca 
freqüência e custam muito pouco quando ocorrem. 
 
7. Um sistema pode detectar que algum de seus processos está sofrendo de inanição? Se você responder 
“sim”, explique como ele pode fazer isso. Se responder “não”, explique como o sistema pode lidar com o 
problema da inanição. 
A starvation é um tópico difícil de se definir, pois pode significar que diferentes coisas para 
diferentes sistemas. Para os propósitos desta pergunta, definiremos starvation como a situação em que um 
processo precisa esperar além de um período razoável – talvez indefinidamente – antes de receber um 
recurso requisitado. Uma maneira de detectar starvation seria primeiro identificar um período de tempo – 
T – que seja considerado excessivo. Quando um processo requisita um recurso, um temporizador é 
iniciado. Se o tempo gasto ultrapassar T, então tal processo é considerado como em starvation. 
Uma estratégia para lidar com starvation seria adotar uma política na qual os recursos são 
atribuídos apenas ao processo que esteve esperando por mais tempo. Por exemplo, se o processo Pa esteve 
esperando por mais tempo pelo recurso X do que o processo Pb, a requisição do processo Pb seria adiada 
até que a requisição do processo Pa tivesse sido satisfeita. 
Outra estratégia seria menos estrita do que a que acabamos de mencionar. Nesse cenário, um 
recurso poderia ser concedido a um processo que tenha esperado menos do que outro processo, desde que o 
outro não esteja sendo adiado. Porém, se outro processo for considerado em starvation, sua requisição seria 
satisfeita primeiro. 
 
8. Considere a política de alocação de recursos a seguir. Solicitações e liberações de recursos são permitidas 
a qualquer momento. Quando uma solicitação de recursosnão pode ser atendida porque os recursos não 
estão disponíveis, procuramos quaisquer processos que estejam bloqueados esperando por recursos. Se 
um processo bloqueado obtiver os recursos desejados, esses recursos serão retirados dele e passados ao 
processo solicitante. O vetor de recursos pelos quais o processo bloqueado está esperando é aumentado 
para incluir os recursos que foram removidos. 
Por exemplo, um sistema tem três tipos de recursos, e o vetor ​Disponível é inicializado com (4,2,2). 
Se o processo ​P​0 solicitar (2,2,1), ele os receberá. Se ​P​1 solicitar (1,0,1), ele os receberá. Em seguida, se 
P​0 solicitar (0,0,1), ele será bloqueado (recurso não disponível). Agora se ​P​2 solicitar (2,0,0), ele receberá 
o recurso disponível (1,0,0), assim como um recurso que foi alocado a ​P​0 (já que ​P​0 está bloqueado). O 
vetor ​Alocação​ de ​P​0​ diminui para (1,2,1) e seu vetor ​Necessidade​ aumenta para (1,0,1). 
a. Pode ocorrer um deadlock? Se você responder “sim”, dê um exemplo. Se responder “não”, 
especifique que condição necessária não pode ocorrer. 
O deadlock não pode ocorrer porque existe preempção. 
b. Pode ocorrer um bloqueio indefinido? Explique sua resposta. 
Sim. Um processo pode nunca adquirir todos os recursos de que precisa se eles forem continuamente 
preemptados por uma série de requisições, como aquelas do processo C. 
 
9. Suponha que você tenha codificado o algoritmo de segurança que evita deadlocks e agora tenha sido 
solicitado a implementar o algoritmo de detecção de deadlocks. Você pode fazer isso simplesmente 
usando o código do algoritmo de segurança e redefinindo ​Max​i = ​Espera​i + ​Alocação​i​, em que ​Espera​i é 
um vetor que especifica os recursos pelos quais o processo ​i está esperando e ​Alocação​i ​segue o definido 
na ​Seção 7.5​? Explique sua resposta. 
Sim. O vetor Máximo representa a requisição máxima que um processo pode fazer. Ao calcular o algoritmo 
de segurança, usamos a matriz Necessário, que representa Máximo – Alocação. Outra maneira de pensar 
nisso é Máximo = Necessário + Alocação. De acordo com a pergunta, a matriz Esperando possui um papel 
semelhante à matriz Necessário; portanto, Máximo = Esperando + Alocação. 
 
10. É possível ocorrer um deadlock envolvendo apenas um processo com um único thread? Explique sua 
resposta. 
Não. Isso segue diretamente da condição de manter e esperar. 
Exercícios 
11. Considere o deadlock de tráfego mostrado na ​Figura 7.10​. 
a. Mostre que as quatro condições necessárias para a ocorrência do deadlock estão presentes nesse 
exemplo. 
As quatro condições necessárias para um deadlock são: 
(1) exclusão mútua; 
(2) manter e esperar; 
(3) não-preempção; e 
(4) espera circular. 
 A condição de exclusão mútua existe porque somente um carro pode ocupar um espaço na rua. Manter e 
esperar ocorre quando um carro mantém seu lugar na rua enquanto espera para avançar na rua. Um carro 
não pode ser removido (ou seja, preemptado) de sua posição na rua. Por fim, há realmente uma espera 
circular porque cada carro está esperando que um carro subseqüente avance. A condição de espera 
circular também é facilmente observada no do desenho. 
b. Defina uma regra simples para evitar deadlocks nesse sistema. 
Uma regra simples que evitaria esse deadlock de tráfego é que um carro não pode avançar para um 
cruzamento, se estiver vazio, a menos que possam sair imediatamente da interseção, ou seja, nenhum carro 
pode parar em um cruzamento. 
 
12. Suponha que uma aplicação multithreaded use apenas locks de leitor ​gravador para a sincronização. 
Considerando as quatro condições necessárias para a ocorrência de deadlocks, continua ainda possível 
ocorrer um deadlock se vários locks de leitor​ gravador forem usados? 
SIM. 
(1) A exclusão mútua é mantida, pois não podem ser compartilhadas se houver um escritor. 
(2) Espera Ocupada é possível, uma vez que uma trhead pode conter um bloqueador de escrita-leitura 
enquanto espera para adquirir outro. 
(3) Você não pode tirar do bloqueio, portanto, a não preempção é mantida. 
(4) É possível uma espera circular entre todas as Threads. 
 
13. O exemplo de programa mostrado na ​Figura 7.4 nem sempre leva a um deadlock. Descreva que papel o 
scheduler da CPU desempenha e como ele pode contribuir para a ocorrência de deadlocks nesse 
programa. 
 
Figura 7.10​ Deadlock de tráfego do ​Exercício 7.11​. 
Se a thread um estiver escalonada antes do thread 2 e a thread 1 for capaz de adquirir ambos os 
bloqueios mutex antes do thread 2 estar escalonada, o deadlock não ocorrerá. O Deadlock só 
pode ocorrer se qualquer, thread 1 ou thread 2, é capaz de adquirir apenas um bloqueio antes 
que outra thread adquira o segundo bloqueio. 
 
14. Na ​Seção 7.4.4​, descrevemos uma situação em que prevenimos deadlocks assegurando que todos os 
locks sejam adquiridos em determinada ordem. No entanto, também ressaltamos que é possível ocorrer 
um deadlock nessa situação se dois threads invocarem simultaneamente a função ​transaction ( )​. 
Corrija a função ​transaction ( )​ para prevenir deadlocks. 
Adicione um novo lock a esta função. Este terceiro lock deve ser adquirido antes que os dois locks 
associados às contas sejam adquiridos. A função transaction () agora aparece da seguinte forma: 
 
void transaction(Account from, Account to, double amount) 
{ 
Semaphore lock1, lock2, lock3; 
wait(lock3); 
lock1 = getLock(from); 
lock2 = getLock(to); 
wait(lock1); 
wait(lock2); 
withdraw(from, amount); 
deposit(to, amount); 
signal(lock3); 
signal(lock2); 
signal(lock1); 
} 
 
15. Compare o esquema de espera circular com os diversos esquemas para evitar deadlocks (como o 
algoritmo do banqueiro) com relação às questões a seguir: 
a. Overheads no tempo de execução 
b. Throughput do sistema 
Um esquema para evitar Deadlock tende a aumentar os custos gerais de tempo de execução, devido ao 
custo da faixa de manter o atual recurso alocado. Entretanto, um esquema para evitar Deadlock 
permite um uso mais simultâneo de recursos do que esquemas que impedem estaticamente a formação 
do deadlock. Nesse sentido, um esquema de evitar o deadlock pode aumentar o rendimento do sistema. 
16. Em um sistema de computação real, nem os recursos disponíveis nem as demandas dos processos por 
recursos são consistentes por longos períodos (meses). Os recursos quebram ou são substituídos, novos 
processos vêm e vão, e novos recursos são comprados e adicionados ao sistema. Se o deadlock é 
controlado pelo algoritmo do banqueiro, quais das alterações a seguir podem ser feitas com segurança 
(sem introduzir a possibilidade de ocorrência de deadlocks) e sob que circunstâncias? 
a. Aumento de ​Disponível​ (novos recursos adicionados). 
Isso pode ser alterado sem problemas. 
b. Diminuição de ​Disponível​ (recurso removido permanentemente do sistema). 
Isso poderia ter um efeito no sistema e introduzir a possibilidade de deadlock como a segurança do 
sistema assumiu que havia um certo número de recursos disponíveis. 
c. Aumento de ​Max para um processo (o processo quer mais recursos ou precisa de mais recursos 
do que o permitido). 
Isso poderia ter um efeito no sistema e introduzir a possibilidade de deadlock. 
d. Diminuição de ​Max​ para um processo (o processo decideque não precisa de tantos recursos). 
Isso pode ser alterado sem problemas. 
 e. Aumento do número de processos. 
Isso pode ser permitido assumindo que os recursos foram alocados para o (s) novo (s) processo (s) de 
modo que o sistema não entre em um estado inseguro. 
 ​f. Diminuição do número de processos. 
Isso pode ser alterado com segurança sem problemas. 
 
17. Considere um sistema composto por quatro recursos do mesmo tipo que são compartilhados por três 
processos, cada um precisando de no máximo dois recursos. Mostre que o sistema está livre de 
deadlocks. 
Suponha que o sistema esteja em deadlock. Isso implica que cada processo está segurando um recurso 
e está aguardando mais um. Uma vez que existem três processos e quatro recursos, um processo deve 
ser capaz de obter dois recursos. Este processo não requer mais recursos e, portanto, retornará seus 
recursos quando terminar. 
 
18. Considere um sistema composto por ​m recursos do mesmo tipo sendo compartilhados por ​n ​processos. 
Um processo pode solicitar ou liberar apenas um recurso de cada vez. Mostre que o sistema está livre de 
deadlocks se ocorrerem as duas condições a seguir: 
a. A necessidade máxima de cada processo está entre um recurso e ​m​ recursos. 
b. A soma de todas as necessidades máximas é menor do que ​m​ + ​n​. 
 
19. Considere a versão do problema dos filósofos comensais em que os chopsticks são colocados no centro 
da mesa e qualquer par deles pode ser usado por um filósofo. Suponha que as solicitações de chopsticks 
sejam feitas uma de cada vez. Descreva uma regra simples para determinar se uma solicitação específica 
pode ser atendida sem causar deadlock, dada a alocação corrente de chopsticks para os filósofos. 
A seguinte regra evita o deadlock: quando um filósofo faz um pedido para o primeiro chopstick, não 
conceda a solicitação se não houver outro filósofo com dois chopsticks e se houver apenas um chopstick 
restante. 
 
20. Considere novamente a situação do exercício anterior. Suponha que agora cada filósofo precise de três 
chopsticks para comer. As solicitações de recursos ainda são emitidas uma de cada vez. Descreva 
algumas regras simples para determinar se uma solicitação específica pode ser atendida sem causar um 
deadlock, dada a alocação corrente de chopsctiks para os filósofos. 
Quando um filósofo faz um pedido para um ​chopstick​, aloque a solicitação se: 
1) o filósofo tem dois chopsticks e há pelo menos um chopstick restante, 
2) o filósofo tem um chopstick e há pelo menos dois chopsticks restantes, 
3) há pelo menos um chopstick remanescente, e há pelo menos um filósofo com Três chopsticks 
4) o filósofo não tem chopsticks, há dois chopsticks restantes, e há pelo menos um outro filósofo com 
dois chopsticks atribuídos. 
 
21. Podemos obter o algoritmo do banqueiro para um único tipo de recurso a partir do algoritmo do 
banqueiro geral simplesmente reduzindo de 1 unidade a dimensionalidade dos diversos arrays. Mostre, 
por meio de um exemplo, que não podemos implementar o esquema do banqueiro para múltiplos tipos de 
recursos aplicando o esquema do único tipo de recurso, para cada tipo de recurso individualmente. 
Considere um sistema com os recursos A, B e C e os processos P0, P1, P2, P3 e P4 com os seguintes valores 
de Alocação: 
 
Alocação 
 A B C 
P0 0 1 0 
P1 3 0 2 
P2 3 0 2 
P3 2 1 1 
P4 0 0 2 
 
E o valor a seguir de Necessário: 
 
Necessário 
 A B C 
P0 7 4 3 
P1 0 2 0 
P2 6 0 0 
P3 0 1 1 
P4 4 3 1 
 
Se o valor de Disponível for (2 3 0), podemos ver que uma requisição do processo P0 para (0 2 0) 
não pode ser satisfeita, pois isso reduz Disponível para (2 1 0) e nenhum processo poderia ser terminado 
com segurança. 
Porém, se tivéssemos de tratar os três recursos como três tipos de único recurso do algoritmo do 
banqueiro, obteríamos o seguinte: 
Para o recurso A (que temos dois disponíveis), 
 
 Alocado Necessário 
P0 0 7 
P1 3 0 
P2 3 6 
P3 2 0 
P4 0 4 
Os processos poderiam terminar com segurança na ordem de P1, P3, P4, P2, P0. 
Para o recurso B (que agora temos um disponível, pois dois foram considerados atribuídos ao processo P0), 
 
 Alocado Necessário 
P0 3 2 
P1 0 2 
P2 0 0 
P3 1 1 
P4 0 3 
 
Os processos poderiam terminar com segurança na ordem de P2, P3, P1, P0, P4. 
E, finalmente, para o recurso C (que temos 0 disponível), 
 
 Alocado Necessário 
P0 0 3 
P1 2 0 
P2 2 0 
P3 1 1 
P4 2 1 
Os processos poderiam terminar com segurança na ordem de P1, P2, P0, P3, P4. 
 
Como podemos ver, se usarmos o algoritmo do banqueiro para múltiplos tipos de recursos, a requisição 
para os recursos (0 2 0) do processo P0 é negada porque deixa o sistema em um estado inseguro. Porém, se 
considerarmos o algoritmo do banqueiro para os três recursos separados, em que usamos um único tipo de 
recurso, a requisição é concedida. Portanto, se tivermos múltiplos tipos de recursos, precisamos usar o 
algoritmo do banqueiro para múltiplos tipos de recursos. 
 
22. Considere o seguinte instantâneo de um sistema: 
 Alocação Max 
 A B C D A B C D 
P​0 3 0 1 4 5 1 1 7 
P​1 2 2 1 0 3 2 1 1 
P​2 3 1 2 1 3 3 2 1 
P​3 0 5 1 0 4 6 1 2 
P​4 4 2 1 2 6 3 2 5 
Usando o algoritmo do banqueiro, determine se cada um dos estados a seguir é ou não é inseguro. Se 
o estado for seguro, demonstre a ordem em que os processos podem ser concluídos. Caso contrário, 
demonstre por que o estado é inseguro. 
a. Disponível​ = (0, 3, 0, 1) 
 Necessário 
 A B C D 
P​0 2 1 0 3 
P​1 1 0 0 1 
P​2 0 2 0 0 
P​3 4 1 0 2 
P​4 2 1 1 3 
 
P0 - termina [0] = F (2103 > 0301) 
P1 - termina [1] = F (1001 > 0301) 
P2 - termina [2] = V (0200 < 0301), então soma a alocação ao disponível. Novo Disponível = 3422 
P3 - termina [3] = F (4102 > 3422) 
P4 - termina [4] = V (2113 < 3422) então soma a alocação ao disponível. Novo Disponível = 7634 
P0 - termina [0] = V (2103 < 7634) então soma a alocação ao disponível. Novo Disponível = 10648 
P1 - termina [1] = V (1001 < 10648) então soma a alocação ao disponível. Novo Disponível = 12850 
P3 - termina [3] = V (4102 < 12850) então soma a alocação ao disponível. Novo Disponível = 13360 
 
Não é seguro. Processos P2, P1 e P3 podem terminar, mas nenhum processo remanescente pode 
terminar. 
 
 
b. Disponível​ = (1, 0, 0, 2) 
 ​ Alocação Necessário 
 ABCD A B C D 
P0 3014 2 1 0 3 
P1 2210 1 0 0 1 
P2 3121 0 2 0 0 
P3 0510 4 1 0 2 
P4 4212 2 1 1 3 
 
P0 - termina [0] = F (2103 > 1002) 
P1 - termina [1] = V (1001 > 1002) então soma a alocação ao disponível. Novo Disponível = 3212 
P1 - termina [1] = V (1001 > 3212) então soma a alocação ao disponível. Novo Disponível = 3212 
 
 
 
 
Seguro. Os processos P1, P2 e P3 podem terminar. Seguindo isso, os processos P0 e P4 também podem 
terminar. 
23. Considere o seguinte instantâneo de um sistema: 
 Alocação Max Disponível 
 A B C D A B C D A B C D 
P​0 2 0 0 1 4 2 1 2 3 3 2 1 
P​1 3 1 2 1 5 2 5 2 
P​2 2 1 0 3 2 3 1 6 
P​3 1 3 1 2 1 4 2 4 
P​4 1 4 3 2 3 6 6 5 
Responda as perguntas a seguir usando o algoritmo do banqueiro: 
a. Mostre que o sistema está emum estado seguro demonstrando uma ordem em que os processos 
podem ser concluídos. 
b. Se uma solicitação do processo ​P​1​ chega para (1,1,0,0), ela poderá ser atendida imediatamente? 
c. Se uma solicitação do processo ​P​4​ chega para (0,0,2,0), ela poderá ser atendida imediatamente? 
 
24. Qual é a suposição otimista feita no algoritmo de detecção de deadlocks? Como essa suposição pode ser 
violada? 
A suposição otimista é que não haverá qualquer forma de espera circular em termos de recursos 
alocados e processos que façam pedidos para eles. Esta suposição poderia ser violada se uma espera 
circular realmente ocorrer na prática. 
 
25. Uma ponte com uma única pista conecta as duas vilas North Tunbridge e South Tunbridge em Vermont. 
Os fazendeiros das duas vilas usam essa ponte para distribuir sua produção na cidade vizinha. A ponte 
pode apresentar um deadlock se um fazendeiro em direção ao norte e um em direção ao sul entrarem na 
ponte ao mesmo tempo (os fazendeiros de Vermont são teimosos e não concordam em voltar). Usando 
semáforos e/ou locks mutex, projete um algoritmo em pseudocódigo para prevenir deadlocks. 
Inicialmente, não se preocupe com a inanição (a situação em que fazendeiros em direção ao norte 
impedem fazendeiros indo para o sul de usar a ponte, ou vice​versa). 
semaphore ok to cross = 1; 
void enter bridge() { 
ok to cross.wait(); 
} 
void exit bridge() { 
ok to cross.signal(); 
} 
 
26. Modifique sua solução para o ​Exercício 7.25​ para que não ocorra inanição. 
monitor bridge { 
int num waiting north = 0; 
int num waiting south = 0; 
int on bridge = 0; 
condition ok to cross; 
int prev = 0; 
 
void enter bridge north() { 
num waiting north++; 
while (on bridge || (prev == 0 &amp;&amp; num waiting south &gt; 0)) 
ok to cross.wait(); 
num waiting north-- ; 
prev = 0; 
} 
 
void exit bridge north() { 
on bridge = 0; 
ok to cross.broadcast(); 
} 
 
void enter bridge south() { 
num waiting south++; 
while (on bridge ||(prev == 1 &amp;&amp; num waiting north &gt; 0)) 
ok to cross.wait(); 
num waiting south-- ; 
prev = 1; 
} 
 
void exit bridge south() { 
on bridge = 0; 
ok to cross.broadcast(); 
} 
} 
Problemas de Programação 
1 Implemente sua solução para o ​Exercício 7.25 usando a sincronização POSIX. Especificamente, 
represente os fazendeiros que vão para o norte e para o sul como threads separados. Uma vez que um 
fazendeiro esteja na ponte, o thread associado adormecerá por um período de tempo aleatório, 
representando a passagem pela ponte. Projete seu programa de modo que você possa criar vários threads 
representando o fazendeiro que vai para o norte e o que vai para o sul. 
 
Projetos de Programação 
Algoritmo do Banqueiro 
Nesse projeto, você escreverá um programa multithreaded que implemente o algoritmo do banqueiro 
discutido na ​Seção 7.5.3​. Vários clientes solicitam e liberam recursos do banco. O banqueiro atenderá uma 
solicitação somente se ela deixar o sistema em um estado seguro. Uma solicitação que deixe o sistema em 
um estado inseguro será negada. Essa tarefa de programação combina três tópicos diferentes: (1) criar 
múltiplos threads, (2) prevenir condições de corrida e (3) evitar deadlocks. 
O Banqueiro 
O banqueiro considerará solicitações de ​n clientes por ​m tipos de recursos, como descrito na ​Seção 7.5.3​. O 
banqueiro controlará os recursos usando as estruturas de dados a seguir: 
/* estes podem ser quaisquer valores >= 0 */ 
#define NUMBER_OF_CUSTOMERS 5 
#define NUMBER_OF_RESOURCES 3 
/* o montante disponível de cada recurso */ int 
available[NUMBER_OF_RESOURCES]; 
/* a demanda máxima de cada cliente */ int 
maximum[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES]; 
/* o montante correntemente alocado a cada cliente */ int 
allocation[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES]; 
/* a necessidade remanescente de cada cliente */ int 
need[NUMBER_OF_CUSTOMERS][NUMBER_OF_RESOURCES]; 
Os Clientes 
Crie ​n threads de clientes que solicitem e liberem recursos do banco. Os clientes estarão em um loop 
contínuo, solicitando e depois liberando números aleatórios de recursos. As solicitações dos clientes por 
recursos serão limitadas por seus respectivos valores no array need. O banqueiro atenderá uma solicitação se 
ela satisfizer ao algoritmo de segurança descrito na ​Seção 7.5.3​.1. Se uma solicitação não deixa o sistema em 
um estado seguro, o banqueiro a negará. Os protótipos das funções para a solicitação e liberação de recursos 
são os seguintes: 
int request_resources(int customer_num, int 
request[]); 
int release_resources(int customer_num, int 
release[]); 
Essas duas funções devem retornar 0, se bem​sucedidas, e – 1, se não houver êxito. Múltiplos threads 
(clientes) acessarão concorrentemente dados compartilhados por meio dessas duas funções. Portanto, o 
acesso deve ser controlado por meio de locks mutex para prevenir condições de corrida. As APIs Pthreads e 
Windows fornecem locks mutex. O uso de locks mutex do Pthreads é abordado na ​Seção 5.9.4; os locks 
mutex dos sistemas Windows são descritos no projeto intitulado “Problema do Produtor​Consumidor” no fim 
do ​Capítulo 5​. 
Implementação 
Você deve invocar seu programa passando o número de recursos de cada tipo na linha de comando. Por 
exemplo, se houver três tipos de recursos, com dez instâncias do primeiro tipo, cinco do segundo tipo e sete 
do terceiro tipo, você invocaria seu programa assim: 
./a.out 10 5 7 
O array available seria inicializado com esses valores. Você pode inicializar o array maximum (que 
contém a demanda máxima de cada cliente) usando qualquer método que achar conveniente.