Powerpoint Sobre WSClock

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Sistemas de Computação
Algoritmo Working Set
Algoritmo Working Set Clock
Anomalia de Belady
Carolina Fernandes
Marcello Lins
Working Set
É o conjunto de páginas que um processo está referenciando em um determinado tempo.
Objetivo principal: reduzir a ocorrência de page faults, carregando na memória as páginas do WS do processo antes que o mesmo continue a sua execução. Esse processo ocorre através da pré-paginação.
Função w(k,t): Retorna a quantidade de páginas usadas pelas k referências do WS em um dado instante t.
Working Set
Implementação:
O SO precisa manter registro de que páginas estão no working set.
Quando ocorre um page fault, ele encontra uma página fora do working set e a remove, caso não haja mais nenhuma moldura livre.
Working Set
Algoritmo:
O hardware define os bits R e M. Em cada ciclo do clock, o bit de referência é limpo.
O tempo do working set se estende por vários ciclos do clock
Em cada page fault, a tabela de páginas inteira é buscada
À medida que cada entrada é processada, examine R
Se 1, escreva o tempo virtual corrente no campo Tempo do Último Uso (TLU), indicando que a página estava em uso no instante da page fault, ou seja, estava no working set e, por isso, não é candidata.
Working Set
Algoritmo:
Em cada page fault, a tabela de páginas inteira é buscada
À medida que cada entrada é processada, examine R
Se R=0, a página não foi referenciada no ciclo atual, e pode ser uma candidata
Nesse caso, se sua idade for maior que o intervalo t do working set, ela não está nele, e pode ser removida
A busca continua atualizando as demais entradas
Se, contudo, a idade for menor que t, a página é poupada e a página com maior idade é marcada
Se nenhum candidato for encontrado (todas as páginas estão no working set), substitua a página mais velha, dentre as com R=0
Working Set
Working Set Clock
Na troca de páginas baseada no algoritmo Working Set, há uma varredura por toda a tabela de páginas.
O algoritmo de WSClock permite que apenas as páginas presentes em uma lista circular sejam avaliadas.
Algoritmo:
Cada página possui os bits R e M, além de um timestamp (tempo da última referência).
Quando a primeira página é carregada, ela é inserida na lista, inicialmente vazia.
A cada page fault, a página da cabeça é examinada primeiro para remoção.
Working Set Clock
Algoritmo:
Se R=1, a página já foi usada durante o ciclo de clock corrente e, por isso, não é candidata a remoção. Faz-se R=0 e avança-se a cabeça à próxima página, repetindo o algoritmo para esta.
Se R=0, verifica-se se a idade é maior que o tamanho do WS t e se a página está limpa (M=0). Se sim, a página é substituída e a cabeça da lista avança. Se a página estiver suja, agenda-se uma escrita ao disco, evitando troca de processo e avança-se a cabeça da lista, prosseguindo para a página seguinte.
Working Set Clock
Algoritmo:
Se a cabeça der uma volta completa na lista sem substituir e pelo menos uma escrita em disco for agendada, a cabeça continua se movendo em busca de uma página limpa. Em algum momento a lista agendada será executada, marcando a página como limpa.
Caso nenhuma escrita tenha sido agendada, todas as páginas estão no working set e, na falta de informações adicionais, qualquer página limpa pode ser substituida. Se não existirem páginas limpas, qualquer uma pode ser escolhida e escrita no disco.
Working Set Clock
Anomalia de Belady
Geralmente, quanto maior o número de molduras, menor o número de Page Faults, mas a Anomalia de Belady prova nem sempre isso é verdadeiro.
Contra-exemplo para páginas referenciadas pela ordem 0 1 2 3 0 1 4 0 1 2 3 4: