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

📅 آخر تحديث: ١٨ يوليو ٢٠٢٦
✍️ نُشر في: ١٨ يوليو ٢٠٢٦
الموسوعة الحرة

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

طُوِّرت هذه الخوارزمية خلال عملية تصميم نظام التشغيل THE، ووُصفت لأول مرة (باللغة الهولندية ) في EWD108. [ 1 ] عند دخول عملية جديدة إلى النظام، يجب عليها تحديد الحد الأقصى لعدد مثيلات كل نوع من أنواع الموارد التي يُمكنها استخدامها؛ ومن الواضح أن هذا العدد لا يجوز أن يتجاوز إجمالي عدد الموارد في النظام. كذلك، عندما تحصل العملية على جميع الموارد المطلوبة، يجب عليها إعادتها خلال فترة زمنية محددة.

موارد

لكي تعمل خوارزمية المصرفي، فهي تحتاج إلى معرفة ثلاثة أشياء:

  • ما مقدار كل مورد يمكن أن تطلبه كل عملية على الأرجح ("الحد الأقصى")
  • ما مقدار كل مورد الذي تحتفظ به كل عملية حاليًا ("المخصص")
  • ما مقدار كل مورد متاح حاليًا في النظام ("متاح")

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

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

يُستمد اسم خوارزمية المصرفي من إمكانية استخدامها في النظام المصرفي لضمان عدم نفاد موارد البنك، إذ لا يُخصص البنك أمواله بطريقة تُعجزه عن تلبية احتياجات جميع عملائه. [ 2 ] باستخدام خوارزمية المصرفي، يضمن البنك عدم خروجه عن حالة الأمان عند طلب العملاء للأموال. فإذا لم يُؤدِّ طلب العميل إلى خروج البنك عن حالة الأمان، يُخصص المبلغ، وإلا فعلى العميل الانتظار حتى يُودع عميل آخر المبلغ الكافي.

هياكل البيانات الأساسية التي يجب الحفاظ عليها لتنفيذ خوارزمية المصرفي:

لنفترض أن n هو عدد العمليات في النظام و m هو عدد أنواع الموارد. عندئذٍ نحتاج إلى هياكل البيانات التالية:

  • المتاح: يشير متجه بطول m إلى عدد الموارد المتاحة من كل نوع. إذا كان Available[j] = k، فهذا يعني وجود k من الموارد من النوع R j متاحة.
  • الحد الأقصى: تحدد مصفوفة n × m الحد الأقصى للطلب لكل عملية. إذا كان Max[i,j] = k، فيمكن للعملية P i أن تطلب على الأكثر k من مثيلات نوع المورد R j .
  • التخصيص: تحدد مصفوفة n × m عدد الموارد من كل نوع المخصصة حاليًا لكل عملية. إذا كان Allocation[i,j] = k، فإن العملية P i مخصصة حاليًا k من موارد النوع R j .
  • الحاجة: تشير مصفوفة n × m إلى احتياجات الموارد المتبقية لكل عملية. إذا كانت Need[i,j] = k، فقد تحتاج العملية P i إلى k من مثيلات نوع المورد R j لإكمال المهمة.

ملاحظة: Need[i,j] = Max[i,j] - Allocation[i,j]. n=ma.

مثال

موارد النظام الكلية
أبجد
6576
موارد النظام المتاحة
أبجد
3112
العمليات (الموارد المخصصة حاليًا)
أبجد
P11221
P21033
P31210
العمليات (بأقصى قدر من الموارد)
أبجد
P13322
P21234
P31350
الاحتياج = الحد الأقصى للموارد - الموارد المخصصة حاليًا
العمليات (الموارد التي قد تكون مطلوبة)
أبجد
P12101
P20201
P30140

حالات آمنة وحالات غير آمنة

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

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

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

  1. يحتاج P1 إلى 2 من الموارد A و1 من الموارد B و1 من الموارد D الإضافية، لتحقيق أقصى إمكاناته
    • [المورد المتاح: ⟨ 3 1 1 2 ⟩ − ⟨ 2 1 0 1 ⟩ = ⟨ 1 0 1 1 ⟩ ]
    • لا يزال النظام يحتوي الآن على مورد واحد من النوع A، ولا يوجد مورد من النوع B، ومورد واحد من النوع C ومورد واحد من النوع D متاحين.
  2. ينتهي البرنامج P1، ويعيد 3 موارد من النوع A، و3 موارد من النوع B، وموارد من النوع C، وموارد من النوع D إلى النظام.
    • [المورد المتاح: ⟨ 1 0 1 1 ⟩ + ⟨ 3 3 2 2 ⟩ = ⟨ 4 3 3 3 ⟩ ]
    • يتوفر في النظام الآن 4 موارد من النوع أ، و3 موارد من النوع ب، و3 موارد من النوع ج، و3 موارد من النوع د
  3. يحصل اللاعب P2 على موردين إضافيين من النوع B ومورد إضافي واحد من النوع D، ثم ينهي العملية ويعيد جميع موارده.
    • [المورد المتاح: ⟨ 4 3 3 3 ⟩ − ⟨ 0 2 0 1 ⟩ + ⟨ 1 2 3 4 ⟩ = ⟨ 5 3 6 6 ⟩ ]
    • يحتوي النظام الآن على 5 موارد من النوع أ، و3 موارد من النوع ب، و6 موارد من النوع ج، و6 موارد من النوع د.
  4. يستحوذ P3 على مورد واحد من النوع B وأربعة موارد من النوع C ثم ينهي العملية.
    • [المورد المتاح: ⟨ 5 3 6 6 ⟩ − ⟨ 0 1 4 0 ⟩ + ⟨ 1 3 5 0 ⟩ = ⟨ 6 5 7 6 ⟩ ]
    • يحتوي النظام الآن على جميع الموارد: 6 أ، 5 ب، 7 ج، و6 د
  5. بما أن جميع العمليات قد تمكنت من الإنهاء، فإن هذه الحالة آمنة

كمثال على حالة غير آمنة، فكر فيما سيحدث إذا كانت العملية 2 تحتفظ بوحدة واحدة من المورد B في البداية.

الطلبات

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

  1. هل يمكن الموافقة على الطلب؟
    • وإلا، فإن الطلب مستحيل ويجب إما رفضه أو وضعه على قائمة الانتظار
  2. افترض أن الطلب قد تمت الموافقة عليه
  3. هل الولاية الجديدة آمنة؟
    • إذا كان الأمر كذلك، فامنح الطلب
    • وإلا، فإما أن ترفض الطلب أو تضعه على قائمة الانتظار

إن قرار النظام برفض أو تأجيل طلب مستحيل أو غير آمن هو قرار خاص بنظام التشغيل.

مثال

انطلاقاً من نفس الحالة التي بدأ بها المثال السابق، افترض أن العملية 1 تطلب وحدتين من المورد C.

  1. لا يتوفر ما يكفي من الموارد (ج) لتلبية الطلب
  2. تم رفض الطلب

من ناحية أخرى، افترض أن العملية 3 تطلب وحدة واحدة من المورد C.

  1. تتوفر موارد كافية لتلبية الطلب
  2. بافتراض الموافقة على الطلب
    • ستكون الحالة الجديدة للنظام كالتالي:
 موارد النظام المتاحة ABCD مجاني 3 1 0 2
 العمليات (الموارد المخصصة حاليًا): ABCD P1 1 2 2 1 P2 1 0 3 3 P3 1 2 2 0
 العمليات (بأقصى قدر من الموارد): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
  1. حدد ما إذا كانت هذه الحالة الجديدة آمنة
    1. يمكن لـ P1 الحصول على موردين من النوع A ومورد واحد من النوع B ومورد واحد من النوع D وإنهاء العملية
    2. بعد ذلك، يمكن لـ P2 الحصول على موردين من النوع B ومورد واحد من النوع D وإنهاء المهمة
    3. وأخيرًا، يمكن لـ P3 الحصول على مورد واحد من النوع B وثلاثة موارد من النوع C وإنهاء المهمة
    4. لذلك، فإن هذه الدولة الجديدة آمنة.
  2. بما أن الولاية الجديدة آمنة، فامنح الطلب

مثال أخير: انطلاقاً من الحالة التي بدأنا منها، افترض أن العملية 2 تطلب وحدة واحدة من المورد B.

  1. توجد موارد كافية
  2. بافتراض الموافقة على الطلب، ستكون الحالة الجديدة كالتالي:
 موارد النظام المتاحة: ABCD مجاناً 3 0 1 2
 العمليات (الموارد المخصصة حاليًا): ABCD P1 1 2 5 1 P2 1 1 3 3 P3 1 2 1 0
 العمليات (بأقصى قدر من الموارد): ABCD P1 3 3 2 2 P2 1 2 3 4 P3 1 3 5 0
  1. هل هذه الحالة آمنة؟ بافتراض أن P1 و P2 و P3 يطلبون المزيد من الموارد B و C.
    • لا يستطيع P1 الحصول على موارد B كافية
    • لا يستطيع P2 الحصول على موارد B كافية
    • لا يستطيع P3 الحصول على موارد B كافية
    • لا يمكن لأي عملية الحصول على موارد كافية لإنهاء عملها، لذا فإن هذه الحالة غير آمنة.
  2. بما أن الولاية غير آمنة، ارفض الطلب
استيراد numpy كـ npn_processes = int ( input ( "عدد العمليات؟ " )) n_resources = int ( input ( "عدد الموارد؟ " ))available_resources = [ int ( x ) for x in input ( "Claim vector? " ) . split ( " " )]currently_allocated = np.array ([ [ int ( x ) for x in input ( f "Currently allocation for process { i + 1 } ? " ) .split ( " " ) ] for i in range ( n_processes ) ] )max_demand = np.array ([ [ int ( x ) for x in input ( f "Maximum demand from process { i + 1 } ? " ) .split ( " " )] for i in range ( n_processes ) ] )إجمالي الموارد المتاحة = الموارد المتاحة - مجموع الموارد المخصصة حاليًا ، المحور = 0 العمليات الجارية = مصفوفة تحتوي على عدد العمليات ( عددها 1 ) # مصفوفة تحتوي على عدد العمليات (عددها 1 ) للإشارة إلى ما إذا كانت العملية قيد التشغيل أم لابينما np.count_nonzero ( running ) > 0 : at_least_one_allocated = False for p in range ( n_processes ): if running [ p ] : if all ( i >= 0 for i in total_available - ( max_demand [ p ] - currently_allocated [ p ] )): at_least_one_allocated = True print ( f " { p } is running" ) running [ p ] = 0 total_available += currently_allocated [ p ] if not at_least_one_allocated : print ( "Unsafe" ) break # exit else : print ( "Safe" )

القيود

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

مراجع

  1. ^ Dijkstra، Edsger W. خوارزمية ter voorkoming van de dodelijke omarming (EWD-108) (PDF) . أرشيف إي دبليو ديكسترا. مركز التاريخ الأمريكي، جامعة تكساس في أوستن .( نص مكتوب ) (باللغة الهولندية؛ خوارزمية للوقاية من العناق المميت )
  2. ↑ سيلبرشاتز، جالفين، وجاجن (2013). مفاهيم أنظمة التشغيل، الطبعة التاسعة . وايلي. ص 330. ISBN  978-1-118-06333-0.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

للمزيد من القراءة