题目描述

我们提供一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例。其中一个线程将会调用foo() 方法，另一个线程将会调用 bar() 方法。

请设计修改程序，以确保 "foobar" 被输出n 次。

样例

示例 1:

输入: n = 1
输出: "foobar"
解释: 这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，"foobar" 将被输出一次。
示例 2:

输入: n = 2
输出: "foobarfoobar"
解释: "foobar" 将被输出两次。

算法1

(原子变量)

原子变量定义：atomic<bool> flag;

函数1：原子变量为true时，线程切换：this_thread::yield();
原子变量为false时，打印Foo
函数2：原子变量为false时，线程切换：this_thread::yield();
原子变量为true时，打印Bar

C++ 代码

class FooBar {
private:
    int n;
    atomic<bool> flag  = true;

public:
    FooBar(int n) {
        this->n  = n;
    }

    void foo(function<void()> printFoo) {

        for (int i  = 0; i  < n; i++) {
            while (!flag) {
                this_thread::yield();
            }
            // printFoo() outputs "foo". Do not change or remove this line.
            printFoo();
            flag  = false;
        }
    }

    void bar(function<void()> printBar) {

        for (int i  = 0; i  < n; i++) {
            while (flag) {
                this_thread::yield();
            }
            // printBar() outputs "bar". Do not change or remove this line.
            printBar();
            flag  = true;
        }
    }
};

算法2

(信号量)

信号量类型：sem_t
信号量相关函数：

sem_init函数
sem_init函数是Posix信号量操作中的函数。sem_init() 初始化一个定位在 sem 的匿名信号量。value 参数指定信号量的初始值。 pshared 参数指明信号量是由进程内线程共享，还是由进程之间共享。如果 pshared 的值为 0，那么信号量将被进程内的线程共享，并且应该放置在这个进程的所有线程都可见的地址上(如全局变量，或者堆上动态分配的变量)。

如果 pshared 是非零值，那么信号量将在进程之间共享，并且应该定位共享内存区域(见 shm_open(3)、mmap(2) 和 shmget(2))。因为通过 fork(2) 创建的孩子继承其父亲的内存映射，因此它也可以见到这个信号量。所有可以访问共享内存区域的进程都可以用 sem_post(3)、sem_wait(3) 等等操作信号量。初始化一个已经初始的信号量其结果未定义。

返回值 
sem_init() 成功时返回 0；错误时，返回 -1，并把 errno 设置为合适的值。

用下面一组函数（系统调用）来实现。


int sem_init(sem_t *sem,int pshared,unsigned int value); 
int sem_destroy(sem_t *sem); 
int sem_wait(sem_t *sem); 
int sem_trywait(sem_t *sem); 
int sem_post(sem_t *sem); 
int sem_getvalue(sem_t *sem); 

Foo函数：减少信号量2，打印Foo，增加信号量1
Bar函数：减少信号量1，打印Bar，增加信号量2

C++ 代码

#include<semaphore.h>

class FooBar {
private:
    int n;
    sem_t sem1;
    sem_t sem2;

public:
    FooBar(int n) {
        this->n = n;
        sem_init(&sem1, 0, 0);
        sem_init(&sem2, 0, 1);
    }

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

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

算法3

(条件变量)

C++代码

class FooBar {
private:
    int n;
    mutex mtx;
    condition_variable cv;

public:
    bool flag = false;

    FooBar(int n) {
        this->n = n;
    }

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

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