Aula 4 Infraestrutura de Sistemas Computacionais - Memória e Caches

INFRAESTRUTURA DE SISTEMAS COMPUTACIONAIS Sérgio Johann Filho Aula 04 2 MAPA DA AULA Neste material você tem uma linha do tempo com os principais acontecimentos das videoaulas organizados nas seguintes seções Momentos importantes da disciplina Conceitos e termos relevantes para o conteúdo da aula Para lembrar Dinâmicas exercícios interativos e infográficos Para exercitar Para ir além Curiosidades personalidades e entretenimento Esta é uma versão simplificada do Mapa da Aula para impressão Os recursos interativos disponíveis no material não funcionarão nesta versão Para uma experiência mais enriquecedora acesse a versão completa do Mapa da Aula na aba AULAS 3 AULA 4 PARTE 1 Considerando um contexto no qual um programa precisa ser trazido do armazenamento secundário ou seja do disco para a memória e alocado em um processo para que possa ser executado o professor explica que a memória principal e os registradores configuramse como os únicos meios de armazenamento que a CPU consegue acessar diretamente A memória possui um tempo de acesso de muitos ciclos dezenas ou centenas dependendo da tecnologia utilizada para implementar essa memória Sendo assim caso não existisse uma camada intermediária mais rápida entre a memória principal e a CPU as caches o professor nota que o processador ficaria paralizado enquanto a memória é acessada O acesso aos registradores que é um mecanismo implementado no hardware tem como objetivo manter o estado de execução da CPU corrente Diferentemente da memória os registradores dependendo da implementação possuem tempo de acesso de pelo menos 1 ciclo de máquina como pontua o professor não de relógio Para que o sistema operacional possa intervir em casos de problemas na execução dos programas é necessário a existência de mecanismos de hardware e de sistema operacional de proteção de memória Contexto Entre a memória e a CPU há um bloco de hardware que compreende dois registradores que definem um espaço de endereços lógicos ou possíveis que um determinado processo gerará a partir do processador quando este estiver em execução Esses endereços lógicos precisam estar dentro de uma faixa de valores mínimo e máximo configurada pelo sistema operacional que estabelece os valores que um programa pode acessar Sendo assim a CPU precisa verificar cada acesso à memória gerado por um programa de usuário para certificarse de que este acesso está de fato entre os valores estabelecidos de modo semelhante às figuras abaixo Mecanismos de proteção registradores baselimite A primeira parte da aula irá tratar sobre o conceito de memória real mais especificamente sobre o problema básico de alocação de recursos Com relação ao tema central os seguintes tópicos serão abordados Gerência de memória real física Registradores auxiliares baselimite Diferenciação do endereçamento lógico e físico MMU unidade genérica de memória Carga e ligação dinâmica Introdução 0441 1028 1413 4 Os programas armazenados em disco prontos para serem trazidos para a memória e então executados formam uma fila de entrada Cada processo é posicionado nela de acordo com a sua prioridade Quando os programas não possuem nenhum suporte para relocação são carregados a partir do endereço 0 é no entanto inconveniente que todos sejam compilados e relocados para o endereço 0 pois como explica o professor nesse caso seria impossível termos um sistema operacional que implementasse a multiprogramação ou seja permitisse a troca de processos de forma dinâmica Os endereços são representados de formas diferentes durante os estágios de execução de um processo em uma abordagem há a relocação do código compilado a partir do código fonte para funcionar em endereços específicos em outra o ligador ou o carregador reloca o programa para trabalhar em uma determinada região Assim o programa poderia ser compilado para trabalhar a partir do endereço 0 e o sistema operacional durante a carga faria a relocação desses endereços para um endereço a partir de um deslocamento Através de um mecanismo de relocação seria então possível termos diversos processos compartilhando a mesma memória física desde que os endereços sejam regerados durante a carga dos processos pelo sistema operacional Atribuição de endereços Essa atribuição pode ser implementada de três formas Em tempo de compilação conhecese em um primeiro momento o espaço de endereços então o programa é compilado para funcionar nesses endereços Sobre ela o professor comenta que ainda que seja uma forma mais primitiva não está obsoleta tende a funcionar bem quando não é necessário carregar novos processos no sistema operacional na medida em que há um conjunto de aplicações que serão executadas sempre É utilizada principalmente para a implementação de aplicações embarcadas Atribuição de instruções e dados à memória Caso tivesse de ser realizado por um software o professor explica que esse processo seria muito mais custoso Por isso normalmente temse um bloco de hardware chamado MMU unidade de gerência de memória que implementa esse mecanismo Desta maneira o processo pode ser realizado em paralelo com a execução da aplicação na qual a CPU está realizando a verificação 2014 1809 5 Sistemas computacionais completos e independentes mais simples que um computador de propósito geral os desktops inseridos dentro dos microprocessadores dos equipamentos eletrônicos desempenhando uma função ou servindo a uma aplicação específica Sem eles os dispositivos precisariam ser comandados manualmente durante todo o tempo de uso O núcleo destes sistemas são os microcontroladores isto é unidades de processamento bastante flexíveis em termos de sua utilização e facilidade de aplicação Devido ao seu tamanho compacto baixo custo e aspectos de design simplificado estes sistemas são muito populares estando presentes desde os equipamentos mais simples até os mais complexos como exemplo podemos pensar nos smartphones e até mesmo nos reatores nucleares e os mísseis Sistemas embarcados ou Embedded Systems Em tempo de carga mecanismo no qual se o endereço de memória for desconhecido será necessário gerar código relocável Na opinião do professor é a forma mais difícil de se implementar além de ser a mais ineficiente pois além de ser relocável o código precisa ser traduzido durante a sua carga Em tempo de execução mecanismo no qual se o processo pode ser movido durante sua execução de um segmento de memória para outro a atribuição é atrasada até o momento da execução Esta seria a forma mais flexível para um sistema que suporte a execução de múltiplos processos As primeiras etapas compreendem a compilação desse programa e a geração de códigoobjeto Esse código pode ser usado para a montagem de binários O binário final pode ser carregado pelo sistema operacional junto com as bibliotecas de sistema que por sua vez podem ser compartilhadas entre diversos processos o que reduz a demanda em termos de memória Com o binário final montado o processo pode carregar dinamicamente ainda outras bibliotecas seja como for o processo já estará relocado e mapeado para uma região de memória física neste momento Processamento de um programa de usuário Endereços lógicos também chamados de endereços virtuais são os endereços efetivamente gerados na CPU como resultado de processos executados por ela O espaço de endereços lógicos consiste no conjunto de todos os endereços lógicos gerados por um programa em execução Esses endereços como nota o professor devem estar compreendidos entre as regiões permitidas para a execução daquele processo Espaço de endereços lógicos e físicos 2201 2318 6 Já os endereços físicos são os endereços traduzidos por uma unidade de gerência a partir de endereços virtuais de memória Ao serem traduzidos podem ser vistos pela unidade de memória O espaço de endereços físicos consiste no conjunto de todos os endereços gerados por um programa em execução A Unidade de Gerência de Memória Memory Management Unit MMU é um dispositivo de hardware que traduz endereços virtuais para endereços físicos dinamicamente em tempo de execução Sua forma mais simples de aplicação consiste na utilização de apenas dois registradores base deslocamento onde um valor base é adicionado a cada endereço lógico gerado por um processo deslocamento Apesar disso como nota o professor esse mecanismo tenha uma série de limitações geralmente quando há uma unidade de gerência de memória funcional outros recursos adicionais são necessários como por exemplo uma TLB que em essência servirá como um acelerador para a tradução de endereços Um programa de usuário lida com endereços lógicos ou seja consistiria em um mapa de endereços puramente virtual que só existe no contexto de execução daquele processo Ele nunca enxerga por assim dizer endereços físicos estes são atendidos pela memória que de todo modo desconhece o significado da sequência de operações que é gerada pela MMU Unidade de Gerência de Memória MMU Nesse mecanismo associado a cada rotina processo biblioteca haverá um registrador de deslocamento O professor o considera interessante na medida em que permite uma maior flexibilidade na utilização da memória Relocação dinâmica com registrador de deslocamento Se for necessário uma recarga de outro processo essa série de passos será seguida novamente Na imagem a seguir podemos ver uma ilustração das etapas deste processo Dispositivo de hardware implementado a partir de uma pequena memória associativa que fica integrada na MMU de um processador Destinase a facilitar a tradução de endereços lineares em endereços físicos evitando a consulta à tabela de páginas localizada na memória TLB 2441 2618 7 Todas as rotinas são mantidas em disco em formato relocável por exemplo compiladas para executarem a partir do endereço 0 quando o sistema operacional realizar a carga desta rotina ele procurará por um lugar onde essa rotina possa ser mapeada e então irá configurar um registrador de relocação Assim toda a referência a essa rotina compreenderá o endereço base definido pelo registrador de relocação acrescido de um deslocamento o próprio endereço lógico gerado pela CPU Provém da necessidade de implementar a ligação de programas de modo que possam ser dinamicamente carregados ou se estiverem definidos de maneira estática ao menos possam ser traduzidos Carga dinâmica Conjunto de bibliotecas e códigos de programas que são combinados pelo carregador em uma imagem final Ligação estática Processo mais flexível que permite que em tempo de execução o processo de ligação e carga da aplicação seja prorrogado até o momento em que dado processo é solicitado Ligação dinâmica O professor explica ainda que há a possibilidade de compartilhamento de código de modo que não somente os processos poderão utilizar esse mecanismo mas também as bibliotecas compartilhadas entre processos Para exercitar Assinale a definição correta para o conceito abaixo Para exercitar Reflita sobre a afirmação abaixo a partir dos conteúdos estudados nesta parte da aula e assinale o retângulo correspondente A atribuição de instruções e dados à memória em tempo de compilação consiste em uma implementação primitiva e já obsoleta não sendo mais usada em nenhum sistema 2750 Unidade de Gerência de Memória Dispositivo de hardware que traduz endereços virtuais para endereços físicos dinamicamente em tempo de execução Dispositivo de hardware implementado a partir de uma pequena memória associativa que fica integrada em uma parte do processador Camada intermediária mais rápida entre a memória principal e a CPU Verdadeiro Falso 8 AULA 4 PARTE 2 Nesta parte o professor abordará o swapping e em seguida a alocação contínua a fragmentação e a segmentação mais precisamente Como a alocação contínua pode ser implementada dentro de um sistema operacional O que será necessário em termos de capabilidade de hardware para suportála Suas limitações fragmentação interna e externa Segmentação de diferentes partes de um programa como uma forma mais interessante de flexibilizar o modo como a memória pode ser alocada através de diferentes processos Introdução Consiste na possibilidade de um processo que não está sendo solicitado naquele momento ser transferido swapped temporariamente da memória principal para a secundária ou backing store para então voltar à memória principal quando necessário Swapping ou troca de processos I Disco rápido grande o suficiente para acomodar cópias de imagens de todos os usuários e seus processos da memória principal Memória secundária Variação da política de troca de processos usada para algoritmos de escalonamento baseados em prioridade Ou seja um processo de baixa prioridade é transferido para a memória secundária a fim de que um outro processo de prioridade mais alta possa ser carregado e executado Roll out roll in O swapping não vai ser usado apenas quando um novo processo for carregado ele pode ser usado dinamicamente durante a execução de múltiplos processos já mapeados pelo sistema operacional A imagem a seguir ilustra o funcionamento deste mecanismo Swapping II 0141 0208 0355 9 O professor destaca que em alguns sistemas os processos que não modificam a memória ou seja não realizam nela operações de escrita serão os alvos ideais para o swapping Isso seria assim porque se não forem modificados em memória as suas cópias existentes no disco serão idênticas àquelas que estão na memória de modo que não haverá necessidade de que todo o processo volte ao disco apenas as informações referentes ao contexto de execução os registradores Na medida em que a memória secundária seria mais lenta que a principal o uso do swapping exerce uma influência negativa no sistema operacional Nesse sentido a maior parte do tempo gasto em uma troca de processos consiste no tempo de transferência que é diretamente proporcional à quantidade de memória transferida e também ao desempenho do próprio sistema de armazenamento secundário Esse tempo pode eventualmente ser reduzido se a quantidade de memória referenciada para o swap for conhecida nesse caso apenas parte do processo precisará ser copiado Seja como for segundo o professor não deixa de ser um mecanismo interessante na medida em que permite que haja uma quantidade maior de processos em execução sem demandar mais memória Sistemas iOS e Android Forma de alocar memória de modo a disponibilizála para processos que necessitam ser alocados dinamicamente Nesses casos a memória principal será dividida em duas partes Parte na qual o sistema operacional será alocado Geralmente situase em na região baixa dos endereços juntamente com o vetor de interrupções endereços que mantém referências a rotinas que podem ser invocadas em função dos eventos que acontecem em um sistema computacional Alocação contígua de memória Diversos sistemas modernos como UNIX Linux e Microsoft Windows apresentam o swapping em versões modificadas neles normalmente o mecanismo estará desabilitado só sendo iniciado quando for ultrapassado determinado limite de memória utilizada nesse caso será desabilitado novamente quando a demanda for reduzida O professor destaca ainda que o swapping não é ao menos normalmente suportado por dispositivos móveis que tendem a ser baseados em um armazenamento do tipo flash Espaço limitado Reduzido número de escritas Reduzida velocidade de transferência Os sistemas mobile predominantes possuem outros métodos para lidar com uma eventual falta de memória Swapping III 1527 0719 10 Quando o sistema iOS percebe que existe pouca memória livre ele solicita para que as aplicações voluntariamente finalizem Caso não haja liberação por parte das aplicações o sistema operacional intervém e finaliza determinadas aplicações Já o sistema Android frente à mesma circunstância finaliza diretamente algumas aplicações Antes disso porém o sistema salva o contexto dos registradores assim a impressão que o usuário tem ao acessar novamente esta aplicação é que ela não havia sido finalizada em primeiro lugar Parte na qual os processos de usuário serão alocados Geralmente situase em uma região mais alta que poderá ser alocada dinamicamente em pequenas regiões Para a implementação da alocação contígua o professor explica que são utilizados registradores de relocação cujo objetivo é proteger os acessos gerados por um processo de modo que um processo não interfira no outro O registrador base contém o valor do menor endereço físico a partir do qual o processo irá acessar a memória O registrador limite contém o tamanho do intervalo dos endereços lógicos A unidade de gerência de memória realizará a tradução do endereço lógico para físico de forma dinâmica Uma versão simples da alocação contígua se dá da seguinte forma O professor explica que seria possível ter a alocação de múltiplas partições de maneira que múltiplos processos poderiam ser executados em um mesmo espaço de endereços Nesse contexto precisaria haver em termos de regiões alocadas um pool geral de espaços de endereços que poderá ser quebrado em várias parcelas que por sua vez poderão ser utilizadas para a eficiência ou seja para que cada processo aloque apenas a quantidade necessária de memória para poder funcionar O professor indica que é possível observar durante o tempo de vida de um sistema que os processos são carregados existem por um tempo determinado e então terminam Ao terminarem passam a existir regiões não ocupadas chamadas de buracos que podem estar espalhadas pela memória fragmentando o espaço de endereços Quando um novo processo for carregado é alocado na memória um buraco cujo tamanho é suficiente para acomodálo Alocação contígua particionada 1824 11 O problema que nós temos na alocação particionada é que se os processos forem dinamicamente carregados e finalizados vai chegar um determinado momento onde a memória estará fragmentada como se fosse um queijo suíço nós teremos uma grande quantidade de memória livre porém essa quantidade de pequenas regiões estará toda fragmentada Quando há uma alocação particionada então os sistemas operacionais mantêm duas informações importantes As partições alocadas endereços base e limite para cada uma das partições Uma estrutura de dados mantendo todos os buracos livres na memória física Considerando que existam várias regiões livres dentro de um sistema com memória que permite a alocação dinâmica há o problema de qual estratégia utilizar para encontrar o buraco de tamanho suficiente para que uma determinada aplicação possa executar Problema da alocação dinâmica É realizada uma varredura da lista de blocos livres à procura do primeiro que tenha memória suficiente para satisfazer a solicitação requisitada pelo processo Segundo o professor esta seria a estratégia mais rápida embora não seja aquela que geraria a menor fragmentação Firstfit Procura o menor bloco livre que ainda assim seja grande o suficiente para suportar o processo que está sendo carregado Essa seria a estratégia que menos desperdiça memória além de alocar o bloco com o tamanho mais próximo do solicitado Bestfit Procura o maior bloco livre e ali tenta alocar nele o processo que está sendo carregado Deve ser utilizada como explica o professor apenas em casos bastante específicos na medida em que seria inferior às demais em termos de velocidade e utilização de armazenamento Worstfit Fragmentação Ocorre quando há espaço de memória suficiente para satisfazer uma requisição mas este espaço não é contíguo Fragmentação externa Geralmente acontece quando são alocados blocos de um tamanho fixo ou quando se aloca um bloco de tamanho maior ao que está sendo realmente solicitado Nesses casos a memória alocada pode ser ligeiramente maior que a memória solicitada gerando um desperdício Fragmentação interna A fragmentação externa pode ser reduzida através da compactação que irá deslocar os blocos de memória de maneira a colocálos juntos em um grande bloco único fazendo com que os blocos anteriormente espalhados passem a existir em uma região contígua 2328 2104 12 No entanto a compactação só é possível se a relocação for feita em tempo de execução Além disso ela possui uma série de complicações com relação a problemas como por exemplo problemas de entradasaída enquanto a compactação for realizada o sistema realizará entradas e saídas em demasia e como consequência ficará preso realizando a compactação por um longo tempo Para amenizar este tipo de complicação existe uma estratégia mais elaborada de armazenamento a paginação que será explorada pelo professor nas próximas partes da aula Esquema utilizado para a gerência de memória que suporta a visão do usuário sobre a memória Ele demanda um suporte especial do hardware para funcionar Através dele um programa será alocado na memória como uma coleção de segmentos cada um dos quais será uma unidade lógica que por sua vez compreenderá diferentes informações tais como código e funções de biblioteca A ideia do uso da segmentação é manter os segmentos em memória de maneira que eles possam ser compartilhados por múltiplos processos aproveitando melhor assim a memória A visão do usuário de um programa segmentado pode ser ilustrada pela imagem a seguir Segmentação No que diz respeito ao que é necessário que o hardware suporte para viabilizar a aplicação desse mecanismo Quebrar o endereço lógico gerado pela CPU em duas partes ou seja transformálo em uma tupla número do segmento deslocamento O sistema operacional deverá manter uma tabela de segmentos que mapeará os endereços físicos de duas dimensões o endereço base que contém o endereço físico inicial onde o segmento reside em memória e o endereço limite que especifica o tamanho do segmento Assim será possível verificar se o acesso É válido no contexto do segmento Será relacionado a uma posição ou outra da memória Em cada entrada da tabela pode ser mantida uma informação sobre os privilégios de leitura escrita e execução de cada segmento Como exemplo o professor indica que não faz sentido permitir que o processo realize operações de escrita em um segmento de código Arquitetura para segmentação 2846 2647 13 Esses segmentos serão então mapeados para partições que são alocadas dinamicamente no espaço físico de endereços assim cada uma delas poderá ser mapeada para um número de segmento que será utilizado como uma referência para a visão lógica sobre o programa em questão Para que possamos entender como a segmentação poderia ser implementada em um sistema real o professor usa a seguinte imagem Associe os tipos de fragmentação na primeira coluna a sua devida caracterização na segunda Clique nas opções e identifique a resposta correta de acordo com sua cor correspondente Para exercitar Considere as afirmações abaixo e selecione aquelas que seriam verdadeiras com respeito ao mecanismo de swapping Para exercitar Fragmentação Interna Geralmente acontece quando são alocados blocos de um tamanho fixo ou quando se aloca um bloco de tamanho maior ao que está sendo realmente solicitado Ocorre quando há espaço de memória suficiente para satisfazer uma requisição mas este espaço não é contíguo Fragmentação Externa Em alguns sistemas os processos que não modificam a memória serão os alvos ideais para o mecanismo Na medida em que a memória secundária seria mais rápida que a principal o uso do swapping exerce uma influência positiva no sistema operacional Normalmente é suportado por dis positivos móveis 14 AULA 4 PARTE 3 O tema da terceira parte da aula será a paginação mais precisamente como ela pode ser utilizada como uma solução mais genérica para virtualizar a memória Com relação a este conteúdo o professor abordará os seguintes pontos Modelo básico memória lógica virtual e física Estrutura de dados elementar tabela de páginas Mecanismos de proteção Mecanismos de compartilhamento de páginas Introdução Tratase da implementação de um espaço de endereços físicos de um processo que pode ser alocado de forma não contígua Com ela o processo pode alocar a quantidade de memória necessária quando ela estiver disponível e de acordo com a sua necessidade específica reduzindo assim o desperdício de memória por fragmentação e evitando os problemas de alocação de partições variáveis Esse mecanismo divide a memória física em blocos de tamanho fixo uma potência de 2 geralmente entre 512 bytes e 16 megabytes chamados de molduras ou frames e a memória lógica em blocos de tamanho igual às molduras chamados de páginas ou pages Outras características da paginação Mantém um mapa de todas as molduras livres indicando todas as partes da memória física que estão aptas para receber páginas Para executar um programa cujo tamanho corresponda a N páginas será necessário alocar N molduras livres para carregálo Mantém uma tabela de páginas para traduzir endereços lógicos para endereços físicos O professor explica que em essência uma tabela de páginas referencia uma determinada moldura onde a informação deverá ser armazenada Paginação O endereço lógico será dividido em duas partes Número da página p utilizado como um índice em uma tabela de páginas que contém o endereço base de cada página na memória física Deslocamento da página d é combinado com o endereço base para definir o endereço físico de memória que será enviado a ela para acesso à informação Considerando essas partes o professor mostra o seguinte esquema Para um espaço de endereços com 2m endereços e tamanho de página 2n Esquema para a tradução de endereços na paginação 0145 0154 0641 15 Pode ser expandido para suportar o modelo de memória virtual também em armazenamento secundário swap que também será dividido em páginas Assim como outros mecanismos a paginação também possui certas limitações uma delas está relacionada à fragmentação interna nas páginas ou molduras Seja como for o professor aponta que como as molduras e as páginas são pequenas o desperdício causado por essa fragmentação será mínimo Ademais em razão de possuírem um formato fixo as páginas e molduras não sofrem fragmentação externa Hardware para paginação Em sua análise da imagem acima o professor observa a importância de que a tabela de página seja gerenciada pelo sistema operacional para que ela seja mantida em memória e acessada de maneira eficiente caso ela precisar ser acessada fisicamente toda vez um processo chamado page walk isso demandará um desempenho abismal Modelo de paginação para memória lógica e física Esse modelo nos permite notar que o acesso pode ser realizado de forma aleatória ou seja as páginas poderão estar em qualquer posição da memória física que não esteja ocupada Cálculo da fragmentação interna de uma página Supondo que o tamanho da página seja 2kB 2048 bytes e o tamanho do processo seja 72766 bytes Seriam necessárias 35 páginas 1086 bytes aproximadamente meia página 1209 0959 0828 16 Por ser uma estrutura que precisa ser acessada eficientemente normalmente a tabela de páginas será mantida em memória e haverá além disso Um registrador base que irá referenciála para que o hardware consiga acessála rapidamente Exemplo PTBR page table base register Um registrador que indica o seu tamanho Exemplo PTLR page table length register Neste esquema cada acesso que pode ser uma instrução ou dados por parte do processador requer outros dois à memória Um para referenciar a tabela de páginas Outro para acessar a instrução ou os dados Isso porém gera um problema o desempenho dos programas é reduzido à metade Para solucionálo podemos acoplar a unidade de gerência de memória uma entrada chamada TLB ou translation lookaside buffer Ela é essencialmente uma cache de endereços que mantém as entradas mais recentes da tabela de páginas de sorte que esta tabela não precise ser acessada sempre Em uma falha na TLB como por exemplo se houver uma referência e a informação não for encontrada em uma entrada na TLB para tradução o valor será carregado da tabela de páginas para a TLB Implementação da tabela de páginas Supondo que o tamanho da página seja 2kB 2048 bytes e o tamanho do processo seja 72766 bytes Seriam necessárias 35 páginas 1086 bytes aproximadamente meia página Cálculo da fragmentação interna 2048 tamanho da página 1086 valor restante 962 bytes de fragmentação O caso médio de fragmentação seria metade do tamanho de uma moldura Para minimizar a fragmentação molduras de tamanho menor são desejáveis no entanto considerando que para cada moldura há uma entrada na tabela de páginas se tivermos molduras menores teremos por consequência um número maior de páginas molduras e entradas na tabela de páginas Com isso mais memória será utilizada e mais tempo será gasto realizando buscas por informações na tabela Algumas podem ser utilizadas para armazenar outras informações referentes a processos como informações de proteção Por serem muito caras por demandarem uma grande área em termos de recursos para serem implementadas no hardware são tipicamente pequenas de 64 a 1024 polegadas isso não é um grande problema como explica o professor na medida em que os acessos seguirão o princípio de localidade Sobre as TLBs 1456 1700 17 Vejamos um sistema de paginação em hardware com TLB Será possível compartilhar código e dados o que permite uma redução na quantidade de memória necessária para executar múltiplos processos Nesse sentido o professor explica que muitas das aplicações que estão em execução em um sistema operacional realizam chamadas às mesmas rotinas ou bibliotecas sendo assim é do interesse do sistema manter o compartilhamento de algumas páginas de forma que seja necessário manter apenas uma cópia física em memória Páginas compartilhadas Qualquer violação na proteção ou na validade resultará em uma exceção causando uma chamada ao sistema operacional Como exemplo o professor aponta que no caso de uma violação na validade o sistema operacional gera uma falha de segmentação que tem por consequência a finalização da aplicação que gerou a violação É implementada por meio da associação de bits de proteção à cada moldura indicando se o acesso será permitido apenas para leitura ou também para escrita Geralmente cada entrada da tabela de páginas terá um bit de validade associado à ela uma página será considerada válida se estiver associada ao espaço de endereços lógicos de um processo Proteção de memória 2245 2036 18 AULA 4 PARTE 4 Nesta parte da aula o professor segue tratando do mecanismo de paginação focando agora nos seguintes pontos Estrutura da tabelas de páginas Tabelas de páginas hierárquicas Conceito de função hash Tabelas de páginas indexadas Tabelas de páginas invertidas Introdução Para uma tabela de páginas a estrutura de dados pode ser utilizada de maneira linear como vimos na parte anterior da aula caso o espaço de endereços seja muito grande por exemplo de 64 bits no entanto este método pode ser inviável Estrutura da tabela de páginas Este modelo consiste em quebrar o espaço de endereços lógicos em múltiplas tabelas de páginas assim poderíamos ter uma tabela chamada diretório e as demais seriam usadas como referências a partir dela Fazendo isso a própria tabela de páginas poderia ser paginada o que seria vantajoso na medida em que poderíamos manter apenas parte da tabela de páginas em memória Uma maneira simples de implementála caso o espaço de endereços não seja tão esparso é manter a tabela de páginas em dois níveis Tabelas de páginas hierárquicas Tabelas de páginas hierárquicas de dois níveis 0636 0534 0209 0205 19 No caso de uma tabela de páginas semelhante à imagem acima poderíamos ter a seguinte configuração Espaço de endereços lógicos em uma máquina de 32 bits com páginas de 4kB dividido em Um número de página 20 bits Um deslocamento 12 bits Como a tabela de páginas é ela mesma paginada o número da página seria dividido em campos adicionais de maneira que um endereço físico possuiria a seguinte forma Onde p1 é um índice referente à tabela de páginas externa e p2 é um deslocamento na página da tabela de páginas interna Já o esquema de tradução das tabelas de páginas hierárquicas seria representado pelo esquema abaixo No caso de um espaço de endereços maior de 64 bits por exemplo até mesmo um sistema de paginação em dois níveis seria insuficiente dado que demandaria um grande espaço de memória Uma solução possível seria adicionar uma segunda tabela de páginas externa tendo assim uma tabela de páginas hierárquica em três níveis Paginar um sistema com espaço de endereços consideravelmente amplo se tornará algo bastante complexo caso seguíssemos quebrando a tabela de páginas em múltiplos níveis no caso da paginação em três níveis possivelmente quatro acessos à memória seriam necessários para obter uma tradução de endereços Considerando este ponto o professor indica que teríamos de pensar em outras estruturas de tabelas de páginas como a tabela de páginas indexada ou a tabela de páginas invertida Paginação em três níveis Tabelas de páginas indexadas com hashes Tabelas de páginas utilizadas comumente em sistemas com espaços de endereços maiores que 32 bits Nestes casos o número da página será atribuído por meio de uma função hash na tabela de páginas Uma tabela deste tipo permite que uma corrente ou lista de elementos que compartilham a mesma entrada isto significa de acordo com o professor que embora possamos resumir a quantidade de entradas na tabela de páginas cada uma delas será o início de uma lista a ser percorrida 1233 1520 20 Cada um dos elementos contém o número de página virtual o valor da moldura mapeada e uma referência para o próximo elemento da corrente Na corrente os números de páginas virtuais são comparados em busca de uma coincidência se ela for encontrada o endereço da moldura será extraído No caso de um espaço de endereços de 64 bits o modelo é chamado de tabelas de páginas agrupadas ou clustered e funciona de modo semelhante com a diferença de que cada entrada fará referência a diversas páginas ao invés de uma Isso simplifica ainda mais a construção da tabela em termos de memória utilizada A arquitetura Intel IA32 As CPUs Pentium 54 são arquiteturas de 32 bits nas quais há suporte para segmentação e segmentação com paginação Por processos é possível haver até 16k 1638 segmentos cada um dos quais pode ter 4GB de espaço 232 bytes Antes de passar à exposição sobre projetos de tabelas de páginas mais flexíveis para o atendimento de sistemas que possuem um espaço de endereços muito grande o professor define o conceito de função resumo ou hash que é usado pelas tabelas de páginas indexadas como base para a indexação Tratase de um algoritmo que traduz dados de comprimento variável para dados de comprimento fixo A entrada para uma função hash será um valor e como saída será retornado um código para o valor Os valores retornados por esta função podem ser chamados das seguintes formas Valores hash Códigos hash Somas hash ou hash sums Checksums Hashes O professor explica que esta função será considerada como sendo de boa qualidade quando a partir de um determinado valor for gerada uma sequência de bits que possui um algoritmo de dispersão de alta qualidade ou seja para uma quantidade pequena de modificação teremos um algoritmo de dispersão que gerará hashes com valor praticamente aleatório Função resumo hash 1340 21 Ao invés de cada processo ter a sua própria tabela de páginas e manter o controle de todos os possíveis endereços lógicos a tabela de páginas invertida mantém o controle dos endereços físicos assim haverá apenas uma tabela na qual haverá uma entrada para cada moldura de memória Cada entrada estará associada à referência à proteção de uma moldura e ao endereço virtual da página nela armazenada Tabelas de páginas invertidas Esse modelo permite uma redução da quantidade de memória necessária para manter a tabela contudo há um aumento no tempo de busca em comparação aos demais modelos dado que será necessário procurar uma referência na tabela de páginas inteira Para solucionar este problema o professor explica que seria possível utilizar uma função hash limitando a busca a uma ou poucas entradas na tabela Se essa função não for usada o modelo pode ser viável ao implementarmos uma TLB Nessa arquitetura a tabela é dividida em duas partições A primeira possui até 8k segmentos privados do processo e é também conhecida como tabela local de descritores LDT local descriptor table A segunda possui até 8k segmentos compartilhados com todos os processos e é também conhecida como tabela de descritores global GDT global descriptor table Quando a CPU gera um endereço lógico ele é dividido em três campos tal como a imagem abaixo s número do segmento g indica se o segmento está na GDT ou na LDT p informações de proteção O endereço linear é fornecido à unidade de paginação que por sua vez gera o endereço físico na memória principal Essa unidade compreende o equivalente a um MMU Abaixo é possível ver como funciona a tradução dos endereços nessa arquitetura A Intel especificou ainda para esta arquitetura uma série de extensões para o endereço de página chamada de Intel IA32 PAE Ela permite que sejam criados sistemas de paginação para uma quantidade maior de memória Nesse caso a paginação é implementada em um esquema com três níveis os dois bits mais significativos referemse a uma tabela de referências page directory pointer table 1905 22 AULA 4 PARTE 5 Na última parte da aula o professor falará sobre a memória virtual mais precisamente como ela é implementada em um sistema operacional Com relação a este conteúdo os seguintes tópicos serão abordados Espaços de endereços virtuais Implementação de um processo de paginação sob demanda Falhas de página Compartilhamento de memória Algoritmo para substituição de página Arquivos mapeados em memória Introdução Para que seja possível executar uma aplicação seus dados e seu código devem estar mapeados fisicamente na memória seja como for raramente são utilizados todos os dados ou todo o código de uma aplicação durante a execução códigos de erro subrotinas não comuns e estruturas de dados grandes são exemplos de informações que não precisam ser carregadas a todo momento Considerando isso podemos pensar na possibilidade de executar um programa parcialmente carregado de forma que somente as informações necessárias a cada momento da execução de uma aplicação estarão fisicamente na memória sem perdermos em todo caso a informação de contexto ou seja da relação entre a informação que está em memória e aquela que está armazenada fisicamente em disco Neste cenário o professor explica que o programa em questão não será mais limitado pelo tamanho da memória física mas sim pela quantidade de molduras contendo as páginas que estão sendo necessárias naquele dado momento da execução Na medida que uma quantidade menor de memória será necessária ao longo da execução desta aplicação haverá mais memória disponível para que outros programas possam executar em paralelo Isso faz com que seja possível aumentar a utilização da CPU e o número de processos completados throughput sem com isso haver um aumento do tempo de resposta ou de compleção Contexto de aplicação Consiste nas palavras do professor na separação da memória lógica do usuário da memória física Ela pode ser implementada por paginação sob demanda ou segmentação sob demanda A memória virtual compreende então um espaço de endereços virtuais que consiste em uma visão lógica de como um processo é armazenado na memória Esse espaço geralmente inicia no endereço lógico 0 e seus endereços são referências a endereços contíguos que seguem até o final do espaço de endereços definido pelo processo Na memória virtual o espaço de endereços lógicos é maior que a memória física Conceito de Memória Virtual 0202 0217 0644 23 Outras vantagens O mecanismo de swap só será utilizado quando realmente for necessário O espaço de endereços lógicos pode ser muito maior que a memória física Permite que espaços de endereços sejam compartilhados entre diversos processos Permite a criação mais eficiente de processos Ao analisar a imagem o professor nota que a memória virtual não é usada somente para que seja possível ter uma maior quantidade de programas em execução mas também para permitir que os programas sejam executados da maneira mais eficiente possível considerando a memória disponível Isso não impede que seja possível ter uma quantidade maior de memória física e como consequência um melhor desempenho do sistema o ponto seria que o modo mais agressivo de se explorar este desempenho seria a partir da memória virtual De modo geral é composto por quatro segmentos principais O segmento do código ou texto que inicia pelo endereço mais baixo O segmento dos dados que contém os dados alocados estaticamente O segmento heap que é usado para a alocação dinâmica de memória Assim se as aplicações solicitam dinamicamente a alocação de memória este segmento irá crescer em direção ao endereço mais alto O segmento da pilha que cresce em direção contrária isto é do endereço mais alto para o endereço mais baixo O professor indica que há ainda um espaço não utilizado um buraco que é uma região de endereços esparsos onde há um pouco de código alguns dados e pequenas regiões de pilha e heap préalocadas Sobre o espaço de endereços virtuais Uma abordagem possível de implementação da memória virtual por paginação seria trazer o processo inteiro para a memória em tempo de carga De acordo com o professor não seria necessariamente a abordagem mais eficiente mas pode ser utilizada por exemplo para explorar a localidade espacial quando assumese que as próximas páginas referentes ao mesmo processo serão necessárias Paginação sob demanda 1312 1544 24 Usualmente no entanto utilizase a abordagem da paginação sob demanda na qual de acordo com a necessidade a paginação será utilizada e a memória física será alocada de maneira eficiente Algumas de suas vantagens são A necessidade de operações de entradasaída inout ou somente IO será reduzida drasticamente Redução da quantidade de memória utilizada Menor será o tempo de resposta Mais usuários poderão estar compartilhando o sistema Alguns pontos básicos sobre essa abordagem Quando uma página é solicitada basta apenas referenciá la se a referência for inválida o sistema operacional pode interceder finalizando o processo alegando falha na segmentação Se por outro lado a página solicitada não estiver mapeada ela pode ser trazida para a memória física Com o swapping o sistema de paginação tenta adivinhar quais páginas irão ser utilizadas antes de jogálas novamente no disco swap out por ser uma questão de sorte o professor aponta que pode não funcionar muito bem Ocorre quando é feita uma referência a uma página que ainda não está mapeada para a memória física Neste momento o sistema operacional é invocado e passa a verificar outra tabela e decide se a referência está contida entre os endereços válidos ou não se não estiver o sistema operacional finaliza o processo se estiver o sistema realizará os seguintes passos Procurará uma moldura livre na memória física Acessará o disco e realizará o swap da página em uma moldura livre Atualizará a tabela de páginas indicando a entrada na qual a página está agora inserida e que esta entrada seria válida Reiniciará a instrução que causou a falha de página Falha de página page fault Normalmente um sistema operacional realiza a criação de múltiplos processos através de uma operação chamada fork Nela não haverá só a criação de um novo processo mas também a duplicação das referências associadas aos mesmos segmentos de código dados pilha etc 2241 25 Se as páginas já residirem na memória física o sistema funcionará tal qual o processo de paginação sem demanda caso contrário será necessário detectar e carregar a página na memória a partir do disco Abaixo é possível ver uma ilustração de uma tabela de páginas onde algumas páginas não estão na memória Caso extremo chamado de paginação sob demanda pura iniciar um processo sem páginas na memória Seria bastante custoso nota o professor o sistema operacional terá de configurar uma referência para a primeira instrução e para os próximos acessos Caso no qual uma mesma instrução pode acessar múltiplas páginas teria como consequência múltiplas falhas de páginas o que seria um problema para o qual o professor afirma que não há uma solução óbvia Por isso seria necessário tratar individualmente cada uma das falhas Demanda um suporte de hardware Quando já não há moldura livre é necessário implementar uma substituição de páginas ou seja descobrir quais páginas já não são mais necessárias embora tenham sido em outro momento dentre aquelas que estão mapeadas na memória física Esse mecanismo completa a separação entre a memória lógica e a memória física Outros aspectos sobre a paginação sob demanda Prevenir a alocação desnecessária na memória apenas referenciar páginas que são necessárias naquele momento além de manter uma lista de páginas que poderiam ser imediatamente substituídas Utilizar um dirty bit para reduzir o custo de transferência de páginas fazendo com que somente as páginas modificadas sejam escritas no disco O dirty bit é um recurso que marca como sujas por assim dizer todas as páginas modificadas Maneiras de implementar uma substituição de páginas Passoapasso 1 Procurar no disco uma página necessária gerada por um acesso válido Mecanismo básico de substituição de páginas 2516 2832 3001 26 2 Procurar uma moldura livre para inserila se houver alguma usála caso contrário utilizar um algoritmo de substituição de páginas e escolher uma moldura como vítima idealmente alguma que não esteja marcada como dirty se no entanto for necessário utilizar uma moldura modificada devemos copiála para o disco 3 Atualizar a tabela de páginas referenciando a moldura na qual a página será inserida 4 Continuar a execução do processo reiniciando a instrução que causou a falha de página Os arquivos podem ser manipulados com chamadas de sistema open read e write ou ainda ser acessados utilizando a memória virtual de um processo através de uma chamada de sistema mmap Arquivos mapeados em memória Relacione os conceitos na primeira coluna com suas respectivas definições na segunda Para exercitar Considere a afirmação abaixo e em seguida classifiquea como verdadeira ou falsa A função resumo é usada pelas tabelas de páginas indexadas como base para a indexação Para exercitar 3141 Memória Virtual Separação da memória lógica do usuário da memória física Referenciação a uma página que ainda não está mapeada para a memória física Recurso que marca todas as páginas modificadas Falha de página Dirty bit Verdadeiro Falso PUCRS online