חוטים ומנעולים.

[אלוהים1980]

חוטים ומנעולים.

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

cond_wait(TA_cond, lock);​

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

 

[gmorphus]

לא בדיוק הבנתי

מה אתה מנסה לעשות ומה התרגיל, אבל הרעיון במנעולים הוא כזה: זה קשור לגישה למשאבים משותפים בעיקר. את הרעיון הזה אפשר לקחת לכל מיני מקומות אבל זה עיקר השימוש. thread רוצה לגשת לאיזשהו משאב משותף. המשאב הזה יכול להיות מוגן באופן לוגי באמצעות איזשהו מנגנון סינכרון - מנעול למשל. ב thread מבקש את המנעול. אם מישהו משתמש במשאב, זאת אומרת שהנמעול נעול, הthread יחכה באותה השורה עד שה"מישהו" האחר יסיים. ברגע שהוא מסיים הthread שלנו מקבל את המנעול ונועל אותו עד שהוא מסיים להשתמש במשאב. לפי איך שאתה מתאר את התרגיל שלך בthread מחכה על איזשהו מנעול, ואז הוא מחכה עוד פעם, אחרי שהוא נעל את המנעול בעצמו על תנאי מסוים. אם התנאי הזה קשור למנעול, וכדי שהתנאי הזה ישתנה דרוש שthread אחר יקבל את המנעול יצרת פה deadlock (אם starvation - אני כבר לא זוכר

)

 

[Pembelton]

אם נסתמך על מה שקורה בג'אווה...

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

 

[אלוהים1980]

המממ...

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

 

[ahab]

condition variables

כאשר מבצעים wait על משתנה תנאי, המנעול משוחרר (זו הסיבה שמעבירים ל-wait מצביע למנעול). כאשר חוזרים מ-wait, מובטח לך כי החוט מחזיק את המנעול. כלומר, ניתן להתייחס ל-wait כפונקציה המבצעת את הפסאודקוד הבא: 1. שחרר מנעול. 2. לך לישון, עד שמבוצע notify על משתנה התנאי. 3. תפוס מנעול.

 

[אלוהים1980]

עוד הבהרה בבקשה,

האם מובטח לחוט שלאחר שהוא תפס מחדש את המנעול (בסעיף 3 בפסאודו קוד שלך) משתנה התנאי נשאר כשהיה? או שיכול להיות שהוא השתנה שוב?

 

[Pembelton]

בג'אווה זה מובטח

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

 

[אלוהים1980]

הנה התרגיל:

למתרגל במערכות הפעלה יש שעת קבלה פעם בשבוע. אם אף אחד לא בא לשאול אותו שאלות בזמן שעת הקבלה הוא גולש באינטרנט. אם סטודנטים באים לשאול שאלות, הם צריכים להסתנכרן בינם כך שיתקיימו התנאים הבאים: 1. רק סטודנט אחד שואל שאלה בכל רגע נתון. 2. סטודנט יכול לשאול שאלה רק אם המתרגל סיים לענות על השאלה הקודמת. כמו כן, המשרד של המתרגל הוא קטן ולא יכול להכיל יותר מ –4 סטודנטים. סטודנט שמגיע ומגלה שהוא לא יכול להיכנס למשרד עוזב. הפסאודו-קוד הבא מממש את הבעיה המוצגת. המתרגל מבצע את פרוצדורת TA(). סטודנט שמגיע לשעות הקבלה מבצע את פרוצדורת Student(). הניחו שמשתני תנאי ו-mutex-ים מאתחלים

MAX_STUDENT=4; students = 0; questions = 0; Lock lock; Condition TA_cond; Condition student_cond; answering = FALSE; 1. procedure TA() 2. { 3. while (true) 4. { 5. acquire(lock); 6. while ((students == 0) || (questions == 0)) 7. cond_wait(TA_cond, lock); 8. questions --; 9. answering = TRUE; 10. release(lock); 11. AnswerQuestion(); 12. acquire(lock); 13. answering = FALSE; 14. cond_signal(student_cond); 15. release(lock); 16. } 17. } 18. procedure Student() 19. { 20. acquire(lock); 21. if (students == MAX_STUDENT) 22. { 23. release(lock); 24. return; 25. } 26. students++; 27. release(lock); 28. while (have questions to ask) 29. { 30. acquire(lock); 31. while (answering) 32. cond_wait(student_cond, lock); 33. question ++; 34. AskQuestion(); 35. cond_signal(TA_cond); 36. release(lock); 37. } 38. acquire(lock); 39. students--; 40. release(lock); 41. }​

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

 

[Pembelton]

תלוי בהגדרה של cond_wait

... ובשביל לדעת איך cond_wait מוגדר תצטרך לשאול את מי שכתב את התרגיל הזה

 

[i c e b e r g]

--->

הבעיה שאתה מתאר מוכרת ונקראת בעיית "הספר הישן" או באנגלית : The Sleeping Barber Problem חיפוש קטן בגוגל יתן לך תוצאות מעניינות

 

[ahab]

לא בדיוק

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

 

[ahab]

בבקשה..

בניגוד לשם שלו, משתנה תנאי לא מחזיק אף תנאי. תפקידך כמתכנת "לקשור" אותו לתנאי כלשהו בתוכנית. לכן השימוש הנפוץ יהיה בסגנון: 1. כל עוד התנאי לא מתקיים... 1.1. חכה על משתנה התנאי. 2. עשה משהו (בנקודה זו אתה יודע כי התנאי מתקיים) שים לב לשימוש בלולאה, ולא בבדיקה פשוטה (while, ולא if) עבור בדיקת משתנה התנאי. תפקיד הלולאה לוודא כי לאחר שאתה מקבל את המנעול (לאחר שמישהו ביצע notify), אתה מבצע בדיקה נוספת של התנאי, ורק אם הוא עדיין מתקיים, אתה נכנס לקטע הקריטי. אם היית משתמש ב-if, לא הייתה מתבצעת בדיקה נוספת, ואז ייתכן מצב כי חוט אחר ישנה את התנאי לפני שהחוט שלך קיבל את המעבד (ואז נוצר מצב בו הוא נכנס לקטע הקריטי למרות שהתנאי לא מתקיים). תעבור שוב על ההרצאה/תרגול. סביר להניח כי חוזרים מספר פעמים על נקודה זו.

 

[אלוהים1980]

עוד הבהרה בבקשה:

כאשר מישהו מבצע notify (אצלי בתרגיל זה: cond_signal), האם באופן מיידי השליטה תעבור למי שממתין, או שזה שביצע notify יוכל להמשיך? ונראה אם הבנתי נכון: שאלה: האם הפתרון הנ"ל מבטיח שסטודנט לא ישאל שאלה כאשר מתרגל עונה על שאלה של סטודנט אחר ( מניעה הדדית בין מתרגל לסטודנט) ? אם כן נמק/י בפרוט, אם לא תן/י דוגמה. התשובה שלי: הפתרון לא מבטיח שסטודנט לא ישאל שאלה בזמן שהמתרגל מדבר: נניח ששני סטודנטים מגיעים לשורה 27. אחד מהם תופס את המנעול, ונכנס אל לולאת ההמתנה בשורות 31-32, עד שהמתרגל יסיים לענות לסטודנט שהגיע לפניהם. הכניס ללולאה משחררת את המנעול, ולכן הסטודנט השני יכול גם כן להיכנס ולהגיע לאותו מצב כמו הסטודנט הראשון. לאחר שהמתרגל יסיים לענות, שני הסטודנטים יתקדמו לשורה 33. נניח שאחד מהם ימשיך עד שורה 36, ובכך יגרום למתרגל להתחיל לענות. אולם תוך כדי שהמתרגל עונה, בשורה 11, הוא חייב קודם לשחרר את המנעול, ולכן גם הסטודנט השני יוכל להתקדם לשורה 34 ולשאול שאלה בזמן שהתרגל עונה לשאלה של הסטודנט הראשון. שאלה: האם הפתרון הנ"ל מבטיח ששני סטודנטים לא ישאלו שאלה באותו זמן (מניעה הדדית בין הסטודנטים, תנאי 1 בשאלה ) ? אם כן נמק/י בפרוט, אם לא תן/י דוגמה. התשובה שלי: הפתרון לא מבטיח ששני סטודנטים לא ישאלו שאלה באותו הזמן: נניח ששני סטודנטים מגיעים לשורה 27. אחד מהם תופס את המנעול, ונכנס אל לולאת ההמתנה בשורות 31-32, עד שהמתרגל יסיים לענות. הכניסה ללולאה משחררת את המנעול. לכן הסטודנט השני יכול גם כן להיכנס, ולהגיע לאותו מצב כמו הסטודנט הראשון. לאחר שהמתרגל יסיים לענות, שני הסטודנטים יתקדמו במקביל לשורה 34, וישאלו שאלה באותו הזמן.

 

[ahab]

לרוב אין הבטחות

כאשר חוט מבצע notify (או signal, broadcast, notifyAll... לא משנה), לרוב לא מובטח שום דבר לגבי החוט הבא שירוץ. כל מה שמובטח הוא שחוט אחר ישוחרר מההמתנה שלו (או כולם, במקרה של broadcast/notifyAll), ויחזור לקבוצת החוטים שמחכים לזמן מעבד. אלא אם כן צויין, לא מובטח שהחוט שביצע notify יותר מייד על המעבד (וסביר שלא, כי הוא עדיין מחזיק במנעול), ולא מובטח כי חוט שה-notify העיר יקבל מייד את המעבד (ראה דוגמא בתגובה קודמת שלי). (הערה קטנה.. ייתכן בהחלט מימוש של מנעולים/משתני תנאי שבו מובטחים תנאים מסויימים לגבי מי ירוץ ומתי) לגבי התרגיל עצמו, את שיעורי הבית שלי כבר עשיתי בזמנו. אני מציע לך לעקוב אחרי הביצוע בצורה מסודרת, שלב אחר שלב. שים לב בעיקר לקיום התנאים, זרימת הביצוע (לאחר wait, החוט נמצא עדיין בלולאה. הוא יוצא ממנה רק כשהתנאי ב-while לא מתקיים), ומי מחזיק במנעול בכל שלב. תעשה חיים.

 

[אלוהים1980]

תודה רבה.

 

[Zack DA]

../images/Emo45.gif אגב,

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