Concurrent GC#

We briefly discussed David's three line mark-and-sweep solution.

def start(x) = x.write() >> each(Succ(x)) >y> start(y)
def finish(y) = >> x.clear() ; Free(x)
def gc() = each(roots) >r> start(r) ; each(nodes) >n> finish(n) >> stop ; signal

Nodes with written cells are black, unwritten are white. This is a simplified version of the actual algorithm. The real algorithm also requires that the mutator not allow edges from black (reachable) nodes to white (unreachable) nodes.

Jay would prefer not to allow the .clear (reset) method on cells. Here is an alternate version without the reset:

def start(x) = atomic(if( >> x.write(false)) >> each(Succ(x)) >y> start(y)
def finish(y) = if( then Free(x) else x.write(true)
def gc() = each(roots) >r> start(r) ; each(nodes) >n> finish(n) >> stop ; signal

The atomic section is not necessary for correctness, but a race between the read and the write may result in repeated work, as another thread starts a node that may be about to be colored black. Assuming that the scheduling is fair, the algorithm will still terminate without atomic.


A region encloses an expression, giving it some sort of implicit dynamic object. A simulation region has a logical timer, an atomic region has a transaction, etc. Given an expression e, (region e) is also an expression; this means that regions can be nested to any depth.

Within a region, there are usually operations that observe or change the current dynamic object. While we could add these specifically as new syntax, it seems easier to add them as sites which operate on the most enclosing region.

Real Time Regions#

The simplest region to consider is a real-time region. Since real time advances simultaneously in any part of a program, a real-time region simply sets a new zero point; the region's object is a relative timer, which starts at 0, and advances at the same rate as any other real timer.

A real-time region has two operations. Rtimer(t) waits for t units of time. Rclock() returns the amount of time that has passed since this real-time region began to execute.

As a simple test of real timers, Jay proposes implementing a clock synchronization algorithm.

Logical Time Regions#

In addition to real-time regions, there are also logical time regions, which we have been writing as (sim e). The dynamic object of such a region is a new logical timer.

A logical time region also has two operations. Ltimer(t) waits for t units of logical time. Lclock() returns the amount of logical time that has passed since this logical time region began to execute. Jay has proposed three axions for logical time: Common ("immediate") operations (add, multiply, etc) do not advance the logical timer. All other calls (uncommon/"non-immediate" operations) take an unknown amount of logical time. Logical time is non-decreasing. The logical timer eventually advances. In order to satisfy property #3, we must require two properties of the execution:

All immediate operations eventually return a value or halt. It is not possible to do an infinite amount of computation in zero logical time.

Nested Logical Timers#

Since regions can be nested, a new logical time region may be executed within the context of another logical timer. What happens?

Our consensus for now is that the execution of the nested region takes zero logical time in the timeline of the parent region. The question we still have to answer is: what happens when a site interacts with two different logical time regions?

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-1) was last changed on 15-Dec-2010 16:46 by DavidKitchin