I've been working on a StackThread library which allows users to create unlimited lightweight threads which execute round robin style.  The basic idea behind this is that many game actions like animations or menus use loops to perform certain actions, like

void ai_update()
{
while(not_dead)
{
while(my_pos != player_pos)
{
move_toward(player_pos);
end_turn();
}

while(my_pos == player_pos)
{
attack_player()
end_turn();
}
}
}

This code can be replaced with the use of complicated finite state machines, but the result is usually rather hideous.  Here's an example:

void ai_update()
{
switch(my_state)
{
case SEARCHING:
move_toward(player_pos);
if(my_pos == player_pos)
my_state = ATTACKING;
break;

case ATTACKING:
if(my_pos != player_pos)
{
my_state = SEARCHING;
break;
}
attack_player();
break;

case DEAD:
break;
}
}

Another option would be to give each object it's own thread, but this can make the situation even worse especially with concurrency.  I expect that stack threads will improve the readability of code and make it easier to generate novell game logic.

Each stack thread has its own chunk of stack memory, and the stack threading library just switches them round robin style until it returns to the main program.  The main program must call run() once a frame to execute one time slice for each of the stack threads, which have control of the cpu until they yield it.  This is very fast and pretty simple to do, just a pushad/popad and a modified esp. In addition, it also removes all possibility for race conditions/deadlocks since none of the threads are actually running concurrently.

Unfortunately, I've hit a snag.  The library in its current state is usable, the threads can be run, suspended, resumed and killed, but there are no exceptions. Are there any documents out there on how D's exceptions work or any other sorts of info?  I tried sorting it out from the source in deh.c, but it's rather complex.

mclysenk@mtu.edu wrote:
> I've been working on a StackThread library which allows users to create
> unlimited lightweight threads which execute round robin style.  The basic idea
> behind this is that many game actions like animations or menus use loops to
> perform certain actions

Interesting.  You might be interested in a paper that was published recently on this entitled "User-Level Threads for Hierarchically Composed Simulations."  If I remember correctly, it includes a link to a full implementation of the concept that's quite portable (though it is written in C++).  Link is here:

http://members.ozemail.com.au/~mjhodson/papers/papers.html

> Unfortunately, I've hit a snag.  The library in its current state is usable, the
> threads can be run, suspended, resumed and killed, but there are no exceptions.
> Are there any documents out there on how D's exceptions work or any other sorts
> of info?  I tried sorting it out from the source in deh.c, but it's rather
> complex.

That's the place to look.  Basically, the Windows exception handling mechanism builds upon Structured Exception Handling in some respects, but the stack unwinding is done manually.  I'm not sure what you're trying to accomplish, but perhaps it would be enough to wrap the run() function in a try/catch block that passes the exception somewhere appropriate?


Sean

In article <dmid5r$24jc$1@digitaldaemon.com>, Sean Kelly says...
>
>http://members.ozemail.com.au/~mjhodson/papers/papers.html
>

This sounds sort of like the implementation I was looking at, but I couldn't find any source code or downloads.

>> Unfortunately, I've hit a snag.  The library in its current state is usable, the threads can be run, suspended, resumed and killed, but there are no exceptions. Are there any documents out there on how D's exceptions work or any other sorts of info?  I tried sorting it out from the source in deh.c, but it's rather complex.
>
>That's the place to look.  Basically, the Windows exception handling mechanism builds upon Structured Exception Handling in some respects, but the stack unwinding is done manually.  I'm not sure what you're trying to accomplish, but perhaps it would be enough to wrap the run() function in a try/catch block that passes the exception somewhere appropriate?

I tried that.  Exceptions just kill the program outright, not even the typical "This program has generated an error" dialog box.  Another issue that needs to be resolved, is that when a try-catch block is used in a stack thread, it links itself in the SEH chain.  If that thread yields in the block, it needs to save the SEH information otherwise the global exception handling information will become corrupted.  What information besides FS:[0] do I need to save if I want to keep the exception handling stuff intact between threads?

I'm posting the source code in case anyone wants to look at it.

I am very interested in these stackthreads.
Did you found a solution for the exception problem?
Does this work on linux also?

Frank

Yes, I was forgetting to set the stack top and stack bottom in the FS register. I have a working windows version, but unfortunately I don't have linux so I haven't made a linux release.  Here is the source for the windows code that I am currently using.  As soon as I am done with classes I will attempt to create a full library based on the concept, with support for linux.

I intend on creating some more basic synchronization structures as well as splitting up the scheduler to allow for multiple thread sets.

Mik


In article <e0minm$f7n$1@digitaldaemon.com>, Frank Benoit says...
>
>I am very interested in these stackthreads.
>Did you found a solution for the exception problem?
>Does this work on linux also?
>
>Frank

mclysenk@mtu.edu schrieb:
> As soon as I am done with classes I will attempt to create a full library based on the concept, with support for linux.

That would be great.

What I do not understand is ...
Is this complete saving of context really necessary? There is no action
which is interrupted. If you have only cooperative thread switches, than
the switches always occurs in a yield function. Isn't it enough to set
the stackpointer to the other thread and return?

I think of an environment where there is one initial thread (called
master). It can create StackThreads as slaves. Switching is allway only
cooperative and is only between the master and his slaves. The master
thread is also the scheduler. The master has to have a loop where he
calls the slaves, until all slaves are complete.
Switching than should be lightning fast.

I need this for simulation threads. Each thread does one kind of job. If
the thread wants to proceed in time, he can increment his local time and
yield. The master allways calls the slave with the lowest local time.
The whole cluster is a normal pthread and can be interrupted preemptive
by other pthreads.
There are so many switches between these simulation threads, i think
StackThreads can really boost the performance.

>What I do not understand is ...
>Is this complete saving of context really necessary? There is no action
>which is interrupted. If you have only cooperative thread switches, than
>the switches always occurs in a yield function. Isn't it enough to set
>the stackpointer to the other thread and return?
>

Upon consideration, you are correct, I am saving more information than is necessary.  There is no practical reason to maintain the entire floating point state.  However, it is still necessary to save the base pointer as well as the context info in FS, and any other information required by a function call.

>I think of an environment where there is one initial thread (called
>master). It can create StackThreads as slaves. Switching is allway only
>cooperative and is only between the master and his slaves. The master
>thread is also the scheduler. The master has to have a loop where he
>calls the slaves, until all slaves are complete.
>Switching than should be lightning fast.
>
That's the idea.  It's also nice to have 'simple' concurrency for state machines.  For lots of concurrent state machines, stack threads are a better system than the traditional approach, which is to use a gigantic switch statement.  Moreover, they don't have complex synchronization issues like regular threads, since they are nonpreemptive.

I've actually been using them in several of my school projects, and even with the very simple scheduler used in the current version, it has greatly simplified many of my projects.  Once I get some more time, I will conduct a more thorough investigation of their merits and implentation.

Mik