كيف يعمل استبدال الصفحات (page replacement)، وما الذي يسبّب الـ thrashing؟

Question

IT Interview Practice · Accepted Answer

حين تمتلئ الـ RAM الفعلية بينما تحتاج العمليات إلى مزيد من الصفحات، يجب على نظام التشغيل أن **يطرد (evict)** صفحة مقيمة لإفساح المجال — كاتبًا إياها إلى **swap** (القرص) إن كانت متسخة (dirty). أيّ صفحة يطرد هو قرار **استبدال الصفحات (page replacement)**، وإخطاؤه يحطّم الأداء.

## سياسات الاستبدال

الأمثل نظريًّا هو طرد الصفحة التي ستُستخدَم في المستقبل الأبعد (**OPT لِـ Bélády**) — مستحيل، إذ لا يمكنك رؤية المستقبل. فنقارِب **LRU (least recently used — الأقل استخدامًا مؤخرًا)**: اطرد الصفحة الأطول بقاءً دون استخدام. الـ LRU الحقيقي يحتاج طابعًا زمنيًّا عند كل وصول (مكلف جدًّا)، فتستخدم النوى الحقيقية **خوارزمية الساعة (clock / second-chance)**:

```text
Frames arranged in a ring; each has a REFERENCE bit the hardware sets on access.
A "hand" sweeps around the ring:
   ref bit = 1 → clear it, give the page a second chance, move on
   ref bit = 0 → evict THIS page (approximates "least recently used")

[1]→[1]→[0] ← evict here   (the sweep clears 1s until it finds a 0)
         ▲___________|
```

تعطي الساعة نتائج شبيهة بـ LRU بكلفة O(1). ويصقلها لينكس أكثر بـ **قوائم LRU للنشط/غير النشط (active/inactive)**.

## Working set والـ thrashing

**working set** العملية هو مجموعة الصفحات التي تستخدمها بنشاط ضمن نافذة زمنية. يعمل الـ paging على ما يرام *ما دامت مجاميع working sets تسع في الـ RAM*. وحين لا تسع:

```text
working set > RAM → evict a page that's about to be needed → immediate page fault →
evict another needed page → ... → the CPU spends ~all its time paging to disk, ~0% on real work
                            = THRASHING
```

الـ thrashing جُرف لا منحدر: تجاوز الحدّ قليلًا فينهار الـ throughput لأن كل وصول تقريبًا يخفق (miss). الأعراض: CPU شبه خامل لكن I/O القرص مُشبَع، وlatency ينفجر.

## إصلاحه / تفاديه

- **أضِف RAM** أو **قلّل الحِمل** (عمليات متزامنة أقل) لتسع working sets.
- يمكن للـ scheduler أن **يعلّق ويُخرِج (swap out)** عمليات كاملة لتقليص الطلب (medium-term scheduling).
- الـ **OOM killer** في لينكس هو الملاذ الأخير — اقتل عملية بدل الـ thrash إلى الأبد.
- حسّن **المحلّية (locality)** ليصغر الـ working set نفسه.

## لماذا يهم

يجمع هذا قصة الذاكرة كلها، وهو سؤال senior مفضّل لأن الـ thrashing نمط فشل حقيقي في الإنتاج: خدمة على ما يرام عند N مستخدمًا تسقط عن الجُرف عند N+1 حين يتجاوز working set-ها الـ RAM. التعرّف على البصمة (paging ثقيل، قرص مُشبَع، CPU متوقّف) ومعرفة الروافع (RAM، إسقاط الحمل، المحلّية — وأن الـ swap يحوّل نقص الذاكرة إلى كارثة latency) هو الفرق بين تشخيصه في دقائق والتحديق في صندوق متجمّد بلا سبب ظاهر.

سياسات الاستبدال

Working set والـ thrashing

إصلاحه / تفاديه

لماذا يهم

أسئلة ذات صلة