Dinamiskā atmiņas iedalīšana

Vikipēdijas lapa
Jump to navigation Jump to search

Atmiņas piešķiršanas stratēģijas ir stratēģijas atmiņas piešķiršanai.

Definīcija: Par reģionu sauksim blakus stāvošas atmiņas zonas (kā, piemēram, celiņus), kas piešķirtas vienam failam. Fails var sastāvēt no vairākiem reģioniem, kurus pārvalda failsistēma. Definīcija: Par granulu sauksim failam piešķirtās atmiņas vienību. Jeb mazāko iespējamo reģionu failā.

Atmiņas piešķiršanas stratēģiju mērķi:

  • Minimizēt faila aizņemtās atmiņas reģionu skaitu, ar mērķi samazināt lasošās galviņas pārvietošanos skaitu, nolasot secīgu failu. Kā arī samazināt faila aprakstošo reģionu deskriptoru skaitu.
  • Minimizēt fizisko attālumu starp faila aizņemtās atmiņas reģioniem, lai samazinātu galviņas pārvietošanās amplitūdu.

Stratēģijas[labot šo sadaļu | labot pirmkodu]

Stratēģijas var iedalīt dažādi, atbilstoši to sarežģītībai. Vienkāršākās stratēģijas piešķir fiksēta izmēra atmiņas daļas, kas vienādas ar granulas izmēru. Sarežģītākās stratēģijas piešķir mainīga izmēra atmiņas daļas, kas ir vairāku secīgu granulu izmērā. Visas stratēģijas uztur tabulu ar pieejamo brīvo granulu informāciju.

Tabulas tiek organizētas dažādos veidos:

  • Sakārtots vai nesakārtots brīvo granulu vai reģionu saraksts. Reģionu piešķiršana nozīmē izņemt atbilstošo ierakstu no saraksta un pievienot to faila sarakstam.
  • Bitkarte, kur katrs bits atbilst vienai granulai. Granulas piešķiršana nozīmē atrast bitu ar 0 vērtību, nomainīt to uz 1 un pievienot atbilstošās granulas adresi faila deskriptorā.

Fiksēta izmēra reģionu stratēģijas[labot šo sadaļu | labot pirmkodu]

Šāda veida stratēģijas neizšķir granulas un reģionus un pamatā tiek lietotas mazās sistēmās. Tās piešķir vienam failam vienlaicīgi vienu granulu. Pirmā-atrastā stratēģija piešķir granulu no brīvo granulu saraksta augšgala, vai arī pirmo nulles bitu no tabulas.

Labākās-izvēles stratēģija piešķir tuvāko granulu (atbilstoši galviņas novietojumam) attiecībā pret pēdējo piešķirto granulu, izvēloties no iespējamajiem brīvajiem variantiem.

Mainīga izmēra reģionu stratēģijas[labot šo sadaļu | labot pirmkodu]

Šāda veida stratēģijas piešķir reģionus, kas komponēti no secīgām granulām atbilstoši pieprasītajam atmiņas apjomam. Failsistēmas kodols saņem pieprasījumus par atmiņas pieprasīšanu un atbrīvošanu. Pieprasītās atmiņas apjoms ir dažāda izmēra. Ja nepārtraukta atmiņa nav pieejama, tad failam izdalītā atmiņa var tikt sadalīta vairākos reģionos.

Tuvākās-izvēles stratēģija pievieno divus secīgus brīvus reģionus. Kad tiek saņemts pieprasījums pēc nepieciešamās atmiņas brīvo reģionu saraksts tiek pārskatīts, meklējot brīvus reģionus pieprasītajā izmērā. Ja tādu reģionu neizdodas atrast, pirmais reģions ar lielāko izmēru, tiek sadalīts divos reģionos — viens pieprasītās atmiņas izmērā, un otrs atlikušajā izmērā un tiek pievienots brīvo reģionu sarakstā.

Kaimiņa (buddy) stratēģija[labot šo sadaļu | labot pirmkodu]

Kaimiņa stratēģija piedāvā iespēju piešķirt reģionus, kas sastāv no 1, 2, 4, 8, .. 2n granulām. Katram no šiem reģioniem tiek uzturēts savs saraksts. Ja tiek saņemt pieprasījums par nepieciešamu atmiņu izmērā 2i, tad pieprasījums var tikt apmierināts, piešķirot atmiņu no atbilstošā 2i saraksta, vai arī no saraksta, kas atbilst 2i+1, kurš tiek sadalīts divās daļās. Ja netiek atrasta atmiņa 2i+1 sarakstā, tad algoritms meklē 2i+2, resp. rekursīvi ar noteiktu rekursijas dziļumu. Kad atmiņa atbrīvojas, tad divi blakus stāvoši kaimiņi ar izmēru 2i, tiek apvienoti vienā ar izmēru 2i+1.