SOII_Materia_Parte08

Prévia do material em texto

SISTEMA OPERACIONAL II – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 1 
 
47) 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. 
 
48) MECANISMO PARA REDUZIR O USO DO DISCO NA PAGINAÇÃO SOB DEMANDA 
 
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 – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 2 
 
 
 
Figura 1 
 
 
Figura 2 
 
 
Figura 3 
 
 
SISTEMA OPERACIONAL II – PARTE 8 
 
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 – PARTE 8 
 
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. 
 
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. 
 
- Algoritmos para escolha das páginas vítimas, ou seja, páginas que são escolhidas para 
serem salvas em disco: 
 
 FIFO : A primeira página que entra na fila é a primeira a sair 
 Ótimo : Escolhe a página que não será usada em futuro próximo. Não é usado na 
prática; 
 LRU (Least Recently Used): É usado na prática. É escolhida a página usada mais 
recentemente para ir para o disco. Respeita o princípio da localidade 
 2ª chance: 
 
 
1º) ALGORITMO – FIFO (FIRST IN FIRST OUT) 
 
SISTEMA OPERACIONAL II – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 5 
 
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 paginada fila sempre. 
 
 
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 logica 7 é 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) 
 
SISTEMA OPERACIONAL II – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 6 
 
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 
 
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. 
 
SISTEMA OPERACIONAL II – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 7 
 
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. 
 
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. 
 
O LRU é um algoritmo que não é fácil de implementar, porque, o LRU significa uma ordem de 
quem vai usar por mais tempo, isso é difícil de manter, pois, qualquer execução faz com que a página 
seja a página mais recentemente usada, então qualquer coisa que rode muda a ordem de uso da 
página. Existe uma alternativa de verificar o tempo de uso das páginas que não é exatamente o LRU, 
é uma forma de aproximar a idéia do uso recente, mantendo a ordem exata de como a página foi 
usada. 
 
Como funciona? 
A tabela de páginas tem um campo a mais que é o “acessado”, toda vez que uma página lógica é 
acessada o hardware vai ao campo e muda o bit, por exemplo, se a página 8 for usada o hardware vai 
ao campo acessado e desliga o bit. 
 
Qual a idéia básica do uso do LRU? 
De tempos em tempos uma rotina é executada e zera todos os bits de todas as páginas. Digamos que 
falte memória e o SO tenha que escolher uma página vítima, que tipo de página que o SO vai 
escolher? A página que está com o bit 0 em acessado ou a página com bit 1 em acessado? A página 
que está com bit 0, pois a página com bit 0 não foi acessada recentemente. Sabe-se, com isso, quem 
teve acesso recente, e quem não teve acesso recente. Então, escolhe uma das páginas que não teve 
acesso recente. 
 
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. 
 
SISTEMA OPERACIONAL II – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 8 
 
 
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. 
 
 
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. 
 
SISTEMA OPERACIONAL II – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 9 
 
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 
 
 
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 usada somente pelo SO no 
campo Realmente Valido que vão conter o valor 1. No campo Acessado ele coloca o valor 0. 
SISTEMA OPERACIONAL II – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 10 
 
 
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) 
 
Problema: Tem muita página e se zerar todos os bits de tempo em tempo terá desperdício de tempo. 
 
Tem outro mecanismo que é mais eficiente: Para começar estão todos zerados então, tem um 
ponteiro que vai passando e só anda quando tem falta de página. O ponteiro vai zerando os que não 
estiverem zerados. 
 
Divide páginas em páginas que tiveram acessos recentes e páginas que não tiveram recentes. Se a 
página não foi executada desde a última vez que o ponteiro passou por ela é porque não teve uso 
recente. Se a página não foi acessada não teve uso recente. 
 
Escolhe um tempo de passagem e considera recente se não passou nesse tempo. Assim, se for um 
processo antigo então pode ser vítima. 
 
O que é acesso recente? 
De tempos em tempos o algoritmo zera tudo, então o acesso recente é o tempo que ele zerou desde a 
última vez que ele zerou todo mundo. É o momento que o ponteiro passou pela página pela última 
vez, se não teve uso nesse intervalo de tempo é por que não teve uso recente. 
 
 
 
 
 
 
6º) ALGORITMO do relógio de 2 ponteiros: 
 
Cada ponteiro tem uma função diferente, nessa versão existe um ponteiro que desce zerando o bit de 
validade. Digamos agora que vamos escolher uma página vítima o algoritmo vai rodando, a página 
pode ser vítima? Não, pois o byte de validade é 1(1ª linha da tabela de página), então o algoritmo vai 
rodando e desce o ponteiro, a linha de baixo pode ser vítima? Sim, então essa vira vítima. O tempo 
recente é o intervalo de tempo de passagem entre os ponteiros, com isso consegue-se medir o que é 
recente, quanto mais distantes estejam os ponteiros, mais perto fica do que é recente. 
 
 
 
 
agora 
A vítima que o ponteiro 
percorre 
O ponteiro esta passando 
pela página 
recente 
Passou o ponteiro que 
procura a vítima 
SISTEMA OPERACIONAL II – PARTE 8 
 
Elaborado por Luciana SA Amancio Página 11 
 
 
 
 
Existe uma questão agora que é a seguinte: 
Onde eu posso escolher a página vítima? 
Qual o conjunto de páginas que podem ser vítimas? 
Alocação de páginas físicas: global (escolha de página vítima de qualquer processo) e local(escolha 
de página vítima de um único processo) 
 
Difícil implementação: Local: Quantidade de páginas físicas que serão reservadas a cada processo. 
Cada processo terá um nº x de páginas físicas reservada a ele, se um processo gera falta de página, 
incluirá a página vítima entre as páginas físicas reservadas a este processo. A maior dificuldade é 
saber qual número de páginas físicas que devem ser reservadas. Como o SO sabe quanto de páginas 
tem que reservar para cada processo, usando o princípio da localidade? O número de páginas que o 
processo esta usando é chamado de working – set, que é constante em um certo intervalo de tempo, 
baseado no princípio da localidade. A idéia é definir com o nº de páginas reservadas ao processo, o 
tamanho é o tamanho do working –set reservado a esse processo de forma que enquanto o processo 
estiver usando aquelas páginas, não haverá falta de páginas. Existe um mecanismo que verifica se 
está sendo reservado o nº de páginas maior ou menor que o working-set daquele processo. Esse 
mecanismo observa o nº de falta de páginas que o processo gera. Se uns processos geram poucas 
falta de páginas é porque está reservado para este processo um nº de páginas que é maior que o 
tamanho do working –set, pois a falta de página só vai acontecer quando o working-set mudar. Por 
exemplo, uma rotina A, com m working –set, são as páginas locais a rotina e a página da área de 
código da rotina, se esse processo da rotina A , chama um processo da rotina B, poucas páginas vão 
ser usadas, as páginas usadas são as de código e as de pilha da rotina B, então mudou o working set. 
 
Quando o working – set muda? Quando a rotina for chamada. 
 
Percorre o ponteiro que o 
bit é acessado 
recente