作業(yè)3 線程實(shí)現(xiàn)加減乘除

1、電子科技大學(xué)學(xué)生姓名： 學(xué) 號： 指導(dǎo)教師： 學(xué)生E-mailE-mail：、作業(yè)名稱線程實(shí)現(xiàn)加減乘除服務(wù) 二、作業(yè)要求試驗(yàn)要求：使用多個隊(duì)列， 每一個計(jì)算線程有獨(dú)立的隊(duì)列用于存儲計(jì)算請求， 請求線程 可用一個隊(duì)列用于接收結(jié)果。只需要實(shí)現(xiàn)A(+,-,X,/)B簡單兩元計(jì)算請求線程與計(jì)算線程是多對多關(guān)系三、設(shè)計(jì)與實(shí)現(xiàn)根據(jù)試驗(yàn)要求， 線程間的通信用隊(duì)列， 所以通信結(jié)構(gòu)就不用考慮了， 提到隊(duì) 我們就要做初始化隊(duì)列， 朝隊(duì)列里面添加信息， 從隊(duì)列頭部取走信息這些工但是在隊(duì)列的操作中， 最重要的就是線程的同步問題了， 我選擇了一個互斥互斥鎖保證對隊(duì)列的任何操作必須唯一， 條件 變量使我們可以放心的等待隊(duì)

2、列有內(nèi)容，接著我們就需要選擇我們的整體結(jié)構(gòu) 了。最開始，我考慮用一個隊(duì)列，發(fā)送線程把計(jì)算式結(jié)構(gòu)體放到這個隊(duì)列里面，這個計(jì)算式結(jié)構(gòu)體里面包括接收線程的ID號，每個接收線程輪流去讀取隊(duì)列， 但是只能讀取接受進(jìn)程是自己的結(jié)構(gòu)體， 然后再把這些結(jié)果都返回給主線程， 主3.1設(shè)計(jì)方案列，作，鎖和一個條件變量相結(jié)合的方法，線程對這個計(jì)算式進(jìn)行打印到屏幕，但是這個模型有一定的限制，那就是接受計(jì) 算線程個數(shù)每次去取得互斥鎖，并準(zhǔn)備去取計(jì)算式，發(fā)現(xiàn)這個結(jié)構(gòu)體里面的接受 線程不是自己，不得不釋放互斥鎖，輪流這樣做，這樣的效率會比較低。由于計(jì)算類型是確定的，經(jīng)過綜合考慮，我覺得還是初始化四個發(fā)送隊(duì)列，每個計(jì)算線程（

3、加，減，乘，除）各對應(yīng)一個隊(duì)列，發(fā)送線程會根據(jù)自己產(chǎn)生的 計(jì)算式類型，把這個結(jié)構(gòu)體放入對應(yīng)的隊(duì)列中，這樣接收線程在隊(duì)列不空的情況 下，就可以去取，并且保證可以取到，同時初始化四個回傳隊(duì)列，計(jì)算線程計(jì)算 完畢后，把結(jié)果回傳個產(chǎn)生這個計(jì)算式的線程。 這樣雖然會占有一定的空間，但 是對于充足的內(nèi)存，空間換時間的做法還是可以選擇的。在最后選擇進(jìn)程結(jié)束時，我考慮的是計(jì)算線程不能退出，因?yàn)闀簳r隊(duì)列為空，不代表沒有了該類型的計(jì)算式，但是還要保證最后整個線程正常退出，只能讓所 有的發(fā)送線程在接收到各自全部的計(jì)算式后返回主線程，這樣主線程根據(jù)返回的 發(fā)送線程的個數(shù)來判斷是否結(jié)束整個進(jìn)程。另外發(fā)送線程的個數(shù)以及每

4、個發(fā)送線程發(fā)送多少個計(jì)算式作業(yè)， 都是用宏定義定義的，只要改變這兩個值就可以修改線程的個數(shù)和現(xiàn)成的作業(yè)數(shù)，我這里主 要的思想還是想把加減乘除與0，1,2,3對應(yīng)起來，這樣可以保證四個發(fā)送隊(duì)列的類型與加減乘除匹配起來，并且計(jì)算線程id數(shù)組的下標(biāo)剛好也用0，1,2,3與加減乘除對應(yīng)，這樣可以簡單好理解。-1加肚汁算線程:牛減法計(jì)算線程I-發(fā)送線程 2- K:4 tnnfrOT回傳隊(duì)列減法發(fā)送隊(duì)列 2-.-W-回傳 Ik 列2- -加法發(fā)匹 liu 吐乘法塩學(xué)隊(duì)列 3*I II I除法發(fā)食認(rèn)列卄-J&=乘法計(jì)算線程結(jié)構(gòu)圖1除法計(jì)算線e這里只是大體的模型，下面會詳細(xì)說明中間的細(xì)節(jié)。3.2模塊分析根據(jù)我

5、自己的代碼分析，我大概分了初始化隊(duì)列，隊(duì)尾插入，對頭移除，計(jì)算式產(chǎn)生，計(jì)算，輸出這六個模塊，模塊圖如下:模塊圖23.3流程介紹加法發(fā)送隊(duì)列，減法發(fā)送隊(duì)列，乘法發(fā)送隊(duì)列，除法發(fā)送隊(duì)列，接著會初始化N個回傳隊(duì)列，這個N的個數(shù)與發(fā)送線程的個數(shù)保持一致，都有代碼開始的宏定 義定義，然后根據(jù)宏定義N產(chǎn)生N個子線程，開始發(fā)送子線程的工作，同時也要產(chǎn)生四個計(jì)算子線程，分別對應(yīng)于加法計(jì)算，減法計(jì)算，乘法計(jì)算，除法計(jì)算, 他們從對應(yīng)的發(fā)送隊(duì)列中取出要計(jì)算的計(jì)算式， 并把他們計(jì)算出來，再根據(jù)這個計(jì)算式是由哪個發(fā)送線程產(chǎn)生的，把計(jì)算結(jié)果回送給那個發(fā)送進(jìn)程，發(fā)送進(jìn)程把 這個計(jì)算式打印出來，并返回主線程，主線程當(dāng)所有發(fā)

6、送線程都返回時， 就退出 這個進(jìn)程，到此為止，主進(jìn)程結(jié)束，先畫出大概的流程圖，在詳細(xì)畫出發(fā)送線程 和計(jì)算線程各自的流程圖。從主程序開始，首先主線程初始化發(fā)送隊(duì)列,發(fā)送隊(duì)列主要分為四種類型,- M- - -初始化發(fā)送0人列:丨；初始化回傳隊(duì)列丨I產(chǎn)生發(fā)迖線程并匸作產(chǎn)生計(jì)算進(jìn)程井匸作一丄一等到所有發(fā) 團(tuán)程返回主線:I :退出遲程=- - M-主線程的流程圖3對于發(fā)送線程，首先通過一個函數(shù)產(chǎn)生兩個一定范圍的隨機(jī)數(shù), 加減乘除的符號，并判斷當(dāng)符號為除號時，除數(shù)是否為零，若為零，則重新產(chǎn)生 兩個數(shù)字作為除數(shù)與被除數(shù)，然后根據(jù)運(yùn)算符號把自己產(chǎn)生的計(jì)算式結(jié)構(gòu)體插入 在相對應(yīng)隊(duì)列的尾部，插入的過程需要保證取得

7、互斥鎖，這樣可以保證線程的同 步，當(dāng)自己產(chǎn)生JNUM個作業(yè)后，這些發(fā)送線程就要在屬于自己的回傳隊(duì)列上 等待接受計(jì)算過的計(jì)算式，并打印到屏幕，當(dāng)線程接收到自己發(fā)送的所有計(jì)算作 業(yè)后，就要返回到主線程。并產(chǎn)生一個-餐-隨機(jī)產(chǎn)生計(jì)算符號 隨即產(chǎn)牛.兩個數(shù)字:否:遍過術(shù)環(huán)把產(chǎn)生的INLH個計(jì)算 式插入到對應(yīng)符號的隊(duì)列中 i 等待汁算線程N(yùn)算完畢后回傳 冋來訃算結(jié)果I I-I:t:沢打印屏幕奪號為除號，除數(shù)為0是接受回傳什果是占大于加I I- -是一*:返回主線程-M M-對于計(jì)算線程，由于我這里各個計(jì)算線程要執(zhí)行的函數(shù)是同一個函數(shù)，所以這些計(jì)算線程開始要確定自己線程id在線程id數(shù)組中的下標(biāo)，下標(biāo)0,

8、1,2,3分別對應(yīng)于加，減乘，除，如果一個線程對應(yīng)的下標(biāo)是0,則表示這個線程要執(zhí)行加法計(jì)算，并根據(jù)這個下標(biāo)，去發(fā)送隊(duì)列中取出一個計(jì)算作業(yè)， 這是不僅要取得隊(duì)列的互斥鎖，而且還要等待條件變量，這個條件變量只是為了保證這個隊(duì)列不空，才能使計(jì)算線程能成功取得該作業(yè)，取得一個作業(yè)后，進(jìn)行相應(yīng)的計(jì)算,然后把該計(jì)算結(jié)果放到發(fā)送線程對應(yīng)的回傳隊(duì)列中， 就這樣一直循環(huán)，知道主線程退出，它就自動退出了。發(fā)送線程的流程圖計(jì)算線程的流程圖5結(jié)合這三個流程圖，可以對大概思路有個了解。3.4關(guān)鍵代碼分析上面說到一些大體的思路，但是中間的一些實(shí)現(xiàn)細(xì)節(jié)這里會詳細(xì)分析， 首先先介紹下，這個實(shí)驗(yàn)用的數(shù)據(jù)結(jié)構(gòu)以及一些關(guān)鍵的變量定

9、義。做這些工作主要想讓代碼更容易理解，在本代碼中把0，1,2,3與加減乘除對應(yīng)起來，包括發(fā)送隊(duì)列在隊(duì)列數(shù)組中的下標(biāo)與計(jì)算線程id在線程id數(shù)組的下標(biāo)，都是與計(jì)算符號相對應(yīng)的。#define PNUM 3#defi ne ADD 0#defi ne SUB 1#defi ne MUL 2#defi ne DIV 3pthread_t ptidPNUM,ctid4;#define JNUM 3PNUM定義了發(fā)送線程的個數(shù)，JNUM可以改變每個發(fā)送線程要產(chǎn)生的計(jì)算作業(yè)個數(shù)， 我們可以修改這兩個值來動態(tài)的進(jìn)行測試。 最終的作業(yè)總數(shù)是兩者的成績。structjobinta;intb;intop;intr

10、es;int pno;struct job *next;struct job *prev;這個定義了隊(duì)列上的節(jié)點(diǎn)結(jié)構(gòu)a和b是兩個運(yùn)算數(shù)字，op是一個0到3的數(shù)字，代表加減乘除算法，res是計(jì)算線程計(jì)算過結(jié)果之后把計(jì)算結(jié)果存在該變量中，并會傳給發(fā)送線程，pno標(biāo)記的是與發(fā)送線程對應(yīng)的回傳隊(duì)列的下標(biāo)，計(jì)算線程正是靠這個變量來尋找到某個計(jì)算式的發(fā)送線程的， 并把它放入對應(yīng)的回傳隊(duì)列中。next和prex是該節(jié)點(diǎn)前一個節(jié)點(diǎn)和后一個節(jié)點(diǎn)的地址，通過他們構(gòu)成鏈隊(duì)列。struct queuestruct job * head;struct job *tail;pthread_mutex_t lock;pth

11、read_cond_t ready;這個是對隊(duì)列的聲明，其中head和tail是隊(duì)列的對頭和隊(duì)尾指針，lock是一個互斥鎖，所有對隊(duì)列的操作都要先獲得這個互斥鎖，否則不能進(jìn)行，ready是一個條件變量， 一個線程去取計(jì)算結(jié)構(gòu)體， 就要等到這個條件符合，這個條件變量保證隊(duì)列不為空時，線程才可以去取結(jié)構(gòu)體。pthread_t ptidPNUM,ctid4;struct queue *qlist4;struct queue *qrelistPNUM;ptid這個數(shù)組是產(chǎn)生發(fā)送線程時，存儲他們的線程id，同樣，ctid這個數(shù)組是產(chǎn)生計(jì)算線程時，存儲他們的線程id，qlist4是四個發(fā)送隊(duì)列，每個發(fā)送線

12、程產(chǎn)生計(jì)算式后，都會根據(jù)計(jì)算符合把計(jì)算式放入到這四個隊(duì)列中的某一個上，qrelistPNUM這PNUM個隊(duì)列就是要說的回傳隊(duì)列，這個是與發(fā)送線程個數(shù)相 同的，每個發(fā)送線程對應(yīng)于一個回傳隊(duì)列。void init_queue(struct queue *qlist,int num)qlisti-head=NULL;qlisti-tail=NULL;pthread_mutex_init(&qlisti-lock,NULL)pthread_cond_init(&qlisti-ready,NULL)這個初始化隊(duì)列的函數(shù)需要動態(tài)申請queue結(jié)構(gòu)體空間，并初始化隊(duì)列結(jié)構(gòu)體中的head和tail，以及初始化

13、隊(duì)列中的互斥鎖，和條件變量。struct job * produce(int selfnum)這個函數(shù)主要是用來產(chǎn)生隨機(jī)的計(jì)算式， 它產(chǎn)生兩個隨機(jī)數(shù)和一個隨機(jī)的計(jì) 算符號，并初始化計(jì)算式結(jié)構(gòu)體的其他變量，并且可以確保除號的除數(shù)不為零。部分代碼如下：while(1)srand(unsigned)time(0)*(ran);if(i=0) p_job-op=rand()%4;i+;ran+;else if(i=1) p_job-a=rand()%1000;i+;pthread_mutex_unlock(&(pq-lock);ran+;else p_job-b=rand()%1000;if(p_jo

14、b-b=0 & p_job-op=DIV) i=1;i+;ran+;if(i=3) break;如上代碼顯示，當(dāng)i等于0時產(chǎn)生計(jì)算符號，當(dāng)i等于1時，產(chǎn)生第一個數(shù) 字，當(dāng)i等于2時，產(chǎn)生第二個數(shù)字，當(dāng)i等于3時，結(jié)束。void job_append(struct queue *pq,struct job * pj)這個函數(shù)主要用于朝隊(duì)尾添加計(jì)算式， 要考慮隊(duì)列為空時添加和隊(duì)列有元素時添加，其中主要就是要取得隊(duì)列的互斥鎖， 才能添加。 另外就是如果本身隊(duì)列 為空，添加一個元素成功時，就要對阻塞在條件變量上的線程執(zhí)行喚醒操作。pthread_mutex_lock(&(pq-lock);pj-nex

15、t=NULL;pj-prev=pq-tail;if(pq-tail!=NULL)pq-tail-next=pj;elsepq-head=pj;pq-tail=pj;if(prestatus=NULL & pq-head!=NULL)pthread_t self=pthread_self();pthread_cond_broadcast(&pq-ready);這其實(shí)就是在平常隊(duì)列添加操作的基礎(chǔ)上添加了條件變量和互斥鎖。void show(struct job * pj)這個是發(fā)送進(jìn)程接收到回傳的計(jì)算式時，需要執(zhí)行該函數(shù)打印到屏幕上。void compute(struct job * pj)這個函

16、數(shù)是計(jì)算線程要調(diào)用的一個函數(shù)，他根據(jù)計(jì)算符號主要完成計(jì)算任 務(wù)，把計(jì)算結(jié)果保存到計(jì)算式結(jié)構(gòu)體中。void * pthfun(void *arg)這個是發(fā)送線程要執(zhí)行的代碼部分，其中pthread_t self=pthread_self();for(i=0;iPNUM;i+) if(pthread_equal(ptidi,self)!=0) break;主要是來確定自己發(fā)送線程id所在線程id數(shù)組中的下標(biāo)，把這個下標(biāo)記錄 在計(jì)算式結(jié)構(gòu)體里面， 用于計(jì)算線程計(jì)算過之后， 把它放到以這個下標(biāo)的回傳隊(duì) 列中。for(i=0;iJNUM;i+) p_job=job_remove(qrelistselfn

17、um);show(p_job);這個代碼主要用于發(fā)送線程接受回傳的計(jì)算式， 并打印到屏幕上， 如果接受 完了自己產(chǎn)生的所有計(jì)算式就要返回主線程了。void * cthfun(void * arg)這個函數(shù)是計(jì)算線程要執(zhí)行的代碼， 他主要就是去取數(shù)據(jù)并計(jì)算， 然后放回 各自發(fā)送線程的隊(duì)列里。for(i=0;ihead=NULL) pthread_cond_wait(&pq-ready,&pq-lock);這里是計(jì)算線程要去取數(shù)據(jù)時， 防止阻塞的線程返回時， 又有其他線程使這 個條件失效。3.5異常情況設(shè)計(jì)異常情況在代碼中其實(shí)需要考慮的很多， 基本上每個關(guān)鍵的代碼都可能出現(xiàn) 異常，這是就要檢測這些

18、異常，并做出處理。if(qlisti=malloc(sizeof(struct queue)=NULL)printf(malloc qlist%d errorn,i);exit(0);/在malloc時，如果失敗就要打印出失敗信息，并退出整個進(jìn)程。if(err=pthread_mutex_init(&qlisti-lock,NULL)!=0) strerror(err);free(qlisti);exit(0);/ if(err=pthread_cond_init(&qlisti-ready,NULL)!=0)strerror(err);free(qlisti);exit(0);這部分的代碼主

19、要是為了保證互斥鎖和條件變量的初始化， 如果初始化失敗 就會返回錯誤碼，并顯示錯誤碼對應(yīng)的信息，同時也需要釋放已申請的隊(duì)列。if(err=(pthread_create(&ptidi,NULL,pthfun,NULL)!=0)strerror(err);exit(0);/if(err=(pthread_create(&ctidi,NULL,cthfun,NULL)!=0)strerror(err);exit(0);err=pthread_join(ptidi,NULL);if(err!=0)strerror(err);exit(0);這三小段代碼也主要是在創(chuàng)建發(fā)送線程， 創(chuàng)建接受線程， 和主線

20、程等待發(fā)送 線程結(jié)束時防止出現(xiàn)的錯誤。四、測試對于性能分析，空間復(fù)雜度主要是隊(duì)列的定義，以及計(jì)算式結(jié)構(gòu)體的定義， 由于該代碼中產(chǎn)生了八個隊(duì)列的定義，還有JNUM*PNUM個計(jì)算式結(jié)構(gòu)體的定 義，每個結(jié)構(gòu)體大小是固定的，我感覺空間復(fù)雜度應(yīng)該是O(JNUM*PNUM*sizeof(job)+8*sizeof(queue),而時間復(fù)雜度主 要是O(n)，當(dāng)PNUM等于3，JNUM也等于3時，測試結(jié)果如下圖：O O O O夕餌丨DODO BsishtBsisht CtrlCtrl當(dāng)PNUM等于3,JNUM等于50時，也就是說產(chǎn)生150個計(jì)算式時，執(zhí)行的時間測試結(jié)果如下圖:1012.h10-11 .C1

21、0-15.cabcbanbb10-2,CCil10-3. C110 0client2-2.C2-3上5-1.5-2.5 3*5-3,POOtOPOOtO13S -aoyuan146 =Cc1 - CC Czclient.c匚iient.pnef inish匚omputecompute * clpue_匚deslpue_codes_EOll mmnohole.filepipefileqqscanfile.c scaniile.c.bak serverserver.ctesT4.txttree.ctree.匚.bak treefilettLjordcount. cLjondcaunt. c. ba

22、k16117343B32 +3E0Zapue# tifoe./匚mpuTe0167R1-34143red1 user sysrooTtggaoYuanT/ariue#0m0*0lsOmO * 004&OmO.016sIgdebidebi anan正在 行*OracleOracleVivfViirtusiBoxViirtusiBoxLFj j旦L翳蘭竺山出 IIIIII川IXIX1 1=B71571=1二355431=-569=0=624051=9105662307=1671=-5565442044&=385956=0=7B2=46二70realuser sysrootagaoTuan： 7a口ue#OmO.151sOmOOmO. .008sOmO-140sif。IgdebidnIgdebidn正在運(yùn)勞;-OradedeVTvi!Virtue!Virtue!BoxBlBl_ : :41OfflO. 105sOmO,000sOmO.ISOs rootgaotuan：/apue# 鏗二BSBS （SBjRishtS