producer-consumer stack behavior instead of queue

Question

I have coded a solution to the standard producer-consumer problem using a buffer of size 5 and pthreads with an empty and full semaphore and mutex lock. I thought everything was working as expected but just noticed I am getting Stack behavior(LIFO) rather than the expected queue(FIFO) behavior. I have searched but couldn't find any similar issues since I am producing and consuming as expected other than the order.

This is a homework assignment so I am not really looking for code I am just wondering where to look for the error or know why the behavior may be different than expected.

struct data
{
pthread_mutex_t mutex;  
sem_t full;             
sem_t empty;
};

int bufferCount;        

buffer_item buffer[BUFFER_SIZE];
pthread_t thread;

int insert_item(buffer_item item)
{
  if (bufferCount < BUFFER_SIZE)
  {
    buffer[bufferCount] = item;
    ++bufferCount;
    return 0;
  }
  else
    return -1; //insert failed 
}

int remove_item(buffer_item *item)
{
  if (bufferCount > 0) 
  {
    *item = buffer[bufferCount - 1];
    --bufferCount;
    return 0;
  }
  else
    return -1; //error failed to remove

}

void Initialize (void *param)
{
  struct data *locks = param;

  pthread_mutex_init(&(locks->mutex), NULL);
  sem_init(&(locks->full), 0, 0);
  sem_init(&(locks->empty), 0, BUFFER_SIZE);
  bufferCount = 0;

}

void *producer (void *param)
{
  struct data *locks = param;
  do
  {
    sleep(rand()%5 + 1); //sleep for between 1 and 5 seconds
    buffer_item num = rand();
    sem_wait(&(locks->empty));
    pthread_mutex_lock(&(locks->mutex));
    if (insert_item(num))
    {
      printf("Insert in producer failed\n");
      exit(1);
    }
    else
      printf("Producer produced %d\n", num);
    pthread_mutex_unlock(&(locks->mutex));
    sem_post(&(locks->full));
  }while(1);
}


void *consumer (void *param)
{
  struct data *locks = param;
  do
  {
    sleep(rand()%5 + 1); //sleep for between 1 and 5 seconds
    buffer_item num;
    sem_wait(&(locks->full));
    pthread_mutex_lock(&(locks->mutex));
    if (remove_item(&num))
    {
      printf("Remove in consumer failed\n");
      exit(1);
    }
    else
      printf("Consumer consumed %d\n", num);
    pthread_mutex_unlock(&(locks->mutex));
    sem_post(&(locks->empty));
  }while(1);
}


int main(int argc, char *argv[])
{
  if (argc != 4)
  {
    printf("Incorrect number of arguments should be 4\n");
    exit (1);
  }
  int sleepTime = atoi(argv[1]);  
  int producerThreads = atoi(argv[2]);
  int consumerThreads = atoi(argv[3]);
  struct data *locks = (struct data *) malloc(sizeof(struct data));
  Initialize(locks);

  for (int i =0; i < producerThreads; ++i)
    pthread_create(&thread, NULL, producer, locks);

  for(int i = 0; i < consumerThreads; ++i)
    pthread_create(&thread, NULL, consumer, locks);

  sleep(sleepTime); 
  free (locks);
  return 0;
}

Answer 1

Your "error" lies here : *item = buffer[bufferCount - 1];

When you remove an item, you popped the furthest in the array , which is also the last inserted (thus LIFO behaviour). You need to pop the first one (and memcpy/index-keeping to shift the start of the buffer).

What you do :

begin         <-end  
-------------------
| | | | | | | | |x|
-------------------
                 |
                 -> *item

What you want to do :

begin->         end  
-------------------
|x| | | | | | | | |
-------------------
 |
 -> *item

PS : there are performance penalty to memcpy the buffer to realign the beginning of the data array, which is why circular buffers are often used.