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

אלגוריתם scheduling lottery הינו אלגוריתם תזמון הסתברותי. כל תהליך במערכת מקבל מספר כלשהו של "כרטיסי הגרלה" (לכל כרטיס מספר ייחודי); בכל שלב, האלגוריתם מגריל מספר של אחד מכרטיסי ההגרלה שחולקו, והתהליך שמחזיק בכרטיס הגרלה זה מקבל את המעבד לפרק זמן קצוב. א. נניח כי לאלגוריתם יש 20 כרטיסים. כיצד עליו לחלק אותם בין ארבעה תהליכים $A, B, C, D$ כך שהתהליכים יקבלו $10\%(A), 5\%(B), 60\%(C), 25\%(D)$ בהתאמה? ב. כיצד ניתן להגיע באמצעות אלגוריתם זה לביצועים הדומים לאלו המושגים על-ידי אלגוריתם round-robin? ג. איך ניתן להגיע באמצעות אלגוריתם זה לביצועים הדומים לאלו המושגים על-ידי אלגוריתם shortest remaining time first? (ניתן להניח כי יש preemption, התהליכים לא מגיעים יחד, אבל זמן הביצוע ידוע כאשר התהליך מגיע.)

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

פתרון: א. **תזמון הגרלות (Lottery Scheduling)** מקצה זמן מעבד באופן פרופורציונלי למספר ה**כרטיסים** שכל תהליך מחזיק. כדי להשיג את החלוקה המבוקשת, עלינו לחלק את 20 הכרטיסים הזמינים לפי האחוזים הנתונים: * תהליך A: צריך לקבל $10\%$ מזמן המעבד, ולכן יקבל $10\%$ מהכרטיסים. מספר הכרטיסים: $0.10 \times 20 = 2$. * תהליך B: צריך לקבל $5\%$ מזמן המעבד, ולכן יקבל $5\%$ מהכרטיסים. מספר הכרטיסים: $0.05 \times 20 = 1$. * תהליך C: צריך לקבל $60\%$ מזמן המעבד, ולכן יקבל $60\%$ מהכרטיסים. מספר הכרטיסים: $0.60 \times 20 = 12$. * תהליך D: צריך לקבל $25\%$ מזמן המעבד, ולכן יקבל $25\%$ מהכרטיסים. מספר הכרטיסים: $0.25 \times 20 = 5$. בדיקה: $2 + 1 + 12 + 5 = 20$. סך הכרטיסים שחולקו שווה לסך כל הכרטיסים במערכת. $\blacksquare$ ב. אלגוריתם **Round-Robin (RR)** מאופיין במתן הזדמנות שווה והוגנת לכל תהליך לקבל את המעבד. הוא מקצה לכל תהליך בתור המוכנים **פרוסת זמן (quantum)** קבועה, בסבבים. כדי לחקות התנהגות זו באמצעות תזמון הגרלות, עלינו להבטיח שלכל תהליך תהיה הסתברות שווה להיבחר בכל הגרלה. ניתן להשיג זאת על ידי חלוקה שווה של הכרטיסים בין כל התהליכים המוכנים. הדרך הפשוטה ביותר היא להקצות לכל תהליך כרטיס אחד בדיוק. באופן כללי, אם יש $N$ תהליכים, כל אחד יקבל $T/N$ כרטיסים, כאשר $T$ הוא המספר הכולל של הכרטיסים. $\blacksquare$ ג. אלגוריתם **Shortest Remaining Time First (SRTF)** הוא אלגוריתם **תזמון מונע (preemptive)** הנותן עדיפות לתהליך עם זמן הריצה הנותר הקצר ביותר. כדי לחקות התנהגות זו, עלינו להעניק הסתברות גבוהה משמעותית להיבחר לתהליך שהכי קרוב לסיום. ניתן לעשות זאת על ידי חלוקת כרטיסים ביחס הפוך לזמן הריצה הנותר של כל תהליך. באופן קונקרטי: 1. **הקצאת כרטיסים:** תהליך עם זמן ריצה נותר קצר יקבל מספר גדול של כרטיסים, בעוד שתהליך עם זמן ריצה נותר ארוך יקבל מספר קטן של כרטיסים. לדוגמה, אם לתהליך $P_i$ נותר זמן ריצה $R_i$, הוא יכול לקבל מספר כרטיסים $T_i$ הפרופורציונלי ל-$1/R_i$. 2. **דינמיות והרחקה:** מכיוון ש-SRTF הוא אלגוריתם מונע, חלוקת הכרטיסים חייבת להיות דינמית ולהתעדכן באופן רציף: * כאשר תהליך חדש מגיע למערכת, יש לחשב מחדש את חלוקת הכרטיסים לכל התהליכים. * לאחר שתהליך רץ במשך פרוסת זמן, זמן הריצה הנותר שלו קטן, ולכן ייתכן שיש לעדכן את מספר הכרטיסים שלו (ושל האחרים) כדי לשקף את המצב החדש. באופן זה, התהליך עם זמן הריצה הנותר הקצר ביותר יחזיק ברוב המכריע של הכרטיסים בכל רגע נתון, ולכן ההסתברות שהוא ייבחר לרוץ תהיה קרובה מאוד ל-1, מה שמדמה את ההתנהגות הדטרמיניסטית של SRTF. $\blacksquare$