在许多为了性能和效率的场景下，需要开发一些lock-free的算法和数据结构

atomic_flag

原子布尔类型，只支持 test-and-set 和 clear 操作

构造函数

atomic_flag()noexcept=default;
atomic_flag(const atomic_flag&)=delete;

只有默认构造函数，而不能从其他对象构造
atomic_flag对象需要使用ATOMIC_FLAG_INIT初始化，使其处于 clear 状态，否则是unspecified未指定的

创建10个线程用于计数，先完成计数任务的线程输出id

#include<iostream>
#include<thread>
#include<atomic>
#include<vector>

std::atomic<bool> ready(false);
std::atomic_flag winner=ATOMIC_FLAG_INIT;

void count1m(int id){
  while(!ready){
    std::this_thread::yield();
  }
  for(int i=0; i<10000; ++i){
    // count
  }
  // 执行完后，该函数
  if(!winner.test_and_set()){
    std::cout<<"thread "<<id<<" first\n";
  }
};

int main(){
  std::vector<std::thread> ths;
  std::cout<<"spawning 10 threads that count to 1 million..."<<std::endl;

  for(int i=1; i<=10; ++i){
    ths.push_back(std::thread(count1m, i));
  }
  ready= true;

  for(auto& th:ths){
    th.join();
  }

  return 0;
}

std::atomic_flag::test_and_set

函数原型如下：

bool test_and_set(memory_order sync=memory_order_seq_cst)volatile noexcept;
bool test_and_set(memory_order sync=memory_order_seq_cst)noexcept;

用于检查标志，若std::atomic_flag之前被设置过，则返回true，否则返回false并设置标志
该操作为原子操作，可以指定的Memory Order如下

#include<iostream>
#include<atomic>
#include<thread>
#include<vector>
#include<sstream>

std::atomic_flag lock_stream=ATOMIC_FLAG_INIT;
std::stringstream stream;

void append_number(int x){
  while(lock_stream.test_and_set()){}
  stream<<"thread "<<x<<'\n';
  lock_stream.clear();
}

int main(){
  std::vector<std::thread> ths;
  for(int i=1; i<=10; ++i){
    ths.push_back(std::thread(append_number,i));
  }
  for(auto& th:ths){
    th.join();
  }
  std::cout<<stream.str()<<std::endl;
  return 0;
}

std::atomic_flag::clear

清除对象标志，即设置为false
函数原型如下：

void clear(memory_order sync=memory_order_seq_cst)volatile noexcept;
void clear(memory_order sync=memory_order_seq_cst)noexcept;

该函数也可以指定Memory Order的值

std::atomic_flag可以当作一个简单的自旋锁使用

#include<iostream>
#include<thread>
#include<vector>
#include<atomic>

std::atomic_flag lock= ATOMIC_FLAG_INIT;

void f(int n){
  for(int cnt=0; cnt<100; ++i){
    while(lock.test_and_set(std::memory_order_acquire))
    ; //spin
    std::cout<<"output from thread "<<n<<'\n';
    lock.clear(std::memory_order_release);
  }
}

int main() {
  std::vector<std::thread> ths;
  for(int n=0; n<10; ++n){
    ths.emplace_back(f,n);
  }
  for(auto& th:ths){
    th.join();
  }

  return 0;
}

对std::atomic_flag的加锁操作可以理解为lock.test_and_set(std::memory_order_acquire);
加锁操作时，返回false表示加锁成功
因为此前lock的标志为false，调用test_and_set()后标志为true，说明某一线程获得了锁
对std::atomic_flag的解锁操作相当于lock.test_and_set(std::memory_order_release);

atomic

原子类型atomic_flag过于简单，下面介绍功能更完善的std::atomic
原子类型对象的特点：不同线程访问不会导致数据竞争data race问题

构造函数

std::atomic是一个模板类

template<class T>
struct atomic;

template<>
struct atomic<integral>{};

template<class T>
struct atomic<T*>{};

标准库提供了对整型和指针类型的特化实现

默认构造函数
atomic()noexcept=default;
对象处于未初始化状态，需要使用atomic_init进行初始化

初始化构造函数
constexpr atomic(T val)noexcept;
可用T对象对atomic进行初始化

拷贝构造函数
atomic(const atomic&)=delete;
被禁用，不可拷贝

#include<iostream>
#include<atomic>
#include<thread>
#include<vector>

std::atomic<bool> ready(false);
std::atomic_flag winner= ATOMIC_FLAG_INIT;

void do_count1m(int id){
  while(!ready){
    std::this_thread::yield();
  }
  for(volatile int i=0; i<1000000; ++i){
  }
  if(!winner.test_and_set()){
    std::cout<<"thread "<<id<<" first\n";
  }
}

int main(){
  std::vector<std::thread> ths;
  std::cout<<"spawning 10 threads that count to 1 million...\n";
  for(int i=1; i<=10; ++i){
    ths.push_back(std::thread(count1m,i));
  }
  ready= true;
  for(auto& th:ths){
    th.join();
  }
  return 0;
}

成员函数

赋值操作
std::atomic::operator=()函数

copy (deleted)

atomic& operator=(const atomic&)=delete;
atomic& operator=(const atomic&)volatile=delete;

赋值运算是被禁用的

set value

T operator=(T val)noexcept;
T operator=(T val)volatile noexcept;

重载了赋值运算符，使得原子类型可以被类型为T的变量赋值，类似于隐式转换
该操作是原子操作，内存序默认为顺序一致性std::memory_order_seq_cst
若需要使用其他内存序，可以使用std::atomic::store()

#include<iostream>
#include<atomic>
#include<thread>

std::atomic<int> foo=0;

void set_foo(int x){
  foo=x;
}
void print_foo(){
  while(foo==0){
    std::this_thread::yield();
  }
  std::cout<<"foo:"<<foo<<std::endl;
}
int mian(){
  std::thread first(print_foo);
  std::thread second(set_foo, 10);
  first.join();
  second.join();
  return 0;
}

常用成员函数

bool is_lock_free()const volatile noexcept;
bool is_lock_free()const noexcept;

判断对象是否有lock-free特性
若对象具有该特性，则多线程访问该对象时不会导致线程阻塞

void store(T val, memory_order sync=memory_order_seq_cst)volatile noexcept;
void store(T val, memory_order sync=memory_order_seq_cst)noexcept;

修改被封装的值，将val复制给原子对象所封装的值，sync指定内存序

示例如下

#include<iostream>
#include<atomic>
#include<thread>
std::atomic<int> foo(0);
void set_foo(int x){
  foo.store(x, std::memory_order_relaxed);
}
void print_foo(){
  int x;
  do{
    x= foo.load(std::memory_order_relaxed);
  }while(x==0);
  std::cout<<"foo:"<<x<<std::endl;
}
int main(){
  std::thread first(print_foo);
  std::thread second(set_foo, 10);
  first.join();
  second.join();
  return 0;
}

T load(memory_order sync=memory_order_seq_cst)const volatile noexcept;
T load(memory_order sync=memory_order_seq_cst)const noexcept;

读取被封装的值，参数sync设置内存序

示例如下

#include<iostream>
#include<atomic>
#include<thread>
std::atomic<int> foo(0);
void set_foo(int x){
  foo.store(x, std::memory_order_relaxed);
}
void print_foo(){
  int x;
  do{
    x= foo.load(std::memory_order_relaxed);
  }while(x==0);
  std::cout<<"foo:"<<x<<'\n';
}
int main(){
  std::thread first(print_foo);
  std::thread second(set_foo, 10);
  first.join();
  second.join();
  return 0;
}

operator T()const volatile noexcept;
operator T()const noexcept;

与load功能类似，读取封装的值，默认内存序是std::memory_order_seq_cst

示例如下

T exchange(T val, memory_order sync=memory_order_seq_cst)volatile noexcept;
T exchange(T val, memory_order sync=memory_order_seq_cst)noexcept;

compare_exchange_weak

compare_exchange_strong

1

std::atomic对整型和指针类型特化

成员函数
fetch_add
fetch_sub
fetch_and
fetch_or
fetch_xor
operator++
operator--

2

C++11原子操作中C风格的API
std::atomic和std::atomic_flag