C - How to make my data structure implementation synchronized?

Question

I have a data structure which I personally implemented that now needs to be used across multiple threads.

typedef struct 
{
    void** array_of_elements;
    size_t size;
} myStruct;

For simplicity, let's say my data structure has these functions:

// Gets a data element from the structure.
void* get(myStruct *x);
// Prints out all the data elements.
void print(myStruct *x);
// Adds an element into the structure.
void add(myStruct *x, void *to_be_added);

It's not a problem whatsoever to call get while another thread is calling print since they are both accessors. However, get and print cannot work while add is currently being called. Vice versa, add cannot work if get and print are currently in-progress.

So I changed myStruct to look like the following:

typedef struct 
{
    void** array_of_elements;
    size_t size;

    // True when a mutator is editing this struct.
    bool mutating;
    // The number of threads currently accessing this struct.
    int accessors;
} myStruct;

Now my functions look like the following:

void* get(myStruct *x)
{
    // Wait for mutating to end.
    while (x->mutating);
    // Indicate that another accessor is now using this struct.
    x->accessors++;

    // get algorithm goes here

    // Declare we are finished reading.
    x->accessors--;

    return ...
}

// Same as above...
void print(myStruct *x)
...

void add(myStruct *x)
{
    // Wait for any accessors or mutators to finish.
    while (x->mutating || x->accessors > 0);    
    x->mutating = true;

    // add algorithm here

    x->mutating = false;
}

BUT, I think there are a lot of problems with this approach and I can't find a way to solve them:

• One of my classmates told me using while loops like this slows the thread down immensely.
• It has no sense of a queue. The first method that begins waiting for the myStruct to finish being used isn't necessarily the one that goes next.
• Even IF I had a queue data structure for which thread goes next, that data structure would also need to be synchronized, which in itself is an infinite loop of needing a synchronized data structure to synchronize itself.
• I think it's possible that in the same nano second one thread changes the accessors counter from 0 to 1 (meaning they want to start reading), it's possible for a mutator thread to see it's value is 0 and start mutating. Then, both a mutator thread and an accessor thread would be going at the same time.
• I'm pretty sure this logic can cause grid-lock (threads waiting on each other infinitely).
• I don't know how to make certain threads sleep and wake up right when they need to for this task, besides having it stuck in a while loop.

Answer 1

You have the right idea, just the wrong approach. I'm not sure what OS you're programming on, but you want to look at the concepts of mutex or semaphore to do what you want to do.

On Linux/Unix that is POSIX compliant, you can look at pthreads:

http://www.cs.wm.edu/wmpthreads.html

On Windows, you can look at Critical Sections for something close to a mutex concept:

https://msdn.microsoft.com/en-us/library/windows/desktop/ms682530(v=vs.85).aspx

Or WaitForMultipleObjects for something close to a semaphore:

https://msdn.microsoft.com/en-us/library/windows/desktop/ms687025(v=vs.85).aspx

And, yes, using while loops are a bad idea. In this case, you are using what is known as a busy loop. More reading on it here:

What is a busy loop?

Using mutex or semaphore, no while loop is required. Good luck!