OSDev.org

I thought of a way of allocating memory, that would avoid any fragmentation, but is slow.

Think of memory like water in a cup. When you allocate memory, you poor water into the cup. When you want to free memory, you remove part of the water, and the rest flows to the bottom.

I'm not sure if that's the clearest example, but my idea of a memory manager is the following:

• A variable, such as memStackEnd, initially refers to the beginning of the free space.
  When malloc is called, memory is allocated at the position memStackEnd is located at, and memStackEnd is increased by the size allocated, referring to the beginning of the free memory.
  When free is called, all memory above the block is automatically copied down.

Freeing memory may take a while, but as technology has advanced, it may be feseable to do so, and it removes all possibilities of fragmentation.

When freeing memory, the pointers above the freed memory will be rendered invalid, I haven't thought of a solution to this problem yet.

Does any one know how the garbage collection in Java and .NET work? I like the idea in .NET of ArrayLists, where any object of any size can be added or removed from any point within the array without any (noticable) fragmentation, and I was thinking something along that sort could be applied in an operating system.

Hi.

Does any one know how the garbage collection in Java and .NET work? I like the idea in .NET of ArrayLists, where any object of any size can be added or removed from any point within the array without any (noticable) fragmentation, and I was thinking something along that sort could be applied in an operating system.

I only know 2 versions of garbage collection in Java.Maybe I cannot describe them very accurately in specific terms or even misunderstand some points...

Version 1
This version is based on reference counter.Every object at runtime has such a counter.For example,if object A creates(requests) a new reference(link) which points to object B,then B's counter will be increased by one.And if one of A's references to B is set to other objects or null,B's counter will be decreased by one.It's not hard to understand,but if 2 objects both have a reference to each other and there're no external reference to either of them,the garbage collection may not identify this occasion and will not free the memory they've taken up(it can test this but in a way which takes too much time).

Version 2
This one seems to be used more widely.
Since the live objects have got one or several references pointing to others as well as been involved by others,all these references together make up a network,just like that many linked lists mix together.If we find one reference(as an entry to the linked list),we can certainly find many more objects through one or several reference layers(e.g. ObjA.ObjB.Obj.C,etc. ignoring accessing control because it's the system prospective).In this way,all the objects in use will be found,avoiding the inter-reference situation in Version 1.(But still one thing I don't understand:how does the JVM locate the entry?)
Since we have such a method to go through and find out all the objects to remain,we can have several methods to deal with them.In some JVMs,the objects to be reserved will be marked and dealt with in different ways.Only when it's necessary(e.g. the free memory is very little) will the garbage collection delete the unmarked ones(to free the memory they take up) and re-arrange the marked ones(e.g. move them to another heap or put them in a better order).I heard that Sun's earlier JVMs used self-adaptive(is it called so?I'm not sure...) mechanism for that.The marking is executed along with Java applications' execution but when deleting the garbage objects and re-arrange the remaining ones the JVM will stop the application and do this in front.(Luckily this won't happen continuously as the marking work does.)

Anyway I recommend reading some documents about that.

MessiahAndrw wrote:I thought of a way of allocating memory, that would avoid any fragmentation, but is slow.

Think of memory like water in a cup. When you allocate memory, you poor water into the cup. When you want to free memory, you remove part of the water, and the rest flows to the bottom.

I'm not sure if that's the clearest example, but my idea of a memory manager is the following:

• A variable, such as memStackEnd, initially refers to the beginning of the free space.
  When malloc is called, memory is allocated at the position memStackEnd is located at, and memStackEnd is increased by the size allocated, referring to the beginning of the free memory.
  When free is called, all memory above the block is automatically copied down.

Freeing memory may take a while, but as technology has advanced, it may be feseable to do so, and it removes all possibilities of fragmentation.

When freeing memory, the pointers above the freed memory will be rendered invalid, I haven't thought of a solution to this problem yet.

Well, this comes to the problem, when you copy memory down to the new location, you must update any and all pointers to memory as well! Think of it this way, a have a huge array allocated in memory, then after this is allocated I create a linked list of sorts (tons of pointers), then I free the really huge array of allocated memory. If you move memory around, the linked list is no longer valid, so you would have to store a pointer to every single pointer in memory as well, then traverse this list and patch the pointer as necessary. This would require making major modifications to your compiler (for example, whenever you set a pointer to a location, it would have to call a function in your memory manager to change this pointers memory location), anytime a new pointer is created you would have to track it and do the same, not just add it to the list, but any time it changes you would have to update it. The overhead involved is probably not worth the effort, the memory you are saving by having it contigous is being wasted storing lists and lists of pointers. The way I am trying to minimize fragmentation is to allocate memory blocks when memory is asked for, of sizes no smaller than a designated size (testing will hopefully point me to the correct size to use for this). Any allocations smaller than that will be sent to a pool allocator of a specified size (closest fit). The first time I create a pool, I find open chunks of random sized memory and use them to store the pool, thus being able to use these otherwise unuseable small blocks of memory. This will not eliminate the problem, but it will help use a little bit more of the memory that normally gets unused, especially for a byte allocator, etc.

MessiahAndrw wrote:... Does any one know how the garbage collection in Java and .NET work? ...

According to this page on OSFAQ2 GarbageCollection, the garbage collector in Java and .NET does exactly what you described, namely the copy (or compacting) collector. (don't know how correct the page is)

Ready4Dis wrote: Well, this comes to the problem, when you copy memory down to the new location, you must update any and all pointers to memory as well!

The only pointers I'll have to update are those in the kernel. Pointers in userland should only refer to virtual memory addresses, which can be easily remapped.

MessiahAndrw wrote:When freeing memory, the pointers above the freed memory will be rendered invalid, I haven't thought of a solution to this problem yet.

All pointers to the moved memory would be invalid. When you are coding at operating system level, the way to fix that is presumably to use the processor's paging mechanism.

MessiahAndrw wrote:

Ready4Dis wrote: Well, this comes to the problem, when you copy memory down to the new location, you must update any and all pointers to memory as well!

The only pointers I'll have to update are those in the kernel. Pointers in userland should only refer to virtual memory addresses, which can be easily remapped.

Ok, if that's the case, then you will just have to update all the page table and page directory entries for each process that moved . But, for example, I am more worried about not wasting virtual memory, since each page that is open must be either 4k or 64k depending on mode, then allocating 8 bytes, and wasting the rest of the memory is a HUGE waste, having fragmentation in physical memory isn't as big of a deal, since you can easily allocate multiple fragmented pages into one contiguous virtual memory location. I don't understand what you are trying to accomplish I guess .

Unless you know of ALL pointers in programs, and you are able to change them, you can always code in such a fashion that fragmentation will occur. The only way to minimalize this, is when you want some memory you try to allocate it in those pages that are not fully used.

Yeah, I still don't see how your idea will work without a list of pointers to every pointer, say you have 2k of a page allocated to one variable, and the rest of it in another. If you free the first 2k of that page, you cannot copy memory back, because that virtual memory page still points to the beginning of the page, so you would have to leave it as is unless you could modify the second pointer to point to the beginning of the page instead of the middle. If you were talking about page granularity, there isn't even really a reason to do this .

m wrote:Version 1
This version is based on reference counter.Every object at runtime has such a counter.For example,if object A creates(requests) a new reference(link) which points to object B,then B's counter will be increased by one.And if one of A's references to B is set to other objects or null,B's counter will be decreased by one.It's not hard to understand,but if 2 objects both have a reference to each other and there're no external reference to either of them,the garbage collection may not identify this occasion and will not free the memory they've taken up(it can test this but in a way which takes too much time).

Often also called Smartpointer.

As I don't have much time atm, for garbage collection I throw the words Stop & Compact and Mark & Sweep into the room.

MessiahAndrw wrote: Freeing memory may take a while, but as technology has advanced, it may be feseable to do so, and it removes all possibilities of fragmentation.

When freeing memory, the pointers above the freed memory will be rendered invalid, I haven't thought of a solution to this problem yet.

I've worked with several embedded systems that use a similar approach, but couple it with a lock/unlock pointer system.

For example:
MemoryHandle getVideoFrameBuffer();

Would return an opaque pointer. You can't really do anything with it until you lock it:
void * lockHandle(MemoryHandle);

You can then access this memory directory and, when done, unlock it:
unlockHandle(MemoryHandle);

The trick here is that, after unlocking, the pointer returned by lockHandle() can now, no longer, be considered valid. This is because any unlocked handle can be moved anywhere inside memory without the users/clients knowledge.

With a system like this, as long as the user keeps unused handles in the unlocked state, they can be moved in order to prevent fragmentation.

Generally speaking, these systems will only perform memory block movement when they're running low on memory, or when an allocation fails because there isn't a large enough contiguous block, but there is enough free memory available.

And btw, the second garbage collection method mentioned below looks to be "mark & sweep," upon a very quick scan of the description. This is a fairly common GC method.

However, keep in mind that GC in C is more difficult then in Java. In Java everything is accessed via an indirect object handle and the stack is managed by the vm itself. In C, memory is accessed directly through pointers, and the stack can be managed by the application.

Trying to find if an object is referenced in the Java stack often involves iterating through all the active objects and their references. In C, it seems like you'd have to iterate through all the available registers, any buffers pointed to by the registers, and the same for the stack. On top of that, you have to be smart to notice values offset from the original pointer -- if a register contains (ptr + 4), you'll probably want to consider ptr as being referenced and not eligible for GC.

--Jeff