P2_2011-2

Prévia do material em texto

DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO 
SISTEMAS OPERACIONAIS I - 20 SEM/11 – PROVA II 
 
G A B A R I T O 
 
Tempo de Prova: 100 minutos / Escore Máximo: 300 pontos 
 
Aluno: __________________________________________________ Escore: __________ 
 
 
 
1ª Questão – Particionamento da Memória (100 pontos) 
 
Calcule e responda de forma sucinta e clara cada uma das questões a seguir. 
 
1. Considerando que num sistema dotado de uma memória cache para instruções de 512MB e uma memó-
ria primária de 2GB, o tempo médio de acesso (leitura) de uma instrução qualquer seja dado pela fórmu-
la abaixo: (50) 
 
mccma thittT *)1(  
Onde, 
Tma  tempo médio de acesso 
tc  tempo de acesso à cache 
tp  tempo de acesso à memória principal 
hitc  taxa de hit (sucesso) da cache 
 
Supondo que neste sistema você tenha tc = 10ns e tm = 800ns 
 
a. Calcule Tma caso a taxa de hit na cache seja zero. 
R. Tma = tc + tm = 810ns 
b. Calcule agora, a taxa mínima de hit da cache de forma a garantir um Tma máximo de 90ns. 
R. 90 ≥ tc + (1 – hitc) * tm  hitc ≥ 90% 
 
Considerando agora a existência de uma cache L2 de 1GB, a fórmula de cálculo do Tma passa a ser a seguinte: 
 
]*)1([*)1( 2211 mLLLLma thitthittT  
 
c. Estime o Tma considerando que o sistema tenha sofrido um upgrade e possua agora os seguintes níveis de ar-
mazenamento temporário da instrução: cache L1 de 512MB com tL1=10ns e hitL1=90%; cache L2 de 1GB 
com tL2=20ns e hitL2=95%; memória primária expandida para 4GB com tm=800ns e PF=30% (Page Fault) e 
uma memória virtual de 300GB mantida em um HD SCSI com as seguintes características técnicas: velocida-
de de rotação – 6000rpm; número de cilindros – 100; número de setores por trilha – 1000; número de bytes 
por setor – 512; número de superfícies úteis – 10; tempo gasto no movimento das cabeças de leitura/gravação 
entre cilindros adjacentes (parâmetro “m”) – 10s; startup e stop time – 5s cada um (assuma que cada pá-
gina virtual tenha 512 bytes e que o acesso às PVs tenha comportamento aleatório). 
R. Tma = tL1 + (1 – hitL1) * [tL2 + (1 – hitL2) * {tm + PF * tMV}] onde tMV = Ts + A + Tt 
 Ts = n * m + S = 100/2 * 10s + 2 * 5s= 510s = 510000ns 
 A = 1/2r = 1 / (2 * 6000rpm) = 0,005s = 5000000ns 
 Tt = b / Nr = 512 / (512*1000*6000rpm) = 0,00001s = 10000ns 
 TMV = 510000 + 5000000 + 10000 = 5520000ns 
 Tma = 10 + (1 – 0,9) * [20 + (1 – 0,95) * {800 + 0,3 * 5520000}] = 8296ns = 8,296s 
Tma = 8,296s 
d. A taxa de hit de uma cache é constante (sempre a mesma) para todos os processos em execução? Justifique 
sua resposta. 
R. NÃO. Varia de fluxo de execução para fluxo de execução. 
e. Apresente (cite) o que, a seu ver, são os principais fatores que influenciam na taxa de hit real de uma cache. 
R. Depende de condições inerentes à própria da cache (tamanho; velocidade de acesso e tipo – acesso 
direto ou associativa, por exemplo); e 
 da taxa de hit que é muito dependente do princípio da localidade, que é inerente a cada fluxo de execu-
ção 
 
2. Considerando as possíveis estratégias de particionamento da memória principal vistas em sala: (50) 
 
a. O que significam os termos “fragmentação interna” e “fragmentação externa”? 
R. Fragmentação interna  espaço de memória não utilizado dentro (interno) da partição recebida pe-
lo processo; 
Fragmentação externa  espaço de memória impossível de ser usado (em função do seu tamanho) e 
que é externo as partições recebidas pelos processos 
b. Em termos de desempenho, aponte qual das estratégias de particionamento: dinâmico; estático ou estático re-
locável é a pior? Justifique. 
R. Dinâmico em função do overhead gerado a partir da fragmentação externa (que quando excessiva é 
conhecida por colcha de retalhos) 
c. Qual a diferença conceitual entre as estratégias de particionamento conhecidas por Paginação e Segmentação? 
R. Na Paginação todas as páginas são de tamanho fixo (todas iguais ou variando finitamente em valores 
pré-definidos) e formadas seqüencialmente independente de qualquer lógica do programa; 
Na segmentação os segmentos podem ter tamanhos diferentes e são criados com o intuito de preservar 
alguma lógica do programa (área de dados, rotina principal, etc). 
d. Sabendo que o Buddy System é um tipo de particionamento dinâmico onde a memória a ser alocada a um 
processo qualquer é organizada em blocos de 2K, com L ≤ K ≤ U, onde 2L – é menor bloco que pode ser 
alocado e 2U – o maior bloco (tamanho da memória), calcule o endereço inicial e o tamanho dos blocos de 
memória que seriam alocados para atender a seguinte seqüência de requisições: PA120K; PB230K; 
PC320K e PD60K (considere o tamanho de 1MB para a memória do usuário e como sugestão monte a ár-
vore de particionamento) 
 
R. PA = 0.....0 (20bits) – 128KB 
PB = 010...0 (20bits) – 256KB 
PC = 10.....0 (20bits) – 512KB 
PD = 001..0 (20bits) – 64KB 
 
 
e. Assumindo que um particionamento por paginação faz uso de um endereço lógico (EL) de 16bits, sendo 11 
bits para deslocamento e 5 para o número da página, pergunta-se: 
i) Quantos e qual o tamanho que deve ter cada página do programa, considerando que cada célula pos-
sui um byte? 
R. Número = 25 = 32; Tamanho = 211 = 2KB 
ii) Qual o tamanho máximo em bytes, que pode ter um processo neste contexto? Mostre como chegou a 
ele. 
R. Processo = 32 * 4 = 128KB 
iii) Como fica o EL de uma instrução cujo endereço relativo seja 4100/10? (pode responder em base 10 ou 
base 2) 
R. Considerando 1K = 1000  EL: 3.100/10 ou 00011.00001100100/2 
 Considerando 1K = 1024  EL: 3.4/10 ou 00011.00000000100/2 
iv) Mostre, com base na PT abaixo, como é feito o mapeamento do endereço lógico abaixo para o ende-
reço absoluto (EL dado em binário e PT em decimal). 
00010 00000000100 
PT 
0 30 
1 21 
2 15 
3 00 
4 09 
: : 
 
 R. EA: 15.4/10 ou 01111. 00000000100/2 
 
2a Questão – Gerenciamento de E/S (100 pontos) 
 
1. Suponha um sistema de disco com as seguintes características: (60) 
 
o Velocidade de rotação - 3000rpm 
o Número de pratos - 10 
o Número de cilindros - 100 
o Setores / trilha - 2000 
o Bytes / setor - 500 
o Tempo de start/stop - 10ms 
o Constante de Hardware - 500s 
 
LmtsaLmt
s
mcmedio
TTTT
r
T
Nr
bT
snmTiXiXiXiXiX
TmissTT
sizeblocksystemfilex
bytesinsizediskM



*2
1
*
*)(0)(1)(2)(3)(4
*
8
 
Calcule: 
a) O tempo médio de busca (seek time) esperado considerando um escalonamento randômico 
 
R. Ts = 50 * 500s + 20ms = 45ms 
 
b) A latência média da unidade de disco 
 
R. A = 1 / 2*r = 60 / (2 * 3000) = 0,01s 
 
c) O tempo médio de transferência, considere que a unidade de acesso seja de 4 setores 
 
R. Tt = 4 * 60 / (2000 * 3000) = 0,04ms 
 
d) O tempo esperado médio de acesso 
EV 
 
R. Ta = 45ms + 0,01s + 0,04ms = 45,04ms 
 
e) O comprimento médio de busca (average seek length – SL) para cada uma das estratégias de escalo-
namento abaixo, dado que as cabeças de leitura e escrita estão posicionadas sobre o cilindro de nú-
mero 10, com movimento do braço na direção ascendente, e que haja a seguinte sequência de pedi-
dos pendentes - 97, 16, 110, 186, 147, 41, 10, 64, 120 e 5, 
i) SSTF 
 
R. 10: 10 – 5 – 16 – 41 – 64 – 97 – 110 – 120 – 147 – 186  186/10 = 18.6 
 
ii) SCAN 
 
R. 10↑: 10 – 16 – 41 – 64 – 97 – 110 – 120 – 147 – 186 – 5  357/10 = 35.7 
 
2. Considere os fluxos de execução abaixo, onde cada um dos blocos, identificados de A a H, representa 
um trecho de fluxo e responda as perguntas que se seguem: (40) 
 
 
 
a) Qual ou quais dos blocos no seu entender exercem ou podem exercer a função de rotina principal? 
 
R. Rotinas Principais: Blocos “A” e “B” 
 
b) Todos os blocos formam uma única unidade de execução? Casopositivo justifique ou, em caso ne-
gativo, enumere os blocos que pertençam a unidades distintas de execução. 
 
R. Não. Unidade 1: A, C, D e G Unidade 2: B, D, E, F e H 
 
c) O que podem representar os blocos C, D, E, F, G e H? 
 
R. D – rotina compartilhada (re-entrante), possivelmente uma DLL 
 C e G – sub-rotinas da unidade 1 de execução 
a 
b 
a b 
c 
 E e F – threads da unidade 2 de execução 
 H – sub-rotina da thread F 
 
d) O que representam as setas “a”, “b” e “c” nos blocos “A”, “B” e “E”? 
 
R. No bloco A – a (chamada de sub-rotina), b (retorno de sub-rotina) 
 No bloco B – a (criação da thread E), b (criação da thread F) 
 No bloco E – c (desvio condicional de execução) 
 
3a Questão – Memória Virtual (100 pontos) 
 
Leia, interprete e responda cada um dos itens a seguir: (a interpretação faz parte da questão) 
 
1. Considere um sistema que utiliza a técnica de Gerência de Memória Virtual por Paginação com páginas 
reais de 512 bytes. O programa a seguir deve ser executado: 
 
Endereço Virtual 510: Programa Prova2; 
Endereço Virtual 511: Var A, B, C: inteira; 
Endereço Virtual 512: A = 1; 
Endereço Virtual 513: B = 1; 
Endereço Virtual 514: C = A + B; 
Endereço Virtual 515: D = 0; 
Endereço Virtual 516: Fim. 
 
No início da execução do programa, o PC/CI recebe o valor (510)10 e a tabela parcial de páginas do processo pos-
sui o seguinte conteúdo: 
 
Entr. na Tab. Páginas Endereço do frame 
0 **** 
1 **** 
2 **** 
3 **** 
4 **** 
5 **** 
6 **** 
 
 
A Lista de Páginas Livres do sistema é composta pelas seguintes páginas reais (a tabela indica o endereço inicial 
do frame): 
 
 Início da 
 Lista ponteiro para a próxima área livre 
512 
4608 
5120 
7680 
 
Considere que: 
 
 A variável A está associada ao endereço virtual (528)10 
 A variável B está associada ao endereço virtual (1032)10 
 A variável C está associada ao endereço virtual (1537)10 
 A variável D está associada ao endereço virtual (2049)10 
 A execução das instruções “Programa Prova2”; “Var A, B, C: inteira” e “Fim” não fazem acesso à me-
mória. 
 Para qualquer instrução, o ciclo de busca é executado em um único acesso à memória principal. 
 O limite de páginas reais (frames) para o processo é igual a 3. 
 Cada processo pode ter até 128 páginas virtuais. 
 A política de substituição de páginas utilizada é a LRU. 
 A tradução da operação de soma é feita da seguinte forma: 
 LOAD Op1  ACC (Op1) 
 Op3 = Op1 + Op2 ADD Op2  R1 (Op2) 
 ACC ACC + R1 
 STORE Op3  (Op3) ACC 
 Onde ACC é o registrador Acumulador e R1 é um registrador de dados auxiliar. 
 
a) Complete a tabela a seguir indicando todas as referências realizadas a endereços de memória nos ciclos de 
busca e de execução do programa. 
 
Instrução Ciclo de 
Busca ou 
Execução 
Endereço 
Virtual Refe-
renciado 
Página 
Virtual 
Deslo-
camento 
Page 
Fault 
(S/N)? 
Houve 
Page in 
(S/N)? 
Página 
que sai 
Bit de 
Modi-
ficação 
Houve 
Page out 
(S/N) ? 
Endereço Real 
Traduzido 
Programa Busca 51010 0 510 S S -- 0 N 512+510=102210
Var Busca 51110 0 511 N N -- 0 N 512+511=102310
A = 1 Busca 51210 1 0 S S -- 0 N 4608+0=460810
A = 1 Execução 52810 1 16 N N -- 1 N 4608+16=462410
B = 1 Busca 51310 1 1 N N -- 1 N 4608+1=460910 
B = 1 Execução 103210 2 8 S S -- 1 N 5120+8=512810 
C = A + B Busca 51410 1 2 N N -- 1 N 4608+2=461010 
LOAD A Execução 52810 1 16 N N -- 1 N 4608+16=462410 
ADD B Execução 103210 2 8 N N -- 1 N 5120+8=512810 
STORE C Execução 153710 3 1 S S 0 1 S 512+1=51310 
D = 0 Busca 51510 1 3 N N -- 1 N 4608+3=461110 
D = 0 Execução 204910 4 1 S S 2 1 S 5120+1=512110 
Fim Busca 51610 1 4 N N -- 1 N 4608+4=461210 
 
 
 
 
 
 
b) Mostre a Lista de Áreas Livres imediatamente antes do ciclo de busca da instrução do endereço virtual 51610. 
 
 Início da 
 Lista ponteiro para a próxima área livre 
7680 
 
c) Mostre a Tabela de Páginas Virtuais imediatamente antes do ciclo de busca da instrução do endereço virtual 
51610. 
 
Entr. na Tab. Páginas Endereço do frame 
0 **** 
1 4608 
2 **** 
3 512 
4 5120 
5 **** 
6 **** 
 
 
"O melhor fiscal do ser humano é sua própria consciência" 
 
 
CONCENTRE-SE E FAÇA UMA BOA PROVA!