8.5 זכרון וירטואלי בחומרה פתרון
פתרון תרגול - זכרון וירטואלי בחומרה¶
1. חישוב כתובת פיזית¶
סעיף 1:
הכתובת 0x00007F5A3B2C1D08 בבינארי (48 ביט):
נפרק (מימין):
- Offset (ביטים 11-0): 1101 0000 1000 = 0xD08 = 3336
- PT Index (ביטים 20-12): 0 1100 0001 = 0x0C1 = 193
- PD Index (ביטים 29-21): 1 1011 0010 = 0x1B2 = 434. רגע, נחשב שוב ביתר דיוק.
נעבוד עם חישוב ישיר:
כתובת = 0x00007F5A3B2C1D08
- Offset = bits 11-0 =
0xD08= 3336 - PT Index = bits 20-12 = (0x7F5A3B2C1D08 >> 12) & 0x1FF = (0x7F5A3B2C1) & 0x1FF
0x7F5A3B2C1 & 0x1FF = 0x2C1 & 0x1FF = 0x0C1 = 193
- PD Index = bits 29-21 = (0x7F5A3B2C1D08 >> 21) & 0x1FF
0x7F5A3B2C1D08 >> 21 = 0x3FAD1D96
0x3FAD1D96 & 0x1FF = 0x196 = 406
- PDPT Index = bits 38-30 = (0x7F5A3B2C1D08 >> 30) & 0x1FF
0x7F5A3B2C1D08 >> 30 = 0x1FEB4
0x1FEB4 & 0x1FF = 0x0B4 = 180
- PML4 Index = bits 47-39 = (0x7F5A3B2C1D08 >> 39) & 0x1FF
0x7F5A3B2C1D08 >> 39 = 0xFE
0xFE & 0x1FF = 0xFE = 254
סיכום:
| חלק | ערך הקסדצימלי | ערך עשרוני |
|---|---|---|
| PML4 Index | 0xFE | 254 |
| PDPT Index | 0x0B4 | 180 |
| PD Index | 0x196 | 406 |
| PT Index | 0x0C1 | 193 |
| Offset | 0xD08 | 3336 |
סעיף 2:
מסגרת פיזית: 0x00000001234AB
כתובת פיזית = (page frame << 12) + offset = 0x00000001234AB000 + 0xD08 = 0x00000001234ABD08
(הpage frame number מייצג את הדף, מכפילים ב-4096 = shift left 12, ומוסיפים offset)
סעיף 3:
עם דף ענק (2MB):
- הoffset גדל ל-21 ביט (bits 20-0) = 2MB
- אין שלב PT - הPD מצביע ישירות על הדף
- הoffset יהיה: bits 20-0 של הכתובת = 0x0C1D08 = 794888 (793KB בתוך הדף)
- רק 3 רמות: PML4 -> PDPT -> PD -> דף 2MB
2. התנהגות TLB¶
TLB עם 4 כניסות, fully associative, LRU.
כתובות ודפים:
- 0x1000, 0x1004 -> VPN = 1 (0x1000 / 0x1000)
- 0x2000 -> VPN = 2
- 0x3000 -> VPN = 3
- 0x1008 -> VPN = 1
- 0x4000 -> VPN = 4
- 0x5000 -> VPN = 5
- 0x1000 -> VPN = 1
- 0x2000 -> VPN = 2
| גישה | כתובת | VPN | Hit/Miss | TLB (LRU: שמאל=ישן) |
|---|---|---|---|---|
| 1 | 0x1000 | 1 | Miss | [1] |
| 2 | 0x1004 | 1 | Hit | [1] |
| 3 | 0x2000 | 2 | Miss | [1, 2] |
| 4 | 0x3000 | 3 | Miss | [1, 2, 3] |
| 5 | 0x1008 | 1 | Hit | [2, 3, 1] (1 הפך לחדש) |
| 6 | 0x4000 | 4 | Miss | [2, 3, 1, 4] (TLB מלא) |
| 7 | 0x5000 | 5 | Miss | [3, 1, 4, 5] (2 נדחק - LRU) |
| 8 | 0x1000 | 1 | Hit | [3, 4, 5, 1] |
| 9 | 0x2000 | 2 | Miss | [4, 5, 1, 2] (3 נדחק) |
סה"כ: 3 hits, 6 misses.
סעיף 3:
6 misses = 6 page table walks. כל walk = 4 גישות לזכרון. סה"כ: 24 גישות נוספות רק לתרגום כתובות.
סעיף 4: עם huge pages (2MB = 0x200000):
כל הכתובות (0x1000 עד 0x5000) נמצאות בתוך דף ענק אחד (0x0 עד 0x1FFFFF). כולן ממופות ל-VPN=0 (huge page VPN).
| גישה | כתובת | Huge VPN | Hit/Miss |
|---|---|---|---|
| 1 | 0x1000 | 0 | Miss |
| 2 | 0x1004 | 0 | Hit |
| 3-9 | ... | 0 | Hit (הכל על אותו דף!) |
סה"כ: 1 miss, 8 hits! במקום 6 misses. שיפור משמעותי.
3. תקורת טבלאות דפים¶
1GB = 1,073,741,824 בתים.
סעיף 1: דפים של 4KB = 1GB / 4KB = 262,144 דפים
סעיף 2: כל PT מכיל 512 כניסות (ממפה 512 x 4KB = 2MB).
- צריך 262,144 / 512 = 512 טבלאות PT
- סה"כ כניסות PT: 262,144
סעיף 3: כל PD מכיל 512 כניסות (ממפה 512 x 2MB = 1GB).
- צריך 512 / 512 = 1 טבלת PD
- סה"כ כניסות PD: 512
סעיף 4: PDPT: 1 כניסה (שמצביעה על הPD)
סעיף 5: PML4: 1 כניסה (שמצביעה על הPDPT)
סעיף 6: זכרון לטבלאות:
- PML4: 1 טבלה x 4KB = 4KB
- PDPT: 1 טבלה x 4KB = 4KB
- PD: 1 טבלה x 4KB = 4KB
- PT: 512 טבלאות x 4KB = 2,048 KB = 2MB
סה"כ: 4 + 4 + 4 + 2048 = 2,060 KB = כ-2MB
אחוז מ-1GB: 2MB / 1024MB = 0.2% (תקורה קטנה)
סעיף 7: עם דפים ענקיים של 2MB:
- דפים: 1GB / 2MB = 512 דפים
- אין צורך ב-PT כלל! PD מצביע ישירות על דפים ענקיים.
- PML4: 1 טבלה x 4KB = 4KB
- PDPT: 1 טבלה x 4KB = 4KB
- PD: 1 טבלה x 4KB = 4KB (512 כניסות, כל אחת לדף 2MB)
סה"כ: 12 KB (במקום 2MB) - חיסכון של פי 170!
4. השוואת דפים רגילים מול ענקיים¶
סעיף 1:
סריקה עם stride 4096 (גודל דף) גורמת ל-TLB miss על כל גישה כי כל גישה נוגעת בדף חדש. עם 1GB / 4096 = 262,144 גישות, ו-TLB שמחזיק רק 64-2048 כניסות, יש מאות אלפי TLB misses.
סריקה עם stride 64 (cache line) ניגשת ל-64 כתובות שונות באותו דף לפני שעוברת לדף הבא. כל 64 גישות, רק אחת היא TLB miss. שיעור ה-TLB misses נמוך בהרבה.
בנוסף, stride 4096 יוצר רק cache miss אחד לכל גישה (כל גישה לcache line חדש), בעוד ש-stride 64 מנצל את כל ה-cache line.
סעיף 2:
עם stride 4096: 1GB / 4KB = 262,144 TLB misses. כל miss דורש page table walk של 4 גישות = 1,048,576 גישות נוספות לזכרון (חלקן cache hits כי טבלאות הדפים עצמן cached).
סעיף 3:
עם madvise(MADV_HUGEPAGE), הקרנל מנסה להשתמש בhuge pages של 2MB. עם stride 4096, כל דף ענק מכסה 2MB = 512 גישות. TLB misses יורדים ל-1GB / 2MB = 512 (במקום 262,144). שיפור דרמטי!
סעיף 4:
בסיסי נתונים מתאימים ל-huge pages כי:
- מקצים כמויות גדולות של RAM (buffer pool/shared_buffers) - אפשר לנצל דפים ענקיים ביעילות
- הזכרון מוקצה בהפעלה ולא משתנה - אין בעיית fragmentation
- דפוסי גישה אקראיים (חיפוש ב-index, גישה לשורות שונות) - TLB misses הם bottleneck אמיתי בלי huge pages
- ה-buffer pool הוא Hot memory - הנתונים נשארים ב-RAM לאורך זמן, אז הTLB שומר עליהם