LIRS кэштеу алгоритмі - LIRS caching algorithm

LIRS (Төмен анықтамалық аралық қалпына келтіру жиынтығы) Бұл бетті ауыстыру алгоритмі жақсартылған өнімділікпен LRU (Ең аз жақында қолданылған) және басқа көптеген жаңа алгоритмдер.[1] Бұған «қайта пайдалану қашықтығын» қолдану арқылы қол жеткізіледі[2] ауыстыру туралы шешім қабылдау үшін қол жеткізілген беттерді динамикалық дәрежелеу үшін жергілікті көрсеткіш ретінде.

Қысқаша мазмұны

Елділікті анықтау

Бетті алмастырудың барлық алгоритмдері болғандығына сенеді анықтамалық аймақ Әр түрлі ауыстыру алгоритмдерінің негізгі айырмашылығы осы елді мекеннің біліктілігіне байланысты. LIRS локалдылықты анықтау үшін парақтың қайта пайдалану қашықтығын немесе парақтың екі дәйекті сілтемелері арасында қол жетімді нақты парақтар санын пайдаланады. Нақтырақ айтқанда, LIRS осы мақсат үшін соңғы және екіншіден соңғы сілтемелерді (егер олар бар болса) қолданады. Егер параққа бірінші рет қол жеткізілсе, оны қайта пайдалану қашықтығы шексіз. Керісінше, LRU парақтың реценсивтілігін пайдаланады, бұл парақтың сілтемесінен кейін кіретін айрықша беттердің саны, елді мекеннің санын анықтау үшін. Заманауи қатынасу тарихын ескеру үшін LIRS-ті іске асыру RD-R деп белгіленетін оның орналасуын сандық көрсеткішке айналдыру үшін парақтың қайта пайдалану қашықтығы мен рецензиясының үлкенін қолданады. Кэштің С парағына сыйымдылығы бар деп есептесек, LIRS алгоритмі жақында қол жеткізілген беттерді RD-R мәндеріне сәйкес бағалау және кэштегі ең жоғары дәрежелі С парақтарын сақтау болып табылады.

Қайта пайдалану қашықтығы мен реценция тұжырымдамаларын төмендегідей етіп бейнелеуге болады, онда T1 және T2 сәйкесінше B парағының екіншіден соңғыға дейінгі және соңғы сілтеме уақыты, ал T3 - қазіргі уақыт.

 . . . B. . . B. . . . . . . . . . B. . . . . ^ ---- Қайта пайдалану қашықтығы --- ^ - Қайталау - ^ T1 T2 T3

Жәбірленушіні ауыстыратын адамды таңдау

LIRS кэштелген беттердің және кейбір кэштелмеген беттердің метадеректерін ұйымдастырады және оларды төменде сипатталған ауыстыру операцияларын жүргізеді, олар мысалда келтірілген [3] графикте.

LIRS ауыстыру операциялары
  1. Кэш Төмен анықтамалық аралық реценцияға (LIR) және Жоғары анықтамалық аралық реценцияға (HIR) бөлінеді. LIR бөлімі ең жоғары рейтингке ие беттерді (LIR парақтарын), ал HIR бөлімі басқа парақтарды (HIR беттерін) сақтауға арналған.
  2. LIR бөлімі кэштің көп бөлігін алады және барлық LIR парақтары кэште орналасқан.
  3. Жақында қол жеткізілген барлық парақтар LIRS стегі деп аталатын FIFO кезегіне орналастырылады (графикадағы S стегі), сонымен қатар барлық HIR парақтары басқа FIFO кезегіне орналастырылады (графикадағы Q стегі).
  4. Кіру парағы S стекінің жоғарғы жағына жылжытылады және стек түбіндегі барлық HIR парақтары жойылады. Мысалы, (b) график (a) графикте В бетіне қол жеткізілгеннен кейін жасалады.
  5. Stack S ішіндегі HIR парағына кіргенде, ол LIR бетіне айналады және сәйкесінше Stack S төменгі жағындағы LIR парағы HIR бетіне айналады және Stack Q шыңына ауысады. Мысалы, график (с) кейін жасалады E парағына (а) графиктен қол жеткізуге болады.
  6. Жіберу болған кезде және резиденттік парақты ауыстыру қажет болса, Q стекінің төменгі жағында орналасқан HIR парағы ауыстыру үшін жәбірленуші ретінде таңдалады. Мысалы, (d) және (e) графиктері сәйкесінше (а) графикте D және C парақтарына қол жеткізілгеннен кейін жасалады.

Орналастыру

LIRS орналастырылды MySQL 5.1 нұсқасынан бастап.[4] Ол сондай-ақ қабылданған Infinispan деректер торы платформасы.[5] LIRS, CLOCK-Pro жуықтауы,[6] жылы қабылданған NetBSD.[7]

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Сонг Цзян және Сяодун Чжан »LIRS: буферлік кэштің өнімділігін жақсарту үшін тиімділігі төмен реценсивті ауыстыру саясатын орнату «, компьютерлік жүйелерді өлшеу және модельдеу бойынша ACM SIGMETRICS конференциясының материалдарында (SIGMETRICS'02), Марина Дель Рей, Калифорния, маусым, 2002 ж.
  2. ^ Дж.Гечси, Д.Р.Слуц және И.Л.Трейгер, «Иерархияларды сақтау техникасы», IBM Systems Journal, No2, 1970. https://pdfs.semanticscholar.org/4a58/e3066f12bb86d7aef2776e9d8a2a4e4daf3e.pdf
  3. ^ Сонг Цзян және Сяодун Чжан »LRU-ді әлсіз жерлерде жұмыс жасау жүктемесі: файл буферінің кэш өнімділігін жақсартудың жаңа алгоритмі «, IEEE Transmissions on Computers, 54 (8): 939-952, тамыз 2005 ж.
  4. ^ svn жаса - mysqldoc @ docsrva: r6768 - магистраль / ndbapi
  5. ^ Infinispan-дан шығару, пакеттік жаңартулар және LIRS
  6. ^ Сонг Цзян, Фэн Чен және Сяодун Чжан »CLOCK-Pro: сағатты ауыстыруды тиімді жетілдіру «, 2005 ж. USENIX жыл сайынғы техникалық конференциясының материалдарында (USENIX'05), Анахайм, Калифорния, сәуір, 2005 ж.
  7. ^ FreeBSD / Linux Kernel Cross Reference sys / uvm / uvm_pdpolicy_clockpro.c

Сыртқы сілтемелер

  • O (1) VM-ге қарай Linux-те кэш пен бағдарламалық жадыны теңдестіру үшін LIRS-ті қолдану туралы Рик ван Рилдің авторы.
  • A есеп беру CLOCK-Pro парағын ауыстыру туралы.
  • Бетті ауыстырудың кеңейтілген жобалары Linux жадыны басқаруды дамыту тобы құрды.
  • CLOCK-Pro патч әзірлеген Рик ван Риэль.
  • CLOCK-Pro патч Питер Зильстра әзірлеген.
  • Бөлімінде мысал ретінде CLOCK-Pro келтірілген Linux және Academia Кітапта Кәсіби Linux ядролық архитектурасы Вольфган Мауерер.
  • A қағаз LIRS және басқа алгоритмдердің өнімділік айырмашылықтарын егжей-тегжейлі сипаттайды. Али Р. Батт, Крис Гниади және Ю.Чарли Ху «Буферлік кэшті ауыстыру алгоритмдеріне ядроны алдын-ала алудың тиімділігі».