Виртуалды жадты жүзеге асыру алгоритмдері және беттерді алмастыру

Виртуалды жадты басқарудағы беттерді алмастыру алгоритмдері: қағидалары, мақсаты, тиімділігі. Жадыны оңтайландыру, жүйе жұмысын жақсарту туралы біліңіз.

16 мин оқу

100%

Дереккөз: Page replacement algorithm — Wikipedia

Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.

Мазмұны

Кіріспе

Виртуалды жадты іске асыру алгоритмі, парақтандыруға тән алгоритмдер.

Компьютерлік операциялық жүйеде виртуалды жадты басқару үшін парақтандыру қолданылса, бет алмастыру алгоритмдері жад беттерін қай бетке шығаруды (кейде ауыстырып алу деп аталады) немесе жад беті бөлінуі қажет болғанда дискіге жазуды шешеді. Бет алмастыру, сұралған бет жадыда болмаған кезде (бет қатесі) және бөлуді қанағаттандыру үшін бос бетті пайдалану мүмкін болмағанда болады, себебі бос беттер жоқ немесе бос беттердің саны белгілі бір шектен төмен. Алмастыру үшін таңдалған және дискіге жазылған бетке қайта сілтеме жасалғанда, оны жадыға қайтару қажет (дискіден оқу), бұл I/O аяқталуын күтуді білдіреді. Осы күту уақытының аздығы бет алмастыру алгоритмінің сапасын анықтайды: жадға беттерді кіргізуге күту уақыты аз болған сайын алгоритм жақсырақ болады. Бет алмастыру алгоритмі аппараттық қамтамасыз ету арқылы ұсынылған беттерге қолжетімділік туралы шектеулі ақпаратты қарастырады және бет қатесінің жалпы санын азайту үшін қай беттерді алмастыру керектігін болжауға тырысады, сонымен қатар алгоритмнің өзінің шығындарымен (негізгі жад және процессор уақыты) теңестіреді. Бет алмастыру мәселесі – бәсекелестік талдау тұрғысынан қарағанда, оптималды детерминистік алгоритм белгілі бір типтік онлайн мәселесі болып табылады.

Тарих

Бет алмастыру алгоритмдері 1960 және 1970 жылдары зерттеулер мен пікірталастардың қызу тақырыбы болды. Бұл көбінесе күрделі LRU (ең соңғы пайдаланылған) жуықтамалары мен жұмыс жиынтығы алгоритмдерін әзірлеумен аяқталды. Содан бері дәстүрлі бет алмастыру алгоритмдері жасаған кейбір негізгі болжамдар күшін жойды, нәтижесінде зерттеулер қайта жанданды. Атап айтқанда, негізгі аппараттық және пайдаланушы деңгейіндегі бағдарламалық жасақтаманың мінез-құлқындағы келесі тенденциялар бет алмастыру алгоритмдерінің өнімділігіне әсер етті: Негізгі жадтың көлемі бірнеше есе ұлғайды. Бірнеше гигабайт негізгі жадымен, әрбір жад блогын үнемі тексеруді қажет ететін алгоритмдер азайып, тәжірибеде аз қолданылатын болып келеді. Жад иерархиясы биікке көтерілді. CPU кэшінің қатесінің құны әлдеқайда қымбат. Бұл бұрынғы мәселені одан әрі күшейтеді. Пайдаланушы бағдарламалық жасақтамасының жергіліктілігі әлсіреді. Бұл көбінесе объектіге бағытталған бағдарламалау техникаларының таралуына, үлкен мөлшердегі шағын функцияларды қолдануға, ағаштар және хэш-кестелер сияқты күрделі дерек құрылымдарын пайдалануға, олар хаотикалық жад сілтеме үлгілеріне әкеп соқтырады, және қоқыс жинаудың пайда болуына байланысты, ол қолданбалардың жадқа қатынасу мінез-құлқын күрт өзгертті. Бет алмастыру алгоритмдеріне қойылатын талаптар операциялық жүйе ядросының архитектурасындағы айырмашылықтарға байланысты өзгерді. Атап айтқанда, қазіргі заманғы OS ядроларының көпшілігі виртуалды жад пен файлдық жүйе кэштерін біріктіреді, бұл бет алмастыру алгоритміне пайдаланушы бағдарламасының виртуалды адрестік кеңістіктеріндегі және кэштелген файлдардағы беттердің арасынан бір бетті таңдауды талап етеді. Соңғы беттердің ерекше қасиеттері бар. Мысалы, олар құлыпталуы мүмкін немесе журналдау арқылы жазу тәртібі талаптарына ие болуы мүмкін. Сонымен қатар, бет алмастырудың мақсаты жадты күтудің жалпы уақытын азайту болғандықтан, ол жадты бөлуді жүзеге асыратын басқа ядролық кіші жүйелердің жад талаптарын ескеруі керек. Нәтижесінде, қазіргі заманғы ядроларда (Linux, FreeBSD және Solaris) бет алмастыру виртуалды жадтың жоғары деңгейінде емес, жалпы мақсаттағы ядролық жад бөлуші деңгейінде жұмыс істейді.

Page replacement algorithms were a hot topic of research and debate in the 1960s and 1970s. That mostly ended with the development of sophisticated LRU (least recently used) approximations and working set algorithms. Since then, some basic assumptions made by the traditional page replacement algorithms were invalidated, resulting in a revival of research. In particular, the following trends in the behavior of underlying hardware and user level software have affected the performance of page replacement algorithms:

Size of primary storage has increased by multiple orders of magnitude. With several gigabytes of primary memory, algorithms that require a periodic check of each and every memory frame are becoming less and less practical. Memory hierarchies have grown taller. The cost of a CPU cache miss is far more expensive. This exacerbates the previous problem. Locality of reference of user software has weakened. This is mostly attributed to the spread of object oriented programming techniques that favor large numbers of small functions, use of sophisticated data structures like trees and hash tables that tend to result in chaotic memory reference patterns, and the advent of garbage collection that drastically changed memory access behavior of applications. Requirements for page replacement algorithms have changed due to differences in operating system kernel architectures. In particular, most modern OS kernels have unified virtual memory and file system caches, requiring the page replacement algorithm to select a page from among the pages of both user program virtual address spaces and cached files. The latter pages have specific properties. For example, they can be locked, or can have write ordering requirements imposed by journaling. Moreover, as the goal of page replacement is to minimize total time waiting for memory, it has to take into account memory requirements imposed by other kernel sub systems that allocate memory. As a result, page replacement in modern kernels (Linux, FreeBSD, and Solaris) tends to work at the level of a general purpose kernel memory allocator, rather than at the higher level of a virtual memory subsystem.

Жергілікті және жаһандық алмастыру

Ауыстыру алгоритмдері жергілікті немесе жаһандық болуы мүмкін. Процесс бет қатесіне тап болғанда, жергілікті бет ауыстыру алгоритмі сол процесске тиесілі (немесе жад бөлімін бөлісетін процестер тобына) бір бетті ауыстыруға таңдайды. Жаһандық ауыстыру алгоритмі жадтағы кез келген бетті таңдауға құқылы. Жергілікті бет ауыстыру, белгілі бір процесске немесе процестер тобына қанша бет бөлу керектігін анықтайтын жадты бөлуді талап етеді. Бөлудің ең көп таралған түрлері – жұмыс жиынтығы моделіне негізделген тұрақты бөлу және теңгерілген жиынтық алгоритмдері. Жергілікті бет ауыстырудың артықшылығы – оның кеңейтімділігі: әрбір процесс өз бетімен бет қатесін дербес шеше алады, нәтижесінде сол процесс үшін тұрақты өнімділік қамтамасыз етіледі. Дегенмен, жаһандық бет ауыстыру жалпы жүйелік деңгейде тиімдірек.

Қай беттерге сілтеме жасалып , өзгертілгенін анықтау

Қазіргі заманғы жалпы мақсаттағы компьютерлер мен кейбір кіріктірілген процессорлар виртуалды жадты қолдайды. Әрбір процесс өзінің виртуалды адрестік кеңістігіне ие. Бет кестесі процесс виртуалды мекенжайларының бір бөлігін физикалық мекенжайларға шартады. Сонымен қатар, көптеген архитектураларда бет кестесі әрбір бет үшін "кіру" биті мен "өзгертілген" битін сақтайды. Процесс сол бетке жадты оқығанда немесе жазғанда процессор кіру битін қояды. Процесс сол бетке жад жазғанда процессор өзгертілген битін қояды. Операциялық жүйе кіру және өзгертілген биттерді өзгерте алады. Операциялық жүйе жад пен файлдарға кіруді келесідей анықтай алады:
Процесс бет кестесіндегі беттердегі кіру битін нөлдеу арқылы. Біраз уақыттан кейін операциялық жүйе бет кестесін сканерлеп, процессор қойған кіру биті бар беттерді іздейді. Бұл жылдам, себебі кіру биті процессормен автоматты түрде қойылады, бірақ дәл емес, өйткені операциялық жүйе кіру туралы дереу хабар алмайды және процесс осы беттерге кірген тәртіп туралы ақпаратқа ие болмайды. Процесс бет кестесінен беттерді физикалық жадтан алып тастау арқылы. Келесі кіру дереу анықталады, себебі ол бет қатесін тудырады. Бұл баяу, себебі бет қатесі операциялық жүйеге контексттік ауысуды, сәйкес физикалық мекенжайды бағдарламалық іздеуді, бет кестесін өзгертуді және процеске контексттік ауысуды қамтиды, бірақ дәл, себебі кіру орын алғаннан кейін бірден анықталады. Процесс жүйелік шақырулар жасағанда тікелей, олар POSIX-те оқу және жазу сияқты бет кэшін қолжетімді етеді.

Алдын ала тазалау

Көптеген алмастыру алгоритмдері мақсатты бетті ғана қайтарады. Бұл, егер мақсатты бет кір бет болса (яғни, бетті қайта пайдалану алдында тұрақты сақтауға жазылуы тиіс деректерді қамтиды), онда осы бетті тұрақты сақтауға жіберу үшін (бетті тазалау үшін) I/O операциясы басталуы керек дегенді білдіреді. Виртуалды жадтың алғашқы жылдарында тазалауға жұмсалатын уақытқа көп мән берілмеді, себебі виртуалды жад тұрақты сақтауға толық дуплекстік арналары бар жүйелерде алғаш рет іске асырылды және тазалау әдетте беттерді ауыстырумен үйлестірілді. Ал қазіргі заманғы тұтынушылық аппараттық құралдары толық дуплекстік деректерді жіберуді қолдамайды, сондықтан мақсатты беттерді тазалау мәселесі туындайды. Осы жағдайды шешу үшін түрлі алдын ала тазалау саясаттары қолданылады. Алдын ала тазалау – бұл кір беттерде I/O операциясын бастайтын механизм, олар (вероятно) жақын арада алмастырылуы мүмкін. Осы идея бойынша, алдын ала тазаланған бетті алмастыру үшін таңдаған кезде I/O операциясы аяқталып, бет таза болады. Алдын ала тазалау келесі алмастырылатын беттерді анықтау мүмкіндігіне негізделген. Шамадан тыс алдын ала тазалау I/O өткізу қабілетін босқа жұмсайды, себебі қайтадан кір беттерді жазып, оларды алмастыру үшін таңдайды.

(h,k) -кеңдеу проблемасы

(h,k) бет ауыстыру мәселесі – бет ауыстыру мәселесі моделінің жалпыламасы: h және k оң бүтін сандар болсын. Біз белгілі бір өлшемдегі кэштің алгоритмінің теориялық тұрғыдан оңтайлы бет ауыстыру алгоритмімен салыстырылған өнімділігін өлшейміз. Егер , онда біз оңтайлы бет ауыстыру алгоритмін айтарлықтай аз ресурстармен қамтамасыз етеміз. (h,k) бет ауыстыру мәселесі – онлайн алгоритмнің өнімділігін оңтайлы алгоритмнің өнімділігімен салыстыру арқылы бағалау тәсілі болып табылады, бұл ретте онлайн алгоритмнің кэш өлшемі мен оңтайлы алгоритмнің кэш өлшемі жеке-жеке параметрленеді.

Белгілеу алгоритмдері

Белгілеу алгоритмдері – беттеу алгоритмдерінің жалпы класы. Әрбір бетке оның белгісі деп аталатын бит тағайындалады. Бастапқыда барлық беттер белгісіз деп белгіленеді. Беттік сұраныстардың бір кезеңінде (жұмыс кезеңі немесе сұраныстар тізбегі) бет алғаш рет сұралғанда белгіленеді. Белгілеу алгоритмі – бұл белгіленген бетті ешқашан жадтан шығармайтын алгоритм. Егер ALG k көлеміндегі кэшпен белгілеу алгоритмі болса, ал OPT h көлеміндегі кэшпен оңтайлы алгоритм болса, онда ALG бәсекеге қабілетті. Осылайша, кез келген белгілеу алгоритмі бәсекеге қабілетті коэффициентке жетеді. LRU белгілеу алгоритмі болып табылады, ал FIFO – белгілеу алгоритмі емес.

Консервативті алгоритмдер

Алгоритм консервативті деп аталады, егер кез келген тізбектелген сұраулар тізбегінде, егер онда k немесе одан аз түрлі бетке сілтемелер болса, алгоритм k немесе одан аз бет қатесін тудырса. Егер ALG k өлшемді кэшпен консервативті алгоритм болса, ал OPT сол өлшемдегі кэшпен оптималды алгоритм болса, онда ALG бәсекеге қабілетті. Осылайша, кез келген консервативті алгоритм бәсекеге қабілеттілік коэффициентіне жетеді. LRU, FIFO және CLOCK – консервативті алгоритмдер.

Бетті ауыстыру алгоритмдері

Жаңа беттерді алмастыру алгоритмдерінің әртүрлі түрлері бар: бұл алгоритм келесідей жұмыс істейді: жаңа бетті ауыстыру қажет болғанда, операциялық жүйе болашақта пайдалануы ең алыс болатын бетті ауыстырып шығарады. Мысалы, келесі 6 секунд ішінде пайдаланылмайтын бет, келесі 0,4 секунд ішінде пайдаланылатын беттің орнына ауыстырылады. Бұл алгоритмді жалпы мақсаттағы операциялық жүйеде іске асыру мүмкін емес, өйткені беттің пайдаланылуына дейін қанша уақыт өтетінін сенімді түрде есептеу қиын. Бұл тек жүйеде іске қосылатын барлық бағдарламалық қамтамасы алдын ала белгілі болса және оның жадқа сілтеме жасау үлгілерін статикалық талдау арқылы зерделеуге болады, немесе орындалу кезінде талдауға мүмкіндік беретін қосымшалар класы болған жағдайда ғана мүмкін. Осы шектеуге қарамастан, жақын-оптималды өнімділік бере алатын алгоритмдер бар. Операциялық жүйе бағдарлама сілтеме жасаған барлық беттерді қадағалайды және осы деректерді кейінгі іске қосылуларда қай беттерді ауыстыру керектігін шешу үшін пайдаланады. Бұл алгоритм жақын-оптималды өнімділік бере алады, бірақ бағдарламаның алғашқы іске қосылуында емес, және тек бағдарламаның жадқа сілтеме жасау үлгісі әр іске қосылуда салыстырмалы түрде тұрақты болса ғана. Беттеу мәселесін талдау онлайн алгоритмдер саласында да жүргізілді. Беттеу мәселесі үшін кездейсоқ онлайн алгоритмдердің тиімділігі амортизациялық талдау арқылы өлшенеді.

Соңғы кезде қолданылмаған

Жақында пайдаланылмаған (NRU) беттерді алмастыру алгоритмі – жақында пайдаланылған беттерді жадыда сақтауға басымдық беретін алгоритм. Бұл алгоритм келесі принцип бойынша жұмыс істейді: бетке сілтеме жасалғанда, сол бет үшін сілтеме биті қойылып, ол сілтеме жасалған бет ретінде белгіленеді. Сол сияқты, бет өзгертілгенде (жазылғанда) өзгертілген биті қойылады. Биттерді орнату әдетте аппараттық құралдар арқылы жасалады, бірақ бағдарламалық деңгейде де жасау мүмкін. Белгілі бір уақыт интервалында таймерлік үзіліс туындайды және барлық беттердің сілтеме битін нөлдейді, сондықтан тек ағымдағы таймер интервалында сілтеме жасалған беттер ғана сілтеме битімен белгіленеді. Бетті алмастыру қажет болғанда, операциялық жүйе беттерді төрт классқа бөледі:

3. сілтеме жасалған, өзгертілген
2. сілтеме жасалған, өзгертілмеген
1. сілтеме жасалмаған, өзгертілген
0. сілтеме жасалмаған, өзгертілмеген

Бетті өзгерту және сілтеме жасалмауы мүмкін болмаса да, бұл 3-ші классқа жататын беттің сілтеме биті таймерлік үзіліс арқылы нөлденген кезде болады. NRU алгоритмі ең төменгі категориядағы бетті кездейсоқ түрде алып тастау үшін таңдайды. Жоғарыда аталған төрт бет категориясының ішінде NRU алгоритмі сілтеме жасалмаған, өзгертілмеген бетті алмастырады, егер мұндай бет болса. Бұл алгоритм соңғы таймер интервалында сілтеме жасалмаған, бірақ өзгертілген беттің, сілтеме жасалған, бірақ өзгертілмеген бетке қарағанда маңыздылығы төмен екенін көрсетеді. NRU – бұл белгілеу алгоритмі, сондықтан ол бәсекеге қабілетті.

Бірінші кіруші, бірінші шығушы

Бетті алмастырудың ең қарапайым алгоритмі FIFO алгоритмі болып табылады. Бірінші кірген, бірінші шыққан (FIFO) бетті алмастыру алгоритмі – операциялық жүйе тарапынан аз көлемде есеп жүргізуді талап ететін, төмен шығынды алгоритм. Атынан-ақ идеясы түсінікті: операциялық жүйе жадтағы барлық беттерді кезекте сақтайды, ең соңғы түскені кезек соңында, ал ең ескісі – басында болады. Бетті алмастыру қажет болғанда, кезек басындағы бет (ең ескі бет) таңдалады. FIFO арзан әрі түсінікті болғанымен, практикалық қолдануда тиімсіз жұмыс істейді. Сондықтан ол өзгертілмеген күйінде сирек қолданылады. Бұл алгоритм Беляди аномалиясын көрсетеді. Қарапайым тілмен айтқанда, бет қатесі кезінде жадыда ең ұзақ уақыт болған фрейм алмастырылады. FIFO бет алмастыру алгоритмі OpenVMS операциялық жүйесінде, кейбір өзгерістермен қолданылады. Шешілген екінші мүмкіндік дұрыс аударма кестесіне сілтемелері бар шектеулі жазбаларды өткіріп жіберу арқылы қамтамасыз етіледі, сондай-ақ беттер процестің жұмыс жиынтығынан жүйелік жиынтыққа жылжытылады, олар қайта қолданылмаса, оларды қалпына келтіруге болады. FIFO консервативті алгоритм, сондықтан ол бәсекеге қабілетті.

Екінші мүмкіндік

FIFO бет алмастыру алгоритмінің, екінші мүмкіндік бет алмастыру алгоритмі деп аталатын өзгертілген түрі, жақсартуға келетін шығын аз болғандықтан FIFO-дан салыстырмалы түрде жақсы жұмыс істейді. Ол FIFO сияқты кезектің басына қарап жұмыс істейді, бірақ сол бетті бірден алмастырудың орнына, оның пайдаланылған биті орнатылған-орнатылмағанын тексереді. Егер ол орнатылмаса, бет алмастырылады. Әйтпесе, пайдаланылған биті нөлдендіріледі, бет кезектің соңына (жаңа беттей) қосылады және осы процесс қайталанады. Бұл шеңберлі кезек ретінде де қарастырылуы мүмкін. Егер барлық беттердің пайдаланылған биті орнатылған болса, тізімдегі бірінші бетті екінші рет кездестіргенде, оның пайдаланылған биті нөлденгендіктен, ол алмастырылады. Егер барлық беттердің пайдаланылған биті нөлденген болса, екінші мүмкіндік алгоритмі қарапайым FIFO алгоритміне дейін төмендейді. Аты айтқандай, екінші мүмкіндік әр бетке "екінші мүмкіндік" сыйлайды – бұрын пайдаланылған ескі бет, әдетте қолданыста болады және жаңа, пайдаланылмаған беттің орнына алмастырылмауы керек.

Сағат

Сағат, Екінші мүмкіндікке қарағанда FIFO-ның тиімдірек түрі, себебі беттерді тізімнің соңына үнемі жылжыту қажеттілігі болмайды, бірақ ол Екінші мүмкіндік сияқты бірдей жалпы функцияны атқарады. Сағат алгоритмі жадтағы беттердің шеңберлі тізімін ұстайды, ал "қол" (итератор) тізімдегі соңғы қарастырылған беттік жаққа нұсқайды. Егер беттік қате туындаса және бос жақтаулар болмаса, "қолдың" орналасқан жеріндегі R (қабылданған) биті тексеріледі. Егер R 0 болса, жаңа бет "қол" көрсеткен беттің орнына қойылады және қол бір қадамға жылжытылады. Әйтпесе, R биті нөлдендіріледі, содан кейін сағат тілі бірге өседі және бір бет ауыстырылғанша процесс қайталанады. Бұл алгоритмді алғаш рет 1969 жылы Фернандо Ж. Корбато сипаттаған.

Сағаттың түрлері

GCLOCK: Жалпыланған сағат бет алмастыру алгоритмі. Clock Pro жақында сілтеме жасалған беттер туралы ақпараттың дөңгелек тізімін сақтайды, оның ішінде жадтағы барлық M беттері және соңғы M беті, сондай-ақ жадтан шығарылған беттер де бар. Жадтан шығарылған беттер туралы қосымша ақпарат, ARC сақтайтын ұқсас ақпарат сияқты, үлкен циклдарда және бір реттік сканерлеулерде LRU-дан жақсы жұмыс істеуге көмектеседі. WSclock. Сағат алгоритмін жұмыс жиынтығы (яғни, белгілі бір уақыт аралығында осы процесс қолданатын беттер жиынтығы) тұжырымдамасымен біріктіру арқылы алгоритмнің өнімділігін жақсартуға болады. Іс жүзінде, «қарттау» (aging) алгоритмі және «WSClock» алгоритмі ең маңызды бет алмастыру алгоритмдері болып табылады. Адаптивті алмастырумен сағат (CAR) – ARC-мен салыстырылатын өнімділікке ие және LRU және CLOCK-тан әлдеқайда жақсы жұмыс істейтін бет алмастыру алгоритмі. CAR алгоритмі өздігінен реттеліп, пайдаланушы белгілеген арнайы параметрлерді қажет етпейді. CLOCK консервативті алгоритм болғандықтан, бәсекеге қабілетті.

Соңғы кезде қолданылған

Ең соңғы пайдаланылған (LRU) бет алмастыру алгоритмі, NRU-ға есімдері ұқсас болғанымен, LRU беттерді пайдалануды қысқа мерзім ішінде қадағалайды, ал NRU тек соңғы уақыт аралығындағы пайдалануды қарастырады. LRU идеясы – өткен бірнеше нұсқауда ең көп пайдаланылған беттер, келесі бірнеше нұсқауда да жиі пайдаланылуы мүмкін дегенге негізделген. LRU теориялық тұрғыдан жақын-оптималды өнімділік бере алады (бейімделмелі алмастыру кэші сияқты жақсы), бірақ оны іс жүзінде жүзеге асыру өте қымбат. Бұл алгоритмді жүзеге асырудың бірнеше әдісі бар, олар шығындарды азайтуға тырысады, бірақ мүмкіндігінше өнімділікті сақтайды. Ең қымбат әдіс – жадтағы барлық беттерді қамтитын тізімді пайдалану, яғни байланысты тізім әдісі. Бұл тізімнің соңында ең соңғы пайдаланылған бет, ал басында – ең соңғы пайдаланылған бет орналасады. Осы жүзеге асырудың құны – тізімдегі элементтерді әр жадқа сілтеме жасаған сайын жылжыту қажеттігінде, бұл өте көп уақыт алатын процесс. Тағы бір әдіс, ол аппараттық қолдауды қажет етеді: аппаратта әр нұсқауда өсетін 64 биттік санағыш бар деп есептейік. Бетке қол жеткенде, ол бетке қол жеткен кезде санағыштың мәнін алады. Бетті алмастыру қажет болғанда, операциялық жүйе ең төменгі санағыш мәніне ие бетті таңдап, оны ауыстырады. Жүзеге асыру шығындарына байланысты, LRU-ға ұқсас, бірақ арзанрақ жүзеге асыруды ұсынатын алгоритмдерді (олардың ішінде келесілері) қарастыруға болады. LRU алгоритмінің маңызды артықшылығы – ол толық статистикалық талдауға жарамды. Мысалы, LRU OPT алгоритміне қарағанда N еседен артық бет қатесіне себеп болмайтыны дәлелденді, мұнда N басқарылатын жиынғы беттер санына пропорционал. Екінші жағынан, LRU-дың кемшілігі – оның өнімділігі көптеген кең таралған сілтеме үлгілерінде нашарлауға бейім. Мысалы, егер LRU жиынтығында N бет болса, N+1 беттен тұратын массив бойынша циклді орындайтын қосымша әрбір қол жеткенде бет қатесі тудырады. Үлкен массивтердегі циклдер жиі кездесетіндіктен, мұндай жағдайларда жақсы жұмыс істеу үшін LRU-ны өзгертуге көп күш жұмсалды. Ұсынылған LRU-дың көптеген модификациялары циклдық сілтеме үлгілерін анықтауға және ең соңғы пайдаланылған (MRU) сияқты қолайлы алмастыру алгоритміне ауысуға тырысады.

The least recently used (LRU) page replacement algorithm, though similar in name to NRU, differs in the fact that LRU keeps track of page usage over a short period of time, while NRU just looks at the usage in the last clock interval. LRU works on the idea that pages that have been most heavily used in the past few instructions are most likely to be used heavily in the next few instructions too. While LRU can provide near optimal performance in theory (almost as good as adaptive replacement cache), it is rather expensive to implement in practice. There are a few implementation methods for this algorithm that try to reduce the cost yet keep as much of the performance as possible. The most expensive method is the linked list method, which uses a linked list containing all the pages in memory. At the back of this list is the least recently used page, and at the front is the most recently used page. The cost of this implementation lies in the fact that items in the list will have to be moved about every memory reference, which is a very time consuming process. Another method that requires hardware support is as follows: suppose the hardware has a 64 bit counter that is incremented at every instruction. Whenever a page is accessed, it acquires the value equal to the counter at the time of page access. Whenever a page needs to be replaced, the operating system selects the page with the lowest counter and swaps it out. Because of implementation costs, one may consider algorithms (like those that follow) that are similar to LRU, but which offer cheaper implementations. One important advantage of the LRU algorithm is that it is amenable to full statistical analysis. It has been proven, for example, that LRU can never result in more than N times more page faults than OPT algorithm, where N is proportional to the number of pages in the managed pool. On the other hand, LRU's weakness is that its performance tends to degenerate under many quite common reference patterns. For example, if there are N pages in the LRU pool, an application executing a loop over array of N + 1 pages will cause a page fault on each and every access. As loops over large arrays are common, much effort has been put into modifying LRU to work better in such situations. Many of the proposed LRU modifications try to detect looping reference patterns and to switch into suitable replacement algorithm, like Most Recently Used (MRU).

LRU нұсқалары

LRU K соңғы K рет қол жеткен беттердің ең көнесін шығарады. Мысалы, LRU 1 қарапайым LRU, ал LRU 2 беттерді соңғы рет екінші рет қол жеткен уақытына сәйкес шығарады. LRU K уақыт бойынша локальдық қасиеттері тұрғысынан LRU-дан әлдеқайда жақсы. ARC алгоритмі LRU-ны жақында шығарылған беттердің тарихын сақтап, осы арқылы жақында немесе жиі қол жеткізілуіне қарай басымдық беруді өзгертеді. Ол тізбектеп сканерлеуге қарсы тұрады. 2Q алгоритмі LRU және LRU/2 алгоритмдерін жақсартады. Екі кезек болғандықтан, біреуі «желдетілген» элементтер үшін, екіншісі «суық» элементтер үшін, элементтер алдымен «суық» кезекке қойылады, ал екінші рет қол жеткеннен кейін «желдетілген» элементтерге көшіріледі. Қосылған элементтерге сілтемелер LRU және LRU/2 алгоритмдеріне қарағанда ұзақ сақталады, сондықтан ол кэштің тиімділігін арттыратын жақсы «желдетілген» кезекке ие. ARC-ді басқа алгоритмдермен (LRU, MQ, 2Q, LRU 2, LRFU, LIRS) Megiddo & Modha 2004 жұмысынан салыстыруға болады. LRU – бұл белгілеу алгоритмі, сондықтан ол бәсекеге қабілетті.

Кездейсоқ

Кездейсоқ ауыстыру алгоритмі жадтағы кездейсоқ бетті алмастырады. Бұл бетке сілтеме жасауды қадағалаудың қосымша шығындарын жояды. Әдетте, ол FIFO-дан жақсы жұмыс істейді, ал жадқа циклдік сілтемелер жасалғанда LRU-дан да жақсы нәтиже береді, бірақ көбінесе LRU практикада тиімдірек болады. OS/390 жаһандық LRU жуықтауын қолданады және LRU өнімділігі нашарлағанда кездейсоқ ауыстыруға көшеді, ал Intel i860 процессоры кездейсоқ ауыстыру саясатын қолданған (Rhodehamel 1989).

Жиі қолданылмайтын (NFU)

Не жиі қолданылатын (NFU) бет ауыстыру алгоритміне бір санаушы қажет, және әр беттің бастапқыда 0-ге орнатылған жеке санауышы болады. Әрбір уақыт аралығында, сол аралықта сілтеме жасалған барлық беттердің санауышы 1-ге артады. Іс жүзінде, санаушылар беттің қанша рет қолданылғанын тіркеп отырады. Осылайша, ең төмен санауышы бар бет қажет болған жағдайда ауыстырылуы мүмкін. NFU-дың басты мәселесі – ол пайдалану жиілігін, пайдалану уақытына қарамастан қадағалайды. Мысалы, көп өтетін компиляторда, бірінші өту кезінде көп пайдаланылған, бірақ екінші өтуде қажеті жоқ беттер, екінші өтуде салыстырмалы түрде аз пайдаланылған беттерге қарағанда жоғары жиілік санауыштары болғандықтан, артықшылыққа ие болады. Бұл нашар өнімділікке алып келеді. NFU-дың осы сияқты жұмыс істейтін басқа да жағдайлар бар, мысалы, операциялық жүйенің (OS) жүктелуі. Құдайға шүкір, ұқсас және жақсырақ алгоритм бар, оның сипаттамасы төменде келтірілген. Бет алмастыру алгоритмі жиі қолданылмайтын жағдайда, бет кестесінде нөлдік көрсеткіштер болғанда, соңғы пайдаланылған бетті ауыстыру алгоритміне қарағанда, азырақ бет қателіктерін тудырады.

Ең ұзақ қашықтықтан бірінші (LDF) бетті ауыстыру алгоритмі

Бұл алгоритмнің негізгі идеясы LRU-да қолданылатын сілтемелік жақындық принципі, бірақ LDF-де жақындық пайдаланылған сілтемелерге емес, қашықтыққа негізделген. LDF-де ағымдағы беттен ең алыс қашықтықта тұрған бет ауыстырылады. Егер екі беттің ара қашықтығы бірдей болса, сағат тіліне қарсы айналым бойынша ағымдағы бетке жақын тұрған бет ауыстырылады.

Бағалау биті жоқ аппараттық техника

Жоғарыда талқыланған көптеген техникалар әрбір бетке сәйкес сілтеме бітінің болуын қабылдайды. Кейбір аппараттық құралдарда мұндай біт жоқ, сондықтан тиімді пайдалану үшін осы бітсіз жұмыс істейтін техникалар қажет. Бір көрнекті мысал – OpenVMS жүйесінде жұмыс істейтін VAX аппараттық құралдары. Бұл жүйе бет өзгертілгенін біледі, бірақ бет оқылған-оқылмағанын міндетті түрде білмейді. Оның тәсілі Екіншілік бет кэштеу деп аталады. Жұмыс жиынтығынан (әдетте, процестің жеке жадысынан) алынған беттер физикалық жадыда біраз уақытқа қалып, арнайы тізімдерге орналастырылады. Жұмыс жиынтығынан бетті алып тастау техникалық тұрғыдан бетті алмастыру операциясы емес, бірақ ол бетті үміткер ретінде белгілейді. Қайта жазудың қажеті жоқ немесе мазмұны бұзылмаған (dirty) беттер бос беттер тізімінің соңына қойылады. Сақталған мазмұнын жазуды қажет ететін беттер өзгертілген беттер тізіміне қойылады. Бұл әрекеттер әдетте бос беттер тізімінің мөлшері реттелетін шектен төмен түскенде орындалады. Жұмыс жиынтығынан беттерді шығару үшін, жақсы таңдау жасалмаса, болашақта физикалық жадыдан алынбастан бұрын бос немесе өзгертілген тізімнен сол бет қайтарылып алынады деп күтіледі, кездейсоқ әдіс қолданылуы мүмкін. Осылай сілтеме жасалған беттер бос немесе өзгертілген тізімнен алынып, процестің жұмыс жиынтығына қайта орналастырылады. Өзгертілген беттер тізімі бірнеше беттен тұратын топтарда беттерді сақтауға мүмкіндік береді, бұл тиімділікті арттырады. Осы беттерді бос беттер тізіміне орналастыруға болады. Бос беттер тізімінің басына жететін беттер тізбегі LRU немесе NRU механизмінің нәтижелеріне ұқсайды және жалпы әсері бұрын сипатталған Екінші мүмкіндік алгоритміне ұқсас. Тағы бір мысал – ARM жүйесіндегі Linux ядросы. Аппараттық мүмкіндіктердің жетіспеушілігі екі беттік кестелерді ұсыну арқылы толықтырылады: процессордың түпкілікті беттік кестелері, сілтемеленген және өзгертілген биттері жоқ, және қажетті биттері бар бағдарламалық қамтамасыз етумен басқарылатын беттік кестелер. Бағдарламалық қамтамасыз ету кестесіндегі эмуляцияланған биттер бет қателері арқылы орнатылады. Бет қателерін алу үшін екінші кестедегі эмуляцияланған биттерді тазалау сәйкес бетке кіру құқықтарының бір бөлігін жояды, бұл түпкілікті кестені өзгерту арқылы жүзеге асырылады.

Many of the techniques discussed above assume the presence of a reference bit associated with each page. Some hardware has no such bit, so its efficient use requires techniques that operate well without one. One notable example is VAX hardware running OpenVMS. This system knows if a page has been modified, but not necessarily if a page has been read. Its approach is known as Secondary Page Caching. Pages removed from working sets (process private memory, generally) are placed on special purpose lists while remaining in physical memory for some time. Removing a page from a working set is not technically a page replacement operation, but effectively identifies that page as a candidate. A page whose backing store is still valid (whose contents are not dirty, or otherwise do not need to be preserved) is placed on the tail of the Free Page List. A page that requires writing to backing store will be placed on the Modified Page List. These actions are typically triggered when the size of the Free Page List falls below an adjustable threshold. Pages may be selected for working set removal in an essentially random fashion, with the expectation that if a poor choice is made, a future reference may retrieve that page from the Free or Modified list before it is removed from physical memory. A page referenced this way will be removed from the Free or Modified list and placed back into a process working set. The Modified Page List additionally provides an opportunity to write pages out to backing store in groups of more than one page, increasing efficiency. These pages can then be placed on the Free Page List. The sequence of pages that works its way to the head of the Free Page List resembles the results of a LRU or NRU mechanism and the overall effect has similarities to the Second Chance algorithm described earlier. Another example is used by the Linux kernel on ARM. The lack of hardware functionality is made up for by providing two page tables – the processor native page tables, with neither referenced bits nor dirty bits, and software maintained page tables with the required bits present. The emulated bits in the software maintained table are set by page faults. In order to get the page faults, clearing emulated bits in the second table revokes some of the access rights to the corresponding page, which is implemented by altering the native table.