Exerc Mem Resp

Sistemas Operacionais – Prof. Rafael R. Obelheiro – Semestre: 2008.1

Lista de Exerc´ıcios 5 — Gerˆ encia de Mem´ oria — Respostas 1. A mem´oria cont´em o SO (em uma parti¸c˜ao de 64K) e 9 processos, cada um em uma parti¸c˜ ao de 16K. Portanto, a mem´ oria alocada ´e MA = 64 + 9 × 16 = 208K. A mem´oria efetivamente utilizada ´e dada pela soma dos tamanhos do SO e dos processos: MU = 48 + 10 + 4 + 7 + 9 + 12 + 13 + 5 + 16 + 6 = 130K. A mem´oria desperdi¸cada ´e a diferen¸ca entre a alocada e a utilizada, ou MD = MA − MU = 208 − 130 = 78K. Em termos porcentuais, isso representa MD% = MD/MA = 78/208 = 37,5% da mem´oria alocada. Para obter a fragmenta¸c˜ ao m´edia, ´e necess´ario determinar a fragmenta¸c˜ao em cada uma das 10 parti¸c˜oes utilizadas e calcular a m´edia dos valores: FSO = F4 =

7 16

F8 = 0

F¯ =

16 64

= 0,25

F1 =

6 16

= 0,375

F2 =

12 16

= 0,75

F3 =

9 16

= 0,5625

= 0,4375

F5 =

4 16

= 0,25

F6 =

3 16

= 0,1875

F7 =

11 16

= 0,6875

F9 =

10 16

= 0,625

P

0,25 + 0,375 + 0,75 + 0,5625 + 0,4375 + 0,25 + 0,1875 + 0,6875 + 0,625 Fi = = n 10 = 0,4125 = 41,25%

2. As lacunas ocupadas pelas requisi¸c˜ oes ser˜ao as seguintes: (a) 10K (sobram 5K), 20K (sobram 10K), 10K (sobram 4K) (b) 7K (sobram 2K), 10K, 9K (sobram 3K) (c) 20K (sobram 15K), 18K (sobram 8K), 15K (sobram 9K) (d) 10K (sobram 5K), 20K (sobram 10K), 10K (sobram 4K) 3. As lacunas ocupadas pelas requisi¸c˜ oes ser˜ao as seguintes: (a) 20K (sobram 5K), 10K (sobram 6K), 18K (sobram 10K) (b) 18K (sobram 3K), 4K, 9K (sobra 1K) (c) 20K (sobram 5K), 18K (sobram 14K), 14K (sobram 6K) (d) 20K (sobram 5K), 5K (sobra 1K), 18K (sobram 10K) 4. (a) EEL = 216 = 65.536 = 64K (b) EEF = 220 = 1.048.576 = 1M (c) 20 bits (d) Dada uma p´ agina de 1K= 210 bytes, a tabela de p´aginas possui 216 /210 = 64 entradas. 5. (a) mem´ oria f´ısica = 224 = 16M (b) maior programa = 220 = 1M (c) Dada uma p´ agina de 1K= 210 bytes, a tabela de p´aginas possui 220 /210 = 1.024 entradas. (d) Cada entrada na tabela de p´ aginas ocupa 24 + 2 = 26 bits. Portanto, a tabela de p´aginas ocupa 1.024 × 26 = 26.624 bits. 6. (a) Para representar 16 segmentos, s˜ao necess´arios log2 16 = 4 bits para o n´ umero de segmento. (b) Cada segmento possui at´e 64K/512 = 128 p´aginas. Portanto, s˜ao necess´arios log2 128 = 7 bits para o n´ umero de p´ agina l´ ogica. (c) Como cada p´ agina tem 512 bytes, s˜ao necess´arios log2 512 = 9 bits de deslocamento.

(d) O endere¸co l´ ogico ´e formado por n´ umero de segmento, n´ umero de p´agina l´ogica e deslocamento, o que d´ a um total de 4 + 7 + 9 = 20 bits. 7.

• First-fit: 500K (sobram 288K), 600K (sobram 183K), 288K (sobram 176K), n˜ao cabe • Best-fit: 300K (sobram 88K), 500K (sobram 83K), 200K (sobram 88K), 600K (sobram 174K) • Worst-fit: 600K (sobram 388K), 500K (sobram 83K), 388K (sobram 276K), n˜ao cabe Best-fit ´e o mais eficiente neste caso, pois ´e o u ´nico que consegue alocar todos os processos.

8. (a) Como s˜ ao necess´ arios dois acessos `a mem´oria (uma `a tabela de p´aginas e outro `a p´ agina f´ısica), o tempo de acesso ´e de 200 + 200 = 400 ns. (b) h = 0,75 tac = h · tmem + (1 − h) · 2tmem = 0,75 · 200 + 0,25 · 400 = 250 ns 9. A f´ormula usada para obter o endere¸co f´ısico ´e EL = BASE + EF. Representando os endere¸cos solicitados por letras de (a) a (e), tem-se: (a) EF = 219 + 430 = 649 (b) EF = 2300 + 10 = 2310 (c) erro (EL > limite) (d) EF = 1327 + 400 = 1727 (e) erro (EL > limite) j k endere¸co 10. O n´ umero de p´ agina ´e dado por p = tamanho p´ agina . O deslocamento ´e dado por d = endere¸co − (p × tamanho p´agina). Para p´aginas de 4 KB, os pares (p´ agina, deslocamento) s˜ao (4, 3616), (8, 0) e (14, 2656). Para p´aginas de 8 KB, os pares s˜ ao (2, 3616), (4, 0) e (7, 2656). 11. A tabela de p´ aginas cont´em 232 /213 = 524.488 entradas. O carregamento da tabela de p´aginas leva 52 ms. Se um processo recebe 100 ms, isso corresponde a 52 ms para carregar a tabela de p´aginas e 48 ms para executar. Logo, 52% do tempo do processo ´e gasto carregando a tabela de p´aginas. 12. 20 bits s˜ao usados para o n´ umero de p´agina virtual, e restam 12 para o deslocamento, o que d´ a p´aginas de 212 = 4 KB. Com 20 bits para o n´ umero de p´agina existem 220 p´aginas. 13. Para pagina¸c˜ ao em um n´ıvel, s˜ ao necess´arias 220 = 1M entradas. Para pagina¸c˜ao em dois n´ıveis, a tabela de p´ aginas principal possui 210 = 1K entradas que apontam, cada uma, para uma tabela de p´aginas de segundo n´ıvel. Apenas duas dessas tabelas s˜ao usadas (uma para c´odigo+dados e outra para pilha), cada uma tendo tamb´em 210 = 1K entradas. Portanto, no total s˜ao necess´ arias 3 × 210 = 3072 entradas. 14. O tempo de acesso ´e dado por tac = h · ttlb + (1 − h)tmem . Usando ttlb = 1 ns e tmem = 5 ns e fazendo tac = 2 ns, tem-se: 2 = h + (1 − h)5 2 = h + 5 − 5h h = 0,75 Ou seja, a taxa de acerto necess´ aria ´e de 75%.

2

15. Suponha um sistema com 16 KB de mem´oria que utiliza pagina¸c˜ao, com p´aginas de 1 KB. Os processos podem ter at´e 8 KB de mem´oria. Em um dado instante, o sistema possui a seguinte aloca¸c˜ao de mem´ oria: 0

Mem F´ısica P22

Processo 1 P11 P12 P13 P14 P15 P16

P15 P11 P24 P16 P23 P12

Processo 2 P21 P22 P23 P24

P13

P21 P14 16383

Determine: (a) As tabelas de p´ aginas dos processos 1 e 2 (b) Os endere¸cos f´ısicos correspondentes aos seguintes endere¸cos l´ogicos: P1: 512, 1023, 1024, 2000, 3100, 4000, 5200, 6000 P2: 512, 1023, 1024, 2000, 3100, 4000 (c) O tempo m´edio de acesso ` a mem´oria para os processos 1 e 2, supondo que: • • • • •

exista uma TLB com duas entradas; o tempo de consulta ` a TLB ´e de 1 ns; o tempo de acesso ` a mem´ oria ´e de 50 ns; os acessos ` a mem´ oria s˜ ao efetuados na seq¨ uˆencia dada no item (b); a tabela de p´ aginas ´e armazenada na mem´oria.

3

RESPOSTAS: (a)

Processo 1 Processo 2 Frame V Frame V 0 4096 1 0 14336 1 1 8192 1 1 1024 1 2 11264 1 2 7168 1 3 15360 1 3 5120 1 4 3072 1 4 0 5 6144 1 5 0 6 0 6 0 7 0 7 0 Os n´ umeros ` a esquerda representam o n´ umero de p´agina l´ogica, e a coluna V indica o bit de v´ alido de cada entrada.

(b) P1: 4608, 5119, 8192, 9168,15388, 16288, 6224, 7024 P2: 14848, 15359, 1024, 2000, 5148, 6048 (c) Os tempos de acesso s˜ ao de 51 ns (em caso de acerto na TLB) e 101 ns (em caso de erro). Tanto para P1 como para P2 s˜ ao feitos pares de acessos consecutivos a uma mesma p´agina, o que d´ a um erro e um acerto na TLB a cada dois acessos. Portanto, o tempo m´edio de acesso, em ambos os casos, ´e de (101 + 51)/2 = 76 ns.

4