سياسات استبدال التخزين المؤقت

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

نظرة عامة

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

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

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

السياسات

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

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