תזכורת: submit_time – arrival_time = wait time: כלומר משך הזמן בין קבלתה-job למערכת לבין הזמן שבו הוא מתחיל לרוץ)
Full original question text (raw OCR)
שאלה 4 - תזמון תהליכים (25 נק') תזכורת: למערכת לבין הזמן שבו job-כלומר משך הזמן בין קבלתה( wait time = arrival_time – submit_time:תזכורת הוא מתחיל לרוץ) 1. (2 נק') במערכת עם ליבה אחת, בה כל התהליכים מגיעים יחד וזמני הריצה שלהם ידועים מראש, איזה אלגוריתם batch scheduling (כלומר בלי הפקעות תהליכים) ימזער ככל הניתן את ה-average wait time? (אין צורך בנימוק) a. SJF (shortest job first) algorithm b. FCFS (first come first serve) algorithm c. EASY (FCFS + backfilling) algorithm d. RR (round robin) algorithm e. תלוי בחומרת המערכת f. אם קיים תהליך שרץ על כל המעבדים במערכת – Round Robin, ואחרת SJF g. תלוי כמה מהתהליכים שייכים למערכת ההפעלה 2. (5 נק') נגדיר מערכת בעלת 3 ליבות (המסוגלת להריץ תהליכים במקביל, בהתאם לדרישות של התהליכים), בה ישנם אך ורק 4 תהליכים המעוניינים לרוץ: תהליך 1 דורש 2 ליבות וירוץ למשך 2 שניות עד לסיום תהליך 2 דורש 1 ליבות וירוץ למשך 4 שניות עד לסיום תהליך 3 דורש 3 ליבות וירוץ למשך 1 שניות עד לסיום תהליך 4 דורש 2 ליבות וירוץ למשך 2 שניות עד לסיום התהליכים נשלחים למעבד בסדר זה (קודם תהליך 1 מגיע, אחרי זה תהליך 2, אחרי זה תהליך 3, ואחרון מגיע תהליך 4). לאחר הגעת תהליך 4 אך לפני תחילת הרצת תהליך 1 נקצה את כולם למעבדים ונחלק לוח זמנים לכל מעבד (כלומר לכל מעבד נקבע מתי להריץ איזה תהליך). איזה אלגוריתם יגרום לסיום כל התהליכים ראשון? a. כל האלגוריתמים יסיימו את הריצה באותו זמן b. FCFS c. SJF d. EASY e. תשובות b, c נכונות f. תלוי עד כמה יש את "אפקט השיירה" (convoy effect) במערכת לפני תחילת ריצת התהליכים g. תשובות c, d נכונות נימוק: 3. (3 נק') במערכת ההפעלה לינוקס אנו משתמשים באלגוריתם זימון תהליכים המורכב ממערכת תזמון round robin או FIFO עבור תהליכי זמן-אמת, ובאלגוריתם CFS (כפי שנלמד בתרגולים) עבור תהליכים "רגילים". נניח שיש תהליך רגיל אחד ותהליך זמן-אמת אחד. מהו החיסרון המשמעותי ביותר בשימוש באלגוריתם CFS גלובלי על כל התהליכים? כלומר, מה החיסרון בכך שנתייחס לתהליכי זמן-אמת בתור תהליכים רגילים, וניתן להם niceness מקסימלי כדי לתת להם עדיפות גבוהה באלגוריתם? a. לאלגוריתם CFS יש סיבוכיות זמן ריצה של בחירת התהליך הבא ((O(log(n ולכן לא נרצה לאלץ את התהליך זמן-האמת לחכות לריצה שלו b. אלגוריתם round robin יותר הוגן מאשר אלגוריתם CFS כיוון שהוא לא מתייחס למשקול (niceness) של תהליך c. אלגוריתם CFS גלובלי לא יתן לתהליך זמן האמת את כל זמן המעבד d. אלגוריתם CFS לא מתחשב בזמן שתהליכים לוקחים לבצע ס/ו e. תהליכים חדשים מתווספים עם זמן ריצה וירטואלי מינימאלי ולכן יכולים לגרום להרעבת תהליך זמן האמת f. אף תשובה לא נכונה נימוק: 4. (3 נק') באלגוריתם CFS (כפי שנלמד בתרגול), כאשר מעבירים תהליך P ממעבד A למעבד B (למשל, לצורך איזון עומסים בין מעבדים שונים), איזה זמן ריצה וירטואלי יקבל תהליך P אחרי שמעבירים אותו? a. זמן הריצה הוירטואלי המינימאלי מבין התהליכים של מעבד A b. זמן הריצה הוירטואלי המקסימאלי מבין התהליכים של מעבד A c. אותו זמן ריצה וירטואלי כפי שהיה לו במעבד A לפני שהועבר d. זמן הריצה הוירטואלי המינימאלי מבין התהליכים של מעבד B e. זמן הריצה הוירטואלי המקסימאלי מבין התהליכים של מעבד B נימוק: 5. (4 נק') אלגוריתם CFS מגדיר לתהליכים חדשים את זמן הריצה הוירטואלי _________, ואילו מגדיר לתהליכים שחוזרים משהייה ארוכה את זמן הריצה הוירטואלי a. חדשים: המינימאלי, חוזרים משהייה: המינימאלי b. חדשים: המקסימאלי, חוזרים משהייה: המקסימאלי c. חדשים: המינימאלי, חוזרים משהייה: המקסימאלי d. חדשים: המקסימאלי, חוזרים משהייה: המינימאלי e. חדשים: המקסימאלי, חוזרים משהייה: שהיה לו לפני היציאה לשהייה f. חדשים: הממוצע, חוזרים משהייה: שהיה לו לפני היציאה לשהייה g. חדשים: הממוצע, חוזרים משהייה: הממוצע h. אף תשובה לא נכונה נימוק: 6. (4 נק') במערכת בה תהליכים מגיעים בזמנים שרירותיים, באיזה אלגוריתם תזמון נעדיף להשתמש – SRTF או SJF? מדוע? הערה: נגדיר "אלגוריתם מועדף" בתור אלגוריתם שמשפר את ה-average wait time כפי שהוגדר בסעיף הראשון. נימוק: 7.(4 נק') ד"ר פישבך, חוקר אלגוריתמי תזמון במערכות הפעלה, מתבאס מכל אלגוריתמי התזמון המסובכים ומציע אלגוריתם מאוד פשוט: כל מעבד יעבור לתהליך חדש בכל פסיקת שעון (בלי התנגשויות כמובן, כך שלא יקרה מצבו בוזוג מעבדים יריצו את אותו תהליך), וככה חלוקת הזמנים בין התהליכים תהיה הכי הוגנת שהיא יכולה להיות, כי בכל epoch כל התהליכים יקבלו את אותה כמות זמן. הוא מגביל את האלגוריתם למערכות שמבצעות רק תהליכים שלא נכנסים למצב המתנה, ובעלי niceness אחיד קבוע. ד״ר טאוב שהשקיע הרבה זמן בתרגילי הבית במערכות הפעלה נרתע מאלגוריתם זה ומעדיף להשתמש במערכת הקיימת. הוא טוען שישנה בעיה מאוד חמורה באלגוריתם זה. מה הבעיה? נימוק:
1. (2 נק') במערכת עם ליבה אחת, בה כל התהליכים מגיעים יחד וזמני הריצה שלהם ידועים מראש, איזה אלגוריתם batch scheduling (כלומר בלי הפקעות תהליכים) ימזער ככל הניתן את ה-average wait time? (אין צורך בנימוק) a. SJF (shortest job first) algorithm b. FCFS (first come first serve) algorithm c. EASY (FCFS + backfilling) algorithm d. RR (round robin) algorithm e. תלוי בחומרת המערכת f. אם קיים תהליך שרץ על כל המעבדים במערכת – Round Robin, ואחרת SJF g. תלוי כמה מהתהליכים שייכים למערכת ההפעלה
libc syscall wrapper caching pitfallsSRT / preemptive Gantt construction2. (5 נק') נגדיר מערכת בעלת 3 ליבות (המסוגלת להריץ תהליכים במקביל, בהתאם לדרישות של התהליכים), בה ישנם אך ורק 4 תהליכים המעוניינים לרוץ: תהליך 1 דורש 2 ליבות וירוץ למשך 2 שניות עד לסיום תהליך 2 דורש 1 ליבות וירוץ למשך 4 שניות עד לסיום תהליך 3 דורש 3 ליבות וירוץ למשך 1 שניות עד לסיום תהליך 4 דורש 2 ליבות וירוץ למשך 2 שניות עד לסיום התהליכים נשלחים למעבד בסדר זה (קודם תהליך 1 מגיע, אחרי זה תהליך 2, אחרי זה תהליך 3, ואחרון מגיע תהליך 4). לאחר הגעת תהליך 4 אך לפני תחילת הרצת תהליך 1 נקצה את כולם למעבדים ונחלק לוח זמנים לכל מעבד (כלומר לכל מעבד נקבע מתי להריץ איזה תהליך). איזה אלגוריתם יגרום לסיום כל התהליכים ראשון? a. כל האלגוריתמים יסיימו את הריצה באותו זמן b. FCFS c. SJF d. EASY e. תשובות b, c נכונות f. תלוי עד כמה יש את "אפקט השיירה" (convoy effect) במערכת לפני תחילת ריצת התהליכים g. תשובות c, d נכונות נימוק:
libc syscall wrapper caching pitfallsreview:T2·223. (3 נק') במערכת ההפעלה לינוקס אנו משתמשים באלגוריתם זימון תהליכים המורכב ממערכת תזמון round robin או FIFO עבור תהליכי זמן-אמת, ובאלגוריתם CFS (כפי שנלמד בתרגולים) עבור תהליכים "רגילים". נניח שיש תהליך רגיל אחד ותהליך זמן-אמת אחד. מהו החיסרון המשמעותי ביותר בשימוש באלגוריתם CFS גלובלי על כל התהליכים? כלומר, מה החיסרון בכך שנתייחס לתהליכי זמן-אמת בתור תהליכים רגילים, וניתן להם niceness מקסימלי כדי לתת להם עדיפות גבוהה באלגוריתם? a. לאלגוריתם CFS יש סיבוכיות זמן ריצה של בחירת התהליך הבא ((O(log(n ולכן לא נרצה לאלץ את התהליך זמן-האמת לחכות לריצה שלו b. אלגוריתם round robin יותר הוגן מאשר אלגוריתם CFS כיוון שהוא לא מתייחס למשקול (niceness) של תהליך c. אלגוריתם CFS גלובלי לא יתן לתהליך זמן האמת את כל זמן המעבד d. אלגוריתם CFS לא מתחשב בזמן שתהליכים לוקחים לבצע ס/ו e. תהליכים חדשים מתווספים עם זמן ריצה וירטואלי מינימאלי ולכן יכולים לגרום להרעבת תהליך זמן האמת f. אף תשובה לא נכונה נימוק:
nice value and dynamic prioritylibc syscall wrapper caching pitfalls4. (3 נק') באלגוריתם CFS (כפי שנלמד בתרגול), כאשר מעבירים תהליך P ממעבד A למעבד B (למשל, לצורך איזון עומסים בין מעבדים שונים), איזה זמן ריצה וירטואלי יקבל תהליך P אחרי שמעבירים אותו? a. זמן הריצה הוירטואלי המינימאלי מבין התהליכים של מעבד A b. זמן הריצה הוירטואלי המקסימאלי מבין התהליכים של מעבד A c. אותו זמן ריצה וירטואלי כפי שהיה לו במעבד A לפני שהועבר d. זמן הריצה הוירטואלי המינימאלי מבין התהליכים של מעבד B e. זמן הריצה הוירטואלי המקסימאלי מבין התהליכים של מעבד B נימוק:
nice value and dynamic prioritylibc syscall wrapper caching pitfallsSRT / preemptive Gantt construction5. (4 נק') אלגוריתם CFS מגדיר לתהליכים חדשים את זמן הריצה הוירטואלי _________, ואילו מגדיר לתהליכים שחוזרים משהייה ארוכה את זמן הריצה הוירטואלי a. חדשים: המינימאלי, חוזרים משהייה: המינימאלי b. חדשים: המקסימאלי, חוזרים משהייה: המקסימאלי c. חדשים: המינימאלי, חוזרים משהייה: המקסימאלי d. חדשים: המקסימאלי, חוזרים משהייה: המינימאלי e. חדשים: המקסימאלי, חוזרים משהייה: שהיה לו לפני היציאה לשהייה f. חדשים: הממוצע, חוזרים משהייה: שהיה לו לפני היציאה לשהייה g. חדשים: הממוצע, חוזרים משהייה: הממוצע h. אף תשובה לא נכונה נימוק:
nice value and dynamic prioritylibc syscall wrapper caching pitfallsSRT / preemptive Gantt construction6. (4 נק') במערכת בה תהליכים מגיעים בזמנים שרירותיים, באיזה אלגוריתם תזמון נעדיף להשתמש – SRTF או SJF? מדוע? הערה: נגדיר "אלגוריתם מועדף" בתור אלגוריתם שמשפר את ה-average wait time כפי שהוגדר בסעיף הראשון. נימוק:
libc syscall wrapper caching pitfallsSRT / preemptive Gantt construction7.(4 נק') ד"ר פישבך, חוקר אלגוריתמי תזמון במערכות הפעלה, מתבאס מכל אלגוריתמי התזמון המסובכים ומציע אלגוריתם מאוד פשוט: כל מעבד יעבור לתהליך חדש בכל פסיקת שעון (בלי התנגשויות כמובן, כך שלא יקרה מצבו בוזוג מעבדים יריצו את אותו תהליך), וככה חלוקת הזמנים בין התהליכים תהיה הכי הוגנת שהיא יכולה להיות, כי בכל epoch כל התהליכים יקבלו את אותה כמות זמן. הוא מגביל את האלגוריתם למערכות שמבצעות רק תהליכים שלא נכנסים למצב המתנה, ובעלי niceness אחיד קבוע. ד״ר טאוב שהשקיע הרבה זמן בתרגילי הבית במערכות הפעלה נרתע מאלגוריתם זה ומעדיף להשתמש במערכת הקיימת. הוא טוען שישנה בעיה מאוד חמורה באלגוריתם זה. מה הבעיה? נימוק:
nice value and dynamic prioritylibc syscall wrapper caching pitfallsLocal vs global interrupt disable
The exam question — original PDF
pages 14, 15, 16Exactly 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.
קריאות המערכת getpid(), getppid()pid_t getpid();קריאת מערכת המחזירה לתהליך הקורא את ה-pid של עצמו.pid_t getppid();קריאת מערכת המחזירה את ה-PID של תהליך האב של התהליך הקורא.שאלה: מה המשמעות של getppid() == 1 עבור תהליך משתמש טיפוסי?תשובה: תהליך האב הוא init. קורה למשל אם תהליך הבן יתום.מערכות הפעלה - תרגול 222
מערכות הפעלה - תרגול 2281שאלה ממבחן
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
נהוג לסווג תהליכים לשני סוגיםתהליך אינטראקטיבי I/O Boundמעוניין בזמן המתנה נמוך.latency sensitive.דוגמה: נגן סרטים שמחליף 60 פריימים בשנייה.בדרך-כלל מוותר על המעבד מרצונו אחרי פרק זמן קצר בגלל המתנה לפעולות I/O.תהליך חישוביCPU Boundמעוניין בזמן תגובה נמוך.throughput sensitive.דוגמה: סקריפט python שמנתח נתונים ע"י חישובים אלגבריים.בדרך-כלל לא מוותר על המעבד מרצונו אלא מופקע.מערכות הפעלה - תרגול 523
עדיפויותCFS מאפשר למשתמש להגדיר עדיפויות לתהליכים וכך לחלק את זמן המעבד בצורה שונה בין התהליכים.העדיפות של התהליך מיוצגת ע"י הערך -20 ≤ nice ≤ +19 .ברירת המחדל היא nice=0 .תהליך "נחמד" יותר יהיה בעדיפות נמוכה יותר.לכל עדיפות יש משקל:מערכות הפעלה - תרגול 550
קצת נוסחאותנניח שיש במערכת n תהליכים עם עדיפויות: P1, P2, …, Pnומשקלים: W1, W2, …, Wn .נניח כי W0 הוא המשקל המתאים לעדיפות nice=0.אז זמן הריצה הווירטואלי של התהליך ה-i מתקדם לפי:VRi += (W0 / Wi) ∙ ∆Tכאשר ∆T הוא זמן הריצה לפי שעון אמיתי.זמן הריצה הווירטואלי זהה לזמן הריצה האמיתי עבור ברירת המחדל nice=0.ניתן להוכיח כי הקוונטום של התהליך ה-i הוא:Qi = (Wi / ΣWi) ∙ sched_latencyמערכות הפעלה - תרגול 551
מהי החלפת הקשר?מערכות הפעלה - תרגול 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.
תרגול 8מנגנוני סנכרון: משתני תנאימנגנוני סנכרון: סמפוריםדוגמה: מימוש מנעול קוראים-כותביםסינכרון בגרעין לינוקס1מערכות הפעלה - תרגול 8
מימוש מנעול קוראים-כותבים (1)int readers_inside, writers_inside;cond_t read_allowed;cond_t write_allowed;mutex_t global_lock; void readers_writers_init() { readers_inside = 0; writers_inside = 0; cond_init(&read_allowed, NULL); cond_init(&write_allowed, NULL); mutex_init(&global_lock, NULL);}32מערכות הפעלה - תרגול 8מה ערכו המקסימלי של writers_inside?
The exam text, the skills it tests, and the exact slides are already in context.