Algoritmo Do Relogio

SistemasOperacionais

GerenciamentodeMemriaVirtual AlgoritmosdePaginaoNortonTrevisanRoman MarceloMorandini JUeyama

ApostilabaseadanostrabalhosdeKalinkaCasteloBranco,AntnioCarlos Sementille,LucianaA.F.Martimianoenastransparnciasfornecidasno sitedecompradolivro"SistemasOperacionaisModernos"1

AlgoritmosdeTrocadePgina

timo; NRU; FIFO; SegundaChance; Relgio; LRU; Workingset; WSClock;

Veremoscadaumem detalhes

2


Algoritmotimo

Cadapginamarcadacomonmerode instruesqueseroexecutadasantesquea pginasejareferenciada

Retiradamemriaapginaquetemmenoschancede serreferenciada(maiornmerodeinstruesfaltantes)

Praticamenteimpossveldesesaber; Impraticvel; Usadoemsimulaesparacomparaocom outrosalgoritmos;3


AlgoritmoNotRecentlyUsedPage Replacement(NRU)

ParaauxiliaroS.O.acoletarestatsticasdepgina deuso:

02bitsassociadosacadapginaR(eferenciada)e M(odificada)

Classe0(00)noreferenciada,nomodificada; Classe1(01)noreferenciada,modificada; Classe2(10)referenciada,nomodificada; Classe3(11)referenciada,modificada;

Referenciadalidaouescrita Modificadaescrita4



ParaauxiliaroS.O.acoletarestatsticasdepgina deuso:

ReMsoatualizadosacadarefernciamemria;

Armazenadosemcadaentradadatabeladepgina Seuvalordeterminadopelohardware

Quandoumprocessoiniciado,ambosReMso 0paratodassuaspginas

Periodicamente,obitRlimpoparadiferenciaras pginasquenoforamreferenciadasrecentemente;

Acadainterrupoderelgio;5



ObitMnolimpo,poisoS.O.precisasaberse deveescreverapginanodisco Quandoocorreumapagefault:

Removeumapginaaleatoriamente,escolhendodentre asclassesmaisinferioresbits00,01,10,11 Fcildeentender,eficienteparaimplementarefornece bomdesempenho;6

Vantagens:


AlgoritmoFirstinFirstoutPageReplacement (FIFO)

SOmantmumafiladaspginascorrentesna memria;

Apginanoinciodafilaamaisantigaeapginano finalamaisnova; Quandoocorreumpagefault

Apginadoincioremovida Anovainseridaaofinaldafila

Simples,maspodeserineficiente,poisumapgina queestemusoconstantepodeserretirada; Poucoutilizado;7


AlgoritmodaSegundaChance

FIFO+bitR; InspecionaobitRdapginamaisvelha

Sefor0,elavelhaenofoiusadarecentemente trocada Sefor1,obitfeito0

Apginacolocadanofinaldafila Seutempodecargamodificado,fazendoparecerquerecm chegounamemria(recebeumasegundachance) Abuscacontinua

8



Ex:

Ocorrepagefaultnotempo20eRA=0

Aremovido,eonovoelementoinseridoaofinal9



Ex:

Ocorrepagefaultnotempo20eRA=1

RA=0agora

RepeteaoperaocomB

SeRB=0,troca Seno,passaaofinaldafila,comRB=0,everificaseC

10


AlgoritmodoRelgio

MelhoriaaoSegundaChance:

Listacircularcomponteiroapontandoparaapginamais antiga,naformadeumrelgio Acabeaapontaparaapgina maisantiga

11


AlgoritmodoRelgio

Quandoocorreumpagefault:

Inspecionaseacabeadalista

RC=0

12


AlgoritmodoRelgio


Inspecionaseacabeadalista SeR=0:

Substituiseapginadacabeapelanovapgina

RC=0

13


AlgoritmodoRelgio



Substituiseapginadacabeapelanovapgina Avanaseacabeaemumaposio

RC=0

14


AlgoritmodoRelgio



Avanaseacabeaemumaposio RepeteseoprocessoatencontrarpginacomR=0

RC=1;RD=0

RC=0;RD=015


AlgoritmodoRelgio



Avanaseacabeaemumaposio RepeteseoprocessoatencontrarpginacomR=0 Agecomonocasoanterior(R=0)

RC=1;RD=0

RC=0;RD=0

RC=0;RD=1

16


AlgoritmoLeastRecentlyUsedPage Replacement(LRU)

Idia:

Pginasqueforammuitousadasnasltimasinstrues seroprovavelmenteusadasnovamentenasprximas Trocaapginaquepermaneceuemdesusopelomaior tempo Devesemanterlistaencadeadacomtodasaspginas queestonamemria,comasmaisrecentemente utilizadasnoincioeasmenosutilizadasnofinal; Alistadeveseratualizadaacadarefernciadamemria;17

Altocusto



Podeserimplementadotantoporhardwarequanto porsoftware:

Hardware:MMUdevesuportaraimplementaoLRU;

Contadoremhardware(64bits),incrementadoautomaticamente apscadainstruo TabeladepginasarmazenaovalordessecontadorCem cadaentrada Apscadarefernciamemria,ovaloratualdeC armazenadonaentradacorrespondente(pgina)natabela Emumpagefault,oS.O.examinatodasasentradasnatabela, paraencontraracommenorC18



Implementao:

Hardware(Alternativo):

Seocomputadortemnmolduras,ohardwaedeLRUmantm umamatrizdennbits,inicialmentezero

Quandoumamoldurak(ex,k=0)referenciada,ohardwarefaz todososbitsdalinhakserem1,eosda colunakserem0

19



Implementao:


Aqualquermomento,alinhacomomenorvalorbinrioa menosrecentementeusada.Alinhaseguinteasegunda menosrecentementeusada,eassimpordiante. Ex:

Pginas:0123220



Implementao:


Ex:

Pginas:01232

Pginas:1032321




SoftwareNFU(Notfrequentlyused):

Paracadapginaexisteumcontador,iniciadocomzero Acadainterrupodoclock,oSOvarretodasaspginasda memria Paracadapgina,adicionaobitR(residncia)aocontador Emumpagefault,escolheapginacomomenorcontador Problema:Comoessealgoritmonoseesquecedenada, pginasfrequentementeacessadasemumaporopequenado cdigo,masquenomaisseroacessadas,nosero candidatas22




SoftwareAging:

SoluoaoproblemadoalgoritmoNFU Almdesaberquantasvezesapginafoireferenciada,tambm controlaquandoelafoireferenciada Primeiro,oscontadoressodeslocadosdireitaemumbit.S entoobitRadicionado,squeaobitmaisdaesquerda Tambmacadainterrupodoclock Emumpagefault,apginacomomenorcontadorremovida

23

Aging

Notequeaps8clocksumapginanoreferenciadatemseucontador zerado.Quantomaistempoficarsemserreferenciada,maiszeros suaesquerdater,emenorserseucontador

24


AlgoritmoWorkingSet(WS):

Paginaopordemandapginassocarregadas namemriasomentequandosonecessrias; PrpaginaoWorkingset

Conjuntodepginasqueumprocessoestefetivamente utilizando(referenciando)emumdeterminadotempot;

w(k,t)WS P1 P3 P4 P7 P8 P4 t1 t2 tempo25



Objetivoprincipal:reduzirafaltadepginas

Umprocessosexecutadoquandotodasaspginas necessriasnotempotestocarregadasnamemria;

Atento,gerarpagefaults

Aidiadeterminaroworkingsetdecadaprocessoe certificarsedetlonamemriaantesderodaro processoModelodeConjuntodeTrabalhooupr paginao Conjuntoconsistindo,emumdadoinstantet,detodasas pginasusadaspelaskrefernciasmaisrecentes memria26

Workingsetw(k,t)



Oworkingsetvarialentamentecomotempo

Podemosestimaronmerodepginasnecessrias quandooprogramatrazidododiscocombaseemseu workingsetdequandofoiinterrompido. Prpaginaoconsisteemcarregaressaspginasantes derodarnovamenteoprocesso OSOprecisamanterregistrodequepginasestono workingset. Quandoocorrerumpagefault,encontreumapginafora doworkingsetearemova,casonohajamaisnenhuma molduralivre27

Implementao:



Implementao:

Contaraskrefernciasmaisrecentescustoso Parasimplificaroworkingsetpodeservistocomoo conjuntodepginasqueoprocessoreferencioudurante osltimostsegundosdesuaexecuo

Contaotempoindividualdoprocesso,descontando escalonamentoseutempovirtualcorrente

UtilizabitReotempoderelgio(tempovirtual)daltima vezqueapginafoireferenciada;

28



Algoritmo:

Pressupostos:

OhardwaredefineosbitsReM Emcadaciclodoclock,obitdereferncialimpo Otempodoworkingsetseestendeporvriosciclosdoclock

Emcadapagefault,atabeladepginasinteira buscada

medidaquecadaentradaprocessada,examineR

Se1,escrevaotempovirtualcorrentenocampoTempodo ltimoUso(TLU),indicandoqueapginaestavaemusono instantedapagefault,ouseja,estavanoworkingsetno candidata29



Algoritmo:

Emcadapagefault,atabeladepginasinteira buscada

medidaquecadaentradaprocessada,examineR SeR=0,apginanofoireferenciadanocicloatual,epodeser umacandidata Nessecaso,sesuaidadeformaiorqueointervalotdo workingset,elanoestnele,epodeserremovida Abuscacontinuaatualizandoasdemaisentradas Se,contudo,aidadeformenorquet,apginapoupada. Contudo,apginacommaioridademarcada

Senenhumcandidatoforencontrado(todasaspginasestono workingset),substituaapginamaisvelha,dentreascomR=030



31


AlgoritmoWSClock:

Clock+WorkingSet Amplamenteusado,devidosuasimplicidadee performance Utilizalistacirculardepginas

Inicialmentevazia medidaquemaispginassocarregadas,entramna lista,formandoumanel Cadaentradacontmotempodeltimouso,almdos bitsReM32


AlgoritmoWSClock:

Mnomostrado nafigura

Funcionamento:

Acadapagefault,apginada cabeaexaminadaprimeiro SeR=1

Apginafoiusadaduranteociclode clockcorrentenocandidataa remoo FazR=0eavanaacabea prximapgina,repetindooalgoritmo paraestapgina

33


AlgoritmoWSClock:

Funcionamento:

SeR=0

Seaidadeformaiorqueotamanhodo workingsetteapginaestiverlimpa (M=0)noestnoworkingseteuma cpiavlidaexistenodisco

Apginasubstituda Acabeadalistaavana

34


AlgoritmoWSClock:

Funcionamento:

SeR=0

Se,contudo,apginaestiversujanopossuicpiavlidano disco

Agendaumaescritaaodisco,evitandotrocadeprocesso Avanaacabeadalista,prosseguindodapginaseguinte

35


AlgoritmoWSClock:

Funcionamento:

SeR=0

Se,contudo,apginaestiversujanopossuicpiavlidano disco

Agendaumaescritaaodisco,evitandotrocadeprocesso Avanaacabeadalista,prosseguindodapginaseguinte

36


AlgoritmoWSClock:

Seacabeaderumavoltacompletanalistasem substituir:

Epelomenosumaescritanodiscofoiagendada

Acabeacontinuasemovendo,embuscadeumapginalimpa Emalgummomentoaescritaagendadaserexecutada, marcandoapginacomolimpa Todasaspginasestonoworkingset Nafaltadeinformaoadicional,substituaqualquerpgina limpa Senenhumapginalimpaexistir,escolhaqualqueroutraea escrevanodisco

Enenhumaescritafoiagendada

37


Algoritmosde substituiolocal:

WorkingSet; WSClock;

Algoritmosde substituio local/global:

timo; NRU; FIFO; SegundaChance; LRU; Relgio;38

Oconceitodeworking setseaplicasomente aumnicoprocesso nohworkingset paraamquinacomo umtodo

ImplementaodaPaginao

Ondecolocaraspginasnodisco,quando retiradasdamemria?

Asoluomaissimplesterumapartioespecial deswap

SoluodoUnixeLinux Nopossuiumsistemadearquivosnormal

Quandoosistemainicia,apartioestvazia Representadanamemriacomoumanicaentrada contendosuaorigemetamanho medidaemqueprocessossoiniciados,oSOreservaum pedaodareadeswapdotamanhodoprocesso

Quandoterminam,oespaoliberado Areadetrocagerenciadacomoumalistadeespaos disponveis;

39



Asoluomaissimplesterumapartioespecial deswap

Halgoritmosmelhores,masquenoserodiscutidos

Associadoacadaprocessoestoendereono discodesuareadeswap

Mantidonatabeladeprocessos Clculodoendereoparaescreverumapgina:

Adicioneoendereodoinciodapgina(seuvalornoendereo virtual)aoinciodareadeswapassociadaaoprocesso

40



Problema:antesdeumprocessoiniciar,areade swapdeveserinicializada

PossibilidadeAAssimqueoprocessocriado,ele copiadotodoparasuareadetrocanodisco,sendo carregadoparamemriaquandonecessrio;

Alternativamente,podemoscopilotodoparaamemria principal(espelhamento) Problema:processospodemaumentardetamanhoaps iniciarem(pilhaedados) Soluo:reservarreasdetrocadiferentesparatextodo programa,dadosepilha,permitindoqueelasconsistamdemais deumbloconodisco41



Problema:antesdeum processoiniciar,area deswapdeveser inicializada

PossibilidadeA

Bastasaberoendereodo inciodareadeswapdo processo Aspginasso espelhadasnodisco readetroca(swap) esttica

42



Problema:antesdeumprocessoiniciar,areade swapdeveserinicializada

PossibilidadeBNadaalocadoantecipadamente.

Espaoalocadoemdiscoquandoapginaforenviadaparal edesalocadoquandovoltaparaamemria Assim,processonamemriaRAMnoficaamarradoauma reaespecfica; Desvantagem:precisamos,namemria,deumendereode discoparacadapgina.

Devehaverumatabelaemcadaprocessodizendoonde cadapginaestnodisco(seestiverl) Antes,bastavasaberondeoprocessoestavanodisco43



Problema:antesdeum processoiniciar,area deswapdeveser inicializada

PossibilidadeB

Almdoendereodo inciodareadeswapdo processo,temosquesaber ondeestapginadentro desseendereo(seu deslocamento) readetrocadinmica44

Documents

Algoritmo Do Relogio