לדלג לתוכן

6.4 ניהול זכרון הרצאה

הקדמה

בפרק 2 למדנו על paging וזכרון וירטואלי ברמה הרעיונית - מה זה page table, איך כתובת וירטואלית מתורגמת לכתובת פיזית, ומדוע כל תהליך חושב שהוא לבד בעולם. בפרק 5 השתמשנו ב-mmap כדי למפות זכרון ולעבוד עם קבצים ממופים, ולמדנו על fork ותהליכים.

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

ניהול זכרון פיזי

הדף - page

היחידה הבסיסית ביותר בניהול זכרון של לינוקס היא הדף (page). בארכיטקטורת x86 גודל הדף הוא 4KB (4096 בתים). כל הזכרון הפיזי מחולק לדפים, וכל ההקצאות, השחרורים, והמיפויים עובדים ביחידות של דפים.

זה לא במקרה - ה-MMU (יחידת ניהול הזכרון בחומרה) עובד עם דפים. ה-page tables שלמדנו עליהם בפרק 2 ממפים דפים וירטואליים לדפים פיזיים. אז טבעי שגם הקרנל ינהל את הזכרון בגרנולריות של דפים.

struct page - הייצוג של דף פיזי בקרנל

לכל דף פיזי במערכת יש מבנה נתונים שמייצג אותו בקרנל - הstruct שנקרא struct page. אם למחשב יש 8GB של RAM, יש בערך 2 מיליון דפים, ולכן יש 2 מיליון מופעים של struct page במערך גלובלי.

הנה הstruct (מפושט):

struct page {
    unsigned long flags;        // דגלים: dirty, locked, active, slab...
    atomic_t _refcount;         // מונה הפניות - כמה משתמשים מחזיקים את הדף
    struct address_space *mapping;  // אם הדף שייך לקובץ - מצביע לקובץ
    pgoff_t index;              // אם הדף שייך לקובץ - ההיסט בקובץ
    struct list_head lru;       // רשימת LRU לצורך החלפת דפים
    // ... ועוד שדות רבים
};

כמה שדות חשובים:

  • flags - דגלים שמתארים את מצב הדף. האם הוא dirty (שונה ולא נכתב חזרה לדיסק)? האם הוא נעול? האם הוא ב-slab cache? יש עשרות דגלים אפשריים.
  • _refcount - מונה הפניות. כל עוד מישהו משתמש בדף, המונה גדול מאפס. כשהמונה מגיע לאפס, אפשר לשחרר את הדף.
  • mapping - אם הדף הוא חלק מקובץ (file-backed page), השדה הזה מצביע על הקובץ שהדף שייך אליו.
  • index - ההיסט של הדף בתוך הקובץ.

המקצה החבר - buddy allocator

הקרנל צריך דרך יעילה להקצות ולשחרר דפים פיזיים. הפתרון של לינוקס הוא ה-buddy allocator (מקצה החבר).

הרעיון פשוט ואלגנטי: המקצה מנהל רשימות חופשיות (free lists) של בלוקים בגדלים שהם חזקות של 2. יש רשימה של בלוקים בגודל 1 דף, רשימה של בלוקים בגודל 2 דפים, רשימה של 4 דפים, 8, 16, 32, וכן הלאה עד 1024 דפים (4MB בx86).

כשהקרנל צריך להקצות, למשל, דף אחד:

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

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

אפשר לראות את מצב ה-buddy allocator בכל רגע נתון:

cat /proc/buddyinfo

הפלט נראה משהו כזה:

Node 0, zone   Normal   1234   567   234   89   34   12   5   2   1   0   0

המספרים מייצגים כמה בלוקים חופשיים יש בכל גודל (מ-1 דף בצד שמאל עד 1024 דפים בצד ימין).

אזורי זכרון - memory zones

לא כל הזכרון הפיזי שווה. חלק מהחומרה יכול לגשת רק לחלקים מסוימים של הזכרון (למשל, התקני DMA ישנים יכולים לגשת רק ל-16MB הראשונים). לכן לינוקס מחלק את הזכרון הפיזי לאזורים (zones):

  • ZONE_DMA - 16MB הראשונים. שמור להתקני ISA DMA ישנים שיכולים לגשת רק לכתובות נמוכות.
  • ZONE_DMA32 - עד 4GB. להתקנים שיכולים לגשת לכתובות של 32 ביט אבל לא מעבר.
  • ZONE_NORMAL - הזכרון ה"רגיל". בארכיטקטורת 64 ביט, זה כל הזכרון מעל 4GB (ומתחת לגבול של ZONE_DMA32).
  • ZONE_HIGHMEM - קיים רק במערכות 32 ביט. בקרנל 32 ביט, הקרנל יכול לגשת ישירות רק ל-896MB הראשונים (כי הוא תופס 1GB מתוך 4GB של מרחב כתובות וירטואלי). זכרון מעל 896MB נמצא ב-ZONE_HIGHMEM וצריך מיפוי מיוחד כדי לגשת אליו. במערכות 64 ביט אין צורך בזה.

כל zone מנהל buddy allocator משלו.

ניהול זכרון וירטואלי

mm_struct - מתאר הזכרון של תהליך

כל תהליך בלינוקס מקבל מרחב כתובות וירטואלי משלו. המבנה שמנהל את הזכרון הוירטואלי של תהליך הוא struct mm_struct. הוא נמצא בתוך ה-task_struct שלמדנו עליו ב-6.3 (מתזמן התהליכים).

struct mm_struct {
    pgd_t *pgd;                // מצביע לטבלת הדפים ברמה העליונה
    atomic_t mm_users;         // כמה תהליכים חולקים את ה-mm הזה
    atomic_t mm_count;         // מונה הפניות
    struct maple_tree mm_mt;   // עץ maple שמכיל את כל ה-VMAs
    unsigned long total_vm;    // סך כל הדפים הוירטואליים
    unsigned long locked_vm;   // דפים נעולים (לא ניתנים ל-swap)
    unsigned long start_code, end_code;    // אזור הקוד
    unsigned long start_data, end_data;    // אזור הנתונים
    unsigned long start_brk, brk;          // אזור ה-heap
    unsigned long start_stack;             // תחילת המחסנית
    // ... ועוד שדות
};

השדה הכי חשוב כאן הוא pgd - המצביע לטבלת הדפים ברמה העליונה. זוכרים מפרק 2 את מבנה העץ של page tables? ה-pgd הוא השורש של העץ הזה. כשהמתזמן עובר מתהליך לתהליך (context switch), הוא טוען את ה-pgd של התהליך החדש לתוך הרגיסטר CR3, וככה ה-MMU יודע לתרגם כתובות לפי טבלת הדפים של התהליך הנוכחי.

VMA - vm_area_struct

בתוך מרחב הכתובות של תהליך, לא כל כתובת תקפה. הזכרון הוירטואלי מורכב מאזורים רציפים, וכל אזור כזה מיוצג על ידי struct שנקרא vm_area_struct (בקיצור VMA).

כל שורה ב-/proc/[pid]/maps מתאימה ל-VMA אחד. למשל:

00400000-0040b000 r-xp 00000000 08:01 131074  /usr/bin/cat
00600000-00601000 rw-p 0000b000 08:01 131074  /usr/bin/cat
7f1234560000-7f1234720000 r-xp 00000000 08:01 262150  /lib/x86_64-linux-gnu/libc-2.27.so
7ffc12340000-7ffc12361000 rw-p 00000000 00:00 0       [stack]

הנה ה-struct (מפושט):

struct vm_area_struct {
    unsigned long vm_start;         // כתובת התחלה
    unsigned long vm_end;           // כתובת סיום (לא כולל)
    vm_flags_t vm_flags;            // דגלי הרשאות: VM_READ, VM_WRITE, VM_EXEC
    struct file *vm_file;           // מצביע לקובץ (אם file-backed), או NULL
    unsigned long vm_pgoff;         // היסט בקובץ (ביחידות של דפים)
    struct mm_struct *vm_mm;        // מצביע חזרה ל-mm_struct של התהליך
    const struct vm_operations_struct *vm_ops;  // פעולות ספציפיות ל-VMA
    // ...
};

השדות החשובים:

  • vm_start, vm_end - טווח הכתובות של האזור. שימו לב ש-vm_end הוא exclusive (לא כולל).
  • vm_flags - ההרשאות. האם אפשר לקרוא (VM_READ)? לכתוב (VM_WRITE)? להריץ קוד (VM_EXEC)? האם האזור משותף (VM_SHARED)?
  • vm_file - אם האזור ממופה לקובץ (כמו ספריה דינמית או קובץ שמופה עם mmap), השדה מצביע על הקובץ. אם זה מיפוי אנונימי (heap, stack), השדה הוא NULL.
  • vm_pgoff - ההיסט בקובץ, ביחידות של דפים.

העץ של הVMA-ים

כל ה-VMAs של תהליך צריכים להיות מאורגנים במבנה נתונים שמאפשר חיפוש מהיר לפי כתובת. כשקורה page fault, הקרנל צריך למצוא את ה-VMA שמתאים לכתובת הפוגעת - ומהר.

עד גרסה 6.1 של הקרנל, ה-VMAs היו מאורגנים בעץ אדום-שחור (red-black tree). מגרסה 6.1 המבנה הוחלף לעץ maple (maple tree) - מבנה נתונים יעיל יותר שתוכנן במיוחד עבור טווחים.

בנוסף ל-tree, ה-VMAs מקושרים גם ברשימה מקושרת לפי סדר כתובות, כדי שיהיה קל לעבור על כולם לפי הסדר.

מה קורה כשקוראים ל-mmap

כשתהליך קורא ל-syscall של mmap (כפי שלמדנו בפרק 5.7), הנה מה שקורה בתוך הקרנל:

  1. הקרנל מחפש חור פנוי במרחב הכתובות הוירטואלי (כתובות שאין עליהן VMA).
  2. הוא יוצר struct vm_area_struct חדש עם הפרמטרים שנתנו (כתובת התחלה, גודל, הרשאות, קובץ).
  3. הוא מכניס את ה-VMA לעץ ה-maple ולרשימה המקושרת.
  4. הוא מחזיר את כתובת ההתחלה של ה-VMA.

שימו לב מה לא קורה: שום דף פיזי לא מוקצה! טבלת הדפים לא מתעדכנת. הדפים הוירטואליים עדיין לא ממופים לדפים פיזיים. זה הקצאה עצלנית (lazy allocation), ורק כשהתהליך באמת ניגש לאחת הכתובות האלה - אז יקרה page fault והקרנל יקצה דף פיזי.

שגיאת דף - page fault

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

הזרימה

  1. התהליך ניגש לכתובת וירטואלית - למשל, קריאה מכתובת שמופה כ-VMA אבל עדיין אין לה דף פיזי.

  2. הMMU מגלה שאין מיפוי בpage table - הוא מפעיל חריגה (exception) מסוג page fault (חריגה מספר 14 בx86, שנקראת #PF).

  3. הקרנל תופס את החריגה - הפונקציה do_page_fault רצה. היא מקבלת את הכתובת שגרמה לpage fault ואת סיבת הpage fault (קריאה/כתיבה, user/kernel).

  4. חיפוש VMA - הקרנל מחפש בעץ ה-maple את ה-VMA שמתאים לכתובת. הפונקציה find_vma מקבלת את ה-mm_struct ואת הכתובת, ומחזירה את ה-VMA.

  5. אם לא נמצא VMA - הכתובת לא תקפה. התהליך ניגש לזכרון שלא שייך לו. הקרנל שולח SIGSEGV - segmentation fault. התהליך מת.

  6. אם נמצא VMA אבל ההרשאות לא מתאימות - למשל, התהליך ניסה לכתוב לאזור שמסומן כread-only. גם כאן - SIGSEGV.

  7. אם נמצא VMA והכל תקין - הקרנל ממשיך ל-handle_mm_fault, שמקצה דף פיזי, ממלא אותו בתוכן המתאים, ומעדכן את טבלת הדפים כך שהכתובת הוירטואלית ממופה לדף הפיזי החדש.

  8. חזרה לתהליך - הפקודה שגרמה ל-page fault רצה שוב. הפעם ה-MMU מוצא את המיפוי ב-page table, ותרגום הכתובת מצליח.

סוגי page faults

לא כל ה-page faults שווים:

שגיאה קטנה - minor fault - הדף צריך רק להיות מוקצה בזכרון. לא צריך לקרוא שום דבר מהדיסק.

דוגמאות:
- גישה ראשונה לזכרון שהוקצה עם mmap אנונימי - הקרנל מקצה דף פיזי מאותחל לאפסים.
- גישה לstack שגדל - הקרנל מקצה דפים חדשים ל-stack.

שגיאה גדולה - major fault - הקרנל צריך לקרוא נתונים מהדיסק. זה הרבה יותר איטי.

דוגמאות:
- גישה לדף של קובץ ממופה (file-backed mmap) שעדיין לא נטען לזכרון - הקרנל קורא את הדף מהדיסק.
- גישה לדף שהועבר ל-swap (החלפה) - הקרנל קורא אותו חזרה מ-swap.

הקצאה לפי דרישה - demand paging

מנגנון ה-page faults מאפשר את מה שנקרא demand paging - דפים מוקצים רק כשמישהו ניגש אליהם.

נזכר בדוגמה מפרק 5.7: כשקוראים ל-mmap על קובץ, הקרנל לא טוען את כל הקובץ לRAM. הוא רק יוצר VMA. כשהתהליך ניגש לבית מסוים בקובץ, קורה page fault, הקרנל קורא את הדף המתאים מהדיסק, ממפה אותו, והתהליך ממשיך. אם הקובץ הוא 1GB אבל התהליך קורא רק את 10KB הראשונים - רק שלושה דפים ייטענו לזכרון.

זה גם מסביר למה הקרנל משתמש ב-mmap כדי לטעון קבצי ELF להרצה (כפי שלמדנו ב-5.7). קובץ הרצה יכול להיות גדול, אבל בהרצה רגילה רוב הקוד אף פעם לא רץ (קוד טיפול בשגיאות, פיצ'רים שלא בשימוש). עם demand paging, רק הדפים שבאמת נדרשים נטענים.

העתקה-בכתיבה - Copy-on-Write

זוכרים מפרק 5.2 את fork? כשתהליך קורא ל-fork(), נוצר תהליך בן שהוא עותק של האב. אבל להעתיק את כל הזכרון של תהליך זה יקר מאוד. אם לתהליך יש 500MB של זכרון, לא נרצה להעתיק חצי גיגה בכל fork.

הפתרון הוא Copy-on-Write (בקיצור COW), וככה זה עובד:

  1. ברגע ה-fork - הקרנל לא מעתיק שום דף פיזי. במקום זאת, הוא יוצר mm_struct חדש לתהליך הבן עם VMAs חדשים, אבל טבלאות הדפים של שני התהליכים מצביעות על אותם דפים פיזיים. כל הדפים האלה מסומנים כ-read-only בטבלת הדפים של שני התהליכים.

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

  3. כשמישהו מנסה לכתוב - קורה page fault (כי הדף מסומן read-only). הקרנל מזהה שזה COW fault:

  4. הוא מקצה דף פיזי חדש.
  5. הוא מעתיק את תוכן הדף הישן לדף החדש.
  6. הוא מעדכן את טבלת הדפים של הכותב כך שהכתובת ממופה לדף החדש, עם הרשאת כתיבה.

  7. הדף הישן נשאר ממופה לתהליך השני (ואם יש רק תהליך אחד שמשתמש בו, גם הוא מקבל חזרה הרשאת כתיבה).

  8. מנקודה זו - כל תהליך יש לו עותק פרטי של אותו דף, ושניהם יכולים לכתוב בלי להשפיע אחד על השני.

היופי במנגנון הזה הוא שהעתקה מתבצעת רק על דפים שבאמת משתנים. אם תהליך עושה fork ואז מיד קורא ל-exec (מה שקורה בכל פעם שמריצים פקודה מה-shell), כמעט אף דף לא מועתק - כי exec מחליף את כל הזכרון בתמונה חדשה.

החלפה - swapping

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

איך הקרנל מחליט מה להעביר ל-swap

הקרנל מנהל רשימות LRU (Least Recently Used) של דפים:

  • רשימה פעילה - active list - דפים שנגישו לאחרונה.
  • רשימה לא פעילה - inactive list - דפים שלא נגישו כבר זמן מה.

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

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

הדמון kswapd

הדמון kswapd רץ ברקע ודואג שתמיד יהיו כמה דפים חופשיים זמינים. הוא לא מחכה שהזכרון ייגמר לגמרי - הוא מתחיל לפעול כשמספר הדפים החופשיים יורד מתחת לסף מסוים (watermark).

הוא עובר על הרשימה הלא פעילה ומשחרר דפים:

  • דפים של קבצים ממופים שלא השתנו - הקרנל פשוט זורק אותם. הם קיימים על הדיסק ואפשר לטעון אותם מחדש אם צריך.
  • דפים dirty של קבצים ממופים - הקרנל כותב אותם חזרה לקובץ ואז זורק אותם.
  • דפים אנונימיים (heap, stack) - אלה צריכים ללכת ל-swap space, כי אין להם קובץ על הדיסק.

הרוצח OOM - OOM Killer

מה קורה כשגם הRAM מלא וגם ה-swap space מלא? המערכת במצב קריטי - אי אפשר להקצות זכרון לשום דבר.

במצב כזה, הקרנל מפעיל את ה-OOM Killer (Out Of Memory Killer). זה מנגנון שבורר תהליך ל"הריגה" כדי לשחרר את הזכרון שלו.

איך הוא בוחר את הקורבן

לכל תהליך יש oom_score שאפשר לראות:

cat /proc/[pid]/oom_score

הציון מחושב לפי כמה זכרון התהליך משתמש, כמה זמן הוא רץ, ופרמטרים נוספים. תהליכים שמשתמשים בהרבה זכרון מקבלים ציון גבוה יותר ולכן סביר יותר שייבחרו.

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

echo -1000 > /proc/[pid]/oom_score_adj  # הגנה מקסימלית (לא ייהרג)
echo 1000 > /proc/[pid]/oom_score_adj   # עדיפות גבוהה להריגה

ה-OOM Killer הוא מנגנון שנוי במחלוקת. מצד אחד, הוא מציל את המערכת מקריסה מוחלטת. מצד שני, הוא הורג תהליך שלא ביקש להיהרג - וזה יכול להיות תהליך חשוב. בשרתי production, מנהלי מערכת מגדירים oom_score_adj לתהליכים קריטיים כדי להגן עליהם.

סיכום

בפרק הזה ראינו איך הקרנל של לינוקס מנהל זכרון ברמה העמוקה:

  • זכרון פיזי - מנוהל בדפים של 4KB. כל דף מיוצג ב-struct page. ה-buddy allocator מקצה בלוקים של דפים ביעילות. הזכרון הפיזי מחולק לzones.
  • זכרון וירטואלי - לכל תהליך יש mm_struct שמנהל את מרחב הכתובות שלו. אזורים רציפים מיוצגים כ-VMAs ומאורגנים בעץ maple.
  • שגיאות דף - page faults - המנגנון המרכזי שמחבר בין זכרון וירטואלי לפיזי. מאפשר demand paging - הקצאת דפים רק כשבאמת צריך.
  • העתקה-בכתיבה - COW - מאפשר fork מהיר בלי להעתיק זכרון שלא משתנה.
  • החלפה - swapping - מעבירה דפים לא פעילים לדיסק כשנגמר הRAM.
  • OOM Killer - מוצא אחרון כשממש אין יותר זכרון.

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