CS330 - أنظمة التشغيل
الجمود في النظام، المنع، التجنب، الاكتشاف والاسترداد
الجمود هو حالة حيث مجموعة من العمليات محجوبة لأن كل عملية تمتلك موردًا وتنتظر موردًا آخر مملوكًا بواسطة عملية أخرى.
عملية P1 تمتلك مورد R1 وتنتظر مورد R2
عملية P2 تمتلك مورد R2 وتنتظر مورد R1
النتيجة: كلتا العمليتين تنتظران إلى الأبد!
الجمود يمكن أن يحدث إذا تحققت كل الشروط الأربعة في نفس الوقت:
يجب أن يكون مورد واحد على الأقل محتجزًا بطريقة غير قابلة للمشاركة. عملية واحدة فقط في كل مرة يمكنها استخدام المورد.
يجب أن تحتجز العملية موردًا واحدًا على الأقل وتنتظر للحصول على موارد إضافية محتجزة بواسطة عمليات أخرى.
لا يمكن استباق الموارد؛ يمكن تحرير المورد فقط طواعية بواسطة العملية التي تحتجزه.
يجب أن توجد مجموعة {P0, P1, ..., Pn} من العمليات المنتظرة بحيث P0 تنتظر P1، P1 تنتظر P2، ...، و Pn تنتظر P0.
يجب توفر جميع الشروط الأربعة لحدوث الجمود. إذا تمكنا من منع أي شرط واحد من هذه الشروط، يمكننا منع الجمود!
رسم بياني موجه يستخدم لوصف الجمود
[إدراج مخططات RAG تظهر سيناريوهات جمود وبدون جمود]
ضمان أن شرطًا واحدًا على الأقل من الشروط الأربعة لا يمكن أن يتحقق.
يتطلب معرفة مسبقة باحتياجات الموارد. النظام يقرر ما إذا كان الطلب يجب أن ينتظر.
السماح بحدوث الجمود، ثم اكتشافه والاسترداد منه.
خوارزمية النعامة - التظاهر بأن الجمود لا يحدث أبدًا.
تقييد طرق تقديم طلبات الموارد لضمان أن شرطًا واحدًا على الأقل لا يمكن أن يحدث:
المنع: غير عملي لمعظم الموارد. بعض الموارد بطبيعتها غير قابلة للمشاركة (مثل الطابعة).
الحل: استخدام spooling لبعض الموارد (قوائم انتظار الطابعة).
المنع: ضمان أنه عندما تطلب عملية موردًا، فإنها لا تحتجز أي موارد أخرى.
الحلول:
المنع: إذا كانت عملية تحتجز موارد وتطلب موردًا آخر لا يمكن تخصيصه فورًا، يتم تحرير جميع الموارد المحتجزة حاليًا.
الحدود: يُطبق فقط على الموارد التي يمكن حفظ حالتها (المعالج، الذاكرة).
المنع: فرض ترتيب كلي لجميع أنواع الموارد.
الحل: طلب العمليات للموارد بترتيب تصاعدي.
الحالة آمنة إذا كان بإمكان النظام تخصيص موارد لكل عملية بترتيب ما وتجنب الجمود.
النظام في حالة آمنة إذا كان هناك تسلسل آمن لجميع العمليات.
لا جمود ممكن
قد تؤدي لجمود
النظام عالق
لنسخة واحدة من كل نوع مورد:
سميت على اسم النظام المصرفي الذي يضمن أن البنك لا يخصص كل النقود.
الموارد المتاحة
الحد الأقصى للطلب
المخصص حاليًا
الاحتياج = Max - Allocation
النظام في حالة آمنة مع هذا الترتيب للتنفيذ
السماح للنظام بالدخول في حالة جمود، ثم اكتشافه والاسترداد منه.
| العامل | الاعتبارات |
|---|---|
| الأولوية | عملية ذات أولوية أقل تُختار أولاً |
| الوقت | كم من الوقت حسبت العملية والوقت المتبقي |
| الموارد | الموارد المستخدمة والموارد اللازمة للاكتمال |
| تكلفة التراجع | عدد العمليات التي تحتاج إنهاء |
| تفاعلية/دفعية | العمليات التفاعلية قد تكون لها أولوية أعلى |
المعطيات: ٥ عمليات (P0-P4)، ٣ أنواع موارد (A=١٠، B=٥، C=٧)
| العملية | المخصص (A B C) |
الحد الأقصى (A B C) |
الاحتياج (A B C) |
|---|---|---|---|
| P0 | ٠ ١ ٠ | ٧ ٥ ٣ | ٧ ٤ ٣ |
| P1 | ٢ ٠ ٠ | ٣ ٢ ٢ | ١ ٢ ٢ |
| P2 | ٣ ٠ ٢ | ٩ ٠ ٢ | ٦ ٠ ٠ |
| P3 | ٢ ١ ١ | ٢ ٢ ٢ | ٠ ١ ١ |
| P4 | ٠ ٠ ٢ | ٤ ٣ ٣ | ٤ ٣ ١ |
المتاح: A=٣، B=٣، C=٢
التسلسل الآمن: <P1, P3, P4, P2, P0>
حالة النظام: آمنة ✓
إذا طلبت P1 (١،٠،٢):
س١. أي مما يلي ليس شرطًا ضروريًا للجمود؟
س٢. في رسم تخصيص الموارد، الدورة تشير إلى:
س٣. خوارزمية المصرفي تستخدم لـ:
س٤. الحالة الآمنة تعني:
س٥. أي طريقة تمنع الانتظار الدائري؟
س٦. اشرح الفرق بين منع الجمود وتجنب الجمود.
المنع: يجعل الجمود مستحيلًا هيكليًا بضمان أن شرطًا واحدًا على الأقل من الشروط الضرورية لا يمكن أن يحدث.
التجنب: يفحص ديناميكيًا حالة تخصيص الموارد لضمان أن النظام لا يدخل أبدًا في حالة غير آمنة.
س٧. لدينا ٣ عمليات بالاحتياجات التالية. هل النظام في حالة آمنة؟
| العملية | المخصص | الحد الأقصى |
|---|---|---|
| P0 | ١ | ٤ |
| P1 | ٢ | ٣ |
| P2 | ٢ | ٩ |
المتاح = ٢
الاحتياج: P0=٣، P1=١، P2=٧
يمكن تلبية P1 (الاحتياج=١ ≤ المتاح=٢)
بعد P1: المتاح = ٢ + ٢ = ٤
يمكن تلبية P0 (الاحتياج=٣ ≤ المتاح=٤)
بعد P0: المتاح = ٤ + ١ = ٥
لا يمكن تلبية P2 (الاحتياج=٧ > المتاح=٥)
النظام ليس في حالة آمنة
| المصطلح | التعريف |
|---|---|
| جمود | عمليات محجوبة إلى الأبد تنتظر بعضها البعض |
| جمود حي | عمليات تغير حالتها باستمرار ولكن لا تتقدم |
| تجويع | عملية تنتظر إلى أجل غير مسمى بينما تتقدم عمليات أخرى |
| حالة آمنة | النظام يمكنه تخصيص موارد بدون الدخول في جمود |
| حالة غير آمنة | قد تؤدي لجمود (ليست بالضرورة في جمود) |
| RAG | رسم تخصيص الموارد لتصور تخصيص الموارد |
| خوارزمية المصرفي | خوارزمية تجنب الجمود لعدة نسخ من الموارد |
| رسم انتظار | متغير من RAG لاكتشاف الجمود |
| انتظار دائري | سلسلة دائرية من العمليات تنتظر موارد |
| ترتيب الموارد | تقنية منع بتعيين ترتيب للموارد |
| تراجع | إعادة عملية إلى حالة آمنة سابقة |
| اختيار ضحية | اختيار عملية لإنهائها أو استباقها |
[إدراج مخطط RAG مع عمليات وموارد]
[إدراج مقارنة RAGs مع وبدون دورات]
[إدراج مخطط انتقال الحالة]
[إدراج تنفيذ خوارزمية المصرفي خطوة بخطوة]
ملاحظة: يرجى توفير المخططات الفعلية من مواد المقرر لاستبدال هذه العناصر النائبة.