Domanda

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.

È stato utile?

Soluzione

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.

Altri suggerimenti

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.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top