• Advertisement
Sign in to follow this  

How does memory management work internally?

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My question is basically the one in the thread title, in general as both in an OS or program which decides to implement its own version of a malloc or new. However, to guide you into more what I want to know (any replies or references to sites/Google keywords could be helpful), I'll demonstrate with a simple example here. Assume we have somehow been given a sequential block of 100 bytes. Now, let's say we have one process requesting 40 bytes for something which are placed at the first bytes in the sequence. Then another process comes in and requests 2 bytes, and after that the original process requests another 40 bytes leaving 18 bytes left at the end. Now the memory should look something like this: 40 - Process 1 2 - Process 2 40 - Process 1 18 - Unused Now, let's say process 1 removes all its allocated memory which means 98 bytes are suddenly free. Great! What happens when a new third process decides to allocate 80 bytes? This is my problem. The obvious answer is to move the 2 bytes. However, all algorithmical solutions to this I can think of become woefully inefficient when there's megabytes of memory involved with many different blocks getting allocated and freed. Even the relatively simple procedure of moving the memory gets inefficient since there's large numbers of bytes involved. The greatest problem still remains though which is to determine where to move and from. I assume any memory manager keeps an internal list of blocks allocated: their sizes, positions and owners. Here I run into another problem, the one of the cyclical dependency. What if I want this list to grow? It is basically a block of memory as well, which has to be allocated somewhere. Does the memory management system handle its own memory this way alongside everything else? Because I really can't imagine there being a static limit on the number of available allocations (except for the actual physical memory restrictions given). If one program wants to allocate ten million 16 byte blocks it should be able to do so (which is a problem for a general memory manager since it cannot make assumptions about its callers). All solutions I have considered myself are way too impractical in terms of CPU time or memory use. Hence I figured I should research the topic a bit since the world out to have come a farther distance in this than I did. ;)

Share this post


Link to post
Share on other sites
Advertisement
Although I had some course on this, I don't recall much of it. However, I think processes get a (relatively large) block of memory assigned to them such that the memory interleaving (in order of allocation by different processes) does not occur. Moreover, it is immediately clear who the caller was.

The cyclic dependency is not a problem. If the memory manager can handle allocation requests from other applications, it will be able to handle its own. So any guiding structures can be grown and shrunk were necessary.

Perhaps this is not in much detail, but it might shed some light. I might also look up stuff in some books here, if you like.

Greetz,

Illco

Share this post


Link to post
Share on other sites
Systems such as Win32 and *nix, memory is virtual. This means the values returned from the allocators do not point to physical RAM locations. Therefore, the system can still efficently handle cases where there are large holes in the address space. One of two things happen when a memory access occurrs:

1. The page the address is in is mapped to physical RAM
On the CPU there's a unit called the MMU (memory management unit) which maps virtual pages (4K usually) to physical memory. If there is a mapping for the requested address, the memory is accessed without any delay.

2. The page the address is in is not mapped to physical RAM
In this instance, the CPU will generate a page fault. The OS catches this exception and either creates a new memory page if this is the first request or attempts to load the page from disk into a free memory page. In doing either of these, the OS may have to write a memory page to disk to free up the memory.

The CRT (C runtime library) actually allocates more memory than was requested by new/malloc. This extra memory mostly lies before the returned address and sometimes after the end of the allocated block. This memory is used to store the linked list pointers of allocated memory (if you have the CRT sources, you can see what this extra data contains). The CRT can also add a guard block - these are bytes immediately before and after the returned allocation - and then fills them with a know byte code. If this byte code changes when the block is freed, then there's been a memory under/over run.

At start up, the CRT is allocated all available memory by the OS (about 2GB in Win32). This doesn't allocate 2GB of virtual pages, as described above, pages are only allocated when the first access is made.

So, there is no cyclic problem. When a 'malloc (n)' call is made, the CRT looks for a free block of memory equal to 'n + sizeof of housekeeping'. If it can't find a block big enough, it fails and returns 0, otherwise it initialises the housekeeping data at the start of the block and any other blocks that need to be updated (next / previous blocks in list) and returns the start address of the block plus the size of the housekeeping data.

Skizz

Share this post


Link to post
Share on other sites
Quote:
Original post by Unwise owl
Now, let's say process 1 removes all its allocated memory which means 98 bytes are suddenly free. Great! What happens when a new third process decides to allocate 80 bytes?

This is called "fragmentation". In most allocators, your request for 80 bytes would simply fail. There are several techniques for reducing fragmentation, including the one you mention.
Quote:
Original post by Unwise owl
I assume any memory manager keeps an internal list of blocks allocated: their sizes, positions and owners. Here I run into another problem, the one of the cyclical dependency. What if I want this list to grow?

Actually, it is quite simple. Each allocated block also contains information about the allocation and a node in the list of allocated blocks (if there is such a list). Each unallocated block contains a node in the list of unallocated blocks.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement