7/21/2019 Cap04-Algoritmos Paginas (1)

1/18

1Pearson Education Sistemas Operacionais Modernos 2 Edio

Sistemas Operacionais

FATEC-PB

Professor: Gustavo Wagner

gugawaggmai!"com

7/21/2019 Cap04-Algoritmos Paginas (1)

2/18

#Pearson Education Sistemas Operacionais Modernos 2 Edio

Gerenciamento de Memria

Captulo 4

4.1 Gerenciamento !sico de memria4.2 "roca de processos

4.# Memria $irtual

4.4 %l&oritmos de sustituio de p!&inas

4.' (uest)es de pro*eto para sistemas de pa&inao4.+ (uest)es de implementao

4., Se&mentao

7/21/2019 Cap04-Algoritmos Paginas (1)

3/18

$Pearson Education Sistemas Operacionais Modernos 2 Edio

%l&oritmos de Sustituio de

-!&inas

% /alta de p!&ina /ora uma escol0a ual p!&ina de$e ser remo$ida

alocao de espao para a p!&ina a ser tra3idapara a memria

% p!&ina modi/icada de$e primeiro ser sal$a se no ti$er sido modi/icada apenas soreposta

Mel0or no escol0er uma p!&ina ue est!sendo muito usada pro$a$elmente precisar! ser tra3ida de $olta lo&o

7/21/2019 Cap04-Algoritmos Paginas (1)

4/18

%Pearson Education Sistemas Operacionais Modernos 2 Edio

A!goritmo &e Su'stitui()o &eP*ginas timo

+ Se uma p*gina foi acessa&a ,* 1instru(.es/ e outra ,* 0/ a primeira &eve

ser su'stitu&a numa fa!ta &e p*gina2+ Pro'!ema: n)o ,* como o SO sa'er 3uan&o

uma p*gina ser* novamente acessa&a2

+ E se a pr45ima instru()o for para acessar aprimeira p*gina cita&a acima6+ A!goritmo impossve! &e ser imp!ementa&o2

7/21/2019 Cap04-Algoritmos Paginas (1)

5/18

0Pearson Education Sistemas Operacionais Modernos 2 Edio

O %l&oritmo de Sustituio de -!&ina

No Usada Recentemente (NUR)

Cada p!&ina tem os its 5e/erenciada 657 eModi/icada 6M7

8its so colocados em 1 uando a p!&ina

re/erenciada e modi/icada

%s p!&inas so classi/icadas9 pelo SO Classe :; no re/erenciada9 no modi/icada

Classe 1; no re/erenciada9 modi/icada

Classe 2; re/erenciada9 no modi/icada Classe #; re/erenciada9 modi/icada

a ue no este*a $a3ia

7/21/2019 Cap04-Algoritmos Paginas (1)

6/18

7Pearson Education Sistemas Operacionais Modernos 2 Edio

O %l&oritmo de Sustituio de -!&ina

No Usada Recentemente (NUR)

+ 8 me!,or remover uma p*gina mo&ifica&a/mas 3ue n)o foi referencia&a2

+ A!goritmo f*ci! &e enten&er e imp!ementar2+ 9esempen,o n)o 4timo/ mas a&e3ua&o2

7/21/2019 Cap04-Algoritmos Paginas (1)

7/18;Pearson Education Sistemas Operacionais Modernos 2 Edio

%l&oritmo de Sustituio de -!&ina

Primeira a Entrar, Primeira a Sair

?ma&ine retirar um produto de um supermercado9

dado ue um no$o c0e&ou9 e no tem mais

espao nas prateleiras@

O supermercado mantm uma lista de todos osprodutos9 por ordem de c0e&ada@

Ae$eBse retirar o produto estocado a mais tempo@

Se o produto retirado /or cera para i&ode9 o@ Mas e se /or aDcar

Situao an!lo&a a ?O@

7/21/2019 Cap04-Algoritmos Paginas (1)

8/18

7/21/2019 Cap04-Algoritmos Paginas (1)

9/18=Pearson Education Sistemas Operacionais Modernos 2 Edio

%l&oritmo de Sustituio de -!&ina

Segunda Chance (SC)

+ >o&ifica()o &e F?FO2+ 9esta ve@/ se o 'it for 1/ a p*gina ser* poupa&a/

o 'it co!oca&o em e a p*gina vai para o fina!&a fi!a2+ Se n)o/ a p*gina ser* removi&a2+ 9*-se c,ance s p*ginas 3ue est)o sen&o

uti!i@a&as/ mesmo sen&o antigas2+ Se to&as as p*ginas forem referencia&as/ o

a!goritmo &egenera-se para F?FO2

7/21/2019 Cap04-Algoritmos Paginas (1)

10/181Pearson Education Sistemas Operacionais Modernos 2 Edio

%l&oritmo de Sustituio de -!&ina

Segunda Chance (SC)

Operao do al&oritmo segunda chancea7 lista de p!&inas em ordem ?O

7 estado da lista em situao de /alta de p!&ina no instante 2:9 com o it Rda p!&inaAem 1 6nDmeros representam instantes decarre&amento das p!&inas na memria7

7/21/2019 Cap04-Algoritmos Paginas (1)

11/1811Pearson Education Sistemas Operacionais Modernos 2 Edio

%l&oritmo de Sustituio

de -!&ina Relgio

+ 9ifere-se &o Segun&a C,ance apenas naimp!ementa()o2

+ O SC &esnecessariamente inefica@/ * 3ueco!oca constantemente no fina! &a fi!a &ep*ginas2

+ O e!4gio cria simp!esmente uma !istacircu!ar2

7/21/2019 Cap04-Algoritmos Paginas (1)

12/181#Pearson Education Sistemas Operacionais Modernos 2 Edio

%l&oritmo de Sustituio

de -!&ina Relgio

7/21/2019 Cap04-Algoritmos Paginas (1)

13/181$Pearson Education Sistemas Operacionais Modernos 2 Edio

Menos 5ecentemente

=sada 6M5=7

%pro>imao do desempen0o terico do

al&oritmo timo@

%ssume ue p!&inas usadas recentementelo&o sero usadas no$amente

retira da memria p!&ina ue 0! mais tempo no

usada

?mplementao por SH muito onerosa9 poistemBse ue atuali3ar uma lista encadeada@

7/21/2019 Cap04-Algoritmos Paginas (1)

14/181%Pearson Education Sistemas Operacionais Modernos 2 Edio

Menos 5ecentemente

=sada 6M5=7

=ma lista encadeada de p!&inas de$e ser mantida

p!&ina mais recentemente usada no incio da lista9 menos

usada no /inal da lista

atuali3ao da lista I cada re/erFncia I memria

?mplementao por JH;

Contador de '4 its9 ue incrementado a cada instruo

MantemBse contador em cada entrada da taela de p!&ina escol0e p!&ina com contador de menor $alor

7/21/2019 Cap04-Algoritmos Paginas (1)

15/1810Pearson Education Sistemas Operacionais Modernos 2 Edio

Menos 5ecentemente

=sada 6M5=7

+ Outra maneira em DW:Para uma m*3uina com n mo!&uras/ gera-se

matri@ &e n 5 n/ inicia!mente com to&os osva!ores 2

Sempre 3ue a mo!&ura for referencia&a/ o DWmarcar* os 'its &a !in,a com 1/ e to&os os 'its&a co!una com 2

7/21/2019 Cap04-Algoritmos Paginas (1)

16/1817Pearson Education Sistemas Operacionais Modernos 2 Edio

Menos 5ecentemente

=sada 6M5=7

M5= usando uma matri3 p!&inas re/erenciadas na ordem:91929#92919:9#929#

7/21/2019 Cap04-Algoritmos Paginas (1)

17/181;Pearson Education Sistemas Operacionais Modernos 2 Edio

Simulao do M5= em So/tKare

+ Em'ora imp!ementa(.es anteriores seamrea!i@*veis/ n)o ,* m*3uinas com o DW

&escrito2+ sa-se o a!goritmo &o enve!,ecimento:

Co!oca-se o 'it no 'it mais es3uer&a &o

conta&or/ a ca&a tic29es!oca-se &ireita to&os os 'its

7/21/2019 Cap04-Algoritmos Paginas (1)

18/181