申時全

　?。◤V東科技學院 計算機系,， 廣東 東莞 523000）

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

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

0引言

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

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

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

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

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

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

　　#include <pthread.h>

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

　　1.1.1線程創(chuàng)建函數

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

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

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

　　1.1.2線程退出函數

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

　　void pthread_exit(void *retval);

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

　　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);

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

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

　　函數原型定義為：

　　int pthread_equal(pthread_t pid1,pthread_t pid2);

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

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

　　1.2.1創(chuàng)建信號量函數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執(zhí)行P操作和V操作,。兩個函數的參數都是一個sem_t 類型指針,，指向由sem_init調用初始化的信號量。

　　1.2.3銷毀信號量函數

　　函數原型定義為：

　　int sem_destroy(sem_t *sem);

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

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

　　2.1游戲規(guī)則定義

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

　　2.2程序功能定義

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

　　2.3程序實現技術

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

　?。?）鏈表技術

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

　　typedef struct UserNode{

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

　　intcount;//累計次數

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

　　intwin_count;//累計獲勝次數

　　Struct UserNode*next;

　　}Node_type;

　　把4個游戲者用戶節(jié)點組成一個帶頭節(jié)點的循環(huán)鏈表結構,，如圖1所示。

　?。?）安全輸入技術

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

　?。?）輸入游戲者姓名創(chuàng)建用戶鏈表結構

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

　　（4）生成隨機數問題

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

　　rnd_num=rand()%9+1;

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

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

　　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;

　　}

　?。?）多窗口顯示技術

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

　　創(chuàng)建窗口函數，函數原型：

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

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

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

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

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

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

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

3程序實現

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

　　創(chuàng)建線程語句：

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

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

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

4結論

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

參考文獻

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

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

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

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

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

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

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

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