שאלת מבחן במערכות הפעלה - האוניברסיטה הפתוחה 2017 - זיכרון

במערכת הפעלה כלשהי קיים מנגנון לניהול זיכרון המקצה לכל דף מזהה מספרי $i$. מדיניות הדפדוף הממומשת ע"י המנגנון לניהול הזיכרון היא המדיניות הבאה: אם נרצה להביא לזיכרון דף מספר $i$, והזיכרון מלא, נפנה מהזיכרון דף $j$ כך ש- $|j-i|$ הינו מקסימאלי. אם יש שני דפים כאלה נבחר אחד באקראי. בשאלות זו נניח שגודל הזיכרון הפיזי הוא 3 מסגרות (אלא אם מצוין אחרת). א. (5 נק') עבור סדרת הגישות הבאה, רשמו את תוכן הזיכרון. כמה Page Faults מתבצעים במהלך הריצה? (המספרים מציינים את מזהי הדפים). הניחו שהזיכרון היה ריק בתחילת הריצה. (משמאל לימין) 1 2 3 4 1 4 3 2 1 4 | t | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |---|---|---|---|---|---|---|---|---|---|---| | frame 1 | | | | | | | | | | | | frame 2 | | | | | | | | | | | | frame 3 | | | | | | | | | | | סה"כ page faults : ___ ב. (5 נק') תנו דוגמא לסדרת גישות בה אלגוריתם LRU טוב יותר ממדיניותה של המערכת. ג. (5 נק') השוו בין כמות המסגרות אותה יש לבדוק כדי למצוא דף לפינוי מהזיכרון, לפי האלגוריתם LRU ולפי מדיניותה של המערכת.

רמז: לסעיף א', עקבו אחר תוכן הזיכרון בכל שלב וחפשו את הדף $j$ הממקסם את $|j-i|$. לסעיף ב', בנו סדרת גישות המדגישה לוקליות זמנית, שבה LRU מצטיין. לסעיף ג', השוו את מספר הפעולות הנדרש בכל אלגוריתם כדי למצוא את הדף המועמד לפינוי.

פתרון: ### א. נעקוב אחר מצב הזיכרון בכל צעד. **Page Fault** (תקלת דף) מתרחש כאשר דף אינו בזיכרון. **החלפת דפים** מתרחשת כאשר מתרחש Page Fault והזיכרון מלא. הדף המפונה הוא $j$ עבורו $|j-i|$ מקסימלי, כאשר $i$ הוא הדף הנכנס. **מעקב אחר סדרת הגישות:** 1. **גישה ל-1:** זיכרון ריק. טעינת 1. זיכרון: {1}. (Page Fault) 2. **גישה ל-2:** זיכרון לא מלא. טעינת 2. זיכרון: {1, 2}. (Page Fault) 3. **גישה ל-3:** זיכרון לא מלא. טעינת 3. זיכרון: {1, 2, 3}. (Page Fault) 4. **גישה ל-4:** זיכרון מלא. דף נכנס $i=4$. נחשב הפרשים: $|1-4|=3, |2-4|=2, |3-4|=1$. הערך המקסימלי הוא 3, ולכן נפנה את דף 1. זיכרון: {2, 3, 4}. (Page Fault) 5. **גישה ל-1:** זיכרון מלא. דף נכנס $i=1$. נחשב הפרשים: $|2-1|=1, |3-1|=2, |4-1|=3$. הערך המקסימלי הוא 3, ולכן נפנה את דף 4. זיכרון: {1, 2, 3}. (Page Fault) 6. **גישה ל-4:** זיכרון מלא. דף נכנס $i=4$. כמו בצעד 4, נפנה את דף 1. זיכרון: {2, 3, 4}. (Page Fault) 7. **גישה ל-3:** הדף נמצא בזיכרון. (Hit) 8. **גישה ל-2:** הדף נמצא בזיכרון. (Hit) 9. **גישה ל-1:** זיכרון מלא. דף נכנס $i=1$. כמו בצעד 5, נפנה את דף 4. זיכרון: {1, 2, 3}. (Page Fault) 10. **גישה ל-4:** זיכרון מלא. דף נכנס $i=4$. כמו בצעד 4, נפנה את דף 1. זיכרון: {2, 3, 4}. (Page Fault) **טבלת תוכן הזיכרון:** | t | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |---|---|---|---|---|---|---|---|---|---|---| | frame 1 | 1 | 1 | 1 | 4 | 2 | 4 | 4 | 4 | 2 | 4 | | frame 2 | - | 2 | 2 | 2 | 3 | 2 | 2 | 2 | 3 | 2 | | frame 3 | - | - | 3 | 3 | 1 | 3 | 3 | 3 | 1 | 3 | **סה"כ page faults : 8** ### ב. אלגוריתם **LRU (Least Recently Used)** מפנה את הדף שלא נעשתה אליו גישה במשך הזמן הארוך ביותר. הוא מנצל **לוקליות זמנית (temporal locality)**. המדיניות הנתונה מתעלמת מהיסטוריית הגישות, ולכן תתפקד גרוע בסדרות גישה המציגות לוקליות כזו. נבחר סדרה שבה יש גישה לסירוגין לשתי קבוצות דפים שמספריהן רחוקים, למשל: `1, 2, 3, 100, 1, 100`. **ניתוח לפי המדיניות הנתונה:** 1. `1`: {1} (PF) 2. `2`: {1, 2} (PF) 3. `3`: {1, 2, 3} (PF) 4. `100`: מפנה את 1 ($|1-100|=99$ מקסימלי). זיכרון: {2, 3, 100}. (PF) 5. `1`: מפנה את 100 ($|100-1|=99$ מקסימלי). זיכרון: {1, 2, 3}. (PF) 6. `100`: מפנה את 1. זיכרון: {2, 3, 100}. (PF) סה"כ **6 Page Faults**. כל גישה לדף מחוץ לקבוצה {2,3} גורמת לתקלת דף. **ניתוח לפי LRU:** 1. `1`: {1} (PF) 2. `2`: {1, 2} (PF) 3. `3`: {1, 2, 3} (PF). סדר שימוש: 3 (חדש), 2, 1 (ישן). 4. `100`: מפנה את 1 (ה-LRU). זיכרון: {2, 3, 100}. (PF). סדר שימוש: 100, 3, 2. 5. `1`: מפנה את 2 (ה-LRU). זיכרון: {1, 3, 100}. (PF). סדר שימוש: 1, 100, 3. 6. `100`: הדף בזיכרון. (Hit). סדר שימוש: 100, 1, 3. סה"כ **5 Page Faults**. האלגוריתם מתייצב ומזהה את קבוצת העבודה {1, 3, 100}. מאחר ש- $5 < 6$, אלגוריתם LRU טוב יותר עבור סדרה זו. $\blacksquare$ ### ג. נשווה את הסיבוכיות של מציאת דף לפינוי עבור כל אלגוריתם, כאשר בזיכרון יש $N$ מסגרות. **אלגוריתם LRU:** במימוש יעיל, **מערכת ההפעלה** מתחזקת רשימה מקושרת כפולה של הדפים שבזיכרון. הדף שנעשתה אליו גישה לאחרונה נמצא בראש הרשימה, והדף שלא נעשתה אליו גישה במשך הזמן הרב ביותר (LRU) נמצא בזנב. כאשר יש צורך לפנות דף, פשוט בוחרים את הדף שבזנב הרשימה. פעולת איתור הקורבן היא בזמן קבוע, $O(1)$. **המדיניות הנתונה:** כאשר מתרחש **Page Fault** ויש צורך לפנות דף, יש לבצע את הפעולות הבאות: 1. לעבור על כל $N$ הדפים הנוכחיים בזיכרון. 2. עבור כל דף $j$ בזיכרון, לחשב את הערך $|j-i|$, כאשר $i$ הוא מזהה הדף הנכנס. 3. למצוא את הדף $j$ שעבורו הערך הנ"ל הוא מקסימלי. תהליך זה דורש סריקה מלאה של כל המסגרות בזיכרון, ולכן הסיבוכיות שלו היא לינארית בגודל הזיכרון, $O(N)$. **השוואה:** אלגוריתם LRU (במימוש יעיל) מהיר יותר משמעותית במציאת הדף לפינוי ($O(1)$) מאשר המדיניות הנתונה ($O(N)$).