الوحدة 6: الجمود (Deadlock) والمجاعة (Starvation)

1️⃣ مبادئ الجمود (Deadlock)

🔸 الجمود (Deadlock):

الجمود هو حالة حرجة في أنظمة التشغيل المتزامنة تحدث عندما تتوقف مجموعة من العمليات بشكل دائم، لأن كل عملية في المجموعة تنتظر موردًا محتجزًا من قبل عملية أخرى في نفس المجموعة. هذا يؤدي إلى توقف جميع العمليات المعنية عن التقدم.

🔹 شروط نشوء الجمود (Coffman Conditions):

لكي يحدث الجمود، يجب أن تتحقق الشروط الأربعة التالية في نفس الوقت:

• الحصر المتبادل (Mutual Exclusion): يجب أن يكون المورد غير قابل للمشاركة، أي يمكن لعملية واحدة فقط احتجاز المورد في أي وقت. إذا حاولت عملية أخرى الوصول إليه، يجب أن تنتظر.
• الاحتفاظ والانتظار (Hold and Wait): يجب أن تكون العملية قادرة على الاحتفاظ بمورد واحد على الأقل بينما تنتظر (وتطلب) موردًا آخر محتجزًا من قبل عملية أخرى.
• عدم الإزاحة القسرية (No Preemption): لا يمكن إجبار عملية على التنازل عن المورد الذي تحتجزه (أي لا يمكن سحب المورد منها بالقوة) إلا بعد أن تنتهي من استخدامه وتطلقه طواعية.
• الانتظار الدوري (Circular Wait): يجب أن توجد سلسلة مغلقة من العمليات (P1, P2, ..., Pn) حيث P1 تنتظر موردًا تحتجزه P2، وP2 تنتظر موردًا تحتجزه P3، وهكذا حتى Pn تنتظر موردًا تحتجزه P1.

📘 ملاحظة: إذا توفرت الشروط الأربعة جميعها، فقد يحدث الجمود. كسر أي من هذه الشروط يمكن أن يمنع حدوث الجمود.

2️⃣ منع الجمود (Deadlock Prevention)

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

🔸 أمثلة على طرق منع الجمود:

• كسر شرط الانتظار الدوري (Circular Wait):
  • فرض ترتيب ثابت لطلب الموارد: يتم تعيين رقم فريد لكل نوع من الموارد، وتُجبر العمليات على طلب الموارد بترتيب تصاعدي للأرقام. هذا يضمن عدم وجود انتظار دوري.
• كسر شرط الاحتفاظ والانتظار (Hold and Wait):
  • طلب جميع الموارد دفعة واحدة: يجب على العملية أن تطلب وتحتجز جميع الموارد التي تحتاجها في بداية تنفيذها. إذا لم تكن جميع الموارد متاحة، فلا تحتجز أيًا منها.
  • إطلاق الموارد المحتجزة: إذا كانت العملية تحتجز موارد وتحتاج إلى مورد آخر غير متاح، فيجب عليها إطلاق جميع الموارد التي تحتجزها حاليًا ثم إعادة طلبها كلها لاحقًا.
• كسر شرط عدم الإزاحة القسرية (No Preemption):
  • السماح بالإزاحة القسرية: إذا كانت عملية تحتاج إلى مورد تحتجزه عملية أخرى، يمكن إجبار العملية الأخرى على التنازل عن المورد (إزاحته قسريًا) إذا كانت حالتها تسمح بذلك (مثل أن تكون في حالة انتظار).
• كسر شرط الحصر المتبادل (Mutual Exclusion):
  • جعل الموارد قابلة للمشاركة: إذا أمكن، يتم تصميم الموارد بحيث يمكن لعدة عمليات مشاركتها في نفس الوقت (مثل ملفات القراءة فقط). ومع ذلك، هذا ليس ممكنًا دائمًا لجميع أنواع الموارد.

📌 ملاحظة: على الرغم من أن هذه الطرق تمنع الجمود، إلا أنها قد تؤثر سلبًا على الأداء، أو تقلل من استخدام الموارد، أو تزيد من تعقيد تصميم النظام.

3️⃣ تجنّب الجمود (Deadlock Avoidance)

تعمل استراتيجيات تجنب الجمود على تحليل حالة النظام بشكل ديناميكي قبل منح أي مورد. الهدف هو التأكد من أن منح المورد لن يؤدي إلى حالة جمود في المستقبل. يتطلب ذلك معرفة مسبقة بمتطلبات الموارد القصوى لكل عملية.

🔹 خوارزمية البنّاء (Banker’s Algorithm):

هي خوارزمية شهيرة لتجنب الجمود. تمثل النظام كأنه بنك يمنح قروضًا (تمثل الموارد) للعملاء (تمثل العمليات). قبل منح أي "قرض" (مورد)، يتحقق البنك (نظام التشغيل) دائمًا من أن حالة النظام ستظل "آمنة" بعد منح المورد.

• الحالة الآمنة (Safe State): هي حالة يمكن فيها للنظام تخصيص الموارد لكل عملية (حتى لو طلبت أقصى مواردها) بترتيب معين دون الوقوع في جمود.
• الحالة غير الآمنة (Unsafe State): هي حالة قد تؤدي إلى جمود، ولا يضمن النظام فيها تلبية جميع طلبات الموارد.

🔸 متطلبات خوارزمية البنّاء:

• المعرفة المسبقة: يجب أن يعرف نظام التشغيل الحد الأقصى لعدد كل نوع من الموارد التي قد تحتاجها كل عملية.
• تحديث مستمر: يجب تحديث مصفوفات الطلب والتخصيص للموارد باستمرار.
• تعقيد الحساب: تتطلب الخوارزمية حسابات معقدة نسبيًا في كل مرة يتم فيها طلب مورد، مما قد يؤثر على الأداء في الأنظمة الكبيرة.

4️⃣ كشف الجمود (Deadlock Detection)

إذا لم يقم نظام التشغيل بمنع أو تجنب الجمود، فإنه يمكن أن يسمح بحدوثه ثم يحاول كشفه ومعالجته.

🔸 كيفية الكشف عن الجمود:

• استخدام رسم بياني للموارد (Resource Allocation Graph): يمكن لنظام التشغيل بناء رسم بياني يوضح العمليات والموارد، والعلاقات بينها (من يطلب ماذا، ومن يحتجز ماذا). إذا تم رصد دورة (Cycle) في هذا الرسم البياني، فهذا يشير إلى وجود جمود.
• خوارزميات الكشف: يتم تشغيل خوارزميات خاصة بشكل دوري (أو عند طلب مورد لا يمكن تلبيته) لتحليل الرسم البياني وتحديد ما إذا كان هناك جمود.

🔸 استعادة النظام بعد الكشف عن الجمود:

إذا تم رصد الجمود، يقوم النظام بمحاولة استعادة حالته الطبيعية، وذلك عادةً عن طريق:

• إيقاف العمليات (Process Termination): إنهاء عملية واحدة أو أكثر من العمليات المتورطة في الجمود. قد يكون ذلك إنهاءً لجميع العمليات المتورطة، أو إنهاءً تدريجيًا لعملية واحدة تلو الأخرى حتى يتم كسر الجمود.
• سحب الموارد (Resource Preemption): إجبار عملية على التنازل عن مورد تحتجزه، ثم تخصيص هذا المورد لعملية أخرى متورطة في الجمود.
• إعادة جدولة العمليات (Process Rollback): إعادة العملية إلى حالة سابقة (نقطة تحقق - Checkpoint) قبل أن تدخل في حالة الجمود، ثم إعادة تشغيلها من تلك النقطة.

5️⃣ استراتيجية متكاملة (An Integrated Deadlock Strategy)

في الممارسة العملية، لا يوجد حل واحد مثالي للتعامل مع الجمود يناسب جميع الأنظمة والسيناريوهات. لذلك، غالبًا ما تتبنى أنظمة التشغيل الحديثة استراتيجية متكاملة تجمع بين عدة أساليب:

• منع Deadlock في الموارد الحرجة: بالنسبة للموارد الحيوية والنادرة التي يمكن أن يسبب الجمود فيها كارثة (مثل أقفال النواة الأساسية)، قد يتم تطبيق آليات منع صارمة لضمان عدم حدوث الجمود على الإطلاق.
• الكشف فقط في الموارد منخفضة التأثير: بالنسبة للموارد الأقل أهمية أو التي يكون فيها حدوث الجمود نادرًا ولا يسبب أضرارًا جسيمة، قد يكتفي النظام بالكشف عن الجمود فقط ثم اتخاذ إجراءات استعادة بسيطة (مثل إنهاء العملية المتورطة).
• تجاهل الجمود أحيانًا: في بعض البيئات، خاصة في أنظمة المستخدم الواحد أو الأنظمة التي يكون فيها الجمود نادرًا جدًا وتكلفة الكشف والمعالجة عالية، قد يتم تجاهل مشكلة الجمود. يُعرف هذا النهج بـ "خوارزمية النعامة" (Ostrich Algorithm)، حيث يتم تجاهل المشكلة على أمل ألا تحدث، أو أن المستخدم سيقوم بإعادة تشغيل النظام يدويًا إذا حدثت. هذا هو النهج المتبع في بعض إصدارات أنظمة التشغيل مثل Windows.

📘 الخلاصة: تعتمد الاستراتيجية المختارة على طبيعة النظام، أهمية الموارد، وتكلفة تطبيق كل استراتيجية، بالإضافة إلى مدى تأثير الجمود على أداء النظام واستقراره.

6️⃣ مشكلة الفلاسفة الجائعين (Dining Philosophers Problem)

مشكلة الفلاسفة الجائعين هي مشكلة كلاسيكية في علوم الحاسوب، تُستخدم لشرح تحديات التزامن والحصر المتبادل، وتوضح بشكل خاص إمكانية حدوث الجمود والمجاعة.

🔹 الوصف الكلاسيكي للمشكلة:

تخيل خمسة فلاسفة يجلسون حول طاولة دائرية. يوجد طبق من الأرز في منتصف الطاولة، وشوكة واحدة بين كل فيلسوفين.

• كل فيلسوف يتناوب بين التفكير وتناول الطعام.
• لكي يتمكن الفيلسوف من تناول الطعام، يحتاج إلى شوكتين (موردين): الشوكة التي على يساره والشوكة التي على يمينه.
• يمكن للفيلسوف أن يلتقط شوكة واحدة في كل مرة.

📌 سيناريو الجمود: إذا قام كل فيلسوف بالتقاط الشوكة التي على يساره في نفس الوقت، ثم انتظر الشوكة التي على يمينه، فسيحدث جمود. كل فيلسوف يحتجز موردًا (شوكة واحدة) وينتظر موردًا آخر (الشوكة الثانية) الذي تحتجزه عملية أخرى في حلقة دائرية. لا يمكن لأي فيلسوف أن يأكل، ولا يمكن لأي شوكة أن تُطلق.

🔸 حلول مقترحة للمشكلة:

• تخصيص شوكة واحدة فقط لكل فيلسوف في البداية: يتم تعديل القواعد بحيث لا يمكن للفيلسوف أن يلتقط الشوكة الثانية إلا إذا كانت متاحة فورًا، وإلا يجب عليه إطلاق الشوكة الأولى.
• السماح لفيلسوف واحد فقط بتناول الطعام في نفس الوقت: استخدام قفل عام (mutex) يضمن أن فيلسوفًا واحدًا فقط يمكنه محاولة التقاط الشوكتين في أي وقت.
• إدخال ترتيب تسلسلي للشوكت: تعيين ترتيب معين للشوكت (مثل ترقيمها) وإجبار الفلاسفة على التقاط الشوكت بترتيب معين (الأصغر أولًا) لمنع الانتظار الدوري.

7️⃣ آليات التزامن في أنظمة التشغيل

تختلف أنظمة التشغيل في كيفية تنفيذها لآليات التزامن والتعامل مع مشاكل الجمود. فيما يلي نظرة على بعض الأنظمة الشهيرة:

🔹 Unix:

• استخدام wait() و signal() عبر المكتبة pthreads.
• استخدام flock() لقفل الملفات ومنع الوصول المتزامن.
• دعم Semaphores و Mutexes عبر واجهات برمجة النظام.

🔹 Linux:

• دعم كامل لـ Semaphores و Spinlocks في النواة.
• استخدام futex() (Fast Userspace Mutex) لقفل خفيف الوزن.
• آليات متقدمة مثل RCU (Read-Copy-Update) للوصول المتزامن للقراءة والكتابة.

🔹 Windows:

• يستخدم CRITICAL_SECTION للقفل داخل مساحة عملية واحدة.
• يدعم Mutex و Event objects للتزامن بين العمليات.
• يوفر WaitForMultipleObjects للانتظار على عدة كائنات تزامن.

🔹 Android:

• يعتمد على نواة Linux ويستخدم آليات التزامن الخاصة بها.
• يستخدم HandlerThread و MessageQueue لإدارة التزامن بين الخيوط.
• يوفر Binder للاتصال بين العمليات مع ضمان التزامن.