Fixação sobre Comunicação entre Processos (IPC) e Escalonamento (1)

Prévia do material em texto

1. Explique com palavras e desenhos o funcionamento de comunicação entre processos 
por: 
(a) Troca de mensagens. 
R: Para a comunicação existir deve haver entre eles um canal de comunicação. A 
implementação da maioria destes canais se baseia nas primitivas de mensagens 
send(msg) e receive(msg).​ ​Podem ser implementadas como procedimentos: send 
(destination,&message); receive (source,&message). O procedimento send envia para um 
determinado destino uma mensagem, enquanto que o procedimento receive recebe essa 
mensagem em uma determinada fonte; Se nenhuma mensagem está disponível, o 
procedimento receive é bloqueado até que uma mensagem chegue. 
 
 
 
(b) Memória compartilhada. 
R: Cada processador tem acesso total à memória compartilhada, comunicação entre 
processos se dá através da memória (acesso concorrente necessita sincronização 
explícita). A comunicação ocorre através de variáveis compartilhadas. 
 
 
 
2. Suponha que um sistema operacional implementa ambas as chamadas ao sistema 
send(port,msg) e receive(port,msg) como funções que bloqueiam. 
 
(a) Explique o isso significa. 
R: Isso significa que quando o processo fizer a chamada ao sistema send(x, y), ele irá 
informar ao kernel, que deseja enviar uma mensagem para a porta X, com o conteúdo 
da mensagem Y, desta maneira, o kernel irá disponibilizar está mensagem lá, para 
que o outro lado possa “receber” no destino correto, que é onde a outra função entra 
em ação, o segundo processo irá informar ao kernel que está esperando uma 
mensagem através da chamada ao sistema receive(x, y), onde X representa a porta no 
qual ele deseja escutar a mensagem, desta maneira o kernel disponibiliza para ele a 
mensagem que foi enviada a porta X, pelo processo que utilizou o método send. 
 
(b) O que um processo pode fazer para evitar que seja bloqueado ao utilizar alguma dessas 
chamadas? 
R: Se registrar em uma dessas portas para ser notificado sempre que uma mensagem 
chegar, desta maneira, ele ficará “escutando” a porta, saberá quando uma mensagem 
chega e ao utilizar as chamadas, não ficará bloqueando esperando uma resposta, 
isso será feito instantaneamente. 
 
3. Na abordagem de comunicação por troca de mensagens, explique quais as diferenças 
entre os modelos de comunicação direta e indireta. Lembre-se da analogia da caixa de 
correio. 
R: No modelo de comunicação direta, uma mensagem é enviada de maneira direta a 
um processo e recebida diretamente de um processo, neste modelo, a comunicação 
ocorre apenas entre dois processos e para isso, ambos devem saber os nomes uns 
dos outros em toda a rotina de troca de mensagens. Já no modelo de comunicação 
indireta a mensagem é enviada para uma porta, ou socket, onde está fica armazenada 
para que todos os processo ouvintes desta porta possam escutar a mensagem, isso 
permite que mais de dois processos possam se comunicar. 
 
4. Sobre condição de corrida (race condition), responda: 
(a) Explique o que é? 
R: Condição de corrida é é uma falha no qual, quando processos que interagem entre 
si utilizando os mesmo recursos levam a um resultado inesperado do que se foi 
imaginado primeiramente, quando dois processos utilizam um mesmo estado 
compartilhado assim, modificando-o em momentos diferentes. 
 
(b) Por que pode ser difícil verificar sua existência? 
R: Pois nem sempre o programa apresenta o resultado ‘inesperado’ ao ser rodado, 
desta maneira, só apresentando a anomalia em algum outro momento já no futuro, 
pois quando você roda diversas vezes o mesmo programa, ele pode ter o resultado 
esperado pelo programador todas as vezes, assim como, pode apresentar as outras 
centenas de resultados não esperados pelo programador. 
 
(c) Dê um exemplo de quando pode ocorrer. 
R: Quando dois programas tentam acessar e modificar o mesmo arquivo. 
 
(d) Como garantir que não vai ocorrer? 
R: Para que a condição de corrida não aconteça é aplicar a técnica da exclusão 
mútua, onde está determina, identificação das regiões críticas, não permitir que dois 
processos estejam ao mesmo tempo em suas regiões críticas, algoritmos não podem 
ser escrito com base no relógio, velocidade e quantidade de CPUs, processos que 
estão fora de sua região crítica não podem bloquear outros processos e nenhum 
processo deve esperar para sempre para adentrar a sua região crítica. 
 
 
5. Considere o código de implementação de uma Pilha abaixo: 
Suponha que um programador utilizou essa implementação de pilha em seu programa, que 
é multithreaded. No programa, diversas threads operam sobre uma mesma pilha (memória 
compartilhada), empilhando e desempilhando objetos. A seguir, o código do programador: 
Sob estas condições, faça o que se pede: 
(a) Replique este programa em seu computador, rode-o pelo menos 5 vezes e analise os 
resultado. Explique por que o código apresenta condição de corrida; 
R: ​Ocorre porque duas threads acessaram o mesmo topo, sendo a thread que estava 
na vez foi interrompida, e a outra entrou em execução e atualizou topo, sendo que o 
valor lido do topo é o mesmo para as duas threads, quando a thread que foi 
interrompida volta a executar ela sobrescreve o valor do topo novamente, sendo 
assim gerando uma necessidade de acessar a posição -1 da memória lançando a 
exceção. As threads estão competindo tanto no método empilhar quanto o 
desempilhar, podendo sobrar números na pilha. 
 
(b) Resolva a condição de corrida utilizando a técnica das trancas (locks). 
R:​ ​class Pilha { 
 ​private boolean condicao = true; 
 
 public void empilhar(Object o) { 
 ​while(condicao == true){ 
 pilha[topo++] = o; 
 condicao = false; 
 } 
 
 } 
 public Object desempilhar() { 
 ​while(condicao == true){ 
 condicao = false; 
 return pilha[--topo]; 
 } 
 
 
 } 
 public int getQtdeElementos() { 
 return topo; 
 } 
 private final Object[] pilha = new Object[1000]; 
 private int topo = 0; 
} 
 
 
(c) Volte ao código original e dessa vez resolva a condição de corrida utilizando a técnica de 
monitores. 
R: ​class Pilha { 
 public ​synchronized​ void empilhar(Object o) { 
 pilha[topo++] = o; 
 } 
 public ​synchronized​ Object desempilhar() { 
 return pilha[--topo]; 
 } 
 public ​synchronized​ int getQtdeElementos() { 
 return topo; 
 } 
 private final Object[] pilha = new Object[1000]; 
 private int topo = 0; 
} 
 
 
6. Considere o problema do Produtor-Consumidor, apresentado nos slides da aula ou nos 
livros da bibliografia básica dessa disciplina. Responda: 
(a) Qual é o problema existente? 
R: O problema é a falta de sincronização entre o produtor e o consumir, podendo 
gerar a condição de corrida. 
 
(b) Quando ele acontece? 
R: Quando o produtor tentar inserir um novo item, porém a vaga já está preenchida, 
após isso ele vai dormir e teoricamente deveria esperar até que o consumir 
consumisse o item, porém como dito acima, pode acarretar na condição de corrida, e 
pode ser que tanto produtor quanto consumir entre em modo sleep. 
 
(c) Como e por que a utilização de semáforos resolve o problema? 
R: A solução semáforos prevê duas novas funções, up e down, que operam sobre 
uma variável chamada semáforo, onde up irá armazenar um sinal de acordar para o 
futuro e down irá consumi-lo, a operação down, deverá ser atômica, ou seja, uma vez 
que ela tenha começado nenhum outro processo pode acessar semáforo e bloqueá-lo 
até que o mesmo seja concluído. Esta implementação resolve o problema pois caso o 
produtor tente inserir um item, e o buffer já esteja preenchido, quando este for 
dormir, o sinal de acordar que ele emite para o consumidor será armazenado e 
enviado posteriormente ao consumir após as devidas verificações, logo, os nenhum 
dos dois processo irá dormir de maneira incorreta, assim eliminando a condição de 
corrida e evitando que ambos entre em modo dormir de maneira eterna. 
 
7. Defina os seguintes critérios de avaliação de qualidade de escalonamento em SistemasOperacionais e explique como podem ser avaliados: 
 
(a) Throughput; 
R: ​Números de processos terminados por unidade de tempo. Procurar maximizar o 
número de tarefas processadas por unidade de tempo. 
 
(b) Turnaround; 
R: ​ Tempo transcorrido desde o momento em que o software entra e o instante em que 
termina sua execução 
 
(c) Utilização de CPU; 
R: ​Fração de tempo durante a qual ela está sendo ocupada 
 
(d) Tempo de resposta; 
R: ​Intervalo entre a chegada ao sistema e início de sua execução 
 
(e) Atingir metas; 
R: Garantir que um processo estará terminado em determinada quantidade de tempo. 
 
(f) Previsibilidade; 
R: Garantir que haverá espaço para certos processos em intervalos de tempo 
regulares. 
 
(g) Distribuição; 
R: Manter todos os dispositivos ocupados ao mesmo tempo. 
 
(h) Proporcionalidade. 
R: Que as respostas para atividades requisitadas pelo usuário tenham um tempo 
aceitável. 
 
8. Realize os seguintes algoritmos de escalonamento para os processos das tabelas I e II e 
determine as qualidades que se pede: 
22 
(a) Algoritmo First-Come First Served, qualidades throughput e turnaround; 
R: throughtput: 0,25 e turnaround: 12,5 
 throughtput: 0,21 e turnaround: 20 
 
(b) Algoritmo Shortest-Job First, qualidades throughput e turnaround; 
R: throughtput: 0,25 e turnaround: 7,5 
 throughtput: 0,21 e turnaround: 11,5 
 
(c) Algoritmo Round-Robin com quantum igual a 1 e troca de contexto igual a 0,5, 
qualidades​ ​utilização de CPU e tempo de resposta; 
R: 66% de utilização de CPU (16/24), tempo de resposta: 0,08s 
 66% de utilização de CPU (29/43,5), tempo de resposta: 0,12s 
 
(d) Algoritmo Shortest Remaining Time Next com quantum igual a 1 e troca de contexto 
igual a 0,5, qualidades utilização de CPU, throughput, turnaround e tempo de resposta; 
R: 66% de utilização de CPU (16/24), throughput: 0,010, tempo de resposta: 105.25 
 66% de utilização de CPU (29/43,5/24), throughput: 0,004, tempo de resposta: 278.5 
 
 
 
 
9. Defina processos CPU-bound e I/O-bound. Dê três exemplos reais de processos, para 
cada grupo. 
R: Processos CPU-bound são processo que necessitam fazer uso da CPU por um 
longo período de tempo, assim, quando apresentam o burst de uso, seus tempos de 
utilização são grande, especialmente em comparação a processo I/O-bound. 
Exemplo: Renderização de vídeo; Abrir uma planilha no excel com uma quantidade 
enorme de dados (1gb+); Compilação do programa java pelo Intellij; 
 
Processos I/O-bound, são processo que passam longos períodos de tempo em 
estado de espera, ou seja, esperando pelo INPUT/OUTPUT do usuário, desta maneira, 
fazendo pouco uso do tempo da CPU. 
Exemplo: Word com o cursor piscando; Copiar algum arquivo 
 
10. Explique como um processo pode ser classificado como CPU-bound ou I/O-bound 
apenas ao analisar o código-fonte de seu programa? De qual outra maneira ele também 
pode ser classificado? 
 
11. Sobre tipos de escalonamento: 
 
(a) Defina escalonamento preemptivo e cooperativo. 
R: No escalonamento preemptivo o sistema operacional determina um tempo fixado 
de execução para cada processo, desta maneira, ao final deste tempo, o sistema 
poderá interromper o processo, colocando este em estado de pronto, e alocando 
outro processo para iniciar a execução. Já no escalonamento cooperativo o processo 
só será interrompido quando terminar sua execução ou quando ceder de maneira 
voluntária o uso da CPU, dessa maneira, nenhum agente externo poderá causar a sua 
interrupção. 
 
(b) Quais as vantagens e desvantagens de cada um? 
R: No escalonamento cooperativo, uma de suas vantagens é que a aplicação pode ter 
uma implementação mais simples, pois não irá ter que lidar com interrupções de 
processamento, porém, por outro lado, como desvantagem, uma aplicação mal 
escrita, ou um erro cometido em seu desenvolvimento, pode monopolizar o tempo de 
uso do processado, ocasionando o travamento do sistema operacional.No 
escalonamento preemptivo, uma de suas vantagens é a priorização de execução de 
processo como no caso de aplicações em tempo real, onde o fator tempo é crítico, 
além de prever implementação de políticas de escalonamento que fazem a divisão do 
tempo de processador ser mais justo entre todos os processos. 
 
(c) Explique como o escalonamento cooperativo pode ser perigoso para o sistema. 
R: O processo pode tomar conta total do sistema, uma vez que ele foi mal escrito, ou 
escrito de forma maliciosa e nenhum agente externo pode forçar sua interrupção a 
não ser o fim de sua execução ou abrindo mão do uso da CPU, isto tendo em vista, 
pode ocasionar o travamento do sistema. 
 
 
12. Explique o funcionamento dos seguintes algoritmos de escalonamento: 
 
(a) Lottery. 
R: Funciona como uma loteria, os processos são presente com bilhetes numerados, 
onde no momento do escalonamento o sistema operacional irá sortear um bilhete e o 
processo que possuir o bilhete sorteado entrará em execução. Processos que 
possuem maior importância recebem mais bilhetes. ex: se um processo necessita de 
20% de CPU, ele receberá 20% dos bilhetes. 
 
(b) Priority. 
R: No escalonamento Priority os processos são atribuídos com um valor de 
prioridade, onde quanto maior este valor, maior é sua prioridade de execução. Neste 
tipo de escalonamento o sistema tem o poder de alterar a prioridade dos processos e 
também neste caso, o sistema só irá colocar em execução processos que possuem 
prioridade máxima. 
 
(c) Shortest Process Next. 
R: Este tipo de escalonamento é uma adaptação do “Shortest Job First”, onde o 
sistema irá guardar o tempo dos processos, assim criando um histórico, desta 
maneira irá estimar a próxima carga de um processo, assim selecionando o próximo 
da fila de execução como o que terá menor tempo de serviço. Utiliza a técnica de 
envelhecimento para poder armazenar os valores de tempo dos processos. 
 
13. Quais as diferenças entre Priority Scheduling com grupos e Multiple Queues 
Scheduling? 
R:​ ​São usadas várias filas de processos prontos para executar, cada processo é colocado 
em uma fila, e cada fila tem uma política de escalonamento própria e outra entre filas, 
preemptivo, cada fila tem um determinado nível de prioridade, sendo um dos mais antigos 
agendadores de prioridade, estava presente no CTSS (Compatible Time-Sharing System - 
Sistema Compatível de Divisão por Tempo).No algoritmo de Múltiplas Filas, também pode 
ser aplicado particularmente, em cada fila, diferentes algoritmos. 
 
14. Você foi contratado para implementar o algoritmo de escalonamento de um servidor de 
aluguel de sistemas em nuvem. O sistema é multiprogramado e oferece uma quantidade de 
tempo de processamento a cada cliente de acordo com o preço pago. Clientes que pagam 
$10/hora, têm maior preferência de processamento, enquanto clientes que pagam apenas 
$1/hora, tem menor. A empresa oferece também planos intermediários com preços de 
$7,50/hora e $3,50/hora. Elabore um algoritmo de escalonamento que atenda às 
necessidades desse sistema e explique. 
R: O melhor algoritmo de escalonamento para este caso seria o escalonamento por 
prioridades, pois tendo em vista que existem planos pagos, onde quem paga mais, 
tem mais preferência de processamento e o que paga menos tem menor preferência, 
o melhor escalonador seria o de prioridade, onde o próprio sistema irá receber a 
informação de que o usuário X é o que pagou maior valor pelo plano, e desta maneira 
ele pode ir e mudar e aumentar as prioridade das demandas do usuário X. 
 
15. Suponha que a empresa do sistema anterior queira mudar o modelo de vendas de 
processamento. Ao invés de vender preferência em processamento, agora vende tempo 
relativo. Se o usuário pagar $10/hora, vai garantir 20% de tempo de processamento, 
enquanto se pagar $7,50/hora, vai garantir 15%, e assim por diante. Elabore outro algoritmo 
de escalonamento para atender a essas necessidades. 
R: ​Com estas condições de vendas pode se aplicar o escalonamento por loteria, pois 
é fácil de controlar a quantidade de processamentodado a um processo 
pontualmente, se um processo necessita de 20% da CPU, dê a ele 20% dos bilhetes. 
 
16. Classifique os seguintes algoritmos de escalonamento quanto ao tipo de sistema de 
escalonamento (preemptivo ou cooperativo): First-Come First-Served; Shortest Job First; 
Round-Robin; Priority Scheduling; Multiple Queues; Shortest Process Next; Lottery 
Scheduling;Fair-Share Scheduling. 
R: 
First-Come First-Serve - Cooperativo; 
Shortest Job First - Cooperativo; 
Round-Robin- Preemptivo; 
Priority Scheduling - Preemptivo ou Cooperativo; 
Multiple Queues - Preemptivo; 
Shortest Process Next - Cooperativo; 
Lottery Scheduling - Preemptivo ou Cooperativo;