Multi-threaded MUD driver
TUB Multi User Domain
>Actually, the idea of multi-threading has been on my mind as well.
I don't want to discourage you, but the topic keeps showing up every
other month for years and so far hasn't been solved satisfactorily.
>But real multi-threading, not multi-tasking.
Hmm, what do you mean by _real_ multithreading compared to _mere_
multitasking? I must confess that I haven't the slightest idea
what the difference is nor what the advantages for the driver would
be. (In fact, I _do_ have an idea what you're aiming at, but I hope
I will be proved wrong.)
>Too bad there are so
>few OSes around that can do it. If I ever find the time to rewrite
>the driver (HA!), I would not consider leaving it single-threaded.
Why not? How do you propose to solve the diverse consistency and
causality problems caused by a multithreaded approach? Don't you
think a single-threaded driver is less prone to producing errors
(especially irreproducible ones)? How are you going to model the
happens-before relation?
>Anyone already working on it (maybe on Solaris 2.2 or 2.3)?
>Putting different functionality into separate processes is a generally
>losing proposition, I think. There are better ways (discussed and not),
>to handle consistency of coding, memory usage, speed, data vs. code
>delineation, etc IMHO.
I (and probably other people on this group, too) would like to hear
how to go about the problems caused by making a driver multithreaded.
Reimer Behrends
Tony Brannigan
>den...@canada.sun.com (Dennis Simpson Sun Canada) writes:
>>Actually, the idea of multi-threading has been on my mind as well.
Me too :)
>>But real multi-threading, not multi-tasking.
>
>Hmm, what do you mean by _real_ multithreading compared to _mere_
>multitasking? I must confess that I haven't the slightest idea
>what the difference is nor what the advantages for the driver would
>be. (In fact, I _do_ have an idea what you're aiming at, but I hope
>I will be proved wrong.)
Given that the original author was talking about having separate
processes to make up the mud, I assume that is what is meant by multi-
tasking. Multi-threaded would mean one process with lots of threads.
A single-threaded driver is not vulnerable to race conditions and so on,
admittedly a lot of things in the current MudOS driver (the driver I am
familiar with) and associated mudlibs would not work if it was multi-
threaded. Synchronization would be a problem, as 'safe' inter-object
communication does not yet exist.
As an example, consider a piece of code strewn throughout the tmi-2
mudlib:
seteuid(geteuid(previous_object()))
This would no longer be sufficent to ensure security, as you have no
guarantee that you will not be interupted right there, then be called
again from a new object with a different euid, so that when you return
to the original you have to wrong euid. Of course you can solve this
kind of thing using 'critical sections' but in a mud these would
probably turn out to be a lot longer than standard critical sections,
and would cause a much degraded response time.
Perhaps some form of cooperative multi-tasking would work?
Or, like the transputer, preempt a process only during certain
instructions (e.g. return from subroutine, I/O, so on).
Tony
--
To see a World in a Grain of Sand | There are three types of people,
And a Heaven in a Wild Flower, | those that make things happen,
Hold Infinity in the palm of your hand | those that watch things happen,
And Eternity in an hour. | and those that wonder what happened.
TUB Multi User Domain
>r_be...@informatik.uni-kl.de writes:
>>den...@canada.sun.com (Dennis Simpson Sun Canada) writes:
>>>Actually, the idea of multi-threading has been on my mind as well.
>Me too :)
>>>But real multi-threading, not multi-tasking.
>>
>>Hmm, what do you mean by _real_ multithreading compared to _mere_
>>multitasking? I must confess that I haven't the slightest idea
>>what the difference is nor what the advantages for the driver would
>>be. (In fact, I _do_ have an idea what you're aiming at, but I hope
>>I will be proved wrong.)
>Given that the original author was talking about having separate
>processes to make up the mud, I assume that is what is meant by multi-
>tasking. Multi-threaded would mean one process with lots of threads.
That is what I was afraid of. I do not see what it has to do with
driver design. In fact, it is an implementation issue. A very low-level
one. One might even call it an efficiency issue. And it made the
posting look like a Solaris plug (especially considering the posters
email and the mentioning of Solaris later).
>A single-threaded driver is not vulnerable to race conditions and so on,
Precisely. My question, therefore: what do we gain for giving up
the benefits of single-threaded-ness?
>admittedly a lot of things in the current MudOS driver (the driver I am
>familiar with) and associated mudlibs would not work if it was multi-
>threaded. Synchronization would be a problem, as 'safe' inter-object
>communication does not yet exist.
>As an example, consider a piece of code strewn throughout the tmi-2
>mudlib:
>seteuid(geteuid(previous_object()))
Not much of a problem. Make it a monitor or something like that.
>This would no longer be sufficent to ensure security, as you have no
>guarantee that you will not be interupted right there, then be called
>again from a new object with a different euid, so that when you return
>to the original you have to wrong euid. Of course you can solve this
>kind of thing using 'critical sections' but in a mud these would
>probably turn out to be a lot longer than standard critical sections,
>and would cause a much degraded response time.
They can't degrade response time more than a single-threaded driver,
unless the enter/exit-critical-section code is costly.
>Perhaps some form of cooperative multi-tasking would work?
>Or, like the transputer, preempt a process only during certain
>instructions (e.g. return from subroutine, I/O, so on).
I guess I will have to pose some typical problems:
1). Have a dragon, a gate, and a player, all separate objects.
Dragon does:
if (gate->is_open())
go_to_room_on_other_side();
Player does:
gate->close();
Now what happens if the dragon gets interrupted after the if ()
and the player closes the gate meanwhile? He will walk through
the closed gate, eating the player and thus make him send lots
of complaints to the admin ;-).
More general, if we have a piece of code of the form:
if (f(o1,...,on)) modify(p1,...,pm);
all kind of evil things may happen if we get interrupted. And
we can't just bar all those objects from being accessed since
we do not know what they are short of solving the halting
problem (in the general case).
2.) Have two players try to pick up the same object. Suppose the
code is:
if (ob->env() == player->env())
ob->move_to(player);
Now all kind of nasty things can happen:
a) Both players succeed in the if() check, thus both will
manage to pick up the object, but only one will
be holding it.
b) One player is teleported away between the check and the action,
thus learning to teleport things around for a short time. ;-)
3.) Write a people command that is consistent. I.e. one that doesn't
for example show two people to be in the same location if they
never were. This requires getting a snapshot of the global state.
True, an error in this particular application won't harm anybody,
but what if the computer is going to process the result of such
a snapshot?
Btw, you will notice that your transputer idea won't help here. ;-)
Reimer Behrends
Tony Brannigan
technical crap, skip the bits between the '**'.
r_be...@informatik.uni-kl.de writes:
[...about solaris and so on...]
Even SunOS 4 has an implementation of threads (lightweight process
library). They are woefully inadquate for a multi-threaded mud, but
proper implementations are becoming widespread. I know that WinNT,
Mach and Nextstep all support threads, other modern operating systems
will too.
>Precisely. My question, therefore: what do we gain for giving up
>the benefits of single-threaded-ness?
We gain much 'nicer' code. The current system of input_to and callbacks
for everything and its mother is pretty horrible IMHO. It even damages
data encapsulation by forcing variables that should be local to be
global. Consider:
int foo;
void
a()
{
<something with foo>
input_to(b);
}
void
b(string dummy)
{
<something with foo & dummy>
}
This would be much nicer as:
void
a()
{
int foo;
string dummy;
<something with foo>
read dummy;
<something with foo & dummy>
}
You also gain the advantage that it isn't as easy for something to hang
the mud. True, with the eval_cost limit it is hard to permanently hang
the mud but it is easy for someone to cause large scale lag for others.
A multi-threaded implementation would help to stem this (especially if
the lag is due to I/O). With a totally pre-emptive system you eliminate
the problem.
**
>Not much of a problem. Make it a monitor or something like that.
Hmm. I think that to make enough of a current mudlib thread-safe just
about every function would have to be a monitor :) Having such huge
amounts of mutual exclusion loses the possible response benifit you can
get from having a mutli-threaded driver.
>They can't degrade response time more than a single-threaded driver,
>unless the enter/exit-critical-section code is costly.
You seem to be arguing against single-threadedness here :)
>I guess I will have to pose some typical problems:
>
>1). Have a dragon, a gate, and a player, all separate objects.
>2.) Have two players try to pick up the same object. Suppose the
These two problems seem to be both the same, access to a shared resource
(state of another object in both cases). It is tempting to say
"implement exclusion", but this goes against my argument above to reduce
critical sections :(.
On the other hand the transputer idea might help. Say we go for a
transputer-like scheme where a process can be interupted during the
following:
while statement
call_other
I/O of any form
when it wants to sleep
> if (gate->is_open())
> go_to_room_on_other_side();
It is then possible for this to be interupted when it does the
gate->is_open() call, but once it returns it will continue until the
monster moves through to the other room.
Another possibility would be to allow objects to lock other objects out
of each other. In semaphore terms:
> down(gate);
> if (gate->is_open())
> go_to_room_on_other_side();
> up(gate);
The same solution would work for the second problem. Unfortunatley
coding this is not going to be every newbie wiz's cup of tea.
>3.) Write a people command that is consistent. I.e. one that doesn't
> for example show two people to be in the same location if they
> never were. This requires getting a snapshot of the global state.
> True, an error in this particular application won't harm anybody,
> but what if the computer is going to process the result of such
> a snapshot?
Admittedly this sort of thing could warrant some sort of 'don't interupt
me' facility.
**
I am pretty much in favour of multi-threaded drivers. I may not have
given good answers to your problems, but I am sure they exist. It would
cetainly be possible to make a totally preemptive multi-threaded driver
and acheive synchronisation through semaphores or whatever, the problem
I see is to make it easy for a newbie wiz to program it without making
them CSP experts :) On the other hand I do not think the language to
program it in needs to resemble LPC. How about LPOCCAM? :)
James Waldrop
Tony Brannigan <tbr...@oxford.ac.uk> wrote:
>
>r_be...@informatik.uni-kl.de writes:
>>Precisely. My question, therefore: what do we gain for giving up
>>the benefits of single-threaded-ness?
>
>We gain much 'nicer' code. The current system of input_to and callbacks
>for everything and its mother is pretty horrible IMHO. It even damages
>data encapsulation by forcing variables that should be local to be
>global.
There's no reason to need threads to make input_to() or any other callback
seem to be multi-threaded. The single-threaded driver can save the
state of the object, moving it back in when necessary. MudOS already
gets close to this by letting you pass an unlimited amount of
variables along with the callback in input_to, as well as increasing
the number of variables allowed with call_out from one to infinite.
Well, maybe not infinite, I haven't looked at the code, but certainly
more than one in the case of callout and more than 0 in the case
of input_to. :-)
I can conceive of this being valuable for things like input_to
and call_out. I don't think the complications are worth it otherwise.
Sulam
--
j...@shekel.cs.columbia.edu ...one day we'll awake and still be in fifth
grade and and our lives will be on video tape and the teacher is some witch-
god thing that created everything and she'll show the class and they'll laugh
and laugh and laugh at how stupid yer life was oh yess... - david fremont
jsc...@ux4.cso.uiuc.edu
Here's how I would handle a previous_object() call, and timing calls so that
one object is only doing one task at a time ..... a "message" deamon ...
when one object does a call_other or calls a func down the inheritance tree,
it posts a "message" to the deamon. Every object, when I has "free time" will
ask the deamon for it's "next" message .... when it's done, it will call back
with "I've completed that message" message to the deamon .... then a
previous_object() is just as simple as a "what object sent me my current
message?" request ....
But then, this will not work when A calls B calls A, but then I just thought
this up, and there surely is a way to modify it to work in that regard, I
would think.
Blackstaff
Michael O'Reilly
[ ignoreing other stuff... ]
: threaded. Synchronization would be a problem, as 'safe' inter-object
: communication does not yet exist.
: As an example, consider a piece of code strewn throughout the tmi-2
: mudlib:
: seteuid(geteuid(previous_object()))
: This would no longer be sufficent to ensure security, as you have no
: guarantee that you will not be interupted right there, then be called
: again from a new object with a different euid, so that when you return
: to the original you have to wrong euid.
This is non-sense. previous_object() refers to the object that invoked
the current function. Stacks are per thread. Thus previous_object() is
simply the previous frames environment. It doesn't matter if you get
interrupted or not, the stack for this thread will remain unchanged.
This is not to say that you don't have problems, just that this isn't
one of them.
: Of course you can solve this
: kind of thing using 'critical sections' but in a mud these would
: probably turn out to be a lot longer than standard critical sections,
: and would cause a much degraded response time.
This is also nonsense. Given the truely massive overhead of
interpreting LPC, looking after mutex's would be insignificant. Simply
adding minimal language support gets you 99% of the way there.
things like {{ instead of { to indicate object level mutex.
i.e.
object foo:
def muxtex_wrt_this_object(arg1, arg2) {{
/* for each instance of object foo, there will be
only a single thread executing this function.
other threads will block until the executing
thread leaves this function. */
}}
This doesn't get you all the way there. You need to worry about
deadlocks, and so forth, but you can simply things a lot...
: Perhaps some form of cooperative multi-tasking would work?
: Or, like the transputer, preempt a process only during certain
: instructions (e.g. return from subroutine, I/O, so on).
co-operative multi-tasking would work quite well. In fact, it would
work very well, but you'd still need the lpmud kludge of breaking
execution if a thread runs too long w/o a switch..
: Tony
Michael.
TUB Multi User Domain
>r_be...@informatik.uni-kl.de writes:
>[...about solaris and so on...]
>Even SunOS 4 has an implementation of threads (lightweight process
>library). They are woefully inadquate for a multi-threaded mud, but
>proper implementations are becoming widespread. I know that WinNT,
>Mach and Nextstep all support threads, other modern operating systems
>will too.
Yes, but I still don't understand how this efficiency and implementation
issue should influence driver design (and even the implementation
would probably be hidden behind some abstraction mechanism).
>>Precisely. My question, therefore: what do we gain for giving up
>>the benefits of single-threaded-ness?
>We gain much 'nicer' code. The current system of input_to and callbacks
>for everything and its mother is pretty horrible IMHO. It even damages
>data encapsulation by forcing variables that should be local to be
>global. Consider:
[Large example about the ugliness of input_to() deleted]
You don't need multithreaded drivers for that. MOOs do exactly what
you suggest. And they're aren't multithreaded.
>You also gain the advantage that it isn't as easy for something to hang
>the mud. True, with the eval_cost limit it is hard to permanently hang
>the mud but it is easy for someone to cause large scale lag for others.
And it isn't easy to avoid such lags in a multi-threaded system while
guaranteeing correctness.
>A multi-threaded implementation would help to stem this (especially if
>the lag is due to I/O). With a totally pre-emptive system you eliminate
>the problem.
Hmm. As far as I can see, even under the most lucky circumstances
it will still lag at least one player. But I agree, it could
improve the overall situation. This of course implies that there
are no lags due to deadlocks, a problem you don't have in a
single-threaded system.
>>Not much of a problem. Make it a monitor or something like that.
>Hmm. I think that to make enough of a current mudlib thread-safe just
>about every function would have to be a monitor :) Having such huge
>amounts of mutual exclusion loses the possible response benifit you can
>get from having a mutli-threaded driver.
Exactly. But doesn't it occur to you that exactly this might be necessary?
All the examples I have presented to other people were finally crammed
with semaphores and monitors to make them correct.
>>They can't degrade response time more than a single-threaded driver,
>>unless the enter/exit-critical-section code is costly.
>You seem to be arguing against single-threadedness here :)
I try to be objective. ;-) (Well, I _try_ ;-).)
>>I guess I will have to pose some typical problems:
>>
>>1). Have a dragon, a gate, and a player, all separate objects.
>>2.) Have two players try to pick up the same object. Suppose the
>These two problems seem to be both the same, access to a shared resource
>(state of another object in both cases). It is tempting to say
>"implement exclusion", but this goes against my argument above to reduce
>critical sections :(.
Tempting as it may be, it is not even possible, unless you give
up the benefits of data hiding and implement mutual exclusion
across objects limits. Or what exactly is the section of code
you want to make mutually exclusive? I guess you do not count
use of semaphores, since you do use them below?
>On the other hand the transputer idea might help. Say we go for a
>transputer-like scheme where a process can be interupted during the
>following:
> while statement
> call_other
> I/O of any form
> when it wants to sleep
>> if (gate->is_open())
>> go_to_room_on_other_side();
>It is then possible for this to be interupted when it does the
>gate->is_open() call, but once it returns it will continue until the
>monster moves through to the other room.
No. Absolutely no. You assume here that neither is_open() nor
go_to_room_on_the_other_side() contain any of the above constructs.
And it is quite likely that either of them contains call_other()s.
Unless you resort to mutual exclusion again. ;-)
Besides, you probably should extend call_other() to 'any function call'
in the above list. (Or what if somebody decides to compute A(10,10),
where A is the Ackermann function? ;-) ).
>Another possibility would be to allow objects to lock other objects out
>of each other. In semaphore terms:
>> down(gate);
>> if (gate->is_open())
>> go_to_room_on_other_side();
>> up(gate);
Such a solution either assumes that a) both procedures don't rely on
code in other objects or b) safeguard their calls with a similar mechanism.
In either case, the caller has to know about the implementation,
which is a bad thing (tm). If it didn't know, it would be impossible to
guarantee correctness.
>The same solution would work for the second problem.
Sorry, no. Or more precisely, you're likely to forget something.
For this, consider how move_to() is implemented. It needs three
steps. First, change the environment to the destination. Second,
remove us from the inventory of the object we're in (this will
require making a call to the object holding us). Third, add us
to the inventory of our destination. And of course the order
of these steps may be different. And for every different ordering
something different will go wrong. And if you lock the object, the
source and the destination of the move first, you're likely to
end up in a deadlock as soon as either the source or the destination
do something with the object.
Or do you have a working solution for the problem?
>Unfortunatley
>coding this is not going to be every newbie wiz's cup of tea.
It is also astonishing how many expert coders screw up when
having to work with a multitasking system. And remember, these
are toy examples, not a fully-fledged mudlib.
>>3.) Write a people command that is consistent. I.e. one that doesn't
>> for example show two people to be in the same location if they
>> never were. This requires getting a snapshot of the global state.
>> True, an error in this particular application won't harm anybody,
>> but what if the computer is going to process the result of such
>> a snapshot?
>Admittedly this sort of thing could warrant some sort of 'don't interupt
>me' facility.
Surprisingly enough, we can do without (although we may need other
less stringent low level operations). Check the literature on
distributed systems for the 'global snapshot' problem. Unfortunately,
all these solutions are non-trivial. It is probably easier to halt
the system while collecting the snapshot. It is even easier to forget
about the correctness of the result and just compute an approximation.
But I don't want to trade correctness for speed. A little bit incorrect
is just about as meaningful as a little bit pregnant.
>I am pretty much in favour of multi-threaded drivers. I may not have
>given good answers to your problems, but I am sure they exist.
Unfortunately they all seem to forget about data hiding and abstracting
from the implementation - something that the software engineering part
of my self abhors.
>It would
>cetainly be possible to make a totally preemptive multi-threaded driver
>and acheive synchronisation through semaphores or whatever, the problem
>I see is to make it easy for a newbie wiz to program it without making
>them CSP experts :)
No, the problem is to get the code right, no matter whether the coder
is a newbie or an expert.
>On the other hand I do not think the language to
>program it in needs to resemble LPC. How about LPOCCAM? :)
Frankly, I don't know if Hoare's model of 'Communicating Sequential
Processes' is adequate here.
Reimer Behrends
Sven C. Dack
been a lot of discussions on that topic here in rgm.lp and other groups (about
every month or so ;-).
I don't have much knowledge about how to implement such a driver, so I
won't/can't add anything to the technical problems.
Besides the feasibility of world-wide communication I believe the reason why
MUDs have become that famous is because everything is based on text and
everyone can write descriptions for a room or an item. The task of
programming isn't that difficult and you get quite good results just after a
few weeks of exercise. Most MUDs are continuously evolving games and the
source of it are all those players who achieved wizardhood and contributed
their ideas and fantasies to it (at least this is the case for most
LPMUDs). Wizards come and go and only a few stay for more than 2-3 years. But
what stays is what they have done for the MUD.
IMHO without this evolutionary process MUDs would never have become that
popular as they are right now. And no end in sight :-).
The idea of graphical MUDs is also rather old. And there are allready a few
systems available. But besides 3D modelling and raytracing: who is going to
draw all the nice pictures (not to mention animations)? You have to be an
artist to get acceptable results. Maybe playing such a game is more fun than
those text-based games. But once you've played it, you probably won't try to
become a wiz because it's simply impossible to express your ideas/fantasies.
That's why I believe the text-based MUDs will never die out because of their
simplicity (from a wizard's point of view).
Writting a multi-threated driver shouldn't be such a big problem compared to
other applications. But when doing so, will its use still be that simple for
others not so experienced programmers or people who never programmed before to
extend the game and to get a continuously growing world opposed to a fixed
one? If one has to learn new programming techniques (i.e. locking mechanisms)
and to think in parallel dimensions, you have to be an CS artist and therefore
I doubt your system will become very popular.
I'm not trying to tell you that you HAVE TO make your driver as simple as
possible for a wizard, because I say so. But what would a game be without a
large community playing and extending it, enjoying what you've created?
Afterall it is just a game.
But if you only want to implement such a gamedriver for your own purpose (or
to discuss how it could be done) without thinking much about how many people
are finally going to use it, well, then ignore what I'm writting :-).
PS: These are just my subjective thoughts. Also my mud experience is fairly
restricted to the world of LPMUDs. But I hope you understand what I'm
trying to say.
--
Sven C. Dack / GMD-IPSI, Dolivostr. 15, 64293 Darmstadt / da...@darmstadt.gmd.de
Bob Farmer
>Tony Brannigan (tbr...@oxford.ac.uk) wrote:
>
>[ ignoreing other stuff... ]
>
>: threaded. Synchronization would be a problem, as 'safe' inter-object
>: communication does not yet exist.
>
>: As an example, consider a piece of code strewn throughout the tmi-2
>: mudlib:
>
>: seteuid(geteuid(previous_object()))
>
>: This would no longer be sufficent to ensure security, as you have no
>: guarantee that you will not be interupted right there, then be called
>: again from a new object with a different euid, so that when you return
>: to the original you have to wrong euid.
>
>This is non-sense. previous_object() refers to the object that invoked
>the current function. Stacks are per thread. Thus previous_object() is
>simply the previous frames environment. It doesn't matter if you get
>interrupted or not, the stack for this thread will remain unchanged.
>
>This is not to say that you don't have problems, just that this isn't
>one of them.
Boggle...he meant that by the time your code runs, the object might have
the wrong euid. ie if you have /cmds/dev/rm, and it sets its euid to
player a, then player b starts using it too, and it sets its euid to that
of player b, then by the time it actually tries to rm the file that player
a wanted rm'ed, it could have player b's euid....he didnt' mean taht
previous_object() would not return the right value..laugh.
Tony Brannigan
>This is non-sense. previous_object() refers to the object that invoked
>the current function. Stacks are per thread. Thus previous_object() is
>simply the previous frames environment. It doesn't matter if you get
>interrupted or not, the stack for this thread will remain unchanged.
Consider objects a,b,c. Object c has root uid and can change it's euid
to anything. Object a and b both want to use c to get at something else.
There are two threads running, I & II.
I a does c->func()
I c sets euid to euid of a
<interupt thread switch to II>
II b does c->func()
II c sets euid to euid of b
II c does whatever it is supposed to.
<interupt thread switch to I>
I c does whatever it is supposed to. It's euid is still that of b,
while the previous object is now a. *BOOM*
>This is not to say that you don't have problems, just that this isn't
>one of them.
Looks like a problem to me.
[...my stuff about large critical sections...]
>This is also nonsense. Given the truely massive overhead of
>interpreting LPC, looking after mutex's would be insignificant. Simply
>adding minimal language support gets you 99% of the way there.
>
>things like {{ instead of { to indicate object level mutex.
>i.e.
>
>object foo:
> def muxtex_wrt_this_object(arg1, arg2) {{
> /* for each instance of object foo, there will be
> only a single thread executing this function.
> other threads will block until the executing
> thread leaves this function. */
> }}
This would seem to indicate that everything inside {{ }} would run to
completion, which is the exact problem you said was 'nonsense'.
*boggle*
>This doesn't get you all the way there. You need to worry about
>deadlocks, and so forth, but you can simply things a lot...
Please, post your ideas!
>co-operative multi-tasking would work quite well. In fact, it would
>work very well, but you'd still need the lpmud kludge of breaking
>execution if a thread runs too long w/o a switch..
That depends on how the coperative multi-tasking is implemented. Given
that any construct can be made a candidate for a context-switch (for
example ';') this problem should be very rare.
Mad Dax
>den...@canada.sun.com (Dennis Simpson Sun Canada) writes:
>>Actually, the idea of multi-threading has been on my mind as well.
[...]
>>Too bad there are so
>>few OSes around that can do it. If I ever find the time to rewrite
>>the driver (HA!), I would not consider leaving it single-threaded.
You'd be "fixing" so much.. might aswell start from scratch. IMHO.
>Why not? How do you propose to solve the diverse consistency and
>causality problems caused by a multithreaded approach? Don't you
>think a single-threaded driver is less prone to producing errors
>(especially irreproducible ones)? How are you going to model the
>happens-before relation?
Yup. But I think handling all of the critical things (like logons,
password changing... etc.) from the hardcoded level only, would reduce
the impact of such errors (I'm also saying that most of the stuff
in current mudlibs regarding security should be in the driver code..
or linked in only after careful thought.)
How to model?... hmm how to model... good question. In a system such as:
y = x + external
do_something(y)
The external variable may change value before we get to do_something...
and thus produce unexpected results.... (asuming we wished to have the
result (x+external)... However the specification:
do_something( x + external )
should be evaluated as expected..... likewise:
y = x + external [ time 0 ]
do_something(y) [ time 1 ]
Does what is desired assuming we realize that had do_something(x + external)
been done at time period 0.. the results would be identical.. If the time
difference between 0 and 1 is small enough, perhaps we don't care if
'external' changes before do_something.... Of course this version
lets us keep a value representing what we passed to do_something (y).
The case of:
a = external1
b = external2
c = external3
y = (5*b+(c-b))/4
Raises complexity a bit.. but still:
y = (5*external1 + (external3 - external2))/4
The only question in any case is if you must know the data represented
in the externals has changed from one decleration to the next - or if
the time difference is imporntnat.... I am assuming in the above
that all evaluations will be limited in scope to a small period of time
involving data which we don't mind getting a *tiny* bit stale. The
picture changes for information regarding exactly what players are in
the game.. or room.. (for example) but I think the point is that worrying
about causes for the form of the externals when passed to the local program
may not be important... so long as all data related to the external
thing to be tested is modified in the smallest time period.
Which is to say that the more complex the relation of the external
information the more shaky or unpredictable reuslts will be -
One can break programs (in game ones) into smaller portions, so that
consistency of data over a given time period is not as important tho
(does this make sense, I do tend to ramble ;)
[...]
>>Anyone already working on it (maybe on Solaris 2.2 or 2.3)?
I'm presently working on an original driver... It won't be as sophisticated
(for this first version) as some present muds in terms of optimal memory
usage.. but my multi-thread operations are all suitable kernel for
use in a future well-rounded game.
Lemme say that it is NOT an LP clone... or derived from any present
MUD system. The MUD database consist of 2 or 3 binary files... The
internal language resembles C only to the extant of function calling
and most of its basic operators (variable decleration is completely
different for instance.)
Ummm... the language I am developing for use in this new driver has
adequate constructs for dealing with multi-threaded operation. The
coder must add some error checking to his programs if he wishes for
things like "error-free" list searching.. but its VERY easy.
I think the big question (in terms of my MUD) one has to worry about
with respect to multi-thread operation is an eternal: "Is this list
we start searching going to be the same list it was when we finish."
To make a looong story short, the coder should have control over
various degrees of error-catching and declaring if eternal functions
should behave as blocking or non-blocking operations in the local
caller. The main operations which should be multi-threaded are those
involving list of information (list which would otherwise take too
long to process.)
Multi-threading, I've found leads to a tiny bit more complexity in the
building of "simple" objects. However you probably should make a game
where coders are aware of and willing to reduce the percentage of processing
time their creations take while not having to limit their scope.
A multi-threaded game takes much more thought on all levels of design...
but is this so bad (as many monuments to mostly undocumented, or highly
complex games built from hundreds of programs created on-the-fly -as
LP'rs are so fond fo saying- exist currently .. including my own LP
MUD)?
-McDaniel
jsc...@ux4.cso.uiuc.edu
[lots-o-stuff removed]
>
>I a does c->func()
>I c sets euid to euid of a
> <interupt thread switch to II>
noticing it's being interupted, c saves it's euid.
>II b does c->func()
>II c sets euid to euid of b
>II c does whatever it is supposed to.
> <interupt thread switch to I>
noticing it's returning from being interupted, c restores it's euid.
>I c does whatever it is supposed to. It's euid is still that of b,
> while the previous object is now a. *BOOM*
>
[lots-o-stuff removed]
Problem solved!
Blackstaff
PS. I know I've said a lot about this, all seemingly contridicory, but then
there it's ONE solution to the problem, there are many ways to solve any
problem ........
jsc...@ux4.cso.uiuc.edu
Considering it's neccessary to save the local "state" anyway, why you think
that euid wouldn't be taken care of in that I don't know .....
Ok, so say Player a starts to run /cmds/dev/rm and then it sets it's euid to
player a, then player b starts makes a call to the SAME functions that player
a did. Hmm, no problem, for when the call to get_euid(previous_object()) is
made, it will have saved the euid of previous_object() allong with the value
of previou_object in the message deamon that sends messages to the object
instances .... thus, thou in general, you would be able to have a
geteuid() function, you COULD impliment a get_previous_euid() function, to
gain the same functionallity of geteuid(previous_object()).
Blackstaff
Dennis Simpson Sun Canada
I only read this group periodically these days.
In article 4...@news.cs.tu-berlin.de, tub...@cs.tu-berlin.de (TUB Multi User Domain) writes:
>
>That is what I was afraid of. I do not see what it has to do with
>driver design. In fact, it is an implementation issue. A very low-level
>one. One might even call it an efficiency issue. And it made the
>posting look like a Solaris plug (especially considering the posters
>email and the mentioning of Solaris later).
Sorry if it came across that way, not intentional. I do like Solaris,
overall, but that was not my point. I would not argue with it being an
efficiency issue. I do not immediately see how it would fundamentally
alter the game or anything like that, just thought it might be an
interesting way to improve performance and general efficiency of the
driver. I am not a threads expert, on the contrary, I am a threads
beginner. But what I have seen of threads so far encourages me.
>>A single-threaded driver is not vulnerable to race conditions and so on,
The "daemonized" driver is. But then, that wouldn't be single-threaded
anymore, I guess.
>Precisely. My question, therefore: what do we gain for giving up
>the benefits of single-threaded-ness?
Benefits of single-threadedness? I'm not sure there are any beyond
simpler debugging, and that I think might be a familiarity issue
more than anything else.
>>admittedly a lot of things in the current MudOS driver (the driver I am
>>familiar with) and associated mudlibs would not work if it was multi-
>>threaded. Synchronization would be a problem, as 'safe' inter-object
>>communication does not yet exist.
>
>>As an example, consider a piece of code strewn throughout the tmi-2
>>mudlib:
>
>>seteuid(geteuid(previous_object()))
This one is bad anyway. euid is not a universal concept, even in UNIX.
>>to the original you have to wrong euid. Of course you can solve this
>>kind of thing using 'critical sections' but in a mud these would
>>probably turn out to be a lot longer than standard critical sections,
>>and would cause a much degraded response time.
I would question that assumption. The data which would truly need
protecting is not probably in use long for the most part.
>I guess I will have to pose some typical problems:
>
>1). Have a dragon, a gate, and a player, all separate objects.
> Dragon does:
> if (gate->is_open())
> go_to_room_on_other_side();
> Player does:
> gate->close();
> Now what happens if the dragon gets interrupted after the if ()
> and the player closes the gate meanwhile?
The dragon thread sets a lock on the gate var first. Then goes through.
If the player thread grabs the lock first, then the player just cheated
the dragon of a meal. Otherwise... shish-kabob (sp?)!
> More general, if we have a piece of code of the form:
> if (f(o1,...,on)) modify(p1,...,pm);
> all kind of evil things may happen if we get interrupted. And
> we can't just bar all those objects from being accessed since
> we do not know what they are short of solving the halting
> problem (in the general case).
I dunno. As I said in my original post, it would require rewrite in
a big way. A great deal of thought would need to go into the locking
granularity. Again, I am not a threads expert, I just thought it might
make an interesting project.
>2.) Have two players try to pick up the same object. Suppose the
> code is:
> example synchronization problems deleted <
Again, the locking scheme would take much thought.
3.) Write a people command that is consistent. I.e. one that doesn't
> for example show two people to be in the same location if they
> never were. This requires getting a snapshot of the global state.
I don't understand the problem you propose. Data should be accessible
whenever it is not being modified, generally speaking.
> Reimer Behrends
To sum up, I do not think it would be a mudding revolution to multi-thread
the driver. I think it might solve some of the design problems inherent in
some current muds by forcing some synchronization at a very basic level. Then
again, maybe not. :-)
I just thought it might be an interesting project, which might put the
driver in a very different light for growth potential.
dennis
--
/------------------------------------------------------------------------------\
| Dennis Simpson work: den...@canada.sun.com home: daddy!den...@uunet.ca |
| "A bad xhost is a good thing to waste. Here, have a cookie." - Brian Onn |
|"When life hands you a bag of sh*t, it's up to you to plant roses in it." - Me|
\------------------------------------------------------------------------------/
TUB Multi User Domain
>>Precisely. My question, therefore: what do we gain for giving up
>>the benefits of single-threaded-ness?
>Benefits of single-threadedness? I'm not sure there are any beyond
>simpler debugging, and that I think might be a familiarity issue
>more than anything else.
The benefits of single-threadedness are that programs are 1) far
easier to write and 2) less likely to produce errors, especially
irreproducible ones.
[...]
[Several suggestions of solving the problems with semaphores deleted]
My point is that semaphores are far too low-level and do require
insight into an object's implementation to be used.
>3.) Write a people command that is consistent. I.e. one that doesn't
>> for example show two people to be in the same location if they
>> never were. This requires getting a snapshot of the global state.
>I don't understand the problem you propose. Data should be accessible
>whenever it is not being modified, generally speaking.
I was talking about the following problem: 'people' might show two
players to be in the same room while they in fact never have been.
Or similar problems.
Reimer Behrends
Joern Rennecke
>Tony Brannigan (tbr...@oxford.ac.uk) wrote:
>[ ignoreing other stuff... ]
>: threaded. Synchronization would be a problem, as 'safe' inter-object
>: communication does not yet exist.
>: As an example, consider a piece of code strewn throughout the tmi-2
>: mudlib:
>: seteuid(geteuid(previous_object()))
>: This would no longer be sufficent to ensure security, as you have no
>: guarantee that you will not be interupted right there, then be called
>: again from a new object with a different euid, so that when you return
>: to the original you have to wrong euid.
>This is non-sense. previous_object() refers to the object that invoked
>the current function. Stacks are per thread. Thus previous_object() is
>simply the previous frames environment. It doesn't matter if you get
>interrupted or not, the stack for this thread will remain unchanged.
The problem here is not previous_object(), but seteuid() . While it is
hard to do euid based security right (judging from how often it is done
wrong, and how long it took people to get to a thing that has not been
proven bugged yet), it is nonsentical to try this in a multithreaded
environment. The euid of an object is global state information. When
you depend on changing it, you get unnecessary inconsistency problems,
and when you solve these, unnecessary deadlock possibilities. You
should rather only read the stack frame, or pass privileges like data,
like this already can be done with passing arrays, mappings and closures.
The optimum for a multithreaded environment is actually a completely
functional design. The only problem there is that I/O is not present.
(input might have happened before the computation, and output might
hapen after it, but not while the computation is in progress.)
Thus, by eleminating getuid() there is one problem less for a multithreaded
mud. But of course, plenty enough remain.
Amylaar