موقف من الحياة اليومية

جراج تحت الأرض فيه أماكن مرسومة على الأرض بخطوط بيضا، وعربيات راكنة في بعضها.
صورة توضيحية مولّدة بالـ AI

جراج عمارة فيه 4 أماكن بس، وكل شقة ليها مكان واحد محدد حسب آخر رقم في رقم الشقة. شقة 12 وشقة 22 الاتنين نفس المكان. لو صاحب شقة 22 جه وشقة 12 راكنة، واحد لازم يمشي.

ولو الجراج قال: «كل مكانين ليهم مجموعة شقق، واركن في أي واحد فاضي فيهم»، المشكلة تقل كتير.

الـ Cache جوه المعالج بتواجه نفس المشكلة بالظبط. في المقال اللي فات شفنا ليه الـ Cache موجودة، ودلوقتي هنشوف بتشتغل إزاي من جوه.

خلاصة سريعة

  • الـ Cache متقسمة Lines، وكل Line فيها Block من البيانات وTag بيقول البيانات دي جاية من أنهي حتة في الذاكرة. والعنوان نفسه بيتقسم 3 أجزاء: Tag وIndex وOffset.
  • لو البيانات موجودة يبقى Hit، ولو مش موجودة يبقى Miss. والـ Set associative بتقلل الـ Miss اللي سببه تزاحم العناوين، والـ LRU بتطلّع الأقدم استخدامًا.
  • في الـ Multicore، كل Core عنده Cache، فلازم Coherence protocol يضمن إن كله شايف آخر قيمة.

ببساطة

لما المعالج يطلب عنوان، الـ Cache بتعمل 3 أسئلة بسرعة:

1 - أبص في أنهي مكان؟
من جزء في نص العنوان اسمه Index. 2 - المكان ده فيه بيانات صالحة؟
وهي بتاعة العنوان ده ولا عنوان تاني؟

من بت اسمه Valid وجزء من العنوان اسمه Tag. 3 - لو هي، أنهي بايت جوه الـ Block؟
من آخر جزء في العنوان اسمه Offset.

لو الإجابة «أيوه هي»: Hit، والبيانات تطلع في لحظة. لو «لأ»: Miss، والمعالج يستنى الـ RAM، والـ Block الجديد ياخد المكان.

بالتفصيل

1 - الـ Hit والـ Miss

المعالج بيبعت العنوان للـ Cache والذاكرة مع بعض:

  • Hit: البيانات في الـ Cache، فالـ Cache ترد أسرع، وطلب الذاكرة يتلغي.
  • Miss: المعالج يستنى الذاكرة، ولما البيانات توصل تتحط في الـ Cache علشان المرة الجاية. وده بيحصل حتى في الكتابة، لأن البرنامج غالبًا هيرجع لنفس المكان.

ولو الـ Cache مليانة، لازم حاجة تطلع، وده اسمه Eviction، علشان الجديدة تدخل. ولو اللي طالعة اتعدلت، لازم تتكتب في الذاكرة الأول.

2 - الـ Cache line

الـ Cache متقسمة لوحدات اسمها Cache lines، وكل Line فيها:

  • Block: حتة من بيانات الذاكرة. والمعالجات النهارده بتستخدم Blocks من 16 لـ 64 بايت.
  • Metadata (بيانات وصفية): مش بيانات البرنامج، دي معلومات عن الـ Line:
    • Valid bit: الـ Line فيها بيانات صالحة؟
      لو 0 يبقى المكان فاضي.
    • Tag: البيانات دي جاية من أنهي حتة في الذاكرة.

3 - العنوان بيتقسم 3 أجزاء

من اليمين للشمال:

  • Offset: مكان البايت جوه الـ Block. لو الـ Block 32 بايت، محتاج 5 بت، لأن 2⁵ = 32.
  • Index: أنهي Line. لو الـ Cache فيها 1,024 Line، محتاج 10 بت.
  • Tag: كل الباقي. في عنوان 32 بت مع 5 و10، الـ Tag = 32 − 15 = 17 بت.

ليه الـ Index من النص؟ لأن البرنامج بيحط متغيراته جنب بعض، فالبتات اللي على الشمال بتبقى متشابهة. لو اتاخد الـ Index منها، كل المتغيرات هتتزاحم على نفس الأماكن. والبتات اللي في النص بتوزّعهم أحسن.

مثال: Cache فيها 128 Line وBlock من 32 بايت. الـ Index بيحدد الصف، والـ Tag بيأكد إن البيانات بتاعة العنوان ده، والـ Offset بيختار البايت.

4 - الـ Direct-mapped: كل عنوان ليه مكان واحد

في الـ Direct-mapped cache، كل عنوان ليه Line واحدة بس يروح لها. بسيطة وسريعة في البحث، بس عناوين كتير بتشترك في نفس الـ Line.

ولو برنامج بيستخدم متغيرين على نفس الـ Line، كل واحد هيطرد التاني كل مرة، حتى لو الـ Cache فاضية. وده زي شقة 12 وشقة 22 في الجراج.

5 - أنواع الـ Miss

  • Compulsory (إجباري): أول مرة البرنامج يطلب العنوان، ومفيش مفر منه.
  • Capacity (سعة): البرنامج محتاج بيانات أكتر من حجم الـ Cache.
  • Conflict (تزاحم): عنوانين على نفس المكان والـ Cache مش مليانة.

وتصميم الـ Cache بيأثر أساسًا على الـ Conflict.

6 - الـ Associative: أكتر من مكان

  • Fully associative: أي بيانات تروح أي مكان. مرونة كاملة، بس لازم تدوّر في كل الأماكن كل مرة، فبتتستخدم في حاجات صغيرة بس، زي الـ TLB.
  • Set associative: كل عنوان ليه Set واحد، والـ Set فيه أكتر من Line، غالبًا من 2 لـ 8. الـ Cache بتدوّر في Lines الـ Set كلها مع بعض، وده الحل الوسط المناسب للمعالجات.

مثال من نفس الأرقام: نفس سلسلة الطلبات اللي عملت Miss مرتين بسبب التزاحم في Direct-mapped، ما عملتش ولا مرة في 2-way set associative، لأن العنوانين لقوا مكانين في نفس الـ Set.

7 - مين يطلع؟ الـ LRU

لو الـ Set مليانة، الـ Cache بتطلّع الـ Line اللي ما اتستخدمتش من أطول وقت. دي اسمها LRU (Least Recently Used)، وهي نفس فكرة الطالب اللي بيرجّع للرف الكتاب اللي ما فتحهوش من أطول وقت. ومحتاجة بتات زيادة في كل Set علشان تفتكر الترتيب: في 2-way بت واحد يكفي.

8 - الكتابة: Write-through ولا Write-back؟

  • Write-through: كل كتابة بتتعمل في الـ Cache والذاكرة في نفس الوقت. أبسط، بس كل تعديل بيروح للذاكرة البطيئة.
  • Write-back: الكتابة في الـ Cache بس، ومعاها بت اسمه Dirty bit بيقول «الـ Line دي اتعدلت». ولما الـ Line تطلع، تتكتب في الذاكرة مرة واحدة.

لو برنامج بيعدّل نفس المتغير ألف مرة، الـ Write-through بيروح للذاكرة ألف مرة، والـ Write-back مرة واحدة في الآخر. وعلشان كده أغلب الـ Caches الحديثة Write-back.

9 - الـ Cache في المعالجات متعددة الـ Cores

  • كل Core ليه L1 خاصة بيه، وغالبًا L1 متقسمة اتنين: واحدة للتعليمات وواحدة للبيانات.
  • الـ L3 غالبًا مشتركة بين كل الـ Cores.
  • والـ L2 بتختلف من تصميم للتاني: ممكن خاصة، أو مشتركة، أو بين مجموعة Cores.

10 - الـ Cache coherence: نسختين من نفس البيانات

المشكلة: Core 0 وCore 1 الاتنين عندهم نسخة من نفس البيانات في الـ L1. Core 0 عدّلها. دلوقتي نسخة Core 1 قديمة!

الحل: Cache coherence protocol (بروتوكول اتساق الـ Cache) بيضمن إن أي Core يقرا آخر قيمة. ومن أشهرها MSI، وفيه 3 حالات لكل Line:

  • M (Modified): الـ Core ده عدّل النسخة بتاعته، وهي الأحدث.
  • S (Shared): النسخة زي الأصل، وأكتر من Core يقدر يقرا منها بأمان.
  • I (Invalid): النسخة قديمة، وما ينفعش تتستخدم.

إزاي بيشتغل؟

  • Core 0 كتب: النسخ التانية بتبقى Invalid، ونسخته Modified.
  • Core 1 عايز يقرا: نسخته Invalid، فـ Core 0 يكتب القيمة الجديدة في الـ L2، وCore 1 يجيبها، والاتنين يبقوا Shared.

وفيه Protocols تانية زي MESI وMOESI، وكلهم بيلغوا النسخ التانية عند الكتابة. وعلشان كل Cache تعرف إن حد كتب، فيه طريقتين: Snooping (كل Cache بتسمع على Bus مشترك)، أو Directory (جدول بيسجّل مين معاه إيه، وبيكبر أحسن مع عدد Cores كبير، بس أبطأ).

الـ Protocol بتاع MSI: الكتابة بتلغي النسخ التانية، والقراءة بعدها بتجيب آخر قيمة.

11 - الـ TLB: Cache للعناوين الافتراضية

البرامج بتشتغل على عناوين افتراضية، والمعالج لازم يترجمها لعناوين حقيقية في الـ RAM، والترجمة دي متخزنة في جدول في الذاكرة. لو كل طلب محتاج يقرا الجدول ده الأول، كل حاجة هتبطأ.

فالمعالج فيه Cache صغيرة للترجمات دي اسمها TLB (Translation Lookaside Buffer)، وهي جزء من وحدة اسمها MMU (Memory Management Unit).

  • Hit: الترجمة جاهزة، والطلب يكمّل بسرعة.
  • Miss: لازم يقرا الجدول من الذاكرة، وده غالي.

والـ TLB غالبًا فيها 32 أو 64 أو 128 خانة، وFully associative. وتفاصيل العناوين الافتراضية والصفحات في مقال إدارة الذاكرة في مجال أنظمة التشغيل.

أخطاء شائعة

  • «الـ Cache بتشيل رقم رقم»: بتشيل Blocks كاملة، من 16 لـ 64 بايت غالبًا.
  • «Miss معناه إن فيه غلط»: لأ، Miss معناه إن البيانات مش في الـ Cache، والمعالج هيجيبها من الذاكرة.
  • «الـ Fully associative أحسن دايمًا»: أمرن، بس البحث فيها أتقل، فالمعالجات بتستخدم Set associative.
  • «الـ Write-back ممكن يضيّع التعديلات»: الـ Dirty bit بيضمن إن الـ Line اللي اتعدلت تتكتب في الذاكرة قبل ما تطلع.
  • «كل Core شايف نفس الـ Cache، فمفيش مشكلة»: كل Core ليه L1 خاصة، وعلشان كده محتاجين Coherence.

المصطلحات

  • سطر الذاكرة المخبئية (Cache line): وحدة تخزين في الذاكرة المخبئية فيها كتلة بيانات وبيانات وصفية.
  • العلامة (Tag): جزء العنوان الذي يحدد أي جزء من الذاكرة موجود في السطر.
  • الفهرس (Index): جزء العنوان الذي يحدد السطر أو المجموعة.
  • الإزاحة (Offset): جزء العنوان الذي يحدد البايت داخل الكتلة.
  • الإصابة (Hit): وجود البيانات المطلوبة في الذاكرة المخبئية.
  • الإخفاق (Miss): عدم وجود البيانات المطلوبة في الذاكرة المخبئية.
  • التعيين المباشر (Direct-mapped): تصميم يكون فيه لكل عنوان سطر واحد فقط.
  • الترابط الجزئي (Set associative): تصميم يكون فيه لكل عنوان مجموعة من عدة أسطر.
  • الأقدم استخدامًا (LRU): سياسة إخراج السطر الذي لم يُستخدم منذ أطول وقت.
  • الكتابة المؤجلة (Write-back): الكتابة في الذاكرة المخبئية فقط، ثم في الذاكرة عند الإخراج.
  • اتساق الذاكرة المخبئية (Cache coherence): ضمان أن كل الأنوية ترى أحدث قيمة للبيانات المشتركة.
  • مخزن ترجمة العناوين (TLB): ذاكرة مخبئية صغيرة لترجمات العناوين الافتراضية إلى حقيقية.

اختبر نفسك

الـ Cache Block حجمه 32 بايت. الـ Offset محتاج كام بت؟

إظهار الإجابة

الإجابة الصحيحة: 5

5 بت.
لأن 2⁵ = 32، فـ 5 بتات تكفي تحدد أي بايت من الـ 32.

ليه أغلب الـ Caches الحديثة Write-back؟

إظهار الإجابة

الإجابة الصحيحة: لأنها بتكتب في الذاكرة مرة واحدة لما الـ Line تطلع، بدل كل تعديل

بتوفّر الكتابة في الذاكرة.
لو المتغير اتعدل كتير، بيتكتب في الذاكرة مرة واحدة بس، بفضل الـ Dirty bit.

Core 0 عدّل بيانات، وCore 1 عنده نسخة منها في الـ L1. الـ Protocol بتاع MSI هيعمل إيه في نسخة Core 1؟

إظهار الإجابة

الإجابة الصحيحة: يخليها Invalid

يخليها Invalid.
النسخة بقت قديمة، فلما Core 1 يحتاجها لازم يجيب آخر قيمة الأول.