Forum: Ruby Ruby Multithreaded producer-consumer problem

Hi,
I started on Ruby less than a week ago but have already come to
appreciate the power of the language. I am trying my hands on a classic
producer-consumer problem, implemented as an Orange tree (c.f.
http://pine.fm/LearnToProgram/?Chapter=09). The Orange tree grows each
year until it dies and produces a random number of Oranges each year
(Producer). Oranges can be picked as long there are any on the tree
(Consumer).

I've got two problems here:

1) The attached code gives me the following exception:
/Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:84:
warning: instance variable @orange_tree not initialized
/Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:84:in
`<class:Worker>': undefined method `age' for nil:NilClass
(NoMethodError)
  from
/Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:45:in
`<main>'

2) I am not sure that the multithreading part is correctly coded.

Any help is very much appreciated. I've got myself a couple of books,
including "Programming Ruby" and "The Ruby Programming Language" but
none of them contain a true "producer-consumer problem".

You might take a look at Celluloid:

http://celluloid.io/

Subject: Ruby Multithreaded producer-consumer problem
  Date: gio 14 feb 13 12:50:48 +0900

Quoting Abhijit Sarkar (lists@ruby-forum.com):

> 1) The attached code gives me the following exception:
> /Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:84:
> warning: instance variable @orange_tree not initialized
> /Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:84:in
> `<class:Worker>': undefined method `age' for nil:NilClass
> (NoMethodError)
>   from
> /Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:45:in
> `<main>'

Instance variables are only accessible from within methods. Lines
83-86 are not within a method. Take lines 83-86 out of the class
definition, and change them to something like:

worker=Worker.new(Mutex.new,ConditionVariable.new,OrangeTree.new)
worker.do_some_work
until(worker.orange_tree.age==OrangeTree::AGE_TO_DIE)
  # wait for the Threads to finish
end

Of course, variable orange_tree has to be visible from the outside, so
you have to add something like

attr_reader(:orange_tree)

at the beginning of the Worker class. This way you should not have
those exceptions anymore.

Carlo

Tony Arcieri wrote in post #1096818:
> You might take a look at Celluloid:

Thanks but no. As I mentioned, I am new to Ruby and am practising. A
multithreading framework would not do much good in my learning process.

Carlo E. Prelz wrote in post #1096828:

> Instance variables are only accessible from within methods. Lines
> 83-86 are not within a method. Take lines 83-86 out of the class
> definition, and change them to something like:
>
> worker=Worker.new(Mutex.new,ConditionVariable.new,OrangeTree.new)
> worker.do_some_work
> until(worker.orange_tree.age==OrangeTree::AGE_TO_DIE)
>   # wait for the Threads to finish
> end
>
> Of course, variable orange_tree has to be visible from the outside, so
> you have to add something like
>
> attr_reader(:orange_tree)
>
> at the beginning of the Worker class. This way you should not have
> those exceptions anymore.

After making the changes you suggested and adding joins inside class
Worker, (file attached) I am now getting:

Orange picker going to sleep for 5
Orange picker woke up after sleeping for 5
Sorry, no Oranges to pick
Orange picker waiting patiently...
Age increaser going to sleep for 2
Age increaser woke up after sleeping for 2
/Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:76:in
`join': deadlock detected (fatal)
  from
/Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:76:in
`do_some_work'
  from
/Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:82:in
`<class:Worker>'
  from
/Users/Abhijit/Workspace/eclipse/ruby/learn_to_program/orange_tree.rb:39:in
`<main>'

That's great. That's the real problem the author wants you to solve. Sit 
down with some paper and crayons / colored pencils and draw a picture of 
the objects and what they have access to via your code. Then act out the 
process. Can you understand how the deadlock occurs? What can you do to 
avoid it?

You might want to google dining philosophers for another example.

Ryan Davis wrote in post #1096951:
> That's great. That's the real problem the author wants you to solve. Sit
> down with some paper and crayons / colored pencils and draw a picture of
> the objects and what they have access to via your code. Then act out the
> process. Can you understand how the deadlock occurs? What can you do to
> avoid it?

If I were able to figure out the issue myself, why would I be sitting
here having this conversation? Do you see the problem? If yes, would you
be kind enough to point it out to me? If you do not see the problem
yourself, well, what can I say.

That's not to say that I am going to sit with my thumb in my mouth while
someone else solves the problem for me. I am trying but a little help
goes a long way.

> You might want to Google dining philosophers for another example.

I am very much aware of the Dining Philosophers example. It is not a
producer-consumer problem. It suggests a possible way to avoid deadlocks
which is to lock two shared resources in the same order in two competing
threads. I do not see the relevance with my issue here as I am not
dealing with two shared resources.

On Feb 14, 2013, at 13:10 , Abhijit Sarkar <lists@ruby-forum.com> wrote:

> be kind enough to point it out to me? If you do not see the problem
> yourself, well, what can I say.

If I knew you were going to act like that I wouldn't have bothered 
writing in the first place.

Sit down _away_ from your code. Draw out the problem on _paper_. Act it 
out.

I actually like to act it out with one person per object, but sometimes 
that is not feasible.

If you can't figure it out from there, you're probably not drawing the 
problem out correctly or completely.

I rewrote the code using MonitorMixin and then back to using Mutex, same
result. I used 2 ConditionVariable, same result :( If it's not working,
it's certainly not for the lack of trying.

Abhijit Sarkar wrote in post #1097009:
> I rewrote the code using MonitorMixin and then back to using Mutex, same
> result. I used 2 ConditionVariable, same result :( If it's not working,
> it's certainly not for the lack of trying.

How much have you tried? Your description not showing that.. You should 
Google first.. Then try those all. Let us know what have you tried and 
what you got.

thanks

Love U Ruby wrote in post #1097084:
> How much have you tried? Your description not showing that.. You should
> Google first.. Then try those all. Let us know what have you tried and
> what you got.

Look who's talking :) the 1d10t trying to get even because he got 
slapped on the wrist. Funny.

Abhijit Sarkar wrote in post #1097123:
> Love U Ruby wrote in post #1097084:
>> How much have you tried? Your description not showing that.. You should
>> Google first.. Then try those all. Let us know what have you tried and
>> what you got.
>
> Look who's talking :) the 1d10t trying to get even because he got
> slapped on the wrist. Funny.


Don't make me rude on you. don't think yourself master on that. because 
you didn't invent Ruby.You are learning and me too. behave like an 
educated guy.

No one here who can slap me .... before that he will get it.

Love U Ruby wrote in post #1097126:
> No one here who can slap me .... before that he will get it.
No one said anything about slapping you, though you have it coming for
sure. It's an English phrase which, as usual, you did not try to
understand by Googling. Why am I not surprised?
I am curious though, how will you hurt anyone in the forum? Are you
going to piss yourself in anger and expect them to have a heart attack
in content?

Abhijit Sarkar wrote in post #1097129:
> Love U Ruby wrote in post #1097126:
>> No one here who can slap me .... before that he will get it.
> No one said anything about slapping you, though you have it coming for
> sure. It's an English phrase which, as usual, you did not try to
> understand by Googling. Why am I not surprised?
> I am curious though, how will you hurt anyone in the forum? Are you
> going to piss yourself in anger and expect them to have a heart attack
> in content?


Don't try to escape and you made that comments first. This is English 
language forum. And I am least interested to do that. I don't want to be 
off topic.

go your own way...

D. Deryl Downey wrote:
> Can you show the MonitorMixin complete error?

Entering Orange picker sync block...Entering age increaser sync block...

Entered age increaser sync block
Entered Orange picker sync block
C:/workspace/eclipse/ruby/learn_to_program/orange_tree.rb:108:in `join':
deadlock detected (fatal)
  from C:/workspace/eclipse/ruby/learn_to_program/orange_tree.rb:108:in
`do_some_work'
  from C:/workspace/eclipse/ruby/learn_to_program/orange_tree.rb:116:in
`block in <class:Worker>'
  from C:/workspace/eclipse/ruby/learn_to_program/orange_tree.rb:115:in
`times'
  from C:/workspace/eclipse/ruby/learn_to_program/orange_tree.rb:115:in
`<class:Worker>'
  from C:/workspace/eclipse/ruby/learn_to_program/orange_tree.rb:45:in
`<main>'

Bump!
A problem unsolved keeps bugging me, I seriously hope the great minds 
here would have something for me.

On Sun, Feb 24, 2013 at 2:30 AM, Abhijit Sarkar <lists@ruby-forum.com> 
wrote:
> Bump!
> A problem unsolved keeps bugging me, I seriously hope the great minds
> here would have something for me.

Just so we are sure we are all on the same level, can you please
repost the current version of the code?  It may also help to get a
github account (free) and post all files in a single gist. That would
also allow for version tracking.  It would also be help readability to
get rid of all the comments which contain alternative code.

I rechecked your posts and this seems to be the most recent version:
http://www.ruby-forum.com/attachment/8132/orange_tree.rb

I haven't fully understood what you are trying to do here but a few
things occurred to me

- OrangeTree apparently is the shared resource yet it does not include
any synchronization logic.
- you create the Worker inside Worker class context. While that may
actually work it's simpler to read to have your main program logic on
the top level.
- You have picked bad names for condition variables which convey
nothing about their intended semantics.
- Insert this line at the top of the script and you'll know what's going 
on:

Thread.abort_on_exception = true

Could be that you hit this bug - although I'd be surprised. What
version are you using.
https://bugs.ruby-lang.org/issues/6288

Kind regards

robert

On Sun, Feb 24, 2013 at 1:30 AM, Abhijit Sarkar <lists@ruby-forum.com> 
wrote:
> Bump!
> A problem unsolved keeps bugging me, I seriously hope the great minds
> here would have something for me.
>

Hi,

I've created a gist at https://gist.github.com/seanohalpin/5023887
which attempts to make your program do what I think it's trying to do.
I've tried to keep as close to your original as possible so you can
see the differences more easily. There are other things I would change
but they are not relevant to this discussion. This is running on ruby
1.9.3p194.

A couple of points:

- it's really not clear what you're trying to do - a problem
definition would help.
- as Robert pointed out, using Thread.abort_on_exception = true would
help. You would have found that Math does not have a rand method for
example.
- the only shared state you need to protect access to is the
@orange_count variable - it's unnecessary to use synchronize around
the whole loop. Also, that logic would probably be better encapsulated
in the OrangeTree class itself.
- you don't check whether the exit condition for the orange_picker
thread is true before waiting on the CV. This will halt your thread
indefinitely when the age_increaser thread exits before the
orange_picker thread starts the wait. Multiple checking of conditions
is an unfortunate but necessary aspect of multi-threaded programming
with mutexes, etc.
- lastly, before you go down the rabbit hole of mutexes and condition
variables, I would strongly advise you adopt the Actor model to
isolate access to state and use queues to communicate between threads.
You will save yourself a world of pain. BTW Tony's advice to look at
DCell is good advice!

Regards,
Sean

On Sun, Feb 24, 2013 at 2:12 PM, Sean O'Halpin <sean.ohalpin@gmail.com> 
wrote:
> BTW Tony's advice to look at DCell is good advice!

s/DCell/Celluloid/

First of all, Sean's modified version works!. It does not run into the
deadlock that mine does.
That being said, I'll answer his questions below and, for newbies who
are facing similar problem like mine, also point out the difference that
made his code work and mine not.

Sean O'halpin wrote in post #1098770:
> - it's really not clear what you're trying to do - a problem
> definition would help.
When I wrote this program about 3 weeks back, I was just starting to
learn Ruby and I picked on different aspects of the language that I
thought I needed practice on.
> - as Robert pointed out, using Thread.abort_on_exception = true would
> help. You would have found that Math does not have a rand method for
> example.
Lesson learnt, didn't know. I guess this is one issue with interpreted
languages that you don't see most problems until runtime.
> - the only shared state you need to protect access to is the
> @orange_count variable - it's unnecessary to use synchronize around
> the whole loop.
True. I thought then that @age also needs protection but on closer
review now, it doesn't.
> - you don't check whether the exit condition for the orange_picker
> thread is true before waiting on the CV. This will halt your thread
> indefinitely when the age_increaser thread exits before the
> orange_picker thread starts the wait.
THIS was causing the deadlock. When I added just the check to my
program, it worked flawlessly. The missing check is the consequence of
(wrongly) thinking that @age is also protected by the sync block.

Thank you much for taking the time to troubleshoot the issue. I'd also
attempt a Monitor version of the same program later but for now I am
working on the Ruby Quiz challenges.

On Sun, Feb 24, 2013 at 4:51 PM, Abhijit Sarkar <lists@ruby-forum.com> 
wrote:

> Sean O'halpin wrote in post #1098770:

>> - the only shared state you need to protect access to is the
>> @orange_count variable - it's unnecessary to use synchronize around
>> the whole loop.
> True. I thought then that @age also needs protection but on closer
> review now, it doesn't.

Access to at least these variables needs proper synchronization:
Worker@next_run
OrangeTree@age
OrangeTree@orange_count

>> - you don't check whether the exit condition for the orange_picker
>> thread is true before waiting on the CV. This will halt your thread
>> indefinitely when the age_increaser thread exits before the
>> orange_picker thread starts the wait.

No.  If the age_increaser exits before the orange_picker starts to
wait it means that it will have set @next_run to :orange.
orange_picker won't block then.

> THIS was causing the deadlock.

No, the deadlock error was caused by the fact that one of the two
threads died silently because of Math.rand().  When you fix that by
deleting "Math." your code works.

> When I added just the check to my
> program, it worked flawlessly. The missing check is the consequence of
> (wrongly) thinking that @age is also protected by the sync block.

Can you please share the code which is working and the change you
believe made the difference?

Note, I was still using
http://www.ruby-forum.com/attachment/8132/orange_tree.rb as basis.

Kind regards

robert

On Sun, Feb 24, 2013 at 4:23 PM, Robert Klemme
<shortcutter@googlemail.com> wrote:
> Access to at least these variables needs proper synchronization:
> Worker@next_run
> OrangeTree@age
> OrangeTree@orange_count
>

Hi,

I think we must have been looking at different versions of the code -
there's no @next_run in the version I responded to
(http://www.ruby-forum.com/attachment/8128/orange_tree.rb). I guess I
should have made it clear which version I was trying to fix (there
appear to be quite a few). Note, I did mistakenly point to the OP's
first version in the description of the gist I wrote but that does not
use @next_run either. I take it you didn't look at
https://gist.github.com/seanohalpin/5023887.

Also, why would @age need synchronization?

>>> - you don't check whether the exit condition for the orange_picker
>>> thread is true before waiting on the CV. This will halt your thread
>>> indefinitely when the age_increaser thread exits before the
>>> orange_picker thread starts the wait.
>
> No.  If the age_increaser exits before the orange_picker starts to
> wait it means that it will have set @next_run to :orange.
> orange_picker won't block then.
>
>> THIS was causing the deadlock.

Like I said, there's no @next_run in the version I responded to.
You're right for the version of the code you're referring to. Putting
the check on age in worked for the version I was looking at.

Regards,
Sean

Robert Klemme wrote in post #1098804:
> Access to at least these variables needs proper synchronization:
> Worker@next_run
> OrangeTree@age
> OrangeTree@orange_count

It seems that you are looking at the Monitor version of the code. I was
trying everything under the sun to get the code working so there exist a
couple of versions. The version Sean fixed does NOT use a Monitor, it
uses a Mutex.
I've uploaded my Mutex and Monitor versions and Sean's Mutex version to
my GitHub
(https://github.com/abhijitsarkar/ruby/tree/master/...).
The names are self-descriptive (orange_tree_*)
The Monitor version still has the deadlock issue but I have pushed it
off for later.

> No.  If the age_increaser exits before the orange_picker starts to
> wait it means that it will have set @next_run to :orange.
> orange_picker won't block then.

Again, guess we are talking about 2 different versions.

> No, the deadlock error was caused by the fact that one of the two
> threads died silently because of Math.rand().  When you fix that by
> deleting "Math." your code works.
>
You are right that Math.rand was a culprit but it wasn't alone. In Mutex
version, the deadlock happens without the following check even with
Math.rand fixed.
if @orange_tree.age < OrangeTree::AGE_TO_DIE
  @cv.wait(@mutex)
end
> Can you please share the code which is working and the change you
> believe made the difference?

https://github.com/abhijitsarkar/ruby/tree/master/...

I apologize if there was any confusion about different versions of the
program. It is not so confusing in the forum posts but I guess may not
be in the mailing list.

On Sun, Feb 24, 2013 at 9:08 PM, Sean O'Halpin <sean.ohalpin@gmail.com> 
wrote:

> I think we must have been looking at different versions of the code -
> there's no @next_run in the version I responded to

Too bad.

> (http://www.ruby-forum.com/attachment/8128/orange_tree.rb). I guess I
> should have made it clear which version I was trying to fix (there
> appear to be quite a few). Note, I did mistakenly point to the OP's
> first version in the description of the gist I wrote but that does not
> use @next_run either. I take it you didn't look at
> https://gist.github.com/seanohalpin/5023887.
>
> Also, why would @age need synchronization?

In http://www.ruby-forum.com/attachment/8132/orange_tree.rb there is
read access to @age from one thread (#pick_an_orange) and read write
access from the other (#one_year_passes) => synchronization needed.

Cheers

robert

On Sun, Feb 24, 2013 at 10:37 PM, Robert Klemme
<shortcutter@googlemail.com> wrote:
> On Sun, Feb 24, 2013 at 9:08 PM, Sean O'Halpin <sean.ohalpin@gmail.com> wrote:
>>
>> Also, why would @age need synchronization?
>
> In http://www.ruby-forum.com/attachment/8132/orange_tree.rb there is
> read access to @age from one thread (#pick_an_orange) and read write
> access from the other (#one_year_passes) => synchronization needed.
>

Ah yes - thanks. I have a bad habit of thinking of integer read/writes
as atomic but a Fixnum isn't that simple (nor is anything anyway with
multiprocessors in the mix).

Regards,
Sean