נוסעים באים לאוטובוס 11 בתחנת חוף הכרמל כדי להגיע לטכניון בזמן להרצאה במערכות הפעלה. כשהאוטובוס מגיע, כל הנוסעים קוראים לפונקציה boardBus() וכל מי שמגיע בזמן שהאוטובוס אוסף נוסעים צריך להמתין לאוטובוס הבא. האוטובוס יכול להכיל עד 50 נוסעים. כשכל הנוסעים עלו, האוטובוס יכול להפעיל את הפונקציה depart(), ואם האוטובוס הגיע ואין נוסעים, הוא עוזב מיד.
Full original question text (raw OCR)
שאלה 3 - סנכרון (25 נק') נוסעים באים לאוטובוס 11 בתחנת חוף הכרמל כדי להגיע לטכניון בזמן להרצאה במערכות הפעלה. כשהאוטובוס מגיע, כל הנוסעים קוראים לפונקציה boardBus() וכל מי שמגיע בזמן שהאוטובוס אוסף נוסעים צריך להמתין לאוטובוס הבא. האוטובוס יכול להכיל עד 50 נוסעים. כשכל הנוסעים עלו, האוטובוס יכול להפעיל את הפונקציה depart(), ואם האוטובוס הגיע ואין נוסעים, הוא עוזב מיד. א' (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 נק') בפתרון הבעיה (שמוצג בסעיפים הבאים) יש שימוש במספר סמפורים, כתבו איזה סמפור: 1. מאפשר הגעה אטומית של נוסעים או של האוטובוס לתחנה: 2. נועד להעלות נוסע בצורה אטומית לאוטובוס באמצעות הפונקציה boardBus: 3. נועד להודיע לאוטובוס שעלה נוסע לאוטובוס:
Semaphore blocking and busy-wait(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();
Mutex correctness and deadlock avoidanceSRT / preemptive Gantt construction(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);
Mutex correctness and deadlock avoidance(7 נק') יכול להיות מתסכל עבור הנוסעים שמגיעים בזמן שהאוטובוס בתחנה להמתין לאוטובוס הבא. איזה שינוי בשורה אחת יש לבצע בקוד כדי לאפשר גם להם אפשרות לעלות לאוטובוס? עליכם להוסיף שורה (או יותר) בקוד משני סעיפים קודמים שלא ציינו בנוסף לשורות שלכם. (רמז: בקוד של האוטובוס). שורת קוד להוספה: מיקום (לאן להוסיף): הסבר:
Semaphore blocking and busy-waitMutex correctness and deadlock avoidanceSRT / preemptive Gantt construction
The exam question — original PDF
pages 7, 8Exactly 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
דוגמת FCFSaverageResponseTime = (10 + 20 + 30) / 3 = 20כעת נסיר את הנחה 1 ("כל התהליכים רצים למשך אותו זמן"). לכל תהליך זמן ריצה משלו.תוכלו לחשוב על דוגמה שבה FCFS אינו יעיל?מערכות הפעלה - תרגול 59כל התהליכים רצים למשך אותו זמן.כל התהליכים מגיעים באותו זמן (t=0).אם תהליך התחיל לרוץ, אז הוא ירוץ עד לסיומו ללא הפסקות.התהליכים משתמשים רק במעבד ולא מבצעים I/O.זמן הריצה של כל התהליכים ידוע מראש.
אפקט השיירה (convoy effect)averageResponseTime = (100 + 110 + 120) / 3 = 110אלגוריתם FCFS עלול לסבול מ"אפקט השיירה": מצב שבו תהליך אחד ארוך מעכב הרבה תהליכים קצרים. מערכות הפעלה - תרגול 510
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
The exam text, the skills it tests, and the exact slides are already in context.