11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal)

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal)

hogy memóriájuk több különbözo kapacitású, hozA mai számítógépekre az jellemzo, áll. A processzor számára közvetlenül elérheto szintet záférési ideju és költségu szintbol zikai memóriának (vagy röviden memóriának), a további szinteket pedig háttértárnak nevezzük. Rendszerint több program fut egyidejuleg, amelyeknek együttes tárigénye nagyobb, mint a zikai memória kapacitása. Ezért a memóriát a folyamatok között el kell osztani. algoritmusaival foglakozunk. A Ebben a fejezetben a memóriagazdálkodás alapveto 11.1. alfejezetben a statikus és dinamikus partícionálás, majd a 11.2. alfejezetben a lapozás legismertebb módszereit tekintjük át. A 11.3. alfejezetben az operációs rendszerek történetének legnevezetesebb anomáliáit algoritmusok a FIFO lapcserélési algoritmus, az átfedéses memória és a listás ütemezo tulajdonságait elemezzük. meglepo algoritmuVégül a 11.4. alfejezetben annak az optimalizálási feladatnak a közelíto sait tekintjük át, melyben adott méretu fájlokat kell minimális számú mágneslemezen elhelyezni.

11.1. Partícionálás A memória programok közötti elosztásának egyszeru módja, hogy a teljes címtartományt részekre bontjuk, és minden folyamat egy ilyen részt kap. Ezeket a részeket partícióknak nevezzük. Ehhez a megoldáshoz nincs szükség különösebb hardvertámogatásra, csupán az címekre lehessen betölteni, azaz a programok áthekell, hogy egy programot különbözo lyezhetok legyenek. Erre azért van szükség, mert nem tudjuk garantálni, hogy egy program mindig ugyanabba a partícióba kerüljön, hiszen összességében szinte mindig több futtatható program van, mint amennyi a memóriába befér. Ráadásul azt sem tudjuk meghatározni, hogy mely programok futhatnak egyszerre, és melyek nem, hiszen a folyamatok ál felhasználók a tulajdonosaik. Így még talában egymástól függetlenek, sokszor különbözo az is elofordulhat, hogy egyszerre többen futtatják ugyanazt a programot, és a példányok adatokkal dolgoznak, tehát nem lehetnek ugyanott a memóriában. Az áthelyekülönbözo ha a szerkesztoprogram zés szerencsére könnyen elvégezheto, nem abszolút, hanem relatív címekkel dolgozik, azaz nem a pontos memóriabeli helyeket, hanem egy kezdocímhez viszonyított eltolásokat használ minden címzésnél. Ezt a módszert báziscímzésnek nevezzük,

11.1. Partícionálás

457

ahol a kezdocímet az úgynevezett bázisregiszter tartalmazza. A legtöbb processzor ismeri ezt a címzési módot, ezért a program nem lesz lassabb, mintha abszolút címeket használna. hogy a program egy hiba vagy szándékos felBáziscímzés használatával az is elkerülheto, használói magatartás folytán valamely másik, alacsonyabb memóriabeli címeken elhelyez program adatait kiolvassa, esetleg módosítsa. Ha a módszert kiegészítjük egy másik, kedo úgynevezett határregiszter használatával, amely a legnagyobb megengedett eltolást, azaz a partíció méretét adja meg, akkor azt is biztosítani tudjuk, hogy egy program számára a program se legyen hozzáférheto. többi, nála magasabb memóriabeli címeken elhelyezkedo A partícionálást régebben gyakran alkalmazták nagygépes operációs rendszerekben. A modern operációs rendszerek többsége azonban virtuális memóriakezelést használ, amihez viszont már különleges hardvertámogatásra van szükség. A partícionálás, mint memóriafelosztási módszer azonban nemcsak operációs rendsze rekben alkalmazható. Ha a gépi kódhoz közeli szinten programozunk, akkor elofordulhat, változó méretu hogy különbözo, adatszerkezeteket amelyek dinamikusan jönnek létre, illetve szunnek meg kell elhelyeznünk egy folytonos memóriaterületen. Ezek az adatszerkezetek hasonlítanak a folyamatokhoz, azzal a kivétellel, hogy olyan biztonsági problémákkal, mint a saját területen kívülre való címzés, nem kell foglalkoznunk. Ezért az alább felsorolandó algoritmusok nagy része kisebb-nagyobb módosításokkal hasznunkra lehet alkalmazások fejlesztésénél is. Alapvetoen kétféleképpen lehet felosztani egy címtartományt partíciókra. Az egyik módszer, hogy kezdetben a még üres címtartományt osztjuk fel elore meghatározott méretu és számú részre, és ezekbe próbáljuk meg folyamatosan belehelyezni a folyamatokat vagy más adatszerkezeteket, illetve eltávolítjuk belolük, ha már nincs rájuk szükség. Ezek a rögzített partíciók, hiszen mind helyük, mind méretük elore, az operációs rendszer vagy az alkalmazás indulásakor rögzítve van. A másik módszer, hogy folyamatosan jelölünk ki az újonnan keletkezo folyamatok vagy adatszerdarabokat a címtartomány szabad részérol kezetek számára, illetve megszunésükkor újra szabaddá nyilvánítjuk azokat. Ezt a megoldást hívjuk a dinamikus partíciók módszerének, mivel a partíciók dinamikusan keletkeznek, illetve szunnek meg. Mindkét módszernek vannak mind elonyei, mind hátrányai, és megva algoritmusokat igényel. Ezeket tekintjük át a következokben. lósításuk teljesen különbözo

11.1.1. Rögzített partíciók A rögzített partíciók módszerénél a címtartomány felosztása elore rögzített, és futás közben nem változtatható. Operációs rendszerek esetén ez úgy történik, hogy a rendszergazda betöltodésekor egy táblázatban meghatározza a partíciókat, és a rendszer következo a fel felhasználói alkalmazás elindul, a címtartomány osztás alapja ez a táblázat. Amikor az elso már partícionálva van. Alkalmazásoknál a partícionálást akkor kell elvégezni, amikor még egyetlen adatszerkezet sincs a felosztandó memóriaterületen. Ezután a kész partíciókban méretu lehet elhelyezni a különbözo adatszerkezeteket. A továbbiakban csakis az operációs rendszerekbeli megvalósítást vizsgáljuk, a feladat és az algoritmusok átfogalmazását adott alkalmazáshoz az Olvasóra bízzuk, hiszen ezek alkalmazásfajtánként egymástól nagyon eltéroek is lehetnek. A címtartomány felosztásakor azt kell gyelembe venni, hogy mekkora folyamatok és milyen arányban fognak a rendszerbe érkezni. Nyilvánvalóan van egy maximális méret, folyamatok nem futhatnak az adott rendszerben. A legnagyobb partíció méamelyet túllépo

458


rete ezzel a maximummal egyezik meg. Az optimális partícionáláshoz gyakran statisztikai újraindítása elott a partíciók méretét ezen felméréseket kell végezni, és a rendszer következo statisztikák alapján kell módosítani. Ennek mikéntjével most nem foglalkozunk. Mivel konstans számú (m) partíciónk van, adataikat tárolhatjuk egy vagy több állandó hosszúságú vektorban. A partíciók konkrét helyével absztrakt szinten nem foglalkozunk: feltételezzük, hogy ezt egy konstans vektor tárolja. Egy folyamatot úgy helyezünk el egy partícióban, hogy sorszámát rögzítjük a folyamat leírójában. Természetesen a konkrét meg eltérhet. A partíciók méretét a méret[1 . . m] vektor tartalmazza. Folyamatainvalósítás ettol n-ig számozzuk. Azt, hogy egy partícióban épp mely folyamat fut, a part[1 . . m] kat 1-tol vektor tartalmazza, melynek párja a hely[1 . . n] vektor, ami azt adja meg, hogy egy folyamat mely partícióban fut. Egy folyamat vagy fut, vagy pedig várakozik arra, hogy bekerüljön egy partícióba, és ott futhasson. Ezt az információt a vár[1 . . n] vektor tartalmazza: ha az i-edik folyamat vár, akkor vár[i]

= , egyébként pedig vár[i] = . A folyamatok helyigé-

nye különbözik. A helyigény[1 . . n] azt adja meg, hogy legalább mekkora partíció szükséges a folyamatok futtatásához. méretu helyigényu Ha különbözo partícióink és különbözo folyamataink vannak, akkor nyilván nem szeretnénk, hogy a kis folyamatok a nagy partíciókat foglalják el, miközben a kisebb partíciók üresen maradnak, hiszen oda nem férnének be a nagyobb folyamatok. Ezért azt kell elérnünk, hogy minden partícióba az kerüljön betöltésre a várakozó folyamatok kö zül, amely oda befér, és nincs nála nagyobb, ami szintén beférne. Ezt biztosítja a következo algoritmus: L- ´  (hely, helyigény, méret, part, vár) 1 2

← 1 to m

for j

do if part[j]

=0

then B ¨ -(hely, helyigény, méret, j, part, vár)

3

A legnagyobb olyan folyamat megtalálása, amelynek helyigénye nem nagyobb egy adott méretnél, egy egyszeru feltételes maximumkeresés. Amennyiben egyáltalán nem talá folyamatot, kénytelenek vagyunk a partíciót üresen hagyni. lunk a feltételnek megfelelo B ¨ -(hely, helyigény, méret, p, part, vár)

←0 ←0 for i ← 1 to n

1

max

2

ind

3 4

=  és max < helyigény[i] ≤ méret[p] ←i max ← helyigény[i]

do if vár[i]

then ind

5 6 7 8 9 10

if ind

>0 ← ind ←p vár[ind] ← 

then part[p]

hely[ind]

algoritmusok helyességének alapveto kritériuma, hogy A folyamatokat partícióba tölto


459

ne töltsenek nagyobb folyamatot egy partícióba, mint amekkora belefér. Ezt a feltételt telje a feltételes maximumkeresés tételére pontosan síti a fenti algoritmus, hiszen visszavezetheto az említett feltétellel. Egy másik nagyon fontos kritérium, hogy ne töltsön egy partícióba több folyama eset azért zárható ki, tot, illetve ne töltsön egyetlen folyamatot több partícióba. Az elso mert csakis azokra a partíciókra hajtjuk végre a B ¨ - algoritmust, amelyekre part[ j]

=

0, és ha betöltünk egy folyamatot a p-edik partícióba, akkor part[ p]-nek érté-

kül adjuk a betöltött folyamat sorszámát, ami pozitív egész. A második eset bizonyítása is hasonló: a feltételes maximumkeresés feltétele kizárja azokat a folyamatokat, amelyekre vár[i]

= , és ha az ind-edik folyamatot egynél többször betöltjük valamely partícióba,  értéket adunk.

akkor vár[ind]-nek

Az, hogy az algoritmus nem tölt nagyobb folyamatot egyik partícióba sem, mint amekkora belefér, illetve hogy egyetlen partícióba sem tölt egynél több folyamatot és hogy egyetlen folyamatot sem tölt egynél több partícióba, még nem elég. Ezeket az üres algoritmus is teljesíti. Ezért mi többet követelünk: mégpedig azt, hogy ne hagyjon szabadon egyetlen partíciót sem, ha van olyan folyamat, amely beleférne. Ehhez szükségünk van egy invariánsra, amely az egész ciklus során fennáll, és a ciklus végén biztosítja ezt a feltételt is. Legyen az invariánsunk az, hogy j darab partíció megvizsgálása után nem létezik olyan pozitív k

≤

= 0,

j, amelyre part[k]

helyigény[i]

és amelyre van olyan pozitív i

≤ n,

= 

hogy vár[i]

és

≤ méret[k].

Teljesül: Az algoritmus elején j létezik pozitív k

≤

=

0 darab partíciót vizsgáltunk meg, így egyáltalán nem

j.

Megmarad: Ha az invariáns teljesül j-re a ciklusmag elején, akkor eloször is azt kell látnunk, hogy ugyanerre a j-re a ciklus végén is teljesülni fog. Ez nyilvánvaló, hiszen az

+ 1)-edik vizsgálata során, a bennük levo fo= , ami nem felel meg a B ¨ - algoritmusmaximumkeresés feltételének. A ( j + 1)-edik partícióra pedig

j darab partícióhoz nem nyúlunk a ( j elso lyamatokra pedig vár[i] ban található feltételes

azért fog teljesülni az invariáns a ciklusmag végén, mert ha van a feltételnek megfelelo folyamat, azt a feltételes maximumkeresés biztosan megtalálja, hiszen a feltételes maximumkeresésünk feltétele megegyezik az invariánsunk egyes partíciókon értelmezett követelményével. Befejezodik: Mivel a ciklus egyesével halad végig egy rögzített intervallumon, biztosan be is fog fejezodni. Mivel a ciklusmag pontosan annyiszor hajtódik végre, mint ahány partíció van, a ciklus befejezodésekor igaz lesz, hogy nem létezik olyan pozitív k m, amelyre part[k] helyigény[i]

≤

= 0,

és amelyre van olyan pozitív i

≤

= 

n, hogy vár[i]

≤ és

méret[k], azaz nem hagytunk szabadon egyetlen olyan partíciót sem,

amelyben lenne folyamat, ami belefér. ciklus mindig teljes egészében A L- ´  algoritmus 13. soraiban lévo lefut, tehát a ciklusmag

Θ(m)-szer

hajtódik végre. A ciklusmag egy feltételes maximum-

keresést hajt végre az üres partíciókon vagy azokon, amelyekre part[ j]

=

0. Mivel a

feltételt minden j-re ki kell értékelni, ezért a feltételes B ¨ - 4. sorában lévo maximumkeresés Θ(n) lépést igényel. Bár azokra a partíciókra, amelyekre part[ j]

> 0, a be-

eljárás nem hívódik meg, a futási ido szempontjából legrosszabb esetben akár minden tölto partíció üres lehet, ezért az algoritmus összes lépésszáma

Θ(mn).

Az, hogy az algoritmus minden üres partícióba betölt egy várakozó folyamatot, ami

460


Gyakran szükség van arra is, hogy egy folyamat valabefér, sajnos nem mindig elegendo. belül memóriához jusson. Ezt azonban a fenti algoritmus akkor milyen megadott határidon korlátot tudunk adni. Amikor sem biztosítja, ha az egyes folyamatok futási idejére felso ugyanis újra és újra lefuttatjuk az algoritmust, mindig jöhetnek újabb folyamatok, amik kiszoríthatják a régóta várakozókat. Tekintsünk erre egy példát. 11.1. példa. Legyen két partíciónk, 5 kB és 10 kB méretekkel. Kezdetben két folyamatunk van, egy másod8 és egy 9 kB helyigényu. Mindkét folyamat futása 22 másodpercig tart. Azonban az elso perc végén megjelenik egy újabb, szintén 9 kB helyigényu és 2 másodperc futási ideju folyamat, és ez megismétlodik 2 másodpercenként, azaz a harmadik, az ötödik stb. másodpercekben. Ha most megvizsgáljuk az algoritmusunkat, akkor láthatjuk, hogy annak mindig két folyamat közül kell választania, és mindig a 9 kB helyigényu lesz a nyertes. A 8 kB-os, noha nincs más partíció, amelybe beférne, soha nem fog memóriához jutni.

Ahhoz, hogy a fent említett követelményt is teljesítsük, módosítani kell az algoritmusunkat: gyelembe kell vennünk, hogy mely folyamatok azok, amelyek már túl hosszú ideje várakoznak, és elonyben kell részesítenünk oket minden más folyamattal szemben akkor is, ha kisebb a helyigényük, mint azoknak. Az új algoritmusunk ugyanúgy megvizsgál minden o. partíciót, mint az eloz L-- ´ -´  (hely, helyigény, küszöb, méret, part, vár) ´  ´ - ´ 1 2

for j

← 1 to m

do if part[j]

=0

then B ´ (hely, helyigény, ¨ --- ´  ´ - ´

3

küszöb, méret, j, part, vár)

Azonban a betöltésnél meg kell vizsgálnunk minden folyamatra, hogy az mennyi ideje várakozik. Mivel az algoritmust mindig akkor futtatjuk, amikor egy vagy több partíció fel vizsgálni, csak azt, hogy hányszor nem tettük be egy szabadul, nem tudjuk a konkrét idot olyan partícióba, amelybe befért volna. Ehhez módosítanunk kell a feltételes maximumkeresés algoritmusát: azokon az elemeken is muveletet kell végeznünk, amelyek ugyan teljesítik a feltételt (memóriára várakoznak és be is férnének), de nem a legnagyobbak ezek közül. Ez a muvelet egy számláló növelése. A számlálóról feltételezzük, hogy a folyamat keletkezésekor a 0 értéket veszi fel. Ezenkívül a feltételt is kicsit módosítanunk kell: ha a számláló értéke egy elemnél túl magas (azaz egy bizonyos küszöb feletti), és az eddig talált legnagyobb helyigényu folyamat számlálójánál is nagyobb, akkor lecseréljük azt erre az elemre. Az, hogy az algoritmus nem helyez több folyamatot ugyanabba a partícióba, ugyanúgy o algoritmusnál, hiszen a külso ciklust és az abban található elágazás látható, mint az eloz feltételét nem változtattuk meg. A másik két kritérium bizonyításához, azaz hogy nem kerül egy folyamat több partícióba vagy olyan partícióba, amibe nem fér, azt kell látnunk, hogy a feltételes maximumkeresés feltételét úgy alakítottuk át, hogy ez a tulajdonság megmaradt. része pontosan ez, amit követelünk, és ha Látható, hogy a feltételt kettébontottuk, így elso ez nem teljesül, az algoritmus biztosan nem helyezi be a folyamatot a partícióba. Az a tulajdonság is megmarad, hogy nem hagyunk üresen partíciót, hiszen a feltételt, amely alapján o megkiválasztottuk a folyamatot, nem szukítettük, hanem csak bovítettük, így ha az eloz


461

talált minden folyamatot, ami megfelel a kritériumnak, akkor az új algoritmus is megtalálja folyamatok közötti sorrend az, amit változtattunk. ezeket. Csupán a kritériumnak megfelelo ciklust milyen felA ciklusok lépésszáma sem változott, mint ahogy az sem, hogy a belso tétel mellett kell elkezdeni végrehajtani. Tehát az algoritmus lépésszámának nagyságrendje is ugyanannyi, mint az eredeti algoritmusé. Meg kell még vizsgálnunk, hogy az algoritmus teljesíti-e azt a feltételt, hogy egy folyamat csak meghatározott ideig várakozhat memóriára, amennyiben feltételezzük, hogy korlátot a folyamatok futási idejére (ellenkezo esetben a probismerünk valamilyen p felso léma megoldhatatlan, hiszen minden partíciót elfoglalhat egy-egy végtelen ciklus). Továbbá azt is minden esetben fel kell tételeznünk, hogy a rendszer nincs túlterhelve, azaz tudunk becslést adni a várakozó folyamatok számára minden idopillanatban. egy q felso Ekkor látható, hogy egy folyamatnak egy adott partícióba kerüléshez legrosszabb esetben meg kell várnia az elotte álló folyamatokat, azaz azokat, amelyeknek a számlálója nagyobb, mint az övé (legfeljebb q darab), valamint legfeljebb küszöb darab nála nagyobb folyamatot. Így korlátot adni arra, hogy egy folyamat legfeljebb mennyi ideig valóban tudunk egy felso várakozhat memóriára: (q

+ küszöb) p ideig.

Az algoritmus pszeudokódja a következo. B ´ (hely, helyigény, küszöb, méret, p, part, vár) ¨ --- ´  ´ - ´

←0 ←0 for i ← 1 to n

1

max

2

ind

3 4

do if vár[i]

5 6 7 8 9

← ind ←p vár[ind] ← 

10

part[j]

11

hely[ind]

12

=  és helyigény[i] ≤ méret[p] > küszöb és pont[i] > pont[ind]) vagy helyigény[i] > max then pont[ind] ← pont[ind] + 1 ind ← i max ← helyigény[i] else pont[i] ← pont[i] + 1

then if (pont[i]

o példánkban a 8 kB helyigényu 11.2. példa. Az eloz folyamatnak küszöb

+ 1 = k darab másikat kell

megvárnia, melyek mindegyike 2 másodpercig tart, azaz a 8 kB helyigényu folyamatnak pontosan 2k másodpercet kell várnia arra, hogy bekerüljön a 10 kB méretu partícióba.

Eddigi algoritmusainkban a folyamatok abszolút helyigényét vettük a rangsorolás alapjául, azonban ez a módszer nem igazságos: ha egy partícióba két folyamat is beleférne, és egyik sem férne bele kisebb partícióba, nem számít a méretkülönbség, hiszen elobb-utóbb úgyis ugyanabban, vagy egy másik, a vizsgáltnál nem kisebb partícióban kell elhelyezni a kisebbet is. Így az abszolút helyigény helyett annak a legkisebb partíciónak a méretét kel ha a partíciók lene gyelembe venni rangsoroláskor, amelybe befér az adott folyamat. Sot, méretük szerint növekvoen rendezve vannak, akkor elég a partíció sorszáma is a rendezett listában. Ezt a sorszámot nevezzük a folyamat ragjának. A rangok számítását a következo

462


algoritmus végzi. R- ´ ´(helyigény, méret, rang)

← R(méret) ← 1 to n do u ← 1 v ← m rang[i] ← b(u + v)/2c while rend[rang[i]] < helyigény[i] vagy rend[rang[i] + 1] > helyigény[i] do if rend[rang[i]] < helyigény[i] then u ← rang[i] + 1 else v ← rang[i] − 1 rang[i] ← b(u + v)/2c

1

rend

2

for i

3 4 5 6 7 8 9 10 11

return rang Jól látható, hogy ez az algoritmus elobb rendezi a partíciókat méretük szerint növekvo

sorrendbe, majd minden folyamathoz kiszámítja annak rangját. Ezt azonban csak kezdetben kell megtennünk, valamint akkor, ha új folyamat jön. Ez utóbbi esetben azonban már csak ciklust. A rendezést sem kell újra végreaz új folyamatokra kell végrehajtanunk a belso hajtanunk, hiszen a partíciók nem változnak a rendszerünk muködése során. Az egyetlen, két partíció közé, amelyek közül amire szükség van, a folyamat beillesztése a megfelelo a nagyobba befér, a kisebbe már nem. Ez egy logaritmikus kereséssel megoldható, ami tudjuk, hogy helyes is. Már csak a rangszámítás lépésszámát kell megmondanunk: az rol összehasonlításos rendezés

Θ(m lg m),

Θ(lg m), Θ((n + m) lg m).

a logaritmikus keresés pedig

folyamatra kell végrehajtanunk. Így az összes lépésszám

amit n darab

A rangok kiszámítása után ugyanazt kell tennünk, mint eddig. R´  ´ ----´ (hely, helyigény, méret, part, vár) ´ - ´ 1 2 3

for i

← 1 to m

do if part[i]

=0

then B ´ ---(hely, helyigény, ¨ - ´  ´ - ´ méret, i, part, vár)

algoritmusban van: nem a Különbség egyedül a folyamatot egy adott partícióba tölto méret, hanem a rang vektoron kell a feltételes maximumkeresést végrehajtani. o változatának és a rangszámítás algoritAz algoritmus helyessége az algoritmus eloz következik. Lépésszámának nagyságrendje is az eloz o változatéval musának helyességébol egyezik meg. o példát tekintve látszik, hogy a 8 kB helyigényu 11.3. példa. Az eloz és a 9 kB helyigényu folyamatok mindegyike csak a 10 kB méretu partícióba fér be, az 5 kB méretube nem. Ezért a rangjuk is meg fog lesz), így érkezési sorrendben kerülnek elhelyezésre, tehát a 8 kB méretu egyezni (ketto eloször vagy másodszor kapja meg az általa igényelt memóriaterületet.


463

B ´ ---(hely, helyigény, méret, p, part, vár ¨ - ´  ´ - ´ 1 2 3

←0 ←0 for i ← 1 to n max ind

≤ méret[p] > küszöb és pont[i] > pont[ind]) vagy rang[i] > max then pont[ind] ← pont[ind] + 1 ind ← i max ← rang[i] else pont[i] ← pont[i] + 1

4

do if vár[i] és helyigény[i]

5

then if (pont[i]

6 7 8 9

← ind ←p vár[ind] ← 

10

part[p]

11

hely[ind]

12

11.1.2. Dinamikus partíciók A dinamikus partícionálás egészen máshogy történik, mint a rögzített. Ennél a módszernél nem azt kell eldönteni, hogy egy üres partícióban mely folyamatot helyezzük el, hanem méretu azt, hogy egy folyamatot hol helyezünk el egy adott, több különbözo darabból álló memóriaterületen, azaz hol hozunk neki létre dinamikusan egy partíciót. Ebben a részben szintén az operációs rendszerek terminológiáját fogjuk használni, de az algoritmusok természetesen átfogalmazhatók alkalmazások szintjén megadott feladatok megoldására is. Ha a folyamatok elindulásuk után mind egyszerre érnének véget, nem lenne probléma, hiszen az üres memóriaterületet alulról felfelé folyamatosan tölthetnénk fel. A helyzet azonban szinte mindig bonyolultabb, hiszen a folyamatok egymástól gyakran nagy mértékben különböznek, így a futásidejük sem azonos. Ezáltal viszont az elfoglalt memóriaterület nem feltétlenül lesz folytonos, hanem a foglalt partíciók között szabad partíciók jelennek meg. Mivel a memóriabeli másolás rendkívül költséges muvelet, a gyakorlatban nem célravezeto a foglalt partíciókat a memória aljára tömöríteni. Gyakran a tömörítés nem is oldható meg a bonyolult relatív címzések miatt. Tehát a szabad terület, amelyen el kell helyezni az új Nyilvánvaló, hogy a folyamatokat egy-egy szabad parfolyamatokat, nem lesz összefüggo. tíció elején célszeru elhelyezni, az viszont kevésbé, hogy melyik szabad partícióban a sok közül. Az egyes partíciókat legegyszerubb egy láncolt listában tárolni. Természetesen sok más, az itt felsorolt algoritmusok bemutaesetleg hatékonyabb tárolási módszer is elképzelheto, A p címu tásához azonban ez elegendo. partíció elejét az eleje[p], a méretét a méret[p] tartalmazza, azt pedig, hogy mely folyamat fut az adott partícióban, a part[p] változóban tároljuk. Ha a folyamat azonosítója 0, akkor üres, különben pedig foglalt partícióról van partíció címe köv[p]. szó. A láncolt listában következo méretu Ahhoz, hogy dinamikusan létrehozzunk egy megfelelo partíciót, elobb ketté kell algoritmus. vágnunk egy legalább akkora, szabad partíciót. Ezt végzi el a következo

464


K ´  ´ -´ ´ (határ, eleje, köv, méret, p, q)

← eleje[p] + határ ← méret[p] − határ méret[p] ← határ köv[q] ← köv[p] köv[p] ← q

1

eleje[q]

2

méret[q]

3 4 5

A rögzített partíciók módszerénél látott algoritmusokkal szemben, melyek a partíciókhoz választották a folyamatokat, itt fordított szemlélettel dolgozunk. Itt a folyamatok listáján megyünk végig, és minden várakozó folyamathoz keresünk egy olyan szabad partíciót, levágjuk a szükséges darabot, és a amelybe befér. Amennyiben befért, a partíció elejébol folyamathoz rendeljük, a folyamat leírójában pedig jelöljük, hogy mely partícióban fut. Ha nem fért be egyik szabad partícióba sem, akkor az adott körben a folyamatot nem tudtuk elhelyezni. E(vár) 1

for j

2

← 1 to n =  ∗-(j)

do if vár[j]

3

then

A pszeudokódban lévo

∗ a F, N, B, K -, W és K - ´ ´

értékeket veheti fel. szabad partíció kiválasztására több lehetoség A megfelelo is kínálkozik. Az egyik, hogy olyan szabad partícióban helyezzük el a folyamatot, a partíciók listáján elindulva az elso amelyben elfér. Ez lineáris keresés segítségével könnyen megoldható. F-(f, eleje, fej, p, helyigény, köv, méret, part, vár)

← fej[P]

1

p

2

while vár[f]

3 4 5 6 7 8

=  és p ,  = 0 és méret[p] ≥ helyigény[f] then K ´  ´ -´ ´ (helyigény[f], eleje, köv, méret, p, q) part[p] ← f hely[f] ← p vár[f] ←  p ← köv[p]

do if part[p]

most is az, hogy Az algoritmus helyességéhez itt is több dolgot kell belátnunk. Az elso ne töltsünk egy folyamatot kisebb partícióba, mint amekkorába beférne. Ennek teljesülése mivel annak feltételében ez a kritérium is szerepel. következik a lineáris keresés tételébol, Ennél a módszernél is fontos, hogy egyetlen folyamat se kerüljön több partícióba, illetve egyetlen partícióba se kerüljön több folyamat. Ezen kritérium teljesülésének bizonyítása szó szerint megegyezik a rögzített partíciónál ismertetettel, azzal a különbséggel, hogy itt


465

nem a feltételes maximumkeresés, hanem a lineáris keresés tételének helyességére vezetünk vissza. Természetesen most sem elegendoek ezek a feltételek, hiszen az üres algoritmus is teljesíti mindhármat. Azt fogjuk még bizonyítani, hogy az algoritmus minden olyan folyamatot elhelyez a memóriában, amelyhez tartozik olyan partíció, amelybe befér. Ehhez ismét szükségünk lesz egy invariánsra: j darab folyamat megvizsgálása után nem létezik

≤ j, amelyre vár[k], és amelyre van olyan ≥ helyigény[k].

olyan pozitív k méret[ p]

Teljesül: Az algoritmus elején j létezik pozitív k

≤

p partíció, hogy part[ p]

=

0 és

= 0 darab folyamatot vizsgáltunk meg, így egyáltalán nem

j.

Megmarad: Ha az invariáns teljesül j-re a ciklusmag elején, akkor eloször is azt kell látnunk, hogy ugyanerre a j-re a ciklus végén is teljesülni fog. Ez nyilvánvaló, hiszen az + 1)-edik vizsgálata során, az oket tartal> 0, ami nem felel meg a F- algoritmusban találfeltételének. A ( j + 1)-edik folyamatra pedig azért fog teljesülni

j darab folyamathoz nem nyúlunk a ( j elso mazó partíciókra pedig part[ p] ható lineáris keresés

szabad blokk, azt a az invariáns a ciklusmag végén, mert ha van a feltételnek megfelelo lineáris keresés biztosan megtalálja, hiszen a lineáris keresésünk feltétele megegyezik az invariánsunk egyes partíciókon értelmezett követelményével.

Befejezodik: Mivel a ciklus egyesével halad végig egy rögzített intervallumon, biztosan be is fog fejezodni. Mivel a ciklusmag pontosan annyiszor hajtódik végre, mint ahány folyamat van, a ciklus befejezodésekor igaz lesz, hogy nem létezik olyan pozitív k n, amelyre vár[k] és amelyre van olyan p partíció, hogy part[ p]

=

0 és méret[ p]

≤ ≥

helyigény[i], azaz nem hagytunk várakozni egyetlen olyan folyamatot sem, amelyhez lenne partíció, amibe belefér.

Az algoritmus lépésszáma most is könnyen kiszámítható. Mindenképp végignézzük az n darab folyamatot. Ha például minden folyamat vár és a partíciók foglaltak, akkor az algoritmus lépésszáma

Θ(nm).

A lépésszám kiszámításánál azonban nem vettünk gyelembe néhány fontos szempontot. Az egyik az, hogy m nem állandó, hanem az algoritmus többszöri lefuttatása után várha mivel a folyamatok egymástól függetlenek, különbözo idopillanatokban tóan no, indulnak, illetve érnek véget, és méretük is jelentosen eltérhet egymásétól. Ezért gyakrabban vágunk egyesíthetnénk. Ezt a jelenséget a memória elaprózóketté egy partíciót, minthogy kettot dásának nevezzük. Tehát a legrosszabb eset lépésszáma az algoritmus többszöri futtatása Ráadásul a lineáris keresés mindig a legelso megfelelo méretu során folyamatosan no. par után sok kis partíció lesz a memóriaterület elején, amelyekbe tíciót vágja ketté, így egy ido nem tölthetjük be a folyamatok többségét. Így az átlagos lépésszám is növekedni fog. Ez utóbbi problémára megoldást jelenthet, ha a keresést nem mindig a partíciók listájának ele kezdjük, hanem annak a partíciónak a másik felétol, amelynek elso felébe a legutóbbi jérol folytatjuk mindaddig, amíg a folyamatot töltöttük, és ha a lista végére érünk, az elejérol folyamat be nem fért valamelyik partícióba, vagy újra el nem értük a kiindulási elemet, azaz ciklikusan járjuk be a partíciók listáját.

466


N-(f, fej, utolsó, méret, helyigény, köv, part, vár)

,  ← köv[utolsó[P]] else p ← fej[P] while vár[f] =  és p , utolsó[P] do if p =  then p ← fej[P] if part[p] = 0 és méret[p] ≥ helyigény[f] then K ´  ´ -´ ´ (helyigény[f], eleje, köv, méret, p, q) part[p] ← f hely[f] ← p vár[f] ←  utolsó[P] ← p p ← köv[p]

1

if utolsó[P]

2

then p

3 4 5 6 7 8 9 10 11 12 13

A N- algoritmus helyességének bizonyítása lényegében megegyezik a F- van ével, és lépésszámának nagyságrendje is azonos. Gyakorlatilag itt is lineáris keresésrol ciklusban, csupán az intervallumot forgatjuk el mindig a végén. Ez az algoritmus szó a belso azonban egyenletesen járja be a szabad területek listáját, így nem aprózza el az elejét. Ennek következtében az átlagos lépésszám is várhatóan kisebb lesz, mint a F- algoritmusé. Ha csak annyit vizsgálunk minden partícióról, hogy elfér-e benne a folyamat, akkor elofordulhat, hogy kis folyamatok számára vágunk el nagy partíciókat, így a késobb érkezo méretu nagyobb folyamatoknak már nem jut megfelelo partíció. A nagy partíciók pazarlását el tudjuk kerülni, ha minden folyamatot a legkisebb olyan partícióban helyezünk el, amelyben elfér. B-(f, fej, helyigény, köv, part, vár)

←∞ ←  p ← fej[P] while p , 

1

min

2

ind

3 4

= 0 és helyigény[ f ] ≤ méret[p] < min ←p min ← méret[p]

5

do if part[p]

6

then ind

7 8 9 10 11 12 13

p ← köv[p] ,  then K ´  ´ -´ ´ (helyigény[ f ], eleje, köv, méret, ind, q) part[ind] ← f hely[f] ← ind vár[f] ← 

if ind

Az algoritmus helyességének összes kritériuma belátható jelen esetben is, ugyanúgy, oekben. mint az eloz Az egyetlen különbség a F--hez képest, hogy most lineáris keresés helyett feltételes minimumkeresést alkalmazunk. Nyilvánvaló az is, hogy ez az algo-


467

ritmus egyetlen folyamat számára sem fog nagyobb partíciót kettévágni, mint amekkorát a közül minimálisan szükséges . meglévok Nem mindig jó azonban, ha minden folyamatot a legkisebb olyan szabad helyre teszünk be, ahová befér. Ekkor ugyanis a partíció üresen maradó része gyakran annyira kicsi, hogy az már csak nagyon kevés folyamat számára használható. Ez két okból is hátrányos. Egyrészt ezeket a partíciókat minden folyamat elhelyezésekor újra és újra megvizsgáljuk, hiszen benne vannak a szabad partíciók listájában. Másrészt pedig, hogy sok kis partíció együtt nagy területet foglalhat el, amit azonban nem tudunk hasznosítani, mert nem össze Tehát valamilyen módon ki kell védenünk azt, hogy az üresen maradó partíciók túlfüggo. ságosan kicsik legyenek. A túlságosan kicsi fogalom jelenthet egy konstanst is, de lehet az folyamat helyigényének függvénye is. (Például legalább még egyszer akkora elhelyezendo folyamat.) Mivel a korlátot az egész partílegyen a szabad terület, mint az elhelyezendo cióra, és nem a megmaradó részre vizsgáljuk, ezért ezt mindig egy a folyamattól függo függvényként kezeljük. Természetesen, ha a nincs olyan partíció, amely ennek a kiegészíto kritériumnak is megfelel, akkor helyezzük el a folyamatot a legnagyobb partícióban. Így a algoritmust kapjuk. következo K --(f, méret, fej, helyigény, köv) ´ 1 2 3 4

←∞ ←  p ← fej[P] while p ,  min ind

= 0 és méret[ p] ≥ helyigény[ f ] és < min és méret[ p] ≥ K ´ (helyigény[ f ])) vagy ind =  vagy (min < K ´ (helyigény[ f ]) és méret[ p] > min)) then ind ← p min ← méret[p] p ← köv[p]

do if part[ p]

5

((méret[ p] 6 7 8 9 10

if ind

, 

then K ´  ´ -´ ´ (helyigény[ f ], eleje, köv, méret, ind, q)

←f ← ind vár[f] ← 

11

part[ind]

12

hely[f]

13

oek. Ez az algoritmus bonyolultabb, mint az eloz Helyességének bizonyításához azt kell ciklus egy módosított feltételes minimumkeresés. A feltétel elso észrevennünk, hogy a belso része, azaz hogy part[p]

= 0 és méret[p] ≥ helyigény[f], továbbra is azt mondja, hogy olyan

partíciót keresünk, amely szabad, és belefér a folyamat. A második rész egy diszjunkció, azaz három esetben cseréljük ki a vizsgált elemet az eddig megtalálttal. Az egyik eset, amikor méret[ p]

<

min és méret[ p]

≥

K ´ (helyigény[ f ]), vagyis a vizsgált partíció mérete

legalább akkora, mint az eloírt minimális, de kisebb, mint az eddig talált legkisebb. Ha nem lenne több feltétel, akkor ez a feltételes minimumkeresés lenne, ahol a feltételek közé bevettük azt is, hogy a partíció mérete egy bizonyos korlát fölött legyen. Azonban van még két lehetoség is, amikor kicseréljük az eddig megtalált elemet az éppen vizsgálttal. Ezek közül amikor ind az elso,

= ,

olyan, amely szabad, és azaz az éppen vizsgált partíció az elso

468


elfér benne a folyamat. Erre azért van szükség, mert továbbra is megköveteljük, hogy ha van olyan szabad partíció, amelyben elfér a folyamat, akkor az algoritmus helyezze is azt el ezek valamelyikében. Végül a harmadik feltétel alapján akkor cseréljük ki az eddig megvizsgál tak közül legmegfelelobbnek talált elemet az aktuálissal, ha min és méret[p]

>

<

K ´ (helyigény[ f ])

min, vagyis az eddigi minimum nem érte el az eloírt korlátot, és az aktuális

célt szolgál. Egyrészt, ha eddig olyan elemet találtunk nagyobb nála. Ez a feltétel kettos feltételnek, az aktuális pedig igen, akkor kicseréljük csak, amely nem felel meg a kiegészíto vele, hiszen ekkor min

< K ´ (helyigény[ f ]) ≤ méret[ p], tehát az aktuális partíció mérete

nyilvánvalóan nagyobb. Másrészt, ha sem az eddig megtalált, sem az aktuális partíció mé rete nem éri el az eloírt korlátot, de az aktuálisan vizsgált jobban közelíti azt alulról, akkor min

<

méret[ p]

<

K ´ (helyigény[ f ]) teljesül, tehát ebben az esetben is kicseréljük az

eddig megtaláltat az aktuálisra. Így, ha van olyan partíció, amely legalább akkora, mint az eloírt korlát, akkor az algoritmus minden folyamatot ezek közül a legkisebbe fog helyezni, míg ha nincsenek ilyenek, akkor a legnagyobba, amelybe befér. Bizonyos feladatoknál elofordulhat, hogy kizárólag az a cél, hogy a megmaradó területek mérete minél nagyobb legyen. Ezt úgy érhetjük el, hogy minden folyamatot a legnagyobb szabad partícióban helyezünk el: W-(f, fej, méret, helyigény, köv, part, vár)

←0 ←  p ← fej[P] while p , 

1

max

2

ind

3 4

= 0 és méret[p] ≥ helyigény[f] és méret[p] > max ←p max ← méret[p]

5

do if part[p]

then ind

6 7 8 9 10 11 12 13

p ← köv[p] ,  then K ´  ´ -´ ´ (helyigény[ f ], eleje, köv, méret, ind, q) part[ind] ← f hely[f] ← ind vár[f] ← 

if ind

Az algoritmus helyességének bizonyítása hasonló a B- algoritmuséhoz, a különbség csupán annyi, hogy feltételes minimumkeresés helyett feltételes maximumkeresést hasz hogy a fennmaradó helyek mérete maximális lesz. nálunk. Az is nyilvánvaló ebbol, A W- algoritmus garantálja, hogy a legkisebb üresen maradó partíció mérete a legnagyobb lesz, azaz kevés lesz az olyan partíció, amely a legtöbb folyamat száleheto mára már túl kicsi. Ezt azáltal éri el, hogy mindig a legnagyobb partícióból vág le. Ennek az a következménye, hogy a nagy helyigényu folyamatok számára sokszor már nem is jut méretu megfelelo partíció, hanem azok várakozásra kényszerülnek a háttértárban. Hogy ez feltételt. ne így történjen, a B--hez hasonlóan itt is megfogalmazhatunk egy kiegészíto korlátot adunk. Az algoritmus igyekszik olyan partíciót Itt azonban nem alsó, hanem felso kettévágni, amelynek mérete egy bizonyos korlát alatt van. A korlát itt is a folyamat helyigényének függvénye. (Például annak kétszerese.) Ha talál ilyen partíciókat, akkor ezek


469

közül a legnagyobbat választja, hogy elkerülje a túl kis partíciók létrejöttét. Ha csak olyanokat talál, amelyek nagyobbak ennél a korlátnál, akkor viszont a minimálisat vágja ketté közülük, nehogy elvegye a helyet a nagy folyamatok elol. K --(f, fej, méret, helyigény, köv, part, vár) ´ 1 2 3 4

←0 ←  p ← fej[P] while p ,  max ind

5

= 0 és méret[ p] ≥ helyigény[ f ] és > max és méret[ p] ≤ K ´ (helyigény[ f ])) vagy ind =  vagy (max > K ´ (helyigény[ f ]) és méret[ p] < max)) then ind ← p max ← méret[p] p ← köv[p] ind ,  then K ´  ´ -´ ´ (helyigény[f], eleje, köv, méret, ind, q) part[ind] ← f hely[f] ← ind vár[f] ←  do if part[ p]

((méret[p]

6 7 8 9 10 11 12 13

if

Látható, hogy az algoritmus nagyon hasonlít a K ---hez, csupán a relációs ´ irányba. A különbség valóban nem nagy. Mindkét algoritmusjelek mutatnak az ellenkezo ban ugyanazt a két feltételt próbáljuk teljesíteni: ne keletkezzenek túl kis üres partíciók, és ne pazaroljuk el a nagy szabad partíciókat kis folyamatokra. Az egyetlen különbség, hogy e két feltétel közül melyiket vesszük gyelembe elsodlegesen, és melyiket másodlagosan. Ezt mindig az adott feladat határozza meg.

Gyakorlatok 11.1-1. Adott egy rögzített partíciókat használó rendszer két darab 100 kB, egy 200 kB és egy 400 kB méretu partícióval. Kezdetben mindegyik üres, majd egy másodperc múlva érkezik egy 80 kB, egy 70 kB, egy 50 kB, egy 120 kB és egy 180 kB helyigényu folyamat, vektorokban. A 180 kB amelyek adatai ebben a sorrendben kerülnek tárolásra a megfelelo számított ötödik másodpercben véget ér, ám ekkorra már egy 280 méretu a beérkezésétol kB helyigényu folyamat is érkezett a memóriába. Mely partíciókban mely folyamatok lesz számított hatodik másodpercben, ha feltételezzük, nek a kezdeti folyamatok beérkezésétol hogy más folyamatok nem érnek véget addig, és a L- ´  algoritmust használjuk? Mi a helyzet, ha a L-- ´ -´  , illetve ha a R´ ´  ´ - ´ ´ -

 ´ ----´  algoritmust használjuk 4 küszöbértékkel? ´ szabad partíciók ta11.1-2. Egy dinamikus partíciókat használó rendszerben a következo lálhatók meg a partíciók listájában: egy 20 kB méretu, amit egy 100 kB, egy 210 kB, egy 180 kB, egy 50 kB, egy 10 kB, egy 70 kB, egy 130 kB és egy 90 kB méretu követ, pontosan ebben a sorrendben. Legutoljára a 180 kB méretu szabad partíció elé helyeztünk el folyamatot. A rendszerbe érkezik egy 40 kB helyigényu folyamat. Melyik szabad partícióban fogja ezt elhelyezni a F-, a N-, a B-, a K --, a W-, illetve a ´

470


K -- algoritmus? ´ 11.1-3. A W- algoritmus egy hatékony megvalósítása, ha a partíciókat nem lineárisan láncolt listában, hanem bináris kupacban tároljuk. Mekkora lesz így az E algoritmus muveletigénye?

11.2. Lapcserélési algoritmusok áll. A felhasználóknak Mint már említettük, a mai számítógépek memóriája több szintbol nincs szüksége arra, hogy ezt a többszintes szerkezetet részletesen ismerjék: az operációs rendszerek egységesnek látszó virtuális memóriává szervezik a szinteket. Ennek a virtuális memóriának a kezelésére a két legelterjedtebb módszer a lapozás és a szegmentálás: elobbi egységes méretu részekre, úgynevezett lapkeretekre osztja mindkét memóriaszintet (és ennek megfeleloen a programokat is), míg a szegmentálásnál a program szegmenseknek nevezett, változó méretu részeit mozgatjuk a memóriaszintek között. Eloször az egyszeru tárgyalás érdekében tegyük fel, hogy a vizsgált számítógép memó áll: a kisebb és gyorsabb elérésu riája két szintbol rész a zikai memória (röviden memória), a nagyobb méretu és nagyobb elérési ideju rész pedig a háttérmemória. Kezdetben a zikai memória üres, a háttérmemóriában pedig egyetlen program van, áll. Feltesszük, hogy a program futása során utasításokat kell végrehajtani, amely n részbol és minden utasítás végrehajtásához egy-egy programrészre van szükségünk. részfeladatokat kell megoldani. A hivatkozási sorozat feldolgozása során a következo

1.

utasítás végrehajtásáHol helyezzük el a zikai memóriában (ha nincs ott) a következo hoz szükséges programrészt?

2.

Mikor helyezzünk el programrészeket a zikai memóriában?

3.

programrészek Hogyan szabadítsunk fel helyet a zikai memóriában az elhelyezendo számára? kérdésre az elhelyezési algoritmusok válaszolnak: a lapozásnál egyszeruen Az elso azt,

hogy akárhol ugyanis a zikai memória lapkeretei azonos méretuek és hozzáférési idejuek. A szegmentálás során a zikai memóriában programszegmensek és lyukaknak nevezett üres kérdésre a szegmenselhelyezési algoritmusok vámemóriarészek váltakoznak és az elso laszolnak. rendszerek nagy A második kérdésre az átviteli algoritmusok válaszolnak: a muköd o többségében azt, hogy igény szerint, azaz akkor kezdodik meg a programrész beolvasása a háttértárból, amikor kiderül, hogy az adott programrészre szükség van. A másik lehetoség az elobetöltés lenne, a tapasztalatok szerint azonban ez sok felesleges munkával jár, ezért nem terjedt el. A harmadik kérdésre a cserélési algoritmusok válaszolnak: lapozásnál a lapcserélési algoritmusok, amelyeket ebben az alfejezetben mutatunk be. A szegmentálásnál alkalmazott szegmenscserélési algoritmusok lényegében a lapcserélési algoritmusok ötleteit hasznosít méretének megfeleloen ják azokat a szegmensek különbözo kiegészítve. A lapozott számítógépekben mindkét szintet azonos méretu részekre úgynevezett lapkeretekre osztjuk. A zikai memória mérete m lapkeret, a háttérmemória mérete pedig n lapkeret. A paraméterek között természetes az 1

≤

m

≤

n egyenlotlenség. A gyakorlatban

11.2. Lapcserélési algoritmusok

471

n rendszerint több nagyságrenddel nagyobb, mint m. Kezdetben a zikai memória üres, a háttérmemóriában pedig egyetlen program van. Feltesszük, hogy a program futása során p lapra utasítást kell végrehajtani, és a t-edik utasítás végrehajtásához az rt lapkeretben lévo van szükségünk, azaz a program futását az R

= hr1 , r2 , . . . , r p i hivatkozási tömbbel model-

lezzük. A továbbiakban csak az igény szerinti lapozással, azon belül is csak a lapcserélési algoritmusokkal foglalkozunk. Ebben az egyszeru modellben azt tételezzük fel, hogy az utasítás végrehajtásához az rt programrészt beolvassuk, és az utasítás végrehajtásának eredményét is az rt programrészbe írjuk. Ahol szükség van arra, hogy az olvasást és írást megkülönböztessük, ott az R tömb mellett egy W

= hw1 , w2 , . . . , w p i írási tömböt is megadunk, melynek wt = .

eleme

, ha az

rt lapra írunk, egyébként wt

Az igény szerinti lapcserélési algoritmusokat szokás statikus és dinamikus algoritmusokra osztani. A program futásának elején mindkét típus teletölti a zikai memória lapkereteit lapokkal, a statikus algoritmusok azonban ezután a futás végéig pontosan m lapkeretet tartanak lekötve, míg a dinamikus algoritmusok legfeljebb m lapkeretet foglalnak le.

11.2.1. Statikus lapcserélés adatai a zikai memória mérete lapkeretben A statikus lapcserélési algoritmusok bemeno (m), a program mérete lapban (n), a program futási ideje utasításban ( p) és a hivatkozási adata pedig a laphibák száma (laphiba). sorozat (R), kimeno A statikus algoritmusok muködése a laptábla kezelésén alapul. A laptábla egy n méretu tömb, melynek i-edik sora (i

∈

[0 . . n

−

×2

1]) az i-edik lapra vonatkozik. A sor

eleme egy logikai változó (jelzobit), elso melynek értéke azt jelzi, hogy a lap az adott idopontban a zikai memóriában van-e: ha az i-edik lap a zikai memóriában van, akkor laptábla[i, 1]

=  és laptábla[i, 2] = j, ahol a

j

∈

[0 . . m

− 1] azt adja meg, hogy a lap a

zikai memória j-edik lapkeretében van. Ha az i-edik lap nincs benn a zikai memóriában, akkor laptábla[i, 1]

=  és laptábla[i, 2] értéke deniálatlan. A foglalt munkaváltozó a

zikai memória foglalt lapkereteinek számát tartalmazza. úgy számítjuk ki az f zikai címet, Ha a lapok mérete z, akkor a v virtuális címbol hogy j

= bv/zc

− zbv/zc

megadja a virtuális lap indexét, v

pedig megadja a v virtuális

címhez tartozó s eltolást. Ha az adott idopontban a j-edik lap a zikai memóriában van amit laptábla[ j, 1]

=  jelez , akkor

=

f

s

+ z · laptábla[ j, 2]. Ha viszont a

j-edik lap

nincs a zikai memóriában, laphiba lép fel. Ekkor a lapcserélési algoritmus segítségével kiválasztjuk a zikai memória egyik lapkeretét, abba betöltjük a j-edik lapot, frissítjük a laptábla j-edik sorát és azután számítjuk ki f -et. Az igény szerinti statikus lapcserélési algoritmusok muködése leírható kezdoállapottal Mealy-automatával. Ezek az automaták (Q, q0 , X, Y, δ, λ) alakban adhatók meg, rendelkezo állapotok halmaza, q0 ahol Q a vezérlo jelek halmaza, halmaza, Y a kimeno

λ:

Q

×X→Y

δ

∈

Q a kezdeti vezérlo állapot, X a bemeno jelek

: Q

×

X

→

Q az állapot-átmenetfüggvény és

a kimenetfüggvény.

Itt nem foglalkozunk az automaták leállásának formalizálásával. jelek R p A bemeno

= hr1 , r2 , . . . , r p i

(vagy R∞

= hr1 , r2 , . . .i)

sorozatát hivatkozási

sorozatnak hívjuk. Egyszerusíti az algoritmusok deniálását az S t (t

= 1, 2, . . . )

memóriaállapotok beve-

472


jel feldolgozása után az automata memóriájában (a zetése: ez az állapot a t-edik bemeno zikai memóriában) tárolt lapok halmaza. Az igény szerinti statikus lapcserélési algoritmusok esetén S 0

= ∅.

különbözik (azaz lapbevitelre volt Ha az új memóriaállapot a régitol

szükség), akkor laphiba történt. Eszerint mind a lapnak üres lapkeretbe való bevitelét, mind pedig a lapcserét laphibának nevezzük. A lapcserélési algoritmusok esetén Denning javaslatára M × Q× X

→

λ és δ helyett inkább a g

:

M × Q×Y átmenetfüggvényt használjuk, ahol M a lehetséges memóriaállapotok

halmaza. Mivel a lapcserélési algoritmusokra X

= {0, 1, . . . , n − 1} és Y =

X

∪ ∅, ez a két elem

a denícióból elhagyható és így a P lapcserélési algoritmus a (Q, q0 , gP ) hármassal adható meg. példánk az egyik legegyszerubb Elso lapcserélési algoritmus, a FIFO (First In First Out), amely a lapokat a betöltés sorrendjében cseréli. q0 Deníciója a következo:

= hi és

   (S , q, ),     gFIFO (S , q, x) = (S ∪ { x}, q0 , ),     (S \ {y1 } ∪ { x}, q, y1 ),

∈S , ha x < S , |S | = k < m , ha x < S s|S | = k = m ,

ha x

(11.1)

= hy1 , y2 , . . . , yk , xi és q00 = hy2 , y3 , . . . , ym , xi. *- algoritmus végzi. Ebben az alfejezetben A programok futtatását a következo az algoritmusok nevében a ∗ helyére mindig az alkalmazandó lapcserélési algoritmus neve ahol q

= hy1 , y2 , . . . , yk i,

0

q

kerül (FIFO, LRU OPT, LFU vagy NRU). A pszeudokódokban feltételezzük, hogy a meghívott eljárások ismerik a hívó eljárásban használt változók értékét, és a hívó eljárás hozzáfér az új értékekhez. *-F(m, n, p, R, hibaszám, laptábla)

7

←0 ←0 for i ← 0 to n − 1 do laptábla[i, 1] ←  *-  ´ ´(laptábla) for i ← 1 to p do *- ´ (laptábla, i)

8

return hibaszám

1 2 3 4 5 6

hibaszám foglalt

B A laptábla elokészítése.

B A program futtatása.

megvalósítása egy Q sorban tartja nyilván a lapok betöltési Az algoritmus következo algoritmus feladata az üres sor létrehozása, azaz a Q sorrendjét. Az elokészít o

← ∅ utasítás

végrehajtása. pszeudokódban kidob a cserélendo lap sorszáma, behoz a zikai memória A következo azon lapjának sorszáma, melybe az új lapot behozzuk.


473

FIFO- ´ (laptábla, t), 1

if laptábla[rt , 1]

2 3

then

= 

B A következo lap benn van.




=  ← laphiba + 1 if foglalt < m then S(Q, rt ) behoz ← foglalt foglalt ← foglalt + 1 if foglalt = m then kidob ← S ´ (Q) laptábla[kidob, 1] ←  behoz ← laptábla[kidob, 2] K´(behoz, kidob) B(rt , behoz) laptábla[rt , 1] ←  laptábla[rt , 2] ← behoz

4

B A következo lap nincs benn.

then laphiba

5 6 7 8 9 10 11 12 13 14 15 16

B A zikai memória nincs tele.

B A zikai memória tele van.

B Beolvasás. B Adatok frissítése.

paraA K´ eljárás feladata, hogy a cserére kiválasztott lapot kiírja a háttértárba: elso métere a honnan (a memória melyik lapkeretébol), második paramétere a hová (a háttértár melyik lapkeretébe) kérdésre ad választ. A B eljárás feladata az, hogy a következo lapkeutasítás végrehajtásához szükséges lapot a háttértárból a zikai memória megfelelo paramétere a honnan (a háttértár melyik lapkeretébol), retébe beolvassa: elso második paramétere a hová (a memória melyik lapkeretébe) A két eljárás paramétereinek megadásánál kihasználjuk, hogy a lapkeretek mérete azonos, ezért a j-edik lapkeret kezdocíme mindkét memóriában a z lapméret j-szerese. A lapcserélési algoritmusok többségének az rt hivatkozás feldolgozásához nincs szüksége az R sorozat többi elemének ismeretére, ezért a helyigény elemzésekor a sorozat helyigényével nem kell számolnunk. Kivételt képez például az OPT algoritmus. A FIFO- algoritmus helyigényét a laptábla mérete határozza meg ez a helyigény

Θ(m).

A FIFO- algoritmus futási idejét a ciklusa határozza meg. Mivel a 67.

sorokban meghívott eljárás csak konstans számú lépést végez (feltéve, hogy a sorkezelo alatt elvégezzük), ezért FIFO- futási ideje muveleteket O(1) ido

Θ( p).

Érdemes megjegyezni, hogy a lapok egy része a memóriában tartózkodás alatt nem lapokhoz használtsági bitet rendelünk, akkor az változik meg, ezért ha a memóriában lévo kiírás megtakarítható. esetek egy részében a 12. sorban lévo példánk az egyik legnépszerubb A következo lapcserélési algoritmus, az LRU (Least Recently Used), amely a legrégebben használt lapot cseréli.

= hi és  000   (S , q , ),     gLRU (S , q, x) = (S ∪ { x}, q0 , ),     (S \ {y1 } ∪ { x}, q, y1 ),

q0 Ennek deníciója a következo:

= hy1 , y2 , . . . , yk i, q0 = hy1 , y2 , . . . , yk , xi, q00 = hy2 , y3 , . . . , ym , xi és ha = hy1 , y2 , . . . , yk−1 , . . . , yk+1 . . . ym , yk i.

ahol q q

000

∈S , < S , |S | = k < m , ha x < S s|S | = k = m , ha x

(11.2)

ha x

x

=

yk , akkor

474

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal) megvalósítása nem igényel elokészítést. Az LRU következo Az utolsó-hiv[0 . . n

− 1]

tömbben tartjuk nyilván az egyes lapok utolsó használatának idopontját, és amikor cserélni kell, lineáris kereséssel határozzuk meg a legrégebben használt lapot. LRU- ´ (laptábla, t) 1


2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

=  B A következo lap benn van. ←t laptábla[rt , 1] =  B A következo lap nincs benn. then laphiba ← laphiba + 1 if foglalt < m B A zikai memória nincs tele. then behoz ← foglalt foglalt ← foglalt + 1 if foglalt = m B A zikai memória tele van. then kidob ← rt−1 for i ← 0 to n − 1 do if laptábla[i, 1] =  és utolsó-hiv[i] < utolsó-hiv[kidob] then kidob ← utolsó-hiv[i] laptábla[kidob, 1] ←  behoz ← laptábla[kidob, 2] K´(behoz, kidob) B(rt , behoz) B Beolvasás. laptábla[rt , 1] ←  B Adatok frissítése. laptábla[rt , 2] ← behoz utolsó-hiv[rt ] ← t then utolsó-hiv[rt ]

if

Ha most n és p értékét is változónak tekintjük, akkor az LRU- ´  1011. sorában lineáris keresés miatt az LRU- algoritmus futási ideje szereplo

Θ(n p).

algoritmus optimális abban az értelemben, hogy az adott feltételek (azaz A következo lapok rögzített m és n) mellett minimális számú laphibát okoz. Ez az algoritmus a bennlévo közül azt a lapot választja a cseréhez, amelyikre a legkésobb lesz újra szükség (ha több olyan lap is van, amelyre többet nincs szükség, akkor közülük a legkisebb memóriacímen lapot választjuk). lévo Elokészítésre ennek az algoritmusnak sincs szüksége. OPT- ´ (t, laptábla, R) 1 2 3 4

if laptábla[rt , 1] then

= 




if laptábla[rt , 1] then laphiba

=  ← laphiba + 1



475

<m

B A zikai memória nincs tele.

5

if foglalt

6

← f oglalt foglalt ← foglalt + 1 if foglalt = m then OPT-(t, R) laptábla[kidob, 1] ←  behoz ← laptábla[kidob, 2] K´(behoz, kidob) B(rt , behoz) laptábla[rt , 1] ←  laptábla[rt , 2] ← behoz then behoz

7 8 9 10 11 12 13 14 15



lap A 9. sorban hívott OPT- eljárás feladata, hogy meghatározza a cserélendo indexét. OPT-(t, R)

13

←0 B Elokészítés. ← 0 to m − 1 do keret[ j] ←  s ← t+1 B A lapkeretek védettségének meghatározása. while s ≤ p és laptábla[r s , 1] =  és keret[laptábla[r s , 2]] =  és védve < m − 1 do védve ← védve + 1 keret[r s ] ←  s ← s+1 kidob ← m − 1 B A cserélendo lapot tartalmazó keret meghatározása. j ← 0 while keret[ j] =  do j ← j + 1 kidob ← j

14

return kidob

1 2 3 4 5 6 7 8 9 10 11 12

védve for j

A keret[0 . . m tokat: keret[ j]

− 1] tömbben tároljuk a zikai memóriában lévo lapokra vonatkozó ada=  azt jelzi, hogy a j-edik keretben tárolt lap a közeli felhasználás miatt

A védve változóban pedig azt tartjuk számon, hány védett lapról tuvédve van a cserétol. dunk. Ha már találtunk m

− 1 védett lapot, vagy R végére értünk, akkor a zikai memória

védetlen lapot választjuk cserélendo lapnak. legkisebb címén lévo Mivel az OPT algoritmusnak szüksége van a teljes R tömbre, ezért tárigénye

Θ( p).

részét kell Mivel az OPT- algoritmus 58. sorában legfeljebb az R tömb hátralévo átnézni, ezért az OPT- algoritmus futási ideje O( p ). 2

LFU (Least Frequently Used) algoritmus a legritkábban használt lapot A következo cseréli. A lapcsere egyértelmuségének érdekében feltesszük, hogy azonos gyakoriság esetén a zikai memória legkisebb címén tárolt lapot cseréljük.

476

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal) A gyakoriság[0 . . n

− 1]

tömb segítségével tartjuk nyilván, hogy a zikai memóriába

való betöltésük óta hányszor hivatkoztunk az egyes lapokra. Elokészítésre ennek az algoritmusnak sincs szüksége, LFU- ´ (laptábla, t) 1


2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

=  B A következo lap benn van. ← gyakoriság[rt ] + 1 laptábla[rt , 1] =  B A következo lap nincs benn. then laphiba ← laphiba + 1 if foglalt < m B A zikai memória nincs tele. then behoz ← foglalt foglalt ← foglalt + 1 if foglalt = m B A zikai memória tele van. then kidob ← rt−1 for i ← n − 1 downto 0 do if laptábla[i, 1] =  és gyakoriság[i] ≤ gyakoriság[kidob] then kidob ← utolsó-hiv[i] laptábla[kidob, 1] ←  behoz ← laptábla[kidob, 2] K´(behoz, kidob) B(rt , laptábla[kidob, 2]) B Beolvasás. laptábla[rt , 1] ←  B Adatok frissítése. laptábla[rt , 2] ← behoz gyakoriság[rt ] ← 1 then gyakoriság[rt ]

if

ciklus magját legfeljebb n-szer kell Az LFU- ´  algoritmus 1113. sorában lévo végrehajtani, ezért az algoritmus futási ideje O(n p). lapokhoz tartozik két álBizonyos operációs rendszerekben a zikai memóriában lévo lapotbit. A hivatkozott bit minden hivatkozáskor (olvasáskor és íráskor) a piszkos bit pedig minden módosításkor (azaz íráskor) minden lap mindkét állapotbitjét



-ra

állítódik,

lesz. A program indításakor

-ra állítjuk. Az operációs rendszer bizonyos idokö-ra állítja azoknak a lapoknak a piszkos bitjét, ame-

zönként (például k utasításonként)

o átállítás óta nem volt hivatkozás. lyekre az eloz A két állapotbit alapján a lapok négy osztályba sorolhatók: a nulladik osztályba a nem hivatkozott és nem módosított, az elso osztályba a nem hivatkozott, módosított, a második osztályba a hivatkozott és nem módosított és végül a harmadik osztályba a hivatkozott és módosított lapok kerülnek. Az NRU (Not Recently Used) algoritmus a legkisebb indexu, nemüres osztályból vá lapot. A determinisztikusság érdekében feltesszük, hogy az NRU algoritlaszt cserélendo mus minden osztály elemeit egy sorban tárolja. Ennek az algoritmusnak az elokészítése a jelzobiteket tartalmazó hivatkozott és piszkos tömbök

 értékekkel való feltöltését és a négy üres sor létrehozását jelenti.


477

NRU-  ´ ´(n) 1

for i

← 0 to n − 1 ←  ← 

2

do hivatkozott[ j]

3

piszkos[ j]

4

Q0

5

Q1

6

Q2

7

Q3

←∅ ←∅ ←∅ ←∅

NRU- ´ (hivatkozott, piszkos, k, R, W ) 1


2

then if W [rt ]

3 4 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 24

←  =  then laphiba ← laphiba + 1 if foglalt < m then behoz ← foglalt foglalt ← foglalt + 1 hivatkozott[rt ] ←  if W [rt ] =  then piszkos[rt ] ←  if foglalt = m then NRU-(t, kidob) laptábla[kidob, 1] ←  behoz ← laptábla[kidob, 2] if piszkos[kidob] =  then K´(behoz, kidob) B(rt , laptábla[kidob, 2]) laptábla[rt , 1] ←  laptábla[rt , 2] ← behoz t/k = bt/kc then for i ← 0 to n − 1 do if hivatkozott[i] =  then piszkos[i] ← 


then piszkos[rt ]


5

21

=  = 

if

B A következo lap nincs benn. B A zikai memória nincs tele.



lap kiválasztása azon alapul, hogy a zikai memóriában lévo lapokat négy A cserélendo sorba (Q0 , Q1 , Q2 , Q3 ) soroljuk.

478


NRU-(ido) 1

for i

2 3 4 5 6 7 8 9

if

10 11 12 13 14 15 16

← 0 to n − 1

B Lapok osztályozása.

=  then if piszkos[i] =  then S(Q1 ,i) else S(Q2 ,i) else if piszkos[i] =  then S(Q3 ,i) else S(Q4 ,i) Q1 , ∅ then kidob ← S ´ (Q1 ) else if Q2 , ∅ then kidob ← S ´ (Q2 ) else if Q3 , ∅ then kidob ← S ´ (Q3 ) else kidob ← S ´ (Q4 ) do if hivatkozott[i]

B Cserélendo lap kiválasztása.

return kidob A F-NFU algoritmus helyigénye

Θ(m), futási ideje pedig Θ(n p).

A M - ´ ´  algoritmus a FIFO módosítása. Lényege, hogy ha a FIFO szerint cse lapnak a hivatkozott változója hamis, akkor kidobjuk. Ha viszont a hivatkozott válrélendo tozója

,

akkor azt

-ra

a sor végére tesszük, majd állítjuk és a lapot a sor elejérol

ezt ismételjük addig, míg olyan lapot nem találunk a sor elején, amelynek a hivatkozott változója

.

Ennek az ötletnek egy hatékonyabb megvalósítása az Ó algoritmus, amely egy cikli m lap indexét, és egy mutatót használ arra, hogy a kus listában tárolja a memóriában lévo cserélendo lapot kijelölje. következo A LIFO (Last In First Out) algoritmus lényege, hogy a zikai memória igény szerinti feltöltése után mindig az utoljára beérkezett lapot cseréljük, azaz a kezdeti szakasz után m

− 1 lap állandóan a memóriában van és az összes csere a legnagyobb címu lapkeretben

történik.

11.2.2. Dinamikus lapcsere hogy egyidejuleg A számítógépek többségére az jellemzo, több program hajtódik bennük lokálisan és végre. Ha ezekben a gépekben lapozott virtuális memória van, az kezelheto globálisan is. Elobbi esetben minden program igényét külön kezeljük, utóbbi esetben egy program helyigénye más programok rovására is kielégítheto. o pontban A lokális kezelést megvalósító statikus lapcserélési algoritmusokat az eloz tárgyaltuk. Most két dinamikus algoritmust mutatunk be. A WS (Working Set) algoritmus alapja az a tapasztalat, hogy a programok futása során belül csak a lapjaik kis részére van szükség. Ezek a lapok alkotják az viszonylag rövid idon adott idointervallumhoz tartozó munkahalmazt. Ezt a munkahalmazt deniálhatjuk például úgy, mint az utolsó h utasítás során használt lapok halmazát. Az algoritmus muködését elképzelhetjük úgy, hogy egy h hosszúságú

ablakot csúsztatunk végig az R hivatkozási tömbön, és mindig az ablakban látható lapokat tartjuk a memóriában.


479

WS(laptábla, t, h) 1 2


= 


then WS-(t)

3

K´(laptábla[kidob, 2], kidob)

4

laptábla[rt , 1]

5

laptábla[rt , 2]

6 7

if t

←  ← kidob

>h

B Benn marad-e rt−h a memóriában? ←h−1 while r j , rt−h és j < t do j ← j + 1 if j > t then laptábla[rt−h , 1] ← 

then j

8 9 10 11

A WS algoritmus elemzésekor az egyszeruség kedvéért feltesszük, hogy h

≤ n,

így

lapok memóriában tárolása, ha mind a h hivatkozás akkor is megoldható az ablakban lévo (a gyakorlatban a hivatkozási sorozatban lévo sok ismétlodés különbözo miatt h rendszerint lényegesen nagyobb, mint n). algoritmus, amely a A WS- algoritmus lehet például egy olyan statikus lapcserélo összes lap közül azaz memóriában lévo például erre a célra a

lapot. Ha globálisan választja ki a cserélendo

Θ( p) futási ideju FIFO algoritmust használjuk, akkor WS futási ideje

mivel legrosszabb esetben minden utasítással kapcsolatban meg kell vizsgálni az ablakban lapokat lévo

Θ(h p).

A PFF (Page Frequency Fault) algoritmus is használ egy paramétert. Ez az algoritmus számon tartja az utolsó laphiba óta végrehajtott utasítások számát. Ha ez a szám egy újabb laphiba elofordulásakor kisebb, mint az elore megadott d paraméter értéke, akkor a program kap egy új lapkeretet a hibát okozó lap betöltéséhez. Ha azonban a laphiba nélkül végrehaj tott utasítások száma eléri a d értéket, akkor elobb elveszünk a programtól minden olyan lapkeretet, amely az utolsó laphiba óta nem használt lapot tartalmaz, és csak ezután kap a program egy lapkeretet a hibát okozó lap tárolására. PFF(laptábla, t, d)

←0 ← 1 to n

1

számláló

2

for i

3

do laptábla[i, 1]

4

hivatkozott[i]

5 6 7 8 9 10 11 12 13 14

for j

← 1 to

B Elokészítés.

←  ← 

p

do if laptábla[rt , 1]

=  then számláló ← számláló + 1 else PFF-(t, d , kidob) K´(laptábla[kidob, 2], kidob) laptábla[rt , 1] ←  for i ← to n do if hivatkozott[i] =  then laptábla[i, 1] ←  hivatkozott[i] ← 

B Futtatás.

480


Gyakorlatok hivatkozási sorozatot: R 11.2-1. Tekintsük a következo

= h1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3,

ha a FIFO, LRU és OPT algoritmust alkal7, 6, 3, 2, 1, 2, 3, 6i. Hány laphiba fordul elo, mazzuk k (1

≤ k ≤ 8) lapkeretes zikai memóriájú gépen?

11.2-2. Valósítsuk meg a FIFO algoritmust úgy, hogy a Q sor helyett egy mutatót kezelünk, lapbetöltésre váró lapkeretére mutat. amely mindig a zikai memória következo, 11.2-3. Milyen elonyökkel és hátrányokkal járna, ha a lapcserélési algoritmusok a laptábla

× 2 méretu laptérképet is kezelnének, melynek j-edik sora a zikai memória ∈ [0 . . m − 1]) lapkeretének foglaltságát jelezné, illetve tartalmát adná meg? Írjuk meg és elemezzük a M - ´ ´ , az Ó és a LIFO algoritmusok pszeu-

mellett egy m j-edik ( j 11.2-4.

dokódját. 11.2-5. Csökkentheto-e az NFU futási idejének nagyságrendje, ha nem minden laphiba után osztályozzuk a lapokat, hanem folyamatosan karbantartjuk a négy sort? 11.2-6. Ismert az NRU algoritmus olyan NFU' változata is, amely a lapok osztályozására lapot a legkisebb indexu 4 halmazt használ, és a cserélendo nemüres halmazból véletlenül választja. Írjuk meg az ehhez szükséges H és H pszeudokódját ´ muveletek és elemezzük az NFU' algoritmus eroforrásigényét.

11.2-7.? Terjesszük ki úgy a lapcserélési automata denícióját, hogy a véges hivatkozási sorozat utolsó elemének feldolgozása után megálljon. Útmutatás. Egészítsük ki a bemeno jelek halmazát egy

sorozat vége szimbólummal.

11.3. Anomáliák lapcserélési algoAmikor az 1960-as évek elején az IBM Watson Kutató Intézetében az elso ritmusokat tesztelték, nagy meglepetést okozott, hogy bizonyos esetekben a zikai memória méretének növelése a programok futási idejének növekedését okozta. A számítógépes rendszerekben anomáliának nevezzük azt a jelenséget, amikor egy feladat megoldásához több eroforrást felhasználva rosszabb eredményt kapunk. a FIFO lapcserélési algoritmussal, a második a Három konkrét példát említünk. Az elso processzorok ütemezésére használt L - algoritmussal, a harmadik az átfedéses ´ ¨ memóriájú számítógépekben folyó párhuzamos programvégrehajtással kapcsolatos. Érdemes megjegyezni, hogy a három példa közül kettoben is az a ritka eset fordul elo, hogy az anomália mértéke tetszolegesen nagy lehet.

11.3.1. Lapcsere Legyenek m, M, n és p pozitív egészek (1 A

= {a1 , a2 , . . . , an }

egy véges ábécé. A

k

≤

m

≤

M

≤

n

< ∞),

k nemnegatív egész,

az A feletti, k hosszúságú, A

∗

pedig az A feletti

véges szavak halmaza. lapkereLegyen m egy kis, M pedig egy nagy számítógép zikai memóriájában lévo lapok száma (mindkét számítógépben), A a lapok tek száma, n a háttérmemóriában lévo halmaza. o alfejezetben deniáltuk. Mivel ebben a pontban csak A FIFO algoritmust már az eloz

11.3. Anomáliák

481

elhagyhatjuk a lapcserélési algoa FIFO lapcserélési algoritmust vizsgáljuk, a jelölésekbol ritmus jelét. A laphibák számát fP (R, m)-vel jelöljük. Anomáliának nevezzük azt a jelenséget, amikor M

>

m és fP (R, M)

>

fP (R, m). Ekkor az fP (R, M)/ fP (R, m) hányados az anomália

mértéke. R

A P algoritmus hatékonyságát az E P (R, m) lapozási = hr1 , r2 , . . . , r p i véges hivatkozási sorozatra az E P (R, m)

R

fP (R, m)

=

p

sebességgel jellemezzük, amit az

,

(11.3)

= hr1 , r2 , . . .i végtelen hivatkozási sorozatra pedig a E P (R, m)

módon deniálunk, ahol Rk Legyen 1

≤

< n = 1.

m

Ekkor E FIFO (C, m)

= lim inf

fP (Rk , m)

k→∞

(11.4)

k

= hr1 , r2 , . . . , rk i.

és C

=

∗

(1, 2, . . . , n)

egy végtelen ciklikus hivatkozási sorozat.

Ha végrehajtjuk az R = h1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5i hivatkozási sorozatot, akkor az = 3 esetben 9, az m = 4 esetben pedig 10 laphibát kapunk, így fFIFO (R, M)/ fFIFO (R, m) = 10/9. m

szükséges és elégséges feltételt adták az anomáBélády, Nelson és Shedler a következo lia létezésére. 11.1. tétel. Akkor és csak akkor létezik olyan R hivatkozási sorozat, amelyre a FIFO lapcserélési algoritmus anomáliát okoz, ha m

<

M

< 2m − 1.

bizonyították. Az anomália mértékével kapcsolatban pedig a következot

< M < 2m − 1, akkor hr1 , r2 , . . . , r p i hivatkozási sorozat, amelyre

11.2. tétel. Ha m

tetszoleges

f (R, M) f (R, m)

>

0 számhoz létezik olyan R

>2− .

=

(11.5)

sejtették. Bélády, Nelson és Shedler a következot 11.3. sejtés. Tetszoleges R hivatkozási sorozatra és M fFIFO (R, M) fFIFO (R, m)

> m ≥ 1 memóriaméretekre

≤2.

(11.6)

példával cáfolhatjuk. A sejtést például a következo

= 5, M = 6, n = 7, k ≥ 1 és R = U V k , ahol V = (1, 2, 3, 4, 5, 6, 7)3 és U = h1, 2, 3, 4, 5, 6, 7, 1, 2, 4, 5, 6, 7, 3, 1, 2, 4, 5, 7, 3, 6, 2, 1, 4, 7, 3, 6, 2, 5, 7, 3, 6, 2, 5i. Ha az U végrehajtási sorozatot m = 5 lapkeretet tartalmazó zikai memóriával hajtjuk állapotot végre, akkor 29 laphiba következik be és a feldolgozás a h7, 3, 6, 2, 5i vezérlo Legyen m

eredményezi. Ezután a V hivatkozási sorozat minden végrehajtása 7 további laphibát okoz

482


T1 /3

T2 /2

T9 /9

T5 /4

P1

S1 :

T3 /2

T4 /2

T6 /4

T1

T9

P2

T2

T4

T5

P3

T3

-

T6

0

1

2

11.1. ábra. A

T8 /4

T7 /4

τ1

3

4

5

T7 T8

6

7

8

9

10

11

12

taszkrendszer, és annak optimális ütemezése.

állapotot eredményezi. és ugyanazt a vezérlo Ha az U sorozatot M

= 6 lapkeretet tartalmazó zikai memóriával hajtjuk végre, akkor

állapotot és 14 laphibát kapunk. Ezután V minden végrehajtása 21 a h2, 3, 4, 5, 6, 7i vezérlo állapotot eredményezi. további laphibát és ugyanazt a vezérlo Ak

= 7 választással az anomália mértéke (14 + 7 × 21)/(29 + 7 × 7) = 161/78 > 2. Ha

k értékét növeljük, akkor az anomália mértéke tart a háromhoz. tétele szerint az anomália Ennél több is igaz: Fornai Péter és Iványi Antal következo mértéke tetszolegesen nagy lehet. 11.4. tétel. Tetszolegesen nagy L számhoz megadhatók olyan m, M és R paraméterek, melyekre f (R, M) f (R, m)

>

L

.

(11.7)

11.3.2. Listás ütemezés Tegyük fel, hogy n programot akarunk végrehajtani egy p processzoros láncon. A végre hajtásnak gyelembe kell vennie a programok közötti megelozési relációt. A processzorok mohók, és a végrehajtás egy adott L lista szerint történik. E. G. Coffman jr. 1976-ban leírta, hogy a p processzorszám csökkenése, az egyes prog ramok végrehajtásához szükséges lépések ti számának csökkenése, a megelozési korlátozások enyhítése és a lista változtatása külön is anomáliát okozhat. Legyen a programok végrehajtásának lépésszáma

τ, a megelozési reláció <, a lista L és

a programok közös listás végrehajtásához szükséges lépések száma p azonos processzoron

0

0 <0 ⊆< megelozési reláció, a τ ≤ τ lépésszám vektor és a 0 0 0 0 0 processzorszám esetén a lépésszám legyen C ( p , L , < , τ ).

C( p, L, <, τ). Az L lista, a

0

p

≥

p

Az anomália mértékét ezúttal relatív lépésszámmal jellemezzük. típusaira. Eloször négy példát mutatunk az anomália különbözo 11.4. példa. Tekintsük az alábbi S 1 ütemezését három (m

=

τ1

taszkrendszert, és annak az L

=

(T 1 , T 2 , . . . , T 9 ) listával kapott

3) azonos processzoron. Ekkor (lásd 11.1. ábra) C max (S 1 )

könnyen belátható, hogy optimális érték.

=

12, amirol

11.3. Anomáliák 11.5. példa.

483 τ1

Ütemezzük az elobbi

hT1 , T2 , T4 , T5 , T6 , T3 , T9 , T7 , T8 i

=

taszkrendszert m

3 azonos processzorra az L

0

listával. Ekkor a kapott S 2 ütemezésre (lásd 11.2. ábra) C max (S 2 )

= =

14. P1 S2 :

T1

T3

T2

T5

T7

P3

T4

T6

T8

0

1

2

3

11.2. ábra. A

Ütemezzük a τ1 = 15 (lásd 11.3. ábra).

11.6. példa. C max (S 3 )

4

τ1

5

6

7

8

9

10

11

taszkrendszert az L listával m

0

=

T8

-

T5

T9

P3

T3

T6

-

P4

T4

T7 2

3

4

11.3. ábra.

τ1

14

4 processzorra. Az eredmény

T2

1

12

0

P2

0

13

taszkrendszer ütemezése az L lista esetén.

T1

P1 S3 :

T9

P2

5

6

7

8

9

0

ütemezése az L listával m

10

11

13

12

14

15

= 4 processzorra.

τ1 -ben a végrehajtási idoket eggyel. Ütemezzük az így kapott τ2 taszkrend= 3 processzorra. Az eredmény: Cmax (S 4 ) = 13 (ld. 11.4. ábra).

11.7. példa. Csökkentsük szert az L listával m P1 S4 :

T1

P2

T2

P3

T3 0

T5 T4 -

1

τ1

3

τ2

4

5

6

7

ütemezése az L listával m

8

9

10

11

12

13

= 3 processzorra.

taszkrendszerben a precedencia-korlátozásokat: hagyjuk el a (T4 , T5 ) és

a (T4 , T6 ) éleket a gráfból. Az így kapott látható: C max (S 5 )

T9

T7 2

11.4. ábra.

11.8. példa. Enyhítsük a

T8

T6

τ3

taszkrendszer S 5 ütemezésének eredménye a 11.5. ábrán

= 16.

példa azt mutatja, hogy a maximális befejezési ido növekedése nem csak A következo a lista rossz megválasztása miatt következhet be. 11.9. példa. Legyen a C max (S OPT )

= 19.

τ taszkrendszer és annak S OPT optimális ütemezése a 11.6. ábra szerinti. Ekkor

484

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal) P1

S5 :

T1

P2

T2

P3

T3 0

T6

T9

T4

T7

-

T5

1

2

3

T8

4

11.5. ábra. A

5

τ3

6

7

8

9

10

taszkrendszer ütemezése m

11

12

13

14

15

16

= 3 processzorra.

T2 /2

T1 /4

T3 /2 T4 /5

T5 /5

T6 /10

T7 /10

S OPT :

P1

T1

P2

T2

T3

T4

T6

T5

T7

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

11.6. ábra. A

τ taszkrendszer, és annak S OPT

ütemezése két processzoron.

Könnyen belátható, hogy ha most a végrehajtási idoket 1-gyel csökkentjük, akkor a kapott taszkrendszeren C max (S 6 )

S6 :

P1

= 20 értéknél egyetlen listával sem érhetünk el jobbat (lásd a 11.10. ábrát).

T1

P2 T2 0

T4

T5

T3

1

τ0

T7

T6

2

3

4

5

6

11.7. ábra. A

τ0

7

8

9

10

11

12

13

14

15

16

17

18

19

20

taszkrendszer optimális listás ütemezése.

relatív korlátot adunk meg. Ezen példák után az ütemezési paraméterek hatását jellemzo Tegyük fel, hogy adott egy L, a

0

τ

τ és τ0

0

taszkrendszerekre T

=

T,

<0 ⊆ <, t0 ≤

τ taszkrendszert

taszkrendszert pedig egy L lista alkalmazásával ütemezzük mégpedig elob-

0

bit m, utóbbit pedig m azonos processzorra. Az így kapott S ill. S C(S )

t. A

0

= C és C(S

0

)

=C

0

0

ütemezésekre legyen

.

11.5. tétel (ütemezési korlát). A fenti feltételek mellett C

0

C

≤1+

m

−1

m0

0

.

(11.8)

0

paraméterekhez (S -höz) tartozó D ütemezési diagramot. Bizonyítás. Tekintsük a vesszos

11.3. Anomáliák

485

0

Legyen a [0, C ) intervallum pontjainak két A és B részhalmazának deníciója a követ A kezo:

0 = {t ∈ [0, C 0 ) | a t idopontban minden processzor foglalt}, B = [0, C ) \ A. Érdemes

megemlíteni, hogy mindkét halmaz diszjunkt, félig nyílt (balról zárt, jobbról nyílt) intervallumok uniója.

0

0

Legyen T j1 egy olyan taszk, melynek a végrehajtása D szerint az C idopontban fejezodik be (azaz f j1

=C

0

pontja, ). Ekkor két lehetoség van: a T j1 taszk s j1 kezdopontja vagy B belso

vagy nem az. pontja, akkor B deníciója szerint van olyan processzor, amelyre Ha s j1 B belso

1.

mellett igaz, hogy az [s j1

2.

− ε, s j

ha van olyan T j2 taszk, amelyre T j2 fordulhat elo,

<0

T j1 és f j2

pontja B-nek, akkor vagy s j1 Ha s j1 nem belso

=

0 (b eset), vagy s j1

=

B-nek s j1 -nél kisebb eleme (c eset), akkor legyen x1 egyébként pedig legyen x1

=

ε>

0

) intervallumban nem dolgozik. Ez azonban csak úgy 1

>

0 (d eset). Ha x1

=

sup{ x

s j1 (a eset).

|

x

<

>

0. Ha van

s j1 és x

∈

B},

0, akkor A és B konstrukciójából

következik, hogy van olyan processzor, amelyhez található olyan T j2 taszk, amelynek ebben az intervallumban még tart a végrehajtása, és amelyre T j2 A két esetet összegezve tehát vagy van olyan T j2 y

∈

A (a vagy c eset), vagy pedig minden x

<

<0

<0

T j1 .

T j1 taszk, amelyre y

s j1 számra x

∈

A és x

<

∈

[ f j2 , s j1 ) esetén

0 egyike fennáll (b

vagy d eset). Ezt az az eljárást ismételve olyan T jr , T jr−1 , . . . , T j1 taszklánchoz jutunk, amelyre igaz, hogy x

<

s jr esetén vagy x

∈

<

A vagy x

0. Ezzel megmutattuk, hogy léteznek olyan taszkok,

amelyekre

<0

T jr továbbá minden t

∈

T jr−1

<0 · · · <0

T j1 ,

(11.9)

B idopontban van olyan processzor, amelyik dolgozik, és éppen a lánc

következik, hogy valamelyik elemét hajtja végre. Ebbol

X

0

t ( φ)

≤ (m0 − 1)

φ∈S 0 ahol

φ-vel

r X

0

tj

k

,

(11.10)

k=1

0

összes az üres periódusokat jelöltük, és így a bal oldali összeg az S -ben lévo

üres periódusra vonatkozik. (11.9) és

<0 ⊆ < alapján T j < T j − < · · · < T j r

r 1

C

1

, és így

r X

≥

t jk

≥

r X

k =1

Mivel mC

≥

és C

0

=

1 m0

k

.

(11.11)

,

(11.12)

k =1

n X

ti i=1

0

tj

≥

n X

0

ti i=1

  n X  X 0 ,  ti0 + t (φ) i=1

φ∈S 0

486

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal) Tm+1

T1

S7 :

T2

Tm+2

.. .

.. .

Tm−1

T2m−1 Tm

11.8. ábra. Az L

= (T1 , . . . , Tn ) listához tartozó S 7 (τ4 ) ütemezés.

Tm+1

Tm

Tm+2

-

.. .

.. .

S8 :

T2m−1 T1

T2

-

...

Tm−1

-

0

11.9. ábra. Az L listához tartozó S 8 (τ4 ) ütemezés.

így (11.10), (11.11) és (11.12) alapján C ahonnan C

0

/C ≤ 1 + (m −

0

≤

1 m0

mC

+ (m0 − 1)C ,

0 1)/m .

példák nemcsak azt mutatják meg, hogy a tételben szereplo korlát a leA következo legjobb, hanem azt is, hogy az adott korlát (legalábbis aszimptotikusan) a paraméterek heto bármelyikének változtatásával elérheto. 11.10. példa. Ebben a példában a lista változik, zok:

     =   

= 1, . . . , m − 1 , =m, m − 1, ha i = m + 1, . . . , 2m − 1 . Ha ezt a τ4 taszkrendszert m processzorra az L = (T1 , . . . , T2m−1 n) listával ütemezzük, akkor 11.8. S 7 (τ4 ) optimális ütemezést kapjuk. ábrán lévo 0 Ha az L lista helyett az L = (Tm+1 , . . . , T2m−1 , T1 , . . . , Tm−1 , Tm ) listát alkalmazzuk, akkor a 11.9. ábrán látható S 8 (τ4 ) ütemezést kapjuk. 0 0 Ebben az esetben C = (S 7 ) = m, C = (S 8 ) = 2m − 1, így C /C = 2 − 1/m; tehát a lista változtatásával elértük, hogy a tétel állításában az egyenloség teljesüljön, vagyis a ≤ jel jobb oldalán ti

1,

ha i

m,

ha i

a követke< üres, m tetszoleges. A végrehajtási idok

kifejezés nem csökkentheto. szereplo

11.11. példa. Ebben a példában a végrehajtási idoket csökkentjük. A lista mindkét esetben az L = 0 L = hT1 , . . . , T3m i. Itt és a fejezet további részében ε tetszoleges kis pozitív számot jelöl. Az eredeti végrehajtási idoket at

= (t1 , . . . , tn ) vektor tartalmazza, ahol   2ε, ha i = 1, . . . , m ,    ha i = m + 1, . . . , 2m , ti =  1,    m − 1, ha i = 2m + 1, . . . , 3m .

11.3. Anomáliák

487

T1

T2

Tm−1

Tm

T2m−1

T2m

...

T2m+2 T2m+3

...

T3m

...

Tm+1

Tm+2

...

T2m+1 11.10. ábra.

Az új végrehajtási idok

( 0 ti

ti

=

− ε,

ti ,

τ5

és

ha i ha i

τ05

azonos gráfja.

= 1, . . . , m − 1 , = m, . . . , 3m .

0 A τ5 , illetve a módosított τ5 taszkrendszer megelozési gráfját 11.10. ábra mutatja, az S 9 (τ5 ) (optimális) 0 0 ütemezés és az S 10 (τ5 ) ütemezés pedig 11.11. ábrán látható. Itt C = C max (S 9 (τ5 )) = m + 2ε és C =

S9 :

T1

Tm+1

T2m+1

T2

Tm+2

T2m+2

.. .

.. .

Tm−1 Tm

S 10 :

.. .

T2m−1

T3m−1

T2m

T3m

T1

T2m+2

T2

T2m+3

.. .

T2m−1

T2m+1 -

.. . T3m

Tm−1 Tm

Tm+1

.. . ...

T2m−1

-

0

11.11. ábra. Az S 9 (τ5 ) és S 10 (τ ) ütemezések. 5

0 C max (S 10 (τ5 )

= 2m − 1 +ε, ezért ε csökkenésével C 0 /C tart a 2 − 1/m értékhez (limε→0 C 0 /C = 2 − 1/m).

korlátot. Tehát a végrehajtási idoket változtatva tetszolegesen megközelíthetjük a tételben szereplo

11.12. példa.

Ebben a példában a megelozési korlátozásokat gyengítjük. A

τ6

taszkrendszer meg-

= ε, ti = 1, ha = 1, . . . , m2 − m + 1, és tm −m+2 = m. τ6 -nak az L = (T1 , . . . , Tm −m+2 ) listához tartozó, optimális korlátozás elhagyásával kapjuk S 11 (τ6 ) ütemezését a 11.13. ábra tartalmazza. Az összes megelozési τ6 -ból a τ06 taszkrendszert. A 11.14. ábra mutatja az S 12 (τ06 ) ütemezést.

elozési gráfját 11.12. ábra mutatja. A taszkok végrehajtási ideje pedig: t1 i

2

2

0 m -re. A 11.13. példa. Ezúttal a processzorok számát növeljük: m-rol

τ7

taszkrendszer gráfját 11.15.

488


Tm2 −m+2

T1

T2

T3

11.12. ábra. A

T1

Tm2 −m+1

... τ6

taszkrendszer gráfja.

Tm+1

T2

...

Tm2 −2m+2

...

Tm2 −2m+3

Tm2 −m+2 S 11 :

T3

-

.. .

.. .

-

Tm

-

Tm+2

.. .

..

T2m−1

.. .

.

...

Tm2 −m+1

11.13. ábra. Az S 11 (τ6 ) optimális ütemezés.

T1

S 12 :

...

Tm+1

Tm2 −m+1

-

T2

Tm+2

...

T3

Tm+3

...

-

..

.

.. .

T2m+1

...

-

T2m

...

-

.. .

.. .

Tm−1 Tm

Tm2 −m+2

0

11.14. ábra. Az S 12 (τ ) ütemezés. 6

T1

T2

Tm

...

Tm+1

Tmm′ −m′ +m+2

Tm+2 11.15. ábra.

τ7

Tm+3

...

Tmm′ −m′ +m+1

rákövetkezési gráfja.

pedig ábra mutatja, a végrehajtási idok

ti

  ε,    1, =    m0 ,

= 1, . . . , m + 1, = m + 2, . . . , mm0 − m0 + m + 1, 0 0 ha i = mm − m + m + 2. ha i

ha i

A taszkrendszer optimális ütemezését m, illetve m

0

processzoron 11.16., illetve 11.17. ábra mu-

tatja. A maximális befejezési idoket összehasonlítva itt is a kívánt aszimptotikus értéket kapjuk: 0 0 0 0 0 C = C max (S 13 (τ7 )) = m + 2ε, C = C max (S 14 (τ7 )) = m + m − 1 + ε, így C /C = 1 + (m − 1 − ε)(m + 2ε), 0 0 valamint limε→0 C /C = 1 + (m − 1)/m .

11.3. Anomáliák

489 T1 Tm+1

Tm+2

S 13 :

T3

-

Tm+3

.. .

.. .

.. .

S 14 :

Tm

-

T2m

Tm+2

...

Ta

T2

Tm+3

...

Ta+1

.. .

-

Te

= m + m0 + 1,

f

.

.. .

...

Tc

Tmm0 −m0 +m+2 -

.. .

...

Td

-

.

.. .

.. .

...

Tf

-

..

= mm0 − m0 + m + 1).

-

.

11.17. ábra. Az S 14 (τ7 ) optimális ütemezés (a e

Tb

.. .

..

Tc

.. .

...

= mm0 − m0 + 3, b = a + 1, c = mm0 − m0 + m + 1).

T1

Tb

Ta

..

11.16. ábra. Az S 13 (τ7 ) optimális ütemezés (a

.. .

... Tmm0 −m0 +2

T2

= mm0 − 2m0 + m + 2, b = m + 1, c = 2m + 2, d = mm0 − 2m0 + 2m + 2,

állítás helyességét. Ezeknek a példáknak a segítségével beláttuk a következo 11.6. tétel (ütemezési korlát élessége). A relatív sebességre adott (11.8) korlát az m, t,

< és

L paraméterek mindegyikének változására nézve (külön-külön is) aszimptotikusan éles.

11.3.3. Párhuzamos feldolgozás átfedéses memóriával Népszeru formában fogalmazzuk meg az átfedéses memóriájú számítógépek muködését párhuzamos algoritmust. A gombócsorozatok a feldolgozandó hivatkozási somodellezo rozatokat, az óriások a processzorokat, a falatok az egyidejuleg végrehajtott utasításokat modellezik. A T0, T1,

. . . , T r törpék n különbözo fajtájú gombócot foznek. Ezeket az egyszeruség . . . , n számokkal jelöljük. Mindegyik törpe végtelen gombócsorozatot állít

kedvéért az 1, 2,

(a T i törpe sorozatát G i , a gombócsorozatok mátrixát G jelöli). elo Ezeket a gombócokat O f óriások eszik meg ahol az f paraméter azt mutatja, hogy az adott óriás az egyes gombócfajtákból legfeljebb hányat ehet meg egy falatban. falatához a T 0 törpe sorozatának elejérol a Az O f óriás a következoképpen eszik. Elso legtöbb gombócot választja ki (de egy-egy fajtából legfeljebb f darabot). Ezt a falatot leheto még a T 1 ,

...,

kiegészíti az f korlátot betartva. T r törpék sorozatának elejérol

A további falatokat hasonlóan állítja össze. Legyen hi ( f ) (i az O f óriás S

f

= 1, 2, . . .) az óriás i-edik harapásában lévo gombócok száma. Ekkor

gombócevési sebességét az

Pt S f (G) határértékkel deniáljuk.

= lim inf t→∞

i=1

hi ( f ) t

(11.13)

490

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal) ≤

Könnyen belátható, hogy ha 1 f

≤ g, akkor a gombócevési sebességekre fennáll

f

≤ S f (G) ≤

f n,

g

≤ S g (G) ≤ gn ,

(11.14)

a két óriás relatív gombócevési sebességére pedig f

≤

gn

S f (G) S g (G)

fn

≤

g

.

(11.15)

Most megmutatjuk, hogy a kis óriás gombócevési sebessége akárhányszor nagyobb lehet, mint a nagy óriásé. 11.7. tétel. Ha r

≥ 1,

n

≥ 3,

g

>

f

≥

1, akkor léteznek olyan G gombócsorozatok, ame-

lyekre egyrészt S g (G) S f (G)

=

g fn

,

(11.16)

.

(11.17)

másrészt S g (G) S f (G)

=

gn f

alsó korBizonyítás. A természetes korlátokat megadó (11.15) egyenlotlenségben szereplo lát élességének belátásához tekintsük az G1

= 1 f 22 f +1 1∗

(11.18)

és

= 1 f +1 (2 3 . . .

G2

n)

∗

(11.19)

sorozatokat. korlát élességét a A felso G1

= 1 22 f +1

∗

1

(11.20)

és G2 sorozatok

= 1 f −1 32 f

1

f

(2 3

...

n)

∗

(11.21)

megevésével láthatjuk be.

Az alsó korlát élessége azt fejezi ki, hogy a kis óriás ehet sokkal kevesebbet ami felso korlát élessége azonban természetes. Az n növelésével tetszolegesen naggyá teheto eros anomália.

11.3.4. Az anomália elkerülése Az anomáliát általában igyekszünk elkerülni. A lapcserélésnél például az elkerülés elégséges feltétele az, ha a cserélési algoritmus rendelkezik a veremtulajdonsággal: ha ugyanazt a hivatkozási sorozatot m és m + 1 méretu memóriájú gépen futtatjuk, akkor minden hivatkozás után igaz az, hogy a nagyobb memória mindazokat a lapokat tartalmazza, amelyeket a kisebb tartalmaz.

11.4. Állományok optimális elhelyezése

491

az, ha nem követeljük meg az ütemezo algoA vizsgált ütemezési feladatnál elegendo ritmustól a lista alkalmazását.

Gyakorlatok

11.3-1. Adjunk meg olyan m, M, n, p és R paramétereket, amelyekre a FIFO algoritmus az M méretu zikai memóriával legalább hárommal több laphibát okoz, mint az m méretu memóriával. 11.3-2. Adjunk meg olyan paramétereket, hogy a listás ütemezésnél a processzorszám nö veléseker legalább másfélszeresére nojön a maximális befejezési ido. 11.3-3. Adjunk meg olyan paramétereket, hogy a kis óriás gombócevési sebessége kétszerese legyen a nagy óriásénak.

11.4. Állományok optimális elhelyezése Ebben az alfejezetben egy olyan memóriakezelési feladatot tárgyalunk, amelyben ismert méretu fájlokat kell elhelyezni adott méretu lemezeken. A cél a felhasznált lemezek számának minimalizálása. A feladat megegyezik az Új algoritmusok címu könyv Közelíto algoritmusok címu fe ládapakolási feladattal. Az ütemezéselmélet pedig a jezetében a feladatok között szereplo processzorszám minimalizálásával kapcsolatban használja ugyanezt a modellt. fájlok méretét tartalmazó t Adott a fájlok n száma, valamint az elhelyezendo (t1 , t2 , . . . , tn ) vektor, melynek elemeire teljesül 0

<

ti

≤

1 (i

=

=

1, 2, . . . , n). A fájlokat

úgy kell elhelyezni a lemezeken, hogy nem szabad oket részekre bontani és gyelembe kell venni, hogy a lemezek kapacitása egységnyi.

11.4.1. Közelít® algoritmusok közelíto algoritmusokat haszAz adott feladat NP-teljes. A gyakorlatban ezért különbözo nálnak. adatai: a fájlok n száma és a fájlméretek t = Ezeknek az algoritmusoknak a bemeno ht1 , t2 , . . . , tn i vektora. A kimeno adatok pedig a szükséges lemezek száma (lemezszám) és a lemezek h = hh1 , h2 , . . . hn i szintvektora. Lineáris algoritmus (LF) A lineáris algoritmus (Linear Fit) szerint az F i fájlt az Li lemezen helyezzük el. LF pszeu dokódja a következo. LF(n, t)

3

← 1 to n ← t[i] lemezszám ← n

4

return lemezszám

1 2

for i

do h[i]

Ennek az algoritmusnak mind a helyigénye, mind pedig a futási ideje

Θ(n). Ha azonban

ciklusban oldjuk meg, a méretek beolvasását és a szintek nyomtatását az 12. sorokban lévo

492


akkor a helyigény

Θ(1)-re csökkentheto.

Egyszeru algoritmus (NF) lemezre, amíg Az egyszeru algoritmus (Next Fit) addig rakja a fájlokat a soron következo lehet. Pszeudokódja a következo. NF(n, t)

← t[1] ←1 for i ← 2 to n

1

h[1]

2

lemezszám

3 4

+ t[i] ≤ 1 ← h[lemezszám] + t[i] lemezszám ← lemezszám + 1 h[lemezszám] ← t[i]

do if h[lemezszám]

5

then h[lemezszám]

6

else

7 8

return lemezszám Ennek a algoritmusnak mind a helyfoglalása, mind pedig a futási ideje

Θ(n). Ha a futási

beolvasását és a szintek kivitelét a 37. sorokban lévo ciklusban oldjuk meg, akkor a idok helyfoglalás

a futási ido azonban Ω(n). Θ(1)-re csökkentheto,

Mohó algoritmus (FF) olyan lemezen helyezi el, amelyikre A mohó algoritmus (First Fit) a fájlokat rendre az elso ráférnek. FF(n, t)

4

←1 ← 1 to n do h[i] ← 0 for i ← 1 to n do k ← 1

5

while t[i]

1

lemezszám

2

for i

3 3

6 7 8 9 10

+ h[k] > 1 ←k+1 h[k] ← h[k] + t[i] if k > lemezszám then lemezszám ← lemezszám + 1 do k

return lemezszám

2 Θ(n), idoigénye pedig O(n ). Ha például minden 2 fájlméret 1, akkor az algoritmus futási ideje Θ(n ).

Ennek az algoritmusnak a helyigénye

Gazdaságos algoritmus (BF) olyan lemezre rakja, ahol a A gazdaságos algoritmus (Best Fit) a fájlokat rendre a legelso legkisebb szabad kapacitás marad. leheto


493

BF(n, t)

14

←1 ← 1 to n do h[i] ← 0 for i ← 1 to n do szabad ← 1.0 ind ← 0 for k ← 1 to lemezszám do if h[k] + t[i] ≤ 1 és 1 − h[k] − t[i] < szabad then ind ← k szabad ← 1 − h[k] − t[i] if ind > 0 then h[ind] ← h[ind] + t[i] else lemezszám ← lemezszám + 1 h[lemezszám] ← t[i]

15

return lemezszám

1 2 3 4 5 6 7 8 9 10 11 12 13

lemezszám

for i

Ennek az algoritmusnak a helyigénye

Θ(n), futási ideje pedig O(n2 ).

Párosító algoritmus (PF) és utolsó elemébol rendre párt kéA párosító algoritmus (Pairwise Fit) a méretvektor elso pez, és a két fájlt a két méret összegének megfeleloen egy, illetve két lemezre rakja. elemének indexe, eind A pszeudokódban két segédváltozó van: bind az aktuális pár elso pedig az aktuális pár második elemének indexe. PF(n, t) 1

lemezszám

2

bind

3

←1 eind ← n

4

while eind

5 6 7 8 9 10 11 12 13 14 15 16 17

←0

≥ bind − bind ≥ 1 then if t[bind] + t[eind] > 1 then lemezszám ← lemezszám + 2 h[lemezszám − 1] ← t[bind] h[lemezszám] ← t[eind] else lemezszám ← lemezszám + 1 h[lemezszám] ← t[bind] + t[eind] if eind = bind then lemezszám ← lemezszám + 1 h[lemezszám] ← t[eind] bind ← bind + 1 eind ← eind − 1

do if eind

return lemezszám Ennek az algoritmusnak a helyigénye (Θ(n)), futási ideje

Θ(n). Ha azonban a fájlméreΘ(1).

tek beolvasását és a lemezszintek kivitelét online módon megoldjuk, a helyigény csak

494

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal) öt algoritmus két részbol áll: eloször alapján csökkeno A következo a végrehajtási idok

sorrendbe rendezik a taszkokat (ennek a rendezésnek az eredménye a s vektor), majd a második részben a rendezett taszkokat ütemezik. egyszeru Rendezo algoritmus (NFD) egyszeru A rendezo algoritmus (Next Fit Decreasing) a rendezés után az egyszeru algo ritmus (NF) szerint dolgozik. Így mind helyigénye, mind pedig idoigénye az alkalmazott algoritmus és NF megfelelo igényeibol tevodik rendezo össze. mohó algoritmus (FFD) Rendezo algoritmus (First Fit Decreasing) a rendezés után a mohó algoritmus (FF) A mohó rendezo szerint dolgozik, így helyigénye

2 Θ(n), idoigénye pedig O(n ).

gazdaságos algoritmus (BFD) Rendezo algoritmus (Best Fit Decreasing) a rendezés után a gazdaságos algoA gazdaságos rendezo ritmus (BF) szerint dolgozik, így helyigénye

2 Θ(n), idoigénye pedig O(n ).

párosító algoritmus (PFD) Rendezo algoritmus (Pairwise Fit Decreasing) a rendezés után rendre párokat A párosító rendezo és legutolsó taszkokból, majd azokat lehetoleg képez a legelso egy processzorra (ha a vég összege nem nagyobb egynél) ütemezi. Ha ez nem lehetséges, akkor az adott rehajtási idok pár két processzorra ütemezi. gyors algoritmus (QFD) Rendezo algoritmus (Quick Fit Decreasing) a rendezés után rendre a legelso fájlt A gyors rendezo üres lemezre teszi, majd ehhez a fájlhoz mindaddig hozzáteszi a leheto a soron következo kezdi keresni), amíg ez legnagyobb fájlt (ezeket rendre a rendezett méretsorozat végétol lehetséges. vizsgálandó fájl indexe, eind A pszeudokódban használt munkaváltozók: bind az elso pedig az utolsó vizsgálandó fájl indexe. QFD(n, s)

←1 ←n

1

bind

2

eind

4

lemezszám

5

while eind

6

← lemezszám + 1 ← s[bind] bind ← bind + 1 while eind ≥ bind és h[lemezszám] + s[eind] ≤ 1 do ind ← eind while ind > bind és h[lemezszám] + s[ind − 1] ≤ 1 do ind ← ind − 1 h[lemezszám] ← h[lemezszám] + s[ind]

7 8 9 10 11 12 13

←0 ≥ bind

do lemezszám

h[lemezszám]


> ind

14

if eind

15 17

← ind to eind − 1 ← s[i + 1] eind ← eind − 1

18

return lemezszám

16

495

then for i

do s[i]

Ennek a programnak a helyigénye

Θ(n),

futásideje kedvezotlen esetben

Θ(n2 ), a gyaΘ(n lg n).

esetén körülbelül korlatban azonban egyenletes eloszlású végrehajtási idok

11.4.2. Optimális algoritmusok Egyszeru hatvány típusú optimális algoritmus (SP) Ez az algoritmus a fájlokat rendre egymástól függetlenül n lemez mindegyikére elhen

lyezi, így n

majd ezek közül kiválaszt egy optimálisat. Mivel ez az elhelyezést állít elo,

algoritmus minden elhelyezést eloállít (feltéve, hogy két elhelyezést azonosnak tekintünk, ha minden lemezhez ugyanazokat a fájlokat rendelik), így biztosan megtalálja az egyik optimális elhelyezést. Faktoriális típusú optimális algoritmus (FACT) Ez az algoritmus rendre eloállítja a fájlok permutációit (ezek száma n!), majd az így kapott listákat helyezi el a NF segítségével. Az algoritmus optimalitása így látható be. Tekintsünk egy tetszoleges fájlrendszert és a fájlok egy P perannak egy S OPT (τ) optimális elhelyezését. S OPT (τ) alapján állítsuk elo mutációját úgy, hogy rendre felsoroljuk a P1 , P2 , . . . , POPT(τ) lemezekre elhelyezett fájlokat. Ha a P permutációt az NF algoritmussal helyezzük el, akkor vagy S OPT -hoz jutunk, vagy egy másik optimális elhelyezéshez (bizonyos taszkok esetleg eggyel kisebb indexu lemezre kerülnek). Gyors hatványtípusú optimális algoritmus (QP) Ez az algoritmus (Quick Power) azzal próbálja SP idoigényét csökkenteni, hogy a

nagy fájlokat (melyek mérete nagyobb, mint 0.5) eleve külön lemezre helyezi, és csak a többi fájl n

(a kicsi fájlokat) próbálja mind az n lemezre elhelyezni. Így n helyett csak n ahol K a kicsi fájlok száma. állít elo,

K

elhelyezést

Gazdaságos hatványtípusú optimális algoritmus (EP) Ez az algoritmus (Economic Power) azt is gyelembe veszi (amellett, hogy két nagy fájl nem fér el egymás mellett), hogy két kis fájl mindig elfér egy lemezen. Ezért a nagy fájlok számát N-nel, a kicsikét K-val jelölve legfeljebb N

+ b(K + 1)/2c lemezre van szüksége. Így

eloször a nagy lemezeket ütemezzük külön lemezekre, majd a kicsiket a fenti számú lemez mindegyikére. Ha például N eloállítanunk.

=

K

= n/2, akkor ezek szerint csak (0.75n)0.5n elhelyezést kell

496


11.4.3. Listarövidítés (SL) Bizonyos feltételek mellett igaz, hogy a t lista felbontható úgy t1 és t2 listákra, hogy OPT(t1 )

+ OPT(t2 ) ≤

OPT(t) (ilyen esetekben szükségképpen az egyenloség teljesül). En-

alatt tudjuk optimálisan nek elonye, hogy a rövidebb listákat rendszerint rövidebb összido elhelyezni, mint az eredeti listát.

+ t j = 1. Ekkor legyen t1 = (ti , t j ) és t2 = t \ t1 . Ekkor − 1. Tekintsük ugyanis egy optimális elhelyezés esetén azt a két lemezt, amelyekre a t1 lista elemei kerültek. Mivel mellettük legfeljebb 1 − t1 , illetve 1 − t2 összegu fájlok lehetnek, így azok helyfoglalásainak összege legfeljebb 2 − (t1 + t2 ), Tegyük fel például, hogy ti

OPT(t1 )

=

1 és OPT(t2 )

=

OPT(t)

alatt kiválaszthatjuk azokat a azaz 1. A listát egyszerre mindkét végén vizsgálva O(n) ido összege 1. Ezután rendezzük a t listát. Legyen a fájlpárokat, melyekre a végrehajtási idok rendezett lista s. Ha például s1

+ sn > 1, akkor az elso fájl minden elhelyezésben külön = (t1 ) és t2 = (t2 , t3 , . . . , tn ) jó választás. Ha a rendezett listára s1 + sn < 1, de s1 + sn−1 + sn > 1, akkor legyen s j a legnagyobb

lemezre kerül, és így t1

olyan listaelem, amelyet s1 -hez adva nem lépjük túl az egyet. Ekkor t1

= (t1 , t j ) és t2 = t \ t1

választás mellett a t2 lista két elemmel rövidebb, mint a

t lista volt. Az utóbbi két muvelettel gyakran lényegesen lerövidíthetoek a listák (szerencsés esetben úgy, hogy mindkét listára könnyen megkaphatjuk az optimális lemezszámot). A rövidítés után megmaradó listát például a korábbi algoritmusok valamelyikével természetesen még fel kell dolgozni.

11.4.4. Becslések (ULE) és alsó becslésekre (Upper and Lower Estimations) támaszkodó algoritmusok a A felso algoritmussal eloállítják következoképpen muködnek. Valamelyik közelíto az OPT(t) egy becslését, majd alulról is megbecsülik OPT(t) értékét. Erre alkalmasak például A(t) felso azonos lemezre, az elhelyezések azon tulajdonságai, hogy két nagy fájl nem helyezheto és hogy a méretek összege egyik lemezen sem lehet 1-nél több. Ezért mind a nagy fájlok száma, mind pedig a fájlméretek összege, így ezek MAX(t) maximuma is alsó becslést ad. Ha A(t)

=

Ellenkezo MAX(t), akkor az A algoritmus optimális ütemezést állított elo.

algoritmussal folytathatjuk. esetben például valamelyik idoigényes optimumkereso

11.4.5. Algoritmusok páronkénti összehasonlítása Ha egy ütemezési (vagy más) probléma megoldására több algoritmust ismerünk, akkor az algoritmusok összehasonlításának egyik egyszeru módja annak vizsgálata, hogy paraméterek értékei úgy, hogy a kiválasztott teljesítménymérték megadhatók-e a szereplo értéke az egyik algoritmus esetén kedvezobb legyen, mint a másik algoritmus esetén. A most vizsgált elhelyezési probléma esetén a t méretvektorhoz az A, illetve B algoritmus által rendelt lemezszámot A(t)-vel, illetve B(t)-vel jelölve azt vizsgáljuk, vannak-e olyan t1 , illetve t2 vektorok, melyekre A(t1 )

<

B(t1 ), illetve A(t2 )

>

B(t2 ). Ezt a kérdést

és az optimális algoritmusra vizsgáljuk meg. most az elobb deniált tíz közelíto Az optimális algoritmusok deníciójából adódik, hogy minden t-re és minden A algoritmusra OPT(t)

≤ A(t).

A továbbiakban a példavektorok elemei huszadok lesznek.


497

LF

NF

FF

BF

PF

NFD

FFD

BFD

PFD

QFD

OPT

t1

4

3

3

3

3

3

2

2

2

2

2

t2

6

2

2

2

3

3

3

3

3

3

2

t3

7

3

2

3

4

3

2

3

4

2

2

t4

8

3

3

2

4

3

3

2

4

3

2

t5

5

3

3

3

3

2

2

2

3

2

2

t6

4

3

2

2

2

3

2

2

2

2

2

t7

4

3

3

3

2

3

2

2

2

2

2

11.18. ábra. Lemezszámok összefoglalása.

hét listát: Tekintsük a következo t1 t2 t3 t4 t5 t6 t7

= (12/20, 6/20, 8/20, 14/20), = (8/20, 6/20, 6/20, 8/20, 6/20, 6/20), = (15/20, 8/20, 8/20, 3/20, 2/20, 2/20, 2/20), = (14/20, 8/20, 7/20, 3/20, 2/20, 2/20, 2/20, 2/20), = (10/20, 8/20, 10/20, 6/20, 6/20), = (12/20, 12/20, 8/20, 8/20), = (8/20, 8/20, 12/20, 12/20).

Ezeknek a listáknak az elhelyezési eredményeit a 11.18. ábrán foglaltuk össze. listához LF 4, míg a többi algoritmus ennél keveA 11.18. ábra mutatja, hogy az elso sebb lemezt igényel. Továbbá azt is mutatja t1 lista sora, hogy FFD, BFD, PFD, QFD és OPT kevesebb lemezt igényel, mint NF, FF, BF, PF és NFD. Természetes, hogy nincs olyan lista, amelyre bármelyik algoritmus kevesebb lemezt használna fel, mint OPT. Az is közvetlenül adódik, hogy nincs olyan lista, melyhez az LF kevesebb lemezt használna fel, mint a többi tíz algoritmus közül bármelyik. X szimEzeket a megállapításokat mutatja a 11.19. ábra. Az ábrán a foátlóban lévo bólumok azt jelzik, hogy az egyes algoritmusokat önmagukkal nem hasonlítjuk össze. Az oszlopban lévo nagykötojelek algoritmushoz nincs elso azt jelzik, hogy a sornak megfelelo olyan lista, melyet az algoritmus több lemez felhasználásával dolgozna fel, mint az oszlop algoritmus, azaz LF. nak megfelelo nagykötojelek Az utolsó sorban lévo pedig azt mutatják, hogy nincs olyan lista, melyhez az optimális algoritmus több lemezt igényelne, mint bármelyik másik vizsgált algoritmus. Végül az egyesek azt jelzik, hogy a t1 listához az ábra adott mezoje sorának megfelelo oszlopának megfelelo algoritmus. algoritmus több lemezt használ fel, mint a mezo Ha tovább folytatjuk a 11.19. ábra lemezszámainak elemzését, a 11.19. ábrát a 11.20. ábrává egészíthetjük ki. sort és az elso oszlopot már kitöltöttük, az LF algoritmussal nem foglalMivel az elso kozunk többet. A t2 listához NF, FF, BF és OPT 2 lemezt használ, míg a többi 6 algoritmus hár mat. Ezért a gyoztesek oszlopainak és a vesztesek sorainak metszéspontjaiba ketteseket

498

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal) LF

NF

FF

BF

PF

NFD

FFD

BFD

PFD

QFD

OPT

LF

X

1

1

1

1

1

1

1

1

1

1

NF

X

1

1

1

1

1

FF

1

1

1

1

1

BF

1

1

1

1

1

PF

1

1

1

1

1

NFD

1

1

1

1

1

FFD

BFD

PFD

QFD

OPT

X X X X

X X X X

X

11.19. ábra. Algoritmusok páronkénti összehasonlítása.

írunk (a PF és OPT, valamint az NFD és OPT metszéspontjában azonban a már ott lévo egyest nem írjuk felül, így 4 × 6 − 2

= 22 mezobe kerül kettes). Mivel OTP sorát és oszlopát

kitöltöttük, ezért a pont további részében nem foglalkozunk vele. üres mezokbe A harmadik lista hátrányos PF és PFD számára, ezért a soraikban lévo hármasokat írunk. Ez a lista arra is példa, hogy NF rosszabb lehet, mint FF, BF rosszabb lehet FF-nél, BFD az FFD-nél és a QFD-nél. A negyedik listát csak BF és BFD tudja optimálisan azaz két lemez felhasználásával feldolgozni. Ezért a két algoritmus oszlopában a még üres mezokbe négyest írhatunk. Az ötödik listához NFD, FFD, BFD és QFD csak két, míg NF, FF, BF, PF és PFD három mezokbe lemezt használ. Ezért a megfelelo ötös kerülhet. A t6 lista írunk.

vesztesei NF és NFD ezért a soraikban még üresen álló mezokbe hatost

A t7 lista feldolgozását PF jobban végzi, mint FF. kitöltését segíti a következo További mezok 11.8. tétel. Ha t

∈

D, akkor FF(t)

≤ NF(t) .

Bizonyítás. A lista hossza szerinti indukciót alkalmazunk.

= ht1 , t2 , . . . , tn i és ti = ht1 , t2 , . . . , ti i (i = 1, 2, . . . , n). Legyen NF(ti ) = Ni és = Fi , továbbá legyen ni az utolsó lemez szintje NF szerint, azaz a legnagyobb indexu,

Legyen t FF(ti )

nem üres lemezre tett állományok hosszainak összege akkor, amikor NF éppen feldolgozta ti -t. Hasonlóképpen legyen fi az utolsó lemez szintje FF szerint. invariáns tulajdonság teljesülését bizonyítjuk minden i-re: vagy F i A következo vagy F i

=

Ha i

Ni és fi

=

<

Ni ,

≤ ni .

1, akkor F 1

=

N1 és f1

=

n1

=

t1 , azaz az invariáns tulajdonság második

része teljesül. Tegyük fel, hogy a tulajdonság teljesül az 1

≤

i

<

n értékre. Ha most a ti+1

az invariáns tulajdonság elso része teljesült, akkor vagy érvényes marad az elhelyezése elott Fi

<

lesznek és fi Ni egyenlotlenség, vagy pedig a lemezszámok egyenlok

<

ni fog fenn-

a lemezszámok egyenlok voltak, akkor az elhelyezés állni. Ha most a ti+1 elhelyezése elott


499

LF

NF

FF

BF

PF

NFD

FFD

BFD

PFD

QFD

OPT

LF

X

1

1

1

1

1

1

1

1

1

1

NF

X

3

4

7

5

1

1

1

1

1

FF

X

4

7

5

1

1

1

1

1

BF

3

X

8

5

1

1

1

1

1

PF

2

2

2

X

3

1

1

1

1

1

NFD

2

2

2

6

X

1

1

1

1

1

FFD

2

2

2

X

4

2

BFD

2

2

2

3

X

3

2

PFD

2

2

2

3

3

3

3

2

QFD

2

2

2

4

OPT

3

X

X

2

X

11.20. ábra. Algoritmusok páronkénti összehasonlításának eredményei.

lemezszám mellett FF utolsó után vagy FF lemezszáma kisebb lesz, vagy pedig egyenlo lemezének szintje legfeljebb akkora lesz, mint NF utolsó lemezének szintje.

Hasonló állítás bizonyítható az NFBF, NFDFFD és NFDBFD algoritmuspárokra. Indukcióval belátható, hogy FFD és QFD minden listára ugyanannyi lemezt igényelnek. Az eddigi megállapításokat a 11.20. ábrán összesítjük.

11.4.6. Közelít® algoritmusok hibája Két algoritmus (A és B) relatív hatékonyságát gyakran jellemzik a kiválasztott hatékonysági mérték értékeinek hányadosával, jelen esetben az A(t)/B(t) relatív lemezszámmal. Ennek jellemzok deniálhatók. Ezeket két csoportba a hányadosnak a felhasználásával különbözo szokás sorolni: egyik csoportba a legrosszabb, míg a másikba az átlagos esetet jellemzo mennyiségek kerülnek. Itt csak a legrosszabb esettel foglalkozunk (az átlagos eset vizsgálata rendszerint lényegesen nehezebb). Legyen

Dn

azon valós listák halmaza, amelyek n elemet tartalmaznak, és legyen

D az

összes valós lista halmaza, azaz D

= ∪∞ Di . i= 1

Alsz az állományelhelyezo, (azaz a minden t ∈ D listához egy nemnegatív valós D → R+0 leképezést megvalósító) algoritmusok halmaza. algoritmusok halLegyen Aopt a minden listához az optimális lemezszámot rendelo

Legyen

és így a számot hozzárendelo,

maza, és OPT ennek a halmaznak egy eleme (azaz egy olyan algoritmus, amely minden t

∈

D listához megadja a listához tartozó fájlok elhelyezéséhez szükséges és elégséges le-

mezek számát).

∈ Alsz algoritmusok halmaza, amelyekre A(t) ≥ OPT(t) minden ∈ D lista, amelyre A(t) > OPT(t). Legyen Abecs azon E ∈ Alsz algoritmusok halmaza, amelyekre E(t) ≤ OPT(t) minden t ∈ D listára, és van olyan t ∈ D lista, amelyre E(t) < OPT(t). Legyen F n azon valós listák halmaza, amelyekre OPT(t) = n, azaz F n = {t|t ∈ D és Legyen

t

∈

Aköz

azon A

D listára, és van olyan t

500


OPT(t)

= n} (n = 1, 2, . . .). A továbbiakban csak Alsz -beli algoritmusokat fogunk vizsgálni. ∈ A) RA,B,n hibafüggvényét, RA,B hibáját (abszolút hibáját)

Az A és B algoritmusok (A, B

és RA,∞ aszimptotikus hibáját a következoképpen deniáljuk: RA, B,n

R A, B RA,∞

= sup t∈ Dn

= sup t∈ D

=

A(t)

,

B(t) A(t) B(t)

lim RA, B,n

n→∞

, .

∈ Aopt . Ilyenkor az egyszeruség ∈ A, illetve az E ∈ A algoritmusok

Ezek a mennyiségek foleg akkor érdekesek, ha B elhagyjuk a B-t, és az A kedvéért a jelölésekbol

hibájáról és aszimptotikus hibájáról beszélünk. hibafüggvényérol, algoritmus jellemzo adatai ismertek. A NF fájlelhelyezo 11.9. tétel. Ha t

∈

F n , akkor n

Továbbá, ha k

= OPT(t) ≤ NF(t) ≤ 2OPT(t) − 1 = 2n − 1 .

∈ Z, akkor léteznek olyan uk

(11.22)

és vk listák, melyekre

= OPT(uk ) = NF(uk )

(11.23)

= OPT(vk ) és NF(vk ) = 2k − 1 .

(11.24)

k és k

az állításból adódik a NF fájlelhelyezo algoritmus hibafüggvénye, abszolút hibája Ebbol és aszimptotikus hibája. 11.10. következmény. Ha n

∈ Z, akkor RNF,n

=2−

1 n

,

(11.25)

továbbá RNF

= RNF,∞ = 2 .

(11.26)

algoritmus legrosszabb esetére vonatkozik a következo állítás. A FF és BF fájlelhelyezo 11.11. tétel. Ha t

∈

F n , akkor OPT(t)

Továbbá, ha k

≤ FF(t),

BF(t)

∈ Z, akkor léteznek olyan uk

≤ 1.7OPT(t) + 2 .

(11.27)

és vk listák, melyekre

= OPT(uk ) = FF(uk ) = BF(uk )

(11.28)

= OPT(vk ) és FF(vk ) = BF(vk ) = b1.7kc .

(11.29)

k valamint k

korlát is érvényes. A FF algoritmusra egy erosebb felso

11. fejezet feladatai 11.12. tétel. Ha t

∈

501

F n , akkor

≤ FF(t) < 1.7OPT(t) + 1 .

OPT(t)

(11.30)

a két állításból adódik FF és BF aszimptotikus hibája, valamint hibafüggvényük Ebbol jó becslése. 11.13. következmény. Ha n

∈ Z, akkor b1.7nc n

és

b1.7nc n

≤ RFF,n ≤

≤ RBF,n ≤

d1.7ne

(11.31)

n

b1.7n + 2c

(11.32)

n

továbbá RFF,∞

= RBF,∞ = 1.7 .

(11.33)

határok megeaz alsó és felso Ha n osztható tízzel, akkor a (11.31) egyenlotlenségben gyeznek, azaz ebben az esetben 1.7

= RF F,n .

Gyakorlatok 11.4-1. Példával bizonyítsuk, hogy a FF és BF algoritmusok abszolút hibája legalább 1.7. 11.4-2.

Valósítsuk meg a FF és BF algoritmusok alapgondolatát úgy, hogy a futási ido

O(n lg n) legyen. 11.4-3. Egészítsük ki a 11.20 ábrát.

Feladatok 11-1. Lapcserélési anomália elkerülése Osztályozzuk a tárgyalt lapcserélési algoritmusokat aszerint, hogy biztosítják-e az anomália elkerülését. 11-2. Optimális lapcserélési algoritmus Bizonyítsuk be, hogy minden A igény szerinti lapcserélési algoritmusra, m memóriaméretre és R hivatkozási tömbre teljesül, hogy fA (m, R)

≥

fOPT (m, R).

11-3. Anomália Tervezzünk egy algoritmust (és valósítsuk is meg), amelynél elofordulhat, hogy egy adott feladatot q

>

p processzoron megoldani tovább tart, mint p

> 1 processzoron.

11-4. Fájlelhelyezési algoritmusok hibája korlátokat a BF, BFD, FF és FFD algoritmusok hibájára. Adjunk alsó és felso

Megjegyzések a fejezethez A lapcserélési algoritmusokat Silberschatz, Galvin és Gagne [24], valamint Tanenbaum és Woodhull [25] tankönyvei alapján tárgyaljuk.

502

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal) A lapcserélési algoritmusok Mealy-automatával való deniálása Denning összefoglaló

cikkén [6], Gécseg Ferenc és Peák István [9], Hopcroft, Motwani és Ullman [10], valamint Peák István [22] tankönyvein alapul. A MIN algoritmus optimalitását Mihnovszkij és Shor 1965-ben [21], majd Mattson, Gecsei, Slutz és Traiger 1970-ben [20] bizonyították. A FIFO lapcserélési algoritmusnál a gyakorlatban tapasztalt anomáliát eloször Bélády László [2] írta le 1966-ban, majd Shedlerrel közös dolgozatában [3] konstruktív módon Ugyanebben bizonyította, hogy az anomália mértéke tetszolegesen megközelítheti a kettot. a cikkben fogalmazták meg (1969-ben) azt a sejtést, hogy az anomália mértéke nem érheti Fornai Péter és Iványi Antal [7] 2002-ben megmutatták, hogy a nagy és kisebb el a kettot. memóriájú számítógépekben szükséges lapcserék számának hányadosa akármilyen nagy lehet. Ütemezési anomáliára példák szerepelnek Coffman [4], Iványi és Szmeljánszkij [14], valamint Roosta [23] könyvében, továbbá Lai és Sahni [19] cikkében. Ennek a fejezetnek az anyaga több helyen is kapcsolódik az Ütemezéselmélet címu fejezethez. Például az 11.5. tétel m

=

0

m

,

t

=

0

t

, <=<0

speciális esete ott szerepel a listás

algoritmus pedig ott ládapakoló algoütemezéssel kapcsolatban. Az FF szegmenselhelyezo ritmusként szerepet játszik az egyik többprocesszoros eredmény bizonyításában. származik. Az átfedéses memória elemzése a [11] cikkbol Az NF(t)

≤

2OPT(t)

+

2 korlát D. S. Johnson PhD értekezésében szerepelt [15], a

származik. A FF-re és BF-re vonatkozó felso korlát Johnson, pontos 11.11. tétel [12]-bol Demers, Ullman, Garey és Graham [16] eredménye, a korlát pontosságára vonatkozó bizo korlát forrása nyítás pedig Iványi Antalé [12, 13]. Az FFD-re és BFD-re vonatkozó felso [16], az NFD-re vonatkozó korláté pedig [1]. A fájlelhelyezési feladat NP-nehézségének bizonyítása a részletösszeg feladatra való visszavezetéssel szerepel az Új algoritmusok algoritmusokkal foglalkozó fejezetében [5]. közelíto A témakör magyar nyelvu tankönyvei közül Varga László munkáját [26], Kernighan és Pike [18], Kóczy és Kondorosi [17] Tanenbaum és Woodhull [25] muvét, valamint Galambos Gábor [8] 2003-ban megjelent tankönyvét ajánljuk.

Irodalomjegyzék

[1] B. Baker. A tight asymptotic bound for next-t decreasing bin-packing. SIAM Journal on Algebraic and Discrete Methods, 2(2):147152, 1981. 502 [2] L. A. Bélády. A study of replacement algorithms for a virtual storage computer. IBM Systems Journal, 5(2):78101, 1965. 502 [3] L. A. Bélády, R. Nelson, G. S. Shedler. An anomaly in space-time characteristics of certain programs running in paging machine. Communications of the ACM, 12(1):349353, 1969. 502 [4] E. Coffman. Computer and Job Shop Scheduling. John Wiley & Sons, 1976. 502 [5] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms. The MIT Press/McGrawHill, 2004 (Második kiadás ötödik, javított utánnyomása. Magyarul: Új algoritmusok. Scolar Kiadó, 2003). 502 [6] P. Denning. Virtual memory. Computing Surveys, 2(3):153189, 1970. 502 és Winkler Zoltán (szerkeszto), 5th [7] P. Fornai, A. Iványi. Bélády's anomaly is unbounded. In Kovács Elod International Conference on Applied Informatics, 6572. o. Molnár és társa, 2002. 502 [8] G. Galambos. Operációs rendszerek (Operating Systems). Muszaki Könyvkiadó, 2003. 502 [9] F. Gécseg, I. Peák. Algebraic Theory of Automata. Akadémiai Kiadó, 1972. 502 [10] J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001 (németül: Einführung in Automatentheorie, Formale Sprachen und Komplexitätstheorie, Pearson Studium, 2002). 2. kiadás. 502 [11] A. Iványi. On dumpling-eating giants. In Finite and Innite Sets (Eger, 1981), Colloquia of Mathematical Society János Bolyai 37. kötete, 379390. o. North-Holland, 1984. 502 [12] A. Iványi. Performance bounds for simple bin packing algorithms. Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Computarorica, 5:7782, 1984. 502 [13] A. Iványi. Tight worst-case bounds for bin packing algorithms. In Theory of Algorithms (Pécs, 1984), Colloquia of Mathematical Society János Bolyai 44. kötete, 233240. o. North-Holland, 1985. 502 [14] A. Iványi, R. Szmeljánszkij. Elements of Theoretical Programming (in Russian). Moszkvai Állami Egyetem, 1985. 502 [15] D. Johnson. Near-optimal bin packing algorithms. PhD értekezés, MIT Department of Mathematics, 1973. 502 [16] D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, R. L. Graham. Worst-case performance-bounds for simple one-dimensional bin packing algorithms. SIAM Journal on Computing, 3:299325, 1974. 502 [17] A. Kóczy, K. Kondorosi. Operációs rendszerek mérnöki megközelítésben (magyarul: Operating Systems An Engineering Approach). Panem, 1999. 502 [18] B. Kernighan, R. Pike. The UNIX programming Environment. Prentice Hall, 1984 (Magyarul: A UNIX ope Könyvkiadó, 1987 és 1999). 502 rációs rendszer, Muszaki [19] T. Lai, S. Sahni. Anomalies in parallel branch and bound algorithms. Communications of ACM, 27(6):594 602, 1984. 502 [20] R. L. Mattson, J. Gecsei, D. R. Slutz, I. Traiger. Evaluation techniques for storage hierarchies. IBM Systems Journal, 9(2):78117, 1970. 502 [21] Sz. Mihnovszkij, N. Shor. Estimation of the page fault number in paged memory (in russian). Kibernetika (Kiev), 1(5):1820, 1965. 502

504

Irodalomjegyzék

[22] I. Peák. Bevezetés az automaták elméletébe. Az automaták mint információátalakító rendszerek 1. (Introduction to the Theory of Automata. Automata as Systems for the Transformation of the Information). Tankönyvkiadó, 1977. 502 [23] S. H. Roosta. Parallel Processing and Parallel Algorithms. Springer-Verlag, 1999. 502 [24] A. Silberschatz, P. Galvin, G. Gagne. Applied Operating System Concepts. John Wiley & Sons, 2000. 501 [25] A. S. Tanenbaum, A. Woodhull. Operating Systems. Design and Implementation. Prentice Hall, 1997 (Magyarul: Operációs rendszerek. Panem, 1999). 501, 502 [26] L. Varga. Rendszerprogramok elmélete és gyakorlata (Theory and Practice of System Programs). Akadémiai Kiadó, 1980. 502

Tárgymutató

A, Á

hivatkozási sorozat, 471

állapot-átmenetfüggvény, 471 algoritmus, 499 állományelhelyezo anomália, 480, 481, 501 anomálisa mértéke, 481 programok, 456 áthelyezheto átmenetfüggvény, 472

I, Í igény szerint, 470

K B báziscímzés, 456 bázisregiszter, 457 jelek halmaza, 471 bemeno B-, 469gy

BF, 493, 494, lásd gazdaságos algoritmus gazdaságos algoritmus BFD, lásd rendezo

K ´  ´ -´ ´ , 464 állapot, 471 kezdeti vezérlo kimenetfüggvény, 471 jelek halmaza, 471 kimeno K --, 469gy ´

K --, 470gy ´

L CS

*-, 472

lapcserélési algoritmus statikus, 471 lapcserélési algoritmusok, 470480 laphiba, 472 lapkeret, 470

E, É egyszeru algoritmus (NF), 492 egyszeru hatvány algoritmus (SP), 495 E, 464, 470gy elobetöltés, 470

EP, lásd gazdaságos hatványtípusú algoritmus

lapozási sebesség, 481

L- ´  , 458, 469gy

L-- ´ -´  , 460, ´  ´ - ´ 469gy LF, 491

LFU- ´ , 476 listarövidítés, 496

LRU- ´ , 474 F

lyuk, 470

és alsó becslések, 496 felso FF, 492, lásd mohó algoritmus mohó algoritmus FFD, lásd rendezo

M

FIFO, 480

Mealy-automata, 471

FIFO- ´ , 473 F-, 469gy zikai memória, 470

memória elaprózódása, 465 mohó algoritmus (FF), 492

N G

N-, 466, 469gy

gazdaságos algoritmus (BF), 492 gazdaságos hatványtípusú algoritmus (EP), 495 algoritmus (BFD), 494 gazdaságos rendezo

NF, 492, lásd egyszeru algoritmus egyszeru NFD, lásd rendezo algoritmus

gombócevési sebesség, 489

NRU-  ´ ´, 477 NRU-, 478

NRU- ´ , 477

H határregiszter, 457 háttérmemória, 470

O, Ó

506

Tárgymutató

OPT-, 475

rögzített partíciók, 457

P

S SL, lásd listarövidítés

páronkénti összehasonlítás, 496

SP, lásd egyszeru hatvány algoritmus

OPT- ´ , 474

párosító algoritmus, 493 partíció, 456 dinamikus, 463 rögzített, 457 PF, 493, lásd párosító algoritmus párosító algoritmus PFD, lásd rendezo

U, Ú és alsó becslések ULE, lásd felso

PFF, 479

V

Q

veremtulajdonság, 490 állapotok halmaza, 471 vezérlo virtuális lap indexe, 471

gyors algoritmus QFD, 494, lásd rendezo

R

R- ´ ´, 462 R´  ´ ----´ , 462, 469gy ´ - ´ egyszeru rendezo algoritmus (NFD), 494 gyors algoritmus (QFD), 494 rendezo

virtuális memória, 470

W W-, 469gy, 470gy WS, 479

WS-, 479

Tartalomjegyzék


. . . . . . . . . . . . .

456

11.1. Partícionálás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

456

11.1.1. Rögzített partíciók

. . . . . . . . . . . . . . . . . . . . . . . . . .

457

. . . . . . . . . . . . . . . . . . . . . . . . .

463

. . . . . . . . . . . . . . . . . . . . . . . . . .

470

11.2.1. Statikus lapcserélés . . . . . . . . . . . . . . . . . . . . . . . . . .

471

11.2.2. Dinamikus lapcsere . . . . . . . . . . . . . . . . . . . . . . . . . .

478

11.3. Anomáliák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

480

11.1.2. Dinamikus partíciók 11.2. Lapcserélési algoritmusok

11.3.1. Lapcsere

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

480

11.3.2. Listás ütemezés . . . . . . . . . . . . . . . . . . . . . . . . . . . .

482

11.3.3. Párhuzamos feldolgozás átfedéses memóriával

. . . . . . . . . . .

489

11.3.4. Az anomália elkerülése . . . . . . . . . . . . . . . . . . . . . . . .

490

11.4. Állományok optimális elhelyezése . . . . . . . . . . . . . . . . . . . . . .

491

algoritmusok 11.4.1. Közelíto

. . . . . . . . . . . . . . . . . . . . . . . .

491

Lineáris algoritmus (LF) . . . . . . . . . . . . . . . . . . . . . . .

491

Egyszeru algoritmus (NF)

. . . . . . . . . . . . . . . . . . . . . .

492

. . . . . . . . . . . . . . . . . . . . . . . .

492

Gazdaságos algoritmus (BF) . . . . . . . . . . . . . . . . . . . . .

492

Párosító algoritmus (PF)

. . . . . . . . . . . . . . . . . . . . . . .

493

egyszeru Rendezo algoritmus (NFD) . . . . . . . . . . . . . . . . .

494

mohó algoritmus (FFD) Rendezo

494

Mohó algoritmus (FF)

. . . . . . . . . . . . . . . . . .

gazdaságos algoritmus (BFD) Rendezo

. . . . . . . . . . . . . . .

494

. . . . . . . . . . . . . . . . .

494

. . . . . . . . . . . . . . . . . .

494

11.4.2. Optimális algoritmusok . . . . . . . . . . . . . . . . . . . . . . . .

495

Egyszeru hatvány típusú optimális algoritmus (SP) . . . . . . . . .

495

Faktoriális típusú optimális algoritmus (FACT)

. . . . . . . . . . .

495

Gyors hatványtípusú optimális algoritmus (QP) . . . . . . . . . . .

495

Gazdaságos hatványtípusú optimális algoritmus (EP) . . . . . . . .

495

párosító algoritmus (PFD) Rendezo gyors algoritmus (QFD) Rendezo

11.4.3. Listarövidítés (SL)

. . . . . . . . . . . . . . . . . . . . . . . . . .

496

11.4.4. Becslések (ULE) . . . . . . . . . . . . . . . . . . . . . . . . . . .

496

11.4.5. Algoritmusok páronkénti összehasonlítása . . . . . . . . . . . . . .

496

algoritmusok hibája . . . . . . . . . . . . . . . . . . . . . 11.4.6. Közelíto

499

Irodalomjegyzék . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

503

508

Tartalomjegyzék

Tárgymutató . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

505

11. Memóriagazdálkodás (Balogh Ádám és Iványi Antal)

Recommend Documents