疑似Google多線程面試題的Java實現 – JAVA編程語言程序開發技術文章

來到一個完全陌生的地方,即將一切從新開始,內心興奮又忐忑。這幾天忙著租房,裝寬帶直到今天才算告一段落,幾經折騰,總算能安靜的寫寫東西瞭。對我而言排解緊張情緒和壓力的方式,就是投入一個問題的思考和解決中。之前在網上找相關的多線程問題,想通過演練來加深和熟練對多線程的掌握時,看到一個疑似Google的多線程面試題,感覺可以思考一下,題目如下:
    啟動4個線程,向4個文件A,B,C,D裡寫入數據,每個線程隻能寫一個值。
    線程1:隻寫1
    線程2:隻寫2
    線程3:隻寫3
    線程4:隻寫4
    4個文件A,B,C,D。
    程序運行起來,4個文件的寫入結果如下:
    A:12341234…
    B:23412341…
    C:34123412…
    D:41234123…
   
    這個題目主要是要解決線程調度的問題,可能原來是要求C/C++多線程的實現,不過語言不是問題的關鍵,我嘗試用Java浩瀚的API堆瞭一個實現。先簡單的說說思路,分析知有三個對象是必須的:線程對象,文件對象以及共享協調對象。線程對象不用多說瞭,擴展Thread,為其提供一個唯一的綁定值;文件對象可以使用虛擬文件先代替,反正寫入文件和寫入對象存儲大同小異;最後就是負責調度線程寫入文件的共享協調對象,這個對象的職責就是保證線程安全並且提供多線程正確寫入數值到文件的方法。我能想到的方式有兩種:一個是控制線程順序依次寫入文件,顯然這種方式難度較大,畢竟線程之間的執行順序很難保證;另一種就是線程競爭寫入權,共享協調對象向獲得寫入權限的線程提供符合條件的文件寫入。後者不用控制線程的執行順序,並且各個線程完全相對獨立,故而我采用瞭後面得方案進行實現:
Java代碼    
1. import java.io.File;  
2. import java.io.FileWriter;  
3. import java.io.IOException;  
4. import java.io.PrintWriter;  
5. import java.util.ArrayList;  
6. import java.util.Collections;  
7. import java.util.Comparator;  
8. import java.util.List;  
9. import java.util.concurrent.CountDownLatch;  
10.  
11. /** 
12.  * @author: yanxuxin 
13.  * @date: 2010-2-18 
14.  */ 
15. public class MultiThreadWriter {  
16.  
17.     public static String[] FILE_NAMES = { "A", "B", "C", "D" };  
18.  
19.     /** 文件路徑 */ 
20.     public static String FILE_PATH = "D:" + File.separator;  
21.  
22.     private final List<MockOutput> outList = new ArrayList<MockOutput>(FILE_NAMES.length);  
23.  
24.     /** 平衡優先級的比較器 */ 
25.     private final Comparator<MockOutput> comparator = new PriorityComparator();  
26.  
27.     /** 線程運行開關 */ 
28.     private volatile boolean working = true;  
29.  
30.     public static void main(String[] args) {  
31.         final MultiThreadWriter writer = new MultiThreadWriter();  
32.         final CountDownLatch start = new CountDownLatch(1); // 發令信號  
33.         final CountDownLatch end = new CountDownLatch(64); // 終止信號  
34.  
35.         for (int i = 0; i < FILE_NAMES.length; i++) {  
36.             writer.new WriteWorker(writer, i + 1, start, end).start(); // 開啟4個線程,每個線程分別隻寫入單一值  
37.         }  
38.  
39.         start.countDown(); // 熟悉的開閘放狗  
40.  
41.         try {  
42.             end.await(); // 等待其他子線程工作  
43.         }  
44.         catch (InterruptedException e) {  
45.             e.printStackTrace();  
46.         }  
47.  
48.         writer.cleanAndDisplay(); // 計數為0時,打印最後一次調整瞭存儲順序的StringBuilder的值  
49.     }  
50.  
51.     public MultiThreadWriter() {  
52.         try {  
53.             init();  
54.         }  
55.         catch (IOException e) {  
56.             e.printStackTrace();  
57.         }  
58.     }  
59.  
60.     public boolean isWorking() {  
61.         return working;  
62.     }  
63.  
64.     /** 
65.      * 供子線程調用並寫入線程綁定的數值給文件和StringBuilder 
66.      *  
67.      * @param num 
68.      * @return 
69.      */ 
70.     public boolean writeToOutput(int num) {  
71.         synchronized (outList) {  
72.             for (int i = 0; i < FILE_NAMES.length; i++) {  
73.                 MockOutput output = outList.get(i);  
74.  
75.                 int lastest = output.getTheLatestNum();  
76.                 if ((lastest % FILE_NAMES.length) + 1 == num) { // 取此output最後一次寫入的值,判斷是否滿足再次寫入  
77.                     output.append(num);  
78.                     output.setTheLatestNum(num);  
79.  
80.                     adjustPriority(); // 調整outList中各MockOutput實例的順序  
81.  
82.                     return true;  
83.                 }  
84.             }  
85.         }  
86.         return false;  
87.     }  
88.  
89.     public void cleanAndDisplay() {  
90.         working = false;  
91.         synchronized (outList) {  
92.             for (int i = 0; i < FILE_NAMES.length; i++) {  
93.                 MockOutput out = outList.get(i);  
94.                 out.close();  
95.  
96.                 System.out.println(out.toString());  
97.             }  
98.         }  
99.     }  
100.  
101.     /** 
102.      * 初始化每個MockOutput實例的最後一次寫入值,並把其加入到outList中 
103.      * @throws IOException 
104.      */ 
105.     private void init() throws IOException {  
106.         for (int i = 0; i < FILE_NAMES.length; i++) {  
107.             MockOutput output = new MockOutput(64, FILE_NAMES[i], FILE_PATH);  
108.             output.setTheLatestNum(i);  
109.             outList.add(output);  
110.         }  
111.     }  
112.  
113.     /** 
114.      * 使用Comparator的自身實現對outList內的對象進行排序,其作用在於平衡寫入優先級. 
115.      *  例如:線程Thread-2取得瞭outList對象的鎖執行寫入,其綁定的值為3,而outList中 
116.      *  有兩個MockOutput實例的最後一次寫入都為2,均滿足再次寫入的條件.但是其中一個的長度 
117.      *  遠遠大於另一個,並且其在outList內的位置又在另一個之前,則其將先於後者獲得再次寫  
118.      *  入得機會,使得兩者的機會不均衡. 
119.      * 此方法的作用就在於把寫入機會少的MockOutput調整到最前面從而提高其被寫入的機會. 
120.      */ 
121.     private void adjustPriority() {  
122.         Collections.sort(outList, comparator);  
123.     }  
124.  
125.     private class WriteWorker extends Thread {  
126.  
127.         /** 多個線程共享同一個MultiThreadWriter實例 */ 
128.         private MultiThreadWriter writer;  
129.  
130.         /** 線程綁定的寫入值,每個線程隻反復寫入一個固定值 */ 
131.         private final int num;  
132.  
133.         private final CountDownLatch start;  
134.         private final CountDownLatch end;  
135.  
136.         public WriteWorker(MultiThreadWriter writer, int num, CountDownLatch start, CountDownLatch end) {  
137.             this.writer = writer;  
138.             this.num = num;  
139.             this.start = start;  
140.             this.end = end;  
141.         }  
142.  
143.         public void run() {  
144.             try {  
145.                 start.await();// 等待主線程一聲令下,所有的子線程均喚醒開始工作  
146.                 doWork();  
147.             }  
148.             catch (InterruptedException e) {  
149.                 e.printStackTrace();  
150.             }  
151.         }  
152.  
153.         /** 
154.          * 子線程寫入固定值,寫入成功則遞減計數器www.aiwalls.com 
155.          *  
156.          * @throws InterruptedException 
157.          */ 
158.         private void doWork() throws InterruptedException {  
159.             while (writer.isWorking()) {  
160.                 boolean isWrited = writer.writeToOutput(num);  
161.                 if (isWrited) {  
162.                     end.countDown();  
163.                     Thread.sleep(50); // 調整線程競爭,使得每個線程獲取outList鎖的幾率均衡  
164.                 }  
165.             }  
166.         }  
167.     }  
168.  
169.     private class MockOutput {  
170.  
171.         /** 用於終端顯示的記錄 */ 
172.         private final StringBuilder stringBuilder;  
173.  
174.         /** 需要寫入的文本輸出 */ 
175.         private final PrintWriter printWriter;  
176.  
177.         /** 文件名 */ 
178.         private final String name;  
179.  
180.         /** 最後一次寫入的值 */ 
181.         private int theLatestNum;  
182.  
183.         /** 優先級因子,值越大優先級越低 */ 
184.         private int priorityFactor = 0;  
185.  
186.         public MockOutput(int capacity, String name, String path) throws IOException {  
187.             this.stringBuilder = new StringBuilder(capacity);  
188.             this.name = name;  
189.             this.printWriter = new PrintWriter(new FileWriter(path + name + ".txt"));  
190.         }  
191.  
192.         public int getTheLatestNum() {  
193.             return theLatestNum;  
194.         }  
195.  
196.         public void setTheLatestNum(int theLatestNum) {  
197.             this.theLatestNum = theLatestNum;  
198.         }  
199.  
200.         public int getPriorityFactor() {  
201.             return priorityFactor;  
202.         }  
203.  
204.         /** 
205.          * 遞增優先級因子的值,降低寫入優先級 
206.          */ 
207.         private void reducePriority() {  
208.             priorityFactor++;  
209.         }  
210.  
211.         /** 
212.          * 寫入操作 
213.          *  
214.          * @param i 
215.          * @return 
216.          */ 
217.         public MockOutput append(int i) {  
218.             stringBuilder.append(i);  
219.             printWriter.print(i);  
220.             reducePriority();  
221.             return this;  
222.         }  
223.  
224.         /** 
225.          * 關閉文本輸出 
226.          */ 
227.         public void close() {  
228.             printWriter.close();  
229.         }  
230.  
231.         public String toString() {  
232.             return name + ": " + stringBuilder.toString();  
233.         }  
234.     }  
235.  
236.     /** 
237.      * 用於平衡寫入優先級的比較器 
238.      *  
239.      * @author: yanxuxin 
240.      * @date: 2010-2-24 
241.      */ 
242.     private class PriorityComparator implements Comparator<MockOutput> {  
243.  
244.         @Override 
245.         public int compare(MockOutput o1, MockOutput o2) {  
246.             int pf1 = o1.getPriorityFactor();  
247.             int pf2 = o2.getPriorityFactor();  
248.             return pf1 – pf2;  
249.         }  
250.  
251.     }  
252.  
253. } 

    這個實現中,虛擬文件對象MockOutput的theLatestNum屬性記錄每個實例最後一次寫入的值,由於每個線程僅僅寫入一個固定的值,所以一旦得到文件最後一次寫入的值就可以判斷此文件是否符合線程寫入的條件。另外起初我僅僅是使用StringBuilder記錄寫入的值,PrintWriter是重構時加入的,所以兩者都保留瞭。WriteWorker既是寫入線程,其循環檢測共享協調對象MultiThreadWriter的working的最新值是否為true,從而調用MultiThreadWriter的writeToOutput(int)去寫文件。最初的版本並沒有PriorityComparator這個比較器也保證瞭程序的正常工作。但是輸出的結果形如:
  A:1234123412341234…
  B:23412341234…
  C:341234…
  D:4123…
之所以出現這樣的不協調的結果是因為我使用List存儲MockOutput是有序的,所以取值時如果排在前面的和排在後面的均滿足寫入的話,顯然排名靠前的搶瞭被寫入的機會,貧富差距拉大。不過現實雖然我改變不瞭,程序我還是能主宰的。所以重構時我加入瞭PriorityComparator這個比較器,在每次寫入完畢時調用adjustPriority()使用比較器把機會少的調整到前面均衡一下,這樣最終寫入的幾率基本上能相差無幾。

    這個實現其實基本上就是API的堆砌,沒有什麼自我實現的算法,如果以後有好的思路我會再次重構的。如果寫程序能不用考慮吃飯,生活該多好啊…新的一年祝願Developers諸事順利,我也要好好地準備一下瞭。為瞭興趣,為瞭生活,Wish I Can…
 

摘自  code dream 

發佈留言