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

בחרו את הפעולה היקרה ביותר במערכת קבצים מבוססת I-Node במונחים של מעברי בלוקים של הדיסק (disk block transfers) בהנחה שלא קיימים נתונים רלוונטיים בזיכרון המטמון (buffer cache) לפני הפעולות: א. סדרת עשר קריאות של תו אחד באמצעות fgetc מקובץ קטן מאוד בגודל 10 Byte ב. קריאת בלוק אחד באמצעות read מתחילתו של קובץ גדול מאוד בגודל 1 GigaByte ג. קריאת בלוק מספר שלושים באמצעות read מתוך קובץ גדול מאוד בגודל 1 GigaByte ששמור ברצף בגישה אקראית (ישירה) ד. קריאת בלוק מספר שלושים באמצעות read מתוך קובץ גדול מאוד בגודל 1 GigaByte ששמור לא ברצף בגישה אקראית (ישירה)

רמז: חשבו כיצד מערכת הקבצים מאתרת בלוק נתונים ספציפי (כמו בלוק 0 לעומת בלוק 30) באמצעות מבנה המצביעים הישירים והעקיפים ב-i-node.

פתרון: השאלה מבקשת לזהות את הפעולה היקרה ביותר במונחים של **מעברי בלוקים מהדיסק**, בהנחה שהמטמון ריק. העלות נמדדת במספר הבלוקים השונים שיש לקרוא מהדיסק כדי להשלים את הפעולה. במערכת קבצים מבוססת **i-node**, כל קובץ מקושר ל-i-node המכיל מטא-דאטה על הקובץ, כולל מצביעים לבלוקי הנתונים שלו. מבנה ה-i-node הטיפוסי כולל: 1. מספר מצביעים ישירים (למשל, 12) המצביעים ישירות לבלוקי הנתונים הראשונים של הקובץ. 2. מצביע עקיף יחיד (single indirect) המצביע לבלוק שמכיל רשימת מצביעים לבלוקי נתונים נוספים. 3. מצביע עקיף כפול (double indirect) ומצביע עקיף משולש (triple indirect) עבור קבצים גדולים מאוד. כעת ננתח את העלות של כל פעולה: **א. סדרת עשר קריאות של תו אחד מקובץ קטן (10 Byte):** הקובץ קטן מאוד ויכנס כולו לבלוק נתונים אחד. קריאת `fgetc` הראשונה תגרום לקריאת מערכת `read` שתביא בלוק שלם לחוצץ (buffer) בספריית ה-C. הקריאות הבאות יסופקו מחוצץ זה. הגישה לדיסק תכלול: 1. קריאת ה-**i-node** של הקובץ (1 העברת בלוק). 2. שימוש במצביע ישיר הראשון ב-i-node כדי לקרוא את בלוק הנתונים (1 העברת בלוק). סה"כ: **2 העברות בלוקים**. **ב. קריאת בלוק אחד מתחילתו של קובץ גדול (1GB):** אנו קוראים את הבלוק הלוגי הראשון (בלוק מספר 0) של הקובץ. בלוק זה תמיד יאותר על ידי **מצביע ישיר** ב-i-node. הגישה לדיסק תכלול: 1. קריאת ה-**i-node** של הקובץ (1 העברת בלוק). 2. קריאת בלוק הנתונים הראשון באמצעות המצביע הישיר (1 העברת בלוק). סה"כ: **2 העברות בלוקים**. **ד. קריאת בלוק מספר שלושים מקובץ גדול, שאינו רציף:** זהו המקרה הסטנדרטי במערכת i-node. בלוק לוגי מספר 30 נמצא מעבר לטווח הטיפוסי של המצביעים הישירים (שבדרך כלל מכסים כ-12 בלוקים ראשונים). לכן, כדי לגשת אליו, מערכת ההפעלה צריכה להשתמש ב**מצביע העקיף היחיד**. הגישה לדיסק תכלול: 1. קריאת ה-**i-node** של הקובץ (1 העברת בלוק). 2. מה-i-node, קבלת הכתובת של בלוק המצביעים העקיף וקריאת בלוק זה מהדיסק (1 העברת בלוק). 3. מתוך בלוק המצביעים העקיף, איתור המצביע לבלוק הנתונים מספר 30 וקריאת בלוק הנתונים עצמו (1 העברת בלוק). סה"כ: **3 העברות בלוקים**. **ג. קריאת בלוק מספר שלושים מקובץ גדול, השמור ברצף:** העובדה שהקובץ שמור פיזית ברצף אינה משנה את הלוגיקה של מעקב המצביעים במערכת i-node קלאסית. עדיין נדרש לעבור דרך המצביע העקיף כדי למצוא את כתובת הבלוק, ולכן גם כאן העלות תהיה 3 העברות בלוקים. עם זאת, אופציה ד' מתארת את המקרה הכללי והנפוץ יותר של פיזור בלוקים, המחייב את מנגנון ההפניה העקיפה במלואו. **סיכום:** - פעולות א' ו-ב' דורשות 2 העברות בלוקים כל אחת, מכיוון שהן משתמשות במצביעים ישירים. - פעולה ד' דורשת 3 העברות בלוקים, מכיוון שהיא מחייבת מעבר דרך בלוק מצביעים עקיף. זוהי הפעולה היקרה ביותר. התשובה הנכונה היא ד'. $\blacksquare$