--On 25.08.2000 16:20 Uhr -0500 David L. Nicol wrote:
>
> 1: make a list of all variables referenced w/in expression
>
> 2: obtain global mutex-setting sceptre (block for this)
>
> 3: block until allowed to set mutexes on entire list in 1
>
> 4: release sceptre
>
> 5: run expression
>
> 6: release all mutexes when leaving it for
> any reason (and redoing 2 through 4 on reentry)
I hope I did not completey misunderstand what "deadlock avoidance strategy"
actually means for David and Steven - if it means what I think it means the
above won't work.
What you describe is more of a strategy to absolutely ensure no data is
destroyed by threading - and it fullfills that role fine - but I think
especially this strategy is prone to deadlocking.
Wouldn't this strategy not also need to track all subs called from within
the expression to work? If not, the following thing could happen
Thread A Thread B
|| ||
enter block with enter block with $c,$d #everything's still fine
$a, $b ||
|| ||
now call sub x call sub y
|| ||
sub x accesses $c sub y accesses $a # => deadlock
Each of the subs waits for the other one freeing its mutexes.
But I think if you start tracking even calls to other blocks you're
running into real trouble as you could have to check mutexes in your
whole program then everytime you try entering a new block. Also, taken
to the extreme, it would not even be possible anymore to construct threads
at all ;-)
Example in Pseudo Code:
create 10 times thread with code:
block start
access $a, $b, $c
do stuff
block end
If I understood the above strategy properly the interpreter couldn't enter
the block with the code for the thread more often than once.
> The problem is, as long as expressions can be within each other,
> and include terms that are multiple expressions, a robust deadlock
> avoidance strategy is required even with cooperative threading.
>
> Or you can just pass the buck to the programmer, and make them use
> explict mutexes and deadlocks while they learn.
Hmm.. I fear the interpreter can never do more than to garantuee that
certain instructions like $a=1; are atomic which could be a hard enough
task to implement for some statements. I don't think anyone has yet found
solutions for automatic deadlock avoidance which still allows your program
to run at acceptable speeds.
Maybe the only solution is to either code in a purely functional style
(which as far as I remember does not have that problems due to a lack of
state, but don't nail me on that statement) or to offer fine grained
synchronization techniques/mutexes which at least leave the programmer in
full control.
--
Markus Peter - SPiN GmbH
[EMAIL PROTECTED]
