Memória Virtual-2023-2

INE5611 - Sistemas Operacionais Memória Virtual Prof. Eduardo Camilo Inacio, Dr. eduardo.camilo@ufsc.br Universidade Federal de Santa Catarina Departamento de Informática e Estatística Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 1 / 48 Aviso Legal O conteúdo apresentado nestes slides foi baseado parcialmente nos livros abaixo, assim como nos seus respectivos materiais de apoio, quando disponível: OLIVEIRA, R. S.; CARISSIMI, A. S.; TOSCANI, S. S. Sistemas Operacionais. 4. ed. Porto Alegre: Bookman, 2010. 374 p. ISBN 978-85-7780-521-1. TANENBAUM, A. S.; BOS, H. Modern Operating Systems. 4. ed. [S. l.]: Pearson Education, 2015. 1136 p. ISBN 978-0-13-359162-0. SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Operating System Concepts. 9. ed. [S. l.]: Wiley, 2012. 976 p. ISBN 978-1-118-06333-0. Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 2 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 2 / 48 Introdução Técnicas de gerência de memória vistas até o momento carregam para a memória principal todo o programa a ser executado Todo o espaço lógico é mapeado no espaço físico Problemas inerentes a este modelo Tamanho do programa que pode ser executado é limitado pelo tamanho da memória Grau de multiprogramação limitado pelo tamanho da memória Porção da memória “desperdiçada” mantendo código não utilizado frequentemente Funcionalidades raramente usadas de um programa Rotinas de tratamento de erros Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 3 / 48 Introdução Memória virtual é a técnica de gerência de memória que permite a execução de um processo sem que ele esteja completamente carregado na memória física. Páginas/segmentos são carregados na memória principal apenas quando forem necessários Expande a memória total disponível adicionando à memória real um espaço em memória secundária (em geral, disco) chamada área de swap Área organizada de forma diferenciada para otimizar o acesso Páginas/segmentos de um programa podem ser movidos para área de swap para liberar espaço na memória física para carregamento de páginas/segmentos de outros programas Páginas/segmentos na área de swap pode ser trazidas novamente para memória quando necessário Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 4 / 48 Introdução Memória virtual é a técnica de gerência de memória que permite a execução de um processo sem que ele esteja completamente carregado na memória física. Páginas/segmentos são carregados na memória principal apenas quando forem necessários Expande a memória total disponível adicionando à memória real um espaço em memória secundária (em geral, disco) chamada área de swap Área organizada de forma diferenciada para otimizar o acesso Páginas/segmentos de um programa podem ser movidos para área de swap para liberar espaço na memória física para carregamento de páginas/segmentos de outros programas Páginas/segmentos na área de swap pode ser trazidas novamente para memória quando necessário Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 4 / 48 Introdução Memória virtual é a técnica de gerência de memória que permite a execução de um processo sem que ele esteja completamente carregado na memória física. Páginas/segmentos são carregados na memória principal apenas quando forem necessários Expande a memória total disponível adicionando à memória real um espaço em memória secundária (em geral, disco) chamada área de swap Área organizada de forma diferenciada para otimizar o acesso Páginas/segmentos de um programa podem ser movidos para área de swap para liberar espaço na memória física para carregamento de páginas/segmentos de outros programas Páginas/segmentos na área de swap pode ser trazidas novamente para memória quando necessário Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 4 / 48 Introdução Possibilita a execução de programas maiores que a capacidade disponível de memória física Aumenta o grau de multiprogramação Mais programas carregados, em um dado momento, na memória física Memória Lógica Memória Física Área de Swap Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 5 / 48 Introdução Possibilita a execução de programas maiores que a capacidade disponível de memória física Aumenta o grau de multiprogramação Mais programas carregados, em um dado momento, na memória física Memória Lógica Memória Física Área de Swap Memória Lógica Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 5 / 48 Sumário 1 Introdução 2 Implementação Princípio da Localidade de Referência Paginação sob Demanda 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 5 / 48 Implementação Princípio básico: divisão do espaço de endereçamento em porções de memória mantidas parte na memória física, parte no disco Paginação e segmentação oferecem abstrações que satisfazem esta necessidade Ambas podem ser utilizadas para implementar memória virtual Paginação é mais adotada na prática Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 6 / 48 Implementação Sistema operacional precisa controlar o fluxo de páginas (ou segmentos) entre a memória principal (física) e a memória secundária (disco) Gerenciar áreas livres e ocupadas Determinar políticas de alocação de memória física Substituir páginas (ou segmentos) em memória Controlar o compartilhamento e proteção de memória entre processos Suporte de hardware para auxílio e aceleração das tarefas (MMU) Bits de controle de acesso à memória Mecanismos de proteção contra acessos inválidos Tradução de endereço lógico para endereço físico Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 7 / 48 Sumário 1 Introdução 2 Implementação Princípio da Localidade de Referência Paginação sob Demanda 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 7 / 48 Princípio da Localidade de Referência Princípio da localidade de referência está relacionado com a constatação de que, em determinados momentos, acessos a instruções e dados se concentram em uma certa região do espaço de endereçamento do processo. Explorado para manter na memória física apenas partes da memória lógica necessárias para a execução do processo Possibilidade de “adivinhar” as regiões necessárias para sequência da execução Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 8 / 48 Princípio da Localidade de Referência Princípio da localidade de referência está relacionado com a constatação de que, em determinados momentos, acessos a instruções e dados se concentram em uma certa região do espaço de endereçamento do processo. Explorado para manter na memória física apenas partes da memória lógica necessárias para a execução do processo Possibilidade de “adivinhar” as regiões necessárias para sequência da execução Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 8 / 48 Princípio da Localidade de Referência Localidade temporal: região acessada recentemente tem mais chances de ser acessada novamente do que uma região acessada há mais tempo Instrução i + 1 executada após a instrução i Instruções executadas em estruturas de repetição for, while e do...while Localidade espacial: maior probabilidade de acesso a instruções e dados próximos àqueles acessados recentemente Acesso a elementos de vetores e matrizes (arrays) Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 9 / 48 Sumário 1 Introdução 2 Implementação Princípio da Localidade de Referência Paginação sob Demanda 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 9 / 48 Paginação sob Demanda Implementação de memória virtual baseada no mecanismo de paginação Apenas páginas efetivamente acessadas pelo processo carregadas na memória física Bit Presente/Ausente da tabela de páginas utilizado para indicar páginas carregadas para a memória física (presente) ou em disco (ausente) Número do quadro Presente/Ausente Proteção Modificado Referenciado Caching Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 10 / 48 Paginação sob Demanda Na paginação por demanda, um acesso à memória pode ter dois tratamentos: Se a página estiver marcada como presente na tabela de páginas, o endereço lógico é traduzido para o endereço físico e o acesso transcorre normalmente Se a página estiver marcada como ausente na tabela de páginas, a MMU gera uma interrupção de proteção e aciona o sistema operacional Quando a interrupção é causada devido ao acesso a uma página fora do espaço de endereçamento lógico, o processo é abortado Caso contrário, significa que a página referenciada não foi carregada para a memória física Diz-se que a interrupção ocorreu por falta de página (page fault) Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 11 / 48 Paginação sob Demanda Tratamento de um Page Fault 1 Alocação de quadro livre (pode necessitar liberar um quadro) 2 Determinação da localização da página no disco 3 Solicitação da operação de leitura da página “faltante” do disco para o quadro 4 Suspensão do processo que gerou a interrupção e escalonamento de outro processo apto 5 Interrupção do disco, indicando final da transferência da página 6 Atualização da tabela de páginas 7 Retirada do processo da fila de suspensos e inclusão na fila de aptos 8 Repetição da instrução que causou o page fault Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 12 / 48 Paginação sob Demanda Desempenho Taxa de page fault: 0 ≤ p ≤ 1 p = 0 → nenhum acesso gera page fault p = 1 → todo acesso gera page fault Cálculo do tempo efetivo (ou médio) de acesso à memória, te: te = (1 − p) × tam + p × tpf onde tam denota o tempo de acesso a memória e tpf denota o tempo para tratamento de um page fault Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 13 / 48 Paginacao sob Demanda Desempenho e@ Exemplo 1 — Calcular o tempo efetivo nas seguintes condicoes © tam = 100 ns = 10? ns © tor = 25 ms = 25 x 10° ns e Um page fault a cada 1000 acessos — p = 1/1000 = 1/10° t =(1 t ) x 10 + 95 x 108 . 108 103 999 te = —— +25 x 10° e~ a9 7 te © 25 ps Paginação sob Demanda Desempenho Exemplo 2 – Reduzir o tempo efetivo do exemplo anterior em 10% te = 22,5 µs = 22,5 × 103 ns tam = 100 ns = 102 ns tpf = 25 ms = 25 × 106 ns 22,5 × 103 = (1 − p) × 102 + p × 25 × 106 22,4 × 103 ≈ p × 25 × 106 p ≈ 1 1151 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 15 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 15 / 48 Alocação de Memória Para um processo executar, é necessário que uma certa quantidade de páginas estejam carregadas em quadros da memória física Problema consiste em determinar quantos quadros serão alocados para cada processo Quanto menor o número de quadros alocados, maior a taxa de page fault Quanto maior o número de quadros alocados, menor o grau de multiprogramação Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 16 / 48 Alocação de Memória Alocação Igualitária Consiste em dividir entre os processos ativos a quantidade total de quadros existentes Para uma memória física com m quadros e n processos aptos para executar, cada processo recebe m/n quadros Desvantagem: provoca distorções, já que processos possuem demandas distintas de memória Exemplo Em um sistema com 10 processos e 100 quadros, cada processo teria 10 quadros alocados na memória física. Um processo com 50 páginas seria prejudicado em relação a um processo com 12 páginas. Primeiro processo teria apenas 1/5 das suas páginas carregadas. Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 17 / 48 Alocacao de Memoria Alocacao Proporcional e@ Considera uma constante de proporcionalidade, como o tamanho do processo e@ Processos maiores recebem mais quadros que processos menores Si fi=—— xm et 35 @ f;: quantidade de quadros alocados para o processo 7 @ s;: tamanho do processo 7 e@ nm: nimero de processos aptos ® m: ndmero de quadros Alocação de Memória Alocação igualitária e alocação proporcional apresentam um mesmo problema Alocação precisa ser ajustada dinamicamente em função do grau de multiprogramação Processos são criados, executados e finalizados Quadros são alocados e liberados durante a execução Quadros liberados não são propriamente um problema Podem formar um conjunto (poll) de quadros livres Problema ocorre quando um processo necessita alocar mais memória e não há mais quadros livres disponíveis Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 19 / 48 Alocação de Memória Solução 1: sistema operacional poderia suspender um processo Espaço na memória física seria liberado para atender a demanda dos outros processos Pode suspender o processo que provocou a situação, retomando sua execução quando houver memória disponível, ou suspender outro processo para atender o primeiro Mecanismo de swapping Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 20 / 48 Alocação de Memória Solução 2: remover da memória física uma ou mais páginas de um processo Liberando quadros para carregar uma ou mais novas páginas Todos os processos continuam executando Gerência de memória virtual seleciona uma página “vítima” utilizando um algoritmo de substituição de páginas Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 21 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória Primeiro a Entrar, Primeiro a Sair (FIFO) Segunda Chance e Relógio Não Usada Recentemente (NRU) Usada Menos Recentemente (LRU) 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 21 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 011 Quadro Página 111 110 101 100 011 010 001 000 H B E A 000 001 010 011 D F 100 101 P/A 1 0 0 1 1 1 1 1 Quadros Disco 110 111 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 011 Quadro Página 111 110 101 100 011 010 001 000 H B E A 000 001 010 011 D F 100 101 P/A 1 0 0 1 1 1 1 1 Quadros Disco 110 111 Página referenciada pelo processo Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 011 Quadro Página 111 110 101 100 011 010 001 000 H B E A 000 001 010 011 D F 100 101 P/A 1 0 0 1 1 1 1 1 Quadros Disco 110 111 Page fault!! Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 011 Quadro Página 111 110 101 100 011 010 001 000 H B E A 000 001 010 011 D F 100 101 P/A 1 0 0 1 1 1 1 1 Quadros Disco 110 111 Nenhum quadro livre Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 011 Quadro Página 111 110 101 100 011 010 001 000 H B E A 000 001 010 011 D F 100 101 P/A 1 0 0 1 1 1 1 1 Quadros Disco 110 111 Seleciona página para page-out Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 011 Quadro Página 111 110 101 100 011 010 001 000 H B E A 000 001 010 011 D F 100 101 P/A 1 0 0 1 1 1 0 1 Quadros Disco 110 111 B Page-out Atualiza tabela de páginas Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 101 011 Quadro Página 111 110 101 100 011 010 001 000 H G E A 000 001 010 011 D F 100 101 P/A 1 1 0 1 1 1 0 1 Quadros Disco 110 111 Page-in Atualiza tabela de páginas Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 101 011 Quadro Página 111 110 101 100 011 010 001 000 H G E A 000 001 010 011 D F 100 101 P/A 1 1 0 1 1 1 0 1 Quadros Disco 110 111 Reexecuta a instrução Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória ? ? Páginas A B C D E F G H 000 001 010 011 100 110 111 101 000 101 100 001 111 101 011 Quadro Página 111 110 101 100 011 010 001 000 H G E A 000 001 010 011 D F 100 101 P/A 1 1 0 1 1 1 0 1 Quadros Disco 110 111 Qual página selecionar para sofrer o page-out??? Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 22 / 48 Substituição de Páginas na Memória Algoritmo de substituição de páginas é utilizado para selecionar uma página “vítima” Página que irá sofrer um page-out Algoritmo simples consiste em escolher uma página “vítima” aleatória Se escolhida uma página intensamente utilizada, um novo page fault pode ocorrer nas instruções seguintes Degradação de desempenho em função de sucessivos page-outs e page-ins Algoritmo ótimo selecionaria a página que levaria mais tempo (maior número de instruções) para ser referenciada novamente Adiar ao máximo um page fault para uma página removida da memória Na prática, não é realizável em sistemas de propósito geral Sistema operacional não tem como saber quando cada página vai ser referenciada no futuro Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 23 / 48 Substituição de Páginas na Memória Algoritmo de substituição de páginas é utilizado para selecionar uma página “vítima” Página que irá sofrer um page-out Algoritmo simples consiste em escolher uma página “vítima” aleatória Se escolhida uma página intensamente utilizada, um novo page fault pode ocorrer nas instruções seguintes Degradação de desempenho em função de sucessivos page-outs e page-ins Algoritmo ótimo selecionaria a página que levaria mais tempo (maior número de instruções) para ser referenciada novamente Adiar ao máximo um page fault para uma página removida da memória Na prática, não é realizável em sistemas de propósito geral Sistema operacional não tem como saber quando cada página vai ser referenciada no futuro Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 23 / 48 Substituição de Páginas na Memória Algoritmo de substituição de páginas é utilizado para selecionar uma página “vítima” Página que irá sofrer um page-out Algoritmo simples consiste em escolher uma página “vítima” aleatória Se escolhida uma página intensamente utilizada, um novo page fault pode ocorrer nas instruções seguintes Degradação de desempenho em função de sucessivos page-outs e page-ins Algoritmo ótimo selecionaria a página que levaria mais tempo (maior número de instruções) para ser referenciada novamente Adiar ao máximo um page fault para uma página removida da memória Na prática, não é realizável em sistemas de propósito geral Sistema operacional não tem como saber quando cada página vai ser referenciada no futuro Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 23 / 48 Substituição de Páginas na Memória Existem diversos algoritmos de substituição de páginas Abordagens distintas na seleção da página “vítima” Maioria depende de suporte de hardware Bits auxiliares das entradas na tabela de páginas Principais bits auxiliares utilizados: Modificado: indica se a página foi modificada depois de ter sido carregada para um quadro Referenciado: indica se a página foi acessada Número do quadro Presente/Ausente Proteção Modificado Referenciado Caching Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 24 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória Primeiro a Entrar, Primeiro a Sair (FIFO) Segunda Chance e Relógio Não Usada Recentemente (NRU) Usada Menos Recentemente (LRU) 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 24 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) FIFO, First-In, First-Out Utiliza uma estrutura de fila para ordenar as páginas por ordem de alocação Páginas alocadas são adicionadas sempre ao final da fila Quando ocorre um page fault, o algoritmo seleciona a página no início da fila Substitui a página a mais tempo na memória Página do início é movida pra disco e removida da fila Nova página é carregada no quadro liberado e adicionada ao final da fila 1 Página referenciada Início/Final Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) FIFO, First-In, First-Out Utiliza uma estrutura de fila para ordenar as páginas por ordem de alocação Páginas alocadas são adicionadas sempre ao final da fila Quando ocorre um page fault, o algoritmo seleciona a página no início da fila Substitui a página a mais tempo na memória Página do início é movida pra disco e removida da fila Nova página é carregada no quadro liberado e adicionada ao final da fila 1 Página referenciada Início/Final Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) FIFO, First-In, First-Out Utiliza uma estrutura de fila para ordenar as páginas por ordem de alocação Páginas alocadas são adicionadas sempre ao final da fila Quando ocorre um page fault, o algoritmo seleciona a página no início da fila Substitui a página a mais tempo na memória Página do início é movida pra disco e removida da fila Nova página é carregada no quadro liberado e adicionada ao final da fila 2 Página referenciada 1 Início/Final Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) FIFO, First-In, First-Out Utiliza uma estrutura de fila para ordenar as páginas por ordem de alocação Páginas alocadas são adicionadas sempre ao final da fila Quando ocorre um page fault, o algoritmo seleciona a página no início da fila Substitui a página a mais tempo na memória Página do início é movida pra disco e removida da fila Nova página é carregada no quadro liberado e adicionada ao final da fila 18 Página referenciada 1 2 Início Final Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) FIFO, First-In, First-Out Utiliza uma estrutura de fila para ordenar as páginas por ordem de alocação Páginas alocadas são adicionadas sempre ao final da fila Quando ocorre um page fault, o algoritmo seleciona a página no início da fila Substitui a página a mais tempo na memória Página do início é movida pra disco e removida da fila Nova página é carregada no quadro liberado e adicionada ao final da fila 1 2 18 Início 15 Página referenciada Final Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) FIFO, First-In, First-Out Utiliza uma estrutura de fila para ordenar as páginas por ordem de alocação Páginas alocadas são adicionadas sempre ao final da fila Quando ocorre um page fault, o algoritmo seleciona a página no início da fila Substitui a página a mais tempo na memória Página do início é movida pra disco e removida da fila Nova página é carregada no quadro liberado e adicionada ao final da fila 1 2 18 15 63 7 Início Final 21 Página referenciada Page fault! Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) FIFO, First-In, First-Out Utiliza uma estrutura de fila para ordenar as páginas por ordem de alocação Páginas alocadas são adicionadas sempre ao final da fila Quando ocorre um page fault, o algoritmo seleciona a página no início da fila Substitui a página a mais tempo na memória Página do início é movida pra disco e removida da fila Nova página é carregada no quadro liberado e adicionada ao final da fila 1 2 18 15 63 7 Início Final 21 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) FIFO, First-In, First-Out Utiliza uma estrutura de fila para ordenar as páginas por ordem de alocação Páginas alocadas são adicionadas sempre ao final da fila Quando ocorre um page fault, o algoritmo seleciona a página no início da fila Substitui a página a mais tempo na memória Página do início é movida pra disco e removida da fila Nova página é carregada no quadro liberado e adicionada ao final da fila 21 2 18 15 63 7 Início Final 21 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 25 / 48 Primeiro a Entrar, Primeiro a Sair (FIFO) Desvantagem: pode remover páginas que são intensamente referenciadas Página substituída pode ser necessária logo a seguir Novo page fault Perda de desempenho Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 26 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória Primeiro a Entrar, Primeiro a Sair (FIFO) Segunda Chance e Relógio Não Usada Recentemente (NRU) Usada Menos Recentemente (LRU) 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 26 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final R 1 R 1 R 0 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final R 1 R 1 R 0 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final 21 Página referenciada R 1 R 1 R 0 R 1 R 0 R 1 Page fault! Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final 21 Página referenciada R 1 R 1 R 0 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final 21 Página referenciada R 0 R 1 R 0 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final 21 Página referenciada R 0 R 1 R 0 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final 21 Página referenciada R 0 R 0 R 0 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final 21 Página referenciada R 0 R 0 R 0 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 18 15 63 7 Início Final 21 Página referenciada R 0 R 0 R 0 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Implementação similar ao algoritmo FIFO Estrutura de fila, com páginas carregadas a mais tempo no início Considera o bit Referenciado (R) da tabela de páginas Bit R é definido como 1 sempre que uma página é referenciada Quando ocorre um page fault, verifica a página no início da fila Se bit R é 1, atribui 0 ao bit R e move página para final da fila (segunda chance) Se bit R é 0, move página para disco e remove da fila Nova página é carregada para quadro liberado e adicionada ao final da fila, com o bit R definido como 1 1 2 21 15 63 7 Início Final 21 Página referenciada R 0 R 0 R 1 R 1 R 0 R 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 27 / 48 Segunda Chance e Relógio Desnecessariamente ineficiente Constantemente movendo páginas do início para o fim da fila Abordagem mais eficiente seria utilizar uma estrutura de dados de lista circular Um ponteiro aponta para a próxima página candidata a ser substituída Conhecido como algoritmo do relógio Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 28 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 18 R 1 R 1 R 0 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 18 R 1 R 1 R 0 43 Página referenciada Page fault! Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 18 R 1 R 1 R 0 43 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 18 R 0 R 1 R 0 43 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 18 R 0 R 1 R 0 43 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 18 R 0 R 0 R 0 43 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 18 R 0 R 0 R 0 43 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 18 R 0 R 0 R 0 43 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Segunda Chance e Relógio 54 21 15 R 0 R 0 R 1 63 7 R 0 R 1 1 2 43 R 0 R 0 R 1 43 Página referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória Primeiro a Entrar, Primeiro a Sair (FIFO) Segunda Chance e Relógio Não Usada Recentemente (NRU) Usada Menos Recentemente (LRU) 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 29 / 48 Não Usada Recentemente (NRU) NRU, Not Recently Used Princípio básico: é melhor remover uma página modificada, mas não referenciada, do que uma página não modificada que está sendo intensamente utilizada Considera os bits Referenciado (R) e Modificado (M) da tabela de páginas Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 30 / 48 Não Usada Recentemente (NRU) Quando ocorre um page fault, verifica todas as páginas da tabela de páginas, classificando-as em quatro categorias Descrição R M Classe 0 Não referenciadas, não modificadas 0 0 Classe 1 Não referenciadas, modificadas 0 1 Classe 2 Referenciadas, não modificadas 1 0 Classe 3 Referenciadas, modificadas 1 1 Remove aleatoriamente uma página da classe de ordem mais baixa Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 31 / 48 Não Usada Recentemente (NRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 1 1 1 M 0 0 0 1 0 1 0 1 Exemplo: memória física com 6 quadros Classificação das páginas carregadas Páginas Classe 0 4, 7 Classe 1 5 Classe 2 1 Classe 3 0, 3 Seleciona uma página aleatória da Classe 0 Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 48 Não Usada Recentemente (NRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 1 1 1 M 0 0 0 1 0 1 0 1 2 Página referenciada Page fault! Exemplo: memória física com 6 quadros Classificação das páginas carregadas Páginas Classe 0 4, 7 Classe 1 5 Classe 2 1 Classe 3 0, 3 Seleciona uma página aleatória da Classe 0 Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 48 Não Usada Recentemente (NRU) 0 2 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 0 0 1 1 1 R 0 0 0 1 1 M 0 0 1 1 1 4 1 0 0 3 1 0 0 1 5 1 1 0 2 Página referenciada Exemplo: memória física com 6 quadros Classificação das páginas carregadas Páginas Classe 0 4, 7 Classe 1 5 Classe 2 1 Classe 3 0, 3 Seleciona uma página aleatória da Classe 0 Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 48 Não Usada Recentemente (NRU) 0 5 2 4 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 0 0 1 1 1 1 R 0 0 0 1 1 1 M 0 0 1 1 0 1 1 3 1 1 0 0 0 0 2 Página referenciada Exemplo: memória física com 6 quadros Classificação das páginas carregadas Páginas Classe 0 4, 7 Classe 1 5 Classe 2 1 Classe 3 0, 3 Seleciona uma página aleatória da Classe 0 Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 48 Não Usada Recentemente (NRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 1 1 1 M 0 0 0 1 0 1 0 1 2 Página referenciada Exemplo: memória física com 6 quadros Classificação das páginas carregadas Páginas Classe 0 4, 7 Classe 1 5 Classe 2 1 Classe 3 0, 3 Seleciona uma página aleatória da Classe 0 Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 48 Não Usada Recentemente (NRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 0 1 1 1 R 0 0 0 0 0 1 1 1 M 0 0 0 1 0 1 0 1 2 Página referenciada Exemplo: memória física com 6 quadros Classificação das páginas carregadas Páginas Classe 0 4, 7 Classe 1 5 Classe 2 1 Classe 3 0, 3 Seleciona uma página aleatória da Classe 0 Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 48 Não Usada Recentemente (NRU) 0 5 1 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 1 1 0 1 1 1 R 0 0 1 0 0 1 1 1 M 0 0 0 1 0 1 0 1 2 Página referenciada Exemplo: memória física com 6 quadros Classificação das páginas carregadas Páginas Classe 0 4, 7 Classe 1 5 Classe 2 1 Classe 3 0, 3 Seleciona uma página aleatória da Classe 0 Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 32 / 48 Não Usada Recentemente (NRU) Periodicamente, o bit R de todas as páginas é definido como 0 Período pode ser um número n de interrupções de relógio Algoritmo de fácil compreensão e implementação Pode apresentar desempenho adequado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 33 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória Primeiro a Entrar, Primeiro a Sair (FIFO) Segunda Chance e Relógio Não Usada Recentemente (NRU) Usada Menos Recentemente (LRU) 5 Considerações Finais Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 33 / 48 Usada Menos Recentemente (LRU) LRU, Least Recently Used Construído sobre as seguintes suposições: Páginas muito utilizadas nas últimas instruções serão, provavelmente, muito utilizadas nas próximas instruções Páginas não utilizadas por um longo período de tempo, provavelmente, permanecerão inutilizadas por muito tempo Estratégia: remover a página não utilizada pelo período de tempo mais longo Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 34 / 48 Usada Menos Recentemente (LRU) Mantém uma lista encadeada ordenada de todas as páginas carregadas em memória Páginas mais recentemente utilizadas no início da lista Páginas menos recentemente utilizadas no final da lista Quando ocorre um page fault, remove sempre a última página da lista Problema: atualizar a lista a cada referência à memória Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 35 / 48 Usada Menos Recentemente (LRU) Mantém uma lista encadeada ordenada de todas as páginas carregadas em memória Páginas mais recentemente utilizadas no início da lista Páginas menos recentemente utilizadas no final da lista Quando ocorre um page fault, remove sempre a última página da lista Problema: atualizar a lista a cada referência à memória Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 35 / 48 Usada Menos Recentemente (LRU) Embora LRU seja teoricamente realizável, na prática, não é uma solução viável Utilização de abordagens de software que se aproximam do LRU Não Usadas Frequentemente (NFU, Not Frequently Used) Envelhecimento (Aging) Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 36 / 48 Usada Menos Recentemente (LRU) Não Usadas Frequentemente (NFU, Not Frequently Used) Mantém um contador, inicializado com zero, para cada página carregada A cada interrupção de relógio, o sistema operacional percorre todas as páginas Para cada página... Valor do bit Referenciado (R) é adicionado ao contador Bit R é zerado Quando ocorre um page fault, remove a página apresentando o menor contador Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 37 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 1 1 1 C 0 0 0 0 0 0 0 0 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 1 1 1 C 0 0 0 0 0 1 1 1 Interrupção 1 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 0 0 0 0 0 1 1 1 Interrupção 1 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 1 0 1 0 0 C 0 0 0 0 0 1 1 1 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 1 0 1 0 0 C 0 0 0 1 0 2 1 1 Interrupção 2 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 0 0 0 1 0 2 1 1 Interrupção 2 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 2 0 0 1 3 10 6 6 Após n interrupções Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 2 0 0 1 3 10 6 6 2 Página referenciada Page fault! Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 2 0 0 1 3 10 6 6 2 Página referenciada Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 0 1 1 1 1 R 0 0 0 0 0 0 0 0 C 2 0 0 1 3 10 6 6 2 Página referenciada Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) 0 5 4 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 1 0 1 1 1 1 R 0 0 0 0 0 0 0 0 C 2 0 0 1 3 10 6 6 2 Página referenciada Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 38 / 48 Usada Menos Recentemente (LRU) Problema do elefante: “jamais esquece de nada” Páginas muito referenciadas durante um intervalo de tempo, acabam não sendo eliminadas durante muito tempo Mesmo que não estejam sendo referenciadas recentemente Páginas carregadas recentemente têm mais chances de serem removidas Mesmo que estejam sendo intensamente referenciadas Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 39 / 48 Usada Menos Recentemente (LRU) Envelhecimento Resultado de duas modificações no algoritmo NFU Antes de adicionar o bit Referenciado (R), desloca (shift) os contadores 1 bit à direita Bit R é adicionado ao bit mais à esquerda “Penaliza” páginas não referenciadas por mais tempo Contador reduz pela metade a cada interrupção de relógio na qual a página não é referenciada Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 40 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 1 1 1 C 0000 (0) 0000 (0) 0000 (0) 0000 (0) 0000 (0) 0000 (0) 0000 (0) 0000 (0) Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 1 1 1 C 0000 (0) 0000 (0) 0000 (0) 0000 (0) 1000 (8) 0000 (0) 1000 (8) 1000 (8) Interrupção 1 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 0000 (0) 0000 (0) 0000 (0) 0000 (0) 1000 (8) 0000 (0) 1000 (8) 1000 (8) Interrupção 1 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 1 0 1 0 0 C 0000 (0) 0000 (0) 0000 (0) 0000 (0) 1000 (8) 0000 (0) 1000 (8) 1000 (8) Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 1 0 1 0 0 C 0000 (0) 0000 (0) 1000 (8) 0000 (0) 1100 (12) 0000 (0) 0100 (4) 0100 (4) Interrupção 2 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 0000 (0) 0000 (0) 1000 (8) 0000 (0) 1100 (12) 0000 (0) 0100 (4) 0100 (4) Interrupção 2 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 1 0 0 0 0 0 1 0 C 0000 (0) 0000 (0) 1000 (8) 0000 (0) 1100 (12) 0000 (0) 0100 (4) 0100 (4) Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 1 0 0 0 0 0 1 0 C 1000 (8) 0000 (0) 0100 (4) 0000 (0) 0110 (6) 0000 (0) 1010 (10) 0010 (2) Interrupção 3 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 1000 (8) 0000 (0) 0100 (4) 0000 (0) 0110 (6) 0000 (0) 1010 (10) 0010 (2) Interrupção 3 Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 1000 (8) 0000 (0) 0100 (4) 0000 (0) 0110 (6) 0000 (0) 1010 (10) 0010 (2) 2 Página referenciada Page fault! Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 1 R 0 0 0 0 0 0 0 0 C 1000 (8) 0000 (0) 0100 (4) 0000 (0) 0110 (6) 0000 (0) 1010 (10) 0010 (2) 2 Página referenciada Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 0 1 1 1 1 0 R 0 0 0 0 0 0 0 0 C 1000 (8) 0000 (0) 0100 (4) 0000 (0) 0110 (6) 0000 (0) 1010 (10) 0010 (2) 2 Página referenciada Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) 0 5 0 2 1 4 3 Quadro Pág. 7 6 5 4 3 2 1 0 P/A 1 0 1 1 1 1 1 0 R 0 0 0 0 0 0 0 0 C 1000 (8) 0000 (0) 0100 (4) 0000 (0) 0110 (6) 0000 (0) 1010 (10) 0010 (2) 2 Página referenciada Exemplo: memória física com 6 quadros Contador (C) é atualizado a cada interrupção de relógio Seleciona a página que possui o menor valor no contador Move a página para o disco Carrega nova página para o quadro liberado Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 41 / 48 Usada Menos Recentemente (LRU) Em uma interrupção de relógio, não se sabe em que ordem as páginas foram referenciadas Sabe-se somente quais páginas foram referenciadas naquele intervalo de tempo Tamanho dos contadores limita a “longevidade da memória” Para um contador com n bits, informação é perdida após n interrupções Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 42 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Exercícios Referências Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 42 / 48 Considerações Finais Memória virtual possibilita a execução de programas sem que estes estejam completamente carregados na memória principal Explora os princípios de localidade de referência temporal e espacial Tipicamente, utiliza paginação por demanda Páginas são carregadas do disco para a memória física quando referenciadas pelo processo Interrupção por page fault sinaliza a ausência de uma página na memória física Memória física pode ser alocada para processos de modo igualitário ou proporcional Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 43 / 48 Considerações Finais Algoritmos de substituição de páginas são utilizados quando uma nova página precisa ser carregada e não há quadros livres Responsáveis pela seleção de páginas para remoção da memória física Embora o algoritmo ótimo não seja realizável, existem vários algoritmos com diferentes abordagens para o problema Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 44 / 48 Considerações Finais Algoritmo Comentário FIFO Pode descartar páginas importantes Segunda Chance Grande melhoria sobre o FIFO Relógio Implementação eficiente e realista do Segunda Chance LRU Excelente algoritmo, porém, difícil de ser implementado NRU Aproximação muito rudimentar do LRU NFU Aproximação bastante rudimentar do LRU Envelhecimento Algoritmo eficiente que aproxima bem o LRU Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 45 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Exercícios Referências Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 45 / 48 Exercícios 1 Considere um computador com uma memória física composta por 4 quadros. O momento da carga, o momento do último acesso e os bits Referenciado (R) e Modificado (M) para cada página carregada na memória física é apresentado abaixo (momento descrito em ciclos de clock): Página Carregado Últ. Referência R M 0 126 280 1 0 1 230 265 0 1 2 140 270 0 0 3 110 285 1 1 Na ocorrência de um page fault, qual página seria selecionada para remoção... Pelo algoritmo NRU? Pelo algoritmo FIFO? Pelo algoritmo Segunda Chance? Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 46 / 48 Exercícios 2 Suponha um sistema com uma memória física composta por 3 quadros, todos, inicialmente, livres. Um processo, com memória lógica composta por 8 páginas, é colocado em execução. Assumindo que nenhuma página foi carregada antes do início da execução e que o processo referencia, ao longo do tempo, as páginas descritas na sequência abaixo, calcule o número de page faults utilizando os algoritmos FIFO, Segunda chance e Envelhecimento. Páginas referenciadas: 7, 0, 1, 4, 0, 2, 0, 6, 5, 6, 3, 7, 0, 1 Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 47 / 48 Sumário 1 Introdução 2 Implementação 3 Alocação de Memória 4 Substituição de Páginas na Memória 5 Considerações Finais Exercícios Referências Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 47 / 48 Referências OLIVEIRA, R. S.; CARISSIMI, A. S.; TOSCANI, S. S. Sistemas Operacionais. 4. ed. Porto Alegre: Bookman, 2010. 374 p. ISBN 978-85-7780-521-1. TANENBAUM, A. S.; BOS, H. Modern Operating Systems. 4. ed. [S. l.]: Pearson Education, 2015. 1136 p. ISBN 978-0-13-359162-0. SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Operating System Concepts. 9. ed. [S. l.]: Wiley, 2012. 976 p. ISBN 978-1-118-06333-0. Prof. Eduardo Camilo Inacio, Dr. INE5611 UFSC/INE 48 / 48 INE5611 - Sistemas Operacionais Memória Virtual Prof. Eduardo Camilo Inacio, Dr. eduardo.camilo@ufsc.br Universidade Federal de Santa Catarina Departamento de Informática e Estatística