נתון התרשים המופשט של מצבי התהליכים: [Diagram of Running, Ready, Waiting states with arrows] עבור כל אחד מהמעברים תנו תרחיש המוביל למעבר: נתון שהמערכת עובדת עם זמן תהליכים מסוג (RR (Round Robin: תזכורת: מאז גרעין 2.6 בלינוקס משתמשים בזמן תהליכים הנקרא (CFS (Completely Fair Scheduler אשר מזמן את התהליך בעל זמן הווירטואלי הקטן ביותר. נתונה מערכת זימון תהליכים כפי שלמדנו בתרגול ורצה על מחשב עם מעבד יחיד וכל התהליכים מגיעים בזמן 0: בהנחה שיש במערכת את התהליכים הבאים, ואורך הקוונטום הוא 2ms: [Table with Process A, B details] איזה תהליך ירוץ בכל אחד מהזמנים הנתונים: [Table to fill] בהנחה שיש במערכת את התהליכים הבאים, ואורך הקוונטום הוא 2ms: [Table with Process A, B, C details] איזה תהליך ירוץ בכל אחד מהזמנים הנתונים (נא להמשיך את הטבלה עד 17ms) נתון הקוד של 2 תהליכים ומדיניות הזימון שלהם (אפשר להניח ששניהם מגיעים בו זמנית): [Code for Process A (SCHED_FIFO) and Process B (SCHED_OTHER (CFS))]
Full original question text (raw OCR)
נתון התרשים המופשט של מצבי התהליכים: [Diagram of Running, Ready, Waiting states with arrows] עבור כל אחד מהמעברים תנו תרחיש המוביל למעבר: נתון שהמערכת עובדת עם זמן תהליכים מסוג (RR (Round Robin: תזכורת: מאז גרעין 2.6 בלינוקס משתמשים בזמן תהליכים הנקרא (CFS (Completely Fair Scheduler אשר מזמן את התהליך בעל זמן הווירטואלי הקטן ביותר. נתונה מערכת זימון תהליכים כפי שלמדנו בתרגול ורצה על מחשב עם מעבד יחיד וכל התהליכים מגיעים בזמן 0: 4. (2 נק') בהנחה שיש במערכת את התהליכים הבאים, ואורך הקוונטום הוא 2ms: Process Scheduling policy Priority level Expected runtime A SCHED_RR 30 5 ms B SCHED_FIFO 31 6 ms איזה תהליך ירוץ בכל אחד מהזמנים הנתונים: process Time 0 1 2 3 4 5 6 7 8 stamp (ms) דוגמא למילוי: process A B A A B B Time 0 1 2 3 4 5 6 7 8 stamp (ms) הסבר: 5. (2 נק') בהנחה שיש במערכת את התהליכים הבאים, ואורך הקוונטום הוא 2ms: Process Scheduling policy Priority level Expected runtime A SCHED_RR 30 5 ms B SCHED_RR 31 6 ms C SCHED_RR 30 6 ms איזה תהליך ירוץ בכל אחד מהזמנים הנתונים (נא להמשיך את הטבלה עד 17ms) process Time 0 1 2 3 4 5 stamp (ms) 17 הסבר: נתון הקוד של 2 תהליכים ומדיניות הזימון שלהם (אפשר להניח ששניהם מגיעים בו זמנית): Process A SCHED FIFO int main() { while(1); } printf("Hello World"); return 0; Process B SCHED_OTHER (CFS) int main() { printf("Hello from CFS"); while(1); return 0; }
Running → Ready
libc syscall wrapper caching pitfallsSCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionReady → Running
libc syscall wrapper caching pitfallsSCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionRunning → Waiting
SRT / preemptive Gantt constructionWaiting → Ready
SRT / preemptive Gantt constructionמה היתרון בשימוש ב quantum גדול (מספיק יתרון אחד)?
libc syscall wrapper caching pitfallsSCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionמה היתרון בשימוש ב quantum קטן (מספיק יתרון אחד)?
libc syscall wrapper caching pitfallsSCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionבמידה והמערכת עמוסה (מכילה הרבה תהליכים מוכנים לריצה), מדוע עדיף להוסיף תהליכים חדשים בסוף התור?
libc syscall wrapper caching pitfallsעבור זמן תהליכים CFS, איזה בעיה פותרת ה min_granularity ?
libc syscall wrapper caching pitfallsSCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionאיזה תהליך ירוץ בכל אחד מהזמנים הנתונים: [Table to fill]
libc syscall wrapper caching pitfallsSCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionאיזה תהליך ירוץ בכל אחד מהזמנים הנתונים (נא להמשיך את הטבלה עד 17ms) [Table to fill]
libc syscall wrapper caching pitfallsSCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionהאם תודפס ההודעה "Hello from CFS"? (הסבר)
libc syscall wrapper caching pitfallsSCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionאילו היינו משנים את מדיניות הזימון של תהליך A ל SCHED_RR במקום SCHED_FIFO, האם התשובה לסעיף הקודם היתה משתנה?
SCHED_FIFO / SCHED_RR real-time policiesSRT / preemptive Gantt constructionלדני יש מחשב בעל 2 מעבדים ורוצה לממש "איזון עומסים" במערכת זימון תהליכים שלו, כך שהתהליך יכול לבחור לאיזה מעבד לעבור דרך קריאת מערכת חדשה. להזכירכם: "איזון עומסים" או load balancing היא פעולה בה מעבירים תהליכים בין מעבד אחד לשני כדי לאזן את העומס על שני המעבדים. לדני עלתה 3 אופציות לממש את העברת תהליכים רגילים, בעלי מדיניות זימון CFS, ממעבד A למעבד B: • להשאיר את התהליך עם אותו vruntime שצבר עד כה. • לתת לתהליך vruntime = min_vruntime הזמן הוירטואלי המינימלי בין הזמנים הוירטואלים של התהליכים הרצים על המעבד B. • לתת לתהליך vruntime = max_vruntime הזמן הווירטואלי המקסימלי בין הזמנים הוירטואלים של התהליכים הרצים על המעבד B. מה לדעתכם האופציה העדיפה ביותר? ולמה?
libc syscall wrapper caching pitfalls
The exam question — original PDF
pages 4, 5, 6, 7, 8Exactly 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.
SRTF (Shortest-Remaining-Time First) • Assume different jobs may arrive at different times • SJF is not optimal – As it’s not preemptive, and – A short job might arrive while a very long job is running => recall: convoy effect • SRTF is just like SJF but – Is allowed to use preemption – Hence, it’s “optimal” (assuming a zero context-switch cost etc.) • Whenever a new job arrives, or an old job terminates – SRTF schedules the job with the shortest remaining time – Thereby making an optimal decision 39 OS (234123) - scheduling
קריאת המערכת exit()שאלה: למה בכלל לקרוא ל-exit(status) , אם אפשר פשוט לרשום return status בסוף פונקציית ה-main?תשובה: main היא לא באמת הפונקציה הראשית של התכנית...main() נקראת ע"י __libc_start_main() שאוספת את ערך החזרה של main() וקוראת ל-exit().int __libc_start_main(…) { …… exit(main(…));}מסקנה: הפונקציה exit תמיד נקראת לסיום סטנדרטי של התוכנית.מערכות הפעלה - תרגול 218
קריאות המערכת getpid(), getppid()pid_t getpid();קריאת מערכת המחזירה לתהליך הקורא את ה-pid של עצמו.pid_t getppid();קריאת מערכת המחזירה את ה-PID של תהליך האב של התהליך הקורא.שאלה: מה המשמעות של getppid() == 1 עבור תהליך משתמש טיפוסי?תשובה: תהליך האב הוא init. קורה למשל אם תהליך הבן יתום.מערכות הפעלה - תרגול 222
דוגמת קודמסכמתprintf("pid = %d\n", getpid());pid_t pid = fork();if (pid == 0) { printf("child pid = %d\n", getpid()); char* args[] = {"/bin/date", NULL}; execv(args[0], args); printf("This should not be printed\n");} else { wait(NULL); printf("parent pid = %d\n", getpid());}פלט לדוגמה:pid = 8919child pid = 8920Sun Oct 29 00:31:32 IDT 2017parent pid = 8919מערכות הפעלה - תרגול 224
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.זמן הריצה של כל התהליכים ידוע מראש.
אפקט השיירה (convoy effect)averageResponseTime = (100 + 110 + 120) / 3 = 110אלגוריתם FCFS עלול לסבול מ"אפקט השיירה": מצב שבו תהליך אחד ארוך מעכב הרבה תהליכים קצרים. מערכות הפעלה - תרגול 510
אלגוריתם 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.