Hi,
Tony Garnock-Jones <[email protected]> writes:
> In short, the communication between the two programs would be
> messages about speculative output (and about begins, commits, and
> rollbacks), not messages carrying committed output.
This is really an interesting idea! Here are some details I've worked
out:
struct Buffer
{
SEMAPHORE_T new_buffer_or_rollback;
void **data;
size_t len;
struct Buffer *next;
};
struct Transaction
{
SEMAPHORE_T new_buffer_or_subtransaction;
struct Buffer *first, *last;
struct Transaction *parent, *child;
};
To create a new transaction, an empty Buffer is assigned to tx->first
and tx->last (this provides a sentinel object for readers to block
on), tx->parent is the parent transaction and tx->parent->child = tx.
Of course, this means that only a single writer can have a "published"
transaction via the tx->child link, though there shouldn't be any
limits on having multiple other writers use private transactions.
A semaphore on Buffer blocks the transaction's reader until more data
is available (i.e. another Buffer has been atomically appended), or
the transaction is rolled back. A semaphore on Transaction is raised
when more output is added to this transaction or a published
subtransaction is begun.
I don't think there's a reason to provide an explicit commit message
to the reader: they just read the transaction that they're interested
in, which may be the toplevel transaction if they only want to see
toplevel commits.
So, regular readers would walk the toplevel transaction's tx->first
list, and wait on the "buf->new_buffer_or_rollback" semaphore when
they reach buf->next == 0. Speculative readers would do the same, but
monitor the "tx->new_buffer_or_subtransaction" semaphore and descend
into tx->child when there is a subtransaction.
When transactions commit, we just do a compare-and-swap to get
subtx->parent->last->next = subtx->first, and subtx->parent->last =
subtx->last. When they rollback, we set all the transaction's buffers
to len = 0 and next = 0, raising "buf->new_buffer_or_rollback", so
that readers know there's a rollback, and set subtx->first =
subtx->last = 0 so that writers can rollback instead of commit,
subtx->parent->child = 0.
I'm implementing this in Figure now for all of its output streams (the
repl was asymmetric before now; input was done through buffers that
could be rolled back by resetting the World pointer, but output was
direct to stdout). It's a little more encapsulated than described
above, because any per-object semaphores and the functions that use
them are stored in closures corresponding to methods on each
individual Transaction and Buffer, not in visible struct members (I'm
insistent on making Figure independent of the underlying concurrency
mechanism).
This is getting fun! Thanks for the reply,
--
Michael FIG <[email protected]> //\
http://michael.fig.org/ \//
_______________________________________________
fonc mailing list
[email protected]
http://vpri.org/mailman/listinfo/fonc
