TechCodeview

הבעיה של פילוסוף האוכל היא הבעיה הקלאסית של סנכרון שאומרת שחמישה פילוסופים יושבים סביב שולחן עגול ותפקידם לחשוב ולאכול לחלופין. קערת אטריות מונחת במרכז השולחן יחד עם חמישה מקלות אכילה לכל אחד מהפילוסופים. כדי לאכול פילוסוף צריך גם מקלות אכילה ימין וגם שמאל. פילוסוף יכול לאכול רק אם יש מקלות אכילה מיידיים של הפילוסוף שמאלה וימינה. במקרה שאם גם מקלות האכילה הימניים והשמאליים של הפילוסוף אינם זמינים, הפילוסוף מניח את מקלות האכילה שלהם (שמאלי או ימין) ומתחיל לחשוב שוב.

פילוסוף האוכל מדגים מחלקה גדולה של בעיות בקרת מקביליות ולכן זו בעיית סנכרון קלאסית.

חמישה פילוסופים יושבים סביב השולחן

בעיית פילוסופים לאוכל - בוא נבין את בעיית הפילוסופים של האוכל עם הקוד שלהלן, השתמשנו באיור 1 כהתייחסות כדי לגרום לך להבין את הבעיה בדיוק. חמשת הפילוסופים מיוצגים בתור P0, P1, P2, P3 ו-P4 וחמישה מקלות אכילה לפי C0, C1, C2, C3 ו-C4.

פונקציית chr python

 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 רוצה לאכול, הוא יכנס לפונקציה פילוסוף () ויבצע take_chopstick[i]; על ידי כך זה מחזיק מקל אכילה C1 אחרי זה זה יבוצע take_chopstick[ (i+1) % 5]; על ידי כך זה מחזיק מקל אכילה C2 (מכיוון ש-i =1, לכן (1 + 1) % 5 = 2)

אבל למעשה Chopstick C1 אינו זמין מכיוון שהוא כבר נלקח על ידי הפילוסוף P0, ומכאן שהקוד לעיל יוצר בעיות ומייצר מצב גזע.

btree ו-b tree

פתרון בעיית הפילוסופים של האוכל

אנו משתמשים בסמפור כדי לייצג מקל אכילה וזה באמת פועל כפתרון לבעיית הפילוסופים של האוכל. פעולות המתנה ואותות ישמשו לפתרון בעיית הפילוסופים של אוכל, לבחירת מקל אכילה ניתן לבצע פעולת המתנה ואילו לשחרור סמפור אות אכילה ניתן לבצע.

סמפור: סמפור הוא משתנה מספר שלם ב-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]. זה מראה לפילוסוף שהרמתי את מקלות האכילה משמאל ומימין. פונקציית האכילה מתבצעת לאחר מכן.

אלטרנטיבה xampp

עם השלמת האכילה על ידי הפילוסוף i the, פעולת האות מתבצעת על take_chopstickC[i] ו-tak_chopstickC [(i+1) % 5]. זה מראה שהפילוסוף שאכלתי והנחתי את מקלות האכילה הימניים והשמאליים. לבסוף, הפילוסוף מתחיל לחשוב שוב.

בואו נבין איך הקוד הנ'ל נותן פתרון לבעיית פילוסוף האוכל?

תן לערך של i = 0(ערך התחלתי), נניח שהפילוסוף P0 רוצה לאכול, הוא ייכנס לפונקציה Philosopher() ויבצע Wait( take_chopstickC[i] ); על ידי כך זה מחזיק מקל אכילה C0 ומפחית את הסמפור C0 ל-0 , אחרי זה זה יבוצע Wait( take_chopstickC[(i+1) % 5] ); על ידי כך זה מחזיק מקל אכילה C1 (מכיוון i =0, לכן (0 + 1) % 5 = 1) ומפחית את הסמפור C1 ל-0

באופן דומה, נניח שעכשיו פילוסוף P1 רוצה לאכול, הוא ייכנס לפונקציה Philosopher() ויבצע Wait( take_chopstickC[i] ); על ידי כך הוא ינסה להחזיק מקל אכילה C1 אבל לא יוכל לעשות זאת , מכיוון שהערך של סמפור C1 כבר הוגדר ל-0 על ידי הפילוסוף P0, לכן הוא ייכנס ללולאה אינסופית שבגללה הפילוסוף P1 לא יוכל לבחור אכילה C1 ואילו פילוסוף P2 ירצה לאכול, הוא ייכנס בפילוסוף () פונקציה, וביצוע Wait( take_chopstickC[i] ); על ידי כך זה מחזיק מקל אכילה C2 ומפחית את סמפור C2 ל-0, לאחר מכן, הוא מבצע Wait( take_chopstickC[(i+1) % 5] ); על ידי כך זה מחזיק מקל אכילה C3 (מכיוון ש-i =2, לכן (2 + 1) % 5 = 3) ומפחית את הסמפור C3 ל-0.

מכאן שהקוד לעיל מספק פתרון לבעיית הפילוסוף האוכל, פילוסוף יכול לאכול רק אם מקלות האכילה הימניים והשמאליים של הפילוסוף זמינים, אחרת הפילוסוף צריך לחכות. גם בבת אחת שני פילוסופים עצמאיים יכולים לאכול בו זמנית (כלומר, פילוסוף P0 ו-P2, P1 ו-P3 & P2 ו-P4 יכול לאכול בו-זמנית שכן כולם הם התהליכים העצמאיים והם עוקבים אחר האילוץ לעיל של בעיית פילוסוף האוכל)

java mvc

החיסרון של הפתרון לעיל של בעיית פילוסוף האוכל

מהפתרון לעיל של בעיית פילוסוף האוכל, הוכחנו שאין שני פילוסופים שכנים יכולים לאכול באותה נקודת זמן. החיסרון של הפתרון לעיל הוא שפתרון זה יכול להוביל למצב מבוי סתום. מצב זה קורה אם כל הפילוסופים קוטפים את הצ'ופסט השמאלי שלהם בו-זמנית, מה שמוביל למצב של מבוי סתום ואף אחד מהפילוסופים לא יכול לאכול.

כדי למנוע מבוי סתום, חלק מהפתרונות הם כדלקמן -

• המספר המרבי של פילוסופים על השולחן לא צריך להיות יותר מארבעה, במקרה זה, צ'ופצ'יק 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 יש גם מקלות אכילה שמאליים ו-C4 ימניים זמינים, לכן הוא יתחיל לאכול ויניח את שני מקלות האכילה שלו ברגע שיסיים ויאפשר לאחרים לאכול מה שמסיר את בעיית הקיפאון.

התכנון של הבעיה היה להמחיש את האתגרים של הימנעות מבוי סתום, מצב מבוי סתום של מערכת הוא מצב בו אין התקדמות של המערכת אפשרית. שקול הצעה שבה כל פילוסוף מקבל הוראה להתנהג באופן הבא:

• הפילוסוף מקבל הוראה לחשוב עד שהמזלג השמאלי יהיה זמין, כאשר הוא זמין, החזק אותו.
• הפילוסוף מקבל הוראה לחשוב עד שהמזלג הנכון יהיה זמין, כאשר הוא זמין, החזק אותו.
• הפילוסוף מקבל הוראה לאכול כאשר שני המזלגות זמינים.
• לאחר מכן, הנח קודם את המזלג הימני
• לאחר מכן, הנח את המזלג השמאלי למטה
• לחזור מההתחלה.