Dekker’s algorithm for N threads

In the previous post I described Dekker’s algorithm. Its limitation is that it only works for 2 threads. I wanted it to work for N threads, but I can’t atomically check N-1 flags belonging to other threads 🙁 now what?

Instead of multiple flags we’ll use one atomic variable’s bits to indicate which thread wants entry into the critical section. So, if first bit is set that means first thread declares its intent to enter. And so on for N threads.

Complete listing:

#include <iostream>
#include <atomic>
#include <thread>
#include <vector>
using namespace std;

const unsigned int COUNT = 5;
const unsigned int THREADS = thread::hardware_concurrency();
const unsigned int THREAD_MASK = 0b1;

int main(int argc, char** argv)
{
	atomic_uint flag{0};

	auto proc = [&](int t, unsigned int thread_mask) {
		for(int i = 0; i < COUNT;)
		{
			if(flag.fetch_or(thread_mask) == 0)
			{
				cout << "T" << t << " in critical section" << endl;
				++i;
			}

			flag.fetch_xor(thread_mask);
		}
	};

	vector<thread> vt;
	for(int i = 0; i < THREADS; ++i)
		vt.emplace_back(proc, i, THREAD_MASK << i);

	for(auto& t : vt)
		t.join();

	return 1;
}

#include <iostream>

#include <atomic>

#include <thread>

#include <vector>

using namespace std;

const unsigned int COUNT = 5;

const unsigned int THREADS = thread::hardware_concurrency();

const unsigned int THREAD_MASK = 0b1;

int main(int argc, char** argv)

{

atomic_uint flag{0};

auto proc = [&](int t, unsigned int thread_mask) {

for(int i = 0; i < COUNT;)

{

if(flag.fetch_or(thread_mask) == 0)

{

cout << "T" << t << " in critical section" << endl;

++i;

}

flag.fetch_xor(thread_mask);

}

};

vector<thread> vt;

for(int i = 0; i < THREADS; ++i)

vt.emplace_back(proc, i, THREAD_MASK << i);

for(auto& t : vt)

t.join();

return 1;

}

Practical Modern C++

Dekker’s algorithm for N threads

Like this:

Related

One Reply to “Dekker’s algorithm for N threads”

Leave a ReplyCancel reply

Practical Modern C++

Dekker’s algorithm for N threads

Share this:

Like this:

Related

One Reply to “Dekker’s algorithm for N threads”

Leave a ReplyCancel reply