How to detect blocking?

Ruby
#1

I’ve been (barely, occasionally) writing an Actor system for Ruby.

It was actually pretty easy, when I was doing one thread per actor, but
that
has some serious drawbacks – among them that threads can’t be garbage
collected (can they?), whereas actors really should be collectable.

So now I’m considering running a smaller number of threads – at least
one per
usable CPU (so at least one on mainline Ruby, more on JRuby) – but
more,
since operations might block.

The problem is, how do I detect a blocked thread, and execute some code
when
that happens?

The best I can think of is to poll, checking for #stop?, but that’s
hackish,
and performance would be awful. Poll too often, and I burn CPU – not
often
enough, and I end up with large windows of my app waiting for the poll
thread
to wake up.

#2

On 11.09.2008 06:48, David M. wrote:

The problem is, how do I detect a blocked thread, and execute some code when
that happens?

Block on what? IO? In that case you probably want to use more threads
as Ruby does handle this nicely.

The best I can think of is to poll, checking for #stop?, but that’s hackish,
and performance would be awful. Poll too often, and I burn CPU – not often
enough, and I end up with large windows of my app waiting for the poll thread
to wake up.

I do not have a clear idea of your app but usually with multiple threads
you use some form of synchronization (blocking queues, condition
variables etc.). HTH

Kind regards

robert

#3

On Thursday 11 September 2008 01:33:25 Robert K. wrote:

On 11.09.2008 06:48, David M. wrote:

The problem is, how do I detect a blocked thread, and execute some code
when

that happens?

Block on what? IO?

Mostly, yes, but really any blocking operation. Could be a mutex. Could
be a
sleep call. Could be it was deliberately suspended.

In other words, anything that would cause Thread#stop? to return true.

In that case you probably want to use more threads
as Ruby does handle this nicely.

Maybe not as nicely as I’d like, though – I imagine 1.9’s OS threads
are
heavier. And it presents problems with garbage-collection, with my
current
design.

The best I can think of is to poll, checking for #stop?, but that’s
hackish,

and performance would be awful. Poll too often, and I burn CPU – not
often

enough, and I end up with large windows of my app waiting for the poll
thread

to wake up.

I do not have a clear idea of your app

It’s an actor library, which means apps will be written for it.
(Maybe. I might still drop it and just use Dramatis.)

but usually with multiple threads
you use some form of synchronization (blocking queues, condition
variables etc.).

Right. An actor library is designed to abstract all of that away.

Let me phrase it differently – it’s like having a hundred thousand
fibers
that I want to execute at least once. I don’t need to spawn a hundred
thousand threads – and I can’t, I remember the limit being around three
thousand in 1.9, and I really only need one or two.

But if one of those fibers blocks somewhere, I want to spawn another
thread.
Ideally, I need N + S threads, where N is the number of CPUs my program
can
use concurrently, and S is the number of other threads which are
stopped.

That’s oversimplifying a bit – but if you want to know more, read about
Erlang’s process model. I’m trying to do something like that. The
technical
term for that is the “actor model”.

#4

On 13.09.2008 22:59, David M. wrote:

end
to the thread, so the thread isn’t going to be doing anything useful at this
Thread.new do
Is there any way to handle this gracefully? For example: Any way to tell that
the queue has gone out of scope, there? Or any way to fire any code right
before an object is collected?

Or do I always have to remember to kill that thread explicitly, somehow – by
sending that nil, for example?

The usual solution is that the queue will not “go out of scope” before
the thread dies. In a farmer worker scenario (or however you call it)
the farmer distributes work and is also often responsible for collecting
results. If there is no work left he needs to notify workers of this
fact so they can react appropriately (die).

If I implement such a scenario I define a terminator (you used nil for
that) that is sent n times down the queue (n = # threads). Then the
main thread joins all threads and that way you can be sure that all work
is done when main thread exits.

Kind regards

robert

#5

On Sunday 14 September 2008 03:24:53 Robert K. wrote:

The usual solution is that the queue will not “go out of scope” before
the thread dies.

Right.

In a farmer worker scenario (or however you call it)
the farmer distributes work and is also often responsible for collecting
results. If there is no work left he needs to notify workers of this
fact so they can react appropriately (die).

I’d like to detect “no work left” as a case of the “farmer” going out of
scope, if possible.

So, it sounds like you’re telling me all the “usual” ways of doing this.
Is there no way to make my suggestion work?

#6

Suppose I start a worker thread, like so:

require ‘thread’
queue = Queue.new

Thread.new do
loop do
# Suppose this does something useful…
puts queue.pop
end
end

And I start sending things to that queue:

queue.push ‘Hello, world!’
queue.push ‘(from inside the thread)’

…and so on.

Now, at some point, the queue will fall out of scope – at which point,
I’m
obviously not going to push anything onto it. It’s also the only way to
talk
to the thread, so the thread isn’t going to be doing anything useful at
this
point.

I’d like to collect that thread, but, of course, that’s really
impossible.
After all, the loop will never end, so the thread will never exit
normally.
Without solving the Halting Problem, Ruby can’t know that the thread
won’t do
anything useful, even if nothing else refers to it – maybe it will push
something onto that queue, after all.

Now, I know the logical solution to this particular problem:

Thread.new do
until (item = queue.pop).nil?
puts item
end
end

But then, I have to remember to send that message just before the queue
goes
out of scope:

queue.push nil

Is there any way to handle this gracefully? For example: Any way to tell
that
the queue has gone out of scope, there? Or any way to fire any code
right
before an object is collected?

Or do I always have to remember to kill that thread explicitly, somehow
– by
sending that nil, for example?

#7

On 14.09.2008 19:27, David M. wrote:

On Sunday 14 September 2008 03:24:53 Robert K. wrote:

In a farmer worker scenario (or however you call it)
the farmer distributes work and is also often responsible for collecting
results. If there is no work left he needs to notify workers of this
fact so they can react appropriately (die).

I’d like to detect “no work left” as a case of the “farmer” going out of
scope, if possible.

There is no hook in Ruby that is called when the scope of a variable
ends. An object without any references can be garbage collected. But a
finalizer won’t work because then the object is gone already. Also, the
queue that connects farmer and workers will still have references even
if the farmer is gone, so the finalizer will never be called…

So, it sounds like you’re telling me all the “usual” ways of doing this.

What’s wrong with using the usual ways?

Is there no way to make my suggestion work?

You can use begin ensure end. This will guarantee that action will be
taken even in case of an exception. If that’s what you’re after.

Cheers

robert

#8

On Sunday 14 September 2008 15:22:53 Robert K. wrote:

There is no hook in Ruby that is called when the scope of a variable
ends. An object without any references can be garbage collected. But a
finalizer won’t work because then the object is gone already.

What is a “finalizer” in this context?

Also, the
queue that connects farmer and workers will still have references even
if the farmer is gone, so the finalizer will never be called…

Is it possible to have weak references in Ruby?

So, it sounds like you’re telling me all the “usual” ways of doing this.

What’s wrong with using the usual ways?

The usual ways still force me to explicitly clean up after my worker
threads.
This is irritating, philosophically – if I wanted to do manual resource
management, I’d write C++, not Ruby.

It also means that if I’m implementing any kind of library on top of
that, I
have to force all my users to do the same manual cleanup.

#9

2008/9/14 David M. [email protected]:

On Sunday 14 September 2008 15:22:53 Robert K. wrote:

There is no hook in Ruby that is called when the scope of a variable
ends. An object without any references can be garbage collected. But a
finalizer won’t work because then the object is gone already.

What is a “finalizer” in this context?

http://www.ruby-doc.org/core/classes/ObjectSpace.html#M006791

Also, the
queue that connects farmer and workers will still have references even
if the farmer is gone, so the finalizer will never be called…

Is it possible to have weak references in Ruby?

http://www.ruby-doc.org/core/classes/WeakRef.html

So, it sounds like you’re telling me all the “usual” ways of doing this.

What’s wrong with using the usual ways?

The usual ways still force me to explicitly clean up after my worker threads.
This is irritating, philosophically – if I wanted to do manual resource
management, I’d write C++, not Ruby.

You have to close file handles as well (even if you use the block form
of File.open you take care of this in a way).

It also means that if I’m implementing any kind of library on top of that, I
have to force all my users to do the same manual cleanup.

No, because you can make that part of the library. At least you can
built your library in a way that it will invoke a cleanup hook which
you define as empty method for application specific cleanup so users
of the lib do not have to but can add cleanup functionality. Cleanup
of the framework is done automatically of course. Note that there are
already libraries that abstract such a scenario.

Cheers

robert

#10

On Monday 15 September 2008 03:55:06 Robert K. wrote:

2008/9/14 David M. [email protected]:

What is a “finalizer” in this context?

http://www.ruby-doc.org/core/classes/ObjectSpace.html#M006791

Cool.

Can they be lambdas/closures? If so, I think I’ve got what I need –
it’s just
going to be very tricky to get right.

Is it possible to have weak references in Ruby?

http://www.ruby-doc.org/core/classes/WeakRef.html

Hmm. It mentions WeakRef::RefError. While I’m at it – is it safe to
poke at
WeakRefs to see if they’re still alive?

(That is: If the object is gone, will I always get a RefError, or is it
ever
possible to get something undefined or bad/wrong?)

You have to close file handles as well (even if you use the block form
of File.open you take care of this in a way).

The block form of File.open is a good example, though, and it’s also an
API
which is tolerable, in the common case.

But even here, it might be useful to wrap it in some sort of
garbage-collectable object – assuming collection run on every single
object
when the program exits.

To be usable, of course, you’d have to force collection to occur when
running
out of file descriptors, in case one is being held open by an object
that
hasn’t been collected… right?

It also means that if I’m implementing any kind of library on top of that,
I

have to force all my users to do the same manual cleanup.

No, because you can make that part of the library. At least you can
built your library in a way that it will invoke a cleanup hook which
you define as empty method for application specific cleanup so users
of the lib do not have to but can add cleanup functionality. Cleanup
of the framework is done automatically of course.

The problem is, with the API that it exposes, I don’t know when to have
the
framework cleanup, other than when a particular object has no more
strong
references to it. I’m not worried about the app-specific cleanup.

The idea is: Apps can be built as they always were, just some objects
are
really actors (object + thread). So, where an app would let an object
fall
out of scope (and thus be collected), it can also let an actor fall out
of
scope (and thus be collected, and have the thread closed, too).

Thanks for your help. I’m probably going to have to spend a few solid
hours
(days?) playing with this to be sure, but it looks like I can build
this.

#11

On Tuesday 16 September 2008 03:55:18 Brian C. wrote:

I’d like to detect “no work left” as a case of the “farmer” going out of
scope, if possible.

In principle, if the Farmer is an object, then it can have a finalizer
which sends the terminate message to all the workers. The finalizer
won’t be called immediately when the Farmer goes out of scope, but at
some time later.

That’s fine. As long as “some time” is reasonably soon, I’m not
intending to
assume anything about when the workers are terminated.

Ideally, I would be able to trigger collection manually.

In practice, it isn’t easy to do.

That’s fine. I intend to solve this once, and I don’t mind a challenge!

The finalizer is only called after
the farmer has been destroyed, so you can’t use any methods or instance
variables on it.

However, wouldn’t it be scoped? I could as easily set a local variable
when I
create the finalizer, right?

Still doesn’t answer the other part I need: Weak references. I need to
know
exactly how I can use them, and how I can’t – what might be dangerous
about
them, for example.

Looking at your example, your workers still have references to your
queue and
to the farmer, which means the farmer will never be collected.

#12

I’d like to detect “no work left” as a case of the “farmer” going out of
scope, if possible.

In principle, if the Farmer is an object, then it can have a finalizer
which sends the terminate message to all the workers. The finalizer
won’t be called immediately when the Farmer goes out of scope, but at
some time later.

In practice, it isn’t easy to do. The finalizer is only called after
the farmer has been destroyed, so you can’t use any methods or instance
variables on it. And I find it very hard to demonstrate in practice. The
following attempt is broken and I can’t see what’s wrong:

#---- 8< --------------
require ‘thread’

class Farmer
attr_reader :queue, :workers

def self.cleanup(workers)
  lambda { |id|
    workers.each { |t| p t; Thread.kill(t) }
  }
end

def self.create
  farmer = new
  workers = farmer.workers
  ObjectSpace.define_finalizer(farmer, cleanup(workers))
  farmer
end

def self.make_worker(queue)
  Thread.new do
    loop do
      puts queue.pop
    end
  end
end

def initialize
  @workers = []
  @queue = Queue.new
end

def add_worker
  @workers << self.class.make_worker(queue)
end

def push(x)
  @queue.push(x)
end

end

def testit
f = Farmer.create
3.times { f.add_worker }
f.push(“hello”)
f.push(“world”)
end

10.times { testit }
GC.start

For some reason the farmers still exist

ObjectSpace.each_object(Farmer) { |f| p f }
puts “End of the world”

sleep 1
#---- 8< --------------

When I run this, I see that the finalizers are indeed called when ruby
terminates - but not when garbage-collection is requested. Indeed, the
Farmers remain in ObjectSpace even after garbage collection. I can’t see
why that should be.

I’ve tried to ensure that neither the finalizer lambda nor the worker
threads have the farmer bound to their environment, and I can’t see what
else is holding a reference. This is with ruby 1.8.6 (2008-03-03
patchlevel 114) [i686-linux]

Regards,

Brian.

#13

David M. wrote:

The finalizer is only called after
the farmer has been destroyed, so you can’t use any methods or instance
variables on it.

However, wouldn’t it be scoped? I could as easily set a local variable
when I
create the finalizer, right?

Yes, as long as the local variable (bound into the finalizer) refers to
objects held by the farmer, not the farmer itself. Otherwise the
existence of the finalizer holding a reference to the farmer will in
itself prevent the farmer from being garbage collected, so the finalizer
can never be called.

I started a separate thread about why garbage collection isn’t happening
in this case:
http://www.ruby-forum.com/topic/165961

It’s looking suspiciously like a bug in ruby-1.8, since apparently
ruby-1.9 behaves as expected. But there’s been no comment so far from an
expert in Ruby internals.

Still doesn’t answer the other part I need: Weak references.

/usr/lib/ruby/1.8/weakref.rb :slight_smile:

I need to
know
exactly how I can use them, and how I can’t – what might be dangerous
about
them, for example.

I can’t see any particular pitfalls. But equally I can’t see any reason
why you want weak refs in this example.

Looking at your example, your workers still have references to your
queue and
to the farmer, which means the farmer will never be collected.

I don’t think you understand. If A holds a reference to B, then that
may(*) prevent B from being garbage-collected, but it definitely doesn’t
prevent A from being garbage-collected.

So, as long as the farmer exists, then the workers and the queue will
exist. If no-one holds a reference to the farmer, then the farmer will
be GC’d. Then if there no references to the worker or queue, other than
those which were held by the farmer, then the worker or queue also will
be garbage-collected. This is normal behaviour of a “normal” reference
from farmer to worker/queue, not a weak ref.

Regards,

Brian.

(*) I say “may” because Ruby’s garbage collector is mark-and-sweep. If
there is a isolated graph of objects, i.e. the only references to these
objects are from other objects within this graph, then none of them will
get marked, and so they’ll all get swept at once. So in this case, the
farmer and the workers may be GC’d at the same time, even though the
farmer holds references to the workers.

#14

Looking at your example, your workers still have references to your
queue and
to the farmer, which means the farmer will never be collected.

I don’t think you understand. If A holds a reference to B, then that
may(*) prevent B from being garbage-collected, but it definitely doesn’t
prevent A from being garbage-collected.

Sorry I didn’t read your post exactly - I overlooked that you wanted the
workers to contain a reference to the farmer. But even then the
conclusion is still correct.

If the farmer and the workers form an isolated subgraph of objects -
e.g. there are no other references to them from the stack or from global
variables or from other objects - then they will all be garbage
collected together.

#15

On Friday 19 September 2008 05:31:07 Brian C. wrote:

If the farmer and the workers form an isolated subgraph of objects -
e.g. there are no other references to them from the stack or from global
variables or from other objects - then they will all be garbage
collected together.

Unless the worker includes a running Thread. Since Ruby does not solve
the
Halting Problem, it can’t predict what that Thread will do, and thus,
can’t
discard anything still referenced by the thread.

Now, once I’ve stopped the thread, it should be able to discard all of
it. But
I need it to collect the farmer to trigger my finalizer, and I need the
finalizer to cleanup the threads.

And there is, indirectly, a reference, by way of a queue. But I suppose
the
queue won’t refer back to the farmer, so that should work well.

#16

David M. wrote:

If the farmer and the workers form an isolated subgraph of objects -
e.g. there are no other references to them from the stack or from global
variables or from other objects - then they will all be garbage
collected together.

Unless the worker includes a running Thread. Since Ruby does not solve
the
Halting Problem, it can’t predict what that Thread will do, and thus,
can’t
discard anything still referenced by the thread.

A thread of execution has its own stack, and any object references on
the stack will prevent those objects from being garbage-collected, yes.

If you’re saying that each worker is a thread, and each worker has a
reference to the farmer, then indeed that will stop the farmer from
being garbage-collected.

But I see no reason for the worker to have a reference to the farmer.
All it needs is a reference to the queue, to pick up things to do. The
input queue can also contain instructions as to where to send the
results, or you can have a separate output queue.

Then in theory, when no-one has a reference to the farmer it will be
GC’d, and at that point the finalizer can deal with all the threads (the
finalizer will need to have access to the queue to send ‘stop’ messages,
or to the array of threads in order to kill them)

Unfortunately in practice with ruby-1.8, the farmer seems to end up on
the thread’s stack too for some reason. But even then it can be made to
work, with care: you need to create all the worker threads first, then
create the farmer object to hold them. As long as you don’t need to add
new workers dynamically, that should be fine.