www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Stack Threads and Exceptions

reply mclysenk mtu.edu writes:
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.
Nov 29 2005
parent reply Sean Kelly <sean f4.ca> writes:
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
Nov 29 2005
parent reply mclysenk mtu.edu writes:
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.
Nov 29 2005
parent reply Frank Benoit <benoit__ __tionex.de> writes:
I am very interested in these stackthreads.
Did you found a solution for the exception problem?
Does this work on linux also?

Frank
Apr 01 2006
parent reply mclysenk mtu.edu writes:
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
Apr 02 2006
parent reply Frank Benoit <benoit__ __tionex.de> writes:
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.
Apr 03 2006
parent mclysenk mtu.edu writes:
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.



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
Apr 04 2006