Paginação e Segmentação -2023-2

INE5611 - Sistemas Operacionais Paginação e Segmentação Prof. Eduardo Camilo Inacio, Dr. eduardo.camilo@ufsc.br Universidade Federal de Santa Catarina Departamento de Informática e Estatística Sumário 1 Introdução 2 Paginação 3 Segmentação 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 1 / 52 Aviso Legal O conteúdo apresentado nestes slides foi baseado parcialmente nos livros abaixo, assim como nos seus respectivos materiais de apoio, quando disponível: OLIVEIRA, R. S.; CARISSIMI, A. S.; TOSCANI, S. S. Sistemas Operacionais. 4. ed. Porto Alegre: Bookman, 2010. 374 p. ISBN 978-85-7780-521-1. TANENBAUM, A. S.; BOS, H. Modern Operating Systems. 4. ed. [S. l.]: Pearson Education, 2015. 1136 p. ISBN 978-0-13-359162-0. SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Operating System Concepts. 9. ed. [S. l.]: Wiley, 2012. 976 p. ISBN 978-1-118-06333-0. Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 2 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 2 / 52 Introdução Alocação particionada de memória apresenta alguns problemas Particionamento estático (partições fixas) gera muita perda de memória Devido à fragmentação interna e externa Não é mais utilizado na prática Particionamento dinâmico (partições variáveis) é mais flexível Desperdício de memória por fragmentação externa ainda é grave Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 3 / 52 Introdução Origem da Fragmentação Externa Programas precisam ocupar uma área contígua de memória. Solução Remover esta restrição, permitindo que programas ocupem áreas não contíguas da memória. Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 4 / 52 Introdução Origem da Fragmentação Externa Programas precisam ocupar uma área contígua de memória. Solução Remover esta restrição, permitindo que programas ocupem áreas não contíguas da memória. Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 4 / 52 Introdução Métodos de alocação não contígua exploram a existência de um espaço de endereçamento lógico e de um espaço de endereçamento físico Espaço de endereçamento lógico, “visto” pelo processo, continua sendo contíguo Espaço de endereçamento físico não precisa ser contíguo Requer um mecanismo para mapeamento do espaço lógico para o espaço físico Principais métodos: Paginação Segmentação Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 5 / 52 Sumário 1 Introdução 2 Paginação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Páginas Paginação Multinível Considerações sobre Paginação 3 Segmentação 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 5 / 52 Paginação Alocação Contígua Não contígua Simples Particionada Estática Dinâmica Paginação Segmentação Segmentação paginada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 6 / 52 Paginação Paginação é um método de alocação de memória que define uma abstração de páginas e quadros de tamanho fixo, assim como o mapeamento entre eles, para permitir que o espaço de endereçamento físico de um processo seja não contíguo. Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 7 / 52 Paginação Processo “enxerga” um espaço de endereçamento lógico contíguo Memória lógica é dividida em blocos de tamanho fixo chamados de páginas Memória física é dividida em blocos de tamanho fixo chamados de quadros Mesmo tamanho da página Memória Lógica Memória Física A B C D E F G H 000 001 010 011 100 110 111 101 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 8 / 52 Paginação Processo “enxerga” um espaço de endereçamento lógico contíguo Memória lógica é dividida em blocos de tamanho fixo chamados de páginas Memória física é dividida em blocos de tamanho fixo chamados de quadros Mesmo tamanho da página Memória Lógica Memória Física A B C D E F G H 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 Página 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 8 / 52 Paginação Processo “enxerga” um espaço de endereçamento lógico contíguo Memória lógica é dividida em blocos de tamanho fixo chamados de páginas Memória física é dividida em blocos de tamanho fixo chamados de quadros Mesmo tamanho da página Memória Lógica Memória Física A B C D E F G H 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 Quadro 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 8 / 52 Paginação Para executar um processo com n páginas, basta encontrar n quadros livres Páginas podem ser carregadas em qualquer quadro livre da memória Quadros não precisam ser contíguos Ordem dos quadros não precisa ser a mesma das páginas Elimina a fragmentação externa e reduz a fragmentação interna Necessidade de traduzir endereços lógicos (páginas) para endereços físicos (quadros) Memória Lógica Memória Física A B C D E F G H 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 9 / 52 Paginação Para executar um processo com n páginas, basta encontrar n quadros livres Páginas podem ser carregadas em qualquer quadro livre da memória Quadros não precisam ser contíguos Ordem dos quadros não precisa ser a mesma das páginas Elimina a fragmentação externa e reduz a fragmentação interna Necessidade de traduzir endereços lógicos (páginas) para endereços físicos (quadros) Memória Lógica Memória Física A B C D E F G H G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 9 / 52 Paginação Para executar um processo com n páginas, basta encontrar n quadros livres Páginas podem ser carregadas em qualquer quadro livre da memória Quadros não precisam ser contíguos Ordem dos quadros não precisa ser a mesma das páginas Elimina a fragmentação externa e reduz a fragmentação interna Necessidade de traduzir endereços lógicos (páginas) para endereços físicos (quadros) Memória Lógica Memória Física A B C D E F G H G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 9 / 52 Paginação Para executar um processo com n páginas, basta encontrar n quadros livres Páginas podem ser carregadas em qualquer quadro livre da memória Quadros não precisam ser contíguos Ordem dos quadros não precisa ser a mesma das páginas Elimina a fragmentação externa e reduz a fragmentação interna Necessidade de traduzir endereços lógicos (páginas) para endereços físicos (quadros) Memória Lógica Memória Física A B C D E F G H G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 9 / 52 Sumário 1 Introdução 2 Paginação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Páginas Paginação Multinível Considerações sobre Paginação 3 Segmentação 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 9 / 52 Tradução de Endereço Lógico para Endereço Físico Memória Lógica A B C D E F G H 000 001 010 011 100 110 111 101 100 bits Memória lógica com m posições, necessita de endereços lógicos com ao menos log2 m bits Número de páginas é o quociente do tamanho da memória lógica m pelo tamanho da página k, isto é, m/k Para identificar uma página, são necessários log2(m/k) bits Para uma página de tamanho k posições, são necessários log2 k bits de deslocamento Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 10 / 52 Tradução de Endereço Lógico para Endereço Físico Memória Lógica A B C D E F G H páginas 000 001 010 011 100 110 111 101 Memória lógica com m posições, necessita de endereços lógicos com ao menos log2 m bits Número de páginas é o quociente do tamanho da memória lógica m pelo tamanho da página k, isto é, m/k Para identificar uma página, são necessários log2(m/k) bits Para uma página de tamanho k posições, são necessários log2 k bits de deslocamento Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 10 / 52 Tradução de Endereço Lógico para Endereço Físico 100 Memória Lógica A B C D E F G H bits 000 001 010 011 100 110 111 101 Memória lógica com m posições, necessita de endereços lógicos com ao menos log2 m bits Número de páginas é o quociente do tamanho da memória lógica m pelo tamanho da página k, isto é, m/k Para identificar uma página, são necessários log2(m/k) bits Para uma página de tamanho k posições, são necessários log2 k bits de deslocamento Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 10 / 52 Tradução de Endereço Lógico para Endereço Físico 11 Memória Lógica A B C D E F G H 10 01 00 Número da Página 100 bits 000 001 010 011 100 110 111 101 Memória lógica com m posições, necessita de endereços lógicos com ao menos log2 m bits Número de páginas é o quociente do tamanho da memória lógica m pelo tamanho da página k, isto é, m/k Para identificar uma página, são necessários log2(m/k) bits Para uma página de tamanho k posições, são necessários log2 k bits de deslocamento Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 10 / 52 Tradução de Endereço Lógico para Endereço Físico 100 Memória Lógica A B C D E F G H bit 000 001 010 011 100 110 111 101 Memória lógica com m posições, necessita de endereços lógicos com ao menos log2 m bits Número de páginas é o quociente do tamanho da memória lógica m pelo tamanho da página k, isto é, m/k Para identificar uma página, são necessários log2(m/k) bits Para uma página de tamanho k posições, são necessários log2 k bits de deslocamento Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 10 / 52 Tradução de Endereço Lógico para Endereço Físico Endereço lógico é dividido em duas partes Número (identificador) da página (p) Deslocamento dentro de uma página (d) Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 11 / 52 Tradução de Endereço Lógico para Endereço Físico Exemplo Memória lógica (tamanho do processo) de 256 KB 256 KB = 218 B → endereço lógico com 18 bits Páginas de 4 KB 256 4 = 64 páginas = 26 páginas → p = 6 bits 4 KB = 212 B → d = 12 bits 18 bits 6 bits 12 bits Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 12 / 52 Tradução de Endereço Lógico para Endereço Físico Mesma abordagem é utilizada na memória física Memória física com n posições, necessita de endereços físicos com ao menos log2 n bits Endereço físico é dividido em duas partes Número (identificador) do quadro (f) Deslocamento dentro de um quadro (d) Número de quadros é o quociente do tamanho da memória física n pelo tamanho do quadro k, isto é, n/k Tamanho do quadro é igual ao tamanho da página Para identificar um quadro, são necessários log2(n/k) bits Para um quadro de tamanho k posições, são necessários log2 k bits de deslocamento Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 13 / 52 Tradução de Endereço Lógico para Endereço Físico Durante a carga, uma tabela de páginas é montada para o processo Tabela informa, para cada página, qual o quadro correspondente Utilizada pelo mecanismo de tradução de endereços lógicos para endereços físicos Número (identificador) da página é extraído do endereço lógico Dado o número da página, obtém o número do quadro na tabela de páginas Bits de deslocamento da página, extraídos do endereço lógico, são concatenados ao número do quadro para formar o endereço físico Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 14 / 52 Tradução de Endereço Lógico para Endereço Físico Memória Lógica Memória Física A B C D E F G H G H C D F A B E 000 001 010 011 100 110 111 101 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 Página Quadro 00 01 10 11 010 110 000 101 Tabela de Páginas Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 15 / 52 Tradução de Endereço Lógico para Endereço Físico 101 0001 Memória Lógica Memória Física A B C D E F G H G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 CPU End. Lógico End. Físico Página Quadro 00 01 10 11 010 110 000 101 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 16 / 52 Sumário 1 Introdução 2 Paginação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Páginas Paginação Multinível Considerações sobre Paginação 3 Segmentação 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 16 / 52 Implementação da Tabela de Páginas Aspecto importante da paginação reside em como a tabela de páginas é implementada Entradas na tabela de páginas possuem, além do número do quadro, bits adicionais que auxiliam o gerenciador de memória Layout exato pode variar de máquina para máquina Informação presente costuma ser a mesma Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 17 / 52 Implementação da Tabela de Páginas Número do quadro Presente/Ausente Proteção Modificado Referenciado Caching Presente/Ausente: indica se a entrada corresponde a uma página válida (que pode ser acessada pelo processo) ou inválida (MMU gera uma interrupção) Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 18 / 52 Implementação da Tabela de Páginas Número do quadro Presente/Ausente Proteção Modificado Referenciado Caching Proteção: indica o tipo de acesso permitido (leitura, escrita, execução) Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 18 / 52 Implementação da Tabela de Páginas Número do quadro Presente/Ausente Proteção Modificado Referenciado Caching Modificado: também conhecido como dirty bit, indica que o conteúdo de uma página foi alterado pelo processo Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 18 / 52 Implementação da Tabela de Páginas Número do quadro Presente/Ausente Proteção Modificado Referenciado Caching Referenciado: indica se uma página foi acessada pelo processo Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 18 / 52 Implementação da Tabela de Páginas Número do quadro Presente/Ausente Proteção Modificado Referenciado Caching Caching: se definido, impede que a página seja movida para memória cache; utilizado com páginas mapeadas para dispositivos de E/S Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 18 / 52 Implementação da Tabela de Páginas Tabelas de Páginas em Registradores Implementação possível quando a tabela de páginas é pequena Exemplo: se memória lógica dos processos tem até 64 KB e páginas são de 8 KB, cada tabela de páginas tem, no máximo, 8 entradas Descritor de processo deve manter uma cópia da tabela de páginas Atualizar os registrados durante troca de contexto Vantagem: velocidade dos registradores não degrada o desempenho de acesso à memória Desvantagem: número de registradores necessários pode limitar a utilização Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 19 / 52 Implementação da Tabela de Páginas Tabelas de Páginas em Memória Abordagem convencional para tabelas de páginas de tamanho moderado à grande MMU possui dois registradores para localizar a tabela de páginas na memória: Page Table Base Register (PTBR): endereço físico do início da tabela Page Table Limit Register (PTLR): número de entradas na tabela Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 20 / 52 Implementação da Tabela de Páginas Memória Lógica Memória Física A B C D E F G H 010 110 000 101 G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 CPU End. Lógico 000 001 010 011 100 110 111 101 101 0110 PTBR Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 21 / 52 Implementação da Tabela de Páginas 101 Memória Lógica Memória Física A B C D E F G H 010 110 000 101 G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 CPU End. Lógico 0110 PTBR + 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 21 / 52 Implementação da Tabela de Páginas Memória Lógica Memória Física A B C D E F G H 010 110 000 101 G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 CPU End. Lógico End. Físico 000 000 001 010 011 100 110 111 101 101 0110 PTBR + Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 21 / 52 Implementação da Tabela de Páginas 0001 Memória Lógica Memória Física A B C D E F G H 010 110 000 101 G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 CPU End. Lógico End. Físico 101 0110 PTBR + 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 21 / 52 Implementação da Tabela de Páginas 101 0001 Memória Lógica Memória Física A B C D E F G H 010 110 000 101 G H C D F A B E 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 CPU End. Lógico End. Físico 0110 PTBR + 000 001 010 011 100 110 111 101 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 21 / 52 Implementação da Tabela de Páginas Cada acesso que um processo faz à memória lógica transforma-se em dois acessos à memória física Primeiro para traduzir o endereço lógico para endereço físico Segundo para acessar a memória do processo Descritor de processo deve manter cópia dos valores do PTBR e PTLR Atualizar registradores da MMU na troca de contexto Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 52 Implementação da Tabela de Páginas Translation Lookaside Buffer (TLB) Meio termo entre a implementação via registradores e via memória Baseada em uma memória cache especial, interna à MMU Memória associativa: componente de hardware que permite buscar valores por conteúdo, de forma paralela, para um banco de registradores Objetivo: manter uma cópia parcial da tabela de páginas na TLB Se a página acessada estiver na TLB (hit), obtém o número do quadro diretamente Se a página acessada não estiver na TLB (miss), busca o quadro na memória e adiciona a respectiva entrada da tabela na TLB Supõe (corretamente, na maioria das vezes) que a página será acessada novamente Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 23 / 52 Implementação da Tabela de Páginas 101 Memória Lógica Memória Física A B C D E F G H 010 110 000 101 G H C D F A B E 000 001 010 011 100 110 111 101 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 CPU End. Lógico End. Físico 0110 PTBR + 0001 000 110 01 10 TLB hit miss Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 24 / 52 Implementação da Tabela de Páginas Melhora o desempenho de acesso a tabela de páginas Tempo de acesso 10 vezes menor que na memória RAM Desvantagem da TLB é seu custo Tamanho limitado (de 8 a 2048 entradas) MMU possui uma única TLB, que é compartilhada por todos os processos Apenas as páginas em uso por um processo precisam estar na TLB Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 52 Implementação da Tabela de Páginas Taxa de Acerto na TLB (hit ratio) Probabilidade de uma entrada da tabela de páginas contendo uma página referenciada pelo processo estar na TLB Complemento da taxa de acerto (hit ratio) é a taxa de erro (miss ratio) Tempo médio de acesso a memória pode ser estimado considerando o hit ratio thit = tTLB + tMem tmiss = tTLB + 2 × tMem t = h × thit + (1 − h) × tmiss com tTLB e tMem denotando, respectivamente, tempo de acesso à TLB e à memória principal, e h denotando o hit ratio Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 26 / 52 Implementação da Tabela de Páginas Exemplo tTLB = 20 ns tMem = 100 ns thit = 20 + 100 = 120 ns tmiss = 20 + 2 × 100 = 220 ns Para um hit ratio de 80% (h = 0.80): t = 0.80 × 120 + (1 − 0.80) × 220 = 140 ns Para um hit ratio de 98% (h = 0.98): t = 0.98 × 120 + (1 − 0.98) × 220 = 122 ns Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 52 Sumário 1 Introdução 2 Paginação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Páginas Paginação Multinível Considerações sobre Paginação 3 Segmentação 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 52 Paginação Multinível Na prática, as tabelas de páginas possuem tamanho variável Como dimensionar o tamanho da tabela de páginas? Fixo ou variável conforme a necessidade? Como armazenar a tabela de páginas? Contíguo em memória → fragmentação externa Paginando a própria tabela Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 28 / 52 Paginação Multinível Paginação multinível surge como solução para esses problemas Tabelas de páginas podem crescer de pedaço em pedaço Tabelas auxiliares chamadas “diretórios” mantém o endereço de cada pedaço t p d f d Diretório Tabela de Páginas Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 52 Paginação Multinível Nível 1 Nível 2 Página Deslocamento Diretório Global Diretório Intermediário Tabela de Páginas Quadro Típico em arquiteturas de processadores de 64 bits Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 30 / 52 Sumário 1 Introdução 2 Paginação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Páginas Paginação Multinível Considerações sobre Paginação 3 Segmentação 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 30 / 52 Considerações sobre Paginação Paginação é um tipo de relocação dinâmica Não gera fragmentação externa Página pode ser carregada em qualquer quadro livre Fragmentação interna é restrita apenas à última página do processo Em média, pode-se esperar um desperdício de meia página por processo Na visão do processo, espaço de endereçamento é contíguo Na visão do sistema, processo está espalhado pela memória física Facilita implementação de proteção e compartilhamento Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 31 / 52 Considerações sobre Paginação Tamanho da página é imposto pelo hardware (MMU) Valores típicos variam entre 1 KB e 8 KB Definição do tamanho da página possui objetivos conflitantes Páginas maiores implicam em... Processos compostos por menos páginas e, portanto, tabelas de páginas menores Aumento da fragmentação interna na última página Páginas menores implicam em... Processos compostos por mais páginas e, portanto, tabelas de páginas maiores Diminuição da fragmentação interna na última página Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Segmentos Considerações sobre Segmentação Segmentação Paginada 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 52 Segmentação Alocação Contígua Não contígua Simples Particionada Estática Dinâmica Paginação Segmentação Segmentação paginada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 33 / 52 Segmentação Leva em consideração a visão de programadores e compiladores Programa é uma coleção de segmentos, tipicamente: Código Dados alocados estaticamente Dados alocados dinamicamente (heap) Pilha de execução (stack) Sistemas podem trabalhar com granularidades diferentes Objetos, módulos, bibliotecas, procedimentos, etc. Gerência de memória pode suportar diretamente o conceito de segmentos Código Dados Heap Stack 0 0xFF... Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 34 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Segmentos Considerações sobre Segmentação Segmentação Paginada 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 34 / 52 Tradução de Endereço Lógico para Endereço Físico Endereço lógico é dividido em duas partes Número (identificador) do segmento Deslocamento dentro do segmento Segmentos não necessitam ter o mesmo tamanho Existe um tamanho máximo de segmento Segmentação é similar a alocação particionada dinâmica Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 35 / 52 Tradução de Endereço Lógico para Endereço Físico Tradução é feita de forma similar a paginação Via uma tabela de segmentos Cada entrada na tabela de segmentos possui: Base: endereço físico do início do segmento na memória Limite: tamanho do segmento Para proteção, endereço físico tem que ser verificado a cada acesso Depende de suporte de hardware Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 36 / 52 Tradução de Endereço Lógico para Endereço Físico C1 C2 C3 C4 D1 D2 D3 P1 0000 0001 0010 0011 0000 0010 0000 0001 P2 0001 Segmento 00 Código Segmento 01 Dados Segmento 10 Pilha Memória Lógica Memória Física 0000 0001 0010 0011 0100 0110 0111 0101 1000 1001 1010 1011 1100 1101 P1 P2 D1 D2 D3 C1 C2 C3 C4 1010 100 0000 011 00 01 10 0100 010 Segmento Base Limite CPU 100001 < + Interrupção Sim Não Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 37 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Segmentos Considerações sobre Segmentação Segmentação Paginada 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 37 / 52 Implementação da Tabela de Segmentos Cada segmento do programa corresponde a uma entrada na tabela de segmentos Implementação com alternativas análogas à tabela de páginas: Mantendo tabela de segmentos em registradores ou em memória Para tabela em memória, TLB pode ser empregada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 52 Implementação da Tabela de Segmentos Tabela de Segmentos em Registradores Implementação possível quando a tabela de segmentos é pequena Cada segmento ocupa dois registradores (base e limite) Descritor do processo deve manter uma cópia dos registradores Atualização dos registradores durante troca de contexto Não degrada o desempenho durante o acesso à memória Número de registradores impõem uma limitação prática ao tamanho da tabela Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 39 / 52 Implementação da Tabela de Segmentos Tabela de Segmentos em Memória Abordagem para tabelas de segmentos de tamanho moderado à grande MMU possui dois registradores para localizar a tabela de segmentos na memória: Segment Table Base Register (STBR): endereço físico do início da tabela Segment Table Limit Register (STLR): número de entradas na tabela Número do segmento é comparado com o STLR Válido apenas de for menor que STLR STBR é somado ao número do segmento para obter a entrada na tabela de segmentos Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 40 / 52 Implementação da Tabela de Segmentos Descritor do processo deve manter uma cópia do STBR e STLR Atualização dos registradores durante troca de contexto Apresenta problemas similares à tabela de páginas em memória Tabela pode ser muito grande Cada acesso à memória lógica se traduz em dois acessos a memória física Solução: utilizar TLB Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Segmentos Considerações sobre Segmentação Segmentação Paginada 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 52 Considerações sobre Segmentação Entradas na tabela de segmentos podem possuir além dos valores base e limite, bits de proteção, validade e outros, como na tabela de páginas Segmentação adiciona a possibilidade de compartilhar apenas trechos da área de código Processos diferentes referenciando um mesmo segmento na memória física Desvantagem: provoca fragmentação externa quando segmentos começam a ser liberados da memória Memória pode ser compactada e segmentos adjacentes combinados, assim como na alocação particionada dinâmica Paginação é a solução natural para a fragmentação Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 42 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação Tradução de Endereço Lógico para Endereço Físico Implementação da Tabela de Segmentos Considerações sobre Segmentação Segmentação Paginada 4 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 42 / 52 Segmentação Paginada Alocação Contígua Não contígua Simples Particionada Estática Dinâmica Paginação Segmentação Segmentação paginada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 43 / 52 Segmentação Paginada Analisar o problema sob dois pontos extremos Processo é um segmento Equivalente a alocação contígua particionada dinâmica Sofre com fragmentação externa Cada byte é um segmento Sem fragmentação externa, nem interna Alto custo (overhead) de gerência Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 44 / 52 Segmentação Paginada Solução: encontrar um meio termo entre os extremos Segmentos compostos por um número fixo e “mais apropriado” de bytes Equivale a ter o segmento dividido internamente em blocos Combinar as vantagens da paginação e da segmentação em termos de fragmentação Paginação Segmentação Fragmentação Interna   Fragmentação Externa   Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 45 / 52 Segmentação Paginada Na segmentação paginada, o espaço de endereçamento lógico é formado por segmentos e cada segmento é dividido em páginas Entrada na tabela de segmentos aponta para a tabela de páginas do segmento Endereço lógico é dividido em três partes: Número (identificador) do segmento Número (identificador) da página Deslocamento dentro da página Memória física alocada em termos de quadros Elimina a fragmentação externa s p d f d Tabela de Segmentos Tabela de Páginas do Segmento 0 Tabela de Páginas do Segmento 2 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 46 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação 4 Considerações Finais Exercícios Referências Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 46 / 52 Considerações Finais Paginação como solução para problemas da alocação particionada Permite alocar uma área não contígua da memória física para um processo Elimina a fragmentação externa Fragmentação interna apenas na última página do processo Tradução do endereço lógico para o endereço físico Endereço lógico composto de duas partes Tabela de páginas Tabela de páginas pode ser implementada em registradores ou em memória TLB utilizado para evitar dois acessos à memória física para cada acesso à memória lógica Para tabela de páginas grandes, pode-se utilizar paginação multinível Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 47 / 52 Considerações Finais Segmentação aproxima a alocação da memória física à visão do programador e compilador Segmentos de código, dados e pilha de execução Tradução do endereço lógico para endereço físico similar ao utilizado na paginação Tabela de segmentos indexada pelo número do segmento com base e limite Tabela de segmentos pode ser implementada em registrados e em memória TLB também pode ser utilizada para reduzir o tempo de acesso Fragmentação externa continua sendo problema Solução: dividir um segmento em paginas Segmentação paginada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 48 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação 4 Considerações Finais Exercícios Referências Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 48 / 52 Exercícios 1 Considere um sistema operacional que trabalha com paginação simples. As páginas são de 1 KB. O endereço lógico é formado por 16 bits. O endereço físico é formado por 20 bits. Qual o tamanho do: a Espaço do endereçamento lógico (maior programa possível)? b Espaço do endereçamento físico (memória principal)? c Entrada da tabela de páginas, sem considerar bits auxiliares? d Tabela de páginas (número de entradas necessárias no pior caso)? Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 49 / 52 Exercícios 2 Considere a seguinte tabela de segmentos: Segmento Base Limite 000 000011011011 1001011000 001 100011111100 0000001110 010 000001011010 0001100100 011 010100101111 1001000100 100 011110100000 0001100000 Quais os endereços físicos para os seguintes endereços lógicos? a 000000110101110 b 001000000001010 c 010000111110100 d 011000110010000 e 100000001110000 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 50 / 52 Exercícios 3 Em um sistema usando segmentação paginada, o espaço de endereçamento lógico de cada processo consiste de no máximo 16 segmentos, cada um deles podendo ter até 64 KB de tamanho. As páginas físicas são de 512 bytes. Diga quantos bits são necessários para especificar cada uma das grandezas abaixo, mostrando os cálculos de origem de cada número. a Número do segmento b Número de uma página lógica dentro do segmento c Deslocamento dentro de um página d Endereço lógico completo Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 51 / 52 Sumário 1 Introdução 2 Paginação 3 Segmentação 4 Considerações Finais Exercícios Referências Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 51 / 52 Referências OLIVEIRA, R. S.; CARISSIMI, A. S.; TOSCANI, S. S. Sistemas Operacionais. 4. ed. Porto Alegre: Bookman, 2010. 374 p. ISBN 978-85-7780-521-1. TANENBAUM, A. S.; BOS, H. Modern Operating Systems. 4. ed. [S. l.]: Pearson Education, 2015. 1136 p. ISBN 978-0-13-359162-0. SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Operating System Concepts. 9. ed. [S. l.]: Wiley, 2012. 976 p. ISBN 978-1-118-06333-0. Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 52 / 52 INE5611 - Sistemas Operacionais Paginação e Segmentação Prof. Eduardo Camilo Inacio, Dr. eduardo.camilo@ufsc.br Universidade Federal de Santa Catarina Departamento de Informática e Estatística