1

Working with the classic multiple Consumer/Producer problem, and I have an issue that is driving me around the bend, regarding how to avoid race conditions when inserting/removing from a circular buffer. Appreciate any help in advance!

Sample code for circular buffer for example purposes. Similar to my implementation (Note: I cannot use collection types, only arrays for this):

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class BoundedBuffer {
    private final String[] buffer;
    private final int capacity;

    private int front;
    private int rear;
    private int count;

    private final Lock lock = new ReentrantLock();

    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    public BoundedBuffer(int capacity) {
        super();

        this.capacity = capacity;

        buffer = new String[capacity];
    }

    public void deposit(String data) throws InterruptedException {
        lock.lock();

        try {
            while (count == capacity) {
                notFull.await();
            }

            buffer[rear] = data;
            rear = (rear + 1) % capacity;
            count++;

            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }

    public String fetch() throws InterruptedException {
        lock.lock();

        try {
            while (count == 0) {
                notEmpty.await();
            }

            String result = buffer[front];
            front = (front + 1) % capacity;
            count--;

            notFull.signal();

            return result;
        } finally {
            lock.unlock();
        }
    }
}

What I need to know is how can I implement a method for checking if the buffer is full/Empty? This method needs to be included in this BoundedBuffer and must be called from another class (Producer/Consumer) before giving the go ahead for/Calling Inserting/Writing methods.

Pseudocode for method in Producer class.

    if (!bufferFull) {
        buffer.addelement;
    }

    else {
        thread.sleep(5)
        threadHasSleptFor++;
    }

I am using threads, and there are multiple producers/consumers (In this case 2 producers/consumers, but I may require more). I need it so that if the buffer is full, the thread has to wait until it becomes available for insertion, and the time it waits needs to be stored for output purposes (Not debug, part of the core features). The issue I am having is this:

  1. Thread 1 Producer checks is bufferfull condition, it's false.
  2. Scheduler switches to Thread 2 midway.
  3. Thread 2 also checks bufferfull condition, it's false.
  4. thread 2 proceeds to insert.
  5. Scheduler switches back to Thread 1.
  6. Thread 1 now goes to insert line, as it already checked, but Thread 2 beat it.
  7. Booom.

Somewhat new to Java, though as I understand this is the "time-of-check/time-of-use" race condition issue.

Can someone please advise as to how this can be implemented safely, and how would I loop the code so the threadHasSleptFor variable keeps incrementing on every fail (Providing the methods would be great). I want it so that only the Thread that has requested the check can begin to insert item; the second producer must wait for the lock.

Thanks.

2 Answers 2

0

This is by definition impossible to do without higher level locking.

You have to guarantee that the check of whether the buffer is full or not and the following insert are atomic from the thread's perspective which means you have to acquire some common lock to do so. This general problem is indeed called Time of check to time to use and leads to many interesting race conditions down the line.

The solution to these problems is to not check if you can do an operation and then do it, but to just try the operation and handle the error case. So if you don't want to block if the buffer is full with your operation, just implement a tryDeposit method that throws an exception if it can't store a value, or return a boolean success value.

Although in your case if you have to store the time necessary before you could push the value onto the stack, I don't see why a simple:

long start = System.nanotime();
queue.deposit();
long end = System.nanotime();

wouldn't do the trick as well.

3
  • System.nanotime (...) is not guaranteed to be monotonic. end could be before start in some JDK implementations under rare circumstances if you do not guard against that. Feb 3, 2014 at 2:20
  • Thanks for this. I had the idea of implementing an error case but was unsure as to how to go about it. Regarding the second part, I needed the thread to go output some stuff and wait (Storing the waited 'time' as an arbitrary increment var in a loop) if it was unable to execute the function immediately, so I'll try the trydeposit method first.
    – Error-404
    Feb 3, 2014 at 2:34
  • @Andon nanotime() not being monotonic on some implementations may be the case, but should be considered a bug. Very likely on older JDKs that couldn't use TIME_MONOTONIC_RAW I guess, but in that case there aren't necessary (m)any good solutions available anyhow.
    – Voo
    Feb 3, 2014 at 12:54
0

If I understand you correctly, you are asking how to make a thread wait until it's OK to call deposit() or wait until it's OK to call fetch(). But, there's no need for that. Your deposit() method will block the calling thread until there is room in the queue, and your fetch() method will block the caller until there is something to fetch. That's what the notFull.await() and notEmpty.await() calls do.

await() unlocks the lock, sleeps until the condition is signalled by another thread, and then it re-locks the lock. The condition may or may not still be true when the caller finally gets the lock again, but that's why you have the await() calls in loops, so that the thread keeps trying until finally it has the lock and the condition is true. Then it does its work (add an item or remove an item), unlocks the lock, and returns.

1
  • Thanks. Yes the code was implemented to prevent the buffer from becoming corrupted however I found I had no reliable way for the external call method to determine if the buffer was full at the time and had waited, or not. This was to be looped storing the amount of 'time' taken before successfully inserting. Going to try the tryDeposit method though the brief stated a method for checking if empty should be implemented, though this way seems safer.
    – Error-404
    Feb 3, 2014 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.