This would be accurate for Linux. You'll find Windows, other Unix flavors, MSDOS, and rt/embedded OS's all use their own approaches. This is why I suggested getting several sources to study.
The usual is that the malloc gets big blocks from the OS and has a separate algorithm for allocating small blocks from the big ones. Again, strategies differ. I have not studied malloc implementations for about 10 years, but when I did, the "rotating first fit" was common. It is a very simple scheme that is O(N) where N is the number of free blocks available, but it can be implemented to be probabilistically constant time under reasonable assumptions. The free blocks are doubly linked in a circular free list. This means that the smallest block that can be allocated by malloc must hold two pointers (so it's 8 or 16 bytes). There is a single search pointer S into the circular list. When malloc is called, S is advanced around the list until the first block big enough to satisfy the request, including a small header for the block, is found. If this search fails, a new big block is obtained from the operating system and chained to the free list, S is set to the new block, and the search is restarted. Of course, normally the available block will be bigger than the request. It is removed from the list, the requested piece is allocated by filling in the header, which is normally just the size of the request and a pointer to the previous block, which is needed later. A pointer to the byte following the header is returned. The left-over smaller block (if any) is returned to the free list. When free is called, the freed block is placed on the free list. Checks are made to see if contiguous blocks before and/or after are already free. If so, the contiguous blocks are merged. Clever design of the header and the double links make it possible to do this merging in constant time. There are many possible enhancements to reduce the O(N) worst case performance of malloc. Each has advantages and disadvantages. There are also considerations for multi-threading support. There are variations on policy of returning memory to the OS if an entire big block is free. Etc. Etc. As I said, you must study examples. On Aug 16, 1:51 am, Mihai Donțu <mihai.do...@gmail.com> wrote: > On Monday 16 August 2010 06:48:56 Ashish Goel wrote: > > > do u have a refenrce for that, i am more interested in knowing how heap > > manager intracts with VMM > > Have a look at > this:http://mxr.mozilla.org/mozilla-central/source/memory/jemalloc/jemalloc.c > > Quoting from the Linux malloc(3) page: > "Normally, malloc() allocates memory from the heap, and adjusts the size of > the heap as required, using sbrk(2). When allocating blocks of memory larger > than MMAP_THRESHOLD bytes, the glibc malloc() implementation allocates the > memory as a private anonymous mapping using mmap(2). MMAP_THRESHOLD is 128 kB > by default, but is adjustable using mallopt(3). Allocations performed using > mmap(2) are unaffected by the RLIMIT_DATA resource limit (see getrlimit(2))." > > mmap() being the interaction you are looking for ... > > -- > Mihai Donțu -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
