L1 - Lista de SO

Prévia do material em texto

Sistemas Operacionais - Lista de Exercícios 1
1. Na Figura 2.2, são mostrados três estados de processos. Na teoria, com três
estados, poderia haver seis transições, duas para cada. No entanto, apenas quatro
transições são mostradas. Existe alguma circunstância na qual uma delas ou ambas as
transições perdidas possam ocorrer?
R.: Sim. A transição do estado BLOQUEADO para o estado EM EXECUÇÃO seria
possível considerando um cenário no qual a CPU não estivesse executando nada no
momento em que o processo saísse do estado de bloqueio. Já a outra transição, do
estado PRONTO para BLOQUEADO, não é possível.
3. Em todos os computadores atuais, pelo menos parte dos tratadores de interrupções
é escrita em linguagem de montagem. Por quê?
R.: Os tratadores de interrupções devem atuar próximo ao hardware, manipulando
registradores, lidando com interrupções etc. e isso não é possível com linguagens de
mais alto nível, que buscam abstrair esses detalhes. Também poderíamos citar a busca
por um melhor desempenho desses tratadores, o qual seria alcançado com as
instruções mais diretas da linguagem de montagem.
4. Quando uma interrupção ou uma chamada de sistema transfere controle para o
sistema operacional, geralmente uma área da pilha do núcleo separada da pilha do
processo interrompido é usada. Por quê?
R.: Isso acontece por uma questão de segurança, pois se o núcleo e o processo
interrompido compartilhassem a mesma área da pilha, uma eventual falha (ou até
mesmo um código malicioso) desse processo interrompido poderia afetar o
funcionamento do núcleo, o que não é desejável.
5. Um sistema computacional tem espaço suficiente para conter cinco programas em
sua memória principal. Esses programas estão ociosos esperando por E/S metade do
tempo. Qual fração do tempo da CPU é desperdiçada?
R.: Temos 5 programas rodando em paralelo. Cada um deles tem a probabilidade de
50% de estar esperando operações de E/S. Assim, a probabilidade de que todos eles
estejam esperando por E/S ao mesmo tempo é de 0,5^5 = 0,03125. Portanto, a fração
do tempo de CPU desperdiçada é 0,03125 = 1/32.
6. Um computador tem 4 GB de RAM da qual o sistema operacional ocupa 512 MB.
Os processos ocupam 256 MB cada (para simplificar) e têm as mesmas
características. Se a meta é a utilização de 99% da CPU, qual é a espera de E/S
máxima que pode ser tolerada?
R.: Antes de iniciarmos os cálculos, gostaria de salientar o fato de que podemos
calcular o uso da CPU através da seguinte fórmula:
C = 1 - P
Onde C é o uso da CPU e P é a probabilidade de que nenhum processo a esteja usando.
Tendo isso em consideração, retomemos os cálculos:
Sabemos que o computador tem 4 GB de RAM (isso é, 4096 MB), dos quais 512 MB
são ocupados pelo SO. Sendo assim, restarão 3.584 MB, o que é suficiente para 14
processos de 256 MB.
Como nosso objetivo é alcançar 99% de utilização da CPU, tendo em vista a fórmula
acima mencionada, objetivamos que a probabilidade de que nenhum processo esteja
sendo usado (P) seja igual a 0.01, já que 0.99 = 1 - P, quando P = 0.01.
Podemos calcular P através da multiplicação das probabilidades de que os processos
estejam em espera de E/S. Como os processos têm as mesmas características,
podemos assumir que todos eles têm a mesma probabilidade de estar esperando E/S,
chamaremos essa probabilidade de p (minúsculo).
Como temos 14 processos, a probabilidade de que nenhum deles esteja utilizando a
CPU (isso é, que todos eles estejam esperando E/S) é igual a p^14. E como queremos
que p^14 = 0.01, então p deve ser 0.719685673.
Ou seja, para que consigamos um aproveitamento de 99% da CPU, é preciso que os
processos tenham uma taxa de aproximadamente 71,97% de espera por E/S.
7. Múltiplas tarefas podem ser executadas em paralelo e terminar mais rápido do que
se forem executadas de modo sequencial. Suponha que duas tarefas, cada uma
precisando de 20 minutos de tempo da CPU, iniciassem simultaneamente. Quanto
tempo a última levará para completar se forem executadas sequencialmente? Quanto
tempo se forem executadas em paralelo? Presuma uma espera de E/S de 50%.
R.: Supondo 2 tarefas, cada uma necessitando de 20 minutos de tempo da CPU, com
50% de espera de E/S:
Cada tarefa, precisa de 40 minutos (20 minutos de tempo da CPU + 20 minutos de
espera de E/S [50%]), sendo assim, as duas tarefas levarão, sequencialmente, 80
minutos para terminarem.
Por outro lado, se forem executadas em paralelo, enquanto uma tarefa espera por E/S,
a outra é executada. Assim, considerando que 50% do tempo de execução dessas
tarefas se tratam de espera por E/S, temos que, em um certo instante, a probabilidade
de a CPU estar em uso é de 1 - 0.5^2 = 1 - 0.25 = 0.75, ou seja, 75%. A partir disso,
podemos concluir que, em média, a cada 1 minuto, 45 segundos da CPU é usada (0.75
minutos). Portanto, haja vista que os dois processos precisam, juntos, de 40 minutos
de uso da CPU, ao todo precisaremos de aproximadamente 53.33 minutos para que 40
minutos da CPU seja usada, completando, assim, as duas tarefas.
8. Considere um sistema multiprogramado com grau de 6 (isto é, seis programas na
memória ao mesmo tempo). Presuma que cada processo passe 40% do seu tempo
esperando pelo dispositivo de E/S. Qual será a utilização da CPU?
R.: Sabemos que, para cada processo, a probabilidade de se estar esperando E/S é de
40%. Dado isso, queremos calcular a probabilidade de pelo menos um processo estar
usando a CPU.
Para tanto, calculemos a probabilidade de que nenhum processo esteja utilizando a
CPU (isto é, a probabilidade de que todos os processos estejam esperando E/S):
Como a probabilidade de estar esperando E/S para cada processo é 0.4, então a
probabilidade de que todos eles estejam é de 0,4^6 = 0,004096.
A partir disso, podemos calcular a probabilidade de que pelo menos um esteja
utilizando a CPU por 1 - 0,4^6 = 1 - 0,004096 = 0,995904.
9. Presuma que você esteja tentando baixar um arquivo grande de 2 GB da internet. O
arquivo está disponível a partir de um conjunto de servidores espelho, cada um deles
capaz de fornecer um subconjunto dos bytes do arquivo; presuma que uma
determinada solicitação especifique os bytes de início e fim do arquivo. Explique
como você poderia usar os threads para melhorar o tempo de download.
R.: Poderiam ser utilizadas diversas threads, cada uma solicitando um subconjunto
de bytes do arquivo para um servidor diferente, pois, enquanto uma thread aguarda a
resposta do servidor com seu determinado subconjunto chegar, uma outra thread já faz
a solicitação de outro subconjunto, o que poderá reduzir o tempo de download.
10. No texto foi afirmado que o modelo da Figura 2.11(a) não era adequado a um
servidor de arquivos usando um cache na memória. Por que não? Será que cada
processo poderia ter seu próprio cache?
R.: Não é adequado pois, se houver a alteração de um arquivo por um dos processos,
os outros processos, consultando o cache, poderiam enviar arquivos desatualizados.
11. Se um processo multithread bifurca, um problema ocorre se o filho recebe cópias
de todos os threads do pai. Suponha que um dos threads originais estivesse esperando
por entradas do teclado. Agora dois threads estão esperando por entradas do teclado,
um em cada processo. Esse problema ocorre alguma vez em processos de thread
único?
R.: Não, pois um processo (thread) bloqueado, à espera de entrada, não pode bifurcar.
12. Um servidor web multithread é mostrado na Figura 2.8. Se a única maneira de ler
de um arquivo é a chamada de sistema read com bloqueio normal, você acredita que
threads de usuário ou threads de núcleo estão sendo usados para o servidor web? Por
quê?
R.: Provavelmente estão sendo usados threads de núcleo, pois se estivessem sendo
usados threads de usuário todo o processo seria bloqueado pela chamada de sistema
read, inclusive as outras threads, e não é esse o comportamento que se espera.
13. No texto, descrevemos um servidor web multithread, mostrando por que ele é
melhor do que um servidor de thread único e um servidor de máquina de estado finito.Existe alguma circunstância na qual um servidor de thread único possa ser melhor?
Dê um exemplo.
R.: Sim, existe. Quando o servidor não precisar fazer operações que causem o
bloqueio da thread (como operações de entrada/saída), isso é, quando ele depender
apenas do trabalho da CPU, não seria necessário o multithread, já que essa abordagem
visa exatamente a permitir que o servidor continue atendendo a outras requisições
enquanto uma thread está bloqueada. Assim, posto que, por hipótese, nenhuma thread
será bloqueada, a abordagem com múltiplas threads para esse caso não trará
benefícios.
Um exemplo bem simples disso seria um servidor que ao receber dois números os
soma e responde a requisição com esse resultado. Perceba que não há nenhuma ação
bloqueante nisso.
14. Na Figura 2.12, o conjunto de registradores é listado como um item por thread em
vez de por processo. Por quê? Afinal de contas, a máquina tem apenas um conjunto de
registradores.
R.: Porque, como outras threads compartilham os mesmos registradores, cada thread
tem seu próprio contexto de execução, no qual cada registrador tem seu valor. Esses
valores devem ser salvos e recarregados para seus respectivos registradores assim que
a thread for escalonada para execução.
15. Por que um thread em algum momento abriria mão voluntariamente da CPU
chamando thread_yield? Afinal, visto que não há uma interrupção periódica de
relógio, ele talvez jamais receba a CPU de volta.
R.: Espera-se que os threads em um mesmo processo cooperem entre si, afinal
normalmente são programados pela mesma pessoa. Assim, um thread chamaria
thread_yield para que todo o processo pudesse ter progresso.
16. É possível que um thread seja antecipado por uma interrupção de relógio? Se a
resposta for afirmativa, em quais circunstâncias?
R.: Sim, os threads a nível do núcleo podem ser antecipados caso eles tenham gasto
todo o seu tempo reservado; já os threads a nível de usuário podem ser antecipados
caso o tempo reservado para o processo tenha se esgotado.
23. A solução da espera ocupada usando a variável turn (Figura 2.23) funciona
quando os dois processos estão executando em um multiprocessador de memória
compartilhada, isto é, duas CPUs compartilhando uma memória comum?
R.: Funciona, porém haveria problema se as duas CPUs tivessem velocidades muito
diferentes, como vimos em aula. Nesse caso, o processo rodando na CPU mais lenta
poderia impedir, fora de sua área crítica, o outro processo de acessar sua área crítica.
24. A solução de Peterson para o problema da exclusão mútua mostrado na Figura
2.24 funciona quando o escalonamento de processos é preemptivo? E quando ele é
não preemptivo?
R.: Sim, ele funciona para escalonamento preemptivo. Quando se trata de
escalonamento não preemptivo, no entanto, ele pode falhar, já que a solução proposta
por Peterson baseia-se em espera ocupada e, considerando que o sistema não seja
preemptivo, isso implica que o laço de espera ocupada rodará para sempre, haja visto
o fato de que, durante essa espera, o outro processo não terá sua vez e, portanto, as
condições necessárias para “quebrar” esse laço de espera (condições essas que apenas
o outro processo poderia mudar) não serão nunca alcançadas.