הרצאה 7 דדלוק Flashcards
מה הדוגמה של הדדלוק בשולחן
יש 5 אנשים במעגל
ו5 מקלות אכילה
לכל אחד מצד ימין ושמאל
כל אחד צריך את 2 המקלות ימין ושמאל בשביל לאכול
יכול להווצר מצב שכל אחד מחזיק את המקל אכילה הימני לו ומחכה לנצח שהשמאלי יתפנה
מה התנאים לקיום דדלוק
1
מניעה הדדית - יש משאבים שלא יכולים להיות מוקצים ליותר מתהליך אחד
2
תהליכים יכולים להחזיק משאב ולחכות למשאב אחר
3
יש המתנה במעגל - כל תהליך מחכה לתהליך אחר במעגל
4
אין הפקעה של משאבים
לא מאבדים אותם אחרי זמן מסויים
איזה גישות יש כדי לטפל בדדלוק
או למנוע כבר בתכנון שיהיה דדלוק
או לאפשר למערכת ההפעלה לזהות ולטפל בדדלוק
לדוגמה כשהזכרון מותש - ואז להרוג תהליך רנדומלי
איך מונעים דדלוק
כמה מילים
מפרים את אחד מארבעת הכללים של דדלוק
איך מונעים את
1
מניעה הדדית - יש משאבים שלא יכולים להיות מוקצים ליותר מתהליך אחד
נשתמש רק בפקודות אטומטית שנתמכות על ידי החומרה
אפשר להשתמש גם בספריה שתסתיר את המימוש האטומי מהשתמש
איך מונעים את
2
תהליכים יכולים להחזיק משאב ולחכות למשאב אחר
כל משתמש יבקש את כל המנעולים שהוא יצטרך בבת אחת
מערכת ההפעלה תיתן לו את הכל או שתכניס אותו להמתנה,
יש לזה דיוק או שיפור שלפני כל פעולה אטומטית על מבנה מסויים נשחרר את כל המנעולים האחרים
איך מונעים את
3
יש המתנה במעגל - כל תהליך מחכה לתהליך אחר במעגל
הכי פרקטי לשינוי
נמספר את המשאבים
כל תהליך יכול לבקש משאבים בסדר עולה
כך לא יווצר מצב של מעגל
אם תהליך ירצה מנעול נמוך יצטרך לאפס את כל מה שיש לו כבר
איך מונעים את
4
אין הפקעה של משאבים
לא מאבדים אותם אחרי זמן מסויים
אפשר באופן אלים לעשות את זה
לדוגמה אם אין מספיק משאבי זכרון
אפשר להרוג את התהליך או לשמור את המשאבים שלו לדיסק ואז לשחרר את הזכרון שלו
דוגמה על זכרון אבל רעיון דומה
איך אפשר תלות מעגלית
3 בעזרת גרף
ואיך אפשר לטפל בהם
אפשר לצייר את כל התהליכים
ולעשות קשת
מתהליך
לתהליך שמחזיק במשאב שהתהליך הראשון צריך
גילינו מעגל וזה שלב הזיהוי
שלב הטיפול יהיה להרוג תהליכים עד שנפתר
או להפקיע משאבים עד שנפתר
כמה קל לזהות סט מינימלי של תהליכים להרוג בשביל לפתור את המערל
NP קשה
מהו אלגוריתם הבנקאי של דיאקסטרה
מנגנון למניעה של דדלוק מראש
כל תהליך מצהיר כמה משאבים הוא יצטרך
כמו מסגרת אשראי לכל תהליך
בכל בקשת משאבים מערכת ההפעלה מסתכלת על הבקשה ובודקת האם יכול להיות שהבקשה תגרור דדלוק בעתיד אם כן היא לא מאשרת את הבקשה ומכניסה למצב המתנה
זה כמו לבקש עסקה באשראי
מערכת ההפעלה כל הזמן עוקבת אחרי כמו משאבים נשאר מכל סוג
אפשר להסתכל על זה ככמות שקלים דולרים ויין
וכל פעם שיש בקשה אנחנו בודקים האם שניתן לתהליך את הכסף במסגרת האשראי שלו לא נגיע למצב שלא יהיה לנו כסף להביא
לתהליך המבקש בשביל לספק את המסגרת המקסימלית שלו ואז הוא יתקע כשהוא מחזיק משאבים נחוצים ביד
מה זמן הריצה של אלגורתיתם הבנקאי
n^2