خوارزمية التخزين المؤقت لـ LIRS

الموسوعة الحرة

خوارزمية LIRS ( مجموعة المراجع المنخفضة للحداثة ) هي خوارزمية لاستبدال الصفحات تتميز بأداء محسّن مقارنةً بخوارزمية LRU (الأقل استخدامًا مؤخرًا) والعديد من خوارزميات الاستبدال الحديثة الأخرى. [ 1 ] ويتحقق ذلك باستخدام "مسافة إعادة الاستخدام" [ 2 ] كمقياس للموضع لترتيب الصفحات التي تم الوصول إليها ديناميكيًا لاتخاذ قرار الاستبدال. وقد طوّر هذه الخوارزمية كلٌ من سونغ جيانغ وشياودونغ تشانغ .

ملخص

تحديد النطاق المكاني

بينما تعتمد جميع خوارزميات استبدال الصفحات على وجود مرجعية مكانية لكي تعمل، يكمن الاختلاف الرئيسي بينها في كيفية قياس هذه المرجعية. تستخدم خوارزمية LIRS مسافة إعادة استخدام الصفحة، أي عدد الصفحات المختلفة التي تم الوصول إليها بين مرجعين متتاليين للصفحة، لقياس المرجعية. تحديدًا، تستخدم LIRS المرجع الأخير والمرجع قبل الأخير (إن وُجد) لهذا الغرض. إذا تم الوصول إلى صفحة لأول مرة، فإن مسافة إعادة استخدامها تكون لانهائية. في المقابل، تستخدم خوارزمية LRU حداثة الصفحة، أي عدد الصفحات المختلفة التي تم الوصول إليها بعد مرجع الصفحة، لقياس المرجعية. ولمراعاة سجل الوصول المُحدّث، تستخدم خوارزمية LIRS القيمة الأكبر بين مسافة إعادة الاستخدام وحداثة الصفحة كمقياس لقياس مرجعيتها، ويُشار إليها بـ RD-R. بافتراض أن ذاكرة التخزين المؤقت تحتوي على سعة C صفحة، فإن خوارزمية LIRS تقوم بترتيب الصفحات التي تم الوصول إليها مؤخرًا وفقًا لقيم RD-R الخاصة بها والاحتفاظ بأعلى C صفحة مرتبة في ذاكرة التخزين المؤقت.

يمكن تصور مفاهيم مسافة إعادة الاستخدام والحداثة كما يلي، حيث يمثل T1 و T2 وقتي المرجع قبل الأخير والأخير للصفحة B على التوالي، و T3 هو الوقت الحالي.

... ب ... ب ... ب ... ب ... ب ... ... ^---- مسافة إعادة الاستخدام ---^-- الحداثة ---^ T1 T2 T3

اختيار الضحية البديلة

يقوم LIRS بتنظيم البيانات الوصفية للصفحات المخزنة مؤقتًا وبعض الصفحات غير المخزنة مؤقتًا ويجري عمليات الاستبدال الموضحة أدناه، والتي تم توضيحها أيضًا بمثال [ 3 ] في الرسم البياني.

عمليات استبدال نظام معلومات السكك الحديدية في لونغ آيلاند
  1. تنقسم ذاكرة التخزين المؤقت إلى قسمين: قسم ذو حداثة مرجعية منخفضة (LIR) وقسم ذو حداثة مرجعية عالية (HIR). يُخصص قسم LIR لتخزين الصفحات ذات الترتيب الأعلى (صفحات LIR)، بينما يُخصص قسم HIR لتخزين بعض الصفحات الأخرى (صفحات HIR).
  2. يحتوي قسم LIR على غالبية ذاكرة التخزين المؤقت، وجميع صفحات LIR موجودة في ذاكرة التخزين المؤقت.
  3. يتم وضع جميع الصفحات التي تم الوصول إليها مؤخرًا في قائمة انتظار FIFO تسمى مكدس LIRS (المكدس S في الرسم البياني)، كما يتم وضع جميع صفحات HIR المقيمة أيضًا في قائمة انتظار FIFO أخرى (المكدس Q في الرسم البياني).
  4. تُنقل الصفحة التي تم الوصول إليها إلى أعلى المكدس S ، وتُزال أي صفحات HIR موجودة في أسفل المكدس. على سبيل المثال، يتم إنشاء الرسم البياني (ب) بعد الوصول إلى الصفحة B في الرسم البياني (أ).
  5. عند الوصول إلى صفحة HIR في المكدس S ، فإنها تتحول إلى صفحة LIR، وبناءً على ذلك، تتحول صفحة LIR الموجودة حاليًا في أسفل المكدس S إلى صفحة HIR وتنتقل إلى أعلى المكدس Q. على سبيل المثال، يتم إنتاج الرسم البياني (c) بعد الوصول إلى الصفحة E في الرسم البياني (a).
  6. عند حدوث خطأ ما، وعند الحاجة إلى استبدال صفحة موجودة، يتم اختيار صفحة HIR الموجودة في أسفل المكدس Q كصفحة مستهدفة للاستبدال. على سبيل المثال، يتم إنشاء الرسمين البيانيين (د) و(هـ) بعد الوصول إلى الصفحتين د و ج في الرسم البياني (أ)، على التوالي.

الانتشار

تم استخدام LIRS في MySQL منذ الإصدار 5.1، [ 4 ] ومرجع آخر عبر الرابط . كما تم اعتماده في منصة شبكة بيانات Infinispan . [ 5 ] ويُستخدم نظام CLOCK-Pro، وهو نسخة مُقاربة لـ LIRS، [ 6 ] في NetBSD . [ 7 ] ويُستخدم LIRS أيضًا في Apache Jackrabbit ، وهو مستودع محتوى . وتم تطوير ذاكرة تخزين مؤقتة لـ LIRS في نظام Red Hat JBoss لمحاكاة البيانات . ويُستخدم LIRS في محرك قاعدة بيانات H2 ، والذي يُسمى ذاكرة تخزين مؤقتة مقاومة للمسح . بالإضافة إلى ذلك، يُستخدم LIRS في Apache Impala ، وهو نظام لمعالجة البيانات باستخدام Hadoop.

انظر أيضاً

مراجع

  1. ↑ جيانغ، سونغ؛ تشانغ، شياودونغ (يونيو 2002). "LIRS: سياسة استبدال فعالة لمجموعة المراجع المنخفضة لتحسين أداء ذاكرة التخزين المؤقت". مجلة ACM SIGMETRICS لتقييم الأداء . 30 (1): 31-42 . doi : 10.1145/511399.511340 .
  2. ↑ ماتسون، آر إل؛ جيكسي، جيه؛ سلوتز، دي آر؛ ترايجر، آي إل (1970). "تقنيات تقييم التسلسلات الهرمية للتخزين" . مجلة أنظمة آي بي إم . 9 (2): 78-117 . doi : 10.1147/sj.92.0078 .
  3. ↑ سونغ جيانغ؛ شياودونغ تشانغ (2005). "جعل خوارزمية LRU ملائمة لأحمال العمل ذات الموقع الضعيف: خوارزمية استبدال جديدة لتحسين أداء ذاكرة التخزين المؤقت". معاملات IEEE للحواسيب . 54 (8): 939-952 . Bibcode : 2005ITCmp..54..939J . doi : 10.1109/TC.2005.130 . S2CID 11539061 . 
  4. ↑ svn commit - mysqldoc@docsrva: r6768 - trunk/ndbapi
  5. ↑ إخلاء إنفينيسبان، وتحديثات التجميع، وLIRS
  6. ↑ سونغ جيانغ، فينغ تشن، وشياودونغ تشانغ، " CLOCK-Pro: تحسين فعال لاستبدال CLOCK "، في وقائع المؤتمر التقني السنوي لعام 2005 لـ USENIX (USENIX'05)، أناهايم، كاليفورنيا، أبريل 2005.
  7. ↑ مرجع متقاطع لنواة FreeBSD/Linux sys/uvm/uvm_pdpolicy_clockpro.c
  • نحو آلة افتراضية O(1) بقلم ريك فان ريل حول الاستخدام المحتمل لـ LIRS لموازنة ذاكرة التخزين المؤقت وذاكرة البرنامج في لينكس.
  • تقرير عن تنفيذ استبدال صفحة CLOCK-Pro.
  • مشاريع استبدال الصفحات المتقدمة التي أنشأها فريق تطوير إدارة الذاكرة في نظام لينكس.
  • تم تطوير برنامج CLOCK-Pro بواسطة ريك فان ريل.
  • تم تطوير برنامج CLOCK-Pro بواسطة بيتر زيلسترا.
  • تمت الإشارة إلى CLOCK-Pro كمثال في قسم Linux والأوساط الأكاديمية في كتاب Professional Linux Kernel Architecture للمؤلف Wolfgan Mauerer.
  • ورقة بحثية توضح بالتفصيل اختلافات الأداء بين LIRS والخوارزميات الأخرى بعنوان "تأثير الأداء لجلب النواة المسبق على خوارزميات استبدال ذاكرة التخزين المؤقت" من تأليف علي ر. بوت، وكريس غنيادي، وي. تشارلي هو.