·
Cursos Gerais ·
Outros
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Sistemas Operacionais Gerência de Memória ProfVagner Sistemas Operacionais Gerência de Memória A organização e gerência da memória principal têm sido fatores importantes no projeto de sistemas operacionais Quando falamos em gerência de memória estamos falando da memória primária também denominada RAM Principal ou Real Sistemas Operacionais Gerência de MemóriaMonoprogramação Não confundir Memória Principal Onde residem todos os programas e dados que serão utilizados pelo processador Memória Secundária É um meio permanente mais abundante e de baixo custo para armazenar os dados Sistemas Operacionais Gerência de Memória com Monoprogramação Sistemas Operacionais Gerência de MemóriaMonoprogramação A memória principal é dividida em 2 partes uma para o SO e outra para os programas do usuário O programador não deve ultrapassar o espaço de memória disponível o tamanho da memória principal menos o espaço ocupado pelo SO Sistemas Operacionais Gerência de MemóriaMonoprogramação Sistema Operacional Área para o programa do Usuário Sistemas Operacionais Gerência de MemóriaMonoprogramação O usuário tem total acesso a memória inclusive a área do SO É possível ao usuário destruir o SO Implementação de uma proteção através de um registrador Sistemas Operacionais Gerência de MemóriaMonoprogramação Sistema Operacional Área para o programa do Usuário Registrador Sistemas Operacionais Gerência de Memória com Multiprogramação Sistemas Operacionais Gerência de MemóriaMultiprogramação Como vimos em ambientes monoprogramáveis os problemas eram mais simples Basicamente o SO deveria garantir espaço para o próprio SO e para o programa em uso Sistemas Operacionais Gerência de MemóriaMultiprogramação Porém quando múltiplos processos residem na memória simultaneamente num ambiente multiprogramável os problemas de gerenciamento e proteção são muito mais complexos Isto se dá basicamente porque o sistema deve proteger os processos dos usuários uns dos outros Sistemas Operacionais Gerência de MemóriaMultiprogramação Principais aspectos relativos ao gerenciamento da memória principal Armazenar novos processos em memória sem destruir um processo que já está atualmente na memória Impedir que um processo em execução altere os dados de outro Sistemas Operacionais Gerência de MemóriaMultiprogramação O que fazer se um processo precisa ser executado mas não há espaço na memória Gerenciar a ocupação da memória O que fazer se um processo necessitar de mais memória do que o sistema possui Sistemas Operacionais Gerência de MemóriaMultiprogramação Se um processo que não está na memória tem de ser executado mas a memória está cheia o que deve ser removido da memória Todos estes aspectos estão envolvidos no gerenciamento de memória Sistemas Operacionais Gerência de MemóriaMultiprogramação Uma abordagem inicial para o gerenciamento de memória em sistemas multitarefa envolve a divisão da memória em regiões denominadas partições Sistemas Operacionais Gerência de MemóriaMultiprogramação Neste método o sistema operacional deve ter uma tabela de dados indicando quais partições estão disponíveis Essa tabela é chamada de tabela de partições Sistemas Operacionais Gerência de MemóriaMultiprogramação Regras Um programa pode ocupar somente uma partição Uma partição pode conter somente um processo Sistemas Operacionais Partições Fixas Sistemas Operacionais Partições Fixas O esquema de partições fixas utiliza a memória de maneira pouco eficiente O tamanho da partição faz parte do esquema do sistema operacional A proteção baseiase em dois registradores inferior e superior Sistemas Operacionais Partições Fixas Tamanho estabelecido na fase de inicialização Programas geralmente não ocupam toda a partição O problema da memória desperdiçada é denominado fragmentação Sistemas Operacionais Partições Fixas Exemplo 1 Para um computador de 320 KB de memória serão criadas 4 partições iguais Imagine que surjam os seguintes processos Processo A cnecessidade de 40 KB de memória Processo B cnecessidade de 70 KB de memória Processo C cnecessidade de 68 KB de memória Mostre como será alocados estes processos Sistemas Operacionais Partições Fixas Exemplo 1 continuação Dada a situação anterior o que ocorrerá se um novo processo D surgir necessitando de 95 KB Sistemas Operacionais Partições Fixas Exemplo 2 Para o mesmo computador do exemplo anterior 320 KB RAM serão criadas as seguintes partições 40 KB 40 KB 70 KB 70 KB e 100 KB Como serão alocados os mesmos processos do exemplo anterior Sistemas Operacionais Partições Dinâmicas Sistemas Operacionais Partições Dinâmicas No esquema de partições dinâmicas o tamanho das partições não é definido previamente Em vez disso o sistema operacional as define dinamicamente com base na necessidade dos processos correntes Sistemas Operacionais Partições Dinâmicas O sistema operacional cria uma partição cujo tamanho corresponde exatamente às necessidades de memória do processo Quando o processo termina o sistema então libera a memória Sistemas Operacionais Partições Dinâmicas Exemplo 1 Para o mesmo computador do exercício anterior 320 KB RAM Como serão alocados os mesmos processos do exemplo anterior Processo A 40KB Processo B 70KB Processo C 68KB e Processo D 95KB Sistemas Operacionais Partições Dinâmicas Exemplo 2 Suponha que os processos A e C terminem e as respectivas partições sejam liberadas Agora suponha que surja um processo E com necessidade de 110 KB o que ocorrerá Sistemas Operacionais Partições Dinâmicas Observações Apesar de termos um total livre de 155 KB o processo não poderá ser alocado na memória Neste momento não existe uma partição livre que comporte o processo Sistemas Operacionais Partições Dinâmicas Observações Se estivéssemos falando das partições fixas este processo nunca seria alocado Porém nas partições dinâmicas depois de identificada a fragmentação da memória existem duas soluções para o problema Sistemas Operacionais Partições Dinâmicas Soluções possíveis 1 Reunir os espaços adjacentes Ou seja as áreas contíguas livres são reunidas numa única partição Para esta solução seria necessário esperarmos o término do processo B que liberaria 70 KB Sistemas Operacionais Partições Dinâmicas Soluções possíveis 1 Reunir os espaços adjacentes Desta forma seria possível reunirmos a partição 1 40 KB e a partição 2 70 KB o que totalizaria 110 KB Assim seria possível a alocação do processo E nesta nova partição Sistemas Operacionais Partições Dinâmicas Soluções possíveis 2 Relocar toda a memória Esta solução envolve a reorganização da memória Ocorre assim a relocação de todas as partições ocupadas São eliminando todos os espaços entre elas e criando uma única área livre contígua Sistemas Operacionais Partições Dinâmicas Soluções possíveis 2 Relocar toda a memória Ou seja é como se a memória fosse zerada e os processos existentes fossem novamente alocados Sistemas Operacionais Exercício 1 Temos um computador com memória de 450 KB Surgem os processos A B e C que necessitam respectivamente de 50 100 e 150 KB O esquema utilizado é o gerenciamento por partições fixas de mesmo tamanho 3 partições iguais Sistemas Operacionais Exercício 1 a Como serão alocados estes processos b Haverá fragmentação Especifique c O que vai acontecer se um novo processo D com necessidade de 70 KB surgir Comente d O que vai acontecer se o processo B terminar e um novo processo E com necessidade de 160 KB surgir Comente Sistemas Operacionais Exercício 2 Refaça o exercício anterior para o esquema de gerenciamento por partições fixas Partições criadas 50 75 150 e 175 Kb Sistemas Operacionais Exercício 3 Refaça o exercício para o esquema de gerenciamento por partições dinâmicas Obs para cada item considere o anterior Sistemas Operacionais Estratégias de alocação de partições Sistemas Operacionais Estratégias de alocação de partições É o método utilizado para que um processo seja alocado numa partição já existente Devem principalmente evitar ou diminuir o problema da fragmentação O fator mais importante na escolha da estratégia é o tamanho do programa Basicamente implementamse três estratégias Firstfit Bestfit e Worstfit Sistemas Operacionais 1 Estratégia Firstfit Nesta estratégia a primeira partição livre que comporte o processo deve ser a escolhida Não importa o tamanho da mesma Apesar da simplicidade não há nenhum comprometimento com a eficiência do método Obs este foi o método utilizado nos nossos exemplos e no exercício anterior Sistemas Operacionais 2 Estratégia Bestfit Nesta estratégia a partição escolhida deve ser a menor partição livre que comporte o processo Ou seja aquela que tem o melhor ajuste Neste método o objetivo é que a fragmentação seja a menor possível a partir da escolha da partição mais próxima do tamanho do processo Apesar de inicialmente a fragmentação ser menor conforme os processos forem terminando processos cada vez menores serão alocados aumentando a fragmentação Sistemas Operacionais 3 Estratégia Worstfit Nesta estratégia a partição escolhida deve ser a maior partição livre que comporte o processo Ou seja aquela que tem o pior ajuste Neste método o objetivo é que apesar da fragmentação ser maior inicialmente a medida que os processos forem terminando os espaços deixado sejam maiores evitando assim o problema da Best fit Sistemas Operacionais Exercício 4 Temos livres as seguintes partições 1 2 e 3 com as respectivas áreas de 3 2 e 5 KB Surge um processo A que necessita de 1 KB de memória Como o mesmo será alocado para as estratégias a FirstFit b BestFit c WorstFit Sistemas Operacionais Exercício 5 Refaça os itens para a chegada de um novo processo B com necessidade de 3 KB Sistemas Operacionais Swapping Mesmo com o aumento da eficiência do gerenciamento de memória muitas vezes um processo não podia ser executado por falta de uma partição livre disponível Imagine a seguinte situação temos a memória ocupada conforme descrito a seguir Sistemas Operacionais Swapping Sistemas Operacionais Swapping Surge então um processo F com necessidade de 20 KB e precisa ser executado Para que ele possa ser executado tem que estar alocado na memória o que fazer então se não há partição disponível Sistemas Operacionais Swapping A técnica de swapping veio tentar resolver o problema O swapping é uma técnica aplicada à gerência de memória para programas que esperam por memória livre para serem processados Sistemas Operacionais Swapping Nesta situação o sistema escolhe um programa para deixar a memória Este será levado da memória para o disco swap out O programa que aguardava memória fará o caminho inverso do disco para a memória principal swap in Sistemas Operacionais Swapping No exemplo o SO deve escolher um processo e leválo para o disco para que a partição ocupada por ele fique livre e o processo F possa então ser alocado Mas qual deverá ser o processo escolhido De preferência um processo que não esteja prestes a retornar para a CPU Sistemas Operacionais Swapping Sistemas Operacionais Swapping Apesar da evolução no sistema de partições e da técnica de swapping um problema não podia ser resolvido O que fazer quando um processo maior que a memória disponível precisava ser alocado Sistemas Operacionais Gerência de Memória Virtual Sistemas Operacionais Gerência de Memória Virtual A estratégia denominada Memória virtual é uma técnica de gerenciamento de memória onde as memórias principal RAM e secundária Disco são combinadas permitindo a execução de um determinado processo cujo tamanho exceda o da memória principal disponível Sistemas Operacionais Memória Virtual Memória Principal Memória Secundária Sistemas Operacionais Mas surge uma questão Como sempre vimos o processo em execução dados instruções deve estar alocado na Memória RAM sendo assim como então é possível que parte do processo esteja no disco Sistemas Operacionais Isto é possível pois não é o processo inteiro que precisa estar na memória mas apenas as partes que estão sendo referenciadas Sendo assim o sistema operacional passa a ser responsável por manter na memória as partes do processo efetivamente em uso deixando o resto no disco Sistemas Operacionais Por exemplo um processo de 1 Mb pode rodar numa máquina com 256 Kb de memória escolhendose cuidadosamente os 256 Kb do processo que deverão ser mantidos na memória a cada instante Desta forma os conceitos de memória virtual e multitarefa funcionam muito bem em conjunto Enquanto um programa está esperando que outra parte dele seja carregado na memória ele estará bloqueado e não poderá ser executado e assim o processador será entregue a outro processo Sistemas Operacionais Mas então duas novas questões surgem Como o processador pode acessar endereços maiores que o existente na memória física Como dividir o processo para que partes estejam na memória real e partes no disco Sistemas Operacionais Respondendo a primeira questão Como o processador pode acessar endereços maiores que o existente na memória física Espaço de endereçamento virtual Sistemas Operacionais Espaço de endereçamento virtual Os programas não fazem referência aos endereços físicos endereços reais mas sim aos endereços virtuais No momento da execução o endereço virtual é traduzido para o endereço físico pois o processador acessa apenas posições da memória principal Sistemas Operacionais Espaço de endereçamento virtual Espaço de endereçamento virtual é o nome que se dá ao conjunto de endereços virtuais que os processos podem endereçar Muito próximo da idéia de um vetor referência da posição em que um dado se encontra Sistemas Operacionais Espaço de endereçamento virtual End Físico 500 501 700 720 350 100 502 Vetor Vetor1 Vetor2 Vetor3 Vetor4 Vetor5 Vetor6 Vetor7 Sistemas Operacionais Espaço de endereçamento virtual Quando a memória virtual é utilizada os endereços virtuais não são enviados diretamente para o barramento do computador e sim para um dispositivo chamado Memory Management Unit MMU Este dispositivo é um componente de hardware que mapeia endereços virtuais nos endereços de memória física Sistemas Operacionais Memória Virtual Memória Principal Mapeamento Sistemas Operacionais MMU Memory Management Unit Unidade de gerência de Memória Componente do hardware responsável por implementar os mecanismos usados pelo Sistema Operacional para gerenciar a memória Vai mapear os endereços lógicos gerados pelos processos nos correspondentes endereços físicos que serão enviados para a memória Sistemas Operacionais TLB Translation lookaside buffer Nos sistemas atuais a tradução é realizada por hardware em conjunto com o SO O TLB é uma tabela que funciona como uma memória associativa mantendo os últimos endereços mapeados Objetivo é reduzir o tempo gasto no mapeamento Cada processo passou a implementar a sua própria tabela de mapeamento tabelas exclusivas de mapeamento Sistemas Operacionais Espaço virtual de A Memória Principal Tabela de Mapeamento A Espaço virtual de B Tabela de Mapeamento B Sistemas Operacionais Respondendo a segunda questão Como dividir o processo para que partes estejam na memória real e partes no disco Paginação paging Sistemas Operacionais Paginação paging O espaço de endereçamento virtual é dividido em unidades denominadas páginas As unidades correspondentes na memória física RAM são as molduras de páginas page frames As páginas e as molduras de páginas são sempre do mesmo tamanho Sistemas Operacionais Paginação paging As transferências da memória para o disco e viceversa são sempre feitas em páginas Por exemplo Páginas de 4 KB Com 128 KB de espaço de endereçamento virtual e 64 KB de memória real teremos 32 páginas virtuais 16 molduras de página Sistemas Operacionais Memória Principal Disco Sem memória virtual CPU Tabela de endereços de memória Memória física Antes a tabela apontava para exatamente o endereço físico da memória Com memória virtual 0 1 2 3 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Tabela de endereços de memória MMU 0 1 2 3 Fonte da imagem do HD httpwwwshutterstockcom Memória física Memória secundária Sistemas Operacionais Paginação paging Quando uma página é referenciada e não está na memória real ocorre um page fault falha de página Memória Principal Sistemas Operacionais Endereço Virtual Tab Páginas Bit validade 0 Tab Páginas Bit validade 1 Memória Principal Page fault Sistemas Operacionais Paginação paging Neste caso a página deverá ser carregada da memória secundária disco para a memória RAM ocorrendo um page in Caso uma página precise ser retirada da Memória acontecerá um page out Sistemas Operacionais Page out Page in Memória Principal Arquivo de Paginação Sistemas Operacionais A técnica de paginação responde a questão anterior porém novas questões surgem Como as páginas dos diversos processos dividirão entre si a memória Na ocorrência do page fault como a página deverá ser trazida para a memória No caso de não existirem frames livres qual página deverá sofrer o page out para que uma nova página sofra o page in Sistemas Operacionais Estas questões são respondidas pelas 3 políticas que normatizam a paginação 1 Política de alocação 2 Política de busca 3 Política de substituição Sistemas Operacionais 1 Política de alocação É a estratégia que define quantos frames um processo terá direito Duas estratégias são possíveis Alocação Fixa Alocação Variável Sistemas Operacionais 1a Política de alocação fixa Nesta estratégia o número de frames que o processo tem direito é fixo Neste caso dois problemas podem acontecer Se o processo receber um número de frames muito pequeno a taxa de paginação pode ser alta Se o processo receber um número muito grande de frames pode ocorrer um desperdício de memória Sistemas Operacionais 1b Política de alocação variável Nesta estratégia o número de frames vai variar de acordo com a ocupação da memória e a taxa de paginação Desta forma o número de frames pode ser adequado a necessidade dos processos Sistemas Operacionais 2 Política de Busca Quando ocorre o page fault a página referenciada deve ser trazida do disco para a memória real A política de busca é a estratégia que define como a página será levada para a memória Duas estratégias são possíveis Busca por demanda Busca antecipada Sistemas Operacionais 2a Política de Busca por Demanda Nesta estratégia somente a página referenciada é carregada do disco para a memória RAM quando ocorre o page fault Esta forma é muito eficiente pois somente a página efetivamente necessária é carregada na memória Sistemas Operacionais 2b Política de Busca Antecipada Nesta estratégia além da página referenciada as páginas próximas também são carregadas na memória principal O objetivo é antecipar as páginas que serão referenciadas num próximo momento com o objetivo de reduzir a taxa de paginação Sistemas Operacionais 2b Política de Busca Antecipada Por outro lado o fato de antecipar páginas na memória RAM pode carregar na memória páginas que nunca serão referenciadas Ocorrerá assim um desperdício de memória Sistemas Operacionais 3 Política de Substituição Imagine a seguinte situação ocorreu o page fault e uma página deve ser carregada na memória RAM porém não há nenhum frame livre O que o sistema operacional deve fazer O S O deve escolher uma página que está na memória para sofrer o page out ou seja deixar a memória RAM e voltar para o disco Sistemas Operacionais 3 Política de Substituição A política de substituição é responsável por definir de qual processo deverá ser o frame liberado Duas estratégias são possíveis Substituição Local Substituição Global Sistemas Operacionais 3a Política de Substituição Local Nesta estratégia o frame a ser liberado deve pertencer ao mesmo processo que gerou o page fault Ou seja o page in e o page out serão do mesmo processo Sistemas Operacionais 3b Política de Substituição Global Nesta estratégia o frame a ser liberado pode pertencer a qualquer processo do sistema Ou seja não há relação entre o processo que sofrerá o page in e o processo que sofrerá page out Sistemas Operacionais Conclusão As 3 políticas respondem as perguntas anteriores 1 Como as páginas dos diversos processos dividirão entre si a memória 2 Na ocorrência do page fault como estas páginas deverão ser trazidas para a memória 3 No caso de não existirem frames livres qual página deverá sofrer o page out para que uma nova página sofra o page in Mas surge uma nova pergunta No caso do pageout qual deve ser exatamente a página a ser liberada Sistemas Operacionais Algoritmos de substituição Como citado no slide anterior no momento em que uma página deve ser carregada porém não há nenhum frame livre uma página deve ser retirada da memória para que um frame seja liberado O algoritmo de substituição é o responsável por determinar qual deve ser a página a sair da memória Sistemas Operacionais Algoritmo Ótimo Este é um algoritmo hipotético ou seja existe apenas no campo das hipóteses Serve apenas como um referencial para os demais algoritmos E o que seria então um algoritmo considerado ótimo Sistemas Operacionais Algoritmo Ótimo Seria o algoritmo que conseguisse prever exatamente a página que não será mais utilizada sendo assim a página ideal para ser substituída Por que isto seria ótimo Sistemas Operacionais Algoritmo Ótimo Porque se o algoritmo retirar uma página que será referenciada a página vai gerar um page fault necessitará do page in e aumentará o tráfego entre memória e disco Sendo assim o algoritmo que conseguisse evitar com precisão esta situação poderia ser considerado ótimo Sistemas Operacionais Algoritmo FIFO First In First Out Nesta estratégia a página que foi alocada primeiro deve ser a escolhida Ou seja a página mais antiga na memória é a que sofrerá o page out O algoritmo FIFO parte do princípio que a página mais antiga é aquela que não será mais utilizada Sistemas Operacionais Algoritmo FIFO First In First Out Apesar de inicialmente parecer um raciocínio correto isto não é o que ocorre na prática Sendo assim apesar do algoritmo FIFO ser de fácil implementação o algoritmo deixa a desejar Sistemas Operacionais Algoritmo LFU Least Frequently Used O algoritmo LFU tem por objetivo escolher a página menos referenciada ou seja a página que o processo acessou menos vezes Para tornar isto possível o algoritmo associa a cada página um contador de referências A cada referência na página o contador correspondente é incrementado Sistemas Operacionais Algoritmo LFU Least Frequently Used No momento da substituição o algoritmo escolhe a página cujo contador é o menor entre todos ou seja a página que foi menos vezes referenciada Novamente podemos achar esta estratégia muito boa afinal a página menos referenciada poderá ser aquela que não será mais utilizada correto Sistemas Operacionais Algoritmo LFU Least Frequently Used Mas novamente há uma falha evidente imagine que uma página acabou de ser alocada na memória quando ocorrer um novo page fault o que acontecerá Por ter sido referenciada uma só vez a página que acabou de ser alocada será a escolhida e deixará a memória Sistemas Operacionais Algoritmo LRU Least Recently Used O algoritmo LRU escolhe a página que está mais tempo sem ser referenciada O raciocínio é simples a página que está mais tempo sem ser referenciada é porque não está mais sendo utilizada Portanto é a candidata ideal para sofrer o page out Sistemas Operacionais Algoritmo LRU Least Recently Used O algoritmo mantém a fila ordenada em ordem cronológica por referência e a cada nova referência a fila deve ser reordenada Este é o único ponto negativo do algoritmo pois gera um grande overhead pois as páginas precisam ser constantemente atualizadas no momento do último acesso Sistemas Operacionais Algoritmo NRU Not Recently Used Este algoritmo também busca escolher a página que não está mais sendo referenciada Porém ao invés de trabalhar com uma fila constantemente reordenada como vimos anteriormente este algoritmo trabalha com um BR Bit de referência para cada página alocada na memória Sistemas Operacionais Algoritmo NRU Not Recently Used O BR Bit de referência tem em seus valores os seguintes significados 0 Página não referenciada 1 Página referenciada Sistemas Operacionais Algoritmo NRU Not Recently Used Estes valores são atribuídos da seguinte forma Quando uma página é referenciada o valor 1 é atribuído para o seu BR correspondente De tempos em tempos todos os BRs Bits de referência são zerados Sistemas Operacionais Algoritmo NRU Not Recently Used Sendo assim no momento da substituição o algoritmo deverá escolher entre as páginas que estão com BR0 Também pode ser utilizado o BM Bit de modificação que tem em seus valores os seguintes significados 0 Página não modificada 1 Página modificada Sistemas Operacionais Algoritmo NRU Not Recently Used O objetivo do uso do BM é determinar se a página que deixará a memória deverá ser salva no disco ou não Se a página teve alguma modificação BM1 ela necessariamente deverá ser salva caso contrário haverá perda de integridade Sistemas Operacionais Algoritmo NRU Not Recently Used Porém se no momento da substituição BM0 isto significa que a página não foi alterada e portanto não precisa ser salva Desta forma uma operação de IO desnecessária Por que salvar uma página que não modificada não será realizada melhorando a performance Sistemas Operacionais Exercícios Um processo com necessidade de 80 KB de memória está com as 5 primeiras páginas carregadas na memória real A Quantas páginas estarão na memória secundária sabendose que o frame tem 4 KB B O que acontecerá se o programa endereçar uma instrução da página 6 Sistemas Operacionais C Qual página deverá ser substituída para os métodos FIFO LFU LRU NRU Considere que as páginas foram referenciadas na ordem 1 2 3 4 4 5 1 2 3 1 2 e 3 Para o NRU considere BR0 após 7 referências de páginas Sistemas Operacionais Algoritmo FIFO com buffer Neste algoritmo ao invés de uma só fila para determinar qual página deve ser substituída temos duas LPA Lista de páginas alocadas LPL Lista de páginas livres Sistemas Operacionais Algoritmo FIFO com buffer Como o próprio nome diz a metodologia de trabalho é FIFO Porém a página mais antiga da LPA ao invés de ser a página a ser substituída é inserida no final da LPL Sistemas Operacionais Algoritmo FIFO com buffer Sistemas Operacionais Algoritmo FIFO com buffer A página a ser substituída deverá ser a página que estiver no topo da LPL Inicialmente isto poderá parecer um FIFO com duas filas porém se uma página que estiver na LPL for referenciada ela volta ao final da LPA Desta forma a página que estiver no topo da LPL é porque realmente não foi mais referenciada Sistemas Operacionais Algoritmo FIFO com buffer Sistemas Operacionais Algoritmo FIFO com clock Neste algoritmo existe uma só fila para determinar qual página deve ser substituída Cada página contém um BR O ponteiro apontará inicialmente para a página mais antiga como um FIFO tradicional Sistemas Operacionais Algoritmo FIFO com clock Mas apesar do ponteiro inicialmente apontar para a página mais antiga ela somente será substituída se o BR0 Caso o BR1 o algoritmo troca o BR para zero e vai verificar a próxima página da fila Assim sendo o ponteiro vai circular pela fila Sistemas Operacionais Algoritmo FIFO com clock Sistemas Operacionais Algoritmo FIFO com clock Sistemas Operacionais Algoritmo FIFO com clock Sistemas Operacionais Algoritmo FIFO com clock No exemplo finalmente na terceira posição encontramos um BR0 ou seja a terceira página é a que deve ser a substituída Quanto as páginas 1 e 2 se elas forem referenciadas novamente o BR correspondente voltará a ser 1 caso contrário elas serão candidatas naturais a serem substituídas Sistemas Operacionais Algoritmo FIFO com clock Mas porque FIFO com clock Porque esquematicamente o algoritmo funciona como se fosse um relógio
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Sistemas Operacionais Gerência de Memória ProfVagner Sistemas Operacionais Gerência de Memória A organização e gerência da memória principal têm sido fatores importantes no projeto de sistemas operacionais Quando falamos em gerência de memória estamos falando da memória primária também denominada RAM Principal ou Real Sistemas Operacionais Gerência de MemóriaMonoprogramação Não confundir Memória Principal Onde residem todos os programas e dados que serão utilizados pelo processador Memória Secundária É um meio permanente mais abundante e de baixo custo para armazenar os dados Sistemas Operacionais Gerência de Memória com Monoprogramação Sistemas Operacionais Gerência de MemóriaMonoprogramação A memória principal é dividida em 2 partes uma para o SO e outra para os programas do usuário O programador não deve ultrapassar o espaço de memória disponível o tamanho da memória principal menos o espaço ocupado pelo SO Sistemas Operacionais Gerência de MemóriaMonoprogramação Sistema Operacional Área para o programa do Usuário Sistemas Operacionais Gerência de MemóriaMonoprogramação O usuário tem total acesso a memória inclusive a área do SO É possível ao usuário destruir o SO Implementação de uma proteção através de um registrador Sistemas Operacionais Gerência de MemóriaMonoprogramação Sistema Operacional Área para o programa do Usuário Registrador Sistemas Operacionais Gerência de Memória com Multiprogramação Sistemas Operacionais Gerência de MemóriaMultiprogramação Como vimos em ambientes monoprogramáveis os problemas eram mais simples Basicamente o SO deveria garantir espaço para o próprio SO e para o programa em uso Sistemas Operacionais Gerência de MemóriaMultiprogramação Porém quando múltiplos processos residem na memória simultaneamente num ambiente multiprogramável os problemas de gerenciamento e proteção são muito mais complexos Isto se dá basicamente porque o sistema deve proteger os processos dos usuários uns dos outros Sistemas Operacionais Gerência de MemóriaMultiprogramação Principais aspectos relativos ao gerenciamento da memória principal Armazenar novos processos em memória sem destruir um processo que já está atualmente na memória Impedir que um processo em execução altere os dados de outro Sistemas Operacionais Gerência de MemóriaMultiprogramação O que fazer se um processo precisa ser executado mas não há espaço na memória Gerenciar a ocupação da memória O que fazer se um processo necessitar de mais memória do que o sistema possui Sistemas Operacionais Gerência de MemóriaMultiprogramação Se um processo que não está na memória tem de ser executado mas a memória está cheia o que deve ser removido da memória Todos estes aspectos estão envolvidos no gerenciamento de memória Sistemas Operacionais Gerência de MemóriaMultiprogramação Uma abordagem inicial para o gerenciamento de memória em sistemas multitarefa envolve a divisão da memória em regiões denominadas partições Sistemas Operacionais Gerência de MemóriaMultiprogramação Neste método o sistema operacional deve ter uma tabela de dados indicando quais partições estão disponíveis Essa tabela é chamada de tabela de partições Sistemas Operacionais Gerência de MemóriaMultiprogramação Regras Um programa pode ocupar somente uma partição Uma partição pode conter somente um processo Sistemas Operacionais Partições Fixas Sistemas Operacionais Partições Fixas O esquema de partições fixas utiliza a memória de maneira pouco eficiente O tamanho da partição faz parte do esquema do sistema operacional A proteção baseiase em dois registradores inferior e superior Sistemas Operacionais Partições Fixas Tamanho estabelecido na fase de inicialização Programas geralmente não ocupam toda a partição O problema da memória desperdiçada é denominado fragmentação Sistemas Operacionais Partições Fixas Exemplo 1 Para um computador de 320 KB de memória serão criadas 4 partições iguais Imagine que surjam os seguintes processos Processo A cnecessidade de 40 KB de memória Processo B cnecessidade de 70 KB de memória Processo C cnecessidade de 68 KB de memória Mostre como será alocados estes processos Sistemas Operacionais Partições Fixas Exemplo 1 continuação Dada a situação anterior o que ocorrerá se um novo processo D surgir necessitando de 95 KB Sistemas Operacionais Partições Fixas Exemplo 2 Para o mesmo computador do exemplo anterior 320 KB RAM serão criadas as seguintes partições 40 KB 40 KB 70 KB 70 KB e 100 KB Como serão alocados os mesmos processos do exemplo anterior Sistemas Operacionais Partições Dinâmicas Sistemas Operacionais Partições Dinâmicas No esquema de partições dinâmicas o tamanho das partições não é definido previamente Em vez disso o sistema operacional as define dinamicamente com base na necessidade dos processos correntes Sistemas Operacionais Partições Dinâmicas O sistema operacional cria uma partição cujo tamanho corresponde exatamente às necessidades de memória do processo Quando o processo termina o sistema então libera a memória Sistemas Operacionais Partições Dinâmicas Exemplo 1 Para o mesmo computador do exercício anterior 320 KB RAM Como serão alocados os mesmos processos do exemplo anterior Processo A 40KB Processo B 70KB Processo C 68KB e Processo D 95KB Sistemas Operacionais Partições Dinâmicas Exemplo 2 Suponha que os processos A e C terminem e as respectivas partições sejam liberadas Agora suponha que surja um processo E com necessidade de 110 KB o que ocorrerá Sistemas Operacionais Partições Dinâmicas Observações Apesar de termos um total livre de 155 KB o processo não poderá ser alocado na memória Neste momento não existe uma partição livre que comporte o processo Sistemas Operacionais Partições Dinâmicas Observações Se estivéssemos falando das partições fixas este processo nunca seria alocado Porém nas partições dinâmicas depois de identificada a fragmentação da memória existem duas soluções para o problema Sistemas Operacionais Partições Dinâmicas Soluções possíveis 1 Reunir os espaços adjacentes Ou seja as áreas contíguas livres são reunidas numa única partição Para esta solução seria necessário esperarmos o término do processo B que liberaria 70 KB Sistemas Operacionais Partições Dinâmicas Soluções possíveis 1 Reunir os espaços adjacentes Desta forma seria possível reunirmos a partição 1 40 KB e a partição 2 70 KB o que totalizaria 110 KB Assim seria possível a alocação do processo E nesta nova partição Sistemas Operacionais Partições Dinâmicas Soluções possíveis 2 Relocar toda a memória Esta solução envolve a reorganização da memória Ocorre assim a relocação de todas as partições ocupadas São eliminando todos os espaços entre elas e criando uma única área livre contígua Sistemas Operacionais Partições Dinâmicas Soluções possíveis 2 Relocar toda a memória Ou seja é como se a memória fosse zerada e os processos existentes fossem novamente alocados Sistemas Operacionais Exercício 1 Temos um computador com memória de 450 KB Surgem os processos A B e C que necessitam respectivamente de 50 100 e 150 KB O esquema utilizado é o gerenciamento por partições fixas de mesmo tamanho 3 partições iguais Sistemas Operacionais Exercício 1 a Como serão alocados estes processos b Haverá fragmentação Especifique c O que vai acontecer se um novo processo D com necessidade de 70 KB surgir Comente d O que vai acontecer se o processo B terminar e um novo processo E com necessidade de 160 KB surgir Comente Sistemas Operacionais Exercício 2 Refaça o exercício anterior para o esquema de gerenciamento por partições fixas Partições criadas 50 75 150 e 175 Kb Sistemas Operacionais Exercício 3 Refaça o exercício para o esquema de gerenciamento por partições dinâmicas Obs para cada item considere o anterior Sistemas Operacionais Estratégias de alocação de partições Sistemas Operacionais Estratégias de alocação de partições É o método utilizado para que um processo seja alocado numa partição já existente Devem principalmente evitar ou diminuir o problema da fragmentação O fator mais importante na escolha da estratégia é o tamanho do programa Basicamente implementamse três estratégias Firstfit Bestfit e Worstfit Sistemas Operacionais 1 Estratégia Firstfit Nesta estratégia a primeira partição livre que comporte o processo deve ser a escolhida Não importa o tamanho da mesma Apesar da simplicidade não há nenhum comprometimento com a eficiência do método Obs este foi o método utilizado nos nossos exemplos e no exercício anterior Sistemas Operacionais 2 Estratégia Bestfit Nesta estratégia a partição escolhida deve ser a menor partição livre que comporte o processo Ou seja aquela que tem o melhor ajuste Neste método o objetivo é que a fragmentação seja a menor possível a partir da escolha da partição mais próxima do tamanho do processo Apesar de inicialmente a fragmentação ser menor conforme os processos forem terminando processos cada vez menores serão alocados aumentando a fragmentação Sistemas Operacionais 3 Estratégia Worstfit Nesta estratégia a partição escolhida deve ser a maior partição livre que comporte o processo Ou seja aquela que tem o pior ajuste Neste método o objetivo é que apesar da fragmentação ser maior inicialmente a medida que os processos forem terminando os espaços deixado sejam maiores evitando assim o problema da Best fit Sistemas Operacionais Exercício 4 Temos livres as seguintes partições 1 2 e 3 com as respectivas áreas de 3 2 e 5 KB Surge um processo A que necessita de 1 KB de memória Como o mesmo será alocado para as estratégias a FirstFit b BestFit c WorstFit Sistemas Operacionais Exercício 5 Refaça os itens para a chegada de um novo processo B com necessidade de 3 KB Sistemas Operacionais Swapping Mesmo com o aumento da eficiência do gerenciamento de memória muitas vezes um processo não podia ser executado por falta de uma partição livre disponível Imagine a seguinte situação temos a memória ocupada conforme descrito a seguir Sistemas Operacionais Swapping Sistemas Operacionais Swapping Surge então um processo F com necessidade de 20 KB e precisa ser executado Para que ele possa ser executado tem que estar alocado na memória o que fazer então se não há partição disponível Sistemas Operacionais Swapping A técnica de swapping veio tentar resolver o problema O swapping é uma técnica aplicada à gerência de memória para programas que esperam por memória livre para serem processados Sistemas Operacionais Swapping Nesta situação o sistema escolhe um programa para deixar a memória Este será levado da memória para o disco swap out O programa que aguardava memória fará o caminho inverso do disco para a memória principal swap in Sistemas Operacionais Swapping No exemplo o SO deve escolher um processo e leválo para o disco para que a partição ocupada por ele fique livre e o processo F possa então ser alocado Mas qual deverá ser o processo escolhido De preferência um processo que não esteja prestes a retornar para a CPU Sistemas Operacionais Swapping Sistemas Operacionais Swapping Apesar da evolução no sistema de partições e da técnica de swapping um problema não podia ser resolvido O que fazer quando um processo maior que a memória disponível precisava ser alocado Sistemas Operacionais Gerência de Memória Virtual Sistemas Operacionais Gerência de Memória Virtual A estratégia denominada Memória virtual é uma técnica de gerenciamento de memória onde as memórias principal RAM e secundária Disco são combinadas permitindo a execução de um determinado processo cujo tamanho exceda o da memória principal disponível Sistemas Operacionais Memória Virtual Memória Principal Memória Secundária Sistemas Operacionais Mas surge uma questão Como sempre vimos o processo em execução dados instruções deve estar alocado na Memória RAM sendo assim como então é possível que parte do processo esteja no disco Sistemas Operacionais Isto é possível pois não é o processo inteiro que precisa estar na memória mas apenas as partes que estão sendo referenciadas Sendo assim o sistema operacional passa a ser responsável por manter na memória as partes do processo efetivamente em uso deixando o resto no disco Sistemas Operacionais Por exemplo um processo de 1 Mb pode rodar numa máquina com 256 Kb de memória escolhendose cuidadosamente os 256 Kb do processo que deverão ser mantidos na memória a cada instante Desta forma os conceitos de memória virtual e multitarefa funcionam muito bem em conjunto Enquanto um programa está esperando que outra parte dele seja carregado na memória ele estará bloqueado e não poderá ser executado e assim o processador será entregue a outro processo Sistemas Operacionais Mas então duas novas questões surgem Como o processador pode acessar endereços maiores que o existente na memória física Como dividir o processo para que partes estejam na memória real e partes no disco Sistemas Operacionais Respondendo a primeira questão Como o processador pode acessar endereços maiores que o existente na memória física Espaço de endereçamento virtual Sistemas Operacionais Espaço de endereçamento virtual Os programas não fazem referência aos endereços físicos endereços reais mas sim aos endereços virtuais No momento da execução o endereço virtual é traduzido para o endereço físico pois o processador acessa apenas posições da memória principal Sistemas Operacionais Espaço de endereçamento virtual Espaço de endereçamento virtual é o nome que se dá ao conjunto de endereços virtuais que os processos podem endereçar Muito próximo da idéia de um vetor referência da posição em que um dado se encontra Sistemas Operacionais Espaço de endereçamento virtual End Físico 500 501 700 720 350 100 502 Vetor Vetor1 Vetor2 Vetor3 Vetor4 Vetor5 Vetor6 Vetor7 Sistemas Operacionais Espaço de endereçamento virtual Quando a memória virtual é utilizada os endereços virtuais não são enviados diretamente para o barramento do computador e sim para um dispositivo chamado Memory Management Unit MMU Este dispositivo é um componente de hardware que mapeia endereços virtuais nos endereços de memória física Sistemas Operacionais Memória Virtual Memória Principal Mapeamento Sistemas Operacionais MMU Memory Management Unit Unidade de gerência de Memória Componente do hardware responsável por implementar os mecanismos usados pelo Sistema Operacional para gerenciar a memória Vai mapear os endereços lógicos gerados pelos processos nos correspondentes endereços físicos que serão enviados para a memória Sistemas Operacionais TLB Translation lookaside buffer Nos sistemas atuais a tradução é realizada por hardware em conjunto com o SO O TLB é uma tabela que funciona como uma memória associativa mantendo os últimos endereços mapeados Objetivo é reduzir o tempo gasto no mapeamento Cada processo passou a implementar a sua própria tabela de mapeamento tabelas exclusivas de mapeamento Sistemas Operacionais Espaço virtual de A Memória Principal Tabela de Mapeamento A Espaço virtual de B Tabela de Mapeamento B Sistemas Operacionais Respondendo a segunda questão Como dividir o processo para que partes estejam na memória real e partes no disco Paginação paging Sistemas Operacionais Paginação paging O espaço de endereçamento virtual é dividido em unidades denominadas páginas As unidades correspondentes na memória física RAM são as molduras de páginas page frames As páginas e as molduras de páginas são sempre do mesmo tamanho Sistemas Operacionais Paginação paging As transferências da memória para o disco e viceversa são sempre feitas em páginas Por exemplo Páginas de 4 KB Com 128 KB de espaço de endereçamento virtual e 64 KB de memória real teremos 32 páginas virtuais 16 molduras de página Sistemas Operacionais Memória Principal Disco Sem memória virtual CPU Tabela de endereços de memória Memória física Antes a tabela apontava para exatamente o endereço físico da memória Com memória virtual 0 1 2 3 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 Tabela de endereços de memória MMU 0 1 2 3 Fonte da imagem do HD httpwwwshutterstockcom Memória física Memória secundária Sistemas Operacionais Paginação paging Quando uma página é referenciada e não está na memória real ocorre um page fault falha de página Memória Principal Sistemas Operacionais Endereço Virtual Tab Páginas Bit validade 0 Tab Páginas Bit validade 1 Memória Principal Page fault Sistemas Operacionais Paginação paging Neste caso a página deverá ser carregada da memória secundária disco para a memória RAM ocorrendo um page in Caso uma página precise ser retirada da Memória acontecerá um page out Sistemas Operacionais Page out Page in Memória Principal Arquivo de Paginação Sistemas Operacionais A técnica de paginação responde a questão anterior porém novas questões surgem Como as páginas dos diversos processos dividirão entre si a memória Na ocorrência do page fault como a página deverá ser trazida para a memória No caso de não existirem frames livres qual página deverá sofrer o page out para que uma nova página sofra o page in Sistemas Operacionais Estas questões são respondidas pelas 3 políticas que normatizam a paginação 1 Política de alocação 2 Política de busca 3 Política de substituição Sistemas Operacionais 1 Política de alocação É a estratégia que define quantos frames um processo terá direito Duas estratégias são possíveis Alocação Fixa Alocação Variável Sistemas Operacionais 1a Política de alocação fixa Nesta estratégia o número de frames que o processo tem direito é fixo Neste caso dois problemas podem acontecer Se o processo receber um número de frames muito pequeno a taxa de paginação pode ser alta Se o processo receber um número muito grande de frames pode ocorrer um desperdício de memória Sistemas Operacionais 1b Política de alocação variável Nesta estratégia o número de frames vai variar de acordo com a ocupação da memória e a taxa de paginação Desta forma o número de frames pode ser adequado a necessidade dos processos Sistemas Operacionais 2 Política de Busca Quando ocorre o page fault a página referenciada deve ser trazida do disco para a memória real A política de busca é a estratégia que define como a página será levada para a memória Duas estratégias são possíveis Busca por demanda Busca antecipada Sistemas Operacionais 2a Política de Busca por Demanda Nesta estratégia somente a página referenciada é carregada do disco para a memória RAM quando ocorre o page fault Esta forma é muito eficiente pois somente a página efetivamente necessária é carregada na memória Sistemas Operacionais 2b Política de Busca Antecipada Nesta estratégia além da página referenciada as páginas próximas também são carregadas na memória principal O objetivo é antecipar as páginas que serão referenciadas num próximo momento com o objetivo de reduzir a taxa de paginação Sistemas Operacionais 2b Política de Busca Antecipada Por outro lado o fato de antecipar páginas na memória RAM pode carregar na memória páginas que nunca serão referenciadas Ocorrerá assim um desperdício de memória Sistemas Operacionais 3 Política de Substituição Imagine a seguinte situação ocorreu o page fault e uma página deve ser carregada na memória RAM porém não há nenhum frame livre O que o sistema operacional deve fazer O S O deve escolher uma página que está na memória para sofrer o page out ou seja deixar a memória RAM e voltar para o disco Sistemas Operacionais 3 Política de Substituição A política de substituição é responsável por definir de qual processo deverá ser o frame liberado Duas estratégias são possíveis Substituição Local Substituição Global Sistemas Operacionais 3a Política de Substituição Local Nesta estratégia o frame a ser liberado deve pertencer ao mesmo processo que gerou o page fault Ou seja o page in e o page out serão do mesmo processo Sistemas Operacionais 3b Política de Substituição Global Nesta estratégia o frame a ser liberado pode pertencer a qualquer processo do sistema Ou seja não há relação entre o processo que sofrerá o page in e o processo que sofrerá page out Sistemas Operacionais Conclusão As 3 políticas respondem as perguntas anteriores 1 Como as páginas dos diversos processos dividirão entre si a memória 2 Na ocorrência do page fault como estas páginas deverão ser trazidas para a memória 3 No caso de não existirem frames livres qual página deverá sofrer o page out para que uma nova página sofra o page in Mas surge uma nova pergunta No caso do pageout qual deve ser exatamente a página a ser liberada Sistemas Operacionais Algoritmos de substituição Como citado no slide anterior no momento em que uma página deve ser carregada porém não há nenhum frame livre uma página deve ser retirada da memória para que um frame seja liberado O algoritmo de substituição é o responsável por determinar qual deve ser a página a sair da memória Sistemas Operacionais Algoritmo Ótimo Este é um algoritmo hipotético ou seja existe apenas no campo das hipóteses Serve apenas como um referencial para os demais algoritmos E o que seria então um algoritmo considerado ótimo Sistemas Operacionais Algoritmo Ótimo Seria o algoritmo que conseguisse prever exatamente a página que não será mais utilizada sendo assim a página ideal para ser substituída Por que isto seria ótimo Sistemas Operacionais Algoritmo Ótimo Porque se o algoritmo retirar uma página que será referenciada a página vai gerar um page fault necessitará do page in e aumentará o tráfego entre memória e disco Sendo assim o algoritmo que conseguisse evitar com precisão esta situação poderia ser considerado ótimo Sistemas Operacionais Algoritmo FIFO First In First Out Nesta estratégia a página que foi alocada primeiro deve ser a escolhida Ou seja a página mais antiga na memória é a que sofrerá o page out O algoritmo FIFO parte do princípio que a página mais antiga é aquela que não será mais utilizada Sistemas Operacionais Algoritmo FIFO First In First Out Apesar de inicialmente parecer um raciocínio correto isto não é o que ocorre na prática Sendo assim apesar do algoritmo FIFO ser de fácil implementação o algoritmo deixa a desejar Sistemas Operacionais Algoritmo LFU Least Frequently Used O algoritmo LFU tem por objetivo escolher a página menos referenciada ou seja a página que o processo acessou menos vezes Para tornar isto possível o algoritmo associa a cada página um contador de referências A cada referência na página o contador correspondente é incrementado Sistemas Operacionais Algoritmo LFU Least Frequently Used No momento da substituição o algoritmo escolhe a página cujo contador é o menor entre todos ou seja a página que foi menos vezes referenciada Novamente podemos achar esta estratégia muito boa afinal a página menos referenciada poderá ser aquela que não será mais utilizada correto Sistemas Operacionais Algoritmo LFU Least Frequently Used Mas novamente há uma falha evidente imagine que uma página acabou de ser alocada na memória quando ocorrer um novo page fault o que acontecerá Por ter sido referenciada uma só vez a página que acabou de ser alocada será a escolhida e deixará a memória Sistemas Operacionais Algoritmo LRU Least Recently Used O algoritmo LRU escolhe a página que está mais tempo sem ser referenciada O raciocínio é simples a página que está mais tempo sem ser referenciada é porque não está mais sendo utilizada Portanto é a candidata ideal para sofrer o page out Sistemas Operacionais Algoritmo LRU Least Recently Used O algoritmo mantém a fila ordenada em ordem cronológica por referência e a cada nova referência a fila deve ser reordenada Este é o único ponto negativo do algoritmo pois gera um grande overhead pois as páginas precisam ser constantemente atualizadas no momento do último acesso Sistemas Operacionais Algoritmo NRU Not Recently Used Este algoritmo também busca escolher a página que não está mais sendo referenciada Porém ao invés de trabalhar com uma fila constantemente reordenada como vimos anteriormente este algoritmo trabalha com um BR Bit de referência para cada página alocada na memória Sistemas Operacionais Algoritmo NRU Not Recently Used O BR Bit de referência tem em seus valores os seguintes significados 0 Página não referenciada 1 Página referenciada Sistemas Operacionais Algoritmo NRU Not Recently Used Estes valores são atribuídos da seguinte forma Quando uma página é referenciada o valor 1 é atribuído para o seu BR correspondente De tempos em tempos todos os BRs Bits de referência são zerados Sistemas Operacionais Algoritmo NRU Not Recently Used Sendo assim no momento da substituição o algoritmo deverá escolher entre as páginas que estão com BR0 Também pode ser utilizado o BM Bit de modificação que tem em seus valores os seguintes significados 0 Página não modificada 1 Página modificada Sistemas Operacionais Algoritmo NRU Not Recently Used O objetivo do uso do BM é determinar se a página que deixará a memória deverá ser salva no disco ou não Se a página teve alguma modificação BM1 ela necessariamente deverá ser salva caso contrário haverá perda de integridade Sistemas Operacionais Algoritmo NRU Not Recently Used Porém se no momento da substituição BM0 isto significa que a página não foi alterada e portanto não precisa ser salva Desta forma uma operação de IO desnecessária Por que salvar uma página que não modificada não será realizada melhorando a performance Sistemas Operacionais Exercícios Um processo com necessidade de 80 KB de memória está com as 5 primeiras páginas carregadas na memória real A Quantas páginas estarão na memória secundária sabendose que o frame tem 4 KB B O que acontecerá se o programa endereçar uma instrução da página 6 Sistemas Operacionais C Qual página deverá ser substituída para os métodos FIFO LFU LRU NRU Considere que as páginas foram referenciadas na ordem 1 2 3 4 4 5 1 2 3 1 2 e 3 Para o NRU considere BR0 após 7 referências de páginas Sistemas Operacionais Algoritmo FIFO com buffer Neste algoritmo ao invés de uma só fila para determinar qual página deve ser substituída temos duas LPA Lista de páginas alocadas LPL Lista de páginas livres Sistemas Operacionais Algoritmo FIFO com buffer Como o próprio nome diz a metodologia de trabalho é FIFO Porém a página mais antiga da LPA ao invés de ser a página a ser substituída é inserida no final da LPL Sistemas Operacionais Algoritmo FIFO com buffer Sistemas Operacionais Algoritmo FIFO com buffer A página a ser substituída deverá ser a página que estiver no topo da LPL Inicialmente isto poderá parecer um FIFO com duas filas porém se uma página que estiver na LPL for referenciada ela volta ao final da LPA Desta forma a página que estiver no topo da LPL é porque realmente não foi mais referenciada Sistemas Operacionais Algoritmo FIFO com buffer Sistemas Operacionais Algoritmo FIFO com clock Neste algoritmo existe uma só fila para determinar qual página deve ser substituída Cada página contém um BR O ponteiro apontará inicialmente para a página mais antiga como um FIFO tradicional Sistemas Operacionais Algoritmo FIFO com clock Mas apesar do ponteiro inicialmente apontar para a página mais antiga ela somente será substituída se o BR0 Caso o BR1 o algoritmo troca o BR para zero e vai verificar a próxima página da fila Assim sendo o ponteiro vai circular pela fila Sistemas Operacionais Algoritmo FIFO com clock Sistemas Operacionais Algoritmo FIFO com clock Sistemas Operacionais Algoritmo FIFO com clock Sistemas Operacionais Algoritmo FIFO com clock No exemplo finalmente na terceira posição encontramos um BR0 ou seja a terceira página é a que deve ser a substituída Quanto as páginas 1 e 2 se elas forem referenciadas novamente o BR correspondente voltará a ser 1 caso contrário elas serão candidatas naturais a serem substituídas Sistemas Operacionais Algoritmo FIFO com clock Mas porque FIFO com clock Porque esquematicamente o algoritmo funciona como se fosse um relógio