申時全

　?。◤V東科技學(xué)院 計算機(jī)系， 廣東 東莞 523000）

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

　　關(guān)鍵詞：多線程；線程同步；隨機(jī)數(shù)；擲骰子游戲程序

0引言

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

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

　　為了實現(xiàn)游戲中擲骰子點(diǎn)數(shù)的隨機(jī)性，需要用到偽隨機(jī)數(shù)生成函數(shù)。偽隨機(jī)數(shù)在很多領(lǐng)域中都有應(yīng)用［3］。通過C標(biāo)準(zhǔn)庫中隨機(jī)函數(shù)rand( )及相關(guān)函數(shù)的應(yīng)用，給出解決指定范圍隨機(jī)整數(shù)生成通用方法。

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

1Linux多線程編程中的幾個主要函數(shù)

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

　　#include <pthread.h>

　　1.1與線程編程相關(guān)的幾個常用函數(shù)

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

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

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

　　參數(shù)tid是一個指向pthread_t類型指針，如果創(chuàng)建線程成功，則在該指針?biāo)缸兞恐袑懭刖€程的標(biāo)識符（ID號）;參數(shù)attr是指向線程屬性的結(jié)構(gòu)體指針，一般無需設(shè)定，只要設(shè)置為NULL即可；參數(shù)start_rtn用來傳遞一個函數(shù)地址，該函數(shù)應(yīng)返回一個任意類型指針，該參數(shù)用一個定義了的函數(shù)名設(shè)置即可；參數(shù)arg是傳遞給函數(shù)的參數(shù)指針，可以為任何類型。

　　1.1.2線程退出函數(shù)

　　線程退出函數(shù)原型定義為：

　　void pthread_exit(void *retval);

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

　　1.1.3使線程掛起的函數(shù)

　　函數(shù)原型定義為：

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

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

　　1.1.4獲得本線程ID的函數(shù)

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

　　pthread_t pthread_self(void);

　　通過調(diào)用該函數(shù)，可獲得當(dāng)前執(zhí)行的線程標(biāo)識符（ID號）。

　　1.1.5判斷兩個線程是否為同一線程的函數(shù)

　　函數(shù)原型定義為：

　　int pthread_equal(pthread_t pid1,pthread_t pid2);

　　1.2線程同步與互斥的幾個函數(shù)

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

　　1.2.1創(chuàng)建信號量函數(shù)sem_init()

　　函數(shù)原型定義：

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

　　該函數(shù)初始化一個信號量，參數(shù)sem是指向信號量的指針；參數(shù)pshared為0指示該信號量是當(dāng)前進(jìn)程的局部信號量，在線程編程中，該參數(shù)置為0；參數(shù)value是信號量的值。

　　1.2.2控制信號量的函數(shù)

　　函數(shù)原型定義如下：

　　int sem_wait(sem_t *sem);

　　int sem_post(sem_t *sem);

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

　　1.2.3銷毀信號量函數(shù)

　　函數(shù)原型定義為：

　　int sem_destroy(sem_t *sem);

　　用完一個信號量后應(yīng)銷毀該信號量，并清理相關(guān)資源。該函數(shù)以一個信號量指針為參數(shù)，清理該信號量擁有的所有資源并銷毀這個信號量。

2擲骰子游戲模擬程序設(shè)計技術(shù)

　　2.1游戲規(guī)則定義

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

　　2.2程序功能定義

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

　　2.3程序?qū)崿F(xiàn)技術(shù)

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

　?。?）鏈表技術(shù)

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

　　typedef struct UserNode{

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

　　intcount;//累計次數(shù)

　　intscore［MAX_NUM］;//存放每次點(diǎn)數(shù)

　　intwin_count;//累計獲勝次數(shù)

　　Struct UserNode*next;

　　}Node_type;

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

　?。?）安全輸入技術(shù)

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

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

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

　　（4）生成隨機(jī)數(shù)問題

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

　　rnd_num=rand()%9+1;

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

　　下面給出一個用于產(chǎn)生給定范圍的隨機(jī)數(shù)函數(shù)。

　　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;

　　}

　?。?）多窗口顯示技術(shù)

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

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

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

　　在窗口指定位置進(jìn)行格式化輸出，函數(shù)原型：

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

　　限于篇幅，其他函數(shù)不再列出。

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

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

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

3程序?qū)崿F(xiàn)

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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