תזכורת: בהרצאה ראיתם את תכונות המנעולים הבאות: • מניעה הדדית: בכל רגע נתון לכל היותר חוט אחד נמצא בתוך בקטע הקריטי. • אין קיפאון: אם תהליך מנסה להיכנס לקטע הקריטי בנקודת זמן מסוימת אז לאחר מכן תהליך כלשהו הצליח להיכנס לקטע הקריטי. • אין הרעבה: אם תהליך כלשהו מנסה להיכנס לקטע הקריטי בנקודת זמן מסוימת אז לאחר מכן התהליך הזה הצליח להיכנס לקטע הקריטי. • המתנה חסומה: קיים N טבעי כך שאם תהליך מנסה להיכנס לקטע הקריטי, אז לכל היותר N פעמים תהליכים אחרים יצליחו להיכנס לקטע הקריטי לפניו. להלן שלושה מימושים שונים של mutex ללא עזרת הגרעין. עליכם לסמן ולנמק אילו מהתכונות הנ"ל מקיים כל מימוש. התעלמו מבעיות consistency and coherency. יש להניח שכל החוטים במערכת נמצאים במצב RUNNABLE. על מנת לפשט את השאלה הניחו כי השמת ערך למשתנה וקריאתו הינן אטומיות. מימוש 1 (6 נק'): struct mutex { int locked; // initialized to 0 } void lock(mutex* m) { while (m->locked == 1); // busy wait m->locked = 1; } void unlock(mutex* m) { m->locked = 0; } מימוש 2 (8 נק'): המימוש משתמש בפקודה testAndSet, אשר מבצעת באופן אטומי את הפעולה הבאה: int testAndSet(int *ptr) { int old = *ptr; // fetch old value at ptr *ptr = 1; // store '1' into ptr return old; // return the old value } להלן המימוש: typedf struct mutex { int locked; } mutex; void init(mutex* m) { m->locked = 0; } void lock(mutex* m) { while(testAndSet(&m->locked) == 1); } void unlock(mutex* m) { m->locked = 0; } מימוש 3 (10 נק'): המימוש משתמש בפקודה fetchAndInc, אשר מבצעת באופן אטומי את הפעולה הבאה: int fetchAndInc(int *ptr) { int old = *ptr; // fetch old value at ptr *ptr = old + 1; // store 'old + 1' into ptr return old; // return the old value } להלן המימוש: struct mutex { int waitArray[n]; int last; int n; // number of threads int curr; } void init(mutex* m, int n) { for (int i = 0; i < n; i++) m->waitArray[i] = 0; m->waitArray[0] = 1; m->last = 0; m->n = n; m->curr = 0; } void lock(mutex* m) { int loc = fetchAndInc(&m->last) % m->n; while (m->waitArray[loc] != 1); m->waitArray[loc] = 0; m->curr = loc; } void unlock(mutex* m) { m->waitArray[(m->curr + 1) % m->n] = 1; }
Full original question text (raw OCR)
שאלה 2 - סינכרוניזציה (30 נק')
struct mutex { int locked; // initialized to 0 } void lock(mutex* m) { while (m->locked == 1); // busy wait m->locked = 1; } void unlock(mutex* m) { m->locked = 0; } הקיפו בעיגול את התשובה הנכונה ונמקו או הפריכו. 1. האם המימוש מקיים את תכונת מניעה הדדית? כן \ לא נימוק:
Spinlock implementation propertiesMutex correctness and deadlock avoidance2. האם המימוש מקיים את תכונת אין קיפאון? נימוק:
Process state transitions3. האם המימוש מקיים את תכונת אין הרעבה? כן \ לא נימוק:
Process state transitions4. האם המימוש מקיים את תכונת המתנה חסומה (אם כן, יש לציין עבור איזה N)? כן \ לא נימוק:
Process state transitionsהקיפו בעיגול את התשובה הנכונה ונמקו או הפריכו. 1. האם המימוש מקיים את תכונת מניעה הדדית? כן \ לא נימוק:
Process state transitions2. האם המימוש מקיים את תכונת אין קיפאון? כן \ לא נימוק:
Process state transitions3. האם המימוש מקיים את תכונת אין הרעבה? כן \ לא נימוק:
Process state transitions4. האם המימוש מקיים את תכונת המתנה חסומה (אם כן, יש לציין עבור איזה N)? כן \ לא נימוק:
Process state transitionsהקיפו בעיגול את התשובה הנכונה ונמקו או הפריכו. 1. האם המימוש מקיים את תכונת מניעה הדדית? כן \ לא נימוק:
Process state transitions2. האם המימוש מקיים את תכונת אין קיפאון? כן \ לא נימוק:
Process state transitions3. האם המימוש מקיים את תכונת אין הרעבה? כן \ לא נימוק:
Process state transitions4. האם המימוש מקיים את תכונת המתנה חסומה (אם כן, יש לציין עבור איזה N)? כן \ לא נימוק:
Process state transitionsנניח שהפעולות fetchAndInc i testAndSet הינן פעולות כבדות מבחינה חישובית, כלומר, פעולות אלו לוקחות זמן רב ביחס לפקודת מעבד רגילה, אך עדיין הן לוקחות פחות זמן מאשר החלפת הקשר בגרעין. ב. (6 נק') קים ג'ונג-און, רודן ידוע ומעצב שיער בהתהוות, ידוע בשל חיבתו לאטומיות ולכן החליט לבצע את המבחן הבא לבדיקת ביצועי מנעולים: 1. mutex m; 2. void* func(void* param) { 3. m.lock(); 4. m.unlock(); 5. return null; 6. } 7. 8. int main() { 9. m.init(); 10. pthread_t threads [5000];; 11. for (int i = 0 ; i < 5000 ; i++) { 12. 13. } 14. for (int i 15. pthread_create(threads + i, NULL, func, NULL); = 0; i < 5000; i++) { pthread_join(threads[i], NULL); 16. } 17. return 0; 18. } להפתעתו גילה קים כי עבור מנעול ממימוש 3 שהוצג לעיל, בממוצע התוכנית איטית באופן ניכר ביחס לשימוש במנעול mutex מסוג מהיר שנלמד בתרגולים. הסבירו לקים את התופעה (אבל בזהירות, הוא בחור עצבני...) הסבר:
Voluntary vs preemptive context switchPipe IPC semanticsMutex correctness and deadlock avoidance
The exam question — original PDF
pages 4, 5, 6, 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.
Process states created service provided ready preempted scheduled waiting finished or killed requires “slow” service (notably I/O) zombie running termination process is process is status collected runnable sleeping OS (234123) - processes & signals 4
קריאת המערכת wait()pid_t wait(int *wstatus);פעולה: ממתינה עד אשר אחד מתהליכי הבן יסיים.פרמטרים:wstatus – מצביע למשתנה בו יאוחסנו פרטים על תהליך הבן שהסתיים.למשל, wstatus יכיל את ערך הסיום של הבן (הערך שהעביר כארגומנט ל-exit()). ערך הסיום מופיע בבית השני מתוך ארבעת בתי ה- wstatus. כדי לחלץ אותו יש לנצל את המאקרו WEXITSTATUS(*wstatus), המחזיר (*wstatus>>8) & 0xff. במידה ולא מעוניינים בסטטוס הבן שסיים, אפשר להעביר NULL.ערך מוחזר:אם אין בנים או שכל הבנים כבר סיימו ובוצע להם wait() – יוחזר מיד הערך -1.אם יש בנים שסיימו ועדיין לא בוצע עבורם wait() (כלומר הם במצב zombie – יפורט בשקופיות הבאות) – יוחזר מיד ה-pid של אחד הבנים הנ"ל.אחרת – המתנה עד שבן כלשהו יסיים.מערכות הפעלה - תרגול 214איך תהליך אב יכול לחכות לסיום כל תהליכי הבן?מבינים את החישוב?
סיום תהליכיםכדי לאפשר לאב לקבל מידע על סיום הבן, לאחר שתהליך מסיים את פעולתו הוא עובר למצב מיוחד – zombie – שבו התהליך קיים כרשומת נתונים בלבד ללא שום ביצוע משימה.הרשומה נמחקת לאחר שהאב קיבל את המידע על סיום הבן באמצעות wait().שאלה: מה קורה לתהליך "יתום" (orphan), כלומר תהליך שסיים לאחר שאביו כבר סיים בלי לקרוא ל-wait() ?התהליך הופך להיות בן של init.התהליך init ממשיך להתקיים לאורך כל פעולת המערכת.אחד מתפקידיו העיקריים – המתנה לכל בניו כדי לפנות את נתוניהם לאחר סיומם.מערכות הפעלה - תרגול 219
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
יצירת חוט חדשפרמטרים:thread – מצביע למקום בו יאוחסן מזהה החוט החדש במקרה של סיום הפונקציה בהצלחה.attr – מאפיינים המתארים את תכונות החוט החדש, כגון האם החוט הוא חוט גרעין או חוט משתמש, האם ניתן לבצע לו join, כלומר להמתין לסיומו, וכו'. בד"כ נספק ערך NULL המציין חוט ברירת המחדל של המערכת, שניתן להמתין לסיומו.void* (*start_routine)(void*) מצביע לפונקציה שתהווה את קוד החוט. הערך המוחזר מפונקציה זו במקרה של סיומה הטבעי הינו ערך הסיום של החוט.arg – פרמטר שיסופק לפונקציה עם הפעלתה.מערכות הפעלה - תרגול 714
מנעולים עם/בלי המתנהspinlockכאשר חוט מנסה לתפוס מנעול נעול, הוא בודק את ערך המנעול שוב ושוב מבלי לצאת מתור הריצה.טכניקה כזו נקראת גם: polling, busy waiting, busy looping.יתרון: התהליך יכול להמשיך לרוץ עוד בקוונטום הנוכחי, וכך לחסוך את התקורה על החלפת הקשר.עדיף כאשר זמן ההמתנה המשוער נמוך יותר מהמחיר של החלפת הקשר (כלומר, כאשר הקטע הקריטי קצר, כפי שקורה לרוב בקוד גרעין).mutexכאשר חוט מנסה לתפוס מנעול נעול, מערכת ההפעלה תעביר אותו לתור המתנה ותבצע החלפת הקשר.כאשר המנעול ישוחרר, מערכת ההפעלה תעיר את אחד החוטים המחכים למנעול.יתרון: תהליך חדש יכול לרוץ מיד, וכך לא מתבזבז זמן מעבד יקר.עדיף כאשר זמן ההמתנה המשוער גבוה יחסית (כלומר, כאשר הקטע הקריטי ארוך, כפי שקורה לרוב בקוד משתמש).מערכות הפעלה - תרגול 745
משתנה תנאי (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
פסיקות חומרה במערכת מרובת ליבותבמערכת מרובת ליבות, מעבדים שונים יכולים לגשת בו-זמנית למבני נתונים משותפים יש להוסיף נעילה מעבר לחסימת הפסיקות המקומית.שגרות טיפול בפסיקות חומרה עושות שימוש במנעולי spinlock (מנעולים הממומשים כ-busy wait).שאלה: מדוע מעדיפים מנעולי spinlock על-פני מנעולי סמפור?busy wait הוא המתנה יעילה יותר כאשר מדובר בנעילות קצרות מאוד כפי שקורה בגרעין, מפני שכך נחסכת התקורה של כניסה ויציאה מהמתנה.בעיית הוגנות, למשל בתרחיש הבא:תהליך רץ, ובאותו הזמן מתקבלת פסיקת חומרה (למשל מהמקלדת).הטיפול בפסיקה מנסה לתפוס את המנעול, אבל המנעול כבר תפוס.התהליך עובר לתור המתנה מסיבה שאינה תלויה בו.מערכות הפעלה - תרגול 856
The exam text, the skills it tests, and the exact slides are already in context.