الذاكرة الافتراضية
تغطي هذه الوحدة مفاهيم الذاكرة الافتراضية، جلب الصفحات عند الطلب، خوارزميات استبدال الصفحات، تخصيص الإطارات، ومشكلة التعثر (Thrashing).
Virtual Memory
This module covers virtual memory concepts, demand paging, page replacement algorithms, frame allocation, and thrashing.
أهداف التعلم
- تعريف الذاكرة الافتراضية ووصف فوائدها.
- توضيح كيفية تحميل الصفحات في الذاكرة باستخدام تقنية الجلب عند الطلب (Demand Paging).
- تطبيق خوارزميات استبدال الصفحات: FIFO، المثلى (Optimal)، و LRU.
- وصف مجموعة العمل (Working Set) لعملية ما، وشرح علاقتها بمحلية البرنامج (Program Locality).
- Define virtual memory and describe its benefits.
- Illustrate how pages are loaded into memory using demand paging.
- Apply the FIFO, optimal, and LRU page-replacement algorithms.
- Describe the working set of a process, and explain how it is related to program locality.
1 أساسيات الذاكرة الافتراضية
1 Virtual Memory Basics
الذاكرة الافتراضية تفصل بين الذاكرة المنطقية للمستخدم والذاكرة المادية، مما يسمح بتشغيل برامج أكبر من الذاكرة الفعلية المتاحة.
Virtual memory separates user logical memory from physical memory, allowing execution of programs larger than available physical memory.
الذاكرة الافتراضية تسمح بتنفيذ البرامج المحملة جزئياً في الذاكرة. هذا يعني أن البرنامج لم يعد مقيداً بحدود الذاكرة المادية.
من فوائدها: تستهلك كل عملية ذاكرة أقل أثناء التشغيل (مما يسمح بتشغيل المزيد من البرامج في نفس الوقت)، زيادة استخدام وحدة المعالجة المركزية (CPU)، وتقليل عمليات الإدخال/الإخراج (I/O) اللازمة لتحميل أو تبديل البرامج.
Virtual memory allows the execution of partially-loaded programs. The program is no longer constrained by the limits of physical memory.
Benefits include: each program takes less memory while running (allowing more programs to run concurrently), increased CPU utilization and throughput, and less I/O needed to load or swap processes.
يتم تنفيذ الذاكرة الافتراضية عادةً عبر تقنية الجلب عند الطلب (Demand Paging) أو التجزئة عند الطلب (Demand Segmentation).
وحدة إدارة الذاكرة (MMU) هي المسؤولة عن تعيين العناوين المنطقية إلى عناوين مادية.
مساحة العنوان المنطقي يمكن أن تكون أكبر بكثير من مساحة العنوان المادي، مما يتيح مشاركة مساحات العناوين بين عدة عمليات وإنشاء عمليات بشكل أكثر كفاءة.
Virtual memory is typically implemented via Demand Paging or Demand Segmentation.
The Memory Management Unit (MMU) maps logical addresses to physical ones.
The logical address space can be much larger than the physical address space, which also allows address spaces to be shared by several processes and allows for more efficient process creation.
كيف تساهم الذاكرة الافتراضية في زيادة درجة تعدد البرمجة (Multiprogramming)؟ How does virtual memory increase the degree of multiprogramming?
من خلال السماح بتحميل أجزاء فقط من كل برنامج في الذاكرة المادية، مما يترك مساحة كافية لتحميل أجزاء من برامج أخرى إضافية في نفس الوقت.
By allowing only parts of each program to be loaded into physical memory, leaving enough space to load parts of additional programs simultaneously.
2 جلب الصفحات عند الطلب
2 Demand Paging
جلب الصفحات عند الطلب يعني إحضار الصفحة إلى الذاكرة فقط عندما يحتاجها البرنامج فعلياً، مثل قراءة كتاب وفتح الصفحة التي تقرأها فقط.
Demand paging brings a page into memory only when it is needed, like opening a book only to the page you are currently reading.
بدلاً من جلب العملية بأكملها إلى الذاكرة وقت التحميل، يقوم نظام الجلب عند الطلب بإحضار الصفحات المطلوبة فقط.
هذا يقلل من عمليات الإدخال/الإخراج غير الضرورية ويقلل من الذاكرة المطلوبة، مما يؤدي إلى استجابة أسرع ودعم عدد أكبر من المستخدمين.
يتم استخدام بت (Valid-Invalid Bit) في جدول الصفحات لتحديد ما إذا كانت الصفحة موجودة في الذاكرة (v) أو غير موجودة (i).
Instead of bringing the entire process into memory at load time, a demand paging system brings in only the required pages.
This results in less I/O, less memory needed, faster response, and supports more users.
A valid-invalid bit is used in the page table to indicate whether a page is memory resident (v) or not-in-memory (i).
عندما يحاول المعالج الوصول إلى صفحة تحمل البت (i)، يحدث 'خطأ صفحة' (Page Fault).
يتطلب هذا من نظام التشغيل التدخل (Trap)، البحث عن إطار فارغ في الذاكرة المادية، قراءة الصفحة من القرص (Backing Store) إلى هذا الإطار، تحديث جدول الصفحات ليصبح البت (v)، ثم إعادة تشغيل التعليمة التي تسببت في الخطأ.
كل هذا يحدث بشفافية تامة دون الحاجة لتغيير كود المبرمج.
When the CPU tries to access a page with an invalid bit (i), a 'Page Fault' occurs.
This traps to the OS, which must find a free frame, read the page from the backing store into the frame, update the page table (set bit to v), and restart the instruction that caused the fault.
This happens transparently without changing program behavior or code.
ماذا يحدث إذا كانت الإشارة المرجعية للصفحة غير صالحة تماماً (عنوان خارج حدود البرنامج) بدلاً من كونها غير موجودة في الذاكرة فقط؟ What happens if the page reference is truly invalid (out of bounds) rather than just not in memory?
سيقوم نظام التشغيل بإحباط (Abort) العملية بدلاً من محاولة جلب الصفحة من القرص.
The operating system will abort the process instead of trying to fetch the page from the disk.
3 استبدال الصفحات
3 Page Replacement
عندما تمتلئ الذاكرة المادية، يجب إخراج صفحة (ضحية) لإفساح المجال لصفحة جديدة، مثل إخراج ملابس قديمة من خزانة ممتلئة لوضع ملابس جديدة.
When physical memory is full, a page (victim) must be swapped out to make room for a new page, like removing old clothes from a full closet to fit new ones.
يمنع استبدال الصفحات التخصيص المفرط للذاكرة.
إذا لم يكن هناك إطار فارغ عند حدوث خطأ صفحة، تستخدم خوارزمية استبدال الصفحات لاختيار 'إطار ضحية' (Victim Frame) لإخراجه إلى القرص.
لتقليل العبء، يتم استخدام 'بت التعديل' (Dirty Bit) بحيث يتم كتابة الصفحات التي تم تعديلها فقط إلى القرص، بينما الصفحات غير المعدلة يتم التخلص منها ببساطة.
Page replacement prevents over-allocation of memory.
If there is no free frame during a page fault, a page replacement algorithm selects a 'victim frame' to be swapped out to disk.
To reduce overhead, a modify (dirty) bit is used so that only modified pages are written back to disk; unmodified pages are simply discarded.
استكمال استبدال الصفحات يفصل تماماً بين الذاكرة المنطقية والمادية، مما يوفر ذاكرة افتراضية ضخمة على ذاكرة مادية صغيرة.
الهدف من أي خوارزمية استبدال هو تقليل معدل أخطاء الصفحة (Page-fault rate).
يتم تقييم الخوارزميات عن طريق تشغيلها على 'سلسلة مراجع' (Reference String) وحساب عدد أخطاء الصفحة الناتجة.
Page replacement completes the separation between logical and physical memory, providing a large virtual memory on a smaller physical memory.
The goal of any replacement algorithm is to minimize the page-fault rate.
Algorithms are evaluated by running them on a particular 'reference string' of memory references and computing the number of page faults.
لماذا يعتبر 'بت التعديل' (Dirty Bit) مهماً جداً لأداء النظام؟ Why is the 'Dirty Bit' so important for system performance?
لأنه يمنع عمليات الكتابة غير الضرورية على القرص البطيء؛ إذا لم يتم تعديل الصفحة، فلا حاجة لحفظها مرة أخرى على القرص لأن النسخة الموجودة هناك لا تزال صالحة.
It prevents unnecessary writes to the slow disk; if a page hasn't been modified, there's no need to save it back to disk since the copy there is still valid.
4 خوارزميات استبدال الصفحات
4 Page Replacement Algorithms
تحدد الخوارزميات أي صفحة يجب إزالتها. FIFO تزيل الأقدم، OPT تزيل الأبعد استخداماً في المستقبل، و LRU تزيل الأقل استخداماً مؤخراً.
Algorithms determine which page to evict. FIFO evicts the oldest, OPT evicts the one used furthest in the future, and LRU evicts the least recently used.
- FIFO (First-In-First-Out): تستبدل الصفحة التي دخلت الذاكرة أولاً. قد تعاني من مفارقة بيلادي (Belady's Anomaly) حيث تزيد أخطاء الصفحة بزيادة الإطارات.
- Optimal (OPT): تستبدل الصفحة التي لن يتم استخدامها لأطول فترة في المستقبل. هي الأفضل ولكن يستحيل تنفيذها عملياً لأنها تتطلب معرفة المستقبل. تُستخدم كمعيار للمقارنة.
- LRU (Least Recently Used): تستخدم المعرفة السابقة بدلاً من المستقبلية، وتستبدل الصفحة التي لم تُستخدم لأطول فترة زمنية. أداؤها جيد وشائعة الاستخدام.
- FIFO: Replaces the oldest page. It can suffer from Belady's Anomaly, where adding more frames causes more page faults.
- Optimal (OPT): Replaces the page that will not be used for the longest period of time. It is optimal but impossible to implement as it requires future knowledge. Used as a benchmark.
- LRU: Uses past knowledge, replacing the page that has not been used in the most amount of time. Generally good and frequently used.
تنفيذ LRU يتطلب دعماً من الأجهزة (Hardware) لتتبع وقت الاستخدام، وهو أمر مكلف.
لذلك، تُستخدم تقريبات لـ LRU مثل خوارزمية 'الفرصة الثانية' (Second-Chance) أو 'الساعة' (Clock).
تعتمد هذه الخوارزمية على بت مرجعي (Reference Bit) توفره الأجهزة.
إذا كان البت 0، تُستبدل الصفحة. إذا كان 1، يُعاد تعيينه إلى 0 وتُعطى الصفحة فرصة ثانية وتبقى في الذاكرة، ثم يُنتقل للصفحة التالية.
Implementing strict LRU requires hardware support to track usage time, which is expensive.
Thus, LRU approximations like the Second-Chance (Clock) algorithm are used.
It relies on a hardware-provided reference bit.
If the bit is 0, the page is replaced. If 1, the bit is cleared to 0, the page is given a second chance (kept in memory), and the algorithm moves to the next page.
لماذا لا تعاني خوارزمية LRU من مفارقة بيلادي؟ Why doesn't the LRU algorithm suffer from Belady's Anomaly?
لأن LRU تنتمي إلى فئة خوارزميات المكدس (Stack Algorithms)، حيث تكون مجموعة الصفحات الموجودة في الذاكرة لـ n إطارات دائماً مجموعة فرعية من الصفحات الموجودة لـ n+1 إطارات.
Because LRU belongs to a class of algorithms called Stack Algorithms, where the set of pages in memory for n frames is always a subset of the pages in memory for n+1 frames.
5 تخصيص الإطارات
5 Allocation of Frames
تخصيص الإطارات يحدد كم إطاراً من الذاكرة تحصل عليه كل عملية، إما بالتساوي أو بناءً على حجم العملية.
Frame allocation determines how many memory frames each process gets, either equally or proportionally based on process size.
تحتاج كل عملية إلى حد أدنى من الإطارات لتنفيذ تعليماتها. هناك مخططات رئيسية للتخصيص الثابت (Fixed Allocation):
- التخصيص المتساوي (Equal Allocation): إذا كان هناك 100 إطار و 5 عمليات، تحصل كل عملية على 20 إطاراً.
- التخصيص النسبي (Proportional Allocation): يتم تخصيص الإطارات بناءً على حجم العملية. العمليات الأكبر تحصل على إطارات أكثر.
Each process needs a minimum number of frames to execute instructions. There are major fixed allocation schemes:
- Equal Allocation: If there are 100 frames and 5 processes, each gets 20 frames.
- Proportional Allocation: Allocate according to the size of the process. Larger processes get more frames.
بالإضافة إلى التخصيص الثابت، هناك التخصيص الشامل والمحلي (Global and Local Allocation).
الاستبدال الشامل (Global Replacement): يسمح للعملية باختيار إطار ضحية من مجموعة الإطارات الكلية (يمكنها أخذ إطار من عملية أخرى). هذا يزيد من الإنتاجية ولكنه يجعل وقت التنفيذ متغيراً.
الاستبدال المحلي (Local Replacement): يقيد العملية باختيار ضحية من إطاراتها المخصصة فقط. يوفر أداءً أكثر اتساقاً للعملية ولكنه قد يؤدي إلى عدم استغلال الذاكرة بشكل كامل.
Beyond fixed allocation, there is Global and Local Allocation.
Global replacement: A process selects a replacement frame from the set of all frames (can steal from another process). This yields greater throughput but variable execution time.
Local replacement: Each process selects only from its own allocated frames. This provides consistent per-process performance but possibly underutilized memory.
| Global Replacement | Local Replacement | |
|---|---|---|
| الإنتاجية (Throughput)Throughput | أعلى (أكثر شيوعاً)Higher (more common) | أقل (بسبب عدم استغلال الذاكرة بالكامل)Lower (due to possible underutilized memory) |
| اتساق الأداء (Performance Consistency)Performance Consistency | متغير بشكل كبير (يعتمد على العمليات الأخرى)Varies greatly (depends on other processes) | أكثر اتساقاً لكل عمليةMore consistent per-process |
| اختيار الإطار الضحيةVictim Frame Selection | من جميع الإطارات في النظامFrom the set of all frames in the system | من الإطارات المخصصة للعملية فقطOnly from its own set of allocated frames |
أيهما أكثر شيوعاً في أنظمة التشغيل الحديثة: الاستبدال الشامل أم المحلي؟ ولماذا؟ Which is more common in modern OS: Global or Local replacement? Why?
الاستبدال الشامل (Global Replacement) هو الأكثر شيوعاً لأنه يؤدي إلى إنتاجية (Throughput) أعلى للنظام ككل واستغلال أفضل للذاكرة.
Global replacement is more common because it results in greater overall system throughput and better memory utilization.
6 التعثر ونموذج المحلية
6 Thrashing and Locality Model
التعثر يحدث عندما تقضي العملية وقتاً في تبديل الصفحات من وإلى القرص أكثر من وقت التنفيذ الفعلي، مما يؤدي إلى انهيار أداء النظام.
Thrashing occurs when a process spends more time paging in and out than executing, leading to a collapse in system performance.
إذا لم يكن لدى العملية عدد 'كافٍ' من الصفحات، سيكون معدل أخطاء الصفحة مرتفعاً جداً.
ستقوم العملية باستبدال إطار، ولكنها ستحتاجه مرة أخرى بسرعة.
هذا يؤدي إلى انخفاض شديد في استخدام المعالج (CPU utilization).
نظام التشغيل يلاحظ هذا الانخفاض فيعتقد أنه بحاجة لزيادة درجة تعدد البرمجة (إضافة عمليات جديدة)، مما يزيد المشكلة سوءاً ويؤدي إلى التعثر (Thrashing).
If a process does not have 'enough' pages, the page-fault rate is very high.
It replaces a frame but quickly needs it back.
This leads to low CPU utilization.
The OS sees low CPU utilization and thinks it needs to increase the degree of multiprogramming (adding more processes), which makes the problem worse, causing Thrashing.
لماذا يعمل الجلب عند الطلب بشكل جيد عادةً؟ بسبب 'نموذج المحلية' (Locality Model).
تنتقل العملية من محلية (مجموعة من الصفحات المستخدمة معاً) إلى أخرى أثناء التنفيذ.
يحدث التعثر عندما يكون حجم المحلية أكبر من إجمالي الذاكرة المتاحة للعملية.
للحد من آثار التعثر، يمكن استخدام الاستبدال المحلي (Local Replacement) أو استبدال الصفحات بناءً على الأولوية.
Why does demand paging work normally? Because of the 'Locality Model'.
A process migrates from one locality (a set of pages actively used together) to another.
Thrashing occurs when the size of the locality is greater than the total memory size allocated.
To limit thrashing effects, local or priority page replacement can be used.
كيف يساهم الاستبدال المحلي (Local Replacement) في الحد من انتشار التعثر في النظام؟ How does Local Replacement help limit the spread of thrashing in a system?
في الاستبدال المحلي، لا يمكن لعملية متعثرة أن تسرق إطارات من عمليات أخرى، مما يمنعها من التسبب في تعثر العمليات السليمة الأخرى.
In local replacement, a thrashing process cannot steal frames from other processes, preventing it from causing healthy processes to also thrash.