AD1_2021-1_Gabarito_SistemasOperacionais

Prévia do material em texto

Curso de Tecnologia em Sistemas de Computação
Disciplina de Sistemas Operacionais
Professores: Claudio Micelli de Farias e Diego L. C. Dutra
Assistente: Alexandre H. L. Porto e Davi Brilhante
AD1 - Primeiro Semestre de 2021
Atenção: Cada aluno é responsável por redigir suas próprias respostas.
Provas iguais umas às outras terão suas notas diminuídas. As
diminuições nas notas ocorrerão em proporção à similaridade entre as
respostas. Exemplo: Três alunos que respondam identicamente a uma
mesma questão terão, cada um, 1/3 dos pontos daquela questão.
Nome -
Assinatura - _______________________________________________
1. (2,0) Em um ambiente computacional monoprocessado, suponha
que um programa A, que precisa executar no processador por 8x
ms, faça uma operação de E/S, com duração de a ms, após
executar por 1/4 do seu tempo de execução. Suponha ainda que
um programa B, no mesmo ambiente computacional, que precisa
executar no processador por 10x ms, faça uma operação de E/S,
com duração de b ms, após executar por 3/5 do seu tempo de
execução. Considere que a multiprogramação seja usada
somente para evitar a ociosidade do processador quando
operações de E/S são feitas. Qual será a ociosidade do
processador se A e B alternarem as suas execuções e se, mesmo
com o uso da multiprogramação, existir ociosidade antes de cada
programa terminar a sua execução? Justifique a sua resposta.
Resp.: Inicialmente vamos mostrar como será o fluxo de
execução dos programas A e B. Pelo enunciado, vemos que o
programa A executará por 2x ms antes de fazer a sua operação
de E/S com duração de a ms, e por mais 6x ms após o término
dessa operação. Já o programa B executará por 6x ms antes de
fazer a sua operação de E/S com duração de b ms, e por mais 4x
ms depois de fazer essa operação. A figura a seguir ilustra esse
comportamento de A e de B.
2x ms a ms 6x ms
A E/S A
6x ms b ms 4x ms
B E/S B
Primeiramente, vamos lembrar que o enunciado diz que os
programas A e B precisam alternar as suas execuções no
processador, e que deve existir ociosidade do processador antes
de cada programa terminar a sua execução. Como a ordem inicial
de execução dos programas não foi dada, precisaremos
considerar dois casos, A iniciar antes de B e B iniciar antes de A.
Se A foi o primeiro a iniciar, então a primeira parte da execução de
B poderá ser usada para evitar parte da ociosidade durante a
operação de E/S feita por A, e a segunda parte da execução de A
poderá ser usada para evitar parte da ociosidade durante a
operação de E/S feita por B. Logo, o tempo 6x da primeira parte
da execução de B deverá ser menor do que o tempo a da
operação de E/S de A, para garantir que exista ociosidade antes
de A terminar a sua execução. Além disso, o tempo 6x da
segunda parte da execução de A deverá ser menor do que b − (a
− 6x), que é o tempo restante da operação de E/S de B (note que,
por (a − 6x) ms, as operações de E/S de A e de B serão feitas de
modo concorrente), para garantir que exista ociosidade antes de B
terminar a sua execução. Nessa primeira ordem, mostrada na
figura a seguir, o tempo de ociosidade do processador será de a −
6x + b − a = (b − 6x) ms.
2x ms 6x ms a-6x ms 6x ms b -a 4x ms
A B Ocioso A Ocioso B
|---------------a-------------|
|----------------------b-------------------|
Agora, quando B for o primeiro a iniciar, então a primeira parte da
execução de A poderá ser usada para evitar parte da ociosidade
durante a operação de E/S feita por B, e a segunda parte da
execução de B poderá ser usada para evitar parte da ociosidade
durante a operação de E/S feita por A. Logo, o tempo 2x da
primeira parte da execução de A deverá ser menor do que tempo
b da operação de E/S de B, para garantir que exista ociosidade
antes de B terminar a sua execução. Além disso, o tempo 4x da
segunda parte da execução de B deverá ser menor do que a − (b
− 2x), que é o tempo restante da operação de E/S de A (agora
devido a as operações serem feitas concorrentemente por (b − 2x)
ms), para garantir que exista ociosidade antes de A terminar a sua
execução. Nessa segunda ordem, mostrada na figura a seguir, o
tempo de ociosidade será de b − 2 x + a − b − 2x = (a − 4x) ms.
6x ms 2x ms b-2x ms 4x ms a-b-2xms 6x ms
B A Ocioso B Ocioso A
|---------------b-------------|
|----------------------a-------------------|
2. (1,0) Considere a hierarquia de diretórios dada a seguir, e
suponha que você está no diretório /usr/files/. Com relação a
esse diretório, existirá algo no diretório cujo caminho relativo é
../../etc/../home/docs/../../usr/exec/../local/bin/../../../home/files/,
supondo que “..” indica o diretório pai do diretório atual durante o
percurso? Qual será o caminho relativo mais sucinto ao mesmo
diretório final a partir do mesmo diretório inicial? E qual será o
caminho absoluto ao mesmo diretório final?
Resp.:
Caminho mais sucinto: ../../home/files/
Caminho absoluto: /home/files/
3. (2,0) Suponha que o sistema operacional esteja executando
diretamente sobre o hardware de um computador onde cada
operação de E/S demore 0,75 ms. Suponha ainda que um
processo tenha executado por 15.250 ms e que, durante a sua
execução, tenha feito 3.000 operações de E/S. Se o sistema
operacional agora executar sobre uma máquina virtual que reduza
a velocidade do processador em 40% e a velocidade das
operações de E/S em x%, e se além disso forem feitas somente a
metade das operações de E/S feitas sobre o hardware, qual será
o valor de x se o tempo de execução do processo na máquina
virtual for de 27.250 ms? Justifique a sua resposta.
Resp.: Como o tempo total de execução é de 15.250 ms, e como
o processo faz 3.000 operações de E/S com duração de 0,75 ms
cada, então 2.250 ms dos 15.250 ms são gastos com operações
de E/S quando a execução ocorre sobre o hardware do
computador. Logo, o processo executa no processador desse
hardware por 13.000 ms (15.250 − 2.250). Note que a velocidade
do processador ser reduzida em 40% significa que a velocidade
do processador virtual é 60% da velocidade do processador real, o
que por sua vez significa que, durante os 13.000 ms, somente
60% das instruções poderão ser executadas. O tempo necessário
para executar 100% das instruções sobre a máquina virtual será
de 13000/0,6 ms. Agora, como o processo fez a metade das
operações de E/S, ou seja, 1.500 operações, na máquina virtual, e
como o novo tempo de cada operação de E/S é de
0,75/((100-x)/100) = 75/(100-x) ms (já que, similarmente à redução
da velocidade do processador, a redução da velocidade de cada
operação de E/S em x% significa que no mesmo tempo podemos,
na máquina virtual, executar somente (100 − x)% das operações
de E/S originais), então 1500 × 75/(100-x) = 112500/(100-x) ms
dos 27.250 ms de execução do processo na máquina virtual serão
gastos com E/S. Logo, o tempo de execução do processo no
processador virtual será de:
(27.250 ms - 112500/(100-x)) ms.
Usando 13000/0,6 ms = (27.250 - 112500/(100-x)) ms, temos que:
13000/0,6 = 27250 - 112500/(100-x)
27250 - 13000/0,6 = 112500/(100-x)
27250*0,6 - 13000 = 0,6*112500/(100-x)
3350*(100-x) = 67500
335000 - 3350x = 67500
x = 267500/3350
x = 79,850746269
Logo, a redução de velocidade das operações de E/S sobre
máquina virtual será de 79,85%.
4. (1,0) Suponha que tenha ocorrido uma interrupção do disco
enquanto um processo estava em execução. Um aluno de
sistemas operacionais disse que a figura a seguir mostra a ordem
correta das ações realizadas quando essa interrupção foi tratada
pelo sistema operacional. Se você acha que a figura do aluno está
correta basta responder que sim mas, se você acha que ela está
errada, então indique quais são os erros na figura do aluno.
Resp.: A figura do aluno está errada porque somente a sequência
das ações de 6 até 9 está correta. A sequência correta das ações
de 1 até 6, já renumeradas, é dada a seguir. Após a ação 1,
quando o processo foi suspenso para o tratamento da interrupção
do disco, a ação 2, “Inıćio do procedimentoem assembly”, e,
dentro do procedimento em assembly, a ação 3, “Inıćio do
procedimento em C”, são executadas em sequência, com o
objetivo de fazer as tarefas necessárias para salvar o contexto do
processo que estava executando e preparar para a execução do
tratador do disco. Após a ação 3, o escalonador é chamado para
escolher o “Tratador do disco” para ser executado e tratar a
interrupção. Logo, a próxima ação 4, “Escalonador”, dada na parte
esquerda da figura, é executada para fazer exatamente isso. Após
o término da ação 4, as ações 5, “Fim do procedimento em C”, e
6, “Fim do procedimento em assembly”, são executadas, em
ordem, para fazer as finalizações necessárias para executar o
tratador do disco. Finalmente, após a ação 6 ser finalizada, a
sequência das ações restantes é a mesma dada pelo aluno. A
seguir está a figura com as ações executadas na ordem correta.
5. (2,0) Suponha que três processos, A, B e C, compartilhem uma
pilha, inicialmente cheia, que pode armazenar até p números, e
uma fila, inicialmente vazia, que pode armazenar até f números. O
processo A continuamente insere x números no topo da pilha. Já o
processo B continuamente remove três números do topo da pilha
e, quando consegue obter com sucesso esses números, adiciona
a soma deles ao topo da pilha e o produto deles no final da fila.
Finalmente, o processo C remove y números do inıćio da fila e os
imprime na tela. Como quatro semáforos de contagem e dois
semáforos binários podem ser usados para garantir que os
processos executem sem condições de corrida ou impasses?
Justifique a sua resposta. Suponha que a pilha possua um
procedimento InsereTopo(a) para inserir a no topo da pilha e a
função RemoveTopo() para remover e retornar o número que está
no topo da pilha, e que a fila possua um procedimento
InsereFinal(b) para inserir b no final da fila e a função
RemoveInicio() para remover e retornar o número que está no
inıćio da fila.
Resp.: A seguir mostramos como seis semáforos, dois binários e
quatro de contagem, podem ser usados para implementar os
códigos dos processos. O primeiro semáforo binário, chamado
AcessoPilha, é usado para garantir o acesso exclusivo à pilha. Já
o segundo semáforo binário, chamado de AcessoFila, é usado
para garantir o acesso exclusivo à fila. O primeiro semáforo de
contagem, chamado LivresPilha, conta a quantidade de números
que ainda podem ser inseridos na pilha, e é usado para bloquear
A quando x números adicionais não puderem ser inseridos na
pilha (note que B não precisa usar esse semáforo porque ele
remove três números da pilha antes de adicionar a soma ao topo
da pilha). O segundo semáforo de contagem, chamado
UsadosPilha, conta a quantidade de números presentes na pilha,
e é usado para bloquear B quando a pilha possui menos do que
três números. O terceiro semáforo de contagem, chamado
LivresFila, conta a quantidade de números que ainda podem ser
inseridos na fila, e é usado para bloquear B quando a fila está
cheia. Finalmente, o quarto semáforo de contagem, chamado
UsadosFila, conta a quantidade de números presentes na fila, e é
usado para bloquear C quando a fila não possui pelo menos y
números. Como inicialmente a pilha está cheia, a fila está vazia, e
ambas não estão sendo usadas, então os valores iniciais dos
semáforos, AcessoPilha, AcessoFila, LivresPilha, UsadosPilha,
LivresFila e UsadosFila, são respectivamente, 1, 1, 0, p, f e 0. A
seguir mostramos os códigos para os processos A, B e C.
6. (2,0) Suponha que dois processos, A e B, que não fazem
operações de E/S, estejam em execução no sistema operacional,
precisando executar por, respectivamente, a ms e b ms no
processador, sendo a e b inteiros, a ıḿpar, b par, a > 1 e b > 2.
Suponha ainda que o sistema operacional use o escalonamento
por prioridades, em que a prioridade do processo em execução é
reduzida em 1 unidade a cada 1 ms, e em que o processo em
execução somente seja suspenso quando um outro processo
passa a ter a maior prioridade. Se as prioridades iniciais de A e de
B forem os seus tempos de execução, qual será a ordem de
execução de A e de B no processador? E quais serão os tempos
decorridos entre o inıćio e o término de A e de B? Justifique a sua
resposta.
Resp.: Pelo enunciado, vemos que os processos A e B precisam
executar por, respectivamente, a ms e b ms, e que as prioridades
iniciais deles são de, respectivamente, a e b. Como a é ıḿpar e b
é par, então precisaremos avaliar apenas dois casos, a < b e a >
b, já que a = b não é possivel. Se a < b, inicialmente B executará
consecutivamente no processador por b − (a − 1) = b − a + 1
vezes, porque a prioridade será reduzida em 1 a cada 1 ms, e
porque A, cuja prioridade é a, somente poderá executar quando a
prioridade de B for a − 1. Depois disso, A executará duas vezes,
reduzindo a sua prioridade de a para a − 2, B por mais duas
vezes, reduzindo a sua prioridade de a − 1 para a − 3, e assim
sucessivamente, até B terminar a sua execução, o que ocorrerá
após A e B terem executado, como explicado, por (a−1)/2 vezes.
Agora, como A somente terá executado por a − 1 vezes, então
precisará executar por mais uma vez. A ordem de execução
referente a este primeiro caso é mostrada na figura a seguir.
Nesta figura damos também, abaixo do nome do processo, a
prioridade dele antes de executar no processador. Pela figura,
vemos que os tempos decorridos entre o inıćio e o término de A e
de B serão de, respectivamente, 2a − 2 + 1 = (2a − 1) ms e b − a +
1 + 2a − 2 = (a + b − 1) ms.
Porém, se a > b, inicialmente A executará consecutivamente no
processador por a − (b − 1) = a − b + 1 vezes, porque a prioridade
será reduzida em 1 a cada 1 ms, e porque B, cuja prioridade é b,
somente poderá executar quando a prioridade de A for b − 1.
Depois disso, B executará duas vezes, reduzindo a sua prioridade
de b para b − 2, A por mais duas vezes, reduzindo a sua
prioridade de b − 1 para b − 3, e assim sucessivamente, até faltar
somente 1 ms para A terminar, o que ocorrerá após B e A terem
executado, como explicado, por (b−2)/2 vezes. Agora, como A terá
executado por a − 1 vezes e B por b − 2 vezes, e como as
prioridades de A e de B, após as execuções anteriores, serão 1 e
2, B executará por mais duas vezes adicionais, seguidas por mais
uma execução de A. A ordem de execução, referente a este
segundo caso, é mostrada na figura a seguir, na qual também
mostramos a prioridade do processo antes de ele executar,
sempre abaixo do seu nome. Pela figura, vemos que os tempos
decorridos entre o inıćio e o término dos processos serão de,
respectivamente, (a+b) ms e 2b−4+2 = (2b−2) ms.