6^{\underline{\mathbf{a}}} Questão: O algoritmo de substituição aleatória (Random) escolhe uma página para substituir sem considerar histórico de uso.
(a) Liste ao menos uma vantagem e uma desvantagem dessa abordagem. (b) Em que tipo de sistema ou cenário esse algoritmo pode ser útil? Dê exemplos.

Passo 1

O enunciado diz que o algoritmo de substituição “Random” escolhe uma página para substituir sem considerar histórico de uso.
Perguntas pedidas:
(a) Liste ao menos uma vantagem e uma desvantagem dessa abordagem.
(b) Em que tipo de sistema ou cenário esse algoritmo pode ser útil? Dê exemplos.
Informações relevantes fornecidas: o algoritmo seleciona a vítima de forma aleatória, isto é, não usa informações de recência, frequência, bits de referência, ou qualquer histórico.

Passo 2

O que é o problema de substituição de páginas (resumo didático):
  • Em sistemas com memória virtual temos um conjunto de quadros de memória física (frames) que armazenam páginas.
  • Quando o processo referencia uma página que não está em memória, ocorre uma falta de página (page fault) e o sistema precisa trazer a página da memória secundária e, se não houver frame livre, escolher uma página em memória para expulsar (substituir).
  • O objetivo é escolher uma vítima de modo a minimizar o número de faltas de página (ou maximizar a razão de acertos, hit ratio). Uma forma de medir é a razão de acertos:
\text{hit\_ratio}=\frac{\text{número de acertos}}{\text{número de acessos}}.úú
  • Muitos algoritmos (LRU, FIFO, Ótimo) tentam usar informação sobre uso passado para melhorar essa métrica porque programas tendem a apresentar localidade (tempos curtos de referências à mesma página).

Passo 3

Descrição do algoritmo Random (passo a passo simples):
  • Suponha que existam N frames ocupados. Quando for preciso escolher uma vítima, o algoritmo gera um número aleatório i uniformemente em \{1,\dots,N\} e escolhe o frame i para expulsar.
  • Não mantém bits de referência, contadores, filas ou listas. A operação de escolha é de tempo constante O(1) (gerar um inteiro aleatório e indexar).

Passo 4

Vantagens — explicação detalhada e por que conta como vantagem:
  • Simplicidade e baixo overhead: não precisa de estruturas de dados para manter histórico (listas, timestamps, bits de referência). Na prática isso significa menos código, menos leitura/gravação de metadados, e escolha da vítima em tempo constante. Em sistemas com recursos limitados (CPU lento, memória muito pequena), essa economia é importante.
  • Robustez contra padrões adversariais: como a decisão é aleatória, um atacante ou uma sequência de acessos especificamente construída para explorar um comportamento determinístico (por exemplo, causar thrashing em FIFO ou LRU) não consegue forçar sempre o mesmo resultado. Em palavras simples: Random pode evitar pior caso extremo que explora previsibilidade.
  • Quando o padrão de acesso já é praticamente aleatório, Random tem desempenho parecido com outras políticas (não perde muito).
Exemplo concreto de como é rápido: para escolher uma vítima basta executar “vítima = rand() mod N” e expulsar o frame correspondente — nenhuma leitura de bits de referência e nenhuma atualização de estruturas.

Passo 5

Desvantagens — explicação detalhada e por que conta como desvantagem:
  • Ignora localidade e histórico: pode expulsar justamente uma página que será referenciada imediatamente após, causando muitas faltas adicionais. Isso tende a resultar em uma taxa de faltas maior do que algoritmos que usam recência (LRU) ou frequência (LFU).
  • Performance média geralmente pior: em cargas de trabalho típicas (com forte localidade temporal e espacial) políticas como LRU ou CLOCK obtêm bem menos faltas; Random perde essa vantagem.
  • Difícil dar garantia de limite inferior de faltas: embora seja aleatório, a expectativa de número de faltas geralmente é maior que a de algoritmos informados. Em resumo, simplicidade vem à custa de eficiência.
Ilustração simples: se um processo usa duas páginas alternadamente e temos apenas uma moldura livre, Random tem 50% de chance de expulsar a página necessária — resultando numa falta quase a cada acesso; LRU conseguiria manter a página correta e evitar faltas.

Passo 6

Cenários e exemplos práticos onde Random pode ser útil (explicação e justificativa):
  • Sistemas embarcados ou microcontroladores com recursos muito limitados: quando não há hardware para bits de referência nem espaço para tabelas auxiliares, Random é uma escolha válida por simplicidade. Exemplo: firmware simples de dispositivos IoT com memória escassa.
  • Boot loaders e estágios iniciais do sistema operacional: fases onde a complexidade precisa ser mínima e a sobrecarga de manter histórico não compensa.
  • Ambientes onde a carga de trabalho é essencialmente aleatória: por exemplo, caches para workloads de hashing distribuído que já acessam itens de forma pseudo-aleatória — aí Random terá desempenho similar a políticas mais sofisticadas.
  • Segurança — mitigação de ataques: em caches de hardware ou software onde uma política determinística pode ser explorada por ataques de canal lateral (eviction-based side-channel attacks), randomizar evicções dificulta o atacante. Exemplo: mecanismos de substituição em caches de CPU projetados para reduzir previsibilidade.
  • Testes e simulações: para avaliar o comportamento médio de um sistema ou como baseline simples contra o qual comparar algoritmos mais sofisticados.
  • Dispositivos com memória flash onde se quer espalhar escritas (wear-leveling): embora wear-leveling seja uma preocupação diferente, em alguns esquemas simples a seleção aleatória reduz concentração de escritas sobre poucas células — mas cuidado: esse uso costuma requerer adaptações além de um Random puro.

Passo 7

Como responder isso na prova (formule curto e eficaz):
  • Para (a) escreva uma frase para a vantagem e outra para a desvantagem, por exemplo: “Vantagem: muito simples e de baixo overhead; Desvantagem: não considera localidade e tende a aumentar faltas de página.”
  • Para (b) cite 2–3 cenários curtos: “uso em sistemas embarcados com poucos recursos; estágios iniciais do SO; cenários onde se quer reduzir previsibilidade por segurança; workloads efetivamente aleatórios.”
    Dica: se o examinador pedir justificativa, explique brevemente “simplicidade” e “ignora localidade” como fizemos — isso mostra que você sabe o porquê e não apenas memoriza.

Resposta

(a) Vantagem: muito simples e de baixo overhead (escolha da vítima em tempo constante), além de ser robusto contra padrões adversariais; Desvantagem: ignora localidade e histórico, o que geralmente provoca maior taxa de faltas de página comparado a algoritmos informados (como LRU).
(b) Útil em sistemas com recursos limitados (por exemplo, firmware/IoT embarcado), em estágios iniciais do boot do sistema, em workloads essencialmente aleatórios, para mitigar ataques que exploram previsibilidade de substituição (alguns cenários de segurança), ou como baseline em testes/simulações.

Exercícios relacionados