Questão de Algoritmos e Estrutura de Dados — Algoritmos — Marinha 2020
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq610734
Banca
Marinha
Órgão
CAP
Ano
2020
Nível
Médio
Cargo
Cabo - Processamento de Dados
A técnica de memória virtual por paginação é organizada em blocos. Esses blocos podem ser alocados em páginas da memória física, mas eventualmente um bloco pode precisar ser substituído para liberar espaço. Assinale a opção que apresenta um algoritmo de substituição de páginas que utiliza um bit adicional, conhecido como bit de referência.
AAleatório.
BFirst-ln-First-Out (FIFO).
CLeast-Frequently-Used (LFU).
DLeast-Recently-Used (LRU).
ENot-Recently-Used (NRU).
Revelar gabarito e comentário▾
GabaritoE — Not-Recently-Used (NRU).
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Algoritmos de substituição de páginas
Gabarito: letra E. O algoritmo NRU (Not Recently Used) utiliza um bit de referência (R) e um bit de modificação (M) para classificar as páginas em quatro classes, escolhendo uma página aleatória da classe de menor ordem para substituição. É o único entre as alternativas que emprega explicitamente um bit de referência adicional.
O enunciado cobra o conhecimento sobre algoritmos de substituição de páginas que utilizam um bit de referência. O NRU é clássico nesse aspecto, conforme descrito na literatura de sistemas operacionais.
Algoritmo
Utiliza bit de referência?
Critério de substituição
Observação
Aleatório
Não
Escolha aleatória
Não considera histórico de acesso
FIFO
Não
Página mais antiga na memória
Baseia-se na ordem de carregamento
LFU
Não
Menor frequência de acesso
Requer contadores de frequência
LRU
Não (implementação exata)
Página menos recentemente usada
Necessita hardware especial (registros de idade)
NRU
Sim (bits R e M)
Página da classe de menor ordem (sem R e sem M)
Divide páginas em 4 classes; bit R é limpo periodicamente
Algoritmos de substituição de páginas
1Sem bit de referência
Aleatório (sem histórico)
FIFO (ordem de carga)
LFU (contador de frequência)
LRU (registro de idade)
2Com bit de referência
NRU (bits R e M)
4 classes (R/M)
Escolhe classe mais baixa
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O algoritmo Aleatório não utiliza nenhum bit de referência; escolhe uma página aleatória sem considerar histórico de acesso.
Alternativa B — ❌ Incorreta
O FIFO (First-In-First-Out) substitui a página que está há mais tempo na memória, baseando-se na ordem de carregamento, não em bits de referência.
Alternativa C — ❌ Incorreta
O LFU (Least Frequently Used) substitui a página com menor frequência de acesso, mas não utiliza um bit de referência único; requer contadores de frequência.
Alternativa D — ❌ Incorreta
O LRU (Least Recently Used) substitui a página menos recentemente usada, mas sua implementação exata exige hardware especial (registros de idade) e não se baseia apenas em um bit de referência. Aproximações como NRU são mais simples.
Alternativa E — ✅ Correta ⟵ GABARITO
O NRU (Not Recently Used) divide as páginas em classes com base nos bits R (referência) e M (modificação). A cada interrupção de relógio, o bit R é limpo; quando uma falta de página ocorre, uma página da classe mais baixa (sem R e sem M) é escolhida aleatoriamente. Esse uso explícito do bit de referência atende perfeitamente ao enunciado.
Fonte: O conteúdo de apoio descreve o NRU como um algoritmo que “divide as páginas em quatro classes, dependendo do estado dos bits R e M” e o classifica como uma “aproximação muito rudimentar do LRU”.