Synchronization & Threadshigh-yield

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. האם המימוש מקיים את תכונת מניעה הדדית? כן \ לא נימוק:

2. האם המימוש מקיים את תכונת אין קיפאון? נימוק:

3. האם המימוש מקיים את תכונת אין הרעבה? כן \ לא נימוק:

4. האם המימוש מקיים את תכונת המתנה חסומה (אם כן, יש לציין עבור איזה N)? כן \ לא נימוק:

הקיפו בעיגול את התשובה הנכונה ונמקו או הפריכו. 1. האם המימוש מקיים את תכונת מניעה הדדית? כן \ לא נימוק:

2. האם המימוש מקיים את תכונת אין קיפאון? כן \ לא נימוק:

3. האם המימוש מקיים את תכונת אין הרעבה? כן \ לא נימוק:

4. האם המימוש מקיים את תכונת המתנה חסומה (אם כן, יש לציין עבור איזה N)? כן \ לא נימוק:

הקיפו בעיגול את התשובה הנכונה ונמקו או הפריכו. 1. האם המימוש מקיים את תכונת מניעה הדדית? כן \ לא נימוק:

2. האם המימוש מקיים את תכונת אין קיפאון? כן \ לא נימוק:

3. האם המימוש מקיים את תכונת אין הרעבה? כן \ לא נימוק:

4. האם המימוש מקיים את תכונת המתנה חסומה (אם כן, יש לציין עבור איזה N)? כן \ לא נימוק:

נניח שהפעולות 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 מסוג מהיר שנלמד בתרגולים. הסבירו לקים את התופעה (אבל בזהירות, הוא בחור עצבני...) הסבר:

ייתכן מקרה בו הספר ישן ויש לקוחות שממתינים לתורם (נכון / לא נכון)

ייתכן שלקוח יצא מהמספרה בלי להסתפר (נכון / לא נכון)

במצב שיש יותר מספר אחד, ייתכן שאחד הספרים ישן כאשר יש מספר לקוחות (ממתינים + מסתפרים כעת) גדול ממספר הספרים (נכון / לא נכון)

(4 נק') בהתייחס לקוד הנ״ל, הקיפו את התשובות הנכונות הסבר a. קיימת בעיית נכונות עקב race condition למשאבים משותפים.

c. הקוד משתמש ב-Busy Wait שפוגע בנצילות המעבד.

d. הקוד מפר את כללי הכניסה לחדר ההמתנה (שהוגדרו בתחילת השאלה).

(8 נק') בהתייחס לקוד הנ״ל, הקיפו את התשובות הנכונות (בהתייחסות לספר יחיד) a. קיימת בעיית נכונות עקב race condition למשאבים משותפים.

c. הקוד משתמש ב-Busy Wait שפוגע בנצילות המעבד.

d. הקוד מפר את כללי הכניסה לחדר ההמתנה (שהוגדרו בתחילת השאלה). הסבירו, והדגימו באמצעות תרחישים אפשריים.

(5 נק') הציעו דרך פשוטה לתקן את הקוד (תיאור מילולי - בהתייחסות לספר אחד)

(5 נק') סאמי שם לב שהקוד הנ"ל (מסעיף ג) לא עובד כמו שצריך ולכן עבד קשה לתקן אותו. לאחר שהוא תיקן את כל הבעיות שיש בקוד, הוא שם לב שהקוד המתוקן עדיין לא עובד במקרה של יותר מספר אחד. תארו תרחיש בעייתי שקורה רק במצב שיש יותר מספר אחד (בעיה שלא הוזכרה קודם) ואיך לתקן אותו.

(7 נק') לקוד זה 7 אופציות להדפסה מתוך ה-15 הבאות. יש להקיף את האופציות הנכונות. אין צורך להסביר את פתרונכם. כלום Andrey Leonid Sasha Andrey Leonid Andrey Sasha Sasha Leonid Andrey Andrey Andrey Leonid Sasha Sasha Andrey Leonid Leonid Sasha Leonid Andrey Leonid Sasha Andrey Sasha Andrey Leonid Andrey Sasha Leonid

(6 נק') הקוד של אחינועם בעייתי כאשר מספר חוטים משתמשים במחלקה במקביל. סמנו את כל התשובות הנכונות (תיתכן יותר מאחת) מהתשובות הבאות: a. הקוד בזבזני בגלל שמבצע Busy Wait לשווא b. השימוש במחלקה יכול לגרום ל-Deadlock c. יתכן Race condition אם החוטים קוראים לפונקציה plusOne במקביל d. יתכן Race condition אם החוטים קוראים לפונקציות getVal ו-plusOne במקביל e. יתכן Race condition אם החוטים קוראים לפונקציות doubleVal ו-getVal במקביל f. בקוד זה תתכן הרעבה של כותבים g. בקוד זה תתכן הרעבה של קוראים

הסבירו רק על הבעיות שסימנתם, ללא התייחסות לסעיפים שלא סומנו.

(6 נק') הקוד החדש של אחינועם עדיין בעייתי. סמנו את כל התשובות הנכונות (תיתכן יותר מאחת) מהתשובות הבאות: a. הקוד בזבזני בגלל שמבצע Busy Wait לשווא b. השימוש במחלקה יכול לגרום ל-Deadlock c. יתכן Race condition אם החוטים קוראים לפונקציה plusOne במקביל d. יתכן Race condition אם החוטים קוראים לפונקציות getVal ו-plusOne במקביל e. יתכן Race condition אם החוטים קוראים לפונקציות doubleVal ו-getVal במקביל f. בקוד זה תתכן הרעבה של כותבים g. בקוד זה תתכן הרעבה של קוראים

הסבירו רק על הבעיות שסימנתם, ללא התייחסות לסעיפים שלא סומנו.

(6 נק') בקוד הנתון בעיה חמורה בעת שימוש במחלקה זו ע"י מספר חוטים במקביל. סמנו את כל התשובות הנכונות (תיתכן יותר מאחת) מהתשובות הבאות: a. הקוד בזבזני בגלל שמבצע Busy Wait לשווא b. השימוש במחלקה יכול לגרום ל-Deadlock c. יתכן Race condition אם החוטים קוראים לפונקציה plusOne במקביל d. יתכן Race condition אם החוטים קוראים לפונקציות getVal ו-plusOne במקביל e. יתכן Race condition אם החוטים קוראים לפונקציות doubleVal ו-getVal במקביל f. בקוד זה תתכן הרעבה של כותבים g. בקוד זה תתכן הרעבה של קוראים

הסבירו רק על הבעיות שסימנתם, ללא התייחסות לסעיפים שלא סומנו.

(5 נק') שימו לב: בסעיף זה נתייחס לנכונות הפונקציה getVal בלבד. נביט בסעיף זה על המימוש הראשוני מסעיף (ב). המהנדס הנודע (וחובב הטחינה המושבע) איליה טען שאין צורך במנעול בפונקציה getVal, והציע מימוש חדש לפונקציה getVal: מימוש קודם int getVal() { int ret_val; mutex_lock(&m); ret_val = val; mutex_unlock(&m); return ret_val; } מימוש חדש מוצע int getVal() { return val; } בהנחה שהמשתנה val יכול להיקרא ולהיכתב במקביל בפונקציות אחרות בקוד ע"י מספר חוטים, כתבו במשפט אחד את התנאי לכך שהמימוש שאיליה הציע יהיה נכון: הסבירו:

(1 נק') יכולים להיות שני סטודנטים מפקולטות שונות באותו חדר במקביל: נכון / לא נכון

(1 נק') יכולים להיות שני סטודנטים מפקולטות זהות בחדר במקביל: נכון / לא נכון

(1 נק') סטודנטי פקולטה אחת עלולים להרעיב (כניסת) סטודנטי פקולטה אחרת: נכון / לא נכון

(8 נק') בהתייחס לקוד הנ״ל, הקיפי את כל התשובות הנכונות (עשויה להיות יותר מאחת). עבור כל תשובה שהקפת, תארי דוגמת הרצה המובילה לתשובה זו. a. קיימת בעיית נכונות עקב condition race למשאבים משותפים. b. קיימת בעיית Livelock / DeadLock בקוד. c. הקוד משתמש ב-Wait Busy שפוגע בנצילות המעבד. d. הקוד מפר את כלל הכניסה לחדר (שהוגדר בתחילת השאלה). נימוק:

אך דני (עתודאי במדמ"ח) טען שקוד זה גורם לחוטים להתעורר שלא לצורך ומיד לחזור למצב המתנה. (4 נק') הסבירי את טענתו של דני באמצעות דוגמת ריצה קונקרטית.

(5 נק') כיצד ניתן לתקן את הבעיה שהציג דני בסעיף הקודם? נימוק:

(8 נק') בהתייחס לקוד הנ״ל, הקיפי את כל התשובות הנכונות (עשויה להיות יותר מאחת). עבור כל תשובה שהקפת, תארי דוגמת הרצה המובילה לתשובה זו. a. יתכנו 2 סטודנטים מפקולטות שונות בתוך החדר ביחד, עקב race condition למשאב משותף. b. יתכן סטודנט שלא נכנס לחדר למרות כלל הכניסה שמתיר זאת, עקב race condition למשאב משותף. c. קיימת בעיית DeadLock / Livelock בקוד. d. סיגנלים עלולים ללכת לאיבוד. נימוק:

הסבירו את המונחים הבאים בקצרה: a. קטע קריטי b. מניעה הדדית c. Race condition d. Deadlock

בהינתן קטעי הקוד משני חוטים (X ו-Y משתנים בוליאניים משותפים שמאותחלים באופן רנדומלי לפני שהחוטים מגיעים לקטעי קוד הבאים): Thread1: while (X == Y); // critical section X = Y; Thread 2: while(X != Y); // critical section X = !Y; אילו מהטיעונים הבאים נכון: a. הקוד מבטיח מניעה הדדית, אבל לא מבטיח ״התקדמות" (progress). b. הקוד מבטיח התקדמות, אבל לא מבטיח מניעה הדדית. c. הקוד לא מבטיח התקדמות ולא מבטיח מניעה הדדית. d. הקוד מבטיח מניעה הדדית והתקדמות. נימוק:

להלן הצעה למימוש מנעול: המשתנה L משתנה מסוג int שמאותחל ל- 0, הפונקציה (fetch_and_add(x,c מבצעת את הפעולות הבאות באופן אטומי: קוראת ערך המשתנה x, מוסיפה אליו c ומחזירה את הערך לפני ההוספה. lock(L) { while (fetch_and_add(L, 1)) { L = 1; } } unlock(L) { L = 0; } האם המימוש הנ"ל עובד? כן / לא הסבירו בקצרה (אם המימוש לא עובד, תארו תרחיש בעייתי): נימוק:

בהינתן השינוי הבא בקוד מסעיף קודם: lock(L) { while (fetch_and_add(L, 1)); } unlock(L) { L = 0; } האם המימוש החדש עובד? כן / לא הסבירו בקצרה (אם המימוש לא עובד, תארו תרחיש בעייתי): נימוק:

יונתן, סטודנט לקורס מערכות הפעלה מימש מנעול חדש שתומך בשתי הפעולות הבאות: struct my_lock { unsigned int value = 0; }; void lock (struct my_lock *s) { unsigned int y; unsigned int *x = &(s->value); do { fetch_and_set(x, &y); } while (y); } void unlock (struct my_lock *s) { s->value = 0; } כאשר (fetch_and_set(x,y פעולה אטומית שמעדכנת את הערך ש- x מצביע עליו ל- 1, ושומרת את הערך הקודם בתוך המשתנה y. א ) אילו מהטיעונים הבאים נכון: 1. הקוד לא מבטיח מניעה הדדית. 2. המנעול עובד באופן תקין. 3. במערכת מרובת מעבדים, הקוד עלול ליצור deadlock. 4. במערכת מרובת מעבדים, הקוד לא מבטיח מניעה הדדית. נימוק:

ב) בהנחה שהמנעול הנ"ל עובד (תוקן במידת הצורך), משיקולי יעילות, באיזה מרחב (גרעין או משתמש) עדיף להשתמש במנעול כזה? גרעין / משתמש נימוק:

(4 נק') בניסיון הראשון כתב אוהד את הקוד הבא: int done; void initialize() { done = 0; } void* first(void* p) { printf("I should run first.\n"); done = 1; return NULL; } void* second(void* p) { while (!done); printf("I should run second.\n"); return NULL; } void finalize() { } דנית טענה ללא היסוס כי הקוד של אוהד אמנם נכון, אבל בזבזני. הסבירו את טענתה של דנית.

(5 נק') דנית הציעה להשתמש במשתנה תנאי ומנעול mutex כדי לפתור את הבעיה שהייתה בקוד של אוהד: pthread_cond_t c; pthread_mutex_t m; void initialize() { pthread_mutex_init(&m, NULL); pthread_cond_init(&c, NULL); } void* first(void* p) { printf("I should run first.\n"); pthread_cond_signal(&c); return NULL; } void* second(void* p) { pthread_mutex_lock(&m); pthread_cond_wait(&c, &m); pthread_mutex_unlock(&m); printf("I should run second.\n"); return NULL; } void finalize() { pthread_mutex_destroy(&m); pthread_cond_destroy(&c); } למרבה הצער, אוהד הבחין מיד כי הפתרון של דנית שגוי. תארו בפירוט מדוע הקוד שגוי, כלומר תארו תרחיש מסוים שבו הקוד של דנית לא יפעל כנדרש.

(5 נקודות) אוהד ודנית לא התייאשו והציעו פתרון שלישי לבעיה: pthread_cond_t c; pthread_mutex_t m; int done; void initialize() { done = 0; pthread_mutex_init(&m, NULL); pthread_cond_init(&c, NULL); } void* first(void* p) { printf("I should run first.\n"); done = 1; pthread_cond_signal(&c); return NULL; } void* second(void* p) { pthread_mutex_lock(&m); while (!done) { pthread_cond_wait(&c, &m); } pthread_mutex_unlock(&m); printf("I should run second.\n"); return NULL; } void finalize() { pthread_mutex_destroy(&m); pthread_cond_destroy(&c); } אך שוב אוהד ודנית התאכזבו כאשר המתרגל רמז להם כי הפתרון הנ"ל שגוי. תארו בפירוט מדוע הקוד שגוי, כלומר תארו תרחיש מסוים שבו הקוד הנ"ל לא יפעל כנדרש.

(6 נקודות) השלימו את המימוש המוצע מטה, תוך שימוש במשתנה תנאי יחיד ומנעול mutex יחיד. pthread_cond_t c; pthread_mutex_t m; int done; void initialize() { done = 0; pthread_mutex_init(&m, NULL); pthread_cond_init(&c, NULL); } void* first(void* p) { printf("I should run first.\n"); return NULL; } void* second(void* p) { printf("I should run second.\n"); return NULL; } void finalize() { pthread_mutex_destroy(&m); pthread_cond_destroy(&c); }

(5 נקודות) הציעו מימוש תקין העושה שימוש בסמפור יחיד. sem_t s; void initialize() { sem_init(&s, 0, ); /* the 3rd argument is the initial value */ } void* first(void* p) { printf("I should run first.\n"); } return NULL; void* second(void* p) { } printf("I should run second.\n"); return NULL; void finalize() { sem_destroy(&s); } הסבר:

(5 נק') אילו אובייקטים הם ייחודיים לכל חוט (כלומר מוקצים בנפרד לכל אחד מהחוטים של אותו תהליך)? .a הערימה (heap) b. מחסנית המשתמש (user stack). c. הקוד של התכנית (text section). d. טבלת הקבצים הפתוחים (file descriptor table) e. טבלת הדפים (page table) f. מתאר מרחב הזיכרון (memory descriptor) נמקו:

(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 נמקו:

(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); } נמקו:

(5 נק') מה היתרונות של ספריית ULTL על-פני pthreads a. ניתן להריץ חוטים שונים של אותו תהליך על מעבדים שונים בו-זמנית. b. ביצוע של חוט לא יכול להיקטע ע"י פסיקת חומרה. c. החלפת הקשר בין חוטים של אותו תהליך היא זולה יותר כי אין צורך לחמם מטמונים. d. החלפת הקשר בין חוטים של אותו תהליך היא זולה יותר כי לא מחליפים טבלת דפים. e. קבצים שנפתחו ע"י חוט אחד יהיו נגישים גם לשאר החוטים באותו תהליך. f. הספריה פורטבילית, כלומר ניתן להדר את הקוד כמו שהוא על מערכות הפעלה שונות. נמקו:

(5 נק') מה היתרונות של ספריית pthreads על-פני ULTL? a. ניתן להריץ חוטים שונים של אותו תהליך על מעבדים שונים בו-זמנית. b. ביצוע של חוט לא יכול להיקטע ע"י פסיקת חומרה. c. החלפת הקשר בין חוטים של אותו תהליך היא זולה יותר כי אין צורך לחמם מטמונים. d. החלפת הקשר בין חוטים של אותו תהליך היא זולה יותר כי לא מחליפים טבלת דפים. e. קבצים שנפתחו ע"י חוט אחד יהיו נגישים גם לשאר החוטים באותו תהליך. f. הספריה פורטבילית, כלומר ניתן להדר את הקוד כמו שהוא על מערכות הפעלה שונות. נמקו:

1. (4 נק) האם הקוד הבא ממש מנעול מסוג spin lock ? (כל החוטים ניגשים לאותו משתנה גלובלי lock) 01 int32 lock = 0; // initially the lock is free 02 03 void lock() { 04 while (CAS(&lock, 0, 1) == true); 05 } 06 07 void unlock() { 08 lock = 1; 09 } a. כן b. לא, כי זה מממש spinlock ולא wait lock c. לא, כי הערך המצופה (expectedValue) של CAS בשורה 4 צריך להיות 1 ולא 0 d. לא, כי צריך השמה של 0 ולא 1 בשורה 8 e. תשובות d ו-c נכונות f. אף תשובה לא נכונה נימוק:

2. (5 נק) האם הקוד הבא ממש מנעול מסוג spin lock ? (כל החוטים ניגשים לאותו משתנה גלובלי lock) 01 int32 lock = 0; // initially the lock is free 02 03 void lock() { 04 while (CAS(&lock, 0, 1) == true); 05 } 06 07 void unlock() { 08 lock = 0; 09 } a. כן b. לא, כי זה מממש spinlock ולא wait lock c. לא, כי הערך המצופה (expectedValue) של CAS בשורה 4 צריך להיות 1 ולא 0 d. לא, כי צריך השמה של 1 ולא 0 בשורה 8 e. לא, כי צריך memory fence לפני ואחרי שורה 8 או השמה דרך פקודת מכונה אטומית בשורה 8 f. תשובות d ו-c נכונות g. אף תשובה לא נכונה נימוק:

3. (6 נק) האם הקוד הבא מממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = NULL; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 Node* expectedTopNode; 12 do { 13 expectedTopNode = top; 14 newNode.next = expectedTopNode; 15 } while (!CAS(&top, expectedTopNode, newNode)); 16 } a. כן b. לא, כי newNode.next זה משתנה שנמצא בערימה ולכן ערכו עלול להשתנות c. לא, כי צריך memory fence לפחות במקום אחד d. לא, כי יכולה להיות החלפת הקשר בזמן ביצוע פקודת CAS e. לא, כי יכולה להיות החלפת הקשר בין השורות 13 ו-14 f. אף תשובה לא נכונה נימוק:

4. (5 נק) סטודנט אחד טוען שאפשר לא להשתמש במשתנה expectedTopNode וכך לחסוך בזיכרון. האם הקוד הבא ממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = null; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 do { 12 newNode.next = top; 13 } while (!CAS(&top, top, newNode)); 14 } a. כן, בכל מקרה הערך של expectedTopNode נלקח מ-top b. לא, כי newNode.next זה משתנה שנמצא בערימה ולכן ערכו עלול להשתנות c. לא, כי צריך memory fence לפחות במקום אחד d. לא, כי יכולה להיות החלפת הקשר בזמן ביצוע פקודת CAS e. לא, כי יכולה להיות החלפת הקשר בין השורות 12 ו-13 f. אף תשובה לא נכונה נימוק:

5. (5 נק) סטודנטית אחת טוענת שאפשר לא להשתמש במשתנה expectedTopNode וכך לחסוך בזיכרון, אבל עושה את זה באופן אחר. האם הקוד הבא ממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = null; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 do { 12 newNode.next = top; 13 } while (!CAS(&top, newNode.next, newNode)); 14 } a. כן b. לא, כי newNode.next זה משתנה שנמצא בערימה ולכן ערכו עלול להשתנות c. לא, כי צריך memory fence לפחות במקום אחד d. לא, כי יכולה להיות החלפת הקשר בזמן ביצוע פקודת CAS e. לא, כי יכולה להיות החלפת הקשר בין השורות 12 ו-13 f. אף תשובה לא נכונה נימוק:

האם החלפה בין השורות 3 ל- 4 בקוד של ה- barber פוגעת בנכונות האלגוריתם? תשובה: (כן / לא) נימוק:

האם החלפה בין השורות 2 ל-3 בקוד של ה- customer פוגעת בנכונות האלגוריתם? תשובה: (כן / לא) נימוק:

תחת איזה הנחה כדאי להחליף את ה mutex ב- spinlock בקוד הנ"ל? (נמק בפחות מעשרים מילים)

תציינו בעיית נכונות בקוד הנ"ל (על ידי תיאור תרחיש עם מספר שורות הקוד)

השלימו בעזרת משתנה תנאי ומנעול את המימוש הבא של מחסנית מקבילית: [Incomplete code for class stack with push and pop methods]

(6 נק') איזה תכונות מתקיימות עבור spinlock כפי שנלמד בהרצאה? a. A בלבד b. B בלבד c. C בלבד d. A,B בלבד e. A,C בלבד f. B,C בלבד

(6 נק') איזה תכונות מתקיימות עבור semaphore כפי שנלמד בהרצאה? a. A בלבד b. B בלבד c. C בלבד d. A,B בלבד e. A,C בלבד f. B,C בלבד

(6 נק') האם הטענה של ליאוניד נכונה? a. הטענה נכונה. שורה זו הכרחית רק במערכת מרובת ליבות כדי למנוע deadlock. b. הטענה נכונה. שורה זו הכרחית רק במערכת מרובת ליבות כדי להבטיח מניעה הדדית. c. הטענה נכונה. שורה זו הכרחית רק במערכת מרובת ליבות כדי להבטיח סדר ביצוע נכון. d. הטענה שגויה. ללא שורה זו שימוש במנעול עלול לגרום ל-deadlock. e. הטענה שגויה. ללא שורה זו המנעול לא מבטיח מניעה הדדית. f. הטענה שגויה. ללא שורה זו המעבד עלול לבצע את הפקודות בסדר לא נכון.

(6 נק') האם שורה 2 צריכה לבטל את הפסיקות מקומית (רק בליבת המעבד הנוכחית) או גלובאלית (בכל הליבות במערכת)? a. מקומית, כי אחרת יהיה deadlock. b. מקומית, כדי לשפר את הביצועים. c. מקומית, אחרת המנעול לא יבטיח מניעה הדדית. d. גלובאלית, כי אחרת יהיה deadlock. e. גלובאלית, כדי לשפר את הביצועים. f. גלובאלית, אחרת המימוש לא מבטיח שהמעבד יבצע את הפקודות בסדר הנכון.

(5 נק') האם המימוש הנ"ל נכון? (כלומר אכן תומך בהפרדה הדדית עבור המשתנה המשותף X?) נמקו.

(5 נק') לדעת דני, הקוד נכון במערכת שהינה בעלת ליבת מעבד יחידה. האם הוא צודק? נמקו.

(5 נק') האם המחשב של דני היה נתקע אילו היינו משתמשים בסמפור במקום ב-spinlock? (כלומר, חישבו על aux_lock-כסמפור והחליפו את הקריאות ל-spin_lock/spin_unlock ב-sem_down/sem_up?)

כעת נדון בקוד שונה במעט אשר משתמש בשני המאקרו-ים הבאים: • cond_wait - מקבל שלושה פרמטרים: (i) תור המתנה, (ii) משתנה mutex המספק מניעה הדדית, ו- (iii) תנאי בולאני. פעולתו של cond_wait היא אטומית: הוא בודק את התנאי הבוליאני ואם התנאי מתקיים משחררים את ה- mutex ונכנסים להמתנה (בשינה) על התור. כאשר cond_wait חוזרת, מתבצעת נעילה mutex-חוזרת של ה • cond_signal - מקבל תור המתנה ומעיר תהליך יחיד מתור זה. המימוש הבא יוצר מנעול תקין: Mutex m; int sys_global_lock() { lock(m); while (global_lock != 0) { cond_wait(global_queue, m, (global_lock!=0)); } unlock(m); } int sys_global_unlock() { lock(m); global_lock=0; //Free lock cond_signal(global_queue); //Wakes a single process waiting in uni_queue unlock(m); } דנה שמה לב שעל אף שהמימוש תקין, לעתים הוא עלול לגורם למצבי קיפאון בעקבות נעילה כפולה מאותו החוט (קריאה של מספר פעמים ברצף לפונקציה uni_lock) או בעקבות שחרור המנעול ע"י חוט שלא נעל אותו. (5 נק') הציעו שיפור למנעול כפי שהוא כתוב לעיל, המאפשר לאותו החוט לקרוא לפונקציית הנעילה כמה פעמים ברצף מבלי להיתקע (בכל נעילה נוספת לאחר הראשונה יוחזר הערך EPERM), ושעבור חוט שמנסה לשחרר מנעול שלא נעל בעצמו יוחזר ערך השגיאה EPERM. על הקוד שלכם להיות כתוב בשפת C (אך לא יורדו נקודות על שגיאות תחביר קטנות). הקפידו על תיעוד שמנמק את הנכונות של הקוד שלכם.

הציעו תיקון בקוד C לשתי בעיות הסנכרון בעזרת amfifo בלבד. ספקו שורת קוד יחידה המתקנת את בעיות הסנכרון וספקו את מספר השורה שלאחריה היא תופיע. הסבירו בקצרה

הסבירו למה פתרונכם בסעיף 13 בזבזני מבחינת משאבי מעבד.

המימוש המוצע מקולקל (בעיית נבונות – correctness). הסבירו בקצרה מדוע.

המימוש המוצע מקולקל ( בעיית נבונות – correctness). הסבירו בקצרה מדוע.

(2 נק') בקוד של אברהם יש בעיה: במקרים מסוימים התוכנית very_special רצה בתור תהליך רגיל למשך פרק זמן כלשהו. הסבירו באילו מקרים הבעיה מתרחשת ומדוע היא אינה בהכרח מתרחשת תמיד. נימוק:

אברהם ניסה לתקן את הבעיה וכתב תוכנית חדשה: prog2.c ```c 1. #include <sys/types.h> 2. #include <unistd.h> 3. 4. int main() { 5. pid_t p1 = fork(); 6. if (p1 > 0) { // parent 7. set_special(p1); 8. } else if (p1 == 0) { // child 9. pid_t p2 = fork(); 10. if (p2 == 0) { // grand-child 11. execv("/usr/bin/very_special", ...); 12. } 13. } 14. return 0; 15. } ``` (3 נק') למרבה הצער, הבעיה רק החריפה: במקרים מסוימים התוכנית very_special רצה בתור תהליך רגיל *לנצח* (ולא רק למשך פרק זמן כלשהו). הסבירו באילו מקרים הבעיה מתרחשת ומדוע היא גורמת לתוכנית very_special להיתקע לנצח בתור תהליך רגיל. נימוק:

אברהם ביקש מחבריו לקורס "מערכות הפעלה" לעזור לו לפתור את הבעיות שתוארו לעיל. לשמחתו הוא קיבל ארבע הצעות לתיקון. בכל אחד מהסעיפים הבאים מציגים הצעה לפתרון הבעיה על ידי הוספת שורות קוד לתוכנית המקורית prog1 (לנוחותכם, השורות שהתווספו מודגשות). הצעה ראשונה לתיקון הבעיה: prog3.c ```c 1. #include <sys/types.h> 2. #include <unistd.h> 3. 4. int main() { 5. pid_t p = fork(); 6. if (p > 0) { // parent 7. set_special(p); 8. } else if (p == 0) { // child 9. If (is_special()) 10. execv("/usr/bin/very_special", ...); 11. } 12. return 0; 13. } ``` (5 נק') האם שינוי זה פותר את הבעיה? כן / לא נימוק: אם לא, האם אתם יכולים להציע שינוי בשורת קוד אחת ויחידה שהתווספה כדי לתקן את הבעיה? כן / לא אם כן, נא לציין איזה שורה ואיך לתקן אותה: מספר שורה התיקון (שורת קוד החדשה במקום השורה הקיימת)

הצעה שניה לתיקון הבעיה: prog4 ```c 1. // includes all necessary headers... 2. int main() { 3. // declare and initialize semaphore with initial value=0 4. pid_t p = fork(); 5. if (p > 0) { // parent 6. set_special(p); 7. sem_post(&sem); 8. } else if (p == 0) { // child 9. sem_wait(&sem); 10. execv("/usr/bin/very_special", ...); 11. } 12. // destroy the semaphore 13. return 0; 14. } ``` (5 נק') האם שינוי זה פותר את הבעיה? כן / לא נימוק: אם לא, האם אתם יכולים להציע שינוי בשורת קוד אחת ויחידה שהתווספה כדי לתקן את הבעיה? כן / לא אם כן, נא לציין איזה שורה ואיך לתקן אותה: מספר שורה התיקון (שורת קוד החדשה במקום השורה הקיימת)

נתון סמפור sem שמאותחל ל- 0 אשר נגיש מ Thread A וגם מ Thread B .השלימו את הקוד החסר כך שביצוע statement a1 יסתיים לפני תחילת ביצוע statement b1.

נרצה להכליל את הרעיון של הסעיף הקודם ולהפוך אותו לסימטרי. ביכולתכם להגדיר כמה סמפורים כרצונכם. השלם את הקוד הבא כך שמתקיים: statement a2 מסתיים לפני תחילתו של statement b1. statement b2 מסתיים לפני תחילתו של statement a1.

דני הציע את המימוש הבא לפונקצית barrier: void barrier(){ sem1.wait(); counter+=1; sem1.post(); while(counter <= n); } תארו את הבעייה בקוד הנתון

הציעו תיקון על ידי הוספת שורת קוד אחת כך שהקוד הנ"ל יהיה נכון: נרצה להוסיף (כתבו שורת הקוד): אחרי השורה

(6 נק') בפתרון הבעיה (שמוצג בסעיפים הבאים) יש שימוש במספר סמפורים, כתבו איזה סמפור: 1. מאפשר הגעה אטומית של נוסעים או של האוטובוס לתחנה: 2. נועד להעלות נוסע בצורה אטומית לאוטובוס באמצעות הפונקציה boardBus: 3. נועד להודיע לאוטובוס שעלה נוסע לאוטובוס:

(6 נק') לצורך מימוש בעיית הסנכרון הזאת, יש צורך בקוד עבור האוטובוס. השלימו את המימוש: 1 void depart(); 2 void boardBus(); 3 4 sem_t mutex, bus, boarded; 5 sem_init(&mutex, 0, 1); //Notice. 6 sem_init(&bus, 0, 0); 7 sem_init(&boarded, 0, 0); 8 int waiting = 0; 9 10 // bus code 11 sem_wait(mutex); 12 int n = waiting < 50 ? waiting : 50; 13 for(int i = 0; i < n; i++){ 14 sem_post(bus); 15 // add your code here 16 } 17 waiting = waiting-50 > 0 ? waiting-50: 0; 18 // add your code here 19 depart();

(6 נק') כמו כן, יש צורך בקוד עבור סטודנט שבא לתחנה. השלימו את המימוש: 20 // rider code 21 sem_wait(mutex); 22 // add your code here 23 sem_post(mutex); 24 // add your code here 25 board(); 26 sem_post(boarded);

(7 נק') יכול להיות מתסכל עבור הנוסעים שמגיעים בזמן שהאוטובוס בתחנה להמתין לאוטובוס הבא. איזה שינוי בשורה אחת יש לבצע בקוד כדי לאפשר גם להם אפשרות לעלות לאוטובוס? עליכם להוסיף שורה (או יותר) בקוד משני סעיפים קודמים שלא ציינו בנוסף לשורות שלכם. (רמז: בקוד של האוטובוס). שורת קוד להוספה: מיקום (לאן להוסיף): הסבר:

(2 נק') האם הקוד הנ"ל תקין ונכון (מקיים את התנאים של המסעדה) עבור מושב יחיד (כלומר, NUM_SEATS=1)? (כן / לא)

(2 נק') האם הקוד הנ"ל תקין ונכון (מקיים את התנאים של המסעדה) עבור יותר ממושב יחיד (למשל, NUM_SEATS=5)? (כן / לא)

(9 נק') בהתייחס לקוד הנ"ל, סמנו עבור כל אחת מהבעיות בטבלה אם היא מתקיימת (ואז תנו דוגמא), או שלא מתקיימת (ואז הסבירו בקצרה) שאלה תשובה (כן / לא) הסבר קיימת בעיית הוגנות? קיימת בעיית נכונות? קיימת בעיית ? DeadLock / Livelock

(12 נק') אחרי ש- USHI התחיל ללמוד לבחינה במערכות הפעלה, סוף סוף הוא התחיל להרגיש שהוא שולט יותר טוב בחומר שלמד בקורס ואז נזכר שהוא צריך לשפר ולשכתב את התוכנית הנ"ל בצורה יותר טובה. USHI התייעץ עם השותף שלו בקורס SHUSHI איך לשכתב את הקוד, ואכן הם הצליחו לשכתב את רוב הקוד חוץ מכמה שורות ריקות שעדיין מתלבטים לגביהן. אתם יכולים לעזור ל- USHI ו- SHUSHI לכתוב את הקוד החסר כך שהתוכנית הזו תעבוד בצורה תקינה (כך שהקוד יהיה נקי מהבעיה/ות שגיליתם בסעיף הקודם)? והסבירו בקצרה איך הקוד החדש מתקן את הבעיה/ות מסעיף קודם. 1 #define NUM_SEATS (5) 2 int eating = waiting = 0; // hint: where should be updated? 3 bool must_wait = false; // hint: where should be updated? 4 sem_t mutex, block; 5 sem_init(&mutex, 0, 1); // value=1 6 sem_init(&block, 0, 0); // value=0 7 8 enter_OSUSHI() { 9 sem_wait(&mutex) 10 if (must_wait) { 11 waiting += 1; 12 sem_post(&mutex); 13 sem_wait(&block); 14 } 15 sem_wait(&mutex); // reacquire mutex 16 waiting -= 1; 17 } 18 eating += 1; 19 must_wait = (eating == NUM_SEATS); 20 sem_post(&mutex); 21 } 22 23 exit_OSUSHI() { 24 sem_wait(&mutex); 25 eating -= 1; 26 if (eating == 0) { 27 int n = min(NUM_SEATS, waiting ); 28 sem_post(&block, n); 29 must_wait = false; 30 } 31 sem_post(&mutex); 32 }

(1 נק') המשפט "goodbye from canceller" אף פעם לא יודפס. כן / לא (הקיפי) נימוק:

(5 נק') קיימת ריצה שבה תודפס (בין היתר) המילה "thread" למסך. כן / לא (הקיפי) נימוק:

(5 נק') קיימת ריצה שבה יודפס (בין היתר) הפלט הבא. כן / לא (הקיפי) Dan 234123 Leonid נימוק:

באיזה סוג של אמצעי סנכרון צריך להשתמש, אם רוצים להבטיח שבכל תא במערך ייכתב באופן תקני מספר מזהה של החוט מחובר עם מונה רץ? איך זה ישפיע על הביצועים? א. לא צריך אמצעי סנכרון ב. מספיק מנעול אחד ג. צריך מספר מנעולים ד. צריך אמצעי סנכרון אחר ממנעול (הסבר מטה) ה. אף תשובה לא נכונה

באיזה סוג של אמצעי סנכרון צריך להשתמש, אם רוצים להבטיח שבכל תא במערך יכתב באופן תקני מספר מזהה של החוט מחובר עם מונה רץ? איך זה ישפיע על ביצועים? א. לא צריך אמצעי סנכרון ב. מספיק מנעול אחד ג. צריך מספר מנעולים ד. צריך אמצעי סנכרון אחר ממנעול (הסבר מטה) ה. אף תשובה לא נכונה

(5 נק') שלומית הציעה בהתחלה את האלגוריתם הבא: 1. if no milk: 2. if (Yehuda): 3. wait until there is milk 4. if (Shlomit): 5. get the car keys 6. get the wallet 7. buy milk יהודה טוען שהאלגוריתם עשוי לא להסתיים, האם יהודה צודק? נמקו

(4 נק') נתון קטעי קוד לשני חוטים שנכתב על ידי גדליה ואבינועם. הקוד מיועד לריצה מקבילית על מספר חוטים עם מערכת מרובת ליבות, נכונות האלגוריתם דורשת ש do_work יתבצע פעם אחת בלבד. // flag_a,flag_b are global variables initialized to zero 1: flag_b = 1; 2: while (flag_a) {}; 3: do_work(); //no synchronization inside do_work() // flag_a, flag_b are global variables initialized to zero 1: flag_a = 1; 2: while (flag_b == 0) { 3: do_work(); //no synchronization inside do_work() 4: return; 5: } הקוד רץ על שני מעבדים במקביל בשני חוטים. גדליה טוען שייתכן do_work יתבצע יותר מפעם אחת ולכן התוכנית אינה נכונה. אבינועם טוען, שמצב זה לא ייתכן ואם אחד החוטים ביצע 1=flag_a או 1=flag_b אז כל החוטים יראו מיד את השינוי. הכריעו מי צודק, בפרט, אם גדליה צודק, האם קיים פתרון לבעיה? נמקו.

(4 נק') בהנחה שהמעבד מרובה ליבות, אם נוסיף לתוכנית המקורית את הטקסט הבא: g_alarm = 2; בשורה 13, אז יתכן race condition בהתייחס למשתנה g_alarm נכון / לא נכון. נימוק: