תזכורת: • לאורך כל השאלה הזאת הניחו ארכיטקטורת 32 ביט. מילת מכונה היא בגודל 32 ביט. • קריאה וכתיבה של מילת מכונה מתבצעת באופן אטומי, כלומר לא תתכן קריאה/כתיבה של מספר ביטים של ערך אחד של המילה ואז השלמה של שאר הביטים מ/אל ערך אחר של המילה. • Memory fence או Memory barrier זאת פקודה הגורמת ל: (1) כל הכתיבות שקרו לאחרונה בליבה זאת מחלחלות לזיכרון, כלומר כתובות הזיכרון הרלוונטיות נראות באופן מעודכן לכל החוטים. (2) Memory barrier או Memory fence גורם לכך שהמעבד והקומפיילר לא יחליפו פקודות מכונה ממקומותיהם, סביב פקודה זאת. • Compare-And-Swap או CAS היא פקודת מכונה אטומית שמספקת (באופן אטומי ובפקודת מכונה אחת) את הקוד המוצג למטה. 01 // int32 means of the size of machine word 02 Bool CAS( 03 int32 machineWordAddress, 04 int32 expectedValue, 05 int32 newValue) { 06 07 Bool result = (*machineWordAddress == expectedValue); 08 if (result) { 09 *machineWordAddress = newValue; 10 } 11 memory_fence_instruction(); 12 return result; 13 }
Full original question text (raw OCR)
שאלה 3 - תכנות מקבילי (25 נק') תזכורת: • לאורך כל השאלה הזאת הניחו ארכיטקטורת 32 ביט. מילת מכונה היא בגודל 32 ביט. • קריאה וכתיבה של מילת מכונה מתבצעת באופן אטומי, כלומר לא תתכן קריאה/כתיבה של מספר ביטים של ערך אחד של המילה ואז השלמה של שאר הביטים מ/אל ערך אחר של המילה. • Memory fence או Memory barrier זאת פקודה הגורמת ל: (1) כל הכתיבות שקרו לאחרונה בליבה זאת מחלחלות לזיכרון, כלומר כתובות הזיכרון הרלוונטיות נראות באופן מעודכן לכל החוטים. (2) Memory barrier או Memory fence גורם לכך שהמעבד והקומפיילר לא יחליפו פקודות מכונה ממקומותיהם, סביב פקודה זאת. • Compare-And-Swap או CAS היא פקודת מכונה אטומית שמספקת (באופן אטומי ובפקודת מכונה אחת) את הקוד המוצג למטה. 01 // int32 means of the size of machine word 02 Bool CAS( 03 int32 machineWordAddress, 04 int32 expectedValue, 05 int32 newValue) { 06 07 Bool result = (*machineWordAddress == expectedValue); 08 if (result) { 09 *machineWordAddress = newValue; 10 } 11 memory_fence_instruction(); 12 return result; 13 } 1. (4 נק) האם הקוד הבא ממש מנעול מסוג spin lock ? (כל החוטים ניגשים לאותו משתנה גלובלי lock) 01 int32 lock = 0; // initially the lock is free 02 03 void lock() { 04 while (CAS(&lock, 0, 1) == true); 05 } 06 07 void unlock() { 08 lock = 1; 09 } 2. (5 נק) האם הקוד הבא ממש מנעול מסוג spin lock ? (כל החוטים ניגשים לאותו משתנה גלובלי lock) 01 int32 lock = 0; // initially the lock is free 02 03 void lock() { 04 while (CAS(&lock, 0, 1) == true); 05 } 06 07 void unlock() { 08 lock = 0; 09 } 3. (6 נק) האם הקוד הבא מממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = NULL; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 Node* expectedTopNode; 12 do { 13 expectedTopNode = top; 14 newNode.next = expectedTopNode; 15 } while (!CAS(&top, expectedTopNode, newNode)); 16 } 4. (5 נק) סטודנט אחד טוען שאפשר לא להשתמש במשתנה expectedTopNode וכך לחסוך בזיכרון. האם הקוד הבא ממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = null; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 do { 12 newNode.next = top; 13 } while (!CAS(&top, top, newNode)); 14 } 5. (5 נק) סטודנטית אחת טוענת שאפשר לא להשתמש במשתנה expectedTopNode וכך לחסוך בזיכרון, אבל עושה את זה באופן אחר. האם הקוד הבא ממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = null; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 do { 12 newNode.next = top; 13 } while (!CAS(&top, newNode.next, newNode)); 14 }
1. (4 נק) האם הקוד הבא ממש מנעול מסוג spin lock ? (כל החוטים ניגשים לאותו משתנה גלובלי lock) 01 int32 lock = 0; // initially the lock is free 02 03 void lock() { 04 while (CAS(&lock, 0, 1) == true); 05 } 06 07 void unlock() { 08 lock = 1; 09 } a. כן b. לא, כי זה מממש spinlock ולא wait lock c. לא, כי הערך המצופה (expectedValue) של CAS בשורה 4 צריך להיות 1 ולא 0 d. לא, כי צריך השמה של 0 ולא 1 בשורה 8 e. תשובות d ו-c נכונות f. אף תשובה לא נכונה נימוק:
Pipe IPC semanticsSpinlock implementation propertiesMutex correctness and deadlock avoidance2. (5 נק) האם הקוד הבא ממש מנעול מסוג spin lock ? (כל החוטים ניגשים לאותו משתנה גלובלי lock) 01 int32 lock = 0; // initially the lock is free 02 03 void lock() { 04 while (CAS(&lock, 0, 1) == true); 05 } 06 07 void unlock() { 08 lock = 0; 09 } a. כן b. לא, כי זה מממש spinlock ולא wait lock c. לא, כי הערך המצופה (expectedValue) של CAS בשורה 4 צריך להיות 1 ולא 0 d. לא, כי צריך השמה של 1 ולא 0 בשורה 8 e. לא, כי צריך memory fence לפני ואחרי שורה 8 או השמה דרך פקודת מכונה אטומית בשורה 8 f. תשובות d ו-c נכונות g. אף תשובה לא נכונה נימוק:
Pipe IPC semanticsSpinlock implementation propertiesMutex correctness and deadlock avoidance3. (6 נק) האם הקוד הבא מממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = NULL; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 Node* expectedTopNode; 12 do { 13 expectedTopNode = top; 14 newNode.next = expectedTopNode; 15 } while (!CAS(&top, expectedTopNode, newNode)); 16 } a. כן b. לא, כי newNode.next זה משתנה שנמצא בערימה ולכן ערכו עלול להשתנות c. לא, כי צריך memory fence לפחות במקום אחד d. לא, כי יכולה להיות החלפת הקשר בזמן ביצוע פקודת CAS e. לא, כי יכולה להיות החלפת הקשר בין השורות 13 ו-14 f. אף תשובה לא נכונה נימוק:
Voluntary vs preemptive context switchPipe IPC semanticsSRT / preemptive Gantt construction4. (5 נק) סטודנט אחד טוען שאפשר לא להשתמש במשתנה expectedTopNode וכך לחסוך בזיכרון. האם הקוד הבא ממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = null; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 do { 12 newNode.next = top; 13 } while (!CAS(&top, top, newNode)); 14 } a. כן, בכל מקרה הערך של expectedTopNode נלקח מ-top b. לא, כי newNode.next זה משתנה שנמצא בערימה ולכן ערכו עלול להשתנות c. לא, כי צריך memory fence לפחות במקום אחד d. לא, כי יכולה להיות החלפת הקשר בזמן ביצוע פקודת CAS e. לא, כי יכולה להיות החלפת הקשר בין השורות 12 ו-13 f. אף תשובה לא נכונה נימוק:
Voluntary vs preemptive context switchPipe IPC semanticsSRT / preemptive Gantt construction5. (5 נק) סטודנטית אחת טוענת שאפשר לא להשתמש במשתנה expectedTopNode וכך לחסוך בזיכרון, אבל עושה את זה באופן אחר. האם הקוד הבא ממש מחסנית מקבילית (concurrent lock-free stack) תקינה? (כל החוטים ניגשים לאותו משתנה גלובלי top) 01 typedef struct node { 02 int data; 03 Struct node* next; 04 } Node; 05 06 Node* top = null; 07 08 void push(int newData) { 09 // assume correctness and success of the following allocation 10 Node* newNode = allocateNewNodeWithData(newData); 11 do { 12 newNode.next = top; 13 } while (!CAS(&top, newNode.next, newNode)); 14 } a. כן b. לא, כי newNode.next זה משתנה שנמצא בערימה ולכן ערכו עלול להשתנות c. לא, כי צריך memory fence לפחות במקום אחד d. לא, כי יכולה להיות החלפת הקשר בזמן ביצוע פקודת CAS e. לא, כי יכולה להיות החלפת הקשר בין השורות 12 ו-13 f. אף תשובה לא נכונה נימוק:
Voluntary vs preemptive context switchPipe IPC semanticsSRT / preemptive Gantt construction
The exam question — original PDF
pages 9, 10, 11, 12, 13Exactly 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.
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
מהי החלפת הקשר?מערכות הפעלה - תרגול 610
מהי החלפת הקשר?לכל תהליך יש "הקשר ביצוע" (execution context) המכיל את כל המידע הדרוש לביצוע התהליך.מחסניות, רגיסטרים, תכולת זיכרון, קבצים פתוחים, ..."החלפת הקשר" = עצירת הביצוע של התהליך הנוכחי ושמירת ההקשר שלו.טעינת ההקשר של התהליך הבא לביצוע.הקשר התהליך הנוכחי מתחלף – מכאן שם הפעולה "החלפת הקשר".מערכות הפעלה - תרגול 611
יצירת חוט חדשפרמטרים:thread – מצביע למקום בו יאוחסן מזהה החוט החדש במקרה של סיום הפונקציה בהצלחה.attr – מאפיינים המתארים את תכונות החוט החדש, כגון האם החוט הוא חוט גרעין או חוט משתמש, האם ניתן לבצע לו join, כלומר להמתין לסיומו, וכו'. בד"כ נספק ערך NULL המציין חוט ברירת המחדל של המערכת, שניתן להמתין לסיומו.void* (*start_routine)(void*) מצביע לפונקציה שתהווה את קוד החוט. הערך המוחזר מפונקציה זו במקרה של סיומה הטבעי הינו ערך הסיום של החוט.arg – פרמטר שיסופק לפונקציה עם הפעלתה.מערכות הפעלה - תרגול 714
משתנה תנאי (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
סיכום השיעור שעבר2the CPU searches the TLBhitmissthe CPU walks the page tablecompletedpage faultphysical addressvirtual addressthe OS serves the page faultמערכות הפעלה - תרגול 10
מה נלמד היום?3the CPU searches the TLBhitmissthe CPU walks the page tablecompletedpage faultphysical addressvirtual addresskill the process or the entire systemfix the page table and retrythe OS serves the page faultinvalidvalidמערכות הפעלה - תרגול 10
הרשאות של אזור זיכרוןהדגלים המציינים את הרשאות האזור נשמרים בשדה vm_flags והם מאפשרים לגרעין לסווג גישות חוקיות ולא חוקיות לדפים באזור.VM_READ, VM_WRITE, VM_EXEC – האם מותר לקרוא/לכתוב/לבצע נתונים בדפים באזור.VM_MAYREAD, VM_MAYWRITE, VM_MAYEXEC – "הרשאת הרשאה" לכל אחת מההרשאות הנ"ל.לדוגמה VM_MAYWRITE קובע האם מותר להדליק את VM_WRITE.הדגלים האלה קשורים לקריאת המערכת mprotect() – מעבר לחומר הקורס.VM_SHARED – האם צריך לשתף דפים באזור זה עם תהליכי בן.VM_LOCKED – אסור לפנות את הדפים באזור מהזיכרון לדיסק.17מערכות הפעלה - תרגול 10
מרחבי זיכרון וקריאות מערכתחוטים הנוצרים ע"י קריאת המערכתclone() משתפים את מרחב הזיכרון ע"י הצבעה לאותו מתאר מרחב הזיכרון של תהליך האב.יש להגדיל את מונה השיתוף (mm_users) של מתאר מרחב הזיכרון של תהליך האב.קריאת המערכת execv() ודומותיה טוענות תהליך חדש ולכן הן משחררות את מרחב הזיכרון ומקצות אחד חדש.קריאת המערכתfork() מקצה לתהליך הבן מרחב זיכרון משלו.במקרה שכזה צריך להעתיק את מרחב הזיכרון של האב לזה של הבן.בפועל, בדרך-כלל אין באמת העתקה בזכות מנגנון copy-on-write.23מערכות הפעלה - תרגול 10
הפתרון: copy-on-write (COW)הרעיון של מנגנון copy-on-write (COW) הוא:דפים הניתנים לכתיבה שאינם יכולים להיות משותפים (לדוגמה, המחסנית), מוגדרים בתחילה כמשותפים אבל מועתקים לעותק פרטי כאשר אחד התהליכים השותפים (האב או הבן) מנסה לכתוב אליהם לראשונה.שאר הדפים (כדוגמת דפי קוד או דפי נתונים לקריאה בלבד) הופכים למשותפים בין מרחבי הזיכרון של האב והבן.מנגנון COW פותר את שתי הבעיות שהוצגו קודם:COW מקטין את זמן הביצוע של fork() כי הוא "פורס לתשלומים" את ההעתקה של כל מרחב הזיכרון להרבה העתקות קטנות בגודל דף שיתבצעו בעתיד---בכל כתיבה ראשונה לדף שאינו משותף.במידה ותהליך הבן יבצע מיד execv(), מרחב הזיכרון שלו יימחק וכך תיחסך רוב פעולת ההעתקה.27מערכות הפעלה - תרגול 10
father processpage tablememory regionsדוגמה: לפני קריאת מערכת fork()28…PTE #11r/w = 1…frame #250count == 1מערכות הפעלה - תרגול 10region #1VM_MAYWRITE=1VM_WRITE=1region #2
The exam text, the skills it tests, and the exact slides are already in context.