作業(yè)3 線程實現加減乘除

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

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

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

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

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

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

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

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

9、義。做這些工作主要想讓代碼更容易理解，在本代碼中把0，1,2,3與加減乘除對應起來，包括發(fā)送隊列在隊列數組中的下標與計算線程id在線程id數組的下標，都是與計算符號相對應的。#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ā)送線程的個數，JNUM可以改變每個發(fā)送線程要產生的計算作業(yè)個數， 我們可以修改這兩個值來動態(tài)的進行測試。 最終的作業(yè)總數是兩者的成績。structjobinta;intb;intop;intr

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

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

12、程產生計算式后，都會根據計算符合把計算式放入到這四個隊列中的某一個上，qrelistPNUM這PNUM個隊列就是要說的回傳隊列，這個是與發(fā)送線程個數相 同的，每個發(fā)送線程對應于一個回傳隊列。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)這個初始化隊列的函數需要動態(tài)申請queue結構體空間，并初始化隊列結構體中的head和tail，以及初始化

13、隊列中的互斥鎖，和條件變量。struct job * produce(int selfnum)這個函數主要是用來產生隨機的計算式， 它產生兩個隨機數和一個隨機的計 算符號，并初始化計算式結構體的其他變量，并且可以確保除號的除數不為零。部分代碼如下：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;如上代碼顯示，當i等于0時產生計算符號，當i等于1時，產生第一個數 字，當i等于2時，產生第二個數字，當i等于3時，結束。void job_append(struct queue *pq,struct job * pj)這個函數主要用于朝隊尾添加計算式， 要考慮隊列為空時添加和隊列有元素時添加，其中主要就是要取得隊列的互斥鎖， 才能添加。 另外就是如果本身隊列 為空，添加一個元素成功時，就要對阻塞在條件變量上的線程執(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);這其實就是在平常隊列添加操作的基礎上添加了條件變量和互斥鎖。void show(struct job * pj)這個是發(fā)送進程接收到回傳的計算式時，需要執(zhí)行該函數打印到屏幕上。void compute(struct job * pj)這個函

16、數是計算線程要調用的一個函數，他根據計算符號主要完成計算任 務，把計算結果保存到計算式結構體中。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數組中的下標，把這個下標記錄 在計算式結構體里面， 用于計算線程計算過之后， 把它放到以這個下標的回傳隊 列中。for(i=0;iJNUM;i+) p_job=job_remove(qrelistselfn

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

18、異常，并做出處理。if(qlisti=malloc(sizeof(struct queue)=NULL)printf(malloc qlist%d errorn,i);exit(0);/在malloc時，如果失敗就要打印出失敗信息，并退出整個進程。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、要是為了保證互斥鎖和條件變量的初始化， 如果初始化失敗 就會返回錯誤碼，并顯示錯誤碼對應的信息，同時也需要釋放已申請的隊列。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ā)送 線程結束時防止出現的錯誤。四、測試對于性能分析，空間復雜度主要是隊列的定義，以及計算式結構體的定義， 由于該代碼中產生了八個隊列的定義，還有JNUM*PNUM個計算式結構體的定 義，每個結構體大小是固定的，我感覺空間復雜度應該是O(JNUM*PNUM*sizeof(job)+8*sizeof(queue),而時間復雜度主 要是O(n)，當PNUM等于3，JNUM也等于3時，測試結果如下圖：O O O O夕餌丨DODO BsishtBsisht CtrlCtrl當PNUM等于3,JNUM等于50時，也就是說產生150個計算式時，執(zhí)行的時間測試結果如下圖: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正在運勞;-OradedeVTvi!Virtue!Virtue!BoxBlBl_ : :41OfflO. 105sOmO,000sOmO.ISOs rootgaotuan：/apue# 鏗二BSBS （SBjRishtS