Circular buffer - logic difficulty

**erasm** · 10-05-2009

I have written a get_buffer function that will not allow the buffer to be read if the buffer is empty. However, i am having difficulty doing the logic for the requirement of disallowing the buffer to be read when the buffer is at it's minimum fill level.

Code:

void init_buffer(bufferQueue *b, int min, int max)
{
        b = malloc(sizeof(bufferQueue));
        b->buffer_array = malloc(max*sizeof(int));
        b->in = 0;
        b->out = 0;
        b->min_buffer_size = min;
        b->max_buffer_size = max;
}

bufferQueue *destroy_buffer(bufferQueue *b)
{
        free(b);
        return b;
}

void put_buffer(bufferQueue *b, int v)
{
        if((b->in+1)%b->max_buffer_size == b->out)
        {
                //semWait(sem);
        }

        b->buffer_array[b->in] = v;
        b->in = (b->in+1)%b->max_buffer_size;
        }

int get_buffer(bufferQueue *b)
{
        if(b->in == b->out)
        {
                return;
                //semWait(sem);
        }
        return b->buffer_array[b->out];
        b->out = (b->out+1)%b->max_buffer_size;
}

**brewbuck** · 10-05-2009

Without some kind of special trick, it's impossible to tell the difference between a circular queue being completely full vs. completely empty. This is one of the classic difficulties of circular queues.

**yezaim** · 10-05-2009

I'm assuming you have a threaded-like environment, with fork or pthread_create...

Your problem is also known as "the busy barber", or "the sleepy barber", a classical subject of computer sciences.

You need to use two semaphores to handle the critical region, one to avoid consumers of reading empty buffers and another one to stop producers to insert anything when the buffer's full.

This is a piece of a code I used in a c++ class used for synching multithreads... I just do not control whether the buffer's full or not, I simply don't mind

(I just check the memory consumption, but buffer's level is always low in my program)

Code:

 
void Produce(Item *t) {
   down_mutex(); // enter critical region
      _buffer.put_buffer(t); // produce on your circular buffer
      is_empty=false;
      _count++;  //any check for is_full would be done here!
    up_mutex(); 
    up_empty (); // release customers waiting when buffer's empty
}

and the consumer:
Item * Consume () {
    Item * ret;
    down_empty(); // go sleep if ain't no messages, up_empty releases!!
    down_mutex();  // enter RC
      ret = get_buffer(); // consume
      if (--_count==0) is_empty=true;  // down_empty controls
    up_mutex(); 
    return ret;
  }

Now, just rewrite it using semaphores... follows the supressed functions.

Code:

 
 void down_mutex() { pthread_mutex_lock(&mutex); }
  void up_mutex() { pthread_mutex_unlock(&mutex); }

  void down_empty() { while(is_empty) pthread_cond_wait(&empty, &mutex); up_mutex(); }
  void up_empty() { pthread_cond_signal(&empty); }

  void down_full()  { while(is_full) pthread_cond_wait(&full, &mutex); up_mutex(); }
  void up_full()  { pthread_cond_signal(&full); }

Good luck!

yezaim

Thread: Circular buffer - logic difficulty

Thread Tools

Search Thread

Display

Circular buffer - logic difficulty

Similar Threads

Function call from another .c module

buffer contents swapping

Console Screen Buffer

Circular Logic