arttnba3's old blog

- arttnba3的垃圾堆积处 -

0%

【OJ-0x0006-Leetcode】多线程部分write up by arttnba3

Posted on Edited on In

0x00.绪论

虽然说很久以前已经“学过了“多线程的内容，但是其实还是一知半解XD（其实是一点都不懂多线程（虽然说写过几个简单的多线程的应用小程序（👈那只是Java作业的程度啊喂（👈没有用心学习的屑

思来想去还是得靠leetcode来巩固基础知识啊（x

虽然说题目挺少……不过也凑合凑合刷刷

其实盯上的就是题目少的题库

（偷偷在这里说一句为了巩固代码力决定各种语言的写法都学一遍（

0x01.简单

0x00. 按序打印

我们提供了一个类：

public class Foo {
public void first() { print(“first”); }
public void second() { print(“second”); }
public void third() { print(“third”); }
}
三个不同的线程将会共用一个 Foo 实例。

线程 A 将会调用 first() 方法
线程 B 将会调用 second() 方法
线程 C 将会调用 third() 方法
请设计修改程序，以确保 second() 方法在 first() 方法之后被执行，third() 方法在 second() 方法之后被执行。

示例 1:

输入: [1,2,3]
输出: “firstsecondthird”
解释:
有三个线程会被异步启动。
输入 [1,2,3] 表示线程 A 将会调用 first() 方法，线程 B 将会调用 second() 方法，线程 C 将会调用 third() 方法。
正确的输出是 “firstsecondthird”。
示例 2:

输入: [1,3,2]
输出: “firstsecondthird”
解释:
输入 [1,3,2] 表示线程 A 将会调用 first() 方法，线程 B 将会调用 third() 方法，线程 C 将会调用 second() 方法。
正确的输出是 “firstsecondthird”。

提示：

尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。
你看到的输入格式主要是为了确保测试的全面性。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-in-order
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

【简单】难度的唯一一道题，看来题库也才刚刚建设起来呐

解法一：信号量

使用自带锁的信号量（Semaphore）可以很方便地实现我们的功能，各大语言的标准库都提供有自己的标准信号量的实现

因为只需要保证second()和third()方法在first()方法之后执行即可，故不需要为first()方法上锁

大致执行过程如下：

  • 为second()和third()设置两个信号量s2，s3，置为0
  • 执行first()方法时解锁s2
  • 执行second()方法时先等待s2解锁，在最后锁上s2并解锁s3
  • 执行third()方法时先等待s3解锁，在最后锁上s3

构造代码如下：

C++版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <semaphore.h>

class Foo 
{
public:
    sem_t sem_pthread_2, sem_pthread_3;
    Foo() 
    {
        sem_init(&sem_pthread_2,0,0);
        sem_init(&sem_pthread_3,0,0);
    }

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

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

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

image.png

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Foo 
{
    Semaphore sem_thread_2,sem_thread_3;
    public Foo() 
    {
        sem_thread_2 = new Semaphore(0);
        sem_thread_3 = new Semaphore(0);
    }

    public void first(Runnable printFirst) throws InterruptedException 
    {        
        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
        sem_thread_2.release();
    }

    public void second(Runnable printSecond) throws InterruptedException 
    {
        sem_thread_2.acquire();
        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
        sem_thread_3.release();
    }

    public void third(Runnable printThird) throws InterruptedException 
    {
        sem_thread_3.acquire();    
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}

image.png

在多线程上Java的速度似乎比C++快好多呢

Python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from threading import Semaphore
class Foo:
    def __init__(self):
        self.sem_thread_s2 = Semaphore(0)
        self.sem_thread_s3 = Semaphore(0)


    def first(self, printFirst: 'Callable[[], None]') -> None:
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.sem_thread_s2.release()


    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.sem_thread_s2.acquire()
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.sem_thread_s3.release()


    def third(self, printThird: 'Callable[[], None]') -> None:
        self.sem_thread_s3.acquire()
        # printThird() outputs "third". Do not change or remove this line.
        printThird()

image.png

解法二：互斥锁

和解法一的思路其实是类似的

构造代码如下：

C++版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <mutex>

class Foo 
{
public:
    std::mutex lock_2, lock_3;
    Foo() 
    {
        lock_2.lock();
        lock_3.lock();
    }

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

    void second(function<void()> printSecond) 
    {
        lock_2.lock();    
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        lock_3.unlock();
    }

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

image.png

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Foo 
{
    boolean first_finished, second_finished;
    public Foo() 
    {
        first_finished = false;
        second_finished = false;
    }

    public void first(Runnable printFirst) throws InterruptedException 
    {        
        // printFirst.run() outputs "first". Do not change or remove this line.
        synchronized(this)
        {
            printFirst.run();
            first_finished = true;
            this.notifyAll();
        }
    }

    public void second(Runnable printSecond) throws InterruptedException 
    {
        synchronized(this)
        {
            while(!first_finished)
                this.wait();
            first_finished = false;
            printSecond.run();
            second_finished = true;
            this.notifyAll();
        }
        // printSecond.run() outputs "second". Do not change or remove this line.
        
    }

    public void third(Runnable printThird) throws InterruptedException 
    {
        synchronized(this)
        {
            while(!second_finished)
                wait();
            second_finished = false;
            printThird.run();
            notifyAll();
        }   
        // printThird.run() outputs "third". Do not change or remove this line.
        
    }
}

image.png

Python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from threading import Lock
class Foo:
    def __init__(self):
        self.lock_s2 = Lock()
        self.lock_s3 = Lock()
        self.lock_s2.acquire()
        self.lock_s3.acquire()


    def first(self, printFirst: 'Callable[[], None]') -> None:
        # printFirst() outputs "first". Do not change or remove this line.
        printFirst()
        self.lock_s2.release()


    def second(self, printSecond: 'Callable[[], None]') -> None:
        self.lock_s2.acquire()
        # printSecond() outputs "second". Do not change or remove this line.
        printSecond()
        self.lock_s3.release()


    def third(self, printThird: 'Callable[[], None]') -> None:
        self.lock_s3.acquire()
        # printThird() outputs "third". Do not change or remove this line.
        printThird()

GUBN_FI1CF7RB06CDLJLJV2.png

0x01.中等

0x00.打印零与奇偶数

假设有这么一个类：

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”

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-zero-even-odd
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：信号量

依然可以使用信号量来解决这个问题

需要注意的是数字0是需要第一个被打印的，故打印0的线程的初始信号量应当设为1

C++版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <semaphore.h>
class ZeroEvenOdd 
{
private:
    int n, count = 0;
    sem_t sem_zero, sem_even, sem_odd;

public:
    ZeroEvenOdd(int n) 
    {
        this->n = n;
        sem_init(&sem_zero,0,1);
        sem_init(&sem_even,0,0);
        sem_init(&sem_odd,0,0);
    }

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

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

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

image.png

Java版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.concurrent.Semaphore;

class ZeroEvenOdd 
{
    Semaphore sem_even, sem_odd, sem_zero;
    int n;
    public ZeroEvenOdd(int n) 
    {
        sem_zero = new Semaphore(1);
        sem_even = new Semaphore(0);
        sem_odd = new Semaphore(0);
        this.n = n;
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException 
    {
        for(int i=0;i<n;i++)
        {
            sem_zero.acquire();
            printNumber.accept(0);
            if(i%2 != 0)
                sem_even.release();
            else
                sem_odd.release();
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException 
    {
        for(int i=2;i<=n;i+=2)
        {
            sem_even.acquire();
            printNumber.accept(i);
            sem_zero.release();
        }
    }

    public void odd(IntConsumer printNumber) throws InterruptedException 
    {
        for(int i=1;i<=n;i+=2)
        {
            sem_odd.acquire();
            printNumber.accept(i);
            sem_zero.release();
        }
    }
}

image.png

Python版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from threading import Semaphore
class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n
        self.sem_zero = Semaphore(1)
        self.sem_odd = Semaphore(0)
        self.sem_even = Semaphore(0)
        
        
	# printNumber(x) outputs "x", where x is an integer.
    def zero(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(0,self.n):
            self.sem_zero.acquire()
            printNumber(0)
            if i%2 == 0:
                self.sem_odd.release()
            else:
                self.sem_even.release()
        
        
        
    def even(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(2,self.n+1,2):
            self.sem_even.acquire()
            printNumber(i)
            self.sem_zero.release()
        
        
        
    def odd(self, printNumber: 'Callable[[int], None]') -> None:
        for i in range(1,self.n+1,2):
            self.sem_odd.acquire()
            printNumber(i)
            self.sem_zero.release()

image.png

解法二：互斥锁

依然可以用互斥锁来解决这个问题

构造代码如下：

C++版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <mutex>
class ZeroEvenOdd 
{
private:
    int n;
    std::mutex lock_zero, lock_odd, lock_even;

public:
    ZeroEvenOdd(int n) 
    {
        this->n = n;
        lock_zero.unlock();
        lock_odd.lock();
        lock_even.lock();
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) 
    {
        for(int i=0;i<n;i++)
        {
            lock_zero.lock();
            printNumber(0);
            if(i % 2)
                lock_even.unlock();
            else
                lock_odd.unlock();
        }
    }

    void even(function<void(int)> printNumber) 
    {
        for(int i=2;i<=n;i+=2)
        {
            lock_even.lock();
            printNumber(i);
            lock_zero.unlock();
        }
    }

    void odd(function<void(int)> printNumber) 
    {
        for(int i=1;i<=n;i+=2)
        {
            lock_odd.unlock();
            printNumber(i);
            lock_zero.unlock();
        }
    }
};

image.png

Welcome to my other publishing channels