Hello, I would like to know how memory allocation on the lowest levels works. For example if program wants to create some long array or anything else, how it will ask for the memory, how does the program ensure itself that it does not take memory same other program is using.
I would be very grateful if someone would bring some light for me into this matter.
To the best of my understanding (on UNIX at least) the program in question makes a call into the system library for memory (e.g. malloc and friends). These libraries maintain a list of free memory blocks in the program's virtual address space and dole out memory from this list (this is an oversimplification, the methods in which they maintain this list and deal with word alignment, consecutive block, etc. are fairly complex). As for making sure that programs don't touch each other's memory, the OS has a concept of virtual memory, which essentially maps addressable memory for each program to different segements of the physical memory. See http://en.wikipedia.org/wiki/Virtual_memory for more info.
Memory can be allocated in a number of ways...the two broad ways being static and dynamically allocated.
Static allocation means that all the memory that can be used by a program is allocated at once, and it is able to use up to that amount.
Dynamic allocation means that when the program needs to allocate memory, it goes to the heap and puts a pointer at the first available chunk of memory (specified in size according to the dynamic allocation algorith in use). Then, as it needs (such as in an array) it takes more, maintaining the pointer at that original spot so it knows where the beginning of the array is. Modern computers usually do a good job of allocating resources including memory to applications, which reduces the chance of deadlock. On a higher level, garbage collection takes care of this memory when the object/array/whatever can be removed from memory.
The problem here is that when free memory is given and freed at will, different programs can grab different chunks which aren't necessarily in order. This is what we call fragmentation (which is why you defrag your disk drive every now and then). When memory is allocated in a contiguous fashion, it can be read more efficiently.
There's a huge amount of information on memory, so here is a minute amount of data for you to allocate in your own memory ;)
Wiki Link to OSDev on Dynamic Allocation
Dynamic allocation in C++
Memory in C (This is kind of low level yet easy to understand)
Happy reading!
The simplest solution would be to not allow freeing of allocated memory. Assume the the operating system has a heap of memory it knows is available for programs to allocate from. The operating system keeps track of an address at the start of this free area. if there is enough memory available for the first alloc that alloc gets the free pointer address and the free pointer moves forward by the amount of the alloc. And this continues to move forward until there is no more memory or nobody allocates any more. so if the starting address was 0x1000 and someone wanted 0x20 bytes they would get 0x1000 returned as the pointer for the alloc and the free pointer moves to 0x1020. The next alloc of say 0x100 returns 0x1020 and the free pointer moves to 0x1120, etc.
You could also work down from a high address, top down instead of bottom up. Top of memory might be 0x10000, first alloc of 0x20 results in 0x10000-0x20 = 0xFFE0 so 0xFFE0 is sent to the application and is also saved as the top of free memory. The 0x100 alloc gets 0xFEE0, etc.
The problem with this simplistic idea, never freeing memory, is that you run out of memory quickly. By that time much if it may have been orphaned by programs that have completed. so it might work in some embedded systems, but in general something more has to be done.
So not unlike a file system a table has to be maintained by the memory allocation system (operating system) that contains at least the start address and amount of data allocated for each alloc that has occured. Then some sort of search algorithm goes through that list trying to determine open chunks of memory with which to complete an alloc. When a free happens then it might be a simple manner of finding the entry with a matching address and deleting it from the table. Making a table structure that is fast to parse, sort, whatever, but also allows for small and large allocs without too much wasted memory.
Mmus can make this much easier, partly because they are driven by tables already, the hardware navigates the mmu table to find the physical address among other things. The big feature here is that you can take chunks of memory that are not next to each other in physical address space but can be placed linearly in virtual address space. So your application may want 12345 bytes, and your mmu system may have its smallest memory division being 4kbytes, so you simply need to find four free chunks of memory that dont have to be remotely near each other, you do have to find four mmu table entries that are next to each other, and you can point those four mmu entries at the four separate physical entries creating a 16kbyte space which is allocated to that application. You still need some other table outside the mmu system that tells you these four mmu entries are part of the same allocated space. This is not unlike a file system where a 12345 byte file might be stored in 4 4096 byte sectors that are not necessarily next to each other on the disk. The directory structure and file system tables use a link list or some other method of keeping track of what sectors are consumed by that one file.
As far as the management of that memory, what physical address to choose, etc. Well over the decades of operating systems there are have been countless solutions, countless hours of experiments and research. Think about the host at a restaurant. You come in with three people and want a table. How many different ways have you seen the table chosen? Sometimes they have a chart and a wax pencil, sometimes they just wander into the seating area and find a table. You may or may not realise but sometimes they are not just trying to find any four top hopefully and in desperation six top, but they are also trying to balance the number of customers per waiter/waitress. They are probably also trying to leave chunks of tables available just in case a 8 or 10 person party comes in they can push tables together. For as many different restaurants and hosts there are there may be as many different solutions for allocating a table for your party. Likewise from the early timeshare computers to the present there have been as many different solutions for memory allocation.
There is nothing to stop you from trying this out yourself. Write a program that takes a chunk of memory and make your own malloc and free routines that try to divide that chunk of memory up to serve the malloc and frees, and maybe take a randomiser and use it to call your malloc and free routines.
Assuming you are approaching this subject from the point of view of a user mode programmer, there are two parts two this answer:
malloc() or something similar that your code calls will be a user mode library that manages usually a heap data structure. The simplest allocator will just call a system/kernel function usually called brk(...) which returns a block of memory of the desired size. However making a system call every time your app wants memory is expensive. So your malloc library takes a large chunk from brk() and manages it in a heap and returns small pieces from there.
This is the brk implementation. At a high level, a process descriptor has a list of "memory areas" that make up its used address space. brk() basically allocates a block of pages frames to grow the data segment. How it allocates the page frames, and for a discussion on page frames, is probably out of scope of this question but if you'd like to go further do ask.