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):
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.
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:
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.