الأحد، 24 أغسطس، 2014

5- نظام التشغيل (Linux) - النواة، الجدولة، جدولة المهام



بسم الله الرحمن الرحيم

الدرس الخامس - النواة، الجدولة، جدولة المهام



النواة: Kernel
قام لينوس تروفالدوز بكتابة نواة نظام تشغيل لغرض تشغيل نظام التشغيل الخاص به على حاسبته المنزلية لان أنظمة التشغيل كانت تعمل على حواسيب عملاقة في الجامعات والمؤسسات وبعد نجاحه في كتابة النواة تم دمجها مع مشروع (GNU) لينتج نظام التشغيل (Linux).
والنواة لنظام التشغيل هي الجزء المركزي الذي يدير النظام وهي عبارة عن برنامج خاص جدا يدير كل العمليات وسواقات الأجهزة وعمليات الإدخال والإخراج, وعندما يبدأ تشغيل النظام يتم تشغيل النواة أولا. وثم تقوم بتهيئة الأجزاء المادية وهياكل البيانات وبعد أن تنهي النواة هذه المرحلة تقوم بتحميل وتشغيل برامج النظام.
وللنواة العديد من الوظائف فبعد إقلاع النظام تبدأ مرحلة إدارة الأجهزة والعمليات على الرغم من أن المعالج -في مفهوم الحاسوب- يستطيع أن ينفذ برنامجاً واحداً في وقت واحد فأن النواة تحمل العديد من البرامج على الذاكرة وإدارتها, وعملية إدارة العمليات تكون كالأتي:
  1. النواة لها السيطرة على المعالج, وهنالك العديد من العمليات في الذاكرة.
  2. النواة تختار عملية وتؤشر إلى أين وصل تنفيذ هذه العملية.
  3. النواة تترك السيطرة على المعالج.
  4. يتم تنفيذ العملية لوقت معين (مثلا عدة ثواني).
  5. عندما ينتهي وقت العملية توقف ساعة القطع العملية ويرجع التحكم مرة أخرى للنواة.
  6. النواة تهتم بأعمال النظام المطلوبة مثل القراءة أو الكتابة على احد الأجهزة.
  7. اذهب إلى خطوة (2).
يبسط هذا الوصف عمل النواة بعض الشيء ويتبين أن النواة عبارة عن جزء من الشفرة الذي ينفذ بين حين وآخر بين العمليات.
في (Linux) تقع النواة عادة في ملف اسمه /vmlinuz أو /boot/vmlinuz والـ(Boot Loader ) يحمل هذا الملف إلى الذاكرة يمكنه من العمل عند انطلاق النظام.

الجدولة في لينكس: Scheduling in Linux
الجدولة هي عملية تعيين وقت المعالج إلى مهام مختلفة موجودة في نظام التشغيل و كل مهمة يسمح لها بان تنفذ فقط إذا كانت هي المهمة الوحيدة في النظام ولا علاقة لها بالمهام الأخرى (ما لم يكن تصميم البرنامج يتطلب ذلك) وهذا يجعل البرامج أكثر سهولة في التطوير والصيانة والنقل وعلى الرغم من أن المعالج ينفذ (Thread) واحدة ضمن المهمة فان النظام يتواجد فيه في الوقت نفسه العديد من الـ (Thread) تابعة لعدة مهام بحيث أن النظام يجدول (Thread) واحدة للتنفيذ بوقت قصير ثم يتم الانتقال لتنفيذ (Thread) أخرى ويجب أن تحقق الجدولة وقت استجابة سريع للمهام و(throughput) جيد للمهام التي تعمل بالخلفية، كما يجب تجنب حالات المجاعة للمهام والتوفيق بين متطلبات الأسبقية العالية والمنخفضة وهذا يتم حسب مجموعة من القواعد تحدد متى وكيف سيتم اختيار المهمة لتنفيذها تدعى سياسة الجدولة (scheduling policy).

جدولة المهام: Task Scheduling
في الإصدار 2.4 من نواة (Linux) تدعم النواة طرق جدولة تقليدية من خوارزميات الجدولة الخاصة بيونكس وان هذه الطرق لا تنمو بصورة جيدة (not scale well) عندما يزداد عدد المهام في النظام كما إنها لا توفر دعماً لتعدد المعالجات. ومع الإصدار 2.5 غير المستقر من النواة ثم الإصدار 2.6 المستقر تم استخدام خوارزمية جدولة جديدة هي O1 algorithm وان الحرف Big-O يعني معدل الزيادة في وقت التنفيذ لخوارزمية الجدولة بالاعتماد على كمية الإدخالات للخوارزمية فمثلا On يعني أن وقت التنفيذ للخوارزمية يزداد بصورة خطية كلما ازداد حجم الإدخالات كما أن On^2 يعني أن النمو تربيعي والخوارزمية O1 يعني أن الوقت الأعلى لتنفيذ الخوارزمية هو وقت ثابت أي إنها تضمن الانتهاء بكمية محددة من الوقت بغض النظر عن حجم الإدخالات وتوفر هذه الخوارزمية موازنة للحمل والعدالة والدعم للمهام الفعالة.
مجدول (Linux) يكون قابل للمقاطعة (preemptive) ويستخدم خوارزمية تعتمد على الأولوية (priority-based algorithm) باستخدام نطاقين منفصلين من الأولوية هما مدى الزمن الحقيقي (real-time range) وهو من 0-99 والمدى المعتمد على قيم الـ(nice) وهو من 100-140 والقيم الأقل هي الأعلى أولوية وال(Linux) يعطي وقتاً اكبر للمهام الأعلى أولوية و الشكل (1) يوضح العلاقة بين الأولوية وطول شريحة الوقت

الشكل (1) العلاقة بين الأولوية وطول شريحة الزمن


أي مهمة تعتبر مرشحة للتنفيذ من المعالج طالما أن لها وقتاً متبقياًً في شريحة الوقت الخاصة بها. وعندما تستنزف المهمة شريحة وقتها فإنها تعتبر منتهية (expired) ولا ترشح للتنفيذ ثانية حتى تكمل جميع المهام الأخرى شرائح الوقت الخاصة بها، النواة تدير قائمة بكل المهام قيد التنفيذ في هيكل بيانات هو (runqueue) وهو يراقب ويتابع كل المهام قيد التنفيذ وكل معالج له (runqueue) خاص به والـ (runqueue) يتكون من مصفوفتين مرتبتين حسب الأولوية (Priority arrays) هما (active) و (expired) تحوي المصفوفة (active) جميع المهام التي لها وقت متبقي في شرائح الوقت الخاصة بهم وتحوي المصفوفة (expired) جميع المهام المنتهية لاحظ الشكل (2). مصفوفة الأولوية (Priority arrays) هي عبارة عن مصفوفة كل عنصر يشير إلى بداية قائمة موصولة وكل قائمة موصولة تمثل مستوى من الأولوية وعندما يتم إضافة مهمة إلى الـ (Priority arrays) فإنها تضاف إلى القائمة في مستوى الأولوية الخاص بها ويتم تعديل مصفوفة (bitmap) وهي تحوي على قيم تمثل فعالية أو تعطيل مستوى الأولوية في الـ (Priority arrays) فمثلا إذا كان هنالك ثلاث مهام في النظام واحدة في مستوى الأولوية 5 واثنتين في مستوى الأولوية 0 فانه سيتم تفعيل البت 0 و 5 من الـ (bitmap).

الشكل (2) ترتيب المهام حسب الأولوية

المجدول يقوم باختيار المهمة ذات الأولوية الأعلى من مصفوفة الـ(active) ليتم تنفيذها على المعالج وعملية إيجاد المهمة ذات أعلى أولوية هي عملية سهلة لأنه فقط يجب إيجاد أول بت فعال في الـ (bitmap) ثم تحديد القائمة الموصولة المطلوبة من مصفوفة الـ (active) وإذا كان هنالك أكثر من مهمة في القائمة نفسها فإنها ستنفذ بأسلوب (round-robin) ثم بعد تنفيذ المهمة للـ(time slice) الخاص بها يتم نقلها من مصفوفة الـ(active) إلى مصفوفة الـ(expired) وعندما يتم نقل جميع المهام وتصبح مصفوفة الـ(active) فارغة يتم تبديل مصفوفة الـ(active) و مصفوفة الـ(expired) أي تبديل المؤشرين فقط بين المصفوفتين نلاحظ أن عملية إيجاد أول بت في الـ(bitmap) وإيجاد أول عنصر في القائمة يتطلب وقتاً محدداً لإكمال العملية ولهذا تسمى الخوارزمية O1.


هذه صورة مصغرة لخارطة النواة......

ممكن استخدام الخارطة التفاعلية لنواة اللنكس من الرابط التالي
Interactive map of linux kernel

هناك تعليقان (2):