OS PyramidTechnion 234123 · Operating Systemsbasics → exam
the pyramid
Stage 7 / 10 · Core Mechanics

Deadlocksupporting

Deadlock occurs when two or more processes are indefinitely blocked, each waiting for resources held by another. Understanding its four necessary conditions (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait) is fundamental. This topic is crucial for designing robust operating systems that can prevent, avoid, detect, or recover from such states, making it a recurring exam subject.

Where to learn it

lectureLecture 7
41 slides
Start with slides 1, 2, 3, 4, 5

How to study it

  • Master the four necessary conditions for deadlock and be able to identify them in scenarios.
  • Practice the Banker's Algorithm extensively for both safety state determination and resource request evaluation.
  • Differentiate clearly between deadlock prevention, avoidance, detection, and recovery strategies, including their trade-offs.

What the exam asks

Typical exam questions will require applying the Banker's Algorithm to determine system safety or evaluate resource requests, or identifying the presence and conditions of deadlock in a given resource allocation graph.

The components, basic → advanced

These are the atomic skills this stage is built from. Learn them in this order — later ones assume the earlier ones.

L4 · advanced
Banker's algorithm safety check
needs first: mutex correctness

Exam subsections in this stage (27 parts across 9 questions)

OS-Winter-2020-2021-examBQ4core7 parts here

deadlocks קיפאון

  1. 1.1· mcq· 2 pts

    האם יתכן deadlock? כן / לא תשבה: נימוק:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  2. 1.2· short_answer· 8 pts

    עבור 4 תנאים ל-deadlock רשמו לכל אחד: מהו השם של התנאי, והאם הוא מתקיים כן או לא (בהתאם לתשובה למעלה), ובנוסף איך הוא מתקיים או לא מתקיים. תנאי 1: שם: האם מתקיים: כן / לא נימוק: תנאי 2: שם: האם מתקיים: כן / לא נימוק: תנאי 3: שם: האם מתקיים: כן / לא נימוק: תנאי 4: שם: האם מתקיים: כן / לא נימוק:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  3. 2.1· mcq· 2 pts

    האם יתכן deadlock? כן / לא תשבה: נימוק:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  4. 2.2· short_answer· 8 pts

    עבור 4 תנאים ל-deadlock רשמו לכל אחד: מהו שם של התנאי, והאם הוא מתקיים כן או לא (בהתאם לתשובה למעלה), ובנוסף איך הוא מתקיים או לא מתקיים. תנאי 1: שם: האם מתקיים: כן / לא נימוק: תנאי 2: שם: האם מתקיים: כן / לא נימוק: תנאי 3: שם: האם מתקיים: כן / לא נימוק: תנאי 4: שם: האם מתקיים: כן / לא נימוק:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  5. 3.1· diagram· 4 pts

    צייר את גרף הקצאת משאבים (resource allocation graph) כמו שנלמד בהרצאות עבור אלגוריתם הבנקאי, עבור תחילת ריצה של מקרה זה. נמק למה.

    Pipe IPC semanticsMutex correctness and deadlock avoidanceBanker's algorithm safety check
  6. 3.2· short_answer· 4 pts

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

    Mutex correctness and deadlock avoidance
  7. 3.3· calculation· 4 pts

    נניח התוכנה רצה כמו שתואר בסעיף הקודם. להריץ את כל הפונקציונליות הנדרשת בעזרת חוט אחד לוקח T₁ זמן. תניחו הרצה של תוכנה לעיל על N תהליכים (או חוטים) תחת שימוש באלגוריתם הבנקאי לחלוקת משאבים כמו שהסברת בסעיף הקודם. בהינתן הביצועים הגרועים ביותר מה יהיה ה-speedup לפי חוק אמדל (Amdahl law)?

    Pipe IPC semantics
2018B_Spring_AQ2core5 parts here

אלגוריתם הבנקאי

  1. 1· mcq· 5 pts

    (5 נק') מה מטרתו של אלגוריתם הבנקאי? a. לסנכרן בין שני תהליכים או יותר. b. לפתור את בעיית ה-deadlock לאחר שכבר קרתה. c. לזהות את ה-deadlock שיכול להתרחש במקרה שבקשת קבלת המשאבים הנוכחית תענה. d. לענות האם ייתכן deadlock בהינתן גרף הקצאת המשאבים של התהליכים לפני ריצתם. e. מטרה זהה לזו של אלגוריתם קופת חולים. נימוק:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  2. 2· mcq· 5 pts

    (5 נק') מהי ההגדרה של "מצב בטוח" (safe state) באלגוריתם הבנקאי? a. מצב בו תהליכים אינם ב-deadlock b. מצב בו תהליכים אינם ב-deadlock וגם כל בקשת משאבים עתידית לא תגרום ל-deadlock וכל הצרכים למשאבים יסופקו. c. מצב בו רק תהליך אחד משתמש בכל המשאבים שהוא צריך וכל השאר ממתינים. d. מצב בו תהליכים אינם ב-deadlock וקיימת סדרת בקשות משאבים עתידית שלא תגרום ל-deadlock וכל הצרכים למשאבים יסופקו. e. המצב ההתחלתי בלבד של אלגוריתם הבנקאי. נימוק:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  3. 3· mcq· 5 pts

    (5 נק') מהי הסיבוכיות של אלגוריתם הבנקאי עבור בקשת משאבים אחת בהנחה שיש n תהליכים? מדוע זאת הסיבוכיות? a. O(n) כי עוברים על כל התהליכים פעם אחת. b. O(n) כי בכל איטרציה עוברים על כל התהליכים שנשארו בקבוצה ומורידים תהליך אחד מהקבוצה (או שעוצרים) עד שהקבוצה מתרוקנת. c. O(n) כי בשתי לולאות for מקוננות, עוברים על כל התהליכים בשביל כל תהליך. d. O(n!) כי עוברים על כל הסידורים האפשריים של n תהליכים. e. אף תשובה אינה נכונה. נימוק:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  4. 4· mcq· 5 pts

    (5 נק') מבין שיטות הטיפול ב-deadlock (קיפאון), לאיזו קטגוריה משתייך אלגוריתם הבנקאי? a. Deadlock prevention מניעת קיפאון. b. Deadlock avoidance הימנעות מקיפאון. c. Deadlock detection & recovery זיהוי מצב קיפאון וחילוץ מהמצב. d. Deadlock protection שמירת מצב קיפאון. e. אף תשובה לא נכונה. נימוק:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  5. 5· short_answer· 5 pts

    (5 נק') ציינו יתרון אחד וחיסרון אחד של אלגוריתם הבנקאי לעומת טכניקת הקצאת משאבים לפי הסדר (circular wait no.). יתרון של אלגוריתם הבנקאי: חיסרון של אלגוריתם הבנקאי:

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
2017A_Winter_AQ3core4 parts here

סינכרוניזציה

  1. 2· short_answer· 5 pts

    (5 נק') שלומית שמה לב שהיא זו שתמיד קונה את החלב ולכן ניסחה את האלגוריתם באופן סימטרי: 1. if no milk: 2. atomically get the car keys and the wallet 3. buy milk יהודה טוען שהאלגוריתם עשוי לא להסתיים, האם יהודה צודק? נמקו.

    Voluntary vs preemptive context switchPreemption trigger identificationMutex correctness and deadlock avoidance
  2. 3· short_answer· 5 pts

    (5 נק') יהודה טוען שהאלגוריתם קשה למימוש ולכן שלומית ניסחה אלגוריתם חדש: 1. if no milk: 2. get the car keys 3. get the wallet 4. buy milk יהודה טוען שהאלגוריתם עשוי לא להסתיים, האם יהודה צודק? נמקו.

    Voluntary vs preemptive context switchPreemption trigger identificationMutex correctness and deadlock avoidance
  3. 4· short_answer· 5 pts

    (5 נק') שלומית שמה לב שהאלגוריתם גורם לוויכוחים על המפתחות של הרכב ולכן החליטה לנסח אלגוריתם נוסף: 1. if no milk: 2. if (Yehuda): 3. get the car keys 4. get the wallet 5. buy milk 6. if (Shlomit): 7. get the wallet 8. try to get the car keys 9. //try: non-blocking attempt to take the keys 10. if could not get the car keys: 11. release the wallet 12. buy milk יהודה טוען שהאלגוריתם עשוי לא להסתיים, האם יהודה צודק? נמקו.

    Voluntary vs preemptive context switchPreemption trigger identificationMutex correctness and deadlock avoidance
  4. 5· short_answer· 5 pts

    (5 נק') שלומית שמה לב שהאלגוריתם לא מספיק חברתי ולכן החליטה לנסח אלגוריתם נוסף: 1. if (Yehuda): 2. while (no milk): 3. get the wallet 4. try to get the car keys 5. if could not get car keys: 6. release the wallet 7. else 8. buy milk 9. if (Shlomit): 10. while (no milk): 11. get the car keys 12. try to get the wallet 13. if could not get the wallet: 14. release the car keys 15. else 16. buy milk שלומית טוענת שלפחות אחד מהתנאים לקיום deadlock לא מתקיים כאן. יהודה טוען שהאלגוריתם עשוי לא להסתיים, מי צודק? נמקו.

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
2017B_Spring_AQ2core4 parts here

אלגוריתם הבנקאי

  1. א· calculation· 6 pts

    (6 נק') השלימו את הטבלה הבאה על-פי אלגוריתם הבנקאי בהנחה שתהליך P1 מבקש לנעול משאב אחד מסוג R1 R=)1,0,0( כלומר ,

    libc syscall wrapper caching pitfallsMutex correctness and deadlock avoidanceBanker's algorithm safety check
  2. ב· short_answer· 6 pts

    (6 נק') האם הדרישה של P1 תסופק על-ידי המערכת? אם כן, האם היא תסופק מיידית? הסבירו

    libc syscall wrapper caching pitfalls
  3. ג· calculation· 7 pts

    הסעיפים הבאים מתייחסים למצב מערכת התחלתי הנתון בתרשים הבא: (שימו לב לשינוי ב-R1, לעומת הסעיפים הקודמים) (7 נק') השלימו את הטבלה הבאה על-פי אלגוריתם הבנקאי בהנחה שתהליך P1 מבקש לנעול משאב אחד מסוג R1, R=)1,0,0( כלומר

    libc syscall wrapper caching pitfalls
  4. ד· short_answer· 6 pts

    (6 נק') האם הדרישה של P1 תסופק על-ידי המערכת? אם כן, האם היא תסופק מיידית? הסבירו

    libc syscall wrapper caching pitfalls
OS-Winter-2020-2021-examBQ1core2 parts here

סנכרון

  1. 4· short_answer· 4 pts

    דני הציע מימוש חדש לפונקצית barrier: void barrier(){ sem1.wait(); counter+=1; while(counter <= n); sem1.post(); } תארו את הבעייה בקוד הנתון

    SRT / preemptive Gantt construction
  2. 5· short_answer· 4 pts

    דני הסיק שהמימוש שלו בעייתי ולכן הציע מימוש חדש של פונקצית barrier: void barrier(){ sem1.wait(); counter+=1; sem1.post(); if (counter == n) sem2.post(); sem2.wait(); } תארו את הבעייה בקוד הנתון

    SRT / preemptive Gantt construction
examB-spring2020Q3corecritical2 parts here

סנכרון

  1. 2.b· mcq· 1 pts

    b. קיימת בעיית DeadLock / Livelock בקוד.

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
  2. 3.b· mcq· 2 pts

    b. קיימת בעיית DeadLock / Livelock בקוד.

    Mutex correctness and deadlock avoidanceBanker's algorithm safety check
2018A_Winter_AQ4core1 part here

חלק 4 - סינכרוניזציה

  1. 17· mcq· 6 pts

    (6 נק') האם הטענה של עידו נכונה? a. הטענה נכונה. שורה זו הכרחית רק במערכת מרובת ליבות כדי למנוע deadlock. b. הטענה נכונה. שורה זו הכרחית רק במערכת מרובת ליבות כדי להבטיח מניעה הדדית. c. הטענה נכונה. שורה זו הכרחית רק במערכת מרובת ליבות כדי להבטיח סדר ביצוע נכון. d. הטענה שגויה. ללא שורה זו שימוש במנעול עלול לגרום ל-deadlock. e. הטענה שגויה. ללא שורה זו המנעול לא מבטיח מניעה הדדית. f. הטענה שגויה. ללא שורה זו המעבד עלול לבצע את הפקודות בסדר לא נכון.

    libc syscall wrapper caching pitfallsMutex correctness and deadlock avoidanceBanker's algorithm safety check
2017B_Spring_AQ4core1 part here

סנכרוניזציה

  1. ג· short_answer· 5 pts

    כדי לשפר את התמיכה במערכת מרובת-ליבות, יוסי הציע להוסיף spinlocks לקוד של דני באופן הבא: spinlock_t aux_lock; int sys_global_lock() { spin_lock(aux_lock); while (global_lock != 0) wait_event_interruptible(global_queue, &global_lock); global_lock = 1; } int sys_global_unlock() { global_lock = 0; wake_up_interruptible(global_queue); spin_unlock(aux_lock); } (5 נק') כאשר יוסי בחן את הקוד המשופר (על מחשב בעל מספר ליבות) המנעול אכן עבד נכון, אך דני טען שכשהריץ את אותו הקוד (על מחשב בן ליבה אחת) מערכת ההפעלה נתקעה. מה גרם לתקלה במערכת של דני? נמקו.

    libc syscall wrapper caching pitfallsLocal vs global interrupt disableSpinlock implementation propertiesMutex correctness and deadlock avoidanceSRT / preemptive Gantt construction
OS-Spring2021-examBQ4core1 part here

סנכרון (Synchronization)

  1. g· code· 4 pts

    יונתן שינה את קוד הגרעין כך שהמנעול החדש משמש להגנה על תור הריצה ובנוסף הוא הוסיף קריאת מערכת חדשה שמדפיסה את כל התהליכים שנמצאים בתור הריצה: void print_rq_syscall() { lock(&rq_lock); // // print run queue // unlock(&rq_lock); } יונתן שם לב שבחלק מהמקרים, קריאת המערכת החדשה גורמת למחשב להיתקע. הסבירו למה זה קורה, הדגימו באמצעות תרחיש, והציעו דרך לתיקון הבעיה. נימוק:

    libc syscall wrapper caching pitfallsMutex correctness and deadlock avoidance