مسألة عشاء الفلاسفة

رسم يوضح مشكلة الفلاسفة المتناولين الطعام حيث يكون لدى كل فيلسوف وعاء من السباغيتي، ويستطيع الوصول إلى شوكتين.

مسألة عشاء الفلاسفة هي مسألة في علوم الحاسب تُستخدم عادةً في تصميم الخوارزميات المتزامنة لتوضيح أخطاء التزامن وتقنيات حلها.

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

المسألة

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

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

تحليل المسألة

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

الحلول

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

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

• الاستبعاد المتبادل: لا يُمكن لأكثر من فيلسوف استخدام نفس المورد في نفس الوقت.
• الاحتفاظ بالموارد: لا يمكن لأي فيلسوف الاحتفاظ بأحد الموارد في انتظار الوصول إلى المورد الآخر.
• عدم الاستباق: لا يُمكن لأيّ فيلسوف الحصول على المورد المُشترك من زميله مُباشرة.
• الانتظار الدائري: قد ينتظر كل فيلسوف ريثما ينتهي الفيلسوف الذي على يساره من الأكل.

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

حل ديكسترا

يعتمد حل ديكسترا على نفي الاحتفاظ بالموارد؛ حيث يختار الفلاسفة استخدام كلا الموردين معا، أو ينتظرون دون الاحتفاظ بمورد واحد فقط. لتحقيق ذلك، يستخدم حل ديكسترا قفل مُزامنة واحدًا، وسيمافورًا واحدًا لكل فيلسوف، ومتغير حالة واحدًا لكل فيلسوف. يُعتبر هذا الحل أكثر تعقيدًا من حل التسلسل الهرمي للموارد. وفيما يلي تطبيق لحل ديكسترا باستخدام الإصدار الإصدار C++20 من لغة سي++ مع التغييرات التي أجراها عالم الحواسب الأمريكي أندرو تانينباوم:

#include <chrono>
# include <iostream>
# include <mutex>
# include <random>
# include <semaphore>
# include<thread>

constexpr const size_t N = 5;  // number of philosophers (and forks)
enum class State
{
    THINKING = 0,  // philosopher is THINKING
    HUNGRY = 1,    // philosopher is trying to get forks
    EATING = 2,    // philosopher is EATING
};

size_t inline left(size_t i)
{ 
    // number of the left neighbor of philosopher i, for whom both forks are available
    return (i - 1 + N) % N; // N is added for the case when  i - 1 is negative
}

size_t inline right(size_t i)
{ 
    // number of the right neighbor of the philosopher i, for whom both forks are available
    return (i + 1) % N;
}

State state[N]؛  // array to keep track of everyone's both_forks_available state

std::mutex critical_region_mtx;  // mutual exclusion for critical regions for
// (picking up and putting down the forks)
std::mutex output_mtx;  // for synchronized cout (printing THINKING/HUNGRY/EATING status)

// array of binary semaphors, one semaphore per philosopher.
// Acquired semaphore means philosopher i has acquired (blocked) two forks
std::binary_semaphore both_forks_available[N]
{
    std::binary_semaphore{0}, std::binary_semaphore{0},
    std::binary_semaphore{0}, std::binary_semaphore{0},
    std::binary_semaphore{0}
};

size_t my_rand(size_t min, size_t max)
{
    static std::mt19937 rnd(std::time(nullptr));
    return std::uniform_int_distribution<>(min, max)(rnd);
}

void test(size_t i)
// if philosopher i is hungry and both neighbors are not eating then eat
{
    // i: philosopher number, from 0 to N-1
    if (state[i] == State::HUNGRY &&
        state[left(i)] != State::EATING &&
        state[right(i)] != State::EATING)
    {
        state[i] = State::EATING;
        both_forks_available[i].release(); // forks are no longer needed for this eat session
    }
}

void think(size_t i)
{
    size_t duration = my_rand(400, 800);
    {
        std::lock_guard<std::mutex> lk(output_mtx); // critical section for uninterrupted print
        std::cout << i << " is thinking " << duration << "ms\n";
    }
    std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}

void take_forks(size_t i)
{
    {
        std::lock_guard<std::mutex> lk{critical_region_mtx};  // enter critical region
        state[i] = State::HUNGRY;  // record fact that philosopher i is State::HUNGRY
        {
            std::lock_guard<std::mutex> lk(output_mtx); // critical section for uninterrupted print
            std::cout << "\t\t" << i << " is State::HUNGRY\n";
        }
        test(i);                        // try to acquire (a permit for) 2 forks
    }                                   // exit critical region
    both_forks_available[i].acquire();  // block if forks were not acquired
}

void eat(size_t i)
{
    size_t duration = my_rand(400, 800);
    {
        std::lock_guard<std::mutex> lk(output_mtx); // critical section for uninterrupted print
        std::cout << "\t\t\t\t" << i << " is eating " << duration << "ms\n";
    }
    std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}

void put_forks(size_t i)
{
   
    std::lock_guard<std::mutex> lk{critical_region_mtx};    // enter critical region
    state[i] = State::THINKING;  // philosopher has finished State::EATING
    test(left(i));               // see if left neighbor can now eat
    test(right(i));              // see if right neighbor can now eat
                                 // exit critical region by exiting the function
}

void philosopher(size_t i)
{ 
    while (true)
    {                         // repeat forever
        think(i);             // philosopher is State::THINKING
        take_forks(i);        // acquire two forks or block
        eat(i);               // yum-yum, spaghetti
        put_forks(i);         // put both forks back on table and check if neighbors can eat
    }
}

int main() {
    std::cout << "dp_14\n";

    std::jthread t0([&] { philosopher(0); }); // [&] means every variable outside the ensuing lambda
    std::jthread t1([&] { philosopher(1); }); // is captured by reference
    std::jthread t2([&] { philosopher(2); });
    std::jthread t3([&] { philosopher(3); });
    std::jthread t4([&] { philosopher(4); });
}

هكذا يتجنب حل ديكسترا الجمود من خلال الدالة test() واستخدامها في دالة take_forks() ودالة put_forks().

حل التسلسل الهرمي للموارد

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

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

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

يوضح كود المصدر التالي تطبيق حل التسلسل الهرمي للموارد لمشكلة الفلاسفة المتناولين للطعام باستخدام الإصدار C++11 من لغة سي++. في هذا التطبيق تحاكي دالة sleep_for() الوقت المستغرق عادةً مع منطق الأعمال.

# include <iostream>
# include <chrono>
# include <mutex>
# include<thread>
# include <random>
# include <ctime>

using namespace std;

int myrand(int min, int max) {
  static mt19937 rnd(time(nullptr));
  return uniform_int_distribution<>(min,max)(rnd);
}

void philosopher(int ph, mutex& ma, mutex& mb, mutex& mo) {
  for (;;) {  // prevent thread from termination
    int duration = myrand(200, 800);
    {
      // Block { } limits scope of lock
      lock_guard<mutex> gmo(mo);
      cout<<ph<<" thinks "<<duration<<"ms\n";
    }
    this_thread::sleep_for(chrono::milliseconds(duration));
    {
      lock_guard<mutex> gmo(mo);
      cout<<"\t\t"<<ph<<" is hungry\n";
    }
    lock_guard<mutex> gma(ma);
    // sleep_for() Delay before seeking second fork can be added here but should not be required.
    lock_guard<mutex> gmb(mb);
    duration = myrand(200, 800);
    {
      lock_guard<mutex> gmo(mo);
      cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
    }
    this_thread::sleep_for(chrono::milliseconds(duration));
  }
}

int main() {
  cout<<"dining Philosophers C++11 with Resource hierarchy\n";
  mutex m1, m2, m3, m4, m5;   // 5 forks are 5 mutexes
  mutex mo;           // for proper output
  // 5 philosophers are 5 threads
  thread t1([&] {philosopher(1, m1, m2, mo);});
  thread t2([&] {philosopher(2, m2, m3, mo);});
  thread t3([&] {philosopher(3, m3, m4, mo);}); 
  thread t4([&] {philosopher(4, m4, m5, mo);}); 
  thread t5([&] {philosopher(5, m1, m5, mo);});  // Force a resource hierarchy
  t1.join();  // prevent threads from termination
  t2.join();
  t3.join();
  t4.join();
  t5.join();
}

حل المُحكِّم

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

حل الحد من عدد رواد المائدة

تصميم الخوارزمية المتزامنة

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

حل تشاندي/ميسرا

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

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

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

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