במערכות רבות תהליכים מייצרים משימות (events), שאותן יש לבצע לפי זימון מסויים. דוגמה למשימה: שליחת חבילה ברשת. משימות שנוצרו ע"י אותו תהליך לא מתבצעות במקביל ותמיד בסדר FIFO (סדר FIFO רק בין משימות שנוצרו על ידי אותו תהליך). כך אם תהליך P רוצה לשלוח חבילה A ואחרי זה B, אז אנחנו לא נשדר את B במקביל או לפני A. לעומת זאת, אם תהליך אחר יצר משימה של שידור חבילה C, אז אותה ניתן לשדר לפני A או במקביל אליה. לכל משימה יש מספר יחידות חישוב שעליה לעשות (למשל, לשדר 800 ביטים). זמן הביצוע של יחידת חישוב לא תלוי במשימה המתבצעת (למשל תלוי בקצב השידור שהכרטיס רשת תומך, אך לא בחבילה המשודרת). שימו לב שאורך המשימות יכול להיות שונה זו מזו. בכל הסעיפים נניח שקיים מעבד יחיד נניח שניתן לבצע משימות במקביל והמעבד יודע לבצע משימות במקביל. כמובן, כתוצאה מכך זמן הביצוע של כל משימה גדל בהתאם לאחוז המעבד שהיא מקבלת. למשל, אם מבצעים את משימה A במקביל למשימה B אז ל- A נותנים 50% מזמן המעבד ול- B גם 50% וזמן החישוב של כל משימה מוכפל (פי 2). נסתכל על זמן שנקרא Generalized Processor Sharing (או בקיצור GPS). זמן זה בכל רגע נתון מסתכל על כל התהליכים שיש להם משימות לביצוע ומחלק את המעבד באופן שווה בין תהליכים אלו. ברגע שמשימות נוצרות או מסתיימות הוא מבצע חלוקה מחדש של המעבד. למשל אם יש 4 תהליכים שלהם 2 משימות לביצוע אז המעבד מחולק באופן שווה בין 2 המשימות האלו (50% לכל משימה). אם תגיע משימה נוספת מתהליך 3 אז GPS יחלק את המעבד באופן שווה בין שלושת המשימות. יחד עם זאת, אם לתהליך יש מספר משימות, הזמן לא יתן לו עדיפות כלשהי או יותר אחוזים מהמעבד (תמיד מסתכלים על המשימה הותיקה ביותר של התהליך). לרוב, תהליכים הם לא זהים ויש להם עדיפות. במערכות אלו עדיפות באה לידי ביטוי על ידי משקל שקובע איך החלוקה מתבצעת. במקום לחלק מעבד באופן זהה לכל המשימות, כל משימה מקבלת חלק פרופורציוני שלה לפי נוסחה: Wi / ΣWj (all processes that have tasks) למשל, אם שני תהליכים A ו- B רוצים להריץ משימות ומשקל (W) של תהליך A הינו 3 ושל B הינו 1, אז משימות של A יקבלו 75% מעבד ומשימות של B יקבלו 25%. לרוב, מעבד לא יכול לבצע משימות במקביל וגם עבור משימות רבות אנחנו לא יכולים לעשות הפקעה (למשל: לא ניתן לשדר חצי מחבילה 1 ואז חבילה 2 ובסוף חצי שני של החבילה הראשונה). האלגוריתם batch הנפוץ למשימות האלו הינו Weighted Fair Queuing (או בקיצור WFQ). אלגוריתם זה מריץ סימולציה של GPS ובוחר מבין כל המשימות הזמינות לביצוע את המשימה שזמן הסיום שלה ב-GPS הינו המוקדם ביותר מבין כל המשימות (שטרם הסתיימו). נתון תזמון GPS של מערכת כלשהי: [table with Time Interval and Executing tasks] זמני ההגעה של המשימות הינם: A1:0, B1:0, A2:4, C1:6, A3:13, B2:12 נניח שהמעבד יכול לבצע 24 יחידות חישוב לשנייה. אחת הבעיות הידועות של WFQ היא שהוא מתזמן משימות מוקדם מדי. זה גורם להרעבה של תהליכים בעלי עדיפות נמוכה. הניחו שיש 6 תהליכים במערכת: תהליך P1 עם עדיפות 5 ועוד 5 תהליכים (P2,...P6) עם עדיפות 1. לתהליך P1 יש 5 משימות של שנייה אחת ולכל שאר התהליכים יש משימה אחת של שנייה אחת.
Full original question text (raw OCR)
במערכות רבות תהליכים מייצרים משימות (events), שאותן יש לבצע לפי זימון מסויים. דוגמה למשימה: שליחת חבילה ברשת. משימות שנוצרו ע"י אותו תהליך לא מתבצעות במקביל ותמיד בסדר FIFO (סדר FIFO רק בין משימות שנוצרו על ידי אותו תהליך). כך אם תהליך P רוצה לשלוח חבילה A ואחרי זה B, אז אנחנו לא נשדר את B במקביל או לפני A. לעומת זאת, אם תהליך אחר יצר משימה של שידור חבילה C, אז אותה ניתן לשדר לפני A או במקביל אליה. לכל משימה יש מספר יחידות חישוב שעליה לעשות (למשל, לשדר 800 ביטים). זמן הביצוע של יחידת חישוב לא תלוי במשימה המתבצעת (למשל תלוי בקצב השידור שהכרטיס רשת תומך, אך לא בחבילה המשודרת). שימו לב שאורך המשימות יכול להיות שונה זו מזו. בכל הסעיפים נניח שקיים מעבד יחיד נניח שניתן לבצע משימות במקביל והמעבד יודע לבצע משימות במקביל. כמובן, כתוצאה מכך זמן הביצוע של כל משימה גדל בהתאם לאחוז המעבד שהיא מקבלת. למשל, אם מבצעים את משימה A במקביל למשימה B אז ל- A נותנים 50% מזמן המעבד ול- B גם 50% וזמן החישוב של כל משימה מוכפל (פי 2). נסתכל על זמן שנקרא Generalized Processor Sharing (או בקיצור GPS). זמן זה בכל רגע נתון מסתכל על כל התהליכים שיש להם משימות לביצוע ומחלק את המעבד באופן שווה בין תהליכים אלו. ברגע שמשימות נוצרות או מסתיימות הוא מבצע חלוקה מחדש של המעבד. למשל אם יש 4 תהליכים שלהם 2 משימות לביצוע אז המעבד מחולק באופן שווה בין 2 המשימות האלו (50% לכל משימה). אם תגיע משימה נוספת מתהליך 3 אז GPS יחלק את המעבד באופן שווה בין שלושת המשימות. יחד עם זאת, אם לתהליך יש מספר משימות, הזמן לא יתן לו עדיפות כלשהי או יותר אחוזים מהמעבד (תמיד מסתכלים על המשימה הותיקה ביותר של התהליך).
הטבלה הבאה מתארת משימות שנוצרו ע"י 4 תהליכים A,B,C ו-D. עבור כל משימה נתון זמן היווצרותה, מספר יחידות החישוב שהיא דורשת, איזה תהליך יצר אותה ומה המספר הסידורי שלה (A2 נוצרה על ידי תהליך A והמספר הסידורי שלה 2). Task | A1 | B1 | C1 | D1 | A2 | B2 | A3 Computational units | 74 | 146 | 98 | 122 | 72 | 80 | 128 Time of Arrival (sec) | 0 | 0 | 4 | 5 | 8 | 12 | 12 נניח שהמעבד יכול לבצע 24 יחידות חישוב לשנייה. מלאו את הטבלה של הזימון. קבעו את אורך האינטרוול של הזמן והמשימות המתבצעות בו. למשל עבור מערכת בה בזמן 0 עד 3 מתבצעת משימה A1 ומזמן 4 עד 6 מתבצעות A1 ו-B1 הטבלה נראית כך: Time Interval | 0-4 | 4-6 Executing tasks | A1 | A1,B1
fork/exec address-space semanticslibc syscall wrapper caching pitfallsSRT / preemptive Gantt constructionנתונה מערכת עם שני תהליכים A ו-B עם משקלים 1 ו-4 בהתאמה. A מיצר משימה בזמן 0 ואילו B מיצר משימה בזמן 4. גודל של כל משימה 200 יחידות חישוב ומעבד יכול לבצע 25 יחידות חישוב לשנייה. תנו תיאור של הזימון עד גמר הביצוע של שתי המשימות. (שימו לב שצריך להתחשב במשקלי התהליכים). תשובה:
libc syscall wrapper caching pitfallsreview:T2·22חשבו את הגדלים של המשימות: A1: A2: A3: B1: B2: C1: מלאו את טבלת התזמון של WFQ: Time Interval Executing tasks
fork/exec address-space semanticsמלאו טבלה זו עבור זימון של WFQ: Time Interval Executing tasks
fork/exec address-space semanticsהשיפור של WFQ נקרא WF2Q. כמו WFQ גם WF2Q בוחר במשימה עם זמן הסיום המוקדם ביותר לפי GPS. אבל הבחירה היא רק בין הפקטות ש-GPS כבר התחיל לבצע. ז"א אם בזמן t אנחנו רוצים לבחור משימה לביצוע ומשימה A מסתיימת לפני B לפי GPS, אז נבחר את A רק אם בזמן t גם אלגוריתם GPS התחיל לבצע את המשימה A. חזרו על הסעיף הקודם (סעיף 4.1) ומלאו טבלה זו עבור זימון של WF2Q: Time Interval Executing tasks
fork/exec address-space semantics
The exam question — original PDF
pages 8, 9, 10, 11Exactly 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.
אחרי fork()parentint main() { int x = 0; pid_t p = fork(); if (p == 0) { x = 1; } else { x = 2; }}sonint main() { int x = 0; pid_t p = fork(); if (p == 0) { x = 1; } else { x = 2; }}מערכות הפעלה - תרגול 210
הדפסה מתואמת למסךשימוש ב-wait() יכול לפתור את הבעיה שראינו קודם כאשר מדפיסים למסך במקביל משני תהליכים:int main() { pid_t p = fork(); if (p > 0) { // parent waits for child wait(NULL); } printf(“hello”); return 0;}מערכות הפעלה - תרגול 215
קריאות המערכת getpid(), getppid()pid_t getpid();קריאת מערכת המחזירה לתהליך הקורא את ה-pid של עצמו.pid_t getppid();קריאת מערכת המחזירה את ה-PID של תהליך האב של התהליך הקורא.שאלה: מה המשמעות של getppid() == 1 עבור תהליך משתמש טיפוסי?תשובה: תהליך האב הוא init. קורה למשל אם תהליך הבן יתום.מערכות הפעלה - תרגול 222
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
עדיפויות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.
The exam text, the skills it tests, and the exact slides are already in context.