This question spans 2 stages — each part below is tagged with, and links to, the stage it belongs to.
במספרה יש חדר המתנה עם N כסאות וחדר עבודה של K ספרים שבו הלקוחות מסתפרים (N > K). אם אין לקוחות היושבים בחדר ההמתנה, אז ספר שאין אצלו לקוח הולך לישון, אחרת, הספר מספר לקוח שנמצא בחדר ההמתנה. כאשר לקוח נכנס למספרה, הוא מבצע את הפעולות הבאות לפי הסדר: 1. אם יש כיסא פנוי בחדר ההמתנה, אז הלקוח מתיישב וממתין לתורו, אחרת הלקוח עוזב. 2. אם יש ספר ישן, אז הלקוח מעיר אותו. הנחה: כל הסעיפים הבאים מתייחסים לבעיה עם ספר יחיד (1=K) אלא אם נאמר אחרת בשאלה. א. (3 נק') סמנ/י נכון או לא נכון (נא להסביר את התשובה שלכם במשפט אחד): הערה: לצורך השאלה, שליחת סיגנל (בשורה 7 בקוד של סעיף ב, ושורה 10 בקוד של סעיף ג) מהספר ללקוח משמעותה שהלקוח סיים להסתפר. סאמי הציע את המימוש הבא עבור מקרה של ספר יחיד: חוט של לקוח מריץ את הפונקציה customer, וחוט של ספר מריץ את הפונקציה barber. ```c 1. sem_t free_chairs; // initialized to N (number of waiting seats) 2. sem_t customer_ready, barber_ready; // initialized to 0 3. void barber() { 4. while(true) { 5. sem_wait(&customer_ready); 6. sem_post(&free_chairs); 7. sem_post(&barber_ready); 8. } 9. } 10. void customer() { 11. sem_wait(&free_chairs); 12. sem_post(&customer_ready); 13. sem_wait(&barber_ready); 14. // get_haircut 15. } ``` בניסיון לתקן את הקוד, הוצע את המימוש הבא: ```c 1. int waiting_customers = 0; 2. mutex_t barber_lock, customer_lock; //initialized 3. cond_t new_customer, barber_ready; //initialized 4. void barber() { 5. while (true) { 6. mutex_lock(&barber_lock); 7. if (waiting_customers == 0) 8. cond_wait(&new_customer, &barber_lock); 9. waiting_customers--; 10. cond_signal(&barber_ready); 11. mutex_unlock(&barber_lock); 12. } 13. } 14. void customer() { 15. mutex_lock(&customer_lock); 16. if (waiting_customers >= N) 17. return; 18. if (waiting_customers == 0) 19. cond_signal(&new_customer); 20. waiting_customers++; 21. cond_wait(&barber_ready, &customer_lock); 22. // get_haircut 23. mutex_unlock(&customer_lock); 24. } ```
Full original question text (raw OCR)
שאלה 3 - סנכרון (25 נקודות) במספרה יש חדר המתנה עם N כסאות וחדר עבודה של K ספרים שבו הלקוחות מסתפרים (N > K). אם אין לקוחות היושבים בחדר ההמתנה, אז ספר שאין אצלו לקוח הולך לישון, אחרת, הספר מספר לקוח שנמצא בחדר ההמתנה. כאשר לקוח נכנס למספרה, הוא מבצע את הפעולות הבאות לפי הסדר: 1. אם יש כיסא פנוי בחדר ההמתנה, אז הלקוח מתיישב וממתין לתורו, אחרת הלקוח עוזב. 2. אם יש ספר ישן, אז הלקוח מעיר אותו. הנחה: כל הסעיפים הבאים מתייחסים לבעיה עם ספר יחיד (1=K) אלא אם נאמר אחרת בשאלה. א. (3 נק') סמנ/י נכון או לא נכון (נא להסביר את התשובה שלכם במשפט אחד): 1. ייתכן מקרה בו הספר ישן ויש לקוחות שממתינים לתורם (נכון / לא נכון) 2. ייתכן שלקוח יצא מהמספרה בלי להסתפר (נכון / לא נכון) 3. במצב שיש יותר מספר אחד, ייתכן שאחד הספרים ישן כאשר יש מספר לקוחות (ממתינים + מסתפרים כעת) גדול ממספר הספרים (נכון / לא נכון) הערה: לצורך השאלה, שליחת סיגנל (בשורה 7 בקוד של סעיף ב, ושורה 10 בקוד של סעיף ג) מהספר ללקוח משמעותה שהלקוח סיים להסתפר. סאמי הציע את המימוש הבא עבור מקרה של ספר יחיד: חוט של לקוח מריץ את הפונקציה customer, וחוט של ספר מריץ את הפונקציה barber. 1. sem_t free_chairs; // initialized to N (number of waiting seats) 2. sem_t customer_ready, barber_ready; // initialized to 0 3. void barber() { 4. while(true) { 5. sem_wait(&customer_ready); 6. sem_post(&free_chairs); 7. sem_post(&barber_ready); 8. } 9. } 10. void customer() { 11. sem_wait(&free_chairs); 12. sem_post(&customer_ready); 13. sem_wait(&barber_ready); 14. // get_haircut 15. } ב. (4 נק') בהתייחס לקוד הנ״ל, הקיפו את התשובות הנכונות הסבר a. קיימת בעיית נכונות עקב race condition למשאבים משותפים. .b קיימת בעיית DeadLock / Livelock בקוד. c. הקוד משתמש ב-Busy Wait שפוגע בנצילות המעבד. d. הקוד מפר את כללי הכניסה לחדר ההמתנה (שהוגדרו בתחילת השאלה). בניסיון לתקן את הקוד, הוצע את המימוש הבא: 1. int waiting_customers = 0; 2. mutex_t barber_lock, customer_lock; //initialized 3. cond_t new_customer, barber_ready; //initialized 4. void barber() { 5. while (true) { 6. mutex_lock(&barber_lock); 7. if (waiting_customers == 0) 8. cond_wait(&new_customer, &barber_lock); 9. waiting_customers--; 10. cond_signal(&barber_ready); 11. mutex_unlock(&barber_lock); 12. } 13. } 14. void customer() { 15. mutex_lock(&customer_lock); 16. if (waiting_customers >= N) 17. return; 18. if (waiting_customers == 0) 19. cond_signal(&new_customer); 20. waiting_customers++; 21. cond_wait(&barber_ready, &customer_lock); 22. // get_haircut 23. mutex_unlock(&customer_lock); 24. } ג. (8 נק') בהתייחס לקוד הנ״ל, הקיפו את התשובות הנכונות (בהתייחסות לספר יחיד) a. קיימת בעיית נכונות עקב race condition למשאבים משותפים. .b קיימת בעיית DeadLock / Livelock בקוד. c. הקוד משתמש ב-Busy Wait שפוגע בנצילות המעבד. d. הקוד מפר את כללי הכניסה לחדר ההמתנה (שהוגדרו בתחילת השאלה). הסבירו, והדגימו באמצעות תרחישים אפשריים. ד. (5 נק') הציעו דרך פשוטה לתקן את הקוד (תיאור מילולי - בהתייחסות לספר אחד) ה. (5 נק') סאמי שם לב שהקוד הנ"ל (מסעיף ג) לא עובד כמו שצריך ולכן עבד קשה לתקן אותו. לאחר שהוא תיקן את כל הבעיות שיש בקוד, הוא שם לב שהקוד המתוקן עדיין לא עובד במקרה של יותר מספר אחד. תארו תרחיש בעייתי שקורה רק במצב שיש יותר מספר אחד (בעיה שלא הוזכרה קודם) ואיך לתקן אותו.
ייתכן מקרה בו הספר ישן ויש לקוחות שממתינים לתורם (נכון / לא נכון)
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt constructionייתכן שלקוח יצא מהמספרה בלי להסתפר (נכון / לא נכון)
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt constructionבמצב שיש יותר מספר אחד, ייתכן שאחד הספרים ישן כאשר יש מספר לקוחות (ממתינים + מסתפרים כעת) גדול ממספר הספרים (נכון / לא נכון)
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt construction(4 נק') בהתייחס לקוד הנ״ל, הקיפו את התשובות הנכונות הסבר a. קיימת בעיית נכונות עקב race condition למשאבים משותפים.
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt constructionb. קיימת בעיית DeadLock / Livelock בקוד.
Mutex correctness and deadlock avoidanceBanker's algorithm safety checkc. הקוד משתמש ב-Busy Wait שפוגע בנצילות המעבד.
Spinlock implementation propertiesd. הקוד מפר את כללי הכניסה לחדר ההמתנה (שהוגדרו בתחילת השאלה).
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt construction(8 נק') בהתייחס לקוד הנ״ל, הקיפו את התשובות הנכונות (בהתייחסות לספר יחיד) a. קיימת בעיית נכונות עקב race condition למשאבים משותפים.
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt constructionb. קיימת בעיית DeadLock / Livelock בקוד.
Mutex correctness and deadlock avoidanceBanker's algorithm safety checkc. הקוד משתמש ב-Busy Wait שפוגע בנצילות המעבד.
Spinlock implementation propertiesd. הקוד מפר את כללי הכניסה לחדר ההמתנה (שהוגדרו בתחילת השאלה). הסבירו, והדגימו באמצעות תרחישים אפשריים.
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt construction(5 נק') הציעו דרך פשוטה לתקן את הקוד (תיאור מילולי - בהתייחסות לספר אחד)
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt construction(5 נק') סאמי שם לב שהקוד הנ"ל (מסעיף ג) לא עובד כמו שצריך ולכן עבד קשה לתקן אותו. לאחר שהוא תיקן את כל הבעיות שיש בקוד, הוא שם לב שהקוד המתוקן עדיין לא עובד במקרה של יותר מספר אחד. תארו תרחיש בעייתי שקורה רק במצב שיש יותר מספר אחד (בעיה שלא הוזכרה קודם) ואיך לתקן אותו.
libc syscall wrapper caching pitfallsSignal delivery and handler timingSRT / preemptive Gantt construction
The exam question — original PDF
Exactly 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.
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
קריאת המערכת kill#include <sys/types.h>#include <signal.h>int kill(pid_t pid, int sig);פעולה: שולחת את הסיגנל שמספרו sig לתהליך המזוהה ע"י pid.אם הערך של sigהוא 0, אז הפעולה רק בודקת שהתהליך pid קיים, מבלי לשלוח signal (שימושי לבדיקת תקפות pid).ערך מוחזר:0 בהצלחה-1 בכישלון (למשל, אם אין תהליך בעל מזהה pid)מערכות הפעלה - תרגול 38
העברת סיגנלים בשני שלביםרישום – מערכת ההפעלה רושמת ב-PCB של תהליך היעד שיש לו סיגנל ממתין (pending signal).הרישום מתבצע במערך בינארי בין 31 ביטים, ולכן לכל תהליך יכול להיות לכל היותר סיגנל ממתין אחד מכל מספר.טיפול – בכל פעם שהתהליך חוזר ממצב גרעין למצב משתמש, מערכת ההפעלה בודקת אם יש סיגנלים ממתינים ומטפלת בהם.בסיום הטיפול בסיגנל, מערכת ההפעלה תאפס את הביט המתאים במערך. במידה ויש מספר סיגנלים ממתינים, סדר הטיפול מתחילת המערך לסופו.מערכות הפעלה - תרגול 39
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
יצירת חוט חדשפרמטרים: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
משתנה תנאי (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
שחרור חוטים ממתיניםint pthread_cond_signal(pthread_cond_t *cond); משחררת את אחד החוטים הממתינים (הגינות לא מובטחת).int pthread_cond_broadcast(pthread_cond_t *cond);משחררת את כל החוטים הממתינים.כל החוטים מפסיקים להמתין על משתנה התנאי ועוברים להמתין על המנעול. החוטים יחזרו לפעילות בזה אחר זה (בסדר כלשהו, לאו דווקא הוגן) לאחר שינעלו מחדש את ה-mutex.שימו לב: אם אין אף חוט שממתין באותו רגע על משתנה התנאי cond, הפעולות חסרות השפעה (הסיגנל הולך לאיבוד ואינו נזכר הלאה).ערך מוחזר: הפונקציות תמיד מצליחות ומחזירות 0.מערכות הפעלה - תרגול 812
פסיקות חומרה במערכת מרובת ליבותבמערכת מרובת ליבות, מעבדים שונים יכולים לגשת בו-זמנית למבני נתונים משותפים יש להוסיף נעילה מעבר לחסימת הפסיקות המקומית.שגרות טיפול בפסיקות חומרה עושות שימוש במנעולי spinlock (מנעולים הממומשים כ-busy wait).שאלה: מדוע מעדיפים מנעולי spinlock על-פני מנעולי סמפור?busy wait הוא המתנה יעילה יותר כאשר מדובר בנעילות קצרות מאוד כפי שקורה בגרעין, מפני שכך נחסכת התקורה של כניסה ויציאה מהמתנה.בעיית הוגנות, למשל בתרחיש הבא:תהליך רץ, ובאותו הזמן מתקבלת פסיקת חומרה (למשל מהמקלדת).הטיפול בפסיקה מנסה לתפוס את המנעול, אבל המנעול כבר תפוס.התהליך עובר לתור המתנה מסיבה שאינה תלויה בו.מערכות הפעלה - תרגול 856
The exam text, the skills it tests, and the exact slides are already in context.