（Google面試題）有四個線程1、2、3、4同步寫入數據……C++11實現

最近在學習多線程，題目源自 MoreWindows先生的《秒殺多線程第一篇》（http://blog.csdn.net/morewindows/article/details/7392749）題目摘錄：第五題（Google面試題）有四個線程1、2、3、4。線程1的功能就是輸出1，線程2的功能 ...

最近在學習多線程，題目源自 MoreWindows先生的《秒殺多線程第一篇》（http://blog.csdn.net/morewindows/article/details/7392749）

題目摘錄：

第五題（Google面試題）

有四個線程1、2、3、4。線程1的功能就是輸出1，線程2的功能就是輸出2，以此類推.........現在有四個文件ABCD。初始都為空。現要讓四個文件呈如下格式：

A：1 2 3 4 1 2....

B：2 3 4 1 2 3....

C：3 4 1 2 3 4....

D：4 1 2 3 4 1....

請設計程式。

代碼實現如下：

 1 #include <iostream>
 2 #include <string>
 3 #include <thread>
 4 #include "Semaphore.h"
 5 
 6 constexpr unsigned MAX_COUNT = 10;
 7 constexpr unsigned MAX_THREAD = 4;
 8 
 9 unsigned getNext(unsigned current, bool order) {
10     if (order) {
11         unsigned next = current + 1;
12         return  next % MAX_THREAD; // //正序
13     } else {
14         unsigned next = current - 1;
15         return next % MAX_THREAD; //反序
16     }
17 }
18 
19 class File
20 {
21 public:
22     File(const std::string& name = "0") 
23     :m_name(name)
24     ,m_buffer(MAX_COUNT, '0')
25     ,m_pos(0){
26         
27     }
28 
29     void write(char c) {
30         m_buffer.at(m_pos++) = c;
31     }
32 
33     std::string getName() const {
34         return m_name;
35     }
36     std::string getData() const {
37         return m_buffer;
38     }
39 private:
40     std::string m_name;
41     std::string m_buffer;
42     size_t m_pos;
43 };
44 
45 Semaphore t1(1), t2(1), t3(1), t4(1);
46 Semaphore* semaphoreArray[MAX_THREAD] = { &t1, &t2, &t3, &t4 };
47 File files[MAX_THREAD] = { File("A"), File("B"), File("C"), File("D") };
48 unsigned currentFile[MAX_THREAD] = { 0, 1, 2, 3 }; //每個線程當前應該寫入的文件id
49 
50 void write(unsigned threadId) {
51     const char c = '1' + threadId;
52     auto& fid = currentFile[threadId];
53     //auto fid = threadId;
54     auto nextThreadId = getNext(threadId, true); //正序
55     unsigned count = 0;
56     while (MAX_COUNT != count) {
57         semaphoreArray[threadId]->wait();
58         //寫文件        
59         files[fid].write(c);
60         //將文件傳遞給下一個線程。
61         semaphoreArray[nextThreadId]->signal();
62         //更新要寫入的文件id
63         fid = getNext(fid, false); //逆序
64         ++count;
65     }
66 }
67 
68 
69 int main() {
70     std::cout << "hello" << std::endl;
71 
72     //create thread
73     std::thread threads[MAX_THREAD];
74     for (unsigned i = 0; i != MAX_THREAD; ++i) {
75         threads[i] = std::thread(write, i);
76     }
77 
78     //join
79     for (auto& thread : threads) {
80         thread.join();
81     }
82 
83     //output
84     for (const auto& file: files) {
85         std::cout << file.getName() << ": " << file.getData() << std::endl;
86     }
87 
88     std::cout << "bye" << std::endl;
89     return 0;
90 }

其中Semaphore.h的代碼見：http://www.cnblogs.com/waterfall/p/7966116.html

運行結果截圖：

代碼解析：

簡單分析：

本問題也可以認為是生產者與消費者。只不過線程既生產又消費。按文件的角度，比如A文件的內容為1 2 3 4 1…… 相當於每個線程生產完之後交個下一個線程。

所以對於每一個線程，設置好其初始文件，調用自身信號量的wait()進行生產，生產完畢則調用下一個線程的signal()。將完成的文件交給下一個線程，形成流水作業。

啰里八嗦：

首先，本代碼用File類模擬文件寫入，方便列印調試。void File::write(char c) 方法即在文件結尾追加字元c。

根據題目要求可以看出，當文件（比如文件A）被線程1寫入結束後，需要被下一個線程即線程2寫入。因此會有A: 1 2 3 4 1... B，C，D文件同理，只不過初始寫入線程不同。

在代碼中利用：

unsigned currentFile[MAX_THREAD] = { 0, 1, 2, 3 }; //每個線程當前應該寫入的文件id

指定每個線程初始寫入哪個文件。如果不想配置也可以用threadId作為線程初始寫入的文件id（write函數中被註釋掉的那一句），他們剛好相等。

代碼中用信號量表示線程可執行寫入的次數。write函數會在寫入完一個文件後，自動計算下一個要寫入的文件。順序為A，D，C，B，A....，逆序。

Semaphore t1(1), t2(1), t3(1), t4(1); //用於設置信號量
Semaphore* semaphoreArray[MAX_THREAD] = { &t1, &t2, &t3, &t4 }; //放入數組只是為了方便調用

如果只是給線程1的信號量設為1，其他都設為0。線程的運行狀況可以看作：

step1: 線程1 信號量1 A->D　　線程2 信號量0 B 阻塞　　線程3 信號量0 C 阻塞　　線程4 信號量0 D 阻塞

step2: 線程1 信號量0 D 阻塞　　線程2 信號量1 B->A　　線程3 信號量0 C 阻塞　　線程4 信號量0 D 阻塞

step3: 線程1 信號量0 D 阻塞　　線程2 信號量0 A 阻塞　　線程3 信號量1 C->B　　線程4 信號量0 D 阻塞

step4: 線程1 信號量0 D 阻塞　　線程2 信號量0 A 阻塞　　線程3 信號量0 B 阻塞　　線程4 信號量1 D->C

第一輪運行結束：線程1在文件A中寫入了1，線程2在文件B中寫入了2，線程3在文件C中寫入了3，線程4在文件D中寫入了4。

之後第二輪開始：線程1在文件D中寫入了1，線程2在文件A中寫入了2……

以此類推，相當於同一時間只有1個線程在工作。每當線程工作時，將字元寫入自己當前要寫入的文件中，並計算出下一個要寫入的文件。

這種情況顯然是不會出現衝突的。

如果將線程1的初始信號量置為2：

step1: 線程1 信號量2 A->D　　線程2 信號量0 B 阻塞　　線程3 信號量0 C 阻塞　　線程4 信號量0 D 阻塞

step2: 線程1 信號量1 D->C　　線程1 信號量1 B->A　　線程3 信號量0 C 阻塞　　線程4 信號量0 D 阻塞

可以看出文件D中被寫入了字元1，出現錯誤。原因在於文件D當前期待被線程4寫入，在4寫入之前處於未就緒狀態。此時被任何其他線程寫入都是錯誤的。

如果假設線程1和線程4的初始信號量各為1，其他為0。且假設線程4先運行

step1.1: 線程1 信號量1 A 就緒線程2 信號量0 B 阻塞　　線程3 信號量0 C 阻塞　　線程4 信號量1 D->C

step1.2: 線程1 信號量2 A->D　　線程2 信號量0 B 阻塞　　線程3 信號量0 C 阻塞　　線程4 信號量0 C 阻塞

step2.1: 線程1 信號量1 D->C　　線程1 信號量1 B->A　　線程3 信號量0 C 阻塞　　線程4 信號量0 D 阻塞

文件D先被線程4寫入字元4，之後再被線程1寫入字元1便符合題目要求了。（D的序列應該為：4 1 2 3 4……)

也就是說，線程1的信號量的增加，是基於前一個線程已經完成文件寫入了。此時文件處於就緒狀態，可以被下一個線程使用，也即把文件傳遞給下一個線程。

所以最終的代碼中，將每一個線程的初始信號量設置為1。可滿足題目要求。哪怕任何線程在執行中出現阻塞（可用sleep模擬)，也不影響其他線程運行。

假設線上程1中執行一個長時間的sleep。可能的運行情況如下

step0: 線程1 信號量1 A 就緒線程2 信號量1 B 就緒　　線程3 信號量1 C 就緒　　線程4 信號量1 D 就緒

一段時間後……

step1:線程1 信號量4 A 就緒線程2 信號量0 A 阻塞　　線程3 信號量0 A 阻塞　　線程4 信號量0 A 阻塞

所有的線程都在等待將數據寫入文件A中。但只有線程1先在文件A中寫入字元1，之後釋放信號，B才能繼續寫入。之後是C，D。依然沒有衝突。文件A也滿足1，2，3，4的字元順序。

其他：

目前網上搜到的很多代碼，同一時間只允許一個線程進行文件的寫入，或者是通過計數，一輪結束後才進行下一輪寫入。本代碼真正實現了線程間的並行。只有無文件可寫時才會進行等待。

謝謝。