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

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

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

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

הרעבת תהליך

עריכה

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

מקור הבעיה

עריכה

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

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

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

עריכה

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

הרעבת רשת

עריכה

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