操作系統(tǒng)課程設計報告(網絡121朱正杰).doc

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