Subject: Regarding suspend(0) and lag (fwd)

From: Clay Luther <[email-masked]>
Date: Mon, 22 Feb 1993 14:57:00 -0800

In reply to Jeff's endless replies:

Sigh.
 
Look, I'd prefer not to have to deal with the problems
raised by pre-emption of moo tasks unless they are significantly reduced
to the level of the individual programmer needing no concern for them,
whereas you seem to think that pre-emption in any form is a Good Thing(tm).

And it's not like my opinion has any weight anyway.  

I stated my opinion.  It is contrary to yours.

Enough said.

-- 
Clay Luther                              [email-masked]
Software Engineer                        Vortech Data, Inc.
(214) 994-1377                           Fax (214) 994-1310

I dunno.

---

From: [email-masked] (Jeff Prothero)
Date: Thu, 25 Feb 1993 16:19:47 -0800

Pavel Curtis <[email-masked]>:
| Suppose a lot of tasks are mutually conflicting.  What will you do
| about liveness (making sure that each task eventually gets to commit)?
| Otherwise, an approach like this may well work out acceptably in the
| MOO environment.

A good question I hadn't thought about!  I've been presuming this
wouldn't be a significant problem in practice ... but I've little
experience with heavily programmed muds such as moo.  Is there some
practical experience from moo to suggest enough contention that tasks
might thrash heavily due to this?

The only not-too-ugly answers which occur to me offhand are:

 (1) Insert more 'commit' points in particularly long-running tasks;

 (2) Ethernet-style backoff on the competing tasks until they start
     to get enough time to run to commit -- have each task sleep
     successively longer each time it has to be rolled back;

 (3) Successively increase timeslice size of tasks that are rolled
     back -- this would basically (gracefully?) degrade to
     non-preemptive tasking in the limit.
  
(Anyone see any others?  Short of retreating to explicit locking, when
to schedule a task (2), and how long to schedule it for (3), seem the
two main tools we have available.)

(1) is just passing the buck to the application programmer, of course,
which isn't nice unless the problem is rare and mostly confined to
system software.

Between the server-based solutions (2) and (3), (2) should have less
negative impact on interactive response, since unrelated tasks would
keep getting timeslices regularly, but (3) appears more certain to
eventually resolve the problem in theory, since >eventually< each task
will run nonpreemptively to completion, if that's what it takes to
resolve the 'livelock' ...  albeit, if necessary, at the cost of
running nothing else on the mud for an indefinite period.

I'm inclined to wait and see if the problem appears in practice, and
if so, likely try (1), (2) and (3) in about that order...  sticking
fixes in the server for problems which haven't appeared can wind up
doing more harm than good. It is not clear to me that either 2 or 3
would be monotonically better than doing nothing: 2 could lead to a
rather silent accumulation of sleeping tasks, while 3 could lock up
the mud rather nastily if a pathological pair of tasks insist on
conflicting indefinitely ... might be better to live with theoretical
deadlock but consistent interactive response than theoretical lack of
deadlock but effectively locked up systems in practice :).

(Prior to your question, I was just intending a rollback limit N,
killing any process which fails the same commit N times running.  This
wasn't intended as a solution to the above, just cheap insurance.  It
does constitute an answer of sorts, however. :)

Hmm.  Global tuning parameters enabling one/both of (2)/(3) at need,
which defaulted to OFF, might be an idea...

Good food for thought, thank you Pavel :).

    (Another problem with this general class of scheme is that
    the commit itself may wind up taking long enough to impose
    an objectionable pause on the system.  If one wants to keep
    commits atomic and avoid retreating to locking, that appears
    just a necessary price to pay.  The limiting case would be a
    process that read the entire db before doing a commit, which
    commit would then require rereading the entire db to verify
    that nothing had changed.

    I'm trusting that naively written code generally won't
    read/write enough properties for this problem to appear, and
    that the few tasks likely to exhibit such behavior can be
    rewritten to commit at decent intervals.

    Technically, if you really want to know, say, the exact
    number of bytes of strings in the db, you really do need --
    barring special-case solutions -- to lock out access to the
    entire db for the time it takes to scan it, and no
    serialization mechanism is going to be able to change this.
    But mostfolks requesting such a db scan will be willing to
    settle for a somewhat approximate answer, which willingness
    can be indicated by including commits at reasonable
    intervals during such a scan... not a terribly different
    requirement from what moo is currently doing to keep such
    scans from locking the mud up.  Since suspends() should in
    fact be done only when the db has returned to a
    self-consistent state as defined by the task, the
    correspondence should be rather precise -- possibly some
    future pre-emptive moo could simply re-interpret suspend()
    as commit()?  Hmm... odd!)

-- Jeff, wandering off with a new cud to chew.