(1) atomic has compare_exchange for lock free code
(2) to be joinable, thread ctor must take in a func. But could not get it to run push/pop directly. instead run in pusher/poper ctor.
#include "stdafx.h"
#include <atomic>
#include <thread>
#include<vector>
using namespace std;
struct Node {
Node *next;
};
enum {
NumNode = 20,
NumThread = 4
};
class Stack {
atomic<Node*> head;
public:
Stack() : head(0) {}
void push(Node *n) {
do {
n->next = head;
} while (!head.compare_exchange_strong(n->next, n));
}
Node *pop() {
Node *n;
do {
n = head;
if (!n)
return 0;
} while (!head.compare_exchange_strong(n, n->next));
return n;
}
};
class runnerPop : public thread
{
public:
Stack* stack;
runnerPop(Stack* s) : stack(s), thread([](){}) {
runPop();
}
void runPop()
{
auto n = stack->pop();
while (n)
{
delete n;
n = stack->pop();
}
}
};
class runnerPush : public thread
{
public:
Stack* stack;
runnerPush(Stack* s) : stack(s), thread() {
runPush(); // cannot get thread(runnerPush::runPush,this) to work, access violation. have to run after ctor
}
void runPush()
{
for (int i = 0; i < NumNode / NumThread; i++)
{
stack->push(new Node());
}
}
};
int main()
{
Stack stack;
{
vector<runnerPush> vPush;
for (int t = 0; t < NumThread; t++) {
vPush.push_back(runnerPush(&stack));
}
for (auto& v : vPush)
{
v.join(); // this will blow up since thread default ctor is used, not joinalbe
}
}
{
vector<runnerPop> vPop;
for (int t = 0; t < NumThread; t++) {
vPop.push_back(&stack);
}
for (auto& v : vPop)
{
v.join(); // this is joinable, thread ctor has empty lambda
}
}
return 0;
}
Sunday, February 7, 2016
Attempting Lock Free Stack using <atomic>
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment