Logo Passei Direto
Buscar
Material
páginas com resultados encontrados.
páginas com resultados encontrados.

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Escolha uma das opções e acesse esse e outros materiais sem bloqueio. 🤩

Cadastre-se ou realize login

Ao continuar, você aceita os Termos de Uso e Política de Privacidade

Prévia do material em texto

Memória Virtual
RA: 21750295 - Nome: Flávia Resende Peixoto
RA: 21606007 - Nome: Daniel do Prado Borges
RA: - Nome:
Nascimento da memória virtual
O requisito de que as instruções devem estar na memória física para serem executadas parece necessário e racional, mas também é inadequado, já que limita o tamanho de um programa ao tamanho da memória física. Olhe os exemplos:
 Os programas, com frequência, têm um código que manipula condições de erro não usuais. Já que raramente esses erros ocorrem na prática, quando ocorrem, esse código quase nunca é executado.
Arrays, listas e tabelas recebem em geral mais memória do que realmente precisam. Um array pode ser declarado como tendo 100 por 100 elementos, ainda que raramente tenha mais de 10 por 10 elementos. Uma tabela de símbolos de um montador pode ter espaço para 3.000 símbolos, embora o programa médio tenha menos de 200 símbolos.
Motivo para que fosse necessária
Mesmo nos casos em que o programa inteiro é necessário, ele pode não ser necessário em sua totalidade ao mesmo tempo.
A possibilidade de executar um programa que esteja apenas parcialmente na memória traria muitos benefícios:
O programa não ficaria mais restrito ao montante de memória física disponível. Os usuários poderiam escrever programas para um espaço de endereçamento virtual extremamente grande, simplificando a tarefa de programação.
Já que cada programa de usuário poderia usar menos memória física, mais programas poderiam ser executados ao mesmo tempo, com um aumento correspondente na utilização da CPU e no throughput (taxa de transferência), mas sem aumento no tempo de resposta ou no tempo de turnaround.
Menos operações de I/O seriam necessárias para carregar ou permutar programas de usuário na memória; portanto, cada programa de usuário seria executado mais rapidamente.
Assim, a execução de um programa que não esteja inteiramente na memória beneficiaria tanto o sistema quanto o usuário. 
Sendo a memória virtual maior do que a memória física, como mostra a imagem.
Funcionamento da memória virtual
A memória virtual permite simular a existência de mais memória principal (RAM), usando o espaço da memória secundária (HD).
A memória virtual pode ser armazenada em um arquivo especialmente formatado na memória secundária, ou em uma partição dedicada, e a eficiência com que ela é usada varia de Sistema operacional, porém ela permite que o sistema continue funcionando, mesmo com pouca memória principal disponível.
Funções básicas da memória virtual
Realocação, para garantir que cada processo tenha seu próprio espaço de endereçamento, começando em zero.
Proteção, para impedir que um processo utilize um endereço de memória que não seja dele;
Paginação ou swapping, possibilita a um processo utilizar mais memória do que a fisicamente existente (essa é a função mais conhecida).
Visão do Programador
Resumidamente, um usuário ou programador vê um espaço de endereçamento virtual, que pode ser igual, maior ou menor que a memória física (normalmente chamada memória DRAM - Dynamic Random Access Memory).
A memória virtual deixou os programadores despreocupados com quanto de memória seu programa irá precisar para rodar no computador e se o respectivo programa poderia rodar com outros sem travar, podendo o programador se preocupar mais com a tarefa de programação do que com quanto o programa irá gastar de memória.
Endereçamento Virtual
O espaço de endereçamento virtual de um processo diz respeito à visão lógica (ou virtual) de como um processo é armazenado na memória. Normalmente, de acordo com essa visão, um processo começa em determinado endereço lógico, digamos, endereço 0, e existe em memória adjacente.
 Os espaços de endereçamento virtuais que incluem brechas são conhecidos como espaços de endereçamento esparsos. O uso de um espaço de endereçamento esparso é benéfico porque as brechas podem ser preenchidas conforme os segmentos da pilha ou do heap cresçam, ou se quisermos vincular bibliotecas dinamicamente (ou possivelmente outros objetos compartilhados) durante a execução do programa.
Paginação por Demanda
Considere como um programa executável pode ser levado do HD para a memória principal. Uma opção é carregar o programa inteiro na memória física em tempo de execução do programa. Porém, inicialmente podemos não precisar do programa inteiro na memória. Suponha que um programa comece com uma lista de opções disponíveis na qual o usuário deve fazer uma seleção. A carga do programa inteiro na memória resultaria na carga do código executável de todas as opções, independentemente de uma opção ter sido ou não selecionada pelo usuário.
Em vez disso podemos carregar páginas somente à medida que elas sejam necessárias. Essa técnica é conhecida como paginação por demanda e é normalmente usada em sistemas de memória virtual. Na memória virtual paginada por demanda, as páginas são carregadas somente quando são necessárias durante a execução do programa. Portanto, páginas que nunca são acessadas nunca são carregadas na memória física, evitando assim o uso desnecessário da memória.
Permutador Preguiçoso
Na paginação com permuta os processos a serem carregador estão originalmente no disco rígido (memória secundária), quando o processo deve ser executado ele é transferido para a memória principal. Temos uma alternativa para em vez de inserir o processo completo utilizamos o permutador preguiçoso. 
Ele apenas irá inserir uma página na memória sendo ela necessária. Porém ao falarmos permutador, se refere à processos completos, logo utilizamos o termo paginador, que se preocupa com as páginas, no contexto de paginação por demanda.
Conceitos Básicos
O paginador avalia o processo, observando quais páginas serão necessárias, transferindo apenas estas para a memória. Assim evitando transferência desnecessária de páginas que não serão usadas, diminuindo o tempo de permuta e o montante de memória física necessária.
Transferência de uma memória paginada para espaço de disco adjacente.
Quando a página é válida ela se encontra na memória principal.
Quando a página é inválida não faz parte do endereçamento lógico do processo. Ou é válida e se encontra no disco atualmente.
Página Válida ou Inválida
Se uma página for marcada como inválida, porém se o processo nunca tentar acessá-la, a marcação não terá efeito. Portanto se transferirmos para memória apenas páginas necessárias o processo será executado normalmente, como se tivéssemos transferido todas as páginas. Enquanto o processo for executado acessando páginas que se encontram na memória, a execução continuará normalmente. 
Porém se o processo tentar acessar uma página que não se encontra na memória, ou seja acesso à uma página inválida, ocorrerá um erro de página.
Solução do erro de página
Verificamos uma tabela interna (usualmente mantida com o PCB ) desse processo para determinar se a referência foi um acesso válido ou inválido à memória.
Se a referência foi inválida, encerramos o processo. Se ela foi válida, mas ainda não trouxemos a página para a memória, a traremos agora.
Encontramos um quadro livre (usando um da lista de quadros livres, por exemplo).
Incluímos uma operação de disco no escalonador para ler a página desejada para o quadro recém-alocado.
Quando a leitura em disco é concluída, modificamos a tabela interna mantida com o processo e a tabela de páginas para indicar que agora a página está na memória.
Reiniciamos a instrução que foi interrompida pela interceptação. Agora o processo pode acessar a página como se ela sempre tivesse estado na memória.
Paginação por demanda pura
Dessa forma o processo requisita uma página e a mesma é transferida para a memória, depois ele é interrompido novamente e requisita a página novamente, assim evitando erros de página.
Nunca trazer uma página antes que ela seja necessária.
Hardware de paginação
Esse hardware é o mesmo que supor paginação por demanda, paginação e permuta:
Tabela de páginas: É a tabela cujo faz a marcação de páginas como válidas ou inválidasvisto antes nesse capítulo.
Memória Secundária: Onde ficam as páginas que não residem na memória principal, sendo ela comumente um disco de alta velocidade. Um dispositivo de permuta, a seção do disco utilizada para isso é chamada de espaço de permuta.
Tabela de páginas
Figura 1 - Algumas páginas não estando na memória e sim no espaço de permuta.
Figura 2 - Manipulação para a correção do erro de página
Figura 2
Figura 1
Paginação por demanda
A capacidade de reiniciar qualquer instrução após um erro de página é um requisito crucial para a paginação por demanda.
Ao ser reiniciado, como é salvo o estado do processo (registradores, códigos de condição, contador de instruções) que foi interrompido, somos capazes de reiniciar onde ele havia parado com a diferença de que a página desejada agora está na memória.
Casos de erro de página
Ocorrer um erro de página na busca de instrução, reinicia-se o processo buscando novamente a instrução. Ou se ocorrer enquanto busca-se um operando, buscamos e decodificamos a instrução para assim buscar o operando.
Pior caso de erro de página
Temos uma instrução de três endereços ADD(somar) e o conteúdo de A e B, com seus resultados em C. Passos da execução da instrução:
Buscar e decodificar a instrução (ADD).
Buscar A.
Buscar B.
Somar A e B.
Armazenar o resultado em C. 
Continuação
Se ocorrer o erro ao tentarmos armazenar o resultado em C, é devido ao fato de que C está em uma página que não se encontra na memória.
Obtemos a página desejada, transferimos para a memória, corrigimos a tabela de páginas e reiniciamos a instrução.
Desempenho da Paginação por Demanda
A paginação por demanda afeta diretamente o desempenho de um sistema de computação. Observe, calculando o tempo de acesso efetivo de uma memória paginada por demanda.
Podemos representar como ma (memory-access) , variando de 10 a 200 nanossegundos. Se não houver erro de página o tempo efetivo será equivalente ao tempo de acesso a memória.
Se ocorrer erro de página, precisaremos ler a página desejada no disco, e então acessar a palavra requerida.
Tempo de acesso efetivo
Manipulação do erro de página
Interceptar para o sistema operacional
Salvar os registradores do usuário e o estado do processo
Determinar se a interrupção foi um erro de página
Verificar se a referência à página era legal e determinar o local da página no disco
Executar uma leitura do disco para um quadro livre:
Esperar em uma fila por esse dispositivo até que a solicitação de leitura seja atendida.
Esperar pelo tempo de busca e/ou latência do dispositivo.
Começar a transferência da página para um quadro livre.
Continuação das ocorrências
Durante a espera, alocar a CPU a algum outro usuário (scheduling da CPU, opcional).
Receber uma interrupção do subsistema de I/O do disco (I/O concluído).
Salvar os registradores e o estado do processo do outro usuário (se o passo 6 for executado).
Determinar se a interrupção partiu do disco.
Corrigir a tabela de páginas e outras tabelas para mostrar que a página desejada está agora na memória.
Esperar que a CPU seja alocada novamente a esse processo.
Restaurar os registradores do usuário, o estado do processo e a nova tabela de páginas para, então, retomar a instrução interrompida.
Erro de página
Esses passos nem sempre são necessários em todos os casos. 
Por exemplo, estamos supondo que, no passo 6, a CPU tenha sido alocada a outro processo enquanto ocorre o I/O. Esse esquema permite a multiprogramação para mantermos a utilização da CPU, mas requer tempo adicional para a retomada da rotina de serviço do erro de página quando a transferência de I/O for concluída.
Principais componentes do tempo de serviço do erro de página
Manipular a interrupção por erro de página.
Ler a página para a memória.
Reiniciar o processo.
Exemplo tempo de acesso efetivo
tempo de acesso efetivo
=
(1 – p) + (200) 1 p (8 milissegundos)
 
=
(1 – p) + (200) 1 p 3 8.000.000
 
=
200 + 7.999.800 × p.
Com um tempo médio de manipulação do erro de página de 8 milissegundos e um tempo de acesso à memória de 200 nanossegundos, o tempo de acesso efetivo em nanossegundos é
Taxa de erros de página
Substituição de Página Básica
Quando ocorre uma falha de página e não há nenhum quadro livre, é possível liberar um quadro gravando seu conteúdo no espaço de permuta e alterando a tabela de pagina (e todas as outras tabelas) para indicar que a pagina não esta mais na memoria. Assim o quadro que foi liberado pela pagina que estava com falha no processo, poderá ser utilizado por outra página .
Encontre a locação da página desejada no disco.
Procure um quadro livre:
Se houver um quadro livre, use-o.
Se não houver um quadro livre, use um algoritmo de substituição de páginas para selecionar um quadro vítima.
Grave o quadro vítima no disco e promova as devidas alterações nas tabelas de páginas e de quadros.
Transfira a página desejada para o quadro recém-liberado e altere as tabelas de páginas e quadros.
Retome o processo do usuário a partir de onde ocorreu o erro de página
Modificação na rotina de manipulação de erros de pagina para incluir a substituição de páginas
Bit de Modificação
Se nenhum quadro estiver livre, duas transferências de página são necessárias. Essa situação duplica efetivamente o tempo de manipulação do erro de página e aumenta o tempo de acesso efetivo na mesma proporção.
É possível reduzir esse overhead usando um bit de modificação (ou bit sujo).
 Quando esse esquema é usado, cada página ou quadro tem um bit de modificação associado a ele no hardware. O bit é ligado pelo hardware sempre que algum byte da página sofre uma gravação, indicando que a página foi modificada.
Quando selecionamos uma página para substituição, examinamos seu bit de modificação.
Se ligado, a página foi modificada desde que foi transferida do disco, deverá gravar a página no disco. 
Se não estiver ligado, a página não foi modificada desde que foi transferida para a memória, não precisará gravar a página da memória no disco.
 Essa técnica também se aplica a páginas somente-de-leitura (por exemplo, páginas de código binário),que não podem ser modificadas, podendo portanto ser descartadas quando desejado. 
Esse esquema pode reduzir significativamente o tempo necessário à manipulação de um erro de página, já que reduz o tempo de I/O pela metade se a página não tiver sido modificada.
Sequencia de Referencia
Existem muitos algoritmos de substituição de páginas diferentes , geralmente, é utilizado o que
tem a taxa de erros de página mais baixa. Um algoritmo é avaliado , executando em determinada sequência de referências à memória e calculando o número de erros de página, esta sequência de referências à memória é chamada de sequência de referência. 
Pode-se gerar sequências de referência artificialmente, ou podemos rastrear determinado sistema e registrar o endereço de cada referência à memória. A última opção produz uma grande quantidade
de dados (na ordem de 1 milhão de endereços por segundo).
Dois fatos são considerados para reduzir a quantidade de dados :
1º Para determinado tamanho de página é preciso considerar apenas o número da página, em vez de o endereço inteiro .
2º Se tiver uma referência a uma página p, qualquer referência à página p que vier imediatamente a seguir jamais causará um erro de página. A página p estará na memória após a primeira referência; portanto, as referências imediatamente posteriores não causarão erro. 
Para determinar o número de erros de página para determinada sequência de referência e um algoritmo de substituição de páginas específico, também precisamos conhecer o número de quadros de páginas disponíveis. 
Conforme o número de quadros aumenta, o número de erros de página cai a algum nível mínimo. Naturalmente, a adição de memória física aumenta o número de quadros.
Substituição de Páginas FIFO 
O algoritmo de substituição de páginas mais simples é um algoritmo primeiro-a-entrar, primeiro-a-sair(FIFO). 
Um algoritmo de substituição FIFO associa a cada página a hora em que essa página foi trazida para a memória, quando uma página tem que ser substituída, a página mais antiga é selecionada. 
Não é estritamente necessário registrar a hora em que uma página é trazida para a memória, pode-se criar uma fila FIFO para armazenar todas as páginas da memória. 
A página da cabeça da fila é substituída, e quando uma página é trazida para a memória, ela é inserida na cauda da fila.
O algoritmo de substituição de páginas FIFO é fácil de entender e programar, mas nem sempre seu
desempenho é bom. A página substituída pode ser um módulo de inicialização que foi usado há muito tempo, e não é mais necessário. Mas ela poderia conter uma variável muito usada que foi inicializada cedo e é constantemente utilizada. 
Algoritmo de substituição de páginas FIFO 
As três primeiras referências(7, 0, 1) causam erros de página e são trazidas para esses quadros vazios.
A próxima referência (2) substitui a página 7 porque essa página foi trazida primeiro.
Como 0 é a próxima referência e já está na memória, não temos erro para essa referência. 
A primeira referência a 3 resulta na substituição da página 0, já que agora ela é a primeira da fila. 
Por causa dessa substituição, a próxima referência, a 0, causará erro. 
A página 1 é então substituída pela página 0. 
E assim Sucessivamente.
Anomalia de Belady 
A imagem abaixo mostra erros de página para essa sequência de referência versus o número de quadros disponíveis. O número de erros para quatro quadros (10) é maior do que o número de erros para três quadros (nove)! Esse resultado tão inesperado é conhecido como anomalia de Belady.
Em alguns algoritmos de substituição de páginas, a taxa de erros de página pode aumentar conforme o número de quadros alocados aumenta. O esperado seria que o fornecimento de mais memória para um processo melhorasse seu desempenho 
Substituição de Páginas Ótima
Uma consequência da descoberta da anomalia de Belady foi a procura de um algoritmo ótimo de substituição de páginas.
O OPT ou MIN tem a menor taxa de erros de página de todos os algoritmos e nunca sofreu da anomalia de Belady.
O uso desse algoritmo de substituição de páginas garante a menor taxa de erros de página possível para um número fixo de quadros. 
Infelizmente, o algoritmo ótimo de substituição de páginas é difícil de implementar porque requer o conhecimento antecipado da sequência de referência. 
O algoritmo ótimo é usado principalmente em estudos de comparação. Por exemplo, pode ser útil saber que, embora um novo algoritmo não seja ótimo, ele é até 12,3% ótimo, na pior das hipóteses, e até 4,7% ótimo na média. 
Substituição de Páginas LRU
A principal diferença entre os algoritmos FIFO e OPT é que o algoritmo FIFO usa a hora em que uma página foi trazida para a memória, enquanto o algoritmo OPT utiliza a hora em que uma página deve ser usada. 
Se usarmos o passado recente como uma aproximação para o futuro próximo, então poderemos substituir a página que não foi usada pelo período de tempo mais longo.
 Essa abordagem é o algoritmo do menos recentemente-utilizado (LRU — least-recently-used). 
A substituição LRU associa a cada página a hora em que essa página foi usada pela última vez. 
Quando uma página deve ser substituída, o algoritmo LRU seleciona a página que não foi usada pelo período de tempo mais longo. 
Podemos considerar essa estratégia como o algoritmo ótimo de substituição de páginas olhando para trás no tempo em vez de olhar para a frente. 
O algoritmo LRU produz doze erros. 
Os cinco primeiros erros são iguais aos da substituição ótima.
Quando a referência à página 4 ocorre, no entanto, a substituição LRU verifica que, dos três quadros em memória, a página 2 foi a menos recentemente utilizada. 
O algoritmo LRU substitui a página 2, sem saber que a página 2 está para ser usada. 
Quando ocorre um erro causado pela página 2, o algoritmo LRU substitui a página 3, já que agora, das três páginas em memória, ela é a menos recentemente utilizada. 
Apesar desses problemas, a substituição LRU com doze erros é muito melhor do que a substituição FIFO com 15 
O principal problema é como implementar a substituição LRU. 
Um algoritmo de substituição de páginas LRU pode requerer
assistência substancial do hardware. 
O problema é determinar uma ordem para os quadros definida pela hora em que foram usados pela última vez.
Duas implementações são possíveis:
Duas implementações são possíveis:
Contadores: Cada entrada da tabela de página um campo de hora-de-uso e adicionamos à CPU um contador ou relógio lógico, o relógio é incrementado a cada referência à memória. Sempre que é feita uma referência a uma página, os conteúdos do registrador do relógio são copiados para o campo de hora-de-uso na entrada da tabela de páginas para aquela página, assim sempre terá a “hora” da última referência a cada página e a com o menor valor de hora é substituída. 
 Pilha: Para a implementação da substituição LRU é manter uma pilha de números de página, sempre que uma página for referenciada, ela será removida de seu local na pilha e inserida no topo, a página mais recentemente utilizada estará sempre no topo da pilha e a menos recentemente utilizada estará sempre na base As entradas devem ser removidas do meio da pilha, é melhor implementar essa abordagem usando uma lista duplamente encadeada com um ponteiro na cabeça e um ponteiro na cauda. Essa abordagem é particularmente apropriada para implementações da substituição LRU em software ou microcódigo 
	Como a substituição ótima, a substituição LRU não sofre da anomalia de Belady. As duas pertencem a uma classe de algoritmos de substituição de páginas chamada de algoritmos de pilha, que nunca exibem a anomalia de Belady. Um algoritmo de pilha é o algoritmo para o qual é possível demonstrar que o conjunto de páginas na memória para n quadros é sempre um subconjunto do conjunto de páginas que estariam na memória com n + 1 quadros.
Uso de uma pilha para o registro das referências de página mais recentes 
Substituição de Páginas por Aproximação ao LRU
Poucos sistemas de computação fornecem suporte de hardware suficiente para a verdadeira substituição de páginas LRU, alguns sistemas não fornecem suporte de hardware, e outros algoritmos de substituição de páginas (como o algoritmo FIFO) devem ser usados. 
Muitos sistemas fornecem alguma ajuda, no entanto, na forma de um bit de referência. O bit de referência de uma página é ativado pelo hardware sempre que a página é referenciada.
Algoritmo dos Bits de Referência Adicionais
Para obter informações adicionais sobre a ordem de uso registrando os bits de referência em intervalos regulares. Podemos manter um byte de 8 bits para cada página em uma tabela na memória, no intervalos regulares (digamos, a cada 100 milissegundos), uma interrupção de timer transfere o controle para o sistema operacional 
O sistema desloca o bit de referência de cada página para o bit de alta ordem de seu byte de 8 bits, deslocando os outros bits de 1 bit para a direita e descartando o bit de baixa ordem, Esses registradores de deslocamento de 8 bits contêm o histórico de uso da página para os últimos oito períodos de tempo 
Se o registrador de deslocamento contiver 00000000, então a página não foi usada por oito períodos de tempo. 
Uma página que é usada pelo menos uma vez a cada período tem um valor do registrador de deslocamento de 11111111. 
Uma página com um valor histórico do registrador de 11000100 foi usada mais recentemente do que uma com o valor de 01110111. 
Se interpretarmos esses bytes de 8 bits como inteiros sem sinal, a página com o menor número é a página LRU e pode ser substituída. 
Mas não há garantia de que os números sejam exclusivos. Podendo substituir (remover da memória) todas as páginas com o menor valor ou usar o método FIFO para selecionar entre elas 
Algoritmo da Segunda Chance
O algoritmo básico de substituiçãoda segunda chance é um algoritmo de substituição FIFO,no entanto, quando uma página é selecionada, inspecionamos seu bit de referência. 
Se o valor for 0, substituímos a página; mas se o bit de referência estiver posicionado com 1, damos à página uma segunda chance, passando à seleção da próxima página FIFO. 
Quando uma página obtém uma segunda chance, seu bit de referência é zerado, e sua hora de chegada é redefinida para a hora corrente. Assim, uma página que recebe uma segunda chance não será substituída até que todas as outras páginas
tenham sido substituídas 
Uma forma de implementar o algoritmo da segunda chance (às vezes chamado o algoritmo do relógio) é como uma fila circular. Um ponteiro (isto é, um ponteiro do relógio) indica que página deve ser substituída a seguir .
Uma forma de implementar o algoritmo da segunda chance (às vezes chamado o algoritmo do relógio) é como uma fila circular. Um ponteiro (isto é, um ponteiro do relógio) indica que página deve ser substituída a seguir.
Algoritmo da Segunda Chance Aperfeiçoado
Aperfeiçoar o algoritmo da segunda chance considerando o bit de referência e o bit de modificação como um par ordenado, com esses dois bits, podemos ter as quatro categorias a seguir:
 (0, 0) nem recentemente utilizada nem modificada — melhor página para a substituição
 (0, 1) não recentemente utilizada mas modificada — não é uma opção tão boa porque a página terá que ser gravada em disco antes da substituição
 (1, 0) recentemente utilizada mas não modificada — provavelmente será usada novamente em breve
 (1, 1) recentemente utilizada e modificada — provavelmente será usada novamente em breve e terá que ser gravada em disco antes de poder ser substituída 
Cada página está em uma dessas quatro classes. Quando a substituição de páginas é chamada, usamos o mesmo esquema do algoritmo do relógio, mas, em vez de verificar se a página para à qual estamos apontando tem o bit de referência posicionado com 1, examinamos a classe a qual essa página pertence. Substituímos a primeira página encontrada na classe não vazia mais baixa. 
A principal diferença entre esse algoritmo e o algoritmo do relógio mais simples é que aqui damos preferência às páginas que foram modificadas para reduzir a número de operações de I/O requeridas.
Substituição de Páginas Baseada em Contagem
Manter um contador do número de referências que foram feitas a cada página e desenvolver os dois esquemas a seguir.
O algoritmo de substituição de páginas menos frequentemente utilizadas (LFU — least frequently used) requer que a página com a menor contagem seja substituída. A razão dessa seleção é que uma página ativamente utilizada deve ter uma contagem de referências alta. Um problema surge, no entanto, quando uma página é muito usada durante a fase inicial de um processo e então nunca mais é usada. Já que ela foi muito usada, tem uma contagem alta e permanece na memória, ainda que não seja mais necessária. Uma solução é deslocar as contagens de 1 bit para a direita em intervalos regulares, formando uma contagem de utilização média exponencialmente decrescente.
O algoritmo de substituição de páginas mais frequentemente utilizadas (MFU — most frequently used) é baseado no argumento de que a página com a menor contagem provavelmente acabou de ser trazida à memória e ainda deve ser usada. 
Nem a substituição MFU nem a LFU são comuns, a implementação desses algoritmos é cara, e eles não são uma boa aproximação da substituição OPT.
Algoritmos de Armazenamento de Páginas em Buffer 
Os sistemas normalmente mantêm um pool de quadros livres, quando ocorre um erro de página, um quadro vítima é selecionado como antes. 
A página desejada é lida para um quadro livre do pool antes de a vítima ser gravada em disco, esse procedimento permite que o processo seja reiniciado assim que possível, sem esperar que a página-vítima seja gravada, quando a vítima é gravada posteriormente, seu quadro é adicionado ao pool de quadros livres. 
Uma expansão dessa ideia é manter uma lista de páginas modificadas, sempre que o dispositivo de paginação está ocioso, uma página modificada é selecionada e gravada no disco, seu bit de modificação é então redefinido. Esse esquema aumenta a probabilidade de que uma página não tenha modificações quando é selecionada para substituição e ela não precisará ser gravada. 
Outra variação é manter um pool de quadros livres, porém lembrar qual página estava em cada quadro, já que o conteúdo dos quadros não é modificado quando um quadro é gravado em disco, a página anterior pode ser reutilizada diretamente a partir do pool de quadros livres se ela for necessária antes que esse quadro seja reutilizado. Nenhum I/O é necessário nesse caso. Quando ocorre um erro de página, primeiro verificamos se a página desejada está no pool de quadros livres. Se não estiver, devemos selecionar um quadro livre e transferir a página para ele .
Essa técnica é usada no sistema VAX/VMS junto com um algoritmo de substituição FIFO. 
Algumas versões do sistema UNIX usam esse método em conjunção com o algoritmo da segunda chance.
51
As Aplicações e a Substituição de Páginas 
Em certos casos, as aplicações que acessam dados através da memória virtual do sistema operacional têm execução pior do que se o sistema operacional não fornecesse nenhum armazenamento em buffer. Um exemplo típico é um banco de dados que forneça seu próprio gerenciamento de memória e buffer de I/O. 
Por causa desses problemas, alguns sistemas operacionais fornecem a programas especiais o recurso de usar uma partição de disco como um grande array sequencial de blocos lógicos, sem quaisquer estruturas de dados do sistema de arquivos.
 Esse array é em alguns casos chamado disco bruto, e o I/O para esse array é denominado I/O bruto. O I/O bruto ignora todos os serviços do sistema de arquivos, tais como a paginação por demanda do I/O de arquivo, o bloqueio de arquivos, a pré-busca, a alocação de espaço, os nomes de arquivos e os diretórios. 
Embora certas aplicações sejam mais eficientes quando implementam seus próprios serviços de armazenamento de uso específico em uma partição bruta, a maioria das aplicações tem execução melhor quando usa os serviços regulares do sistema de arquivos.
Alocação de Quadros 
Como alocar o montante fixo de memoria livre entre vários processos?
Sistema monousuário.
Sob Paginação por demanda pura.
Numero de Quadros Mínimos 
Interferência no Desempenho.
O numero de quadros mínimos é definido pela arquitetura do computador.
Algoritmos de Alocação
Divisão de Quadros por Processos(Alocação igual)
Alocação proporcional
Alocação Global versus Local
Substituição de Paginas
Substituição Global
Substituição local
Acesso não Uniforme à Memória
Diferenças de Desempenho
Alterações algorítmicas
Numero de Threads
Atividade improdutiva (Thrashing)
Causa da Atividade Improdutiva
Atividade improdutiva (Thrashing)
Substituição local.
Modelo de Localidade.
Modelo de Conjunto de Trabalho
Conjunto de Trabalho.
Interrupção por Timer e um Bit de Referencia.
Frequência de Erros de Paginas 
Controle de taxa de erros.
Arquivos Mapeados para a Memoria
Endereçamento virtual.
Mapeamento de um Bloco de disco para uma Pagina.
Autorização para mapear o mesmo arquivo.
Memoria Compartilhada na API do Windows
Comunicação Entre os Processos
I/O Mapeado para a Memória
I/O para Outros Dispositivos.
I/O Programado.
Alocando Memória do kernel
Uso de Memória de Forma Conservadora.
As páginas alocadas a processos em modalidade de usuário não têm necessariamente que estar em memória física contígua. No entanto, certos dispositivos de hardware interagem diretamente com a memória física — sem o benefício de uma interface de memória virtual — e, consequentemente, podem requerer memória que resida em páginas fisicamente contíguas.
Sistema de Pares
Vantagem do Sistema de Pares.
Desvantagem do Sistema de Pares.
Alocação de Slabs
O queé um Slab?
Armazenamento de Objetos do Kernel.
Atividade Improdutiva
A atividade Improdutiva é a alta atividade de paginação, causada pela insuficiência de quadros de um processo. Caso um processo não tenha o número de quadros que precisa para suportar páginas de uso ativo, ocorrerá um erro, sendo assim ele substitui alguma página. Porém se todas as páginas estão em uso ativo ocorrerá outros erros e outras substituições, gerando um loop de erro e substituição de páginas que deveriam ser retornadas de imediato.
Causas da Atividade Improdutiva
Imagine um cenário dos primeiros sistemas de paginação, em que o sistema operacional monitora o uso da CPU. Quando o uso da CPU está baixo, o grau de multiprogramação é aumentado inserindo um novo processo no sistema. Um algoritmo global de páginas é utilizado, ele substitui páginas sem ter a preocupação com o processo ao qual elas pertencem. Caso um processo entre em uma nova fase de execução que precise de mais quadros, ele começa a falhar e tirar quadros de outros processos. Porém esses processos precisam dessas páginas, sendo assim eles também falham, retirando quadros de outros processos. Esses processos com falhas precisam de usar o dispositivo de paginação para inserir e remover páginas da memória. Á medida que os processos se enfileiram em espera pelo dispositivo de paginação, a fila de prontos esvazia. Enquanto os processos esperam por esse dispositivo de paginação, o uso da CPU diminui.
O scheduler percebe a diminuição do uso da CPU e aumenta o grau de multiprogramação, o novo processo que tenta ser executado tira quadros de processos em execução, gerando mais erros de página e uma fila maior de processo esperando pelo dispositivo de paginação. Como consequência o uso da CPU cai mais ainda e seu scheduler tenta aumentar o grau de multiprogramação de novo. O Thrashing ocorre e o throughtput do sistema despenca. Nenhuma atividade está sendo executada pois os processos estão perdendo tempo paginando.
Outras causas de atividades improdutivas 
No gráfico é possível ver que quando a utilização da CPU está baixa o nível de multiprogramação aumenta até chegar a um pico máximo de utilização de CPU, e se ainda o grau aumentar ainda mais, é quando o Thrashing inicia e há uma queda significativa da atividade da CPU. Para consertar esse problema o grau de multiprogramação deve ser diminuído.
Soluções para Thrashing
É possível amenizar os efeitos de Thrashing utilizando o algoritmo de substituição local. Quando um processo sofre Thrashing ele não pode roubar os quadros de outro processo, causando mais Thrashing. Porém o problema não é resolvido, pois ao ficarem em Thrashing eles passam maior tempo na fila do dispositivo de paginação, o tempo médio de manipulação de um erro de página aumentará em razão do aumento na fila média de espera pelo dispositivo de paginação, ou seja, até para processos que não estão em thrashing o tempo de acesso efetivo aumentará para que o problema seja realmente resolvido é necessário garantir que o processo utilize quantos quadros ele precisar, mas para isso é preciso saber quantos quadros ele precisa. A estratégia do conjunto de trabalho examina quantos quadros um processo está utilizando realmente. Isso define o modelo de localidade de execução de processos.
O modelo de localidade define que um processo quando executado, move-se de uma localidade a outra, e essas localidades são na verdade um conjunto de paginas que são usadas ativamente simultaneamente. Em modo geral um programa é composto por várias localidades diferentes que podem se sobrepor.
Quando uma função é chamada, ela define uma nova localidade, nessa localidade referências de memória são feitas às instruções da chamada de função, suas variáveis locais e um subconjunto das variáveis globais. Após sair da função, o processo deixa essa localidade, pois as variáveis locais e as instruções da função não estão mais em uso ativo. É possível retornar a essa localidade posteriormente.
Sendo assim, as localidades são definidas pela estrutura do programa e suas estruturas de dados. O modelo de localidade define que todos os programas mostrarão essa estrutura básica de referência a memória.
Caso fosse alocado quadros suficientes para um processo acomodar sua localidade corrente, ele falharia pela falta de páginas em sua localidade até que todas essas páginas estiverem na memória e então não irá falhar até mudar de localidade. Se não for alocado o número de quadros suficientes para acomodar o tamanho da localidade corrente, o processo entrará em Thrashing, já que não poderá manter na memória todas as páginas que está utilizando ativamente.
Modelo de Conjunto de Trabalho
O modelo do conjunto de trabalho é baseado em localidade, sendo assim ele usa Δ para definir a janela do conjunto de trabalho. Com isso examina as Δ referências de página mais recentes. O conjunto de páginas das Δ referencias de página mais recentes é o conjunto de trabalho. Se uma página estiver em uso ativo, ela fará parte do conjunto de trabalho. Se não for mais usada, sairpá do conjunto de trabalho Δ unidades de tempo após sua última referencia. Então o conjunto de trabalho é uma aproximação da localidade do programa.
Exemplo
 Dada sequencia de referencias de memória na seguinte figura, se Δ = 10 referencias de memoria, então o conjunto de trabalho no tempo t1 é {1, 2, 5, 6, 7}. No tempo t2, o conjunto de trabalho terá mudado para {3, 4}.
A precisão do conjunto de trabalho depende do tamnho de Δ, se for muito pequeno, não abrangerá a localidade inteira; se Δ for muito grande, poderá sobrepor várias localidades. E no caso extremo se Δ for infinito, o conjunto de trabalho será o conjunto de páginas referenciadas durante a execução do processo.
Uma vez que o Δ tenha sido selecionado, o sistema operacional monitora o conjunto de trabalho de cada processo fornecendo, a cada um desses conjunto de trabalho, quadros suficientes de acordo com seu tamanho. Caso haja quadros adicionais suficientes um outro processo poderá ser iniciado. Se a soma total do tamanho dos conjuntos de trabalho aumentar, excedendo o número total de quadros disponíveis, o sistema operacional selecionará um processo para suspensão. As páginas do processo suspenso serão gravadas em disco (removidas da memória) e seus quadros serão realocados a outros processos. Posteriormente o processo podera ser reiniciado.
Com esse método não há possibilidade de Thrashing e o grau de multiprogramação ficará o mais alto possivel, ou seja, ele otimiza o uso da CPU. A dificuldade do método de conjunto de trabalho é o seu controle. A janela de conjunto de trabalho é uma janela móvel. A cada referencia dá memoria, surge uma nova referencia em uma extremidade, e a referencia mais antiga deixa de existir na outra extremidade. Uma página faz parte do conjunto de trabalho se ela for referenciada em algum ponto na janela do conjunto de trabalho.
Frequência de Erros de Página
A frequência de erros de pagina (PFF - Page-fult frequency) é uma abordagem mais direta que o modelo método de conjunto de trabalho. 
O problema de Thrashing possui alta taxa de erro de paginas, quando ela é muito alta significa que o processo precisa de mais quadros; e inversamente se a taxa é muito baixa significa que o processo possui quadros demais. Afim de corrigir isso podemos estabelecer um limite superior e um inferior, se passar do limite superior aloca mais quadros ao processo, caso passar do limite inferior retiramos quadros do processo, assim medindo e controlando diretamente a taxa de erros de página para impedir o Thrashing.
Como no modelo anterior pode-se retirar um processo da memória, para liberar mais quadros e distribui-los para outros processos, o processo removido é alocado na memória secundária.

Mais conteúdos dessa disciplina