Gestão de Memória - Sistemas Operativos 2017/2018 PDF

3. Gestão de Memória Sistemas Operativos Baseado no Capítulo 3 2017/2018 Valentim Realinho Introdução  É da responsabilidade do sistema operativo gerir a memória disponível no sistema:  Representação do estado da memória  Atribu...

3. Gestão de Memória Sistemas Operativos Baseado no Capítulo 3 2017/2018 Valentim Realinho Introdução  É da responsabilidade do sistema operativo gerir a memória disponível no sistema:  Representação do estado da memória  Atribuição de memória aos processos  Libertação da memória  Conjugação entre a memória principal e secundária Registos Microprogramação Cache Memória principal Sistema Operativo Discos (memória secundária) Tapes Software de Backup 2 Sistemas Mono-programados  Programas executados à vez  Mediante um comando, o SO carrega o programa em memória principal, e este corre até terminar  Programas limitados à dimensão da memória  Para minorar este problema surgiu a técnica dos overlays – partes de programas (definidas pelo programador) são carregadas em memória  Protecção da memória ocupada pelo SO  Registo Fronteira – registo do processador que é carregado com o endereço limite do sistema operativo 3 Sistemas Mono-programados  Organização da memória Espaço de Espaço de endereçamento endereçamento Device ROM Drivers Programa RAM Programa Fronteira RAM Sistema Sistema Operativo Operativo 4 Sistemas Multi-programados  Grau de multi-programação  Uma medida aproximada da utilização do CPU quando vários programas correm “simultaneamente”  Suponha que os processos passam uma fracção do tempo da sua existência – p – bloqueados em operações de I/O  Se n processos estiverem a correr, a probabilidade do CPU estar desocupado será então dada por pn (corresponde à probabilidade de todos os processos estarem bloqueados em operações de I/O)  A taxa de ocupação do CPU será então dada por 1-pn n designa-se por grau de multi-programação 5 Sistemas Multi-programados  Grau de multi-programação 100% 80% Utilização da CPU 60% 40% 20% I/O 50% I/O 20% 80% I/O 90% I/O 0% 20 4 6 8 10 Grau de multi-programação (processos em memória) A curva que melhor se ajusta à realidade estará situada entre 80% e 90% I/O 6 Sistemas Multi-programados  Partições fixas  Memória dividida em várias partições de dimensão fixa, definidas inicialmente pelo gestor de sistema  Cada programa é carregado numa partição com uma dimensão adequada  Fragmentação da memória:  Interna – espaço desperdiçado dentro de cada partição  Externa – partições inteiras desperdiçadas. 7 Sistemas Multi-programados  Formas de implementação Múltiplas filas Fila única 800K 800K Partição 3 Partição 3 700K 700K Partição 2 Partição 2 500K 500K Partição 1 Partição 1 100K 100K Sistema Sistema Operativo Operativo 0K 0K 8 Sistemas Multi-programados  Colocação e Protecção  A multi-programação trouxe dois problemas a resolver:  Colocação – garantir que os endereços referenciados por um programa sejam os correctos independentemente da posição de memória a partir da qual é carregado  Registo Base – a todos os endereços referenciados pelo programa soma-se o endereço base da partição onde este é carregado. Os programas são escritos como se o primeiro endereço fosse 0.  Protecção – impedir que um programa aceda aos endereços de um outro programa  Registo Limite – verifica-se se os endereços referenciados pelo programa se encontram dentro da partição que lhe é atribuída 9 Sistemas Multi-programados  Colocação e Protecção  Exemplos Base e limite para a partição 1 896K Partição 3 Verificação de acesso ao endereço End 768K Partição 2 N End < Limite ? 512K Partição 1 Limite = 384K S Programa Falha de End = Base + End protecção Base = 128K 128K Sistema Operativo 0K 10 Sistemas Multi-programados  Partições variáveis  Outro esquema consiste em atribuir partições com dimensões dinâmicas, ajustadas à dimensão dos programas  Deixa de existir fragmentação interna, mas continua a haver fragmentação externa  Para resolver a fragmentação, utiliza-se de tempos em tempos um procedimento de agrupamento da memória num bloco de endereços contíguos – compactação da memória 11 Sistemas Multi-programados  Swapping  Esquema que envolve a memória principal e a memória secundária (disco)  A ideia consiste em transferir processos da memória principal para o disco e vice-versa  Um possível critério será transferir para o disco um processo que bloqueie, e trazer para a RAM um processo que se torne activo  Esta estratégia é utilizada em conjunto com partições de dimensões variáveis  Conduz à proliferação de buracos (fragmentação) – é necessário recorrer à compactação da memória 12 Sistemas Multi-programados  Exemplo Início Entrada A Entrada B Entrada C swap-out A (RAM livre) C C B B B A A A S.O. S.O. S.O. S.O. S.O. Entrada D swap-out B swap-in A swap-out D compactação swap-in B C C C C B B C C A A A A D D D S.O. S.O. S.O. S.O. S.O. S.O. 13 Sistemas Multi-programados  Representação da memória  Estrutura-se a memória em unidades (blocos) de dimensão fixa 0  Representa-se o estado da memória 1 P1 através de: 2  Listas ligadas 3 4 P 0 3 L 3 4 P 7 2 5 6 7 L 9 2 P 11 4 L 15 1 P2 8  Bitmaps 9 1110000110011110 10 1 – representa bloco ocupado 11 0 – representa bloco livre 12 P3 13 14 15 14 Sistemas Multi-programados  Algoritmos  First fit – procura o primeiro buraco da lista com dimensão suficiente para carregar o programa  Next fit – variante do anterior – procura a partir do ponto em que foi encontrado um buraco anteriormente  Best fit – procura o buraco com a dimensão que melhor se ajusta ao programa a carregar  Worst fit – procura o maior buraco disponível, na esperança de que o espaço que sobra possa ainda ser utilizado por outros programas a carregar no futuro  Quick fit – mantém várias listas de buracos, agrupados de acordo com as suas dimensões 15 Sistemas Multi-programados  Memória dinâmica  Um processo pode ter necessidade de obter mais memória em tempo de execução  Uma solução seria efectuar swap-out do processo e depois swap-in com uma nova dimensão  Demasiado lento...  Outra solução será reservar Stack antecipadamente espaço para Espaço para crescimento crescimento do stack e da heap  Rápido, mas com algum Heap desperdício de memória (é o mais utilizado) Programa 16 Sistemas Multi-programados  Na linguagem C existem algumas funções que para manipulação de memória dinâmica  malloc(size_t m) reserva um bloco de m bytes e devolve um apontador para o bloco criado  calloc(size_t n, size_t m) reserva dinamicamente um array de n elementos com m bytes cada um. Devolve um apontador para a primeira posição do array criado  free(*ptr) liberta o espaço referenciado pelo apontador ptr. Este apontador pode ser o devolvido anteriormente por malloc ou calloc 17 Sistemas Multi-programados  Na linguagem C++ existem dois operadores:  new – para reserva de dinâmica de memória  delete – para libertação de memória Para além de manipulação da memória, estes operadores invocam construtores e destrutores.  Outras linguagens (e.g., java) utilizam garbage collectors (a reserva/manipulação de memória dinâmica é efectuada pelo interpretador/compilador) 18 Memória Virtual  Espaço de endereçamento virtual  Espaço de endereçamento que engloba a memória primária e secundária, tirando partido da sua dimensão pode ser muito superior à da memória RAM  O endereçamento virtual difere do swapping visto anteriormente – cada processo pode ter partes carregadas em memória principal, partes em memória secundária, ou em ambos os lados  Para gestão de memória virtual são habitualmente utilizados dois métodos:  Paginação – o mais utilizado (Linux e Windows)  Segmentação – pode ser utilizado com a paginação 19 Memória Virtual  Endereços reais  Endereços físicos que correspondem ao acesso aos dispositivos de uma forma directa  Endereços virtuais  Endereços utilizados internamente pelo sistema, e que não estão ligados aos dispositivos físicos de uma forma directa – um endereço virtual pode ser muito diferente de um endereço real  São convertidos em endereços reais através de estruturas e algoritmos nos quais intervém o S.O. e também uma unidade de hardware designada MMU (Memory Management Unit) 20 Memória Virtual  MMU (Memory Management Unit)  A função da MMU é converter endereços virtuais em endereços físicos  Notifica o sistema se for feito um acesso a um endereço virtual que não corresponde fisicamente à memória principal (page fault) CPU Controlador Memória de RAM Disco MMU Bus de endereços 21 Memória Virtual  Caracterização dos endereços Endereçamento real Endereçamento virtual Multi-programação Multi-programação Mono- programação Partições Partições Paginação Segmentação Misto fixas variáveis 22 Memória Virtual – Paginação  Paginação Método mais comum de gestão da memória virtual  Páginas (pages) O espaço de endereçamento virtual é divido em blocos de dimensão fixa designadas por páginas. A dimensão de cada página é uma potência de 2  Molduras (page frames) A memória principal é dividida em blocos com a capacidade de alojarem uma página – estes blocos designam-se por molduras ou page frames 23 Memória Virtual – Paginação  Paginação Espaço virtual RAM 512K 256K 448K 192K x 384K 128K x 320K 64K 256K 00K molduras 192K x 128K 64K x 00K páginas Endereço virtual Endereço físico 478K = 448K+30K 128K+30K = 158K 24 Memória Virtual – Paginação  Tabelas de páginas (Page Tables) t bits n bits m bits Página Deslocamento Endereço virtual Page Table 0 Descritor 0 1 Descritor 1 2 Descritor 2 3 Descritor 3 2n-1 Descritor 2n-1 Moldura Deslocamento Endereço real n' bits m bits t' bits (t' < t) 25 Memória Virtual – Paginação  Descritores  Bit de presença – Indica se a página se encontra carregada na memória principal ou não  Moldura – Índice da moldura (page frame) – os bits mais significativos do endereço base da moldura onde a página se encontra localizada  Protecção – Bits de protecção da página (e.g., read-only)  Controlo – Bits auxiliares para o funcionamento dos algoritmos de substituição de páginas Estrutura de um descritor moldura bit de presença protecção controlo 26 Memória Virtual – Paginação  Exemplo 0010 0110 1010 0001 0x26A1 (9889) Page Table 0000 1 101 0001 0 xxx 0010 1 110 0011 0 xxx 0100 1 100 0101 1 111 0110 1 010 0111 0 xxx 1000 0 xxx 1001 0 xxx 1010 1 001 1011 0 xxx 1100 0 xxx 1101 0 xxx 1110 1 000 1111 1 011 110 0110 1010 0001 0x66A1 (26273) 27 Memória Virtual – Paginação  Page faults  Quando é acedida uma página que não se encontra na memória principal, ocorre uma page fault  Uma page fault é uma excepção que causa bloqueio ao processo em questão  Inicia-se o de carregamento da página em falta, da memória secundária para a memória principal  Efectuam-se as alterações necessárias na page table, de modo a esta continuar consistente  Pode ser necessário transferir uma outra página para a memória secundária, de modo a libertar-se uma page frame – nesse caso corre-se o algoritmo de substituição de páginas 28 Memória Virtual – Paginação  Tabelas multi-nível  Cada processo tem associado ao seu espaço de endereçamento uma tabela de páginas  A tabela de páginas de cada processo tem que estar carregada em memória  Para minimizar o espaço em memória ocupado pelas tabelas de páginas, utilizam-se habitualmente tabelas multí-nivel  Guardam-se na memória uma tabela principal (directoria) e as tabelas dos restantes níveis, que contém os descritores das páginas que estão a ser utilizadas pelo processo  Estas tabelas têm uma dimensão muito mais pequena do que se fosse utilizado um esquema com um só nível 29 Memória Virtual – Paginação  Exemplo Tabelas de 2º Nível 0 1 Endereço Virtual (4G) 2 10 10 12 TP1 TP2 Deslocamento Tabela de 1º Nível (Directoria) 1023 0 0 1 1 2 2 1023 1023 0 1 2 1023 30 Memória Virtual – Paginação  TLB (Translation Lookaside Buffer)  Quando é efectuada uma conversão de um endereço virtual para endereço físico, é necessário consultar a page table correspondente  Como consequência da page table se encontrar também carregada em memória, então são feitos acessos extra à memória.  Para minorar, e muitas vezes eliminar, o desperdício de tempo feito por estes acessos, as MMUs contém geralmente uma espécie de cache para páginas, designada TLB 31 Memória Virtual – Paginação  Uma TLB mantém um conjunto de descritores das páginas acedidas mais recentemente  Esta táctica resulta porque cada processo tende a utilizar mais exaustivamente um pequeno conjunto de páginas  Tipicamente uma TLB tem espaço para 64 ou 128 descritores de páginas  Quando uma página é descartada da memória principal, é também libertada a entrada correspondente na TLB 32 Memória Virtual – Paginação  Algoritmos de substituição de páginas  O algoritmo ideal  Sempre que for necessária uma substituição de páginas, a que deveria sair será aquela que só será utilizada daqui a mais tempo  Este algoritmo não é realizável, pois os S.O.s não conseguem prever o futuro...  A aproximação é tentar descartar as páginas que são pouco utilizadas, ou que já não são utilizadas há muito tempo, na esperança de que não venham a ser utilizadas brevemente 33 Memória Virtual – Paginação  NRU (Not recently used)  Quando ocorre uma page fault, este algoritmo classifica as páginas carregadas em memória.  Para tal utiliza dois bits:  R (Referenced) – indica que a página foi acedida desde a última interrupção do relógio  M (Modified) – indica que a página foi modificada desde que foi carregada na memória principal  Estabelecem-se 4 classes diferentes, de acordo com R e M  Classe 0: R=0 e M=0  Classe 1: R=0 e M=1  Classe 2: R=1 e M=0  Classe 3: R=1 e M=1  A página a substituir será uma pertencente à classe mais baixa encontrada 34 Memória Virtual – Paginação  FIFO (First-in, first-out)  A página a substituir é a que se encontra carregada há mais tempo na memória principal  Algoritmo de fácil implementação, bastando ter uma lista com índices de páginas, com a mais antiga no topo e a mais recente no fim  À medida que as páginas vão sendo carregadas na memória, os seus índices vão também sendo acrescentados ao fim da lista mantida pelo algoritmo  Problema: a página que foi carregada há mais tempo pode estar a ser utilizada... 35 Memória Virtual – Paginação  Segunda chance  Algoritmo baseado no FIFO, mas que utiliza o bit de referência (R)  Antes de uma página ser descartada, analisa-se o bit R e, caso este se encontre a “1”, então é posto a “0”, mas a página não é descartada, analisando-se a próxima.  A página a descartar será a primeira que for encontrada com R=0 f e d c b a 0 0 1 0 1 1 bit R b a f e d 0 0 0 0 1 c é descartada 36 Memória Virtual – Paginação  Relógio  Semelhante ao algoritmo da segunda chance, mas a lista de páginas é circular  Deste modo ganha-se eficiência pois deixa de ser necessário retirar estruturas do topo da lista para as inserir no fim a a h 0 b h 0 b 1 1 1 0 g c g c 1 1 1 0 f d f d 0 e 0 0 e 0 1 1 37 Memória Virtual – Paginação  LRU (Least recently used)  A página a substituir será a que não é acedida à mais tempo  Para tal, guarda-se para cada página uma marca temporal com o tempo do último acesso  Teoricamente este algoritmo é o que efectua a melhor escolha na página a substituir  Bom desempenho a um custo elevado:  Na prática, este algoritmo obriga à existência de um temporizador extra (pois as interrupções do relógio são demasiado “lentas”)  Para além disso, exige bastante espaço para guardar as marcas temporais (e.g. 64 bits) sempre que uma página é acedida 38 Memória Virtual – Paginação  NFU (Not frequently used)  Algoritmo que tenta efectuar uma aproximação ao algoritmo LRU  Associado um contador a cada página carregada em memória, inicializado a zero quando a página é carregada  Sempre que ocorre uma interrupção do relógio, e para cada página, soma-se o valor do bit R ao contador  Problema: uma página muito acedida no início, mas que depois deixe de ser acedida fica com um valor elevado no contador, pelo que poderá persistir na memória 39 Memória Virtual – Paginação  Aging  Variante do algoritmo NFU, que tenta resolver o problema descrito anteriormente  Em vez de somar o bit R ao valor do contador, desloca-se o seu conteúdo para a direita com entrada série do bit R  Deste modo consegue-se que uma página muito acedida no passado, mas que já não está a ser utilizada, fique com o valor do contador a zero após algumas interrupções do relógio  Algoritmo com melhor relação custo/desempenho 40 Memória Virtual – Paginação  Thrashing  Um CPU actual executa cada instrução em menos de 1 nano- segundo  Quando ocorre uma page fault, o carregamento de uma página para a memória principal poderá demorar um tempo na ordem mili-segundos  O carregamento de uma página é cerca de 1.000.000 de vezes mais lento que a execução de uma instrução...  Quando um grupo de processos começa a gerar page faults a um ritmo muito elevado diz-se que se entrou numa fase de thrashing – esta situação deve ser evitada a todo o custo 41 Memória Virtual – Paginação  Working Set  O Working Set é o conjunto de páginas que estão a ser utilizadas por um processo  Se todo o Working Set de um processo está carregado em memória, então não ocorrem page faults  Tirando partido deste facto, existem algoritmos de substituição de páginas que funcionam tendo em conta o working set de um processo  A ideia será substituir páginas que não se encontrem dentro do working set de um processo 42 Memória Virtual – Paginação  Política de carregamento de páginas  Paginação a pedido (Demand paging) As páginas de um processo vão sendo carregadas à medida que ocorrem page faults – esta abordagem faz com que ocorram page faults inicialmente, até ser estabelecido o working set do processo  Paginação por antecipação (Prepaging) Antes do processo correr, o SO carrega para a memória um conjunto de páginas – a sua previsão do working Set 43 Memória Virtual – Segmentação  Outro método de gestão de memória virtual é a segmentação  A segmentação providencia diferentes espaços de endereçamento linear designados segmentos  Um segmento é um conjunto de endereços lineares desde 0 até um máximo  Segmentos diferentes podem ter dimensões diferentes  Um processo pode possuir diferentes segmentos 44 Memória Virtual – Segmentação  Com o tempo, o swapping e a libertação de segmentos origina fragmentação... Segmento 4 Segmento 4 Segmento 4 (10K) (10K) (10K) Segmento 3 Segmento 3 Segmento 6 (6K) (6K) (4K) Segmento 2 Segmento 2 Segmento 2 (6K) (6K) (6K) Segmento 1 (8K) Segmento 5 Segmento 5 Fragmentação (6K) (6K) tempo 45  Memória Virtual – Segmentação  A gestão de memória segmentada é feita com recurso a tabelas de descritores de segmentos Selector Deslocamento Endereço virtual Tabela de descritores 0 Descritor 0 1 Descritor 1 Base 2 Descritor 2 3 Descritor 3 Endereço Físico Estrutura de um descritor P Base Limite Protecção Controlo Bit de presença 46 Memória Virtual – Segmentação  Vantagens:  Fácil implementação de partilha de dados  Divisão de um processo em segmentos diferentes (e.g., código, heap, stack)  Múltiplos espaços de endereçamento linear por processo  Desvantagens:  Maior fragmentação da memória  Impossibilidade de se definirem segmentos maiores do que a memória física (a não ser que se utilize também paginação ou overlays) 47 Memória Virtual – Misto  De forma a tirar partido da paginação e da segmentação pode-se utilizar um esquema misto  A um esquema misto também se costuma dar o nome segmentação com paginação  Um esquema misto era utilizado no sistema operativo Multics  O processador Pentium também contém suporte para este tipo de esquema, mas os SOs Linux e Windows não tiram partido desta potencialidade 48 Memória Virtual – Misto  Vantagem:  Elimina as desvantagens de um esquema puro de segmentação, mas mantém as suas vantagens  Desvantagens:  Maior complexidade das MMUs  Mais acessos à memória para conversão de endereços virtuais em físicos 49 Gestão de Memória – UNIX  As primeiras versões do UNIX utilizavam gestão de memória baseadas em partições variáveis e swapping  Actualmente, praticamente todas as versões do UNIX utilizam memória virtual paginada  Processos responsáveis pela gestão de memória  page daemon – gere as page tables e o core map, e executa algoritmo de substituição de páginas  swapper – efectua as transferências de páginas entre a memória principal e secundária 50 Gestão de Memória – UNIX  Espaço de endereçamento dos processos  Dividido em 3 partes:  Segmento de texto – contém o código do programa, e nunca é alterado ao longo do tempo  Segmento de dados – pode crescer através da reserva dinâmica de memória  Segmento do stack – cresce e decresce ao longo do tempo, à medida que vão havendo chamadas a funções NOTA: não é utilizada segmentação, por isso estes segmentos correspondem a um conjunto de páginas  Dois processos diferentes podem partilhar o mesmo segmento de texto (se o programa executado for o mesmo) 51  Gestão de Memória – UNIX  Espaço de endereçamento dos processos Memória Processo A Processo B Stack Stack Dados Dados Espaço virtual Espaço virtual do processo A Texto Texto do processo B Molduras SO 52 Gestão de Memória – UNIX  Core Map  Estrutura com informações acerca das molduras (page frames)  Contém uma entrada por moldura  Tipicamente cada entrada do Core Map tem as seguintes informações  Índices da próxima moldura livre e da anterior  Nº de bloco em disco correspondente à página carregada  Índice para a process table do processo ao qual pertence a página carregada na moldura  Bit que indica se a moldura se encontra livre  Bit que indica se está a decorrer uma transferência de página da moldura para o disco (e vice-versa)  Bit que indica se a página carregada deve permanecer sempre na memória RAM 53 Gestão de Memória – UNIX  Tanto o Core Map como o núcleo (kernel) do sistema operativo permanecem sempre carregados na memória principal Memória Principal... Moldura 2 Moldura 1 Sempre carregados em memória principal Moldura 0 Core Map Kernel do SO 54 Gestão de Memória – UNIX  Algoritmo de substituição de páginas  Originalmente era utilizado o algoritmo do relógio a correr sobre o core map  À medida que as memórias foram crescendo em dimensão, verificou-se que este algoritmo perdia eficiência  O algoritmo foi modificado de modo a ter dois ponteiros (Two- handed clock)  O sistema tenta sempre manter um conjunto de molduras livres na memória principal (tipicamente ¼ das molduras) – o page daemon acorda quando não há molduras livres suficientes 55 Gestão de Memória – Linux  Esquema de paginação a pedido sem conceito de Working Set  Esquema de paginação com 3 níveis  na arquitectura Pentium, o nível do meio fica com apenas uma entrada – o que equivale a ter apenas 2 níveis no total  Nas arquitecturas Pentium Pro e posteriores podem ser utilizados os 3 níveis 56 Gestão de Memória – Linux  Algoritmo de substituição de páginas  Processo kswapd (daemon) – acorda de 1 em 1 segundo para ver se há suficientes molduras livres  O algoritmo de substituição procura diferentes tipos de páginas a substituir:  Páginas em cache – semelhante ao relógio  Páginas partilhadas – descarta as que não estão a ser utilizadas por nenhum utilizador  Restantes páginas – analisadas por ordem crescente de endereço virtual, com um funcionamento semelhante ao algoritmo do relógio  Processo bdflush (daemon) – efectua cópias de páginas modificadas para o disco 57 Agradecimentos Alguns slides e outros materiais utilizados nesta unidade curricular são:  Adaptações de elementos de edições anteriores  Adaptações de materiais disponibilizados na Internet ou associados a livros de texto 58