streamalism.org

1. הקדמה

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

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

2. הבעיה

התרשים שלמעלה מייצג את הבעיה. ישנם חמישה פילוסופים דוממים (P1 - P5) שיושבים סביב שולחן עגול ומבלים את חייהם באכילה וחשיבה.

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

המטרה היא ליצור תוכנית / פרוטוקול המסייע לפילוסופים להשיג את מטרתם לאכול ולחשוב מבלי להרעיב למוות.

3. פיתרון

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

בעוד (נכון) {// בתחילה, חשיבה על החיים, היקום, והכל חושבים (); // קח הפסקה מהמחשבה, רעב עכשיו pick_up_left_fork (); pick_up_right_fork (); לאכול(); put_down_right_fork (); put_down_left_fork (); // כבר לא רעב. חזרה לחשוב! } 

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

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

4. יישום

אנו מודלים כל אחד מהפילוסופים שלנו כשיעורים המיישמים את ה- ניתן לרוץ ממשק כדי שנוכל להריץ אותם כחוטים נפרדים. כל אחד פִילוֹסוֹף יש לו גישה לשני מזלגות בצד שמאל וימין:

מעמד ציבורי פילוסוף מיישם את Runnable {// המזלגות משני צידי האובייקט הפרטי הזה של הפילוסוף leftFork; אובייקט פרטי RightFork; פילוסוף ציבורי (Object leftFork, Object rightFork) {this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run () {// ובכל זאת לאכלס שיטה זו}}

יש לנו גם שיטה שמורה א פִילוֹסוֹף לבצע פעולה - לאכול, לחשוב או לרכוש מזלגות לקראת אכילה:

מחלקה ציבורית פילוסוף מיישם Runnable {// משתני חבר, קונסטרוקטור סטנדרטי ריק voAction (מחרוזת פעולה) זורק InterruptedException {System.out.println (Thread.currentThread (). getName () + "" + פעולה); Thread.sleep (((int) (Math.random () * 100))); } // שאר השיטות שנכתבו קודם}

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

עכשיו, בואו נשתמש בהגיון הליבה של a פִילוֹסוֹף.

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

כדי להשיג זאת, אנו משתמשים ב- מסונכרן מילת מפתח לרכישת המוניטור הפנימי של אובייקט המזלג ולמנוע מאשכולות אחרים לעשות זאת. מדריך ל מסונכרן מילת מפתח ב- Java ניתן למצוא כאן. אנו ממשיכים ביישום ה- לָרוּץ() שיטה ב פִילוֹסוֹף כיתה עכשיו:

מחלקה ציבורית פילוסוף מיישם משתני Runnable {// חברים, שיטות שהוגדרו קודם @ Override public void run () {try {while (true) {// thinking doAction (System.nanoTime () + ": Thinking"); מסונכרן (leftFork) {doAction (System.nanoTime () + ": הרים מזלג שמאלי"); מסונכרן (rightFork) {// אכילת doAction (System.nanoTime () + ": הרים מזלג ימני - אכילה"); doAction (System.nanoTime () + ": הניחו מזלג ימני"); } // חזרה לחשיבה doAction (System.nanoTime () + ": הניחו מזלג שמאלי. חזרה לחשיבה"); לתפוס (InterruptedException e) {Thread.currentThread (). interrupt (); לַחֲזוֹר; }}} 

תוכנית זו מיישמת בדיוק את זו שתוארה קודם: א פִילוֹסוֹף חושב קצת ואז מחליט לאכול.

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

כדי להתחיל את כל התהליך, אנו כותבים לקוח שיוצר 5 פילוסופים כחוטים ומתחיל את כולם:

מעמד ציבורי אוכל פילוסופים {ציבורי ריק סטטי ראשי (מחרוזת [] טענות) זורק חריג {פילוסוף [] פילוסופים = פילוסוף חדש [5]; אובייקט [] מזלגות = אובייקט חדש [פילוסופים.אורך]; עבור (int i = 0; i <forks.length; i ++) {מזלגות [i] = אובייקט חדש (); } עבור (int i = 0; i <philosophers.length; i ++) {Object leftFork = מזלגות [i]; אובייקט rightFork = מזלגות [(i + 1)% מזלגות. אורך]; פילוסופים [i] = פילוסוף חדש (leftFork, rightFork); חוט t = חוט חדש (פילוסופים [i], "פילוסוף" + (i + 1)); t.start (); }}}

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

הפעלת קוד זה מביאה לפלט הדומה להלן. התפוקה שלך תהיה שונה ככל הנראה מהמתואר להלן, בעיקר בגלל ש- לִישׁוֹן() השיטה מופעלת למרווח אחר:

פילוסוף 1 8038014601251: פילוסוף חושב 2 8038014828862: פילוסוף חושב 3 8038015066722: פילוסוף חושב 4 8038015284511: פילוסוף חושב 5 8038015468564: פילוסוף חושב 8038016857288: הרים מזלג שמאלי 3803: 80380 מזלג פילוסוף 4 8038063952219: מזלג שמאלי הרים פילוסוף 1 8038067505168: הניח מזלג ימני פילוסוף 2 8038089505264: מזלג שמאלי הרים פילוסוף 1 8038089505264: הניח מזלג שמאלי. חזרה לחשוב פילוסוף 5 8038111040317: הרים מזלג שמאלי

כל ה פִילוֹסוֹףבתחילה מתחילים לחשוב, ואנחנו רואים את זה פילוסוף 1 ממשיך להרים את המזלג השמאלי והימני, ואז אוכל וממשיך להניח את שניהם, ואז 'פילוסוף 5' מרים אותו.

5. הבעיה בפתרון: מבוי סתום

למרות שנראה שהפתרון שלעיל נכון, יש בעיה של מבוי סתום.

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

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

פילוסוף 1 8487540546530: פילוסוף חושב 2 8487542012975: פילוסוף חושב 3 8487543057508: פילוסוף חושב 4 8487543318428: פילוסוף חושב 5 8487544590144: פילוסוף חושב 3 8487589069046: הרים מזלג שמאל 64 פילוס 8 875: פילוסוף 8 875: פילוסוף 8 875 4 8487617680958: הרים מזלג שמאלי פילוסוף 2 8487631148853: הרים מזלג שמאלי

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

6. פתרון מבוי סתום

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

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

אנו מיישמים זאת בקוד הקיים שלנו על ידי שינוי קל יחסית בקוד:

מעמד ציבורי DiningPhilosophers {public static void main (String [] args) throw Exception {final Philosopher [] פילוסופים = פילוסוף חדש [5]; אובייקט [] מזלגות = אובייקט חדש [פילוסופים.אורך]; עבור (int i = 0; i <forks.length; i ++) {מזלגות [i] = אובייקט חדש (); } עבור (int i = 0; i <philosophers.length; i ++) {Object leftFork = מזלגות [i]; אובייקט rightFork = מזלגות [(i + 1)% מזלגות. אורך]; אם (i == פילוסופים.אורך - 1) {// הפילוסוף האחרון מרים את המזלג הימני הפילוסופים הראשונים [i] = פילוסוף חדש (rightFork, leftFork); } אחר {פילוסופים [i] = פילוסוף חדש (leftFork, rightFork); } חוט t = חוט חדש (פילוסופים [i], "פילוסוף" + (i + 1)); t.start (); }}} 

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

התפוקה הבאה מציגה את אחד המקרים שבהם כל פִילוֹסוֹףהם מקבלים את ההזדמנות לחשוב ולאכול מבלי לגרום למבוי סתום:

פילוסוף 1 88519839556188: פילוסוף חושב 2 88519840186495: פילוסוף חושב 3 88519840647695: פילוסוף חושב 4 88519840870182: פילוסוף חושב 5 88519840956443: פילוסוף חושב 3 88519864404195: מזלג 5 שמאלה 5 פילף 5 משמאל: פילוס 5 מזלג 5 5 88519876989405: הרים מזלג ימין - אוכל פילוסוף 2 88519935045524: הרים מזלג שמאלי פילוסוף 5 88519951109805: הניח מזלג ימין פילוסוף 4 88519997119634: הרים מזלג ימני - אוכל פילוסוף 5 88519997113229: הניח מזלג שמאלי. חזרה לחשוב פילוסוף 5 88520011135846: פילוסוף חושב 1 88520011129013: מזלג שמאלי הרים פילוסוף 4 88520028194269: הניח מזלג ימין פילוסוף 4 88520057160194: הניח מזלג שמאלי. חזרה לחשוב פילוסוף 3 88520067162257: הרים מזלג ימין - אוכל פילוסוף 4 88520067158414: פילוסוף חושב 3 88520160247801: הניח מזלג ימין פילוסוף 4 88520249049308: מזלג שמאלי הרים פילוסוף 3 88520249119769: הניח מזלג שמאלי. חזרה לחשוב 

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

7. מסקנה

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

הקוד למאמר זה ניתן למצוא באתר GitHub.