سياسات استبدال ذاكرة التخزين المؤقت

📅 آخر تحديث: ١٩ يوليو ٢٠٢٦
✍️ نُشر في: ١٩ يوليو ٢٠٢٦
📷 يحتوي على 14 صور
الموسوعة الحرة

في مجال الحوسبة ، تُعرف سياسات استبدال البيانات في الذاكرة المؤقتة (أو خوارزميات استبدال البيانات في الذاكرة المؤقتة ) بأنها تعليمات أو خوارزميات مُحسِّنة يمكن لبرنامج حاسوبي أو بنية مُدارة بواسطة الأجهزة استخدامها لإدارة ذاكرة مؤقتة للمعلومات. يُحسِّن التخزين المؤقت الأداء من خلال الاحتفاظ بعناصر البيانات الحديثة أو المُستخدمة بكثرة في مواقع ذاكرة أسرع أو أقل تكلفة حسابية من مواقع الذاكرة العادية. عندما تمتلئ الذاكرة المؤقتة، يجب على الخوارزمية اختيار العناصر التي يجب التخلص منها لإفساح المجال لبيانات جديدة.

ملخص

متوسط ​​وقت الوصول إلى الذاكرة هو [ 1 ]

تي=م×تيم+تيح+هـ{\displaystyle T=m\times T_{m}+T_{h}+E}

أين

م{\displaystyle m}نسبة الخطأ = 1 - (نسبة الإصابة)
تيم{\displaystyle T_{m}}= الوقت اللازم للوصول إلى الذاكرة الرئيسية عند حدوث خطأ (أو، مع ذاكرة تخزين مؤقت متعددة المستويات، متوسط ​​وقت مرجع الذاكرة لذاكرة التخزين المؤقت الأدنى التالي)
تيح{\displaystyle T_{h}}= زمن الوصول: الوقت اللازم للوصول إلى ذاكرة التخزين المؤقت (يجب أن يكون هو نفسه في حالات النجاح والفشل)
هـ{\displaystyle E}= التأثيرات الثانوية، مثل تأثيرات الانتظار في أنظمة المعالجات المتعددة

تعتمد ذاكرة التخزين المؤقت على معيارين أساسيين: زمن الاستجابة ونسبة الوصول الناجح. كما تؤثر عدة عوامل ثانوية على أداء ذاكرة التخزين المؤقت. [ 1 ]

يصف معدل الوصول في ذاكرة التخزين المؤقت عدد مرات العثور على عنصر مطلوب. وتعتمد استراتيجيات الاستبدال الأكثر كفاءة على تتبع المزيد من معلومات الاستخدام لتحسين معدل الوصول لحجم ذاكرة تخزين مؤقت محدد. أما زمن استجابة ذاكرة التخزين المؤقت فيصف المدة التي تستغرقها ذاكرة التخزين المؤقت لإعادة العنصر المطلوب بعد طلبه عند العثور عليه. وعادةً ما تعتمد استراتيجيات الاستبدال الأسرع على تتبع معلومات استخدام أقل، أو لا تعتمد على أي معلومات في حالة ذاكرة التخزين المؤقت ذات التعيين المباشر، وذلك لتقليل الوقت اللازم لتحديث المعلومات. وتمثل كل استراتيجية استبدال حلاً وسطاً بين معدل الوصول وزمن الاستجابة.

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

السياسات

خوارزمية بلادي

تتمثل خوارزمية التخزين المؤقت الأكثر كفاءة في التخلص من المعلومات التي لن تكون مطلوبة لأطول فترة زمنية؛ وتُعرف هذه الخوارزمية بخوارزمية بيلادي المثلى، أو سياسة الاستبدال المثلى، أو خوارزمية الاستبصار . ونظرًا لاستحالة التنبؤ عمومًا بمدى الحاجة إلى المعلومات في المستقبل، فإن تطبيق هذه الخوارزمية غير عملي. ويمكن حساب الحد الأدنى العملي بعد إجراء التجارب، ومن ثم مقارنة فعالية خوارزمية التخزين المؤقت المختارة.

مخطط خوارزمية بلادي

عند حدوث خطأ في الصفحة ، تكون مجموعة من الصفحات موجودة في الذاكرة. في المثال، يتم الوصول إلى التسلسل 5، 0، 1 بواسطة الإطار 1، والإطار 2، والإطار 3 على التوالي. عند الوصول إلى القيمة 2، تحل محل القيمة 5 (الموجودة في الإطار 1)، مما يشير إلى أن القيمة 5 لن يتم الوصول إليها في المستقبل القريب. ولأن نظام التشغيل العام لا يستطيع التنبؤ بموعد الوصول إلى القيمة 5، فلا يمكن تطبيق خوارزمية بيلادي عليه.

الاستبدال العشوائي (RR)

تعتمد خوارزمية الاستبدال العشوائي على اختيار عنصر والتخلص منه لإفساح المجال عند الحاجة. لا تتطلب هذه الخوارزمية الاحتفاظ بسجل الوصول. وقد استُخدمت في معالجات ARM لبساطتها [ 3 ] ، كما أنها تتيح محاكاة عشوائية فعّالة [ 4 ] .

سياسات بسيطة قائمة على قوائم الانتظار

الأول في الأول خارج (FIFO)

باستخدام هذه الخوارزمية، تتصرف ذاكرة التخزين المؤقت مثل قائمة انتظار FIFO ؛ فهي تقوم بإخراج الكتل بالترتيب الذي تمت إضافتها به، بغض النظر عن عدد مرات الوصول إليها من قبل.

نظام الوارد الأخير الذي يخرج أولاً (LIFO) أو نظام الوارد الأول الذي يخرج أخيراً (FILO)

تتصرف ذاكرة التخزين المؤقت مثل المكدس ، على عكس قائمة الانتظار FIFO. تقوم ذاكرة التخزين المؤقت بإخراج الكتلة المضافة مؤخرًا أولاً، بغض النظر عن عدد مرات الوصول إليها سابقًا.

غربال

SIEVE هي خوارزمية إخلاء بسيطة مصممة خصيصًا لذاكرة التخزين المؤقت للويب، مثل ذاكرة التخزين المؤقت للقيم الرئيسية وشبكات توصيل المحتوى. تعتمد هذه الخوارزمية على مبدأ الترقية الكسولة والتخفيض السريع. [ 5 ] لذلك، لا تُحدِّث SIEVE بنية البيانات العامة عند الوصول إلى ذاكرة التخزين المؤقت، بل تُؤجِّل التحديث حتى وقت الإخلاء؛ وفي الوقت نفسه، تُخلِص الكائنات المُضافة حديثًا بسرعة لأن أحمال عمل ذاكرة التخزين المؤقت تميل إلى إظهار نسب عالية من الوصول لمرة واحدة، ومعظم الكائنات الجديدة لا تستحق الاحتفاظ بها في ذاكرة التخزين المؤقت. تستخدم SIEVE طابور FIFO واحدًا، وتستخدم مؤشرًا متحركًا لاختيار الكائنات المراد إخلاؤها. تحتوي الكائنات في ذاكرة التخزين المؤقت على بت واحد من البيانات الوصفية يُشير إلى ما إذا كان قد طُلب الكائن بعد إدخاله إلى ذاكرة التخزين المؤقت. يشير مؤشر الإخلاء إلى ذيل الطابور في البداية، ثم يتحرك نحو الرأس بمرور الوقت. بالمقارنة مع خوارزمية CLOCK للإخلاء، تبقى الكائنات المُحتفظ بها في SIEVE في موضعها القديم. لذلك، تكون الكائنات الجديدة دائمًا في الرأس، والكائنات القديمة دائمًا في الذيل. مع تحرك اليد نحو الرأس، يتم إخراج الأشياء الجديدة بسرعة (تخفيض سريع للرتبة). [ 6 ]

سياسات بسيطة تعتمد على الحداثة

الأقل استخدامًا مؤخرًا (LRU)

يتخلص هذا الأسلوب من العناصر الأقل استخدامًا أولًا. يتطلب هذا الأسلوب تتبع ما تم استخدامه ومتى، وهو أمر مرهق. يتطلب "بتات عمر" لخطوط التخزين المؤقت ، ويتتبع خط التخزين المؤقت الأقل استخدامًا بناءً على هذه البتات. عند استخدام خط تخزين مؤقت، يتغير عمر خطوط التخزين المؤقت الأخرى. LRU هي عائلة من خوارزميات التخزين المؤقت ، تشمل 2Q من تطوير ثيودور جونسون ودينيس شاشا [ 7 ] وLRU/K من تطوير بات أونيل وبيتي أونيل وجيرهارد ويكوم [ 8 ] . تسلسل الوصول في المثال هو ABCDEDF.

مثال توضيحي لخوارزمية LRU

عند تثبيت ABCD في الكتل ذات أرقام التسلسل (بزيادة 1 مع كل وصول جديد) والوصول إلى E، يُعتبر ذلك خطأً ويجب تثبيته في كتلة. باستخدام خوارزمية LRU، سيحل E محل A لأن A له أدنى رتبة (A(0)). في الخطوة قبل الأخيرة، يتم الوصول إلى D وتحديث رقم التسلسل. ثم يتم الوصول إلى F، ليحل محل B - الذي كان له أدنى رتبة (B(1)). 

خوارزمية الوقت، الأقل استخدامًا مؤخرًا (TLRU)

خوارزمية TLRU (الأقل استخدامًا مؤخرًا مع مراعاة الوقت) [ 9 ] هي نسخة معدلة من خوارزمية LRU، مصممة للاستخدام عندما يكون لمحتويات ذاكرة التخزين المؤقت فترة صلاحية محددة. تُناسب هذه الخوارزمية تطبيقات ذاكرة التخزين المؤقت الشبكية، مثل الشبكات المرتكزة على المعلومات (ICN) وشبكات توصيل المحتوى (CDN) والشبكات الموزعة بشكل عام. تُقدم خوارزمية TLRU مصطلحًا جديدًا: TTU (وقت الاستخدام)، وهو عبارة عن طابع زمني للمحتوى (أو الصفحة) يُحدد مدة صلاحية المحتوى بناءً على موقعه وناشره. يُتيح TTU مزيدًا من التحكم لمسؤول النظام المحلي في إدارة تخزين الشبكة.

عند وصول محتوى خاضع لخوارزمية TLRU، تقوم عقدة التخزين المؤقت بحساب قيمة TTU المحلية بناءً على قيمة TTU التي يحددها ناشر المحتوى. تُحسب قيمة TTU المحلية باستخدام دالة مُعرَّفة محليًا. بعد حساب قيمة TTU المحلية، يتم استبدال جزء من المحتوى الإجمالي لعقدة التخزين المؤقت. تضمن خوارزمية TLRU استبدال المحتوى الأقل استخدامًا والأقصر عمرًا بالمحتوى الوارد.

الأكثر استخدامًا مؤخرًا (MRU)

على عكس خوارزمية LRU، تتخلص خوارزمية MRU من العناصر الأكثر استخدامًا أولًا. في المؤتمر الحادي عشر لقواعد البيانات الكبيرة جدًا (VLDB)، صرّح تشو وديويت قائلين: "عندما يتم مسح ملف بشكل متكرر بنمط مرجعي [متسلسل حلقي]، فإن خوارزمية MRU هي أفضل خوارزمية استبدال ." [ 10 ] وأشار باحثون قدموا عروضهم في المؤتمر الثاني والعشرين لقواعد البيانات الكبيرة جدًا (VLDB) إلى أنه بالنسبة لأنماط الوصول العشوائي وعمليات المسح المتكررة لمجموعات البيانات الكبيرة (المعروفة أيضًا بأنماط الوصول الدورية)، فإن خوارزميات ذاكرة التخزين المؤقت MRU تحقق عددًا أكبر من مرات الوصول مقارنةً بخوارزمية LRU نظرًا لميلها إلى الاحتفاظ بالبيانات الأقدم. [ 11 ] تُعد خوارزميات MRU أكثر فائدة في الحالات التي يكون فيها احتمال الوصول إلى العنصر الأقدم أكبر. تسلسل الوصول في المثال هو ABCDECDB:

مخطط خوارزمية MRU

تُوضع الكتل ABCD في الذاكرة المؤقتة لوجود مساحة كافية. عند الوصول الخامس (E)، تُستبدل الكتلة التي كانت تحتوي على D بالكتلة E لأنها استُخدمت مؤخرًا. عند الوصول التالي (إلى D)، تُستبدل الكتلة C لأنها الكتلة التي تم الوصول إليها قبل D مباشرةً.

LRU المجزأ (SLRU)

تُقسّم ذاكرة التخزين المؤقت SLRU إلى قسمين: تجريبي ومحمي. تُرتّب الأسطر في كل قسم من الأحدث إلى الأقل استخدامًا. تُضاف البيانات المفقودة إلى ذاكرة التخزين المؤقت عند الطرف الأحدث استخدامًا من القسم التجريبي. تُزال البيانات الصحيحة من مكانها وتُضاف إلى الطرف الأحدث استخدامًا من القسم المحمي؛ حيث تم الوصول إلى الأسطر في القسم المحمي مرتين على الأقل. القسم المحمي محدود؛ قد يؤدي نقل سطر من القسم التجريبي إلى القسم المحمي إلى نقل سطر LRU في القسم المحمي إلى الطرف الأحدث استخدامًا من القسم التجريبي، مما يمنح هذا السطر فرصة أخرى للوصول إليه قبل استبداله. يُعدّ حدّ حجم القسم المحمي مُعاملًا في SLRU يتغير وفقًا لأنماط أحمال الإدخال/الإخراج . عندما يجب التخلص من البيانات من ذاكرة التخزين المؤقت، تُؤخذ الأسطر من الطرف LRU للقسم التجريبي. [ 12 ]

تقريبات LRU

قد تكون خوارزمية LRU مكلفة في الذاكرة المؤقتة ذات الترابط العالي . عادةً ما تستخدم الأجهزة العملية تقريبًا لتحقيق أداء مماثل بتكلفة أجهزة أقل.

خوارزمية شبه الأقل استخداماً (PLRU)

بالنسبة لذاكرة التخزين المؤقت لوحدة المعالجة المركزية ذات الترابط العالي (عادةً أكثر من أربعة اتجاهات)، تصبح تكلفة تنفيذ خوارزمية LRU باهظة. في العديد من ذاكرات التخزين المؤقت لوحدة المعالجة المركزية، تكفي خوارزمية تتجاهل دائمًا تقريبًا أحد العناصر الأقل استخدامًا؛ يختار العديد من مصممي وحدات المعالجة المركزية خوارزمية PLRU، التي لا تحتاج إلا إلى بت واحد لكل عنصر في ذاكرة التخزين المؤقت. تتميز خوارزمية PLRU عادةً بنسبة خطأ أقل قليلاً، وزمن استجابة أفضل قليلاً، واستهلاك طاقة أقل قليلاً من خوارزمية LRU، وتكاليف إضافية أقل .

تعمل البتات كشجرة ثنائية من مؤشرات بت واحد تشير إلى شجرة فرعية أقل استخدامًا مؤخرًا. يُحدد تتبع سلسلة المؤشرات إلى عقدة الورقة المرشح البديل. عند الوصول، تُضبط جميع المؤشرات في السلسلة من عقدة ورقة المسار الذي تم الوصول إليه إلى عقدة الجذر لتشير إلى شجرة فرعية لا تحتوي على المسار الذي تم الوصول إليه. تسلسل الوصول في المثال هو ABCDE:

مثال بياني لـ LRU الزائف

عند الوصول إلى قيمة (مثل A) ولم تكن موجودة في الذاكرة المؤقتة، يتم تحميلها من الذاكرة الرئيسية ووضعها في الكتلة التي تشير إليها الأسهم في المثال. بعد وضع هذه الكتلة، تُعكس الأسهم لتشير في الاتجاه المعاكس. يتم وضع A وB وC وD؛ تحل E محل A مع امتلاء الذاكرة المؤقتة لأن الأسهم كانت تشير إليها، ثم تُعكس الأسهم التي كانت تؤدي إلى A لتشير في الاتجاه المعاكس (إلى B، الكتلة التي سيتم استبدالها عند عدم وجودها في الذاكرة المؤقتة في المرة القادمة).

كلوك برو

لا يمكن تطبيق خوارزمية LRU في المسار الحرج لأنظمة الحاسوب، مثل أنظمة التشغيل ، نظرًا لتكاليفها الإضافية العالية؛ لذا يُستخدم Clock ، وهو تقريب لخوارزمية LRU، بشكل شائع. يُعد Clock-Pro تقريبًا لخوارزمية LIRS لتنفيذه بتكلفة منخفضة في الأنظمة. [ 13 ] يعتمد Clock-Pro على إطار عمل Clock الأساسي، مع ثلاث مزايا: فهو يحتوي على ثلاثة "عقارب" (على عكس عقرب Clock الواحد)، ويمكنه قياس مسافة إعادة استخدام البيانات تقريبًا. ومثل LIRS، يمكنه إزالة عناصر البيانات ذات الوصول لمرة واحدة أو ذات الموقع المنخفض بسرعة . يتميز Clock-Pro بنفس تعقيد Clock، ولكنه سهل التنفيذ بتكلفة منخفضة. يجمع تطبيق استبدال المخزن المؤقت في إصدار 2017 من Linux بين خوارزميتي LRU وClock-Pro. [ 14 ] [ 15 ]

سياسات بسيطة تعتمد على التردد

الأقل استخداماً (LFU)

تحسب خوارزمية LFU عدد مرات استخدام عنصر ما؛ وتُستبعد العناصر الأقل استخدامًا أولًا. وهذا مشابه لخوارزمية LRU، إلا أنها تخزن عدد مرات الوصول إلى كتلة ما بدلًا من تاريخ الوصول إليها. أثناء تنفيذ تسلسل الوصول، تُزال الكتلة الأقل استخدامًا من الذاكرة المؤقتة.

الأقل استخدامًا مؤخرًا (LFRU)

تجمع خوارزمية LFRU (الأقل استخدامًا مؤخرًا) [ 16 ] بين مزايا خوارزميتي LFU وLRU. تُعدّ LFRU مناسبة لتطبيقات ذاكرة التخزين المؤقت للشبكة، مثل شبكات المعلومات (ICN ) وشبكات توصيل المحتوى (CDN ) والشبكات الموزعة عمومًا. في LFRU، تُقسّم ذاكرة التخزين المؤقت إلى قسمين: قسم ذو امتيازات وقسم بدون امتيازات. القسم ذو الامتيازات محمي، وإذا كان المحتوى شائعًا، يُنقل إليه. عند استبدال القسم ذي الامتيازات، تُزيل LFRU المحتوى من القسم بدون امتيازات، وتُنقل المحتوى من القسم ذي الامتيازات إليه، وتُدرج المحتوى الجديد في القسم ذي الامتيازات. تُستخدم خوارزمية LRU للقسم ذي الامتيازات، وخوارزمية LFU التقريبية (ALFU) للقسم بدون امتيازات.

LFU مع الشيخوخة الديناميكية (LFUDA)

يستخدم أحد المتغيرات، وهو التحديث الأخير مع التقادم الديناميكي (LFUDA)، التقادم الديناميكي لاستيعاب التغيرات في مجموعة من الكائنات الشائعة؛ حيث يضيف عامل عمر ذاكرة التخزين المؤقت إلى عدد المراجع عند إضافة كائن جديد إلى ذاكرة التخزين المؤقت أو إعادة الإشارة إلى كائن موجود. يزيد LFUDA عمر ذاكرة التخزين المؤقت عند إخراج الكتل عن طريق تعيينه إلى قيمة مفتاح الكائن المُخرج، ويكون عمر ذاكرة التخزين المؤقت دائمًا أقل من أو يساوي الحد الأدنى لقيمة المفتاح في ذاكرة التخزين المؤقت. [ 17 ] إذا كان يتم الوصول إلى كائن ما بشكل متكرر في الماضي وأصبح غير شائع، فسيبقى في ذاكرة التخزين المؤقت لفترة طويلة (مما يمنع الكائنات الجديدة أو الأقل شيوعًا من استبداله). يقلل التقادم الديناميكي من عدد هذه الكائنات، مما يجعلها مؤهلة للاستبدال، ويقلل LFUDA من تلوث ذاكرة التخزين المؤقت الناتج عن التحديث الأخير عندما تكون ذاكرة التخزين المؤقت صغيرة.

S3-FIFO

هذه خوارزمية إخلاء جديدة صُممت عام ٢٠٢٣. بالمقارنة مع الخوارزميات الحالية، التي تعتمد في الغالب على خوارزمية LRU (الأقل استخدامًا مؤخرًا)، تستخدم خوارزمية S3-FIFO ثلاث طوابير FIFO فقط: طابور صغير يشغل ١٠٪ من مساحة التخزين المؤقت، وطابور رئيسي يشغل ٩٠٪ من مساحة التخزين المؤقت، وطابور وهمي يخزن بيانات تعريف الكائنات فقط. يُستخدم الطابور الصغير لتصفية الكائنات التي يتم الوصول إليها مرة واحدة فقط خلال فترة زمنية قصيرة؛ ويُستخدم الطابور الرئيسي لتخزين الكائنات الشائعة، ويستخدم إعادة الإدخال لإبقائها في التخزين المؤقت؛ ويُستخدم الطابور الوهمي لاكتشاف الكائنات التي يُحتمل أن تكون شائعة والتي يتم إخلاؤها من الطابور الصغير. تُضاف الكائنات أولًا إلى الطابور الصغير (إذا لم يتم العثور عليها في الطابور الوهمي، وإلا تُضاف إلى الطابور الرئيسي). عند إخراج عنصر من قائمة الانتظار الصغيرة، إذا تم طلبه، تتم إعادته إلى قائمة الانتظار الرئيسية، وإلا يتم إخراجه وتتبع بياناته الوصفية في قائمة الانتظار الوهمية. [ 18 ]

سياسات على غرار RRIP

تُعد سياسات RRIP أساسًا لسياسات استبدال ذاكرة التخزين المؤقت الأخرى، بما في ذلك Hawkeye. [ 19 ]

التنبؤ بالفاصل الزمني لإعادة الإشارة (RRIP)

تُعدّ RRIP [ 20 ] سياسة مرنة، اقترحتها شركة إنتل ، تهدف إلى توفير مقاومة جيدة للمسح الضوئي مع السماح بإخراج أسطر ذاكرة التخزين المؤقت القديمة التي لم يُعاد استخدامها. لكل سطر من أسطر ذاكرة التخزين المؤقت قيمة تنبؤ، تُسمى RRPV (قيمة تنبؤ إعادة الإشارة)، والتي من المفترض أن تتوافق مع الوقت المتوقع لإعادة استخدام السطر. عادةً ما تكون قيمة RRPV عالية عند الإدخال؛ فإذا لم يُعاد استخدام سطر ما قريبًا، فسيتم إخراجه لمنع عمليات المسح الضوئي (كميات كبيرة من البيانات تُستخدم مرة واحدة فقط) من ملء ذاكرة التخزين المؤقت. عند إعادة استخدام سطر من أسطر ذاكرة التخزين المؤقت، تُضبط قيمة RRPV على الصفر، مما يشير إلى أن السطر قد أُعيد استخدامه مرة واحدة ومن المرجح إعادة استخدامه مرة أخرى.

في حالة عدم العثور على البيانات في الذاكرة المؤقتة، يتم إخراج السطر الذي يساوي قيمة RRPV القصوى الممكنة؛ ففي حالة القيم المكونة من 3 بتات، يتم إخراج السطر الذي تساوي قيمة RRPV فيه 7 (2 ^3 - 1). إذا لم يكن هناك أي سطر بهذه القيمة، يتم زيادة جميع قيم RRPV في المجموعة بمقدار 1 حتى يصل أحدها إلى هذه القيمة. يلزم وجود معيار فاصل، وعادةً ما يكون السطر الأول على اليسار. هذه الزيادة ضرورية لضمان معالجة الأسطر القديمة بشكل صحيح وإخراجها إذا لم يُعاد استخدامها.

العلاج الإشعاعي الثابت (SRRIP)

يقوم SRRIP بإدراج الأسطر بقيمة RRPV maxRRPV؛ وسيكون السطر الذي تم إدراجه للتو هو الأكثر عرضة للإخراج عند عدم وجود ذاكرة تخزين مؤقتة.

معدل الإصابة بالفشل الكلوي المزمن ثنائي النمط (BRRIP)

يعمل بروتوكول SRRIP بشكل جيد في الظروف العادية، ولكنه يعاني من انخفاض الأداء عندما تكون مجموعة العمل أكبر بكثير من حجم ذاكرة التخزين المؤقت، مما يؤدي إلى حدوث تضارب في البيانات . يتم التغلب على هذه المشكلة بإدراج أسطر بقيمة RRPV تساوي maxRRPV في معظم الأحيان، وإدراج أسطر بقيمة RRPV تساوي maxRRPV - 1 بشكل عشوائي باحتمالية منخفضة. يؤدي هذا إلى "تثبيت" بعض الأسطر في ذاكرة التخزين المؤقت، مما يساعد على منع التضارب. مع ذلك، يُضعف بروتوكول BRRIP الأداء عند الوصول إلى البيانات دون حدوث تضارب. يُحقق بروتوكول SRRIP أفضل أداء عندما تكون مجموعة العمل أصغر من حجم ذاكرة التخزين المؤقت، بينما يُحقق بروتوكول BRRIP أفضل أداء عندما تكون مجموعة العمل أكبر من حجم ذاكرة التخزين المؤقت.

RRIP الديناميكي (DRRIP)

تستخدم خوارزمية DRRIP [ 20 ] تقنية المبارزة بين المجموعات [ 21 ] لتحديد ما إذا كان سيتم استخدام SRRIP أو BRRIP. تخصص هذه الخوارزمية عددًا قليلاً من المجموعات (عادةً 32 مجموعة) لاستخدام SRRIP وعددًا آخر لاستخدام BRRIP، وتستخدم عدادًا للسياسات يراقب أداء المجموعات لتحديد السياسة التي سيتم استخدامها من قبل باقي ذاكرة التخزين المؤقت.

سياسات تقارب خوارزمية بلادي

تُعدّ خوارزمية بيلادي السياسة الأمثل لاستبدال البيانات في الذاكرة المؤقتة، لكنها تتطلب معرفة مسبقة بالمستقبل لإزالة الأسطر التي سيُعاد استخدامها لأبعد مسافة في المستقبل. وقد اقتُرحت عدة سياسات استبدال تحاول التنبؤ بمسافات إعادة الاستخدام المستقبلية من أنماط الوصول السابقة، [ 22 ] مما يسمح لها بتقريب السياسة الأمثل للاستبدال. وتسعى بعض أفضل سياسات استبدال البيانات في الذاكرة المؤقتة إلى محاكاة خوارزمية بيلادي.

هوك آي

يحاول برنامج Hawkeye [ 19 ] محاكاة خوارزمية Bélády باستخدام عمليات الوصول السابقة التي أجراها جهاز الكمبيوتر للتنبؤ بما إذا كانت عمليات الوصول التي ينتجها تُولّد عمليات وصول مُلائمة لذاكرة التخزين المؤقت (تُستخدم لاحقًا) أو عمليات وصول غير مُلائمة لها (لا تُستخدم لاحقًا). يقوم البرنامج بأخذ عينات من عدد من مجموعات ذاكرة التخزين المؤقت غير المُحاذية، ويستخدم سجلًا بطول8×حجم ذاكرة التخزين المؤقت{\displaystyle 8\times {\text{حجم ذاكرة التخزين المؤقت}}}ويحاكي خوارزمية بيلادي على عمليات الوصول هذه. يسمح هذا للسياسة بتحديد الأسطر التي كان ينبغي تخزينها مؤقتًا وتلك التي لا ينبغي، متوقعًا ما إذا كانت التعليمات مناسبة للتخزين المؤقت أم لا. ثم تُغذى هذه البيانات إلى RRIP؛ حيث يكون للوصول من التعليمات المناسبة للتخزين المؤقت قيمة RRPV أقل (من المرجح إخراجها لاحقًا)، بينما يكون للوصول من التعليمات غير المناسبة للتخزين المؤقت قيمة RRPV أعلى (من المرجح إخراجها عاجلًا). يتخذ نظام RRIP الخلفي قرارات الإخراج. يحدد كل من ذاكرة التخزين المؤقت المأخوذة عينات منها ومولد OPT قيمة RRPV الأولية لأسطر ذاكرة التخزين المؤقت المُدرجة. فاز Hawkeye ببطولة CRC2 للتخزين المؤقت في عام 2017، [ 23 ] وHarmony [ 24 ] هو امتداد لـ Hawkeye يُحسّن أداء الجلب المسبق.

انظر إلى التعليق
مخطط انسيابي لسياسة استبدال مخبأ موكينج جاي

الطائر المقلد

يحاول برنامج Mockingjay [ 25 ] تحسين برنامج Hawkeye بعدة طرق. فهو يتخلى عن التنبؤ الثنائي، مما يسمح له باتخاذ قرارات أكثر دقة بشأن أي أسطر ذاكرة التخزين المؤقت يجب إخراجها، ويترك قرار أي سطر ذاكرة تخزين مؤقت يجب إخراجه لحين توفر المزيد من المعلومات.

يحتفظ برنامج Mockingjay بذاكرة تخزين مؤقتة مُختارة من عمليات الوصول الفريدة، وأجهزة الكمبيوتر التي أنتجتها، وطوابعها الزمنية. عند الوصول إلى سطر في ذاكرة التخزين المؤقتة المُختارة مرة أخرى، يُرسل فرق التوقيت إلى مُتنبئ مسافة إعادة الاستخدام (RDP). يستخدم RDP تقنية تعلم الفرق الزمني [ 26 ] ، حيث تُزاد أو تُنقص قيمة RDP الجديدة بمقدار صغير للتعويض عن القيم الشاذة؛ ويُحسب هذا المقدار على النحو التالي:w=مين(1،فرق التوقيت16){\displaystyle w=\min \left(1,{\frac {\text{فرق الطابع الزمني}}{16}}\right)}إذا لم يتم تهيئة القيمة، تُدرج مسافة إعادة الاستخدام المُلاحظة مباشرةً. إذا كانت ذاكرة التخزين المؤقت التي تم أخذ عينات منها ممتلئة، وكان لا بد من حذف سطر، يُوجَّه بروتوكول سطح المكتب البعيد (RDP) إلى أن جهاز الكمبيوتر الذي وصل إليها آخر مرة يُنتج عمليات وصول متدفقة.

عند الوصول إلى البيانات أو إضافتها، يتم تحديث وقت إعادة الاستخدام المُقدَّر (ETR) لهذا السطر ليعكس مسافة إعادة الاستخدام المتوقعة. في حالة عدم العثور على البيانات في ذاكرة التخزين المؤقت، يتم إخراج السطر ذي أعلى قيمة ETR. يُحقق خوارزمية Mockingjay نتائج قريبة من خوارزمية Bélády المثلى.

سياسات التعلم الآلي

سعت العديد من السياسات إلى استخدام الشبكات العصبية ، وسلاسل ماركوف ، أو أنواع أخرى من التعلم الآلي للتنبؤ بالخط الذي يجب إزالته. [ 27 ] [ 28 ] كما توجد خوارزميات معززة بالتعلم لاستبدال ذاكرة التخزين المؤقت. [ 29 ] [ 30 ]

سياسات أخرى

مجموعة المراجع المنخفضة للحداثة (LIRS)

LIRS هي خوارزمية لاستبدال الصفحات تتفوق في الأداء على خوارزمية LRU وغيرها من خوارزميات الاستبدال الأحدث. تُستخدم مسافة إعادة الاستخدام كمقياس لترتيب الصفحات التي تم الوصول إليها ديناميكيًا لاتخاذ قرار الاستبدال. [ 31 ] تعالج LIRS قصور خوارزمية LRU باستخدام الحداثة لتقييم حداثة المراجع المتبادلة (IRR) لاتخاذ قرار الاستبدال.

مخطط خوارزمية LIRS

في الرسم التوضيحي، يشير X إلى الوصول إلى كتلة في وقت محدد. إذا تم الوصول إلى الكتلة A1 في الوقت 1، فسيكون معدل حداثتها 0؛ هذه هي الكتلة التي تم الوصول إليها أولاً، وسيكون معدل التكرار الفوري (IRR) 1، لأنه يتوقع الوصول إلى A1 مرة أخرى في الوقت 3. في الوقت 2، بما أنه تم الوصول إلى A4، سيصبح معدل الحداثة 0 لـ A4 و1 لـ A1؛ A4 هي أحدث كتلة تم الوصول إليها، وسيكون معدل التكرار الفوري 4. في الوقت 10، سيكون لدى خوارزمية LIRS مجموعتان: مجموعة LIR = {A1, A2} ومجموعة HIR = {A3, A4, A5}. في الوقت 10، إذا تم الوصول إلى A4، فسيحدث خطأ؛ ستقوم خوارزمية LIRS بإخراج A5 بدلاً من A2 بسبب حداثتها الأكبر.

ذاكرة تخزين مؤقتة بديلة تكيفية

تعمل ذاكرة التخزين المؤقت للاستبدال التكيفي (ARC) على تحقيق توازن مستمر بين خوارزميتي LRU وLFU لتحسين النتيجة الإجمالية. [ 32 ] وهي تُحسّن خوارزمية SLRU باستخدام معلومات حول عناصر ذاكرة التخزين المؤقت التي تم إخراجها مؤخرًا لضبط حجم القطاعات المحمية والاختبارية لتحقيق الاستخدام الأمثل لمساحة ذاكرة التخزين المؤقت المتاحة. [ 33 ]

ساعة مع استبدال تكيفي

تجمع تقنية الساعة ذات الاستبدال التكيفي (CAR) بين مزايا تقنيتي ARC و Clock . وتؤدي CAR أداءً مماثلاً لتقنية ARC، وتتفوق على تقنيتي LRU و Clock. وكما هو الحال مع ARC، فإن CAR ذاتية الضبط ولا تتطلب أي معلمات يحددها المستخدم.

طابور متعدد

طُوِّرت خوارزمية استبدال الطوابير المتعددة (MQ) لتحسين أداء ذاكرة التخزين المؤقت من المستوى الثاني، مثل ذاكرة التخزين المؤقت للخادم، وقُدِّمت في ورقة بحثية من تأليف تشو، وفيلبين، ولي. [ 34 ] تحتوي ذاكرة التخزين المؤقت MQ على m من طوابير LRU: Q0 ، Q1 ، ...، Qm - 1 . تمثل قيمة m تسلسلًا هرميًا قائمًا على عمر جميع الكتل في تلك الطابور. [ 35 ]

مخطط خوارزمية الاستبدال متعددة الطوابير

سل

بانير [ 36 ] هي آلية تخزين مؤقتة سريعة تعتمد على الحاويات، وتُحدد الحاويات التي تتميز كتلها بأنماط وصول متغيرة. تعتمد بانير على بنية قائمة انتظار ذات أولوية لترتيب الحاويات بناءً على مدة بقائها، والتي تتناسب مع البيانات النشطة داخل الحاوية.

التحليل الثابت

يُحدد التحليل الثابت عمليات الوصول التي تُمثل نجاحات أو إخفاقات في ذاكرة التخزين المؤقت، وذلك لتحديد أسوأ وقت تنفيذ للبرنامج. [ 37 ] يتمثل أحد أساليب تحليل خصائص ذاكرة التخزين المؤقت الأقل استخدامًا (LRU) في إعطاء كل كتلة في ذاكرة التخزين المؤقت "عمرًا" (0 للكتلة الأكثر استخدامًا مؤخرًا) وحساب الفترات الزمنية للأعمار المحتملة. [ 38 ] يمكن تحسين هذا التحليل لتمييز الحالات التي يمكن فيها الوصول إلى نفس نقطة البرنامج عبر مسارات تؤدي إلى نجاحات أو إخفاقات. [ 39 ] يمكن الحصول على تحليل فعال من خلال تجريد مجموعات حالات ذاكرة التخزين المؤقت بواسطة سلاسل مضادة، والتي تُمثل بمخططات قرار ثنائية مضغوطة . [ 40 ]

لا ينطبق التحليل الثابت لخوارزمية LRU على سياسات pseudo-LRU. ووفقًا لنظرية التعقيد الحسابي ، فإن مسائل التحليل الثابت التي تطرحها سياسات pseudo-LRU وFIFO تقع ضمن فئات تعقيد أعلى من تلك الخاصة بخوارزمية LRU. [ 41 ] [ 42 ]

انظر أيضاً

مراجع

  1. 1 2 آلان جاي سميث. "تصميم ذاكرة التخزين المؤقت لوحدة المعالجة المركزية". وقائع مؤتمر IEEE TENCON، 1987.
  2. ↑ بول ف. بولوتوف. "المبادئ الوظيفية لذاكرة التخزين المؤقت" مؤرشف في 14 مارس 2012 في Wayback Machine . 2007.
  3. ↑ دليل مبرمج سلسلة ARM Cortex-R
  4. ↑ خوارزمية محاكاة فعالة لسياسة الاستبدال العشوائي في ذاكرة التخزين المؤقت
  5. ↑ يانغ، جونتشنغ؛ تشيو، زيوي؛ تشانغ، يازو؛ يو، ياو؛ راشمي، كي في (22 يونيو 2023). "قد يكون FIFO أفضل من LRU: قوة الترقية الكسولة والتخفيض السريع" . وقائع ورشة العمل التاسعة عشرة حول المواضيع الساخنة في أنظمة التشغيل . HOTOS '23. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 70-79 . doi : 10.1145/3593856.3595887 . ISBN  979-8-4007-0195-5.
  6. ↑ تشانغ، يازو؛ يانغ، جونتشنغ؛ يو، ياو؛ فيغفوسون، يمير؛ راشمي، ك. ف. (2024). خوارزمية SIEVE أبسط من خوارزمية LRU: خوارزمية إخلاء فعّالة وجاهزة للاستخدام لذاكرة التخزين المؤقت للويب . الصفحات 1229-1246 . ISBN  978-1-939133-39-7.
  7. ↑ جونسون، ثيودور؛ شاشا، دينيس (12 سبتمبر 1994). "2Q: خوارزمية استبدال إدارة المخزن المؤقت عالية الأداء ومنخفضة الحمل" (ملف PDF) . وقائع المؤتمر الدولي العشرين لقواعد البيانات الضخمة جدًا . VLDB '94. سان فرانسيسكو، كاليفورنيا: دار مورغان كوفمان للنشر: 439-450 . ISBN 978-1-55860-153-6. S2CID 6259428 . 
  8. ↑ أونيل، إليزابيث ج .؛ أونيل، باتريك إي.؛ ويكوم، جيرهارد (1993). "خوارزمية استبدال الصفحات LRU-K لتخزين البيانات على القرص في قواعد البيانات". وقائع مؤتمر ACM SIGMOD الدولي لإدارة البيانات لعام 1993 - SIGMOD '93 . نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 297-306 . CiteSeerX 10.1.1.102.8240 . doi : 10.1145/170035.170081 . ISBN   978-0-89791-592-2. S2CID 207177617 . 
  9. ↑ بلال، محمد؛ وآخرون (2014). "سياسة إدارة ذاكرة التخزين المؤقت TLRU (الأقل استخدامًا مؤخرًا مع مراعاة الوقت) في شبكات الاتصالات الدولية". المؤتمر الدولي السادس عشر لتكنولوجيا الاتصالات المتقدمة . الصفحات 528-532 . arXiv : 1801.00390 . Bibcode : 2018arXiv180100390B . doi : 10.1109/ICACT.2014.6779016 . ISBN   978-89-968650-3-2. S2CID 830503 . 
  10. ↑ هونغ تاي تشو وديفيد جيه ديويت. تقييم استراتيجيات إدارة المخزن المؤقت لأنظمة قواعد البيانات العلائقية. VLDB، 1985.
  11. ↑ شاؤول دار، مايكل جيه فرانكلين، بيورن ثور جونسون، ديفيش سريفاستافا، ومايكل تان. التخزين المؤقت للبيانات الدلالية واستبدالها. فلدب، 1996.
  12. ↑ راماكريشنا كاريدلا، ج. سبنسر لوف، وبرادلي ج. ويرري. استراتيجيات التخزين المؤقت لتحسين أداء نظام القرص. في مجلة الكمبيوتر ، 1994.
  13. ↑ جيانغ، سونغ؛ تشين، فنغ؛ تشانغ، شياودونغ (2005). "CLOCK-Pro: تحسين فعال لاستبدال CLOCK" (ملف PDF) . وقائع المؤتمر السنوي التقني لجمعية USENIX . جمعية USENIX: 323-336 .
  14. ↑ "إدارة الذاكرة في لينكس: تصميم استبدال الصفحات" . 30 ديسمبر 2017. تم الاطلاع عليه في 30 يونيو 2020 .
  15. ↑ كوربيت، جوناثان (16 أغسطس 2005). "تطبيق استبدال الصفحات في CLOCK-Pro" . LWN.net . تم الاطلاع عليه بتاريخ 30 يونيو 2020 .
  16. ↑ بلال، محمد؛ وآخرون (2017). "مخطط لإدارة ذاكرة التخزين المؤقت من أجل إخلاء المحتوى وتكراره بكفاءة في شبكات ذاكرة التخزين المؤقت" . IEEE Access . 5 : 1692-1701 . arXiv : 1702.04078 . Bibcode : 2017arXiv170204078B . doi : 10.1109/ACCESS.2017.2669344 . S2CID 14517299 .  
  17. ↑ جاياريكا، ب.؛ ناير، ت (2010). "نهج استبدال ديناميكي تكيفي لنظام ذاكرة تخزين مؤقتة للبادئة قائم على البث المتعدد ومدرك للشعبية". arXiv : 1001.4135 [ cs.MM ].
  18. ↑ يانغ، جونتشنغ؛ تشانغ، يازو؛ تشيو، زيوي؛ يو، ياو؛ فيناياك، راشمي (23 أكتوبر 2023). "طوابير FIFO هي كل ما تحتاجه لإخراج البيانات من ذاكرة التخزين المؤقت" . وقائع الندوة التاسعة والعشرين حول مبادئ أنظمة التشغيل . SOSP '23. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 130-149 . doi : 10.1145/3600006.3613147 . ISBN  979-8-4007-0229-7.
  19. 1 2 جاين، أكانكشا؛ لين، كالفن (يونيو 2016). "العودة إلى المستقبل: الاستفادة من خوارزمية بلادي لتحسين استبدال ذاكرة التخزين المؤقت". المؤتمر الدولي السنوي الثالث والأربعون لجمعية ACM/IEEE حول هندسة الحاسوب (ISCA) لعام 2016. الصفحات 78-89. doi : 10.1109 /ISCA.2016.17 . ISBN  978-1-4673-8947-1.
  20. جليل ، عامر؛ ثيوبالد، كيفن ب.؛ ستيلي، سيمون س.؛ إيمر، جويل (19 يونيو 2010). " استبدال ذاكرة التخزين المؤقت عالية الأداء باستخدام التنبؤ بفترة إعادة الإشارة (RRIP)" . وقائع الندوة الدولية السنوية السابعة والثلاثين حول هندسة الحاسوب . ISCA '10. نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة آلات الحوسبة. الصفحات 60-71 . doi : 10.1145/1815961.1815971 . ISBN  978-1-4503-0053-7. S2CID 856628 . 
  21. ↑ قريشي، معين الدين ك.؛ جليل، عامر؛ بات، ييل ن.؛ ستيلي، سيمون س.؛ إيمر، جويل (9 يونيو 2007). "سياسات الإدخال التكيفية للتخزين المؤقت عالي الأداء" . أخبار هندسة الحاسوب ACM SIGARCH . 35 (2): 381-391 . doi : 10.1145/1273440.1250709 . ISSN 0163-5964 . 
  22. ↑ كيراميداس، جورجيوس؛ بيتومينوس، بافلوس؛ كاكزيراس، ستيفانوس (2007). "استبدال الذاكرة المؤقتة بناءً على التنبؤ بمسافة إعادة الاستخدام" . المؤتمر الدولي الخامس والعشرون لتصميم الحاسوب ، 2007. الصفحات 245-250 . doi : 10.1109/ICCD.2007.4601909 . ISBN  978-1-4244-1257-0. S2CID 14260179 . 
  23. ↑ "بطولة استبدال المخبأ الثانية - بالتزامن مع مؤتمر ISCA يونيو 2017" . crc2.ece.tamu.edu . تاريخ الوصول: 24 مارس 2022 .
  24. ↑ جاين، أكانكشا؛ لين، كالفن (يونيو 2018). "إعادة النظر في خوارزمية بلادي لاستيعاب الجلب المسبق". المؤتمر الدولي السنوي الخامس والأربعون لجمعية ACM/IEEE حول هندسة الحاسوب (ISCA) لعام 2018. الصفحات 110-123 . doi : 10.1109/ISCA.2018.00020 . ISBN  978-1-5386-5984-7. S2CID 5079813 . 
  25. ↑ شاه، إيشان؛ جاين، أكانكشا؛ لين، كالفن (أبريل 2022). "المحاكاة الفعالة لسياسة الحد الأدنى لبلدي". HPCA .
  26. ↑ ساتون، ريتشارد س. (1 أغسطس 1988). "التعلم للتنبؤ باستخدام أساليب الفروق الزمنية" . تعلم الآلة . 3 (1): 9-44 . Bibcode : 1988MLear...3....9S . doi : 10.1007/BF00115009 . ISSN 1573-0565 . S2CID 207771194 .  
  27. ↑ ليو، إيفان؛ هاشمي، ميلاد؛ سويرسكي، كيفن؛ رانغاناثان، بارثاساراثي؛ آهن، جونوان (21 نوفمبر 2020). "نهج التعلم بالتقليد لاستبدال ذاكرة التخزين المؤقت" . المؤتمر الدولي للتعلم الآلي . PMLR: 6237–6247 . arXiv : 2006.16239 .
  28. ↑ خيمينيز، دانيال أ.؛ تيران، إلفيرا (14 أكتوبر 2017). "التنبؤ بإعادة الاستخدام من منظورات متعددة" . وقائع الندوة الدولية السنوية الخمسين لمعهد مهندسي الكهرباء والإلكترونيات/رابطة مكائن ​​الحوسبة حول هندسة المعالجات الدقيقة . نيويورك، نيويورك، الولايات المتحدة الأمريكية: رابطة مكائن ​​الحوسبة. الصفحات 436-448 . doi : 10.1145/3123939.3123942 . ISBN  9781450349529. S2CID 1811177 . 
  29. ↑ ليكوريس، ثيودوريس؛ فاسيلفيتسكي، سيرجي (7 يوليو 2021). "التخزين المؤقت التنافسي باستخدام نصائح التعلم الآلي" . مجلة ACM . 68 (4): 1-25 . arXiv : 1802.05399 . doi : 10.1145/3447579 . eISSN 1557-735X . ISSN 0004-5411 . S2CID 3625405 .   
  30. ↑ ميتزنماخر، مايكل ؛ فاسيلفيتسكي، سيرجي (31 ديسمبر 2020). "الخوارزميات مع التنبؤات". ما وراء تحليل أسوأ الحالات للخوارزميات . مطبعة جامعة كامبريدج. ص 646-662 . arXiv : 2006.09123 . doi : 10.1017/9781108637435.037 . ISBN  9781108637435.
  31. ↑ جيانغ، سونغ؛ تشانغ، شياودونغ (يونيو 2002). "LIRS: سياسة استبدال فعالة لمجموعة المراجع المنخفضة لتحسين أداء ذاكرة التخزين المؤقت" (ملف PDF) . مجلة ACM SIGMETRICS لتقييم الأداء . 30 (1). رابطة آلات الحوسبة: 31-42 . doi : 10.1145/511399.511340 . ISSN 0163-5999 . 
  32. ↑ نمرود مجيدو ودارميندرا س. مودها. ARC: ذاكرة تخزين مؤقتة بديلة ذاتية الضبط ومنخفضة الحمل الزائد. FAST، 2003.
  33. ↑ "بعض المعلومات حول ذاكرة التخزين المؤقت للقراءة في نظام الملفات ZFS - أو: ARC - c0t0d0s0.org" . مؤرشف من الأصل بتاريخ 24 فبراير 2009.
  34. ↑ يوانيوان تشو ، جيمس فيلبين، وكاي لي. خوارزمية استبدال الطوابير المتعددة لذاكرة التخزين المؤقت من المستوى الثاني. USENIX، 2002.
  35. ↑ إدواردو بينهيرو، ريكاردو بيانكيني، تقنيات ترشيد الطاقة للخوادم القائمة على مصفوفات الأقراص، وقائع المؤتمر الدولي السنوي الثامن عشر للحوسبة الفائقة، 26 يونيو - 1 يوليو 2004، مالو، فرنسا
  36. ↑ تشنغ لي، فيليب شيلان، فريد دوغليس، وغرانت والاس. بانيير: ذاكرة تخزين مؤقتة سريعة قائمة على الحاويات للكائنات المركبة. مؤتمر ACM/IFIP/USENIX للبرمجيات الوسيطة، 2015.
  37. ↑ كريستيان فرديناند؛ راينهارد فيلهلم (1999). "التنبؤ الفعال والدقيق بسلوك ذاكرة التخزين المؤقت لأنظمة الوقت الحقيقي". أنظمة الوقت الحقيقي . 17 ( 2-3 ): 131-181 . Bibcode : 1999RTSys..17..131F . doi : 10.1023/A:1008186323068 . S2CID 28282721 . 
  38. ↑ كريستيان فرديناند؛ فلوريان مارتن؛ راينهارد فيلهلم؛ مارتن آلت (نوفمبر 1999). "التنبؤ بسلوك الذاكرة المؤقتة من خلال التفسير المجرد". علم برمجة الحاسوب . 35 ( 2-3 ). سبرينغر: 163-189 . doi : 10.1016/S0167-6423(99)00010-6 .
  39. ↑ فالنتين توزيو؛ كلير مايزا؛ ديفيد مونيو؛ جان راينيك (2017). "تحديد عدم اليقين لتحليل دقيق وفعال لذاكرة التخزين المؤقت". التحقق بمساعدة الحاسوب (2) . arXiv : 1709.10008 . doi : 10.1007/978-3-319-63390-9_2 .
  40. ↑ فالنتين توزيو؛ كلير مايزا؛ ديفيد مونيو؛ جان راينيك (2019). "تحليل سريع ودقيق لذاكرة التخزين المؤقت LRU". وقائع مؤتمر لغات البرمجة التابع لجمعية الحوسبة الآلية (ACM)، المجلد 3 ( POPL): 54:1–54:29. arXiv : 1811.01670 .
  41. ↑ ديفيد مونيو؛ فالنتين توزيو (11 نوفمبر 2019). "حول تعقيد تحليل ذاكرة التخزين المؤقت لسياسات الاستبدال المختلفة" . مجلة ACM . 66 (6). رابطة آلات الحوسبة: 1-22 . arXiv : 1811.01740 . doi : 10.1145/3366018 . S2CID 53219937 . 
  42. ↑ ديفيد مونيو (13 مايو 2022). "تتسع فجوة التعقيد في التحليل الثابت لعمليات الوصول إلى الذاكرة المؤقتة عند إضافة استدعاءات الإجراءات" . الأساليب الرسمية في تصميم الأنظمة . 59 ( 1-3 ). سبرينغر فيرلاغ: 1-20 . arXiv : 2201.13056 . doi : 10.1007/s10703-022-00392-w . S2CID 246430884 .