Paginação, Deadlocks e Starvation

Um outro algoritmo com muito pouco overhead na implementação é o FIFO (Primeiro-a-Entrar, Primeiro-a-Sair). Para ilustrar seu funcionamento, considere um supermercado que tem prateleiras suficientes para armazenar exatamente K produtos diferentes. Certo dia, alguma indústria introduz um novo tipo de alimento que faz um tremendo sucesso comercial. Nosso supermercado deve, então, arranjar um jeitinho pra vendê-lo, eliminando de suas prateleira algum outro produto.

Uma possibilidade é descobrir qual dos produtos este supermercado vem estocando há mais tempo e livrar-se dele. De fato, tal decisão é tomada com facilidade, pois o supermercado mantém uma fila ligada de todos os produtos vendidos atualmente, na ordem em que eles entraram pela primeira vez no estoque. O mais novo está no fim da fila, e o mais velho o início, devendo este ser eliminado.

Em algoritmos de substituição de páginas, a mesma idéia pode ser aplicada. O sistema operacional mantém uma fila de todas as páginas que estão na memória, com a página no topo da fila sendo a mais antiga e a do fim da fila a que chegou há menos tempo. Na ocorrência de uma falta de página, a página do início deve ser removida, sendo a nova página adicionada ao fim desta fila. Quando aplicado ao problema do supermercado, o algoritmo FIFO tanto pode remover um dos itens mais vendidos, como sal ou manteiga, quanto um dos menos vendidos, como sacos de lixo. Quando aplicada aos computadores, o mesmo problema ocorre. Por isso, o algoritmo FIFO, em sua forma pura, nunca é usado.