המצאת המושג "פקולטה נחשבת" החמירה את הסכסוך בין הסטודנטים במדמ"ח ובהנדסת חשמל, ולכן הוגדר כי כאשר סטודנט מאחת הפקולטות רוצה להיכנס לחדר מסויים עליו לציית לכלל הבא: אם יש סטודנטים מפקולטה אחרת בחדר אזי אסור לסטודנט להיכנס ועליו להמתין עד שיעזבו (לעומת זאת, מספר סטודנטים מאותה פקולטה יכולים לשהות בחדר באותו הזמן). סמני נכון / לא נכון (אין צורך להסביר): בסעיפים הבאים מוצג קוד למימוש כניסה ויציאה של סטודנטים אל ומחדר מסוים, כאשר נתון כי: * כל חוט מייצג סטודנט. * בכניסה לחדר הסטודנט קורא ל (faculty int(onArrival, שמקבלת את פקולטת הסטודנט. * ביציאה מהחדר הסטודנט קורא ל (faculty int(onLeave שמקבלת את פקולטת הסטודנט. * הערכים 0 ו1- של faculty מייצגים את הפקולטה להנדסת חשמל ומדמ״ח, בהתאמה. * (הניחו שאמצעי הסנכרון עברו אתחול תקין והתעלמו מבעיות קומפילציה אם ישנן, שכן מטרת השאלה אינה לבדוק שגיאות אתחול/תחביר). 1. #include <pthread.h> 2. int students = 0; 3. mutex_t global; 4. void onLeave(int faculty) { 5. mutex_lock(&global); 6. students--; 7. mutex_unlock(&global); 8. } 9. void onArrival(int faculty) { 10. mutex_lock(&global); 11. while (students > 0) { 12. mutex_unlock(&global); 13. sleep(10); 14. mutex_lock(&global); 15. } 16. students++; 17. mutex_unlock(&global); 18. } המימוש של כניסה ויציאה שונה כך שישתמש במשתני תנאי: 1. int students[2] = {0}; // 2 counters 2. cond_t conds[2]; // 2 condition variables 3. mutex_t global; 4. void onArrival(int faculty) { 5. mutex_lock(&global); 6. int other = faculty ? 0 : 1; 7. while(students[other] > 0) 8. cond_wait(&conds[faculty], &global); 9. students[faculty]++; 10. mutex_unlock(&global); 11. } 12. void onLeave(int faculty) { 13. mutex_lock(&global); 14. students[faculty]--; 15. int other = faculty ? 0 : 1; 16. cond_broadcast(&conds[other]); 17. mutex_unlock(&global); 18. } דני ניסה לשפר עוד את יעילות הקוד והחליט להשתמש בשני מנעולים: מנעול ראשון בעבור סטודנטים הנכנסים לחדר, ומנעול שני בעבור סטודנטים היוצאים מהחדר. להלן המימוש החדש (השינויים בקוד מודגשים): 1. int students[2] = {0}; // 2 counters 2. cond_t conds[2]; // 2 condition variables 3. mutex_t m_arrival, m_leave; // there are *2* locks now 4. void onArrival(int faculty){ 5. mutex_lock(&m_arrival); 6. int other = faculty ? 0 : 1; 7. while(students[other] > 0) 8. cond_wait(&conds[faculty], &m_arrival); 9. int tmp = students[faculty]; 10. students[faculty] = tmp + 1; 11. mutex_unlock(&m_arrival); 12. } 13. void onLeave(int faculty){ 14. mutex_lock(&m_leave); 15. int tmp = students[faculty]; 16. students[faculty] = tmp – 1; 17. int other = faculty ? 0 : 1; 18. cond_broadcast(&conds[other]); 19. mutex_unlock(&m_leave); 20. }
Full original question text (raw OCR)
שאלה 2 - סינכרון (28 נק') המצאת המושג "פקולטה נחשבת" החמירה את הסכסוך בין הסטודנטים במדמ"ח ובהנדסת חשמל, ולכן הוגדר כי כאשר סטודנט מאחת הפקולטות רוצה להיכנס לחדר מסויים עליו לציית לכלל הבא: אם יש סטודנטים מפקולטה אחרת בחדר אזי אסור לסטודנט להיכנס ועליו להמתין עד שיעזבו (לעומת זאת, מספר סטודנטים מאותה פקולטה יכולים לשהות בחדר באותו הזמן). סמני נכון / לא נכון (אין צורך להסביר): 1. (1 נק') יכולים להיות שני סטודנטים מפקולטות שונות באותו חדר במקביל: נכון / לא נכון 2. (1 נק') יכולים להיות שני סטודנטים מפקולטות זהות בחדר במקביל: נכון / לא נכון 3. (1 נק') סטודנטי פקולטה אחת עלולים להרעיב (כניסת) סטודנטי פקולטה אחרת: נכון / לא נכון בסעיפים הבאים מוצג קוד למימוש כניסה ויציאה של סטודנטים אל ומחדר מסוים, כאשר נתון כי: * כל חוט מייצג סטודנט. * בכניסה לחדר הסטודנט קורא ל (faculty int(onArrival, שמקבלת את פקולטת הסטודנט. * ביציאה מהחדר הסטודנט קורא ל (faculty int(onLeave שמקבלת את פקולטת הסטודנט. * הערכים 0 ו1- של faculty מייצגים את הפקולטה להנדסת חשמל ומדמ״ח, בהתאמה. * (הניחו שאמצעי הסנכרון עברו אתחול תקין והתעלמו מבעיות קומפילציה אם ישנן, שכן מטרת השאלה אינה לבדוק שגיאות אתחול/תחביר). 1. #include <pthread.h> 2. int students = 0; 3. mutex_t global; 4. void onLeave(int faculty) { 5. mutex_lock(&global); 6. students--; 7. mutex_unlock(&global); 8. } 9. void onArrival(int faculty) { 10. mutex_lock(&global); 11. while (students > 0) { 12. mutex_unlock(&global); 13. sleep(10); 14. mutex_lock(&global); 15. } 16. students++; 17. mutex_unlock(&global); 18. } 4. (8 נק') בהתייחס לקוד הנ״ל, הקיפי את כל התשובות הנכונות (עשויה להיות יותר מאחת). עבור כל תשובה שהקפת, תארי דוגמת הרצה המובילה לתשובה זו. a. קיימת בעיית נכונות עקב condition race למשאבים משותפים. b. קיימת בעיית Livelock / DeadLock בקוד. c. הקוד משתמש ב-Wait Busy שפוגע בנצילות המעבד. d. הקוד מפר את כלל הכניסה לחדר (שהוגדר בתחילת השאלה). נימוק: המימוש של כניסה ויציאה שונה כך שישתמש במשתני תנאי: 1 int students[2] = {0}; // 2 counters 2 cond_t conds[2]; // 2 condition variables 3 mutex_t global; 4 void onArrival(int faculty) { 5 mutex_lock(&global); 6 int other = faculty ? 0 : 1; 7 while(students[other] > 0) 8 cond_wait(&conds[faculty], &global); 9 students[faculty]++; 10 mutex_unlock(&global); 11 } 12 void onLeave(int faculty) { 13 mutex_lock(&global); 14 students[faculty]--; 15 int other = faculty ? 0 : 1; 16 cond_broadcast(&conds[other]); 17 mutex_unlock(&global); 18 } אך דני (עתודאי במדמ"ח) טען שקוד זה גורם לחוטים להתעורר שלא לצורך ומיד לחזור למצב המתנה. 5. (4 נק') הסבירי את טענתו של דני באמצעות דוגמת ריצה קונקרטית. נימוק: 6. (5 נק') כיצד ניתן לתקן את הבעיה שהציג דני בסעיף הקודם? נימוק: דני ניסה לשפר עוד את יעילות הקוד והחליט להשתמש בשני מנעולים: מנעול ראשון בעבור סטודנטים הנכנסים לחדר, ומנעול שני בעבור סטודנטים היוצאים מהחדר. להלן המימוש החדש (השינויים בקוד מודגשים): 1 int students[2] = {0}; 2 cond_t conds[2]; 3 mutex_t m_arrival, m_leave; 4 void onArrival(int faculty){ 5 6 7 8 9 10 11 12} // 2 counters // 2 condition variables // there are *2* locks now mutex_lock(&m_arrival); int other = faculty ? 0 : 1; while(students[other] > 0) cond_wait(&conds [faculty], &m_arrival); int tmp = students[faculty]; students [faculty] = tmp + 1; mutex_unlock(&m_arrival); 13 void onLeave(int faculty){ 14 15 16 17 18 19 20} mutex_lock(&m_leave); int tmp = students[faculty]; students[faculty] = tmp – 1; int other = faculty ? 0 : 1; cond_broadcast(&conds[other]); mutex_unlock(&m_leave); 7. (8 נק') בהתייחס לקוד הנ״ל, הקיפי את כל התשובות הנכונות (עשויה להיות יותר מאחת). עבור כל תשובה שהקפת, תארי דוגמת הרצה המובילה לתשובה זו. a. יתכנו 2 סטודנטים מפקולטות שונות בתוך החדר ביחד, עקב race condition למשאב משותף. b. יתכן סטודנט שלא נכנס לחדר למרות כלל הכניסה שמתיר זאת, עקב race condition למשאב משותף. c. קיימת בעיית DeadLock / Livelock בקוד. d. סיגנלים עלולים ללכת לאיבוד. נימוק:
(1 נק') יכולים להיות שני סטודנטים מפקולטות שונות באותו חדר במקביל: נכון / לא נכון
Signal delivery and handler timingMutex correctness and deadlock avoidanceSRT / preemptive Gantt construction(1 נק') יכולים להיות שני סטודנטים מפקולטות זהות בחדר במקביל: נכון / לא נכון
Signal delivery and handler timingMutex correctness and deadlock avoidanceSRT / preemptive Gantt construction(1 נק') סטודנטי פקולטה אחת עלולים להרעיב (כניסת) סטודנטי פקולטה אחרת: נכון / לא נכון
Signal delivery and handler timingMutex correctness and deadlock avoidanceSRT / preemptive Gantt construction(8 נק') בהתייחס לקוד הנ״ל, הקיפי את כל התשובות הנכונות (עשויה להיות יותר מאחת). עבור כל תשובה שהקפת, תארי דוגמת הרצה המובילה לתשובה זו. a. קיימת בעיית נכונות עקב condition race למשאבים משותפים. b. קיימת בעיית Livelock / DeadLock בקוד. c. הקוד משתמש ב-Wait Busy שפוגע בנצילות המעבד. d. הקוד מפר את כלל הכניסה לחדר (שהוגדר בתחילת השאלה). נימוק:
Mutex correctness and deadlock avoidanceBanker's algorithm safety checkאך דני (עתודאי במדמ"ח) טען שקוד זה גורם לחוטים להתעורר שלא לצורך ומיד לחזור למצב המתנה. (4 נק') הסבירי את טענתו של דני באמצעות דוגמת ריצה קונקרטית.
Pipe IPC semantics(5 נק') כיצד ניתן לתקן את הבעיה שהציג דני בסעיף הקודם? נימוק:
Signal delivery and handler timingMutex correctness and deadlock avoidanceSRT / preemptive Gantt construction(8 נק') בהתייחס לקוד הנ״ל, הקיפי את כל התשובות הנכונות (עשויה להיות יותר מאחת). עבור כל תשובה שהקפת, תארי דוגמת הרצה המובילה לתשובה זו. a. יתכנו 2 סטודנטים מפקולטות שונות בתוך החדר ביחד, עקב race condition למשאב משותף. b. יתכן סטודנט שלא נכנס לחדר למרות כלל הכניסה שמתיר זאת, עקב race condition למשאב משותף. c. קיימת בעיית DeadLock / Livelock בקוד. d. סיגנלים עלולים ללכת לאיבוד. נימוק:
Signal delivery and handler timingMutex correctness and deadlock avoidanceBanker's algorithm safety check
The exam question — original PDF
Exactly 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.
קריאת המערכת kill#include <sys/types.h>#include <signal.h>int kill(pid_t pid, int sig);פעולה: שולחת את הסיגנל שמספרו sig לתהליך המזוהה ע"י pid.אם הערך של sigהוא 0, אז הפעולה רק בודקת שהתהליך pid קיים, מבלי לשלוח signal (שימושי לבדיקת תקפות pid).ערך מוחזר:0 בהצלחה-1 בכישלון (למשל, אם אין תהליך בעל מזהה pid)מערכות הפעלה - תרגול 38
העברת סיגנלים בשני שלביםרישום – מערכת ההפעלה רושמת ב-PCB של תהליך היעד שיש לו סיגנל ממתין (pending signal).הרישום מתבצע במערך בינארי בין 31 ביטים, ולכן לכל תהליך יכול להיות לכל היותר סיגנל ממתין אחד מכל מספר.טיפול – בכל פעם שהתהליך חוזר ממצב גרעין למצב משתמש, מערכת ההפעלה בודקת אם יש סיגנלים ממתינים ומטפלת בהם.בסיום הטיפול בסיגנל, מערכת ההפעלה תאפס את הביט המתאים במערך. במידה ויש מספר סיגנלים ממתינים, סדר הטיפול מתחילת המערך לסופו.מערכות הפעלה - תרגול 39
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
יצירת חוט חדשפרמטרים:thread – מצביע למקום בו יאוחסן מזהה החוט החדש במקרה של סיום הפונקציה בהצלחה.attr – מאפיינים המתארים את תכונות החוט החדש, כגון האם החוט הוא חוט גרעין או חוט משתמש, האם ניתן לבצע לו join, כלומר להמתין לסיומו, וכו'. בד"כ נספק ערך NULL המציין חוט ברירת המחדל של המערכת, שניתן להמתין לסיומו.void* (*start_routine)(void*) מצביע לפונקציה שתהווה את קוד החוט. הערך המוחזר מפונקציה זו במקרה של סיומה הטבעי הינו ערך הסיום של החוט.arg – פרמטר שיסופק לפונקציה עם הפעלתה.מערכות הפעלה - תרגול 714
מנעולים עם/בלי המתנהspinlockכאשר חוט מנסה לתפוס מנעול נעול, הוא בודק את ערך המנעול שוב ושוב מבלי לצאת מתור הריצה.טכניקה כזו נקראת גם: polling, busy waiting, busy looping.יתרון: התהליך יכול להמשיך לרוץ עוד בקוונטום הנוכחי, וכך לחסוך את התקורה על החלפת הקשר.עדיף כאשר זמן ההמתנה המשוער נמוך יותר מהמחיר של החלפת הקשר (כלומר, כאשר הקטע הקריטי קצר, כפי שקורה לרוב בקוד גרעין).mutexכאשר חוט מנסה לתפוס מנעול נעול, מערכת ההפעלה תעביר אותו לתור המתנה ותבצע החלפת הקשר.כאשר המנעול ישוחרר, מערכת ההפעלה תעיר את אחד החוטים המחכים למנעול.יתרון: תהליך חדש יכול לרוץ מיד, וכך לא מתבזבז זמן מעבד יקר.עדיף כאשר זמן ההמתנה המשוער גבוה יחסית (כלומר, כאשר הקטע הקריטי ארוך, כפי שקורה לרוב בקוד משתמש).מערכות הפעלה - תרגול 745
TL;DRבתרגול הקודם למדנו לכתוב קוד מקבילי באמצעות חוטים.ראינו שבכל בעיה לא טריוויאלית יש צורך בסנכרון בין החוטים.היום נלמד על מנגנוני סנכרון נוספים של ממשק pthreads :לבסוף, נלמד דוגמה נוספת של קוד מקבילי חשוב: גרעין לינוקס.קוד הגרעין לא משתמש בחוטים, אבל ניגש לזיכרון משותף מתוך מספר מסלולי בקרה שרצים במקביל, ולכן העקרונות שלמדנו תקפים גם עבורו.2מערכות הפעלה - תרגול 8להבטחת סדרלהבטחת אטומיותמשתני תנאי(condition variables)מנעולים(mutexes)סמפורים (semaphores)
משתנה תנאי (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
שחרור חוטים ממתיניםint pthread_cond_signal(pthread_cond_t *cond); משחררת את אחד החוטים הממתינים (הגינות לא מובטחת).int pthread_cond_broadcast(pthread_cond_t *cond);משחררת את כל החוטים הממתינים.כל החוטים מפסיקים להמתין על משתנה התנאי ועוברים להמתין על המנעול. החוטים יחזרו לפעילות בזה אחר זה (בסדר כלשהו, לאו דווקא הוגן) לאחר שינעלו מחדש את ה-mutex.שימו לב: אם אין אף חוט שממתין באותו רגע על משתנה התנאי cond, הפעולות חסרות השפעה (הסיגנל הולך לאיבוד ואינו נזכר הלאה).ערך מוחזר: הפונקציות תמיד מצליחות ומחזירות 0.מערכות הפעלה - תרגול 812
מועד א', אביב 2008, שאלה 1sem_t sem; // Global semaphore, with initial value 1 int writer_lock() { sem_wait(sem);} int writer_unlock() { sem_post(sem);} int reader_lock() { while(sem_getvalue(sem) <= 0) sleep(1); sem_wait(sem);} int reader_unlock() { sem_post(sem);}סעיף ב: להלן הצעה לפתרון בעיית קוראים/כותבים עם עדיפות לכותבים, המשתמשת בסמפורים.תארו 3 בעיות שונות של נכונות ו/או יעילות שיש בפתרון הנ"ל. הניחו כי הסמפור הינו הוגן.מערכות הפעלה - תרגול 838
מועד א', אביב 2008, שאלה 1sem_t sem; // Global semaphore, with initial value 1 int writer_lock() { sem_wait(sem);} int writer_unlock() { sem_post(sem);} int reader_lock() { while(sem_getvalue(sem) <= 0) sleep(1); sem_wait(sem);} int reader_unlock() { sem_post(sem);}בעיית נכונות: הפתרון לא מאפשר ליותר מקורא אחד להיכנס לקטע קריטי.בעיית נכונות: אם יש גם קוראים וגם כותבים, הכותבים לא בהכרח יקבלו עדיפות ועלולים להיות מורעבים בניגוד לדרישה.בעיית יעילות: קוראים מבצעים busy wait.מערכות הפעלה - תרגול 839
פסיקות חומרה במערכת מרובת ליבותבמערכת מרובת ליבות, מעבדים שונים יכולים לגשת בו-זמנית למבני נתונים משותפים יש להוסיף נעילה מעבר לחסימת הפסיקות המקומית.שגרות טיפול בפסיקות חומרה עושות שימוש במנעולי spinlock (מנעולים הממומשים כ-busy wait).שאלה: מדוע מעדיפים מנעולי spinlock על-פני מנעולי סמפור?busy wait הוא המתנה יעילה יותר כאשר מדובר בנעילות קצרות מאוד כפי שקורה בגרעין, מפני שכך נחסכת התקורה של כניסה ויציאה מהמתנה.בעיית הוגנות, למשל בתרחיש הבא:תהליך רץ, ובאותו הזמן מתקבלת פסיקת חומרה (למשל מהמקלדת).הטיפול בפסיקה מנסה לתפוס את המנעול, אבל המנעול כבר תפוס.התהליך עובר לתור המתנה מסיבה שאינה תלויה בו.מערכות הפעלה - תרגול 856
The exam text, the skills it tests, and the exact slides are already in context.