Thread safe algorithm for arrays information manipulation I have a program which requires a usage of threads and it must be thread safe. I do not have much experience with threads and critical sections, but as much as I know you must lock code sections where resources are being read and written to. Program is working, but I do not know if I did it correctly.

DataB code was added to answer users Incomputable question. It is just a class which stores information required for program to work.

class DataB {
public:
    DataB() { }
    DataB(double sF, int sC, string n);
    double getField(void);
    void increaseFieldCount(void);
    void decreaseFieldCount(void);
    int getFieldCount(void);
    void setField(double f);
    void setCountField(int fC);
    string getName(void);
private:
    string name;
    double field;
    int fieldCount;
};

    DataB::DataB(double sF, int sC, string n) {
    field = sF;
    fieldCount = sC;
    name = n;
}

double DataB::getField(void) {
    return field;
}

void DataB::increaseFieldCount() {
    fieldCount++;
}

int DataB::getFieldCount(void) {
    return fieldCount;
}

void DataB::decreaseFieldCount(void) {
    fieldCount--;
}

void DataB::setCountField(int cF) {
    fieldCount = cF;
}

void DataB::setField(double f) {
    field = f;
}

string DataB::getName(void) {
    return name;
}

mutex threadLock;

void threadRemove(int dataStart, int dataEnd, int dataCount, DataB B[],  DataB V[], int &amp;sortedCount) {
    bool changed = true;

    while (changed || sortedCount != dataCount ) {
        changed = false;

        for (int i = dataStart; i &lt; dataEnd; i++) {

            threadLock.lock();

            int count = V[i].getFieldCount();

            threadLock.unlock();

            if (count &gt; 0) {

                threadLock.lock();

                double delItem = V[i].getField();

                threadLock.unlock();

                for (int x = 0; x &lt; dataCount; x++) {

                    threadLock.lock();

                    double compare = B[x].getField();

                    threadLock.unlock();

                    if (compare == delItem) {

                        threadLock.lock();

                        B[x].decreaseFieldCount();
                        V[i].decreaseFieldCount();

                        if (B[x].getFieldCount() == 0) {
                            B[x].setCountField(-1);
                            B[x].setField(-1);
                        }

                        changed = true;

                        threadLock.unlock();
                        break;
                    }
                }
            }
        }
    }
}

int main(int argc, char * argv[]) {

/* */

    thread G6(threadRemove, 0, 5, dataCount, B, V, ref(sortedCount));
    thread G7(threadRemove, 5, 10, dataCount, B, V, ref(sortedCount));
    thread G8(threadRemove, 10, 15, dataCount, B, V, ref(sortedCount));
    thread G9(threadRemove, 15, 20, dataCount, B, V, ref(sortedCount));
    thread G10(threadRemove, 20, 25, dataCount, B, V, ref(sortedCount));

    G6.join();
    G7.join();
    G8.join();
    G9.join();
    G10.join();
}
Contention

There is only one std::mutex, and every thread is permanently in contention for that same lock for every small partial operation. Thus, all the threads are permanently in contention over that lock, and at most one thread at a time is actually doing any work. A single threaded implementation should be faster - it has to do the same work, but doesn't have to fight over lock control.

So, how can this be fixed?

1) Separate independent data per thread

In the usage example, elements of V are split between threads so that no two threads are accessing the same elements. So, accesses to elements of V don't need a lock - if this convention is followed strictly.

If this is possible, locks aren't needed for those parts!

2) Finer granularity locks

Right now, taking the lock stops every thread from doing any work at all. Even with the improvement of option 1, only one thread at a time can access elements from B. This can be improved by introducing locks at a finer granularity:


simple: one lock per array element (so one for each DataB object)
more advanced: one lock for a subset of each array (e.g. one lock for every 10 array elements)


Doing so allows other threads to perform work on all unrelated elements.

3) Read/Write exclusivity

What's the difference between reading and writing B{0]? Reading can be done concurrently, writing can't. There is a lock that helps for this special case: std::shared_mutex allow multiple threads to read the related object(s), but only allows one thread to write to it (while no one else can access it). The catch? It's only available since C++17. Before that, there might be other libraries providing that functionality, though (e.g. boost), or you make do with a normal std::mutex.

Small problem

In the current version, every changes to an element of B is done in one transaction - no thread can see any partial state. If this property is required, this can be implemented with some special considerations. How do you change a BData object in one transaction?


Create a copy, change the copy, take the lock, overwrite the original with the copy, release lock (aka RCU = Read Copy Update, requires an external lock)
Lock the object, perform changes, unlock the object (this requires giving access to an internal lock)


Implementation


Headers are missing, At least &lt;string&gt;, &lt;mutex&gt; and &lt;thread&gt; need to be included.
using namespace std; is considered bad practice and should be avoided.
Some member functions of DataB and some variables could be marked const (e.g. DataB::getFieldCount(), DataB::getField(), compare, count, every function parameter). Doing so might help reasoning about code and enables the compiler to verify said reasoning and might enable it to generate better machine code.
Inconsistent naming: DataB::getFieldCount and DataB::setCountField.
DataB doesn't encapsulate any behavior, it just provides some getters and setters. Maybe make it a POD struct instead?
Prefer list initialization in the constructor(s).
The void in function_name(void) isn't needed in C++.


Fixed contention code


  For this, I made one internal mutex per DataB object and chose the second option for transactions. Also, I changed DataB to a POD struct to easily provide access to all internals (having getters and setters acquire locks on their own doesn't fit well with having a lock for a transaction).


#include &lt;string&gt;
#include &lt;thread&gt;
#include &lt;shared_mutex&gt;

struct DataB {
    mutable std::shared_mutex mut{}; // mutable so sonst DataB object can still be locked
    std::string name;
    double field;
    int fieldCount;

    DataB() { }
    DataB(const double sF, const int sC, const std::string&amp; n) : name{n}, field{sF}, fieldCount{sC} {}
};

void threadRemove(const int dataStart, const int dataEnd, const int dataCount, const DataB B[], const DataB V[], const int &amp;sortedCount) {
    bool changed = true;

    while (changed || sortedCount != dataCount) {
        changed = false;

        for (auto i = dataStart; i &lt; dataEnd; i++) {
            if (V[i].fieldCount &gt; 0) {
                for (auto x = 0; x &lt; dataCount; x++) {
                    double compare;
                    {
                        std::shared_lock&lt;std::shared_mutex&gt; read_lock{ B[x].mut }; // shared_lock = read only access
                        compare = B[x].field;
                    } // read_lock goes out of scope and gets released
                    if (compare == V[i].field) {
                        std::unique_lock&lt;std::shared_mutex&gt; write_lock{ B[x].mut }; // unique_lock = write access
                        --B[x].fieldCount;
                        --V[i].fieldCount;

                        if (B[x].fieldCount == 0) {
                            B[x].fieldCount = -1;
                            B[x].field = -1;
                        }

                        changed = true;
                    }
                }
            }
        }
    }
}


Note

This could maybe be enhanced by strategic use of atomics. However, that would require more knowledge about the members and usages of DataB than I could gather/guess from the code given.