快快樂樂學遊戲Threading程式設計

這是我在近期內對於 Threading 主題的學習整理文。如果你對於多執行緒程式設計沒有半點概念的話,建議可以先從我之前寫的「多核多緒多樂趣」開始閱讀,然後再視個人需求取用以下各項資源。

所謂的「多執行緒」程式設計,或者可簡稱為「多緒」程式設計,在英文中有許多相關的專業技術名詞,例如 Threading、Multithread、Concurrency、Parallel、Multicore 與 Multiprocessor 等等,在搜尋資料時可以嘗試不同的關鍵字,往往可以找到不少意料之外的好東西。而其中最常見的總括性簡稱,應該就是 Threading 了。

基礎定義

既然要學習 Threading 程式設計的知識,首先要瞭解的當然是 Threading 的基礎概念:

  • Thread:看看 Wikipedia 裡的定義,至少把最前頭那段 Thread 的基本定義,以及 Thread 與 Process 的不同之處搞懂。簡單來說,執行緒是用來執行電腦程式的執行環境;而多執行緒,就是能夠使程式系統同時執行多個不同程式碼區段的一種技術。
  • Thread Safety:雖然使用 Threading 技術能夠提升程式系統的執行效能,但伴隨而來的則是麻煩又難解的 Thread Safety 議題。大致上,我們可以使用 Re-entrancy、Mutual exclusion、Thread-local storage 以及 Atomic operations 這四種方法來達成安全使用多執行緒技術的目標。

教學文章

  • C++ Multithreading Tutorial @ paulbridger.net:質量非常不錯的基礎教學文章,從 Race Condition、Mutex、Deadlock 到 Condition Variables 等等重要的基本概念,都有清楚易懂的文章教學與程式碼範例。
  • Multithreading Tutorial @ Homepage of Mario Konrad:網站裡分成基礎、中間與進階三種等級的教學文章,可以看看 Socket 網路程式與 Producer-Consumer 的程式碼,應該會更加瞭解多執行緒技術的可運用之處。

跨平台函式庫

  • Boost.Thread(連結為 1.38 版):簡單易用且功能完備的跨平台函式庫。如果沒有使用過 Boost C++ Libraries,可以參照這篇文章的步驟來建置 Boost.Thread 函式庫。
  • threadpool:以 Boost.Thread 為基礎,實做出一個非常好用的 Thread Pool 設計模式。

名家專區

  • Intel: Parallel Programming and Multi-Core:因為 Intel 的本業是靠 CPU 吃飯的,所以自然相當注重多執行緒程式設計的議題,在這裡可以挖到不少質量兼具的優秀文章。
  • MSDN: Parallel Computing:MSDN 中的平行計算處理專區,充滿文章、影片以及部落格等相關資源。
  • DevX.com: Move to the Future with Multicore Code:有幾篇不錯的概念性文章,另外還有介紹如何使用 .NET 平台的 Task Parallel Library。
  • Sutter’s Mill:Herb Sutter 大師的個人部落格。目前在 DDJ 雜誌上,有他每個月固定連載的 Effective Concurrency 專欄文章,適合進階高手服用。

投影片

微軟於 2007 年與 2008 時所舉辦的 Gamefest 開發者會議,其中有許多關於 Threading 的演講主題,內容非常豐富多樣且紮實,而且大部分課程都有投影片與錄音檔可供下載:

推薦文章

書籍文章

關於書籍中的文章,我推薦《Game Programming Gems 7》中的「Design and Implementation of a Multi-Platform Threading Engine」與「Multithread Job and Dependency System」這兩篇文章。前者實作出了一個可跨平台的 Threading 引擎架構,後者則著重於更加複雜的任務相依系統上,兩篇文章各有擅場,而且都有完整的程式源碼可供讀者仔細研究!

如果有其他關於遊戲 Threading 程式設計的資源,隨時歡迎各位的回應與補充喔~ :D

23 thoughts on “快快樂樂學遊戲Threading程式設計”

  1. 因為在嵌入式上工作,一直沒有遇到真正的多核。但有準備寫多核心程式。
    最近又發現多了一項和多核心不太相同的平行處理技術:GPGPU。原以為教科書中的SIMD架構沒有機會用到,原來早就在用了。
    多核心+GPGPU會使影像處理能力大增。看來影像處理的應用會更加普遍。

  2. 說個題外話:)
    為什么每次訪問的時候瀏覽器響應速度特別慢?不論firefox還是ie8,ie7到沒試過
    而且在firefox下經常提示http://blog.monkeypotion.net/tw_cn.js:106這個腳本未響應。。。

  3. @Wallace:
    GPGPU 與相關的 CUDA 語言,都是相當具有發展潛力的新技術。繪圖顯示卡的急速發展,已經可以讓程式設計者利用它來處理更多 3D 繪圖以外的工作了。

    @路人甲:
    你好,

    tw_cn.js 這個檔案是用來轉換簡繁字體的腳本,可能因為內容猴子靈藥中的文字過多,所以在轉換程序時會比較緩慢。目前我沒有找到其他更好的簡繁字體互換方法,所以只好暫時使用 tw_cn.js 腳本,還請多多見諒。 ^^a

  4. To wallace,
    CUDA還沒出之前, 就很多人用cg來對image processing做平行處理
    例如GpuCV。
    CUDA雖然平行能力強, 但受限於GPU的天性, 依然沒辦法處理太多logic的程式碼,
    跟multithread有層次上的差別。另外一項限制就是匯流排的速度, 資料往返memory和GPU比CPU還花時間, 因此, 比如4×4的矩陣乘法, 就不可能送去GPU再拿回來,花是commit資料到GPU就可能比64個浮點數乘法慢, 這時,SIMD就是優勢。
    結論是由平行化的層次來看, high level =>Multithread, Medium level => GPU or CUDA, low level => SIMD

  5. 我查了GpuCV,有件事很怪。它並沒有比CUDA早很多出現。因為用Google找出的資料很少。
    OpenCV是最早出的,它是基於CPU的運算,但對於影像處理的演算法提供開源碼。因為CUDA及OpenCV皆使用C語言,所以很快的產生OpenCV+CUDA,反而是它被使用的機會多。
    不過OpenCV是Intel支持的,和nVidia是不合的,要OpenCV公開支持是CUDA是不太可能。
    不過Alvin舉的例子不完整。以4*4矩陣運算來說確實是CPU勝出,因為要GPU運算目前一定要花費傳輸時間,資料不夠多,沒傳完CPU就已算完了。
    但GPU內通常有許多暫存器,暫存器有達8K bytes,若是矩陣運算能利用,就會快很多。
    所以GPU對付矩陣一次運算多以8*8或16*16的部分矩陣來運算,再合併為大矩陣。對於大型矩陣運算,要達每秒數百G浮點運算是很容易的。
    因為3D遊戲一定要對付大量的座標運算,沒有達G級的運算力,那GPU還能玩得下去嗎?
    所以3D顯示卡的記憶體容量會影響運算能力,因為如果能將要大量運算的資料一次載入VRAM中,那傳輸的時間比例將會下降,那數百G的浮點運算力就可以展現出來。
    至於SIMD,有硬體是一定最快的。但是硬體要錢,目前能做的常用SIMD就矩陣運算、FFT、Convolution等。這原本為DSP的領域,只是GPU目前也想攻這塊了。

  6. To Wallace:
    Alvin舉的”4*4矩陣運算”的確不完整, 我嘗試幫他說明一下(其實也是我的看法)- 他想表達的是muti-processor系統的缺點, 在於記憶體/bus通訊上. 避免經常性的將資料在chip間(cpu-gpu)傳遞. 解決辦法1.在程式設計上避免 2.請intel跟nVidia把cpu-gpu整合在一起–雖然這是不太可能的事情. 在嵌入式處理器系統的世界裡, TI的dsp與ARM的cpu整合老早就開始了.
    至於Wallace提到的”GPU內通常有許多暫存器,暫存器有達8K bytes”, 這方面可能要比較一下gpu的硬體架構(例如gpu內的”thread”與一般在cpu上跑的thread,也是本篇提到的, 應該是不同的定義), 或是cpu對於register的處理速度是否相同, 才能進行討, 否則只是名詞一樣但定義不同, 在討論時可能會造成困惑吧. — 可能會越扯越遠就是了.

  7. GPU使用大量暫存器,其原因是缺乏cache。可是它的register file的方式又有點像軟體管理的cache。
    Thread也和一般CPU不大一樣,一般CPU會有一整組的register。記錄程式運算的狀態。
    GPU的Thread只是SIMD單一指令下的thread,要所有的thread皆執行完成,才會整個開始執行下一個指令,nVidia稱為SIMT。
    在學CUDA時,這些硬體上的架構不同於一般CPU,確實給純軟體的人不容易接受。

  8. @Wallace & Hua:
    看完你們的討論,我又更加認識了 CPU 和 GPU 的種種優勢劣勢。

    我想不論是 CPU 或 GPU,平行處理都是未來十年的發展重點。CPU 已經開始很久了,而 GPU 才正要起步而已;另外不只是 GPU 想要搶 CPU 的飯碗(運算能力),CPU 開發商也一樣試圖要跨界發展(Larrabee)。

    回到程式設計者的角度來看,使用 C/C++ 語言來撰寫平行處理的程式系統,其實是一件非常辛苦且易於出錯的事情。我們是否需要更新更合適的程式語言?

    硬體加上軟體的發展潛力,我相信未來一定會非常有趣。 ^^

  9. 「我們是否需要更新更合適的程式語言?」
    我的答案:不需要。需要平行處理大部分是因為blocking IO,要靠平行處理提升速率的情況很少,如果用multi thread發現很困難,就該檢討這個專案也許不適合做成multi thread,你只是為了炫耀技術力而使用
    同步問題通常一個flag變數就可以搞定,簡單的情況下用mutex等功能反而把事情複雜化
    我寫multi thread程式也沒在看什麼資料,一切以底層指令集和stack的角度去想就輕鬆解決了

    另外C是按照系統底層設計的語言(不包括C++一堆擴充的部分),多數作業系統也是用C設計的,用C可以得到最直接、最廣泛的控制能力
    一些高階語言不但不夠直接,而且常有莫名其妙的問題(例如文字編碼),再說解譯器的底層還是C和ASM在運作
    只要是intel based CPU,C和intel based assembly就是程式語言的首選

    最現實的一點:太新的技術還要考慮不是所有人的電腦都能用的問題

  10. 「我們是否需要更新更合適的程式語言?」– 對”multi thread”而言, Erlang就是一種新的語言.

    任一領域都可能有更適合的語言- “特定領域語言” (Domain-Specific Language,DSL). 底層當然是用機械碼控制, 然而為什麼還會出現C/C++/Java/Perl/Python/PHP…等等, 甚至還有Erlang的產生, “目的是創造一種可以應對大規模併發活動的編程語言和運行環境”-wiki. (至於適不適合每個人/環境就是case by case了)
    程式語言一方面做為與機器溝通的工具(成為機械碼/bytecode之後), 另一方面也是軟體工程師思想的表達方式, 所考慮的不只是執行效能, 還有維護(10行code理論上是比1000行code好看懂)等等.

  11. ps.我不是指Java/Perl/Python是DSL, 而是說不只有C的存在, 其他語言都各有擅長的領域. PHP應該才算是DSL.

  12. 這篇的主題是threading而不是程式語言

    我看過multi thread大部分是處理blocking IO,為了執行速率而用multi thread的很少,一個thread就可以跑的程式沒有必要硬要做成多thread
    如果用multi thread覺得很困難,就得想想這部分是真的需要multi thread,還是只是炫耀技術而用(在另一個地方講過類似的話)
    Erlang的資料我看過一些,我是覺得實用價值不大,等遇到以Erlang設計的CPU再說吧
    另外我用C API做multi threading沒碰過什麼困難,不太了解別人會遇到什麼問題

    Java/Perl/Python處理threading用的是跟作業系統底層API類似的機制,在threading方面可視為與C同類,當然高興的話可以做個類似Erlang的API

  13. To Shark:

    “我用C API做multi threading沒碰過什麼困難,不太了解別人會遇到什麼問題”, 這可能要請半路大大分享一下他遇到了什麼問題-“使用 C/C++ 語言來撰寫平行處理的程式系統,其實是一件非常辛苦且易於出錯的事情”. 每個人遇到的問題不同, 感受到的難度也不相同.

    關於”Erlang的實用價值”, 我想它在”處理blocking IO”應該是英雄無用武之地, 你可以在google搜尋”Erlang 多核”, 應該可以感受到它在多核上的價值. (雖然我覺得它著重在程式語言的表達能力上, 而不是多緒在多核上, 更有效率的排程)
    至於”Erlang設計的CPU”? Java/Perl/Python/Erlang都是基於VM上的語言, 將VM實做成cpu不會是個好點子.

  14. 更正, ”Erlang設計的CPU”應該是可能的, 即是在cpu架構下加入Erlang(VM)解譯加速器.

  15. 我也是有研究一下Erlang。用它來架伺服器有一個別的語言無法做到的特性:程式熱抽換。
    也就是說當別的語言做的遊戲伺服器因要升級或加入新的關卡,需要停機時。Erlang做的遊戲伺服器是不需要停機就可以做更新。
    不用因停機將正在玩的使用者”踢出來”,這件事本身就有市場。而傳統語言不好做,那就是新語言會存在的地方。
    伺服器本身就是multi threading最好表現的地方。所以可以看看架伺服器用的語言,都是支援multi threading。
    我想未來遊戲伺服器也會是遊戲發展重點之一,故multi threading是很重要的技術。

  16. @Shark, Hua & Wallace:
    這裡我僅就 Threading 於「遊戲程式」的應用層面,提出一些我的看法:

    就我所知,以前的多執行緒系統,的確是多半用於解決 I/O 阻塞的問題。因為以前的 CPU 只有單個核心,如果將遊戲系統分成多個執行緒,目的通常在於提供更好的反應性 (responsiveness),而不是為了得到提升效能 (performance) 的成果。

    然而,當現在多核心 CPU(甚至 GPU)已成為必然之路時,我們確實能夠利用多核硬體的威力進一步提升遊戲系統的效能,或者加入更複雜真實的模擬運算,例如人工智慧或物理引擎等等。

    理想中,在多核心的系統架構下,我們可以將主程式的運作流程分配在一個核心,繪圖運算交給另一個核心、物理運算交給第三個核心、人工智慧運算再交給第四個核心等等以此類推。但是現實世界總無法過得如此輕鬆寫意。光是要處理核心與核心之間的資料交換與資料同步程序,就會使得原來簡明的程式碼架構,變得非常龐大交錯。

    C/C++ 是屬於一種命令式 (imperative) 的程式語言,並不是不能夠用來撰寫多執行緒的程式系統,但是如 C/C++ 般以程序為基礎 (procedural-based),依序執行的結構式程式語言,與多執行緒「平行並進」的自然法則實在有所違背。就我目前的經驗來說,當多執行緒程式系統越趨於複雜,使用 C/C++ 只會越顯吃力不討好。目前我還沒有機會接觸 Erlang,但我不會排斥它,或許某天,真的能夠將 Erlang 運用於遊戲程式系統中呢。

    應用 Threading 於遊戲程式的潛在問題及有待解決的議題,在本文連結中的投影片和推薦文章都有更詳盡的闡述,不妨參考看看~

    謝謝三位的分享及討論。 ^^

  17. 您好,
    文中提及以 Boost.Thread 為基礎的 threadpool 函式庫,在 Windows 平台上測試過後發現會有 Memory Leak 跟 Handle 沒關閉的問題。
    看了一下原作者網頁一直停在 2007 年釋出的 0.2.5 版,之後就再也沒更新過了。
    請問有其他推薦不錯的 threadpool 函式庫嗎? :(

    Boost 怎麼不出個 Boost.ThreadPool 呢,真是的…

  18. @West:
    你好,

    原來 threadpool 有記憶體漏洞的問題啊… Orz

    由於我只是將 threadpool 使用在工作之外的實驗專案上,所以沒有特別去注意記憶體的問題。目前我也只有看到這個 thread pool 的函式庫是 open source 的授權,很遺憾看起來原作者已經沒有繼續開發維護了。我想,應該可以參照 threadpool 源碼,以及 Boost.Thread 函式庫,自己寫個簡易版的 thread pool 系統吧!

    謝謝你的回應。 :)

  19. 回18和19楼,我在使用threadPool的时候也出现内存泄漏的问题。。。
    环境是Windows XP SP3 + VC90 + Boost1.3.8 + threadPool0.2.5
    囧rz…

  20. @kama:
    感謝你的回報。

    看來 threadpool 只能用於業餘的實驗專案上了。缺乏更新與維護的開源專案,令人心痛哪……

Leave a Reply