Introdução aos Sistemas Operacionais/Gerência de Memória
De Wikiversidade
A maioria dos computadores trabalha com o conceito de hierarquia de memória, possuindo uma pequena quantidade de memória cache, muito rápida, uma quantidade de memória principal (RAM) e uma quantidade muito grande de memória de armazenamento em disco (HD), considerada lenta. O problema básico para o gerenciamento de memória é que os programas atuais são muito grandes para rodarem, completamente, na memória cache. O gerenciador de memória deve ser capaz de controlar que parte da memória está em uso (e quais não estão), alocar memória para processos quando eles necessitam e desalocar quando eles terminam e, principalmente, gerenciar a troca entre a memória principal e o disco,quando a memória principal é muito pequena para armazenar todos os processos.
Tabela de conteúdo |
[editar] Gerenciamento Básico de Memória
Os Sistemas de Gerenciamento de Memória podem ser divididos em duas classes: aqueles que movem processos de um lado para outro entre a memória principal e o disco durante a execução (fazendo troca e paginação) e aqueles que não o fazem. As próximas seções apresentam os mesmos.
[editar] Monoprogramação sem troca ou paginação
Este é o esquema mais simples possível: só é possível executar um programa de cada vez, compartilhando a memória entre o programa e o S.O. Existem três variações para este modelo. Quando o sistema está organizado desta maneira somente um processo por vez pode estar executando.
[editar] Multiprogramação com Partições Fixas
A maneira mais simples de implementar a multiprogramação, em termos de memória, é dividir a mesma em n partições desiguais. Quando um job chega, há duas possibilidades: ele é colocado em uma fila de entrada da menor partição capaz de armazená-lo ou ele é colocado em uma fila de entrada única.
Uma vez que as partições são fixas, qualquer espaço não ocupado por um job é perdido. A desvantagem de classificar os jobs em entradas separadas é apresentada quando uma fila para uma partição grande está vazia e filas para partições pequenas estão muito cheias. Uma possível alternativa é colocar todos os jobs em uma única fila de entrada e sempre que uma partição encontra-se livre, alocar para o próximo job da fila. Para não desperdiçar espaço pode-se realizar uma pesquisa para selecionar o job que melhor se ajuste ao tamanho da partição. No entanto, isto pode deixar jobs pequenos de fora, o que também é indesejável. Neste caso, é interessante dispor de pelo menos uma partição pequena para jobs pequenos ou criar uma regra que limite o número de vezes que um job pode ser ignorado, obrigando que o mesmo seja selecionado em um determinado momento.
Dois conceitos importantes devem ser introduzidos quando há a ocorrência de multiprogramação: realocação e proteção.
Programas (jobs) diferentes são colocados em endereços diferentes (partições). Quando um programa é vinculado, o linkeditor deve saber em que endereço o programa deve começar na memória. Como o gerenciador de memória só decide em qual partição (endereço) o programa vai executar quando este chegar, não há garantia sobre em qual partição um programa vai realmente ser executado. Este problema é conhecido como realocação: modificação dos endereços especificados dentro do programa de acordo com a partição onde ele foi colocado.
Outra questão importante está na proteção: programas diferentes não podem ter acesso a dados e/ou instruções fora de sua partição. Sem esta proteção, a construção de sistemas maliciosos seria facilitada. Uma possível alternativa para ambos os problemas é equipar a máquina com dois registradores especiais de hardware chamados registradores de base e registradores de limite. Quando um processo é agendado, o registrador de base é carregado com o endereço de início de sua partição e o registrador de limite com o comprimento de sua partição. Assim, instruções são verificadas em relação ao seu endereço de armazenamento e para verificar se o mesmo não está fora da partição. O hardware protege os RB e RL para impedir que programas de usuário os modifiquem.
[editar] Troca
Em sistemas computacionais modernos, usualmente, não há memória principal suficiente para armazenar os processos atualmente ativos. Desta forma, os processos excedentes são mantidos em disco e trazidos para a RAM quando necessário. Há duas formas de resolver este problema: troca e memória virtual, (sendo a última explicada posteriormente).
A operação de troca consiste em manter na memória alguns processos por um determinado período e, a seguir, trocar estes processos pelos demais que estão esperando em disco. A partição utilizada para cada processo pode ser fixa ou definida dinamicamente (de acordo com o tamanho do processo). Durante a operação de troca, é possível surgirem lacunas de memória que podem ser reunidas em um espaço maior através da técnica de compactação de memória.
No entanto, a atribuição dinâmica de memória conduz a um problema adicional: o gerenciamento de memória em relação a quais parcelas estão em uso e/ou quais estão livres. Existem duas formas de resolver este problema, vistas nas próximas seções.
[editar] Gerenciamento de Memória com Mapas de Bits
Com mapas de bits, a memória é dividida em unidades de alocação. Cada bit do mapa representa uma unidade de alocação, sendo que se o bit for 0, a unidade está livre; caso contrário, a unidade está ocupada. Quanto menor for a unidade de alocação, maior será o mapa de bits e vice-versa. O maior problema com os mapas de bits é que procurar uma lacuna (seqüência de 0s) suficientemente grande para um determinado processo pode ser uma operação muito lenta.
[editar] Gerenciamento de Memória com Listas Encadeadas
Neste caso, é mantida uma lista encadeada com os segmentos de memória livres e encadeados. Uma possível configuração seria manter, em cada entrada, o endereço em que inicia, o seu comprimento e, evidentemente, o ponteiro para a próxima entrada.
A principal vantagem de utilizar uma lista encadeada classificada por endereço é que sua atualização é simples e direta. Vários algoritmos podem ser utilizados para encontrar uma lacuna de memória para alocação de um processo:
- Primeiro ajuste: varre a lista desde o início e aloca no primeiro espaço (lacuna) suficientemente grande;
- Próximo ajuste: varre a lista da posição atual e aloca no primeiro espaço suficientemente grande;
- Melhor ajuste: varre a lista completamente e aloca no espaço que gerar a menor lacuna de memória;
- Pior ajuste: varre a lista completamente e aloca no espaço que gerar a maior lacuna de memória disponível, de modo que a lacuna resultante possa ser suficientemente grande para ser útil;
- Ajuste rápido: mantém diversas listas separadas para os tamanhos de processos mais comuns.
[editar] Memória Virtual
Quando os programas excedem o espaço de memória física disponível para eles, é possível dividir o programa em pedaços chamados overlays. No entanto, isto exige que o programados seja responsável por esta divisão. De forma a facilitar o desenvolvimento de programas, passando esta tarefa para o Sistema Operacional, foi criado o método conhecido como Memória Virtual.
A idéia básica da memória virtual é que o tamanho combinado do programa, dos seus dados e da pilha pode exceder a quantidade de memória física disponível para ele, ou seja, neste caso, a simples troca, vista anteriormente, não resolveria o problema. O Sistema Operacional, então, mantém partes do programa atualmente em uso na memória principal e o restante em disco.
A memória virtual também pode trabalhar em um sistema de multiprogramação, com pedaços de vários programas na memória simultaneamente. Enquanto um programa está esperando parte dele próprio ser trazido para a memória (ele fica esperando a E/S e não pode executar) a CPU pode ser dada a outro processo, assim como em qualquer sistema de multiprogramação.
Muitos sistemas de Memória Virtual utilizam uma técnica denominada paginação, vista na próxima seção.
[editar] Paginação
Em qualquer computador, existe um conjunto de endereços que um programa pode produzir. Estes endereços gerados por programas são chamados endereços virtuais e formam o espaço de endereço virtual. A MMU (Memory Management Unit) é responsável por mapear os endereços virtuais para endereços físicos de memória, sendo que consiste de um chip ou uma coleção de chips.
O espaço de endereço virtual é dividido em unidades chamadas páginas. As unidades correspondentes na memória física são chamadas molduras de página. As páginas e as molduras têm sempre exatamente o mesmo tamanho.
No espaço físico (memória) tem-se várias molduras de página. Por exemplo, podem existir 05 páginas situadas no espaço de endereço virtual que são mapeadas na memória física. No entanto, o espaço de endereço virtual é maior que o físico. As outras páginas não são mapeadas. No hardware real, um bit presente/ausente em cada entrada monitora se a página é mapeada ou não.
Quando um programa tenta utilizar uma página não mapeada em uma moldura, a MMU detecta o acontecimento (que a página não está mapeada) e gera uma interrupção, passando a CPU para o Sistema Operacional. Tal interrupção é chamada falha de página. O S.O., então, seleciona uma moldura de página pouco utilizada e grava o seu conteúdo de volta ao disco, substituindo-a pela página requisitada.
[editar] Tabelas de Página
O propósito de tabelas de página é mapear páginas virtuais em molduras de página. No entanto, existem duas questões que devem ser consideradas:
- A tabela de páginas pode ser extremamente grande, sendo que cada processo necessita de sua própria tabela de páginas;
- O mapeamento deve ser rápido: o mapeamento do virtual para o físico deve ser feito em cada referência da memória, o que pode ocorrer diversas vezes em uma única instrução,não devendo tomar muito tempo para não se tornar um gargalo na execução da instrução.
Neste caso, há a necessidade de um mapeamento de páginas rápido e grande. Existem duas formas básicas de projetar tabelas de páginas:
- ter uma única tabela de páginas, através de uma matriz de rápidos registradores de hardware, com uma entrada para cada página virtual, indexada pelo número da página. Esta é uma solução cara se a tabela de páginas é grande;
- manter a tabela de páginas inteiramente na memória principal, sendo que o hardware precisa de apenas um registrador que aponta para o início da tabela de páginas.
Esta última solução possui algumas variações que tem desempenho melhor. Uma das propostas que busca evitar o problema de ter enormes tabelas de páginas na memória todo tempo é a de Tabelas de Páginas Multinível. Neste caso, existe uma tabela de primeiro nível e diversas tabelas de segundo nível. O importante aqui é que somente as tabelas mais utilizadas estão presentemente na memória. As demais se encontram em disco. Apesar de permitir um espaço de endereçamento muito grande, o espaço ocupado de memória principal é muito pequeno.
O sistema de tabela de páginas de dois níveis pode ser expandido para três, quatro ou mais níveis, sendo que níveis adicionais dão mais flexibilidade, mas a complexidade da implementação acima de três níveis dificilmente vale a pena. Em relação aos detalhes de uma única entrada de uma tabela de páginas, seu arranjo pode depender da máquina, mas os tipos de informação usualmente são os mesmos.
O campo mais importante é o número da moldura de página, pois o objetivo do mapeamento de páginas é localizar este valor. Ao lado dele, tem-se o bit de presente/ausente. Se este bit for 1, significa que a entrada é válida e pode ser utilizada. Se for 0, a página virtual a que esta entrada pertence não está atualmente na memória. Ao acessar uma entrada da tabela de páginas com este bit configurado como zero ocorrerá uma falha de página.
Os bits “proteção” informam que tipos de acesso são permitidos. Em sua forma simples, este campo contém apenas um bit, com 0 para leitura/gravação e 1 par leitura somente. Um arranjo mais sofisticado é manter 3 bits, cada um para habilitar leitura, gravação e execução da página. Os bits “modificada” e “referenciada” monitoram a utilização da página.Ambos os bits tem como objetivo auxiliar no momento da substituição de páginas. O último bit permite que o cache seja desativado para a página, recurso importante para páginas que são mapeadas em registradores de dispositivo em vez da memória.
[editar] TLBs – Translation Lookside Buffers – Memória Associativa
As TLB, também conhecidas como memória associativa, são um dispositivo de hardware cujo propósito é mapear endereços virtuais em endereços físicos sem passar pela tabela de páginas. Usualmente, ela faz parte da MMU. Ela constitui-se de um pequeno número de entradas, muito rápidas, contendo as tabelas de páginas mais utilizadas. Quando um endereço virtual é enviado a MMU, ela primeiramente verifica se o seu número de página virtual está presente na TLB. Se o resultado for positivo, a moldura de página é tomada diretamente da TLB sem a necessidade de passar pela tabela de páginas. Caso contrário, a pesquisa é feita normalmente na tabela de páginas. Uma das entradas é removida da TLB e a entrada da tabela de páginas pesquisada é colocada em seu lugar.
[editar] Tabelas de Páginas Invertidas
Outra abordagem para trabalhar com páginas é manter uma tabela onde cada entrada representa uma moldura de página ao invés de um endereço virtual. Desta forma, a entrada deve monitorar qual página virtual está associada àquela moldura de página. Embora as tabelas de páginas invertidas economizem quantidade significativas de espaço (pelo menos nas situações em que o espaço de endereço virtual é muito maior que a memória física), elas tem a desvantagem de que o mapeamento (tradução) do endereço virtual para o físico é mais complexo e potencialmente mais lento. Uma forma de facilitar a tradução do virtual para o físico é a utilização da TLB pesquisada por software. A pesquisa pode ser feita a partir de um encadeamento de páginas páginas virtuais que possuam um mesmo endereço hash.
[editar] Algoritmos de substituição de páginas
Como visto anteriormente, sempre que uma página (endereço virtual) não estiver em uma moldura de página, uma interrupção ocorre e ela deve ser carregada para uma moldura antes de ser executada. No entanto, alguma página que está atualmente em uma moldura deve ser retirada (gravada em disco). Os algoritmos de substituição de páginas se preocupam em escolher a melhor página a ser retirada da moldura. Existem várias alternativas:
- algoritmo de substituição de página ótimo: deve ser retirada a página que só será referenciada o mais tarde possível. Apesar de, teoricamente, ser um algoritmo interessante, é extremamente difícil prever quando uma página será referenciada;
- algoritmo de substituição de página não recentemente utilizada: o S.O. e o hardware mantêm uma coleção de estatísticas sobre as páginas referenciadas e/ou modificadas (através dos bits de referência e modificação das entradas da tabela de páginas) e dão preferência para a troca de páginas não referenciadas e/ou não modificadas;
- algoritmo de substituição de página “primeira a entrar, primeira a sair (FIFO – first-in first-out): a página mais antiga é removida.No entanto, pode estar sendo removida uma página bastante utilizada;
- algoritmo de substituição de página de segunda chance: uma modificação do algoritmo FIFO, que busca não substituir uma página antiga e, no entanto, bastante utilizada. A solução é inspecionar o bit R (referenciada) da página mais antiga; se o bit for 1 (foi referenciada) o bit será limpo e a pesquisa continua. Se todas as páginas tiverem sido referenciadas, o algoritmo FIFO acaba sendo executado e a página mais antiga (que agora estará com o bit R limpo) será substituída;
- algoritmo de substituição de página menos recentemente utilizada (LRU – least recently used): a idéia é que as páginas que foram intensamente utilizadas nas últimas instruções provavelmente serão utilizadas de forma intensa no futuro próximo. Desta forma, deve ser removida a página que não foi utilizada por mais tempo.
[editar] Segmentação
A memória virtual apresentada anteriormente é unidimensional, ou seja, os endereços virtuais vão de 0 até algum valor máximo. No entanto, em alguns casos, ter dois ou mais espaços de endereços virtuais separados é uma estratégia interessante. A segmentação prove à máquina vários espaços de endereço completamente independentes, chamados segmentos, liberando o programador da tarefa de gerenciar a expansão e a contração de tabelas, da mesma forma que a memória virtual elimina a preocupação de organizar o programa em overlays.
Os comprimentos de cada segmento podem ser diferentes e podem variar durante a execução. Como cada segmento constitui um espaço de endereçamento completamente independente e diferente, eles podem aumentar ou encolher sem afetar um ao outro. Para especificar um endereço neste tipo de memória segmentada, o programa deve fornecer um endereço de duas partes: um número de segmento e o endereço dentro do segmento. É importante salientar que cada segmento pode conter várias páginas, logo, toda a discussão apresentada anteriormente sobre paginação continua válida aqui. Outra questão fundamental é que, diferentemente da paginação, que é executada inteiramente pelo S.O., os segmentos são entidades lógicas das quais o programador está ciente e as quais ele pode utilizar como qualquer entidade lógica. Um segmento pode conter um procedimento ou uma matriz, ou uma pilha, mas normalmente ele não contém uma mistura de tipos diferentes.
Como cada segmento forma uma entidade lógica da qual o programador está ciente (tal como pilha, procedimentos, etc.) segmentos diferentes podem ter tipos de proteção diferentes: é possível especificar que um procedimento só pode ser executado (sendo proibido ler ou armazenar nele), dados poderão ser lidos e gravados e assim por diante. Este tipo de proteção é útil para detectar erros de programação. A proteção na memória segmentada é importante porque o usuário está ciente do que está em cada segmento. Este modelo é difícil de aplicar a paginação, pois a paginação é invisível ao programador (que não tem como saber de antemão em que página ou moldura um determinado pedaço de programa está), o que não possibilita a separação dos tipos em cada página.
Uma das possibilidades da segmentação é que ela pode facilitar o compartilhamento de procedimentos e/ou dados entre vários processos. Um exemplo é uma biblioteca compartilhada. Neste caso, os procedimentos desta biblioteca permanecem em um único segmento que pode ser utilizado por diversos programas (processos), sem que cada um precise possuí-la em seu espaço de endereço.
A implementação da segmentação difere da paginação porque as páginas têm tamanho fixo e os segmentos não. A substituição dos processos gera lacunas fazendo com que a memória se transforme em um tabuleiro de xadrez, formado por segmentos e lacunas, que pode ser tratado com compactação. No entanto, se os segmentos são grandes pode ser impossível mantê-los na memória principal em sua totalidade (segmentação pura). Neste caso, pode ocorrer uma segmentação com paginação que pode ser implementada de formas diferentes dependendo do sistema computacional. No Pentium, por exemplo, duas tabelas são utilizadas para a implantação da segmentação: a LDT (Local Descriptor Table) e a GDT (Global Descriptor Table). Cada programa tem sua própria LDT, mas há uma única GDT compartilhada por todos os programas no computador. A LDT descreve segmentos locais para cada programa e a GDT descreve segmentos do sistema, incluindo o próprio S.O. Com a paginação ativada, os endereços gerados são considerados virtuais e o mapeamento para o endereço físico ocorre como explicado anteriormente.
[editar] Conclusões
Sistemas computacionais mais simples não precisam realizar nenhum tipo de gerenciamento pois, usualmente, seus programas rodam diretamente na memória principal disponível. No entanto, esta não é a situação mais comum. Na maioria dos sistemas em uso, os programas são muito maiores que a quantidade de memória principal disponível e/ou é necessário rodar mais de um programa ao mesmo tempo. Nestes casos, a utilização de esquemas de troca, páginas e segmentos pode ser uma alternativa. Um modelo de memória virtual, que fornece um espaço de endereçamento maior do que o físico, pode ser disponibilizado para os programadores no desenvolvimento de seus sistemas. Internamente, no entanto, o S.O. deve ser capaz de gerenciar a memória de forma a manter as partes do programa em uso na memória principal, armazenando as demais partes em disco.
|
