הרצאה 7 דדלוק Flashcards

1
Q

מה הדוגמה של הדדלוק בשולחן

A

יש 5 אנשים במעגל
ו5 מקלות אכילה
לכל אחד מצד ימין ושמאל
כל אחד צריך את 2 המקלות ימין ושמאל בשביל לאכול

יכול להווצר מצב שכל אחד מחזיק את המקל אכילה הימני לו ומחכה לנצח שהשמאלי יתפנה

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

מה התנאים לקיום דדלוק

A

1
מניעה הדדית - יש משאבים שלא יכולים להיות מוקצים ליותר מתהליך אחד

2
תהליכים יכולים להחזיק משאב ולחכות למשאב אחר

3
יש המתנה במעגל - כל תהליך מחכה לתהליך אחר במעגל

4
אין הפקעה של משאבים
לא מאבדים אותם אחרי זמן מסויים

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

איזה גישות יש כדי לטפל בדדלוק

A

או למנוע כבר בתכנון שיהיה דדלוק

או לאפשר למערכת ההפעלה לזהות ולטפל בדדלוק
לדוגמה כשהזכרון מותש - ואז להרוג תהליך רנדומלי

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

איך מונעים דדלוק
כמה מילים

A

מפרים את אחד מארבעת הכללים של דדלוק

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

איך מונעים את
1
מניעה הדדית - יש משאבים שלא יכולים להיות מוקצים ליותר מתהליך אחד

A

נשתמש רק בפקודות אטומטית שנתמכות על ידי החומרה

אפשר להשתמש גם בספריה שתסתיר את המימוש האטומי מהשתמש

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

איך מונעים את
2
תהליכים יכולים להחזיק משאב ולחכות למשאב אחר

A

כל משתמש יבקש את כל המנעולים שהוא יצטרך בבת אחת

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

איך מונעים את
3
יש המתנה במעגל - כל תהליך מחכה לתהליך אחר במעגל

A

הכי פרקטי לשינוי

נמספר את המשאבים

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

איך מונעים את
4
אין הפקעה של משאבים
לא מאבדים אותם אחרי זמן מסויים

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

איך אפשר תלות מעגלית
3 בעזרת גרף

ואיך אפשר לטפל בהם

A

אפשר לצייר את כל התהליכים

ולעשות קשת
מתהליך
לתהליך שמחזיק במשאב שהתהליך הראשון צריך

גילינו מעגל וזה שלב הזיהוי

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

כמה קל לזהות סט מינימלי של תהליכים להרוג בשביל לפתור את המערל

A

NP קשה

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

מהו אלגוריתם הבנקאי של דיאקסטרה

A

מנגנון למניעה של דדלוק מראש

כל תהליך מצהיר כמה משאבים הוא יצטרך
כמו מסגרת אשראי לכל תהליך

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

זה כמו לבקש עסקה באשראי

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

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

מה זמן הריצה של אלגורתיתם הבנקאי

A

n^2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly