Paginacao e Substituicao de Paginas
Video da aula estara disponivel em breve
O Problema da Substituicao
Quando ocorre um page fault e nao ha frames livres na RAM, o SO precisa evictar (remover) uma pagina existente para liberar espaco. Qual pagina remover? Essa decisao e critica para performance.
Algoritmo Otimo (Belady)
Substituir a pagina que nao sera usada por mais tempo no futuro. Impossivel de implementar na pratica (requer prever o futuro), mas serve como benchmark para outros algoritmos.
Exemplo — Algoritmo Otimo
Referencia: 7 0 1 2 0 3 0 4 2 3 0 3 2
Frames: 3
|Ref| Frame 0 | Frame 1 | Frame 2 | Fault? |
|----|---------|---------|---------|--------|
| 7 | 7 | | | Sim |
| 0 | 7 | 0 | | Sim |
| 1 | 7 | 0 | 1 | Sim |
| 2 | 2 | 0 | 1 | Sim | evict 7 (mais distante)
| 0 | 2 | 0 | 1 | Nao |
| 3 | 2 | 0 | 3 | Sim | evict 1 (mais distante)
| 0 | 2 | 0 | 3 | Nao |
| 4 | 2 | 4 | 3 | Sim | evict 0 (mais distante)
| 2 | 2 | 4 | 3 | Nao |
| 3 | 2 | 4 | 3 | Nao |
| 0 | 2 | 0 | 3 | Sim | evict 4
| 3 | 2 | 0 | 3 | Nao |
| 2 | 2 | 0 | 3 | Nao |
Total: 7 page faults (minimo possivel)FIFO — First In, First Out
Remove a pagina que esta na RAM ha mais tempo. Simples, mas ignora frequencia de uso.
Exemplo — FIFO
Mesma referencia: 7 0 1 2 0 3 0 4 2 3 0 3 2
Frames: 3
|Ref| Frame 0 | Frame 1 | Frame 2 | Fault? | Evict |
|----|---------|---------|---------|--------|----------|
| 7 | 7 | | | Sim | |
| 0 | 7 | 0 | | Sim | |
| 1 | 7 | 0 | 1 | Sim | |
| 2 | 2 | 0 | 1 | Sim | 7 (mais antigo) |
| 0 | 2 | 0 | 1 | Nao | |
| 3 | 2 | 3 | 1 | Sim | 0 |
| 0 | 2 | 3 | 0 | Sim | 1 |
| 4 | 4 | 3 | 0 | Sim | 2 |
| 2 | 4 | 2 | 0 | Sim | 3 |
| 3 | 4 | 2 | 3 | Sim | 0 |
| 0 | 0 | 2 | 3 | Sim | 4 |
| 3 | 0 | 2 | 3 | Nao | |
| 2 | 0 | 2 | 3 | Nao | |
Total: 10 page faults (vs 7 otimo)
Anomalia de Belady
Com FIFO, adicionar mais frames pode aumentar o numero de page faults! Isso e contra-intuitivo e e conhecido como a anomalia de Belady. Nem todos os algoritmos sofrem disso — LRU, por exemplo, e imune.
LRU — Least Recently Used
Remove a pagina que nao e acessada ha mais tempo. Baseado na observacao de que paginas usadas recentemente provavelmente serao usadas novamente (localidade temporal).
Exemplo — LRU
Referencia: 7 0 1 2 0 3 0 4 2 3 0 3 2
Frames: 3
|Ref| Frame 0 | Frame 1 | Frame 2 | Fault? | Evict (LRU) |
|----|---------|---------|---------|--------|------------------|
| 7 | 7 | | | Sim | |
| 0 | 7 | 0 | | Sim | |
| 1 | 7 | 0 | 1 | Sim | |
| 2 | 2 | 0 | 1 | Sim | 7 (LRU: 7,0,1) |
| 0 | 2 | 0 | 1 | Nao | |
| 3 | 2 | 0 | 3 | Sim | 1 (LRU: 1,2,0) |
| 0 | 2 | 0 | 3 | Nao | |
| 4 | 4 | 0 | 3 | Sim | 2 (LRU: 2,3,0) |
| 2 | 4 | 0 | 2 | Sim | 3 (LRU: 3,0,4) |
| 3 | 4 | 3 | 2 | Sim | 0 (LRU: 0,4,2) |
| 0 | 0 | 3 | 2 | Sim | 4 (LRU: 4,2,3) |
| 3 | 0 | 3 | 2 | Nao | |
| 2 | 0 | 3 | 2 | Nao | |
Total: 9 page faults (entre FIFO=10 e otimo=7)Clock Algorithm (Second Chance)
Aproximacao pratica do LRU. Cada frame tem um bit de referencia (R). Frames sao organizados em circulo. O ponteiro do "relogio" varre os frames:
Diagrama — Clock Algorithm
ponteiro
|
v
+---+ +---+ +---+ +---+ +---+
| P7| | P3| | P1| | P5| | P9|
| R=1| | R=0| | R=1| | R=0| | R=1|
+---+ +---+ +---+ +---+ +---+
^ |
|______________________________| (circular)
Quando precisa evictar:
1. Olha frame no ponteiro
2. Se R=1: da "segunda chance" — seta R=0, avanca ponteiro
3. Se R=0: evicta este frame, carrega nova pagina aqui
4. Repete ate encontrar R=0
Exemplo:
Ponteiro em P3 (R=0) -> EVICTA P3!
Se P3 tivesse R=1: seta R=0, avanca para P1
P1 tem R=1: seta R=0, avanca para P5
P5 tem R=0: EVICTA P5!
Vantagem: aproxima LRU sem manter timestamps
Complexidade: O(1) amortizado
Usado: variantes usadas no Linux e outros SOsThrashing
Thrashing ocorre quando o sistema gasta mais tempo fazendo page replacement do que executando processos. Acontece quando ha muitos processos competindo por pouca RAM.
Diagrama — Thrashing
CPU Utilization
^
100% | .---.
| / \
| / \
50% | / \
| / \....... thrashing!
| /
0% +--+-----+-----+-----+-----+-->
2 4 6 8 10
Grau de Multiprogramacao (processos ativos)
A partir de um ponto, adicionar mais processos
DIMINUI o uso de CPU porque todos estao fazendo
page faults continuamente (I/O de disco constante).
Solucao: reduzir grau de multiprogramacao
- Suspender (swap out) processos inteiros
- Usar Working Set para estimar necessidades de cada processoWorking Set
O working set de um processo e o conjunto de paginas que ele referencia em uma janela de tempo recente. Se o SO garante que o working set de cada processo esta em RAM, evita thrashing.
Exemplo — Working Set
Referencia: ...2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3...
^--- janela delta=5 ---^
Working Set no instante t (com delta=5):
Paginas referenciadas nos ultimos 5 acessos: {6, 2, 3, 4, 1}
|WS| = 5 paginas
Regra do Working Set:
Alocar pelo menos |WS| frames para cada processo.
Se sum(|WS_i|) > total de frames disponiveis:
suspenda um processo (reduza multiprogramacao)No harness.os
Substituicao de paginas mapeia diretamente para o problema de gerencia de contexto no harness.os:
Diagrama — Knowledge Eviction = Page Replacement
Memoria Virtual (SO) Context Window (harness.os)
==================== ============================
Frame livre: OK Tokens disponiveis: OK
Frame cheio: page replacement Tokens cheios: compaction/eviction
FIFO: evicta pagina mais antiga Evicta mensagens mais antigas
Problema: remove dados usados Problema: remove contexto util
LRU: evicta menos recente Evicta knowledge nao referenciado
Melhor: mantem dados quentes Melhor: mantem knowledge ativo
Working Set = Knowledge Ativo:
rules + handoff + knowledge do topico atual
Se WS cabe no contexto: sem eviction necessaria
Se WS > contexto: thrashing! (busca constante no banco)
Thrashing no harness.os:
Agente carrega knowledge -> contexto enche
Compaction remove knowledge -> agente precisa de novo
Busca no banco -> mais tokens gastos -> contexto enche
Ciclo vicioso = thrashing!
Solucao: estimar working set antes de carregar
get_knowledge_by_concern("security") em vez de
get_knowledge() que carrega tudo
Python — LRU cache para knowledge
from collections import OrderedDict
class KnowledgeLRU:
"""LRU cache para knowledge no contexto."""
def __init__(self, max_tokens=50000):
self.cache = OrderedDict()
self.max_tokens = max_tokens
self.current_tokens = 0
def access(self, key, content):
"""Acessa knowledge. Move para 'mais recente'."""
if key in self.cache:
self.cache.move_to_end(key)
return self.cache[key]
tokens = count_tokens(content)
# Evict LRU entries ate caber
while self.current_tokens + tokens > self.max_tokens:
evicted_key, evicted = self.cache.popitem(last=False)
self.current_tokens -= count_tokens(evicted)
print(f"Evicted: {evicted_key}")
self.cache[key] = content
self.current_tokens += tokens
return content
def working_set(self):
"""Retorna o working set atual."""
return list(self.cache.keys())Homework
- Para a sequencia de referencias
1 2 3 4 1 2 5 1 2 3 4 5com 3 frames, calcule page faults para FIFO, LRU, e algoritmo otimo. - Demonstre a anomalia de Belady: encontre uma sequencia onde FIFO com 4 frames gera mais faults que com 3 frames.
- No harness.os, estime o "working set" de uma sessao de QA (quais knowledge chunks sao necessarios) vs uma sessao de feature development. Qual e maior? Por que?
Resumo
- Otimo (Belady): benchmark, impossivel na pratica
- FIFO: simples, sofre anomalia de Belady
- LRU: bom, mas caro de implementar perfeitamente
- Clock: aproximacao pratica do LRU, usado em SOs reais
- Thrashing: sistema gasta mais tempo em page faults que em trabalho util
- Working set: conjunto de paginas ativas; mante-lo em RAM evita thrashing
Verifique seu entendimento
O que e thrashing?