Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pe sq ui sa em M em ór ia S ec un dá ria ∗ Ú lti m a al te ra çã o: 31 de A go st o de 20 10 ∗ Tr an sp ar ên ci as el ab or ad as po rW ag ne rM ei ra Jr ,F lá vi a Pe lig ri ne lli R ib ei ro ,I sr ae lG ue rr a, N ív io Z iv ia ni e C ha rl es O rn el as A lm ei da Pr oj et o de A lg or itm os – C ap .1 In tr od uç ão 1 C on te úd o do C ap ítu lo 6. 1 M od el o de C om pu ta çã o pa ra M em ór ia S ec un dá ria 6. 1. 1 M em ór ia V irt ua l 6. 1. 2 Im pl em en ta çã o de um S is te m a de P ag in aç ão 6. 2 A ce ss o S eq ue nc ia lI nd ex ad o 6. 2. 1 D is co s Ó pt ic os de A pe na s- Le itu ra 6. 3 Á rv or es de Pe sq ui sa 6. 3. 1 Á rv or es B 6. 3. 2 Á rv or es B ∗ 6. 3. 3 A ce ss o C on co rr en te em Á rv or es B ∗ 6. 3. 4 C on si de ra çõ es P rá tic as Pr oj et o de A lg or itm os – C ap .1 In tr od uç ão 2 In tr od uç ão • Pe sq ui sa em m em ór ia se cu nd ár ia : ar qu iv os co nt ém m ai s re gi st ro s do qu e a m em ór ia in te rn a po de ar m az en ar . • C us to pa ra ac es sa ru m re gi st ro é al gu m as or de ns de gr an de za m ai or do qu e o cu st o de pr oc es sa m en to na m em ór ia pr im ár ia . • M ed id a de co m pl ex id ad e: cu st o de tra sf er ir da do s en tre a m em ór ia pr in ci pa l e se cu nd ár ia (m in im iz ar o nú m er o de tra ns fe rê nc ia s) . • M em ór ia s se cu nd ár ia s: ap en as um re gi st ro po de se ra ce ss ad o em um da do m om en to (a ce ss o se qü en ci al ). • M em ór ia s pr im ár ia s: ac es so a qu al qu er re gi st ro de um ar qu iv o a um cu st o un ifo rm e (a ce ss o di re to ). • O as pe ct o si st em a de co m pu ta çã o é im po rt an te . • A s ca ra ct er ís tic as da ar qu ite tu ra e do si st em a op er ac io na ld a m áq ui na to rn am os m ét od os de pe sq ui sa de pe nd en te s de pa râ m et ro s qu e af et am se us de se m pe nh os . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1 3 M od el o de C om pu ta çã o pa ra M em ór ia S ec un dá ri a - M em ór ia V ir tu al • N or m al m en te im pl em en ta do co m o um a fu nç ão do si st em a op er ac io na l. • M od el o de ar m az en am en to em do is ní ve is ,d ev id o à ne ce ss id ad e de gr an de s qu an tid ad es de m em ór ia e o al to cu st o da m em ór ia pr in ci pa l. • U so de um a pe qu en a qu an tid ad e de m em ór ia pr in ci pa le um a gr an de qu an tid ad e de m em ór ia se cu nd ár ia . • P ro gr am ad or po de en de re ça rg ra nd es qu an tid ad es de da do s, de ix an do pa ra o si st em a a re sp on sa bi lid ad e de tra sf er ir o da do da m em ór ia se cu nd ár ia pa ra a pr in ci pa l. • B oa es tra té gi a pa ra al go rit m os co m pe qu en a lo ca lid ad e de re fe rê nc ia . • O rg an iz aç ão do flu xo en tre a m em ór ia pr in ci pa le se cu nd ár ia é ex tre m am en te im po rt an te . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 1 4 M em ór ia V ir tu al • O rg an iz aç ão de flu xo → tra ns fo rm ar o en de re ço us ad o pe lo pr og ra m ad or na lo ca liz aç ão fís ic a de m em ór ia co rr es po nd en te . • E sp aç o de E nd er eç am en to → en de re ço s us ad os pe lo pr og ra m ad or . • E sp aç o de M em ór ia → lo ca liz aç õe s de m em ór ia no co m pu ta do r. • O es pa ço de en de re ça m en to N e o es pa ço de m em ór ia M po de m se r vi st os co m o um m ap ea m en to de en de re ço s do tip o: f : N → M . • O m ap ea m en to pe rm ite ao pr og ra m ad or us ar um es pa ço de en de re ça m en to qu e po de se rm ai or qu e o es pa ço de m em ór ia pr im ár ia di sp on ív el . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 1 5 M em ór ia V ir tu al : S is te m a de Pa gi na çã o • O es pa ço de en de re ça m en to é di vi di do em pá gi na s de ta m an ho ig ua l, em ge ra l, m úl tip lo s de 51 2 K by te s. • A m em ór ia pr in ci pa lé di vi di da em m ol du ra s de pá gi na s de ta m an ho ig ua l. • A s m ol du ra s de pá gi na s co nt êm al gu m as pá gi na s at iv as en qu an to o re st an te da s pá gi na s es tã o re si de nt es em m em ór ia se cu nd ár ia (p ág in as in at iv as ). • O m ec an is m o po ss ui du as fu nç õe s: 1. M ap ea m en to de en de re ço s → de te rm in ar qu al pá gi na um pr og ra m a es tá en de re ça nd o, en co nt ra ra m ol du ra ,s e ex is tir ,q ue co nt en ha a pá gi na . 2. Tr an sf er ên ci a de pá gi na s → tra ns fe rir pá gi na s da m em ór ia se cu nd ár ia pa ra a m em ór ia pr im ár ia e tra ns fe rí- la s de vo lta pa ra a m em ór ia se cu nd ár ia qu an do nã o es tã o m ai s se nd o ut ili za da s. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 1 6 M em ór ia V ir tu al : S is te m a de Pa gi na çã o • E nd er eç am en to da pá gi na → um a pa rt e do s bi ts é in te rp re ta da co m o um nú m er o de pá gi na e a ou tra pa rt e co m o o nú m er o do by te de nt ro da pá gi na (o ffs et ). • M ap ea m en to de en de re ço s → re al iz ad o at ra vé s de um a Ta be la de P ág in as . – a p -é si m a en tra da co nt ém a lo ca liz aç ão p � da M ol du ra de P ág in a co nt en do a pá gi na nú m er o p de sd e qu e es te ja na m em ór ia pr in ci pa l. • O m ap ea m en to de en de re ço s é: f (e ) = f (p ,b ) = p � + b, on de e é o en de re ço do pr og ra m a, p é o nú m er o da pá gi na e b o nú m er o do by te . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 1 7 M em ór ia V ir tu al : M ap ea m en to de E nd er eç os p � p �+ b Ta be la _d e_ Pá gi na s Pá gi na p N ◦ da pá gi na N ◦ do by te E nd er eç o de pr og ra m a p b p � = ni l→ pá gi na nã o pr es en te na m em ór ia � � � � � Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 1 8 M em ór ia V ir tu al : R ep os iç ão de P ág in as • S e nã o ho uv er um a m ol du ra de pá gi na va zi a → um a pá gi na de ve rá se rr em ov id a da m em ór ia pr in ci pa l. • Id ea l→ re m ov er a pá gi na qu e nã o se rá re fe re nc ia da pe lo pe río do de te m po m ai s lo ng o no fu tu ro . – te nt am os in fe rir o fu tu ro a pa rt ir do co m po rt am en to pa ss ad o. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 1 9 M em ór ia V ir tu al : Po lít ic as de R ep os iç ão de P ág in as • M en os R ec en te m en te U til iz ad a (L R U ): – um do s al go rit m os m ai s ut ili za do s, – re m ov e a pá gi na m en os re ce nt em en te ut ili za da , – pa rt e do pr in cí pi o qu e o co m po rt am en to fu tu ro de ve se gu ir o pa ss ad o re ce nt e. • M en os Fr eq üe nt em en te U til iz ad a (L FU ): – re m ov e a pá gi na m en os fe qü en te m en te ut ili za da , –in co nv en ie nt e: um a pá gi na re ce nt em en te tra zi da da m em ór ia se cu nd ár ia te m um ba ix o nú m er o de ac es so s e po de se rr em ov id a. • O rd em de C he ga da (F IF O ): – re m ov e a pá gi na qu e es tá re si de nt e há m ai s te m po , – al go rit m o m ai s si m pl es e ba ra to de m an te r, – de sv an ta ge m : ig no ra o fa to de qu e a pá gi na m ai s an tig a po de se ra m ai s re fe re nc ia da . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 1 10 M em ór ia V ir tu al : Po lít ic a LR U Fi m � In íc io � P ág in a p � � � � . . .. � �� � �� • To da ve z qu e um a pá - gi na é ut ili za da el a é re m ov id a pa ra o fim da fil a. • A pá gi na qu e es tá no in íc io da fil a é a pá gi na LR U . • Q ua nd o um a no va pá - gi na é tra zi da da m e- m ór ia se cu nd ár ia el a de ve se r co lo ca da na m ol du ra qu e co nt ém a pá gi na LR U . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 2 11 M em ór ia V ir tu al : E st ru tu ra de D ad os #d ef in e TA M A N H O D A PA G IN A 51 2 #d ef in e IT E N S P O R PA G IN A 64 /∗ Ta m an ho da Pa gi na / Ta m an ho do Ite m ∗ / ty pe de f st ru ct Ti po R eg is to { Ti po C ha ve C ha ve ; /∗ ou tr os co m po ne nt es ∗ / } T ip oR eg is tr o ; ty pe de f st ru ct Ti po E nd er ec o { lo ng p ; ch ar b ; } Ti po E nd er ec o ; ty pe de f st ru ct Ti po Ite m { T ip oR eg is tr o R eg ; Ti po E nd er ec o Es q, D ir ; } Ti po Ite m ; ty pe de f Ti po Ite m Ti po P ag in a [I te ns P or P ag in a ]; Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 2 12 M em ór ia V ir tu al • E m ca so s em qu e pr ec is am os m an ip ul ar m ai s de um ar qu iv o ao m es m o te m po : – A ta be la de pá gi na s pa ra ca da ar qu iv o po de se rd ec la ra da se pa ra da m en te . – A fil a de m ol du ra s é ún ic a → ca da m ol du ra de ve te ri nd ic ad o o ar qu iv o a qu e se re fe re aq ue la pá gi na . ty pe de f st ru ct Ti po P ag in a { ch ar ti p o ; /∗ ar m az en a o co di go do ti po :0 ,1 ,2 ∗ / un io n { Ti po P ag in aA Pa ; Ti po P ag in aB Pb ; Ti po P ag in aC Pc ; }P ; } Ti po P ag in a ; Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 2 13 M em ór ia V ir tu al • P ro ce di m en to s pa ra co m un ic aç ão co m o si st em a de pa gi na çã o: – O bt em R eg is tro → to rn a di sp on ív el um re gi st ro . – E sc re ve R eg is tro → pe rm ite cr ia ro u al te ra ro co nt eú do de um re gi st ro . – D es ca rr eg aP ag in as → va rr e a fil a de m ol du ra s pa ra at ua liz ar na m em ór ia se cu nd ár ia to da s as pá gi na s qu e te nh am si do m od ifi ca da s. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 1. 2 14 M em ór ia V ir tu al -T ra ns fo rm aç ão do E nd er eç o V ir tu al pa ra R ea l P 2 D et er m in a en de re ço re al P4 R ec up er a pá gi na da m em ór ia se cu nd ár ia A 1 T ab el a de pá gi na s A 3 M em ór ia se cu nd ár ia Pr og ra m a U su ár io A 2 Fi la de m ol du ra s P5 G ra va pá gi na na m em ór ia se cu nd ár ia P1 C on su lta ta be la de pá gi na s P3 D et er m in a m ol du ra pa ra pá gi na � � � � � � � � � � � � � p p � p � p � p Pá gi na p � p � p P ág in a p p � p � p p � Pá gi na p � • Q ua dr ad os → re su lta - do s de pr oc es so s ou ar - qu iv os . • R et ân gu lo s → pr oc es - so s tra ns fo rm ad or es de in fo rm aç ão . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 2 15 A ce ss o S eq üe nc ia lI nd ex ad o • U til iz a o pr in cí pi o da pe sq ui sa se qü en ci al → ca da re gi st ro é lid o se qü en ci al m en te at é en co nt ra ru m a ch av e m ai or ou ig ua la ch av e de pe sq ui sa . • P ro vi dê nc ia s ne ce ss ár ia s pa ra au m en ta ra efi ci ên ci a: – o ar qu iv o de ve se rm an tid o or de na do pe lo ca m po ch av e do re gi st ro , – um ar qu iv o de ín di ce s co nt en do pa re s de va lo re s < x ,p > de ve se r cr ia do ,o nd e x re pr es en ta um a ch av e e p re pr es en ta o en de re ço da pá gi na na qu al o pr im ei ro re gi st ro co nt ém a ch av e x . – E st ru tu ra de um ar qu iv o se qü en ci al in de xa do pa ra um co nj un to de 15 re gi st ro s: 3 14 25 41 1 2 3 4 3 5 7 11 1 14 17 20 21 2 25 29 32 36 3 41 44 48 4 Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 2 16 A ce ss o S eq üe nc ia lI nd ex ad o: D is co M ag né tic o • D iv id id o em cí rc ul os co nc ên tr ic os (tr ilh as ). • C ili nd ro → to da s as tr ilh as ve rt ic al m en te al in ha da s e qu e po ss ue m o m es m o di âm et ro . • La tê nc ia ro ta ci on al → te m po ne ce ss ár io pa ra qu e o in íc io do bl oc o co nt en do o re gi st ro a se rl id o pa ss e pe la ca be ça de le itu ra /g ra va çã o. • Te m po de bu sc a (s ee k tim e) → te m po ne ce ss ár io pa ra qu e o m ec an is m o de ac es so de sl oq ue de um a tr ilh a pa ra ou tra (m ai or pa rt e do cu st o pa ra ac es sa rd ad os ). • A ce ss o se qü en ci al in de xa do = ac es so in de xa do + or ga ni za çã o se qü en ci al , • A pr ov ei ta nd o ca ra ct er ís tic as do di sc o m ag né tic o e pr oc ur an do m in im iz ar o nú m er o de de sl oc am en to s do m ec an is m o de ac es so → es qu em a de ín di ce s de ci lin dr os e de pá gi na s. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 2 17 A ce ss o S eq üe nc ia lI nd ex ad o: D is co s Ó tic os de A pe na s- Le itu ra (C D -R O M ) • G ra nd e ca pa ci da de de ar m az en am en to (6 00 M B )e ba ix o cu st o. • In fo rm aç ão ar m az en ad a é es tá tic a. • A efi ci ên ci a na re cu pe ra çã o do s da do s é af et ad a pe la lo ca liz aç ão do s da do s no di sc o e pe la se qü ên ci a co m qu e sã o ac es sa do s. • Ve lo ci da de lin ea rc on st an te → tr ilh as po ss ue m ca pa ci da de va riá ve le te m po de la tê nc ia ro ta ci on al va ria de tr ilh a pa ra tr ilh a. • A tr ilh a te m fo rm a de um a es pi ra lc on tín ua . • Te m po de bu sc a: ac es so a tr ilh as m ai s di st an te s de m an da m ai s te m po qu e no di sc o m ag né tic o. H á ne ce ss id ad e de de sl oc am en to do m ec an is m o de ac es so e m ud an ça s na ro ta çã o do di sc o. • Va rr ed ur a es tá tic a: ac es sa co nj un to de tr ilh as vi zi nh as se m de sl oc ar m ec an is m o de le itu ra . • E st ru tu ra se qü en ci al im pl em en ta da m an te nd o- se um ín di ce de ci lin dr os na m em ór ia pr in ci pa l. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 18 Á rv or es B • Á rv or es n -á ria s: m ai s de um regi st ro po rn od o. • E m um a ár vo re B de or de m m : – pá gi na ra iz : 1 e 2m re gi st ro s. – de m ai s pá gi na s: no m ín im o m re gi st ro s e m + 1 de sc en de nt es e no m áx im o 2m re gi st ro s e 2m + 1 de sc en de nt es . – pá gi na s fo lh as : ap ar ec em to da s no m es m o ní ve l. • R eg is tro s em or de m cr es ce nt e da es qu er da pa ra a di re ita . • E xt en sã o na tu ra ld a ár vo re bi ná ria de pe sq ui sa . • Á rv or e B de or de m m = 2 co m trê s ní ve is : � � � � � � � � �� � � � � � � 30 � � � � � � � � 10 20 � � �� � � � � � 40 50 � � �� � � � � � � � � �� � � �� � � �� � � �� � � �� � � � 3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55 Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 19 Á rv or es B -T A D D ic io ná ri o • E st ru tu ra de D ad os : ty pe de f lo ng Ti po C ha ve ; ty pe de f st ru ct T ip oR eg is tr o { Ti po C ha ve C ha ve ; /∗ ou tr os co m po ne nt es ∗ / } T ip oR eg is tr o ; ty pe de f st ru ct Ti po P ag in a∗ Ti po A po nt ad or ; ty pe de f st ru ct Ti po P ag in a { sh or t n ; T ip oR eg is tr o r[ M M ]; Ti po A po nt ad or p [M M + 1 ]; } Ti po P ag in a ; Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 20 Á rv or es B -T A D D ic io ná ri o • O pe ra çõ es : – In ic ia liz a vo id In ic ia li za (T ip oA po nt ad or ∗ D ic io na ri o ) { ∗ D ic io na ri o = N U LL ; } – Pe sq ui sa – In se re – R em ov e Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 21 Á rv or es B -P es qu is a vo id P es qu is a( T ip oR eg is tr o ∗ x , Ti po A po nt ad or Ap ) { lo ng i = 1 ; if (A p = = N U LL ) { p ri n tf (" T ip oR eg is tr o na o es ta pr es en te na ar vo re \n ") ; re tu rn ; } w hi le (i < Ap − >n & & x− >C ha ve > Ap − >r [i − 1] .C ha ve ) i+ +; if (x − >C ha ve = = Ap − >r [i − 1] .C ha ve ) { ∗ x = Ap − >r [i − 1] ; re tu rn ; } if (x − >C ha ve < Ap − >r [i − 1] .C ha ve ) P es qu is a( x , Ap − >p [i − 1] ); el se P es qu is a( x , Ap − >p [i ]) ; } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 22 Á rv or es B -I ns er çã o 1. Lo ca liz ar a pá gi na ap ro pr ia da ao nd e o re gi sr o de ve se ri ns er id o. 2. S e o re gi st ro a se ri ns er id o en co nt ra um a pá gi na co m m en os de 2m re gi st ro s, o pr oc es so de in se rç ão fic a lim ita do à pá gi na . 3. S e o re gi st ro a se ri ns er id o en co nt ra um a pá gi na ch ei a, é cr ia da um a no va pá gi na ,n o ca so da pá gi na pa ie st ar ch ei a o pr oc es so de di vi sã o se pr op ag a. E xe m pl o: In se rin do o re gi st ro co m ch av e 14 . � � � � 1 10 � � �� � � � � � � � � � � � � � � 2 3 3 4 8 9 16 20 25 29 (a ) � � � � 1 10 20 � � �� � � � � � � � � � � � � � � � � � � 2 3 4 3 4 8 9 14 16 25 29 (b ) Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 23 Á rv or es B -I ns er çã o E xe m pl o de in se rç ão da s ch av es : 20 ,1 0, 40 ,5 0, 30 ,5 5, 3, 11 ,4 ,2 8, 36 , 33 ,5 2, 17 ,2 5, 13 ,4 5, 9, 43 ,8 e 48 � � � � (a ) 20 � � � � (b ) 30 � � � � � � � � �� � � � 10 20 40 50 � � � � (c ) 10 20 30 40 � � � � � �� � � �� � � � � � � � � � � � � � �� � � �� � � �� � � �� � � � 3 4 11 13 17 25 28 33 36 50 52 55 � � � � � � � � �� � � � � � � (d ) 30 � � � � � � � � 10 20 � � �� � � � � � 40 50 � � �� � � � � � � � � �� � � �� � � �� � � �� � � �� � � � 3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55 Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 24 Á rv or es B -P ri m ei ro re fin am en to do al go ri tm o In se re vo id In s( T ip oR eg is tr o R eg , Ti po A po nt ad or Ap , sh or t ∗ C re sc eu , T ip oR eg is tr o ∗ R eg R et or no , Ti po A po nt ad or ∗ A pR et or no ) { lo ng i = 1 ; lo ng j; Ti po A po nt ad or Ap Te m p; if (A p = = N U LL ) { ∗ C re sc eu = TR U E ; A tr ib u i R eg a R eg R et or no ; A tr ib u i N U LL a A pR et or no ; re tu rn ; } w hi le (i < Ap − > n & & R eg .C ha ve > Ap − > r[ i− 1] .C ha ve ) i+ +; if (R eg .C ha ve = = Ap − > r[ i− 1] .C ha ve ) { p ri n tf (" E rr o : R eg is tr o ja es ta pr es en te \n ") ; re tu rn ; } if (R eg .C ha ve < Ap − > r[ i− 1] .C ha ve ) In s( R eg , Ap − > p [i − − ], C re sc eu , R eg R et or no , A pR et or no ); if (! ∗ C re sc eu ) re tu rn ; if (N um er o de re gi st ro s em Ap < m m ) { In se re na pa gi na Ap e ∗ C re sc eu = FA LS E ; re tu rn ; } /∗ O ve rfl ow : P ag in a te m qu e se r di vi di da ∗ / C ria no va pa gi na Ap Te m p; T ra ns fe re m et ad e do s re gi st ro s de Ap pa ra Ap Te m p; A tr ib u i re g is tr o do m ei o a R eg R et or no ; A tr ib u i Ap Te m p a A pR et or no ; } vo id In se re (T ip oR eg is tr o R eg , Ti po A po nt ad or ∗ Ap ) { In s( R eg , ∗ Ap , & C re sc eu , & R eg R et or no , & A pR et or no ); if (C re sc eu ) { C ria no va pa gi na ra iz pa ra R eg R et or no e A pR et or no ; } } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 25 Á rv or es B -P ro ce di m en to In se re N aP ág in a vo id In se re N aP ag in a( Ti po A po nt ad or Ap , T ip oR eg is tr o R eg , Ti po A po nt ad or A pD ir) { sh or t N ao Ac ho uP os ica o; in t k; k = Ap − >n ; N ao Ac ho uP os ica o = (k > 0 ); w hi le (N ao Ac ho uP os ica o) { if (R eg .C ha ve > = Ap − >r [k − 1] .C ha ve ) { N ao Ac ho uP os ica o = FA LS E ; br ea k; } Ap − >r [k ] = Ap − >r [k − 1] ; Ap − >p [k + 1] = Ap − >p [k ]; k− − ; if (k < 1 ) N ao Ac ho uP os ica o = FA LS E ; } Ap − >r [k ] = R eg ; Ap − >p [k + 1] = A pD ir ; Ap − >n ++ ; } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 26 Á rv or es B -R efi na m en to fin al do al go ri tm o In se re vo id In s( T ip oR eg is tr o R eg , Ti po A po nt ad or Ap , sh or t ∗ C re sc eu , T ip oR eg is tr o ∗ R eg R et or no , Ti po A po nt ad or ∗ A pR et or no ) { lo ng i = 1 ; lo ng j; Ti po A po nt ad or Ap Te m p; if (A p = = N U LL ) { ∗ C re sc eu = TR U E ; (∗ R eg R et or no ) = R eg ; (∗ A pR et or no ) = N U LL ; re tu rn ; } w hi le (i < Ap − >n & & R eg .C ha ve > Ap − >r [i − 1] .C ha ve ) i+ +; if (R eg .C ha ve = = Ap − >r [i − 1] .C ha ve ) { p ri n tf (" E rr o : R eg is tr o ja es ta pr es en te \n ") ; ∗ C re sc eu = FA LS E ; re tu rn ; } if (R eg .C ha ve < Ap − >r [i − 1] .C ha ve ) i− − ; In s( R eg , Ap − >p [i ], C re sc eu , R eg R et or no , A pR et or no ); if (! ∗ C re sc eu ) re tu rn ; if (A p− >n < M M ) /∗ P ag in a te m es pa co ∗ / { In se re N aP ag in a( Ap , ∗ R eg R et or no , ∗ A pR et or no ); ∗ C re sc eu = FA LS E ; re tu rn ; } /∗ O ve rfl ow : P ag in a te m que se r di vi di da ∗ / Ap Te m p = (T ip oA po nt ad or )m al lo c( si ze of (T ip oP ag in a )) ; Ap Te m p− >n = 0 ; Ap Te m p− >p [0 ] = N U LL ; {— C on tin ua na pr óx im a tr an sp ar ên ci a — } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 27 Á rv or es B -R efi na m en to fin al do al go ri tm o In se re if (i < M + 1 ) { In se re N aP ag in a( Ap Te m p, Ap − >r [M M − 1] ,A p− >p [M M ]) ; Ap − >n − − ; In se re N aP ag in a( Ap , ∗ R eg R et or no , ∗ A pR et or no ); } el se In se re N aP ag in a( Ap Te m p, ∗ R eg R et or no , ∗ A pR et or no ); fo r (j = M + 2 ; j < = M M ; j+ +) In se re N aP ag in a( Ap Te m p, Ap − >r [j − 1] ,A p− >p [j ]) ; Ap − >n = M ; Ap Te m p− >p [0 ] = Ap − >p [M + 1] ; ∗ R eg R et or no = Ap − >r [M ]; ∗ A pR et or no = Ap Te m p; } vo id In se re (T ip oR eg is tr o R eg , Ti po A po nt ad or ∗ Ap ) { sh or t C re sc eu ; T ip oR eg is tr o R eg R et or no ; Ti po P ag in a ∗ A pR et or no , ∗ Ap Te m p; In s( R eg , ∗ Ap , & C re sc eu , & R eg R et or no , & A pR et or no ); if (C re sc eu ) /∗ A rv or e cr es ce na al tu ra pe la ra iz ∗ / { Ap Te m p = (T ip oP ag in a ∗ )m al lo c( si ze of (T ip oP ag in a )) ; Ap Te m p− >n = 1 ; Ap Te m p− >r [0 ] = R eg R et or no ; Ap Te m p− >p [1 ] = A pR et or no ; Ap Te m p− >p [0 ] = ∗ Ap ; ∗ Ap = Ap Te m p; } } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 28 Á rv or es B -R em oç ão • P ág in a co m o re gi st ro a se rr et ira do é fo lh a: 1. re tir a- se o re gi st ro , 2. se a pá gi na nã o po ss ui pe lo m en os de m re gi st ro s, a pr op rie da de da ár vo re B é vi ol ad a. Pe ga -s e um re gi st ro em pr es ta do da pá gi na vi zi nh a. S e nã o ex is tir re gi st ro s su fic ie nt es na pá gi na vi zi nh a, as du as pá gi na s de ve m se rf un di da s em um a só . • P ag in a co m o re gi st ro nã o é fo lh a: 1. o re gi st ro a se rr et ira do de ve se rp rim ei ra m en te su bs tit uí do po ru m re gi st ro co nt en do um a ch av e ad ja ce nt e. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 29 Á rv or es B -R em oç ão E xe m pl o: R et ira nd o a ch av e 3. � 4 � � � � 6 8 � �� � 2� �� � 1�� � 3 �� � 5�� � 7 � 9�� � � � � 1 2� * � � � 5��� 4 � 7� � � � 6 8 � � � 9�� � � � � 1 2�� � 4�� � 5�� � 6 � 7�� � 8 � � � 9�� (a )P ág in a vi zi nh a po ss ui m ai s do qu e m re gi st ro s � 1�� � 2� � � 3�� � 4 � 5�� � 6 � � � 7�� � � � � 1 2� * � � � 4 � 5�� � 6 � � � 7�� � � � � � 4 6 � � � � 1 2�� � 5 � 7�� (b )P ág in a vi zi nh a po ss ui ex at am en te m re gi st ro s Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 30 Á rv or es B -R em oç ão R em oç ão da s ch av es 45 30 28 ;5 0 8 10 4 20 40 55 17 33 11 36 ;3 9 52 . � � � � (d ) 13 25 43 48 � � � � (c ) 13 � � � � � � � � �� � � � 3 9 25 43 48 52 � � � � (b ) 10 25 40 50 � � � � � �� � � �� � � � � � � � � � � � � � �� � � �� � � �� � � �� � � � 3 4 8 9 11 13 17 20 33 36 43 48 52 55 � � � � � � � � �� � � � � � � (a ) 30 � � � � � � � � 10 20 � � �� � � � � � 40 50 � � �� � � � � � � � � �� � � �� � � �� � � �� � � �� � � � 3 4 8 9 11 13 17 25 28 33 36 43 45 48 52 55 Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 31 Á rv or es B -P ro ce di m en to R et ir a vo id R ec on st itu i( Ti po A po nt ad or Ap Pa g, Ti po A po nt ad or A pP ai , in t P os P ai , sh or t ∗ D im in ui u ) { Ti po P ag in a ∗ Au x; lo ng D is pA ux , j; if (P os P ai < A pP ai− >n ) /∗ Au x = Ti po P ag in a a d ir e it a de Ap Pa g ∗ / { Au x = A pP ai− >p [P os P ai + 1 ]; D is pA ux = (A ux − >n − M + 1 ) / 2 ; Ap Pa g− >r [A pP ag − >n ] = A pP ai− >r [P os P ai ]; Ap Pa g− >p [A pP ag − >n + 1 ] = Au x− >p [0 ]; Ap Pa g− >n ++ ; if (D is pA ux > 0 ) /∗ E xi st e fo lg a : tr an sf er e de Au x pa ra Ap Pa g ∗ / { fo r (j = 1 ; j < D is pA ux ; j+ +) In se re N aP ag in a( Ap Pa g, Au x− >r [j − 1] ,A ux − >p [j ]) ; A pP ai− >r [P os P ai ] = Au x− >r [D is pA ux − 1] ; Au x− >n − = D is pA ux ; fo r (j = 0 ; j < Au x− >n ; j+ + ) Au x− >r [j ] = Au x− >r [j + D is pA ux ]; fo r (j = 0 ; j < = Au x− >n ; j+ + ) Au x− >p [j ] = Au x− >p [j + D is pA ux ]; ∗ D im in ui u = FA LS E ; } el se /∗ Fu sa o : in te rc al a Au x em Ap Pa g e lib er a Au x ∗ / { fo r (j = 1 ; j < = M ; j+ + ) In se re N aP ag in a( Ap Pa g, Au x− >r [j − 1] ,A ux − >p [j ]) ; fr ee (A ux ); fo r (j = P os P ai + 1 ; j < A pP ai− >n ; j+ +) { A pP ai− >r [j − 1] = A pP ai− >r [j ]; A pP ai− >p [j ] = A pP ai− >p [j + 1 ]; } A pP ai− >n − − ; if (A pP ai− >n > = M ) ∗ D im in ui u = FA LS E ; } } {— C on tin ua na pr óx im a tr an sp ar ên ci a — } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 32 Á rv or es B -P ro ce di m en to R et ir a el se /∗ Au x = Ti po P ag in a a es qu er da de Ap Pa g ∗ / { Au x = A pP ai− >p [P os P ai − 1] ;D is pA ux = (A ux − >n − M + 1 ) / 2 ; fo r (j = Ap Pa g− >n ; j > = 1 ; j− − )A pP ag − >r [j ] = Ap Pa g− >r [j − 1] ; Ap Pa g− >r [0 ] = A pP ai− >r [P os P ai − 1] ; fo r (j = Ap Pa g− >n ; j > = 0 ; j− − )A pP ag − >p [j + 1] = Ap Pa g− >p [j ]; Ap Pa g− >n ++ ; if (D is pA ux > 0 ) /∗ E xi st e fo lg a : tr an sf . de Au x pa ra Ap Pa g ∗ / { fo r (j = 1 ; j < D is pA ux ; j+ +) In se re N aP ag in a( Ap Pa g, Au x− >r [A ux − >n − j] , Au x− >p [A ux − >n − j + 1 ]) ; Ap Pa g− >p [0 ] = Au x− >p [A ux − >n − D is pA ux + 1 ]; A pP ai− >r [P os P ai − 1] = Au x− >r [A ux − >n − D is pA ux ]; Au x− >n − = D is pA ux ; ∗ D im in ui u = FA LS E ; } el se /∗ Fu sa o : in te rc al a Ap Pa g em Au x e lib er a Ap Pa g ∗ / { fo r (j = 1 ; j < = M ; j+ +) In se re N aP ag in a( Au x, Ap Pa g− >r [j − 1] ,A pP ag − >p [j ]) ; fr ee (A pP ag ); A pP ai− >n − − ; if (A pP ai− >n > = M ) ∗ D im in ui u = FA LS E ; } } {— C on tin ua na pr óx im a tr an sp ar ên ci a — } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 33 Á rv or es B -P ro ce di m en to R et ir a vo id R et (T ip oC ha ve C h, Ti po A po nt ad or ∗ Ap , sh or t ∗ D im in ui u ) { lo ng j, In d = 1 ; Ti po A po nt ad or Pa g; if (∗ Ap = = N U LL ) { p ri n tf (" E rr o : re g is tr o na o es ta na ar vo re \n ") ; ∗ D im in ui u = FA LS E ; re tu rn ; } Pa g = ∗ Ap ; w hi le (I nd < Pa g− >n & & C h > Pa g− >r [I nd − 1] .C ha ve ) In d+ +; if (C h = = Pa g− >r [I nd − 1] .C ha ve ) { if (P ag − >p [I nd − 1] == N U LL ) /∗ Ti po P ag in a fo lh a ∗ / { Pa g− >n − − ;∗ D im in ui u = (P ag − >n < M ); fo r (j = In d ; j < = Pa g− >n ; j+ + ) { Pa g− >r [j − 1] = Pa g− >r [j ]; Pa g− >p [j ] = Pa g− >p [j + 1 ]; } retu rn ; } /∗ Ti po P ag in a na o e fo lh a : tr oc ar co m an te ce ss or ∗ / A nt ec es so r( ∗ Ap , In d , Pa g− >p [I nd − 1] , D im in ui u ); if (∗ D im in ui u ) R ec on st itu i( Pa g− >p [I nd − 1] ,∗ Ap , In d − 1 , D im in ui u ); re tu rn ; } if (C h > Pa g− >r [I nd − 1] .C ha ve ) In d+ +; R et (C h, & Pa g− >p [I nd − 1] , D im in ui u ); if (∗ D im in ui u ) R ec on st itu i( Pa g− >p [I nd − 1] ,∗ Ap , In d − 1 , D im in ui u ); } {— C on tin ua na pr óx im a tr an sp ar ên ci a — } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 34 Á rv or es B -P ro ce di m en to R et ir a vo id A nt ec es so r( Ti po A po nt ad or Ap , in t In d , Ti po A po nt ad or A pP ai , sh or t ∗ D im in ui u ) { if (A pP ai− >p [A pP ai− >n ] != N U LL ) { A nt ec es so r( Ap , In d , A pP ai− >p [A pP ai− >n ], D im in ui u ); if (∗ D im in ui u ) R ec on st itu i( A pP ai− >p [A pP ai− >n ], A pP ai , (l on g )A pP ai− >n , D im in ui u ); re tu rn ; } Ap − >r [I nd − 1] = A pP ai− >r [A pP ai− >n − 1] ; A pP ai− >n − − ; ∗ D im in ui u = (A pP ai− >n < M ); } {— C on tin ua na pr óx im a tr an sp ar ên ci a — } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 35 Á rv or es B -P ro ce di m en to R et ir a vo id R et (T ip oC ha ve C h, Ti po A po nt ad or ∗ Ap , sh or t ∗ D im in ui u ) { lo ng j, In d = 1 ; Ti po A po nt ad or Pa g; if (∗ Ap = = N U LL ) { p ri n tf (" E rr o : re g is tr o na o es ta na ar vo re \n ") ; ∗ D im in ui u = FA LS E ; re tu rn ; } Pa g = ∗ Ap ; w hi le (I nd < Pa g− >n & & C h > Pa g− >r [I nd − 1] .C ha ve ) In d+ +; if (C h = = Pa g− >r [I nd − 1] .C ha ve ) { if (P ag − >p [I nd − 1] == N U LL ) /∗ Ti po P ag in a fo lh a ∗ / { Pa g− >n − − ; ∗ D im in ui u = (P ag − >n < M ); fo r (j = In d ; j < = Pa g− >n ; j+ +) { Pa g− >r [j − 1] = Pa g− >r [j ]; Pa g− >p [j ] = Pa g− >p [j + 1 ]; } re tu rn ; } /∗ Ti po P ag in a na o e fo lh a : tr oc ar co m an te ce ss or ∗ / A nt ec es so r( ∗ Ap , In d , Pa g− >p [I nd − 1] , D im in ui u ); if (∗ D im in ui u ) R ec on st itu i( Pa g− >p [I nd − 1] ,∗ Ap , In d − 1 , D im in ui u ); re tu rn ; } {— C on tin ua na pr óx im a tr an sp ar ên ci a — } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 1 36 Á rv or es B -P ro ce di m en to R et ir a if (C h > Pa g− >r [I nd − 1] .C ha ve ) In d+ +; R et (C h, & Pa g− >p [I nd − 1] , D im in ui u ); if (∗ D im in ui u ) R ec on st itu i( Pa g− >p [I nd − 1] ,∗ Ap , In d − 1 , D im in ui u ); } vo id R et ir a (T ip oC ha ve C h, Ti po A po nt ad or ∗ Ap ) { sh or t D im in ui u ; Ti po A po nt ad or Au x; R et (C h, Ap , & D im in ui u ); if (D im in ui u & & (∗ Ap )− >n = = 0 ) /∗ A rv or e di m in ui na al tu ra ∗ / { Au x = ∗ Ap ; ∗ Ap = Au x− >p [0 ]; fr ee (A ux ); } } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 2 37 Á rv or es B * -T A D D ic io ná ri o • E st ru tu ra de D ad os : ty pe de f in t Ti po C ha ve ; ty pe de f st ru ct T ip oR eg is tr o { Ti po C ha ve C ha ve ; /∗ ou tr os co m po ne nt es ∗ / } T ip oR eg is tr o ; ty pe de f en um { In te rn a , E xt er na } T ip oI nt E xt ; ty pe de f st ru ct Ti po P ag in a ∗ Ti po A po nt ad or ; ty pe de f st ru ct Ti po P ag in a { T ip oI nt E xt P t; un io n { st ru ct { in t n i; Ti po C ha ve ri [M M ]; Ti po A po nt ad or p i[ M M + 1 ]; } U 0; st ru ct { in t ne ; T ip oR eg is tr o re [M M 2 ]; } U 1; } U U ; } Ti po P ag in a ; Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 2 38 Á rv or es B * -P es qu is a • S em el ha nt e à pe sq ui sa em ár vo re B , • A pe sq ui sa se m pr e le va a um a pá gi na fo lh a, • A pe sq ui sa nã o pá ra se a ch av e pr oc ur ad a fo re nc on tra da em um a pá gi na ín di ce . O ap on ta do rd a di re ita é se gu id o at é qu e se en co nt re um a pá gi na fo lh a. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 2 39 Á rv or es B * -P ro ce di m en to pa ra pe sq ui sa r na ár vo re B � vo id P es qu is a( T ip oR eg is tr o ∗ x , Ti po A po nt ad or ∗ Ap ) { in t i; Ti po A po nt ad or Pa g; Pa g = ∗ Ap ; if (( ∗ Ap )− >P t = = In te rn a ) { i = 1 ; w hi le (i < Pa g− >U U .U 0. n i& & x− >C ha ve > Pa g− >U U .U 0. ri [i − 1 ]) i+ +; if (x − >C ha ve < Pa g− >U U .U 0. ri [i − 1] ) P es qu is a( x, & Pa g− >U U .U 0. p i[ i − 1 ]) ; el se P es qu is a( x, & Pa g− >U U .U 0. p i[ i] ); re tu rn ; } i = 1 ; w hi le (i < Pa g− >U U .U 1. ne & & x− >C ha ve > Pa g− >U U .U 1. re [i − 1] .C ha ve ) i+ +; if (x − >C ha ve = = Pa g− >U U .U 1. re [i − 1] .C ha ve ) ∗ x = Pa g− >U U .U 1. re [i − 1] ; el se p ri n tf (" T ip oR eg is tr o na o es ta pr es en te na ar vo re \n ") ; } Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 2 40 Á rv or es B * -I ns er çã o e R em oç ão • In se rç ão na ár vo re B * – S em el ha nt e à in se rç ão na ár vo re B , – D ife re nç a: qu an do um a fo lh a é di vi di da em du as ,o al go rit m o pr om ov e um a có pi a da ch av e qu e pe rt en ce ao re gi st ro do m ei o pa ra a pá gi na pa in o ní ve la nt er io r, re te nd o o re gi st ro do m ei o na pá gi na fo lh a da di re ita . • R em oç ão na ár vo re B * – R el at iv am en te m ai s si m pl es qu e em um a ár vo re B , – To do s os re gi st ro s sã o fo lh as , – D es de qu e a fo lh a fiq ue co m pe lo m en os m et ad e do s re gi st ro s, as pá gi na s do s ín di ce s nã o pr ec is am se rm od ifi ca da s, m es m o se um a có pi a da ch av e qu e pe rt en ce ao re gi st ro a se rr et ira do es te ja no ín di ce . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 3 41 A ce ss o C on co rr en te em Á rv or e B * • A ce ss o si m ul tâ ne o a ba nc o de da do s po rm ai s de um us uá rio . • C on co rr ên ci a au m en ta a ut ili za çã o e m el ho ra o te m po de re sp os ta do si st em a. • O us o de ár vo re s B * ne ss es si st em as de ve pe rm iti ro pr oc es sa m en to si m ul tâ ne o de vá ria s so lic ita çõ es di fe re nt es . • N ec es si da de de cr ia rm ec an is m os ch am ad os pr ot oc ol os pa ra ga ra nt ir a in te gr id ad e ta nt o do s da do s qu an to da es tr ut ur a. • P ág in a se gu ra : nã o há po ss ib ili da de de m od ifi ca çõ es na es tr ut ur a da ár vo re co m o co ns eq üê nc ia de in se rç ão ou re m oç ão . – in se rç ão → pá gi na se gu ra se o nú m er o de ch av es é ig ua la 2m , – re m oç ão → pá gi na se gu ra se o nú m er o de ch av es é m ai or qu e m . • O s al go rit m os pa ra ac es so co nc or re nt e fa ze m us o de ss a pr oprie da de pa ra au m en ta ro ní ve ld e co nc or rê nc ia . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 3 42 A ce ss o C on co rr en te em Á rv or e B * -P ro to co lo s de Tr av am en to s • Q ua nd o um a pá gi na é lid a, a op er aç ão de re cu pe ra çã o a tra va ,a ss im , ou tro s pr oc es so s, nã o po de m in te rfe rir co m a pá gi na . • A pe sq ui sa co nt in ua em di re çã o ao ní ve ls eg ui nt e e a tra va é lib er ad a pa ra qu e ou tro s pr oc es so s po ss am le ra pá gi na . • P ro ce ss o le ito r→ ex ec ut a um a op er aç ão de re cu pe ra çã o • P ro ce ss o m od ifi ca do r→ ex ec ut a um a op er aç ão de in se rç ão ou re tir ad a. • D oi s tip os de tra va m en to : – Tr av am en to pa ra le itu ra → pe rm ite um ou m ai s le ito re s ac es sa re m os da do s, m as nã o pe rm ite in se rç ão ou re tir ad a. – Tr av am en to ex cl us iv o → ne nh um ou tro pr oc es so po de op er ar na pá gi na e pe rm ite qu al qu er tip o de op er aç ão na pá gi na . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 4 43 Á rv or e B -C on si de ra çõ es P rá tic as • S im pl es ,f ác il m an ut en çã o, efi ci en te e ve rs át il. • Pe rm ite ac es so se qü en ci al efi ci en te . • C us to pa ra re cu pe ra r, in se rir e re tir ar re gi st ro s do ar qu iv o é lo ga rit m ic o. • E sp aç o ut ili za do é, no m ín im o 50 % do es pa ço re se rv ad o pa ra o ar qu iv o, • E m pr eg o on de o ac es so co nc or re nt e ao ba nc o de da do s é ne ce ss ár io , é vi áv el e re la tiv am en te si m pl es de se ri m pl em en ta do . • In se rç ão e re tir ad a de re gi st ro s se m pr e de ix am a ár vo re ba la nc ea da . • U m a ár vo re B de or de m m co m N re gi st ro s co nt ém no m áx im o ce rc a de lo g m + 1 N pá gi na s. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 4 44 Á rv or e B -C on si de ra çõ es P rá tic as • Li m ite s pa ra a al tu ra m áx im a e m ín im a de um a ár vo re B de or de m m co m N re gi st ro s: lo g 2 m + 1 (N + 1) ≤ a lt u r a ≤ 1 + lo g m + 1 � N + 1 2 � • C us to pa ra pr oc es sa ru m a op er aç ão de re cu pe ra çã o de um re gi st ro cr es ce co m o lo ga rit m o ba se m do ta m an ho do ar qu iv o. • A ltu ra es pe ra da : nã o é co nh ec id a an al iti ca m en te . • H á um a co nj ec tu ra pr op os ta a pa rt ir do cá lc ul o an al íti co do nú m er o es pe ra do de pá gi na s pa ra os qu at ro pr im ei ro s ní ve is (d as fo lh a em di re çã o à ra iz )d e um a ár vo re 2- 3 (á rv or e B de or de m m = 1) . • C on je tu ra : a al tu ra es pe ra da de um a ár vo re 2- 3 ra nd ôm ic a co m N ch av es é h (N ) ≈ lo g 7 / 3 (N + 1) . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 4 45 Á rv or es B R an dô m ic as -M ed id as de C om pl ex id ad e • A ut ili za çã o de m em ór ia é ce rc a de ln 2. – P ág in as oc up am ≈ 69 % da ár ea re se rv ad a ap ós N in se rç õe s ra nd ôm ic as em um a ár vo re B in ic ia lm en te va zi a. • N o m om en to da in se rç ão ,a op er aç ão m ai s ca ra é a pa rt iç ão da pá gi na qu an do el a pa ss a a te rm ai s do qu e 2m ch av es . E nv ol ve : – C ria çã o de no va pá gi na ,r ea rr an jo da s ch av es e in se rç ão da ch av e do m ei o na pá gi na pa il oc al iz ad a no ní ve la ci m a. – P r {j pa rt iç õe s} : pr ob ab ili da de de qu e j pa rt iç õe s oc or ra m du ra nt e a N -é si m a in se rç ão ra nd ôm ic a. – Á rv or e 2- 3: P r { 0 pa rt iç õe s} = 4 7 ,P r { 1 ou m ai s pa rt iç õe s} = 3 7 · – Á rv or e B de or de m m : P r { 0 pa rt iç õe s} = 1 − 1 (2 ln 2 )m + O (m − 2 ), P r {1 ou + pa rt iç õe s} = 1 (2 ln 2 )m + O (m − 2 ). – Á rv or e B de or de m m = 70 : 99 % da s ve ze s na da ac on te ce em te rm os de pa rt iç õe s du ra nt e um a in se rç ão . Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 4 46 Á rv or es B R an dô m ic as -A ce ss o C on co rr en te • Fo ip ro po st a um a té cn ic a de ap lic ar um tra va m en to na pá gi na se gu ra m ai s pr of un da (P sm p) no ca m in ho de in se rç ão . • U m a pá gi na é se gu ra se el a co nt ém m en os do qu e 2m ch av es . • U m a pá gi na se gu ra é a m ai s pr of un da se nã o ex is tir ou tra pá gi na se gu ra ab ai xo de la . • Já qu e o tra va m en to da pá gi na im pe de o ac es so de ou tro s pr oc es so s, é in te re ss an te sa be rq ua lé a pr ob ab ili da de de qu e a pá gi na se gu ra m ai s pr of un da es te ja no pr im ei ro ní ve l. • Á rv or e 2- 3: P r {P sm p es te ja no 1◦ ní ve l} = 4 7 , P r {P sm p es te ja ac im a do 1◦ ní ve l} = 3 7 · • Á rv or e B de or de m m : P r {P sm p es te ja no 1◦ ní ve l} = 1 − 1 (2 ln 2 )m + O (m − 2 ), P r {P sm p es te ja ac im a do 1◦ ní ve l} = 3 7 = 1 (2 ln 2 )m + O (m − 2 ). Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 4 47 Á rv or es B R an dô m ic as -A ce ss o C on co rr en te • N ov am en te ,e m ár vo re s B de or de m m = 70 : 99 % da s ve ze s a P sm p es tá em um a fo lh a. (P er m ite al to gr au de co nc or rê nc ia pa ra pr oc es so s m od ifi ca do re s. ) • S ol uç õe s m ui to co m pl ic ad as pa ra pe rm iti rc on co rr ên ci a de op er aç õe s em ár vo re s B nã o tra ze m gr an de s be ne fíc io s. • N a m ai or ia da s ve ze s, o tra va m en to oc or re rá em pá gi na s fo lh a. (P er m ite al to gr au de co nc or rê nc ia m es m o pa ra os pr ot oc ol os m ai s si m pl es .) Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 4 48 Á rv or e B -T éc ni ca de Tr an sb or da m en to (o u O ve rfl ow ) • A ss um a qu e um re gi st ro te nh a de se ri ns er id o em um a pá gi na ch ei a, co m 2m re gi st ro s. • E m ve z de pa rt ic io ná -la ,o lh am os pr im ei ro pa ra a pá gi na irm ã à di re ita . • S e a pá gi na irm ã po ss ui m en os do qu e 2m re gi st ro s, um si m pl es re ar ra nj o de ch av es to rn a a pa rt iç ão de sn ec es sá ria . • S e a pá gi na à di re ita ta m bé m es tiv er ch ei a ou nã o ex is tir ,o lh am os pa ra a pá gi na irm ã à es qu er da . • S e am ba s es tiv er em ch ei as ,e nt ão a pa rt iç ão te rá de se rr ea liz ad a. • E fe ito da m od ifi ca çã o: pr od uz ir um a ár vo re co m m el ho ru til iz aç ão de m em ór ia e um a al tu ra es pe ra da m en or . • P ro du z um a ut ili za çã o de m em ór ia de ce rc a de 83 % pa ra um a ár vo re B ra nd ôm ic a. Pr oj et o de A lg or itm os – C ap .6 Pe sq ui sa em M em ór ia Se cu nd ár ia – Se çã o 6. 3. 4 49 Á rv or e B -I nfl uê nc ia do S is te m a de Pa gi na çã o • O nú m er o de ní ve is de um a ár vo re B é m ui to pe qu en o(tr ês ou qu at ro ) se co m pa ra do co m o nú m er o de m ol du ra s de pá gi na s. • A ss im ,o si st em a de pa gi na çã o ga ra nt e qu e a pá gi na ra iz es te ja se m pr e na m em ór ia pr in ci pa l( se fo ra do ta da a po lít ic a LR U ). • O es qu em a LR U fa z co m qu e as pá gi na s a se re m pa rt ic io na da s em um a in se rç ão es te ja m di sp on ív ei s na m em ór ia pr in ci pa l. • A es co lh a do ta m an ho ad eq ua do da or de m m da ár vo re B é ge ra lm en te fe ita le va nd o em co nt a as ca ra ct er ís tic as de ca da co m pu ta do r. • O ta m an ho id ea ld a pá gi na da ár vo re co rr es po nd e ao ta m an ho da pá gi na do si st em a, e a tra ns fe rê nc ia de da do s en tre as m em ór ia s se cu nd ár ia e pr in ci pa lé re al iz ad a pe lo si st em a op er ac io na l. • E st es ta m an ho s va ria m en tre 51 2 by te s e 4. 09 6 by te s, em m úl tip lo s de 51 2 by te s.
Compartilhar