תזכורת: בלינוקס יש שני סוגים של החלפות הקשר: (א) החלפת הקשר מרצון - כאשר התהליך מוותר על המעבד. (ב) החלפת הקשר כפויה - כאשר מערכת ההפעלה מפקיעה את המעבד מהתהליך. תזכורת: גרעין לינוקס שנלמד בתרגולים אינו ניתן להפקעה .non-preemptible kernel גרעין שאינו ניתן להפקעה מעניק מספר יתרונות לעומת גרעין ניתן להפקעה, לדוגמה הגנה על מבני נתונים משותפים של הגרעין מפני תרחישי סנכרון בעייתיים. למרבה הצער, לגרעין שאינו ניתן להפקעה יש גם חסרונות, לדוגמה פגיעה בביצועים של תהליכים מסוימים. פרדי, חובב מוזיקה ומשתמש לינוקס כבד, סובל מבעיה כזו כאשר הוא מנסה לשמוע מוזיקה בזמן שהוא מקמפל קוד של תרגילי בית אבל שומע "קפיצות" במוזיקה. לצורך המשך השאלה, נסביר בקצרה איך עובד נגן מוזיקה: התהליך מעביר קובץ אודיו ("שיר") להתקן חומרה מיוחד -- כרטיס קול -- אשר משמיע אותו ברמקולים. כרטיס הקול מכיל חוצץ (buffer) קטן יחסית, למשל בגודל 16KB, ולכן נגן המוזיקה לא יכול להעביר את הקובץ כולו בבת אחת. נגן המוזיקה ממלא את החוצץ (במשך 5ms בערך) ואז מוותר על המעבד ועובר להמתין בזמן שכרטיס הקול קורא את המידע מהחוצץ (במשך 500ms בערך). מעט לפני שהחוצץ מתרוקן, כרטיס הקול שולח פסיקה למעבד, אשר מעירה את נגן המוזיקה כדי שימלא שוב את החוצץ, וחוזר חלילה. החברים של פרדי ניסו לעזור לו לפתור את הבעיה. בריאן הציע לשפר את העדיפות הסטטית (ולכן גם הדינמית) של נגן המוזיקה ע"י הקטנת הערך nice. רוג'ר הציע להפוך את נגן המוזיקה לתהליך זמן-אמת במדיניות SCHED_RR. ג'ון הציע להפוך את נגן המוזיקה לתהליך זמן-אמת במדיניות SCHED_FIFO.
Full original question text (raw OCR)
חלק 2 - החלפת הקשר (25 נק') תזכורת: בלינוקס יש שני סוגים של החלפות הקשר: (א) החלפת הקשר מרצון - כאשר התהליך מוותר על המעבד. (ב) החלפת הקשר כפויה - כאשר מערכת ההפעלה מפקיעה את המעבד מהתהליך. 6. (5 נק') איזה אירוע מבין הבאים יוביל בהכרח להחלפת הקשר כפויה (כלומר הפקעה)? נימוק: תזכורת: גרעין לינוקס שנלמד בתרגולים אינו ניתן להפקעה .non-preemptible kernel 7. (5 נק') מה משמעות המושג "גרעין שאינו ניתן להפקעה"? נימוק: גרעין שאינו ניתן להפקעה מעניק מספר יתרונות לעומת גרעין ניתן להפקעה, לדוגמה הגנה על מבני נתונים משותפים של הגרעין מפני תרחישי סנכרון בעייתיים. 8. (5 נק') איזה תרחיש הוא בלתי אפשרי בגרעין שאינו ניתן להפקעה במערכת מעבד יחיד? הבהרה: A עלול לחתוך את B פירושו ש-A עלול להיכנס באמצע הביצוע של B. נימוק: למרבה הצער, לגרעין שאינו ניתן להפקעה יש גם חסרונות, לדוגמה פגיעה בביצועים של תהליכים מסוימים. פרדי, חובב מוזיקה ומשתמש לינוקס כבד, סובל מבעיה כזו כאשר הוא מנסה לשמוע מוזיקה בזמן שהוא מקמפל קוד של תרגילי בית אבל שומע "קפיצות" במוזיקה. לצורך המשך השאלה, נסביר בקצרה איך עובד נגן מוזיקה: התהליך מעביר קובץ אודיו ("שיר") להתקן חומרה מיוחד -- כרטיס קול -- אשר משמיע אותו ברמקולים. כרטיס הקול מכיל חוצץ (buffer) קטן יחסית, למשל בגודל 16KB, ולכן נגן המוזיקה לא יכול להעביר את הקובץ כולו בבת אחת. נגן המוזיקה ממלא את החוצץ (במשך 5ms בערך) ואז מוותר על המעבד ועובר להמתין בזמן שכרטיס הקול קורא את המידע מהחוצץ (במשך 500ms בערך). מעט לפני שהחוצץ מתרוקן, כרטיס הקול שולח פסיקה למעבד, אשר מעירה את נגן המוזיקה כדי שימלא שוב את החוצץ, וחוזר חלילה. 9. (5 נק') מדוע נגן המוזיקה סובל מגרעין שאינו ניתן להפקעה? נימוק: החברים של פרדי ניסו לעזור לו לפתור את הבעיה. בריאן הציע לשפר את העדיפות הסטטית (ולכן גם הדינמית) של נגן המוזיקה ע"י הקטנת הערך nice. רוג'ר הציע להפוך את נגן המוזיקה לתהליך זמן-אמת במדיניות SCHED_RR. ג'ון הציע להפוך את נגן המוזיקה לתהליך זמן-אמת במדיניות SCHED_FIFO. 10. (5 נק') מי מהחברים של פרדי הציע דרך שתצמצם את הבעיה? נתון כי: • במחשב של פרדי רצים רק שני תהליכים: נגן המוזיקה + קומפילציה של קוד. • שני התהליכים הם בעלי ערך 0 = nice (ערך ברירת המחדל). • תהליך הקומפילציה רץ הרבה על המעבד ויוצא מעט להמתנה. • במחשב של פרדי יש מעבד יחיד. נימוק:
(5 נק') איזה אירוע מבין הבאים יוביל בהכרח להחלפת הקשר כפויה (כלומר הפקעה)? a. פסיקת חומרה אשר מעירה תהליך עדיף יותר מהתהליך הנוכחי. b. חריגת דף בעקבות גישה לא חוקית של התהליך לזיכרון. c. ניסיון לתפוס מנעול שכבר תפוס ע"י קריאה ל-()pthread_mutex_lock. d. קריאת מערכת ()wait. e. קריאת מערכת ()read. f. קריאת מערכת ()exit.
Voluntary vs preemptive context switchlibc syscall wrapper caching pitfallsPreemption trigger identificationNon-preemptible kernel implicationsLocal vs global interrupt disablePage fault error code classification(5 נק') מה משמעות המושג "גרעין שאינו ניתן להפקעה"? a. תהליך חישובי לא יפקיע את המעבד מתהליך גרעין. b. תהליך אינטראקטיבי לא יפקיע את המעבד מתהליך גרעין. c. תהליך (חישובי או אינטראקטיבי) לא יפקיע את המעבד מתהליך גרעין. d. מערכת ההפעלה לא תפקיע את המעבד מתהליך חישובי שרץ במצב גרעין. e. מערכת ההפעלה לא תפקיע את המעבד מתהליך אינטראקטיבי שרץ במצב גרעין. f. מערכת ההפעלה לא תפקיע את המעבד מתהליך (חישובי או אינטראקטיבי) שרץ במצב גרעין.
Voluntary vs preemptive context switchLatency vs throughput process classificationlibc syscall wrapper caching pitfallsNon-preemptible kernel implications(5 נק') איזה תרחיש הוא בלתי אפשרי בגרעין שאינו ניתן להפקעה במערכת מעבד יחיד? הבהרה: A עלול לחתוך את B פירושו ש-A עלול להיכנס באמצע הביצוע של B. a. קריאת מערכת חוסמת עלולה לחתוך קריאת מערכת חוסמת. b. קריאת מערכת לא-חוסמת עלולה לחתוך קריאת מערכת חוסמת. c. קריאת מערכת חוסמת עלולה לחתוך קריאת מערכת לא-חוסמת. d. פסיקת חומרה עלולה לחתוך קריאת מערכת חוסמת. e. פסיקת חומרה עלולה לחתוך קריאת מערכת לא-חוסמת. f. פסיקת חומרה עלולה לחתוך פסיקת חומרה.
Voluntary vs preemptive context switchlibc syscall wrapper caching pitfallsPreemption trigger identificationNon-preemptible kernel implicationsLocal vs global interrupt disable(5 נק') מדוע נגן המוזיקה סובל מגרעין שאינו ניתן להפקעה? a. כי הוא תהליך חישובי אשר רגיש להשהיות במהלך הריצה (latency sensitive). b. כי הוא תהליך אינטראקטיבי אשר רגיש להשהיות במהלך הריצה (latency sensitive). c. כי הוא תהליך חישובי אשר רגיש לזמן הריצה הכולל (throughput sensitive). d. כי הוא תהליך אינטראקטיבי אשר רגיש לזמן הריצה הכולל (throughput sensitive). e. כי הוא תהליך חישובי אשר רגיש לנצילות המעבד (utilization sensitive). f. כי הוא תהליך אינטראקטיבי אשר רגיש לנצילות המעבד (utilization sensitive).
Voluntary vs preemptive context switchLatency vs throughput process classificationNon-preemptible kernel implications(5 נק') מי מהחברים של פרדי הציע דרך שתצמצם את הבעיה? נתון כי: • במחשב של פרדי רצים רק שני תהליכים: נגן המוזיקה + קומפילציה של קוד. • שני התהליכים הם בעלי ערך 0 = nice (ערך ברירת המחדל). • תהליך הקומפילציה רץ הרבה על המעבד ויוצא מעט להמתנה. • במחשב של פרדי יש מעבד יחיד. a. אף אחד מבין החברים. b. רק בריאן. c. רק רוג'ר. d. רק ג'ון. e. רק רוג'ר וג'ון. f. כל שלושת החברים.
nice value and dynamic priority
The exam question — original PDF
pages 7, 8, 9Exactly 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
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.זמן הריצה של כל התהליכים ידוע מראש.
נהוג לסווג תהליכים לשני סוגיםתהליך אינטראקטיבי 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
הפקעה (preemption)בעיה: תהליך משתמש עלול לרוץ לנצח (למשל, לולאה אינסופית) ולמנוע את המעבד משאר התהליכים.פגיעה בהוגנות (fairness) ותגובתיות (rrsponsiveness).פתרון: לינוקס מפקיעה (preempt) את המעבד מתהליך אחד לטובת תהליך אחר, בעזרת התקן חומרה מיוחד – השעון.מערכת ההפעלה מבקשת מהשעון לשלוח פסיקה במרווחי זמן קבועים כדי להעביר את השליטה למערכת ההפעלה.כל הפסיקות, בפרט פסיקת שעון, מטופלות במצב גרעין, ואז הגרעין מחליף הקשר אם יש צורך.מערכות הפעלה - תרגול 614
הפונקציה __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.
מימוש מנעול קוראים-כותבים (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?
סיכום השיעור שעבר2the CPU searches the TLBhitmissthe CPU walks the page tablecompletedpage faultphysical addressvirtual addressthe OS serves the page faultמערכות הפעלה - תרגול 10
מה נלמד היום?3the CPU searches the TLBhitmissthe CPU walks the page tablecompletedpage faultphysical addressvirtual addresskill the process or the entire systemfix the page table and retrythe OS serves the page faultinvalidvalidמערכות הפעלה - תרגול 10
The exam text, the skills it tests, and the exact slides are already in context.