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

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

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

פתרון: מנגנון **Round Robin** הוא מנגנון תזמון **דטרמיניסטי** המחלק את זמן ה-CPU באופן שווה בין כל התהליכים. כל תהליך מקבל קוונטום זמן קבוע, ולאחר מכן נכנס לסוף תור התהליכים המוכנים. מנגנון **תזמון הגרלה (lottery scheduling)**, לעומת זאת, הוא **הסתברותי**. הוא מקצה לכל תהליך מספר "כרטיסי הגרלה", ובכל קוונטום זמן בוחר כרטיס זוכה באופן אקראי. התהליך שמחזיק בכרטיס הזוכה מקבל את ה-CPU. חלקו של תהליך בזמן ה-CPU פרופורציונלי למספר הכרטיסים שברשותו ביחס לסך כל הכרטיסים במערכת. כדי לדמות את התנהגות **Round Robin** באמצעות **תזמון הגרלה** מבלי לשנות את קוד המתזמן, עלינו לגרום לכך שלכל התהליכים תהיה הסתברות שווה להיבחר בכל "הגרלה". ניתן להשיג זאת על ידי הקצאת **מספר זהה של כרטיסי הגרלה** לכל תהליך. הדרך הפשוטה ביותר היא להקצות כרטיס אחד בדיוק לכל תהליך. כאשר לכל אחד מ-$N$ התהליכים במערכת יש כרטיס אחד, סך הכרטיסים הוא $N$, וההסתברות של כל תהליך להיבחר בכל קוונטום זמן היא בדיוק $\frac{1}{N}$. בטווח הארוך, התוצאה תהיה חלוקה שווה של זמן ה-CPU בין כל התהליכים, בדומה ל-**Round Robin**. חשוב לציין שההתנהגות בטווח הקצר תהיה שונה: בעוד ש-Round Robin מבטיח שתהליך יקבל שירות תוך זמן חסום, תזמון ההגרלה הוא אקראי ואינו מספק ערובה כזו (תהליך עלול תיאורטית "להפסיד" בהגרלה מספר פעמים רצופות). עם זאת, מבחינת מדיניות הקצאת המשאבים, זוהי הדרך לדמות את העיקרון המרכזי של Round Robin.$\blacksquare$