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

From: [email-masked] (Jeff Prothero)
Date: Thu, 25 Feb 1993 13:43:14 -0800

Pavel Curtis <[email-masked]>:

| I believe that [traditional database serializability constraint] is
| the right model for the MOO, as well, but you don't want to too far
| with analogies between the MOO and traditional databases.

*nod*.  (Does one _ever_ want to go to far with something?
:) The database world has more applicable theory and
experience to offer us than any other that I'm aware of,
however.  Object-oriented databases are particularly
relevant, I've been skimming some stuff on them for ideas.
Turns out they too use b-trees to break up big strings to
work more nicely in software virtual memory.  Ah well, I'll
have an original idea someday :).

| Yes.  The fundamental problem in attempting to solve
| deadlock and locking problems automatically on the server is
| that, unlike in the traditional database world, it is not
| possible to statically determine what items in the DB will
| need to be locked to run a particular `query'.  Thus, you
| can't, in advance, sort all of those resources by the global
| locking order and then lock them.  You will therefore have
| to lock them as they are accessed by the code.  Since most
| MOO tasks touch a lot of different properties and verbs, and
| these are getting locked in more-or-less random order, you
| can expect a *lot* more deadlocks than in a traditional DB.

*nod*, I'd come to much the same comclusion about that class
of solutions.

For my server, I'm looking at using an optimistic
non-locking approach, tracking all values read by the task
from the db, and buffering all values written to the db
until a commit is done.  At commit time, if no value read by
the task in the db has changed, all writes can be installed
in the db atomically, otherwise the task can be rolled back
and rerun.  This approach isn't altogether without problems
(what engineering solution is?), but it does (to me) seem
cleaner than either explicit locking or living with
non-preemption, and with a judiciously placed implicit
commit or two (I'm thinking of at user input and task
conclusion, at the moment), I hope most naive application
programmers will seldom have problems with it.

If Clay is right that there's a general proof that
pre-emptive multitasking can't work acceptably in a mud
context, then there must be a hole in the above scheme, but
so far I've been unable to find either proof or hole...

| > Unix appears to me a nice demonstration of the benefits of pre-emptive
| > multitasking,
|
| UNIX works as well as it does for multitasking precisely
| because there is very, very little in the way of shared
| data, essentially only files.

*nod*.  To some extent, there is a lesson there: Minimizing
(and localizing) operations with side-effects on other
processes eases the problems of dealing with concurrency
generally, and pre-emptive multitasking in particular.  This
observation wouldn't surprise the functional programming
folks, of course :).  (Speaking of which -- has anyone
considered the appropriateness of Haskell for the mud
environment?  Gofer sounds like a nice PD interpreter, but
I've not familiar with either yet...)

Thanks presumably to the god(dess?) who watches over drunks
and fools, nobody seems to have implemented side-effects on
strings in tinyMuck :).  There being no other nonatomic
datatype at present, the system turns out to be essentially
side-effect free except for object variables -- an
unexpected blessing.  I don't know moo well enough to
analyse how many places it has to consider side-effects on
the db...?

| UNIX does provide file
| locking, but almost no applications use it, so you the human
| have to be careful not to try to print the PostScript output
| of your editor until you're sure the editor has finished
| writing the file.

Partly sheer luck, partly people learning to live within the
limitations of available tools -- people make copies of files
to edit, rather than munging single master copies, in general...

| Similar examples of human mediation of
| shared data conflicts abound in such an environment.
| 
| In UNIX, shared data is the exception, whereas in MOO it is
| the rule.

*grin*: well, if you consider /usr/spool/mqueue shared data,
and reflect what proportion of time is spent on email :) ...

(*nod*)

| This, along with the need to cater to amateur
| programmers, makes the MOO a very unusal kind of OS
| environment. 

And, indeed, a fascinating problem.

| One should not be too glib about applying
| common solutions from other domains.
|
|         Pavel

Again, it's rarely good to be 'too' anything :).  I'm sure
you noted that above I cited Unix as a demonstration of the
>benefits< of multitasking, not as a model of how to achieve
it in the mud environment -- benefits you don't contest
above.

Jeff

---

From: Pavel Curtis <[email-masked]>
Date: Thu, 25 Feb 1993 14:47:55 -0800

> Date:	Thu, 25 Feb 1993 13:43:14 -0800
> From:	[email-masked] (Jeff Prothero)
> 

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.

> analyse how many places it has to consider side-effects on

The only side-effects in MOO are the following:

	-- object creation or destruction,
	-- parent/child or location/contents hierarchy modification,
	-- property and verb creation, renaming, and deletion,
	-- property value and verb code modification,
	-- output to users, and
	-- the pending-task queue.

In particular, the MOO aggregate data values (strings and lists) are not
mutable.

	Pavel