أنظمة التشغيل إدارة الموارد الخوارزميات علوم الحاسب هندسة البرمجيات

خوارزمية المصرفي (Banker’s Algorithm)

- إدارة الموارد, الجمود, المصرفي, خوارزمية, نظام التشغيل

مقدمة عن الجمود

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

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

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

آلية عمل خوارزمية المصرفي

تعمل خوارزمية المصرفي على أساس فكرة “حالة الأمان”. تعتبر حالة النظام آمنة إذا كان من الممكن جدولة العمليات بحيث يمكن لكل عملية إكمال مهمتها، حتى إذا طالبت بحدها الأقصى من الموارد على الفور. إذا لم يكن من الممكن جدولة العمليات بهذه الطريقة، فإن النظام يعتبر في حالة غير آمنة، وقد يؤدي في النهاية إلى الجمود.

تعتمد الخوارزمية على المعلومات المسبقة حول متطلبات الموارد لكل عملية. تحدد الخوارزمية ثلاث مصفوفات رئيسية:

  • المصفوفة الحالية (Allocation): تمثل الموارد المخصصة حاليًا لكل عملية.
  • المصفوفة القصوى (Max): تمثل الحد الأقصى لمتطلبات الموارد لكل عملية.
  • المصفوفة المتاحة (Available): تمثل الموارد المتاحة حاليًا في النظام.

عندما تطلب عملية ما موارد، تتحقق الخوارزمية أولاً مما إذا كان تخصيص هذه الموارد سيؤدي إلى حالة آمنة. إذا كان الأمر كذلك، يتم تخصيص الموارد. وإلا، يتم تأخير طلب العملية حتى تصبح الموارد متاحة أو يتم إطلاق بعض الموارد من قبل عمليات أخرى.

لتحديد ما إذا كانت الحالة آمنة، تقوم الخوارزمية بما يلي:

  1. العثور على عملية يمكنها الإكمال: تبدأ بالتحقق مما إذا كانت هناك عملية يمكنها إكمال مهمتها بالموارد المتاحة حاليًا، أي أن الموارد المتاحة تلبي احتياجات العملية (الحد الأقصى – المخصص).
  2. محاكاة الإكمال: إذا تم العثور على عملية، فإن الخوارزمية تحاكي إكمال هذه العملية، مما يعني أنها تفترض أن العملية قد أطلقت جميع مواردها. يتم تحديث الموارد المتاحة وفقًا لذلك.
  3. التكرار: تكرر الخوارزمية الخطوتين 1 و 2 حتى يتم إكمال جميع العمليات أو لا يمكن العثور على أي عملية أخرى يمكنها الإكمال.
  4. تقييم السلامة: إذا تم إكمال جميع العمليات، فإن النظام في حالة آمنة. وإلا، فإن النظام في حالة غير آمنة، ويجب على الخوارزمية رفض طلب المورد.

خطوات الخوارزمية بالتفصيل

دعونا نتعمق في الخطوات التفصيلية لخوارزمية المصرفي:

  1. إدخال البيانات: يتم إدخال البيانات المتعلقة بالعمليات والموارد في شكل مصفوفات. تشمل هذه المصفوفات:
    • Allocation: مصفوفة (n x m) حيث n هو عدد العمليات و m هو عدد أنواع الموارد. يمثل العنصر (i, j) عدد وحدات المورد j التي تم تخصيصها للعملية i.
    • Max: مصفوفة (n x m) تمثل الحد الأقصى لعدد وحدات كل نوع من الموارد التي قد تحتاجها كل عملية.
    • Available: مصفوفة (1 x m) تمثل عدد وحدات كل نوع من الموارد المتاحة.
    • Need: مصفوفة (n x m) تمثل عدد وحدات كل نوع من الموارد التي لا تزال كل عملية بحاجتها لإكمال مهمتها. تحسب هذه المصفوفة على النحو التالي: Need[i, j] = Max[i, j] – Allocation[i, j]
  2. فحص السلامة: هذه هي الخطوة الرئيسية في الخوارزمية. تتضمن هذه الخطوة ما يلي:
    1. إنشاء مصفوفات عمل: يتم إنشاء مصفوفتين جديدتين:
      • Work: نسخة من مصفوفة الموارد المتاحة (Available).
      • Finish: مصفوفة منطقية بحجم n (عدد العمليات). يتم تهيئة جميع العناصر إلى “خطأ” (False).
    2. البحث عن عملية قابلة للتنفيذ: تبحث الخوارزمية عن عملية i بحيث يكون:
      • Finish[i] = False (لم تنتهِ العملية بعد).
      • Need[i] <= Work (احتياجات العملية من الموارد أقل من أو تساوي الموارد المتاحة).
    3. إذا تم العثور على عملية:
      • Work = Work + Allocation[i] (تحرير الموارد التي تحتفظ بها العملية).
      • Finish[i] = True (تعليم العملية على أنها منتهية).
      • العودة إلى الخطوة 2.
    4. إذا لم يتم العثور على عملية:
      • إذا كان Finish[i] = True لكل i، فإن النظام في حالة آمنة.
      • إذا كان هناك على الأقل عملية واحدة حيث Finish[i] = False، فإن النظام في حالة غير آمنة، وقد يؤدي إلى جمود.
  3. اتخاذ القرار: بناءً على نتيجة فحص السلامة، تتخذ الخوارزمية قرارًا:
    • إذا كانت الحالة آمنة: يتم تخصيص الموارد المطلوبة للعملية.
    • إذا كانت الحالة غير آمنة: يتم رفض طلب الموارد، ويجب على العملية الانتظار.

مثال توضيحي

لنفترض أن لدينا نظامًا به 5 عمليات (P0، P1، P2، P3، P4) و 3 أنواع من الموارد (A، B، C). في لحظة معينة، تكون حالة النظام على النحو التالي:

Allocation:

| | A | B | C |
|—|—|—|—|
| P0| 0 | 1 | 0 |
| P1| 2 | 0 | 0 |
| P2| 3 | 0 | 2 |
| P3| 2 | 1 | 1 |
| P4| 0 | 0 | 2 |

Max:

| | A | B | C |
|—|—|—|—|
| P0| 7 | 5 | 3 |
| P1| 3 | 2 | 2 |
| P2| 9 | 0 | 2 |
| P3| 2 | 2 | 2 |
| P4| 4 | 3 | 3 |

Available: (3, 3, 2)

Need: (Max – Allocation):

| | A | B | C |
|—|—|—|—|
| P0| 7 | 4 | 3 |
| P1| 1 | 2 | 2 |
| P2| 6 | 0 | 0 |
| P3| 0 | 1 | 1 |
| P4| 4 | 3 | 1 |

لتحديد ما إذا كانت الحالة آمنة، نتبع الخطوات التالية:

  1. Work = Available = (3, 3, 2)
  2. Finish = (False, False, False, False, False)
  3. الخطوة 1: العملية P3 يمكن أن تكمل (Need P3 <= Work)، لذا:
    • Work = (3, 3, 2) + (2, 1, 1) = (5, 4, 3)
    • Finish[3] = True
  4. الخطوة 2: العملية P1 يمكن أن تكمل (Need P1 <= Work)، لذا:
    • Work = (5, 4, 3) + (2, 0, 0) = (7, 4, 3)
    • Finish[1] = True
  5. الخطوة 3: العملية P4 يمكن أن تكمل (Need P4 <= Work)، لذا:
    • Work = (7, 4, 3) + (0, 0, 2) = (7, 4, 5)
    • Finish[4] = True
  6. الخطوة 4: العملية P0 يمكن أن تكمل (Need P0 <= Work)، لذا:
    • Work = (7, 4, 5) + (0, 1, 0) = (7, 5, 5)
    • Finish[0] = True
  7. الخطوة 5: العملية P2 يمكن أن تكمل (Need P2 <= Work)، لذا:
    • Work = (7, 5, 5) + (3, 0, 2) = (10, 5, 7)
    • Finish[2] = True

بما أن جميع العمليات قد انتهت (Finish = [True, True, True, True, True])، فإن النظام في حالة آمنة. هذا يعني أنه يمكن تخصيص الموارد للعمليات.

مزايا وعيوب خوارزمية المصرفي

مثل أي خوارزمية، تتمتع خوارزمية المصرفي بمزايا وعيوب:

المزايا:

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

العيوب:

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

تطبيقات خوارزمية المصرفي

على الرغم من عيوبها، يتم استخدام خوارزمية المصرفي في مجموعة متنوعة من الأنظمة:

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

تحسينات وتعديلات على الخوارزمية

تم اقتراح العديد من التحسينات والتعديلات على خوارزمية المصرفي لتحسين كفاءتها وقدرتها على التكيف:

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

خاتمة

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

المراجع

“`

مقالات مرتبطة