OSUSHI הינה מסעדת סושי מפורסמת שיש בה N מושבים, כך שהקיבולת של המסעדה עד N סועדים. אם סועד מגיע למסעדה כשיש מקום פנוי, אז הוא יכול להתיישב מיד. אבל אם הסועד מגיע כשכל ה- N מושבים תפוסים, זאת אומרת שיש כרגע N סועדים שמנסים ליהנות מהסושי, אז תצטרך לחכות עד שכולם יעזבו לפני שאתה מתיישב. בעל המסעדה שקוראים לו USHI הינו במקרה גם סטודנט בקורס OS (מכאן אתם יכולים להסיק את המקור של השם של המסעדה). אחרי ש USHI למד בקורס מערכות הפעלה על סנכרון, אז הוא רצה לבחון את היכולות שלו בתכנות מקבילי ולכתוב תוכנית שתעזור לסועדים להתיישב בלי לריב. בתכנית של USHI כל סועד הינו חוט בתכנית אשר מריץ את הקוד הבא: enter_OSUSHI(); eat_sushi(); exit_OSUSHI(); הסטודנט החרוץ USHI למד על בשרו כשפתר תרגיל בית 3 בהפעלה שכדאי להתחיל לכתוב תכנית מקבילית צעד אחרי צעד ולהתחיל מהמקרה הפשוט. לכן, הוא החליט שיכתוב את התכנית ההתחלתית שלו עבור 1=N, כלומר שיש רק מושב אחד ויחיד במסעדה. מספר זה מיוצג בתכנית של USHI על ידי NUM_SEATS #define NUM_SEATS (1) sem_t block; sem_init(&block, 0, NUM_SEATS); // value=NUM_SEATS enter_OSUSHI() { sem_wait(&block) } exit_OSUSHI() { sem_post(&block); }
Full original question text (raw OCR)
שאלה 4 - סנכרון (25 נק')
(2 נק') האם הקוד הנ"ל תקין ונכון (מקיים את התנאים של המסעדה) עבור מושב יחיד (כלומר, NUM_SEATS=1)? (כן / לא)
Pipe IPC semantics(2 נק') האם הקוד הנ"ל תקין ונכון (מקיים את התנאים של המסעדה) עבור יותר ממושב יחיד (למשל, NUM_SEATS=5)? (כן / לא)
Pipe IPC semantics(9 נק') בהתייחס לקוד הנ"ל, סמנו עבור כל אחת מהבעיות בטבלה אם היא מתקיימת (ואז תנו דוגמא), או שלא מתקיימת (ואז הסבירו בקצרה) שאלה תשובה (כן / לא) הסבר קיימת בעיית הוגנות? קיימת בעיית נכונות? קיימת בעיית ? DeadLock / Livelock
Mutex correctness and deadlock avoidanceBanker's algorithm safety check(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 }
Mutex correctness and deadlock avoidanceSRT / preemptive Gantt construction
The exam question — original PDF
pages 13, 14, 15, 16Exactly 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
Banker’s algorithm • “Safe state” – System state whereby we’re sure that all processes can be executed, in a certain order, one after the other, such that each will obtain all the resources it needs to complete its execution – By ensuring such a sequence exists after each allocation => we avoid deadlock • Banker’s data structure – max[p] = (m_1,m_2, …, m_k) = max resource requirements for process p – cur[p] = (c_1,c_2, …, c_k) = current resource allocation for process p – R = (r_1, r_2, …, r_k) = the current resource request (for some process p) – avail = (a_1, a_2, …., a_k) = currently available (free) resources (global) • Example – max[p] = (3,0,1), cur[p] = (3,0,0) – Note that max[p] >= cur[p] always holds /* compare by coordinates */ OS (234123) - deadlocks 36
Banker’s algorithm • Tentatively assume that request R was granted to process q – cur[q] += R // vector addition – avail -= R // vector subtraction • Check if “safe state” (= can satisfy all processes in some order) – initialize P to hold all non-terminated process – while( P isn’t empty ) { found = false for each p in P { // find one p that can be satisfied if( max[p] – cur[p] <= avail ) // p’s biggest request avail += cur[p] // pretend p terminates P -= {p} found = true } if( ! found ) return FAILURE } return SUCCESS OS (234123) - deadlocks 37
Summary: ways to deal with deadlocks rpt 1. Deadlock “prevention” – Violate one of the 4 conditions necessary for deadlock – Deadlock can’t happen – E.g., by ordering resources & acquiring from smallest to biggest 2. Deadlock “avoidance” – Banker’s algorithm – Requires full knowledge about available & requested resources – System stays away from deadlocks by being careful on a per resource-allocation decision basis 3. Deadlock “detection & recovery” – Allow system to enter deadlock state, but put in place mechanisms that can detect, and then recover from this situation – Typically refer to the algorithmic resource-graph problem OS (234123) - deadlocks 41
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
דוגמת FCFSaverageResponseTime = (10 + 20 + 30) / 3 = 20כעת נסיר את הנחה 1 ("כל התהליכים רצים למשך אותו זמן"). לכל תהליך זמן ריצה משלו.תוכלו לחשוב על דוגמה שבה FCFS אינו יעיל?מערכות הפעלה - תרגול 59כל התהליכים רצים למשך אותו זמן.כל התהליכים מגיעים באותו זמן (t=0).אם תהליך התחיל לרוץ, אז הוא ירוץ עד לסיומו ללא הפסקות.התהליכים משתמשים רק במעבד ולא מבצעים I/O.זמן הריצה של כל התהליכים ידוע מראש.
אפקט השיירה (convoy effect)averageResponseTime = (100 + 110 + 120) / 3 = 110אלגוריתם FCFS עלול לסבול מ"אפקט השיירה": מצב שבו תהליך אחד ארוך מעכב הרבה תהליכים קצרים. מערכות הפעלה - תרגול 510
יצירת חוט חדשפרמטרים: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
The exam text, the skills it tests, and the exact slides are already in context.