Outros que malloc / free é que uma necessidade programa do sistema operacional para fornecer qualquer outra coisa?

Question

Eu estou trabalhando em projetar o kernel (que eu vou realmente chamar o "núcleo" apenas para ser diferente, mas é basicamente o mesmo) para um sistema operacional que estou trabalhando. As especificidades do próprio sistema operacional são irrelevantes se não pode obter multi-tasking, gerenciamento de memória e outras coisas básicas instalado e funcionando, então eu preciso trabalhar nisso primeiro. Eu tenho algumas questinos sobre a criação de uma rotina malloc.

Figura I que malloc () é ou vai ser uma parte do próprio kernel (Estou inclinado para isso) ou de uma parte do programa, mas eu vou ter que escrever a minha própria implementação do C padrão biblioteca de qualquer forma, assim que eu consigo escrever uma malloc. A minha pergunta é realmente bastante simples, a este respeito, como é C (ou C ++) gerenciar seu acervo?

O que eu sempre fui ensinado em theorey classes é que a pilha é uma peça cada vez maior de memória, a partir de um endereço especificado, e em muitos sentidos se comportando como uma pilha. Desta forma, eu sei que as variáveis ??declaradas no escopo global estão no início, e mais variáveis ??são "empurrados" para a pilha como eles são declarados em seus respectivos âmbitos, e as variáveis ??que vão fora do escopo são simplesmente deixados no espaço de memória, mas esse espaço é marcado como livre assim que a pilha pode expandir mais se precisa.

O que eu preciso saber é, como na terra faz C realmente lidar com um monte de expansão dinâmica desta maneira? Será que um programa C compilado tomar suas próprias chamadas para uma rotina malloc e lidar com a sua própria pilha, ou que eu preciso para fornecer-lhe um espaço de expansão automaticamente? Além disso, como é que o know programa C, onde a pilha começa?

Oh, e eu sei que os mesmos conceitos se aplicam a outros idiomas, mas eu gostaria de quaisquer exemplos para estar em C / C ++, porque eu sou mais confortável com essa linguagem. Eu também gostaria de não se preocupar com outras coisas, como a pilha, como eu acho que eu sou capaz de lidar com coisas como esta em meu próprio.

Então eu acho que minha verdadeira questão é, que não malloc / free (que alças recebendo e liberando páginas por si, etc) é que uma necessidade programa do sistema operacional para fornecer qualquer outra coisa?

Obrigado!

Editar Estou mais interessado em saber como C usa malloc em relação com a pilha do que no funcionamento real da própria rotina malloc. Se ajudar, eu estou fazendo isso em x86, mas C é compilador cruzado por isso não deveria importar. ^ _ ^

editar mais: Eu entendo que pode estar recebendo termos confusos. Eu fui ensinado que a "pilha" era onde o programa armazenado coisas como variáveis ??globais / locais. Eu estou acostumado a lidar com uma "pilha" na programação de montagem, e eu só percebi que eu provavelmente significa que em vez. Um pouco de pesquisa da minha parte mostra que "pilha" é mais comumente usado para se referir ao total de memória que um programa alocou para si mesmo, ou, o número total (e ordem) de páginas de memória do sistema operacional tem prestado.

Então, com isso em mente, como faço para lidar com uma cada vez maior pilha ? (Parece que minha classe teoria C foi levemente ... falho.)

Answer 1

malloc geralmente é implementado no tempo de execução C em userspace, contando com chamadas de sistema OS específicos para mapear em páginas de memória virtual. O trabalho de malloc e free é gerenciar as páginas de memória, que são fixos em tamanho (geralmente 4 KB, mas às vezes maior), e para cortar e cortar em pedaços que os aplicativos podem usar.

Veja, por exemplo, o GNU libc implementação.

Para uma implementação muito mais simples, confira o MIT operando classe sistemas do último ano. Especificamente, consulte o laboratório última apostila e dar uma olhada em lib/malloc.c. Esse código usa os JOS sistema operacional desenvolvido na classe. O modo como funciona é que ele lê através das tabelas de páginas (fornecidos somente leitura pelo sistema operacional), procurando intervalos de endereços virtuais não mapeados. Em seguida, usa as chamadas sys_page_alloc e do sistema sys_page_unmap para mapear e páginas unmap no processo atual.

Answer 2

Existem várias maneiras de resolver o problema.

Na maioria das vezes programas em C tem sua funcionalidade própria malloc / free. Que será um trabalho para os pequenos objetos. Inicialmente (e, logo que a memória está esgotada) o gerenciador de memória irá pedir ao sistema operacional para mais memória. Os métodos tradicionais para fazer isso são mmap e sbrk no unix variantes (GlobalAlloc / LocalAlloc em Win32).

Eu sugiro que você dê uma olhada na Doug Lea memória alocador ( google: dlmalloc) a partir de um provedor de memória por exemplo, OS ponto de vista (). Que alocador é top de linha em um muito bom e tem ganchos para todos os principais sistemas de operação. Se você quer saber o que um alto desempenho espera alocador de um sistema operacional Este é o código é a sua primeira escolha.

Answer 3

Você está confundindo a pilha e a pilha?

Eu pergunto porque você menciona "um pedaço cada vez maior de memória", escopo e variáveis ??empurrando na pilha como eles são declarados. Isso soa como você está realmente falando sobre a pilha.

Na maioria dos comum C implementações declarações de variáveis ??automáticas como

int i;

são geralmente vai resultar em i sendo alocados na pilha. Em malloc geral não vai se envolver, a menos que explicitamente invocá-lo, ou alguma chamada de biblioteca que você faça o invoca.

Eu recomendo olhar "Expert C Programming" por Peter Van Der Linden para o fundo sobre como programas em C normalmente trabalho com a pilha eo heap.

Answer 4

Bibliografia: Knuth - Art of Computer Programming, Volume 1, Capítulo 2, Seção 2.5. Caso contrário, você poderia ler Kernighan & Ritchie "The C Programming Language" para ver uma implementação; ou, você pode ler Plauger "The Standard C Library" para ver outra implementação.

Eu acredito que o que você precisa fazer dentro do seu núcleo será um pouco diferente do que os programas fora do núcleo ver. Em particular, a alocação de memória no interior do núcleo para programas será lidar com a memória virtual, etc, enquanto que os programas fora do código simplesmente ver os resultados do que o núcleo tem prestado.

Answer 5

Leia sobre gerenciamento de memória virtual (paginação). É específico CPU-altamente, e cada gestão implementos OS VM especialmente para cada CPU suportadas. Se você estiver escrevendo o seu sistema operacional para x86 / amd64, leia seus respectivos manuais.

Answer 6

Geralmente, a biblioteca C lida com a implementação de malloc, solicitando memória do sistema operacional (via mmap anónima ou, em sistemas mais antigos, sbrk) conforme necessário. Então lado kernel do seu coisas devem lidar com alocação de páginas inteiras através de algo como um desses meios.

Em seguida, cabe a malloc para distribuir a memória de uma forma que não fragmentar a memória livre demais. Eu não estou muito au fait com os detalhes desta, embora; no entanto, o termo Arena vem à mente. Se eu puder caçar uma referência, eu vou atualizar este post.

Answer 7

Danger Danger !! Se o seu mesmo considerando a tentativa desenvolvimento do kernel, você deve estar muito consciente do custo de seus recursos e sua disponibilidade relativamente limitada ...

Uma coisa sobre recursão, é que é muito, caro (pelo menos em terra kernel), você não vai ver muitas funções escritas simplesmente continuar unabaided, ou então o seu kernel irá entrar em pânico.

Para sublinhado meu ponto aqui, (pelo stackoverflow.com heh), confira este post do NT depuração blogue sobre kernel do estouro de pilha de, specificially,

· Em plataformas x86, o pilha de modo kernel é 12K .

· Em plataformas baseadas em x64, o pilha de modo kernel é 24K . (64 x- plataformas incluem sistemas com processadores usando o AMD64 Arquitectura e processadores usando o Intel EM64T arquitetura).

Plataformas · baseados em Itanium On, o pilha de modo kernel é 32K com 32K backing loja.

Isso é realmente, não um lote inteiro;

Os Suspeitos

---

1. Usando a pilha liberalmente.

2. Chamar funções de forma recursiva.

Se você ler sobre o blog um pouco, você vai ver o quão duro o desenvolvimento do kernel pode ser com um conjunto bastante singular de questões. Você está classe teoria não estava errado, era simplesmente, simples. ;)

Para passar da teoria -> desenvolvimento do kernel é tão significativa de um contexto interruptor de como é possível (talvez salvar alguma interação hypervisor no mix !!)

.

De qualquer forma, nunca assumir, validar e testar as suas expectativas.