Oltre a malloc / free un programma ha bisogno che il sistema operativo fornisca qualcos'altro?

StackOverflow https://stackoverflow.com/questions/196136

Domanda

Sto lavorando alla progettazione del kernel (che in realtà chiamerò "core" solo per essere diverso, ma sostanzialmente lo stesso) per un sistema operativo su cui sto lavorando. Le specifiche del sistema operativo stesso sono irrilevanti se non riesco a mettere in funzione il multi-tasking, la gestione della memoria e altre cose di base, quindi devo prima lavorare su quello. Ho alcuni questinos sulla progettazione di una routine malloc.

Immagino che malloc () sarà o una parte del kernel stesso (mi sto sporgendo verso questo) o una parte del programma, ma dovrò scrivere la mia implementazione del C libreria standard in entrambi i casi, quindi riesco a scrivere un malloc. La mia domanda è in realtà piuttosto semplice a questo proposito, come fa C (o C ++) a gestire il suo heap?

Ciò che mi è sempre stato insegnato nelle lezioni di teoreia è che l'heap è un pezzo di memoria in continua espansione, a partire da un indirizzo specificato, e in molti sensi si comporta come uno stack. In questo modo, so che le variabili dichiarate nell'ambito globale sono all'inizio e che più variabili vengono "spinte" sull'heap così come sono dichiarati nei rispettivi ambiti e le variabili che escono dall'ambito vengono semplicemente lasciate nello spazio di memoria, ma tale spazio è contrassegnato come libero in modo che l'heap possa espandersi di più se necessario.

Quello che devo sapere è, in che modo C gestisce effettivamente un mucchio in espansione dinamica in questo modo? Un programma C compilato effettua le proprie chiamate a una routine malloc e gestisce il proprio heap o devo fornire uno spazio in espansione automatica? Inoltre, come fa il programma C a sapere dove inizia l'heap?

Oh, e so che gli stessi concetti si applicano ad altre lingue, ma vorrei che qualsiasi esempio fosse in C / C ++ perché mi sento più a mio agio con quella lingua. Vorrei anche non preoccuparmi di altre cose come lo stack, poiché penso di essere in grado di gestire cose come questa da solo.

Quindi suppongo che la mia vera domanda sia, a parte malloc / free (che gestisce ottenere e liberare pagine per sé, ecc.) un programma ha bisogno che il sistema operativo fornisca qualcos'altro?

Grazie!

EDIT Sono più interessato a come C usa malloc in relazione all'heap che ai meccanismi reali della routine malloc stessa. Se aiuta, lo sto facendo su x86, ma C è cross-compilatore quindi non dovrebbe importare. ^ _ ^

MODIFICA PIÙ: Capisco che potrei essere confuso con i termini. Mi è stato insegnato che il "heap" era dove il programma memorizzava cose come variabili globali / locali. Sono abituato a gestire uno "stack" nella programmazione degli assiemi, e mi sono appena reso conto che probabilmente intendo questo invece. Una piccola ricerca da parte mia mostra che "heap" è più comunemente usato per fare riferimento alla memoria totale che un programma ha allocato per se stesso, o al numero totale (e all'ordine) di pagine di memoria fornite dal sistema operativo.

Quindi, con questo in mente, come posso gestire un stack in continua espansione? (sembra che la mia classe di teoria C sia stata leggermente ... imperfetta.)

È stato utile?

Soluzione

malloc è generalmente implementato nel runtime C nello spazio utente, basandosi su chiamate di sistema OS specifiche per mappare in pagine di memoria virtuale. Il compito di malloc e free è gestire quelle pagine di memoria, che sono di dimensioni fisse (in genere 4 KB, ma a volte più grandi), e tagliarle e tagliarle in pezzi che le applicazioni possono usare.

Vedi, ad esempio, l'implementazione della GNU libc .

Per un'implementazione molto più semplice, controlla la sistemi operativi MIT dall'ultima anno. In particolare, consulta il dispensa del laboratorio finale e dai un'occhiata a lib / malloc.c . Questo codice utilizza il sistema operativo JOS sviluppato nella classe. Il modo in cui funziona è che legge le tabelle delle pagine (fornite in sola lettura dal sistema operativo), alla ricerca di intervalli di indirizzi virtuali non mappati. Quindi utilizza le chiamate di sistema sys_page_alloc e sys_page_unmap per mappare e annullare il mapping delle pagine nel processo corrente.

Altri suggerimenti

Esistono diversi modi per affrontare il problema.

Molto spesso i programmi C hanno la loro funzionalità malloc / free. Quello funzionerà per i piccoli oggetti. Inizialmente (e non appena la memoria è esaurita) il gestore della memoria chiederà al sistema operativo più memoria. I metodi tradizionali per farlo sono mmap e sbrk sulle varianti unix (GlobalAlloc / LocalAlloc su Win32).

Ti suggerisco di dare un'occhiata al allocatore di memoria Doug Lea ( google: dlmalloc) dal punto di vista di un fornitore di memoria (ad es. SO). Quell'allocatore è di prim'ordine in un ottimo e ha ganci per tutti i principali sistemi operativi. Se vuoi sapere cosa si aspetta un allocatore ad alte prestazioni da un sistema operativo, questo è il codice che preferisci.

Stai confondendo l'heap e lo stack?

Chiedo perché menzioni "un pezzo di memoria in continua espansione", ambito e spingendo le variabili sull'heap man mano che vengono dichiarate. Sembra proprio che tu stia effettivamente parlando dello stack.

Nelle dichiarazioni di implementazioni C più comuni di variabili automatiche come

int i;

generano generalmente l'assegnazione in pila. In generale, malloc non sarà coinvolto se non lo invochi esplicitamente, o qualche chiamata in biblioteca che fai invoca.

Consiglio di guardare " Expert C Programming " di Peter Van Der Linden per informazioni generali su come i programmi C funzionano normalmente con lo stack e l'heap.

Lettura obbligatoria: Knuth - Art of Computer Programming, Volume 1, Chapter 2, Section 2.5. Altrimenti, potresti leggere Kernighan & amp; Ritchie " The C Programming Language " per vedere un'implementazione; oppure puoi leggere Plauger "La libreria C standard" per vedere un'altra implementazione.

Credo che ciò che devi fare all'interno del tuo core sarà leggermente diverso da quello che vedono i programmi al di fuori del core. In particolare, l'allocazione di memoria nel core per i programmi si occuperà della memoria virtuale, ecc., Mentre i programmi al di fuori del codice vedono semplicemente i risultati di ciò che il core ha fornito.

Leggi la gestione della memoria virtuale (paging). È altamente specifico per la CPU e ogni sistema operativo implementa la gestione della VM appositamente per ogni CPU supportata. Se stai scrivendo il tuo sistema operativo per x86 / amd64, leggi i rispettivi manuali.

Generalmente, la libreria C gestisce l'implementazione di malloc , richiedendo memoria dal sistema operativo (tramite mmap anonimo o, nei sistemi più vecchi, sbrk ) se necessario. Quindi il lato del kernel dovrebbe gestire l'allocazione di intere pagine tramite uno di questi mezzi.

Quindi tocca a malloc distribuire la memoria in modo da non frammentare troppo la memoria libera. Non sono troppo au fait con i dettagli di questo, però; tuttavia, viene in mente il termine arena . Se posso dare la caccia a un riferimento, aggiornerò questo post.

Pericolo Pericolo !! Se stai pensando di tentare lo sviluppo del kernel, dovresti essere molto consapevole del costo delle tue risorse e della loro disponibilità relativamente limitata ...

Una cosa sulla ricorsione è che è molto, costoso (almeno nella terra del kernel), non vedrai molte funzioni scritte semplicemente per continuare senza errori, altrimenti il ??tuo kernel sarà preso dal panico.

Per sottolineare il mio punto qui, (su stackoverflow.com heh), dai un'occhiata a questo post da Blog di debug NT sugli overflow dello stack del kernel, in particolare,

  

& # 183; Su piattaforme basate su x86, il   lo stack in modalità kernel è 12K .

     

& # 183; Su piattaforme x64, il   lo stack in modalità kernel è 24K . (X64   le piattaforme includono sistemi con   processori che utilizzano AMD64   architettura e processori che utilizzano il   Architettura Intel EM64T).

     

& # 183; Su piattaforme basate su Itanium, il   lo stack in modalità kernel è 32K con un 32K   negozio di supporto.

Questo è davvero, non molto;

  

I soliti sospetti

     
     

1. Usando lo stack liberamente.

     

2. Chiamare le funzioni in modo ricorsivo.

Se leggi un po 'sul blog, vedrai quanto può essere difficile lo sviluppo del kernel con una serie piuttosto singolare di problemi. La tua lezione di teoria non era sbagliata, era semplicemente semplice. ;)

Per passare dalla teoria - > lo sviluppo del kernel è il più significativo possibile di uno switch contesto (forse salvare qualche interazione dell'hypervisor nel mix !!).

Comunque, non assumere mai, convalidare e testare le tue aspettative.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top