Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Implementing Bounded Buffer using condition variables  RSS feed

 
Skripi Mayer
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

2nd question. What are the properties of the Bounded Buffer ?
As far as I understood the text, a bouned buffer does:
- store int MAX number of Objects
- these objects can be added via insert and returned via remove()

I have not understood, if a BoundedBuffer hast _exactly_ one Producer
and one Consumer or if it need at least one of each, but could have hundreds.

A books implementation is the following:


For a single Producer, Consumer this is fine.

But it breaks / does not work properly for more Producers / Consumers. It
even breaks completely, when there are more Producers, that objects held by the buffer.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why does it break for multiple producers? Each producer should be on its own thread. When it tries to insert an item and the buffer is full, that thread will block on the wait. When somebody pulls something out, one of the producers will unblock and complete its insert call. Is that not what happens?

I see what the counter is supposed to do, but it makes me a bit suspicious. Otherwise it passes a 60 second inspection. I don't know if this is homework or just personal exploration, but you might peek at some other implementations. JDK5 has a BlockingQueue that is very similar and the Apache Commons thread pool has one, too.
 
Skripi Mayer
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Stan James:
Why does it break for multiple producers? Each producer should be on its own thread. When it tries to insert an item and the buffer is full, that thread will block on the wait. When somebody pulls something out, one of the producers will unblock and complete its insert call. Is that not what happens?

My problem is:
take 2 Producers(A,B) and 1 consumer (C):
1) the buffer is full and both producers (A,B) block
2) the consumer retrieves 3 itmes (waking one Producer (A) with the first)

under this condition it cannot be garanteed, that B is ever awakened,
even though the Buffer is no longer full.



I see what the counter is supposed to do, but it makes me a bit suspicious. Otherwise it passes a 60 second inspection. I don't know if this is homework or just personal exploration, but you might peek at some other implementations. JDK5 has a BlockingQueue that is very similar and the Apache Commons thread pool has one, too.

Count is necassary to see if the buffer is full or empty. One can determine the size of the buffer with hi and lo for [empty, MAX-1], but a full buffer
has hi == lo, so count is needed
a) to make comparisons easier
b) to determine buffer full or buffer empty.


One can optimize the bounded Buffer implementation, by recording the number of waiting Threads and signaling on each change:


This only holds if the number of consumers and producers is strictly smaller
than the max. Buffer size. Because only one type can block.

My goal is to write a Bounded Buffer, that can garantee to work.
So suppose:
- One bounded Buffer MAX = 2 - so it can only store one Element
- 3 Producer and 3 Consumer.
Problem:
- everytime at least 1 Producer and 1 Consumer is blocked. (?)
-> I cannot use ,
as a full Buffer could wake a Producer instead of a consumer

inside a synchronized method I can wait on a different object,
but no other Thread can enter another method, as the main object is blocked. I cannot give up to Java monitors with a single wait ! (?)

Where can I find help on this problem ?
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!