Memória Virtual - Arquitetura de Computadores II

Arquitetura de Computadores II Prof Leonel Tedesco leoneltedescouniscbr Memória Virtual Arquitetura de Computadores II Leonel Tedesco Slide 2 Sistemas de Memória Principal Memória principal MP é mais um nível da hierarquia de memória Possui o princípio da gerência similar a outros níveis de memória Dados mais usados são trazidos para MP para diminuir tempo médio de acesso ao nível mais baixo neste caso o disco Arquitetura de Computadores II Leonel Tedesco Slide 3 Memória Virtual alguns pressupostos Um único programa pode precisar de mais memória principal do que a máquina dispõe Múltiplos programas devem compartilhar a memória principal sem interferirem entre si Com a memória virtual porções de diferentes programas são carregados do disco para memória de acordo com a demanda Quando a memória é totalmente preenchida algumas porções dos programas podem ser swapped trocadas para o disco Arquitetura de Computadores II Leonel Tedesco Slide 4 Memória Virtual Gerência de MP não utiliza mesmas técnicas que gerência de caches por 2 motivos Evolução Histórica Idéia de memória como área de armazenamento temporário de dados é anterior ao conceito de cache Diferentes Características Tamanho e tempo de acesso da MP são muito maiores que das caches Ao contrário das caches parte da gerência pode ser feita em SW Sistema Operacional Unidades de gerência possuem a identificação do processo dono pode ser utilizado na estratégia de gerência Arquitetura de Computadores II Leonel Tedesco Slide 5 Sistemas Monoprogramados Objetivo Permitir que programas maiores que a memória pudessem executar Primeiras estratégias baseadas em overlays sobreposição No final dessas partes era colocado código responsável pela carga da próxima parte que iria sobrepor Endereços antigos não são mais necessários Programador tinha controle total da memória Responsável pela troca das partes Programa escrito de forma a evitar quebras em muitas partes A troca tinha um alto custo Arquitetura de Computadores II Leonel Tedesco Slide 6 Sistemas Multiprogramados Multiprogramação trouxe dificuldades Gerência de overlays deveria possibilitar vários programas executando concorrentemente mesmo que estes somados não coubessem na memória Gerência de overlays de cada programa não podia interferir na dos outros programas Necessário que agente externo seja responsável pela gerência Responsabilidade de gerenciar memória passou do usuário para monitor residente mais tarde chamado de SO Sistema Operacional Arquitetura de Computadores II Leonel Tedesco Slide 7 Fragmentação de Memória Problema diretamente relacionado com gerência de MP Fragmentação resulta em desperdício de memória Tipos de fragmentação Fragmentação Interna Ocorre quando usada unidade de gerência de tamanho fixo página Requisição não exatamente divisível pela unidade é arredondada para cima resulta unidade alocada mas não completamente ocupada Fragmentação Externa Ocorre quando usada unidade de gerência de tamanho variável segmento Seqüência de alocações e liberações Conseqüência Requisição de usuário pode ser negada apesar de existir memória livre Arquitetura de Computadores II Leonel Tedesco Slide 8 Implementando memória virtual Separar diferentes programas residentes na memória atribuindo endereços diferentes para cada um Identificar quando as instruções ou dados desejados estão ou não na memória Gerar uma interrupção quando eles não estão na memória para serem buscados no disco Prover suporte ao SO para recuperar as instruçõesdados necessários substituindo outros caso necessário Prevenir que usuários de acessar dadosinstruções que não lhes pertence Arquitetura de Computadores II Leonel Tedesco Slide 9 Endereçamento a Memória Principal Como endereços de um programa são usados para acessar posições da MP Modos de endereçamento Endereçamento Contíguo Programa é carregado inteiro em uma única área de memória contígua Endereçamento NãoContíguo Quebra programa em vários pedaços carregados em áreas distintas da memória Vantagens Não há necessidade de manter qualquer ordem Melhorar aproveitamento da memória menor fragmentação externa Desvantagens Gerência de memória mais complexa Arquitetura de Computadores II Leonel Tedesco Slide 10 Geração do endereço na carga Espaço de endereçamento de um programa inicia sempre em 0 sendo relocado na carga pelo carregador loader Problemas A conversão dos endereços pode atrasar a operação de carga O programa não pode ser mudado de lugar durante a sua execução impede compactação e swap Endereçamento Contíguo Direto multiprogramação Arquitetura de Computadores II Leonel Tedesco Slide 11 Endereçamento Contíguo Relativo Alternativa mais flexível uma vez que o endereço é montado somente no acesso Espaço de endereçamento lógico inicia em 0 Processador possui registrador de endereçamento base contém base do endereço físico dos programas Endereço real é montado somando a base com o endereço relativo do programa em cada acesso Programa pode ser trocado de lugar na memória em tempo de execução Arquitetura de Computadores II Leonel Tedesco Slide 12 Endereçamento NãoContíguo Programa é dividido em pedaços carregados em áreas distintas da memória Conversão dinâmica de endereços Ao acessar a memória endereços lógicos são convertidos em físicos Implementada em HW mais rápido Endereçamento Paginação Unidade de gerência de memória física quebrada em frames com tamanho fixo Segmentação Unidade de gerência de memória física quebrada em segmentos com tamanho variável Segmentopaginação Combinação dos tipos de endereçamento anteriores Arquitetura de Computadores II Leonel Tedesco Slide 13 Endereçamento NãoContíguo Paginado Frames com tamanho fixo 4k 8k etc Endereçamento lógico do programa quebrado em páginas do mesmo tamanho dos frames Quando processo é executado todas suas páginas são carregadas para frames livres da memória qualquer página em qualquer frame livre Arquitetura de Computadores II Leonel Tedesco Slide 14 Páginas de memória Transferências entre disco e memória ocorrem em páginas de tamanho especificado pelo ISA O tamanho dessas páginas é usualmente grande de modo a atenuar o alto custo de acesso ao disco 5 a 10 ms No entanto aumentar muito o tamanho da página pode não ser uma boa ideia pois o tempo de acesso também aumenta muito disk main memory L2 cache página 464KB Bloco de cache 16 128B Arquitetura de Computadores II Leonel Tedesco Slide 15 Endereço físico e virtual Os endereços virtuais no programa são traduzidos durante a execução para endereços físicos usados para endereçar a memória Alguns endereços virtuais podem referenciar dados que não estão na memória não residentes Arquitetura de Computadores II Leonel Tedesco Slide 16 Endereços lógicos e físicos Arquitetura de Computadores II Leonel Tedesco Slide 17 Tradução de endereços Tradução de endereços é uma tarefa executada pelo hardware e pelo SO O sistema operacional mantém para cada programa Quais páginas estão associadas com cada programa Onde essas páginas residem no disco Qual páginas estão residentes na memória O ppn associado com cada vpn das páginas residentes na memória Arquitetura de Computadores II Leonel Tedesco Slide 18 Tradução de endereços Para cada programa o SO configura uma tabela de página na memória principal que armazena o ppn correspondente ao vpn de cada página residente na memória O registrador de tabela de página implementado em hardware fornece o endereço base da tabela de página para o processo corrente Cada programa tem uma tabela de página e um valor de registrador de tabela de página únicos carregados pelo SO Arquitetura de Computadores II Leonel Tedesco Slide 19 1GB de memória principal na máquina 4GB de espaço para endereçamento virtual Tradução de endereços O número da página virtual vpn parte do endereço virtual é traduzido para um número de página físico ppn que aponta para a página desejada Os bits de menor ordem offset da página virtual apontam para o byte a ser acessado dentro da página física 212 4KB page Arquitetura de Computadores II Leonel Tedesco Slide 20 Tradução de endereços Acesso à tabela de páginas Endereço é registrador de tabela de página vpn Localizado na memória requer acesso por loadsstores Arquitetura de Computadores II Leonel Tedesco Slide 21 Tradução de endereços Ou Ainda ppn Offset de página Posição do primeiro byte na página 2page offset bytes page Posição do byte endereçado na página Arquitetura de Computadores II Leonel Tedesco Slide 22 Tradução de endereços a antes b depois Arquitetura de Computadores II Leonel Tedesco Slide 23 Tradução de endereços Tabela de páginas pode ser armazenada em Registradores rápido mas limita tamanho da tabela Memória principal área do sistema lento são necessários dois acessos 1 tabela 1 dado pode ter tamanho ilimitado TLB Translation Lookaside Buffer área de memória associativa usada como cache para as conversões mais efetuadas Situase entre processador e cache Tamanho da página Pequena menor fragmentação interna tabela de páginas fica maior Grande maior fragmentação interna tabela de páginas fica menor Arquitetura de Computadores II Leonel Tedesco Slide 24 TLB Traduzindo endereços mais rapidamente Problema para cada instrução ou dado acessado é necessário primeiramente acessar a tabela de página na memória para ver o endereço físico Solução armazenar as traduções de endereços na TLB Translation Lookaside Buffer O TLB guarda o ppn das páginas mais recentemente acessadas O hardware primeiro checa o TLB em busca do par de vpnppn se não for encontrado falha no TLB então a tabela de página é acessada normalmente a partir da memória principal O ppn é carregado no TLB para acessos futuros Arquitetura de Computadores II Leonel Tedesco Slide 25 Operação da paginação e do TLB Arquitetura de Computadores II Leonel Tedesco Slide 26 Acessando o TLB e a Cache MIPS R2000 TLB completamente associativa e Dcache Arquitetura de Computadores II Leonel Tedesco Slide 27 Falhas de página Se o bit de validade para a entrada da tabela de página é 0 página não está na memória uma exceção que indica falha de página chama o SO O SO salva o estado do processo que está rodando muda seu status para idle e inicia o acesso à pagina no disco O SO seleciona outro processo para rodar na CPU enquanto espera o acesso ser completado Quando o acesso completa uma exceção de ES chama o SO que atualiza a tabela de página e muda o status daquele processo para executável Arquitetura de Computadores II Leonel Tedesco Slide 28 Substituição de página Se a memória principal está cheia o SO substitui a página usando um procedimento pseudoLRU Cada página possui um bit de referência que é setado a cada vez que a página é acessada Bits de referência são periodicamente zerados pelo SO SO escolhe uma página com bit de referência 0 para ser substituída Páginas com bit de sujeira setados geram atualização no disco quando são substituídas Depois da substituição a página desejada é carregada na memória e a tabela de página é atualizada TLB também possui bits de referência e sujeira Arquitetura de Computadores II Leonel Tedesco Slide 29 Falhas no TLB Falhas no TLB são gerenciados por microcódigo ou rotina em software Operação de falha no TLB gera Seleciona uma entrada a ser substituída Atualiza qualquer um dos bits especiais que foram modificados da entrada substituída na tabela de página Acessa a entrada da tabela de página correspondente ao vpn desejado Se bit validade 0 geração de falha de página Caso contrário carrega a informação da tabela de página no TLB e refaz o acesso Falha pode ser só na TLB mas também pode ser que a informação não esteja mais na memória falha de página Arquitetura de Computadores II Leonel Tedesco Slide 30 Endereçamento NãoContíguo Segmentado Não divide memória física Pode alocar unidade em qualquer posição Unidade de gerência com tamanho variável denominada segmento Segmento definido pelo usuário ou compilador Endereços de um mesmo segmento estão relacionados Gerência de memória mais preocupada com a visão do usuário Exemplo de segmentos dados código pilha Quando processo é executado todos seus segmentos são carregados para memória em qualquer posição livre Arquitetura de Computadores II Leonel Tedesco Slide 31 Endereçamento NãoContíguo Segmentado Arquitetura de Computadores II Leonel Tedesco Slide 32 Conversão de endereços Número de bits de d determina tamanho máximo dos segmentos Número de bits de s determina número máximo de segmentos de um processo Deslocamento do endereço lógico é comparado com tamanho do segmento em uma tabela de segmentos Evita invasões de segmentos vizinhos Este teste não era necessário no endereçamento paginado pela limitação do número de bits Arquitetura de Computadores II Leonel Tedesco Slide 33 Conversão de endereços Arquitetura de Computadores II Leonel Tedesco Slide 34 Conversão de endereços Unidade de gerência variável Gera fragmentação externa Compactação da memória necessária devido alta fragmentação externa É possível compartilhar segmentos entre vários processos leitura Fácil implementar com várias tabelas de segmento apontando para mesma área de memória Tabela de Segmentos aponta base do segmento na MP e verifica se deslocamento está dentro do limite do segmento Arquitetura de Computadores II Leonel Tedesco Slide 35 Conversão de endereços Tabela de segmentos pode ser armazenada igual a paginação Registradores MP TLB Tabela de Alocação controla quais lacunas estão livres Uma tabela de alocação para todo o sistema de tamanho variável Número de áreas da MP é inicialmente 1 toda a memória Ao longo da gerência pode variar com a inclusão de áreas ocupadas Liberação de segmentos pode resultar na junção de vários segmentos e na diminuição do número de entradas da tabela Arquitetura de Computadores II Leonel Tedesco Slide 36 Algoritmos para Alocação de Segmento na Memória First fit Pega o primeiro segmento livre que tem tamanho suficiente para a requisição de memória Rápido mas gera muita fragmentação Tende a deixar a memória com diversos buracos de tamanho médio Arquitetura de Computadores II Leonel Tedesco Slide 37 Next fit Pega o próximo livre a partir do último Requer um ponteiro que armazena a última posição alocada É uma variação do first fit que utiliza melhor toda a memória Algoritmos para Alocação de Segmento na Memória Arquitetura de Computadores II Leonel Tedesco Slide 38 Best fit Pesquisa a lista de memória inteira procurando o segmento livre que mais se aproxima do tamanho desejado Para a pesquisa se encontra um segmento que atende exatamente ao tamanho desejado Normalmente deixa a memória com vários grandes buracos e pequenos buracos Algoritmos para Alocação de Segmento na Memória Arquitetura de Computadores II Leonel Tedesco Slide 39 Worst fit Pesquisa o maior segmento livre O algoritmo privilegia a existência de segmentos grandes Algoritmos para Alocação de Segmento na Memória Arquitetura de Computadores II Leonel Tedesco Slide 40 Vantagens e desvantagens Arquitetura de Computadores II Leonel Tedesco Slide 41 Endereçamento NãoContíguo SegmentoPaginado Combinação entre segmentação e paginação Do mapeamento segmentado aproveita visão lógica de memória próxima do usuário Do mapeamento paginado aproveita a gerência de memória mais simples Usuário aloca segmentos e estes são mapeados em grupo de páginas Memória física quebrada em frames de tamanho fixo como na paginação Porém existe informação das páginas que compõem cada segmento Unidade de gerência de tamanho fixo gera fragmentação interna Arquitetura de Computadores II Leonel Tedesco Slide 42 Tabela de Segmentos usada para obter base da tabela de páginas do segmento desejado Tabela de páginas usada para converter páginas de cada segmento em frames uma tabela por segmento de cada processo Tabela de Frames usada para controle dos frames livres Uma tabela de frames para todo sistema Tamanho fixo Número de frames da MP é conhecido tamanho da memória tamanho da página Procura por firstfound qualquer lacuna serve para qualquer página Endereçamento NãoContíguo SegmentoPaginado Arquitetura de Computadores II Leonel Tedesco Slide 43 Conversão de endereços Seqüência de acesso Número do segmento fornece na tabela de segmentos a base da tabela de páginas deste segmento Número da página e base da tabela de páginas fornece frame correspondente Número do frame e deslocamento dentro dele fornece acesso à memória Arquitetura de Computadores II Leonel Tedesco Slide 44 Vantagens e Desvantagens Arquitetura de Computadores II Leonel Tedesco Slide 45 Acesso Completo a Endereços