مسألة عشاء الفلاسفة
المحتويات
- thread t4([&] {philosopher(4, m4, m5, mo);});
- {
- {
- }
- {
- {
- }
- } // exit critical region
- تحليل المسألة
- {
- state[left(i)] != State::EATING &&
- {
- }
- حل المُحكِّم
- حل تشاندي/ميسرا
- }
- الحلول
- std::jthread t4([&] { philosopher(4); });
- }
- int main {
- حل الحد من عدد رواد المائدة
- {
- state[i] = State::EATING;
- حل التسلسل الهرمي للموارد
- {
- # include
- المسألة
- {
- {
- };
- THINKING = 0, // philosopher is THINKING
- lock_guard gma(ma);
- }
- }
- };
- }
- std::cout << "dp_14\n";
- }
- حل ديكسترا
- }
- eat(i); // yum-yum, spaghetti
- }
- }

على سبيل التعريف، مسألة عشاء الفلاسفة هي مسألة في علوم الحاسب تُستعمل عادةً في تصميم الخوارزميات المتزامنة لتوضيح أخطاء التزامن وتقنيات حلها. وفيما يلي تفاصيل أوسع عن ذلك.
وفي هذا الصدد، كان عالم الحاسوب الهولندي إدسجر ديكسترا هو من صاغ هذه المسألة لأول مرة في عام 1965 عندما قدمها إلى طلابه في أحد الاختبارات كتمرين يظهر تنافس أجهزة الحواسب على الوصول إلى ملحقات مُحركات الأشرطة، ثم أعاد عالم الحاسوب البريطاني توني هور صياغة المسألة وقدمها في شكلها الحالي فيما بعد بوقت قصير.
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;
- }
{
في هذا الإطار، std::lock_guard lk{critical_region_mtx}; // enter critical region
وعلى صعيد آخر، state[i] = State::HUNGRY; // record fact that philosopher i is State::HUNGRY
{
وفي هذا السياق، std::lock_guard lk(output_mtx); // critical section for uninterrupted print
std::cout << i << " is thinking " << duration << "ms\n";
}
- void think(size_t i)
- {
- size_t duration = my_rand(400, 800);
{
من جهة ثانية، std::lock_guard lk(output_mtx); // critical section for uninterrupted print
std::cout << "\t\t" << i << " is State::HUNGRY\n";
{
return (i + 1) % N;
وعلى صعيد آخر، // number of the right neighbor of the philosopher i, for whom both forks are available
}
- void philosopher(int ph, mutex& ma, mutex& mb, mutex& mo) {
- for (;;) { // prevent thread from termination
- int duration = myrand(200, 800);
} // exit critical region
وفي هذا السياق، both_forks_available[i].acquire; // block if forks were not acquired
تحليل المسألة
من جهة ثانية، صُممت مسألة الفلاسفة المتناولين للطعام لتوضيح تحديات تجنب الجمود، وهي حالة نظامية لا يمكن فيها إحراز أي تقدم. وإذا حاولنا كتابة برنامج مترابط لمحاكاة سلوك الفلاسفة سوف نُلاحظ أن الفلاسفة الخمسة منخرطين في دورة مغلقة تتألف من المراحل التالية (تفكير - التقاط أعواد الطعام - تناول الطعام - وضع الأعواد على جانبي الطبق). وتكمن المشكلة في أن كل فيلسوف لا يمكنه استخدام أعواد الطعام إلا كان زميليه على كلا الجانبين لا يستعملانها.
{
وفي هذا الصدد، std::cout << "\t\t\t\t" << i << " is eating " << duration << "ms\n";
علاوةً على ذلك، std::lock_guard lk(output_mtx); // critical section for uninterrupted print
state[left(i)] != State::EATING &&
state[right(i)] != State::EATING)
{
{
- // Block { } limits scope of lock
- lock_guard gmo(mo);
- cout<<ph<<" thinks "<<duration<<"ms\n";
- }
- this_thread::sleep_for(chrono::milliseconds(duration));
- {
- lock_guard gmo(mo);
- cout<<"\t\t"<<ph<<" is hungry\n";
- }
}
من جهة ثانية، std::mutex output_mtx; // for synchronized cout (printing THINKING/HUNGRY/EATING status)
- 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)
- // 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}
حل المُحكِّم
وفي السياق ذاته، هناك نهج ثالث للحل يعتمد على ضمان قدرة الفيلسوف على التقاط كلا من عودي الطعام في نفس الوقت أو عدم التقاط أيٍّ منهما، وذلك بإدخال مُحكِّم ليحل محل الانتظار الدائري، مثل النادل. لالتقاط عودي الطعام، يجب على الفيلسوف أن يطلب إذن النادل. ولا يمنح النادل الإذن إلا لفيلسوف واحد فقط في كل مرة حتى يلتقط الفيلسوف عودي طعامه. يُسمح دائمًا بوضع الأعواد على المائدة. يمكن استخدام النادل كمفتاح مزامنة. إلى جانب إدخال كيان مركزي جديد (النادل)، يمكن أن يؤدي هذا النهج إلى تقليل التوازي: إذا كان الفيلسوف يأكل وطلب أحد جيرانه أعواد الطعام التي يستعملها، فيجب على جميع الفلاسفة الآخرين الانتظار حتى يتم تلبية هذا الطلب، حتى لو كانت الأعواد لا تزال متاحة لهم.
حل تشاندي/ميسرا
وفي هذا السياق، اقترح العالمان الأمريكيان ك. ماني تشاندي وجاياديف ميسرا في سنة 1984 حلاً مختلفًا لمشكلة الفلاسفة المتناولين للطعام. يسمح هذا الحل لوكلاء عشوائيين مرقمين بالتنافس على عدد عشوائي من الموارد، على عكس حل ديكسترا. كما أنه موزع بالكامل ولا يتطلب سلطة مركزية بعد التهيئة. ومع ذلك، فإن هذا الحل ينتهك شرط عدم تواصل الفلاسفة مع بعضهم البعض (بسبب رسائل الطلب).
علاوةً على ذلك، يتطلب هذا الحل أن تُنشئ لكل زوج من الفلاسفة يتنافسان على مورد عود طعام، ثم تمنح عود الطعام للفيلسوف ذي الرقم الأقل. يمكن أن يكون كل عود طعام إما متسخًا أو نظيفًا، ولكن في البداية، تكون جميع أعواد الطعام متسخة. وعندما يرغب فيلسوف في استخدام مجموعة من الموارد (مثل تناول الطعام)، سوف يتعين عليه الحصول على أعواد الطعام من جيرانه المتنافسين بأن يرسل رسالة طلب لجميع أعواد الطعام التي لا يملكها. عندما يتلقى أي فيلسوف يحمل عود طعام رسالة طلب، فعليه أن يحتفظ بالعود إذا كان نظيفا، أو يتخلى عنه إذا كان متسخا. فإذا قرر الفيلسوف إرسال عود الطعام لزميله، يجب علىه أن ينظفه أولا. بمجرد أن ينتهي الفيلسوف من الأكل، تصبح جميع أعواد طعامه متسخة. وإذا كان هناك فيلسوف آخر قد طلب الحصول على أحد الأعواد بالفعل، فإن الفيلسوف الذي انتهى لتوه من الأكل ينظف الأعواد ويرسلها.
علاوةً على ذلك، يسمح هذا الحل كذلك بدرجة كبيرة من التزامن، ويحل مشكلة كبيرة بشكل عشوائي. كما يحل مشكلة المجاعة. تعمل تسميات "نظيفة/متسخة" كوسيلة لإعطاء الأفضلية للعمليات الأكثر احتياجا (الفلاسفة الأكثر جوعا)، وتأجيل العمليات الأقل احتياجا (الفلاسفة الذين انتهوا من الطعام للتو). يمكن مقارنة هذا الحل بحل مشابه لا يُسمح فيه للفلاسفة بتناول الطعام مرتين متتاليتين دون السماح للآخرين باستخدام أعواد الطعام بينهما. غير أن حل تشاندي وميسرا أكثر مرونة.
ومن جهة أخرى، اشتق تشاندي وميسرا في تحليلهما نظامًا لمستويات التفضيل من توزيع أعواد الطعام وحالاتها "نظيفة/متسخة". وأظهرا أن هذا النظام قد يصف رسمًا بيانيًا غير دوري موجه، وإذا كان الأمر كذلك، فإن العمليات في بروتوكولهما لا يمكنها تحويل هذا الرسم البياني إلى رسم بياني دوري، ويضمن هذا عدم حدوث الجمود عن طريق إلغاء الانتظار الدائري. ومع ذلك، إذا تمت تهيئة النظام إلى حالة متماثلة تمامًا، كما هو الحال مع جميع الفلاسفة الذين يحملون أعوادهم الموجودة على الجهة اليسرى، فإن الرسم البياني يكون دوريًا في البداية، ولا يمكن لحلهما منع الجمود. إن تهيئة النظام بحيث يكون للفلاسفة ذوي الأرقام المنخفضة أعواد طعام متسخة يضمن أن يكون الرسم البياني غير دوري في البداية.
}
{
void take_forks(size_t i)
الحلول
ومن ناحية أخرى، عدم الاستباق: لا يُمكن لأيّ فيلسوف الحصول على المورد المُشترك من زميله مُباشرة.
ومن جهة أخرى، عمليًا، يمكن أن يُعطي نفي الاستبعاد المتبادل أو عدم الاستباق حلاً صحيحًا، غير أن أغلب المعالجات النظرية تفترض أن هذه الافتراضات غير قابلة للتفاوض، ويمكن بدلا منها نفي الاحتفاظ بالموارد أو الانتظار الدائري (غالبًا كليهما).
من جانب آخر، يرتكز الحل السابق على أربعة شروط لا بد من نفي أحدها على الأقل لتفادي حالة الجمود، وهي:
من جانب آخر، يُمكن النظر إلى أعواد الطعام باعتبارها موردًا مُشتركا بين كل اثنين من الفلاسفة. ولحل هذه المشكلة يُمكن جعل كل عود طعام (مورد مُشترك) محميًا بقفلي المزامنة المرتبطين بالأعواد على يمين ويسار طبقه، أيّ أن كُل فيلسوف يجب أن يكون لديه إمكانية الوصول إلى قفلين للمزامنة، وقبل أن يأكل يجب عليه التحقق ممّا إذا كانت أعواد الطعام على جانبي الطبق مُتاحة أم لا، وإن كانت مُتاحة عليه أن يلتقط هذه الأعواد وبعدها يقوم بقفل العود الأيمن وقفل العود الأيسر، ثُم يبدأ في الأكل، وبعد أن ينتهي يقوم بفك الأقفال وإعادة الأعواد إلى وضعها السابق، ثُم يفكر بينما يبدأ زميله في التقاط الأعواد، ثُم القفل، ثم الأكل، ثم فك القفل، ثم الوضع، ثم التفكير، وهكذا دواليك.
كذلك، الاحتفاظ بالموارد: لا يمكن لأي فيلسوف الاحتفاظ بأحد الموارد في انتظار الوصول إلى المورد الآخر.
وفي السياق ذاته، الانتظار الدائري: قد ينتظر كل فيلسوف ريثما ينتهي الفيلسوف الذي على يساره من الأكل.
ومن ناحية أخرى، الاستبعاد المتبادل: لا يُمكن لأكثر من فيلسوف استخدام نفس المورد في نفس الوقت.
std::jthread t4([&] { philosopher(4); });
علاوةً على ذلك، }هكذا يتجنب حل ديكسترا الجمود من خلال الدالة test واستخدامها في دالة take_forks ودالة put_forks.
}
وفي هذا الصدد، std::this_thread::sleep_for(std::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);});
حل الحد من عدد رواد المائدة
وفي هذا السياق، قدّم عالم الحاسوب الأمريكي ويليام ستالينغز حلاً للمسألة يقضي بالسماح لعدد محدود من الفلاسفة بالجلوس على المائدة في نفس الوقت بحد أقصى (ن-1) حيث ن هو إجمالي عدد وحدات العمل (الفلاسفة). هكذا سيتعين على الفيلسوف الأخير الانتظار (مثلًا، باستخدام إشارة) حتى ينتهي أحدهم من تناول الطعام قبل أن يتمكن من الجلوس وطلب الوصول إلى أي عود طعام. هذا يُلغي الانتظار الدائري، ويضمن إمكانية حصول فيلسوف واحد على الأقل على كلا العودين دائمًا، مما يسمح للنظام بالتقدم.
{
- std::lock_guard 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
state[i] = State::EATING;
إضافةً إلى ذلك، both_forks_available[i].release; // forks are no longer needed for this eat session
}
حل التسلسل الهرمي للموارد
في هذا الإطار، كذلك يُعتبر حل التسلسل الهرمي للموارد حلًا غير عادل. إذا كان الفيلسوف رقم 1 بطيئًا في تناول عود الطعام، وإذا كان الفيلسوف رقم 2 سريع التفكير، وسريع في التقاط أعواد الطعام، فلن يتمكن الفيلسوف رقم 1 أبدًا من التقاط أعواد طعامه. يجب أن يضمن الحل العادل أن كل فيلسوف سيتناول عود الطعام في النهاية، وأنه لن يموت جوعًا بغض النظر عن مدى بطء حركته مقارنةً بالآخرين.
من جانب آخر، يوضح كود المصدر التالي تطبيق حل التسلسل الهرمي للموارد لمشكلة الفلاسفة المتناولين للطعام باستخدام الإصدار C++11 من لغة سي++. في هذا التطبيق تحاكي دالة sleep_for الوقت المستغرق عادةً مع منطق الأعمال.# include
- # include
- # include
- # include
- # include
- # include
- using namespace std;
- int myrand(int min, int max) {
- static mt19937 rnd(time(nullptr));
- return uniform_int_distribution(min,max)(rnd);
إضافةً إلى ذلك، مع أن حل التسلسل الهرمي للموارد يتجنب الجمود، إلا أنه ليس عمليًا دائمًا، خاصةً عندما لا تكون قائمة الموارد المطلوبة معروفة تمامًا مسبقًا. مثلًا، إذا كانت وحدة عمل تحتفظ بالموارد 3 و5، ثم حددت حاجتها إلى المورد 2، فيجب عليها أولا تحرير المورد رقم 5، ثم تحرير المورد رقم 3 قبل أن تتمكن من الحصول على المورد رقم 2، ثم يجب عليها من جديد الحصول على المورد رقم 3 والمورد رقم 5 بنفس الترتيب. في هذه الحالة لا تستطيع برامج الحاسوب التي تصل إلى أعداد كبيرة من سجلات قواعد البيانات العمل بكفاءة إذا طُلب منها تحرير جميع السجلات ذات الرقم الأعلى قبل الوصول إلى سجل جديد، مما يجعل هذه الطريقة غير عملية لهذا الغرض.
من جانب آخر، يُلغي هذا الحل الانتظار الدائري بتعيين ترتيب جزئي للموارد، والمتمثلة في أعواد الطعام في هذه الحالة، ويُرسي قاعدةً تقضي بطلب جميع الموارد بالترتيب، وعدم استخدام أيّ وحدة عمل واحدة (فيلسوف) لأي موردَين غير مرتبطَين بالترتيب في نفس الوقت. في هذه الحالة، تُرقّم الموارد (أعواد الطعام) من 1 إلى 5، وستختار كل وحدة عمل (فيلسوف) عود الطعام الأقل رقمًا أولًا، ثم العود الأعلى رقمًا، من بين العودين اللذين يُخطط لاستخدامهما. لا يُهمّ ترتيب وضع كل فيلسوف لأعواد الطعام. في هذه الحالة، إذا اختار أربعة من الفلاسفة الخمسة أعوادهم الأقل رقمًا في وقت واحد، فلن يبقى على الطاولة سوى عود الطعام الأعلى رقمًا، وبالتالي لن يتمكن الفيلسوف الخامس من اختيار أي عود طعام. علاوة على ذلك، لن يتمكن سوى فيلسوف واحد من الوصول إلى عود الطعام ذو الرقم الأعلى، وهو ما يعني أنه سيتمكن من تناول الطعام باستخدام عودي طعام. يمكن تصور هذا بديهيًا كفيلسوف "أعسر" على المائدة، والذي - على عكس جميع الفلاسفة الآخرين - سوف يلتقط العود الذي على يساره أولاً.
{
// i: philosopher number, from 0 to N-1
if (state[i] == State::HUNGRY &&
# include
- constexpr const size_t N = 5; // number of philosophers (and forks)
- enum class State
- {
المسألة
كذلك، افترض ديكسترا أن هناك خمسة فلاسفة يقضون حياتهم في التفكير والتأمل، ثم تخيل أنهم يجلسون داخل غرفة الطعام، حيث يلتفون حول مائدة دائرية عليها خمسة أطباق من الاسباغيتي، والتي لا يُمكن تناولها إلى باستخدام شوكتين معًا في نفس الوقت أو زوج من أعواد الطعام، بينما لا يوجد على المائدة سوى خمسة شوكات أو أعواد طعام فقط، أي أنّ هناك شوكة واحدة بين كُلّ طبقين. يُفكر كل فيلسوف. وعندما يشعر بالجوع، فعليه أن يتناول الطعام باستخدام الشوكتين المحيطتين بطبقه. وإذا تمكن الفيلسوف من التقاط كلا الشوكتين، فهذا يعني إنه سيأكل لفترة من الوقت، وسيبقى كل من الفيلسوف الذي يجلس على يمينه والفيلسوف الذي يجلس على يساره يفكران دون أن يأكلا، حتى ينتهي هو من تناول طعامه ثُم يعيد الشوكتين إلى موضعهما، ويبدأ في التفكير.
كذلك، تكمن المُعضلة في كيفية تصميم نظام خوارزمية متزامنة تسمح لكل فيلسوف بأن يُبادل بين عملية التفكير وعملية الأكل كي لا يموت أي فيلسوف من الجوع، مع افتراض أنه لا يمكن لأي فيلسوف أن يعرف متى قد يرغب الآخرون في الأكل أو التفكير (وهي مشكلة نقص معلومات).
{
- while (true)
- { // repeat forever
- think(i); // philosopher is State::THINKING
- take_forks(i); // acquire two forks or block
{
وفي السياق ذاته، // 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 my_rand(size_t min, size_t max)
- {
- static std::mt19937 rnd(std::time(nullptr));
- return std::uniform_int_distribution(min, max)(rnd);
THINKING = 0, // philosopher is THINKING
EATING = 2, // philosopher is EATING
HUNGRY = 1, // philosopher is trying to get forks
lock_guard gma(ma);
- lock_guard gmb(mb);
- duration = myrand(200, 800);
- {
- lock_guard gmo(mo);
- cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
- }
- this_thread::sleep_for(chrono::milliseconds(duration));
- }
- }
علاوةً على ذلك، // sleep_for Delay before seeking second fork can be added here but should not be required.
}
- void eat(size_t i)
- {
- size_t duration = my_rand(400, 800);
}
test(i); // try to acquire (a permit for) 2 forks
};
size_t inline left(size_t i)
}
void put_forks(size_t i)
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::this_thread::sleep_for(std::chrono::milliseconds(duration));
حل ديكسترا
علاوةً على ذلك، يعتمد حل ديكسترا على نفي الاحتفاظ بالموارد؛ حيث يختار الفلاسفة استخدام كلا الموردين معا، أو ينتظرون دون الاحتفاظ بمورد واحد فقط. لتحقيق ذلك، يستعمل حل ديكسترا قفل مُزامنة واحدًا، وسيمافورًا واحدًا لكل فيلسوف، ومتغير حالة واحدًا لكل فيلسوف. يُعتبر هذا الحل أكثر تعقيدًا من حل التسلسل الهرمي للموارد. وفيما يلي تطبيق لحل ديكسترا باستخدام الإصدار الإصدار C++20 من لغة سي++ مع التغييرات التي أجراها عالم الحواسب الأمريكي أندرو تانينباوم:#include
- # include
- # include
- # include
- # include
}
void philosopher(size_t i)
eat(i); // yum-yum, spaghetti
- put_forks(i); // put both forks back on table and check if neighbors can eat
- }
- }
- int main {
}
void test(size_t i)
ومن جهة أخرى، // if philosopher i is hungry and both neighbors are not eating then eat
}
size_t inline right(size_t i)
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟