Escalonamento de Processos Algoritmos de Mudança de Página
mai 24

5. GERENCIAMENTO DE MEMÓRIA

Gerenciador de Memória é a parte do SO que é responsável por cuidar de quais partes da memória estão em uso, quais estão livres, alocar memória a processos quando eles precisam, desalocar quando eles não necessitarem mais e gerenciar a troca dos processos entre a memória principal e o disco (quando a memória principal não é suficiente para manter todos os processos)

Maneiras de Gerenciar a Memória:

1. Gerenciamento sem Troca ou Paginação: troca e paginação são métodos utilizados de movimentação da memória para o disco e vice-versa durante a execução dos processos. Sem troca ou paginação é o caso mais simples.

2. Monoprogramação sem Troca ou Paginação: temos um único processo sendo executado por vez, de forma que o mesmo possa utilizar toda a memória disponível, com exceção da parte reservada ao SO (que permanece constante em local pré-determinado). O SO carrega um programa do disco para a memória executa-o e em seguida aguarda comandos do usuário para carregar um novo programa, que irá se sobrepor ao anterior.

3. Multiprogramação: a monoprogramação não é mais utilizada em sistemas grandes, pois:

>> Muitas aplicações são mais facilmente programáveis, quando as dividimos em dois ou mais processo;

>> Os grandes computadores em geral oferecem serviços interativos simultaneamente para diversos usuários (seria impossível trabalhar com um único processo por vez, pois representaria sobrecarga devido à constante necessidade de chavear de um processo para outro – constantemente lendo e escrevendo no disco);

>> É necessário que diversos processos estejam “simultaneamente” em execução devido as operações de E/S, que implica em grandes esperas nas quais por questão de eficiência a UCP deve ser entregue a outro processo.

1. Multiprogramação com Partições Fixas: consiste em dividir a memória existente em n partições fixas, podendo ser de tamanhos diferentes. Essas partições poderiam ser criadas ao inicializar o sistema pelo operador.

Uma maneira de se fazer isso seria: criar uma fila para cada partição existente e cada vez que um processo é iniciado, ele é colocado na fila de menor partição capaz de o executar. Os processos em cada partição são escolhidos de acordo com alguma forma de política, por exemplo, o primeiro a chegar é atendido antes. O problema é que pode ocorrer que uma partição grande esteja sem utilização, enquanto que diversos processos estão aguardando para utilizar uma partição menor. Para resolver isso podemos fazer o seguinte: estabelecer apenas uma fila para todas as partições e quando uma partição fica livre, um novo processo que caiba na partição livre é escolhido e colocado na mesma. A melhor forma de fazer a escolha seria percorrer a fila procurando o maior processo aguardando que caiba na partição livre, pois se a partição livre for entregue para o primeiro processo da fila, pode ocorrer que uma partição grande seja entregue a um processo pequeno.

2. Realocação e Proteção: há a necessidade de realocações, pois processos diferentes executam em posições diferentes de memória e com endereços diferentes. Uma possível solução é modificar as instruções conforme o programa é carregado na memória (quando o SO carrega o programa, adiciona a todas as instruções que se referenciarem a endereços, o valor do ponto inicial de carga do programa). Esta solução exige que o linker coloque no início do código do programa, uma tabela que apresente as indicações das posições no programa que devem ser modificadas no carregamento. Mas isso não resolve a proteção, pois um programa malicioso ou errado pode ler ou alterar posições na memória de outros usuários, já que as referências são sempre as posições absolutas de memória.

Uma solução adotada para isso foi dividir a memória em unidades de 2 KB e associar um código de proteção de 4 bits a cada uma dessas regiões. Durante a execução de um processo, o PSW contém um código de 4 bits que é testado com todos os acessos à memória realizados pelo processo, e gera uma interrupção se tentar acessar uma região de código diferente.

Uma solução alternativa para o problema da realocação e da proteção é a utilização de registradores de base e limite. Sempre que um processo é carregado na memória, o SO ajusta o valor do registrador de base de acordo com a disponibilidade de memória. Toda vez que um acesso é realizado na memória pelo processo, o valor do registrado é automaticamente somado, assim não há necessidade de que o código do programa seja modificado durante o carregamento. O registrador de limite indica o espaço de memória que o processo pode executar, então todo acesso realizado pelo processo à memória é testado com o valor do registrador limite para a validação do seu acesso. O método dos registradores permite que um programa seja movido na memória, mesmo após já estar em execução, o que antes não era possível sem antes alterar os endereços novamente.

3. Troca (swapping): num sistema de batch, desde que se mantenha a UCP ocupada o máximo de tempo possível, não há necessidade de se complicar o método de gerenciamento de memória. Mas num sistema de time-sharing, onde muitas vezes existe menos memória do que o necessário para manter todos os processos de usuário, então é preciso que uma parte dos processos seja temporariamente mantida em disco. Para executar processos que estão no disco, eles devem ser enviados para a memória, o que significa retirar algum que lá estava. Este processo é denominado troca.

4. Multiprogramação com Partições Variáveis: partições que variam conforme as necessidades dos processos, em tamanho, em localização e em número de partições, melhorando a utilização da memória (mas complica a alocação e desalocação da memória). Compactação de memória que é a combinação de todos os buracos formados na memória em um único é raramente utilizada devido a grande utilização de UCP requerida.

Para determinarmos quanta memória deve ser alocada a um processo quando ele é iniciado, temos duas situações: se os processos necessitarem de uma quantidade pré-fixada e invariante de memória basta alocar a quantidade necessária a cada processo ativo. E o outro caso é quando os processos necessitam de mais memória durante o processamento (alocação dinâmica de memória). Neste caso pode existir um buraco de memória próximo ao processo bastando alocar a memória desse buraco ou o processo pode estar cercado por outros processos, ou o buraco que existe não é suficiente. Para os dois últimos casos temo que tomar algumas das seguintes ações: mover o processo par um buraco de memória maior e se não houver tal espaço, alguns processos devem ser retirados da memória para deixar espaço para esse processo e se não houver espaço no disco para outros processos, o processo que pediu mais espaço na memória deve ser morto. Quando se espera que diversos processos cresçam durante a execução, o melhor seria reservar espaço extra para esses processos quando eles são criados para eliminar a sobrecarga de lidar com movimentação ou troca de processos.

4. Gerenciamento de espaço: as duas principais formas de cuidar da utilização de memória são:

1. Gerenciamento com Mapa de Bits: A memória é subdividida em unidades de um certo tamanho. A cada unidade é associada um bit que se for 0 indica que essa parte da memória está livre e se for 1 indica que está ocupada. O tamanho deve ser cuidadosamente escolhido. A desvantagem é que quando um novo processo que ocupa k unidades de memória deve ser carregado na memória, o gerenciador deve percorrer o mapa de bits para encontrar k bits iguais a zero consecutivos, o que não é um processo simples.

2. Gerenciamento com Listas Encadeadas: mantemos uma lista encadeada de segmentos alocados e livres, sendo que cada segmento é um processo ou um buraco entre dois processos. A lista apresenta-se em ordem de endereços, e quando um processo termina ou é enviado para o disco, e a atualização da lista ocorre da seguinte maneira: cada processo, desde que não seja nem o primeiro nem o último da lista, apresenta-se cercado por dois segmentos, que podem ser buracos ou outros processos, o que nos dá as quatro possibilidades mostradas na figura abaixo:

Os buracos adjacentes devem ser combinados num único. Para escolher o ponto em que deve ser carregado um processo recém criado ou que veio do disco por uma troca, vamos utilizar alguns algoritmos assumindo que o gerenciador de memória sabe quanto espaço alocar no processo:

- First Fit (primeiro encaixe): percorrer a fila até encontrar o primeiro espaço em que caiba o processo. É um algoritmo rápido.

- Next Fit (próximo encaixe): o mesmo que o algoritmo anterior, só que ao invés de procurar sempre a partir do início da lista, procura a partir do último ponto em que encontrou. Desempenho próximo ao anterior.

- Best Fit (melhor encaixe): consiste em verificar toda a lista e procurar o buraco que tiver espaço mais próximo das necessidades do processo. É mais lento, e desempenho pior que o First Fit

- Worst Fit (pior ajuste): pega sempre o maior buraco disponível. Desempenho ruim.

Esses algoritmos podem ter sua velocidade aumentada pela manutenção de duas listas separadas, uma para processos e outra para buracos. Quando temos duas listas separadas, outro algoritmo é possível. É o Quick Fit (ajuste rápido), que consiste em manter listas separadas para alguns dos tamanhos mais comuns especificados (ex. uma fila para 2k, outra para 4k, outra para 8k etc). Neste caso, a busca de um buraco com o tamanho requerido, é extremamente rápido, entretanto, quando um processo termina, a liberação de seu espaço é complicada, devido à necessidade de reagrupar os buracos e modificá-los de fila.

5. Alocação de espaço de troca (swap): espaço de troca é o espaço ocupado no disco pelos processos que aí estão guardados, pois foram retirados da memória devido a uma troca. Os algoritmos para gerenciar o espaço alocado em disco para swap são os mesmos apresentados para o gerenciamento de memória. A diferença é que em alguns sistemas, cada processo tem no disco um espaço reservado para o mesmo e na memória ele é constantemente mudado de lugar. Além disso, como os discos são dispositivos de bloco, a quantidade de espaço reservado para os processos no disco deverá ser múltipla do tamanho do bloco.

6. Memória Virtual: A primeira solução adotada para programas grandes demais para a quantidade de memória foi a utilização de overlays. Nesta técnica o programa era subdividido em partes menores (overlays), que podiam ser rodadas separadamente e quando um overlay terminava a execução um outro poderia ser carregado na mesma posição de memória utilizada pelo anterior. O problema é a divisão do programa em overlays não é simples e deve ser realizada pelo programador.

A técnica de memória virtual para executar um programa que não cabe na memória existente consiste em manter partes do programa, dos dados e da pilha no disco, sendo que existe uma forma de decisão de quais processos devem permanecer no disco e quais na memória. Esta técnica é realizada de forma automática pelo computador. Podemos alocar diversos processos na memória virtual, de forma que cada um pensa ter uma quantidade de memória que somadas ultrapassam a quantidade real de memória. Técnicas utilizadas em sistemas com memória virtual:

1. Paginação: espaço virtual é o espaço de memória que pode ser referenciado por um programa qualquer em dado processador. Ex: um processador com endereçamento de 16 bits, possui um espaço virtual de 64 kbytes. Quando uma instrução como: LD A,(1000h) o 1000h corresponde a um endereço virtual, de um espaço de endereçamento virtual de 64k bytes. Em um computador sem memória virtual, o endereço virtual corresponde ao endereço efetivamente colocado no duto de endereçamento da memória. Quando o computador possui memória virtual, esse endereço virtual é enviado para uma unidade de gerenciamento de memória (MMU), que corresponde a um chip ou um conjunto de chips que translada esse endereço virtual em um endereço físico, de acordo com uma tabela.

O espaço de endereços virtuais é dividido em unidades chamadas páginas e o espaço de memória física é dividido em unidades chamadas quadros de página, de mesmo tamanho das páginas. A MMU tem uma tabela que indica para cada página, qual o quadro de página que corresponde à mesma. Se o processador tenta acessar o endereço 0, a MMU verifica que isto corresponde ao primeiro endereço da primeira página, verifica então que essa primeira página está alocada no terceiro quadro de página. Converte então esse endereço para 8192 (decimal) e envia o endereço convertido para a memória (nem a memória e nem o processador precisam ficar sabendo da existência de paginação).

Como nem todas as páginas do espaço virtual podem estar residentes na memória simultaneamente, ocorrer o caso de que um acesso seja realizado para um página que não está na memória. Para saber isso a MMU mantém na tabela de translação um bit para cada página que indica se a mesma está presente ou não na memória. Se um acesso for realizado a uma página ausente, é gerada uma falta de página, que chama uma rotina de tratamento de interrupção específica para o SO, que então se encarrega do carregamento da página faltante e o ajuste correspondente na tabela de translação.

A forma mais comum de implementação da MMU, é escolher alguns dos bits mais significativos do endereço virtual como indicadores do número de página e o restante dos bits como um deslocamento dentro dessa página. Ex: na figura acima, de 16 bits do endereço virtual, 12 serão utilizados para o deslocamento e 4 serão utilizados como um índice para qual das 16 páginas está sendo referenciada. A MMU pega os 4 bits do índice da página, acessa a posição correspondente da tabela de translação, verifica se a página está presente na memória, se não estiver, gera uma interrupção para carregamento e depois verifica o valor colocado nessa entrada da tabela de translação e os junto aos 12 bits de deslocamento dentro da página.

A paginação fornece uma forma de se conseguir grande espaços de endereçamento lineares em uma quantidade finita de memória física.

2. Segmentação: Na segmentação temos um espaço bidimensional no sentido de que é dividido em uma um certo número de segmentos, cada um com dado número de bytes. Dessa forma, um endereçamento é sempre expresso da forma (segmento, deslocamento). Os diferentes segmentos são associados a diversos programas ou mesmo arquivos, de forma que neste caso, os arquivos podem ser acessados como se fossem posições de memória. Na segmentação os programadores tentam colocar entidades diferentes em segmentos diferentes para facilitar o compartilhamento de objetos entre processos diferentes.


O material acima está dividido em oito partes, foi escrito por Alex De Francischi Coletta em 2003 e adaptado para a WEB.
Bibliografia: FREITAS, Ricador Luis de “Apostila de Sistemas Operacionais” utilizado no curso de graduação em Engenharia de Computação da Pontifícia Universidade Católica de Campinas na disciplina de Sistemas Operacionais I.


Converter para PDF

Deixe uma resposta


Alex De Francischi Coletta - 2007-2008
Todo o conteúdo deste site é protegido pelos direitos autorais dos respectivos autores.
Qualquer reprodução do conteúdo deste site, somente será permitida com prévia autorização do autor.