申時全

　　（廣東科技學院 計算機系， 廣東 東莞 523000）

　　摘要：為了模擬概率事件，針對擲骰子游戲規則，應用Linux系統下C語言多線程機制以及多個二值信號量以實現多個線程間循環同步。通過偽隨機數模擬擲骰子的點數，設計并實現了一個基于多線程方式模擬4人擲骰子游戲程序,并對1 000次游戲中每個游戲者獲勝的次數進行統計。可以看出，在多次游戲中，每個游戲者獲勝的概率符合概率分布規律。程序運行結果表明，利用信號量可有效實現多個線程間的同步與互斥，并簡化了程序結構。

　　關鍵詞：多線程；線程同步；隨機數；擲骰子游戲程序

0引言

　　概率事件是日常生活中經常會遇到的，如出現某種狀況的可能性，產品出現故障的幾率等。本文通過一個模擬擲骰子游戲程序來模擬人們在某種博弈規則下的獲勝概率。采用線程編程模式，用一個線程模擬一個游戲者擲下6個骰子，并按一定規則給出“叫點”數。通過1 000次游戲，統計出每個游戲者獲勝次數N，則獲勝概率為N/1 000。

　　線程是Linux系統的一個執行序列，其處于進程中，多個線程共享同一進程的存儲空間和資源。操作系統以進程為單位分配資源并進行調度。但在多進程并發運行的系統中，進程調度開銷比較大［1］。按一般定義：線程是一個進程內部的一個控制序列。在一個進程中創建新的線程運行時，該線程會擁有自己的運行棧，并與創建它的線程共享全局變量等系統資源。一個進程中的多個線程可以處于并發運行狀態。因此，要使得一個進程中多個線程有序地工作，并有效地共享資源，就需要在線程之間進行有效的同步和互斥控制［2］。Linux系統提供了多種手段實現進程間、線程間的同步和互斥。本文介紹Linux系統下進行多線程編程中線程創建、線程掛起、線程同步和互斥等有關問題，設計了一個模擬4人進行擲骰子游戲的程序，說明了多線程編程中的同步與互斥編程技術。

　　為了實現游戲中擲骰子點數的隨機性，需要用到偽隨機數生成函數。偽隨機數在很多領域中都有應用［3］。通過C標準庫中隨機函數rand( )及相關函數的應用，給出解決指定范圍隨機整數生成通用方法。

　　通過指定一個較大的游戲次數（如1 000），可以統計出各游戲者獲勝概率，按照隨機數的出現概率，則每個游戲者獲勝次數相差不會太大（當然也會有例外）。

1Linux多線程編程中的幾個主要函數

　　在Linux系統中，線程系統調用函數定義在pthread.h中［2］。因此在程序中應有如下指令：

　　#include <pthread.h>

　　1.1與線程編程相關的幾個常用函數

　　1.1.1線程創建函數

　　建立線程的函數pthread_create()，函數原型定義為：

　　int pthread_create(pthread_t *tid,const pthread_attr_t *attr,void *(*start_rtn)(void),void *arg);

　　參數tid是一個指向pthread_t類型指針，如果創建線程成功，則在該指針所指變量中寫入線程的標識符（ID號）;參數attr是指向線程屬性的結構體指針，一般無需設定，只要設置為NULL即可；參數start_rtn用來傳遞一個函數地址，該函數應返回一個任意類型指針，該參數用一個定義了的函數名設置即可；參數arg是傳遞給函數的參數指針，可以為任何類型。

　　1.1.2線程退出函數

　　線程退出函數原型定義為：

　　void pthread_exit(void *retval);

　　通過調用該函數終止線程執行，返回一個指向某對象的指針（注意不能用于返回指向局部變量的指針）。

　　1.1.3使線程掛起的函數

　　函數原型定義為：

　　int pthread_join(pthread_t thread, void **thread_rtn);

　　參數thread指定要等待的線程；參數thread_rtn是一個指針，指向另一個指針，該指針指向線程返回值。

　　1.1.4獲得本線程ID的函數

　　圖1游戲者用戶鏈表函數原型定義為：

　　pthread_t pthread_self(void);

　　通過調用該函數，可獲得當前執行的線程標識符（ID號）。

　　1.1.5判斷兩個線程是否為同一線程的函數

　　函數原型定義為：

　　int pthread_equal(pthread_t pid1,pthread_t pid2);

　　1.2線程同步與互斥的幾個函數

　　在Linux系統中，有關進程、線程同步與互斥的手段有多種，這里只涉及有關的信號量函數［4］。信號量類型sem_t及相關函數定義在semaphore.h中，因此在程序頭部應包含 #include<semaphore.h> 指令。

　　1.2.1創建信號量函數sem_init()

　　函數原型定義：

　　int sem_init (sem_t *sem,int pshared,unsigned inti value);

　　該函數初始化一個信號量，參數sem是指向信號量的指針；參數pshared為0指示該信號量是當前進程的局部信號量，在線程編程中，該參數置為0；參數value是信號量的值。

　　1.2.2控制信號量的函數

　　函數原型定義如下：

　　int sem_wait(sem_t *sem);

　　int sem_post(sem_t *sem);

　　這兩個函數分別對信號量sem執行P操作和V操作。兩個函數的參數都是一個sem_t 類型指針，指向由sem_init調用初始化的信號量。

　　1.2.3銷毀信號量函數

　　函數原型定義為：

　　int sem_destroy(sem_t *sem);

　　用完一個信號量后應銷毀該信號量，并清理相關資源。該函數以一個信號量指針為參數，清理該信號量擁有的所有資源并銷毀這個信號量。

2擲骰子游戲模擬程序設計技術

　　2.1游戲規則定義

　　假定有4個游戲參與者，每人輪流擲下5個骰子，然后找出點數相同最多的點數，例如5個骰子中，出現最多的是3個4點，那就給出一個“叫點數”，這個叫點數就是出現相同點數最多的個數加1及點數，如3個4點，則“叫點數”為（4，4）。規定所有1點可以代替其他任意點數，如有2個1點，3個3點，則可叫5個3點。最后總點數（個數乘點數）最大者為獲勝者，若在一輪游戲中，有2個以上具有相同點數（最大），則多人同時獲勝，其余游戲者為失敗。這個規則由程序模擬，與實際游戲中規則有些不同。

　　2.2程序功能定義

　　該模擬程序應先輸入游戲者姓名，然后在屏幕上開列4個顯示窗口，用于顯示每個游戲者的點數分布（5個）、叫點數、總盤數、獲勝計數值。

　　2.3程序實現技術

　　為了使用戶界面良好，使用Linux系統庫curses支持，使用該庫中的輸出函數實現窗口數據輸出。另外需要用到如下技術：

　　（1）鏈表技術

　　在許多情況下，使用循環鏈表作為數據存儲便于程序訪問［5］。用一個單向循環鏈表存儲游戲用戶的數據，定義節點結構如下：

　　typedef struct UserNode{

　　char name［21］;//用戶名字

　　intcount;//累計次數

　　intscore［MAX_NUM］;//存放每次點數

　　intwin_count;//累計獲勝次數

　　Struct UserNode*next;

　　}Node_type;

　　把4個游戲者用戶節點組成一個帶頭節點的循環鏈表結構，如圖1所示。

　　（2）安全輸入技術

　　為了輸入用戶名，且必須在指定屏幕位置輸入，用戶輸入時不能超過限定字符個數（例如20），否則會出現運行錯誤。因此不能使用常規標準庫函數gets( )輸入，而是另外編寫一個函數GetString(char *str,int len)來實現。該函數中，通過調用Linux系統無回顯字符輸入函數getch( )讀取字符，并排除非法字符，限制輸入字符數小于或等于參數len。其源程序實現限于篇幅不再贅述。

　　（3）輸入游戲者姓名創建用戶鏈表結構

　　程序中定義一個用于建立鏈表的函數Node_type *creat_List(int n)，這個函數建立具有n個用戶節點的循環鏈表，返回鏈表頭指針。該函數調用前面給出的函數GetString( )輸入游戲者姓名。

　　（4）生成隨機數問題

　　在C語言的標準庫中定義了隨機數生成函數rand( )，用于生成0~RAND_MAX的整數。程序采用單向函數反復迭代，周期性地輸出偽隨機序列［3］。一般，如果要生成一個給定范圍（例如1~9）的隨機數，都會使用如下語句：

　　rnd_num=rand()%9+1;

　　這樣不符合隨機分布原則。為了防止運行程序每次產生的都是同一隨機數列，有必要初始化隨機種子。使用srand((int)time(NULL))來將偽隨機數生成器初始化為某一個不可預測點，在程序初始化時執行。

　　下面給出一個用于產生給定范圍的隨機數函數。

　　int RandomInt(int low,int high){

　　int rnd;double d;

　　d=(double)rand( )/((double)RAND_MAX+1);

　　rnd=(int)(d*(high-low+1));

　　return rnd;

　　}

　　（5）多窗口顯示技術

　　為了在每個獨立窗口顯示一個游戲用戶線程狀態數據，需要用到Linux中curses庫，該庫支持頭文件curses.h。支持窗口顯示的有關函數定義在這個頭文件中。下面列出幾個相關函數：

　　創建窗口函數，函數原型：

　　WINDOW *newwin(int line,int cols,int start_y, int start_x);

　　在窗口指定位置進行格式化輸出，函數原型：

　　int mvwprintw(WINDOW *win, int row,int col, char *format,…);

　　限于篇幅，其他函數不再列出。

　　（6）如何解決程序中線程同步和互斥問題

　　整個游戲程序由4個游戲者用戶線程和一個主線程構成。主線程和4個游戲者用戶線程的關系是：主線程做好初始化工作，創建4個游戲者線程，然后做好初始準備，進入游戲循環控制。因為游戲者線程一旦創建就會開始執行，所以必須處理好主線程與各個游戲用戶線程之間的同步關系。每個線程用2個信號量實現同步，通過參數傳遞方式將信號量傳到線程中，程序中設置5個共享的sem_t信號量。同步順序關系如圖2所示。

　　對于多線程程序，每個線程都可并發運行，但對于訪問共享數據必須是互斥訪問，即滿足互斥關系［6］。使用一個互斥信號量實現共享數據的互斥訪問。主線程必須使第一個游戲者線程正確進入，然后是第二個、第三個、第四個游戲者線程執行，產生游戲數據并修改了狀態數據后，主線程處理結果數據，判定每個游戲者勝負，修改其獲勝統計值，然后進入下一輪游戲。通過共享一個全局工作指針work實現節點數據修改。

3程序實現

　　對于4個游戲者線程的實現，可以分別實現4個線程控制序列，即定義4個線程函數。由于每個線程行為是一致的，可以在創建線程時傳遞一個變量i的指針給線程實現同步。

　　創建線程語句：

　　pthread_crete(&pid［i-1］,NULL,gamer,(void *)&i);

　　在屏幕上實現多窗口顯示效果，顯示游戲者狀態數據，程序中模擬4個游戲者輪流擲骰子MAX_NUM（最多1 000）次，線程負責生成5個隨機數（1~6）表示擲下5個骰子。用一個全局指針變量work指向每個線程的信息節點。一輪游戲結束，work指針指向頭節點，主線程則在處理一輪游戲的勝負決斷后，將work指向首節點，開始下一輪游戲。主線程程序結構如圖3所示，游戲者線程程序結構如圖4所示。

　　運行這個程序需要用到curses庫和pthread庫，編譯時使用選項lpthreadlcurses。經過程序運行，表明采用的同步控制方法是有效的，獲得了預期效果。表1所示為其中一組運行結果。

4結論

　　模擬4人進行擲骰子游戲的多線程游戲程序驗證了隨機數的統計性能，也說明了多線程編程方法的可行性。通過多線程編程可以很好地解決并發性問題［6］。本文給出的模擬程序工作模式，對于具有多個循環控制對象的系統的應用編程具有參考價值［7］，只要將相關操作語句更換成循環控制節點對象的控制（測量）操作即可，其程序采用的多線程同步方法是通用的［8］。另外，如果將此程序移植到網絡模式，每個線程改為與實際游戲者進行通信的程序語句方式，就可以實現網絡下的游戲程序，可以把叫點過程改為接收遠程游戲者輸入的叫點數。當然，要實現網絡模式下的游戲程序還有許多工作要做。在具有多核處理器情況下采用多線程編程將會獲得更高的運行效率。

參考文獻

　　［1］ 何宏宇, 劉正熙, 陳正茂. 基于Linux的多進程MDSL研究與設計［J］. 四川大學學報(自然科學版), 2013, 50(1): 4650.

　　［2］ 劉金, 胡創, 胡明,等. 多線程環境下基于多預取點的文件預取［J］. 計算機應用, 2012, 32(6): 17131716, 1720.

　　［3］ 高樹靜, 曲英杰, 宋廷強. 基于單向函數的偽隨機數發生器［J］. 計算機研究與發展, 2015, 52(6): 13941399.

　　［4］ 彭玉柱.基于多線程機制的電力數據采集系統設計與實現［J］. 計算機應用與軟件, 2015，32(1):7881.

　　［5］ 何先波, 李明東, 王錦, 等. Linux操作系統中通用雙向循環鏈表的實現分析［J］. 西華師范大學學報(自然科學版), 2012, 33(2): 213217.

　　［6］ 謝文斌, 陳學適, 姜忠鼎. 并行繪制游戲系統中同步傳輸協議的設計與實現［J］. 計算機應用與軟件, 2014,31(10):99103.

　　［7］ 趙源, 姜小峰. 基于多線程技術的自動測試系統優化設計［J］. 計算機應用, 2014, 34 (7):21242128.

　　［8］ 吳宇佳, 浦偉, 周妍,等. Linux下多線程數據采集研究與實現［J］. 信息安全與通信保密, 2012(7):9294.