原本這篇不講執行緒，要直接跳到 OOP 多型的應用... 不過看一看 #3 自己寫的程式，實在有點看不下去... 30x30 的大小，程式跑起來就看到 903 條執行緒在那邊跑... 而看一下 CPU usage, 只有 5% 不到... 這實在不是很好看的實作範例，如果這是線上遊戲的 SERVER 程式，裡面的每個人，每個怪物等等都用一條專用的執行緒在控制他的行為的話，我看這遊戲不用太多人玩，SERVER 就掛掉了吧! 因此要繼續更貼近實際的生命模擬遊戲前，我們先來解決效能的問題，所以多安插了這篇進來 :D
前一篇 (#3) 的主題是把生命的進行，從被動的在固定時間被喚醒 (callback) 的作法，改成主動的在指定時間執行 (execute)。 想也知道，現實世界的生物都是 "主動" 的，後面的作法比較符合 OOP 的 "模擬世界，加以處理" 的精神。但是，一個小程式就吃掉 900 條執行緒，是有點過頭了。不知道還有沒有人記得，我騙到獎品的這個程式... 很另類的用 yield return 來解決類似問題的作法... 藉著 compiler 很雞婆的把單一流程翻成數段可以切開執行的邏輯...，正好拿來利用一下，替我們把一連串連續的邏輯切段，以便利用多執行緒來處理。我的想法是這樣，原程式是用個迴圈，作完該作的事，就休息 (sleep) 一段時間。而新的寫法，我打算用 yield return new TimeSpan(…) 來取代 Thread.Sleep(…)。每個 Cell內部的程式結構修改不大，不過對於 GameHost 就是個挑戰了... 來看看修改前及修改後的程式碼:
用 yield return TimeSpan 來取代 Thread.Sleep( ) 的作法[copy code] // 修改前
// 使用 Thread.Sleep( ) 來控制時間
public void WholeLife(object state)
{
int generation = (int)state;
for (int index = 0; index < generation; index++)
{
this.OnNextStateChange();
Thread.Sleep(_rnd.Next(950, 1050));
}
}
//
//
//
// 修改後
// 使用 yield return new TimeSpan( ) 來控制時間
public IEnumerable<TimeSpan> WholeLife(object state)
{
int generation = (int)state;
for (int index = 0; index < generation; index++)
{
this.OnNextStateChange();
yield return TimeSpan.FromMilliseconds(_rnd.Next(950, 1050));
}
yield break;
}
1: // 修改前
2: // 使用 Thread.Sleep( ) 來控制時間
3: public void WholeLife(object state)
4: {
5: int generation = (int)state;
6: for (int index = 0; index < generation; index++)
7: {
8: this.OnNextStateChange();
9: Thread.Sleep(_rnd.Next(950, 1050));
10: }
11: }
12: //
13: //
14: //
15: // 修改後
16: // 使用 yield return new TimeSpan( ) 來控制時間
17: public IEnumerable<TimeSpan> WholeLife(object state)
18: {
19: int generation = (int)state;
20: for (int index = 0; index < generation; index++)
21: {
22: this.OnNextStateChange();
23: yield return TimeSpan.FromMilliseconds(_rnd.Next(950, 1050));
24: }
25: yield break;
26: }
別想的太美，只改這樣，程式是不會動的... 修改過之後，麻煩的地方會在 GameHost. 因為整個 GameHost 的邏輯都反過來了。原本是 GameHost 只要放著那九百條執行緒自生自滅，它只要不斷的刷新畫面就好了。現在它則得用 foreach(…) 去詢問:
"大爺，這次您要休息多久?"
接到 yield return 傳回的 TimeSpan 物件 (代表它要休息多久後，繼續下一個動作) 後，經過這段時間，GameHost 就要再去叫醒 cell, 然後再詢問一次:
"大爺，這次您要休息多久?"
關鍵就在於 GameHost 如何能透過少量的 thread 來伺後這些大爺，而不是像 #3 的程式一樣，每個大爺都用一條專屬的 thread… 要共用執行緒，就要先想辦法把工作切碎，這是基本法則。如果你希望你的生命遊戲程式不只是作業的話，那麼效能跟即時回應的問題是必需要考慮的。在動手改寫 GameHost 程式之前，先來分析一下改寫的目標有那些:
目標是要達到像 #2 範例一樣的效果，但是要用更有效率的方式。
目標很清楚，再來就看看有什麼手段可以用了。第一個是過量的執行緒，應該要想辦法改用執行緒集區。因為 #2 用了高達 900 條執行緒，不過整體 CPU USAGE 不到 5%，大部份的執行緒都在閒置狀態。如果能想辦法把這些運算丟到執行緒集區，由集區動態管理會有效率的多。
第二，就是把原本的 Thread.Sleep(ts) 改成 yield return ts 後，原本每個 thread 自己睡覺的機制，就要改成 cell 各自回報 game host 它想要睡多久，然後由 game host 統一在時間到時叫醒它。由於一次有多個 cell 同時在運作，因此我們需要一個簡單的排程器，作法像這樣:
- 建立一個時間表，依照時間順序，把每個 cell 預計要被叫醒的時間標上去。
- 時間到了之後，就去呼叫該 cell 的 OnNextStateChangeEx()，同時取得該 cell 下次要喚醒的時間，再標到時間表上
- GameHost就不斷的替每個 cell 重複 (1) (2) 的動作..
- 同時另外用一條獨立的執行緒，作畫面更新的動作。
嗯，要處理的方式越來越清楚了。剩下的是 "時間表" 要用什麼型式來表現? 我的選擇是，我希望它是個 ToDo List, 會幫我排好時間，我只要把工作標上時間，丟進 ToDo List, 然後 ToDo List 只要能忠實的回報給我還有沒有排定的工作? 如果有，下一個要處理的工作是那一個? 什麼時後處理?
它的用法只有丟工作進去，跟拿工作出來，因此我設計它的公開介面長這個樣子:
CellToDoList 的類別設計[copy code]
public class CellToDoList
{
public void AddCell(Cell cell) {...}
public Cell GetNextCell() {...}
public Cell CheckNextCell() {...}
public int Count {get;}
}
1: public class CellToDoList
2: {
3: public void AddCell(Cell cell) {...}
4: public Cell GetNextCell() {...}
5: public Cell CheckNextCell() {...}
6: public int Count {get;}
7: }
裡面的實作，我就不多說了。我是把它當成 QUEUE 在設計，唯一的差別是，放進 QUEUE 的東西會先經過排序，因此不見得是 "First In First Out" 這種典型的貯列，而是會以 Cell 上標示的時間為準，依序 Out …。實作起來很簡單，用現成的 SortedList 當內部的儲存方式，加上基本的 lock 機制來確保它是 thread safe 的就夠了。
好，這些雞絲都準備好之後，就可以來打造我們的新版 GameHost 了。來看看 Code:
改用 ThreadPool / CellToDoList 的新版 GameHost:[copy code]
static CellToDoList _cq;
static void _YieldReturnGameHost(string[] args)
{
int worldSizeX = 30;
int worldSizeY = 30;
World realworld = new World(worldSizeX, worldSizeY);
_cq = new CellToDoList();
// init threads for each cell
for (int positionX = 0; positionX < worldSizeX; positionX++)
{
for (int positionY = 0; positionY < worldSizeY; positionY++)
{
Cell cell = realworld.GetCell(positionX, positionY);
cell.OnNextStateChangeEx();
_cq.AddCell(cell);
}
}
// 啟動定期更新畫面的執行緒
Thread t = new Thread(RefreshScreen);
t.Start(realworld);
while (_cq.Count > 0)
{
Cell item = _cq.GetNextCell();
if (item.NextWakeUpTime > DateTime.Now)
{
// 時間還沒到，發呆一下等到時間到為止
Thread.Sleep(item.NextWakeUpTime - DateTime.Now);
}
ThreadPool.QueueUserWorkItem(RunCellNextStateChange, item);
}
}
private static void RunCellNextStateChange(object state)
{
Cell item = state as Cell;
TimeSpan? ts = item.OnNextStateChangeEx();
if (ts != null) _cq.AddCell(item);
}
private static void RefreshScreen(object state)
{
while (true)
{
Thread.Sleep(500);
(state as World).ShowMaps("");
}
}
1: static CellToDoList _cq;
2: static void _YieldReturnGameHost(string[] args)
3: {
4: int worldSizeX = 30;
5: int worldSizeY = 30;
6: World realworld = new World(worldSizeX, worldSizeY);
7: _cq = new CellToDoList();
8: // init threads for each cell
9: for (int positionX = 0; positionX < worldSizeX; positionX++)
10: {
11: for (int positionY = 0; positionY < worldSizeY; positionY++)
12: {
13: Cell cell = realworld.GetCell(positionX, positionY);
14: cell.OnNextStateChangeEx();
15: _cq.AddCell(cell);
16: }
17: }
18: // 啟動定期更新畫面的執行緒
19: Thread t = new Thread(RefreshScreen);
20: t.Start(realworld);
21: while (_cq.Count > 0)
22: {
23: Cell item = _cq.GetNextCell();
24: if (item.NextWakeUpTime > DateTime.Now)
25: {
26: // 時間還沒到，發呆一下等到時間到為止
27: Thread.Sleep(item.NextWakeUpTime - DateTime.Now);
28: }
29: ThreadPool.QueueUserWorkItem(RunCellNextStateChange, item);
30: }
31: }
32: private static void RunCellNextStateChange(object state)
33: {
34: Cell item = state as Cell;
35: TimeSpan? ts = item.OnNextStateChangeEx();
36: if (ts != null) _cq.AddCell(item);
37: }
38: private static void RefreshScreen(object state)
39: {
40: while (true)
41: {
42: Thread.Sleep(500);
43: (state as World).ShowMaps("");
44: }
45: }
GameHost 的工作很明確，一開始 (line 18 ~ 20) 就把更新畫面的動作完全交給另一個執行緒，之後就專心處理 ToDoList 內的工作了。
接著後面的 while loop (line 21 ~ 30) 則是很單純的從 ToDoList 裡取出下一個要要動作的 Cell, 如果時間還沒到就 Sleep 等一下它。執行完後會再詢問下一次是什麼時後，同時再把他加到 ToDoList 內等待下一次輪到他時繼續。
這次的程式我沒有設定停止的條件，因此你會看到程式會不斷的執行下去。程式執行起來，結果跟 #3 沒什麼不同，畫面上的每個細胞會照著題目的規則生長或死亡，不同的是 #3 的 Game Host 需要用到 903 條執行緒，而這版的 Game Host 只要 9 條執行緒...
其實，以這樣的範例題，我大可以不用顧慮到效能的問題，不過就是示範程式怎麼寫嘛。不過，我的目標如果只是訂在怎麼寫這練習題，大可以 GOOGLE 一下就有一堆作業解答了 :D。我的目標是要展示一下，該如何開發這樣的 GameHost ? 這樣的程式，是大部份的遊戲的基礎，尤其是像線上遊戲或是 facebook 這類互動遊戲的基礎。有了像樣的 Game Host 之後，接下來就把目標放在如何建立多樣的生物，一起放在這世界裡面生活了。接下來就會大量運用到 OOP 的特點 (對，就是上一篇預告的...) 繼承及多型。
有沒有人覺的，這種程式越寫越像 Matrix (就是駭客任務裡的 "母體") 了? 裡面活著的東西其實都在我的掌控之下... =_= 哈哈... 未完待續，請期待續集 :D。
--
範例程式:
Subscribe