This question spans 2 stages — each part below is tagged with, and links to, the stage it belongs to.
שאלה זו דנה בסנכרון ובמנעולים בגרעין שנלמד בתרגולים. דני, מפתח לינוקס, החליט להוסיף תמיכה בגרעין עבור מנעולים של רמת המשתמש (user level). לשם כך, הוא הגדיר בגרעין מנעול יחיד (גלובלי) המשותף לכלל התהליכים הרצים במערכת, וכן קריאות מערכת מתאימות בכדי לאפשר לתהליכים לתפוס ולשחרר את המנעול: volatile int global_lock = 0; wait_queue_head_t global_queue; int sys_global_lock() { while (global_lock != 0) { // atomically puts the process to sleep if // global_lock is locked: wait_event_interruptible(global_queue, &global_lock); } global_lock = 1; } int sys_global_unlock() { global_lock = 0; wake_up_interruptible(global_queue); // wakes up all // processes waiting in uni_queue } להלן דוגמא לשימוש בקריאות המערכת הנ"ל ב- user-level: fork(); global_lock(); // wrapper function for sys_global_lock X++; // X is a shared variable between parent & child global_unlock(); // wrapper function for sys_global_unlock
Full original question text (raw OCR)
שאלה 4 - סנכרוניזציה (25 נק') שאלה זו דנה בסנכרון ובמנעולים בגרעין שנלמד בתרגולים. דני, מפתח לינוקס, החליט להוסיף תמיכה בגרעין עבור מנעולים של רמת המשתמש (user level). לשם כך, הוא הגדיר בגרעין מנעול יחיד (גלובלי) המשותף לכלל התהליכים הרצים במערכת, וכן קריאות מערכת מתאימות בכדי לאפשר לתהליכים לתפוס ולשחרר את המנעול: volatile int global_lock = 0; wait_queue_head_t global_queue; int sys_global_lock() { while (global_lock != 0) { // atomically puts the process to sleep if // global_lock is locked: wait_event_interruptible(global_queue, &global_lock); } global_lock = 1; } int sys_global_unlock() { global_lock = 0; wake_up_interruptible(global_queue); // wakes up all // processes waiting in uni_queue } להלן דוגמא לשימוש בקריאות המערכת הנ"ל ב- user-level: fork(); global_lock(); // wrapper function for sys_global_lock X++; // X is a shared variable between parent & child global_unlock(); // wrapper function for sys_global_unlock
(5 נק') האם המימוש הנ"ל נכון? (כלומר אכן תומך בהפרדה הדדית עבור המשתנה המשותף X?) נמקו.
fork/exec address-space semanticslibc syscall wrapper caching pitfallsSRT / preemptive Gantt construction(5 נק') לדעת דני, הקוד נכון במערכת שהינה בעלת ליבת מעבד יחידה. האם הוא צודק? נמקו.
libc syscall wrapper caching pitfallsreview:T2·22כדי לשפר את התמיכה במערכת מרובת-ליבות, יוסי הציע להוסיף spinlocks לקוד של דני באופן הבא: spinlock_t aux_lock; int sys_global_lock() { spin_lock(aux_lock); while (global_lock != 0) wait_event_interruptible(global_queue, &global_lock); global_lock = 1; } int sys_global_unlock() { global_lock = 0; wake_up_interruptible(global_queue); spin_unlock(aux_lock); } (5 נק') כאשר יוסי בחן את הקוד המשופר (על מחשב בעל מספר ליבות) המנעול אכן עבד נכון, אך דני טען שכשהריץ את אותו הקוד (על מחשב בן ליבה אחת) מערכת ההפעלה נתקעה. מה גרם לתקלה במערכת של דני? נמקו.
libc syscall wrapper caching pitfallsLocal vs global interrupt disableSpinlock implementation propertiesMutex correctness and deadlock avoidanceSRT / preemptive Gantt construction(5 נק') האם המחשב של דני היה נתקע אילו היינו משתמשים בסמפור במקום ב-spinlock? (כלומר, חישבו על aux_lock-כסמפור והחליפו את הקריאות ל-spin_lock/spin_unlock ב-sem_down/sem_up?)
Spinlock implementation propertiesSemaphore blocking and busy-waitכעת נדון בקוד שונה במעט אשר משתמש בשני המאקרו-ים הבאים: • cond_wait - מקבל שלושה פרמטרים: (i) תור המתנה, (ii) משתנה mutex המספק מניעה הדדית, ו- (iii) תנאי בולאני. פעולתו של cond_wait היא אטומית: הוא בודק את התנאי הבוליאני ואם התנאי מתקיים משחררים את ה- mutex ונכנסים להמתנה (בשינה) על התור. כאשר cond_wait חוזרת, מתבצעת נעילה mutex-חוזרת של ה • cond_signal - מקבל תור המתנה ומעיר תהליך יחיד מתור זה. המימוש הבא יוצר מנעול תקין: Mutex m; int sys_global_lock() { lock(m); while (global_lock != 0) { cond_wait(global_queue, m, (global_lock!=0)); } unlock(m); } int sys_global_unlock() { lock(m); global_lock=0; //Free lock cond_signal(global_queue); //Wakes a single process waiting in uni_queue unlock(m); } דנה שמה לב שעל אף שהמימוש תקין, לעתים הוא עלול לגורם למצבי קיפאון בעקבות נעילה כפולה מאותו החוט (קריאה של מספר פעמים ברצף לפונקציה uni_lock) או בעקבות שחרור המנעול ע"י חוט שלא נעל אותו. (5 נק') הציעו שיפור למנעול כפי שהוא כתוב לעיל, המאפשר לאותו החוט לקרוא לפונקציית הנעילה כמה פעמים ברצף מבלי להיתקע (בכל נעילה נוספת לאחר הראשונה יוחזר הערך EPERM), ושעבור חוט שמנסה לשחרר מנעול שלא נעל בעצמו יוחזר ערך השגיאה EPERM. על הקוד שלכם להיות כתוב בשפת C (אך לא יורדו נקודות על שגיאות תחביר קטנות). הקפידו על תיעוד שמנמק את הנכונות של הקוד שלכם.
libc syscall wrapper caching pitfallsSignal delivery and handler timingPipe IPC semanticsMutex correctness and deadlock avoidanceSRT / preemptive Gantt construction
The exam question — original PDF
pages 9, 10, 11, 12Exactly 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.
אחרי fork()parentint main() { int x = 0; pid_t p = fork(); if (p == 0) { x = 1; } else { x = 2; }}sonint main() { int x = 0; pid_t p = fork(); if (p == 0) { x = 1; } else { x = 2; }}מערכות הפעלה - תרגול 210
קריאות המערכת 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
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
שחרור חוטים ממתיניםint pthread_cond_signal(pthread_cond_t *cond); משחררת את אחד החוטים הממתינים (הגינות לא מובטחת).int pthread_cond_broadcast(pthread_cond_t *cond);משחררת את כל החוטים הממתינים.כל החוטים מפסיקים להמתין על משתנה התנאי ועוברים להמתין על המנעול. החוטים יחזרו לפעילות בזה אחר זה (בסדר כלשהו, לאו דווקא הוגן) לאחר שינעלו מחדש את ה-mutex.שימו לב: אם אין אף חוט שממתין באותו רגע על משתנה התנאי cond, הפעולות חסרות השפעה (הסיגנל הולך לאיבוד ואינו נזכר הלאה).ערך מוחזר: הפונקציות תמיד מצליחות ומחזירות 0.מערכות הפעלה - תרגול 812
מועד א', אביב 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.