שאלת מבחן במערכות הפעלה - האוניברסיטה הפתוחה 2017 - תזמון

נתון מנגנון תזמון תהליכים בשיטת ההגרלה (lottery scheduling). כיצד, בלי לשנות קוד של מתזמן, ניתן לקבל מהמנגנון הזה תזמון תהליכים שייתן לתהליכים המתוזמנים זמני תגובה כמו round robin?

רמז: תזמון Round Robin מעניק לכל תהליך הזדמנות שווה לרוץ. כיצד ניתן להגדיר את "סיכוי הזכייה" במנגנון ההגרלה כך שיהיה שווה עבור כל התהליכים?

פתרון: כדי להשיג התנהגות הדומה לתזמון **Round Robin** באמצעות **תזמון בהגרלה** (lottery scheduling) מבלי לשנות את קוד המתזמן, יש להקצות מספר שווה של "כרטיסי הגרלה" לכל תהליך שמוכן לריצה. באלגוריתם **תזמון בהגרלה**, הסיכוי של תהליך להיבחר לרוץ בפרוסת הזמן (quantum) הבאה הוא פרופורציונלי למספר הכרטיסים שברשותו, מתוך סך כל הכרטיסים במערכת. כלומר, אם לתהליך $P_i$ יש $t_i$ כרטיסים וסך כל הכרטיסים במערכת הוא $T = \sum t_j$, אז ההסתברות ש-$P_i$ ייבחר היא $p_i = t_i / T$. באלגוריתם **Round Robin**, המטרה היא לתת לכל תהליך נתח שווה וקבוע ממעבד, בסבב קבוע. כל תהליך מקבל הזדמנות שווה לרוץ. כדי לחקות התנהגות זו, עלינו לגרום לכך שההסתברות של כל תהליך להיבחר תהיה שווה. אם קיימים $N$ תהליכים במערכת, נרצה שההסתברות של כל אחד להיבחר תהיה $1/N$. ניתן להשיג זאת בקלות על ידי קביעת מדיניות הקצאת כרטיסים פשוטה: **כל תהליך במצב מוכן (ready) מקבל בדיוק כרטיס הגרלה אחד**. במצב זה, אם יש $N$ תהליכים מוכנים, סך כל הכרטיסים במערכת הוא $N$, והסיכוי של כל תהליך להיבחר הוא $1/N$. חשוב לציין שההתנהגות אינה זהה לחלוטין: **Round Robin** הוא דטרמיניסטי (התהליכים רצים לפי סדר קבוע), בעוד שהפתרון המוצע הוא הסתברותי. ייתכן שתהליך אחד יזכה בהגרלה מספר פעמים ברציפות. עם זאת, על פי חוק המספרים הגדולים, לאורך זמן, כל תהליך יקבל כמות דומה של זמן מעבד, בדומה ל-**Round Robin**, וכך יושגו זמני תגובה ממוצעים דומים.