הרעבה (מדעי המחשב)

במדעי המחשב, הרעבה (באנגלית: Starvation) היא בעיה הנוצרת בסביבה המאפשרת ריבוי משימות (Multitasking), כאשר מתהליך מסוים נמנעת גישה לאחד ממשאבי המערכת כך שהתהליך לעולם לא יצליח לסיים את משימתו.

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

הרעבת תהליך

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

מקור הבעיה

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

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

הימנעות מהרעבה

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

הרעבת רשת

בפרוטוקולי תקשורת מסוימים הנמצאים בשימוש בתקשורת מחשבים יש אלגוריתמי תזמון המוודאים שמשאבי הרשת זמינים לכולם ואין מחשב שמעוניין לשדר אך לא יוכל לבצע זאת. מרבית הפרוטוקולים האלו הם הפרוטוקולים היושבים בשכבה הפיזית של מודל TCP/IP שכן הם אלו ששולטים על הגישה לרשת. פרוטוקולים לדוגמה המבצעים זאת הם Ethernet ו-Wi-Fi.