This question spans 2 stages — each part below is tagged with, and links to, the stage it belongs to.
תניחו את החומרה הבאה: 1. מעבד Intel 64 bits בעל 8 ליבות, כאשר בכל ליבה ישנו TLB שגודלו 128 כניסות (entries) 2. דיסק קשיח מסוג HDD [Diagram of 8 Cores with TLBs and shared Memory] בתהליך מסוים רצים 8 חוטים: ד ... To, T1, T2 (כל חוט רץ על ליבה נפרדת) שכולם ניגשים למשתנה משותף: uint32 array[8192]; /* 32KB */ המערך מגובה על ידי memory mapped file, כלומר עבור כתובת תחילת המערך הופעלה קריאת מערכת הפעלה: ()mmap עם דגל MAP_SHARED כלומר לא פרטי. שום דבר אחר לא קורה על המכונה, חוץ ממה שמתואר בשאלה. לא היו גישות לזיכרון לפני התרחישים המתוארים מטה. מספר מזהה של החוט דהינו ו. אנחנו מתעניינים בביצועים של מספר דרכים בהם החוטים עובדים עם המערך. להלן מספר תרחישים: תרחיש 1 (15 נק') חוטים מעדכנים בו-זמנית את המערך באופן סדרתי: חוט ד כותב לתא ראשון ואז לתא שני ושלישי והלאה במערך, עד ש T מעדכן את 4KB הראשונים במערך. חוט T₁ מעדכן את 4KB השניים במערך, וכך הלאה לכל חוט. כל חוט כותב לכל תא את מספר מזהה של החוט שלו (7...0,1,2) מחובר עם מונה רץ. [Code snippet] תרחיש 2 (15 נק') חוטים מעדכנים בו-זמנית את המערך באופן רנדומלי: חוט ד כותב ל 1024 תאים רנדומליים בתוך המערך, במקביל ד גם כותב ל 1024 תאים רנדומליים בתוך המערך, וכך הלאה כל חוט. כל חוט כותב לכל תא את מספר מזהה של החוט שלו (7...0,1,2) מחובר עם מונה רץ. תרחיש 1 לא התרחש לפני. [Code snippet]
Full original question text (raw OCR)
תניחו את החומרה הבאה: 1. מעבד Intel 64 bits בעל 8 ליבות, כאשר בכל ליבה ישנו TLB שגודלו 128 כניסות (entries) 2. דיסק קשיח מסוג HDD [Diagram of 8 Cores with TLBs and shared Memory] בתהליך מסוים רצים 8 חוטים: ד ... To, T1, T2 (כל חוט רץ על ליבה נפרדת) שכולם ניגשים למשתנה משותף: uint32 array[8192]; /* 32KB */ המערך מגובה על ידי memory mapped file, כלומר עבור כתובת תחילת המערך הופעלה קריאת מערכת הפעלה: ()mmap עם דגל MAP_SHARED כלומר לא פרטי. שום דבר אחר לא קורה על המכונה, חוץ ממה שמתואר בשאלה. לא היו גישות לזיכרון לפני התרחישים המתוארים מטה. מספר מזהה של החוט דהינו ו. אנחנו מתעניינים בביצועים של מספר דרכים בהם החוטים עובדים עם המערך. להלן מספר תרחישים: תרחיש 1 (15 נק') חוטים מעדכנים בו-זמנית את המערך באופן סדרתי: חוט ד כותב לתא ראשון ואז לתא שני ושלישי והלאה במערך, עד ש T מעדכן את 4KB הראשונים במערך. חוט T₁ מעדכן את 4KB השניים במערך, וכך הלאה לכל חוט. כל חוט כותב לכל תא את מספר מזהה של החוט שלו (7...0,1,2) מחובר עם מונה רץ. for (i=threadID*1024; i<(threadID+1)*1024; i++) { } array[i]=threadID+i; תרחיש 2 (15 נק') חוטים מעדכנים בו-זמנית את המערך באופן רנדומלי: חוט ד כותב ל 1024 תאים רנדומליים בתוך המערך, במקביל ד גם כותב ל 1024 תאים רנדומליים בתוך המערך, וכך הלאה כל חוט. כל חוט כותב לכל תא את מספר מזהה של החוט שלו (7...0,1,2) מחובר עם מונה רץ. תרחיש 1 לא התרחש לפני. for (i=threadID*1024; i<(threadID+1)*1024; i++) { int j = randomNumberInRange(0,8191); array[j]=threadID+i; }
מהו המספר הנמוך ביותר של חריגות דף (page faults) עבור ריצה תקינה של תרחיש 1? הסבירו. א. 0 ב. 1 ג. 8 ד. 16 ה. אף תשובה לא נכונה
Page fault error code classificationהאם זמן ריצה של תרחיש 1 יהיה קצר יותר או ארוך יותר, אילו המערך לא היה מגובה על ידי memory mapped file? כלומר פשוט מערך גלובלי רגיל. הסבירו את תשובתכם. א. קצר יותר בלי mmap ב. ארוך יותר בלי mmap ג. אותו דבר בלי mmap ד. לא ניתן לדעת ה. אף תשובה לא נכונה
libc syscall wrapper caching pitfallsVirtual-to-physical address translationSRT / preemptive Gantt constructionאיזה סוג של עקרון המקומיות (locality of access) אנחנו רואים בתרחיש 1? הסבירו. א. Spatial locality. ב. Temporal locality. ג. לא מתקיים עקרון המקומיות (There is no locality at all) ד. לא ניתן לדעת ה. אף תשובה לא נכונה
libc syscall wrapper caching pitfallsVirtual-to-physical address translationSRT / preemptive Gantt constructionבאיזה סוג של אמצעי סנכרון צריך להשתמש, אם רוצים להבטיח שבכל תא במערך ייכתב באופן תקני מספר מזהה של החוט מחובר עם מונה רץ? איך זה ישפיע על הביצועים? א. לא צריך אמצעי סנכרון ב. מספיק מנעול אחד ג. צריך מספר מנעולים ד. צריך אמצעי סנכרון אחר ממנעול (הסבר מטה) ה. אף תשובה לא נכונה
Pipe IPC semanticsMutex correctness and deadlock avoidanceמהו מספר הגבוה ביותר של כניסות TLB (בכל הליבות יחד) שיכילו תרגום תכף (valid) לאחר סיום ריצה של תרחיש 1? הסבירו. א. 1 ב. 8 ג. 64 ד. לא ניתן לדעת ה. אף תשובה לא נכונה
Virtual-to-physical address translationמהו המספר הנמוך ביותר של חריגות דף (page faults) עבור ריצה תקינה של תרחיש 2? הסבירו. א. 0 ב. 1 ג. 8 ד. 16 ה. אף תשובה לא נכונה
Page fault error code classificationהאם זמן ריצה של תרחיש 2 יהיה קצר יותר או ארוך יותר בהשוואה לתרחיש 1. הסבירו את תשובתכם. א. קצר יותר ב. ארוך יותר ג. אותו דבר ד. לא ניתן לדעת ה. אף תשובה לא נכונה
libc syscall wrapper caching pitfallsVirtual-to-physical address translationSRT / preemptive Gantt constructionאת איזה סוג של עקרון המקומיות (locality of access) אנחנו רואים בתרחיש 2? הסבירו. א. Spatial locality. ב. Temporal locality. ג. לא מתקיים עקרון המקומיות (There is no locality at all) ד. לא ניתן לדעת ה. אף תשובה לא נכונה
libc syscall wrapper caching pitfallsVirtual-to-physical address translationSRT / preemptive Gantt constructionבאיזה סוג של אמצעי סנכרון צריך להשתמש, אם רוצים להבטיח שבכל תא במערך יכתב באופן תקני מספר מזהה של החוט מחובר עם מונה רץ? איך זה ישפיע על ביצועים? א. לא צריך אמצעי סנכרון ב. מספיק מנעול אחד ג. צריך מספר מנעולים ד. צריך אמצעי סנכרון אחר ממנעול (הסבר מטה) ה. אף תשובה לא נכונה
Pipe IPC semanticsMutex correctness and deadlock avoidanceמהו מספר הגבוה ביותר של כניסות TLB (בכל הליבות יחד) שיכילו תרגום תכף (valid) לאחר סיום ריצה של תרחיש 2? הסבירו. א. 1 ב. 8 ג. 64 ד. לא ניתן לדעת ה. אף תשובה לא נכונה
Virtual-to-physical address translation
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
יצירת חוט חדשפרמטרים: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
טבלת הדפים (page table)לכל תהליך יש טבלת דפים משלו – מבנה נתונים אשר ממפה בין דפים למסגרות.ניתן לממש טבלת דפים באמצעות מבני נתונים שונים: מערך פשוט, עצים, טבלאות גיבוב (hash tables), ...עבור כל דף במרחב הזיכרון הווירטואלי של התהליך, יש כניסה בטבלת הדפים אשר מציינת:האם הדף נמצא בזיכרון ובאיזו מסגרת?האם הדף נמצא בדיסק ובאיזה מיקום?האם הדף מעולם לא הוקצה? (כלומר איננו בזיכרון ואיננו בדיסק)טבלת הדפים אחראית לתפקידים נוספים כמו הגנת גישה.למשל: טבלת הדפים מסמנת דפים לקריאה בלבד ומונעת גישות כתיבה.19מערכות הפעלה - תרגול 10
סיכום: תהליך התרגום במעבדי אינטל39the CPU searches the TLBhitmissthe CPU walks the page tablecompletedpage faultphysical addressvirtual addressthe OS serves the page faultמערכות הפעלה - תרגול 10
סיכום השיעור שעבר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.