arttnba3's blog

- arttnba3的隐秘小窝 -

0%

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

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