FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Garbage Collectors

 
Post new topic   Reply to topic     Forum Index -> Titan
View previous topic :: View next topic  
Author Message
AndyW



Joined: 17 Oct 2005
Posts: 9
Location: St. Louis, MO

PostPosted: Tue Oct 18, 2005 9:18 am    Post subject: Garbage Collectors Reply with quote

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
View user's profile Send private message
larsivi
Site Admin


Joined: 27 Mar 2004
Posts: 453
Location: Trondheim, Norway

PostPosted: Tue Oct 18, 2005 12:32 pm    Post subject: Re: Garbage Collectors Reply with quote

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 Smile
Back to top
View user's profile Send private message
AndyW



Joined: 17 Oct 2005
Posts: 9
Location: St. Louis, MO

PostPosted: Tue Oct 18, 2005 12:34 pm    Post subject: Garbage collection, from DigitalMars Reply with quote

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
View user's profile Send private message
AndyW



Joined: 17 Oct 2005
Posts: 9
Location: St. Louis, MO

PostPosted: Tue Oct 18, 2005 1:13 pm    Post subject: Too much in one bucket Reply with quote

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
View user's profile Send private message
pragma



Joined: 28 May 2004
Posts: 607
Location: Washington, DC

PostPosted: Tue Oct 18, 2005 2:33 pm    Post subject: Reply with quote

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
View user's profile Send private message Yahoo Messenger
pragma



Joined: 28 May 2004
Posts: 607
Location: Washington, DC

PostPosted: Tue Oct 18, 2005 3:17 pm    Post subject: Reply with quote

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
View user's profile Send private message Yahoo Messenger
Anthony



Joined: 26 Mar 2006
Posts: 2

PostPosted: Sun Mar 26, 2006 10:58 pm    Post subject: A pointer Reply with quote

http://www.cs.washington.edu/homes/bershad/Papers/p118-lim.pdf A memory-efficient, real-time, non-copying garbage collector looks promising. Spin was an operating system that included an extensible kernel with garbage collection, so you should look at its design.

See also http://research.microsoft.com/os/singularity/Microsoft's Singularity Project and the recent tech report. The system borrows heavily from Inferno and related systems.[/url]
Back to top
View user's profile Send private message
JJR



Joined: 22 Feb 2004
Posts: 1104

PostPosted: Mon Mar 27, 2006 12:02 am    Post subject: Reply with quote

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
View user's profile Send private message
Anthony



Joined: 26 Mar 2006
Posts: 2

PostPosted: Tue Mar 28, 2006 12:43 am    Post subject: Modula-2 Reply with quote

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
View user's profile Send private message
dan.lewis



Joined: 21 Feb 2007
Posts: 69
Location: Canada

PostPosted: Tue Apr 17, 2007 5:25 pm    Post subject: Reply with quote

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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> Titan All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
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