Please enable JavaScript.
Coggle requires JavaScript to display documents.
Cap 17 : Paginação em Disco - Coggle Diagram
Cap 17 : Paginação em Disco
Estendendo a memória RAM
A memória RAM e um recursos caro, escasso e que consome muita energia
Muitas vezes é necessário usar o espaço em disco para ajudar a RAM. Os mecanismos de memória virtual permitem fazer isso
Partes ociosas da memória podem ser transferidas para o disco. Deverão ser trazidas de volta posteriormente. Feito de forma transparente para os processos
Overlays: o programador organiza o programa em módulos que são carregados em uma mesma região em momentos diferentes. São gerenciados um uma biblioteca específica. Raramente usada hoje em dia, exige muito esforço do programador
Swapping: mover um processo ociosa da RAM para o disco. Quando esse processo for acordado ele é carregado de volta. Pouco usada em sistemas de uso geral
Paging: mover páginas individuais, conjuntos ou segmentos para o disco. Se um processo tentar acessar uma dessas páginas gera interrupção e a página é recarregada. Mais usada por sua flexibilidade, rapidez e eficiência
A paginação em Disco
Mecanismo básico
A transferência de páginas entre memória e disco é feita pelo núcleo do sistema
A MMU alerta o núcleo quando um processo tenta acessar a página, o núcleo traz a página de volta
O núcleo escolhe as páginas para retirar da memória
Para cada página transferida a tabela de páginas do processo é ajustada: o flag de presença da página na RAM é desligado e posição muda
A área do disco destinada a fazer o armazenamento externo das páginas é chamada área de troca
Quando um processo acessa uma página a MMU verifica se ela está na RAM. Se não estiver gera interrupção e desvia para o SO. Se a página é válida o processo é suspenso enquanto o SO transfere a página de volta para a RAM. O processo é acordado e pode acessar a página. Se não houver espaço na RAM um página deverá ir ao disco antes de trazer de volta a outra
Para ter menos demora é usado um daemon para escolher e transferir páginas para o disco que a memória livre estiver abaixo de um limite
Registradores especiais ajudam na tarefa de reexecução do processo que gerou page fault
Eficiência
Um disco rígido tem um tempo de acesso cerca de 100 000 vezes maior que a RAM
Faltas de páginas frequentes geram muitos acessos ao disco reduzindo desempenho
Sistemas com memória insuficiente ou sobrecarregada podem gerar muitas faltas de páginas
Processos que agrupam seus acessos a poucas páginas em cada momento geram menos falta de páginas
Caso sejam removidas páginas usadas com muita frequência isso aumentará o número de falta de páginas
Critérios de Seleção
Critérios usados para selecionar a página que será movida para o disco caso falte espaço na RAM
Idade da Página: há quanto tempo a página está na memória, páginas antigas tendem a ser menos usadas
Frequência de acesso à página: páginas muito acessadas recentemente provavelmente serão acessadas no futuro próximo
Data do último acesso: páginas há mais tempo sem acessos possivelmente não serão acessadas em um futuro próximo
Prioridade do processo proprietário: processos de alta prioridade podem precisar de suas páginas rapidamente
Conteúdo da página: páginas cujo conteúdo seja código executável exigem menos esforço do mecanismo de paginação
Páginas especiais: páginas contendo buffers de entrada/saída podem gerar dificuldades ao núcleo caso não estejam na RAM no momento certo. Páginas com informações sensíveis ficam na RAM por segurança
Algoritmos Clássicos
Cadeia de referências
A cadeia de referências indica a sequência de páginas acessadas por um processo ao longo de sua execução
Ao submeter a cadeia de referência aos diferentes algoritmos é possível testar suas eficiências
Acessos consecutivos à mesma página não relevantes para a análise. Somente o primeiro acesso pode gerar page fault
Algoritmo FIFO
Considerar o tempo que cada página está na memória
Basta organizar as páginas em uma fila FIFO
É simples porém não apresenta bons resultados. Não leva em conta a importância da página. Páginas carregadas há muito tempo podem ser constantemente acessadas
Algoritmo Ótimo
A melhor página para remover é aquela que ficará mais tempo sem ser usada
Como o comportamento futuro dos processos não pode ser previsto com precisão esse algoritmo não é implementável
Define um limite máximo para o desempenho
Algoritmo LRU
A escolha são as páginas que estão há mais tempo sem ser acessadas
Simétrico ao ótimo em relação ao tempo
Parte do pressuposto que páginas recentemente acessadas serão acessadas novamente em um futuro próximo. Essa hipótese geralmente se verifica na prática se os processos respeitam a localidade de referência
Prejudicado por um padrão de acessos sequencial
Algoritmo RANDOM
Escolhe aleatoriamente as páginas a retirar da memória.
Pode ser útil em casos onde a abordagem LRU e FIFO tem baixo desempenho
Usado por alguns sistemas operacionais antigos
Comparação entre os algoritmos
Ótimo possui o melhor desempenho
RANDOM tem o pior desempenho
Aproximações do LRU
O LRU completo é pouco usado na prática pois precisa registrar muitas datas. Além disso ele precisa varrer muitos valores o que consome muito processamento
As aproximações são mais simples e piores, por isso só são usadas em SOs mais simples
Algoritmo da Segunda chance
Uma melhoria simples do FIFO que consiste em analisar o bit de referência de cada página para ver se ela foi acessada recentemente
Caso tenha acesso recente ela recebe uma segunda chance e não sai da RAM
Problemas se todas as páginas forem muito acessadas. Fica igual ao FIFO
Implementado através de uma lista circular de números de páginas, ordenadas por ordem de chegada
Algoritmo do relógio
Algoritmo NRU
Considera não só o bit de referência como também o de modificação que indica se o conteúdo foi modificado
Classifica em quatro níveis de importância segundo R e M
R = 0 , M = 0 : Melhores candidatas à substituição, podem ser retiradas da memória
R = 0, M = 1: Não são escolhas tão boas. Precisam ser gravadas na área de troca antes de ser substituídas
R = 1, M = 0: Provavelmente páginas de código que estão sendo usadas ativamente
R = 1, M = 1: A pior escolha. Precisam ser gravadas e provavelmente serão necessárias em breve
Algoritmo do envelhecimento
Usar os bits de referência para construir contadores de acesso
Periodicamente o algoritmo varre a tabela e agrega o valor do bit de referência ao contador e o ajusta para 0
Não deve ser uma simples soma: overflow muito rápido e não permite diferenciar antigos de novos acessos
Deslocar o bit do contador para a direita: Acessos mais recentes tem peso maior
Páginas menos acessadas envelhecerão ficando com contadores menores
Conjunto de Trabalho
O conjunto de páginas acessadas na história recente de um processo é chamado Conjunto de Trabalho
A composição do conjunto de trabalho é dinâmica, variando a medida que o processo executa
O tamanho e composição do conjunto de trabalho dependem do número de páginas consideradas em sua história recente
A escolha precisa do tamanho recente não é crítica ; Exponencial inversa
Se um processo tiver todas as páginas de seu conjunto de trabalho carregadas na memória ele sofrerá pouca falta de páginas
Algoritmo que só substitui páginas que não estão no conjunto de trabalho de nenhum processo ativo
Difícil de implementar. É preciso manter atualizados os conjuntos de trabalho
Verificar então que páginas o processo acessou recentemente pelo bit de referência
WSClock define um prazo de validade para as páginas; A idade é o tempo atual menos o tempo de acesso
Ao encontrar uma página com bit de referência 1, atualiza a data de acesso e muda o bit para 0
Ao encontrar um página com bit de referência 0, se a idade for menor que o prazo a página está no conjunto de trabalho, se for maior e a página não foi modificada ele pode ira para o disco
Caso o ponteiro dê a volta e não encontra página para substituir substitui a mais antiga com devida prioridade
Anomalia de Belady
Espera-se que quanto mais memória física o sistema possua menos falta de páginas
Alguns algoritmos possuem comportamento atípico contrário
Esse comportamento atípico é chamado Anomalia de Belady
Algoritmos de Pilha, como OPT e LRU não apresentam a anomalia
Thrashing
Caso a soma de todos os conjuntos de trabalho dos processos prontos para execução seja maior que a memória RAM disponível no sistema, poderá ocorrer um fenômeno conhecido como thrashing
Cada vez que um processo recebe o processador gera uma falta de página e ele é suspenso até seu conjunto de trabalho ser carregado
Um sistema operacional sob thrashing tem seu desempenho muito prejudicado a ponto de se tornar inutilizável
Mudar a política de escalonamento durante o thrashing para evitar a competição de memória
Suspender em massa os processos ativos, adotar uma política de escalonamento que considere o uso de memória, aumentar o quantum do processador ou abortar processos com maior atividade de paginação
Para carregar um conjunto de trabalho é necessário remover outro. O processador fica mais tempo transferindo página do que executando processos