שאלה זו עוסקת בנושא batch-scheduling כפי שנלמד בהרצאות. שימו לב שבכל טבלאות התזמון הבאות המספר המייצג time-slot כלשהו מייצג את הזמן שבו החלון הנתון מסתיים (כלומר - אם time slot = 3 אזי החלון מתחיל ב-2=t ומסתיים ב- 3=t).
Full original question text (raw OCR)
שאלה 1 - זימון תהליכים (25 נק') שאלה זו עוסקת בנושא batch-scheduling כפי שנלמד בהרצאות. שימו לב שבכל טבלאות התזמון הבאות המספר המייצג time-slot כלשהו מייצג את הזמן שבו החלון הנתון מסתיים (כלומר - אם time 3 = slot אזי החלון מתחיל ב-2=t ומסתיים ב- 3=t). Cores 1 2 J1 3 4 J3 J2 J4 J5 1 2 3 4 5 6 7 8 9 10 Time Slot 1. (9 נק') בהינתן התזמון הנתון למעלה, חשבו את המדדים הבאים (הראו את דרך החישוב). הניחו שכל התהליכים בנתונים למעלה הגיעו באותו הזמן (0=t): :)average wait-time( 1) (3 נק') מדד זמן ההמתנה הממוצע( :)average response-time( 2) (3 נק') מדד זמן התגובה הממוצע( 3) (3 נק') מדד הניצולת (utilization): 2. (4 נק') בהנחה שכל התהליכים למעלה מגיעים בזמן 0. איזו מדיניות זימון יכולה לשפר את הניצולת כפי שחושבה בסעיף הקודם? נמקו (ראו מצורפת טבלת זימון ריקה על מנת להמחיש את הזימון החדש לפי האלגוריתם, עליכם למלא את הטבלה בהתאם) Cores 1 2 3 4 1 2 3 4 5 6 7 8 9 10 Time Slot 3.(4 נק') מנו 2 יתרונות ו-2 חסרונות של מדיניות זימון מסוג batch-scheduling על פני מדיניות .נמקו .Round-robin יתרונות: (1 (2 חסרונות: (1 (2 נתונה מדיניות זימון חדשה (BSAF (Biggest Surface-Area First לפיה בהינתן 2 תהליכים זה שנבחר לרוץ קודם הוא זה שהשטח שלו הגדול יותר (שטח = זמן * מספר-מעבדים). שימו לב שמדיניות זימון זו תומכת ב-backfilling - כלומר שאם התהליך העדיף ביותר לפי BSAF לא יכול להיות מתזומן בחלון כלשהו, יתוזמן התהליך הטוב ביותר שמתאים לחלון אחריו (זה שמתאים לחלון הפנוי והוא הטוב ביותר לפי BSAF). בהינתן 2 תהליכים בעלי אותו שטח נבחר בזה שיש לו את זמן הריצה הקצר ביותר. בהינתן 2 תהליכים בעלי שטח זהה וזמן ריצה זהה, נבחר בזה עם ה-ID (מספר) הנמוך יותר. למשל, בהינתן 4 התהליכים הבאים (האיור להמחשה של מימדי התהליכים בלבד): J1 J3 J2 J4 J1 (3*3=9 surface area) J2 (3*2=6, shorter runtime than J3 and J4) J3 (2*3=6, same as J4, but lower ID) J4 האלגוריתם BSAF יתעדף אותם בסדר הבא: 4. (4 נק') האם BSAF סובל מ-convoy effect? נמקו (עליכם להמחיש בעזרת הטבלה הנתונה). Cores 1 2 3 4 Time 1 2 3 4 5 6 7 8 9 10 Slot 5. (4 נק') האם אלגוריתם הזימון BSAF הינו אופטימלי מבחינת מדד הניצולת? הוכיחו או הפריכו (עליכם להמחיש בעזרת הטבלה הנתונה) Cores 1 2 3 4 1 2 3 4 5 6 7 8 9 10 Time Slot
(3 נק') מדד זמן ההמתנה הממוצע (average wait-time):
Voluntary vs preemptive context switchLatency vs throughput process classificationNon-preemptible kernel implications(3 נק') מדד זמן התגובה הממוצע (average response-time):
Voluntary vs preemptive context switchLatency vs throughput process classificationNon-preemptible kernel implications(3 נק') מדד הניצולת (utilization):
Voluntary vs preemptive context switchLatency vs throughput process classificationNon-preemptible kernel implications(4 נק') בהנחה שכל התהליכים למעלה מגיעים בזמן 0. איזו מדיניות זימון יכולה לשפר את הניצולת כפי שחושבה בסעיף הקודם? נמקו (ראו מצורפת טבלת זימון ריקה על מנת להמחיש את הזימון החדש לפי האלגוריתם, עליכם למלא את הטבלה בהתאם)
Voluntary vs preemptive context switchLatency vs throughput process classificationNon-preemptible kernel implications(4 נק') מנו 2 יתרונות ו-2 חסרונות של מדיניות זימון מסוג batch-scheduling על פני מדיניות Round-robin. נמקו.
Voluntary vs preemptive context switchLatency vs throughput process classificationNon-preemptible kernel implications(4 נק') האם BSAF סובל מ-convoy effect? נמקו (עליכם להמחיש בעזרת הטבלה הנתונה).
Voluntary vs preemptive context switchLatency vs throughput process classificationNon-preemptible kernel implications(4 נק') האם אלגוריתם הזימון BSAF הינו אופטימלי מבחינת מדד הניצולת? הוכיחו או הפריכו (עליכם להמחיש בעזרת הטבלה הנתונה)
Voluntary vs preemptive context switchLatency vs throughput process classificationNon-preemptible kernel implications
The exam question — original PDF
pages 2, 3, 4, 5, 6Exactly as it appears on the exam paper.
Built from these components
Ordered basic → advanced. Master the earlier ones first.
Review the material
Read these before you answer — each verified slide teaches a component this question tests, and nothing from an unrelated topic is included. Tutorial slides show the actual slide image.
TL;DRזַמָּן התהליכים ((scheduler הוא הרכיב במערכת ההפעלה שאחראי על בחירת התהליך הבא שירוץ על המעבד.אנחנו נלמד, בתור דוגמה, את אלגוריתם הזימון של לינוקס.אבל לפני שנלמד דוגמה "אמיתית" ומורכבת, נרצה להבין את הגישות הבסיסיות בזימון תהליכים כדי לפתח אינטואיציה.מערכות הפעלה - תרגול 52זימון תהליכים בלינוקסCFS = completely fair schedulerאלגוריתם זימון של תהליכים רגיליםSCHED_FIFO, SCHED_RRאלגוריתם זימון של תהליכי זמן אמת
דוגמת FCFSaverageResponseTime = (10 + 20 + 30) / 3 = 20כעת נסיר את הנחה 1 ("כל התהליכים רצים למשך אותו זמן"). לכל תהליך זמן ריצה משלו.תוכלו לחשוב על דוגמה שבה FCFS אינו יעיל?מערכות הפעלה - תרגול 59כל התהליכים רצים למשך אותו זמן.כל התהליכים מגיעים באותו זמן (t=0).אם תהליך התחיל לרוץ, אז הוא ירוץ עד לסיומו ללא הפסקות.התהליכים משתמשים רק במעבד ולא מבצעים I/O.זמן הריצה של כל התהליכים ידוע מראש.
אלגוריתם SRTFSRTF = shortest remaining time firstנקרא גם: STCF = shortest time to completion firstאופן פעולה: כמו SJF, אבל עם הפקעות.בכל פעם שתהליך חדש מגיע למערכת, SRTF מחשב למי מבין התהליכים (כולל התהליך החדש) נותר הכי פחות זמן לרוץ, ובוחר את התהליך הזה לריצה.תחת ההנחות החדשות, ניתן להוכיח כי SRTF אופטימלי במדד זמן התגובה הממוצע.בתוספת הנחה כי זמן החלפת הקשר הוא אפסי.מערכות הפעלה - תרגול 515כל התהליכים רצים למשך אותו זמן.כל התהליכים מגיעים באותו זמן (t=0).אם תהליך התחיל לרוץ, אז הוא ירוץ עד לסיומו ללא הפסקות.התהליכים משתמשים רק במעבד ולא מבצעים I/O.זמן הריצה של כל התהליכים ידוע מראש.
נהוג לסווג תהליכים לשני סוגיםתהליך אינטראקטיבי I/O Boundמעוניין בזמן המתנה נמוך.latency sensitive.דוגמה: נגן סרטים שמחליף 60 פריימים בשנייה.בדרך-כלל מוותר על המעבד מרצונו אחרי פרק זמן קצר בגלל המתנה לפעולות I/O.תהליך חישוביCPU Boundמעוניין בזמן תגובה נמוך.throughput sensitive.דוגמה: סקריפט python שמנתח נתונים ע"י חישובים אלגבריים.בדרך-כלל לא מוותר על המעבד מרצונו אלא מופקע.מערכות הפעלה - תרגול 523
מדיניות זימון של תהליךלכל תהליך זמן-אמת יש מדיניות זימון (scheduling policy):SCHED_FIFO או SCHED_RR .נקבעת ע"י המשתמש באמצעות קריאות מערכת sched_setscheduler() .מדיניות הזימון – תשפיע על כמה זמן ריצה כל תהליך יקבל ואופן עבודת התור.מערכות הפעלה - תרגול 535
מהי החלפת הקשר?מערכות הפעלה - תרגול 610
מהי החלפת הקשר?לכל תהליך יש "הקשר ביצוע" (execution context) המכיל את כל המידע הדרוש לביצוע התהליך.מחסניות, רגיסטרים, תכולת זיכרון, קבצים פתוחים, ..."החלפת הקשר" = עצירת הביצוע של התהליך הנוכחי ושמירת ההקשר שלו.טעינת ההקשר של התהליך הבא לביצוע.הקשר התהליך הנוכחי מתחלף – מכאן שם הפעולה "החלפת הקשר".מערכות הפעלה - תרגול 611
שני סוגים של החלפת הקשרהחלפת הקשר כפויה(== הפקעה)הגרעין מפקיע (כלומר, לוקח בכוח) את המעבד מהתהליך, למשל בעקבות:פסיקת שעון (מטופלת בשגרה scheduler_tick) אשר מגלה כי הזמן שהוקצב לתהליך הנוכחי אזל.אירוע אסינכרוני אשר מעיר תהליך בעל עדיפות טובה יותר מהתהליך הרץ כרגע.לדוגמה: פסיקת דיסק או שחרור מנעול שתהליך המתין לו.החלפת הקשר יזומההתהליך מוותר מרצונו על המעבד, למשל באמצעות:קריאת מערכת חוסמת (כמו wait(), read(), …) אשר מוציאה את התהליך להמתנה.קריאת מערכת exit() אשר מסיימת את התהליך.קריאת מערכת sched_yield() – קריאת מערכת ייעודית לוויתור על המעבד.מערכות הפעלה - תרגול 613
הפונקציה __switch_to_asm (3) popq %r15 popq %r14 popq %r13 popq %r12 popq %rbx popq %rbp jmp __switch_to מערכות הפעלה - תרגול 635שחזור הרגיסטרים ממחסנית הגרעין של next.אלו הרגיסטרים ש-next שמר כאשר הוא קרא להחלפת הקשר בעבר.קפיצה (jmp) במקום קריאה (call) לפונקציה. למה?כתובת החזרה מהפונקציה __switch_to() כבר שמורה על המחסנית של next.
The exam text, the skills it tests, and the exact slides are already in context.