How to detect blocking?

[David Masover]

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.

 

[Robert Klemme]

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?

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

 

[David Masover]

On 11.09.2008 06:48, David Masover wrote:

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.

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".

 

[David Masover]

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?

 

[Robert Klemme]

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?

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

 

[David Masover]

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?

 

[Robert Klemme]

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

 

[David Masover]

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?

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.

 

[Robert Klemme]

What is a "finalizer" in this context?
http://www.ruby-doc.org/core/classes/ObjectSpace.html#M006791


Is it possible to have weak references in Ruby?
http://www.ruby-doc.org/core/classes/WeakRef.html


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

 

[David Masover]

2008/9/14 David Masover <[email protected]>:

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.

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?

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.

 

[Brian Candler]

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.

 

[David Masover]

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.

 

[Brian Candler]

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

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.

 

[Brian Candler]

Looking at your example, your workers still have references to your

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.

 

[David Masover]

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.

 

[Brian Candler]

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.