Intel x86 Assembly Language & Microarchitecture
Personsökning - Virtuell adressering och minne

Introduktion

Historia

De första datorerna

Tidigare datorer hade ett minnesblock som programmeraren satte in kod och data i och CPU: n kördes inom denna miljö. Med tanke på att datorerna då var mycket dyra, var det olyckligt att det skulle göra ett jobb, stoppa och vänta på att nästa jobb laddades i det och sedan bearbeta det.

Multi-user, multi-processor

Därför blev datorer snabbt mer sofistikerade och stöttade flera användare och / eller program samtidigt - men det var då problem började uppstå med den enkla "ett block av minne" -idén. Om en dator körde två program samtidigt, eller körde samma program för flera användare - vilket naturligtvis skulle ha krävt separat data för varje användare - blev hanteringen av det minnet kritiskt.

Exempel

Till exempel: om ett program har skrivits för att fungera på minnesadress 1000, men ett annat program redan laddats där, kunde det nya programmet inte laddas. Ett sätt att lösa detta skulle vara att få program att fungera med "relativ adressering" - det spelade ingen roll var programmet laddades, det gjorde bara allt i förhållande till minnesadressen som det laddades i. Men det krävde hårdvarustöd.

Raffinemang

När datormaskinvaran blev mer sofistikerad kunde den stödja större minnesblock, vilket möjliggjorde mer samtidiga program, och det blev svårare att skriva program som inte stör det som redan laddats. En strömminnesreferens kan inte bara nämna det aktuella programmet, utan alla andra program i minnet - inklusive operativsystemet självt!

lösningar

Det som behövdes var en mekanism som gjorde det möjligt för minnesblock att ha dynamiska adresser. På så sätt kunde ett program skrivas för att arbeta med sina block av minnen på adresser som det kände igen - och inte kunna komma åt andra block för andra program (såvida inte något samarbete tillät det).

segmente~~POS=TRUNC

En mekanism som implementerade detta var Segmentation. Det gjorde det möjligt att definiera minnesblock av alla olika storlekar, och programmet måste definiera vilket segment det ville ha åtkomst till hela tiden.

problem

Denna teknik var kraftfull - men dess mycket flexibilitet var ett problem. Eftersom segment i huvudsak delade upp det tillgängliga minnet i bitar i olika storlekar, var minneshanteringen för dessa segment ett problem: allokering, omlokalisering, växande, krympande, fragmentering - allt krävde sofistikerade rutiner och ibland masskopiering för att implementera.

personsökning

En annan teknik delade upp hela minnet i lika stora block, kallade "Sidor", vilket gjorde fördelnings- och delningsrutinerna väldigt enkla och tog bort växande, krympande och fragmenterade (med undantag för intern fragmentering, som bara är ett problem med spill).

Virtuell adressering

Genom att dela upp minnet i dessa block kan de allokeras till olika program efter behov med vilken adress programmet behövde på. Denna "kartläggning" mellan minnets fysiska adress och programmets önskade adress är mycket kraftfull och är grunden för varje större processors (Intel, ARM, MIPS, Power et al.) Minnehantering i dag.

Hårdvara och operativsystemstöd

Hårdvaran utförde omappningen automatiskt och kontinuerligt, men krävde minne för att definiera tabellerna för vad de ska göra. Naturligtvis måste hushållningen i samband med denna omläggning kontrolleras av något. Operativsystemet måste tappa ut minnet efter behov och hantera datatabellerna som krävs av hårdvaran för att stödja vad programmen kräver.

Personsökningsfunktioner

När hårdvaran kunde göra den här omappningen, vad tillät den? Huvuddrivrutinen var multiprocessering - förmågan att köra flera program, alla med sitt "eget" minne, skyddade från varandra. Men två andra alternativ inkluderade "glesa data" och "virtuellt minne".

multi~~POS=TRUNC

Varje program fick sitt eget, virtuella "adressutrymme" - ett intervall adresser som de kunde ha kartlagt fysiskt minne, på vilka adresser som helst önskades. Så länge det fanns tillräckligt med fysiskt minne för att gå runt (även om "Virtuella minne" nedan), kunde många program stöds samtidigt.

Dessutom kunde dessa program inte få åtkomst till minne som inte mappades i deras virtuella adressutrymme - skyddet mellan programmen var automatiskt. Om program behövdes för att kommunicera, kan de be operativsystemet att ordna ett delat minnesblock - ett block med fysiskt minne som kartlades i två olika program adressutrymmen samtidigt.

Sparsam data

Att tillåta ett enormt virtuellt adressutrymme (4 GB är typiskt för att motsvara 32-bitarsregisterna som dessa processorer vanligtvis hade) släpper inte i sig självt minne om stora områden i det adressutrymmet inte återställs. Detta möjliggör skapandet av enorma datastrukturer där endast vissa delar är mappade samtidigt. Föreställ dig en tredimensionell matris med 1 000 byte i varje riktning: det tar normalt en miljard byte! Men ett program kan reservera ett block av dess virtuella adressutrymme för att "hålla" denna information, men bara kartlägga små avsnitt när de var befolkade. Detta möjliggör effektiv programmering, samtidigt som man inte slösar bort minne för data som inte behövs ännu.

Virtuellt minne

Ovan använde jag termen "Virtual Addressing" för att beskriva den virtuella-till-fysiska adresseringen som utförts av hårdvaran. Detta kallas ofta "virtuellt minne" - men det uttrycket motsvarar mer korrekt tekniken för att använda virtuell adressering för att ge en illusion av mer minne än vad som faktiskt finns tillgängligt.

Det fungerar så här:

• Eftersom program laddas och begär mer minne, tillhandahåller operativsystemet minnet från vad det har tillgängligt. Förutom att hålla reda på vilket minne som har mappats, håller OS också reda på när minnet faktiskt används - hårdvaran stödjer markering av använda sidor.
• När operativsystemet har slut på det fysiska minnet ser det på det minne som det redan har delat ut för vilken sida som har använts minst eller inte hade använts längst. Det sparar det specifika sidans innehåll på hårddisken, kommer ihåg var det var, markerar det som "Inte närvarande" på hårdvaran för den ursprungliga ägaren och nollar sedan sidan och ger den till den nya ägaren.
• Om den ursprungliga ägaren försöker komma åt den sidan igen, meddelar hårdvaran operativsystemet. OS tilldelar sedan en ny sida (kanske måste göra det föregående steget igen!), Laddar upp den gamla sidans innehåll och överlämnar sedan den nya sidan till det ursprungliga programmet.

  Den viktiga punkten att lägga märke till är att eftersom varje sida kan mappas till vilken adress som helst, och varje sida har samma storlek, så är en sida lika bra som alla andra - så länge innehållet förblir detsamma!

• Om ett program har åtkomst till en icke mappad minnesplats meddelar maskinvaran operativsystemet som tidigare. Den här gången noterar operativsystemet att det inte var en sida som hade sparats bort, så känner igen den som ett fel i programmet och avslutar det!

  Det här är faktiskt vad som händer när din app på mystiskt sätt försvinner på dig - kanske med en MessageBox från OS. Det är också vad (ofta) råkar orsaka en ökänd Blue Screen eller Sad Mac - buggy-programmet var i själva verket en OS-drivrutin som fick åtkomst till minne som det inte borde!

Personsökningsbeslut

Hårdvaruarkitekterna behövde fatta några stora beslut om personsökning, eftersom designen skulle direkt påverka CPU: s design! Ett mycket flexibelt system skulle ha ett högt omkostnad och kräva stora mängder minne bara för att hantera själva personsökningsinfrastrukturen.

Hur stor ska en sida vara?

I hårdvara skulle den enklaste implementeringen av personsökning vara att ta en adress och dela upp den i två delar. Den övre delen skulle vara en indikator på vilken sida som ska åtkomst, medan den nedre delen skulle vara indexet till sidan för önskad byte:

+-----------------+------------+
| Page index      | Byte index |
+-----------------+------------+

Det blev snabbt uppenbart att små sidor skulle kräva stora index för varje program: även minne som inte var kartlagt skulle behöva en post i tabellen som indikerar detta.

Så istället används ett flerskiktigt index. Adressen är indelad i flera delar (tre anges i exemplet nedan), och den övre delen (vanligtvis kallas "katalog") indexeras till nästa del och så vidare tills det sista byteindexet till den sista sidan avkodas:

+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+

Det betyder att ett katalogindex kan indikera "inte mappat" för en stor del av adressutrymmet utan att kräva många sidindex.

Hur optimerar du användningen av sidtabellerna?

Varje adressåtkomst som CPU kommer att göra måste kartläggas - den virtuella-till-fysiska processen måste därför vara så effektiv som möjligt. Om det trestegssystem som beskrivs ovan skulle implementeras skulle det innebära att varje minnesåtkomst faktiskt skulle vara tre åtkomster: en till katalogen; en till sidtabellen; och sedan slutligen själva önskad data. Och om CPU också behövde utföra hushållning, till exempel att indikera att denna sida nu hade åtkomst eller skrivits till, skulle det kräva ännu fler åtkomster för att uppdatera fälten.

Minnet kan vara snabbt, men detta skulle innebära en tredubbla avmattning av alla minnesåtkomstar under personsökning! Lyckligtvis har de flesta program en "lokalisering av omfattning" - det vill säga om de har åtkomst till en plats i minnet, kommer framtida åtkomst förmodligen att vara i närheten. Och eftersom sidor inte är för små, behöver den kartläggningskonvertering bara utföras när en ny sida öppnades: inte för absolut varje åtkomst.

Men ännu bättre skulle det vara att implementera en cache med nyligen åtkomna sidor, inte bara den senaste. Problemet skulle vara att följa med vilka sidor som hade nåtts och vad som inte hade gjort - hårdvaran måste skanna igenom cachen vid varje åtkomst för att hitta det cachade värdet. Så cacheminnet implementeras som en innehållsadresserbar cache: istället för att nås via adress, åtkomst till den med innehåll - om de begärda uppgifterna finns, erbjuds den upp, annars flaggas en tom plats för att fylla i istället. Cachen hanterar allt detta.

Denna cache som kan adresseras med innehåll kallas ofta en TLB (Translation Lookaside Buffer) och krävs för att hanteras av operativsystemet som en del av subsystemet Virtual Addressing. När katalogerna eller sidtabellerna ändras av operativsystemet måste den meddela TLB att uppdatera sina poster - eller helt enkelt ogiltiga dem.

80386 Personsökning

Hög nivå design

80386 är en 32-bitars processor med ett 32-bitars adresserbart minnesutrymme. Konstruktörerna för undersökningssystemet noterade att en 4K-siddesign kartläggs i dessa 32 bitar på ett ganska snyggt sätt - 10 bitar, 10 bitar och 12 bitar:

+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+
 3         2 2          1 1          0  Bit
 1         2 1          2 1          0  number

Det innebar att Byte-indexet var 12 bitar brett, vilket skulle indexeras till en 4K-sida. Katalog- och sidindexen var 10 bitar, som var och en skulle kartlägga i en 1 024-tabell - och om dessa tabellposter var 4 byte, skulle det vara 4K per tabell: också en sida!

Så det var vad de gjorde:

• Varje program skulle ha sin egen katalog, en sida med 1 024 siduppgifter som var och en definierade var nästa nivå sidtabell var - om det fanns en.
• Om det fanns skulle den sidtabellen ha 1 024 sidposter som var och en definierade var den sista nivån var - om det fanns en.
• Om det fanns så kan den sidan ha Byte direkt avläst.

Sidinmatning

Både topplistan och sidtabellen på nästa nivå består av 1 024 sidposter. Den viktigaste delen av dessa poster är adressen till vad den indexerar: en sidtabell eller en faktisk sida. Observera att den här adressen inte behöver de fullständiga 32 bitarna - eftersom allt är en sida är bara de 20 bästa bitarna betydande. Således kan de andra 12 bitarna i sidinmatningen användas för andra saker: om nästa nivå till och med är närvarande; hushållning om sidan har nått eller skrivits till; och även om skrivningar till och med bör tillåtas!

+--------------+----+------+-----+---+---+
| Page Address | OS | Used | Sup | W | P |
+--------------+----+------+-----+---+---+
Page Address = Top 20 bits of Page Table or Page address
OS           = Available for OS use
Used         = Whether this page has been accessed or written to
Sup          = Whether this page is Supervisory - only accessible by the OS
W            = Whether this page is allowed to be Written
P            = Whether this page is even Present

Observera att om P biten är 0 så får resten av posten ha något som operativsystemet vill lägga in där, till exempel där sidans innehåll måste vara på hårddisken!

PDBR ( PDBR )

Om varje program har sin egen katalog, hur vet hårdvaran var man ska börja kartlägga? Eftersom CPU bara kör ett program i taget har den ett enda kontrollregister för att hålla adressen till det aktuella programmets katalog. Detta är CR3 ( CR3 ). När operativsystemet byter mellan olika program uppdaterar det PDBR med relevant sidkatalog för programmet.

Sidfel

Varje gång CPU: n kommer åt minnet måste den kartlägga den angivna virtuella adressen till lämplig fysisk adress. Detta är en trestegsprocess:

1. Indexera de 10 bästa bitarna på adressen till den sida som anges av PDBR att få adressen till rätt sidtabell;
2. Indexera de nästa 10 bitarna av adressen till den sida som anges av katalogen för att få adressen till rätt sida;
3. Indexera de sista 12 bitarna av adressen för att få informationen från den sidan.

Eftersom både steg 1. och 2. ovan använder sidposter kan varje post indikera ett problem:

• Nästa nivå kan markeras "Inte närvarande";
• Nästa nivå kan markeras som "skrivskyddad" - och åtgärden är en skrivning;
• Nästa nivå kan markeras som "Supervisor" - och det är programmet som får åtkomst till minnet, inte OS.

När ett sådant problem noteras av hårdvaran, istället för att slutföra åtkomsten, uppstår det ett fel: Avbrott # 14, sidfel. Den fyller också i vissa specifika kontrollregister med information om varför felet inträffade: adressen som refereras till; huruvida det var en tillsynsadkomst; och om det var ett skrivförsök.

OS förväntas fånga felet, avkoda kontrollregistren och bestämma vad de ska göra. Om det är en ogiltig åtkomst kan den avbryta felprogrammet. Men om det är en virtuell minnesåtkomst, bör OS tilldela en ny sida (som kan behöva utrymma en sida som redan används!), Fylla den med det nödvändiga innehållet (antingen alla nollor eller det tidigare innehållet som laddats tillbaka från disken ), kartlägg den nya sidan i lämplig sidtabell, markera den som närvarande och fortsätt sedan felinstruktionen. Den här gången kommer åtkomsten framgångsrikt och programmet fortsätter utan att veta att något speciellt hände (såvida det inte tar en titt på klockan!)

80486 Personsökning

80486 personsökarsubsystem var mycket likt det 80386. Det var bakåtkompatibelt, och de enda nya funktionerna var att möjliggöra kontroll av minnescache på en sida-för-sida-bas - OS-konstruktörerna kunde markera specifika sidor som inte cache, eller att använda olika genomskrivningar eller omskrivningar cachingtekniker.

I alla andra avseenden är exemplet "80386 personsökning" tillämpligt.

Pentiumsökning

När Pentium utvecklades blev minnesstorlekar och programmen som kördes i dem större. OS måste göra mer och mer arbete för att underhålla personsökningssubsystemet bara i det stora antalet sidindex som behövde uppdateras när stora program eller datauppsättningar användes.

Så Pentium-designarna lade till ett enkelt trick: de satte en extra bit i Entries of the Page Directory som indikerade om nästa nivå var en sidtabell (som tidigare) - eller gick direkt till en 4 MB sida! Genom att ha konceptet 4 MB-sidor skulle OS inte behöva skapa en sidtabell och fylla den med 1 024 poster som i princip indexerade adresser 4K högre än den föregående.

Adresslayout

+-----------+----------------------+
| Dir Index | 4MB Byte Index       |
+-----------+----------------------+
 3         2 2                    0   Bit
 1         2 1                    0   number

Kataloginmatningslayout

+-----------+----+---+------+-----+---+---+
| Page Addr | OS | S | Used | Sup | W | P |
+-----------+----+---+------+-----+---+---+
Page Addr = Top 20 bits of Page Table or Page address
OS        = Available for OS use
S         = Size of Next Level: 0 = Page Table, 1 = 4 MB Page
Used      = Whether this page has been accessed or written to
Sup       = Whether this page is Supervisory - onlly accessible by the OS
W         = Whether this page is allowed to be Written
P         = Whether this page is even Present

Naturligtvis hade det några förgreningar:

• 4 MB-sidan var tvungen att starta på en 4 MB adressgräns, precis som 4K-sidorna var tvungen att starta på en 4K-adressgräns.
• Alla 4 MB måste tillhöra ett enda program - eller delas av flera.

Detta var perfekt för användning i kringutrustning med stort minne, till exempel grafikadaptrar, som hade stora adressutrymme-fönster som måste kartläggas för att OS skulle kunna använda.

Fysisk adressförlängning (PAE)

Introduktion

När minnespriserna sjönk kunde Intel-baserade datorer ha mer och mer RAM-pris överkomligt, vilket lindrade många användares problem med att köra många av de allt större applikationer som producerades samtidigt. Medan virtuellt minne tillät att minnet praktiskt taget skulle "skapas" - byta befintligt "gammalt" sidinnehåll till hårddisken för att tillåta "ny" data lagras - detta bromsade programmets körning eftersom sidan "trashing" fortsatte att byta data på och utanför hårddisken.

Mer RAM

Det som behövdes var möjligheten att få tillgång till mer fysiskt RAM - men det var redan en 32-bitars adressbuss, så varje ökning skulle kräva större adressregister. Eller skulle det? När du utvecklar Pentium Pro (och till och med Pentium M), som ett stopp-gap tills 64-bitars processorer kunde produceras, lägg till fler fysiska adressbitar (vilket möjliggör mer fysiskt minne) utan att ändra antalet registerbitar. Detta kan uppnås eftersom virtuella adresser mappades till fysiska adresser ändå - allt som behövdes för att ändra var mappningssystemet.

Design

Det befintliga systemet kunde ha åtkomst till maximalt 32 bitar fysiska adresser. För att öka detta krävdes en fullständig ändring av strukturen för sidainmatning, från 32 till 64 bitar. Det beslutades att hålla minsta granularitet vid 4K sidor, så 64-bitars posten skulle ha 52 bitar adress och 12 bitar kontroll (som föregående post hade 20 bitar adress och 12 bitar kontroll).

Att ha en 64-bitars post, men en sidstorlek på (fortfarande) 4K, innebar att det bara skulle finnas 512 poster per sidtabell eller katalog, istället för de tidigare 1.024. Det innebar att den 32-bitars virtuella adressen skulle delas annorlunda än tidigare:

+-----+-----------+------------+------------+
| DPI | Dir Index | Page Index | Byte Index |
+-----+-----------+------------+------------+
 3   3 2         2 2          1 1          0   Bit
 1   0 9         1 0          2 1          0   number

 DPI        = 2-bit index into Directory Pointer Table
 Dir Index  = 9-bit index into Directory
 Page Index = 9-bit index into Page Table
 Byte Index = 12-bit index into Page (as before)

Att hugga en bit från både katalogindex och sidindex gav två bitar för en tredje kartläggningsnivå: de kallade detta för sidkatalogen Pointer Table (PDPT), en tabell med exakt fyra 64-bitars poster som adresserade fyra kataloger i stället för den tidigare ett. PDBR ( CR3 ) pekade nu på PDPT istället - som, eftersom CR3 bara var 32 bitar, behövde lagras i de första 4 GB RAM för tillgänglighet. Observera att eftersom de låga bitarna av CR3 används för kontroll måste PDPT börja på en 32-byte gräns.

Sidstorleksförlängning (PSE)

Och eftersom de tidigare 4MB-sidorna var så bra idé ville de kunna stödja stora sidor igen. Den här gången producerade inte det sista lagret i tiersystemet inte 10 + 12 bitars 4MB-sidor, utan 9 + 12 bitars 2MB-sidor istället.

PSE-32 (och PSE-40)

Eftersom det fysiska adressförlängnings-läget (PAE) som introducerades i Pentium Pro (och Pentum M) var en sådan förändring av operativsystemets minnehanteringssystem, när Intel utformade Pentium II beslutade de att förbättra det "normala" sidläget till stödja de nya fysiska adressbitarna i processorn inom de tidigare definierade 32-bitarsposterna.

De insåg att när en 4MB-sida användes såg katalogen in så här:

+-----------+------------+---------+
| Dir Index |  Unused    | Control |
+-----------+------------+---------+

Dir-indexet och kontrollområdena för posten var desamma, men blocket med oanvända bitar mellan dem - som skulle användas av sidindexet om det fanns - slösades bort. Så de beslutade att använda det området för att definiera de övre fysiska adressbitarna över 31 !

+-----------+------+-----+---------+
| Dir Index |Unused|Upper| Control |
+-----------+------+-----+---------+

Detta gjorde att RAM över 4 GB var tillgängligt för operativsystem som inte använde PAE-läget - med lite extra logik kunde de ge stora mängder extra RAM till systemet, om än inte mer än den normala 4 GB för varje program. Till att börja med lades endast fyra bitar till, vilket möjliggjorde 36-bitars fysisk adressering, så detta läge kallades Page Size Extension 36 (PSE-36). Det ändrade faktiskt inte sidstorleken, bara adresseringen emellertid.

Begränsningen av detta var dock att endast 4MB-sidor över 4 GB var definierbara - 4K-sidor tilläts inte. Antagandet av detta läge var inte brett - det var enligt uppgift långsammare än att använda PAE, och Linux slutade inte någonsin med det.

I senare processorer som hade ännu fler fysiska adressbitar breddade både AMD och Intel PSE-området till 8 bitar, vilket vissa människor kallade "PSE-40"