Deterministic and controllable fully automated memory management

Fully automated memory management increases productivity and integrity greatly, but usual implementation (GC) has a critical problem. It’s non-deterministic, and not controllable. This causes many problems such as burst CPU load which is critical for realtime applications. Some kind of optimizations (incremental/concurrent GC) can reduce those problems but still non-deterministic and can’t eliminate the problem completely.

I have been thought GC never can solve this problem, but recently, I learned and realized that GC operation doesn’t need to be fully hidden. GC also can be deterministic and CPU burst-free by exposing some properly designed behavior controls.

I think (RC + manually invoked cycle detection) can do this. But this doesn’t look efficient. Is there any better approach for deterministic and controllable fully automatic memory management implementation? Or can I get some link to example implementations?

Edit

I added these lines to make my question more clear.

deterministic and controllable in this context means user can track and run code at object creation and destroying explicitly. And also controls amount and time of memory management operation load.
fully automatic means it allocates and clears memory as like GC without extra concern.

Let me re-phrase that.

“Is there any way I can get a memory management system which is absolutely perfect and has every desirable property?”.

No such systems exist.

The C++ RAII model gives you deterministic and automatic memory management (from the perspective of the library consumer). It’s not exactly what you’re looking for but it’s a start. Although it is an opt-in design where you must explicitly choose to use it with smart pointers. Theoretically a library user could know nothing of memory management, and get the same automatic clean up as in Java.

Maybe a language with “forced” RAII could approach what you are looking for.

The determinism of RAII is nice because it allows you to apply the same technique for resources even more precious than memory. Such as connections and handles.

void foobar()
{
    //connections are even more precious than memory. A leak is bad news.
    Connection conn("foobar");
    conn.Open();
}//conn is automatically closed as it leaves scope. Memory is free too.

There was a description by Butler Lampson in Hints for Computer System Design (Operating Systems Review 15, 5, Oct. 1983, p 33-48) of a system that combined both an incremental collector based on automatic reference counting and a trace-and-sweep collector that could clean up unreachable circular references. The idea is that an application could rely on the incremental collection to do most of the work, then do the “stop the world” garbage collection “used during coffee breaks to reclaim accumulated circular structures.”

This was, according to that paper, implemented in the Interlisp-D and Cedar programming environments. It cites the following two articles that I haven’t yet read but which—Lampson claims—describe the collector in more detail:

Burton, R.R. et al. Interlisp-D overview. In Papers on Interlisp-D, Technical report SSL-80-4, Xerox
Palo Alto Research Center, 1981.
Deutsch, L.P. and Bobrow, D.G. An efficient incremental automatic garbage collector. Comm. ACM
19, 9, Sep. 1976, pp 522-526.

IBM’s Metronome garbage collector for the JVM is deterministic. Basically, it runs continuously in parallel with the application. You specify how much CPU time it can use, with lower CPU time values requiring a larger heap. It isn’t suitable for applications that do a lot of heap thrashing, but for typical applications it supposedly works well.

Azul System’s C4 garbage collector for their Zing JVM appears to be similar, but I haven’t seen any technical details about how it works, so I don’t know if it’s fully deterministic or not.

All memory management systems have their trade-offs. As DeadMG’s answer points, you can’t have everything.

Here’s a quick guide to some of the trade-offs you can make, and some of the things you CAN have.

Note this isn’t necessarily comprehensive, but it’s a starting point on thinking about memory allocation/deallocation strategies.

1) Full bore manual – the nadir of determinism.

Upside: You decide when each piece of memory goes away. You’ll never get paused by a garbage collector!

Downside: You’ve GOT to do all the accounting for used memory your own self. And you’re likely to screw it up at some point, especially if you try to handle the cases where you need more memory and want to recover it from another part of your program on the fly.

Implemented in: C is the poster child for this one.

2) Deallocate on last reference drop

Upside: You can generally see where deallocation is going to happen, and plan for it appropriately. Since references are automatically cleaned up appropriately, you won’t accidentally lose memory. If you’ve got compiler support, you simply can’t screw up and lose memory.

Downside: If you forget or don’t realize that you’re dropping the last reference to a massive data structure, you can take a big hit at an inappropriate moment.

Implemented in: Perl 5, if I’m not mistaken. Also, if you use it correctly, you can emulate this in C++, though since there’s no compiler forcing of it, it’s not as safe.

3) Full-on GC

Updside: You don’t have to deal with it. Ask for objects, they show up and get cleaned up when you’re done with them. Eliminates all the hassle of accounting for memory – if there’s free memory, you’re good to go! By doing the deallocation in bigger chunks, this also reduces the total cost of the deallocations. If you do a lot of create/delete, that can actually be a good savings.

Downside: The garbage collector may end up locking the heap for extended periods of time. How long is a function of the implementation, but it’s going to be larger than any single deallocation. More complex GC algorithms lock for less time, but at the cost of increased complexity. In general you can’t do useful work based on object destruction, because the objects may well get destroyed at a time MUCH later than when it’s last been used (No RAII for you).

Implemented in: Java’s the GC platform I’m most familiar with. Older versions of Java had less capable GCs and bogged down a lot. Modern Java doesn’t do this much unless you’re doing something pathological.

It is possible to write in C / C++ your own memory manager, that meets the needs for your project. I have seen this done to solve the memory management bottleneck in a server application that had huge numbers of threads with each thread making and destroying large numbers of small objects. This app’s performance was limited by a critical section in the memory manager, and was solved by threads grabbing much larger blocks of memory and managing their own objects.

It is also possible to create an application in C/C++ that largely avoids using the heap for memory allocation. The application creates large fixed size arrays of objects at start up, so then only uses indexs to the array of that object type. I believe that this was a strategy in some big name computer games back in the 1990’s. It completely elminiates the problem of memory fragmentation, and with threads having their own cache of index numbers they can use, it reduces contention memory allocation.

Filed under: softwareengineering - @ 19:08

Thẻ: memory

Thiết kế website giá rẻ

Danh mục

Deterministic and controllable fully automated memory management