SistemasOperacionaris-CEDERJ-2021-1_APX2

Prévia do material em texto

Curso de Tecnologia em Sistemas de Computação
Disciplina de Sistemas Operacionais
Professores: Claudio Miceli de Farias e Diego L. C. Dutra
Assistente: Alexandre H. L. Porto e Davi Brilhante
APX2 - 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. (1,5) Suponha que n processos estejam em execução no sistema
operacional, e que cada processo Pi , 1 ≤ i ≤ n, tenha obtido com
sucesso o recurso não-preemptivo Ri. Quantos impasses
diferentes poderão existir envolvendo todos os processos e todos
os recursos obtidos por eles? Justifique a sua resposta.
RESPOSTA: Primeiramente, vamos notar que as solicitações
dadas no enunciado definiram, no grafo de recursos, n arestas,
sendo que cada aresta é da forma Ri → Pi e indica que o
processo Pi obteve com sucesso o recurso Ri . Agora, note que
um dado impasse envolvendo todos os processos e todos os
recursos obtidos por eles, representado por um ciclo no grafo de
recursos, define uma ordem para essas n arestas, obtida ao
percorrer esse ciclo a partir de um dos recursos R i . Esse mesmo
ciclo também define n − 1 outras ordens, dependendo do recurso
Ri escolhido. Com isso, para descobrir o número total de
impasses, ou seja, o número total de ciclos diferentes do grafo
com arestas Ri → Pi , basta calcular o número de possı́veis
modos de ordenar essas arestas e depois dividir esse número por
n. Para formar o ciclo, cada par de arestas Rx → Px e Ry → Py
consecutivas em uma ordem (incluindo o par formado pela última
aresta seguida pela primeira) é interligado por uma aresta Px →
Ry , indicando que Px foi bloqueado ao tentar solicitar Ry . O
número total de possı́veis modos de ordenar as n arestas é n × (n
− 1) · · · × 1 = n!, porque a cada nova aresta escolhida e
adiconada à ordem, o número de arestas ainda não adicionadas
diminui em 1 até sobrar somente uma aresta ainda não adicionada
à ordem. Logo, o número total de ciclos diferentes, ou seja, de
impasses, é de (n − 1)!, porque n!/n= (n − 1)!.
2. (1,0) Porque é errado afirmar que se a alocação baseada em nós-
i for usada, então existirá um nó-i associado a cada arquivo
armazenado no sistema de arquivos, e nele serão armazenados
os endereços de todos os blocos do disco usados pelo arquivo?
RESPOSTA: Porque, apesar de existir um nó-i associado a cada
arquivo armazenado no disco, ele armazena, junto com os
atributos do arquivo, somente os endereços dos 10 primeiros
blocos usados pelo arquivo.
3. (1,0) De quais fatores depende o tamanho em bits de um mapa de
bits?
RESPOSTA: Esse tamanho depende do número total de blocos
do disco, já que existe um bit diferente no mapa para cada bloco.
Esse bit indica se o bloco está ou não sendo usado por um
arquivo do sistema de arquivos.
4. (1,5) Suponha que quatro processos, A, B, C e D, estejam em
execução, e que seus tamanhos sejam de, respectivamente,
28MB, 571MB, 1211 MB e 234MB. Se a segmentação com
paginação for usada pelo sistema operacional, se cada processo
for armazenado em um segmento, e se os possíveis tamanhos da
página virtual forem 32MB, 128MB, 768MB e 1536MB, qual será o
maior conjunto de processos que poderá ser armazenado na
memória para cada tamanho de página, supondo uma memória
física com 3GB? Se, para um tamanho de página, existirem
múltiplos conjuntos, escolha aqueles que minimizarem o
desperdício de espaço devido à fragmentaçãao interna dentro das
páginas. Justifique a sua resposta.
RESPOSTA: Primeiramente, na tabela a seguir, mostramos o
número de molduras de página (igual ao número de páginas
virtuais) necessário para armazenar cada um dos segmentos com
os processos. Na primeira coluna mostramos o tamanho da
moldura. Na segunda coluna mostramos o número total de
molduras para o tamanho dado na primeira coluna e para uma
memória de 3GB ou 3072MB. Nas colunas 3 a 6 mostramos a
quantidade de molduras usadas pelos segmentos. Finalmente, na
última coluna, mostramos o número total de molduras necessárias
para armazenar simultaneamente todos os segmentos. Como
podemos ver pela tabela, para os tamanhos 32MB e 128MB,
conseguiremos armazenar todos os quatro segmentos na
memória, ou seja, o conjunto com A, B, C e D. Porém, para o
tamanho de 768MB, poderemos armazenar somente três
segmentos. O segmento de C, com 1211MB, usa duas páginas de
768MB, sendo que o espaço gasto na última página devido à
fragmentação interna é de 768 − (1211 − 768) = 325MB. Além
disso, como os segmentos de A, B e D usam somente uma
página, então o espaço desperdiçado devido à fragmentação
interna, para cada segmento, será 768MB menos o tamanho
desse segmento, ou seja, as sobras serão de, respectivamente,
768−28 = 740MB, 768−571 = 197MB e 768 − 234 = 534MB. Como
o processo A tem a maior sobra, para o tamanho de 768MB o
conjunto será composto por B, C e D. Finalmente, para o tamanho
de 1536MB, poderemos somente armazenar dois segmentos e,
similarmente ao que vimos para o tamanho de página de 768MB,
escolheremos os processos com os maiores tamanhos (pois cada
segmento também usa uma página, e novamente a fragmentação
interna, igual a 1536 menos o tamanho do processo, é menor para
os maiores processos). Assim, o conjunto será composto por B e
C.
Tam. da 
Moldura
Num.
De 
Processos
Processos Total de 
MoldurasA B C D
32 MB 96 1 18 38 8 65
128 MB 24 1 5 10 2 18
768 MB 4 1 1 2 1 5
1536 MB 2 1 1 1 1 4
5. (2,0) Qual o nome dado ao algoritmo de substituição de páginas
que ordena as páginas, em ordem crescente, de acordo com o
tempo do seu último acesso, para depois escolher a primeira
nessa ordem para ser a substituída. Forneça um exemplo.
RESPOSTA: LRU 
Como vimos na aula 9, no algoritmo LRU, as páginas são
primeiramente ordenadas, em ordem crescente, de acordo com o
tempo do seu último acesso. A página a ser substituı́da é a
primeira página segundo essa ordenação, isto é, a página não
acessada há mais tempo. Um exemplo pode ser visto na aula 9
onde as páginas são primeiramente ordenadas, em ordem
crescente, de acordo com o tempo do seu último acesso. 
6. (1,5) Corrija a frase a seguir e justifque a sua correção: “Quando a
política de alocação global de memória virtual é usada, todos os
segmentos de todos os processos são consideradas pelo
algoritmo de segmentação quando não existe mais espaço na
memória para armazenar segmentos adicionais. Ao contrário
disso, a política de alocação local somente considera os
segmentos associados ao processo que precisa de mais espaço.”
RESPOSTA: 
Correção possível: “Quando a polı́tica de alocação global é usada,
todas as páginas virtuais de todos os processos são consideradas
pelo algoritmo de substituição de páginas quando uma falha de
página ocorre. Ao contrário disso, somente as páginas alocadas
ao processo que gerou a falha são consideradas pelo algoritmo.”
Justificativa: Na verdade as polı́ticas se referem às páginas
escolhidas pelo algoritmo de memória virtual ou paginação
quando falhas de página ocorrem. Quando a polı́tica de alocação
global é usada, todas as páginas virtuais de todos os processos
são consideradas pelo algoritmo de substituição de páginas
quando uma falha de página ocorre. Já na polı́tica de alocação
local, somente as páginas alocadas ao processo que gerou a falha
são consideradas pelo algoritmo.
7. (1,5) O que é a fragmentação externa de memóriae em que casos
ela ocorre?
RESPOSTA: Quando um processo é carregado e removido da
memória, o espaço livre cria o buraco no espaço da memória e
existem muitos buracos no espaço da memória, isso é chamado
de fragmentação externa.
A fragmentação externa ocorre quando há uma quantidade
suficiente de espaço na memória para satisfazer a solicitação de
memória de um processo. Mas a solicitação de memória do
processo não pode ser atendida, pois a memória disponível é de
maneira não contígua. Se você aplicar a estratégia de alocação de
memória de primeiro ou melhor ajuste, isso causará fragmentação
externa. Ou seja, a fragmentação externa somente ocorre quando
a segmentação pura é usada.