Sistemas Operacionais · FGV · 2023 | Questão sqc-fg063581

Algoritmo de Segunda Chance Aperfeiçoado

Gabarito: letra A. A sequência de remoção de páginas é 3, 5, 1, 6, 2, 4, pois o algoritmo de Segunda Chance Aperfeiçoado prioriza a remoção das páginas não referenciadas e não modificadas (classe 0), depois as não referenciadas e modificadas (classe 1), e assim por diante, percorrendo a fila em ordem circular. A alternativa correta é a letra A. O Algoritmo de Segunda Chance Aperfeiçoado é uma variação do algoritmo da Segunda Chance (ou do Relógio) que utiliza dois bits de status por página: o bit R (referenciada) e o bit M (modificada). Esses bits são combinados para classificar as páginas em quatro classes, conforme a prioridade de remoção:

Classe	R	M	Descrição	Prioridade de remoção
0	0	0	Não referenciada, não modificada	1ª (maior prioridade)
1	0	1	Não referenciada, modificada	2ª
2	1	0	Referenciada, não modificada	3ª
3	1	1	Referenciada, modificada	4ª (menor prioridade)

A lógica é simples: uma página que não foi referenciada recentemente e não foi modificada é a melhor candidata a ser removida, pois não há risco de perder dados e é improvável que seja necessária em breve. Por outro lado, uma página referenciada e modificada é a pior candidata, pois foi usada recentemente e sua remoção exigiria escrita no disco. Na prática, quando ocorre uma falta de página, o sistema operacional percorre a fila de páginas em ordem circular (como um relógio), começando pelo ponteiro atual. Para cada página, ele verifica sua classe:

Se a página é da classe 0, ela é removida imediatamente.
Se a página é da classe 1, ela é removida, mas antes é necessário gravar seu conteúdo no disco (pois foi modificada).
Se a página é da classe 2, o bit R é zerado e a página é movida para o final da fila (ganha uma segunda chance).
Se a página é da classe 3, o bit R é zerado e a página é movida para o final da fila, mas com a ressalva de que, se for escolhida novamente, será necessário gravar no disco.

O algoritmo percorre a fila até encontrar uma página da classe 0 ou 1. Se todas as páginas forem das classes 2 ou 3, ele zera os bits R de todas e recomeça a busca, eventualmente encontrando uma página da classe 0 ou 1. No caso da questão, a figura imagem da questão apresenta o estado inicial da memória com as páginas e seus respectivos bits R e M. Como não haverá novas execuções ou modificações, o algoritmo apenas remove as páginas na ordem de prioridade, começando pela classe 0, depois classe 1, e assim por diante. A sequência correta de remoção é 3, 5, 1, 6, 2, 4, conforme a alternativa A. A pegadinha desta questão está em confundir o Algoritmo de Segunda Chance Aperfeiçoado com o algoritmo FIFO ou com o algoritmo da Segunda Chance simples. No FIFO, a ordem de remoção seria a ordem de chegada das páginas na memória, sem considerar os bits R e M. No algoritmo da Segunda Chance simples, apenas o bit R é considerado, e páginas referenciadas ganham uma segunda chance, mas páginas modificadas não têm tratamento diferenciado. O Algoritmo de Segunda Chance Aperfeiçoado, por sua vez, considera ambos os bits, o que resulta em uma ordem de remoção diferente.

1Classe 0 (R=0, M=0)3, 5
2Classe 1 (R=0, M=1)1, 6
3Classe 2 (R=1, M=0)2
4Classe 3 (R=1, M=1)4

LEVEL · soulevel.com.br

Alternativa A — ✅ Correta ⟵ GABARITO

A sequência 3, 5, 1, 6, 2, 4 está correta porque segue a ordem de prioridade do Algoritmo de Segunda Chance Aperfeiçoado: primeiro as páginas da classe 0 (não referenciadas e não modificadas), depois as da classe 1 (não referenciadas e modificadas), e assim por diante. A página 3 é a primeira da classe 0, seguida pela página 5, também da classe 0. Depois, a página 1 é da classe 1, seguida pela página 6, também da classe 1. Por fim, as páginas 2 e 4 são das classes 2 e 3, respectivamente, completando a sequência.

Alternativa B — ❌ Incorreta

A sequência 3, 5, 2, 4, 6, 1 está incorreta porque coloca as páginas 2 e 4 (classes 2 e 3) antes das páginas 1 e 6 (classe 1). O algoritmo prioriza a remoção das páginas não referenciadas e não modificadas (classe 0), depois as não referenciadas e modificadas (classe 1), e só então as referenciadas. A ordem correta exige que as páginas da classe 1 sejam removidas antes das da classe 2.

Alternativa C — ❌ Incorreta

A sequência 3, 4, 5, 1, 2, 6 está incorreta porque coloca a página 4 (classe 3) logo após a página 3, ignorando que a página 5 (classe 0) e a página 1 (classe 1) têm prioridade maior. O algoritmo não remove uma página referenciada e modificada antes de uma não referenciada e não modificada.

Alternativa D — ❌ Incorreta

A sequência 3, 4, 6, 5, 1, 2 está incorreta porque coloca a página 4 (classe 3) antes das páginas 5 (classe 0) e 1 (classe 1). A página 4, por ser referenciada e modificada, tem a menor prioridade de remoção e só deve ser removida após todas as outras.

Alternativa E — ❌ Incorreta

A sequência 3, 4, 5, 6, 1, 2 está incorreta porque coloca a página 4 (classe 3) antes das páginas 5 (classe 0) e 1 (classe 1). A ordem correta exige que as páginas da classe 0 sejam removidas primeiro, seguidas pelas da classe 1, e só então as das classes 2 e 3.

NÃO CAIA NESSA!

A banca explora a confusão entre o Algoritmo de Segunda Chance Aperfeiçoado e o algoritmo FIFO. No FIFO, a ordem de remoção seria a ordem de chegada das páginas, sem considerar os bits R e M. Já no Segunda Chance Aperfeiçoado, a ordem é determinada pela classe da página, priorizando as não referenciadas e não modificadas. Fique atento aos bits R e M de cada página na figura! 💡 Dica: Para resolver questões sobre o Algoritmo de Segunda Chance Aperfeiçoado, identifique a classe de cada página (0, 1, 2 ou 3) e remova na ordem crescente de classe. Se houver empate dentro da mesma classe, use a ordem da fila (FIFO) como critério de desempate. Pratique com diferentes configurações de bits R e M para fixar o conceito.

Gabarito: letra A