SOII_Aula008_15012013

Prévia do material em texto

SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 1 
 
RESUMO AULA PASSADA 
 
Paginação sob demanda (“Memória Virtual”) 
 
Memória física cheia e é necessário mais memória: uma página é retirada da memória e fica invalida 
na Tabela de Paginas do Processo. Se for usada novamente o HW gera interrupção e o SO no 
tratamento traz a pagina de volta para a memória física. 
 
O processo fica bloqueado durante o tratamento da interrupção. 
 
Cálculo da perda de desempenho da paginação sob demanda. 
 
Mecanismo para reduzir o uso do disco na paginação sob demanda 
 
1º) Quando uma paginação de código é escolhida como vitima não é necessário salvá-la. 
 
2º) Quando o SO escolhe como vitima uma pagina que já foi vitima anteriormente e não foi 
alterada desde então não é necessário salvá-la. 
 
AULA DE HOJE - MECANISMO PARA REDUZIR O USO DO DISCO NA PAGINAÇÃO 
SOB DEMANDA 
 
3°) Carregamento das páginas logicas de código “sob demanda” 
 
O SO faz uma coisa diferente para evitar o uso do disco. Conforme mostra a Figura 1 o processo tem 
um arquivo executável que está no disco. As paginas de código do processo não são todas carregadas 
na memoria física quando o processo começa. As páginas de código não vão para memória física. 
Logo conforme mostra a Figura 2 as páginas de códigos não são válidas na Tabela de Páginas do 
processo. 
 
Como o código não está na memória física quando este processo entra em execução e vai chamar o 
programa principal na primeira rotina do processo fará um salto para uma das paginas do código. 
Geralmente a pagina logica 0. Ela estará invalida. Então o HW gera uma interrupção. O SO vai tratar 
essa interrupção e não abortará o processo. 
 
O que está na página logica 0 é diferente da página logica 6 conforme mostra a Figura 2 da Tabela cde 
Página do Processo. A página logica 0 pertence a área de código. A pagina logica 6 não. Mas como o 
SO sabe disso? Ele consulta a Tabela Mapa de Memória da Figura 6. 
 
A interrupção foi gerada simplesmente porque o SO não carregou ainda a pagina logica 0. Não é uma 
pagina logica que está invalida de verdade ela existe só que não foi carregada para memoria ainda. 
Nesse momento que o SO trata essa interrupção ele coloca na memoria física a pagina logica 0 e 
mapeia na Tabela de Pagina do Processo. Nesse somente um pagina do código esta na memoria as 
outras duas paginas não estão no disco. E o processo é executado. 
 
Se o processo chamar alguma sub rotina que está na pagina logica do código que encontra-se no disco 
a mesma coisa vai acontecer. Vai gerar uma interrupção e o SO ao tratar essa interrupção percebe que 
precisa traz para memória a pagina logica que está no disco. Conforme mostra a Figura 1. E preenche a 
tabela de pagina do processo conforme mostra a Figura 2. 
 
SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 2 
 
 
 
 
Figura 1 
 
 
Figura 2 
 
 
Figura 3 
 
 
SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 3 
 
 
Figura 4 
 
 
 Figura 5 Figura 6 
 
O SO carrega as paginas de código para memoria física aos poucos. Isto é feito quando o processo 
precisa utilizar a pagina pela primeira vez. Dai o nome de carregamento “sob demanda”. O código só é 
carregado quando ele é demandado. Quando tem um sub rotina que precisa dele. É esse mecanismo 
que dá o nome a paginação com o uso do disco que é paginação sob demanda. 
 
Qual é a vantagem desse mecanismo? Temos duas vantagens. Primeiro o fato de não carregar o código 
para memoria pode fazer com que o processo seja útil para o usuário de forma mais rápida. Por 
exemplo, digamos que com as duas paginas carregadas o usuário consiga utilizar o processo 
normalmente. Não tem nenhum rotina sendo chamada para pagina de código que esta no disco. Então 
o usuário consegue utilizar o processo sem estar todo o processo carregado na memoria física. 
 
Qual o beneficio disso? O usuário consegue utilizar o processo mais rapidamente. Isso é importante 
para processo grandes. Por exemplo, o Word. Tem muita coisa que o código dele tem que não é 
utilizado em toda execução do Word. Se ele for ler todo o código do disco para memoria gastará um 
tempo razoável. Mas, como este mecanismo ele não fará isto. O código será carregado aos poucos para 
memoria. Assim para começar a usar será mais rápido e durante a execução do processo do Word será 
um pouco devagar, pois o código está sendo carregado pelo SO para memoria. 
 
Portanto, essa é a primeira vantagem a economia para começar a utilizar o processo. 
 
SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 4 
 
A segunda vantagem e a mais importante é o menor gasto de memoria física. Durante um tempo 
importante utilizou menos memoria porque não carregou todo o código do processo para memoria 
ainda. É importante porque existe processo que nunca utilizarão todas as suas páginas de código. O 
Word é um exemplo disso. Não utiliza todas as funcionalidades (todo o código) de uma só vez, mas 
sim de acordo com a solicitação do usuário. 
 
4º) Adiantar o salvamento no disco das paginas vitimas (pool de paginas vitimas) 
 
No momento que a memoria física está quase cheia. O SO préescolhe as paginas vitimas. O SO só 
escolhe pagina vitima a principio quando a memoria física encheu. O que acontece é que muitas vezes 
tem que liberar espaço na memoria física pra trazer um pagina logica que está no disco. Nesse caso ele 
adianta uma coisa que ele faria no futuro que é adiantar a pagina vitima. 
 
Ao invés de salvar a pagina vitima na hora que precisa de memoria física de verdade. O SO adianta 
esse salvamento no momento que o disco está sem uso. Assim não terá prejuízo, pois o disco não está 
sendo utilizado. Quando o processo precisar de memória não será preciso escolher e salvar uma 
pagina vitima em disco, pois isto já foi feito e tem memoria física livre. 
 
Com este mecanismo a memoria física nunca fica cheia, pois quando está quase cheia o SO escolher 
uma pagina vitima e salva em disco quando o disco não está sendo utilizado. Esse mecanismo também 
é chamado de pool de paginas vitimas. O SO sempre mantem um numero de paginas vitimas para 
serem salvas em disco. 
 
Portanto, esses são os quatro mecanismos para evitar o uso do disco. 
 
ALGORITMOS DE ESCOLHA DE PÁGINAS VITIMAS 
 
A seguir temos a sequencia temporal de paginas logicas que um processo acessou: 
 
 
 
Como o SO escolhe as paginas que vão sair da memória física (paginas vitimas) para colocar as que o 
processo precisa utilizar? Através dos algoritmos a seguir. Utilizaremos no exemplo uma memoria 
física com 3 paginas. E o processo contém 8 paginas logicas. 
 
1º) ALGORITMO – FIFO (FIRST IN FIRST OUT) 
 
Conforme mostra a Figura 7. Dentro da pagina física colocaremos o numero da pagina logica que 
precisa ser colocada na memoria física. Inicialmente até a terceira pagina logica conseguimos colocar 
na memoria física sem problema de falta de pagina de memoria física. Ao tentar colocar a quarta 
pagina logica que é a pagina logica 2 na memoria física não conseguiremos, pois ela está cheia. 
 
O SO escolherá uma pagina vitima para salvar em disco e libar espaço na memoria física para colocar 
a pagina logica 2. Com este algoritmo coloca em uma fila as paginas logicas que foram para memoria 
física e escolhe como vitima primeira pagina da fila sempre. 
 
SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 5 
 
 
Figura 7 
 
Fila de Pagina logica: 701230423 
 
Em 2 a pagina logica 7 é colocada na memoria, em 3 a pagina logica 0 é colocada na memoria, em 4 a 
pagina logica 1 é colocada na memória. Para colocar a pagina logica 2 na memoria é preciso tirar um 
página logica. Então a página logica7 é retirada colocada em uma fila e a pagina logica 2 é colocada 
no lugar dele. 
 
Agora a memoria física tem três paginas validas que são as paginas logicas 2, 0 e 1. A próxima pagina 
a ser acessada é a pagina logica 0 que já está na memoria física é um pagina válida que está com o bit 
valido ligado. Não precisa fazer nada. 
 
A pagina logica utilizada a pagina logica 3 que não está na memoria física é uma pagina logica 
inválida na tabela de paginas e o que o HW vai fazer vai gerar uma interrupção o que o SO vai fazer 
vai tratar a interrupção colocando na memoria física a pagina logica 3. Só que como a memoria física 
está cheia o SO vai escolher a pagina vitima entre as paginas 0, 2 e 1. 
 
Em 5 a pagina logica 0 já está na memória. 
 
Neste algoritmo temos 15 interrupções que é igual 15 Page Fault (Falta de Página) 
 
2º) ALGORITMO ÓTIMO (ALGORITMO TEÓRICO) 
 
Nesse algoritmo escolha-se a pagina vitima que não terá uso logo em seguida. A pagina vitima será a 
que terá uso mais distante no futuro. 
 
Figura 8 
SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 6 
 
 
Em 4 a memória está cheia e sai o próximo mais longe e a pagina 2 entra no lugar dele. 
 
Esse algoritmo é o que gera menos interrupção. Temos 9 interrupções que é igual 9 Page Fault (Falta 
de Página). 
 
O problema dele é que tem conhecer o Futuro, mas não tem como saber o futuro. Logo ele é um 
algoritmo somente teórico serve apenas como base de comparação. 
 
3º) ALGORITMO LEAST RECENTLY USED (LRU) 
 
Esse algoritmo utiliza a ideia do algoritmo ótimo, mas ao invés de olhar para o futuro olha para o 
passado, ou seja, escolhe a pagina que teve o uso mais distante no passado. 
 
 
Figura 9 
 
Nesse algoritmo o mais passado é igual ao menos recente. A pagina vitima é a pagina menos usada 
recentemente. 
 
Em 4 a memoria está cheia e a pagina logica 2 precisa ser colocada na memória, mas uma pagina deve 
ser retirada da memoria. No LRU a pagina vitima é a pagina mais distante usada no passado (atrás, 
anteriormente). Então escolhe a pagina vitima olhando qual das paginas logicas 7, 0 e 1 foi utilizada 
mais distante no passado. Nesse caso a pagina vitima será a 7. Então a pagina logica 2 entra no lugar 
da pagina logica 7. 
 
Em 5 a pagina logica 0 já está na memoria. Em 6 temos que colocar a pagina logica 3 na memoria 
física. Analisando as paginas logicas 2, 0 e 1 o algoritmo escolhe a pagina logica 1, pois é a que tem o 
uso mais distante. Então a pagina logica 3 entra no lugar no pagina logica 1. 
 
A próxima pagina é a 0 que já está na memoria. Em 7 precisamos colocar a pagina logica 4 na 
memoria física. O SO escolhe uma vitima entre as paginas logicas 2, 0 e 3. A pagina logica 2 é a 
vitima ela sai e entra a 4. 
 
Em 8 a pagina logica 2 tem que entrar na memoria física. Acabamos que tirar a pagina logica 2 da 
memoria física. Nesse caso o algoritmo LRU não fez uma boa escolha. O algoritmo continua a ser 
aplicado até que todas paginas logicas da sequencia do exemplo tenham sido colocadas na memoria. 
 
SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 7 
 
O problema é o seguinte o algoritmo que escolhe a pagina vitima tem saber qual foi a sequencia exata 
de paginas acessadas pelo processo, mas isso não é facilmente conhecido porque o SO, por exemplo, 
não sabe quais paginas foram para memoria física ele só fica sabendo das coisas quando está em 
execução. 
 
Nesse exemplo durante a colocação das três primeiras paginas logicas na memoria física o SO não 
entrou em execução, pois nenhuma interrupção aconteceu. O HW sabe quem foi que executou. O 
problema é que o HW não marca as paginas que ele acessou. 
 
A sequencia exata embora ela tenha ocorrido ninguém fica sabendo no futuro. Embora o algoritmo 
LRU seja possível ser implementado na prática hoje em dia ele não é implementado porque não tem 
disponível a informação para o SO. 
 
4º) ALGORITMO NOT RECENTLY USED (NRU) 
 
Tipo de algoritmo usado atualmente é aquele que escolhe uma pagina qualquer que não teve uso 
recente. O nome desse algoritmo é o Not Recently Used. Isto dá para ser feito. Mas como é feito? 
Com ajuda do HW preenchendo um bit a mais que é colocado na Tabela de Páginas do Processo. O 
nome desse bit é Acessado (ou usado). Ele é ligado pelo HW quando a pagina logica tem qualquer tipo 
de acesso. Conforme mostra a Figura 10. 
 
 
Figura 10 
 
O Bit Acessado (ou usado) só diz se teve ou não acesso a esta pagina logica, mas não diz se foi 
recente. Então a pagina está na memoria ela sofreu acesso o HW vai nesse campo e altera para 1. 
Desse jeito consultando esse campo o SO consegue descobrir quais paginas foram acessadas. No 
entanto, isso não resolveu o problema. 
 
Como o SO sabe que o acesso a pagina foi recente? Para isto tem que implementar um mecanismo 
para auxiliar o SO que de tempos em tempos ele vai no bit Acesso é coloque 0. Desse jeito ele 
consegue saber qual a pagina logica que teve o uso mais recente, ou seja, é pagina logica com o bit 
Acessado igual 1 ainda. Isto quer dizer que esta pagina foi acessada depois da ultima vez que o SO 
zerou o campo bit Acessado. 
 
5º) ALGORITMO DA 2ª CHANCE 
 
Esse algoritmo é parecido com o algoritmo FIFO só que dá uma segunda chance para a pagina caso a 
pagina já tenha sido acessada. O que é a segunda chance? É colocar a pagina no final da fila de novo. 
Mas na hora que ela vai para o fim da fila o Bit Acessado dela é zerado. 
 
SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 8 
 
 
Figura 11 
 
Fila de Pagina logica: 7 0 1 7 0 1 2 0 3 ... 
 
Aplicando o algoritmo da 2ª Chance na sequencia de paginas logicas utilizadas pelo processo temos o 
seguinte: a pagina logica 7 é colocada na memoria física e o bit Acessado dela é alterado pelo HW para 
1. Colocamos a pagina logica 0 na memoria e o bit Acessado dela igual a 1. Depois colocamos a 
pagina logica 1 e o bit Acessado dela igual a 1. A memoria encheu precisamos tirar uma pagina logica 
da memoria para salvar em disco e colocar a próxima pagina logica que é a 2. 
 
A pagina vitima é a primeira pagina logica que foi para memória física. Nessa hora é avaliado se a 
pagina 7 terá uma segunda chance. Nesse caso terá, pois o bit Acessado dela está igual a 1. Ela é 
colocada no final da fila novamente e seu o bit Acessado é alterado para 0. No lugar dela é colocada a 
pagina logica 2. 
 
Esse procedimento é repetido até que todas as paginas logicas da sequencia apresentada tenham ido 
para memoria física na ordem apresentada. Lembrando que a pagina vitima só terá segunda chance se 
o bit Acessado dela estiver igual a 1 quando ela foi escolhida como pagina vitima. 
 
Os números ao lado da Figura 11 representam o Bits Acessado da tabela de paginas. 
 
Este algoritmo é utilizado no Windows. Ele segue a lógica do algoritmo NRU. 
 
Se a pagina logica estiver com o bit Acessado igual a 0 ela será a pagina vitima. Se estiver com esse 
bit igual 1 não será a pagina vitima e terá a segunda chance. 
 
O Windows mantem uma fila com a ordem que as paginas vieram da memoria. No caso do Linux é 
igual ao numero da pagina a pagina seguinte é igual ao numero da pagina que se tem e seu nome é 
Algoritmo do Relógio. 
 
O HW que não tem o Bit Acessado o SO simula o Bit Acessado para auxilia-lo a descobrir quando a 
pagina logica foi acessada pela ultima vez. Conforme mostram as Figuras 12 e 13. 
 
Figura 12 
SISTEMA OPERACIONAL II – AULA 8 - 15/01/2013 
 
Elaborado por Luciana SA Amancio Página 9 
 
 
 
Figura 13 
 
Digamos que estejam validas as paginas 0, 1, 2 e 4. O SO simula o bit Acessado colocando uma 
informação falsa na tabela de paginas do processo. Ele coloca Valido igual 0 nas paginas logicas que 
estavam validas. O SO coloca a informação correta na tabela auxiliar que usadasomente pelo SO no 
campo Realmente Valido que vão conter o valor 1. No campo Acessado ele coloca o valor 0. 
 
Quando o processo precisar utilizar, por exemplo, a pagina logica 4 o HW vai gerar uma interrupção. 
O SO vai tratar essa interrupção e verifique na tabela auxiliar o valor verdadeiro do campo bit válido 
da Tabela de pagina do processo. Logo, o SO não aborta o processo. E no tratamento dessa interrupção 
o SO liga o bit Acessado e coloca o valor correto no campo Válido na pagina logica 4 da Tabela de 
Pagina do Processo. Conforme mostram as Figuras 12 e 13. 
 
Através do campo Acessado na tabela auxiliar do processo o SO consegue saber qual pagina logica foi 
acessada recentemente e dá uma 2ª Chance se o bit Acessado for igual a 1. 
 
Quando ocorre a 2ª chance o SO: 
 
1) Zera o bit acessado na tabela auxiliar 
2) Zera o bit válido na tabela principal (Tabela de paginas sem o bit acessado)