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

קריאות המערכת getpid(), getppid()pid_t getpid();קריאת מערכת המחזירה לתהליך הקורא את ה-pid של עצמו.pid_t getppid();קריאת מערכת המחזירה את ה-PID של תהליך האב של התהליך הקורא.שאלה: מה המשמעות של getppid() == 1 עבור תהליך משתמש טיפוסי?תשובה: תהליך האב הוא init. קורה למשל אם תהליך הבן יתום.מערכות הפעלה - תרגול 222

מערכות הפעלה - תרגול 2281שאלה ממבחן

דוגמת FCFSaverageResponseTime = (10 + 20 + 30) / 3 = 20כעת נסיר את הנחה 1 ("כל התהליכים רצים למשך אותו זמן"). לכל תהליך זמן ריצה משלו.תוכלו לחשוב על דוגמה שבה FCFS אינו יעיל?מערכות הפעלה - תרגול 59כל התהליכים רצים למשך אותו זמן.כל התהליכים מגיעים באותו זמן (t=0).אם תהליך התחיל לרוץ, אז הוא ירוץ עד לסיומו ללא הפסקות.התהליכים משתמשים רק במעבד ולא מבצעים I/O.זמן הריצה של כל התהליכים ידוע מראש.

אפקט השיירה (convoy effect)averageResponseTime = (100 + 110 + 120) / 3 = 110אלגוריתם FCFS עלול לסבול מ"אפקט השיירה": מצב שבו תהליך אחד ארוך מעכב הרבה תהליכים קצרים. מערכות הפעלה - תרגול 510

קריאת המערכת clone()flags – מסכת דגלים הקובעת את צורת השיתוף בין התהליך הקורא והתהליך החדש. להלן מספר דגלים אופייניים:ניתן לשלב מספר דגלים יחד באמצעות OR לוגי ביניהם, לדוגמה:CLONE_VM | CLONE_FS .ערך מוחזר: במקרה של הצלחה מוחזר ה-PID של התהליך החדש,אחרת -1.מערכות הפעלה - תרגול 728CLONE_VMשיתוף מרחב הזיכרוןCLONE_FILESשיתוף טבלת הקבצים הפתוחיםCLONE_FSשיתוף טבלת נתוני עבודה עם קבצים, המכילה נתונים כגון ספרית העבודה הנוכחית ועודCLONE_PARENTלתהליך החדש יהיה אותו אב כמו התהליך הקורא (אחרת החדש יהיה הבן של הקורא)CLONE_THREADהתהליך החדש הוא חוט באותה קבוצת חוטים כמו התהליך הקורא (אותו tgid). גורר גם CLONE_PARENT

מנעולים עם/בלי המתנה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

מועד א', אביב 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