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

קריאת המערכת exit()שאלה: למה בכלל לקרוא ל-exit(status) , אם אפשר פשוט לרשום return status בסוף פונקציית ה-main?תשובה: main היא לא באמת הפונקציה הראשית של התכנית...main() נקראת ע"י __libc_start_main() שאוספת את ערך החזרה של main() וקוראת ל-exit().int __libc_start_main(…) { …… exit(main(…));}מסקנה: הפונקציה exit תמיד נקראת לסיום סטנדרטי של התוכנית.מערכות הפעלה - תרגול 218

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

דוגמת קודמסכמתprintf("pid = %d\n", getpid());pid_t pid = fork();if (pid == 0) { printf("child pid = %d\n", getpid()); char* args[] = {"/bin/date", NULL}; execv(args[0], args); printf("This should not be printed\n");} else { wait(NULL); printf("parent pid = %d\n", getpid());}פלט לדוגמה:pid = 8919child pid = 8920Sun Oct 29 00:31:32 IDT 2017parent pid = 8919מערכות הפעלה - תרגול 224

משתנה תנאי (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