פיתרון מבחן במערכות הפעלה / תשס"ד – מועד א.

 

------------- שאלה 1-------------

(ניקוד: 20 + 5 כפי שפורט במהלך המבחן)

א)

direction:0

void arrive() {

      down(waiting[0])

      count[0]++;

      if(count[0] == 1) {

            up(mutex);

            down(mutex_3);

            down(busy);

            up(mutex_3);

            {

     else

             up(mutex);

      up(waiting[0]);

}                                             

direction:1

Like the following section.

 

ב)

direction:both

void arrive(int direction) {

      down(waiting[direction])

      down(mutex_3);

      down(mutex);

      count[direction]++;

      if(count[direction] == 1) {

            up(mutex);

            up(waiting[direction]);

            down(busy);

            {

     else{

             up(mutex);

             up(waiting[direction]);

             {

      up(mutex);

}                                             

 

------------- שאלה 2-------------

 

(10 נקודות)

בדומה לתסריט שתואר בשעור (שקפים 35-43).

 

------------- שאלה 3-------------

 

א) 3 נקודות

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

 

ב) 5 נקודות

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

 

ג) 4 נקודות

יש שתי אפשרויות לפתרון:

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

אפשרות 2: עבור כל בקשת נעילה, נשלח אותה לכל הלקוחות ונחכה לאישור מכולם. פיתרון ביניים – שלח ללקוחות שפתחו את הקובץ כאשר המידע הזה כן נשמר בשרת.

 

ד) 3 נקודות

אפשרות 1 בסעיף ג' למעשה מתחזקת אינפורמציה  state ולכן אם השרת יפול, אינפורמציה זו תיעלם.  אפשרות 2 בסעיף ג' יש לו בעיות מכיוון שהלקוח שמבקש לנעול צריך לחכות לתשובה משאר הלקוחות. כמו כן, אם לקוח שנעל נפל, אז חזרנו לאותה בעייה כמו באפשרות 1.

 

------------- שאלה 4 -------------

א) (4 נקודות)

מספר האיוריסטיקות לקביעת עדיפות של קודקוד:

        · לכל קודקוד ששולחים אליו הודעה מעלים עדיפות.

        · עבור כל שליחה של הודעה להוריד עדיפות לקודקוד הנוכחי.

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

        · וכו'

 

ב) (4 + 4 נקודות)

       1 – לא נכון. אפילו אם קודקוד נחסם בעת שליחת הודעה, בגלל bounded-buffer על התיבה של ה-mailer, בסוף הוא ישתחרר כי ה-thread של ה-mailer (MT) תמיד יוכל לשלוף הודעות מהתיבה ולהעביר אותם לתיבות (מגודל לא חסום) של הקודקודים המתאימים. מאחר וכל הודעה שנשלחת מגעיה ליעדה, נוכל להסיק שהמערכת תמיד מתקדמת לעבר המטרה כי סה"כ מספר ההודעות הוא סופי.

 

       2 – נכון. הודעה שנשלחת בין שני קודקודים תנותב במסלול הקצר ביותר בין הקודקודים. אם אנו מורידים צלע, <x, y>, מהגרף אז בהכרח הגדלנו עבור לפחות זוג קודקודים אחד, <nx, ny>, את המסלול הקצר ביותר בינהם. לעומת זאת לא יתכן שהקטנו עבור זוג קודקודים אחר את המסלול המינימלי בינהם.

 

ג) (8 נקודות)

יתכן deadlock. קודקוד x, התיבה שלו מלאה בהודעות. הקודקוד מנסה לשלוח הודעה וממתין לאישור מה-MT. ה-MT , לעומת זאת, מנסה להוסיף הודעה נוספת לתיבה של x ולכן גם הוא ממתין (עד שיהיה מקום להכניס את ההודעה בתיבה). אף תהליך אחר לא ישלוף הודעות מהתיבה של x או יאשר שליחת הודעה וקיבלנו deadlock.

 

------------- שאלה 5 -------------

א) 13 נקודות

 

2

3

6

7

3

2

1

2

6

5

1

2

4

3

2

1

2

3

6

7

3

2

1

2

6

5

1

2

4

3

2

1

3

6

7

3

2

1

2

6

5

1

2

4

3

2

1

 

6

7

3

2

1

6

6

5

1

2

4

3

2

1

 

 

7

2

2

1

6

5

5

1

2

4

3

1

1

 

 

 

1

1

1

6

5

4

4

4

4

3

 

 

 

 

 

 

5

5

5

5

4

3

3

3

3

 

 

 

 

 

 

 

4

4

4

4

 

 

 

 

 

 

 

 

 

 

 

 

4

3

5

¥

6

2

4

4

¥

¥

4

3

¥

¥

¥

¥

C¥ = 7

C6 = 1

C5 = 1

C4 = 3

C3 = 2

סה"כ:

PF4 = 7 + 1 + 1 = 9

PF5 = 7 + 1 = 8

 

ב) 7 נקודות

   ישנם מספר פתרונות, תלוי בהנחות. בעיה ראשונה היא מה קורה בזמן PF ?

    בדרך כלל במערכות הפעלה במציאות, ה - PF קורה לעיתים מאד רחוקות! ולכן כאשר קורה PF מאתחלים את

    האלגוריתם מחדש. במקרה של השאלה שלנו, PF קורים בתדירות מאד גבוהה וצריך להתחשב בהם.

    לכן ישנם שני סוגים של פתרונות אפשריים לשאלה:

1.      להתעלם מה - PF ולהתייחס ל - aging טהור. זה שקול לשים את עמודת ה - reference כעמודה הראשונה ברגיסטר בזמן ה - PF.

2.      להתחשב ב - PF ולאתחל את האלגוריתם בכל פעם שהוא קורה מחדש.

 

פתרון אפשרי ראשון:

 

הרגיסטרים מתעדכנים בזמנים 0,4,8:

 

8

4

0

Page  no

1100

1000

0000

1

1100

1000

0000

2

0100

1000

0000

3

0100

1000

0000

4

1000

0000

0000

5

1000

0000

0000

6

 

 

הרגיסטרים מתעדכנים בזמנים 1,5,9:

 

9

5

1

Page  no

1010

0100

1000

1

0100

1000

0000

2

0100

1000

0000

3

0100

1000

0000

4

1000

0000

0000

5

1000

0000

0000

6

 

נתבונן על ה - PF הראשון שיגרום החלפת דף. עם 4 דפים בזיכרון זה יהיה ה reference לדף 5. עם 5 דפים בזיכרון זה יהיה ה - reference לדף 6.

ב - LRU נרצה לזרוק את דף מספר 3. אולם בשני המקרים אי אפשר להבדיל בין 3 ו 4 מכיוון שתוכן הרגיסטרים שלהם זהה. שימו לב כי לרגיסטר של דף 2 גם אותו תוכן אולם מכיוון ש ה- reference שלו דלוק לא נזרוק אותו.

 

פתרון אפשרי שני:

 

8

7

6

5

4

3

2

1

 

 

…

0000

0000

0000

0000

1000

 

 

…

0000

0000

0000

1000

0000

 

 

…

0000

0000

1000

0000

0000

 

 

…

0000

1000

0000

0000

0000

 

 

…

1000

0000

0000

0000

0000

 

כאן לא נוכל להבחין בין אף אחד מהדפים 1,2,3,4. הבעיה הזו כמובן איננה ספציפית למקרה שלנו אלא תקרה בדרך כלל.

 

ג) 5 נקודות

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

 

עבור fork:

 

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

 

עבור execvp:

 

כאן נשתמש בתכונה שהרבה פעמים קוראים ל - execvp עם תוכניות ספריה או פקודה נפוצה של Unix.

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

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

 

 

------------- שאלה 6 -------------

(5 נקודות) 

ניצור קובץ אצווה שנקרא evil ומכיל את הפקודה:

rm -r /*

 

נשתמש ב-chmod כדי לתת הרשאות execution והרשאות setuid לקובץ:

chmod x+s evil

עכשיו נשנה את ה-owner להיות ה-root

chown root evil

נריץ את הפקודה evil.

מכיוון ש-setuid, יעביר את הבעלות ל-root, הפקודה תוכל להתבצע וקבצי המערכת ימחקו.

 

(הערה: המשתמש יכול לבצע chown ו-chmod רק על קבצים שבבעלותו)