申時(shí)全

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

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

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

0引言

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

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

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

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

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

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

　　#include <pthread.h>

　　1.1與線程編程相關(guān)的幾個(gè)常用函數(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是一個(gè)指向pthread_t類型指針，如果創(chuàng)建線程成功，則在該指針?biāo)缸兞恐袑?xiě)入線程的標(biāo)識(shí)符（ID號(hào)）;參數(shù)attr是指向線程屬性的結(jié)構(gòu)體指針，一般無(wú)需設(shè)定，只要設(shè)置為NULL即可；參數(shù)start_rtn用來(lái)傳遞一個(gè)函數(shù)地址，該函數(shù)應(yīng)返回一個(gè)任意類型指針，該參數(shù)用一個(gè)定義了的函數(shù)名設(shè)置即可；參數(shù)arg是傳遞給函數(shù)的參數(shù)指針，可以為任何類型。

　　1.1.2線程退出函數(shù)

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

　　void pthread_exit(void *retval);

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

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

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

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

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

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

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

　　pthread_t pthread_self(void);

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

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

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

　　int pthread_equal(pthread_t pid1,pthread_t pid2);

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

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

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

　　函數(shù)原型定義：

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

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

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

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

　　int sem_wait(sem_t *sem);

　　int sem_post(sem_t *sem);

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

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

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

　　int sem_destroy(sem_t *sem);

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

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

　　2.1游戲規(guī)則定義

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

　　2.2程序功能定義

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

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

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

　　（1）鏈表技術(shù)

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

　　typedef struct UserNode{

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

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

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

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

　　Struct UserNode*next;

　　}Node_type;

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

　　（2）安全輸入技術(shù)

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

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

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

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

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

　　rnd_num=rand()%9+1;

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

　　下面給出一個(gè)用于產(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ù)

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

　?。?）如何解決程序中線程同步和互斥問(wèn)題

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

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

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

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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