Kernel level garbage-collection discussion

[Synon]

It's an idea I'm interested in - an OS with a garbage collector for the entire system. There'd be no memory leaks at all and no process would have to worry about freeing its own memory. Of course there would be performance issues, but with the right algorithm, maybe they wouldn't be prohibitive.

Has anyone tried this or anything similar? How well did it work? How well do you think it would work if not?

[bluemoon]

It's an idea I'm interested in - an OS with a garbage collector for the entire system. There'd be no memory leaks at all and no process would have to worry about freeing its own memory. Of course there would be performance issues, but with the right algorithm, maybe they wouldn't be prohibitive.

Why do you think there will be no memory leak with GC? In case of mismatch of retain/release of objects, well, you may not call that memory leak but the end result is the same - something never be collected.

[Mikemk]

There are several open source projects attempting to do this. Cosmos is a notable example. So is Singularity, but I don't have a link for that

[Combuster]

There'd be no memory leaks at all and no process would have to worry about freeing its own memory.

Managed languages can prefectly leak memory as well, just not in the sense of a traditional C program where you forget to deallocate something but rather where you keep a reference to an object you don't actually use.

Memory management will always be a programmer topic. There's just more or less help.

[Synon]

@bluemoon, Combuster
Oh, yeah, true.

@m12
Thanks, I'll check those out.

[linguofreak]

Also, note that kernel-level garbage collection will just affect the kernel: for all applications to be garbage collected, there has to be garbage collection support in userspace, as that's where memory management visible to the application-level programmer generally happens. (And someone could always just write a compiler for a non garbage-collected language that didn't use any of the system runtime libraries and made memory management calls to the kernel directly).

[Synon]

Also, note that kernel-level garbage collection will just affect the kernel: for all applications to be garbage collected, there has to be garbage collection support in userspace, as that's where memory management visible to the application-level programmer generally happens. (And someone could always just write a compiler for a non garbage-collected language that didn't use any of the system runtime libraries and made memory management calls to the kernel directly).

What if you had the GC built into the memory manager so that there was no way to allocate memory without it being marked for GC? I'd make it possible to manually delete memory as well to allow for things like the try-with-resources statement in Java or the using statement in C#, but any memory that wasn't deleted and wasn't referenced would eventually be collected. The only problem with this that I can see is that it might be very slow to have the kernel scanning every process' entire address space for references to every heap allocation, but like I said, with the right algorithm maybe it wouldn't be that bad.

[bluemoon]

but any memory that wasn't deleted and wasn't referenced would eventually be collected.

If by that "eventually" you meant process ends, this also holds for traditional memory manager, eventually, when process ends, everything in the process's scope will be collected.
Otherwise, there is always program bugs for not releasing reference, and the GC or memory manager has no way to identify such object is no longer useful and reclaim it.

[Synon]

but any memory that wasn't deleted and wasn't referenced would eventually be collected.

If by that "eventually" you meant process ends, this also holds for traditional memory manager, eventually, when process ends, everything in the process's scope will be collected.
Otherwise, there is always program bugs for not releasing reference, and the GC or memory manager has no way to identify such object is no longer useful and reclaim it.

No, I know that OSes free all the memory used by a process when said process ends, and that's not what I meant. My idea is this. If you're using Windows, look in the Task Manager and find the System Idle Process. Chances are, it's usually "using" a good percentage of your CPU time because most processes on a home computer (web browsers, word processors, media players, etc.) are I/O-bound and the OS doesn't have anything to schedule while all those processes are waiting for I/O operations to complete. Mine is at 99%. Linux, IIRC, just runs the init process in a loop when there's nothing to do. What if the GC ran during those CPU cycles that would otherwise be spent idling? Surely then there would be no performance hit at all, since those clock cycles would have been wasted anyway. A possible problem is that if there were a lot of CPU-bound processes running, the GC would get far fewer clock cycles. Also, the GC would be I/O-bound too since it's scanning memory so there'd have to be another process to fall back on and run while the GC is waiting for I/O.

[bluemoon]

There is no wasted cpu cycles on idle. What you see on task manager is misleading. All sane OS do HLT when there is absolutely nothing to do. However, I don't count housekeeping task (either part of kernel or root daemon) as idle - since it is actually doing something.

Anyway, it's natural to run housekeeping jobs (GC, swap space management, cleanup for zombie process, etc) on low (or "idle") priority.

[OSwhatever]

Just a question regarding if all objects are GC in the kernel. What happens if some object is being garbage collected (moved to alternate location in RAM), then something happens but the objects is locked and you cannot access it because the lower prio garbage collector is playing with it. Even worse, if the kernel needs the object in an interrupt but it is locked, now you end up in a deadlock situation.

In practice not all objects in the kernel can be garbage collected because you will end up in less than advantageous locking situations.

[bluemoon]

@OSwhatever: This apply not only to GC, but to anything regarding kernel locks and resources locks. The simplest approach is "kernel lock" (cli+spinlock) - this has the side-effect of automatically make the maintenance thread real-time priority when there is something to do; to avoid such side effect special effect should be made on the design.

PS. I'm not a fan of GC anyway.

[FallenAvatar]

bluemoon and OSWhatever: Locks aren't really problem in terms of GC due to the fact the the GC should not need locks period. It simply "loops" over all "objects" and determines if there are any references to it. If the reference count changes mid check, it is likely decreasing by 1, in which case it will be collected next check (if it reached 0), or it is increasing by 1 (where the count was already >= 1) and shouldn't be collected anyways.

As long as at object creation the reference count is set to 1 before being added to the GC Manager, and following those assumptions above, you will never need a lock.

There are, of course, edge cases to consider, such as objects that shouldn't be GC'd, because they are found/modified using pointer arithmetic (page tables? ) and there should be a way in the memory manager to request non-GC'd memory for this purpose.

- Monk

[linguofreak]

What if you had the GC built into the memory manager so that there was no way to allocate memory without it being marked for GC?

This is exactly what is done in userspace when you have garbage collected memory management.

The kernel just provides the address space that the userspace memory manager works in, and is completely uninvolved in the allocation and deallocation of individual objects at the application level, garbage-collected or not.

[Mikemk]

Essentially in this thread, you are arguing over whether or not the garbage collector can have a garbage collector.