Sunday, February 7, 2016

Attempting Lock Free Stack using <atomic>

 (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;
}



No comments:

Post a Comment