17-lekciya Operacion sistemadaǵı virtual yad

13.4-súwret. Associativ tuwrıdan-tuwrı kórsetiwge tiykarlanǵan bet mánzillerin konvertaciyalaw
Virtual maydannıń keńeyiwi betler kestesiniń kóbeyiwine alıp keledi. Bul mashqalanı sheshiwdiń usıllarınan biri bul kóp dárejeli betlew. Bul bóliniwdiń mánisi sonda, bir ólshewli virtual boslıq eki dárejege bólinedi - bólimler hám betler, virtual mánzil eki dárejeli kestege muwapıq ózgertiriledi (13.5-súwret). Birinshi dárejede bólimler kestesi bar bolıp, ol jaǵdayda bólim betleri kestelerinde ssi’lkalar bar. Ekinshi dárejede bólim betleri kestelerin óz ishine aladı. Bul jantasıw mánzil kórgezbesi maǵlıwmatları ushın ajıratılǵan yad kólemin tejeydi, sebebi barlıq bólimler ushın bet kestelerin saqlap turıw múmkin emes, kerisinshe bir dárejeli jantasıwdan ayrıqsha bolıp esaplanadı, bul virtual maydanda tiykarǵı yad barlıq betlerdiń tolıq kestesin saqlawdı talap etedi.

13. 5-súwret. Eki dárejeli sxema tiykarında bet mánzillerin konvertaaiyalaw
Toldırılǵan kesh yadındaǵı maǵlıwmatlardı almastırıw algoritmleri.
Kesh yadın toltırg’anda, oǵan jańa bloktı kiritiw qatarlardan birewiniń quramın almastırıw menen baylanıslı. Tuwrıdan-tuwrı kórsetiwde tiykarǵı yadtıń hár bir blokı kesh yadındaǵı tek bir anıq qatarǵa tuwrı keledi hám bul jerde óshirilgen qatardan basqasın tańlawı múmkin emes. Tolıq hám qisman assotsiativ kórsetiw usılları menen qanday da almastırıw algoritmı (kesh yadınan óshiriletuǵın qatardı tańlaw) talap etiledi.
Ózgertiw strategiyasınıń tiykarǵı maqseti - jaqın keleshekte kiriw múmkinshiligı joqarı bolǵan qatarlardı kesh yadında saqlaw hám keyin kiretuǵın yamasa ulıwma bolmaytuǵın qatarlardı almastırıw. Optimal algoritm boladı, qaysı sızıq ornın, keleshekte qaysı mu’ra’ja’a’t júz beredi, hár qanday basqa Kesh sızıǵına salıstırǵanda. Bunday boljaw derlik ámelge asıri’lmaydi’, sol sebepli optimaldan tómen bolǵan algoritmlerden paydalanadı. Qanday bolmasın, joqarı tezlikke erisiw ushın almastırıw algoritmi apparatda orınlanıwı kerek.
Almastırıw algoritmleriniń eń keń tarqalǵan natiyjeliligin kemeytiwdiń izbe-izligin kórip shıǵamız.

1. 
   Eń uzaq múddetli paydalanıwǵa tiykarlanǵan almastırıw algoritmı (LRU – Least Recently Used). Eń nátiyjeli almastırıw algoritmı. Bul algoritm eń uzaq waqıt dawamında kirilmegen kesh qatarın almastıradı. Izertlewler sonı kórsetdi, LRU algoritmı maqul túsetuǵın algoritm menen salıstırg’anda áp-áneydey isleydi.
   

Bul algoritmdi apparatlı ámelge asırıwdıń eki usılınıń eń jaqsılar málim.
Birinshisinde esaplaǵısh hár bir kesh qatarı menen baylanısqan. Barlıq esaplag’i’shlardi’n’ quramına málim waqıt aralıǵinda birlik qosıladı. Qatarǵa kirilgende onıń esaplag’i’shi’ nolge ornatıladı. Sonday etip, eń úlken nomer eń uzın kirilmegen qatardıń esaplag’i’shi’nda boladı hám bul qatar almastırıw ushın birinshi kandidat esaplanadı.
Ekinshi usıl gezek járdeminde ámelge asıri’ladı, bul qatarlarǵa ssi’lkalar kesh qatarları toldırılǵan tártipte kiritiledi. Hár sapar bir qatarǵa mu’ra’ja’a’t etilgende, oǵan ssi’lka gezektiń aqırına ótkeriledi. Nátiyjede, hár sapar náwbette birinshi bolıp qatarǵa eń uzaq waqıt kire almaǵan ssi’lka kiredi. Aynan shu jónelis áwele almastırıladı.

2. 
   FIFO principi boyınsha isleytuǵın algoritm (birinshi bolıp, birinshi bolıp shıqtı – First In First Out). Bul algoritm keshde eń kóp bolǵan qatardı almastıradı. Algoritm kórip shıǵılǵan gezek járdeminde ańsatǵana ámelge asıri’ladı, tek parq sonda, jeńiliwge kirgennen keyin náwbettegi sáykes keletuǵın ssi’lkaniń poziciyasi’ ózgermeydi.
   
3. 
   Eń kem isletiletuǵın qatardı almastırıw algoritmı (LFU – Least Frequently Used). Bul algoritmge muwapıq, kesh yadındaǵı sızıq eń kem kiriw sanı menen almastırıladı. Algoritmdi qosımsha túrde ámelge asırıw: hár bir qatar hit esaplaǵısh menen baylanıslı bolıp, onıń quramına hár bir qońırawdan keyin qosıladı. Ózgertiw ushın tiykarǵı dawager esaplaǵısh eń kishi nomerdi óz ishine alǵan jeńiliw bolıp tabıladı.
   
4.