Baixe o app para aproveitar ainda mais
Prévia do material em texto
Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition, Gerenciamento de Memória Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition, Capítulo 8: Memória Principal Operating System Concepts – 8th Edition 3 Silberschatz, Galvin and Gagne ©2009 Sumário • Conceitos básicos relacionados à memória • Swapping • Alocação contígua • Paginação • Segmentação Operating System Concepts – 8th Edition 4 Silberschatz, Galvin and Gagne ©2009 Conceitos básicos • Programas precisam ser carregados na memória e associados a um processo para poderem ser executados • Fila de entrada: processos que estejam no disco esperando para serem carregados na mem. • Há vários passos a serem seguidos antes dos processos poderem executar Operating System Concepts – 8th Edition 5 Silberschatz, Galvin and Gagne ©2009 Vinculação de endereços (ligação) • Programas em linguagem de alto nível (quase) nunca referenciam endereços específicos de memória: ° ex.: C define variáveis globais, locais e dinâmicas, mas não define endereços específicos para elas ° Dependendo da linguagem, do S.O. e do HW, há diversos momentos onde a associação entre os comandos e a memória pode acontecer: • Tempo de compilação • Tempo de carga • Tempo de execução Operating System Concepts – 8th Edition 6 Silberschatz, Galvin and Gagne ©2009 Vinculação de endereços (ligação) • Tempo de compilação ° Se houver uma definição fixa sobre localização o compilador pode gerar endereços diretamente ° Se for preciso mudar os endereços, é preciso recompilar o programa ° Comum para elementos com endereços definidos pelo HW (ex., vetor de interrupções) ° Ocorre também na vinculação de símbolos definidos e acessados em módulos diferentes de um programa Operating System Concepts – 8th Edition 7 Silberschatz, Galvin and Gagne ©2009 Vinculação de endereços (ligação) • Tempo de carga: ° Compilador gera anotações sobre acessos relacionados a certos endereços ° O carregador (loader) lê essas anotações e altera o código do programa carregado para inserir os endereços adequados a cada caso ° Endereços ganham valor a partir do momento que sabe-se a posição inicial do programa Operating System Concepts – 8th Edition 8 Silberschatz, Galvin and Gagne ©2009 Vinculação de endereços (ligação) • Tempo de execução: ° Em alguns casos a localização de um processo na memória pode mudar em tempo de execução ° Nesse caso o HW deve prover suporte especial ° É preciso refazer vínculos eficientemente • Mapas de endereços • Tabelas de relação • Endereçamento relativo Operating System Concepts – 8th Edition 10 Silberschatz, Galvin and Gagne ©2009 Endereços lógicos x físicos • End. lógico: gerado pela CPU (virtual, posição relativa) • End. físico: visto pela unidade de memória (real) Operating System Concepts – 8th Edition 18 Silberschatz, Galvin and Gagne ©2009 Swapping • Processos podem ser transferidos entre memória principal e secundária (ex.: processos suspensos) • Exigem relocação ao serem recarregados • Maior overhead é o tempo de transferência Processo P4 (700K) Processo P6 (900K) Sistema Operacional P5 P4 P3 0 400K 1000K 2000K 2300K 2560K 1700K 900K (1) Swap out (2) Swap in Operating System Concepts – 8th Edition 19 Silberschatz, Galvin and Gagne ©2009 Alocação contígua • Forma simples de utilização da memória, duas partições: → (1) S.O. residente (memória baixa, vetor interrupções) ; (2) Processo de usuário • Alocação contígua: cada processo ocupa um bloco único da memória física • É essencial que seja possível fazer relocação dinâmica e proteção entre as áreas de memória: Operating System Concepts – 8th Edition 22 Silberschatz, Galvin and Gagne ©2009 Alocação contígua com múltiplos processos • Cada processo ocupa um bloco da memória • Ao terminar, bloco é liberado (buraco) • Processos que chegam ocupam buracos • S.O. deve controlar partições e buracos • Relocação por tabela ou registrador base Sistema Operacional P1 P2 P3 0 400K 1000K 2000K 2300K 2560K Sistema Operacional P1 P3 0 400K 1000K 2000K 2300K 2560K Sistema Operacional P1 P4 P3 0 400K 1000K 2000K 2300K 2560K 1700K Sistema Operacional P4 P3 0 400K 1000K 2000K 2300K 2560K 1700K Sistema Operacional P5 P4 P3 0 400K 1000K 2000K 2300K 2560K 1700K 900K P2 termina P1 termina P4 iniciado P5 iniciado Operating System Concepts – 8th Edition 23 Silberschatz, Galvin and Gagne ©2009 Problema de alocação dinâmica: onde colocar um processo novo? • First-fit (primeiro apto): primeiro que couber • Best-fit (mais apto): o de tamanho mais próximo • Worst-fit (menos apto): sempre o maior buraco → First-fit e best-fit se saem melhor que worst-fit em termos de velocidade e utilização do espaço. Operating System Concepts – 8th Edition 24 Silberschatz, Galvin and Gagne ©2009 Fragmentação • Quebra do espaço em frações não utilizáveis • Fragmentação externa: ° Memória não utilizada dividida em muitos buracos, pequenos demais para serem úteis • Fragmentação interna: ° Limitações na forma como blocos são alocados podem gerar buracos dentro do bloco ° ex., alocação apenas em blocos de 4 KiB Operating System Concepts – 8th Edition 25 Silberschatz, Galvin and Gagne ©2009 Compactação • Solução para a fragmentação externa ° Mover blocos ocupados para perto uns dos outros ° Agrupar os buracos em um único bloco maior ° Só é possível com relocação dinâmica Outra forma de lidar com fragmentação externa é permitir alocação não contígua (paginação ou segmentação) Operating System Concepts – 8th Edition 26 Silberschatz, Galvin and Gagne ©2009 Segmentação • Divisão da memória do processo em unidades • Baseado na visão lógica do usuário/programador • Um programa é uma coleção de segmentos de memória independentes (código, dados, pilha, ...) • Cada um pode ser acessado independentemente ° Como se fossem diferentes dimensões • Tornou-se “popular” ao ser adotada pela Intel Operating System Concepts – 8th Edition 27 Silberschatz, Galvin and Gagne ©2009 Segmentação • Mesmos problemas da alocação contígua! Pilha de execução Heap (alocação dinâmica) Dados (variáveis globais) Código (instruções) 0 12K 8K 4K 16K 20K Não segmentado Código (instruções) Segmento 1 Dados Segmento 2 Heap Segmento 3 Pilha Segmento 4 Visão lógica Código (instruções) Pilha Dados Heap Visão física Operating System Concepts – 8th Edition 30 Silberschatz, Galvin and Gagne ©2009 Segmentação: exemplo Operating System Concepts – 8th Edition 31 Silberschatz, Galvin and Gagne ©2009 Segmentos compartilhados Operating System Concepts – 8th Edition 32 Silberschatz, Galvin and Gagne ©2009 Paginação (paging) • Memória (lógica/física) é dividida em blocos de tamanho fixo – potências de 2: p.ex., 4 KiB • Blocos lógicos (páginas) são mapeadas em blocos físicos (quadros) pelo HW • Endereços lógicos contíguos podem estar em páginas diferentes, em quadros não contíguos • Quadros vazios são gerenciados • Programa de n páginas requer n quadros (qq) • Fragmentação interna (a última página) Operating System Concepts – 8th Edition 34 Silberschatz, Galvin and Gagne ©2009 Paginação Página 0 Página 1 Página 3 Página 2 Espaço de endereçamento Página 0 Página 1 Página 3 Página 2 0 1 2 3 4 5 6 7 Memória física 0 1 2 3 1 4 3 7 Tabela de páginas OperatingSystem Concepts – 8th Edition 36 Silberschatz, Galvin and Gagne ©2009 Gerência de quadros livres Antes da alocação Depois da alocação Operating System Concepts – 8th Edition 38 Silberschatz, Galvin and Gagne ©2009 Compartilhamento de páginas Operating System Concepts – 8th Edition 45 Silberschatz, Galvin and Gagne ©2009 Tabelas hierárquicas (multinível) • Páginas não são muito grandes (4 KiB → 12 bits) • Se o resto do endereço identificar a página ° Com endereços de 32 bits, pode haver mais de 1 milhão de páginas (20 Bits) ° Tabela gigantesca (4 MiB) teria que ser alocada em posições contíguas da memória! • Solução: quebrar o endereço em várias tabelas ° ex.: para 32 bits, dois níveis de tabelas, cada um com 10 bits Operating System Concepts – 8th Edition 47 Silberschatz, Galvin and Gagne ©2009 Processo de tradução com 2 níveis Página nível 1 Página nível 2 Offset Endereço lógico (32 bits) Tabela nível 1 Endereços base Tabela nível 1 Memória física 12 bits10 bits10 bits Operating System Concepts – 8th Edition 48 Silberschatz, Galvin and Gagne ©2009 Tabelas de páginas por hash • Comuns em endereços com mais de 32 bits • Tabelas de mais níveis se tornam proibitivas • Identificador de página gera um valor de hash ° Tabela de hash com colisão Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition, Capítulo 9: Memória Virtual Operating System Concepts – 8th Edition 55 Silberschatz, Galvin and Gagne ©2009 Sumário • Princípios de paginação sob demanda • Impacto da paginação sob demanda na criação de processos • Algoritmos de substituição de páginas • Alocação de quadros • Thrashing Operating System Concepts – 8th Edition 56 Silberschatz, Galvin and Gagne ©2009 Princípios gerais • Memória física: memória segmentada/paginada já fizeram a separação entre endereço lógico e físico ° O objetivo é manter muitos processos em memória para permitir a multiprogramação • Vamos além! Estendendo a funcionalidade da tabela de páginas... ° nem todas as páginas precisam estar na memória física o tempo todo, apenas a parte do programa em execução • ex.: códigos para manipular condições de erros raramente usados • Memória virtual: permite a execução de processos que não estão completamente em memória (física) Operating System Concepts – 8th Edition 57 Silberschatz, Galvin and Gagne ©2009 Memória Virtual > Memória Física • Espaço de endereços lógicos pode ser muito maior que o físico → os programas podem ser maiores que a memória física! • A memória virtual torna a tarefa de programar mais fácil: ° o programador não precisa preocupar com a quantidade de memória física disponível Operating System Concepts – 8th Edition 58 Silberschatz, Galvin and Gagne ©2009 Paginação por demanda • Tipicamente, carregar todo o programa pra memória pode trazer código com opções que o usuário não vá escolher • Ideia alternativa: trazer as páginas para a memória física apenas quando necessárias (“paginação por demanda”) ° Páginas são carregadas apenas quando necessárias na execução do programa ° Páginas que jamais são acessadas jamais são carregadas na memória física! • Benefícios do uso de Memória Virtual: ° Menos operações de E/S => reduz swap de programas ° Menor área de memória física ocupada => mais programas ° Mais processos/usuários atendidos => melhor utilização da CPU Operating System Concepts – 8th Edition 59 Silberschatz, Galvin and Gagne ©2009 Extensão do princípio de swap • Um permutador faz swap de processos inteiros entre memórias ° Processo era visto como um grande espaço de endereçamento contíguo • Um paginador faz swap das páginas individuais (necessárias) do proc ° Processo agora é visto como uma sequência de páginas Operating System Concepts – 8th Edition 60 Silberschatz, Galvin and Gagne ©2009 Suporte de hardware • O bit válido/inválido é usado para controlar a presença (ou não) da página (lógica) na memória física (principal) ° Válida: página disponível em memória ° Inválida: página está em disco Operating System Concepts – 8th Edition 61 Silberschatz, Galvin and Gagne ©2009 Manipulação de erro de página • Bit inválido para uma página desejada → gera trap • S.O. testa uma tabela interna do processo (no PCB) ° Referência inválida → aborta o processo (acesso ilegal) ° Referência válida • Localiza no disco a página ausente • Localiza um quadro vazio (na lista de quadros livres) • Carrega a página desejada do disco para o quadro na mem. • Atualiza a tabela de páginas indicando o bit como válido • Reinicia a instrução interrompida (pela trap) • O processo pode acessar a página, já na memória Operating System Concepts – 8th Edition 62 Silberschatz, Galvin and Gagne ©2009 Erro de página (page fault) Operating System Concepts – 8th Edition 65 Silberschatz, Galvin and Gagne ©2009 Mem. Virtual: benefícios para a gerência de processos • Redução do custo de criação de processos ° fork() cria processo filho como duplicata do pai ° tradicionalmente, copia o espaço de end. e duplica as páginas ° alternativamente, pai e filho compartilham as mesmas páginas • págs. são marcadas como páginas de cópia-após-gravação • se um processo for gravar, será criada uma cópia da pág. • Acesso a arquivos mapeados em memória ° tratar E/S de arquivo como acesso de rotina à memória ° parte do end. virtual pode ser associado a um arquivo ° pode levar a melhorias significativas de desempenho de E/S Operating System Concepts – 8th Edition 67 Silberschatz, Galvin and Gagne ©2009 Arquivos mapeados em memória • Memória virtual: mapeamento do endereço lógico do processo a uma área em disco ° Normalmente, o sentido é memória → disco • No Unix, com o mmap(), pode-se fazer o oposto: ° Conteúdo do disco (arquivo) → espaço de memória • Simplifica o acesso a arquivos de dados ° Podem ser tratados como vetores na memória • Permite que processos compartilhem arquivos Operating System Concepts – 8th Edition 69 Silberschatz, Galvin and Gagne ©2009 Superalocação de memória • Processo em execução gera erro de página → S.O. determina onde ela reside no disco ° E se não houver um quadro vazio? (toda mem. em uso) ° Há necessidade de substituição de páginas Operating System Concepts – 8th Edition 71 Silberschatz, Galvin and Gagne ©2009 Superalocação de memória • Quando não houver um quadro vazio, o S.O. pode: ° Encerrar o processo do usuário • Péssima escolha, pois vai contra o objetivo de otimizar a utilização ° Remover um processo da memória • Boa escolha, mas como remove todos os seus quadros, reduz o nível de multiprogramação ° Realizar a substituição de páginas • Solução mais comum Operating System Concepts – 8th Edition 72 Silberschatz, Galvin and Gagne ©2009 Substituição de páginas • Substituição/reposição de páginas ° Se nenhum quadro estiver livre ° Encontre uma página que não esteja em uso ° Libere o quadro dela • Grave o conteúdo do quadro no espaço de permuta • Modifique a tabela de páginas invalidando a página vítima ° OBS.: a página retirada pode vir a ser acessada de novo :( Operating System Concepts – 8th Edition 74 Silberschatz, Galvin and Gagne ©2009 Substituição de páginas • Melhoria na seleção da página vítima ° Tabela de páginas inclui bit extra para auxiliar no processo de escolha de candidatos ° Bit de modificação (ou bit poluído) • Bit ligado: página foi modificada desde que foi lida no disco, devemos gravar a página no disco, custo maior • Bit desligado: página não modificada, não precisa gravar no disco, pode ser descartada a um custo menor • Substituição de páginas é essencial para a paginação por demanda ° Completa a separação entrememória física e lógica ° Tamanho do espaço de end. lógico não é mais limitado pela mem. física ° Mem. virtual enorme oferecida ao programador numa mem. física menor Operating System Concepts – 8th Edition 75 Silberschatz, Galvin and Gagne ©2009 Relação entre falhas e nº de quadros disponíveis • Existem muitos algoritmos de substituição de páginas nos S.O. ° Prefere-se aquele com a taxa de erros de página mais baixa ° Em geral, com a curva abaixo: + quadros → - erros • OBS.: aumentando a memória física (RAM), aumenta-se os quadros Operating System Concepts – 8th Edition 88 Silberschatz, Galvin and Gagne ©2009 Alocação de quadros para cada processo • Como alocar a quantidade fixa de memória livre entre os vários processos? ° Cada processo precisa de um mínimo de páginas • Dois esquemas principais: ° Alocação fixa ° Alocação por prioridade Operating System Concepts – 8th Edition 89 Silberschatz, Galvin and Gagne ©2009 Alocação fixa • Igual: todos os processos recebem o mesmo nº de quadros na memória física • Proporcional: função do tamanho do processo si= size of process p i S=∑ si m= total number of frames ai= allocation for pi= si S ×m m=64 si=10 s2=127 a1= 10 137 ×64≈5 a2= 127 137 ×64≈59 Operating System Concepts – 8th Edition 90 Silberschatz, Galvin and Gagne ©2009 Substituição global x local • Substituição Global: ° Quadro a ser substituído escolhida do total de quadros ° Mesmo que o quadro esteja alocado a outro processo ° Um processo pode “tomar” quadros do outro • → um processo não controla sua taxa de erros de página, dependente do comportamento de paginação de outros proc. • Substituição Local ° Quadro tem que ser do próprio processo que gerou o erro ° Nº de quadros de cada processo não muda • → conj. de págs. em mem. somente é afetado pela paginação do processo ° Paginação local pode “travar” um processo (poderia usar págs. menos utilizadas de outros procs.), já o global provê maior vazão de procs. Operating System Concepts – 8th Edition 91 Silberschatz, Galvin and Gagne ©2009 Thrashing (atividade improdutiva) • Quando a utilização de CPU diminui, S.O. aumenta a multiprogramação • Mas, se processos não têm páginas “suficientes” ° Erros de página aumentam ° Utilização de CPU diminui ° S.O.: preciso aumentar a multiprog. ° Outro proc. é trazido para a mem. ° Demanda por quadros aumenta ° Erros de página aumentam • Thrashing → processos estão ocupados apenas fazendo swap de páginas e aguardando na fila do paginador Operating System Concepts – 8th Edition 92 Silberschatz, Galvin and Gagne ©2009 Localidade de referência e Thrashing • Por que memória virtual funciona? → localidade de referência ° Localidade é o conjunto de páginas que são ativamente usadas juntas ° Processo migram entre áreas de acesso (estruturas do programa e dos dados) ° Áreas podem se sobrepor ao longo do tempo (ex.: variáveis locais e globais) • Localidade em padrão de acesso ° Uma função define uma localidade e referências de memória feitas para • Chamada da função • Variáveis locais e globais • Por que thrashing ocorre? ° ∑ localidades > memória total Operating System Concepts – 8th Edition 101 Silberschatz, Galvin and Gagne ©2009 Impacto do padrão de acesso int A[][] = new int[1024][1024]; // linha = uma pág.; memória < 1024 quadros 1024 x 1024 page faults 1024 page faults for (j = 0; j < A.length; j++) for (i = 0; i < A.length; i++) A[i,j] = 0; for (i = 0; i < A.length; i++) for (j = 0; j < A.length; j++) A[i,j] = 0; Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition, Fim dos Capítulos 8 e 9 Slide 1 Slide 2 Slide 3 Background Binding of Instructions and Data to Memory Slide 6 Slide 7 Slide 8 Logical vs. Physical Address Space Slide 18 Contiguous Allocation Contiguous Allocation (Cont.) Dynamic Storage-Allocation Problem Fragmentation Slide 25 Slide 26 Slide 27 Slide 30 Slide 31 Paging Slide 34 Free Frames Shared Pages Example Hierarchical Page Tables Slide 47 Hashed Page Tables Slide 54 Chapter 6: CPU Scheduling Chapter 10: Virtual Memory Virtual Memory That is Larger Than Physical Memory Demand Paging Transfer of a Paged Memory to Contiguous Disk Space Page Table When Some Pages Are Not in Main Memory Page Fault Steps in Handling a Page Fault Process Creation Memory-Mapped Files What happens if there is no free frame? Slide 71 Slide 72 Page Replacement Graph of Page Faults Versus The Number of Frames Allocation of Frames Fixed Allocation Global vs. Local Allocation Thrashing Thrashing Slide 101 Slide 103
Compartilhar