操作系统课程设计报告

操作系统课程设计报告题目：线程安全型双向链表的实现专业：网络工程班级：网络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函数：打印当前链表中的所有元素。完成该链表后，自己编写一个测试程序，生成多个线程同时读写该链表，验证链表执行是否正确，并给出测试报告。系统总体结构描述与主要数据结构说明2.1系统总体结构描述系统总体结构设计的任务，是根据系统分析的逻辑模型设计应用软件系统的物理结构。系统物理模型必须符合逻辑模型，能够完成逻辑模型所规定的信息处理功能。这是物理设计的基本要求。系统应具有可修改性，即易读，易于进行查错、改错、可以根据环境的变化和用户的要求进行各种的改变和改进。系统是否具有可修改性，对于系统开发和维护影响极大。据统计，在系统生命周期中各阶段的应用软件费用及人力投入大体分布如下：系统开发：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执行插入操作，sc执行删除操作)};线程函数部分：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);〃创建互斥量h_Mutexmutex二CreateSemaphore(NULL,1,1,NULL);//创建信号量mutexReadarg*RA=newReadarg[1];//创建读者传参变量RA[0].List=L;//传参变量赋值RA[0].e=random(100);//传参变量赋值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;//传参变量赋值hThread[i]=(HANDLE)_beginthreadex(NULL,0,ReaderThread,(void*)&RA[0],0,&threadID[i]);//创建线程函数WaitForSingleObject(hThread[i],INFINITE);//等待线程执行完毕CloseHandle(hThread[i]);//关闭线程句柄CloseHandle(h_Mutex);//关闭互斥量句柄CloseHandle(mutex);//关闭信号量句柄课程设计报告内容3.1模块功能此程序包含6个模块，分别是初始化兼创建模块，插入模块，删除模块，清空模块，查找模块和打印模块。先是有进程自动初始化并随机产生一个链表，然后创建多个线程，线程同时进行插入结点，删除指定位置结点，查找指定元素及打印链表操作，为清楚区分读和写的操作这里分出了两个线程一个为读者线程一个为写者线程，前者具有查找指定元素功能，后者具有插入和删除兼打印链表功能。对于所有的查找，插入和删除数都是随机产生的，更具有代表性。如下图程序工作原理：图3.1程序工作原理图显示选择菜单1或2打印链表是否还有线程结束21是否清空链表初始化链表创建链表清空控制台信息查找地址插数据删除数据图3.2系统流程图3.3实现思路说明第一步，构建双向链表的基本属性。包括结点结构体，链表结构体，初始化及创建链表函数，插入函数，删除函数，清空函数，查找函数，打印函数。第二步，创建三个线程分别进行插入、删除和查找操作，主函数内创建完链表后通过传参结构体向线程传递链表参数，在线程内使用互斥量对链表的修改操作进行保护。运行过程中所有变量给定固定初始值，测试多线程同步的正确性。第三步，构建两个线程分别为读者线程(执行查找操作)，写者线程(执行插入和删除操作)，所有变量使用随机数定义，利用互斥量对读者数的修改操作进行保护，利用信号量对链表的修改操作进行保护，从而实现读读共享，读写互斥，写写互斥的读者写者问题。并测试读者优先状态下链表多线程操作的正确性。3.4程序清单#include<stdio.h>//c语言标准输入输出头文件#include<malloc.h>//动态存储分配函数头文件#include<stdlib.h>//标准库头文件(malloc(),rand(),srand()等等)#include<process.h>//包含用于和宏指令的作用声明与螺纹和过程一起使用的C标头文件(线程的创建和终结等等)#include<windows.h>//win32头文件#include<time.h>//日期和时间头文件voidInitList(DLLL)//初始化一个空的双向链表并创建链表voidInsert(DLLL,inti,ElemTypee)〃在链表指定位置插入一个结点voidErase(DLLL,inti)//删除指定位置的结点voidClear(DLLL)//删除链表中所有结点DLNFind(DLLL,ElemTypee)//查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回NULLvoidPrint(DLLL)//打印当前链表中的所有元素unsigned__stdcallReaderThread(void*arg)//读者线程(查找)unsigned__stdcallWriterThread(void*arg)//写者线程(包括插入和删除)3.5注释宏定义和主函数内部分代码的详细注释已经在前面章节阐述，下面主要为函数内容注释。〃初始化一个空的双向链表并创建链表voidInitList(DLLL)(intc,i,e;//定义三个整型变量c，i，eDLNp;//定义结点p〃初始化操作L->head=0;//链表头结点置零L->Length=0;//链表长度置零//创建操作printf("双向链表初始化完毕\n");srand((int)time(0));//随机数时间种子设置c=random(lsarea);//变量c取范围0~Lsarea内的随机整数if(!c){printf("链表创建失败！\n");exit(0);//异常处理，如果用户未输入结点个数则跳出该段代码。}else(p=(DuLNode*)malloc(sizeof(DuLNode));//p动态分配存储空间if(!p)(printf("结点p动态分配内存失败！\n");exit(0);〃异常处理，如果节点p动态分配内存失败则跳出该段代码。e=random(earea);//变量e取范围0~earea内的随机整数p->data=e;//将变量e的值送入结点p的数据域p->next=p->prior=p;//将结点p的前驱和后继指针指向它自己L->head=p;//将p结点作为链表头结点L->Length++;//链表长度加1〃下面循环插入后续结点操作for(i=1;i<c;i++){p=(DuLNode*)malloc(sizeof(DuLNode));//p动态分配存储空间if(!p){printf("结点p动态分配内存失败！\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;//将当前链表头节点的前驱指针指向结点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动态分配存储空间if(!p){printf("结点p动态分配内存失败！\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++){//循环定位插入位置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++)(//循环定位删除位置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++){//循环释放每一个结点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指针后移逐个比较查找元素，当知道最后一个元素并且未找到时退出循环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重新指到链表头节点的时候跳出循环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++;//执行完一遍查找读者数加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++;//执行完一遍插入写者数加1Print(WA->List);ReleaseSemaphore(mutex,1,NULL);}else(WaitForSingleObject(mutex,INFINITE);printf("删除操作：写者%^开始删除第％d个位置\n”,th_sc,add);Erase(WA->List,add);th_sc++;//执行完一遍删除写者数加1Print(WA->List);ReleaseSemaphore(mutex,1,NULL);}return0;}intmain()(charsr;printf("**************************\n");printf("1.读者优先\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);〃创建互斥量h_Mutexmutex二CreateSemaphore(NULL,1,1,NULL);//创建信号量mutexsrand((int)time(0));for(i=0;i<sum;i++)(j=random(3);//在0,1,2这三个数内随机取一个值决定该次循环执行哪一个操作(0为查找，1为插入，2为删除)if(j==0)(Readarg*RA=newReadarg[1];RA[0].List=L;RA[0].e=random(earea);//创建读者线程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)(//创建写者线程(插入)hThread[i]=(HANDLE)_beginthreadex(NULL,0,WriterThread,(void*)&WA[0],0,&threadID[i]);}else//创建写者线程(删除)hThread[i]=(HANDLE)_beginthreadex(NULL,0,WriterThread,(void*)&WA[1],0,&threadID[i]);}WaitForSingleObject(hThread[i],INFINITE);//循环内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(-所有线程都执行完毕了。\n〃)；}return0;}总结通过本次课设的编写，熟练掌握了双向链表的基本操作，熟悉了线程创建和传参的基本操作，对于线程同步和调度机