תזכורת: גרעין לינוקס מנהל את הזיכרון של תהליכי משתמש באמצעות רשימה של איזורי זיכרון (VMA). איזור זיכרון הוא רצף כתובות וירטואליות בעל מאפיינים אחידים אשר נשמרים בשדה הנקרא vm_flags. השדה vm_flags הוא למעשה מספר שלם בן 32 ביטים כך שכל ביט אחראי על דגל מסוים, למשל: שם הדגל | מסיכה | משמעות VM_SHARED | 0x0008 | התהליך משתף את איזור הזיכרון עם תהליכי הבנים שלו. (ביט #3) VM_READ | 0x0001 | איזור הזיכרון ניתן לקריאה. (ביט #0) VM_MAYREAD | 0x0010 | ניתן להדליק את הדגל VM_READ באיזור זיכרון זה. לצורך פשטות השאלה, הניחו כי הדגלים VM_MAYREAD,VM_READ זהים בערכם. (ביט #5) VM_WRITE | 0x0002 | איזור הזיכרון ניתן לכתיבה. (ביט #1) שימו לב: אם הדגל VM_WRITE דלוק אז גם הדגל VM_READ דלוק. VM_MAYWRITE | 0x0020 | ניתן להדליק את הדגל VM_WRITE באיזור זיכרון זה. לצורך פשטות השאלה, הניחו כי הדגלים VM_MAYWRITE,VM_WRITE זהים בערכם. (ביט #6) כפי שלמדנו, קריאת המערכת ()fork מעתיקה את הזיכרון של תהליך האב לתהליך הבן בשיטת copy-on-write (או בקיצור COW): • בשלב הראשון ()fork מעתיקה את טבלת הדפים של תהליך האב לתהליך הבן. • בשלב השני ()fork מכבה את הדגל r/w בטבלאות הדפים עבור דפים השייכים לאיזורי זיכרון בעלי מאפיינים מסוימים כדי להגן עליהם. תזכורת: פקודת כתיבה לדפים המוגנים ע"י מנגנון COW תגרום לחריגת דף (page fault). היות וחריגת דף יכולה להתרחש בעקבות אירועים שונים, שגרת הטיפול do_page_fault צריכה לבדוק שני שדות כדי לסווג את החריגה בתור ניסיון כתיבה לדף מוגן COW: • את ההרשאות של איזור הזיכרון (VMA) אליו שייך הדף. • את קוד השגיאה שנדחף למחסנית הגרעין. תזכורת: קוד השגיאה מורכב משלושה ביטים, 2(error code = (ABC, כאשר: A==0 ⇔ the faulting instruction was executed in kernel mode (rather than user mode) B==0⇔ the faulting instruction tried to read (rather than write) C==0 ⇔ present==0 in the corresponding PTE נור רצתה לפשט את הקוד של קריאת המערכת ()fork ולכן היא עדכנה אותו כך שיכבה את הדגל r/w בטבלת הדפים עבור כל הדפים של מרחב המשתמש (ולא רק עבור אלו המקיימים את התנאי משאלה 11). נור לא ערכה את קוד הגרעין מעבר לשינוי הנ"ל.
Full original question text (raw OCR)
חלק 3 - זיכרון וירטואלי (20 נק') תזכורת: גרעין לינוקס מנהל את הזיכרון של תהליכי משתמש באמצעות רשימה של איזורי זיכרון (VMA). איזור זיכרון הוא רצף כתובות וירטואליות בעל מאפיינים אחידים אשר נשמרים בשדה הנקרא vm_flags. השדה vm_flags הוא למעשה מספר שלם בן 32 ביטים כך שכל ביט אחראי על דגל מסוים, למשל: שם הדגל | מסיכה | משמעות VM_SHARED | 0x0008 | התהליך משתף את איזור הזיכרון עם תהליכי הבנים שלו. (ביט #3) VM_READ | 0x0001 | איזור הזיכרון ניתן לקריאה. (ביט #0) VM_MAYREAD | 0x0010 | ניתן להדליק את הדגל VM_READ באיזור זיכרון זה. לצורך פשטות השאלה, הניחו כי הדגלים VM_MAYREAD,VM_READ זהים בערכם. (ביט #5) VM_WRITE | 0x0002 | איזור הזיכרון ניתן לכתיבה. (ביט #1) שימו לב: אם הדגל VM_WRITE דלוק אז גם הדגל VM_READ דלוק. VM_MAYWRITE | 0x0020 | ניתן להדליק את הדגל VM_WRITE באיזור זיכרון זה. לצורך פשטות השאלה, הניחו כי הדגלים VM_MAYWRITE,VM_WRITE זהים בערכם. (ביט #6) כפי שלמדנו, קריאת המערכת ()fork מעתיקה את הזיכרון של תהליך האב לתהליך הבן בשיטת copy-on-write (או בקיצור COW): • בשלב הראשון ()fork מעתיקה את טבלת הדפים של תהליך האב לתהליך הבן. • בשלב השני ()fork מכבה את הדגל r/w בטבלאות הדפים עבור דפים השייכים לאיזורי זיכרון בעלי מאפיינים מסוימים כדי להגן עליהם. 11. (5 נק') מה התנאי על vm_flags עבורו קריאת המערכת ()fork מגינה על איזור הזיכרון? נימוק: תזכורת: פקודת כתיבה לדפים המוגנים ע"י מנגנון COW תגרום לחריגת דף (page fault). היות וחריגת דף יכולה להתרחש בעקבות אירועים שונים, שגרת הטיפול do_page_fault צריכה לבדוק שני שדות כדי לסווג את החריגה בתור ניסיון כתיבה לדף מוגן COW: • את ההרשאות של איזור הזיכרון (VMA) אליו שייך הדף. • את קוד השגיאה שנדחף למחסנית הגרעין. 12. (5 נק') מה התנאי על vm_flags עבורו חריגת הדף מסווגת כ-COW? נימוק: תזכורת: קוד השגיאה מורכב משלושה ביטים, 2(error code = (ABC, כאשר: A==0 ⇔ the faulting instruction was executed in kernel mode (rather than user mode) B==0⇔ the faulting instruction tried to read (rather than write) C==0 ⇔ present==0 in the corresponding PTE 13. (5 נק') מה ערך קוד השגיאה עבורו חריגת הדף מסווגת כ-COW? נימוק: נור רצתה לפשט את הקוד של קריאת המערכת ()fork ולכן היא עדכנה אותו כך שיכבה את הדגל r/w בטבלת הדפים עבור כל הדפים של מרחב המשתמש (ולא רק עבור אלו המקיימים את התנאי משאלה 11). נור לא ערכה את קוד הגרעין מעבר לשינוי הנ"ל. 14. (5 נק') האם המימוש של נור תקין ויעיל? אם לא, מה עליה לעשות כדי לתקן אותו? נימוק:
(5 נק') מה התנאי על vm_flags עבורו קריאת המערכת ()fork מגינה על איזור הזיכרון? a. vma->vm_flags & (VM_SHARED | VM_MAYREAD) == 0 b. vma->vm_flags & (VM_SHARED | VM_MAYREAD) == VM_SHARED c. vma->vm_flags & (VM_SHARED | VM_MAYREAD) == VM_MAYREAD d. vma->vm_flags & (VM_SHARED | VM_MAYWRITE) == 0 e. vma->vm_flags & (VM_SHARED | VM_MAYWRITE) == VM_SHARED f. vma->vm_flags & (VM_SHARED | VM_MAYWRITE) == VM_MAYWRITE
fork/exec address-space semanticslibc syscall wrapper caching pitfallsLinux VMA vm_flags interpretation(5 נק') מה התנאי על vm_flags עבורו חריגת הדף מסווגת כ-COW? a. vma->vm_flags & VM_SHARED == 0 b. vma->vm_flags & VM_SHARED == VM_SHARED c. vma->vm_flags & VM_READ == 0 d. vma->vm_flags & VM_READ == VM_READ e. vma->vm_flags & VM_WRITE == 0 f. vma->vm_flags & VM_WRITE == VM_WRITE
Linux VMA vm_flags interpretationCopy-on-write fork memory protection(5 נק') מה ערך קוד השגיאה עבורו חריגת הדף מסווגת כ-COW? a. 2 b. 3 c. 4 d. 5 e. 6 f. 7
Copy-on-write fork memory protection(5 נק') האם המימוש של נור תקין ויעיל? אם לא, מה עליה לעשות כדי לתקן אותו? a. המימוש תקין ויעיל באותה מידה כמו הקוד המקורי. b. המימוש תקין, אבל פחות יעיל בגלל שהוא גורם ליותר חריגות דף. c. המימוש תקין, אבל פחות יעיל בגלל שהוא גורם להעתקות מיותרות. d. המימוש תקין, אבל פחות יעיל בגלל שהוא גורם ליותר חריגות דף + גורם להעתקות מיותרות. e. המימוש שגוי. כדי לתקן את המימוש צריך לעדכן את הקוד של do_page_fault. f. המימוש שגוי. לא ניתן לתקן את המימוש עבור מעבדי x86.
Page fault error code classificationdo_page_fault handler reasoning
The exam question — original PDF
pages 10, 11, 12Exactly 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
אחרי 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
דוגמת FCFSaverageResponseTime = (10 + 20 + 30) / 3 = 20כעת נסיר את הנחה 1 ("כל התהליכים רצים למשך אותו זמן"). לכל תהליך זמן ריצה משלו.תוכלו לחשוב על דוגמה שבה FCFS אינו יעיל?מערכות הפעלה - תרגול 59כל התהליכים רצים למשך אותו זמן.כל התהליכים מגיעים באותו זמן (t=0).אם תהליך התחיל לרוץ, אז הוא ירוץ עד לסיומו ללא הפסקות.התהליכים משתמשים רק במעבד ולא מבצעים I/O.זמן הריצה של כל התהליכים ידוע מראש.
אפקט השיירה (convoy effect)averageResponseTime = (100 + 110 + 120) / 3 = 110אלגוריתם FCFS עלול לסבול מ"אפקט השיירה": מצב שבו תהליך אחד ארוך מעכב הרבה תהליכים קצרים. מערכות הפעלה - תרגול 510
סיכום השיעור שעבר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
הרשאות של אזור זיכרוןהדגלים המציינים את הרשאות האזור נשמרים בשדה vm_flags והם מאפשרים לגרעין לסווג גישות חוקיות ולא חוקיות לדפים באזור.VM_READ, VM_WRITE, VM_EXEC – האם מותר לקרוא/לכתוב/לבצע נתונים בדפים באזור.VM_MAYREAD, VM_MAYWRITE, VM_MAYEXEC – "הרשאת הרשאה" לכל אחת מההרשאות הנ"ל.לדוגמה VM_MAYWRITE קובע האם מותר להדליק את VM_WRITE.הדגלים האלה קשורים לקריאת המערכת mprotect() – מעבר לחומר הקורס.VM_SHARED – האם צריך לשתף דפים באזור זה עם תהליכי בן.VM_LOCKED – אסור לפנות את הדפים באזור מהזיכרון לדיסק.17מערכות הפעלה - תרגול 10
מרחבי זיכרון וקריאות מערכתחוטים הנוצרים ע"י קריאת המערכתclone() משתפים את מרחב הזיכרון ע"י הצבעה לאותו מתאר מרחב הזיכרון של תהליך האב.יש להגדיל את מונה השיתוף (mm_users) של מתאר מרחב הזיכרון של תהליך האב.קריאת המערכת execv() ודומותיה טוענות תהליך חדש ולכן הן משחררות את מרחב הזיכרון ומקצות אחד חדש.קריאת המערכתfork() מקצה לתהליך הבן מרחב זיכרון משלו.במקרה שכזה צריך להעתיק את מרחב הזיכרון של האב לזה של הבן.בפועל, בדרך-כלל אין באמת העתקה בזכות מנגנון copy-on-write.23מערכות הפעלה - תרגול 10
הפתרון: copy-on-write (COW)הרעיון של מנגנון copy-on-write (COW) הוא:דפים הניתנים לכתיבה שאינם יכולים להיות משותפים (לדוגמה, המחסנית), מוגדרים בתחילה כמשותפים אבל מועתקים לעותק פרטי כאשר אחד התהליכים השותפים (האב או הבן) מנסה לכתוב אליהם לראשונה.שאר הדפים (כדוגמת דפי קוד או דפי נתונים לקריאה בלבד) הופכים למשותפים בין מרחבי הזיכרון של האב והבן.מנגנון COW פותר את שתי הבעיות שהוצגו קודם:COW מקטין את זמן הביצוע של fork() כי הוא "פורס לתשלומים" את ההעתקה של כל מרחב הזיכרון להרבה העתקות קטנות בגודל דף שיתבצעו בעתיד---בכל כתיבה ראשונה לדף שאינו משותף.במידה ותהליך הבן יבצע מיד execv(), מרחב הזיכרון שלו יימחק וכך תיחסך רוב פעולת ההעתקה.27מערכות הפעלה - תרגול 10
father processpage tablememory regionsדוגמה: לפני קריאת מערכת fork()28…PTE #11r/w = 1…frame #250count == 1מערכות הפעלה - תרגול 10region #1VM_MAYWRITE=1VM_WRITE=1region #2
COW: טיפול ב-page faultתרחיש הטיפול: האב או הבן מנסים לכתוב לדף מוגן ע"י COW.המעבד ניגש לסיביות הבקרה ב-PTE של הדף, ומגלה כי r/w כבוי.המעבד יוצר חריגת דף (page fault).הגרעין מטפל בחריגה, ובודק שהדף שייך לאחד מאזורי הזיכרון ושהגישה בכלל חוקית (דגל VM_WRITE דלוק במתאר האזור).הגרעין בודק את ערך המונה השיתוף של המסגרת:אם count > 1, מקצים מסגרת חדשה, מעתיקים אליה את המסגרת המקורית, ומצביעים את הדף למסגרת החדשה.במסגרת הישנה מבוצע count-- .במסגרת החדשה מוצב count = 1 .בעותק החדש מאופשרת הכתיבה.אחרת (count == 1), הגרעין פשוט מאפשר כתיבה בדף ע"י הדלקת הדגל r/w.37מערכות הפעלה - תרגול 10
חריגת דף (page fault)החומרה מתריעה באמצעות חריגת דף על:גישה לדף שאינו נמצא בזיכרון, כלומר הביט present==0 בכניסה המתאימה בטבלת הדפים.גישה לא חוקית (שלא לפי ההרשאות בטבלת הדפים) לדף שנמצא בזיכרון, למשל ניסיון כתיבה לדף שמותר לקריאה בלבד.חריגת דף מפעילה את שגרת הטיפול הממומשת בפונקציית הגרעין do_page_fault().בסיום הטיפול בחריגה מבוצעת מחדש ההוראה שגרמה לה.אלא אם כן, כמובן, הטיפול בחריגה הורג את התהליך.43מערכות הפעלה - תרגול 10
The exam text, the skills it tests, and the exact slides are already in context.