Heap implementation
It is said that dynamic memory in a program is allocated on the heap, and local variables are allocated on the stack. If everything seems to be clear from stack implementations, then how is the heap usually implemented in the OS? I know 3 known heap implementations: binary, binomial, and Fibonacci heap. Which one is used? How does new know the priority of the value being placed in the heap? It is clear that it depends on the implementation, but I would like to hear examples for linux and windows.
1 answers
Just because something is called a heap doesn't mean it can be a binomial or binary heap. It could be a pile of garbage.
This is usually how it works. The application requests a large chunk of memory from the operating system, and then the built-in memory manager (which is implemented inside the stl/glibc/CRT), cuts it into small portions. For most operating systems, it is difficult to ask for exactly 2-4 bytes of memory. They usually do not even allocate less than 4-16 kb.
In fact at a low level in Linux, the application cannot ask for "axis, give me a memory meter". There is only a special call to brk, which pushes the upper limit of memory for the process. That is, a process has a memory area with a fixed start and it can move the upper bound. What the application will do with the memory in this area is a personal matter for the application. Although there is still mmap, but this is a separate topic.
Windows has Heap which is quite similar to the usual one malloc/free.
Which one is used?
The funny thing is that the heap for memory is usually implemented on the basis of a linked list. You can study the code from the IBM site to understand how malloc/free works.
If you want to understand more deeply how it works, you can study various implementations of memory managers
It is possible on habr read.
P.S.
If everything seems to be clear from the stack implementations
I'm afraid not:)