• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Himai Minh

Implement queue to perform read and write operation separately.

 
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I was going through multi threading problem and come across this problem at careercup. It was asked somewhere. I thought to implement for self learning.
Please comment your idea:

Problem:

Implement a queue which performs following operation:

Read:
If queue is empty, wait till it can return a value with time out. If another thread is reading from the queue then wait till that thread is done.
Remove the first element from the queue and return it Do not block if a thread is writing into the queue

Write:
If queue is full, wait till one value is read with time out. If another thread is writing to the queue, wait till that thread is done.
Write the element at the end of the queue. Do not block if a thread is reading from the queue
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My first solution:








 
Marshal
Posts: 76393
364
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sounds like something out of the producer‑consumer problem. Search for that and you should find some standard solutions. Also look for concurrent implementations of the Queue interface.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yeah Campbell it is like producer and consumer problem but i can't use any standard concurrent api's like BlockingQueue or something else.
I have to implement one.
 
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You can't use the concurrency API at all?

java.util.concurrent.locks.Condition is perfect for this problem. You need a queueIsNotEmpty condition and a queueIsNotFull condition that share a common queueLock, and you need a readLock and a writeLock to prevent threads from reading/writing simultaneously.

It's easiest to implement this by creating a circular buffer with a start and an end pointer. You can use AtomicIntegers for the pointers.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Stephan, thanks for the suggestion but as per problem statement, only 1 read can happen at one time but it doesn't block write thread to write
and same as for write thread, only 1 write can work but doesn't block read. So, if i use read/write lock then i can't use both at same time and also
multiple read happened at same time.

If another thread is reading from the queue then wait till that thread is done. Do not block if a thread is writing into the queue



If another thread is writing to the queue, wait till that thread is done. Do not block if a thread is reading from the queue

 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, so you can use a Semaphore for the readers and a Semaphore for the writers. You still need a shared lock with two conditions to signal that the buffer isn't full or empty. This lock can be realized using either the synchronized keyword, or with the ReentrantLock class.

Note that it's impossible to keep the readers and writers completely out of each other's way, because you need a way to synchronize on the remaining space in the buffer.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How about to check whether queue is empty or full after acquired lock.

For an example: I have 3 read thread and 3 write thread, Say if 1 read thread acquire lock and found queue is empty so it goes to while loop
and if same time other read threads come then they have to wait as lock is already been acquired by other read thread.

Same is for write thread. First thread acquire lock and check if queue is full or not. If full then wait for queue to make a space. If in meantime
other write threads come then they will wait for acquire lock.

In this way i think we don't have to use separate mechanism to check whether queue is empty or not or co-ordinate between reader and writer thread.

I may be completely wrong but it is my thought/
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tushar Goel wrote:For an example: I have 3 read thread and 3 write thread, Say if 1 read thread acquire lock and found queue is empty so it goes to while loop
and if same time other read threads come then they have to wait as lock is already been acquired by other read thread.

Same is for write thread. First thread acquire lock and check if queue is full or not. If full then wait for queue to make a space. If in meantime
other write threads come then they will wait for acquire lock.



No, you can't do this, because as soon as the thread waits, it automatically releases the lock. Unless it's a busy wait, which is a horrible solution.

You need a lock for the readers that's only released when one reader is done. Semaphore is perfect for this. The same goes for the writers.

Then you need a third lock to synchronize the buffer pointers on. This is a shared lock between *all* the threads, which has 2 conditions that can be awaited.

I made a solution to the problem which seems to work, here's the outline:
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Unless it's a busy wait, which is a horrible solution


Got your point. I was doing the same. I put a infinite loop while waiting.

Then you need a third lock to synchronize the buffer pointers on. This is a shared lock between *all* the threads, which has 2 conditions that can be awaited.


I am not sure about how to use conditions but i will read docs. I have heard about them but not used it. Thanks again..

Lemme try this..
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just a quick note about locks: A lock is used to guard a critical section. This is how you should use them in combination with conditions:

 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Stephan, as per your suggestion i have made correction but result is not accurate and also looks very complicated. Any suggestion...






 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here i am starting a thread each time an object is inserted or removed. I think it is not correct..
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It looks complicated because it *is* complicated. I'm not sure there's much you can do about this, apart from moving parts of your methods to their own methods.

Anyway, you're making three big mistakes. First of all, readers may not read at the same time. Checking whether the queue has an item is part of the read operation, so this should be part of the critical section. No two readers may check the queue at the same time, because if one element is available, two readers may pass the check before one of them reads and discards the element. The same is true for the writers and writing.

The second mistake is that you're not releasing lock correctly. If an exception occurs in the first while loop, then lock is never released, and the program deadlocks. Locks should *always* be used like this:

Finally, since the lock spans the entire run() method, readers and writers can't access the queue at the same time. You should only lock the shared lock when you're performing checks. After that, release the lock and start the read/write operation. All of this needs to be inside the reader/writer lock.

First show me how you would implement these two methods:
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tushar Goel wrote:Here i am starting a thread each time an object is inserted or removed. I think it is not correct..



This is also true, but not the reason why your program isn't working. Regardless, don't spawn new threads in your get and put methods.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am sorry i have some questions but something are bothering me.. I am sorry if i asking stupid questions as i am not good in concurrency.

Checking whether the queue has an item is part of the read operation, so this should be part of the critical section. No two readers may check the queue at the same time,


As per requirement, no 2 readers threads can read at same time and so does writer threads.

because if one element is available, two readers may pass the check before one of them reads and discards the element.


How can 2 threads enters at same time. I am already using lock.



The second mistake is that you're not releasing lock correctly. If an exception occurs in the first while loop, then lock is never released, and the program deadlocks. Locks should *always* be used like this:



Sorry, i forgot...


Finally, since the lock spans the entire run() method, readers and writers can't access the queue at the same time. You should only lock the shared lock when you're performing checks.



You are right.. sorry...
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here 2 method implementation:

 
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I do not think your code is thread safe. As far as I can see there is no happens-before relationship between the write in WriterQueue and the reads in ReaderQueue.

Since LinkedList is not threadsafe internally this means that there is no guarantee when (or even if) the reads in ReaderQueue will see the writes in WriterQueue. Even worse, they may get back object references that have not completed initialisation.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Mike, can you please explain more? I used semaphore in reader/writer and lock to check wheter queue is empty or not.
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Mike, the happens-before relationship is established by lock.lock(). Readers and writers share the same lock. The problem in this case is that the lock spans the entire method call, so both the readers and writers have mutually exclusive access, which is not what the assignment requires.

Tushar, your waitUntilElementIsAvailable() method calls announceThatSpaceIsAvailable(). Firstly, waitUntilElementIsAvailable() has absolutely no reason to assume that space is available. All it knows when it breaks through the while loop is that start.intValue() != 0. That doesn't imply anything about whether space is available. Secondly, announcements should only be made when a change is made. waitUntilElementIsAvailable() does not make any changes, so it has nothing to announce.

You are catching and rethrowing InterruptedException. This is useless, just leave out the catch clause.

You aren't breaking out of the while loop when the timeout occurs. Right now, even if you specify a timeout it won't have any effect on how long the method blocks.

I'm assuming that if start.intValue() != 0 implies that an element is available, that you're writing to and reading from the end of the buffer. This is not a queue implementation but a stack implementation. You need to write to the end of the buffer, and read from the beginning of the buffer.

announceThatSpaceIsAvailable() may throw an IllegalMonitorStateException. You need to acquire the lock before you may signal the condition.

Maybe the best course of action is that you first implement a CircularBuffer class, that doesn't care about multi-threading at all. This will make your condition checking a lot easier.

[edit]

I renamed end to size, the logic becomes easier that way.
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Implement it so that

gives the following output:

A
B
[D, null, C]

 
Mike. J. Thompson
Bartender
Posts: 689
17
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Mike, the happens-before relationship is established by lock.lock(). Readers and writers share the same lock. The problem in this case is that the lock spans the entire method call, so both the readers and writers have mutually exclusive access, which is not what the assignment requires.



You are right, I misread the code and didn't spot that the locks were shared. I mistakenly assumed they were not since, as you say, any shared lock between the reader and the writer while reading and writing violates the condition that reads do not block on writes.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Stephan, you have pointed out very good point. I'l try to remember this.. i have also implemented the said api:

 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Great job! Now let's refactor it to make it thread-safe. Don't worry about about the precise requirements of the application just yet, we're only interested in making it thread safe regardless of how many readers and writers can access it at the same time.

Identify critical sections by determining what pieces of code share mutable variables, and use the synchronized keyword to provide mutually exclusive access to those critical sections.

You may also want to add a @SuppressWarnings("unchecked") to the generic type cast. Sadly there's no way to do this in a neater way, but we can guarantee that the array contains only objects of type E, so it's alright.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I think all the methods except capacity() method should be synchronized. For get and put methods i used synchronized block. I am assuming size, isEmpty and full method can be called
other than get and put methods as well. So they should be synchronized as well.

 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
But after using synchronized keyword, reader and writer can't be work together as lock is acquired on common object

Actually i think it is wrong because in get/put i acquired lock on buffer and rest of the methods i acquired lock on class object. So both are different.
Instead we need to put same type of lock on all of them.

 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Stephan, just wondering if you get some time to continue on this thread.
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ah! I'm sorry I missed this. I will follow up later today.
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Alright, your last piece of code is correct. Now, what we want to make sure that add() and remove() calls can work simultaneously, but with the restriction that add() can only be run by one thread at a time, and the same restriction for remove().

That means that we can't synchronize the entire method, we need to lock the method just for threads that add and and remove, respectively, and then synchronize the individual critical sections. Add two Semaphores addPermit and removePermit to the class, to prevent two threads from adding at the same time, and to prevent two threads from removing at the same time. Don't worry about synchronizing the critical sections within the methods just yet.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Stephan for giving time.. Here is the update code:

 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This won't work. What happens if there is one space left in the buffer and two add operations happen at the same time? They both pass the check, and then one attains the permit. It fills the empty space, releases the permit, and then the second add operation overwrites an occupied space.

When you acquire or release 1 permit, you can omit the argument. Just use addPermit.acquire() and addPermit.release().

@SuppressWarnings should be applied as tightly as possible. Don't annotate the method, annotate the assignment.

Amend your code and we'll go to the next part.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

This won't work. What happens if there is one space left in the buffer and two add operations happen at the same time? They both pass the check, and then one attains the permit. It fills the empty space, releases the permit, and then the second add operation overwrites an occupied space.



You are right, it will overwrite an index 0 which is occupied. Also same is true when we try to remove last element present in the queue as well.

So may be we need to put a check in both after acquiring lock..

For adding an element check would be to compare whether size of the queue is equals to the capacity or not. Add only if its not.




For the remove we have to compare against 0 size. One more doubt when i am trying to add suppress warning annotation at line 9 in code as below it gives my compilation problem.

 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Why are you adding checks? You already have one at the beginning of the method. Just move it inside the critical section:
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Tushar Goel wrote:One more doubt when i am trying to add suppress warning annotation at line 9 in code as below it gives my compilation problem.


Show the actual code and the error message.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This gives error at line 10. It gives error "item can't be resolved to a type"


 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, SuppressWarnings must target a declaration. You should do it like this:

You can do this if you amend the code to perform the isEmpty() check only once at the beginning, because then you don't need the second if scope.

Update your code and post it and we will move on.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks Stephan, here is updated code:



 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Okay, next problem. What happens when two threads want to add an item at the exact same time, but the buffer is already full?

Describe what happens in both threads, assuming thread 1 acquires the permit, and thread 2 is blocked.
 
Tushar Goel
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
In current implementation, if after adding an element in first thread, queue is full then once second thread acquired the lock it throws exception..

In this once first thread acquired the lock, it put the element into the queue and increase the number of elements in an queue by 1 and release the lock.
Once it released the lock, 2nd thread which was waiting for lock got the lock. Then it check size is full or not. It finds it is full now and throws the exception..
(Oh.. i see need to release the lock in final block)
 
Stephan van Hulst
Saloon Keeper
Posts: 14260
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
No, I was wondering what happened if the buffer is already full before any of the two threads did anything.

Thread 1 would acquire the permit, then throw an exception because the buffer is full.
Thread 2 would stay blocked forever, because the permit is never released.

Yes, you need to release the permit using a try statement.
 
I wasn't selected to go to mars. This tiny ad got in ahead of me:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic