Illusion of Space: Virtual Memory وهم المساحة: Virtual Memory

Running programs larger than physical memory. Demand Paging, Page Faults, Thrashing, and Replacement Algorithms. تشغيل برامج أكبر من الذاكرة الفعلية. يشمل Demand Paging و Page Faults و Thrashing وخوارزميات الاستبدال (Replacement Algorithms).

Demand Paging Demand Paging Page Fault Page Fault Copy-on-Write (COW) Copy-on-Write (COW) FIFO/LRU/Optimal FIFO/LRU/Optimal Thrashing Thrashing

Why Virtual Memory? لماذا الذاكرة الافتراضية (Virtual Memory)؟

Concept: Separation of user logical memory from physical memory. المفهوم: فصل الذاكرة المنطقية للمستخدم (Logical Memory) عن الذاكرة الفعلية (Physical Memory).
Only part of the program needs to be in memory for execution. يحتاج جزء فقط من البرنامج أن يكون في الذاكرة للتنفيذ.

Benefits الفوائد
  • Logical address space can be much larger than physical address space ($2^{64}$ vs 16GB RAM). مساحة العنوان المنطقي يمكن أن تكون أكبر بكثير من مساحة العنوان الفعلي ($2^{64}$ مقابل 16GB RAM).
  • More programs can run simultaneously (Higher CPU utilization). يمكن تشغيل برامج أكثر في وقت واحد (استخدام أعلى للـ CPU).
  • Less I/O needed to load or swap processes. عمليات I/O أقل مطلوبة لتحميل أو تبديل العمليات.
Implementation التنفيذ (Implementation)
  • Demand Paging: Load pages only when needed. Demand Paging: تحميل الصفحات فقط عند الحاجة إليها.
  • Demand Segmentation: (Less common). Demand Segmentation: (أقل شيوعاً).

Demand Paging Demand Paging

The Lazy Swapper المبدل الكسول (The Lazy Swapper)

Never brings a page into memory until it is required. لا يحضر الصفحة إلى الذاكرة أبداً إلا إذا كانت مطلوبة.
Valid-Invalid Bit: With each page table entry, a bit is associated (v = in memory, i = not in memory). Valid-Invalid Bit: مع كل إدخال في جدول الصفحات، يرتبط بت (v = في الذاكرة، i = ليس في الذاكرة).

Page Fault Handling Steps: خطوات معالجة الـ Page Fault:
  1. Access to a page marked 'i' $\to$ Trap to OS (Page Fault). الوصول إلى صفحة معلمة بـ 'i' $\to$ Trap لنظام التشغيل (Page Fault).
  2. OS checks internal table: Invalid reference $\to$ Abort. Just not in memory $\to$ Continue. نظام التشغيل يفحص الجدول الداخلي: مرجع غير صالح $\to$ إلغاء (Abort). فقط ليست في الذاكرة $\to$ استمرار.
  3. Find a free frame in physical memory. إيجاد free frame في الذاكرة الفعلية.
  4. Schedule disk operation to read page into frame. جدولة عملية القرص لقراءة الصفحة إلى الإطار (Frame).
  5. Reset page table (v = 1). إعادة تعيين جدول الصفحات (v = 1).
  6. Restart the instruction that caused the fault. إعادة تشغيل التعليمات التي تسببت في الخطأ.

Performance of Demand Paging أداء الـ Demand Paging

Effective Access Time (EAT) depends heavily on the Page Fault Rate ($p$). وقت الوصول الفعال (EAT) يعتمد بشكل كبير على معدل خطأ الصفحة (Page Fault Rate - $p$).

EAT = (1 - p) * ma + p * (Page Fault Time)

ma = memory access time (~10-200ns). ma = وقت الوصول للذاكرة (~10-200ns).
Page Fault Time = service fault + read page + restart (~8ms). Page Fault Time = خدمة الخطأ + قراءة الصفحة + إعادة التشغيل (~8ms).
Even a small $p$ enables drastic slowdown. حتى قيمة $p$ صغيرة تسبب تباطؤاً كبيراً.

Page Replacement استبدال الصفحات (Page Replacement)

What if there are no free frames? We must find a victim frame, write it to disk (if modified), and replace it. ماذا لو لم تكن هناك إطارات (Frames) فارغة؟ يجب أن نجد إطار ضحية (Victim Frame)، نكتبه إلى القرص (إذا تم تعديله)، ونستبدله.
Goal: Minimize page-fault rate. الهدف: تقليل معدل الـ Page-fault.

FIFO (First-In, First-Out) FIFO (First-In, First-Out)

Replace the oldest page. Simple queue implementation. استبدال أقدم صفحة. تنفيذ بسيط باستخدام طابور (Queue).

Belady's Anomaly: Adding more frames can cause more page faults! Belady's Anomaly: إضافة المزيد من الإطارات قد يسبب المزيد من أخطاء الصفحات!

Optimal Algorithm الخوارزمية المثلى (Optimal Algorithm)

Replace the page that will not be used for the longest period of time. استبدال الصفحة التي لن يتم استخدامها لأطول فترة زمنية.
Impossible to implement (requires future knowledge). Used as a benchmark. مستحيلة التنفيذ (تتطلب معرفة المستقبل). تستخدم كمعيار للمقارنة.

LRU (Least Recently Used) LRU (Least Recently Used)

Replace the page that has not been used for the longest period of time. (Approximation of Optimal). استبدال الصفحة التي لم يتم استخدامها لأطول فترة زمنية. (تقريب للـ Optimal).
Implementation: Counters or Stack. Good performance, no Belady's Anomaly. التنفيذ: عدادات أو مكدس (Stack). أداء جيد، ولا تعاني من Belady's Anomaly.

Allocation & Thrashing التخصيص والـ Thrashing

Frame Allocation تخصيص الإطارات (Frame Allocation)

  • Fixed: Equal allocation or Proportional to size. ثابت: تخصيص متساوٍ أو متناسب مع الحجم.
  • Global Replacement: Process can steal frames from others. (Good throughput, variable execution time). استبدال عالمي (Global): العملية يمكن أن تسرق إطارات من غيرها. (إنتاجية جيدة، وقت تنفيذ متغير).
  • Local Replacement: Must steal from own set. (Consistent perf, potentially lower throughput). استبدال محلي (Local): يجب أن تسرق من مجموعتها الخاصة. (أداء ثابت، إنتاجية قد تكون أقل).

Thrashing Thrashing

A process is busy swapping pages in and out (Page Fault Rate > Service Rate). العملية مشغولة بتبديل الصفحات للداخل والخارج (معدل Page Fault > معدل الخدمة).
CPU Utilization drops to near zero. استخدام الـ CPU ينخفض إلى ما يقارب الصفر.

Cause: $\Sigma$ Size of Locality > Total Memory Size. السبب: مجموع ($\Sigma$) حجم الـ Locality > حجم الذاكرة الكلي.
Solution: Working Set Model (Monitor active pages per process and suspend processes if memory is insufficient). الحل: نموذج Working Set (مراقبة الصفحات النشطة لكل عملية وإيقاف العمليات مؤقتاً إذا كانت الذاكرة غير كافية).

The Exam Vault خزنة الاختبار (The Exam Vault)

Professor's Secrets & Trap Avoidance أسرار البروفيسور وتجنب الفخاخ

TRAP: Modify Bit فخ: Modify Bit

"Why use a Modify (Dirty) bit?" "لماذا نستخدم Modify (Dirty) bit؟"
If the victim page has NOT been modified (Dirty bit = 0), we do NOT need to write it back to disk (it's already there). This saves 50% of the I/O time on replacement. إذا لم يتم تعديل الصفحة الضحية (Dirty bit = 0)، لا نحتاج لكتابتها مرة أخرى للقرص (هي موجودة هناك بالفعل). هذا يوفر 50% من وقت I/O عند الاستبدال.

TRAP: Belady's Anomaly فخ: Belady's Anomaly

Belady's Anomaly (more frames = more faults) happens with FIFO. It does NOT happen with LRU or Optimal (Stack Algorithms). ظاهرة Belady's Anomaly (إطارات أكثر = أخطاء أكثر) تحدث مع FIFO. لا تحدث مع LRU أو Optimal (Stack Algorithms).

SECRET: Copy-on-Write (COW) سر: Copy-on-Write (COW)

`fork()` creates a child process. Instead of copying ALL parent pages (slow), COW allows parent and child to share the same pages initially. `fork()` تنشئ عملية فرعية (Child). بدلاً من نسخ جميع صفحات الأب (بطيء)، COW تسمح للأب والابن بمشاركة نفس الصفحات مبدئياً.
Only if one writes to a page is a copy created. This makes process creation extremely fast. فقط عندما يكتب أحدهما في صفحة يتم إنشاء نسخة. هذا يجعل إنشاء العمليات سريعاً للغاية.

KEY CONCEPT: Working Set مفهوم مفتاحي: Working Set

To prevent thrashing, the OS must ensure the process has enough frames to cover its current Locality (set of pages actively used together). لمنع الـ Thrashing، يجب أن يضمن نظام التشغيل أن العملية لديها إطارات كافية لتغطية Locality الحالية (مجموعة الصفحات المستخدمة بنشاط معاً).
If $\Sigma$ Working Sets > Available Frames $\to$ Swap out a process. إذا كان مجموع ($\Sigma$) الـ Working Sets > الإطارات المتاحة $\to$ يتم إخراج (Swap out) عملية.