[slime-devel] Re: Partial multiprocessing support on CMUCL

[Luke Gorrie]

Helmut Eller <e9626484 at stud3.tuwien.ac.at> writes:

> One idea is that we include a "stack descriptor" in each message.  A
> stack descriptor could be something like (idle eval debugging) or a
> string with the initial letters of the states "IED".

I haven't thought this through yet -- busily cleaning out my office in
preparation for a move and fun stuff like that :-). But lemme float an
idea I had been thinking of:

Suppose we designate that Lisp has the "master" state and Emacs is
essentially a replica, so race conditions are resolved by Emacs
backing off its changes and syncing with Lisp. A problem statement is
then:

  If Lisp and Emacs both make transitions simultaneously, Lisp should
  ignore the transition from Emacs, and Emacs should abort/rollback
  its own transition and then process the transition from Lisp.

(I have no argument for the correctness of that prepared, but it
sounds right.. :-))

This could be implemented with sequence numbers. Suppose each side
numbers the transitions it initiates in sequence 0, 1, 2, etc. Each
transition message includes two numbers: its own sequence number, and
an acknowledgement number -- the highest sequence number received from
the other side at the time the message was sent.

We could add this to the current protocol without changing its
semantics. Then we could detect race conditions: if you get a message
with an acknowledgement number lower than the last message that you
sent, then both messages were "on the wire" at the same time and you
need to resynchronize.

An algorithm to resynchronize is:

  If Lisp receives a message from Emacs with an old acknowledgement
  number, it discards it.

  If Emacs receives such a message, it aborts (rolls back) all state
  from transitions it has initiated with higher sequence numbers than
  the acknowledgement number. Now Emacs is in the same state as Lisp
  was when it sent the message, so the message can be safely
  processed.

The overall effect should be that Emacs and Lisp can only reach
inconsistent states temporarily.

It requires Emacs to keep track of all unacknowledged transitions it
has made, and to have a way of rolling them back. At a glance this
doesn't seem very hard -- EVALUTING state transitions could be rolled
back as with the :ABORT event; DEBUGGING and READ-STRING have simple
analogous "Lisp returned; pop the stack" transitions.

Just an idea...