題目來源
leetcode 多線程 / Shell
相關:
刷題彙總(一)leetcode 精選50題 JavaScript答案總結
刷題彙總(二)劍指Offer 66題 C++答案總結
刷題彙總(三)leetcode 精選50題 C++答案總結
刷題彙總(四)技術類程式設計題彙總 C++
刷題彙總(五)leetcode 熱題 HOT 100 C++ 答案總結
這篇文章使用 POSIX 編寫多線程 C++ 程式。POSIX Threads 或 Pthreads 提供的 API 可在多種類 Unix POSIX 系統上可用,比如 FreeBSD、NetBSD、GNU/Linux、Mac OS X 和 Solaris。
知識點1:建立線程/終止線程
#include <pthread.h>
pthread_create (thread, attr, start_routine, arg)
pthread_exit (status)
使用 -lpthread 庫編譯:
$ g++ test.cpp -lpthread -o test.o
1、按序列印
我們提供了一個類:
public class Foo {
public void one() { print("one"); }
public void two() { print("two"); }
public void three() { print("three"); }
}
三個不同的線程将會共用一個 Foo 執行個體。
線程 A 将會調用 one() 方法
線程 B 将會調用 two() 方法
線程 C 将會調用 three() 方法
請設計修改程式,以確定 two() 方法在 one() 方法之後被執行,three() 方法在 two() 方法之後被執行。
示例 1:
輸入: [1,2,3]
輸出: “onetwothree”
解釋:
有三個線程會被異步啟動。
輸入 [1,2,3] 表示線程 A 将會調用 one() 方法,線程 B 将會調用 two() 方法,線程 C 将會調用 three() 方法。
正确的輸出是 “onetwothree”。
示例 2:
輸入: [1,3,2]
輸出: “onetwothree”
解釋:
輸入 [1,3,2] 表示線程 A 将會調用 one() 方法,線程 B 将會調用 three() 方法,線程 C 将會調用 two() 方法。
正确的輸出是 “onetwothree”。
注意:
盡管輸入中的數字似乎暗示了順序,但是我們并不保證線程在作業系統中的排程順序。
你看到的輸入格式主要是為了確定測試的全面性。
#include <semaphore.h>
class Foo {
public:
sem_t t1, t2, t3;
Foo() {
sem_init(&t1,0,1);
sem_init(&t2,0,0);
sem_init(&t3,0,0);
}
void first(function<void()> printFirst) {
sem_wait(&t1);
// printFirst() outputs "first". Do not change or remove this line.
printFirst();
sem_post(&t2);
}
void second(function<void()> printSecond) {
sem_wait(&t2);
// printSecond() outputs "second". Do not change or remove this line.
printSecond();
sem_post(&t3);
}
void third(function<void()> printThird) {
sem_wait(&t3);
// printThird() outputs "third". Do not change or remove this line.
printThird();
}
};
知識點2:信号量
#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int val); // 初始化信号量
int sem_wait(sem_t *sem); // 信号量減1
int sem_post(sem_t *sem); // 信号量加1
int sem_destory(sem_t *sem); // 銷毀信号量
2、交替列印FooBar
我們提供一個類:
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”
# include<semaphore.h>
class FooBar {
private:
int n;
sem_t t1, t2;
public:
FooBar(int n) {
this->n = n;
sem_init(&t1,0,1);
sem_init(&t2,0,0);
}
void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
sem_wait(&t1);
// printFoo() outputs "foo". Do not change or remove this line.
printFoo();
sem_post(&t2);
}
}
void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
sem_wait(&t2);
// printBar() outputs "bar". Do not change or remove this line.
printBar();
sem_post(&t1);
}
}
};
class FooBar {
private:
int n;
pthread_mutex_t t1, t2;
public:
FooBar(int n) {
this->n = n;
pthread_mutex_init(&t1,NULL);
pthread_mutex_init(&t2,NULL);
pthread_mutex_lock(&t2);
}
void foo(function<void()> printFoo) {
for (int i = 0; i < n; i++) {
pthread_mutex_lock(&t1);
// printFoo() outputs "foo". Do not change or remove this line.
printFoo();
pthread_mutex_unlock(&t2);
}
}
void bar(function<void()> printBar) {
for (int i = 0; i < n; i++) {
pthread_mutex_lock(&t2);
// printBar() outputs "bar". Do not change or remove this line.
printBar();
pthread_mutex_unlock(&t1);
}
}
};
知識點3:互斥量
pthread_mutex_t sum_mutex; //互斥鎖
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER //靜态初始化
pthread_mutex_init( &sum_mutex, NULL ); //動态初始化 初始化成功傳回0
pthread_mutex_lock( &sum_mutex ); //加鎖
pthread_mutex_unlock( &sum_mutex ); //釋放鎖,供其他線程使用
pthread_mutex_destroy( &sum_mutex ); //登出鎖
3、列印零與奇偶數
假設有這麼一個類:
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”
# include<semaphore.h>
class ZeroEvenOdd {
private:
int n;
sem_t t0, t1, t2;
public:
ZeroEvenOdd(int n) {
this->n = n;
sem_init(&t0,0,1);
sem_init(&t1,0,0);
sem_init(&t2,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(&t0);
printNumber(0);
if(i%2==1) sem_post(&t1);
else sem_post(&t2);
}
}
void even(function<void(int)> printNumber) {
for(int i=2;i<=n;i+=2){
sem_wait(&t2);
printNumber(i);
sem_post(&t0);
}
}
void odd(function<void(int)> printNumber) {
for(int i=1;i<=n;i+=2){
sem_wait(&t1);
printNumber(i);
sem_post(&t0);
}
}
};
4、H2O 生成
現在有兩種線程,氫 oxygen 和氧 hydrogen,你的目标是組織這兩種線程來産生水分子。
存在一個屏障(barrier)使得每個線程必須等候直到一個完整水分子能夠被産生出來。
氫和氧線程會被分别給予 releaseHydrogen 和 releaseOxygen 方法來允許它們突破屏障。
這些線程應該三三成組突破屏障并能立即組合産生一個水分子。
你必須保證産生一個水分子所需線程的結合必須發生在下一個水分子産生之前。
換句話說:
如果一個氧線程到達屏障時沒有氫線程到達,它必須等候直到兩個氫線程到達。
如果一個氫線程到達屏障時沒有其它線程到達,它必須等候直到一個氧線程和另一個氫線程到達。
書寫滿足這些限制條件的氫、氧線程同步代碼。
示例 1:
輸入: “HOH”
輸出: “HHO”
解釋: “HOH” 和 “OHH” 依然都是有效解。
示例 2:
輸入: “OOHHHH”
輸出: “HHOHHO”
解釋: “HOHHHO”, “OHHHHO”, “HHOHOH”, “HOHHOH”, “OHHHOH”, “HHOOHH”, “HOHOHH” 和 “OHHOHH” 依然都是有效解。
限制條件:
輸入字元串的總長将會是 3n, 1 ≤ n ≤ 50;
輸入字元串中的 “H” 總數将會是 2n;
輸入字元串中的 “O” 總數将會是 n。
# include<semaphore.h>
class H2O {
public:
sem_t h_limit, o_limit, h, o;
H2O() {
sem_init(&h_limit,0,2);
sem_init(&o_limit,0,1);
sem_init(&h,0,0);
sem_init(&o,0,0);
}
void hydrogen(function<void()> releaseHydrogen) {
sem_wait(&h_limit);
sem_post(&h);
sem_wait(&o);
// releaseHydrogen() outputs "H". Do not change or remove this line.
releaseHydrogen();
sem_post(&h_limit);
}
void oxygen(function<void()> releaseOxygen) {
sem_wait(&o_limit);
sem_post(&o);
sem_post(&o);
sem_wait(&h);
sem_wait(&h);
// releaseOxygen() outputs "O". Do not change or remove this line.
releaseOxygen();
sem_post(&o_limit);
}
};
5、交替列印字元串
編寫一個可以從 1 到 n 輸出代表這個數字的字元串的程式,但是:
如果這個數字可以被 3 整除,輸出 “fizz”。
如果這個數字可以被 5 整除,輸出 “buzz”。
如果這個數字可以同時被 3 和 5 整除,輸出 “fizzbuzz”。
例如,當 n = 15,輸出: 1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz。
假設有這麼一個類:
class FizzBuzz {
public FizzBuzz(int n) { ... } // constructor
public void fizz(printFizz) { ... } // only output "fizz"
public void buzz(printBuzz) { ... } // only output "buzz"
public void fizzbuzz(printFizzBuzz) { ... } // only output "fizzbuzz"
public void number(printNumber) { ... } // only output the numbers
}
請你實作一個有四個線程的多線程版 FizzBuzz, 同一個 FizzBuzz 執行個體會被如下四個線程使用:
線程A将調用 fizz() 來判斷是否能被 3 整除,如果可以,則輸出 fizz。
線程B将調用 buzz() 來判斷是否能被 5 整除,如果可以,則輸出 buzz。
線程C将調用 fizzbuzz() 來判斷是否同時能被 3 和 5 整除,如果可以,則輸出 fizzbuzz。
線程D将調用 number() 來實作輸出既不能被 3 整除也不能被 5 整除的數字。
# include<semaphore.h>
class FizzBuzz {
private:
int n;
sem_t t0, t3, t5, t35;
public:
FizzBuzz(int n) {
this->n = n;
sem_init(&t0,0,1);
sem_init(&t3,0,0);
sem_init(&t5,0,0);
sem_init(&t35,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(&t3);
printFizz();
sem_post(&t0);
}
}
}
// printBuzz() outputs "buzz".
void buzz(function<void()> printBuzz) {
for(int i=1;i<=n;i++){
if(i%3!=0 && i%5==0){
sem_wait(&t5);
printBuzz();
sem_post(&t0);
}
}
}
// printFizzBuzz() outputs "fizzbuzz".
void fizzbuzz(function<void()> printFizzBuzz) {
for(int i=1;i<=n;i++){
if(i%3==0 && i%5==0){
sem_wait(&t35);
printFizzBuzz();
sem_post(&t0);
}
}
}
// printNumber(x) outputs "x", where x is an integer.
void number(function<void(int)> printNumber) {
for(int i=1;i<=n;i++){
sem_wait(&t0);
if(i%3!=0 && i%5!=0){
printNumber(i);
sem_post(&t0);
}
else if(i%3==0 && i%5!=0){
sem_post(&t3);
}
else if(i%3!=0 && i%5==0){
sem_post(&t5);
}
else{
sem_post(&t35);
}
}
}
};
6、哲學家進餐
5 個沉默寡言的哲學家圍坐在圓桌前,每人面前一盤意面。叉子放在哲學家之間的桌面上。(5 個哲學家,5 根叉子)
所有的哲學家都隻會在思考和進餐兩種行為間交替。哲學家隻有同時拿到左邊和右邊的叉子才能吃到面,而同一根叉子在同一時間隻能被一個哲學家使用。每個哲學家吃完面後都需要把叉子放回桌面以供其他哲學家吃面。隻要條件允許,哲學家可以拿起左邊或者右邊的叉子,但在沒有同時拿到左右叉子時不能進食。
假設面的數量沒有限制,哲學家也能随便吃,不需要考慮吃不吃得下。
設計一個進餐規則(并行算法)使得每個哲學家都不會挨餓;也就是說,在沒有人知道别人什麼時候想吃東西或思考的情況下,每個哲學家都可以在吃飯和思考之間一直交替下去。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsICM38FdsYkRGZkRG9lcvx2bjxiNx8VZ6l2cs0TWIFWcwJTWtplMMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL4kTN2MTN0YTMyEjMxkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
問題描述和圖檔來自維基百科 wikipedia.org
哲學家從 0 到 4 按 順時針 編号。請實作函數 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork):
philosopher 哲學家的編号。
pickLeftFork 和 pickRightFork 表示拿起左邊或右邊的叉子。
eat 表示吃面。
putLeftFork 和 pickRightFork 表示放下左邊或右邊的叉子。
由于哲學家不是在吃面就是在想着啥時候吃面,是以思考這個方法沒有對應的回調。
給你 5 個線程,每個都代表一個哲學家,請你使用類的同一個對象來模拟這個過程。在最後一次調用結束之前,可能會為同一個哲學家多次調用該函數。
示例:
輸入:n = 1
輸出:[[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]
解釋:
n 表示每個哲學家需要進餐的次數。
輸出數組描述了叉子的控制和進餐的調用,它的格式如下:
output[i] = [a, b, c] (3個整數)
- a 哲學家編号。
- b 指定叉子:{1 : 左邊, 2 : 右邊}.
-
c 指定行為:{1 : 拿起, 2 : 放下, 3 : 吃面}。
如 [4,2,1] 表示 4 号哲學家拿起了右邊的叉子。
提示:
1 <= n <= 60
# include<semaphore.h>
class DiningPhilosophers {
private:
sem_t sem;
pthread_mutex_t mutex[5];
public:
DiningPhilosophers() {
sem_init(&sem,0,4);
for(int i=0;i<5;i++){
pthread_mutex_init(&mutex[i],NULL);
}
}
// 限定哲學家就餐數量
void wantsToEat(int philosopher,
function<void()> pickLeftFork,
function<void()> pickRightFork,
function<void()> eat,
function<void()> putLeftFork,
function<void()> putRightFork) {
int left = philosopher;
int right = (philosopher+1)%5;
sem_wait(&sem);
pthread_mutex_lock(&mutex[left]);
pthread_mutex_lock(&mutex[right]);
pickLeftFork();
pickRightFork();
eat();
putLeftFork();
putRightFork();
pthread_mutex_unlock(&mutex[left]);
pthread_mutex_unlock(&mutex[right]);
sem_post(&sem);
}
};
# include<semaphore.h>
class DiningPhilosophers {
private:
pthread_mutex_t mutex;
pthread_mutex_t forks_mutex[5];
public:
DiningPhilosophers() {
pthread_mutex_init(&mutex,NULL);
for(int i=0;i<5;i++){
pthread_mutex_init(&forks_mutex[i],NULL);
}
}
// 同時拿起左右2把叉子
void wantsToEat(int philosopher,
function<void()> pickLeftFork,
function<void()> pickRightFork,
function<void()> eat,
function<void()> putLeftFork,
function<void()> putRightFork) {
int left = philosopher;
int right = (philosopher+1)%5;
pthread_mutex_lock(&mutex);
pthread_mutex_lock(&forks_mutex[left]);
pthread_mutex_lock(&forks_mutex[right]);
pickLeftFork();
pickRightFork();
pthread_mutex_unlock(&mutex);
eat();
putLeftFork();
putRightFork();
pthread_mutex_unlock(&forks_mutex[left]);
pthread_mutex_unlock(&forks_mutex[right]);
}
};
# include<semaphore.h>
class DiningPhilosophers {
private:
pthread_mutex_t forks_mutex[5];
public:
DiningPhilosophers() {
for(int i=0;i<5;i++){
pthread_mutex_init(&forks_mutex[i],NULL);
}
}
// 一部分哲學家優先去擷取其左邊的叉子,再去擷取其右邊的叉子;
// 再讓剩餘哲學家優先去擷取其右邊的叉子,再去擷取其左邊的叉子
void wantsToEat(int philosopher,
function<void()> pickLeftFork,
function<void()> pickRightFork,
function<void()> eat,
function<void()> putLeftFork,
function<void()> putRightFork) {
int left = philosopher;
int right = (philosopher+1)%5;
if(philosopher%2 == 1){
pthread_mutex_lock(&forks_mutex[left]);
pthread_mutex_lock(&forks_mutex[right]);
}
else{
pthread_mutex_lock(&forks_mutex[right]);
pthread_mutex_lock(&forks_mutex[left]);
}
pickLeftFork();
pickRightFork();
eat();
putLeftFork();
putRightFork();
pthread_mutex_unlock(&forks_mutex[left]);
pthread_mutex_unlock(&forks_mutex[right]);
}
};
7、統計詞頻
寫一個 bash 腳本以統計一個文本檔案 words.txt 中每個單詞出現的頻率。
為了簡單起見,你可以假設:
words.txt隻包括小寫字母和 ’ ’ 。
每個單詞隻由小寫字母組成。
單詞間由一個或多個空格字元分隔。
示例:
假設 words.txt 内容如下:
the day is sunny the the
the sunny is is
你的腳本應當輸出(以詞頻降序排列):
the 4
is 3
sunny 2
day 1
說明:
不要擔心詞頻相同的單詞的排序問題,每個單詞出現的頻率都是唯一的。
你可以使用一行 Unix pipes 實作嗎?
# Read from the file words.txt and output the word frequency list to stdout.
cat words.txt | xargs -n1 | awk '{data[$1] += 1} END {for(str in data) print data[str],str}' | sort -nr | awk '{print $2, $1}'
xargs 用作替換工具,讀取輸入資料重新格式化後輸出
# cat test.txt
a b c d e
f g h
$ cat test.txt | xargs -n3
a b c
d e f
g h
按照數值大小 反向排序
$ sort -nr
cat words.txt | xargs -n1 | awk '{data[$1] += 1} END {for(str in data) print str,data[str]}' | sort -nr -k2
将第二列按照數值大小 反向排序
$ sort -nr -k2
cat words.txt | awk '{for(i=1;i<=NF;i++) data[$i] += 1} END {for(str in data) print str,data[str]}' | sort -nr -k2
awk '{for(i=1;i<=NF;i++) data[$i] += 1} END {for(str in data) print str,data[str]}' words.txt | sort -nr -k2
NF 一條記錄的字段的數目
NR 已經讀出的記錄數,就是行号,從1開始
統計各行在檔案中出現的次數:
$ sort testfile | uniq -c
當重複的行并不相鄰時,uniq 指令是不起作用的,是以常與sort一起使用
空格改為換行符
$ tr -s ’ ’ ‘\n’
縮減連續重複的字元成指定的單個字元
8、有效電話号碼
給定一個包含電話号碼清單(一行一個電話号碼)的文本檔案 file.txt,寫一個 bash 腳本輸出所有有效的電話号碼。
你可以假設一個有效的電話号碼必須滿足以下兩種格式: (xxx) xxx-xxxx 或 xxx-xxx-xxxx。(x 表示一個數字)
你也可以假設每行前後沒有多餘的空格字元。
示例:
假設 file.txt 内容如下:
987-123-4567
123 456 7890
(123) 456-7890
你的腳本應當輸出下列有效的電話号碼:
987-123-4567
(123) 456-7890
# Read from the file file.txt and output all valid phone numbers to stdout.
grep -E "^\([0-9]{3}\) [0-9]{3}-[0-9]{4}$|^[0-9]{3}-[0-9]{3}-[0-9]{4}$" file.txt
^ 為比對輸入字元串的開始位置,$ 為比對輸入字元串的結束位置
awk "/^\([0-9]{3}\) [0-9]{3}-[0-9]{4}$|^[0-9]{3}-[0-9]{3}-[0-9]{4}$/" file.txt
awk "/^\([0-9]{3}\) [0-9]{3}-[0-9]{4}$/ || /^[0-9]{3}-[0-9]{3}-[0-9]{4}$/" file.txt
awk "/^(\([0-9]{3}\) |[0-9]{3}-)[0-9]{3}-[0-9]{4}$/" file.txt
grep -P "^(\(\d{3}\) |\d{3}-)\d{3}-\d{4}$" file.txt
grep -E主要是用來支援擴充正規表達式 加上-P(使用Perl的正則引擎)在MAC OS下面man grep是沒有-P參數的,新的主流正則引擎已經預設加上了-P參數
9、轉置檔案
給定一個檔案 file.txt,轉置它的内容。
你可以假設每行列數相同,并且每個字段由 ’ ’ 分隔.
示例:
假設 file.txt 檔案内容如下:
name age
alice 21
ryan 30
應當輸出:
name alice ryan
age 21 30
# Read from the file file.txt and print its transposed content to stdout.
awk '{for(i=1;i<=NF;i++)if(arr[i]){arr[i]=arr[i]" "$i}else{arr[i]=$i}}END{for(key in arr)print arr[key]}' file.txt
10、第十行
給定一個文本檔案 file.txt,請隻列印這個檔案中的第十行。
示例:
假設 file.txt 有如下内容:
Line 1
Line 2
Line 3
Line 4
Line 5
Line 6
Line 7
Line 8
Line 9
Line 10
你的腳本應當顯示第十行:
Line 10
說明:
- 如果檔案少于十行,你應當輸出什麼?
- 至少有三種不同的解法,請嘗試盡可能多的方法來解題。
awk 'NR==10' file.txt
NR在awk中指行号
tail -n +10 file.txt | head -1
tail -n +10 從第 10 行至檔案末尾
sed -n '10p' file.txt
-n表示隻輸出比對行,p表示Print