בתרגולים למדנו על ספריית pthreads אשר מממשת חוטים ברמת הגרעין, כלומר יוצרת חוטים חדשים בעזרת קריאת המערכת clone. כעת נגדיר ספרייה חדשה, ULTL, אשר מממשת חוטים ברמת המשתמש, כלומר יוצרת חוטים חדשים ללא תמיכת מערכת ההפעלה (ללא קריאות מערכת כלל). הספרייה תשתמש בשתי פונקציות מספריית libc אשר מתוארות להלן (לקוח מתוך ה-man pages) int setjmp(jmp_buf env); void longjmp(jmp_buf env, int val); DESCRIPTION The setjmp() function dynamically establishes a target to which control may be later transferred by saving the stack pointer, instruction pointer, and other register values in the buffer env. In this case, setjmp() returns 0. The longjmp() function can then transfer control back to the point where setjmp() was called by using the information saved in env. Following a successful longjmp(), execution continues as if setjmp() had returned for a second time. This "fake" return can be distinguished from a true setjmp() call because in this case, setjmp() returns the value provided in val. להלן דוגמת קוד אשר משתמשת בפונקציות setjmp,longjmp ומדפיסה: after setjmp after longjmp כעת נתונה התוכנית הבאה: 1. jmp_buf buffer1, buffer2; 2. 3. void thread2(); 4. 5. void thread1() { 6. int v = 1; 7. printf("(A1)"); 8. V = setjmp(buffer1); 9. if (v == 0) { 10. thread2(); 11. } else { 12. printf("(A2)(v=%d)",v); 13. } 14. } 15. 16. void thread2() { 17. int v = 2; 18. printf("(B1)"); 19. 20. 21. 22. } else { 23. v = setjmp(buffer2); if (v == 0) { longjmp(buffer1, 3); printf("(B2)(v=%d)",v); 24. } 25. } 26. 27. int main() { 28. thread1(); 29. return 0; 30. } ספריית ULTL שומרת את הקשרי הביצוע של החוטים במערך גלובאלי בגודל N: jmp_buf g_buf[N]; החלפת הקשר בין חוטים של אותו תהליך מתבצעת ע"י קריאה לפונקציה context_switch אשר מקבלת שני פרמטרים: prev - מזהה החוט הנוכחי, next - מזהה החוט הבא לביצוע. מה המימוש הנכון של הפונקציה context_switch?
Full original question text (raw OCR)
שאלה 3 - חוטים (25 נק')
(5 נק') אילו אובייקטים הם ייחודיים לכל חוט (כלומר מוקצים בנפרד לכל אחד מהחוטים של אותו תהליך)? .a הערימה (heap) b. מחסנית המשתמש (user stack). c. הקוד של התכנית (text section). d. טבלת הקבצים הפתוחים (file descriptor table) e. טבלת הדפים (page table) f. מתאר מרחב הזיכרון (memory descriptor) נמקו:
fork/exec address-space semanticsPipe IPC semanticsVirtual-to-physical address translation(5 נק') מה תדפיס התוכנית? (A1)(B1) .a (A1)(A2)(v=1).b (A1)(A2)(v=1)(B1)(B2)(v=2) .C (A1)(B1)(A2)(v=3) .d (A1)(B1)(A2)(v=2)(B2)(v=1) .е (A1)(B1)(A2)(v=3)(B2)(v=1) .f נמקו:
pthread create/cancel/join lifecyclePipe IPC semanticsMutex correctness and deadlock avoidance(5 נק') ספריית ULTL שומרת את הקשרי הביצוע של החוטים במערך גלובאלי בגודל N: jmp_buf g_buf[N]; החלפת הקשר בין חוטים של אותו תהליך מתבצעת ע"י קריאה לפונקציה context_switch אשר מקבלת שני פרמטרים: prev - מזהה החוט הנוכחי, next - מזהה החוט הבא לביצוע. מה המימוש הנכון של הפונקציה context_switch? void context_switch(int prev, int next){ a. b. if(setjmp(g_buf[prev]) == 0) if(setjmp(g_buf[prev]) == 1) longjmp(g_buf[next], 1); longjmp(g_buf[next], 1); c. d. if(setjmp(g_buf[next]) == 0) if(setjmp(g_buf[next]) == 1) longjmp(g_buf[prev], 1); longjmp(g_buf[prev], 1); e. f. longjmp(g_buf[next], 1); setjmp(g_buf[prev]); setjmp(g_buf[prev]); longjmp(g_buf[next], 1); } נמקו:
Voluntary vs preemptive context switchPipe IPC semantics(5 נק') מה היתרונות של ספריית ULTL על-פני pthreads a. ניתן להריץ חוטים שונים של אותו תהליך על מעבדים שונים בו-זמנית. b. ביצוע של חוט לא יכול להיקטע ע"י פסיקת חומרה. c. החלפת הקשר בין חוטים של אותו תהליך היא זולה יותר כי אין צורך לחמם מטמונים. d. החלפת הקשר בין חוטים של אותו תהליך היא זולה יותר כי לא מחליפים טבלת דפים. e. קבצים שנפתחו ע"י חוט אחד יהיו נגישים גם לשאר החוטים באותו תהליך. f. הספריה פורטבילית, כלומר ניתן להדר את הקוד כמו שהוא על מערכות הפעלה שונות. נמקו:
Voluntary vs preemptive context switchLocal vs global interrupt disablePipe IPC semanticsPreemption trigger identification(5 נק') מה היתרונות של ספריית pthreads על-פני ULTL? a. ניתן להריץ חוטים שונים של אותו תהליך על מעבדים שונים בו-זמנית. b. ביצוע של חוט לא יכול להיקטע ע"י פסיקת חומרה. c. החלפת הקשר בין חוטים של אותו תהליך היא זולה יותר כי אין צורך לחמם מטמונים. d. החלפת הקשר בין חוטים של אותו תהליך היא זולה יותר כי לא מחליפים טבלת דפים. e. קבצים שנפתחו ע"י חוט אחד יהיו נגישים גם לשאר החוטים באותו תהליך. f. הספריה פורטבילית, כלומר ניתן להדר את הקוד כמו שהוא על מערכות הפעלה שונות. נמקו:
Voluntary vs preemptive context switchLocal vs global interrupt disablePipe IPC semanticsPreemption trigger identification
The exam question — original PDF
pages 10, 11, 12, 13Exactly 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
FD (file descriptors)כל פעולות קלט/פלט של תהליך בלינוקס מבוצעות דרך "קבצים":קבצים "רגילים" לאחסון מידע (/usr/file.txt) נמצאים בדיסק.התקני חומרה גם כן מיוצגים כקבצים, אבל נמצאים בזיכרון.למשל, העכברים המחוברים למחשב מיוצגים כ- /dev/input/mouseN .גם ערוצי תקשורת כמו pipes מיוצגים ע"י קבצים שנמצאים בזיכרון.הקשר בין תהליך לבין קובץ שהוא ניגש אליו נשמר, ברמת המשתמש, ע"י מספר שלם שנקרא file descriptor (FD).לדוגמה: קריאת המערכת open() מחזירה FD.המשתמש מעביר את ה-FD לקריאות מערכת כמו read(), write() כדי לקרוא ולכתוב לקובץ.מערכות הפעלה - תרגול 320
שחרור file objectשאלה: מי מבצע את שחרור הזיכרון של file object? מתי ניתן לשחררו? ייתכנו מצבים בהם תהליכים שונים מצביעים לאותו file object, לכן שחרור ה-file object יכול להתבצע רק לאחר ביצוע close() מכל התהליכים החולקים את אותו ה-file object. זכרו של-file object יש מונה (f_count) הסופר את כמות התהליכים המצביעים עליו בכל רגע נתון. המונה קטן באחד עם כל פעולת close() על האובייקט. כאשר המונה מתאפס, ה-file object ישוחרר.מערכות הפעלה - תרגול 342
מהי החלפת הקשר?מערכות הפעלה - תרגול 610
מהי החלפת הקשר?לכל תהליך יש "הקשר ביצוע" (execution context) המכיל את כל המידע הדרוש לביצוע התהליך.מחסניות, רגיסטרים, תכולת זיכרון, קבצים פתוחים, ..."החלפת הקשר" = עצירת הביצוע של התהליך הנוכחי ושמירת ההקשר שלו.טעינת ההקשר של התהליך הבא לביצוע.הקשר התהליך הנוכחי מתחלף – מכאן שם הפעולה "החלפת הקשר".מערכות הפעלה - תרגול 611
שני סוגים של החלפת הקשרהחלפת הקשר כפויה(== הפקעה)הגרעין מפקיע (כלומר, לוקח בכוח) את המעבד מהתהליך, למשל בעקבות:פסיקת שעון (מטופלת בשגרה scheduler_tick) אשר מגלה כי הזמן שהוקצב לתהליך הנוכחי אזל.אירוע אסינכרוני אשר מעיר תהליך בעל עדיפות טובה יותר מהתהליך הרץ כרגע.לדוגמה: פסיקת דיסק או שחרור מנעול שתהליך המתין לו.החלפת הקשר יזומההתהליך מוותר מרצונו על המעבד, למשל באמצעות:קריאת מערכת חוסמת (כמו wait(), read(), …) אשר מוציאה את התהליך להמתנה.קריאת מערכת exit() אשר מסיימת את התהליך.קריאת מערכת sched_yield() – קריאת מערכת ייעודית לוויתור על המעבד.מערכות הפעלה - תרגול 613
הפקעה (preemption)בעיה: תהליך משתמש עלול לרוץ לנצח (למשל, לולאה אינסופית) ולמנוע את המעבד משאר התהליכים.פגיעה בהוגנות (fairness) ותגובתיות (rrsponsiveness).פתרון: לינוקס מפקיעה (preempt) את המעבד מתהליך אחד לטובת תהליך אחר, בעזרת התקן חומרה מיוחד – השעון.מערכת ההפעלה מבקשת מהשעון לשלוח פסיקה במרווחי זמן קבועים כדי להעביר את השליטה למערכת ההפעלה.כל הפסיקות, בפרט פסיקת שעון, מטופלות במצב גרעין, ואז הגרעין מחליף הקשר אם יש צורך.מערכות הפעלה - תרגול 614
יצירת חוט חדשפרמטרים:thread – מצביע למקום בו יאוחסן מזהה החוט החדש במקרה של סיום הפונקציה בהצלחה.attr – מאפיינים המתארים את תכונות החוט החדש, כגון האם החוט הוא חוט גרעין או חוט משתמש, האם ניתן לבצע לו join, כלומר להמתין לסיומו, וכו'. בד"כ נספק ערך NULL המציין חוט ברירת המחדל של המערכת, שניתן להמתין לסיומו.void* (*start_routine)(void*) מצביע לפונקציה שתהווה את קוד החוט. הערך המוחזר מפונקציה זו במקרה של סיומה הטבעי הינו ערך הסיום של החוט.arg – פרמטר שיסופק לפונקציה עם הפעלתה.מערכות הפעלה - תרגול 714
משתנה תנאי (condition variable)משתנה תנאי הוא אובייקט סנכרון המאפשר לחוט לצאת להמתנה בתוך קטע קריטי.כלומר, לפנות את המעבד ולצאת לתור המתנה.ההמתנה תתבצע עד לקיום תנאי כלשהו.ההמתנה מאפשרת לאכוף סדר בביצוע של החוטים. שימוש תכנותי נכון במשתני תנאי מחייב להגדיר גם:משתנה מצב – החוט עובר להמתנה או חוזר מהמתנה בהתאם לערכו של משתנה המצב.מנעול mutex – מבטיח לנו אטומיות והגנה על הקטע הקריטי.מערכות הפעלה - תרגול 86
סכימה כללית למשתני תנאיcond_t c; // should be initializedmutex_t m; // should be initializedint state_var = 0;החוט הממתין לאירוע יקרא ל:while (!condition_holds(state_var)) cond_wait(&c, &m);החוט שמסמן לחוטים הממתינים להמשיך יקרא ל:if (condition_holds(state_var)) cond_signal(&c);מערכות הפעלה - תרגול 87מדוע cond_wait() מקבלתגם את המנעול?
המתנה על משתני תנאיint pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);פעולה: משחררת את המנעול ומעבירה את החוט להמתין על משתנה התנאי באופן אטומי (ראינו קודם מדוע זה הכרחי).החוט הממתין חייב להחזיק במנעול mutex לפני הקריאה.בחזרה מהמתנה על משתנה התנאי, החוט עובר להמתין על המנעול. החוט יחזור מהקריאה ל-pthread_cond_wait() רק לאחר שינעל מחדש את ה-mutex.ערך מוחזר: הפעולה תמיד מצליחה ומחזירה 0.11מערכות הפעלה - תרגול 8
טבלת הדפים (page table)לכל תהליך יש טבלת דפים משלו – מבנה נתונים אשר ממפה בין דפים למסגרות.ניתן לממש טבלת דפים באמצעות מבני נתונים שונים: מערך פשוט, עצים, טבלאות גיבוב (hash tables), ...עבור כל דף במרחב הזיכרון הווירטואלי של התהליך, יש כניסה בטבלת הדפים אשר מציינת:האם הדף נמצא בזיכרון ובאיזו מסגרת?האם הדף נמצא בדיסק ובאיזה מיקום?האם הדף מעולם לא הוקצה? (כלומר איננו בזיכרון ואיננו בדיסק)טבלת הדפים אחראית לתפקידים נוספים כמו הגנת גישה.למשל: טבלת הדפים מסמנת דפים לקריאה בלבד ומונעת גישות כתיבה.19מערכות הפעלה - תרגול 10
סיכום: תהליך התרגום במעבדי אינטל39the CPU searches the TLBhitmissthe CPU walks the page tablecompletedpage faultphysical addressvirtual addressthe OS serves the page faultמערכות הפעלה - תרגול 10
The exam text, the skills it tests, and the exact slides are already in context.