操作系統課程設計報告題目：線程安全型雙向鏈表的實現專業(yè)：網絡工程班級：網絡121學號：名：上海海事大學信息工程學院2014年12月15日目錄TOC\o"1-5"\h\z\o"CurrentDocument"課程設計任務描述與要求11?1任務描述1\o"CurrentDocument"系統總體結構描述與主要數據結構說明12.1系統總體結構描述12.2主要數據結構說明2\o"CurrentDocument"課程設計報告內容53?1模塊功能53.2詳細流程圖63.3實現思路說明73.4程序清單73.5注釋8\o"CurrentDocument"總結19\o"CurrentDocument"附錄:19程序使用說明19程序測試思想20程序測試結果20參考書目:21課程設計任務描述與要求1.1任務描述編寫一個線程安全的雙向鏈表，所謂線程安全，就是該鏈表能夠實現多個線程同時正確的增刪改鏈表結點，也就是能夠實現對鏈表這個臨界資源的保護。1.2任務要求需要實現的函數包括：（1）InitList函數：初始化一個空的雙向鏈表，并初始化各個用于保護鏈表的信號量。（2）Insert函數：向鏈表指定位置插入一個結點。（3）Erase函數：刪除指定位置的結點。（4）Clear函數：刪除鏈表中的所有結點。（5）Find函數：查找鏈表中是否有指定的元素，若有，返回能夠訪問該結點的指針；若無，返回NULL。（6）Print函數：打印當前鏈表中的所有元素。完成該鏈表后，自己編寫一個測試程序，生成多個線程同時讀寫該鏈表，驗證鏈表執(zhí)行是否正確，并給出測試報告。系統總體結構描述與主要數據結構說明2.1系統總體結構描述系統總體結構設計的任務，是根據系統分析的邏輯模型設計應用軟件系統的物理結構。系統物理模型必須符合邏輯模型，能夠完成邏輯模型所規(guī)定的信息處理功能。這是物理設計的基本要求。系統應具有可修改性，即易讀，易于進行查錯、改錯、可以根據環(huán)境的變化和用戶的要求進行各種的改變和改進。系統是否具有可修改性，對于系統開發(fā)和維護影響極大。據統計，在系統生命周期中各階段的應用軟件費用及人力投入大體分布如下：系統開發(fā)：20%；系統維護：80%。由于程序功能簡單，未用數據庫輔助存儲技術，本程序只供實現對雙向鏈表的插入，刪除，查找和打印等功能。2.2主要數據結構說明宏定義部分：#definerandom(x)(rand()%x)//產生隨機數#definecr1//1標識為插入#definesc0//0標識為刪除volatileintreadcount=0;//讀者數目constintlsarea=10000;〃鏈表大小隨機數constintearea=10000;//元素范圍隨機數constintsum=100000;//線程運行總次數intth=0;//初始化當前線程總數intth_cz=1;〃初始化當前查找線程總數intth_cr=1;//初始化當前插入線程總數intth_sc=1;//初始化當前刪除線程總數HANDLEh_Mutex;//控制讀者數量readcount的互斥訪問量HANDLEmutex;//控制讀寫互斥，寫寫互斥的信號量typedefintElemType;//定義ElemType為int類型的別名typedefstructDuLNode*PNode;〃結點指針〃定義結點結構體typedefstructDuLNode(ElemTypedata;〃定義數據域PNodeprior;//定義前驅指針PNodenext;//定義后繼指針}DuLNode,*DLN;//定義雙向鏈表結構體typedefstructDuLinkList{DLNhead;//定義頭結點intLength;//定義鏈表長度}DuLinkList,*DLL;//定義讀者傳參結構體structReadarg(DLLList;〃定義鏈表ElemTypee;//定義查找元素};//定義寫者傳參結構體structWritearg(DLLList;//定義鏈表intadd;//定義插入或刪除的位置ElemTypee;//定義插入元素intFlag;//定義傳入標示符(cr執(zhí)行插入操作，sc執(zhí)行刪除操作)};線程函數部分：WaitForSingleObject(h_Mutex,-1);//等待互斥量信號WaitForSingleObject(mutex,INFINITE);//等待信號量信號ReleaseMutex(h_Mutex);//釋放互斥量信號ReleaseSemaphore(mutex,1,NULL);//釋放信號量信號主函數部分：HANDLEhThread[sum];//定義線程句柄unsignedthreadID[sum];//定義sum個線程h_Mutex=CreateMutex(NULL,FALSE,NULL);〃創(chuàng)建互斥量h_Mutexmutex二CreateSemaphore(NULL,1,1,NULL);//創(chuàng)建信號量mutexReadarg*RA=newReadarg[1];//創(chuàng)建讀者傳參變量RA[0].List=L;//傳參變量賦值RA[0].e=random(100);//傳參變量賦值Writearg*WA=newWritearg[2];//創(chuàng)建寫者傳參變量WA[0].List=L;//傳參變量賦值WA[0].add=random(lsarea);//傳參變量賦值WA[0].e=random(earea);//傳參變量賦值WA[0].Flag=cr;//傳參變量賦值WA[1].List=L;//傳參變量賦值WA[1].add=random(lsarea);//傳參變量賦值WA[1].e=0;//傳參變量賦值WA[1].Flag=sc;//傳參變量賦值hThread[i]=(HANDLE)_beginthreadex(NULL,0,ReaderThread,(void*)&RA[0],0,&threadID[i]);//創(chuàng)建線程函數WaitForSingleObject(hThread[i],INFINITE);//等待線程執(zhí)行完畢CloseHandle(hThread[i]);//關閉線程句柄CloseHandle(h_Mutex);//關閉互斥量句柄CloseHandle(mutex);//關閉信號量句柄課程設計報告內容3.1模塊功能此程序包含6個模塊，分別是初始化兼創(chuàng)建模塊，插入模塊，刪除模塊，清空模塊，查找模塊和打印模塊。先是有進程自動初始化并隨機產生一個鏈表，然后創(chuàng)建多個線程，線程同時進行插入結點，刪除指定位置結點，查找指定元素及打印鏈表操作，為清楚區(qū)分讀和寫的操作這里分出了兩個線程一個為讀者線程一個為寫者線程，前者具有查找指定元素功能，后者具有插入和刪除兼打印鏈表功能。對于所有的查找，插入和刪除數都是隨機產生的，更具有代表性。如下圖程序工作原理：圖3.1程序工作原理圖顯示選擇菜單1或2打印鏈表是否還有線程結束21是否清空鏈表初始化鏈表創(chuàng)建鏈表清空控制臺信息查找地址插數據刪除數據圖3.2系統流程圖3.3實現思路說明第一步，構建雙向鏈表的基本屬性。包括結點結構體，鏈表結構體，初始化及創(chuàng)建鏈表函數，插入函數，刪除函數，清空函數，查找函數，打印函數。第二步，創(chuàng)建三個線程分別進行插入、刪除和查找操作，主函數內創(chuàng)建完鏈表后通過傳參結構體向線程傳遞鏈表參數，在線程內使用互斥量對鏈表的修改操作進行保護。運行過程中所有變量給定固定初始值，測試多線程同步的正確性。第三步，構建兩個線程分別為讀者線程(執(zhí)行查找操作)，寫者線程(執(zhí)行插入和刪除操作)，所有變量使用隨機數定義，利用互斥量對讀者數的修改操作進行保護，利用信號量對鏈表的修改操作進行保護，從而實現讀讀共享，讀寫互斥，寫寫互斥的讀者寫者問題。并測試讀者優(yōu)先狀態(tài)下鏈表多線程操作的正確性。3.4程序清單#include<stdio.h>//c語言標準輸入輸出頭文件#include<malloc.h>//動態(tài)存儲分配函數頭文件#include<stdlib.h>//標準庫頭文件(malloc(),rand(),srand()等等)#include<process.h>//包含用于和宏指令的作用聲明與螺紋和過程一起使用的C標頭文件(線程的創(chuàng)建和終結等等)#include<windows.h>//win32頭文件#include<time.h>//日期和時間頭文件voidInitList(DLLL)//初始化一個空的雙向鏈表并創(chuàng)建鏈表voidInsert(DLLL,inti,ElemTypee)〃在鏈表指定位置插入一個結點voidErase(DLLL,inti)//刪除指定位置的結點voidClear(DLLL)//刪除鏈表中所有結點DLNFind(DLLL,ElemTypee)//查找鏈表中是否有指定的元素，若有，返回能夠訪問該結點的指針；若無，返回NULLvoidPrint(DLLL)//打印當前鏈表中的所有元素unsigned__stdcallReaderThread(void*arg)//讀者線程(查找)unsigned__stdcallWriterThread(void*arg)//寫者線程(包括插入和刪除)3.5注釋宏定義和主函數內部分代碼的詳細注釋已經在前面章節(jié)闡述，下面主要為函數內容注釋?！ǔ跏蓟粋€空的雙向鏈表并創(chuàng)建鏈表voidInitList(DLLL)(intc,i,e;//定義三個整型變量c，i，eDLNp;//定義結點p〃初始化操作L->head=0;//鏈表頭結點置零L->Length=0;//鏈表長度置零//創(chuàng)建操作printf("雙向鏈表初始化完畢\n");srand((int)time(0));//隨機數時間種子設置c=random(lsarea);//變量c取范圍0~Lsarea內的隨機整數if(!c){printf("鏈表創(chuàng)建失??！\n");exit(0);//異常處理，如果用戶未輸入結點個數則跳出該段代碼。}else(p=(DuLNode*)malloc(sizeof(DuLNode));//p動態(tài)分配存儲空間if(!p)(printf("結點p動態(tài)分配內存失敗！\n");exit(0);〃異常處理，如果節(jié)點p動態(tài)分配內存失敗則跳出該段代碼。e=random(earea);//變量e取范圍0~earea內的隨機整數p->data=e;//將變量e的值送入結點p的數據域p->next=p->prior=p;//將結點p的前驅和后繼指針指向它自己L->head=p;//將p結點作為鏈表頭結點L->Length++;//鏈表長度加1〃下面循環(huán)插入后續(xù)結點操作for(i=1;i<c;i++){p=(DuLNode*)malloc(sizeof(DuLNode));//p動態(tài)分配存儲空間if(!p){printf("結點p動態(tài)分配內存失??！\n");exit(0);//異常處理，如果用戶未輸入結點個數則跳出該段代碼。}e=random(earea);//變量e取范圍0~earea內的隨機整數p->data=e;//將變量e的值送入結點p的數據域p->next=L->head;//將結點p的后繼指針指向當前鏈表的頭結點p->prior=L->head->prior;//結點p的前驅指針指向當前鏈表的尾結點L->head->prior->next=p;//將當前鏈表尾結點的后繼指針指向結點pL->head->prior=p;//將當前鏈表頭節(jié)點的前驅指針指向結點pL->Length++;//鏈表長度加1}}}〃在鏈表指定位置插入一個結點voidInsert(DLLL,inti,ElemTypee)(DLNp,q;//定義結點p，qintj;//定義整型變量j〃下面判斷插入位置是否合法if(i<1||i>L->Length+1){printf("對不起，您插入的位置超過了鏈表范圍！\n\n");}else(printf("恭喜你，插入成功！\n\n");p=(DuLNode*)malloc(sizeof(DuLNode));//p動態(tài)分配存儲空間if(!p){printf("結點p動態(tài)分配內存失??！\n");exit(0);〃異常處理，如果用戶未輸入結點個數則跳出該段代碼。}q=L->head;//q指向當前鏈表頭結點p->data=e;//將變量e的值送入結點p的數據域if(!L&&i==1){//判斷鏈表為空并且插入第一個元素的情況p->next=p->prior=p;//將結點p的前驅和后繼指針指向它自己L->head=p;〃將p結點作為鏈表頭結點L->Length++;//鏈表長度加1}else(if(i==1||i==(L->Length+1))(//判斷鏈表不為空在當前表頭或表尾插入結點q=q->prior;//將q指向當前鏈表尾結點p->next=q->next;//將p的后繼指針指向當前鏈表頭結點p->prior=q;//將p的前驅指針指向當前鏈表的尾結點q->next->prior=p;//將當前鏈表頭結點的前驅指針指向結點pq->next=p;//將當前鏈表尾結點的后繼指針指向結點pL->Length++;//鏈表長度加1if(i==1)//判斷插入位置是否是頭結點L->head=p;//將結點p置為鏈表頭結點}else(for(j=1;j<i;j++){//循環(huán)定位插入位置q=q->next;}q->prior->next=p;//將當前鏈表尾結點的后繼指針指向結點pp->prior=q->prior;//將結點p的前驅指針指向當前鏈表的尾結點q->prior=p;//將當前鏈表頭結點的前驅指針指向結點pp->next=q;//將結點p的后繼指針指向當前鏈表頭結點L->Length++;//鏈表長度加1}}}}//刪除指定位置的結點voidErase(DLLL,inti)(DLNq;//定義結點qintj;//定義整型變量jq=L->head;//q指向當前鏈表頭結點if(i<1||i>(L->Length)||L->head==NULL)(printf(-對不起，您刪除的位置超過了鏈表范圍或者鏈表為空！\n\n〃)；}else(printf("恭喜你，刪除成功！\n\n");for(j=1;j<i;j++)(//循環(huán)定位刪除位置q=q->next;}q->prior->next=q->next;//將結點q前一個結點的后繼指針指向q的后一個結點q->next->prior=q->prior;//將結點q后一個結點的前驅指針指向q的前一個結點if(i==1)(//判斷刪除的位置是否是鏈表頭結點L->head=q->next;//將當前鏈表的頭結點指向第二個結點}L->Length--;//鏈表長度減1if(L->Length==0)(//判斷當前鏈表是否為空L->head=NULL;//將當前鏈表頭結點置空}free(q);//釋放結點q的物理內存}}//刪除鏈表中所有結點voidClear(DLLL)(DLNq,temp;//定義結點q，tempinti,j;//定義整型變量i，ji=L->Length;//將鏈表長度賦給itemp=q=L->head;//結點q和temp指向當前鏈表頭結點for(j=0;j<i;j++){//循環(huán)釋放每一個結點q=q->next;free(temp);temp=q;L->Length--;}L->head=NULL;//鏈表頭結點置空printf("鏈表已清空！");}〃查找鏈表中是否有指定的元素，若有，返回能夠訪問該結點的指針；若無，返回NULLDLNFind(DLLL,ElemTypee)(DLNq;//定義結點qq=L->head;//將q指向鏈表頭結點if(!q){printf("鏈表為空！找不到元素%d\n\n",e);}else(〃控制q指針后移逐個比較查找元素，當知道最后一個元素并且未找到時退出循環(huán)while(q->data!=e&&q->next!=L->head)(q=q->next;}〃判斷是否找到指定元素if(q->data==e)(printf("元素%d已找到！指針已返回！\n\n",e);returnq;}else(printf("元素%d未找到！返回空\n\n",e);returnNULL;}}}//打印當前鏈表中的所有元素voidPrint(DLLL)(DLNp;//定義結點pif(L->head==NULL)(printf("鏈表為空！");}else(p=L->head;printf(〃％d〃,p->data);p=p->next;〃當p重新指到鏈表頭節(jié)點的時候跳出循環(huán)while(p!=L->head)(printf("%4d",p->data);p=p->next;}}printf("\n");printf(〃長度為：％d\n”,L->Length);printf("打印完畢！\n\n");〃讀者線程(查找)unsigned__stdcallReaderThread(void*arg){Readarg*RA;RA=(Readarg*)arg;inte;WaitForSingleObject(h_Mutex,-1);//等待互斥量信號readcount++;if(readcount==1)(WaitForSingleObject(mutex,INFINITE);//等待信號量信號}ReleaseMutex(h_Mutex);//釋放互斥量信號e=RA->e;printf("查找操作：讀者%d開始查找%d\n”,th_cz,e);Find(RA->List,e);th_cz++;//執(zhí)行完一遍查找讀者數加1WaitForSingleObject(h_Mutex,-1);readcount--;if(readcount==0)(ReleaseSemaphore(mutex,1,NULL);//釋放信號量信號}ReleaseMutex(h_Mutex);return0;}〃寫者線程(包括插入和刪除)unsigned__stdcallWriterThread(void*arg){Writearg*WA;WA=(Writearg*)arg;intf,add,e;f=WA->Flag;add=WA->add;e=WA->e;if(f)(WaitForSingleObject(mutex,INFINITE);printf(-插入操作：寫者%d開始在第%d位置插入元素%d\n",th_cr,add,e);Insert(WA->List,add,e);th_cr++;//執(zhí)行完一遍插入寫者數加1Print(WA->List);ReleaseSemaphore(mutex,1,NULL);}else(WaitForSingleObject(mutex,INFINITE);printf("刪除操作：寫者%^開始刪除第％d個位置\n”,th_sc,add);Erase(WA->List,add);th_sc++;//執(zhí)行完一遍刪除寫者數加1Print(WA->List);ReleaseSemaphore(mutex,1,NULL);}return0;}intmain()(charsr;printf("**************************\n");printf("1.讀者優(yōu)先\n");printf("2.退出窗口\n〃)；printf("**************************\n");printf("請輸入你的選擇(1或者2)：");do(sr=(char)getchar();}while(sr!='1'&&sr!='2');//system("cls");if(sr=='2')return0;else(HANDLEhThread[sum];unsignedthreadID[sum];inti,j,k,m;DLLL;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;i<sum;i++)(j=random(3);//在0,1,2這三個數內隨機取一個值決定該次循環(huán)執(zhí)行哪一個操作(0為查找，1為插入，2為刪除)if(j==0)(Readarg*RA=newReadarg[1];RA[0].List=L;RA[0].e=random(earea);//創(chuàng)建讀者線程hThread[i]=(HANDLE)_beginthreadex(NULL,0,ReaderThread,(void*)&RA[0],0,&threadID[i]);}else(Writearg*WA=newWritearg[2];WA[0].List=L;WA[0].add=random(lsarea);WA[0].e=random(earea);WA[0].Flag=cr;WA[1].List=L;WA[1].add=random(lsarea);WA[1].e=0;WA[1].Flag=sc;//k=i;//m=k%4;if(j==1)(//創(chuàng)建寫者線程(插入)hThread[i]=(HANDLE)_beginthreadex(NULL,0,WriterThread,(void*)&WA[0],0,&threadID[i]);}else//創(chuàng)建寫者線程(刪除)hThread[i]=(HANDLE)_beginthreadex(NULL,0,WriterThread,(void*)&WA[1],0,&threadID[i]);}WaitForSingleObject(hThread[i],INFINITE);//循環(huán)內wait操作，及時收回線程}for(i=0;i<sum;i++)(CloseHandle(hThread[i]);}CloseHandle(h_Mutex);CloseHandle(mutex);th=(th_cz+th_cr+th_sc)-3;//統計總線程數printf("當前查找讀者人數為：％d；當前插入寫者人數為：％d；當前刪除寫者人數為：%d；當前總人數為：％d\n〃，th_czT,th_crT,th_scT,th);Clear(L);Print(L);printf(-所有線程都執(zhí)行完畢了。\n〃)；}return0;}總結通過本次課設的編寫，熟練掌握了雙向鏈表的基本操作，熟悉了線程創(chuàng)建和傳參的基本操作，對于線程同步和調度機