APX1_2020-1_Gabarito_Sistemas Operacionais pdf

Prévia do material em texto

Curso de Tecnologia em Sistemas de Computação
Disciplina de Sistemas Operacionais
Professores: Valmir C. Barbosa e Felipe M. G. França
Assistente: Alexandre H. L. Porto
Quarto Peŕıodo
Gabarito da AP1X - Primeiro Semestre de 2020
Atenção: Esta versão da AP1 está sendo realizada, excepcional-
mente, no mesmo molde das ADs. Assim, valem para ela as mes-
mas normas adotadas para as ADs, como a seguir. Cada aluno é
responsável por redigir suas próprias respostas. Provas iguais umas às ou-
tras terão suas notas diminúıdas. As diminuições nas notas ocorrerão em
proporção à similaridade entre as respostas. Exemplo: Três alunos que res-
pondam identicamente a uma mesma questão terão, cada um, 1/3 dos pontos
daquela questão. Esta AP1X deverá ser entregue, através da plata-
forma, até as 13 horas do dia 25/04/2020.
Nome -
Assinatura -
1
1. (1,5) Suponha que um programa A tenha um tempo de execução no
processador de 12 ms e que a sua execução seja interrompida para que
faça duas operações de E/S, com durações de, respectivamente, 2,5 ms
e 3,2 ms. Suponha ainda que a primeira operação de E/S seja feita
após A executar por 3,7 ms, e que a segunda operação de E/S seja feita
após A executar por mais 4,9 ms. Se a multiprogamação for usada
somente para evitar a ociosidade do processador quando operações de
E/S são feitas, e se um programa B puder ser executado, qual deverá
ser a natureza de B e como deverá executar para evitar ambas as ocio-
sidades durante as operações de E/S de A? Qual será o tempo mı́nimo
de execução de B no processador? Justifique a sua resposta.
Resp.: Pelo enunciado, vemos que o programa A executa por 3,7 ms
antes de fazer a sua primeira operação de E/S, com duração de 2,5 ms,
por mais 4,9 ms antes de fazer a sua segunda operação de E/S, com
duração de 3,2 ms, e finalmente por mais 3,4 ms até terminar. Para
que o programa B possa ser usado para evitar a ociosidade durante as
duas operações de E/S feitas por A, ele precisará fazer uma operação
de E/S para permitir que as suas duas execuções, com tempos de x ms
e y ms, antes e depois de ele fazer a sua operação, sejam usadas para
evitar as duas ociosidades durante a execução de A. A figura a seguir
ilustra esse comportamento de A e B.
Tempo
3,7 ms
A
4,9 ms
A
3,4 ms
A
3,2 ms
E/S
2,5 ms
E/S
Tempo
y ms
B
x ms
B E/S
Agora, para que a primeira parte de B, com tempo x ms, executada an-
tes de B fazer a sua operação de E/S, possa evitar a ociosidade durante
a primeira operação de E/S feita por A, o tempo x de execução dessa
parte deve ser pelo menos igual ao tempo de 2,5 ms dessa operação,
2
ou seja, x ≥ 2, 5. Finalmente, para evitar a ociosidade durante a se-
gunda operação de E/S feita por A, com tempo de 3,2 ms, o tempo y
de execução da segunda parte de B deve ser pelo menos igual ao tempo
dessa operação, ou seja, y ≥ 3, 2. Como desejamos o tempo mı́nimo de
execução de B, que é obtido minimizando x e y, então conclúımos que
o tempo mı́nimo de execução de B é de 5,7 ms, obtido quando x = 2, 5
e y = 3, 2. A seguir mostramos como a ociosidade é evitada usando o
tempo mı́nimo de execução de B.
Tempo
2,5 ms
B
3,7 ms
A
4,9 ms
A
3,4 ms
A
3,2 ms
B
Note que, na figura, está sendo suposto que a operação de E/S de
B requer no máximo 4,9 ms. Em caso contrário, haveria ociosidade
causada pelas operações de E/S de A e de B.
2. (2,5) Diga se as seguintes afirmativas são falsas ou verdadeiras. Para
responder, escreva apenas F ou V para cada item em seu caderno de
respostas.
(a) (0,5) Quanto ao número de programas em execução, o sistema ope-
racional pode ser classificado como monoprogramado se somente
um programa, além do sistema, pode estar residente na memória,
ou como multiprogramado se vários programas podem estar resi-
dentes na memória.
Resp.: V (Verdadeira).
(b) (0,5) Um diretório de um sistema de arquivos é um arquivo espe-
cial usado para agrupar um conjunto de arquivos e/ou diretórios
relacionados.
Resp.: V (Verdadeira).
3
(c) (0,5) Quando a espera pelo evento externo que causou o bloqueio
de um processo terminar, o processo passará do estado Bloque-
ado ao estado Executando.
Resp.: F (Falsa), porque o processo desbloqueado deve, na ver-
dade, passar ao estado Pronto, devido a o processo em execução
ou algum outro processo no estado Pronto poder ser mais prio-
ritário do que o processo desbloqueado.
(d) (0,5) Um processo A pode bloquear um outro processo B que co-
opera com ele mesmo quando A não está executando a sua seção
cŕıtica.
Resp.: F (Falsa), pois um processo somente pode bloquear um
outro processo que coopera com ele quando está dentro da sua
seção cŕıtica, para evitar que ambos acessem concorrentemente as
suas seções cŕıticas.
(e) (0,5) Os algoritmos de escalonamento por round robin e por
prioridades são algoritmos preemptivos, pois em ambos os casos
os processos são suspensos após executarem por algum tempo no
processador, sendo que a suspensão ocorre no primeiro algoritmo
após ter passado um intervalo de tempo chamado de quantum,
e no segundo após o processo deixar de ser o mais prioritário.
Resp.: V (Verdadeira).
3. (1,5) Diga a quais conceitos vistos em aula se referem as seguintes
definições:
(a) (0,5) Nome dado à hierarquia definida quando os processos criam
outros processos, relacionando cada processo criado com o pro-
cesso que o criou.
Resp.: Árvore de processos.
4
(b) (0,5) Nome dado aos processos que, ao executarem as suas tare-
fas, não precisam interagir com os usuários do sistema operacional.
Resp.: Em segundo plano ou Background.
(c) (0,5) Nome dado ao tipo de algoritmo de escalonamento que não
usa, caso exista, o temporizador do hardware, implicando em que
o processo em execução em uma unidade de processamento exe-
cutará até terminar ou ser bloqueado.
Resp.: Não-preemptivo.
4. (1,5) Um aluno afirmou que cada ordem de execução e tipo de parale-
lismo dados nas figuras a seguir estão corretos, supondo que os proces-
sos executem em um sistema operacional que não permita a execução
de partes paralelas de um mesmo processo. Se cada ocorrência de um
processo em um dos processadores durar o mesmo tempo, e se cada
processo executar pelo mesmo tempo total quando um, dois ou quatro
processadores forem usados, então todas as afirmações do aluno estão
corretas? Se você acha que sim, basta dizer isso mas, se você acha que
não, diga quais afirmações estão erradas.
1 Processador
Pseudoparalelismo
B C A BAD D D
Pseudoparalelismo
entre processadores
Processador 1 B A BD
Processador 2 AC D D
2 Processadores
Paralelismo real
entre processadores
Processador 1 CB A D D
Processador 2 AB
ocioso
D
5
Paralelismo real
4 Processadores
Processador 1 A A
ocioso
Processador 2 B B B
Processador 3 C
ocioso
Processador 4
ocioso
D D
Resp.: Quatro das afirmações do aluno estão incorretas, porque exis-
tem dois erros na segunda figura e dois erros na terceira figura. Como
vimos na aula 4, o pseudoparalelismo ocorre quando um processador
executa mais de um processo, e o paralelismo real ocorre quando pro-
cessos distintos são executados por processadores distintos. Na figura
que mostra a execução com dois processadores, temos uma situação
mista nas duas partes (esquerda e direita), pois ambas mostram para-
lelismo real entre processadores e pseudoparalelismo em cada proces-
sador. Logo, nessa figura, o erro da parte esquerda é que, assim como
na parte direita, temos um paralelismo real entre processadores. Já na
parte direita dessa figura, o erro é que o paralelismo mostrado é proi-
bido pelo enunciado, já que partes de um mesmo processo não podem
executar em paralelo. Finalmente, na figura que mostra a execução
com quatro processadores, existem dois erros devido a os processos B
e D não executarem pela mesma quantidade total de tempo que exe-
cutaram quando um ou dois processadores foram usados.Nessa figura,
B executou por mais tempo devido a existirem três ocorrências dele
na ordem do Processador 2, e D executou por menos tempo devido a
existirem somente duas ocorrências dele na ordem do Processador 4.
5. (1,5) Suponha que um conjunto possa armazenar até n números. Su-
ponha ainda que ele seja compartilhado por dois processos A e B, e que
inicialmente possua x números, 0 ≤ x ≤ n. O processo A continua-
mente coloca dois números no conjunto caso ele ainda possa armazenar
6
dois números adicionais. Já o processo B continuamente espera que
o conjunto tenha pelo menos dois números, para depois remover dois
números do conjunto e colocar o produto deles no conjunto. Como
dois semáforos de contagem e um semáforo binário podem ser usados
para garantir que os processos executem sem condições de corrida ou
impasses? Justifique a sua resposta.
Resp.: Vamos usar um semáforo binário, chamado de acesso, para ga-
rantir o acesso exclusivo ao conjunto. Um dos semáforos de contagem,
chamado de ocupados , é usado para contar a quantidade de números
no conjunto, e será usado para bloquear o processo B se o conjunto
não possuir pelo menos dois números. Já o outro semáforo de conta-
gem, chamado de livres, é usado para contar a quantidade de números
que ainda podem ser inseridos no conjunto, e será usado para bloquear
o processo A caso não seja posśıvel inserir pelo menos dois números
no conjunto. Como inicialmente o conjunto não está sendo usado e
possui x números, então os semáforos acesso, ocupados e livres serão
inicializados com, respectivamente, 1, x e n − x. A seguir mostramos
os pseudocódigos para os processos A e B usando esses três semáforos.
Nestes pseudocódigos, supomos que a função InsereConjunto(a) insere
o número a no conjunto, e que a função RemoveConjunto() remove e
retorna um número do conjunto.
7
void ProcessoA(void)
{
while(1)
{
// Garante que podemos armazenar pelo menos dois números no conjunto.
P(livres);
P(livres);
// Obtém o acesso exclusivo ao conjunto.
P(acesso);
// Código para gerar dois números e armazená-los em a1 e a2.
// Insere a1 e a2 no conjunto.
InsereConjunto(a1);
InsereConjunto(a2);
// Usa duas operações V sobre ocupados para registrar que a1 e a2 foram
// inseridos no conjunto.
V(ocupados);
V(ocupados);
// Libera o acesso exclusivo ao conjunto.
V(acesso);
}
}
8
void ProcessoB(void)
{
while(1)
{
// Garante que existem pelo menos dois números no conjunto.
P(ocupados);
P(ocupados);
// Obtém o acesso exclusivo ao conjunto.
P(acesso);
// Remove dois números do conjunto e os armazena em a1 e a2.
a1 = RemoveConjunto();
a2 = RemoveConjunto();
// Insere o produto de a1 e a2 no conjunto. Note que podemos inserir um
// novo número porque foram removidos dois números do conjunto.
InsereConjunto(a1 ∗ a2);
// Usa a operação V sobre ocupados para registrar que a1 ∗ a2 foi inserido
// no conjunto.
V(ocupados);
// Como inserimos um número no conjunto, então precisamos usar somente
// uma operação V sobre livres para registrar que mais um número
// adicional pode ser inserido no conjunto.
V(livres);
// Libera o acesso exclusivo ao conjunto.
V(acesso);
}
}
6. (1,5) Suponha que três processos A, B e C, que não fazem operações de
E/S, tenham executado como na tabela dada a seguir, quando o sistema
operacional usou um algoritmo por round robin com um quantum de
4 ms. Nesta tabela, cada coluna da primeira linha dá o tempo, em ms,
antes de o processo dado nessa coluna executar, e a segunda linha dá a
ordem de execução dos processos. Suponha agora que o sistema tenha
passado a usar um algoritmo de prioridades que reduz a prioridade do
processo em execução em 3 unidades a cada 5 ms. Se um processo
executar enquanto não existir um outro processo com uma prioridade
maior, os tempos de término de A, B e C serão os mesmos do caso
round robin se as prioridades iniciais deles forem de, respectivamente,
17, 24 e 19? Justifique a sua resposta.
0 4 8 12 16 20 24 28 32 35 39 41 45 46
A C B A C B A C B A C A A -
9
Resp.: Pela tabela do enunciado, vemos que os tempos de execução
dos processos A, B e C são, respectivamente, 21 ms, 11 ms e 14 ms,
e que os tempos de término são, respectivamente, 46 ms, 35 ms e 41
ms. A seguir mostramos uma tabela similar à dada no enunciado da
questão, mas que possui uma linha adicional onde cada coluna indica,
para o processo dessa coluna, a sua prioridade antes de ele executar
no tempo também dado nessa coluna. Pela tabela, vemos que os novos
tempos de término serão, respectivamente, 46 ms, 16 ms e 35 ms. Logo,
o tempo de término de A foi o mesmo, mas os tempos de término de B
e C foram menores em, respectivamente 19 ms e 6 ms.
0 5 10 15 16 21 26 31 35 40 45 46
B B C B A C A C A A A -
24 21 19 18 17 16 14 13 11 8 5 -
10