[LeetCoe 1116.] 打印零与奇偶数

LeetCoe 1116. 打印零与奇偶数

题目描述

假设有这么一个类:

class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // 构造函数
  public void zero(printNumber) { ... }  // 仅打印出 0
  public void even(printNumber) { ... }  // 仅打印出 偶数
  public void odd(printNumber) { ... }   // 仅打印出 奇数
}

相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程:

线程 A 将调用 zero(),它只输出 0 。
线程 B 将调用 even(),它只输出偶数。
线程 C 将调用 odd(),它只输出奇数。
每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ,其中序列的长度必须为 2n。

示例 1:

输入:n = 2
输出:"0102"
说明:三条线程异步执行,其中一个调用 zero(),另一个线程调用 even(),最后一个线程调用odd()。正确的输出为 "0102"。

示例 2:

输入:n = 5
输出:"0102030405"

解题思路

一个基本思路是用令牌来决定由哪一个线程来工作,通过令牌的传递来决定工作线程和休眠线程。
注意,这里的成员变量被多个线程读写,需要加锁或者使用原子变量。

参考代码

class ZeroEvenOdd {
private:
    int n; // read-only
    atomic<int> x;
    atomic<int> worker;

public:
    ZeroEvenOdd(int n) {
        this->n = n;
        this->x = 1;
        this->worker = -1; // -1,0,1 for 3 worker
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        while (this->x <= this->n) {
            while (this->worker != -1) {
                this_thread::yield();
                // this->x may change its value when this thread yield
                if (this->x > this->n) return;
            }
            printNumber(0);
            this->worker = this->x % 2;
        }
    }

    void even(function<void(int)> printNumber) {
        while (this->x <= this->n) {
            while (this->worker != 0) {
                this_thread::yield();
                // this->x may change its value when this thread yield
                if (this->x > this->n) return;
            }
            printNumber(this->x);
            this->x ++;
            this->worker = -1;
        }
    }

    void odd(function<void(int)> printNumber) {
        while (this->x <= this->n) {
            while (this->worker != 1) {
                this_thread::yield();
                // this->x may change its value when this thread yield
                if (this->x > this->n) return;
            }
            printNumber(this->x);
            this->x ++;
            this->worker = -1;
        }
    }
};

一种错误解答分析

class ZeroEvenOdd {
private:
    int n; // read-only
    atomic<int> x;
    atomic<int> worker;

public:
    ZeroEvenOdd(int n) {
        this->n = n;
        this->x = 1;
        this->worker = -1; // -1,0,1 for 3 worker
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        while (this->x <= this->n) {
            while (this->worker != -1) {
                this_thread::yield();
            }
            // this->x may change its value when this thread yield
            if (this->x > this->n) return;
            printNumber(0);
            this->worker = this->x % 2;
        }
    }

    void even(function<void(int)> printNumber) {
        while (this->x <= this->n) {
            while (this->worker != 0) {
                this_thread::yield();
            }
            // this->x may change its value when this thread yield
            if (this->x > this->n) return;
            printNumber(this->x);
            this->x ++;
            this->worker = -1;
        }
    }

    void odd(function<void(int)> printNumber) {
        while (this->x <= this->n) {
            while (this->worker != 1) {
                this_thread::yield();
            }
            // this->x may change its value when this thread yield
            if (this->x > this->n) return;
            printNumber(this->x);
            this->x ++;
            this->worker = -1;
        }
    }
};

之前写出来上面这种解答,然后超时了,下面分析一下问什么。

我们以 n = 2 为例,错误场景如下:
worker = 0 的线程输出 2 之后,结束运行,此时 x = 3,worker = -1;接下来 worker 1 继续休眠,worker -1 开始工作。
worker = -1 的线程拿到执行令牌,发现此时 x > n 结束了运行,但却没有把令牌继续传递出去。
worker = 1 的线程得不到令牌,始终在尝试拿令牌,无法结束运行。

所以我们的改进办法是,要么按照参考代码一样,每次 yield 都检查是否结束;要么,worker -1 结束的时候,准确把令牌让给还没结束的那个线程。

上一篇:Nginx


下一篇:win10 Celery异步任务报错: Task handler raised error: ValueError('not enough values to unpack (expecte