LIRS keshlash algoritmi - LIRS caching algorithm

LIRS (Kam mos yozuvlar to'plami) a sahifani almashtirish algoritmi yaxshilangan ishlashi bilan LRU (Eng kam ishlatilgan) va boshqa ko'plab yangi almashtirish algoritmlari.[1] Bunga "masofani qayta ishlatish" yordamida erishish mumkin[2] o'rnini bosuvchi qaror qabul qilish uchun kirish huquqiga ega bo'lgan sahifalarni dinamik ravishda tartiblash uchun joy ko'rsatkichi sifatida.

Xulosa

Joyni aniqlash

Barcha sahifalarni almashtirish algoritmlari mavjudligiga ishonadi mos yozuvlar joyi funktsiyalarini bajarish uchun turli xil almashtirish algoritmlari orasidagi asosiy farq bu joyning qanday malakaga ega ekanligidadir. Mahalliylikni aniqlash uchun LIRS sahifaning takroriy foydalanish masofasidan yoki sahifaning ketma-ket ikkita havolasi orasida kirilgan alohida sahifalar sonidan foydalanadi. Xususan, LIRS ushbu maqsadlar uchun oxirgi va ikkinchidan so'nggi ma'lumotlarga (agar mavjud bo'lsa) foydalanadi. Agar sahifaga birinchi marta kirilsa, uni qayta ishlatish masofasi cheksizdir. Aksincha, LRU sahifani qayta tiklanishidan foydalanadi, bu joyni aniqlash uchun sahifaga havola qilinganidan keyin kiradigan o'ziga xos sahifalar soni. Zamonaviy kirish tarixini hisobga olish uchun, LIRS-ni amalga oshirish aslida RD-R deb belgilangan joyning miqdorini aniqlash uchun o'lchov sifatida sahifani qayta ishlatish masofasini va takrorlanishini kattaroq hajmidan foydalanadi. Keshni C sahifalar hajmiga ega deb hisoblasak, LIRS algoritmi yaqinda kirilgan sahifalarni RD-R qiymatlari bo'yicha saralash va keshdagi eng yuqori reytingga ega sahifalarni saqlab qolishdir.

Qayta foydalanish masofasi va qayta tiklanish tushunchalarini quyidagi tarzda tasavvur qilish mumkin, bunda T1 va T2 navbati bilan B sahifaning ikkinchi oxirgi va oxirgi murojaat vaqti, T3 esa hozirgi vaqt hisoblanadi. 

 . . . B. . . B. . . . . . . . . . B. . . . . ^ ---- Masofani qayta ishlatish --- ^ - Qayta ishlash - ^ T1 T2 T3

O'z o'rnini bosuvchi jabrlanuvchini tanlash

LIRS keshlangan sahifalar va ba'zi bir keshlanmagan sahifalar metama'lumotlarini tartibga soladi va ularni quyida tavsiflangan almashtirish operatsiyalarini bajaradi, ular misol bilan ham tasvirlangan [3] grafada.

LIRSni almashtirish operatsiyalari
  1. Kesh mos yozuvlar oralig'idagi past darajadagi (LIR) va yuqori ma'lumotli intervalgacha (HIR) bo'linishga bo'lingan. LIR bo'limi eng yuqori darajadagi sahifalarni (LIR sahifalarini) va HIR bo'limini ba'zi boshqa sahifalarni (HIR sahifalarini) saqlashdan iborat.
  2. LIR bo'limi keshning katta qismini egallaydi va barcha LIR sahifalari keshda joylashgan.
  3. Yaqinda kirilgan barcha sahifalar LIRS stekasi deb nomlangan FIFO navbatiga joylashtirilgan (grafadagi S to'plami) va barcha doimiy HIR sahifalari yana boshqa FIFO navbatiga joylashtirilgan (grafikdagi stack Q).
  4. Kirish qilingan sahifa Stack S-ning yuqori qismiga ko'chiriladi va stakning pastki qismidagi HIR-sahifalar o'chiriladi. Masalan, (b) grafika (a) grafada B sahifaga kirgandan keyin hosil bo'ladi.
  5. Stack S-dagi HIR sahifasiga kirilganda, u LIR sahifasiga aylanadi va shunga ko'ra hozirda Stack S ning pastki qismida joylashgan LIR sahifasi HIR sahifasiga aylanadi va Stack Q-ning yuqori qismiga o'tadi. Masalan, grafika (c) keyin hosil bo'ladi sahifa E ga (a) grafada kirish mumkin.
  6. Agar miss bo'lsa va rezident sahifani almashtirish kerak bo'lsa, Stack Q ning pastki qismida joylashgan HIR sahifasi almashtirish uchun qurbon sifatida tanlanadi. Masalan, (d) va (e) grafalar (a) grafasida D va C sahifalariga tegishlicha kirgandan so'ng hosil bo'ladi.

Joylashtirish

LIRS joylashtirilgan MySQL 5.1 versiyasidan beri.[4] Shuningdek, u qabul qilingan Infinispan ma'lumotlar tarmog'i platformasi.[5] LIRS, CLOCK-Pro,[6] yilda qabul qilingan NetBSD.[7]

Shuningdek qarang

Adabiyotlar

  1. ^ Song Jiang va Xiaodong Zhang "LIRS: Bufer-kesh ishlashini yaxshilash uchun samaradorlik darajasi past bo'lgan intervalgacha o'zgaruvchanlikni o'zgartirish siyosati. ", Kompyuter tizimlarini o'lchash va modellashtirish bo'yicha ACM SIGMETRICS konferentsiyasi (SIGMETRICS'02), Marina Del Rey, KA, iyun, 2002 yil.
  2. ^ J. Gecsei, D. R. Slutz va I. L. Traiger, "Saqlash iyerarxiyasini baholash texnikasi", IBM Systems Journal, 1970 yil 2-son. https://pdfs.semanticscholar.org/4a58/e3066f12bb86d7aef2776e9d8a2a4e4daf3e.pdf
  3. ^ Song Tszyan va Xiaodong Chjan "LRU-ni zaif joylarga mos ish yuklari: Fayl buferi keshining ishlashini yaxshilash uchun yangi algoritmni almashtirish algoritmi. ", IEEE Transmissions on Computers, 54 (8): 939-952, avgust 2005 yil.
  4. ^ svn commit - mysqldoc @ docsrva: r6768 - magistral / ndbapi
  5. ^ Infinispan evakuatsiyasi, ommaviy yangilanishlar va LIRS
  6. ^ Song Jiang, Feng Chen va Xiaodong Zhang "CLOCK-Pro: soatni almashtirishni samarali takomillashtirish ", 2005 yil USENIX yillik texnik konferentsiyasi (USENIX'05) materiallarida, Anaxaym, CA, 2005 yil aprel.
  7. ^ FreeBSD / Linux Kernel Cross Reference sys / uvm / uvm_pdpolicy_clockpro.c

Tashqi havolalar

  • O (1) VM tomon Linuxda kesh va dastur xotirasini muvozanatlash uchun LIRS-dan foydalanish mumkinligi haqida Rik van Riel tomonidan yozilgan.
  • A hisobot CLOCK-Pro sahifasini almashtirishni amalga oshirish to'g'risida.
  • Sahifani almashtirish bo'yicha ilg'or loyihalar Linux xotirasini boshqarishni rivojlantirish jamoasi tomonidan tashkil etilgan.
  • CLOCK-Pro yamoq Rik van Riel tomonidan ishlab chiqilgan.
  • CLOCK-Pro yamoq Piter Zilstra tomonidan ishlab chiqilgan.
  • CLOCK-Pro bo'limida misol sifatida keltirilgan Linux va Academia Kitobda Professional Linux yadrosi arxitekturasi Volfgan Mauerer tomonidan.
  • A qog'oz Ali R. Butt, Kris Gniadi va Y. Charli Xu tomonidan yaratilgan LIRS va boshqa algoritmlarning ishlash samaradorligini "Buffer keshini almashtirish algoritmlariga yadro oldindan olishning ta'siri".