Algoritmo de Substituição de Página Primeira a Entrar

Algoritmo de Substituição de Página Primeira a Entrar

CURSO: TECNOLOGIA EM TELEMÁTICATURNO: MANHÃ

TAUÁ – CE 2012

1. Algoritmo de Substituição de Página Primeira a Entrar, Primeira a Sair.

O algoritmo de substituição de Página primeira a entrar, primeira a sair, tem funcionamento semelhante a uma Fila de estrutura de dados, FIFO(First in First out), para entendermos melhor vamos pegar um exemplo, imaginemos um supermercado que tem exatamente k vagas em seu estoque, e que seu estoque está totalmente ocupado por produtos antigos, então foi lançado um novo produto no mercado que está sendo um sucesso, mas não temos mais vagas no nosso estoque. Então para cadastrar o novo produto verificamos em nosso estoque qual é o produto mais antigo, ou seja o produto que foi cadastrado primeiro em nosso sistema, assim temos um total de k-1 produtos cadastrados, e podemos inserir o novo produto.

Dessa mesma forma funciona o algoritmo de substituição de páginas, o sistema operacional mantém uma lista com todas as páginas que estão atualmente na memória, onde a página mais antiga encabeça a lista, e a página mais recente está no final da mesma, assim se ocorrer uma falta de página, a primeira página da lista é removida, e a nova página é inserida no final da lista. Quando aplicamos essa técnica em nosso sistema de estoque, o produto que saiu da lista poderia ser um chapéu que não está mais sendo vendido, mas também podemos remover arroz ou feijão, que são produtos que são altamente vendáveis, este problema também pode acontecer com a lista de páginas, onde não temos a certeza se a página que vai ser excluída da lista será uma página que não está sendo mais utilizada, ou se é uma página que está sendo bastante usada, por isso não se tem uma implementação pura desse algoritmo de substituição FIFO.

2. Algoritmo de Substituição de Página Segunda Chance (SC).

O algoritmo de segunda chance funciona da mesma forma que funciona o algoritmo

FIFO, com uma diferença verifica-se um campo chamado R, para verificar se a página foi recentemente utilizada ou não, assim supomos que temos uma lista A, B, C, D, se vier uma nova página para ser inserida na memoria, a página A teoricamente seria excluída, mas o algoritmo de segunda chance, como dito anteriormente verifica um campo chamado de R, esse campo pode assumir dois valores 0 se a página não está mais sendo usada e 1 se a página foi recentemente utilizada, assim supondo que a página A tem o campo R com valor 1, então ela é removida da primeira posição da fila e colocada no final da mesma, só que com o campo R = 0, então a busca continua, até que ele encontre uma página que esteja no inicio da fila e com o campo R = 0, se por exemplo os campos B, C, e D estavam com o campo R = 1, então quando ele verificar todos as páginas, a página A estará novamente na primeira posição da lista, só que dessa vez com o campo R = 0, e assim ela agora poderá ser substituída.

Então podemos perceber que esse algorítimo sempre terá um fim, nunca ficará numa consulta constante.

3. Algoritmo de Substituição de Página Relógio.

Mesmo sabendo que o algoritmo de Substituição de Página Segunda Chance, é razoável devemos levar em consideração que ele fica inserindo as páginas constantemente no final da fila, o que não é bom, então para resolvermos isso tem o algoritmo de substituição de página relógio, o seu funcionamento é o mesmo, a diferença é que a lista é organizada em forma circular, e um ponteiro fica apontando para o mais antigo da fila, quando ocorre uma falta de página, a página para a qual o ponteiro está apontado, é verificada se o seu campo R tiver com valor 1, o campo R daquela página passa a receber o valor 0 e ponteiro passa para a página vizinha, até encontrar uma página com o campo R = 0 e poder substituir pela página que foi requisitada. Por ele ter sua lista organizada de forma circular e ter um ponteiro apontando para a página mais antiga, esse algoritmo é chamado de 3. Algoritmo de Substituição de Página Relógio.

Comentários