CODEWITHSUNDEEP
cvariablespthreadsconditional-statements
Ozymandy
Ozymandy

Reputation: 59

posix threading in C condition variables

I've done my share of reading of condition variables, and I am simply stuck not being able to comprehend on how to use them.

I have a tree, who as of now, when you make an insertion for a node which already exists, it returns 0, which implies it already exists hence failure.

I now want to extend pthreads support, where rather than mentioning it can not be done since it already exists and returns 0, I want it to be on a waiting queue, and once the requested node is deleted, go ahead and now insert.

For example,

Suppose a tree has 3 nodes, with value 1, 5, 10 If I want to insert a new node with value 10, rather than returning 0 and throwing an error that the value already exists, it should wait for the node with the value 10 to delete, once it is deleted, it should go back ahead and insert.

My insert function else block, which returns 0 after it has previously inspected that the node exists with that value, you can be assured that the logic of knowing it exists works fine, now I am simply trying to add the conditional variable support where it waits. The datafield condition is initialized at the first line of the insert, so that's done as well. I am now hoping that when it enters this block, the cond_wait is the only line of code which will be executed, and then it will simply wait till the delete signals it. Is my approach here right? If it is, in the delete, how do I signal it? Please help me out here, I have spent hours reading and looking at examples trying to figure this out.

Code,

  else

      {
        //IF DUPLICATE EXISTS
        pthread_mutex_lock(&m);
        node->counter++;
        pthread_cond_wait(&node->condition, &m);
        _insert(string, strlen, ip4_address, node, NULL, NULL);
        pthread_mutex_unlock(&m);

        return 1;//I CHANGED IT FROM 0 to one, since if signalled, and if reached to this limit
        //it was probably successful

    }

Upvotes: 0

Views: 993

Answers (2)

Kaz
Kaz

Reputation: 58510

A condition variable wait must be wrapped in a loop. The loop's guard tests a condition over the shared data protected by a mutex. It makes no sense to use a condition variable as you have it.

If it makes sense to wait for the node with value 10 to be deleted before inserting it, then it is done with logic like this:

lock(mutex)
while (tree.contains(key))
  wait(cond, mutex)
tree.insert(key, value)
unlock(mutex)

The other task does this:

lock(mutex)
tree.delete(key)
unlock(mutex)
broadcast(cond) // could be in the mutex, but better outside!

When C. A. R. Hoare invented monitors and condition variables, the original concept was a little different. Concerns about efficiency on multiple processors wasn't a concern, and so the following logic was supported:

enter(monitor);
if (tree.contains(key))   // no loop
  wait(cond, monitor)
tree.insert(key, value)
leave(monitor);

There was a guarantee that when the other task signals the condition, the waiting task will be atomically transferred back to the monitor without any other task being able to seize the monitor. So for instance when a task is in the monitor and deletes node 10, and signals the condition variable, the first task waiting on that condition variable is guaranteed to immediately get the monitor. It is not that way with POSIX mutexes and conditions (for good reasons).

Another difference between mutexes and monitors is a thread does not have to hold the mutex to signal the condition variable. In fact, it is a good idea not to. Signaling a condition variable is potentially an expensive operation (trip to the kernel). Mutexes should guard critical regions which are as short as possible (just a few instructions, ideally) to minimize contention.

Yet another difference is that POSIX conditions have a pthread_cond_broadcast function which wakes up all threads waiting on a condition. This is always the correct function to use by default. In situations in which it it obvious (or can be shown that) waking up a single thread is correct, then the function pthread_cond_signal can be used to optimize the code.

Upvotes: 1

Valeri Atamaniouk
Valeri Atamaniouk

Reputation: 5163

Here are assumptions:

struct tree
{
   ... // some other data (whatever)
   pthread_mutex_t mitex;
   pthread_cond_t  cond;
};

Helper function:

int tree_contains_value(struct tree *t, int value)
{
    return ...; // returns 0 or 1
}

And here is an insertion:

void tree_insert(struct tree *t, int val)
{
    pthread_mutex_lock(&t->mutex);
    while (tree_contains_value(t, value))
    {
        pthread_cond_wait(&t->cond, &t->mutex);
    }
    ... // do actual insert
    pthread_mutex_unlock(&t->mutex);
}

And removal:

void tree_remove(struct tree *t, int val)
{
    pthread_mutex_lock(&t->mutex);
    ... //remove value
    pthread_cond_broadcast(&t->cond); // notify all wating threads if any
    pthread_mutex_unlock(&t->mutex);
}

Upvotes: 1

Related Questions