Adresseområder, relokering og segmentering

Illusjonen om privat minne

Hver prosess tror den eier hele minnet alene, fra adresse 0 og oppover.

adresseområde kalles dette — den logiske minneverdenen prosessen ser, vanligvis delt opp i kode (nederst), heap (vokser oppover) og stack (vokser nedover fra toppen). Det fine er at illusjonen er konsistent på tvers av prosesser: alle ser «sin» adresse 0x4000 som starten på koden, selv om den fysisk ligger på vidt forskjellige steder.

OS og maskinvare må gjøre to ting for å holde illusjonen oppe. For det første må hver virtuell adresse fra prosessen oversettes til en fysisk adresse i RAM før minneaksessen skjer. For det andre må OS sørge for at en prosess aldri får tak i en annen prosesses minne, enten ved feil eller med vilje. Begge løses av mmu-en — en maskinvarekrets som sitter mellom CPU-en og minnebussen.

Statisk relokering var et blindspor

De første systemene løste relokering statisk: når et program ble lastet inn, gikk lasteren gjennom hver minneaksess i koden og la til en konstant offset. Etter loading var adressene «brent inn» — programmet kunne ikke flyttes uten å lastes på nytt.

Det fungerer for batch-systemer, men ikke når flere prosesser deler minnet og kommer og går. Vi trenger dynamisk relokering: oversettelsen må skje ved hver minneaksess, ikke én gang ved load. Det krever maskinvarestøtte, og det er nettopp det base/bounds gir oss.

Base og bounds — den enkleste hardware-relokering

To registre per prosess: base-register (hvor i fysisk RAM prosessens område starter) og bounds-register (hvor stort det er). Ved hver minneaksess gjør MMU ƒbase/bounds-oversettelse.

Det er to operasjoner: en sammenligning (er adressen innenfor lovlig område?) og en addisjon (legg til base). Begge er én CPU-syklus i moderne maskinvare, så overhead er nærmest null. Når kjernen bytter prosess, oppdaterer den bare base- og bounds-registrene, og hele oversettelsen følger med.

Eksempel: prosessen har Base = 32 KiB og Bounds = 16 KiB. Den utfører en aksess på virtuell adresse 0x100 (256). MMU sjekker at 256 < 16384 (OK), legger til 32768, og leser fra fysisk adresse 32 KiB + 256 = 33 024. Hadde prosessen prøvd å lese på virtuell 0x5000 (20 480), ville sjekken feilet og MMU genererer en segmentation fault-trap til kjernen.

Beskyttelse er et biprodukt

Det fine ved base/bounds er at beskyttelse kommer gratis. En prosess kan ikke peke utenfor sitt eget bounds — MMU fanger det. Prosesser kan ikke se hverandres minne, fordi hver har sin egen base, og kjernen er den eneste som kan endre base-/bounds-registrene (CPU-en har en privilegert modus som kreves for det).

Så langt fungerer dette utmerket — for små, enkle programmer. Problemet kommer når heap og stack vokser dynamisk og uavhengig av hverandre.

Hvorfor base/bounds faller fra hverandre

Et adresseområde med kode på bunn, heap som vokser oppover og stack som vokser nedover har en stor død sone i midten — minne som er reservert, men aldri brukt. Med base/bounds må vi allokere fysisk minne for hele prosessens adresseområde, inkludert den døde sonen.

Eksempel: prosessen har 16 KiB virtuelt adresseområde. Kode bruker 2 KiB nederst. Heap har vokst til 4 KiB. Stack bruker 2 KiB øverst. Mellom heap-toppen og stack-bunnen ligger 8 KiB ubrukt — men OS reserverer alle 16 KiB i fysisk RAM. Det er intern fragmentering: vi har allokert mer enn vi bruker, og det ledige kan ikke gis til andre.

Segmentering — én base og bounds per logisk del

Løsningen er segmentering: i stedet for ett par av base/bounds-registre per prosess, har vi ett par per logisk segment. Typisk tre segmenter — kode, heap, stack — hver med sin egen base og størrelse.

Oversettelsen blir ƒsegmentoversettelse: avhengig av hvilket segment adressen tilhører (utledet fra de øverste bitene), velger MMU base og legger til offset. ƒgyldighetsregel avgjør om adressen er innenfor segmentet sin deklarerte størrelse.

Resultatet er at den døde sonen mellom heap og stack ikke lenger trenger fysisk RAM. Heap-segmentet er 4 KiB stort, stack-segmentet er 2 KiB stort, og kun de 6 KiB som faktisk brukes er allokert — de 8 KiB som tidligere lå brakk er nå tilgjengelig for andre prosesser.

Ekstern fragmentering — det nye problemet

Segmentering løser intern fragmentering, men introduserer en ny plage: ekstern fragmentering. Etter at prosesser har kommet og gått en stund, er det fysiske minnet et lappeteppe av ledige hull i forskjellige størrelser. Du har kanskje 100 KiB ledig totalt, men det største sammenhengende området er bare 12 KiB. En ny prosess som trenger et 30 KiB heap-segment vil feile, selv om det er masse plass.

Klassiske fikser er kompaktering (flytt segmenter rundt for å samle ledig plass) og best fit vs first fit-allokeringsstrategier. Kompaktering er dyrt — det stopper alle prosesser mens minne kopieres, og må oppdatere base-registrene etterpå. Allokeringsstrategiene reduserer fragmenteringen, men eliminerer den ikke. First fit er rask men gir mange små rester. Best fit minimerer sløsing per allokering, men er dyrere å beregne og fører ofte til veldig små rester som er ubrukbare. Worst fit — alltid bruk det største hullet — gir få men store rester, og brukes sjelden i praksis.

Et tredje problem dukker opp når heap eller stack vil vokse. Sier prosessen sbrk() for å utvide heapet med 4 KiB, men neste 4 KiB i fysisk minne tilhører et annet segment? Da må OS enten flytte heapet til et større ledig område (kostbart, krever oppdatering av base) eller nekte allokeringen. Begge er dårlige svar.

Mer om beskyttelse — privilegerte instruksjoner

Beskyttelse er ikke bare bounds-sjekk. CPU-en har to (noen ganger flere) modus: brukermodus og kjernemodus. Visse instruksjoner — som å oppdatere base/bounds-registrene, eller å kommunisere med I/O-enheter — kan kun utføres i kjernemodus. Forsøk fra brukermodus utløser en trap, og kjernen får kontrollen.

Mode-bittet er den fundamentale skillelinjen i et beskyttet OS. Brukerprogrammer kan ikke endre adresseoversettelsen sin; bare kjernen kan. Brukerprogrammer kan heller ikke lese vilkårlig fysisk minne; alt går gjennom MMU-en, og MMU-en lytter kun til kjernen. Sammen gir dette en sterk garanti: en buggy eller ondsinnet prosess kan ikke korrupere andre prosesser, og kan ikke crashe systemet (kun seg selv).

Kontekstbytte og minnekonfigurasjon

Når kjernen bytter prosess, må adresseoversettelsen byttes også. Med base/bounds er det trivielt: lagre nåværende prosess sine to registre i PCB-en (Process Control Block), last den nye prosessen sine. To minneskrivinger og to minnelesninger — noen titalls nanosekunder.

Med segmentering er det noe mer arbeid — flere segmenter, flere registre. Men det skalerer ikke til paging. Et adresseområde med tusenvis av sider kan ikke ha tusenvis av registre, så vi flytter sidetabellen til RAM og lar et enkelt peker-register (i RISC-V kalles det satp) peke på toppen. Bytte av prosess blir å oppdatere den ene pekeren, men da må også TLB-en flushes — ellers kunne den nye prosessen tilfeldigvis treffe gamle oversettelser fra den forrige. Det er en usynlig kostnad ved kontekstbytte i paging-systemer som vi ikke har i base/bounds.

Veien videre — paging

Den fundamentale grunnen til ekstern fragmentering er at segmenter er variable i størrelse. Fysisk RAM må gi sammenhengende plass for hver. Hvis vi i stedet deler all minnet i faste blokker — sider og rammer av samme størrelse — forsvinner problemet. Det er paging, og det er tema for neste kapittel.

To andre grunner driver overgangen fra segmentering til paging. Den første er at antallet segmenter må være lite (typisk tre til åtte) for å passe i maskinvare-registre, og det begrenser hvor finkornet beskyttelsen kan være. Den andre er at swapping av et helt segment til disk er upraktisk — segmenter er for store. Med faste sider på 4 KiB kan vi swappe små biter, og MMU-en kan håndtere tusenvis av sider uten registre — bare en sidetabell i RAM.