View previous topic :: View next topic |
Author |
Message |
AndyW
Joined: 17 Oct 2005 Posts: 9 Location: St. Louis, MO
|
Posted: Tue Oct 18, 2005 9:18 am Post subject: Garbage Collectors |
|
|
One of the first things the Titan might need is a garbage collector.
Many issues here. There are various GC strategies and implementations. Is this something that *should not* be done in the OS? I do not know the answer.
Let's get some chatter started and start trying answers, good or not. |
|
Back to top |
|
|
larsivi Site Admin
Joined: 27 Mar 2004 Posts: 453 Location: Trondheim, Norway
|
Posted: Tue Oct 18, 2005 12:32 pm Post subject: Re: Garbage Collectors |
|
|
AndyW wrote: | One of the first things the Titan might need is a garbage collector.
Many issues here. There are various GC strategies and implementations. Is this something that *should not* be done in the OS? I do not know the answer.
Let's get some chatter started and start trying answers, good or not. |
I do certainly not know the answer, but discussions on the NG seems to favour the GC as an OS service, including Walter Bright.
Having the OS control all memory, no matter what, might make it easier for other parts of the system, such as sharing of data in memory between processes and dynamic libraries.
Of course, having the GC in the OS, might make implications/complications for applications where the chosen GC strategy is a bad strategy. For those applications, it should probably be possible to either create sub-GC's using different strategies, or just give the application a blob of memory to control.
Just my two øre, I have no experience with making OS' or GCs whatsoever |
|
Back to top |
|
|
AndyW
Joined: 17 Oct 2005 Posts: 9 Location: St. Louis, MO
|
Posted: Tue Oct 18, 2005 12:34 pm Post subject: Garbage collection, from DigitalMars |
|
|
Walter thinks garbage collection should be part of the O/S. From DigitalMars: "Garbage collection should be implemented as a basic operating system kernel service".
Works for me. |
|
Back to top |
|
|
AndyW
Joined: 17 Oct 2005 Posts: 9 Location: St. Louis, MO
|
Posted: Tue Oct 18, 2005 1:13 pm Post subject: Too much in one bucket |
|
|
As I was reading DigitalMars conversations about garbage collectors, it seemed like there were several functions being performed, with different algorithms being proposed.
Mark and sweep algorithms seem to be easy to run simultaneously with memory consuming programs.
Copying algorithms have the advantage of cleaning up fractured free space.
Explicit deallocation by the programmer both solves problems, and creates problems. One thing it solves is that conservative garbage collection gets an explicit notice that at least the programmer thinks this thing is no longer needed. The problem is that if there are pointers to the thingy that the programmer tried to destroy, then we wind up with dangling pointers. Not good.
Conversely, when I destroy something, it is because I do not want it around anymore. This is more than a matter of being tidy and putting storage back when we are done using it. Finalizers do more than just garbage collection.
One of the things I really dislike about Java is the arbitrary timing of garbage collection. Unused objects can hang about for a long time. Small efficient pieces of code might be fine without garbage collection for a long time.
So three ideas here:
1) Identify and separate the various functionalities of garbage collection. If an object is explicity freed, it needs to be finalized, and non-memory resources released. If the programmer does not like that, too bad. He is in control of the process. Do not leave objects lying about after they have been explicitly freed, full of data. Initialize the silly things, or something, so that the data inside them is no longer useable. Help the garbage colletor by marking explicitly freed memory as available for collection.
2) Consider using Mark and Sweep algorithms to run concurrently with memory-consuming processes. If only a minute fraction of the real memory is being used, Mark and Sweep can be a waste of time, so load/timing is a consideration. Just be sure to understand, whichever algorithm we use, eventually somebody will tell us we used the wrong one.
3) Consider using copying algorithms during lax periods. Even SETI at home does not use all of a modern desktop's capabilities.
AndyW. |
|
Back to top |
|
|
pragma
Joined: 28 May 2004 Posts: 607 Location: Washington, DC
|
Posted: Tue Oct 18, 2005 2:33 pm Post subject: |
|
|
More information (sorry to break up Andy's current topic)
The idea of using a GC at the kernel level is a powerful one. I was mulling the idea over when it dawned on me that paging could be considered a key element in its design (provided we're not using the stock GC).
http://en.wikipedia.org/wiki/Page_?28computer_science?29
http://en.wikipedia.org/wiki/Page_replacement_algorithms
In reading about the page replacement algorithms, it became apparent to me that copying and defragmentation of memory could be accomplished by paging alone; the GC wouldn't have to bother. A drawback here is that it would all happen on page (typically 4k) boundaries. Also, it would all require a segmented memory model, rather than a flat memory space, which has ramifications for how programs are compiled (not really if everything is position independent).
Anyway, all this is a tad advanced for a prototype. You could code a very capable "oldschool" style OS that doesn't page at all: just use a flat memory space (up to the limit on RAM) and go from there. For all I know, this is what GRUB gives you at boot.
Also ran into this project, which is pretty bare-bones:
http://freedos-32.sourceforge.net/
.. and is what you'd expect. A flat memory model, no paging, and requires apps to be linked to a specific memory address within RAM (I'm suddenly reminded of my C64 days). They don't even have address translation yet, and have zero support for segmented memory models. _________________ -- !Eric.t.Anderton at gmail |
|
Back to top |
|
|
pragma
Joined: 28 May 2004 Posts: 607 Location: Washington, DC
|
Posted: Tue Oct 18, 2005 3:17 pm Post subject: |
|
|
I also found this wonderful gem on the topic of garbage collection and virtual memory (paging). Judging by their test system specs, I'd say this is *really* recent too. They also make mention of testing it as a 2.4 linux kernel modification, which proceeds to completely mop the floor with other kernel variants.
Page-Level Cooperative Garbage Collection:
http://www.cs.umass.edu/~emery/pubs/04-16.pdf
(Basically what they did is implement a mark-sweep-compact GC, for the entire OS, using memory paging. This strategy definately gets my vote for Titan.)
The parent site for that document also has a ton of other relevant papers:
http://www.cs.umass.edu/~emery/pubs/
On a more general note, these also look good for GC research:
http://www.cs.kent.ac.uk/people/staff/rej/gc.html
http://www.cs.kent.ac.uk/people/staff/rej/gcbib/gcbibA.html
(I would imagine that cross referencing titles in the bibliography with citeseer might save you a few trips to the public library or your local college stacks.) _________________ -- !Eric.t.Anderton at gmail |
|
Back to top |
|
|
Anthony
Joined: 26 Mar 2006 Posts: 2
|
|
Back to top |
|
|
JJR
Joined: 22 Feb 2004 Posts: 1104
|
Posted: Mon Mar 27, 2006 12:02 am Post subject: |
|
|
Heh... I remember reading about spin over 6 years ago, I think. It was one of the first operating system that used an experimental implementation of Modula-3 for it's development language. Modula-3 is a gc-based language that never really caught on (although, I was once quite fascinated with it).
-JJR |
|
Back to top |
|
|
Anthony
Joined: 26 Mar 2006 Posts: 2
|
Posted: Tue Mar 28, 2006 12:43 am Post subject: Modula-2 |
|
|
Modula-2 has produced the Oberon family and Bluebottle OS http://bluebottle.ethz.ch/ which is also not bad to look at for fun, with its active objects. Wirth is retired, but his students are carrying on with the language family. Anyway, languages aside, the above garbage collector uses page remapping to achieve the properties in the title, which would seem to make it worth a look. |
|
Back to top |
|
|
dan.lewis
Joined: 21 Feb 2007 Posts: 69 Location: Canada
|
Posted: Tue Apr 17, 2007 5:25 pm Post subject: |
|
|
Heh...
Putting the GC code in the kernel is against the exokernel philosophy. Instead, you should be able to define some external interface that GC's are expected to provide, and utilize that interface on the GC to make it do stuff. The actual code can be managed however (imported by modifying page tables, copying, far calls, interrupts, whatever)
Before calling it an exokernel, understand the concept. _________________ nop
nop ; problem solved |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|