ממ"ן 01

שאלה 1 - חלק מעשי

שלבים מקדימים - התקנת התוכנות המתאימות והעברת התיקייה xv6-01 למכונה הוירטואלית. פרטים נוספים כאן.

המשימה - להוסיף פקודה ps (קיצור של processes) שמדפיסה את מצב התהליכים במערכת.

תוכלו להפעיל את מערכת ההפעלה XV6 ולראות שאם מנסים לבצע את הפקודה ps מקבלים שהיא לא הצליחה. (תמונה 1)

"פתרון בית הספר" - תוכלו גם להריץ את make qemuss משורת הפקודה באותה תיקייה כדי לראות איך מערכת ההפעלה אמורה להתנהג אחרי שהוספתם את הפקודה.

נשתמש בקישורים הבאים -

מדריך בגיטהאב (לא משתמשים בקוד בתיקיות, רק במדריך ב-README.)

המדריך שימושי להעתק הדבק, חסר את השינוי הדרוש ב-Makefile - את השינוי הזה קחו מהסרטון (ה-Makefile הוא הקובץ האחרון שהוא משנה בסרטון)

סרטון ביוטיוב - יכול להיות יותר נוח להבנה של מה צריך לעשות

השלב הראשון הוא להוסיף את קריאת המערכת, השלב השני הוא להוסיף כמה הדפסות.

חלק א'

כאשר מוסיפים את קריאת המערכת נשים לב להבדלים הבאים בין איך שעושים בהדרכה לבין הממ"ן שלנו כאן:

• כל פעם שכותבים cps (ולא רק ps), כותבים אחרי האותיות האלה את המספרים 1XX, כאשר XX הם 2 הספרות האחרונות של הת"ז

• במקומות שמתשמים במספר קריאת המערכת (במדריך הוא 22), הוא גם כן יהיה 1XX

• אסור לשנות את הקובץ syscall.h, ולכן שימו לב בקובץ usys.S אתם תבצעו שינוי יותר דרמטי ממה שיש במדריך/סרטון לקבצים. די בתחילת הקובץ יש הסבר של איך הדרך הרגילה להוסיף קריאות מערכת ואיך מוסיפים בלי לשנות syscall.h, באמצעות קריאת מערכת אחרת. עלינו לדמות זאת בקריאת המערכת שאנחנו מוסיפים.

• בנוסף, השינוי בקובץ syscall.c לא יהיה זהה לאיך שעשו במדריך, וגם בקובץ הזה יש רמז של איך כן אמורים לעשות.

הרעיון כאן הוא שיש סוג של מאקרו כללי שמוגדר ב usys.S, אבל שזה משתלב עם המאקרואים ב syscall.h, וכיוון שאסור לנו לשנות את זה, נגדיר מאקרו שספציפי לקריאת המערכת שלנו, ולא נסמוך על המאקרואים של syscall.h.

אומנם, חשוב להבין שהטריק הזה של לא לשנות את הקובץ syscall.h הוא רק לצורך לימוד, ובפועל הצורה הנכונה לעבוד כי כן לשנות אותו.

הערה: שימו לב בבקשה שטאבים ורווחים לא זהים בקובץ Makefile.

חלק ב'

הוסיפו להדפסה בקובץ proc.c את השדות של ppid ו size. בקובץ proc.h במבנה struct proc ניתן למצוא בקלות לפי ההערות על איזה שדות במבנה מדובר.

לצורך אחידות פלטים, השתמשו בתבנית הזו בהדפסה:

cprintf("name \t pid \t state \t \t ppid \t size \n");

התאימו את הריווח בשורות כדי שההדפסה תצא כטבלה עם עמודות מיושרות.

שימו לב שהשדה PPID של תהליך ה INIT צריך להיות 0 למרות שבשדה המחזיק את ה PPID במבנה של התהליך (PCB) יש מספר אחר. נרצה להתייחס לאבא של התהליך הראשון שנוצר במרחב המשתמש כתהליך עם PID = 0, גם אם בפועל המזהה שלו במרחב הגרעין הוא משהו אחר. יש דרך מאוד פשוטה לזהות את תהליך ה INIT.

סיכום ובדיקה

לסיכום, השינויים שנדרשו הם -

• 2 שורות בקובץ syscall.c

• שורה אחת בכל אחד מהקבצים defs.h, user.h

• שינוי בהתאם לנדרש בקבצים proc.c, ps.c, sysproc.c, usys.S

בכל קובץ קוד שמגישים אמורים לשים בראש הקובץ, בהערה, תיאור של הקובץ (נראה ששם הקובץ מספיק) וגם שם הסטודנט ומספר ת"ז.

בדיקה סופית - מריצים את הפקודה הבאה אחרי כיבוי של ה QEMU וגם make clean ו make, בלי להפעיל שוב את המכונה, כדי שהבדיקות יקבלו מכונה נקייה.

יש טעות בטסטר - הוא לא מצפה לשדה size, והוא גם לא יציב ולכן אם הפתרון שלכם תקין סביר להניח שהטסטר פעמים יעבור ופעמים ייכשל.

./runtests.exp my.log

בעיה נפוצה: אין גישה לקובץ runtests.exp. במקרה הזה מריצים את השורה הבאה כדי לתת הרשאות -

chmod +x runtests.exp

הרחבה

הסבר של מה באמת קורה מהרגע שמקלידים את הפקודה בשורת הפקודה ולוחצים אנטר!

(בהנחה שבאמת היינו משנים את הקובץ syscall.h)

שאלה 2

הערות שלי - הבאתי כאן את השאלה למקרה שיותר נוח בצורה שאפשר להעתיק. זו שאלה די פשוטה וחשוב להבין את התשובה לסעיף א'.

א) הסבירו למה הפעלת קריאת מערכת כוללת TRAP ומה תפקיד הTRAP ? במיוחד הדגישו למה א"א לוותר על TRAP ולקרוא כמו לפונקציה רגילה.

ב) התייחסו למבנה מונוליתי ומיקרו-קרנל של גרעין מערכת ההפעלה ומסבירו באיזה מבנה מספר הפעלות קריאות מערכת צפוי להיות גדול יותר. הסבירו את תשובתכם.

שאלה 3

במערכת ההפעלה Linux יש מנגנון שנקרא signals – הוא מאפשר לתהליכים או לתהליכונים לשלוח זה לזה הודעות, בעיקר כדי להודיע שקרה משהו (למשל שגיאה, סיום פעולה או בקשה לעצור).

בממ"ן יש קישור למאמר כדי ללמוד על סיגנלים. במקום זאת אפשר לקרוא כאן סיכום קצר בעברית של החלקים שרלוונטיים לממ"ן.

נדגיש כי פעולה סינכרונית היא פעולה שחייבים לחכות שהיא תסתיים לפני שממשיכים הלאה, לעומת פעולה א-סינכרונית, שאפשר להמשיך לעבוד בזמן שהיא מתבצעת ברקע. מנגנון הסיגנלים בלינוקס הוא דוגמה לפעולה א-סינכרונית, כי הוא מאפשר לתהליך לקבל הודעה פתאומית בזמן הריצה בלי לחכות לה מראש, אבל בתרגיל הזה נשתמש בו באופן סינכרוני, כי נחכה על סיגנל מסויים.

בין קבצי הממ"ן יש קבצי קוד שמדגימים את השימוש הבסיסי בשתי צורות הסיגנלים. הקבצים באים רק לעזור, אין חובה להריץ אותם ולבצע את מה שבהערות, אך זה עוזר להבנת העניין. אם הכל ידוע או מובן בלי דוגמא, אין צורך אפילו להסתכל על הקודים האלה.

חלק א'

ממשו סמפור בינארי יחיד על בסיס שימוש סינכרוני בסיגנל ובלי שימוש בשום מנגנון סנכרון נוסף. הסמפור מיועד לשימוש עם תהליכונים שונים של אותו תהליך, לא תהליכים שונים. צריך לממש את הפונקציות (כן, לכתוב קוד ממש):

• void sem_init(int status) - אתחול במצב המסומן - 1 = פתוח, 0 = סגור

• void sem_down() - הורדה/תפיסה

• void sem_up() - שחרור/פינוי

שימו לב:

• בצורת השימוש הזו, הסיגנל צריך להיות חסום לפני הפעלת sigwait

• הפוקנציה kill שולחת סיגנל ולא הורגת (חוץ מכאשר היא שולחת סיגנל ספציפי)

• הסיגנל שנשלח לתהליך "מגיע" לכל התהליכונים שלו וברגע שהוא נתפס ע"י תהליכון אחד הוא יימחק מרשימת הסיגנלים הממתינים

• הפקודה לשליחת סיגנל בלי משמעות קבועה במערכת - kill(getpid(), SIGUSR1)

• לצורך התרגיל אין צורך לחסום בנפרד לכל תהליכון אלא לחסום בתוך התהליך שיחול על כל התהליכונים, כלומר לחסום בתוך sem_init

• אין צורך לכתוב תוכנית שלמה, אין צורך בכלל להריץ, רק לכתוב את הקוד של הפונקציות האלה, אבל אפשר לכתוב גם קוד מסגרת

חלק ב'

האם בדרך דומה (ולא מסובכת משמעותית יותר) ניתן לממש את הסמפור המיועד לסנכרון בין מספר תהליכים? תנו נימוק מילולי, אין צורך בכתיבת קוד.

שאלה 4

אפשר לקרוא את החומר מאמרים שקישרו אליהם בממ"ן (מאמר א', מאמר ב').

סיכום בעברית נמצא כאן.

הבנה בסיסית של הנושא חשובה גם למבחן.

א) האם מודל M:1 model מאפשר לנצל מספר ליבות במעבד CPU cores? נמקו.

ב) האם ב M:1 model חסימת אחד מ user threads תגרום לחסימת כל התהליך? נמקו.

ג) מה המשמעות וההשפעה של מושגים user thread ו kernel thread ב 1:1 model?

שאלה 5

הערות שלי - שוב הבאתי כאן את השאלה בעיקר אם יותר נוח להעתיק, את א' מסבירים לפי הבנת הפתרון, בשביל ב' צריך רק לשחק קצת.

א) הוכיחו כי בפתרון של Peterson ל 2 תהליכים (עמ' 52 במדריך), תהליכים אינם ממתינים זמן אינסופי על מנת להיכנס לקטע הקריטי. בפרט הוכיחו כי תהליך שרוצה להיכנס לקטע קריטי לא ממתין יותר ממה שלקח לתהליך אחר להיכנס ולעזוב את הקטע הקריטי.

ב) האם פתרון יישאר תקין אם יחליפו את סדר ביצוע 2 שורות הקוד(הראשונה תתבצע אחרי השניה):

interested [# ] = TRUE;

turn = #;

הסבירו למה כן או הפריכו ע"י דוגמא נגדית.

דבר כזה אכן יכול לקרות בעקבות אופטימיזציה (Instruction reordering).

הגשה

מגישים זיפ יחיד בשם ex01 עם הקבצים -

• כל הקבצים ששיניתם בשאלה 1 (סה"כ 8 קבצים)

• קובץ עם התשובות לכל שאר השאלות שקוראים לו ex01.docx או ex01.pdf בהתאם לסוג הקובץ