קיפאון (מדעי המחשב)

תנאים הכרחיים לקיפאון

קיפאון יתרחש רק אם ארבעת התנאים הבאים יתרחשו במקביל:
1. מניעה הדדית (mutual exclusion): לפחות אחד מהמשאבים הוא אינו שיתופי. במילים אחרות, ברגע נתון רק תהליך אחד יוכל להשתמש במשאב הזה.
2. החזק והמתן (hold and wait): כל תהליך מחזיק לפחות במשאב אחד ומחכה למשאב אחר נוסף שכרגע בשימוש על ידי תהליך אחר. 
3. אין הפקעה (no preemption): המשאבים לא מופקעים מהתהליכים שמשתמשים בהם. במילים אחרות, משאב יכול להשתחרר רק על ידי התהליך שמחזיק בו, אחרי שאותו תהליך השלים את עבודתו.
4. המתנה מעגלית (circular wait): קיימת קבוצת תהליכים ממתינים {p₀,p₁,...,pₙ}, כך שכל תהליך pᵢ ממתין למשאב שמוחזק על ידי תהליך pᵢ₊₁. תהליך pₙ ממתין למשאב שמוחזק על ידי p₀. באופן כזה, קבוצת התהליכים יוצרת מעגל בו כל תהליך מחכה למשאב המוחזק על ידי תהליך אחר.

דרכי התמודדות עם קיפאון

ישנן שלוש גישות עיקריות בהן משתמשים להתמודד עם בעיית הקיפאון. 
1. מניעה והתחמקות. בגישה זו מוודאים שמערכת ההפעלה לעולם לא תיכנס למצב קיפאון. שיטות המניעה מוודאות שלפחות אחד מארבעת התנאים ההכרחיים לקיפאון לא יתרחש. שיטות ההתחמקות דורשות שמערכת ההפעלה תקבל מידע נוסף מראש בנוגע לאלו משאבים יבקש כל תהליך. עם הידע הזה, היא תוכל להחליט עבור כל בקשה האם התהליך ימתין או לא: אם בזמן הבקשה המערכת תזהה פוטנציאל למצב קיפאון, התהליך לא יקבל את המשאב אלא ימתין שהמצב ישתנה והמערכת תגיע למצב בטוח יותר בו לא יתאפשר קיפאון.
2. זיהוי והתאוששות. בגישה זו מאפשרים למערכת להיכנס למצב קיפאון, מאבחנים זאת, ומשחררים אותו. מערכת ההפעלה מספקת אלגוריתמים שבוחנים את מצבה ומחליטים האם התרחש קיפאון. כמו כן היא מספקת אלגוריתמים לטיפול והתאוששות מאותו קיפאון.
3.  התעלמות. בגישה זו לא מתייחסים כלל לאפשרות הקיפאון. אפשרות זו נמצאת בשימוש ברוב מערכות ההפעלה, ביניהן Windows ו-Unix. במערכות כאלו זה באחריות המתכנת לכתוב תוכנית שמתמודדת עם קיפאון. במידה ויתרחש קיפאון המערכת לא תוכל לזהות זאת. הקיפאון יביא להאטה בביצועי המערכת. יותר ויותר תהליכים יוקפאו כשיבקשו משאבים ולבסוף המשתמש יאלץ לאתחל את המערכת. עם זאת, במערכות רבות מצב קיפאון הוא נדיר מאוד ולכן השיטה הזו זולה יותר מאשר האלגוריתמים למניעה, התחמקות או זיהוי והתאוששות.

מניעת קיפאון

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

מניעה הדדית

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

המתנה מעגלית

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

התחמקות מקיפאון

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

נאמר שמצב הוא בטוח אם המערכת יכולה להקצות משאבים לכל תהליך בסדר מסוים ועדיין למנוע קיפאון. במילים אחרות, מערכת נמצאת במצב בטוח רק אם קיים רצף תהליכים בטוח, שהינו רצף p₀,p₁,...,pₙ בו תהליך pᵢ
יבקש בעתיד רק משאבים שהם כרגע פנויים או מוחזקים על ידי תהליך pⱼ, כך ש j<i. אם המשאבים שpᵢ מבקש תפוסים, הוא ימתין עד ש pⱼ ישחרר אותם.
אם לא ניתן לסדר את התהליכים ברצף כזה, נאמר שהמערכת במצב לא בטוח, שעלול להסתיים בקיפאון. ההבחנה בין המצבים מתייחסת ליכולת של המערכת להגיע למצב קיפאון. ישנם אלגוריתמים שמוודאים שהמערכת תשאר תמיד במצב בטוח. כל פעם שתהליך מבקש משאב פנוי הם מחליטים האם הוא יקבל אותו (כי המערכת תישאר במצב בטוח) או שהתהליך ימתין. בשיטה זו ייתכן ותהליך ימתין גם אם המשאב פנוי ולכן ניצול המשאבים בשיטת ההתחמקות הוא נמוך יותר.

אלגוריתם שממש התחמקות מקיפאון הוא אלגוריתם הבנקאי.

חיזוי וכריעות

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

איתור קיפאון קיים

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