08 BS Linux Speicherverwaltung PDF

BETRIEBSSYSTEME (BS) VIII. VIRTUELLE SPEICHERVERWALTUNG PROF. DR.-ING. RAINER KELLER PROF. DR. DENNIS GREWE 1 LEHREVALUATION WINTERSEMESTER 2024/2025 Bitte nehmen Sie sich die Zeit für die Beantwortung der Fragen....

BETRIEBSSYSTEME (BS) VIII. VIRTUELLE SPEICHERVERWALTUNG PROF. DR.-ING. RAINER KELLER PROF. DR. DENNIS GREWE 1 LEHREVALUATION WINTERSEMESTER 2024/2025 Bitte nehmen Sie sich die Zeit für die Beantwortung der Fragen. Ihre Meinung zählt! 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 2 QUIZ ZUR WIEDERHOLUNG: SCHEDULER https://partici.fi/54815345 [Bild von vecstock auf Freepik] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 3 AGENDA l Was ist virtueller Speicher? l Wie funktioniert die Verwaltung von virtuellem Speicher? l Wie wird virtueller Speicher auf physikalische Adressen abgebildet? l Was versteht man unter Paging? 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 4 ZIELE l Verstehen, wie Linux Speicherverwaltung betreibt l Verstehen von Begrifflichkeiten wie virtueller Speicher, Paging, etc. l Verstehen wie die Umsetzung von virtueller auf physikalische Adresse funktioniert. l HINWEIS: Machen Sie sich Notizen in den jeweiligen Grafiken 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 5 DEFINITION: THREAD l Ein Thread ist die kleines Ausführungseinheit, die vom Linux-Kernel geplant wird. Er is einer von mehreren Ausführungspfaden innerhalb eines Prozesses. l Die Threads innerhalb eines Prozesses teilen sich …: l … die globalen Variablen und offene File-Diskriptoren (FDs) -> (Dateien, Netzwerkverbindungen, etc.) l … den selben Adressraum l …. den selben Heap und dynamischen Speicher (malloc, free) l Jeder Thread innerhalb eines Prozesses hat seine(n) eigene(n): l Registersatz l Stack l Thread ID, Priority l Thread-lokale Fehlervariable errno 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Linux Scheduler 6 LINUX PROZESSKONTEXT: THREADS & TASKS l Für die im Prozesskontext verwalteten Threads gibt es drei Implementierungsmöglichkeiten 1:n Threads 1:1 Threads m:n Threads Prozesskontext Prozesskontext Prozesskontext Thread1 Thread2 Thread3 Thread1 Thread2 Thread3 Thread1 Thread2 Thread3 Thread Scheduler Thread Scheduler OS OS OS Task Task Task Task Task Task Prozess Prozess Prozess Software Software Software Hardware Hardware Hardware Frühere Java VMs Linux Solaris Segment-Fault, wenn Zugriff l Granularity (G): gibt an ob Limit-Wert von Bytes (G=0) oder 4KB (G=1) interpretiert wird (pot. größere Segmente möglich) l Operation Big (B): Legt fest, ob Segmentzugriff standardmäßig 16-Bit (B=0) oder 32-Bit (B=1) ist (Abwärtskompatibilität) 31 23 20 15 11 7 0 A Limit D Type Base 31:24 G B 0 V P P 1 Base 23:16 4 L 19:16 L 0 E W A Base Address 15:00 Segment Limit 15:00 0 31 1615 0 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung PAGES: SPEICHERSEITEN AUS SICHT DES X86-64 l Der i386/i486/Pentium war/ist ein 32-Bit Prozessor … l Seitdem AMD den 64-Bit Opteron (AMD64) eingeführt hat, sind Adressen nicht mehr 32-Bit sondern 64-Bit lang. l Ein 64-Bit physikalischer Adressraum ist (heute noch) nicht notwendig. Von den 64-Bit führt die CPU „nur“ 48-Bit Adressleitungen nach außen. l Nun wird der Seiten-Deskriptor nicht aufgebläht, sondern nur die Bits genommen, die notwendig sind. 31 23 20 15 11 7 0 A D Type G B 1 V P P 1 4 L L 0 E W A 0 31 1615 0 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung SPEICHERSCHUTZ: ABB. VIRTUELL -> PHYSIKALISCHE ADRESSE Virtueller Speicher: 0x0..00 main() Text / page0... Code Text, Code, Daten, page1 myfunc() Segment … Segmente 64-Bit Virtueller Adressraum... page2 werden in 4kB große, virtuelle Page-Segmente überführt. myvar=0 Data page3 mama=42 Ausgehend des Segment page4 „Einstiegspunktes“ der main-Funktion Allozi- HEAP page5 ierter wird das Programm Speicher Speicher page6 in Pages unterteilt. IP-RetAddr Stack page7 int i; Segment int myval; page8... page9 0xf..ff 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 21 SPEICHERSCHUTZ: ABB. VIRTUELL -> PHYSIKALISCHE ADRESSE Virtueller Speicher: Physikalischer Speicher: Mapping von virtueller à physikalische Pages 0x0..00 main() Text / page0 page4 Programm kann... Code page1 page3 genau so aus der myfunc() Segment 64-Bit Virtueller Adressraum vom Compiler... page2 page2 generierten page1 ausführbaren Datei eingelesen werden. page0 myvar=0 Data page3 mama=42 Segment page4 Allozi- HEAP page5 page6 ierter Speicher Speicher page6 page5 IP-RetAddr Stack page7 page7 int i; Segment int myval; page8 page8... page9 page9 0xf..ff 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 23 SPEICHERSCHUTZ: ABB. VIRTUELL -> PHYSIKALISCHE ADRESSE Virtueller Speicher: Physikalischer Speicher: Mapping von virtueller à physikalische Pages 0x0..00 main() Text / page0 page4... Code page1 page3 myfunc() Segment 64-Bit Virtueller Adressraum... page2 page2 page1 page0 myvar=0 Data page3 Pages können (für die mama=42 Segment page4 Anwendung transparent!) vom OS Allozi- HEAP page5 page6 verschoben werden. ierter Speicher Speicher page6 page5 So werden „Löcher“ im phys. Speicher eliminiert! (Stichwort Fragmentierung) IP-RetAddr Stack page7 page7 int i; Segment int myval; page8 page8... page9 page9 0xf..ff 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 24 SPEICHERSCHUTZ: ABB. VIRTUELL -> PHYSIKALISCHE ADRESSE Virtueller Speicher: Physikalischer Speicher: Mapping von virtueller à physikalische Pages 0x0..00 main() Text / page0 page4... Code page1 page3 myfunc() Segment 64-Bit Virtueller Adressraum... page2 page2 Die Speicher- page1 verwaltung des OS muss für jeden Prozess page0 myvar=0 page3 die Speicherbereiche Data mama=42 verwalten. Jedoch Segment page4 können Bereiche im Allozi- HEAP physikalischen page5 page6 ierter Speicher Speicher weit verteilt Speicher page6 page5 sein, sodass eine effiziente virtuelle Adressverarbeitung notwendig ist. IP-RetAddr Stack page7 page7 int i; Segment int myval; page8 page8... page9 page9 0xf..ff 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 25 VIRTUELLER SPEICHER: ADRESSUMWANDLUNG l Die Umwandlung/Übersetzung der 64-Bit virtuellen auf die 64-Bit physikalische Adresse macht der Translation Lookaside Buffer (TLB) der Memory Management Unit (MMU). Damit der Zugriff schnell erfolgt, gibt es einen Hardware Cache zur Übersetzung in der CPU -> der TLB. l Die Umwandlung erfolgt nicht direkt, sondern mithilfe von Seitentabellen (Page Tables), die vom Betriebssystem verwaltet werden. 64-Bit Addr. unused 36-Bit 12Bit Offset Für zukünftige Erweiterungen 1. Eintrag page5 Deskriptor 2. Eintrag TLB 3. Eintrag In jedem Eintrag ist der Ein TLB-Miss löst eine Deskriptor des Speicher- Exception aus und damit Page- n. Eintrag (früher: n=48; heute: n=1024!) segments gecached. Table Walk des OS! 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 28 VIRTUALISIERUNG IN LINUX SPEICHERVERWALTUNG 29 VIRTUELLE SPEICHERVERWALTUNG l Das Betriebssystem muss sehr viele Pages verwalten: l PC mit 4MB RAM (Linus‘ Studentenzeit): 1014 Pages á 4kB Page-Größe l PC mit 4GB RAM (heute normal oder größer): > 1 Mio. Pages á 4 kB Page-Größe l Das OS muss den RAM effizient verwalten, in Bezug auf: l Speicher, um möglichst wenig Speicher für die Verwaltungsdaten zu benötigen. l Zeit, um möglichst wenig Instruktionen zur Verwaltung, wenige Speicherverweise auf nicht-gecachte Daten! l Abbildung von Pages auf Auslagerungsdatei / Swap-Speicher auf der Festplatte l Berücksichtige: l Für jeden TLB-Miss muss das OS die Pages eines Prozesses durchsuchen: das nennt man Page-Table-Walk l Ist eine Page im RAM aber nicht im TLB -> Minor Fault l Ist eine Page nicht im RAM (auf Swap-Speicher / Festplatte) -> Major Fault 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 31 VIRTUELLE SPEICHERVERWALTUNG l Moderne Prozessoren, die Page-Tables verwenden, unterliegen einer hierarchischen Struktur. Dies erlaubt das Aufteilen des Adressraums in kleinere Teile, die effizienter durchsucht und verwaltet werden können. l Der Linux-Kernel arbeitet mit einer dreistufigen Baumstruktur, die wie folgt aussieht: page … … Page Global Directory (PGD) Page Middle Directory (PMD) Page Table Entries (PTE) Quelle: [Four-level page tables by Elektix, Inc.] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 32 VIRTUELLE SPEICHERVERWALTUNG: PAGE GLOBAL DIRECTORY l Auf einem 32-Bit x86 System enthält das Page Global Directory (PDG) nur vier Einträge, die jeweils 1GB virtuellem Adressraum entsprechen. Das PDG wird anhand der oberen beiden Bits der virtuellen Adresse indiziert. Jeder PDG-Eintrag verweist auf ein Page Middle Directory (PMD). page … … Page Global Directory (PGD) Page Middle Directory (PMD) Page Table Entries (PTE) Quelle: [Four-level page tables by Elektix, Inc.] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 33 VIRTUELLE SPEICHERVERWALTUNG: PAGE MIDDLE DIRECTORY l Das Page Middle Directory (PMD) enthält 1024 Einträge die durch 10-Bit der virtuellen Adresse indiziert sind. Der PMD-Eintrag, sofern er nicht leer ist, verweist auf eine tatsächliche Seitentabelle, die Page Table Entries (PTE). page … … Page Global Directory (PGD) Page Middle Directory (PMD) Page Table Entries (PTE) Quelle: [Four-level page tables by Elektix, Inc.] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 34 VIRTUELLE SPEICHERVERWALTUNG: PAGE TABLE ENTRY l Ein Eintrag in der Page Table Entry (PTE) Tabelle enthält die tatsächliche physische Adresse der 4kB Page, vorausgesetzt, dass sich die Page derzeit im RAM befindet. Die letzten 12-Bit der virtuellen Adresse zeigen auf die physische Adresse der Page page … … Page Global Directory (PGD) Page Middle Directory (PMD) Page Table Entries (PTE) Quelle: [Four-level page tables by Elektix, Inc.] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 35  PAGE TABLE WALK @32-BIT BEI 4KB PAGE-GRÖSSE Phys. Mem: page4 page3 page2 page1 page0 page6 page5 page9 page8 page7 32-Bit Adresse in 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 virtuellen Speicherraum 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 36  PAGE TABLE WALK @32-BIT BEI 4KB PAGE-GRÖSSE Phys. Mem: page4 page3 page2 page1 page0 page6 page5 page9 page8 page7 32-Bit Adresse in 10Bit Offset 10Bit Offset 12Bit Offset virtuellen Speicherraum 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 37  PAGE TABLE WALK @32-BIT BEI 4KB PAGE-GRÖSSE Phys. Mem: page4 page3 page2 page1 page0 page6 PGD page5 pgd_t 0... pgd_t 15 page9 page8 4Bit page7 32-Bit Adresse in 10Bit Offset 10Bit Offset 12Bit Offset virtuellen Speicherraum 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 38  PAGE TABLE WALK @32-BIT BEI 4KB PAGE-GRÖSSE Phys. Mem: page4 page3 page2 page1 page0 PMD pmd_t 0 page6 PGD pmd_t 1 page5 pgd_t 0 pmd_t 2...... page9 pgd_t 15 pmd_t 1023 page8 4Bit … page7 32-Bit Adresse in 10Bit Offset 10Bit Offset 12Bit Offset virtuellen Speicherraum 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 39  PAGE TABLE WALK @32-BIT BEI 4KB PAGE-GRÖSSE Phys. Mem: page4 page3 page2 page1 page0 PTE PMD pte_t 0 pmd_t 0 page6 pte_t 1 PGD pmd_t 1 pte_t 2 page5 pgd_t 0 pmd_t 2......... pte_t 1023 page9 pgd_t 15 pmd_t 1023 page8 4Bit … … page7 32-Bit Adresse in 10Bit Offset 10Bit Offset 12Bit Offset virtuellen Speicherraum 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 40  PAGE TABLE WALK @32-BIT BEI 4KB PAGE-GRÖSSE Phys. Mem: page4 page3 page2 struct page page1 {...base...} page0 PTE PMD pte_t 0 pmd_t 0 page6 pte_t 1 PGD pmd_t 1 pte_t 2 page5 pgd_t 0 pmd_t 2......... pte_t 1023 page9 pgd_t 15 pmd_t 1023 page8 4Bit … … page7 32-Bit Adresse in 10Bit Offset 10Bit Offset 12Bit Offset virtuellen Speicherraum 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 41  PAGE TABLE WALK @32-BIT BEI 4KB PAGE-GRÖSSE Phys. Mem: page4 l Die 32-Bit Adresse wird aufgespalten in einzelne Teile: als Index in je page3 4kB Pages mit Pointer auf eine Page (PMD, bzw. PTE) page2 struct page PMD Einträge repräsentieren jeweils page1 {...base_ptr...} immer eine 4kB Page, die auf bis zu page0 jeweils 1024 einzelne PTE-Seiten PTE base_ptr: verweisen. PMD Teil des HW pte_t 0 Descriptors page6 pmd_t 0 pte_t 1 12-Bit PGD pmd_t 1 pte_t 2 Offset in page5 Der Index in der PGD pgd_t 0 Die Page: pmd_t 2 Unterscheidet ob ein...... 0... 4095 Kernel PMD / User- pgd_t 15... pte_t 1023 page9 Space PMD pmd_t 1023 page8 4Bit … … page7 32-Bit Adresse in 10Bit Offset 10Bit Offset 12Bit Offset virtuellen Speicherraum 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 43  PAGE TABLE WALK @32-BIT BEI 4MB HUGE PAGE Phys. Mem: page4 l Huge Pages sind eine Optimierung in Betriebssystemen, insbesondere Linux, um den page3 Speicherzugriff effizienter zu gestalten. Für die Bildung einer Huge Page werden die letzten 10- page2 Bit Offset mit hinzugenommen -> 12+10 = 22 Bit Offset struct page page1 {...base_ptr...} l Mit 22-Bit Offset lassen sich 222 = 4.194.303 (aka 4MB) ansprechen) page0 base_ptr: PMD Teil des HW PTE Descriptors page6 pmd_t 0 22-Bit PGD pmd_t 1 pte_t 0 Offset in page5 Der Index in der PGD pgd_t 0 Die Page: pmd_t 2 pte_t 1 Unterscheidet ob ein... 0... 4095 Kernel PMD / User- pgd_t 15... pte_t 2 page9 Space PMD pmd_t 1023... page8 pte_t 1023 4Bit PMD Einträge == 4kB Page page7 32-Bit Adresse in 10Bit Offset 22Bit Offset virtuellen Speicherraum 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 45 VIRTUELLE SPEICHERVERWALTUNG: 64 BIT SYSTEM l Bei der Verwaltung eines 64-Bit Adressraums verwendet der Linux Kernel ein vierstufige Baumstruktur, die wie folgt aussieht: page … … … Page Global Directory (PGD) Page Middle Page Upper Directory (PMD) Directory (PUD) Page Table Entries (PTE) Quelle: [Four-level page tables by Elektix, Inc.] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 46  PAGE TABLE WALK @64-BIT BEI 4KB PAGE-GRÖSSE Phys. Mem: page4 l Mit der 4-stufigen Abbildung lassen sich theoretisch 256 TB virt. Speicher adressieren, page3 Linux erlaubt 128TB virtuellen Speichers pro Prozess. Äquivalent im Linux-Kernel Source Code: struct mm_struct *mm = current->mm; page2 pgd = pgd_offset(mm, address); page1 pgd = pud_offset(pgd, address); // neu 4-stufiges Mapping struct page pmd = pmd_offset(pgd, address); {...base_ptr...} page0 PTE pte = *pte_offset_map(pmd, address); PMD pte_t 0 page = pte_page(pte); page6 PUD pmd_t 0 pte_t 1 PGD pgd_t 0 pmd_t 1 pte_t 2 page5 pgd_t 0 pgd_t 1 pmd_t 2............ pte_t 511 page9 64-Bit Adresse in pgd_t 15 pgd_t 511 pmd_t 511 page8 virtuellen PGD Einträge Speicherraum page7 == 4kB Page unused 9Bit Offset 9Bit Offset 9Bit Offset 9Bit Offset 12Bit Offset 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 47  PAGE TABLE WALK @64-BIT BEI 2MB HUGE PAGES Phys. Mem: page4 l Huge Pages sind eine Optimierung in Betriebssystemen, insbesondere Linux, um den page3 Speicherzugriff effizienter zu gestalten. Für die Bildung einer Huge Page im 64-Bit System page2 werden die letzten 9-Bit Offset mit hinzugenommen -> 12+9 = 21 Bit Offset page1 l Mit 21-Bit Offset lassen sich 221 = 2MB ansprechen struct page {...base_ptr...} page0 PMD base_ptr: page6 PUD pmd_t 0 PTE Teil des HW PGD pgd_t 0 pmd_t 1 Descriptors page5 pte_t 0 pgd_t 0 pgd_t 1 pmd_t 2 pte_t 1......... pte_t 2 page9 64-Bit Adresse in pgd_t 15 pgd_t 511 pmd_t 511... page8 virtuellen PGD Einträge pte_t 511 Speicherraum page7 == 4kB Page unused 9Bit Offset 9Bit Offset 9Bit Offset 21Bit Offset 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 48  PAGE TABLE WALK @64-BIT BEI 1GB HUGE PAGES Phys. Mem: page4 l Huge Pages sind eine Optimierung in Betriebssystemen, insbesondere Linux, um den page3 Speicherzugriff effizienter zu gestalten. Für die Bildung einer 1GB Huge Page im 64-Bit System page2 werden weitere 9-Bit Offset mit hinzugenommen -> 12+9+9 = 30 Bit Offset page1 l Mit 30-Bit Offset lassen sich 230 = 1GB ansprechen struct page {...base_ptr...} page0 base_ptr: page6 PUD PMD PTE Teil des HW PGD pgd_t 0 page5 pmd_t 0 pte_t 0 Descriptors pgd_t 0 pgd_t 1 pmd_t 1 pte_t 1...... pmd_t 2 pte_t 2 page9 64-Bit Adresse in pgd_t 15 pgd_t 511...... page8 virtuellen PGD Einträge pmd_t 511 pte_t 511 Speicherraum page7 == 4kB Page unused 9Bit Offset 9Bit Offset 30Bit Offset 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 49 SPEICHERSEITEN: PAGES IM LINUX KERNEL l Für die Verwaltung jeder Page muss der Linux Kernel eine Datenstruktur vorhalten: l Ein Prozess hat Listen der ihm zugeordneten Pages. Wird ein PageFault ausgelöst, kann Linux herausfinden, ob der vom Prozess adressierte Speicher wirklich allokiert war, ob die Page vielleicht ausgelagert war, … struct page { // defined in linux/mm_types.h unsigned long flags; // VM-Flags struct address_space * mapping; // defined in linux/fs.h... unsigned long _count; // for reference counting... struct list_head lru; // Pageout list, e.g. active_list... } 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 50 VIRTUALISIERUNG IN LINUX PHYSIKALISCHE SPEICHERVERWALTUNG VON FREIEN SPEICHER -> BUDDY ALGO 51 DEFINITION: BUDDY-SPEICHERVERWALTUNG l Die Buddy-Speicherverwaltung ist ein Algorithmus, der in vielen Betriebssystemen, auch Linux, verwendet wird, um dynamisch Speicherblöcke im Hauptspeicher zu verwalten und dabei Speicherfragmentierung zu reduzieren. Vorteile sind: l Reduzierung der Fragmentierung l Speicherblöcke werden dynamisch zusammengeführt, sobald sie freigegeben werden l Effiziente Speicherzuteilung l Blöcke von 2er Potenzen erlaubt sehr schnelle und effiziente Zuteilung/Zusammenführung bei wenig Rechenaufwand l Einfache Verwaltung l Buddy-Algorithmus ist relativ einfach zu implementieren und funktioniert effizient mit unterschiedlichen Speicheranforderungen 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 52 BUDDY-SPEICHERVERWALTUNG (I) l Grundprinzip: l Aufteilung des Speichers in Blöcke von 2er Potenzen (Pages) l Jeder Speicherblock hat einen „Buddy“ – einen benachbarten Block derselben Größe l Bereitstellung von Speicher: l Wird ein Block benötigt, z.B.: 4kB, und ein 8kB-Block ist verfügbar -> teile 8kB-Block in 2x 4kB und teile zu. 1x 4kB bleibt frei für pot. weitere Bereitstellung l Freigabe von Speicher und Zusammenführung (Coalescing): l Wird ein Block freigegeben, so prüft der Algorithmus, ob sein Buddy ebenfalls frei ist. Falls ja, werden beide Blöcke zu einem größeren Block zusammengeführt (wird coalescing genannt). Der neue Block kann wiederum mit einem weiteren Buddy zusammengeführt werden, usw. 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 53 BUDDY-SPEICHERVERWALTUNG (II) Physikalische Buddy Buddy Buddy Speicherseiten: 1. Ordnung 2. Ordnung 3. Ordnung page15 buddy17 page14 buddy23 page13 buddy16 page12 buddy31 Die Ausgangssituation page11 buddy15 nach dem Booten ist, page10 buddy22 dass der gesamte page9 buddy14 verfügbare page8 physikalische Speicher page7 buddy13 frei ist und zu großen page6 buddy21 Buddies page5 buddy12 zusammengefasst wird. page4 buddy30 page3 buddy11 page2 buddy20 page1 buddy10 page0 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 55 BUDDY-SPEICHERVERWALTUNG (II) l Nun kommen Speicheranfragen, bspw.: 14 kB malloc -> 2. Ordnung l Von der größten Ordnung abwärts werden freie Blöcke gesucht: Physikalische Buddy Buddy Buddy Speicherseiten: 1. Ordnung 2. Ordnung 3. Ordnung page15 buddy17 page14 buddy23 page13 buddy16 page12 buddy31 page11 buddy15 page10 buddy22 page9 buddy14 page8 page7 buddy13 page6 buddy21 page5 buddy12 page4 buddy30 32kB noch frei page3 4 kB buddy11 page2 4 kB 2x 8kB 16kB buddy20 page1 4 kB noch frei noch frei buddy10 page0 4 kB 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 57 AUSLAGERN VON PAGES l Das Auslagern von Pages auf die Festplatte, auch als Paging oder Swapping bekannt, ist eine Technik, die in Betriebssystemen verwendet wird, um den begrenzten physischen Arbeitsspeicher (RAM) effizienter zu nutzen. l Diese werden zum Beispiel ausgelagert um unter anderem … l … verfügbaren Speicher für aktive Anwendungen zu erweitern l … wenig genutzte oder inaktiv Datenbereiche aus dem RAM zu entfernen l … Programmabstürze bei Speichermangel zu vermeiden l Nachteile: l Langsamer Zugriff auf ausgelagerte Daten l Thrashing: Wechsel zwischen RAM und Festpaltte, dies führt zu erheblicher Verlangsamung des Systems. 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 58 FLAGS FÜR PAGES AUSLAGERN Virtueller Speicher: Physikalischer Speicher: Mapping von virtueller à physikalische Pages 0x0..00 main() Text / page0 page4... Code page1 page3 myfunc() Segment 64-Bit Virtueller Adressraum... page2 page2 page1 page0 myvar=0 Data page3 mama=42 Segment page4 Allozi- HEAP page5 page6 page6 ierter Speicher Speicher page6 page5 IP-RetAddr Stack page7 page7 HDD int i; Segment int myval; page8 page8... Auslagern auf page9 page9 Festplatte 0xf..ff 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 59 ALGORITHMEN UM PAGES AUSZULAGERN l Pages auslagern (Tanenbaum S. 255ff, 4th Edition): l Optimaler Algorithmus zur Seitenersetzung l Nicht realisierbar l Der First-In-First-Out Algorithmus (FIFO) l Entfernt evtl. auch wichtige Seiten -> Fehleranfällig l Der Second Chance Algorithmus l Enorme Verbesserung gegenüber dem FIFO-Algorithmus l Der Clock-Algorithmus l Realistische Annahme über „veraltete“ Pages l Der Least-Recently-Used Algorithmus (LRU) l Exzellente Eigenschaften: verwendet von Linux (inkl. Clock) l Der Not-Recently-Used Algorithmus (NRU) l Sehr grobe Annäherung an den LRU-Algorithmus 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 61 FLAGS FÜR PAGES: COPY-ON-WRITE (COW) Virtueller Speicher: Physikalischer Speicher: 0x0..00 main() Text / page0 page4... Code page1 page3 myfunc() Segment 64-Bit Virtueller Adressraum... page2 page2 Zwei virtuelle Speicher- page1 seiten mappen auf die- page0 selbe physikalische myvar=0 Data page3 Speicherseite... mama=42 Segment page4 Das OS setzt das W-Bit auf Allozi- HEAP Null! page5 page5a ierter Speicher Wird von einem Prozesse Speicher page6 page5 schreibend auf diese Seite zugegriffen: Page-Fault und Kopieren in eine eigene Page, aka IP-RetAddr Stack page7 page7 int i; CoW = Copy-on-Write Segment int myval; page8 page8... page9 page9 0xf..ff 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 62  AI BS AUFGABEN ÜBUNGEN Quelle: [Image by Freepik] 63 FRAGE ZU PROZESSOR HARDWARE l Finden Sie heraus: l Welche Page Größen unterstützt ein Intel Core i7 (Sandy Bridge)? l A: 4kB Pages, 2MB und 1GB Huge Pages l Wie viele Pages der TLB je Page-Größe kann dieser Intel Prozessor cachen? l A: Für 4kB Pages 64 TLB-Einträge (L1 Data-Cache) Für 2MB Pages 32 TLB-Einträge Für 1GB Pages 4 Einträge J l Wie viel Speicher ein 64-Bit Prozessor insgesamt ansprechen könnte? l A: Insgesamt 2048 Exabytes!!! Da das derzeit viel zu viel ist, werden „nur“ 48-Bit nach außen als Adresse geführt, damit können 256 TB angesprochen werden. [Bild von vecstock auf Freepik] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 65 TOOLS ZUM ÜBERWACHEN: TOP / HTOP l Während Sie den Firefox Browser öffnen und wieder schließen, überprüfen Sie den Speicherverbrauch mittels top oder htop: 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 66 TOOLS ZUM ÜBERWACHEN: VMSTAT l Während Sie den Firefox Browser öffnen und wieder schließen, überprüfen Sie den Speicherverbrauch mittels vmstat. Dies fasst die Werte für einen Zeitraum zusammen: 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 67 TOOLS ZUM ÜBERWACHEN: PMAP l Während Sie den Firefox Browser öffnen und wieder schließen, überprüfen Sie den Speicherverbrauch mittels pmap. Mit pmap lässt sich /proc/PID/maps interpretieren: 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 68 WEITERE MÖGLICHKEITEN SPEICHERVERBRAUCH ÜBERWACHEN l Linux‘ Möglichkeiten, um Speicher zu überwachen: l cat /proc/meminfo l Was sind Huge Pages? l cat /proc/$$/status l Welche Speichergrößen werden abgebildet? l cat /proc/$$/smaps l Noch feingranulare Informationen zu Bibliotheken. l Jeder Prozess hat Soft- und Hard-Limits: ulimit -a↵ # User-Limit der Shell cat /proc/$$/limits↵ # User-Limits des Prozesses [Bild von vecstock auf Freepik] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 69 QUIZ SPEICHERVERBRAUCH l Laden Sie das Programm memory_allocation.c aus dem BS GitLab repository herunter (Achtung VPN notwendig): l https://gitlab.hs-esslingen.de/dgrewe/betriebssysteme/- /blob/main/08_speicherverwaltung/memory_allocation.c l Was macht das folgende Programm? l Variieren Sie die Größe und beobachten die Ausgabe. [Bild von vecstock auf Freepik] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 70 QUIZ SPEICHERVERBRAUCH l Laden Sie das Programm memory_allocation.c aus dem BS GitLab repository herunter (Achtung VPN notwendig): l https://gitlab.hs-esslingen.de/dgrewe/betriebssysteme/- /blob/main/08_speicherverwaltung/memory_allocation.c l Was macht das folgende Programm? l Variieren Sie die Größe und beobachten die Ausgabe. l Der Aufruf von malloc() in der Bibliothek glibc wird als „Anon“ Speicher angezeigt; strace liefert die Systemaufrufe mmap() und brk() über die Speicher alloziiert wird. [Bild von vecstock auf Freepik] 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 71 QUIZ SPEICHERVERBRAUCH l Der Aufruf von malloc() in der Bibliothek glibc wird als „Anon“ Speicher angezeigt; strace liefert die Systemaufrufe mmap() und brk() über die Speicher alloziiert wird. Der malloc() wird gar nicht an den Kernel weitergegeben! Erst ab 132kB wird via mmap ein anonymous Speicherbereich angelegt! 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 72 QUIZ SPEICHERVERBRAUCH l In pmap sehen wir das Anlegen weiterer anonymous page... l Diese Optimierung von glibc erlaubt es bis 4kB+128 kB keine (langwierigen) Speicheranforderungen zu stellen. Erst hier sehen wir diese zweite, neu angelegte „anonymous“ Speicherseg- ment zur Speicherallokation. Der gesamte allokierte Speicher für die Bibliothek, diesen Speicherbereich Die Resident Set Size (RSS), den im diesen Prozess belegten Speicher. Seiten, die „Dirty“ sind wurden verändert gegenüber der Version auf der Festplatte 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 73 ZUSAMMENFASSUNG l Wiederholung: Unterschiede Prozesse, Threads in Linux l Kennenlernen der Konzepte von Speicherverwaltung sowohl in Hardware als auch in Software (Betriebssystem). l Drei- (32-Bit) bzw. Vier- (64-Bit) Stufen Modell der Speicherverwaltung unter Linux, sowie Erweiterungen wie Huge Pages. l Begrifflichkeiten wie Pages, Paging / Swapping, Buddy-Speicherverwaltung, und Copy-on- Write behandelt. l Übungen an Hand eines Programmcode-beispiels. 10.11.2024 Profs. Grewe & Keller | Betriebssysteme | Virtuelle Speicherverwaltung 74