This question spans 2 stages — each part below is tagged with, and links to, the stage it belongs to.
נרצה להכליל את הסעיף הקודם לכל ח חיובי. נגדיר נקודת מפגש (rendezvous) כנקודה בקוד שאליה צריכים כל החוטים להגיע לפני שאפילו אחד מהם יכול להמשיך. במילים אחרות, 1-n החוטים הראשונים ייחסמו בהגיעם לנקודת המפגש, ורק כאשר יגיע החוט ה- ח יוכלו כל החוטים להמשיך. בכל נקודת מפגש נקרא לפונקציה שנקרא לה barrier שמטרתה לחסום את החוטים עד שיגיע החוט ה- ח ואז לתת להם לעבור הלאה. המטרה שלנו היא לממש את פונקציה זו. לצורך המימוש נגדיר גלובלית את משתני העזר הבאים אשר משתמשים בהם אך ורק בפונקציית barrier. הערה: המימושים הבאים של barrier מיועדים לשימוש חד פעמי. n = number of threads int counter = 0; sem1 = Semaphore(1); sem2 = Semaphore(0);
Full original question text (raw OCR)
שאלה 1 - סנכרון (25 נק') 1. (4 נק') נתון סמפור sem שמאותחל ל- 0 אשר נגיש מ Thread A וגם מ Thread B .השלימו את הקוד החסר כך שביצוע statement a1 יסתיים לפני תחילת ביצוע statement b1. Thread A Thread B 1. statement a1 1. 2. 2. statement b1 נימוק: 2 (4 נק') נרצה להכליל את הרעיון של הסעיף הקודם ולהפוך אותו לסימטרי. ביכולתכם להגדיר כמה סמפורים כרצונכם. השלם את הקוד הבא כך שמתקיים: statement a2 מסתיים לפני תחילתו של statement b1 Ο .statement b2 מסתיים לפני תחילתו של statement a1 // initialize semaphores Thread A Thread B 1. statement a1 1. statement b1 2. 2. 3. 3. 4. statement a2 4. statement b2 נרצה להכליל את הסעיף הקודם לכל ח חיובי. נגדיר נקודת מפגש (rendezvous) כנקודה בקוד שאליה צריכים כל החוטים להגיע לפני שאפילו אחד מהם יכול להמשיך. במילים אחרות, 1-n החוטים הראשונים ייחסמו בהגיעם לנקודת המפגש, ורק כאשר יגיע החוט ה- ח יוכלו כל החוטים להמשיך. בכל נקודת מפגש נקרא לפונקציה שנקרא לה barrier שמטרתה לחסום את החוטים עד שיגיע החוט ה- ח ואז לתת להם לעבור הלאה. המטרה שלנו היא לממש את פונקציה זו. לצורך המימוש נגדיר גלובלית את משתני העזר הבאים אשר משתמשים בהם אך ורק בפונקציית barrier. הערה: המימושים הבאים של barrier מיועדים לשימוש חד פעמי. n = number of threads int counter = 0; sem1 = Semaphore(1); sem2 = Semaphore(0); דני הציע את המימוש הבא לפונקצית barrier: 1. void barrier(){ 2. 3. sem1.wait(); 4. counter+=1; 5. sem1.post(); 6. while(counter <= n); 7. } 3. (4 נק') תארו את הבעייה בקוד הנתון דני הציע מימוש חדש לפונקצית barrier: 1. void barrier(){ 2. 3. sem1.wait(); 4. counter+=1; 5. 6. while(counter <= n); sem1.post(); 7. } 4. (4 נק') תארו את הבעייה בקוד הנתון דני הסיק שהמימוש שלו בעייתי ולכן הציע מימוש חדש של פונקצית barrier: 1. void barrier(){ 2. 3. sem1.wait(); 4. counter+=1; 5. sem1.post(); 6. if (counter == n) 7. sem2.post(); 8. 9. sem2.wait(); 10. 11. } 5. (4 נק') תארו את הבעייה בקוד הנתון 6. (5 נק') הציעו תיקון על ידי הוספת שורת קוד אחת כך שהקוד הנ"ל יהיה נכון: נרצה להוסיף (כתבו שורת הקוד): אחרי השורה נימוק:
נתון סמפור sem שמאותחל ל- 0 אשר נגיש מ Thread A וגם מ Thread B .השלימו את הקוד החסר כך שביצוע statement a1 יסתיים לפני תחילת ביצוע statement b1.
Pipe IPC semanticsSemaphore blocking and busy-waitנרצה להכליל את הרעיון של הסעיף הקודם ולהפוך אותו לסימטרי. ביכולתכם להגדיר כמה סמפורים כרצונכם. השלם את הקוד הבא כך שמתקיים: statement a2 מסתיים לפני תחילתו של statement b1. statement b2 מסתיים לפני תחילתו של statement a1.
Semaphore blocking and busy-waitדני הציע את המימוש הבא לפונקצית barrier: void barrier(){ sem1.wait(); counter+=1; sem1.post(); while(counter <= n); } תארו את הבעייה בקוד הנתון
SRT / preemptive Gantt constructionדני הציע מימוש חדש לפונקצית barrier: void barrier(){ sem1.wait(); counter+=1; while(counter <= n); sem1.post(); } תארו את הבעייה בקוד הנתון
SRT / preemptive Gantt constructionדני הסיק שהמימוש שלו בעייתי ולכן הציע מימוש חדש של פונקצית barrier: void barrier(){ sem1.wait(); counter+=1; sem1.post(); if (counter == n) sem2.post(); sem2.wait(); } תארו את הבעייה בקוד הנתון
SRT / preemptive Gantt constructionהציעו תיקון על ידי הוספת שורת קוד אחת כך שהקוד הנ"ל יהיה נכון: נרצה להוסיף (כתבו שורת הקוד): אחרי השורה
Pipe IPC semanticsSemaphore blocking and busy-waitSRT / preemptive Gantt construction
The exam question — original PDF
pages 2, 3, 4, 5Exactly 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
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
קריאת המערכת 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
תרגול 8מנגנוני סנכרון: משתני תנאימנגנוני סנכרון: סמפוריםדוגמה: מימוש מנעול קוראים-כותביםסינכרון בגרעין לינוקס1מערכות הפעלה - תרגול 8
TL;DRבתרגול הקודם למדנו לכתוב קוד מקבילי באמצעות חוטים.ראינו שבכל בעיה לא טריוויאלית יש צורך בסנכרון בין החוטים.היום נלמד על מנגנוני סנכרון נוספים של ממשק pthreads :לבסוף, נלמד דוגמה נוספת של קוד מקבילי חשוב: גרעין לינוקס.קוד הגרעין לא משתמש בחוטים, אבל ניגש לזיכרון משותף מתוך מספר מסלולי בקרה שרצים במקביל, ולכן העקרונות שלמדנו תקפים גם עבורו.2מערכות הפעלה - תרגול 8להבטחת סדרלהבטחת אטומיותמשתני תנאי(condition variables)מנעולים(mutexes)סמפורים (semaphores)
מועד א', אביב 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.