4^{\underline{\mathbf{a}}} Questão: O algoritmo Clock utiliza um ponteiro circular e bits de referência para decidir a substituição de páginas.
(a) Explique o funcionamento do algoritmo. (b) Simule a sequência de acessos 3, 2, 1, 3, 4, 1, 2, 5, 3, 4 com 3 frames. (c) Quantos page faults ocorreram? Mostre o estado do ponteiro a cada passo.

Passo 1

O enunciado pede três coisas:
  • (a) Explique o funcionamento do algoritmo Clock (com ponteiro circular e bits de referência).
  • (b) Simule a sequência de acessos (3,2,1,3,4,1,2,5,3,4) usando \;3\; frames.
  • (c) Informe quantos page faults ocorreram e mostre o estado do ponteiro a cada passo.
Informações dadas e convenções óbvias do enunciado:
  • String de referência: (3,2,1,3,4,1,2,5,3,4).
  • Número de frames: \;3\;.
  • Vou chamar os frames de F_0, F_1, F_2.
  • Vou mostrar para cada passo: a página referenciada, se houve hit/fault, a ação realizada, o conteúdo dos frames com os bits de referência e a posição do ponteiro p após a ação.

Passo 2

O que é e como funciona o algoritmo Clock (explicação didática, passo a passo).
  • Ideia intuitiva: o Clock é uma versão eficiente do LRU aproximado. Em vez de manter uma lista ordenada pelo uso, cada frame tem um bit de referência R que indica se a página foi usada recentemente. Há um ponteiro circular (a “mão do relógio”) que aponta para o próximo candidato a substituição.
  • Variáveis/objetos importantes:
    • F_i: o i-ésimo frame, guarda uma página ou está vazio.
    • R_i: bit de referência associado a F_i. R_i=1 significa “usada recentemente”; R_i=0 significa “não usada recentemente”.
    • p: ponteiro (hand) que aponta para o frame a ser verificado na próxima substituição.
  • Regras de operação (forma operacional, passo a passo):
    1. Ao acessar uma página x:
      • Se x já está em algum F_i (hit): coloque R_i \leftarrow 1. (Marca que foi usada agora.)
      • Se x não está (page fault):
        a. Se existe um frame vazio, carregue x no frame apontado por p (ou no primeiro frame vazio encontrado, conforme implementação) e coloque R\leftarrow 1. Avance p para o próximo frame (o próximo candidato).
        b. Se não há frame vazio, faça uma varredura iniciando em p: examine R_p.
        • Se R_p = 0: substitua a página em p por x, coloque R_p \leftarrow 1 e avance p para o próximo frame; fim.
        • Se R_p = 1: coloque R_p \leftarrow 0, avance p e continue a varredura até encontrar um frame com R=0.
  • Observações práticas:
    • O ponteiro sempre aponta para o próximo candidato a ser verificado. Após uma substituição o ponteiro avança para o próximo frame.
    • Em acessos que são hits, normalmente não se move o ponteiro (apenas se marca R=1).
  • Vou adotar as convenções explícitas para esta simulação:
    • Ponteiro inicial: p aponta para F_0 antes do primeiro acesso.
    • Ao colocar uma página num frame vazio (primeiros carregamentos), eu coloco no frame apontado por p, defino R=1 e avanço p para o próximo frame.
    • Em hits, p NÃO se move (só R é ajustado).
    • Após cada substituição bem-sucedida, p aponta para o frame seguinte ao substituído.

Passo 3

Configuração inicial e notação que vou usar:
  • Frames inicializados vazios:
    • F_0: \_\; (R=\_), F_1: \_\; (R=\_), F_2: \_\; (R=\_).
  • Ponteiro inicial: p \to F_0.
  • Notação do estado: por exemplo F_0:3(1) significa que F_0 contém a página 3 e tem R=1.
  • Vou enumerar passo por passo para cada referência da string.

Passo 4

Referência 1: página \;3\;.
  • Estado inicial: F_0:\_, F_1:_), F_2:_), p\to F_0.
  • \;3\; não está em memória → page fault.
  • F_0 está livre (apontado por p). Carrego 3 em F_0, defino R_0=1. Avanço p para F_1.
  • Estado após a ação:
    • F_0:3(1),\; F_1:\_\;(\_ ),\; F_2:\_\;(\_).
    • Ponteiro: p \to F_1.
  • Page fault? Sim.

Passo 5

Referência 2: página \;2\;.
  • Estado antes: F_0:3(1),\; F_1:\_\;,\; F_2:\_\;,\; p\to F_1.
  • \;2\; não está → page fault.
  • F_1 está livre. Carrego 2 em F_1, R_1=1. Avanço p para F_2.
  • Estado após:
    • F_0:3(1),\; F_1:2(1),\; F_2:\_\;(\_).
    • p \to F_2.
  • Page fault? Sim.

Passo 6

Referência 3: página \;1\;.
  • Estado antes: F_0:3(1),\; F_1:2(1),\; F_2:\_\;,\; p\to F_2.
  • \;1\; não está → page fault.
  • F_2 vazio. Carrego 1 em F_2, R_2=1. Avanço p para F_0.
  • Estado após:
    • F_0:3(1),\; F_1:2(1),\; F_2:1(1).
    • p \to F_0.
  • Page fault? Sim.

Passo 7

Referência 4: página \;3\;.
  • Estado antes: F_0:3(1),\; F_1:2(1),\; F_2:1(1),\; p\to F_0.
  • \;3\; já está em F_0 → HIT.
  • Em hit: defino R_0 \leftarrow 1 (já era 1). Não movo o ponteiro.
  • Estado após:
    • F_0:3(1),\; F_1:2(1),\; F_2:1(1).
    • p \to F_0.
  • Page fault? Não.

Passo 8

Referência 5: página \;4\;.
  • Estado antes: F_0:3(1),\; F_1:2(1),\; F_2:1(1),\; p\to F_0.
  • \;4\; não está → page fault. Não há frames vazios, precisa substituir.
  • Começo a varredura em p (que aponta para F_0):
    1. F_0: R_0=1 → ponho R_0 \leftarrow 0, avanço p \to F_1.
    2. F_1: R_1=1 → ponho R_1 \leftarrow 0, avanço p \to F_2.
    3. F_2: R_2=1 → ponho R_2 \leftarrow 0, avanço p \to F_0.
    4. F_0: agora R_0=0 → encontro candidato. Substituo 3 por 4 em F_0, ponho R_0 \leftarrow 1, avanço p \to F_1. Fim.
  • Estado após:
    • F_0:4(1),\; F_1:2(0),\; F_2:1(0).
    • p \to F_1.
  • Page fault? Sim.

Passo 9

Referência 6: página \;1\;.
  • Estado antes: F_0:4(1),\; F_1:2(0),\; F_2:1(0),\; p\to F_1.
  • \;1\; está em F_2 → HIT.
  • Em hit: defino R_2 \leftarrow 1. Não movo p.
  • Estado após:
    • F_0:4(1),\; F_1:2(0),\; F_2:1(1).
    • p \to F_1.
  • Page fault? Não.

Passo 10

Referência 7: página \;2\;.
  • Estado antes: F_0:4(1),\; F_1:2(0),\; F_2:1(1),\; p\to F_1.
  • \;2\; está em F_1 → HIT.
  • Em hit: defino R_1 \leftarrow 1. Não movo p.
  • Estado após:
    • F_0:4(1),\; F_1:2(1),\; F_2:1(1).
    • p \to F_1.
  • Page fault? Não.

Passo 11

Referência 8: página \;5\;.
  • Estado antes: F_0:4(1),\; F_1:2(1),\; F_2:1(1),\; p\to F_1.
  • \;5\; não está → page fault. Todos ocupados → varredura a partir de p=F_1:
    1. F_1: R_1=1 → ponho R_1 \leftarrow 0, avanço p \to F_2.
    2. F_2: R_2=1 → ponho R_2 \leftarrow 0, avanço p \to F_0.
    3. F_0: R_0=1 → ponho R_0 \leftarrow 0, avanço p \to F_1.
    4. F_1: agora R_1=0 → substituo 2 por 5 em F_1, ponho R_1 \leftarrow 1, avanço p \to F_2. Fim.
  • Estado após:
    • F_0:4(0),\; F_1:5(1),\; F_2:1(0).
    • p \to F_2.
  • Page fault? Sim.

Passo 12

Referência 9: página \;3\;.
  • Estado antes: F_0:4(0),\; F_1:5(1),\; F_2:1(0),\; p\to F_2.
  • \;3\; não está → page fault. Varredura a partir de p=F_2:
    1. F_2: R_2=0 → candidato encontrado imediatamente. Substituo 1 por 3 em F_2, ponho R_2 \leftarrow 1, avanço p \to F_0. Fim.
  • Estado após:
    • F_0:4(0),\; F_1:5(1),\; F_2:3(1).
    • p \to F_0.
  • Page fault? Sim.

Passo 13

Referência 10: página \;4\;.
  • Estado antes: F_0:4(0),\; F_1:5(1),\; F_2:3(1),\; p\to F_0.
  • \;4\; está em F_0 → HIT.
  • Em hit: defino R_0 \leftarrow 1. Não movo p.
  • Estado final após toda a string:
    • F_0:4(1),\; F_1:5(1),\; F_2:3(1).
    • p \to F_0.
  • Page fault? Não neste passo.

Resposta

(a) Algoritmo Clock: cada frame tem um bit de referência R. Um ponteiro p percorre os frames em círculo; em hit define-se R\leftarrow1. Em page fault, se houver frame vazio insere-se nele com R=1 e avança p; se não, varre-se a partir de p: ao achar R=1 zera-se R e avança; ao achar R=0 substitui-se essa página por nova, define-se R=1 e avança p.
(b) Estado final após a simulação: F_0:4(1),\; F_1:5(1),\; F_2:3(1); ponteiro p \to F_0.
(c) Número de page faults: 6.

Exercícios relacionados