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

מצב של קיפאון (תיקו) בו תהליך א' דורש משאב הנמצא ברשות תהליך ב'. תהליך ב' לא ישחרר את המשאב עד שיקבל את המשאב הדרוש לו המוחזק על ידי תהליך א'

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

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

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

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

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

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

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

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

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

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

מניעת קיפאון

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

מניעה הדדית

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

החזק והמתן

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

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

לשתי הדרכים האלו יש שני חסרונות מרכזיים:

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

אין הפקעה

נוכל להסיר תנאי זה תוך שימוש באחת מהדרכים הבאות:

1. כאשר תהליך שכבר מחזיק מספר משאבים מבקש משאבים אחרים ובקשתו נדחית (ולכן הוא חייב להמתין), אזי כל המשאבים הישנים שכבר מוקצים עבורו יופקעו ממנו, וישוחררו מיידית. אותם משאבים מופקעים יתווספו לרשימת המשאבים שהתהליך ממתין להם. התהליך ישוב לפעול רק כאשר הוא יוכל לקבל את כל המשאבים: הישנים והחדשים.
2. כאשר תהליך מבקש משאבים והמשאבים אינם פנויים נבדוק מי מחזיק בהם. אם הם מוחזקים על ידי תהליך אחר שנמצא במצב המתנה (משום שממתין למשאבים אחרים), נפקיע מהתהליך האחר את המשאבים המבוקשים וניתן אותם לתהליך המבקש. לחלופין, אם המשאבים המבוקשים לא פנויים אך לא מוחזקים על ידי תהליך ממתין (כלומר מוחזקים על ידי תהליך רץ), התהליך המבקש יהיה חייב להמתין. בזמן שהוא ממתין ייתכן וחלק ממשאביו יופקעו, אך רק אם תהליך אחר מבקש אותם. התהליך ישוב לפעול רק כאשר קיבל את המשאבים החדשים שביקש וכן קיבל מחדש את המשאבים שהופקעו ממנו בזמן ההמתנה.

המתנה מעגלית

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

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

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

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

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

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

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

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

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

ראו גם

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