مشكلة فلاسفة الطعام

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

• فكر إلا إذا كان الفرع الأيسر متاحاً؛ وعندما يكون كذلك، التقطه؛
• فكّر ملياً إلا إذا كانت الشوكة المناسبة متوفرة؛ وعندما تكون كذلك، التقطها؛
• عند الإمساك بالشوكتين، تناول الطعام لفترة زمنية محددة؛
• ضع الشوكة اليسرى للأسفل؛
• ضع الشوكة اليمنى للأسفل؛
• كرر من البداية.

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

يُعد نقص الموارد ، والاستبعاد المتبادل ، والتعطل الحي أنواعًا أخرى من مشاكل التسلسل والوصول.

يلغي حل ديكسترا مفهوم حيازة الموارد؛ إذ يلتقط الفلاسفة كلا الفرعين أو ينتظرون بشكل ذري، دون أن يحوزوا فرعًا واحدًا فقط خارج القسم الحرج . ولتحقيق ذلك، يستخدم حل ديكسترا قفلًا متبادلًا واحدًا، وإشارة مرور واحدة لكل فيلسوف، ومتغير حالة واحد لكل فيلسوف. هذا الحل أكثر تعقيدًا من حل التسلسل الهرمي للموارد. ^{[ 5 ] [ 4 ]} هذه نسخة C++20 من حل ديكسترا مع تعديلات من أندرو س. تانينباوم .

#include <chrono> #include <iostream> #include <mutex> #include <random> #include <semaphore> #include <thread>constexpr const size_t N = 5 ; // عدد الفلاسفة (والشوك) enum class State { THINKING = 0 , // الفيلسوف يفكر HUNGRY = 1 , // الفيلسوف يحاول الحصول على شوك EATING = 2 , // الفيلسوف يأكل };size_t inline left ( size_t i ) { // رقم الجار الأيسر للفيلسوف i return ( i - 1 + N ) % N ; // تتم إضافة N في حالة كون i - 1 سالبًا }size_t inline right ( size_t i ) { // رقم الجار الأيمن للفيلسوف i return ( i + 1 ) % N ; }State state [ N ]; // مصفوفة لتتبع حالة both_forks_available لكل مستخدمstd :: mutex critical_region_mtx ; // استبعاد متبادل للمناطق الحرجة لـ // (التقاط الشوكات ووضعها) std :: mutex output_mtx ; // لإخراج متزامن (طباعة حالة التفكير/الجوع/الأكل)// مصفوفة من الإشارات الثنائية، إشارة واحدة لكل فيلسوف. // الحصول على كل إشارة يعني أن الفيلسوف i قد عاد من دالة take_forks، أي أنه حصل (حظر) على فرعين. // يبدأ من الحالة 0/خطأ، مما يعني أن كلا الفرعين غير متاحين 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 ) // إذا كان الفيلسوف i جائعًا ولم يكن أي من جاريه يأكل، فسيتم تحرير إشارة الفيلسوف i. // هذا يمنح الفيلسوف i الإذن بالمتابعة بعد السطر الأخير من take_forks { // i: رقم الفيلسوف، من 0 إلى 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 (); // يتم الإعلان عن توفر كلا الشوكتين للفيلسوف i } }void think ( size_t i ) { size_t duration = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( output_mtx ); // قسم حرج للطباعة المتواصلة std :: cout << i << " يفكر " << duration << "مللي ثانية \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 }; // الدخول إلى المنطقة الحرجة state [ i ] = State :: HUNGRY ; // تسجيل حقيقة أن الفيلسوف i هو State::HUNGRY { std :: lock_guard < std :: mutex > lk ( output_mtx ); // القسم الحرج للطباعة المتواصلة std :: cout << " \t\t " << i << " هو State::HUNGRY \n " ; } test ( i ); // محاولة تحرير إشارة الفيلسوف i، أي الحصول على (تصريح لـ) فرعين } // الخروج من المنطقة الحرجة both_forks_available [ i ]. acquire (); // الانتظار (حظر) إذا لم يكن كلا الفرعين متاحين حاليًا }void eat ( size_t i ) { size_t duration = my_rand ( 400 , 800 ); { std :: lock_guard < std :: mutex > lk ( output_mtx ); // قسم حرج للطباعة المتواصلة std :: cout << " \t\t\t\t " << i << " يأكل " << duration << "مللي ثانية \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 }; // الدخول إلى المنطقة الحرجة state [ i ] = State :: THINKING ; // انتهى الفيلسوف State::EATING test ( left ( i )); // محاولة تحرير إشارة الجار الأيسر لهم test ( right ( i )); // محاولة تحرير إشارة الجار الأيمن لهم // الخروج من المنطقة الحرجة بالخروج من الدالة }void philosophy ( size_t i ) { while ( true ) { // كرر إلى ما لا نهاية think ( i ); // فيلسوف هو State::THINKING take_forks ( i ); // احصل على شوكتين أو ستُمنع eat ( i ); // لذيذ، معكرونة put_forks ( i ); // أعد الشوكتين إلى الطاولة وتحقق مما إذا كان بإمكان الجيران الأكل } }int main () { std :: cout << "dp_14 \n " ;std :: jthread t0 ([ & ] { philosophy ( 0 ); }); // [&] تعني كل متغير خارج دالة لامدا التالية std :: jthread t1 ([ & ] { philosophy ( 1 ); }); // يتم التقاطه بالمرجع std :: jthread t2 ([ & ] { philosophy ( 2 ); }); std :: jthread t3 ([ & ] { philosophy ( 3 ); }); std :: jthread t4 ([ & ] { philosophy ( 4 ); }); }

إن الدالة test() واستخدامها في take_forks() و put_forks() يجعلان حل Dijkstra خالياً من حالات الجمود.

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

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

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

الكود المصدري التالي هو تطبيق بلغة C++11 لحل التسلسل الهرمي للموارد لخمسة فلاسفة. تحاكي الدالة sleep_for() الوقت الذي يُقضى عادةً في منطق الأعمال . ^{[ 6 ]}

بالنسبة لـ GCC: قم بالتجميع باستخدام

g++ src.cpp -std = c++11 -pthread 

#include <iostream> #include <chrono> #include <mutex> #include <thread> #include <random> #include <ctime>باستخدام مساحة الاسم std ؛دالة ` myrand` تأخذ وسيطين من نوع ` int` هما ` min` و` max` ، وتُعيد توزيعًا منتظمًا للأعداد الصحيحة باستخدام الدالة ` rnd` .​​​​void philosophy ( int ph , mutex & ma , mutex & mb , mutex & mo ) { for (;;) { // منع إنهاء الخيط int duration = myrand ( 200 , 800 ); { // Block { } يحدد نطاق القفل lock_guard < mutex > gmo ( mo ); cout << ph << " يفكر " << duration << "مللي ثانية \n " ; } this_thread :: sleep_for ( chrono :: milliseconds ( duration )); { lock_guard < mutex > gmo ( mo ); cout << " \t\t " << ph << " جائع \n " ; } lock_guard < mutex > gma ( ma ); // sleep_for() يمكن إضافة تأخير قبل البحث عن التفرع الثاني هنا ولكن لا ينبغي أن يكون ذلك مطلوبًا. 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 filters are 5 threads thread t1 ([ & ] { philosophy ( 1 , m1 , m2 , mo );}); thread t2 ([ & ] { philosophy ( 2 , m2 , m3 , mo );}); thread t3 ([ & ] { philosophy ( 3 , m3 , m4 , mo );}); thread t4 ([ & ] { philosophy ( 4 , m4 , m5 , mo );}); thread t5 ([ & ] { philosophy ( 5 , m1 , m5 , mo );}); // Force a resource hierarchy t1 . join ( ); // منع إنهاء الخيوط t2.join ( ); t3.join ( ) ; t4.join ( ) ; t5.join () ; }

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

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

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

في عام ١٩٨٤، اقترح ك. ماني تشاندي وج . ميسرا ^{[ ٨ ]} حلاً مختلفاً لمسألة الفلاسفة المتناولين للطعام، يسمح لعددٍ عشوائي من الوكلاء (مرقمة من _P١ إلى P ن ₎ بالتنافس على عددٍ عشوائي من الموارد، على عكس حل ديكسترا. يتميز هذا الحل بأنه موزع بالكامل ولا يتطلب سلطة مركزية بعد التهيئة. مع ذلك، فإنه يخالف شرط "عدم تواصل الفلاسفة فيما بينهم" (بسبب رسائل الطلب).

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

كما يسمح هذا الحل بدرجة كبيرة من التزامن وسيحل مشكلة كبيرة بشكل تعسفي.

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

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