05-Threads_Synchronization_and_Deadlocks.md

חוטים, סנכרון וקיפאון (Threads, Synchronization, and Deadlocks)

🔑 מילון מונחים

• חוט (Thread): יחידת ביצוע עצמאית שחולקת מרחב זיכרון משותף עם חוטים אחרים באותו תהליך, אך מחזיקה הקשר ביצוע עצמאי (מחסנית ורגיסטרים).
• תנאי מרוץ (Race Condition): מצב שבו פלט התוכנית תלוי בסדר התזמון הלא-דטרמיניסטי של חוטים שניגשים לאותו משאב במקביל (מה שעלול להשחית נתונים).
• קטע קריטי (Critical Section): אזור בקוד הניגש למבנה נתונים משותף, שאסור ליותר מחוט אחד לבצע בו-זמנית.
• מניעה הדדית (Mutual Exclusion): דרישת חובה הקובעת שרק משימה אחת יכולה להיכנס לקטע הקריטי בכל רגע נתון.
• התקדמות (Progress): דרישת חובה שמונעת חוסר התקדמות – ההחלטה מי ייכנס לקטע הפנוי תתקבל ללא תלות בחוטים שאינם רוצים להיכנס.
• קיפאון (Deadlock): קבוצת תהליכים נמצאת בקיפאון אם כל תהליך בקבוצה ממתין למשאב שמוחזק על ידי תהליך אחר באותה הקבוצה.
• מצב בטוח (Safe State): מצב באלגוריתם הבנקאי שבו מובטח כי קיים סדר ביצוע תיאורטי אחד לפחות המאפשר לכל התהליכים לסיים את ריצתם, כך שניתן למנוע קיפאון בוודאות.

---

1. חוטים (Threads) בלינוקס

1.1. מה זה חוט?

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

• ממשק משתמש (pthreads): פונקציות POSIX בסיסיות (כמו pthread_create ליצירת חוט, ו-pthread_join המתנה לסיומו).
• איך זה עובד בגרעין (Kernel): לינוקס לא באמת מבדילה מהותית בין חוט לתהליך מנקודת מבטה התחתונה – שניהם מיוצגים תחת רשומות task_struct. לינוקס מממשת חוטים דרך קריאת המערכת clone. קריאה זו מאפשרת ליצור תהליך בן, תוך שליטה מדויקת אילו משאבים ישותפו עם האב באמצעות מסכת דגלים (Flags):
  • CLONE_VM: שיתוף מרחב הזיכרון.
  • CLONE_FILES: שיתוף טבלת הקבצים הפתוחים.
  • CLONE_FS: שיתוף נתוני עבודה עם קבצים (כמו ספריית עבודה נוכחית).
  • CLONE_THREAD: מכניס את התהליך החדש לאותה קבוצת חוטים (אותו tgid) של התהליך הקורא. שילוב של הדגלים הללו יחד הוא מה שיוצר בפועל את מה שאנחנו קוראים לו "חוט" במרחב המשתמש.
• TID לעומת PID: מזהה התהליך (PID) משותף לכולם, אך לצורכי מתזמן הגרעין (Scheduler) שמחלק זמן מעבד, לכל חוט יש מזהה חוט ייחודי משלו (TID). כאשר קוראים לפונקציה getpid, מה שחוזר בפועל הוא ה-tgid (מזהה קבוצת החוטים, שהוא ה-PID של החוט הראשי) ולכן הוא זהה לכל החוטים באותו תהליך. כדי לקבל את המזהה האמיתי והייחודי של החוט בגרעין, יש להשתמש ב-gettid.

⚠️ מלכודת מבחן: היררכיה ומיון מערך שאלה: האם קיימת היררכיית אב-בן בין חוטים באותו תהליך? תשובה: לא! בניגוד לתהליכים שיוצרים עץ היררכי ברור דרך fork, החוטים במערכת שקולים לחלוטין. שאלה: "האם ניתן לבצע מיון מערך מקבילי יעיל באמצעות תהליכים נפרדים?" תשובה: לא (בגלל אי-שיתוף הזיכרון של תהליכים הדורש תקשורת IPC כבדה) - זו קלאסיקה לשימוש בחוטים הניגשים ישירות לאותו מרחב הזיכרון.

---

2. מנגנוני סנכרון (Synchronization)

2.1. הבעיה: למה קוד תוכנתי לא מספיק?

🏦 הבעיה התיאורטית: יש בחשבון המשותף $50K. שני אנשים מושכים $20K ו-$30K בו-זמנית מהכספומט. ללא סנכרון הדוק, שניהם קוראים את היתרה במקביל, מבצעים חישוב ודורסים זה את זה ("התעדכנות אבודה").

🥛 הפתרון הנאיבי (בעיית ביונסה וג'יי-זי): ניסיון למנוע קניית חלב כפולה בעזרת כתיבת "פתק" (שימוש במשתנה דגל על ידי פקודות if ו-while בקוד C בלבד ללא מנעול).

💥 הכישלון הצורב בחומרה מודרנית: פתרון ה"פתק" נכשל לחלוטין! למה?

1. היררכיית הזיכרון ו-Cache Coherency: המעבד קורא מהמטמון המקומי שלו (L1, לוקח כ-4 מחזורי שעון) מהר מאוד, ולא בהכרח מיד רואה שמעבד אחר עדכן את הנתון בזיכרון הראשי (DRAM האיטי, כ-246 מחזורים).
2. Store Buffers (Cache Consistency): מעבדים מודרניים (Out-of-order) כותבים לחוצצי אחסון זמניים (Store Buffers) ומשנים את סדר הפעולות כדי לחסוך זמן עבודה יקר. חוט א' משאיר פתק (עדכון לזיכרון נתקע בחוצץ) $\to$ חוט א' מיד בודק אם לשני יש פתק, ומכיוון שהפתק שלו עצמו טרם פורסם לראווה בזיכרון הראשי, שניהם מפספסים זה את זה וכל הסינכרון נשבר.

🛠️ הפתרון האולטימטיבי בחומרה: חובה להשתמש בגדר זיכרון (Memory Fence / Barrier) כמו למשל הפקודה mfence ב-x86. פקודת חומרה זו מכריחה את המעבד לרוקן את כל חוצצי הכתיבה המעוכבים ולהפוך אותם לגלויים לפני שהוא ממשיך לשורת הקוד הבאה.

2.2. כלים נפוצים לפתרון סנכרון

כדי לממש "מניעה הדדית" כהלכה, משתמשים בפקודות חומרה אטומיות (כגון Compare-and-Swap או פקודת xchg) כבסיס עליו בנויים המנעולים:

סוג הכלי	מה הוא עושה כשהמשאב תפוס?	איפה משתמשים בו לרוב?	היתרון / החיסרון המרכזי
Spinlock (מנעול סחרור)	מבצע לולאת סרק אקטיבית (while(locked)) ושורף מחזורי שעון מעבד (Busy-waiting).	בעיקר בקוד הגרעין (Kernel) להגנה לזמן מיקרוסקופי (למשל מול פסיקות).	יתרון: חוסך לחלוטין את זמן התקורה (Overhead) של הרדמת התהליך והעברת הקשר. חיסרון: שורף מעבד לחינם אם זמן ההמתנה מתארך מעבר לזמן החלפת הקשר יחידה.
Semaphore (סמפור)	מוריד 1 ממונה. אם המונה יורד למינוס, התהליך נחסם ועובר לישון עמוק בתור הממתינים (Sleep Queue).	במרחב המשתמש, לסינכרון גס או ארוך, ולניהול משאבים בעלי מספר מופעים.	יתרון: המעבד מתפנה מיידית לטובת חוטים אחרים. חיסרון: תקורת החלפת הקשר כבדה מאוד. מימוש תוכנתי גרוע עלול ליצור מצב של "התעוררות אבודה".
Cond-Var (משתנה תנאי)	מאפשר לחוט לשחרר מנעול Mutex מקיף וללכת לישון בפעולה אטומית אחת בלתי ניתנת לקטיעה עד שמאירים אותו (cond_wait).	בבעיות אדריכליות כמו "יצרן-צרכן" (עם מבני נתונים מסוג Ring Buffer).	יתרון: פותר בצורה מושלמת המתנה מותנית. חיסרון (ומלכודת קוד!): חובה עליונה לעטוף את הבדיקה בתוך while ולא if בגלל סכנה של התעוררויות שווא וגניבת התנאי! (ראו הרחבה למטה).

⚠️ דגשים קריטיים לגבי משתני תנאי:

1. יציאה אטומית להמתנה: הפונקציה cond_wait מקבלת גם את המנעול כפרמטר מכיוון שהיא חייבת לשחרר את המנעול ולהעביר את החוט למצב המתנה באופן אטומי. אם זה לא היה אטומי, חוט אחר היה יכול לשלוח cond_signal בדיוק ברווח שבין שחרור המנעול ליציאה להמתנה, והאיתות היה הולך לאיבוד (מה שיוביל לקיפאון).
2. Mesa לעומת Hoare (למה חייבים while):
   • בסמנטיקת Mesa (הנפוצה והקיימת ב-Linux): הפעולה cond_signal רק מעירה את החוט הממתין, אך הוא חייב לנסות לתפוס מחדש את מנעול ה-Mutex לפני שימשיך. בזמן הקצר שבו הוא מתעורר ומנסה לתפוס את המנעול, חוט אחר עלול 'לרוץ' ולשנות את התנאי בחזרה. לכן חובה להשתמש בלולאת while כדי לבדוק שוב את התנאי לאחר ההתעוררות.
   • בסמנטיקת Hoare (כמעט ואינה בשימוש כי היא מסובכת למימוש): החוט המעורר מעביר את המנעול ישירות לחוט הממתין. במקרה כזה, החוט הממתין יכול להמשיך מיד כי הוא יודע שהתנאי בהכרח מתקיים, ולכן תנאי if רגיל היה מספיק.

⚠️ מלכודת מבחן אכזרית (פסיקות גרעין וספינלוקים):

• שימוש רגיל ב-Spinlock בתוך קוד הגרעין של לינוקס חושף אותנו לסכנת מוות (Deadlock עצמי): פסיקת חומרה עלולה לקפוץ, לקטוע אותנו באמצע כשאנחנו מחזיקים את המנעול, ואז שגרת הטיפול בפסיקה מנסה לקחת את אותו מנעול בדיוק כדי לבצע עבודתה - המערכת תקפא.
  • הפתרון הרשמי של מפתחי הגרעין: מנטרלים פסיקות חומרה על הליבה רגע לפני לקיחת הספינלוק. אולם, בתוך לולאת ה-Spin עצמה (אם גילינו שהמנעול תפוס ממילא על ידי ליבה אחרת ויש להמתין), חייבים להדליק את הפסיקות חזרה למיקרו-שנייה כדי לא לפגוע בתגובתיות המערכת ולתת לה לנשום, ואז לכבות שוב לסיבוב הבדיקה הבא!

2.3. מנעול קוראים-כותבים

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

הבדלי מימוש (הרצאה מול תרגול):

• מימוש ההרצאה (מבוסס סמפורים): משתמש בסמפורים (sRead, sWrite). חסרונו המרכזי הוא שהוא סובל מהרעבת כותבים: כל עוד קוראים ממשיכים להגיע, הם עוקפים את הכותבים הממתינים והמנעול לא ישתחרר.
• מימוש התרגול (מבוסס משתני תנאי ו-Mutex): משתמש במונה קוראים (readers_inside), מונה כותבים (writers_inside), מנעול גלובלי (global_lock), ושני משתני תנאי (read_allowed, write_allowed).
• פתרון התרגול להרעבת כותבים (מועד א' 2008): כדי לתת עדיפות לכותבים, התרגול מציג הוספה של משתנה writers_waiting. כאשר קורא חדש מנסה להיכנס, הוא ייחסם וימתין (יבצע cond_wait) לא רק אם יש כותב בפנים (writers_inside > 0), אלא גם אם יש כותב שממתין בתור (writers_waiting > 0). כך מובטח שכותבים שהגיעו יכנסו תמיד לפני קוראים חדשים.

2.4. חוק אמדל (Amdahl's Law)

הגבול המתמטי הקשיח של עולם המקביליות שניסח אמדל ב-1967:

$$ Speedup \leq \frac{T_1}{T_n} = \frac{1}{s + \frac{1-s}{n}} \leq \frac{1}{s} $$

• $n$ = מספר הליבות.
• $s$ = אחוז הקוד ש-חייב להישאר סדרתי ואקסקלוסיבי (החלק שלא ניתן למקבול כלל בגלל מנעולים כבדים).
• המסקנה הקריטית: גם במצב האוטופי של צירוף אינסוף ליבות מחשב ($\infty \to n$), המערכת הכללית תמיד מוגבלת על ידי צוואר הבקבוק הסדרתי שלה ולעולם לא תואץ ליותר מהחסם $\frac{1}{s}$.

2.5. סינכרון מסלולי בקרה בגרעין לינוקס

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

הגנה על מבני נתונים בגרעין:

• אם מבנה הנתונים נגיש גם לקריאות מערכת/חריגות וגם לפסיקות חומרה:
  • מעבד יחיד (Single-Core): מספיק להשתמש בנטרול פסיקות מקומי (כיבוי הדגל IF). אסור להשתמש במנעול כי אם פסיקת חומרה תקטע תהליך שמחזיק במנעול, והיא תנסה לקחת את אותו מנעול - נקבל קיפאון מידי.
  • מרובה מעבדים (Multi-Core): חובה להשתמש בנטרול פסיקות מקומי + מנעול Spinlock. משתמשים ב-Spinlock ולא בסמפור מכיוון שבהמתנות קצרות מאוד כמו בגרעין, עדיף "לשרוף" מעבד מאשר לשלם את מחיר החלפת ההקשר של סמפור. כמו כן, מנעולים שישנים (כמו סמפור) אסורים לחלוטין בתוך שגרת טיפול בפסיקת חומרה.
• אם מבנה הנתונים נגיש אך ורק לקריאות מערכת/חריגות (ולא לפסיקות):
  • ניתן ורצוי להשתמש בסמפור / מנעול Mutex גם במעבד יחיד וגם במרובה מעבדים, מכיוון שקריאות מערכת רשאיות ללכת לישון ולוותר על המעבד.

---

3. קיפאון (Deadlocks)

קיפאון יתרחש רק בתנאי שארבעת החוקים הבאים מופרים או מתקיימים במערכת בו-זמנית במדויק:

1. מניעה הדדית (Mutual Exclusion): המשאבים ננעלים בבלעדיות (למשל מנעול מבוסס חומרה או סמפור בינארי).
2. החזקה והמתנה (Hold & Wait): תהליך כבר הצליח לרכוש ולאחוז לפחות במשאב אחד, ובמקביל הוא נעמד וממתין למשאבים נוספים המוחזקים בידי אחרים.
3. המתנה מעגלית (Circular Wait): תהליך ממוספר במעגל סגור של תלויות משאבים.
4. היעדר הפקעה (No Resource Preemption): מערכת ההפעלה אינה מפקיעה משאבים בכוח מתהליכים שמחזיקים בהם. המשאב משוחרר רק בסוף הריצה מרצון.

3.1. גרף הקצאת משאבים וזיהוי הקיפאון

מודל שבו העיגול הוא התהליך, והמרובע הוא המשאב (הנקודות בפנים מראות מופעים זמינים). חץ מתהליך למשאב משמעו בקשת משאב; חץ ממשאב לתהליך מסמל הקצאה תקינה בפועל.

⚠️ מלכודת מבחן - האם מציאת מעגל מחייבת קיפאון? התשובה נחלקת לשניים:

• אם לכל משאב המעורב במעגל יש מופע יחיד (למשל מנעול קלאסי בודד) $\to$ כן במובהק! המעגל מהווה תנאי הכרחי וגם מספיק. יש קיפאון ודאי.
• אם למשאבים בגרף יש מספר מופעים פוטנציאליים $\to$ לא בהכרח! המעגל הוא תנאי הכרחי לקיפאון אך לחלוטין לא מספיק. ייתכן מצב שבו תהליך הניצב מחוץ למעגל משתמש ברגעים אלו במופע חופשי אחר, הוא עתיד לסיים ריצה ולשחרר את מופע המשאב שלו ובכך לשבור את מעגל ההמתנה לכולם!

3.2. טבלת השוואה: 3 הגישות למלחמה ב-Deadlock

רוב מערכות ההפעלה נוטות להתנער מאחריות הקיפאון ומטילות זאת על מתכנתי המרחב-משתמש (בשל תקורת חישוב). המערכת התיאורטית מציעה 3 אסטרטגיות-על:

גישה מרכזית	איך היא עובדת בפועל?	מה החיסרון (המחיר)?	דוגמה קלאסית שמציגים לרוב
1. מניעה מראש (Prevention)	מוודאת מתמטית על סמך תקנון מוקדם שלפחות אחד מ-4 התנאים יופר תמיד ולכן הקיפאון אינו פיזיקלי.	סופר נוקשה, קשה לתכנות דינמי, ופוגע במקביליות משמעותית.	ביטול המתנה מעגלית (הנפוץ מכולם): ממספרים מספרית את כל המשאבים במערכת. כל חוט שמבקש מספר משאבים חייב לבקשם בסדר מספרי עולה בלבד. (ההוכחה: אם היה מעגל היינו מקבלים $M(0) < M(0)$ שזו סתירה מוחלטת השוברת מעגלים!).
2. הימנעות דינמית (Avoidance)	אלגוריתם שמרני הדוגם דינמית כל בקשה חדשה. אם הבקשה מייצרת פוטנציאל לסיכון ארוך טווח בסימולציה, היא מסורבת גם אם המשאב פנוי ממש ברגע זה.	מחייב אותנו לדעת מראש מהי "הדרישה המקסימלית" הסופית של כל תהליך. זמן סימולציה יקר למערכת ההפעלה שפועל בסיבוכיות $O(n^2)$.	אלגוריתם הבנקאי של דייקסטרה (פירוט והרחבה אודותיו מיד למטה).
3. גילוי והתאוששות (Detect & Recover)	מאפשרים לחסימות להיווצר ולקפוא במערכת באופן חופשי! במקביל מריצים סורק מעגלים בתזמונים נמוכים ברקע, וכשמוצאים, מפעילים הפקעות.	מציאת קבוצה מינימלית או אופטימלית של תהליכים להריגה או משאבים להפקעה היא בעיה אלגוריתמית קשה מאוד. הריגת תהליכים לא-נכונים עלולה להשחית דאטה.	מנגנון ההגנה הקיצוני OOM Killer של גרעין לינוקס, הממית תהליכי משתמש באקראי בעת מיצוי זיכרון RAM מלא בכדי להתאושש מהקריסה.

3.3. אלגוריתם הבנקאי (Banker's Algorithm)

אלגוריתם הבנקאי מבוסס על מצב שבו יש $n$ תהליכים ו-$k$ סוגי משאבים (שלכל אחד עשויים להיות מספר מופעים).

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

• $max[p]$: וקטור המייצג את הדרישה המקסימלית של תהליך $p$ לכל אחד מ-$k$ סוגי המשאבים לאורך כל חייו.
• $cur[p]$: וקטור המייצג את ההקצאה הנוכחית של משאבים שכבר ניתנו לתהליך $p$. תמיד יתקיים ש-$cur[p] \le max[p]$.
• $Need[p]$: וקטור הדרישה העתידית, המחושב כ-$max[p] - cur[p]$. זהו המקסימום שתהליך $p$ עוד עלול לבקש.
• $avail$: וקטור גלובלי המייצג את כמות המשאבים הפנויים כרגע במערכת מכל סוג.

שלבי בדיקת בקשה ($R$) מאת תהליך $q$:

1. בדיקת תקינות ראשונית: האם הבקשה חורגת מהמקסימום שהוצהר ($R \le Need[q]$)? אם כן, זו שגיאה.
2. בדיקת זמינות: האם המשאבים זמינים כרגע ($R \le avail$)? אם לא, התהליך יחסם וימתין.
3. הקצאה על-תנאי (סימולציה): האלגוריתם "מעמיד פנים" שהקצה את המשאב, ומעדכן באופן זמני:
   • $cur[q] = cur[q] + R$
   • $avail = avail - R$
4. בדיקת מצב בטוח (Safe State Check): כעת המערכת בודקת האם המצב החדש בטוח.

איך עובדת בדיקת המצב הבטוח ($O(n^2)$):

• מגדירים קבוצה $P$ של כל התהליכים שטרם סיימו.
• מחפשים בתוך $P$ תהליך $p$ שעבורו $Need[p] \le avail$ (כלומר, גם אם התהליך יבקש ברגע זה את כל שאר המשאבים שהוא אי פעם יצטרך, עדיין נוכל לספק לו אותם מהמאגר הפנוי).
• אם נמצא תהליך כזה, אנחנו יודעים שהוא בטוח יצליח לסיים. אנו מדמים את סיומו, מוציאים אותו מ-$P$, ומחזירים את המשאבים שלו לבריכה הפנויה: $avail = avail + cur[p]$. מטרת ההחזרה היא לשקף שסיום התהליך משחרר משאבים למערכת.
• חוזרים על התהליך עד ש-$P$ ריקה. אם רוקנו את $P$, המצב בטוח והבקשה האמיתית תאושר. אם נתקענו ללא יכולת למצוא תהליך שעומד בתנאי (ויש תהליכים שטרם סיימו), המצב אינו בטוח. הבקשה המקורית נדחית והסימולציה מבוטלת.

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

תרשים זרימה של סימולציית מצב בטוח (Safe State):

flowchart TD
    A[בקשה R הגיעה למערכת] --> B(בדיקת היתכנות: נניח זמנית שאישרנו וניתן את המשאבים ל-Cur ונחסיר מ-Avail)
    B --> C{האם קיים תהליך כלשהו שדרישתו הנותרת <br> Need <= Avail ?}
    C -- כן (נמצא תהליך שמסוגל לסיים!) --> D(סימולציה חכמה: נדמה שהתהליך מסיים בהצלחה <br> ומחזיר אוטומטית את משאבי ה-Cur שלו לבריכת ה-Avail הכללית)
    D --> E{האם נשארו עוד תהליכים במערכת?}
    E -- כן --> C
    E -- לא (כולם הצליחו לסיים!) --> F((המצב נחשב בטוח לחלוטין - Safe State <br> הבקשה האמיתית מאושרת רשמית))
    C -- לא (נתקענו במבוי סתום. המשאבים לא מספיקים לאף אחד) --> G((המערכת תגיע לסכנה <br> הבקשה נדחית! התהליך יאלץ להמתין למרות שהמשאב פנוי כעת))

Loading