Sistemas Operacionais - AULA 6
 

Gerencia de Memória - Conceitos Básicos

Gerenciador de memória

O problema principal que o gerente de memória deve resolver é como fornecer ao processo acesso à memória, de maneira escalável e segura, assegurando a mínima ociosidade dos recursos de HW (CPU, I/O, etc.).

Dois detalhes do capítulo anterior são pertinentes aqui:

Um processo é uma instância de programa que para ser executado deve está necessariamente na memória RAM.

Outro detalhe é que o processo é composto das instruções que são carregadas do arquivo do programa, e dos dados derivados da execução das instruções.

Lembrete: O sistema Operacional sempre estará na memória, no todo ou em partes.

Acesso a memória

Em todo computador existe instruções que suportam a manipulação de informações na memória. As operações típicas são leitura ou escrita que referenciam células específicas de memória. Para fazer este trabalho de interface com a memória as CPUs contam com dois registradores específicos: o MAR (ligado ao barramento de endereços) e o MBR (ligado ao barramento de dados). O MAR (Memory Address Register), tem o papel de selecionar a célula de memória que será afetada (leitura/escrita) e o registrador MBR (Memory Buffer Register) tem o papel de receber o dado que vem da memória, em caso de leitura. Em caso de escrita esse registrador deve conter o dado que será armazenado no endereço informado pelo MAR. A unidade de controle (UC), ligada ao barramento de controle, através da decodificação da instrução vai informar se a operação é de leitura ou escrita.

Problemas de Gerenciamento de Memória

Todos os problemas relacionados a Gerencia de Memória tem a mesma origem: O programador.

O programador quer cada vez mais e mais memória e mais rápida;

O programador ou é desonesto ou é relapso, de forma que não devemos permitir que ele possa acessar memória de outros processos ou do SO.

É importante entender que quanto mais rápida a memória, mais cara ela será. O ideal seria ter um computador com memória rápida em abundância, porém ele seria muito caro. O que os engenheiros de computação tentam fazer é o balaceamento entre os tipos de memória: Uma pequena quantidade de memória muito rápida (cache, registrador), com uma quantidade maior de memória menos rápida (RAM), e abundancia de memória lenta (HD), porém persistente. Esse balanceamento é conhecido como hierarquia de memória.

Gerente de Memória

O gerente de memória é o módulo do SO que implementa os serviços de memória que um processo precisa. Por exemplo:

Alocar memória para um processo recém-criado, permitindo ou não o compartilhamento de memória.

Fornecer a possibilidade de um processo crescer ou diminuir em termos de memória. Exemplo: em C o programador faz uma chamada a uma função malloc ou free, ou em java, quando um programador estancia uma determinada classe;

Em alguns SOs, permitir que a demanda por memória seja maior que a quantidade de memória física disponível, através do uso de uma área de troca em disco;

Gerenciar as áreas de memória livre;

E liberar espaço na memória, antes usados pelos processos que terminaram.

Gerenciamento Básico de Memória

Monoprogramação

O Fato de se ter um sistema monoprogramado (um só processo na memória) não dispensa gerência. Esse processo pode precisar crescer, ou simplemente ocupar um maior espaço que a RAM disponível.

Outro detalhe que pode ser percebido é que o Sistema Operacional também deve ocupar a RAM, pois o processo sempre irá requisitar serviços ao SO, e para atendê-los, o SO deve necessariamente está em alguma memória acessível rapidamente pela CPU.

As figuras acima ilustram três formas de disponibilizar memória física para o processo.

Na da esquerda o Sistema Operacional e Processo Compartilham a RAM.

Na do centro o Sistema Operacional em ROM e Processo em RAM → Alguns computadores tem a capacidade de executar instruções direto da ROM.

Na da direita SO e Processo em RAM e Drivers em ROM.

Modelo de Multiprogramação

Colocar Figura Aqui

Esse modelo ajuda a entender as vantagens de se manter N processos na memória ao mesmo tempo, baseado em seu percentual de E/S.

Se no desenvolvimento dos processos os engenheiro tivessem conseguido resolver o problema de E/S ser invariavelmente mais lenta que a CPU, talvez os modelos de gerenciamento de memória fossem construídos de outra forma.

O Fato é que todo o processo faz E/S e neste tempo, se não estiver disponível na memória outro processo, a CPU ficará ociosa. Desta forma, o modelo de multiprogramação reduz o desperdício de tempo de CPU.

Mas qual é o grau mínimo de multiprogramação (quantos processos podem ser colocados na memória) que pode garantir um uso efetivo (100%) de CPU?

É importante lembrar que o modelo proposto acima é ideal (o percentual de E/S sempre varia de processo para o outro).

Gerenciamento Básico - Multiprogramação

Particionamento da Memória - Partiçoes de Tamanho Fixo

Para que haja o compartilhamento de tempo da CPU (multitarefa) entre os processos, estes devem está necessariamente na memória (Multiprogramação).

A solução trivial para gerenciar a memória para permitir que múltiplos processos a ocupem é o seu particionamento.

O sistema operacional precisa saber onde estão os processos para poder passar o controle para eles, e também não deve permitir que um processo acesse dados de outro processo (tarefa impossível sem ajuda do hardaware). Essa solução por ser trivial tem alguns problemas:

Fragmentação Interna: O ideal era que o processo que fosse ocupar uma determinada partição fosse exatamente do tamanho da partição, raramente isso ocorre, o que acontece na realidade é que o processo sempre será menor que a partição, e isso gera um espaço interno que não poderá ser usado por outro processo.

O Número fixo de partições limita o sistema operacional a executar um número máximo de processos.

Filas para acesso as partições

Colocar Figura Aqui

É comum em sistemas multiprogramados que exista vários processos sendo criados num dado instante. Desta forma o sistema operacional deve controlar a forma como as partições deverão ser entregue ao processo.

A primeira alternativa é manter uma fila de admissão com os processos e a medida que eles entrarem na fila procurar uma partição vazia para acomodar esse processo. É importante lembrar que quanto mais próximo o tamanho do processo e da partição, menor será o desperdício, a diante discutiremos alguns algoritmos para escolha da partição. Na figura (b) podemos ver um esquema desta técnica.

Procurar uma partição que gere o menor desperdício possível, é uma tarefa que pode requerer um certo tempo dependendo do tamanho da quantidade de partições. Se for possível criar fila para as partições esse tempo será reduzido, uma vez que, na criação do processo já será atribuído a ele um tamanho de partição. Observe que esta técnica pode provocar uma espera desnecessária para o processo uma vez que pode existir partições ociosas numa fila para processos maiores.

Particionamento da Memória - Partiçoes de Tamanho Variável

Nesta tecnica um processo pode ter o seu inicio e fim em qualquer ponto da memória em que haja espaço livre continuo para alocá-lo. É uma técnica mais flexível que o particionamento fixo e resolve os problemas de fragmentação interna e de limite no número de processos. A técnica de partições variáveis é implementada normalmente com troca de processos.

Problemas e Soluções da Troca de Processos

O fato do processo poder ocupar qualquer espaço na memória, vai gerando espaços vazios na memória, conforme os processos vão sendo criados e destruidos. Esses espaços gerados são muito pequenos para serem usados por novos processos, esse problema é conhecido como fragmentação externa. Para resolver o problema da fragmentação externa, de tempo em tempos, o sistema operacional pode usar tempo de CPU para agrupar todos os processos no inicio da memória, gerando um espaço livre maior, essa técnica é conhecida como compactação de memória.

Na vida real os processos são criados com um tamanho e ao longo do tempo tem o seu tamanho de memória normalmente aumentado (alocação dinâmica de memória). Se um processo está alocado entre dois processos, não há espaço para crescer, e desta forma pode ser trabalhoso para o sistema operacional tratar solicitações de memória por parte do processo. Para resolver esse problema, pode se usar espaço extra (maior que o necessário) na hora de alocar o processo na memória. A figura abaixo tem duas abordagens para o espaço extra:

Colocar Figura Aqui

Troca de Processos

Num sistema que trabalhe com processos em lote é simples usar partições fixas, O processo entra na sua partição e lá permanece até terminar sua execução.

Em sistemas de tempo compartilhado interativos, um processo pode ficar indefinidamente esperando por uma resposta do usuário sem processar absolutamente nada, apenas ocupando memória.

Em casos como este pode existir vários processos na memória e a CPU pode ainda está ociosa. Em situações como essa podemos usar a troca de processo para guardar no disco, um processo que esteja esperando uma resposta do usuário e assim liberar memória para um processo que precise executar.

Quando o sistema envia o processo todo para o disco essa técnica é conhecida como SWAPPING. Quando é possível transferir partes do processo para o disco essa técnica é conhecida com paginação.

O uso da troca de processo permite que um sistema possa ter em execução, uma quantidade de processos maior que a quantidade de memória física disponível.

Relocação

Uma variável definida em linguagem de alto nível sempre será definida em baixo nível como um endereço de memória. Para exemplificar podemos citar o seguinte trecho de código:

I=25;

Podemos supor que este código será traduzido em baixo nível para a seguinte trecho, em arquitetura específica.

MOV 25, $0x0100

A instrução acima, em assembly, vai mover o literal 25 para o endereço de memória 0x0100. Agora imagine que no modelo de particionamento esse processo poderá ser alocado em uma partição em que o endereço 0x1000 não faça parte. Ou seja o programador ou compilador não tem a mínima ideia onde, na memória, o código será carregado. Esse problema é conhecido como relocação de código e existe algumas técnicas que podem resolver esse problema, uma delas, usada anteriormente era o carregador relocador , que reescrevia as referencias à memória no executável, de forma que este refletisse os endereços da partição que será usada pelo processo.

Proteção

Se por acaso algum endereço não pertencente ao espaço de endereçamento do processo for acessado pelo mesmo, isso será considerado uma falha de proteção. A seguir veremos as soluções disponíveis para resolver estes dois problemas.

Soluções para relocação e Proteção

Soluções de Software + hardware

O Problema da relocação pode ser resolvido por software (sem auxílio de hardware), bastando apenas reescrever as referências a memória, porém a questão da proteção, necessita de apoio de hardware.

Fazer o programador trabalhar em relação a um zero, e depois adicionar um endereço de offset à referencia pode resolver o problema da relocação. Digamos que uma partição inicia no endereço 0x3000. No exemplo anterior poderíamos dizer que 0x0100 é um endereço relativo ao inicio da partição, durante o procedimento de carga a instrução seria modificada para 0x3100 (0x100 + 0x3000).

Ainda em relação ao exemplo anterior, imagine que para o programa ser alocado será usado uma partição de 1K, ou seja, os endereços que poderão ser acessados vão variar de 0x0100 (endereço 0 da partição) até 0x0500 ( 0x1100+1k) endereço final da partição. No entanto no momento da tradução o endereço relocado foi 0x1100 que é maior que 0x0500 que é o endereço final da partição. Esse acesso claramente viola a proteção entre processos, um acesso deste tipo, se permitido ira modificar o conteúdo de uma posição de memória fora de sua partição, e possivelmente pertencendo a outro processo. A única maneira de evitar esse tipo de acesso é através de hardware.

Uma solução criada pela IBM para proteção envolvia o uso de 4 BITs no registrador PSW (STATUS). Com isso a memória do computador era particionada em 16 Partições cada uma com 2K. O SO, tendo acesso privilégiado, escrevia o número da partição nestes bits, e entregava o controle ao processo. Se uma instrução fizesse acesso a um endereço cujo os 4 bits mais significativos fossem diferentes dos da PSW, seria gerada uma interrupção de hardware (GPF), e o processo em questão seria terminado. A comparação entre os bits do endereço e do PSW era feita via HW.

Para fins didáticos a figura acima ilustra uma memória de 64K com 16 partições de 4k. A idéia é descrever como funciona a proteção usando a PSW. Observe que temos 2 instruções, a primeira (A) acessa o endereço 0x0100 (256) do segmento, A segunda (B) o endereço 0x1000 (4096).

No exemplo a instrução pertence a um processo que será alocado na partição 3. Nesta partição os endereços vão de 0x3000 (12288) a 0x3FFF (16383). Antes da execução do código as referências precisam ser relocadas, desta forma o carregador irá rescrever os endereços para 0x3100 (12544=12288+256) e 0x4000 (16384=12288+4096) respectivamente.

Dentro da CPU, antes do acesso à memória, é feita a comparação entre os 4 primeiros bits do endereço que está sendo acessado, e o conteúdo armazenado na PSW. O primeiro acesso passará normalmente. Já o segundo gerará uma falha pois o conteúdo da PSW (3) será diferente dos 4 primeiros bits do endereço (4).

Soluções em hardware

As soluções mostradas anteriormente se baseavam na modificação das referências à memória direto no código. Essas soluções em geral foram ruins pois tinham problemas em situações de troca do processo e cálculo de endereços. A solução por hardware é bem menos complexa, para o programador do sistema operacional, porém encarece o valor da CPU. Um hardware é responsável pela validação e tradução dos endereços virtual (programador) para físico (célula de memória específica). Esse hardware é uma unidade de gerência de memória (MMU) elementar. A figura abaixo tem um esquema de funcionamento deste hardware. O SO antes de entregar ao CPU para o processo o SO preenche os registradores BASE e LIMITE na MMU. Toda referência ao endereço é comparada com o registrador limite, caso seja maior é gerada uma interrupção (falha de proteção), se for menor é passada pelo módulo de soma e finalmente cai no barramento de endereços.

Gerenciamento de Espaço Livre - A fazer

Mapas de bits

Lista Encadeada

Algoritmos de Alocação

Best-Fit, Worst-Fit, Next-Fit, Fist-Fit

Overlays

Pela lei de Parkinson, os programadores sempre querem mais memória, neste caso mais memória que o disponível. Em sistemas de troca de processos isso não é possível. Sendo assim uma solução que surgiu para esse problema é o chamado Overlay (Programadores clipper/DOS vão lembrar disto). Nesta técnica, o programador da aplicação é responsável por particionar o seu código de forma que ele seja chamado em partes. Cada parte quando é chamada substitui a outra na memória RAM da máquina.

A solução definitiva para o problema do processo maior que a RAM é a Memória Paginada, na próxima aula essa técnica será discutida em detalhes.