Algoritmo para Remoção de Páginas

Existem diversas situações nas quais uma página deve ser removida da memória, ou seja, desassociada de uma moldura, que é, então, liberada. Por exemplo:
- Quando o sistema detecta que há falta de memória para um determinado processo;
- Quando o sistema hiberna;
- Durante o processo periódico de remoção de páginas não mais usadas.

O algoritmo usado pelo Linux para tratar tais casos é complexo e requer o uso de diversas funções. O esquema abaixo resume algumas delas, que serão descritas mais adiante.

livia3.jpg

Fig. 1. Principais funções do algoritmo de remoção de páginas.

O princípio usado pelo Linux para remover páginas da memória é o do algoritmo LRU (Least Recently Used). As estruturas de dados essenciais usadas pelo Linux na implementação deste algoritmo são duas listas duplamente encadeadas: a active list e a inactive list. A primeira inclui páginas acessadas recentemente e, a segundo, páginas não acessadas há algum tempo. A idéia é remover páginas da inactive list.
O algoritmo deve ser capaz de transferir páginas de uma lista para outra, à medida que são acessadas ou não. Os flags PG_reference e PG_active contidos em cada entrada da tabela de páginas são responsáveis pela contagem de acessos para mover uma página para a active list e o número de “não-acessos” para mover uma página para a inactive list. Estas transferências são representadas pelo esquema abaixo:

livia4.jpg

Fig. 2. Funções de transferência de páginas entre listas.

Funções da Figura 3 são responsáveis por modificar o estado de uma página, como mostrado na Figura 4, e, com isso, decidir qual página será retirada da memória. De forma resumida, as responsabilidades das funções são:
- De “try_to_free_pages()” até “shrink_cache()” ocorre a seleção das páginas candidatas a serem removidas, de acordo com o LRU;
- “shrink_list()” tenta recuperar as páginas passadas como parâmetros. Elas podem estar bloqueadas e não ser removidas;
- “page_out()” é invocado quando uma página suja (que foi modificada recentemente) precisa ser escrita em disco.

Detalhes de a respeito destas funções podem ser obtidos aqui: http://jno.glas.net/data/prog_books/lin_kern_2.6/0596005652/understandlk-CHP-17-SECT-3.html#understandlk-CHP-17-SECT-3.1

//Figura 3 e 4??

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License