theoretical questions from HWs

Question 1

שאלה 1:
תהי P קבוצת כל ה-pid-ים של התהליכים הפעילים ברגע נתון (לינוקס). נגדיר G = (P, E) כך ש־(p1, p2) ∈ E אם ההורה האמיתי (real parent) של תהליך עם pid p2 הוא התהליך עם pid p1. קבעו את נכונות הטענה הבאה:

(א) האם G בהכרח DAG?

Answer 1

נניח בשלילה שיש בו מעגל, במקרה זה לפי הגדרת הגרף יהיה בן שהוא הורה קודם להורה האמיתי שלו, וזו סתירה

Question 2

: שאלה 1
תהי P קבוצת כל ה-pid-ים של התהליכים הפעילים ברגע נתון (לינוקס). נגדיר G = (P, E) כך ש־(p1, p2) ∈ E אם ההורה האמיתי (real parent) של תהליך עם pid p2 הוא התהליך עם pid p1. קבעו את נכונות הטענה הבאה:

(ב) האם G (אם מתעלמים מכיווני הקשתות) בהכרח עץ?

Answer 2

הטענה לא נכונה

הגרף לא בהכרח קשיר, ייתכן שתהליך אב ימות לפני הבנים שלו, ובמקרה זה
init תהפוך להורה של תהליך הבן
אבל לא real parent
ולכן כך הגרף יהפוך ללא קשיר

Question 3

שאלה 1:
תהי P קבוצת כל ה-pid-ים של התהליכים הפעילים ברגע נתון (לינוקס). נגדיר G = (P, E) כך ש־(p1, p2) ∈ E אם ההורה האמיתי (real parent) של תהליך עם pid p2 הוא התהליך עם pid p1. קבעו את נכונות הטענה הבאה:

(ג) האם G (אם מתעלמים מכיווני הקשתות) בהכרח יער?

Answer 3

הטענה נכונה

יהי G הגרף שלנו
יהי מעגל לא מכוון, אי אפשר לכוון את הקשתות בדרך שגם שומרת שהגרף הוא DAG
וגם לשמור על כך שדרגת הכניסה של כל צומת בגרף המכוון תהיה לכל היותר 1 (כי לכל תהליך יש real parent אחד)
לכן לא ניתן לעבור מאף גרף לא מכוון שיש בו מעגל (לא מכוון) לגרף G שעונה על הגדרות השאלה

Question 4

שאלה1:
תהי P קבוצת כל ה-pid-ים של התהליכים הפעילים ברגע נתון (לינוקס). נגדיר G = (P, E) כך ש־(p1, p2) ∈ E אם ההורה האמיתי (real parent) של תהליך עם pid p2 הוא התהליך עם pid p1. קבעו את נכונות הטענה הבאה:
(ד) האם BFS מהקודקוד 0 בהכרח יבקר בכל הקודקודים?

Answer 4

הטענה לא נכונה

במקרה שבו אב מסיים לפני הבן שלו p
נקבל שהאב הוצא מהעץ
ואין קשת שנכנסת לp
ולכן BFS מקודקוד 0 לא תגיע לp

Question 5

שאלה 2:
יהי x משתנה גלובלי שערכו 0, ויהיו p1, p2 שני תהליכים (בלינוקס) שמריצים את הפקודה printf(“%d”, x) בו זמנית. קבעו את נכונות הטענה הבאה:

(א) האם ה-pid של שני התהליכים בהכרח זהה?

Answer 5

הטענה אינה נכונה
מכיוון שהתהליכים רצים בו זמנית, אז הם חיים באותו זמן אז בהכרח יש להם pid שונה - לכל תהליך pid יחודי (אלא אם תהליך מת לפני שהשני נולד - לא מקרה שלנו)

Question 6

: שאלה 2
יהי x משתנה גלובלי שערכו 0, ויהיו p1, p2 שני תהליכים (בלינוקס) שמריצים את הפקודה printf(“%d”, x) בו זמנית. קבעו את נכונות הטענה הבאה:

(ב) האם ה-pid של שני התהליכים בהכרח שונה?

Answer 6

הטענה נכונה
מכיוון שהתהליכים רצים בו זמנית, אז הם חיים באותו זמן אז בהכרח יש להם pid שונה - לכל תהליך pid יחודי (אלא אם תהליך מת לפני שהשני נולד - לא מקרה שלנו)

אותו נימוק של הסעיף הקודם

Question 7

: שאלה 2
יהי x משתנה גלובלי שערכו 0, ויהיו p1, p2 שני תהליכים (בלינוקס) שמריצים את הפקודה printf(“%d”, x) בו זמנית. קבעו את נכונות הטענה הבאה:

(ג) האם הפלט של שני התהליכים בהכרח זהה?

Answer 7

הטענה אינה נכונה
לפי עקרון הווירטואליזציה, לכל תהליך יש זיכרון ווירטואלי משלו, ולכן כל תהליך ידפיס את הכתובת של x בזיכרון שלו
זו לא בהכרח אותה כתובת או כתובת שונה

Question 8

: שאלה 2
יהי x משתנה גלובלי שערכו 0, ויהיו p1, p2 שני תהליכים (בלינוקס) שמריצים את הפקודה printf(“%d”, x) בו זמנית. קבעו את נכונות הטענה הבאה:

(ד) האם הפלט של שני התהליכים בהכרח שונה?

Answer 8

הטענה נכונה
לפי עקרון הווירטואליזציה, לכל תהליך יש זיכרון ווירטואלי משלו, ולכן כל תהליך ידפיס את הכתובת של x
בזיכרון שלו
זו לא בהכרח אותה כתובת או כתובת שונה

אותו נימוק של הסעיף הקודם