Skip to content

Instantly share code, notes, and snippets.

@arkadijs
Created December 16, 2016 12:06
Show Gist options
  • Save arkadijs/13ec2983f333bf9941b022d94d6d8017 to your computer and use it in GitHub Desktop.
Save arkadijs/13ec2983f333bf9941b022d94d6d8017 to your computer and use it in GitHub Desktop.
Dekker's algorithm
#include <iostream>
#include <pthread.h>
volatile bool flag0;
volatile bool flag1;
volatile int turn;
long count;
long count0;
long count1;
const long limit = 10*1000*1000;
void* f0(void *arg) {
while (true) {
// acquire
flag0 = true;
__sync_synchronize(); // mfence
while (flag1) {
if (turn != 0) {
flag0 = false;
while (turn != 0) {
}
flag0 = true;
}
__sync_synchronize(); // mfence
}
// critical section
++count0;
++count;
// yield
turn = 1;
flag0 = false;
__sync_synchronize(); // mfence
// exit
if (count0 == limit)
return 0;
}
}
void* f1(void *arg) {
while (true) {
// acquire
flag1 = true;
__sync_synchronize(); // mfence
while (flag0) {
if (turn != 1) {
flag1 = false;
while (turn != 1) {
}
flag1 = true;
}
__sync_synchronize(); // mfence
}
// critical section
++count1;
++count;
// yield
turn = 0;
flag1 = false;
__sync_synchronize(); // mfence
// exit
if (count1 == limit)
return 0;
}
}
int main(int argc, char** argv) {
pthread_t t0, t1;
pthread_create(&t0, 0, f0, 0);
pthread_create(&t1, 0, f1, 0);
pthread_join(t0, 0);
pthread_join(t1, 0);
std::cout << count << std::endl;
return 0;
}
package dekker;
public class Main {
private static volatile boolean flag0 = false;
private static volatile boolean flag1 = false;
private static volatile int turn = 0;
private static long count = 0;
private static long count0 = 0;
private static long count1 = 0;
private static final long limit = 2*1000*1000;
public static void main(String[] args) throws InterruptedException {
Thread t0 = new Thread(new Runnable () {
public void run() {
while (true) {
// acquire
flag0 = true;
while (flag1) {
if (turn != 0) {
flag0 = false;
while (turn != 0) {
}
flag0 = true;
}
}
// critical section
++count0;
++count;
// yield
turn = 1;
flag0 = false;
// exit
if (count0 == limit)
return;
}
}
});
Thread t1 = new Thread(new Runnable () {
public void run() {
while (true) {
// acquire
flag1 = true;
while (flag0) {
if (turn != 1) {
flag1 = false;
while (turn != 1) {
}
flag1 = true;
}
}
// critical section
++count1;
++count;
// yield
turn = 0;
flag1 = false;
// exit
if (count1 == limit)
return;
}
}
});
t0.start();
t1.start();
t0.join();
t1.join();
System.out.println(count);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment