ذاكرة الوصول العشوائي وذاكرة التخزين المؤقت *

في القسمين الأولين من هذا الفصل، استكشفنا المصفوفات والقوائم المترابطة، وهما بنيتا بيانات أساسيتان مهمتان تمثّلان تخطيطين فيزيائيين: «التخزين المتجاور» و«التخزين المتناثر» على التوالي.

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

وسائل تخزين الحاسوب

يتضمن الحاسوب ثلاثة أنواع من وسائل التخزين: القرص الصلب، وذاكرة الوصول العشوائي (RAM)، وذاكرة التخزين المؤقت. ويعرض الجدول التالي أدوارها المختلفة وخصائص أدائها في نظام الحاسوب.

الجدول   وسائل تخزين الحاسوب

	القرص الصلب	ذاكرة الوصول العشوائي (RAM)	ذاكرة التخزين المؤقت
الغرض	تخزين طويل الأمد للبيانات، بما فيها أنظمة التشغيل والبرامج والملفات	تخزين مؤقت للبرامج التي تعمل حالياً والبيانات قيد المعالجة	تخزين البيانات والتعليمات كثيرة الوصول إليها لتقليل وصول المعالج (CPU) إلى الذاكرة
التطاير	لا تُفقد البيانات بعد انقطاع الطاقة	تُفقد البيانات بعد انقطاع الطاقة	تُفقد البيانات بعد انقطاع الطاقة
السعة	كبيرة، في حدود تيرابايتات (TB)	صغيرة، في حدود غيغابايتات (GB)	صغيرة جداً، في حدود ميغابايتات (MB)
السرعة	بطيئة، من مئات إلى آلاف MB/s	سريعة، عشرات GB/s	سريعة جداً، من عشرات إلى مئات GB/s
التكلفة (يوان/GB)	منخفضة، من أعشار قليلة من اليوان إلى بضعة يوانات لكل GB	مرتفعة، من عشرات إلى مئات اليوانات لكل GB	مرتفعة جداً، وتُحزَّم فعلياً مع حزمة المعالج

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

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

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

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

كفاءة استهلاك الذاكرة في بنى البيانات

من حيث استخدام مساحة الذاكرة، لكل من المصفوفات والقوائم المترابطة مزايا وقيود.

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

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

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

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

من الواضح أنه كلما قلّت «حالات فقدان ذاكرة التخزين المؤقت»، ارتفعت كفاءة قراءة المعالج للبيانات وكتابتها، وتحسّن أداء البرنامج. ونسمّي نسبة البيانات التي يحصل عليها المعالج من ذاكرة التخزين المؤقت بنجاح معدل إصابة ذاكرة التخزين المؤقت (cache hit rate)، وهو مقياس يُستخدم عادةً لقياس كفاءة ذاكرة التخزين المؤقت.

ولتحقيق أعلى كفاءة ممكنة، تعتمد ذاكرة التخزين المؤقت آليات تحميل البيانات التالية.

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

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

• المساحة المشغولة: تشغل عناصر القائمة المترابطة مساحة أكبر من عناصر المصفوفة، لذا يتّسع في ذاكرة التخزين المؤقت قدر أقل من البيانات النافعة.
• أسطر التخزين المؤقت: بيانات القائمة المترابطة متناثرة في الذاكرة، بينما تحمّل ذاكرة التخزين المؤقت «على شكل أسطر»، لذا تكون نسبة البيانات غير النافعة المحمّلة أعلى.
• آلية الجلب المسبق: أنماط الوصول إلى البيانات في المصفوفات أكثر «قابلية للتنبؤ» من القوائم المترابطة، فيسهل على النظام تخمين البيانات التي ستُحمَّل تالياً.
• التموضع المكاني: تُخزَّن المصفوفات في مساحة ذاكرة مركّزة، لذا يزيد احتمال الوصول قريباً إلى بيانات مجاورة للبيانات المحمّلة.

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

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

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