Petter Urkedal <urkedal@ect.unitn.it> wrote:
>
>The aim is to provide a mechanism which makes it *possible* to
>implement a threads library.  To focus to much on threads may
>have obscured the primary argument.
>
>  Consider, for instance, the
>following.  We have a hard problem; at each step there is a series
>of possible paths to take, only a few of which will be successful.
>What we can do is allocate a certain time T for each possibility.
>Execute each path with a *timeout-signal*.  If no computation
>succeeds, allocate time 2T for each possibility; repeat recursively.
>To those familiar with complexity theory, this is an emulation of
>a non-deterministic (Turing-)machine.

The practical problems with permitting exceptions thrown from signal
handlers are not only in the implementation of the virtual machine
(although these are difficult enough).  There are language-semantic
and library-coherence problems as well.

In practice, the only solution I see would be to embargo such
exceptions until certain checkpoints where they could be handled
safely.  That is, the handler would set a flag and return, and
the thread would continue until it reached a checkpoint.

You can code such a checkpoint manually:

  if (thread_cancelled) throw Thread_cancel().

Of course for this you don't need a signal, the (volatile) flag
itself is sufficient.

--
Nathan Myers
ncm@nospam.cantrip.org  http://www.cantrip.org/
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Petter Urkedal wrote:
>
> Upon a signal, the program
> we parse from the saved PC to the mark, and read the data.
> At the next legal point of where an exception may occur, insert
> a break-point of some kind (possibly saving the code and
> temporarily replacing it with a raise-exception.)

This makes the code non-reentrant for multi-threading purposes, unless
you are willing for your breakpoint handler to check what thread is
executing, and ignore the breakpoint if it's the wrong thread. It's the
sort of thing that's often done in debuggers, but it's not for the
fainthearted.

In practice, though, I would think it fairly speed-efficient simply to
include a check of a global variable (volatile sig_atomic_t) at regular
intervals in the code, and throw an exception when it becomes nonzero.
The trick is to call it often enough that your time limits are tested
with sufficient granularity, but not so often that it adds significantly
to the execution time. And if multiple threads all have the same time
limit, then they can all check the same global variable.

--

Ciao,
Paul


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

( Please excuse the lack of citations, where proper; my access
  to newsgroup is very impractical at the moment. )

The aim is to provide a mechanism which makes it *possible* to
implement a threads library.  To focus to much on threads may
have obscured the primary argument.

But never mind the threads.  There are more interesting things one
can do with exception-on-signal.  Consider, for instance, the
following.  We have a hard problem; at each step there is a series
of possible paths to take, only a few of which will be successful.
What we can do is allocate a certain time T for each possibility.
Execute each path with a *timeout-signal*.  If no computation
succeeds, allocate time 2T for each possibility; repeat recursively.
To those familiar with complexity theory, this is an emulation of
a non-deterministic (Touring-)machine.

The complexity of the above algorithms is at best 2 times, at worst
4 times slower than a thread-like computation, if the time spent on
"process/path administration" is much less then the path itself.

Note that the thread-like computation would lead to a fast grow-up
of the number of stack frames.  This means that a computation based
on threads in particular, and on multiple stack-frames in general may
be impractical.

Exception-safe signals opens an interesting programming
technique.  It is possible to implement exceptions on signals in an
efficient manner.  It isn't necessarily trivial, though.  Digital HP
must have found a solution.  If someone knows how they do it, it
will be interesting to hear.  Thinking of a virtual machine I can
think of the following scheme.  It is a suggestion, and somewhat
incomplete.  The purpose is to argue for the possibility.

--------------------------------------------------------------
In each block of code which may declare variables, put a mark.
This may be an instruction, or a set of instructions, which is
not used for any other purpose.  What follows is a set of
(relative) addresses (of code-space) of execution-points where
exceptions may be thrown.  For dtors, the list is empty.  Also,
we store here the address of the clean-up code of the block
(which includes calls to dtors).  Upon a signal, the program
we parse from the saved PC to the mark, and read the data.
At the next legal point of where an exception may occur, insert
a break-point of some kind (possibly saving the code and
temporarily replacing it with a raise-exception.)  Continue
execution in the main program until this point, then proceed
with the clean-up, as if an exception was thrown.  If there
are no legal point to throw an exception within the block,
parse the stack recursively until there is.
--------------------------------------------------------------

Now, there are two problems.  Some code is not written with
the expectation that an exception may occur during execution.
Secondly, it seems that throw() specifications has to be
introduced in every function.  The following would solve both
problems in one stroke, at least if exceptions thrown in signal
handlers are derived from a common class.  Without allowing
exceptions to be raised in signal handlers, we can have a predefined
signal handler which throws `signal_raised'.  Any code which has
throw-specifications, but no throw(signal_raised&), acts the same
way as the destructors; Signal-raised exceptions is not thrown before
the code is finished executed.  If an exception is raised in a
function-call, the unexpected-exception handler is called as usual.
Within try-blocks in such a function, which catches signal_raised,
signal-exceptions may be re-enabled.


In any case, it is not reasonable that the end-user writes signal-
handers himself.  The point is to supply, one way or the other,
this useful part of the hardware.  When it exist as a compatible
feature of the compiler, I believe people will write sensible
libraries to support it.  Including `cross-thread' and `timeout'
exceptions.

The purpose of this letter is not to critisize decitions which
are made, but rather to raise the subject in hope that it will
make an influence so that these mechanisms will somehow be
supported by compilers, and by a future C++ standard.

Petter.



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]