קיפאון (מדעי המחשב) – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה אחרונה מ־08:18, 15 באוגוסט 2024

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

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

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

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

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

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

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

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

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

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

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

מניעת קיפאון

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

מניעה הדדית

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

החזק והמתן

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

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

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

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

אין הפקעה

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

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

המתנה מעגלית

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

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

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

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

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

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

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

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

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

ראו גם

הערות שוליים

^ Ekta Walia, Operating System Concepts, Khanna Publishing House, 2015, עמ' 122, ISBN 978-93-80016-65-8. (באנגלית)
^ D. M. Dhamdhere, Operating Systems: A Concept-based Approach,2E, Tata McGraw-Hill Education, 2006-05-01, עמ' 687, ISBN 978-0-07-061194-8. (באנגלית)
^ Ekta Walia, Operating System Concepts, Khanna Publishing House, 2015, עמ' 123, ISBN 978-93-80016-65-8. (באנגלית)
^ ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE, Operating System Concepts, 8th Edition, John Wiley & Sons, 2008, עמ' 290. (באנגלית)
^ ¹ ² ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE, Operating System Concepts, 8th Edition, John Wiley & Sons, 2008, עמ' 291. (באנגלית)
^ ¹ ² ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE, Operating System Concepts, 8th Edition, John Wiley & Sons, 2008, עמ' 292. (באנגלית)

[1] Ekta Walia, Operating System Concepts, Khanna Publishing House, 2015, עמ' 122, ISBN 978-93-80016-65-8. (באנגלית)

[2] D. M. Dhamdhere, Operating Systems: A Concept-based Approach,2E, Tata McGraw-Hill Education, 2006-05-01, עמ' 687, ISBN 978-0-07-061194-8. (באנגלית)

[3] Ekta Walia, Operating System Concepts, Khanna Publishing House, 2015, עמ' 123, ISBN 978-93-80016-65-8. (באנגלית)

[4] ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE, Operating System Concepts, 8th Edition, John Wiley & Sons, 2008, עמ' 290. (באנגלית)

[:0-5] ¹ ² ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE, Operating System Concepts, 8th Edition, John Wiley & Sons, 2008, עמ' 291. (באנגלית)

[:1-6] ¹ ² ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE, Operating System Concepts, 8th Edition, John Wiley & Sons, 2008, עמ' 292. (באנגלית)

[1]

[2]

[3]

[4]

[5]

[6]

@@ שורה 1: / שורה 1: @@
-{{מחפש מקורות}}
+{{מקורות|רמה=מחפש|נושא=מחשוב}}
-[[קובץ:Deadlock.png|ממוזער|250px|שמאל|מצב של קיפאון(תיקו) בו תהליך א' דורש משאב הנמצא ברשות תהליך ב'. תהליך ב' לא ישחרר את המשאב עד שיקבל את המשאב הדרוש לו המוחזק על ידי תהליך א']]
+[[קובץ:Deadlock.png|ממוזער|250px|שמאל|מצב של קיפאון (תיקו) בו תהליך א' דורש משאב הנמצא ברשות תהליך ב'. תהליך ב' לא ישחרר את המשאב עד שיקבל את המשאב הדרוש לו המוחזק על ידי תהליך א']]
 '''קיפאון''' (או תיקו, ב[[אנגלית]]: '''Deadlock''') הוא מצב בו שתי פעולות מתחרות מחכות כל אחת לסיומה של האחרת, ומכיוון שכך, אף אחת מהן אינה מסתיימת. דוגמה: שני אנשים עומדים בפתחה של דלת, וכל אחד מהם מציע לרעהו את הזכות להיכנס ראשון. אם יתמידו בגישתם זו, לא יעברו לעולם בדלת.
-בענף המחשבים, '''קיפאון''' מתייחס למצב בו שני [[תהליך (מדעי המחשב)|תהליכים]] (או יותר) מחכים האחד לאחר לשחרורו של [[משאב מערכת|משאב]], או למצב בו יותר משני תהליכים מחכים למשאבים בשרשרת מעגלית. דוגמה: תהליך א' נועל את משאב A וממתין לשחרורו של משאב B, משום שהוא זקוק לשני משאבים אלה יחדיו לשם השלמת פעולתו. באותו זמן תהליך ב' נועל את משאב B וממתין לשחרורו של משאב A, משום שגם שהוא זקוק לשני משאבים אלה יחדיו לשם השלמת פעולתו. בקשת הנעילה היא [[פעולה חוסמת]] ועל כן שני התהליכים הפעילו פעולות שלא יחזרו עד שישוחרר המשאב שביקשו לנעול. אך כיוון שהתהליך שמחזיק במשאב נמצא במצב דומה - הוא לא יכול לשחרר את המשאב ומכאן ששני התהליכים תקועים.
+בענף המחשבים, '''קיפאון''' מתייחס למצב בו שני [[תהליך (מדעי המחשב)|תהליכים]] מחכים האחד לאחר לשחרורו של [[משאב מערכת|משאב]], או למצב בו יותר משני תהליכים מחכים למשאבים בשרשרת מעגלית. דוגמה: תהליך א' נועל את משאב A וממתין לשחרורו של משאב B, משום שהוא זקוק לשני משאבים אלה יחדיו לשם השלמת פעולתו. באותו זמן תהליך ב' נועל את משאב B וממתין לשחרורו של משאב A, משום שגם שהוא זקוק לשני משאבים אלה יחדיו לשם השלמת פעולתו. בקשת הנעילה היא [[פעולה חוסמת]] ועל כן שני התהליכים הפעילו פעולות שלא יחזרו עד שישוחרר המשאב שביקשו לנעול. אך כיוון שהתהליך שמחזיק במשאב נמצא במצב דומה - הוא לא יכול לשחרר את המשאב ומכאן ששני התהליכים תקועים<ref>{{צ-ספר|שם=Operating System Concepts|קישור=https://books.google.co.il/books?id=saoEEAAAQBAJ&dq=Operating+System+Concepts+deadlock&hl=iw&source=gbs_navlinks_s|מו"ל=Khanna Publishing House|שנת הוצאה=2015|ISBN=978-93-80016-65-8|מחבר=Ekta Walia|שפה=en|עמ=122}}</ref>.
 קיפאון הוא בעיה נפוצה בתחום ה[[עיבוד מקבילי|עיבוד המקבילי]] שבו תהליכים רבים משתפים משאבים באמצעות מנגנון הידוע כ'[[מנעול (מדעי המחשב)|מנעול]] תוכנה' או 'מנעול רך'. במערכות מחשב המיועדות לפעול תחת אילוצי [[זמן אמת]], ישנו לרוב התקן [[חומרה]] הנקרא 'מנעול קשה' המבטיח [[מנעול קריאה כתיבה|גישה בלעדית]] לתהליכים ומניעת מצבי [[הרעבה (מדעי המחשב)|הרעבה]], על ידי כפיית סדר עיבוד.
 מצבי קיפאון הם מטרידים ביותר מכיוון שאין פתרון כללי למניעתם.
-על [[מתכנת]]ים לנסות ולכתוב [[תוכנית מחשב|תוכניות]] שלא ייתכנו בהם כלל מצבי קיפאון. תוכניות כאלה נקראות תוכניות שיש להן '''חָיות''' (liveness).
+על [[מתכנת]]ים לנסות ולכתוב [[תוכנית מחשב|תוכניות]] שלא ייתכנו בהם כלל מצבי קיפאון. תוכניות כאלה נקראות תוכניות שיש להן '''חָיות''' (liveness)<ref>{{צ-ספר|שם=Operating Systems: A Concept-based Approach,2E|קישור=https://books.google.co.il/books?id=kbBn4X9x2mcC&dq=operating+systems+liveness&hl=iw&source=gbs_navlinks_s|מו"ל=Tata McGraw-Hill Education|שנת הוצאה=2006-05-01|ISBN=978-0-07-061194-8|מחבר=D. M. Dhamdhere|שפה=en|עמ=687}}</ref>.
 == תנאים הכרחיים לקיפאון ==
-קיפאון יתרחש רק אם ארבעת התנאים הבאים יתרחשו במקביל:
+קיפאון יתרחש רק אם ארבעת התנאים הבאים יתרחשו במקביל<ref>{{צ-ספר|שם=Operating System Concepts|קישור=https://books.google.co.il/books?id=saoEEAAAQBAJ&dq=Operating+System+Concepts+deadlock&hl=iw&source=gbs_navlinks_s|מו"ל=Khanna Publishing House|שנת הוצאה=2015|ISBN=978-93-80016-65-8|מחבר=Ekta Walia|שפה=en|עמ=123}}</ref>:
+#'''[[מניעה הדדית]] (mutual exclusion):''' לפחות אחד מהמשאבים הוא אינו שיתופי. במילים אחרות, ברגע נתון רק תהליך אחד יוכל להשתמש במשאב הזה.
+#'''החזק והמתן (hold and wait):''' כל תהליך מחזיק לפחות במשאב אחד ומחכה למשאב אחר נוסף שכרגע בשימוש על ידי תהליך אחר.
+#'''אין הפקעה (no preemption):''' המשאבים לא מופקעים מהתהליכים שמשתמשים בהם. במילים אחרות, משאב יכול להשתחרר רק על ידי התהליך שמחזיק בו, אחרי שאותו תהליך השלים את עבודתו.
+#'''המתנה מעגלית (circular wait):''' קיימת קבוצת תהליכים ממתינים {p<sub>0</sub>,p<sub>1</sub>,...,p<sub>n</sub>}, כך שכל תהליך p<sub>i</sub> ממתין למשאב שמוחזק על ידי תהליך p<sub>i+1</sub>. תהליך p<sub>n</sub> ממתין למשאב שמוחזק על ידי p<sub>0</sub>. באופן כזה, קבוצת התהליכים יוצרת מעגל בו כל תהליך מחכה למשאב המוחזק על ידי תהליך אחר.
+== דרכי התמודדות עם קיפאון ==
-. '''[[מניעה הדדית]] (mutual exclusion):''' לפחות אחד מהמשאבים הוא אינו שיתופי. במילים אחרות, ברגע נתון רק תהליך אחד יוכל להשתמש במשאב הזה.
+ישנן שלוש גישות עיקריות בהן משתמשים להתמודד עם בעיית הקיפאון<ref>{{צ-ספר|שם=Operating System Concepts, 8th Edition|קישור=https://books.google.co.il/books?id=2YdRzQEACAAJ&dq=Operating+System+Concepts+8th&hl=iw&sa=X&redir_esc=y|מו"ל=John Wiley & Sons|שנת הוצאה=2008|מחבר=ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE|שפה=en|עמ=290}}</ref>:
+#'''מניעה והתחמקות'''. בגישה זו מוודאים שמערכת ההפעלה ''לעולם'' לא תיכנס למצב קיפאון. שיטות ה'''מניעה''' מוודאות שלפחות אחד מארבעת התנאים ההכרחיים לקיפאון לא יתרחש. שיטות ה'''התחמקות''' דורשות שמערכת ההפעלה תקבל מידע נוסף מראש בנוגע לאלו משאבים יבקש כל תהליך. עם הידע הזה, היא תוכל להחליט עבור כל בקשה האם התהליך ימתין או לא: אם בזמן הבקשה המערכת תזהה פוטנציאל למצב קיפאון, התהליך לא יקבל את המשאב אלא ימתין שהמצב ישתנה והמערכת תגיע למצב בטוח יותר בו לא יתאפשר קיפאון.
-. '''החזק והמתן (hold and wait):''' כל תהליך מחזיק לפחות במשאב אחד ומחכה למשאב אחר נוסף שכרגע בשימוש על ידי תהליך אחר.
+#'''זיהוי והתאוששות'''. בגישה זו מאפשרים למערכת להיכנס למצב קיפאון, מאבחנים זאת, ומשחררים אותו. מערכת ההפעלה מספקת אלגוריתמים שבוחנים את מצבה ומחליטים האם התרחש קיפאון. כמו כן היא מספקת אלגוריתמים לטיפול והתאוששות מאותו קיפאון.
+#''' התעלמות'''. בגישה זו לא מתייחסים כלל לאפשרות הקיפאון. אפשרות זו נמצאת בשימוש ברוב מערכות ההפעלה, ביניהן [[Windows]] ו-[[UNIX|Unix]]. במערכות כאלו זה באחריות המתכנת לכתוב תוכנית שמתמודדת עם קיפאון. במידה ויתרחש קיפאון המערכת לא תוכל לזהות זאת. הקיפאון יביא להאטה בביצועי המערכת. יותר ויותר תהליכים יוקפאו כשיבקשו משאבים ולבסוף המשתמש יאלץ לאתחל את המערכת. עם זאת, במערכות רבות מצב קיפאון הוא נדיר מאוד ולכן השיטה הזו זולה יותר מאשר האלגוריתמים למניעה, התחמקות או זיהוי והתאוששות.
-. '''אין הפקעה (no preemption):''' המשאבים לא מופקעים מהתהליכים שמשתמשים בהם. במילים אחרות, משאב יכול להשתחרר רק על ידי התהליך שמחזיק בו, אחרי שאותו תהליך השלים את עבודתו.
-. '''המתנה מעגלית (circular wait):''' קיימת קבוצת תהליכים ממתינים {p<sub>0</sub>,p<sub>1</sub>,...,p<sub>n</sub>}, כך שכל תהליך p<sub>i</sub> ממתין למשאב שמוחזק על ידי תהליך p<sub>i+1</sub>. תהליך p<sub>n</sub> ממתין למשאב שמוחזק על ידי p<sub>0</sub>. באופן כזה, קבוצת התהליכים יוצרת מעגל בו כל תהליך מחכה למשאב המוחזק על ידי תהליך אחר.
-== דרכי התמודדות עם קיפאון==
-ישנן שלוש גישות עיקריות בהן משתמשים להתמודד עם בעיית הקיפאון.
-. '''מניעה והתחמקות'''. בגישה זו מוודאים שמערכת ההפעלה ''לעולם'' לא תיכנס למצב קיפאון. שיטות ה'''מניעה''' מוודאות שלפחות אחד מארבעת התנאים ההכרחיים לקיפאון לא יתרחש. שיטות ה'''התחמקות''' דורשות שמערכת ההפעלה תקבל מידע נוסף מראש בנוגע לאלו משאבים יבקש כל תהליך. עם הידע הזה, היא תוכל להחליט עבור כל בקשה האם התהליך ימתין או לא: אם בזמן הבקשה המערכת תזהה פוטנציאל למצב קיפאון, התהליך לא יקבל את המשאב אלא ימתין שהמצב ישתנה והמערכת תגיע למצב בטוח יותר בו לא יתאפשר קיפאון.
-. '''זיהוי והתאוששות'''. בגישה זו מאפשרים למערכת להיכנס למצב קיפאון, מאבחנים זאת, ומשחררים אותו. מערכת ההפעלה מספקת אלגוריתמים שבוחנים את מצבה ומחליטים האם התרחש קיפאון. כמו כן היא מספקת אלגוריתמים לטיפול והתאוששות מאותו קיפאון.
-. ''' התעלמות'''. בגישה זו לא מתייחסים כלל לאפשרות הקיפאון. אפשרות זו נמצאת בשימוש ברוב מערכות ההפעלה, ביניהן [[Windows]] ו-[[UNIX|Unix]]. במערכות כאלו זה באחריות המתכנת לכתוב תוכנית שמתמודדת עם קיפאון. במידה ויתרחש קיפאון המערכת לא תוכל לזהות זאת. הקיפאון יביא להאטה בביצועי המערכת. יותר ויותר תהליכים יוקפאו כשיבקשו משאבים ולבסוף המשתמש יאלץ לאתחל את המערכת. עם זאת, במערכות רבות מצב קיפאון הוא נדיר מאוד ולכן השיטה הזו זולה יותר מאשר האלגוריתמים למניעה, התחמקות או זיהוי והתאוששות.
 ===מניעת קיפאון===
-בשביל שקיפאון יתרחש, כל אחד מאותם ארבעת התנאים ההכרחיים צריך להתקיים. אם נודא שלפחות אחד מהם לא יתרחש, נמנע קיפאון. שיטה זו עלולה להתבטא בניצול נמוך של משאבי המערכת והקטנת התפוקה.
+בשביל שקיפאון יתרחש, כל אחד מאותם ארבעת התנאים ההכרחיים צריך להתקיים. אם נוודא שלפחות אחד מהם לא יתרחש, נמנע קיפאון. שיטה זו עלולה להתבטא בניצול נמוך של משאבי המערכת והקטנת התפוקה.
 ====מניעה הדדית====
-את התנאי הראשון, הקצאות מניעה הדדית, לא נוכל למנוע תמיד. ישנם משאבים שמעצם אופיים הם לא שיתופיים ואי אפשר לבטל את הבלעדיות שלהם, כמו מדפסת שיכולה להדפיס ברגע נתון רק מסמך אחד. לעומת זאת, ישנם משאבים שיתופיים שאינם דורשים בלעדיות. כך לדוגמה, מקובץ לקריאה בלבד יכולים לקרוא בו זמנית מספר תהליכים שונים. בכל מקרה, לא נוכל למנוע קיפאון תוך הסרת תנאי זה, משום שלא נוכל לבטל את הבלעדיות, שהינה מהותית עבור חלק מהמשאבים.
+את התנאי הראשון, הקצאות מניעה הדדית, לא נוכל למנוע תמיד. ישנם משאבים שמעצם אופיים הם לא שיתופיים ואי אפשר לבטל את הבלעדיות שלהם, כמו מדפסת שיכולה להדפיס ברגע נתון רק מסמך אחד. לעומת זאת, ישנם משאבים שיתופיים שאינם דורשים בלעדיות. כך לדוגמה, מקובץ לקריאה בלבד יכולים לקרוא בו זמנית מספר תהליכים שונים. בכל מקרה, לא נוכל למנוע קיפאון תוך הסרת תנאי זה, משום שלא נוכל לבטל את הבלעדיות, המהותית עבור חלק מהמשאבים<ref name=":0">{{צ-ספר|שם=Operating System Concepts, 8th Edition|קישור=https://books.google.co.il/books?id=2YdRzQEACAAJ&dq=Operating+System+Concepts+8th&hl=iw&sa=X&redir_esc=y|מו"ל=John Wiley & Sons|שנת הוצאה=2008|מחבר=ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE|שפה=en|עמ=291}}</ref>.
 ==== החזק והמתן====
-בשביל לודא שתנאי זה לעולם לא יתקיים, נודא שכשאשר תהליך מבקש משאב הוא לא מחזיק שום משאב אחר. ניתן לממש זאת באחת משתי דרכים:
+בשביל לוודא שתנאי זה לעולם לא יתקיים, נוודא שכשאשר תהליך מבקש משאב הוא לא מחזיק שום משאב אחר. ניתן לממש זאת באחת משתי דרכים<ref name=":0" />:
 # לדרוש מהתהליכים לבקש את כל המשאבים שהם רוצים לפני תחילת הריצה. ניתן לממש זאת באמצעות הוספת דרישה שכל קריאות המערכת הדורשות משאבים יקדימו את קריאות המערכת האחרות.
 # לאפשר לתהליך לבקש משאבים רק אם הוא לא מחזיק משאבים אחרים כלל. תהליך יוכל לבקש מספר משאבים ולהשתמש בהם, אך לפני שיבקש משאבים נוספים הוא יצטרך לשחרר את כל המשאבים הראשונים (ואם הוא עדיין יזדקק למשאבים הראשונים, יבקש אותם שוב ביחד עם המשאבים החדשים)
 לשתי הדרכים האלו יש שני חסרונות מרכזיים:
-# ניצולת משאבים נמוכה. אם נחייב את התהליכים לבקש משאבים מראש, ייתכן וחלק מהמשאבים לא יהיו בשימוש זמן רב- בין הרגע בו הם הוקצו עד הרגע בו התהליך משתמש בהם בפועל.
+# ניצולת משאבים נמוכה. אם נחייב את התהליכים לבקש משאבים מראש, ייתכן וחלק מהמשאבים לא יהיו בשימוש זמן רב - בין הרגע בו הם הוקצו עד הרגע בו התהליך משתמש בהם בפועל.
 # תיתכן [[הרעבה_(מדעי_המחשב)|הרעבה]]. תהליך שזקוק למספר משאבים פופולריים יחד אולי לאלץ לחכות זמן רב או בלתי מוגבל, בגלל שלפחות אחד מהמשאבים המבוקשים יהיה תמיד תפוס על ידי תהליך אחר.
 ====אין הפקעה====
-נוכל להסיר תנאי זה תוך שימוש באחת מהדרכים הבאות:
+נוכל להסיר תנאי זה תוך שימוש באחת מהדרכים הבאות<ref name=":1">{{צ-ספר|שם=Operating System Concepts, 8th Edition|קישור=https://books.google.co.il/books?id=2YdRzQEACAAJ&dq=Operating+System+Concepts+8th&hl=iw&sa=X&redir_esc=y|מו"ל=John Wiley & Sons|שנת הוצאה=2008|מחבר=ABRAHAM SILBERSCHATZ, PETER GALVIN, GREG GAGNE|שפה=en|עמ=292}}</ref>:
 # כאשר תהליך שכבר מחזיק מספר משאבים מבקש משאבים אחרים ובקשתו נדחית (ולכן הוא חייב להמתין), אזי כל המשאבים הישנים שכבר מוקצים עבורו יופקעו ממנו, וישוחררו מיידית. אותם משאבים מופקעים יתווספו לרשימת המשאבים שהתהליך ממתין להם. התהליך ישוב לפעול רק כאשר הוא יוכל לקבל את כל המשאבים: הישנים והחדשים.
 # כאשר תהליך מבקש משאבים והמשאבים אינם פנויים נבדוק מי מחזיק בהם. אם הם מוחזקים על ידי תהליך אחר שנמצא במצב המתנה (משום שממתין למשאבים אחרים), נפקיע מהתהליך האחר את המשאבים המבוקשים וניתן אותם לתהליך המבקש. לחלופין, אם המשאבים המבוקשים לא פנויים אך לא מוחזקים על ידי תהליך ממתין (כלומר מוחזקים על ידי תהליך רץ), התהליך המבקש יהיה חייב להמתין. בזמן שהוא ממתין ייתכן וחלק ממשאביו יופקעו, אך רק אם תהליך אחר מבקש אותם. התהליך ישוב לפעול רק כאשר קיבל את המשאבים החדשים שביקש וכן קיבל מחדש את המשאבים שהופקעו ממנו בזמן ההמתנה.
 ==== המתנה מעגלית====
-בשביל למנוע מעגל המתנות יש לסדר את כל המשאבים בסדר כלשהו. יש לדרוש שתהליך יוכל לבקש משאבים רק בסדר עולה. כלומר לכל משאב נצמיד מספר סידורי, ותהליך יוכל לבקש רק משאבים שמספרם גדול מהמשאבים שהוא כבר מחזיק בהם.
+בשביל למנוע מעגל המתנות יש לסדר את כל המשאבים בסדר כלשהו. יש לדרוש שתהליך יוכל לבקש משאבים רק בסדר עולה. כלומר לכל משאב נצמיד מספר סידורי, ותהליך יוכל לבקש רק משאבים שמספרם גדול מהמשאבים שהוא כבר מחזיק בהם<ref name=":1" />.
 ===התחמקות מקיפאון===
-בגישה זו מערכת ההפעלה דורשת מידע מוקדם מראש על איזו בקשות משאבים אמורות להגיע. עם תוספת הידע הזו המערכת יכולה להחליט עבור כל בקשה האם התהליך יקבל כעת את המשאב או ימתין במטרה למנוע קיפאון. האלגוריתמים שממשים את גישת ההתחמקות צריכים לבחון כל הזמן את מצב המשאבים המוקצים, כדי לודא שהמתנה מעגלית לא תתרחש.
+בגישה זו מערכת ההפעלה דורשת מידע מוקדם מראש על איזו בקשות משאבים אמורות להגיע. עם תוספת הידע הזו המערכת יכולה להחליט עבור כל בקשה האם התהליך יקבל כעת את המשאב או ימתין במטרה למנוע קיפאון. האלגוריתמים שמממשים את גישת ההתחמקות צריכים לבחון כל הזמן את מצב המשאבים המוקצים, כדי לודא שהמתנה מעגלית לא תתרחש.
-<br />
-נאמר שמצב הוא '''בטוח''' אם המערכת יכולה להקצות משאבים לכל תהליך בסדר מסוים ועדיין למנוע קיפאון. במילים אחרות, מערכת נמצאת במצב בטוח רק אם קיים רצף תהליכים בטוח, שהינו רצף p<sub>0</sub>,p<sub>1</sub>,...,p<sub>n</sub> בו תהליך p<sub>i</sub>
+נאמר שמצב הוא '''בטוח''' אם המערכת יכולה להקצות משאבים לכל תהליך בסדר מסוים ועדיין למנוע קיפאון. במילים אחרות, מערכת נמצאת במצב בטוח רק אם קיים רצף תהליכים בטוח, שהוא רצף p<sub>0</sub>,p<sub>1</sub>,...,p<sub>n</sub> בו תהליך p<sub>i</sub>
 יבקש בעתיד רק משאבים שהם כרגע פנויים או מוחזקים על ידי תהליך p<sub>j</sub>, כך ש j<i. אם המשאבים שp<sub>i</sub> מבקש תפוסים, הוא ימתין עד ש p<sub>j</sub> ישחרר אותם.
-אם לא ניתן לסדר את התהליכים ברצף כזה, נאמר שהמערכת במצב '''לא בטוח''', שעלול להסתיים בקיפאון. ההבחנה בין המצבים מתייחסת ל''יכולת'' של המערכת להגיע למצב קיפאון. ישנם אלגוריתמים שמוודאים שהמערכת תשאר תמיד במצב בטוח. כל פעם שתהליך מבקש משאב פנוי הם מחליטים האם הוא יקבל אותו (כי המערכת תישאר במצב בטוח) או שהתהליך ימתין. בשיטה זו ייתכן ותהליך ימתין גם אם המשאב פנוי ולכן ניצול המשאבים בשיטת ההתחמקות הוא נמוך יותר.
+אם לא ניתן לסדר את התהליכים ברצף כזה, נאמר שהמערכת במצב '''לא בטוח''', שעלול להסתיים בקיפאון. ההבחנה בין המצבים מתייחסת ל''יכולת'' של המערכת להגיע למצב קיפאון. ישנם אלגוריתמים שמוודאים שהמערכת תישאר תמיד במצב בטוח. כל פעם שתהליך מבקש משאב פנוי הם מחליטים האם הוא יקבל אותו (כי המערכת תישאר במצב בטוח) או שהתהליך ימתין. בשיטה זו ייתכן ותהליך ימתין גם אם המשאב פנוי ולכן ניצול המשאבים בשיטת ההתחמקות הוא נמוך יותר.
 {{ש}}
 אלגוריתם שממש התחמקות מקיפאון הוא [[אלגוריתם הבנקאי]].
@@ שורה 76: / שורה 69: @@
 * [[בעיית הפילוסופים הסועדים]]
 * [[בעיית שני הצבאות]]
+{{מדעי המחשב}}
+<!-- ==קישורים חיצוניים== -->
+==הערות שוליים==
+{{הערות שוליים|יישור=שמאל}}
+[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
+[[קטגוריה:תהליכים (מדעי המחשב)]]
 [[קטגוריה:מערכת הפעלה]]
 [[קטגוריה:בעיות שאינן ניתנות לחישוב]]

תחומים במדעי המחשב
יסודות מתמטים	לוגיקה מתמטית • תורת הקבוצות • תורת המספרים • תורת הגרפים • תורת הטיפוסים • תורת הקטגוריות • אנליזה נומרית • תורת האינפורמציה
תורת החישוביות	תורת האוטומטים • תורת הרקורסיה • תורת הסיבוכיות • מחשוב קוונטי
אלגוריתמים ומבנה נתונים	אנליזה של אלגוריתמים • גאומטריה חישובית
שפות תכנות ומהדרים	מפרש • פרדיגמת תכנות (תכנות פרוצדורלי • תכנות מונחה עצמים • תכנות פונקציונלי • תכנות לוגי)
חישוב מבוזר ועיבוד מקבילי	עיבוד מקבילי • מחשוב סריגי • בקרת מקביליות
הנדסת תוכנה	ניתוח מערכות מידע • עיצוב תוכנה • תכנות מחשבים • שיטות פורמליות • בדיקות תוכנה • מתודולוגיית פיתוח תוכנה
תקשורת	ניתוב • טופולוגיית רשת • קריפטוגרפיה
מסד נתונים	מסד נתונים יחסי • SQL • תנועה • אינדקסים • כריית מידע • CAP theorem
בינה מלאכותית	חשיבה אוטומטית • בלשנות חישובית • ראייה ממוחשבת • עיבוד שפה טבעית • בינה חישובית • מערכת מומחה • למידה חישובית • רובוטיקה
גרפיקה	הדמיה ממוחשבת • הנפשה ממוחשבת • עיבוד תמונה
שפות פורמליות	שפה רגולרית • שפה חסרת הקשר • שפה תלוית הקשר • ההיררכיה של חומסקי
שימושים במדע	ביואינפורמטיקה • מדעים קוגניטיביים • כימיה חישובית • פיזיקה חישובית • אנליזה נומרית

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