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

(6 נק') א. תארו את שיטת תזמון תהליכים באמצעות multilevel queue. (6 נק') ב. הסבירו מה הם ה : * `admission scheduler` * `memory scheduler` * `CPU scheduler` במערכת אינטראקטיבית

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

פתרון: א. **תזמון באמצעות תור רב-שכבתי (multilevel queue)** היא שיטת תזמון המחלקת את תור התהליכים המוכנים (ready queue) למספר תורים נפרדים. כל תהליך המגיע למערכת מוקצה באופן **קבוע** לאחד מהתורים, בדרך כלל על סמך מאפיין כלשהו שלו, כגון דרישות זיכרון, עדיפות, או סוג התהליך (למשל, תהליכים **אינטראקטיביים** מול תהליכי **אצווה**). לכל תור יש **אלגוריתם תזמון** משלו, המותאם לאופי התהליכים שבו. לדוגמה, תור עבור תהליכים אינטראקטיביים (foreground) יכול להשתמש באלגוריתם **Round Robin (RR)** כדי להבטיח זמן תגובה מהיר, בעוד שתור עבור תהליכי אצווה (background) יכול להשתמש ב-**First-Come, First-Served (FCFS)**. בנוסף, קיים אלגוריתם תזמון **בין התורים** עצמם. ישנן שתי גישות עיקריות: 1. **עדיפות קבועה עם דחיקה (Fixed-priority preemptive scheduling):** לכל תור יש עדיפות. תהליכים מתור בעל עדיפות נמוכה יותר ירוצו רק אם כל התורים בעלי העדיפות הגבוהה יותר ריקים. אם תהליך חדש מגיע לתור בעדיפות גבוהה, הוא ידחק (preempt) תהליך שרץ כעת מתור בעדיפות נמוכה. 2. **חלוקת זמן (Time slice):** כל תור מקבל אחוז מסוים מזמן ה-CPU. לדוגמה, תור התהליכים האינטראקטיביים עשוי לקבל 80% מזמן המעבד, ותור תהליכי האצווה יקבל את 20% הנותרים. החיסרון העיקרי של שיטה זו הוא חוסר הגמישות, שכן תהליך אינו יכול לשנות את התור אליו הוא משויך, גם אם התנהגותו משתנה במהלך ריצתו. ב. המתזמנים השונים במערכת אינטראקטיבית: * **`admission scheduler` (מתזמן לטווח ארוך / long-term scheduler):** מתזמן זה קובע אילו תהליכים (או עבודות, jobs) מהמאגר החיצוני יורשו להיכנס למערכת ולהפוך לתהליכים בתור המוכנים (ready queue). בכך, הוא שולט על **דרגת ריבוי התכנות (degree of multiprogramming)** – מספר התהליכים הכולל הנמצא בזיכרון. במערכות אינטראקטיביות מודרניות, תפקידו מצומצם; לרוב, כל בקשה של משתמש להרצת תוכנית חדשה מאושרת מיידית, אך הוא עדיין רלוונטי לתהליכי רקע או עבודות אצווה. * **`memory scheduler` (מתזמן לטווח בינוני / medium-term scheduler):** מתזמן זה אחראי על תהליך ה-**swapping**. הוא יכול להחליט להוציא (swap out) תהליך מהזיכרון הראשי אל הדיסק באופן זמני, ובכך להפחית את דרגת ריבוי התכנות. הדבר נעשה בדרך כלל כדי לפנות זיכרון עבור תהליכים אחרים, למנוע **רפרוף (thrashing)**, או כאשר תהליך מסוים אינו פעיל במשך זמן רב. כאשר התנאים משתנים או כשהתהליך נדרש שוב, המתזמן יחזיר אותו (swap in) לזיכרון. * **`CPU scheduler` (מתזמן לטווח קצר / short-term scheduler):** מתזמן זה בוחר את התהליך הבא שיקבל את המעבד מבין כל התהליכים הנמצאים בתור המוכנים. הוא פועל בתדירות גבוהה מאוד (בסדר גודל של מילי-שניות) ולכן חייב להיות יעיל ומהיר במיוחד. הוא זה שמממש את אלגוריתמי התזמון המוכרים כמו **FCFS, SJF, Round Robin**, ואחראי על ביצוע **החלפת הקשר (context switch)** בין תהליכים.