مواضيع عامةمواضيع ومقالات

مقال: تمرين مشكلة عشاء الفلاسفة , للمساعدة على فهم كيفية توزيع الموارد في انظمة التشغيل

تم أرشفة هذا المحتوى


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

أحد أهم النظريات التي تقوم عليها أنظمة التشغيل اليوم هي نظرية حل “مشكلة عشاء الفلاسفة”.

ما هي المشكلة؟

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

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

 

diningphilosophers

أحد الحلول قد يكون الخوارزمية الآتية:

  1. فكر حتى تكون الشوكة التي على يسارك متاحة.
  2. أمسك بالشوكة التي على يسارك.
  3. فكر حتى تكون الشوكة التي على يمينك متاحة.
  4. أمسك بالشوكة التي على يمينك.
  5. أبدأ بالأكل لمدة 10 ثواني.
  6. ضع الشوكة التي في يمينك على الطاولة.
  7. ضع الشوكة التي في يسارك على الطاولة.
  8. أفعل هذا مجددا.

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

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

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

 

هناك العديد من النظريات لحل هذا التحدي، منها الحل الذي قدمه عالم الكمبيوتر الهولندي Dijkstra تعرف عليه من الرابط التالي :
http://www.isecur1ty.org/?p=6573

 

 

محمد مجدي

محمد من مصر، يعشق التكنلوجيا وأمن المعلومات. مختبر اختراق ومطور ويب. تويتر: @mhassan772

مقالات ذات صلة

‫4 تعليقات

  1. جميل جدًا.. في انتظار التالي

    قيمت المقال بنجمة واحدة خطأً.. قصدت ٥.. ولم أستطع التعديل

    المعذرة.. 🙂

  2. these was called Dining philosophers problem we study its in the coolage the solution that i remmber is called Arbitrator solution and its as fallow
    For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty.
    When a philosopher wants to use a set of resources (i.e. eat), he must obtain the forks from his contending neighbors. For all such forks he does not have, he sends a request message.
    When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so.
    After a philosopher is done eating, all his forks become dirty. If another philosopher had previously requested one of the forks, he cleans the fork and sends it.

    you can see the solutions in wiki

    http://en.wikipedia.org/wiki/Dining_philosophers_problem#Solutions

  3. الفكرة في اعطاء اوقات عشوائيه وليست ثابته لكل منهما
    هذا المبدأ موجود في الشبكات exponential back-off

  4. تشكر علي هذا الحل لكن ممكن حل مختصر لهذه العمليه الرجاء الحل الفوري جزاءك الله خير

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

زر الذهاب إلى الأعلى