TechCodeview

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

يوضح فيلسوف تناول الطعام فئة كبيرة من مشكلات التحكم في التزامن، ومن ثم فهي مشكلة مزامنة كلاسيكية.

خمسة فلاسفة يجلسون حول الطاولة

مشكلة فلاسفة الطعام - دعونا نفهم مشكلة فلاسفة تناول الطعام من خلال الكود أدناه، وقد استخدمنا الشكل 1 كمرجع لنجعلك تفهم المشكلة تمامًا. يتم تمثيل الفلاسفة الخمسة على أنهم P0، P1، P2، P3، وP4 وخمس عيدان بواسطة C0، C1، C2، C3، وC4.

 Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } 

دعونا نناقش الكود أعلاه:

لنفترض أن الفيلسوف P0 يريد أن يأكل، فسوف يدخل في وظيفة Philosopher()، وينفذ take_chopstick[i]; من خلال القيام بذلك فإنه يحمل C0 عود بعد ذلك يتم تنفيذه take_chopstick[ (i+1) % 5]; من خلال القيام بذلك فإنه يحمل عيدان C1 ( بما أن i =0، إذن (0 + 1) % 5 = 1)

وبالمثل لنفترض الآن أن الفيلسوف P1 يريد أن يأكل، فسوف يدخل في وظيفة Philosopher()، وينفذ take_chopstick[i]; من خلال القيام بذلك فإنه يحمل عيدان C1 بعد ذلك يتم تنفيذه take_chopstick[ (i+1) % 5]; من خلال القيام بذلك فإنه يحمل عود C2 ( بما أن i =1، إذن (1 + 1) % 5 = 2)

لكن عمليا Chopstick C1 غير متوفر لأنه تم أخذه بالفعل من قبل الفيلسوف P0، وبالتالي فإن الكود أعلاه يولد مشاكل وينتج حالة السباق.

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

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

الإشارة: الإشارة هي متغير عدد صحيح في S، وبصرف النظر عن التهيئة يتم الوصول إليها من خلال عمليتين ذريتين قياسيتين فقط - الانتظار والإشارة، وتعريفاتها كما يلي:

 1. wait( S ) { while( S <= 0) ; s--; } 2. signal( s ) { s++; < pre> <p>From the above definitions of wait, it is clear that if the value of S <= 0 then it will enter into an infinite loop(because of the semicolon; after while loop). whereas job signal is to increment value s.< p> <p>The structure of the chopstick is an array of a semaphore which is represented as shown below -</p> <pre> semaphore C[5]; </pre> <p>Initially, each element of the semaphore C0, C1, C2, C3, and C4 are initialized to 1 as the chopsticks are on the table and not picked up by any of the philosophers.</p> <p>Let&apos;s modify the above code of the Dining Philosopher Problem by using semaphore operations wait and signal, the desired code looks like</p> <pre> void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } </pre> <p>In the above code, first wait operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows philosopher i have picked up the chopsticks from its left and right. The eating function is performed after that.</p> <p>On completion of eating by philosopher i the, signal operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows that the philosopher i have eaten and put down both the left and right chopsticks. Finally, the philosopher starts thinking again.</p> <h3>Let&apos;s understand how the above code is giving a solution to the dining philosopher problem?</h3> <p>Let value of i = 0( initial value ), Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C0 chopstick</strong> and reduces semaphore C0 to 0 <strong>,</strong> after that it execute <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C1 chopstick</strong> ( since i =0, therefore (0 + 1) % 5 = 1) and reduces semaphore C1 to 0</p> <p>Similarly, suppose now Philosopher P1 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it will try to hold <strong>C1 chopstick</strong> but will not be able to do that <strong>,</strong> since the value of semaphore C1 has already been set to 0 by philosopher P0, therefore it will enter into an infinite loop because of which philosopher P1 will not be able to pick chopstick C1 whereas if Philosopher P2 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C2 chopstick</strong> and reduces semaphore C2 to 0, after that, it executes <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C3 chopstick</strong> ( since i =2, therefore (2 + 1) % 5 = 3) and reduces semaphore C3 to 0.</p> <p>Hence the above code is providing a solution to the dining philosopher problem, A philosopher can only eat if both immediate left and right chopsticks of the philosopher are available else philosopher needs to wait. Also at one go two independent philosophers can eat simultaneously (i.e., philosopher <strong>P0 and P2, P1 and P3 &amp; P2 and P4</strong> can eat simultaneously as all are the independent processes and they are following the above constraint of dining philosopher problem)</p> <h3>The drawback of the above solution of the dining philosopher problem</h3> <p>From the above solution of the dining philosopher problem, we have proved that no two neighboring philosophers can eat at the same point in time. The drawback of the above solution is that this solution can lead to a deadlock condition. This situation happens if all the philosophers pick their left chopstick at the same time, which leads to the condition of deadlock and none of the philosophers can eat.</p> <p>To avoid deadlock, some of the solutions are as follows -</p> <ul> <li>Maximum number of philosophers on the table should not be more than four, in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and after the finish of his eating procedure, he will put down his both the chopstick C3 and C4, i.e. semaphore C3 and C4 will now be incremented to 1. Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available, hence similarly, he will put down his chopstick after eating and enable other philosophers to eat.</li> <li>A philosopher at an even position should pick the right chopstick and then the left chopstick while a philosopher at an odd position should pick the left chopstick and then the right chopstick.</li> <li>Only in case if both the chopsticks ( left and right ) are available at the same time, only then a philosopher should be allowed to pick their chopsticks</li> <li>All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the left chopstick. This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start eating and will put down its both chopsticks once finishes and let others eat which removes the problem of deadlock.</li> </ul> <p>The design of the problem was to illustrate the challenges of avoiding deadlock, a deadlock state of a system is a state in which no progress of system is possible. Consider a proposal where each philosopher is instructed to behave as follows:</p> <ul> <li>The philosopher is instructed to think till the left fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to think till the right fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to eat when both forks are available.</li> <li>then, put the right fork down first</li> <li>then, put the left fork down next</li> <li>repeat from the beginning.</li> </ul> <hr></=></p></=>

في البداية، تتم تهيئة كل عنصر من عناصر الإشارة C0 وC1 وC2 وC3 وC4 إلى 1 حيث أن عيدان تناول الطعام على الطاولة ولم يلتقطها أي من الفلاسفة.

دعونا نعدل الكود أعلاه لمشكلة فيلسوف الطعام باستخدام عمليات الإشارة الانتظار والإشارة، ليبدو الكود المطلوب كما يلي

 void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } 

في الكود أعلاه، يتم تنفيذ عملية الانتظار الأولى على take_chopstickC[i] و take_chopstickC [ (i+1) % 5]. وهذا يوضح للفيلسوف أنني التقطت عيدان تناول الطعام من يساره ويمينه. يتم تنفيذ وظيفة الأكل بعد ذلك.

عند الانتهاء من الأكل بواسطة الفيلسوف i، يتم تنفيذ عملية الإشارة على take_chopstickC[i] و take_chopstickC [ (i+1) % 5]. وهذا يدل على أن الفيلسوف قد أكل ووضع العيدان اليمنى واليسرى. وأخيرا، يبدأ الفيلسوف بالتفكير مرة أخرى.

دعونا نفهم كيف يقدم الكود أعلاه حلاً لمشكلة فيلسوف الطعام؟

دع قيمة i = 0 (القيمة الأولية)، لنفترض أن الفيلسوف P0 يريد أن يأكل، فسوف يدخل في وظيفة Philosopher()، وينفذ انتظر (take_chopstickC[i])؛ من خلال القيام بذلك فإنه يحمل C0 عود ويقلل الإشارة C0 إلى 0 , بعد ذلك يتم تنفيذه انتظر( take_chopstickC[(i+1) % 5] ); من خلال القيام بذلك فإنه يحمل عيدان C1 ( بما أن i =0، وبالتالي (0 + 1) % 5 = 1) ويقلل الإشارة C1 إلى 0

وبالمثل، لنفترض الآن أن الفيلسوف P1 يريد أن يأكل، فسوف يدخل في وظيفة Philosopher()، وينفذ انتظر (take_chopstickC[i])؛ من خلال القيام بذلك سيحاول الصمود عيدان C1 ولكن لن تكون قادرة على القيام بذلك , نظرًا لأن قيمة الإشارة C1 قد تم ضبطها بالفعل على 0 بواسطة الفيلسوف P0، وبالتالي فإنها ستدخل في حلقة لا نهائية بسببها لن يتمكن الفيلسوف P1 من اختيار عيدان تناول الطعام C1 بينما إذا أراد الفيلسوف P2 أن يأكل، فسوف يدخل في الفيلسوف () الوظيفة والتنفيذ انتظر (take_chopstickC[i])؛ من خلال القيام بذلك فإنه يحمل عود C2 ويقلل الإشارة C2 إلى 0، وبعد ذلك يتم تنفيذه انتظر( take_chopstickC[(i+1) % 5] ); من خلال القيام بذلك فإنه يحمل عود C3 ( بما أن i =2، وبالتالي (2 + 1) % 5 = 3) ويقلل الإشارة C3 إلى 0.

وبالتالي فإن الكود أعلاه يوفر حلاً لمشكلة تناول الطعام لدى الفيلسوف، حيث لا يمكن للفيلسوف أن يأكل إلا إذا توفرت عيدان تناول الطعام اليسرى واليمنى للفيلسوف، وإلا سيحتاج الفيلسوف إلى الانتظار. كما يمكن لفيلسوفين مستقلين تناول الطعام في وقت واحد دفعة واحدة (أي الفيلسوف P0 وP2، P1 وP3 وP2 وP4 يمكنهم تناول الطعام في وقت واحد حيث أن جميعها عبارة عن عمليات مستقلة ويتبعون القيد المذكور أعلاه لمشكلة الفيلسوف في تناول الطعام)

عيب الحل أعلاه لمشكلة فيلسوف الطعام

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

لتجنب الجمود، بعض الحلول هي كما يلي -

• يجب ألا يزيد الحد الأقصى لعدد الفلاسفة على الطاولة عن أربعة، في هذه الحالة، سيكون عيدان تناول الطعام C4 متاحًا للفيلسوف P3، لذلك سيبدأ P3 في تناول الطعام وبعد الانتهاء من إجراءات تناول الطعام، سيضع كلا من عيدان تناول الطعام C3 و C4، أي الإشارة C3 و C4 ستتم الآن زيادتها إلى 1. الآن الفيلسوف P2 الذي كان يحمل عيدان تناول الطعام C2 سيكون لديه أيضًا عيدان تناول الطعام C3، وبالتالي بالمثل، سيضع عصا تناول الطعام جانبًا بعد تناول الطعام ويمكّن الفلاسفة الآخرين من تناول الطعام.
• يجب على الفيلسوف الذي يكون في وضع متساو أن يختار العيدان اليمنى ثم العيدان اليسرى بينما يجب على الفيلسوف الذي يكون في وضع فردي أن يختار العيدان اليسرى ثم العيدان اليمنى.
• فقط في حالة توفر كلا عيدان تناول الطعام (اليسار واليمين) في نفس الوقت، عندها فقط يجب السماح للفيلسوف باختيار عيدان تناول الطعام الخاصة به
• يجب على جميع الفلاسفة الأربعة (P0، P1، P2، وP3) أن يختاروا العيدان اليسرى ثم العيد الأيمن، في حين أن الفيلسوف الأخير P4 يجب أن يختار العيدان اليمنى ثم العيد الأيسر. سيجبر هذا P4 على الإمساك بالعصا اليمنى أولاً لأن العصا اليمنى لـ P4 هي C0، والتي كان الفيلسوف P0 يحملها بالفعل وقيمتها مضبوطة على 0، أي أن C0 هي 0 بالفعل، وبسبب ذلك سيتم احتجاز P4 في عدد لا نهائي تظل الحلقة والعصا C4 شاغرة. ومن ثم، فإن الفيلسوف P3 لديه كلا من عصا تناول الطعام اليسرى C3 والأيمن C4 متاحة، وبالتالي سيبدأ في تناول الطعام وسيضع كلا العيدان جانبًا بمجرد الانتهاء ويسمح للآخرين بتناول الطعام مما يزيل مشكلة الجمود.

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

• يُطلب من الفيلسوف أن يفكر حتى تصبح الشوكة اليسرى متاحة، وعندما تكون متاحة، أمسكها.
• يُطلب من الفيلسوف أن يفكر حتى تتوفر الشوكة المناسبة، وعندما تكون متاحة، أمسكها.
• يُطلب من الفيلسوف أن يأكل عند توفر الشوكتين.
• ثم ضع الشوكة اليمنى أولاً
• ثم ضع الشوكة اليسرى لأسفل بعد ذلك
• كرر من البداية.