Intel x86 Assembly Language & Microarchitecture
Cercapersone - Indirizzamento e memoria virtuali

introduzione

Storia

I primi computer

I primi computer avevano un blocco di memoria in cui il programmatore inserisce codice e dati e la CPU viene eseguita all'interno di questo ambiente. Dato che i computer erano molto costosi, è stato un peccato che avrebbe fatto un lavoro, fermarsi e aspettare che il lavoro successivo venisse caricato in esso, e poi elaborarlo.

Multiutente, multi-elaborazione

Così i computer sono diventati rapidamente più sofisticati e hanno supportato più utenti e / o programmi contemporaneamente, ma in quel momento i problemi iniziarono a sorgere con la semplice idea di "un blocco di memoria". Se un computer eseguiva due programmi contemporaneamente o eseguiva lo stesso programma per più utenti, cosa che ovviamente avrebbe richiesto dati separati per ciascun utente, la gestione di quella memoria diventava critica.

Esempio

Ad esempio: se un programma è stato scritto per funzionare all'indirizzo di memoria 1000, ma un altro programma è già stato caricato lì, non è stato possibile caricare il nuovo programma. Un modo per risolverlo sarebbe quello di far funzionare i programmi con "indirizzamento relativo" - non importava dove fosse caricato il programma, semplicemente faceva tutto relativo all'indirizzo di memoria in cui era caricato. Ma ciò richiedeva il supporto hardware.

raffinatezza

Man mano che l'hardware del computer diventava più sofisticato, era in grado di supportare grandi blocchi di memoria, consentendo più programmi simultanei, e diventava più complicato scrivere programmi che non interferivano con ciò che era già stato caricato. Un riferimento alla memoria randagio potrebbe far cadere non solo il programma corrente, ma qualsiasi altro programma in memoria, incluso il sistema operativo stesso!

soluzioni

Ciò che era necessario era un meccanismo che consentisse ai blocchi di memoria di avere indirizzi dinamici . In questo modo, un programma potrebbe essere scritto per funzionare con i suoi blocchi di memorie agli indirizzi riconosciuti, e non essere in grado di accedere ad altri blocchi per altri programmi (a meno che non sia consentito da una cooperazione).

Segmentazione

Un meccanismo che ha implementato questo era la segmentazione. Ciò consentiva di definire blocchi di memoria di tutte le dimensioni e il programma avrebbe dovuto definire a quale segmento desiderava accedere in qualsiasi momento.

I problemi

Questa tecnica era potente, ma la sua estrema flessibilità era un problema. Poiché i segmenti essenzialmente suddivisione della memoria disponibile in blocchi di dimensioni diverse, la gestione della memoria per tali segmenti era un problema: allocazione, deallocazione, crescita, restringimento, frammentazione - tutte richieste di routine sofisticate e talvolta di copia di massa da implementare.

paging

Una tecnica diversa divideva tutta la memoria in blocchi di uguale dimensione, chiamati "Pagine", che rendevano le routine di allocazione e deallocazione molto semplici, eliminando la crescita, il restringimento e la frammentazione (eccetto la frammentazione interna, che è semplicemente un problema di scarto).

Indirizzamento virtuale

Dividendo la memoria in questi blocchi, potrebbero essere assegnati a diversi programmi secondo necessità con qualsiasi indirizzo il programma lo richiedesse. Questa "mappatura" tra l'indirizzo fisico della memoria e l'indirizzo desiderato del programma è molto potente ed è la base per la gestione della memoria di tutti i principali processori (Intel, ARM, MIPS, Power et al.) Oggi.

Supporto hardware e OS

L'hardware eseguiva la rimappatura automaticamente e continuamente, ma richiedeva memoria per definire le tabelle di cosa fare. Naturalmente, il servizio di pulizia associato a questa rimappatura doveva essere controllato da qualcosa. Il sistema operativo dovrebbe scaricare la memoria come richiesto e gestire le tabelle di dati richieste dall'hardware per supportare i programmi richiesti.

Funzionalità di cercapersone

Una volta che l'hardware ha potuto fare questa rimappatura, cosa ha permesso? Il driver principale era multiprocessing: la possibilità di eseguire più programmi, ciascuno con la propria memoria, protetti l'uno dall'altro. Ma altre due opzioni includevano "dati sparsi" e "memoria virtuale".

multiprocessing

Ad ogni programma è stato assegnato il proprio "Spazio indirizzo" virtuale, un intervallo di indirizzi a cui potevano essere mappati la memoria fisica, a qualsiasi indirizzo desiderato. Finché c'era abbastanza memoria fisica per andare in giro (anche se vedi "Memoria virtuale" sotto), numerosi programmi potrebbero essere supportati simultaneamente.

Inoltre, questi programmi non potevano accedere alla memoria che non era mappata nello spazio degli indirizzi virtuali - la protezione tra i programmi era automatica. Se i programmi dovevano comunicare, potevano chiedere al sistema operativo di predisporre un blocco di memoria condiviso - un blocco di memoria fisica mappato simultaneamente in due spazi di indirizzi di diversi programmi.

Dati sparsi

Consentendo un enorme spazio di indirizzamento virtuale (4 GB è tipico, per corrispondere ai registri a 32 bit che in genere hanno questi processori) non spreca di per sé la memoria, se ampie aree di tale spazio indirizzo non vengono mappate. Ciò consente la creazione di enormi strutture di dati in cui solo alcune parti vengono mappate in qualsiasi momento. Immagina una matrice tridimensionale di 1000 byte in ciascuna direzione: normalmente ci vorrebbe un miliardo di byte! Ma un programma potrebbe riservare un blocco del suo spazio di indirizzi virtuale per "contenere" questi dati, ma solo mappare le piccole sezioni mentre venivano popolate. Questo rende la programmazione efficiente, senza sprecare memoria per i dati che non sono ancora necessari.

Memoria virtuale

Sopra ho usato il termine "Indirizzamento virtuale" per descrivere l'indirizzamento da virtuale a fisico eseguito dall'hardware. Questo è spesso chiamato "Memoria virtuale", ma questo termine corrisponde più correttamente alla tecnica di utilizzo dell'indirizzamento virtuale per supportare l'illusione di avere più memoria di quella effettivamente disponibile.

Funziona così:

• Poiché i programmi vengono caricati e richiedono più memoria, il sistema operativo fornisce la memoria da ciò che è disponibile. Oltre a tenere traccia di quale memoria è stata mappata, il sistema operativo tiene traccia di quando viene effettivamente utilizzata la memoria - l'hardware supporta la marcatura delle pagine utilizzate.
• Quando il sistema operativo esaurisce la memoria fisica, guarda a tutta la memoria che ha già distribuito per qualsiasi pagina è stata utilizzata meno, o non era stata utilizzata più a lungo. Salva quel particolare contenuto della Pagina sul disco rigido, ricorda dove si trovava, lo contrassegna come "Non Presente" all'hardware per il proprietario originale, quindi azzera la Pagina e la consegna al nuovo proprietario.
• Se il proprietario originale tenta di accedere nuovamente a quella pagina, l'hardware notifica al sistema operativo. Quindi il sistema operativo assegna una nuova pagina (forse dovendo ripetere il passaggio precedente!), Carica il contenuto della vecchia pagina, quindi passa la nuova pagina al programma originale.

  Il punto importante da notare è che, dal momento che qualsiasi pagina può essere mappata a qualsiasi indirizzo, e ogni pagina ha le stesse dimensioni, una pagina è valida come qualsiasi altra, purché i contenuti rimangano gli stessi!

• Se un programma accede a una posizione di memoria non mappata, l'hardware informa il sistema operativo come prima. Questa volta, il sistema operativo rileva che non era una pagina che era stata salvata, quindi la riconosce come un bug nel programma e la interrompe!

  Questo è in realtà ciò che accade quando la tua app svanisce misteriosamente su di te, magari con un MessageBox dal sistema operativo. È anche ciò che accade (spesso) a causare un famigerato Blue Screen o Sad Mac: il programma buggy era in realtà un driver del sistema operativo che accedeva alla memoria che non dovrebbe farlo!

Decisioni di paging

Gli architetti dell'hardware dovevano prendere alcune grandi decisioni su Paging, dal momento che il design avrebbe influenzato direttamente il design della CPU! Un sistema molto flessibile avrebbe un sovraccarico elevato, richiedendo grandi quantità di memoria solo per gestire l'infrastruttura di paging stessa.

Quanto dovrebbe essere grande una pagina?

Nell'hardware, l'implementazione più semplice di Paging consisterebbe nel prendere un indirizzo e dividerlo in due parti. La parte superiore sarebbe un indicatore di quale pagina accedere, mentre la parte inferiore sarebbe l'indice nella pagina per il byte richiesto:

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

È diventato presto ovvio, anche se le pagine di piccole dimensioni richiedono enormi indici per ciascun programma: anche la memoria che non era mappata avrebbe bisogno di una voce nella tabella che lo indicasse.

Quindi, viene utilizzato un indice a più livelli. L'indirizzo è suddiviso in più parti (tre sono indicate nell'esempio seguente) e la parte superiore (comunemente chiamata "Directory") si indicizza nella parte successiva e così via fino a quando l'indice del byte finale nella pagina finale viene decodificato:

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

Ciò significa che un indice di directory può indicare "non mappato" per una vasta porzione dello spazio degli indirizzi, senza richiedere numerosi indici di pagina.

Come ottimizzare l'utilizzo delle tabelle delle pagine?

Ogni accesso agli indirizzi che la CPU produrrà dovrà essere mappato - il processo da virtuale a fisico deve quindi essere il più efficiente possibile. Se il sistema a tre livelli sopra descritto dovesse essere implementato, ciò significherebbe che ogni accesso alla memoria sarebbe in realtà tre accessi: uno nella Directory; uno nella tabella delle pagine; e infine i dati desiderati stessi. E se la CPU aveva bisogno di eseguire anche le pulizie, come ad esempio che indicava che questa pagina era stata ora utilizzata o scritta, allora sarebbe necessario avere ancora più accessi per aggiornare i campi.

La memoria potrebbe essere veloce, ma ciò imporrebbe un triplo rallentamento su tutti gli accessi alla memoria durante il paging! Fortunatamente, la maggior parte dei programmi ha una "località di visibilità" - cioè, se accedono a una posizione in memoria, gli accessi futuri saranno probabilmente nelle vicinanze. E poiché Pages non è troppo piccolo, quella conversione di mappatura dovrebbe essere eseguita solo quando si accede a una nuova pagina: non per assolutamente ogni accesso.

Ma ancora meglio sarebbe implementare una cache di pagine accessibili di recente, non solo la più recente. Il problema sarebbe tenere il passo con quello a cui era stato effettuato l'accesso a Pages e cosa no: l'hardware avrebbe dovuto eseguire la scansione della cache su ogni accesso per trovare il valore memorizzato nella cache. Quindi la cache è implementata come cache indirizzabile dal contenuto: invece di essere accessibile per indirizzo, è accessibile dal contenuto: se i dati richiesti sono presenti, viene offerto, altrimenti viene invece contrassegnata una posizione vuota per la compilazione. La cache gestisce tutto questo.

Questa cache content-addressable è spesso chiamata Translation Lookaside Buffer (TLB) ed è richiesta per essere gestita dal sistema operativo come parte del sottosistema dell'indirizzamento virtuale. Quando le directory o le tabelle delle pagine vengono modificate dal sistema operativo, è necessario notificare al TLB l'aggiornamento delle voci o semplicemente annullarle.

80386 Cercapersone

Design di alto livello

L'80386 è un processore a 32 bit, con uno spazio di memoria indirizzabile a 32 bit. I progettisti del sottosistema di paging hanno notato che un design di pagina 4K mappato in questi 32 bit in modo abbastanza accurato: 10 bit, 10 bit e 12 bit:

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

Ciò significava che l'indice Byte aveva una larghezza di 12 bit, il che indicava una pagina 4K. Gli indici Directory e Page erano 10 bit, ognuno dei quali sarebbe mappato in una tabella di 1.024 voci - e se quelle voci di tabella erano ogni 4 byte, sarebbe 4K per tabella: anche una pagina!

Quindi è quello che hanno fatto:

• Ogni programma avrebbe la propria Directory, una Pagina con 1.024 Page Entries che ognuno definiva dov'era il successivo Page Table - se ce n'era uno.
• Se c'era, quella Page Table avrebbe avuto 1024 Page Entries che ognuno definiva dove era l'ultima pagina - se ce n'era uno.
• Se c'era, allora quella pagina poteva avere il suo byte letto direttamente.

Voce della pagina

Sia la directory di primo livello che la tabella di pagine di livello successivo sono costituite da 1.024 voci di pagina. La parte più importante di queste voci è l'indirizzo di ciò che sta indicizzando: una Page Table o una Pagina effettiva. Si noti che questo indirizzo non ha bisogno dei 32 bit completi - poiché tutto è una pagina, solo i primi 20 bit sono significativi. Quindi gli altri 12 bit di Page Entry possono essere usati per altre cose: se il livello successivo è ancora presente; pulizia di se la pagina è stata letta o scritta; e anche se le scritture dovrebbero essere permesse!

+--------------+----+------+-----+---+---+
| 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

Notare che se il bit P è 0, il resto della voce può avere tutto ciò che l'OS vuole mettere lì - come dove il contenuto della Pagina dovrebbe essere sul disco rigido!

Pagina Directory Base Register ( PDBR )

Se ogni programma ha una propria directory, come fa l'hardware a sapere dove iniziare la mappatura? Poiché la CPU esegue un solo programma alla volta, ha un unico registro di controllo per contenere l'indirizzo della directory del programma corrente. Questo è il Page Base Base Register ( CR3 ). Mentre il sistema operativo scambia tra diversi programmi, aggiorna il PDBR con la relativa Directory Page per il programma.

Errori di pagina

Ogni volta che la CPU accede alla memoria, deve mappare l'indirizzo virtuale indicato nell'indirizzo fisico appropriato. Questo è un processo in tre fasi:

1. Indicizzare i primi 10 bit dell'indirizzo nella pagina indicata dal PDBR per ottenere l'indirizzo della tabella delle pagine appropriata;
2. Indicizzare i successivi 10 bit dell'indirizzo nella Pagina indicata dalla Directory per ottenere l'indirizzo della Pagina appropriata;
3. Indicizza gli ultimi 12 bit dell'indirizzo per estrarre i dati da quella pagina.

Poiché entrambi i passaggi 1. e 2. sopra utilizzano voci di pagina, ciascuna voce potrebbe indicare un problema:

• Il livello successivo può essere contrassegnato come "Non presente";
• Il livello successivo può essere contrassegnato come "Sola lettura" - e l'operazione è una Scrittura;
• Il livello successivo può essere contrassegnato come "Supervisore" - ed è il programma che accede alla memoria, non al sistema operativo.

Quando un problema di questo tipo viene rilevato dall'hardware, invece di completare l'accesso genera un errore: Interrupt # 14, l'errore di pagina. Riempie anche alcuni Registri di controllo specifici con le informazioni sul perché si è verificato l'errore: l'indirizzo di riferimento; se si trattasse di un accesso Supervisore; e se si trattasse di un tentativo di scrittura.

Ci si aspetta che il SO intrappoli quell'errore, decodifichi i registri di controllo e decida cosa fare. Se si tratta di un accesso non valido, può terminare il programma in errore. Se si tratta di un accesso alla memoria virtuale, tuttavia, il sistema operativo dovrebbe allocare una nuova pagina (che potrebbe dover svuotare una pagina già in uso!), Riempirla con i contenuti richiesti (o tutti gli zeri oi contenuti precedenti caricati di nuovo dal disco) ), mappare la nuova pagina nella tabella pagine appropriata, contrassegnarla come presente, quindi riprendere l'istruzione di errore. Questa volta l'accesso progredirà con successo e il programma procederà senza sapere che è successo qualcosa di speciale (a meno che non dia un'occhiata all'orologio!)

80486 Cercapersone

Il sottosistema di paging 80486 era molto simile a quello 80386. Era compatibile con le versioni precedenti e le uniche nuove funzionalità consistevano nel consentire il controllo della cache di memoria in base a una pagina - i progettisti del sistema operativo potevano contrassegnare pagine specifiche in modo da non essere memorizzate nella cache o utilizzare write-through o write-back diversi tecniche di caching.

In tutti gli altri aspetti, l'esempio "80386 Paging" è applicabile.

Pentium Paging

Quando il Pentium era in fase di sviluppo, le dimensioni della memoria e i programmi in essi contenuti aumentavano. Il sistema operativo doveva fare sempre più lavoro per mantenere il sottosistema di paging proprio nel numero degli indici di pagina che dovevano essere aggiornati quando venivano utilizzati programmi o insiemi di dati di grandi dimensioni.

I progettisti Pentium hanno quindi aggiunto un semplice trucco: hanno inserito un ulteriore elemento nelle voci della directory della pagina che indicava se il livello successivo era una Page Table (come prima) o se andava direttamente a una pagina di 4 MB! Avendo il concetto di 4 pagine MB, il sistema operativo non dovrebbe creare una tabella delle pagine e riempirla con 1.024 voci che erano sostanzialmente indici di indirizzamento 4K superiori a quella precedente.

Layout degli indirizzi

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

Layout di inserimento della directory

+-----------+----+---+------+-----+---+---+
| 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

Certamente, ciò ha avuto alcune ramificazioni:

• La pagina 4 MB doveva iniziare su un limite di 4 MB, proprio come le pagine 4K dovevano iniziare su un confine di indirizzo 4K.
• Tutti i 4 MB dovevano appartenere a un singolo programma o essere condivisi da più di un programma.

Ciò era perfetto per le periferiche con memoria di grandi dimensioni, come gli adattatori grafici, che avevano ampie finestre di spazio degli indirizzi che dovevano essere mappate per il sistema operativo.

Physical Address Extension (PAE)

introduzione

Con il crollo dei prezzi della memoria, i PC basati su Intel erano in grado di avere sempre più RAM in modo conveniente, alleviando i problemi di molti utenti con l'esecuzione di molte delle applicazioni sempre più grandi che venivano prodotte contemporaneamente. Mentre la memoria virtuale permetteva di "creare" virtualmente la memoria, scambiando il contenuto della pagina "vecchio" esistente sul disco rigido per consentire l'archiviazione dei "nuovi" dati - questo rallentava l'esecuzione dei programmi mentre il "thrashing" della pagina continuava a scambiare dati acceso e spento il disco rigido.

Più RAM

Ciò che era necessario era la possibilità di accedere a più RAM fisiche, ma era già un bus di indirizzi a 32 bit, quindi qualsiasi aumento richiederebbe registri di indirizzi più grandi. O lo farebbe? Quando si sviluppa il Pentium Pro (e anche il Pentium M), come stop-gap fino a quando non si possono produrre processori a 64 bit, per aggiungere più bit di indirizzo fisico (consentendo più memoria fisica) senza modificare il numero di bit di registro. Questo potrebbe essere ottenuto dal momento che gli indirizzi virtuali sono stati mappati su indirizzi fisici in ogni caso - tutto ciò che era necessario cambiare era il sistema di mappatura.

Design

Il sistema esistente poteva accedere a un massimo di 32 bit di indirizzi fisici. L'aumento di questo ha richiesto una modifica completa della struttura di Entry Page, da 32 a 64 bit. Si è deciso di mantenere la granularità minima alle pagine 4K, quindi la voce a 64 bit avrebbe avuto 52 bit di indirizzo e 12 bit di controllo (come la voce precedente aveva 20 bit di indirizzo e 12 bit di controllo).

Avere una voce a 64 bit, ma una dimensione di pagina di (ancora) 4K, significava che ci sarebbero solo 512 voci per pagina o directory, invece delle precedenti 1024. Ciò significava che l'indirizzo virtuale a 32 bit sarebbe stato diviso in modo diverso rispetto a prima:

+-----+-----------+------------+------------+
| 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)

Tagliare un bit dell'indice della directory e dell'indice della pagina ha dato due bit per un terzo livello di mappatura: lo hanno chiamato la Page Directory Pointer Table (PDPT), una tabella di esattamente quattro voci a 64 bit che indirizzavano quattro directory anziché la precedente uno. Il PDBR ( CR3 ) ora puntava invece al PDPT - che, dal momento che CR3 aveva solo 32 bit, doveva essere immagazzinato nei primi 4 GB di RAM per l'accessibilità. Si noti che poiché i bit bassi di CR3 vengono utilizzati per il controllo, PDPT deve iniziare su un limite di 32 byte.

Estensione dimensioni pagina (PSE)

E, dal momento che le precedenti 4 MB Pages erano una buona idea, volevano essere in grado di supportare nuovamente Pagine di grandi dimensioni. Questa volta però, la rimozione dell'ultimo livello del sistema di livelli non ha prodotto pagine 10 + 12 bit 4MB, ma 9 + 12 bit 2MB Pages.

PSE-32 (e PSE-40)

Poiché la modalità PAE (Physical Address Extension) introdotta nel Pentium Pro (e Pentum M) rappresentava una modifica del sottosistema di gestione della memoria del sistema operativo, quando Intel progettò il Pentium II decisero di migliorare la modalità di pagina "normale" in supportare i nuovi bit di indirizzo fisico del processore all'interno delle voci a 32 bit precedentemente definite.

Si sono resi conto che quando si utilizzava una pagina da 4 MB, la voce della directory appariva così:

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

Le aree di Dir Index e Control di Entry erano le stesse, ma il blocco di bit inutilizzati tra di loro - che sarebbe stato usato dall'Indice di pagine se esisteva - era sprecato. Quindi hanno deciso di usare quell'area per definire i bit superiori dell'indirizzo fisico sopra 31 !

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

Ciò ha consentito alla RAM oltre i 4 GB di essere accessibile ai sistemi operativi che non adottano la modalità PAE - con una piccola logica in più, potevano fornire grandi quantità di RAM extra al sistema, anche se non più dei normali 4 GB per ciascun programma. Inizialmente sono stati aggiunti solo 4 bit, consentendo l'indirizzamento fisico a 36 bit, quindi questa modalità è stata chiamata Page Size Extension 36 (PSE-36). In realtà non ha cambiato la dimensione della pagina, ma solo l'indirizzamento.

La limitazione di questo però era che solo le pagine da 4 MB superiori a 4 GB erano definibili: le pagine 4K non erano consentite. L'adozione di questa modalità non era ampia - si dice che fosse più lenta dell'utilizzo di PAE e Linux non l'ha mai usato.

Tuttavia, nei processori successivi che avevano ancora più bit di indirizzo fisico, sia AMD che Intel hanno ampliato l'area PSE a 8 bit, che alcune persone hanno soprannominato "PSE-40"