分别⽤原⼦操作,semaphore,condition variable三种⽅式实现题库中的题目。

1114. 按序打印

atomic operation

#include <atomic>
class Foo {
private:
atomic_bool a = false, b = false;
public:
Foo() {}

void first(function<void()> printFirst) {
// printFirst() outputs "first". Do not change or remove this line.
printFirst();
a = true;
}

void second(function<void()> printSecond) {
while(!a) this_thread::sleep_for(chrono::milliseconds(1));
// printSecond() outputs "second". Do not change or remove this line.
printSecond();
b = true;
}

void third(function<void()> printThird) {
while(!b) this_thread::sleep_for(chrono::milliseconds(1));
// printThird() outputs "third". Do not change or remove this line.
printThird();
}
};

初识原子操作。

semaphore

#include <semaphore.h>
class Foo {
private:
sem_t sem_1, sem_2;
public:
Foo() {
sem_init(&sem_1, 0, 0);
sem_init(&sem_2, 0, 0);
}

void first(function<void()> printFirst) {
// printFirst() outputs "first". Do not change or remove this line.
printFirst();
sem_post(&sem_1);
}

void second(function<void()> printSecond) {
sem_wait(&sem_1);
// printSecond() outputs "second". Do not change or remove this line.
printSecond();
sem_post(&sem_2);
}

void third(function<void()> printThird) {
sem_wait(&sem_2);
// printThird() outputs "third". Do not change or remove this line.
printThird();
}
};

condition variable

条件变量(Condition Variable)的一般用法是:线程 A 等待某个条件并挂起,直到线程 B 设置了这个条件,并通知条件变量,然后线程 A 被唤醒。这里等待的线程可以是多个,通知线程可以选择一次通知一个(notify_one)或一次通知所有(notify_all)。

加锁主要有两方面的作用:

  1. 保护pred资源,避免多线程同时读写该资源
  2. 保证等待线程中pred的读操作和wait操作的原子性

cv.wait(lock, [] { return ready;}); 相当于:while (!ready) { cv.wait(lock);}

ready==false的时候,while语句执行到wait这里,然后就堵塞到这行,等到通知信号来唤醒它,同时解锁互斥量,不影响其他线程获取锁。当 cv.notify_all(); 时,通知所有线程,等待唤醒的线程收到了信号就被唤醒开始干活,首先就是不断的尝试重新获取并加锁互斥量。若获取不到锁,就卡在这里,反复尝试加锁,若获取到了锁才往下执行。

没有locker.unlock();,因为局部变量在函数体中执行完后自动释放。

class Foo {
condition_variable cv;
mutex mtx;
int flag = 0;
public:
Foo() {
}
void first(function<void()> printFirst) {
printFirst();
flag = 1;
cv.notify_all();
}
void second(function<void()> printSecond) {
unique_lock<mutex>locker(mtx);
cv.wait(locker,[this]{return flag == 1;});
printSecond();
flag = 2;
cv.notify_one();
}
void third(function<void()> printThird) {
unique_lock<mutex>locker(mtx);
cv.wait(locker,[this]{return flag == 2;});
printThird();
}
};

1115. 交替打印 FooBar

atomic operation

#include<atomic>
class FooBar {
private:
int n;
atomic_bool foo_done = false;
public:
FooBar(int n) {
this->n = n;
}

void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
while(foo_done) this_thread::yield();
// printFoo() outputs "foo". Do not change or remove this line.
printFoo();
foo_done = true;
}
}

void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
while(!foo_done) this_thread::yield();
// printBar() outputs "bar". Do not change or remove this line.
printBar();
foo_done = false;
}
}
};

这里阻塞进程用了yield(),而不是像1114题一样使用sleep_for()。使用sleep_for()始终超时,使用yield()的效率却和使用信号量的效率相当。而在1114题中,使用sleep_for()的耗时仅为使用yield()的一半。

semaphore

#include<semaphore.h>
class FooBar {
private:
int n;
sem_t foo_done, bar_done;
public:
FooBar(int n) {
this->n = n;
sem_init(&foo_done, 0 , 0);
sem_init(&bar_done, 0 , 1);
}

void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
sem_wait(&bar_done);
// printFoo() outputs "foo". Do not change or remove this line.
printFoo();
sem_post(&foo_done);
}
}

void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
sem_wait(&foo_done);
// printBar() outputs "bar". Do not change or remove this line.
printBar();
sem_post(&bar_done);
}
}
};

condition variable

class FooBar {
private:
int n;
mutex mtx;
condition_variable cv;
bool foo_done = false;
public:
FooBar(int n) {
this->n = n;
}

void foo(function<void()> printFoo) {
unique_lock<mutex>locker(mtx);
for (int i = 0; i < n; i++) {
cv.wait(locker, [this] {return !foo_done;});
// printFoo() outputs "foo". Do not change or remove this line.
printFoo();
foo_done = true;
cv.notify_one();
}
}

void bar(function<void()> printBar) {
unique_lock<mutex>locker(mtx);
for (int i = 0; i < n; i++) {
cv.wait(locker, [this] {return foo_done;});
// printBar() outputs "bar". Do not change or remove this line.
printBar();
foo_done = false;
cv.notify_one();
}
}
};

1116. 打印零与奇偶数

atomic operation

#include <atomic>
class ZeroEvenOdd {
private:
int n;
atomic_int flag = 0;
public:
ZeroEvenOdd(int n) {
this->n = n;
}

// printNumber(x) outputs "x", where x is an integer.
void zero(function<void(int)> printNumber) {
for(int i = 1; i <= n; i++){
while(flag) this_thread::yield();
printNumber(0);
if(i % 2 == 1){
flag = 1;
}
else{
flag = 2;
}
}
}

void even(function<void(int)> printNumber) {
for(int i = 2; i <= n; i += 2){
while(flag != 2) this_thread::yield();
printNumber(i);
flag = 0;
}
}

void odd(function<void(int)> printNumber) {
for(int i = 1; i <= n; i += 2){
while(flag != 1) this_thread::yield();
printNumber(i);
flag = 0;
}
}
};

很快。

semaphore

#include <semaphore.h>
class ZeroEvenOdd {
private:
int n;
sem_t s0, s1, s2;
public:
ZeroEvenOdd(int n) {
this->n = n;
sem_init(&s0, 0, 1);
sem_init(&s1, 0, 0);
sem_init(&s2, 0, 0);
}

// printNumber(x) outputs "x", where x is an integer.
void zero(function<void(int)> printNumber) {
for(int i = 1; i <= n; i++){
sem_wait(&s0);
printNumber(0);
if(i % 2 == 1){
sem_post(&s1);
}
else{
sem_post(&s2);
}
}
}

void even(function<void(int)> printNumber) {
for(int i = 2; i <= n; i += 2){
sem_wait(&s2);
printNumber(i);
sem_post(&s0);
}
}

void odd(function<void(int)> printNumber) {
for(int i = 1; i <= n; i += 2){
sem_wait(&s1);
printNumber(i);
sem_post(&s0);
}
}
};

condition variable

class ZeroEvenOdd {
private:
int n;
mutex mtx;
condition_variable cv;
int flag = 0;
public:
ZeroEvenOdd(int n) {
this->n = n;
}

// printNumber(x) outputs "x", where x is an integer.
void zero(function<void(int)> printNumber) {
unique_lock<mutex> locker(mtx);
for(int i = 1; i <= n; i++){
cv.wait(locker, [this] {return flag == 0;});
printNumber(0);
if(i % 2){
flag = 1;
}
else{
flag = 2;
}
cv.notify_all();
}
}

void even(function<void(int)> printNumber) {
unique_lock<mutex> locker(mtx);
for(int i = 2; i <= n; i+=2){
cv.wait(locker, [this] {return flag == 2;});
printNumber(i);
flag = 0;
cv.notify_all();
}
}

void odd(function<void(int)> printNumber) {
unique_lock<mutex> locker(mtx);
for(int i = 1; i <= n; i+=2){
cv.wait(locker, [this] {return flag == 1;});
printNumber(i);
flag = 0;
cv.notify_all();
}
}
};

1117. H2O 生成

atomic operation

#include<atomic>
class H2O {
private:
atomic_int H_cnt = 0;
public:
H2O() {
}
void hydrogen(function<void()> releaseHydrogen) {
while(H_cnt == 2) this_thread::yield();
releaseHydrogen();
H_cnt++;
}
void oxygen(function<void()> releaseOxygen) {
while(H_cnt != 2) this_thread::yield();
releaseOxygen();
H_cnt = 0;
}
};

很简洁,但比信号量慢点。

semaphore

#include<semaphore.h>
class H2O {
private:
sem_t H_done,O_done;
int H_cnt = 0;
public:
H2O() {
sem_init(&H_done,0,0);
sem_init(&O_done,0,2);
}
void hydrogen(function<void()> releaseHydrogen) {
sem_wait(&O_done);
releaseHydrogen();
H_cnt++;
if(H_cnt == 2){
sem_post(&H_done);
}
}
void oxygen(function<void()> releaseOxygen) {
sem_wait(&H_done);
releaseOxygen();
H_cnt = 0;
sem_post(&O_done);
sem_post(&O_done);
}
};

比1114更复杂,需要变量记录当前已释放的H原子个数,达到2个才能放O原子。

condition variable

class H2O {
mutex mtx;
condition_variable cv;
int H_cnt = 0;
public:
H2O() {
}

void hydrogen(function<void()> releaseHydrogen) {
unique_lock<mutex>locker(mtx);
cv.wait(locker, [this] {return H_cnt < 2;});
// releaseHydrogen() outputs "H". Do not change or remove this line.
releaseHydrogen();
H_cnt++;
cv.notify_all();
}

void oxygen(function<void()> releaseOxygen) {
unique_lock<mutex>locker(mtx);
cv.wait(locker, [this] {return H_cnt == 2;});
// releaseOxygen() outputs "O". Do not change or remove this line.
releaseOxygen();
H_cnt = 0;
cv.notify_all();
}
};

1195. 交替打印字符串

atomic operation

#include <atomic>
class FizzBuzz {
private:
int n;
atomic_int flag = 0;
public:
FizzBuzz(int n) {
this->n = n;
}

// printFizz() outputs "fizz".
void fizz(function<void()> printFizz) {
for(int i = 3; i <= n; i += 3){
if(i % 5 != 0){
while(flag != 1) this_thread::yield();
printFizz();
flag = 0;
}
}
}

// printBuzz() outputs "buzz".
void buzz(function<void()> printBuzz) {
for(int i = 5; i <= n; i += 5){
if(i % 3 != 0){
while(flag != 2) this_thread::yield();
printBuzz();
flag = 0;
}
}
}

// printFizzBuzz() outputs "fizzbuzz".
void fizzbuzz(function<void()> printFizzBuzz) {
for(int i = 1; i <= n; i++){
if(i % 5 == 0 && i % 3 == 0){
while(flag != 3) this_thread::yield();
printFizzBuzz();
flag = 0;
}
}
}

// printNumber(x) outputs "x", where x is an integer.
void number(function<void(int)> printNumber) {
for(int i = 1; i <= n; i++){
while(flag) this_thread::yield();
if(i % 5 != 0 && i % 3 != 0){
printNumber(i);
}
else if(i % 5 != 0 && i % 3 == 0){
flag = 1;
}
else if(i % 5 == 0 && i % 3 != 0){
flag = 2;
}
else{
flag = 3;
}
}
}
};

semaphore

#include <semaphore.h>
class FizzBuzz {
private:
int n;
sem_t numPrint, fizzPrint, buzzPrint, fzbzPrint;
public:
FizzBuzz(int n) {
this->n = n;
sem_init(&numPrint, 0, 1);
sem_init(&fizzPrint, 0, 0);
sem_init(&buzzPrint, 0, 0);
sem_init(&fzbzPrint, 0, 0);
}

// printFizz() outputs "fizz".
void fizz(function<void()> printFizz) {
for(int i = 1; i <= n; i++){
if(i % 3 == 0 && i % 5 != 0){
sem_wait(&fizzPrint);
printFizz();
sem_post(&numPrint);
}
}
}

// printBuzz() outputs "buzz".
void buzz(function<void()> printBuzz) {
for(int i = 1; i <= n; i++){
if(i % 3 != 0 && i % 5 == 0){
sem_wait(&buzzPrint);
printBuzz();
sem_post(&numPrint);
}
}
}

// printFizzBuzz() outputs "fizzbuzz".
void fizzbuzz(function<void()> printFizzBuzz) {
for(int i = 1; i <= n; i++){
if(i % 3 == 0 && i % 5 == 0){
sem_wait(&fzbzPrint);
printFizzBuzz();
sem_post(&numPrint);
}
}
}

// printNumber(x) outputs "x", where x is an integer.
void number(function<void(int)> printNumber) {
for(int i = 1; i <= n; i++){
sem_wait(&numPrint);
if(i % 3 != 0 && i % 5 != 0){
printNumber(i);
sem_post(&numPrint);
}
else if(i % 3 == 0 && i % 5 != 0){
sem_post(&fizzPrint);
}
else if(i % 3 != 0 && i % 5 == 0){
sem_post(&buzzPrint);
}
else{
sem_post(&fzbzPrint);
}
}
}
};

依然是基础的变式。

condition variable

class FizzBuzz {
private:
int n, flag = 0;
mutex mtx;
condition_variable cv;
public:
FizzBuzz(int n) {
this->n = n;
}

// printFizz() outputs "fizz".
void fizz(function<void()> printFizz) {
unique_lock<mutex>locker(mtx);
for(int i = 3; i <= n; i += 3){
if(i % 5 != 0){
cv.wait(locker, [this] {return flag == 1;});
printFizz();
flag = 0;
cv.notify_all();
}
}
}

// printBuzz() outputs "buzz".
void buzz(function<void()> printBuzz) {
unique_lock<mutex>locker(mtx);
for(int i = 5; i <= n; i += 5){
if(i % 3 != 0){
cv.wait(locker, [this] {return flag == 2;});
printBuzz();
flag = 0;
cv.notify_all();
}
}
}

// printFizzBuzz() outputs "fizzbuzz".
void fizzbuzz(function<void()> printFizzBuzz) {
unique_lock<mutex>locker(mtx);
for(int i = 1; i <= n; i++){
if(i % 5 == 0 && i % 3 == 0){
cv.wait(locker, [this] {return flag == 3;});
printFizzBuzz();
flag = 0;
cv.notify_all();
}
}
}

// printNumber(x) outputs "x", where x is an integer.
void number(function<void(int)> printNumber) {
unique_lock<mutex>locker(mtx);
for(int i = 1; i <= n; i++){
cv.wait(locker, [this] {return flag == 0;});
if(i % 5 != 0 && i % 3 != 0){
printNumber(i);
}
else if(i % 5 != 0 && i % 3 == 0){
flag = 1;
cv.notify_all();
}
else if(i % 5 == 0 && i % 3 != 0){
flag = 2;
cv.notify_all();
}
else{
flag = 3;
cv.notify_all();
}
}
}
};

1226. 哲学家进餐

atomic operation

#include <atomic>
class DiningPhilosophers {
private:
atomic_bool forks[5];
public:
DiningPhilosophers() {
for(int i = 0; i < 5; i++){
forks[i] = true;
}
}

void wantsToEat(int philosopher,
function<void()> pickLeftFork,
function<void()> pickRightFork,
function<void()> eat,
function<void()> putLeftFork,
function<void()> putRightFork) {
int L = philosopher, R = (philosopher + 1) % 5;
if(philosopher % 2){
while(!forks[L]) this_thread::yield();
forks[L] = false;
while(!forks[R]) this_thread::yield();
forks[R] = false;
}
else{
while(!forks[R]) this_thread::yield();
forks[R] = false;
while(!forks[L]) this_thread::yield();
forks[L] = false;
}
pickLeftFork();
pickRightFork();
eat();
putLeftFork();
putRightFork();
forks[L] = true;
forks[R] = true;
}
};

思路和semaphore相同。但是对原子操作的使用不太熟练,尝试在声明forks[]时就初始化,出错了,遂改为在constructor中初始化。另一方面,上述代码能通过测试,但似乎并不是原子操作。如下图,经测试,在while()阻塞之后设置延时,就出现了bug。暂未实现真正的原子操作。

semaphore

奇数的哲学家先拿左边叉子,偶数的先拿右边叉子,不会出现循环等待。

#include <semaphore.h>
class DiningPhilosophers {
private:
sem_t forks[5];
public:
DiningPhilosophers() {
for(int i = 0; i < 5; i++){
sem_init(&forks[i], 0, 1);
}
}

void wantsToEat(int philosopher,
function<void()> pickLeftFork,
function<void()> pickRightFork,
function<void()> eat,
function<void()> putLeftFork,
function<void()> putRightFork) {
int L = philosopher, R = (philosopher + 1) % 5;
if(philosopher % 2){
sem_wait(&forks[L]);
sem_wait(&forks[R]);
}
else{
sem_wait(&forks[R]);
sem_wait(&forks[L]);
}
pickLeftFork();
pickRightFork();
eat();
putLeftFork();
putRightFork();
sem_post(&forks[L]);
sem_post(&forks[R]);
}
};

condition variable

class DiningPhilosophers {
private:
mutex mtx;
condition_variable cv;
bool forks[5];
public:
DiningPhilosophers() {
for(int i = 0; i < 5; i++){
forks[i] = true;
}
}

void wantsToEat(int philosopher,
function<void()> pickLeftFork,
function<void()> pickRightFork,
function<void()> eat,
function<void()> putLeftFork,
function<void()> putRightFork) {
int L = philosopher, R = (philosopher + 1) % 5;
unique_lock<mutex> locker(mtx);
cv.wait(locker, [this, L, R] {return forks[L] && forks[R];});
forks[L] = false;
forks[R] = false;
locker.unlock();
pickLeftFork();
pickRightFork();
eat();
putLeftFork();
putRightFork();
locker.lock();
forks[L] = true;
forks[R] = true;
locker.unlock();
cv.notify_all();
}
};

要么同时拿两个餐具,要么都不拿。和原子操作不同的是,在发现左右叉子都可用后,马上加锁了,不会有其他哲学家发现叉子可用。