操作系統(tǒng)課程設(shè)計報告(網(wǎng)絡(luò)121朱正杰).doc

操作系統(tǒng)課程設(shè)計報告題目： 線程安全型雙向鏈表的實現(xiàn) 專 業(yè)： 網(wǎng)絡(luò)工程 班 級： 網(wǎng)絡(luò)121 學(xué) 號： 201210314005 姓 名： 朱正杰 上海海事大學(xué)信息工程學(xué)院2014年 12月 15日目錄1.課程設(shè)計任務(wù)描述與要求11.1任務(wù)描述12.系統(tǒng)總體結(jié)構(gòu)描述與主要數(shù)據(jù)結(jié)構(gòu)說明12.1系統(tǒng)總體結(jié)構(gòu)描述12.2主要數(shù)據(jù)結(jié)構(gòu)說明23.課程設(shè)計報告內(nèi)容53.1模塊功能53.2詳細(xì)流程圖63.3實現(xiàn)思路說明73.4程序清單73.5注釋84.總結(jié)19附錄：19程序使用說明19程序測試思想20程序測試結(jié)果20參考書目：211.課程設(shè)計任務(wù)描述與要求1.1任務(wù)描述編寫一個線程安全的雙向鏈表，所謂線程安全，就是該鏈表能夠?qū)崿F(xiàn)多個線程同時正確的增刪改鏈表結(jié)點，也就是能夠?qū)崿F(xiàn)對鏈表這個臨界資源的保護。1.2任務(wù)要求需要實現(xiàn)的函數(shù)包括：（1） InitList函數(shù)：初始化一個空的雙向鏈表，并初始化各個用于保護鏈表的信號量。（2） Insert函數(shù)：向鏈表指定位置插入一個結(jié)點。（3） Erase函數(shù)：刪除指定位置的結(jié)點。（4） Clear函數(shù)：刪除鏈表中的所有結(jié)點。（5） Find函數(shù)：查找鏈表中是否有指定的元素，若有，返回能夠訪問該結(jié)點的指針；若無，返回NULL。（6） Print函數(shù)：打印當(dāng)前鏈表中的所有元素。完成該鏈表后，自己編寫一個測試程序，生成多個線程同時讀寫該鏈表，驗證鏈表執(zhí)行是否正確，并給出測試報告。2.系統(tǒng)總體結(jié)構(gòu)描述與主要數(shù)據(jù)結(jié)構(gòu)說明2.1系統(tǒng)總體結(jié)構(gòu)描述系統(tǒng)總體結(jié)構(gòu)設(shè)計的任務(wù)，是根據(jù)系統(tǒng)分析的邏輯模型設(shè)計應(yīng)用軟件系統(tǒng)的物理結(jié)構(gòu)。系統(tǒng)物理模型必須符合邏輯模型，能夠完成邏輯模型所規(guī)定的信息處理功能。這是物理設(shè)計的基本要求。系統(tǒng)應(yīng)具有可修改性，即易讀，易于進行查錯、改錯、可以根據(jù)環(huán)境的變化和用戶的要求進行各種的改變和改進。系統(tǒng)是否具有可修改性，對于系統(tǒng)開發(fā)和維護影響極大。據(jù)統(tǒng)計，在系統(tǒng)生命周期中各階段的應(yīng)用軟件費用及人力投入大體分布如下：系統(tǒng)開發(fā)：20%；系統(tǒng)維護：80%。由于程序功能簡單，未用數(shù)據(jù)庫輔助存儲技術(shù)，本程序只供實現(xiàn)對雙向鏈表的插入，刪除，查找和打印等功能。2.2主要數(shù)據(jù)結(jié)構(gòu)說明宏定義部分：#define random(x)(rand()%x) /產(chǎn)生隨機數(shù)#define cr 1 /1標(biāo)識為插入#define sc 0 /0標(biāo)識為刪除volatile int readcount=0; /讀者數(shù)目const int lsarea=10000; /鏈表大小隨機數(shù)const int earea=10000; /元素范圍隨機數(shù)const int sum=100000; /線程運行總次數(shù)int th=0; /初始化當(dāng)前線程總數(shù)int th_cz=1; /初始化當(dāng)前查找線程總數(shù)int th_cr=1; /初始化當(dāng)前插入線程總數(shù)int th_sc=1; /初始化當(dāng)前刪除線程總數(shù)HANDLE h_Mutex; /控制讀者數(shù)量readcount的互斥訪問量HANDLE mutex; /控制讀寫互斥，寫寫互斥的信號量typedef int ElemType; / 定義ElemType為int類型的別名typedef struct DuLNode *PNode; /結(jié)點指針/定義結(jié)點結(jié)構(gòu)體typedef struct DuLNodeElemType data; /定義數(shù)據(jù)域PNode prior; /定義前驅(qū)指針PNode next; /定義后繼指針DuLNode,*DLN;/定義雙向鏈表結(jié)構(gòu)體typedef struct DuLinkListDLN head; /定義頭結(jié)點int Length; /定義鏈表長度DuLinkList,*DLL;/定義讀者傳參結(jié)構(gòu)體struct ReadargDLL List; /定義鏈表ElemType e; /定義查找元素;/定義寫者傳參結(jié)構(gòu)體struct WriteargDLL List; /定義鏈表int add; /定義插入或刪除的位置ElemType e; /定義插入元素int Flag; /定義傳入標(biāo)示符（cr執(zhí)行插入操作，sc執(zhí)行刪除操作）;線程函數(shù)部分：WaitForSingleObject(h_Mutex,-1);/等待互斥量信號WaitForSingleObject(mutex,INFINITE);/等待信號量信號ReleaseMutex(h_Mutex);/釋放互斥量信號ReleaseSemaphore(mutex,1,NULL);/釋放信號量信號主函數(shù)部分：HANDLE hThreadsum;/定義線程句柄unsigned threadIDsum;/定義sum個線程h_Mutex=CreateMutex(NULL,FALSE,NULL); /創(chuàng)建互斥量h_Mutexmutex=CreateSemaphore(NULL,1,1,NULL); /創(chuàng)建信號量mutexReadarg *RA=new Readarg1;/創(chuàng)建讀者傳參變量RA0.List=L;/傳參變量賦值RA0.e=random(100);/傳參變量賦值Writearg *WA=new Writearg2;/創(chuàng)建寫者傳參變量WA0.List=L; /傳參變量賦值WA0.add=random(lsarea); /傳參變量賦值WA0.e=random(earea); /傳參變量賦值WA0.Flag=cr; /傳參變量賦值WA1.List=L; /傳參變量賦值WA1.add=random(lsarea); /傳參變量賦值WA1.e=0; /傳參變量賦值WA1.Flag=sc; /傳參變量賦值hThreadi=(HANDLE)_beginthreadex(NULL,0,ReaderThread,(void*)&RA0,0,&threadIDi);/創(chuàng)建線程函數(shù)WaitForSingleObject(hThreadi,INFINITE);/等待線程執(zhí)行完畢CloseHandle(hThreadi);/關(guān)閉線程句柄CloseHandle(h_Mutex);/關(guān)閉互斥量句柄CloseHandle(mutex);/關(guān)閉信號量句柄3.課程設(shè)計報告內(nèi)容3.1模塊功能此程序包含6個模塊，分別是初始化兼創(chuàng)建模塊，插入模塊，刪除模塊，清空模塊，查找模塊和打印模塊。先是有進程自動初始化并隨機產(chǎn)生一個鏈表，然后創(chuàng)建多個線程，線程同時進行插入結(jié)點，刪除指定位置結(jié)點，查找指定元素及打印鏈表操作，為清楚區(qū)分讀和寫的操作這里分出了兩個線程一個為讀者線程一個為寫者線程，前者具有查找指定元素功能，后者具有插入和刪除兼打印鏈表功能。對于所有的查找，插入和刪除數(shù)都是隨機產(chǎn)生的，更具有代表性。如下圖程序工作原理：開始運行程序初始化并創(chuàng)建鏈表讀者線程查找地址寫者線程刪除數(shù)據(jù)清空鏈表插入數(shù)據(jù)打印鏈表圖3.1 程序工作原理圖3.2詳細(xì)流程圖是否還有線程開始顯示選擇菜單初始化鏈表創(chuàng)建鏈表刪除數(shù)據(jù)插入數(shù)據(jù)查找地址清空控制臺信息1或2清空鏈表打印鏈表結(jié)束21是否圖3.2系統(tǒng)流程圖3.3實現(xiàn)思路說明第一步，構(gòu)建雙向鏈表的基本屬性。包括結(jié)點結(jié)構(gòu)體，鏈表結(jié)構(gòu)體，初始化及創(chuàng)建鏈表函數(shù)，插入函數(shù)，刪除函數(shù)，清空函數(shù)，查找函數(shù)，打印函數(shù)。第二步，創(chuàng)建三個線程分別進行插入、刪除和查找操作，主函數(shù)內(nèi)創(chuàng)建完鏈表后通過傳參結(jié)構(gòu)體向線程傳遞鏈表參數(shù)，在線程內(nèi)使用互斥量對鏈表的修改操作進行保護。運行過程中所有變量給定固定初始值，測試多線程同步的正確性。第三步，構(gòu)建兩個線程分別為讀者線程（執(zhí)行查找操作），寫者線程（執(zhí)行插入和刪除操作），所有變量使用隨機數(shù)定義，利用互斥量對讀者數(shù)的修改操作進行保護，利用信號量對鏈表的修改操作進行保護，從而實現(xiàn)讀讀共享，讀寫互斥，寫寫互斥的讀者寫者問題。并測試讀者優(yōu)先狀態(tài)下鏈表多線程操作的正確性。3.4程序清單#include/c語言標(biāo)準(zhǔn)輸入輸出頭文件#include/動態(tài)存儲分配函數(shù)頭文件#include/標(biāo)準(zhǔn)庫頭文件（malloc(),rand(),srand()等等）#include/包含用于和宏指令的作用聲明與螺紋和過程一起使用的C標(biāo)頭文件（線程的創(chuàng)建和終結(jié)等等）#include/win32頭文件#include/日期和時間頭文件void InitList(DLL L)/初始化一個空的雙向鏈表并創(chuàng)建鏈表void Insert(DLL L,int i,ElemType e) /在鏈表指定位置插入一個結(jié)點void Erase(DLL L,int i) /刪除指定位置的結(jié)點void Clear(DLL L) /刪除鏈表中所有結(jié)點DLN Find(DLL L,ElemType e) /查找鏈表中是否有指定的元素，若有，返回能夠訪問該結(jié)點的指針；若無，返回NULLvoid Print(DLL L) /打印當(dāng)前鏈表中的所有元素unsigned _stdcall ReaderThread(void *arg) /讀者線程(查找)unsigned _stdcall WriterThread(void *arg) /寫者線程（包括插入和刪除）3.5注釋宏定義和主函數(shù)內(nèi)部分代碼的詳細(xì)注釋已經(jīng)在前面章節(jié)闡述，下面主要為函數(shù)內(nèi)容注釋。/初始化一個空的雙向鏈表并創(chuàng)建鏈表void InitList(DLL L)int c,i,e;/定義三個整型變量c，i，eDLN p;/定義結(jié)點p/初始化操作L-head=0;/鏈表頭結(jié)點置零L-Length=0;/鏈表長度置零/創(chuàng)建操作printf(雙向鏈表初始化完畢n);srand(int)time(0);/隨機數(shù)時間種子設(shè)置c=random(lsarea);/變量c取范圍0Lsarea內(nèi)的隨機整數(shù)if(!c)printf(鏈表創(chuàng)建失??！n);exit(0);/ 異常處理，如果用戶未輸入結(jié)點個數(shù)則跳出該段代碼。elsep=(DuLNode*)malloc(sizeof(DuLNode); /p動態(tài)分配存儲空間if(!p)printf(結(jié)點p動態(tài)分配內(nèi)存失??！n);exit(0); /異常處理，如果節(jié)點p動態(tài)分配內(nèi)存失敗則跳出該段代碼。e=random(earea);/變量e取范圍0earea內(nèi)的隨機整數(shù)p-data=e;/將變量e的值送入結(jié)點p的數(shù)據(jù)域p-next=p-prior=p;/將結(jié)點p的前驅(qū)和后繼指針指向它自己L-head=p;/將p結(jié)點作為鏈表頭結(jié)點L-Length+;/鏈表長度加1/下面循環(huán)插入后續(xù)結(jié)點操作for(i=1;idata=e; /將變量e的值送入結(jié)點p的數(shù)據(jù)域p-next=L-head;/將結(jié)點p的后繼指針指向當(dāng)前鏈表的頭結(jié)點p-prior=L-head-prior;/結(jié)點p的前驅(qū)指針指向當(dāng)前鏈表的尾結(jié)點L-head-prior-next=p;/將當(dāng)前鏈表尾結(jié)點的后繼指針指向結(jié)點pL-head-prior=p;/將當(dāng)前鏈表頭節(jié)點的前驅(qū)指針指向結(jié)點pL-Length+;/鏈表長度加1/在鏈表指定位置插入一個結(jié)點void Insert(DLL L,int i,ElemType e)DLN p,q;/定義結(jié)點p，qint j;/定義整型變量j/下面判斷插入位置是否合法if(iL-Length+1)printf(對不起，您插入的位置超過了鏈表范圍！nn);elseprintf(恭喜你，插入成功！nn);p=(DuLNode*)malloc(sizeof(DuLNode); /p動態(tài)分配存儲空間if(!p)printf(結(jié)點p動態(tài)分配內(nèi)存失??！n);exit(0); / 異常處理，如果用戶未輸入結(jié)點個數(shù)則跳出該段代碼。q=L-head;/q指向當(dāng)前鏈表頭結(jié)點p-data=e;/將變量e的值送入結(jié)點p的數(shù)據(jù)域if(!L&i=1)/判斷鏈表為空并且插入第一個元素的情況p-next=p-prior=p; /將結(jié)點p的前驅(qū)和后繼指針指向它自己L-head=p; /將p結(jié)點作為鏈表頭結(jié)點L-Length+;/鏈表長度加1elseif(i=1|i=(L-Length+1)/判斷鏈表不為空在當(dāng)前表頭或表尾插入結(jié)點q=q-prior;/將q指向當(dāng)前鏈表尾結(jié)點p-next=q-next;/將p的后繼指針指向當(dāng)前鏈表頭結(jié)點p-prior=q;/將p的前驅(qū)指針指向當(dāng)前鏈表的尾結(jié)點q-next-prior=p;/將當(dāng)前鏈表頭結(jié)點的前驅(qū)指針指向結(jié)點pq-next=p;/將當(dāng)前鏈表尾結(jié)點的后繼指針指向結(jié)點pL-Length+;/鏈表長度加1if(i=1)/判斷插入位置是否是頭結(jié)點L-head=p;/將結(jié)點p置為鏈表頭結(jié)點else for(j=1;jnext;q-prior-next=p;/將當(dāng)前鏈表尾結(jié)點的后繼指針指向結(jié)點pp-prior=q-prior;/將結(jié)點p的前驅(qū)指針指向當(dāng)前鏈表的尾結(jié)點q-prior=p;/將當(dāng)前鏈表頭結(jié)點的前驅(qū)指針指向結(jié)點pp-next=q;/將結(jié)點p的后繼指針指向當(dāng)前鏈表頭結(jié)點L-Length+;/鏈表長度加1/刪除指定位置的結(jié)點void Erase(DLL L,int i)DLN q;/定義結(jié)點qint j;/定義整型變量jq=L-head;/ q指向當(dāng)前鏈表頭結(jié)點if(i(L-Length)|L-head=NULL)printf(對不起，您刪除的位置超過了鏈表范圍或者鏈表為空！nn);elseprintf(恭喜你，刪除成功！nn);for(j=1;jnext;q-prior-next=q-next;/將結(jié)點q前一個結(jié)點的后繼指針指向q的后一個結(jié)點q-next-prior=q-prior;/將結(jié)點q后一個結(jié)點的前驅(qū)指針指向q的前一個結(jié)點if(i=1)/判斷刪除的位置是否是鏈表頭結(jié)點L-head=q-next;/將當(dāng)前鏈表的頭結(jié)點指向第二個結(jié)點L-Length-;/鏈表長度減1if(L-Length=0)/判斷當(dāng)前鏈表是否為空L-head=NULL;/將當(dāng)前鏈表頭結(jié)點置空free(q);/釋放結(jié)點q的物理內(nèi)存/刪除鏈表中所有結(jié)點void Clear(DLL L)DLN q,temp;/定義結(jié)點q，tempint i,j;/定義整型變量i，ji=L-Length;/將鏈表長度賦給itemp=q=L-head;/結(jié)點q和temp指向當(dāng)前鏈表頭結(jié)點for(j=0;jnext;free(temp);temp=q;L-Length-;L-head=NULL;/鏈表頭結(jié)點置空printf(鏈表已清空！);/查找鏈表中是否有指定的元素，若有，返回能夠訪問該結(jié)點的指針；若無，返回NULLDLN Find(DLL L,ElemType e)DLN q;/定義結(jié)點qq=L-head;/將q指向鏈表頭結(jié)點if(!q)printf(鏈表為空！找不到元素%dnn,e);else/控制q指針后移逐個比較查找元素，當(dāng)知道最后一個元素并且未找到時退出循環(huán)while(q-data!=e&q-next!=L-head)q=q-next;/判斷是否找到指定元素if(q-data=e)printf(元素%d已找到！指針已返回！nn,e);return q;elseprintf(元素%d未找到！返回空nn,e);return NULL;/打印當(dāng)前鏈表中的所有元素void Print(DLL L)DLN p;/定義結(jié)點pif(L-head=NULL)printf(鏈表為空！);elsep=L-head;printf(%d,p-data);p=p-next;/當(dāng)p重新指到鏈表頭節(jié)點的時候跳出循環(huán)while(p!=L-head)printf(%4d,p-data);p=p-next;printf(n);printf(長度為：%dn,L-Length);printf(打印完畢！nn);/讀者線程(查找)unsigned _stdcall ReaderThread(void *arg)Readarg *RA;RA=(Readarg*)arg;int e;WaitForSingleObject(h_Mutex,-1);/等待互斥量信號readcount+;if(readcount=1)WaitForSingleObject(mutex,INFINITE);/等待信號量信號ReleaseMutex(h_Mutex);/釋放互斥量信號e=RA-e;printf(查找操作：讀者%d開始查找%dn,th_cz,e);Find(RA-List,e);th_cz+; /執(zhí)行完一遍查找讀者數(shù)加1WaitForSingleObject(h_Mutex,-1);readcount-;if(readcount=0)ReleaseSemaphore(mutex,1,NULL);/釋放信號量信號ReleaseMutex(h_Mutex);return 0;/寫者線程（包括插入和刪除）unsigned _stdcall WriterThread(void *arg)Writearg *WA;WA=(Writearg*)arg;int f,add,e;f=WA-Flag;add=WA-add;e=WA-e;if(f)WaitForSingleObject(mutex,INFINITE);printf(插入操作：寫者%d開始在第%d位置插入元素%dn,th_cr,add,e);Insert(WA-List,add,e);th_cr+;/執(zhí)行完一遍插入寫者數(shù)加1Print(WA-List);ReleaseSemaphore(mutex,1,NULL);elseWaitForSingleObject(mutex,INFINITE);printf(刪除操作：寫者%d開始刪除第%d個位置n,th_sc,add);Erase(WA-List,add);th_sc+;/執(zhí)行完一遍刪除寫者數(shù)加1Print(WA-List);ReleaseSemaphore(mutex,1,NULL);return 0;int main()char sr;printf(*n);printf( 1.讀者優(yōu)先n);printf( 2.退出窗口n);printf(*n);printf(請輸入你的選擇（1或者2）：);dosr=(char)getchar();while(sr!=1&sr!=2);/system(cls);if(sr=2)return 0;elseHANDLE hThreadsum;unsigned threadIDsum;int i,j,k,m;DLL L;L=(DuLinkList*)malloc(sizeof(DuLinkList);InitList(L);Print(L);h_Mutex=CreateMutex(NULL,FALSE,NULL); /創(chuàng)建互斥量h_Mutexmutex=CreateSemaphore(NULL,1,1,NULL); /創(chuàng)建信號量mutexsrand(int)time(0);for(i=0;isum;i+) j=random(3);/在0,1,2這三個數(shù)內(nèi)隨機取一個值決定該次循環(huán)執(zhí)行哪一個操作（0為查找，1為插入，2為刪除）if(j=0)Readarg *RA=new Readarg1;RA0.List=L;RA0.e=random(earea);/創(chuàng)建讀者線程hThreadi=(HANDLE)_beginthreadex(NULL,0,ReaderThread,(void*)&RA0,0,&threadIDi);elseWritearg *WA=new Writearg2;WA0.List=L;WA0.add=random(lsarea);WA0.e=random(earea);WA0.Flag=cr;WA1.List=L;WA1.add=random(lsarea);WA1.e=0;WA1.Flag=sc;/k=i;/m=k%4; if(j=1)/創(chuàng)建寫者線程（插入）hThreadi=(HANDLE)_beginthreadex(NULL,0,WriterThread,(void*)&WA0,0,&threadIDi);else/創(chuàng)建寫者線程（刪除