Home > Archive > Functional > May 2007 > What's the chance of an Erlang thread being starved?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
What's the chance of an Erlang thread being starved?
|
|
|
| Hi all,
I'm new to Erlang and have been trying it out, and reading more about
it when I happened upon this blog post:
http://ezrakilty.net/research/2006/..._in_erlang.html
It basically tries to implement a simulation of 3 masses (planets,
bodies, etc). that act upon each other with gravity. Since there is
no order to messages sent out to different processes, it is possible
that the simulation will become incorrect, if a thread is run more
often than others for a little bit, and hence getting the positions
from other time steps.
That lead me to a question that I haven't been able to find an answer
to, on FAQ or otherwise:
Is the probabililty that any single thread will be run a uniform
distribution in the Erlang system over time? In other words, can I
really think of Erlang thread as being run concurrently on a single
CPU system, or is it possible some threads get run more often then
others (over a long time) because the probability of a thread being
run isn't uniform?
I hope that makes sense. If anyone can answer the question, I'd
appreciate it. Thanks.
Wil
| |
| Simon Richard Clarkstone 2007-05-17, 8:04 am |
| Wil wrote:
> I happened upon this blog post:
>
> http://ezrakilty.net/research/2006/..._in_erlang.html
>
> It basically tries to implement a simulation of 3 masses (planets,
> bodies, etc). that act upon each other with gravity. Since there is
> no order to messages sent out to different processes, it is possible
> that the simulation will become incorrect, if a thread is run more
> often than others for a little bit, and hence getting the positions
> from other time steps.
Are you sure? The article seems to say that the processes keep track of
which positions they know for each timestep, and they cannot compute a
timestep until they have received all the messages for the previous
timestep, so the actual result calculated by the model is deterministic,
even if the order of execution is not.
I don't know about the actual answer to your question though.
(BTW, the MVar-based Haskell solution he gives is surprisingly shorter!
I am not sure if it synchronises properly though, and some of his
coding is bizzare.)
--
Simon Richard Clarkstone:
s.r.cl?rkst?n?@durham.ac.uk/s?m?n.cl?rkst?n?@hotmail.com
"August 9 - I just made my signature file. Its only 6 pages long.
I will have to work on it some more." -- _Diary of an AOL User_
| |
|
|
> Are you sure? The article seems to say that the processes keep track of
> which positions they know for each timestep, and they cannot compute a
> timestep until they have received all the messages for the previous
> timestep, so the actual result calculated by the model is deterministic,
> even if the order of execution is not.
Oh sorry, it did solve the problem as you described. It just caused
me to wonder about whether thread scheduling on a Single CPU for
Erlang was balanced or not. Does it guarantee that all threads are
executed once before a thread gets a 2nd try (no matter what order),
or do threads just run asynchronously and while in the short term, a
thread might get executed a bit more than another, but in the long
term, it all evens out due to law of large numbers?
Wil
| |
| Steve Schafer 2007-05-17, 7:07 pm |
| On 17 May 2007 05:53:42 -0700, Wil <iamwil@gmail.com> wrote:
>Oh sorry, it did solve the problem as you described. It just caused
>me to wonder about whether thread scheduling on a Single CPU for
>Erlang was balanced or not. Does it guarantee that all threads are
>executed once before a thread gets a 2nd try (no matter what order),
>or do threads just run asynchronously and while in the short term, a
>thread might get executed a bit more than another, but in the long
>term, it all evens out due to law of large numbers?
Unless a system advertises itself as "real time," and provides
guaranteed thread scheduling, you should always write your code as if a
thread might be starved for an arbitrarily long time. If processing
depends on order of execution AT ALL, put in the synchronization
yourself. I can't tell you how many times I've come across
multi-threaded code that assumed "fair" thread scheduling, and
subsequently failed when the schedule was upset by a time-hogging
process, or when the software was moved from a single-CPU machine to a
multi-CPU machine.
Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.com/
| |
| Simon Richard Clarkstone 2007-05-17, 7:07 pm |
| Wil wrote:
> Oh sorry, it did solve the problem as you described. It just caused
> me to wonder about whether thread scheduling on a Single CPU for
> Erlang was balanced or not. Does it guarantee that all threads are
> executed once before a thread gets a 2nd try (no matter what order),
> or do threads just run asynchronously and while in the short term, a
> thread might get executed a bit more than another, but in the long
> term, it all evens out due to law of large numbers?
Unless otherwise stated, assume that the scheduler is malicious and
wants your program to break. :-P This requires thinking about a huge
number of possible orders of execution, or getting a high-powered
parallelism/concurrency model (STM, message-passing, streams,
data-parallelism, etc).
--
Simon Richard Clarkstone:
s.r.cl?rkst?n?@durham.ac.uk/s?m?n.cl?rkst?n?@hotmail.com
"August 9 - I just made my signature file. Its only 6 pages long.
I will have to work on it some more." -- _Diary of an AOL User_
| |
| dbenson@eecs.wsu.edu 2007-05-17, 10:06 pm |
| In Concurrent ML (CML), which runs on (at least) SML/NJ, the running
thread is pre-empted after 10 or 20 microseconds (your choice) if it
is still running. The first thread on the ready-to-run queue goes
next. The thread which still wants to consume more resources goes onto
a secondary queue. The details might be in John Reppy's book. If not
the CML scheduling code is easy enough to read.
I have used this extensively (over 50,000 lines of code, if that means
anything). My experience is that thread starvation has never a problem.
| |
| filippo pacini 2007-05-18, 7:05 pm |
| Hi,
here's an interesting post from the erlang-question mailing list
explaining how the erlang scheduler works.
http://www.erlang.org/ml-archive/er...4/msg00072.html
Filippo
Wil wrote:
> Hi all,
>
> I'm new to Erlang and have been trying it out, and reading more about
> it when I happened upon this blog post:
>
> http://ezrakilty.net/research/2006/..._in_erlang.html
>
> It basically tries to implement a simulation of 3 masses (planets,
> bodies, etc). that act upon each other with gravity. Since there is
> no order to messages sent out to different processes, it is possible
> that the simulation will become incorrect, if a thread is run more
> often than others for a little bit, and hence getting the positions
> from other time steps.
>
> That lead me to a question that I haven't been able to find an answer
> to, on FAQ or otherwise:
>
> Is the probabililty that any single thread will be run a uniform
> distribution in the Erlang system over time? In other words, can I
> really think of Erlang thread as being run concurrently on a single
> CPU system, or is it possible some threads get run more often then
> others (over a long time) because the probability of a thread being
> run isn't uniform?
>
> I hope that makes sense. If anyone can answer the question, I'd
> appreciate it. Thanks.
>
> Wil
>
--
Filippo Pacini
| |
| Ulf Wiger 2007-05-21, 10:05 pm |
| >>>>> "Wil" == Wil <iamwil@gmail.com> writes:
Wil> Is the probabililty that any single thread will be run a
Wil> uniform distribution in the Erlang system over time? In other
Wil> words, can I really think of Erlang thread as being run
Wil> concurrently on a single CPU system, or is it possible some
Wil> threads get run more often then others (over a long time)
Wil> because the probability of a thread being run isn't uniform?
Someone else posted a link to an old post of mine regarding how
the scheduler works, so I'll just add a few comments with that
in mind:
- There is now an SMP version of the Erlang scheduler. It uses
a configurable number of scheduler threads which pick the
next job from a shared job queue. The scheduler threads are
scheduled preemptively by the underlying OS.
- Since the scheduler is based on "reduction counting" (basically
counting function calls), there is every chance that a process
will be given more CPU time(*) than others over a long time. It is
also possible that a process will be given more time slices than
others, if it yields often (either implicitly by entering a
receive clause or explicitly by calling erlang:yield()). It is
reasonably uncommon for processes to consume the entire time slice.
- John Hughes reported difficulties using QuickCheck for testing
concurrency patterns in Erlang, due to the fact that the scheduler
was too predictable. That is, given a sequence of spawns, message
passing, receives, and barring external interference, the scheduler
will run the code _exactly_ the same way every time. This doesn't
hold for SMP erlang, but is still true for the single-threaded version.
BR,
Ulf W
(*) Some operations count as one reduction even though they may
differ in terms of CPU cost. In some obvious cases (e.g. file
operations), function calls are penalised with an extra bump of
the reduction counter. This is a crude way of evening things out
a little bit.
--
Ulf Wiger, Senior Specialist,
/ / / Architecture & Design of Carrier-Class Software
/ / / Team Leader, Software Characteristics
/ / / Ericsson AB, IMS Gateways
| |
|
| On May 21, 11:19 am, Ulf Wiger <etxu...@cbe.ericsson.se> wrote:
> ...
> - John Hughes reported difficulties using QuickCheck for testing
> concurrency patterns in Erlang, due to the fact that the scheduler
> was too predictable. ...
Would randomising the target count help?
> (*) Some operations count as one reduction even though they may
> differ in terms of CPU cost. In some obvious cases (e.g. file
> operations), function calls are penalised with an extra bump of
> the reduction counter. This is a crude way of evening things out
> a little bit.
>
> --
> Ulf Wiger, Senior Specialist,
> / / / Architecture & Design of Carrier-Class Software
> / / / Team Leader, Software Characteristics
> / / / Ericsson AB, IMS Gateways
| |
| Ulf Wiger 2007-05-25, 10:05 pm |
| >>>>> "toby" == toby <toby@telegraphics.com.au> writes:
toby> On May 21, 11:19 am, Ulf Wiger <etxu...@cbe.ericsson.se>
toby> wrote:[color=darkred]
toby> Would randomising the target count help?
That's been suggested (rather, that the timeslice be configurable),
but this of course requires a change to the virtual machine.
Another way to accomplish some increased interleaving is to
(maybe dynamically) rewrite the code, inserting calls to
erlang:yield() here and there.
The opposite problem exists on the SMP version. Here, scheduling
is not deterministic enough for the QuickCheck shrinking algorithm
to be really effective for concurrency-related bugs.
John will probably think of something - he usually does... (:
BR,
Ulf W
--
Ulf Wiger, Senior Specialist,
/ / / Architecture & Design of Carrier-Class Software
/ / / Team Leader, Software Characteristics
/ / / Ericsson AB, IMS Gateways
|
|
|
|
|