Lock

[seeplus]

I have an issue which for simplicity comes down to this:

void process(int n) {
    // Do processing of n if not already processing same value of n
    // Otherwise wait until processing of same value of n has completed before processing
}

process() can be called simultaneously from multiple threads and needs to proceed straight away if not already processing the same value of n in a different thread. If process() is already processing the same value of n in another thread then process() needs to wait until the other thread has finished processing that value. There may be more than one thread trying to process the same value of n at the same time.

The code in process() can't be locked with eg a mutex as if the value of n is not already being processed then no locking takes place. Only if the value of n is already being processed is a lock needed until processing has completed.

What I'd like is something like this:

void process(int n) {
    lock (n);
    // Perform process
}

But how can lock() be implemented? Does anyone have any ideas?

[salem c]

How many n ?

> Otherwise wait until processing of same value of n
But your prose indicates otherwise.

[kigar64551]

One mutex for each possible n value, provided that the range of n isn't huge?

mutex_t mutex[N];

void process(int n) {
    mutex_lock(&mutex[n]);
    // Perform process
    mutex_unlock(&mutex[n]);
}

If this is not feasible, e.g. because the range of n is too big, maybe use a condition variable?
https://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf

cond_var_t cond_var;
mutex_t mutex;
std::set<int> set;

void process(int n) {
    mutex_lock(&mutex);
    while (set.contains(n)) {
        cond_var_wait(&cond_var, &mutex); //wait for the flag to become clear
    }
    set.insert(n); // set the flag for ourselves
    mutex_unlock(&mutex);


    // Perform process
    // ...


    mutex_lock(&mutex);
    set.remove(n); // finally, clear the flag
    mutex_unlock(&mutex);
    cond_var_broadcast(&cond_var); // ...and wake any waiters
}

Note that, in the non-congested case, we temporarily lock the mutex, in order to atomically update the "shared" set.

...but it won't be locked for the whole time, so parallel processing (of different n values) remains possible.

Also note that cond_var_wait() unlocks the given mutex while sleeping, and it automatically re-locks that mutex on wake-up.

[seeplus]

n can be any value in the range of int - so a mutex for every possible value of n isn't feasible/practical.

Using a condition variable may be the way forward. I'll do some investigation. I haven't much used this as mainly we use Windows threading.

Thanks.

[kigar64551]

n can be any value in the range of int - so a mutex for every possible value of n isn't feasible/practical.

Maybe use M mutexes (with M being reasonably small), and map each n value into the 0 to M-1 range.

mutex_t mutex[M];

void process(int n) {
    const size_t slot = hash(n) % M;
    mutex_lock(&mutex[slot]);
    // Perform process
    mutex_unlock(&mutex[slot]);
}

The chance that two different n values block each other's executions is not zero, of course, but should be pretty small.

Using a condition variable may be the way forward. I'll do some investigation. I haven't much used this as mainly we use Windows threading.

There are many implementations of condition variables:

Pthreads, which is cross-platform:
https://pubs.opengroup.org/onlinepubs/007904975/functions/pthread_cond_init.html
https://pubs.opengroup.org/onlinepubs/007904975/functions/pthread_cond_wait.html
https://pubs.opengroup.org/onlinepubs/007904975/functions/pthread_cond_broadcast.html

Native Win32, available in Vista and newer:
https://learn.microsoft.com/en-us/windows/win32/sync/condition-variables

std::condition_variable, since C++11:
https://en.cppreference.com/w/cpp/thread/condition_variable


Win32 also has Events, but those do not support atomic "release mutex and wait for event" operation, which leads to race conditions:
https://learn.microsoft.com/en-us/windows/win32/sync/event-objects

[seeplus]

Win32 also has Events, but those do not support atomic "release mutex and wait for event" operation, which leads to race conditions:

Yeah....

Thanks for the link to Win32 condition variables. I'd forgotten that these were now available since Vista. I now need to mug up this stuff on condition variables as these are almost certainly the way forward.

Cheers!

[kigar64551]

If you want to stay cross-platform and still support Win32, have a look at:
https://sourceware.org/pthreads-win32/
https://sourceforge.net/projects/pthreads4w/files/