PUSH and POP buffer

First, I implemented the normal PUSH/POP functions with out considering any concurrency.

int buffer[5];
int head, tail;

int push(int value) {
    if( head + 1 == tail ) { //full
        return -1;
    }
    buffer[head] = value;
    head++;
    if( head >= 5 ) {
        head = 0;
    }

    return 0;
}

int pop(int &value) {
    if( head == tail ) { //empty
        return -1;
    }
    value = buffer[tail];
    tail++;
    if( tail >= 5 ) {
        tail = 0;
    }

    return 0;
}

It is safe to use the above PUSH/POP function when their is only one Producer/Consumer pair running concurrently.

This is because the push function only move the head forward

and the pop function only move the tail forward.

There is no conflict if only one Producer/Consumer pair exist.

However, if more than one Producer or Consumer exist,

multiple Producer or Consumer will move the head or tail forward concurrently,

it will eventually causes error.

For the one Producer/Consumer pair problem, checkout Shene’s literature.

In this problem, we have one producer and two consumers.

We have to let only one consumers use the pop function at any given time.

Consumer Mutex

I developed Mutex for the two consumers. I create one flag for each consumer.

The action rule for consumer is:

1. Turn on the Flag
2. If the Flag of the other consumer is on for a given time, then I do nothing an turn off my flag and redo step 1 after a second.
3. If the Flag of the other consumer is off, then I go ahead and use pop function.
4. Turn off the Flag after the pop.

The step 2 can prevent two consumers turn on their flag at the same time and cause a deadlock.

Their’s no priority between the two consumers.

The Lock/Free functions are defined as follows:

int mutex[2]; // maximum of 2 concurrent consumer

int lock(int id, int timeout) { //return -1 while timeout
    int time = 0;
    if( id == 1 ) {
        mutex[0] = 1;
        while(mutex[1]) {
            time++;
            if( time >= timeout ) {
                mutex[0] = 0;
                return -1;
            }
        }
    } else if ( id == 2 ) {
        mutex[1] = 1;
        while(mutex[0]) {
            time++;
            if( time >= timeout ) {
                mutex[1] = 0;
                return -1;;
            }
        }
    }

    return 0;
}

int free(int id) {
    if( mutex[ id - 1 ] == 0 ) {
        return -1;
    }
    mutex[ id - 1 ] = 0;
    return 0;
}

Observation

1. The bounded-buffer is safe to use when only one producer and one consumer running concurrently.
2. We need to define N flag if N consumers is running concurrently. This is also true for multiple producer running concurrently.

The simulation is done by using BACI, get the source here.