الذاكرة الرئيسية
تغطي هذه الوحدة تقنيات إدارة الذاكرة في أنظمة التشغيل، بما في ذلك تخصيص الذاكرة المتجاورة، التجزئة (Paging)، استخدام ذاكرة التخزين المؤقت (TLB)، والتبديل (Swapping).
Main Memory
This module covers memory management techniques in operating systems, including contiguous memory allocation, paging, Translation Look-aside Buffers (TLB), and swapping.
أهداف التعلم
- تقديم وصف تفصيلي للطرق المختلفة لتنظيم أجهزة الذاكرة.
- تقييم تقنيات إدارة الذاكرة المختلفة.
- فهم مفهوم التبديل (Swapping) وكيفية عمله.
- To provide a detailed description of various ways of organizing memory hardware.
- To evaluate various memory-management techniques.
- To understand the concept of Swapping.
1 ربط العناوين (Address Binding)
1 Address Binding
هي عملية تعيين التعليمات والبيانات إلى عناوين ذاكرة فعلية، ويمكن أن تحدث في ثلاث مراحل مختلفة.
The process of mapping instructions and data to physical memory addresses, which can happen at three different stages.
يمكن أن يحدث ربط العناوين في ثلاث مراحل:
- وقت الترجمة (Compile time): إذا كان موقع الذاكرة معروفاً مسبقاً، يتم إنشاء كود مطلق (Absolute code).
- وقت التحميل (Load time): يتم إنشاء كود قابل لإعادة التوطين (Relocatable code) إذا لم يكن الموقع معروفاً وقت الترجمة.
- وقت التنفيذ (Execution time): يتأخر الربط حتى وقت التشغيل إذا كان من الممكن نقل العملية بين أجزاء الذاكرة أثناء تنفيذها، ويتطلب ذلك دعماً من الأجهزة (مثل سجلات الأساس والحد).
Address binding can happen at three stages:
- Compile time: If memory location is known a priori, absolute code is generated.
- Load time: Must generate relocatable code if memory location is not known at compile time.
- Execution time: Binding delayed until run time if the process can be moved during its execution. Needs hardware support (e.g., base and limit registers).
الربط في وقت التنفيذ هو الأكثر مرونة ويستخدم في أنظمة التشغيل الحديثة لأنه يسمح بنقل العمليات في الذاكرة بحرية، ولكنه يتطلب وحدة إدارة الذاكرة (MMU) لترجمة العناوين المنطقية إلى مادية في كل دورة وصول للذاكرة.
Execution-time binding is the most flexible and is used in modern OSs because it allows processes to be moved freely in memory. However, it requires a Memory Management Unit (MMU) to translate logical to physical addresses on every memory access.
لماذا لا تستخدم أنظمة التشغيل الحديثة الربط في وقت الترجمة (Compile time binding)؟ Why do modern operating systems not use compile-time binding?
لأنه يتطلب معرفة موقع الذاكرة الدقيق مسبقاً، مما يمنع نظام التشغيل من تحميل برامج متعددة ديناميكياً في أي مساحة فارغة متاحة، ويقيد تعدد المهام.
Because it requires knowing the exact memory location in advance, preventing the OS from dynamically loading multiple programs into any available free space, thus restricting multiprogramming.
2 العنوان المنطقي مقابل العنوان المادي
2 Logical vs Physical Address Space
العنوان المنطقي هو ما تولده وحدة المعالجة المركزية (CPU)، بينما العنوان المادي هو ما تراه وحدة الذاكرة.
Logical address is generated by the CPU, while physical address is seen by the memory unit.
مفهوم مساحة العنوان المنطقي المرتبطة بمساحة عنوان مادي منفصلة هو أمر مركزي لإدارة الذاكرة السليمة.
- العنوان المنطقي (الافتراضي): يتم إنشاؤه بواسطة وحدة المعالجة المركزية.
- العنوان المادي: العنوان الفعلي في الذاكرة.
في أنظمة الربط وقت الترجمة ووقت التحميل، يكون العنوانان متطابقين. أما في الربط وقت التنفيذ، فإنهما يختلفان.
The concept of a logical address space bound to a separate physical address space is central to proper memory management.
- Logical address (virtual): generated by the CPU.
- Physical address: address seen by the memory unit.
In compile-time and load-time binding, logical and physical addresses are the same; in execution-time binding, they differ.
هذا الفصل بين العناوين يسمح للبرامج بأن تُكتب وتُترجم دون القلق بشأن مكان تحميلها الفعلي في الذاكرة (Abstraction)، مما يسهل الحماية وتعدد المهام.
This separation allows programs to be written and compiled without worrying about where they will physically reside in memory (Abstraction), facilitating protection and multiprogramming.
هل يرى برنامج المستخدم العنوان المادي الحقيقي أبداً؟ Does the user program ever see the real physical address?
لا، برنامج المستخدم يتعامل فقط مع العناوين المنطقية، وتقوم وحدة إدارة الذاكرة (MMU) بترجمتها في الخلفية.
No, the user program deals only with logical addresses; the MMU translates them transparently in the background.
3 وحدة إدارة الذاكرة (MMU) وحماية الذاكرة
3 Memory Management Unit (MMU) & Protection
جهاز صلب يترجم العناوين المنطقية إلى مادية ويحمي الذاكرة باستخدام سجلات الأساس والحد.
A hardware device that maps virtual to physical addresses and protects memory using base and limit registers.
وحدة إدارة الذاكرة (MMU): جهاز يقوم بتعيين العناوين الافتراضية إلى مادية في وقت التشغيل. تستخدم سجل إعادة التوطين (Relocation register) (سجل الأساس سابقاً) حيث تُضاف قيمته إلى كل عنوان يطلبه المستخدم.
حماية الذاكرة: يجب على وحدة المعالجة المركزية التحقق من كل وصول للذاكرة للتأكد من أنه يقع بين سجل الأساس (Base) وسجل الحد (Limit). إذا كان العنوان المنطقي أكبر من أو يساوي الحد، يتم إطلاق خطأ (Trap).
MMU: Hardware device that at run time maps virtual to physical address. It uses a relocation register (formerly base register); its value is added to every address generated by a user process.
Protection: CPU must check every memory access in user mode to ensure it is between base and limit registers. If the logical address is >= limit, a trap (addressing error) is generated.
التعليمات الخاصة بتحميل سجلات الأساس والحد هي تعليمات ذات امتيازات (Privileged instructions) لا يمكن تنفيذها إلا بواسطة نظام التشغيل في وضع النواة (Kernel mode)، مما يمنع برامج المستخدم من تعديل حدود ذاكرتها الخاصة.
The instructions to load the base and limit registers are privileged. They can only be executed by the OS in kernel mode, preventing user programs from maliciously altering their own memory boundaries.
ماذا يحدث إذا حاول برنامج مستخدم قراءة عنوان ذاكرة خارج نطاق سجل الحد الخاص به؟ What happens if a user program tries to read a memory address outside its limit register?
ستكتشف الأجهزة (Hardware) ذلك وتولد استثناء (Trap) لنظام التشغيل يشير إلى خطأ في العنونة غير القانونية.
The hardware will detect it and generate a trap to the operating system indicating an illegal addressing error.
4 التخصيص الديناميكي للتخزين
4 Dynamic Storage Allocation
خوارزميات لاختيار الفجوة (Hole) المناسبة في الذاكرة لتخصيصها لعملية جديدة: First-fit، Best-fit، و Worst-fit.
Algorithms to select a free memory hole for a new process: First-fit, Best-fit, and Worst-fit.
عندما تصل عملية، يتم تخصيص ذاكرة لها من فجوة (Hole) كبيرة بما يكفي. الخوارزميات هي:
- First-fit (التوافق الأول): تخصيص أول فجوة كبيرة بما يكفي.
- Best-fit (التوافق الأفضل): تخصيص أصغر فجوة كبيرة بما يكفي (ينتج أصغر فجوة متبقية).
- Worst-fit (التوافق الأسوأ): تخصيص أكبر فجوة (ينتج أكبر فجوة متبقية).
When a process arrives, it is allocated memory from a hole large enough. Algorithms:
- First-fit: Allocate the first hole that is big enough.
- Best-fit: Allocate the smallest hole that is big enough (produces smallest leftover hole).
- Worst-fit: Allocate the largest hole (produces largest leftover hole).
أثبتت التحليلات أن First-fit و Best-fit أفضل من Worst-fit من حيث السرعة واستغلال التخزين.
Best-fit يتطلب البحث في القائمة بأكملها (إلا إذا كانت مرتبة بالحجم)، بينما First-fit أسرع بشكل عام.
Simulations show that First-fit and Best-fit are better than Worst-fit in terms of speed and storage utilization.
Best-fit requires searching the entire list (unless ordered by size), whereas First-fit is generally faster.
| First-fit | Best-fit | Worst-fit | |
|---|---|---|---|
| السرعةSpeed | سريع جداً (يجد أول فجوة)Very fast (finds first hole) | بطيء (يبحث في القائمة كاملة)Slow (searches entire list) | بطيء (يبحث في القائمة كاملة)Slow (searches entire list) |
| حجم الفجوة المتبقيةLeftover Hole Size | متوسطAverage | أصغر فجوة متبقيةSmallest leftover hole | أكبر فجوة متبقيةLargest leftover hole |
لماذا قد يكون Worst-fit مفيداً في بعض الحالات رغم اسمه؟ Why might Worst-fit be useful in some cases despite its name?
لأنه يترك أكبر فجوة متبقية، والتي قد تكون كبيرة بما يكفي لاستيعاب عملية أخرى، بينما Best-fit يترك فجوات صغيرة جداً غير قابلة للاستخدام.
Because it leaves the largest leftover hole, which might be large enough to accommodate another process, whereas Best-fit leaves tiny, unusable holes.
5 تجزئة الذاكرة (Fragmentation)
5 Fragmentation
ضياع مساحات من الذاكرة إما خارج العمليات (External) أو داخلها (Internal).
Wasted memory space either outside processes (External) or inside allocated blocks (Internal).
التجزئة الخارجية (External Fragmentation): توجد مساحة ذاكرة إجمالية كافية لتلبية الطلب، لكنها غير متجاورة (مبعثرة).
التجزئة الداخلية (Internal Fragmentation): الذاكرة المخصصة أكبر قليلاً من الذاكرة المطلوبة؛ هذا الفارق هو ذاكرة داخل القسم ولكن لا يتم استخدامها.
قاعدة الـ 50 بالمائة: تحليل First-fit يكشف أنه مقابل كل N كتلة مخصصة، تضيع 0.5 N كتلة بسبب التجزئة (أي ثلث الذاكرة قد يكون غير قابل للاستخدام).
External Fragmentation: Total memory space exists to satisfy a request, but it is not contiguous.
Internal Fragmentation: Allocated memory may be slightly larger than requested memory; this size difference is internal to a partition but not being used.
50-percent rule: First fit analysis reveals that given N blocks allocated, 0.5 N blocks lost to fragmentation (1/3 may be unusable).
يمكن تقليل التجزئة الخارجية عن طريق الضغط (Compaction)، وهو خلط محتويات الذاكرة لوضع كل الذاكرة الحرة معاً في كتلة واحدة كبيرة.
لكن الضغط ممكن فقط إذا كان إعادة التوطين ديناميكياً ويتم في وقت التنفيذ، ويسبب مشاكل مع عمليات الإدخال/الإخراج (I/O).
External fragmentation can be reduced by Compaction: shuffling memory contents to place all free memory together in one large block.
Compaction is possible only if relocation is dynamic and done at execution time. It also complicates I/O operations.
| External Fragmentation | Internal Fragmentation | |
|---|---|---|
| الموقعLocation | خارج الأقسام المخصصة (مبعثرة)Outside allocated partitions (scattered) | داخل القسم المخصصInside the allocated partition |
| الحلSolution | الضغط (Compaction) أو التجزئة (Paging)Compaction or Paging | تقليل حجم الصفحة (لا يمكن حله تماماً في Paging)Reduce page size (cannot be fully solved in Paging) |
لماذا يمثل الإدخال/الإخراج (I/O) مشكلة أثناء ضغط الذاكرة (Compaction)؟ Why is I/O a problem during memory compaction?
إذا كانت العملية تنتظر بيانات I/O في عنوان ذاكرة محدد، فإن نقل العملية عبر الضغط سيجعل بيانات I/O تُكتب في المكان الخاطئ. الحل هو القيام بـ I/O فقط في مخازن نظام التشغيل (OS buffers).
If a process is waiting for I/O at a specific memory address, moving the process via compaction will cause the I/O to be written to the wrong location. The solution is to do I/O only into OS buffers.
6 تجزئة الذاكرة (Paging)
6 Paging
تقسيم الذاكرة المادية إلى إطارات (Frames) والمنطقية إلى صفحات (Pages) لتجنب التجزئة الخارجية.
Dividing physical memory into frames and logical memory into pages to avoid external fragmentation.
تسمح التجزئة بأن تكون مساحة العنوان المادي للعملية غير متجاورة. يتم تقسيم الذاكرة المادية إلى كتل ثابتة الحجم تسمى إطارات (Frames)، والذاكرة المنطقية إلى كتل بنفس الحجم تسمى صفحات (Pages).
يتم استخدام جدول الصفحات (Page Table) لترجمة العناوين المنطقية إلى مادية.
العنوان المنطقي ينقسم إلى: رقم الصفحة (p) كفهرس في جدول الصفحات، و إزاحة الصفحة (d) التي تُدمج مع عنوان الأساس لتحديد العنوان المادي.
Paging allows the physical address space of a process to be noncontiguous. Physical memory is divided into fixed-sized blocks called frames. Logical memory is divided into blocks of the same size called pages.
A page table translates logical to physical addresses.
Logical address is divided into: Page number (p) used as an index into the page table, and Page offset (d) combined with base address to define the physical address.
التجزئة تقضي تماماً على التجزئة الخارجية (External Fragmentation) ومشكلة الكتل متغيرة الحجم، ولكنها لا تزال تعاني من التجزئة الداخلية (Internal Fragmentation) في الصفحة الأخيرة من العملية إذا لم يكن حجم العملية من مضاعفات حجم الصفحة.
Paging completely avoids external fragmentation and the problem of varying sized memory chunks. However, it still suffers from internal fragmentation in the last page of a process if the process size is not an exact multiple of the page size.
إذا كان حجم الصفحة 2048 بايت، وحجم العملية 72,766 بايت، فما هو مقدار التجزئة الداخلية؟ If page size is 2,048 bytes and process size is 72,766 bytes, what is the internal fragmentation?
العملية تحتاج 35 صفحة كاملة (71,680 بايت) ويتبقى 1,086 بايت للصفحة 36. التجزئة الداخلية = 2048 - 1086 = 962 بايت.
The process needs 35 full pages (71,680 bytes) + 1,086 bytes in the 36th page. Internal fragmentation = 2,048 - 1,086 = 962 bytes.
7 ذاكرة التخزين المؤقت للترجمة (TLB) ووقت الوصول الفعال
7 Translation Look-Aside Buffer (TLB) & EAT
ذاكرة تخزين مؤقت سريعة جداً (Cache) تحل مشكلة الوصول المزدوج للذاكرة في نظام التجزئة.
A very fast hardware cache that solves the two-memory access problem in paging.
بما أن جدول الصفحات يُحفظ في الذاكرة الرئيسية، فإن كل وصول للبيانات يتطلب وصولين للذاكرة (واحد للجدول وواحد للبيانات). لحل هذا، نستخدم TLB (ذاكرة ترابطية سريعة).
إذا كان رقم الصفحة موجوداً في TLB (TLB hit)، نحصل على الإطار فوراً. إذا لم يكن (TLB miss)، نصل إلى جدول الصفحات في الذاكرة ثم نُحمّل القيمة في TLB.
وقت الوصول الفعال (EAT): يُحسب بناءً على نسبة الإصابة (Hit ratio).
Since the page table is kept in main memory, every data access requires two memory accesses (one for the page table, one for data). To solve this, we use a TLB (associative memory).
If the page number is in the TLB (TLB hit), we get the frame immediately. If not (TLB miss), we access the page table in memory and load the value into the TLB.
Effective Access Time (EAT): calculated based on the hit ratio.
بعض TLBs تخزن معرفات مساحة العنوان (ASIDs) لتوفير حماية مساحة العنوان لكل عملية، وإلا يجب مسح (Flush) الذاكرة المؤقتة عند كل تبديل سياق (Context switch).
Some TLBs store address-space identifiers (ASIDs) in each TLB entry to uniquely identify each process and provide protection. Otherwise, the TLB must be flushed at every context switch.
إذا كان وقت الوصول للذاكرة 10ns، ونسبة الإصابة في TLB هي 80%، فما هو EAT؟ If memory access time is 10ns, and TLB hit ratio is 80%, what is the EAT?
EAT = 0.80 * 10ns + 0.20 * 20ns = 8 + 4 = 12ns.
EAT = 0.80 * 10ns + 0.20 * 20ns = 8 + 4 = 12ns.
8 حماية الذاكرة وجدول الصفحات المعكوس
8 Memory Protection & Inverted Page Table
استخدام بتات الصلاحية (Valid/Invalid) للحماية، وجدول معكوس لتقليل حجم الذاكرة المستخدمة للجداول.
Using Valid/Invalid bits for protection, and an inverted table to reduce memory overhead of page tables.
حماية الذاكرة: يتم تنفيذها بربط بت حماية بكل إطار (للقراءة فقط أو القراءة/الكتابة). يُضاف بت صالح-غير صالح (Valid-invalid bit) لكل إدخال في جدول الصفحات؛ "صالح" يعني أن الصفحة قانونية وتقع في مساحة العملية.
جدول الصفحات المعكوس (Inverted Page Table): بدلاً من جدول لكل عملية، يوجد إدخال واحد لكل إطار مادي حقيقي في الذاكرة. يقلل هذا من الذاكرة المطلوبة لتخزين الجداول، لكنه يزيد من وقت البحث (يُستخدم جدول تجزئة Hash table لتسريع البحث).
Memory Protection: Implemented by associating a protection bit with each frame (read-only/read-write). A Valid-invalid bit is attached to each page table entry; "valid" indicates the page is legal and in the process's logical space.
Inverted Page Table: Rather than each process having a page table, there is one entry for each real physical frame of memory. This decreases memory needed to store page tables but increases search time (hash tables are used to limit search).
المشكلة الرئيسية في جدول الصفحات المعكوس هي صعوبة تنفيذ الذاكرة المشتركة (Shared memory)، لأنه يسمح بتعيين عنوان افتراضي واحد فقط لكل عنوان مادي مشترك.
The main difficulty with an inverted page table is implementing shared memory, because there is only one mapping of a virtual address to the shared physical address.
لماذا يقلل جدول الصفحات المعكوس من استهلاك الذاكرة؟ Why does an inverted page table reduce memory consumption?
لأن حجمه يعتمد على حجم الذاكرة المادية (عدد الإطارات) بدلاً من مساحة العنوان المنطقي الشاسعة لجميع العمليات مجتمعة.
Because its size depends on the physical memory size (number of frames) rather than the vast logical address spaces of all processes combined.
9 التبديل (Swapping)
9 Swapping
نقل العمليات مؤقتاً من الذاكرة الرئيسية إلى القرص (Backing store) ثم إعادتها لمواصلة التنفيذ.
Temporarily moving processes out of main memory to a backing store (disk) and bringing them back for continued execution.
يسمح التبديل بأن يتجاوز إجمالي مساحة الذاكرة المادية للعمليات حجم الذاكرة المادية الفعلية المتاحة.
Backing store: قرص سريع وكبير بما يكفي لاستيعاب نسخ من جميع صور الذاكرة.
Roll out, roll in: متغير من التبديل يُستخدم في خوارزميات الجدولة القائمة على الأولوية؛ تُنقل العملية ذات الأولوية المنخفضة للخارج لتحميل عملية ذات أولوية أعلى.
الجزء الأكبر من وقت التبديل هو وقت النقل (Transfer time)، والذي يتناسب طردياً مع كمية الذاكرة المبدلة.
Swapping allows the total physical memory space of processes to exceed actual physical memory.
Backing store: fast disk large enough to accommodate copies of all memory images.
Roll out, roll in: swapping variant used for priority-based scheduling; lower-priority process is swapped out so a higher-priority process can be loaded.
The major part of swap time is transfer time, which is directly proportional to the amount of memory swapped.
يحتفظ النظام بقائمة انتظار جاهزة (Ready queue) للعمليات الجاهزة للتشغيل والتي تمتلك صور ذاكرة على القرص.
التبديل القياسي بطيء جداً في الأنظمة الحديثة، لذا تستخدم الأنظمة الحديثة التبديل مع التجزئة (Swapping with Paging) حيث يتم تبديل صفحات معينة فقط بدلاً من العملية بأكملها.
The system maintains a ready queue of ready-to-run processes which have memory images on disk.
Standard swapping of entire processes is too slow for modern systems, so modern OSs use swapping with paging (page out/page in) where only specific pages are swapped.
ما هو العامل الرئيسي الذي يحدد وقت التبديل (Swap time)؟ What is the major factor determining swap time?
وقت النقل (Transfer time)، وهو يتناسب طردياً مع كمية الذاكرة التي يتم تبديلها.
Transfer time, which is directly proportional to the amount of memory being swapped.