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

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

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

פתרון: אלגוריתם **LRU (Least Recently Used)** הסטנדרטי מהווה נקודת מוצא טובה לניהול מטמון, אך הוא אינו מביא בחשבון מאפיינים ייחודיים של מערכות קבצים. כדי לייעל את ביצועי מערכת הקבצים, יש להתאים את האלגוריתם לשתי מטרות עיקריות: מזעור פניות לדיסק ושמירה על **עקביות (consistency)** של המידע. השינויים הופכים את LRU הפשוט לאלגוריתם מורכב יותר, המותאם לדפוסי הגישה לקבצים. השינויים העיקריים הם: 1. **חיזוי גישה עתידית (Prefetching / Read-Ahead):** * **הבעיה:** LRU הוא אלגוריתם **ריאקטיבי** – הוא מביא בלוק לזיכרון רק לאחר שהתבקשה גישה אליו, מה שעלול לגרום להמתנות רבות לקריאה מהדיסק. * **התובנה:** גישה לקבצים מתבצעת לעיתים קרובות באופן **סדרתי (sequential)**. כלומר, אם תהליך קורא את בלוק מספר $N$, סביר מאוד שבקרוב הוא יבקש לקרוא את בלוק $N+1$. * **הפתרון:** יש להוסיף לאלגוריתם מנגנון **קריאה מראש (Read-Ahead)**. כאשר מתרחשת החטאה במטמון (cache miss) והמערכת קוראת את בלוק $N$ מהדיסק, היא תקרא באופן **פרואקטיבי** גם את הבלוקים הבאים ($N+1$, $N+2$, וכו') אל המטמון. בכך, כשהתהליך יבקש את הבלוקים הללו, הם כבר יהיו בזיכרון, ותיחסך פנייה יקרה לדיסק. 2. **טיפול שונה בבלוקים "מלוכלכים" (Dirty Blocks) ועקביות:** * **הבעיה:** LRU הסטנדרטי מתייחס באופן זהה לגישת קריאה ולגישת כתיבה. במערכת קבצים, יש הבדל מהותי בין בלוק שרק נקרא מהדיסק (**בלוק נקי** - clean) לבין בלוק ששונו נתוניו במטמון אך טרם נכתב חזרה לדיסק (**בלוק מלוכלך** - dirty). פינוי של בלוק נקי הוא פעולה זולה (פשוט משחררים את המקום), אך פינוי של בלוק מלוכלך דורש פעולת כתיבה יקרה לדיסק לפני שניתן לשחרר את המקום. * **הפתרון:** יש לשנות את מדיניות הפינוי כך שתיתן עדיפות לפינוי בלוקים נקיים. כאשר צריך לפנות מקום במטמון, האלגוריתם יחפש את הבלוק ה**נקי** שהשימוש האחרון בו היה הרחוק ביותר בזמן (LRU clean block). רק אם אין בלוקים נקיים פנויים, או שכולם בשימוש תדיר מאוד, האלגוריתם יבחר בלוק **מלוכלך** לפינוי. לפני הפינוי, תבוצע כתיבה שלו לדיסק (פעולה המכונה **write-back**), ולאחר מכן המקום ישוחרר. 3. **מתן עדיפות למטא-דאטה (Metadata):** * **הבעיה:** לא כל הבלוקים במערכת קבצים שווים בחשיבותם. בלוקי **מטא-דאטה**, כגון **i-nodes**, בלוקי מיפוי (bitmaps) וספריות, הם קריטיים לשלמות המבנית של מערכת הקבצים. אובדן שינויים בבלוקים אלו עלול לגרום נזק בלתי הפיך. * **הפתרון:** האלגוריתם המותאם יכול לתת עדיפות לבלוקי מטא-דאטה, למשל על ידי כתיבה מיידית שלהם לדיסק לאחר שינוי (**write-through**), בניגוד לבלוקי מידע רגילים, וכן על ידי מתן עדיפות גבוהה יותר להישארותם במטמון. $\blacksquare$