هيكلة جدول الصفحات في نظام التشغيل Structure of Page Table

يحدد هيكل جدول الصفحات (Structure of page table) ببساطة عدد الطرق التي يمكن بها هيكلة جدول الصفحات، حسنًا، التقسيم إلى صفحات (paging) عبارة عن تقنية لإدارة الذاكرة حيث يتم تقسيم عملية كبيرة إلى صفحات ويتم وضعها في الذاكرة الفعلية التي تنقسم أيضًا إلى إطارات (frames)، حجم الإطار والصفحة متكافئ، يستخدم نظام التشغيل جدول الصفحات لتعيين العنوان المنطقي للصفحة التي تمّ إنشاؤها بواسطة وحدة المعالجة المركزية إلى عنوانها الفعلي في الذاكرة الرئيسية، في هذا المقال، سنناقش ثلاث طرق شائعة نستخدمها لهيكلة جدول الصفحات: جدول الصفحة الهرمي، جدول الصفحات المجزأة، جدول الصفحة المقلوب.

جدول الصفحة الهرمي Hierarchical Page Table

كما علمنا عندما تصل وحدة المعالجة المركزية إلى صفحة من أي عملية يجب أن تكون في الذاكرة الرئيسية، إلى جانب الصفحة، يجب أيضًا تخزين جدول الصفحات لنفس العملية في الذاكرة الرئيسية، الآن، ماذا لو كان حجم جدول الصفحات أكبر من حجم إطار الذاكرة الرئيسية؟ في هذه الحالة، يتعين علينا تقسيم جدول الصفحات على مستويات متعددة من أجل احتوائه في إطار الذاكرة الرئيسية، دعونا نفهم هذا بمساعدة مثال:

ضع في اعتبارك أنّ حجم الذاكرة الرئيسية “الذاكرة الفعلية” هو (512) ميجابايت = 2^{29} “أي يمكن تمثيل الذاكرة الفعلية بـ (29) بت”، تنقسم هذه الذاكرة الفعلية إلى عدد من الإطارات حيث يكون حجم كل إطار = (4) كيلوبايت = 2^{12} “أي يمكن تمثيل حجم الإطار بـ (12) بت”:

الذاكرة الفعلية بالبتات = 29

حجم الإطار بالبتات = 12

عدد البتات المستخدمة لتمثيل رقم الإطار = 29-12 = 17

Total number of frames would be 2^{17} = 1, 31,072

الآن لدينا ذاكرة فعلية تبلغ (512) ميجابايت مقسمة إلى (131072) إطارًا حيث يبلغ حجم كل إطار (4) كيلوبايت، يدعم النظام الحديث اليوم مساحة العنوان المنطقية التي تصل إلى 2^{32} إلى 2^{64} بايت، ضع في اعتبارك أنّ لدينا عملية حجمها (4 جيجابايت = 2^{32})، تنقسم العملية الآن إلى عدد من الصفحات ونعلم أنّ حجم الصفحة يساوي حجم الإطار (= 4 كيلوبايت = 2^{12}):

العنوان المنطقي بالبتات = 32

حجم الصفحة بالبت = 12

عدد البتات المستخدمة لتمثيل رقم الصفحة = 32-12 = 20

لذلك سيكون العدد الإجمالي لصفحات العملية = (2^{20}) أي ما يصل إلى (1) مليون، لذلك، يتعين علينا تنفيذ جدول صفحات لتخزين معلومات صفحات العملية، أي الصفحة التي يتم تخزينها في أي إطار من الذاكرة، نظرًا لأنّ لدينا مليون صفحة من العملية، فسيكون هناك مليون إدخال في جدول الصفحات، الآن في جدول الصفحة، يعمل رقم الصفحة الذي توفره وحدة المعالجة المركزية في العنوان المنطقي كفهرس يقودك إلى رقم الإطار حيث يتم تخزين هذه الصفحة في الذاكرة الرئيسية، هذا يعني أنّ كل إدخال لجدول الصفحة له رقم الإطار.

جدول الصفحات المجزأة Hashed Page Table

عندما تتجاوز مساحة العنوان المنطقي (32) بت في مثل هذه الحالة، يتم تنظيم جدول الصفحات باستخدام جدول الصفحات المجزأة، على الرغم من أنّه يمكننا هيكلة جدول الصفحات الكبير باستخدام جدول الصفحات متعدد المستويات (multilevel page table)، إلّا أنّه يتكون من عدد من المستويات يزيد من تعقيد جدول الصفحات.

يعد جدول الصفحات المجزأ طريقة ملائمة لهيكلة جدول الصفحات حيث تتجاوز مساحة العنوان المنطقي (32) بت، يحتوي جدول التجزئة على عدة إدخالات حيث يحتوي كل إدخال على قائمة ارتباط، تحتوي كل قائمة روابط على مجموعة من العناصر المرتبطة حيث يتم تجزئة كل عنصر إلى نفس الموقع، يحتوي كل عنصر على ثلاثة إدخالات لرقم الصفحة ورقم الإطار ومؤشر للعنصر التالي، سوف نفهم عمل جدول الصفحات هذا بشكل أفضل بمساعدة المثال التالي:

تنشئ وحدة المعالجة المركزية عنوانًا منطقيًا للصفحة التي تحتاجها، الآن، يجب تعيين هذا العنوان المنطقي (logical address) إلى العنوان الفعلي (physical address)، يحتوي هذا العنوان المنطقي على إدخالين، أي رقم الصفحة (P3) على سبيل المثال وإزاحة (offset)، يتم توجيه رقم الصفحة من العنوان المنطقي إلى وظيفة التجزئة، تنتج وظيفة التجزئة قيمة تجزئة مطابقة لرقم الصفحة، توجه قيمة التجزئة هذه إلى إدخال في جدول التجزئة، ونعلم أنّه يحتوي كل إدخال في جدول التجزئة على قائمة ارتباطات، هنا تتم مقارنة رقم الصفحة مع الإدخال الأول للعنصر الأول إذا تمّ العثور على تطابق ثمّ يتم فحص الإدخال الثاني.

على سبيل المثال، يشتمل العنوان المنطقي على رقم الصفحة (P3) الذي لا يتطابق مع العنصر الأول في قائمة الارتباطات لأنّه يتضمن رقم الصفحة (P1)، لذلك سوف نمضي قدما ونتحقق من العنصر التالي؛ الآن يحتوي هذا العنصر على إدخال رقم الصفحة، أي (P3)، لذا سنتحقق من إدخال الإطار للعنصر وهو (fr5)، إلى رقم الإطار هذا، سنلحق الإزاحة المقدمة في العنوان المنطقي للوصول إلى العنوان الفعلي للصفحة، إذن، هذه هي الطريقة التي يعمل بها جدول الصفحات المجزأة لتعيين العنوان المنطقي إلى العنوان الفعلي.

جدول الصفحة المقلوب Inverted Page Table

يشير مفهوم التقسيم العادي للصفحات إلى أنّ كل عملية تحتفظ بجدول الصفحات الخاص بها والذي يتضمن إدخالات جميع الصفحات التي تنتمي إلى العملية، قد تحتوي العملية الكبيرة على جدول صفحات يحتوي على ملايين الإدخالات، يستهلك جدول الصفحات هذا قدرًا كبيرًا من الذاكرة، لنفترض أنّ لدينا ست عمليات قيد التنفيذ، لذلك، ست عمليات تحتوي على جزء أو آخر من صفحتها في الذاكرة الرئيسية ممّا سيجبر جداول الصفحات أيضًا على التواجد في الذاكرة الرئيسية التي تستهلك مساحة كبيرة، هذا هو عيب مفهوم التقسيم.

جدول الصفحات المقلوب هو الحل لهذا الهدر في الذاكرة، يتضمن مفهوم جدول الصفحات المقلوب وجود جدول من صفحة واحدة يحتوي على مدخلات لجميع الصفحات “قد تنتمي إلى عمليات مختلفة” في الذاكرة الرئيسية إلى جانب معلومات العملية المرتبطة بها، للحصول على فهم أفضل، ضع في اعتبارك المثال التالي لجدول الصفحات المقلوب:

تنشئ وحدة المعالجة المركزية العنوان المنطقي للصفحة التي تحتاج إلى الوصول إليها، هذه المرة يتكون العنوان المنطقي من ثلاثة إدخالات معرّف العملية ورقم الصفحة والإزاحة، يحدد معرف العملية العملية، التي تمّ طلب الصفحة منها، ويشير رقم الصفحة إلى أي صفحة من العملية تمّ طلبها وتشير قيمة الإزاحة إلى الإزاحة المطلوبة.

يتم البحث عن تطابق معرف العملية مع رقم الصفحة المقترنة في جدول الصفحة ويقول ما إذا تمّ العثور على البحث في إدخال (ith) في جدول الصفحة، ثمّ يقوم (i و offset) معًا بإنشاء العنوان الفعلي للصفحة المطلوبة، هذه هي الطريقة التي يتم بها تعيين العنوان المنطقي لعنوان فعلي باستخدام جدول الصفحات المقلوب، على الرغم من أنّ جدول الصفحة المقلوب يقلل من إهدار الذاكرة إلّا أنّه يزيد من وقت البحث، وذلك لأنّ الإدخالات الموجودة في جدول الصفحات المقلوب يتم فرزها على أساس العنوان الفعلي بينما يتم إجراء البحث باستخدام العنوان المنطقي، يحدث أحيانًا أن يتم البحث في الجدول بأكمله للعثور على المطابقة.