搜索
操作系统课程设计报告题目：线程安全型双向链表的实现专业：网络工程班级：网络121学号：201210314005姓名：朱正杰上海海事大学信息工程学院2014年12月15日1目录1.课程设计任务描述与要求.................................11.1任务描述..........................................12.系统总体结构描述与主要数据结构说明.....................12.1系统总体结构描述..................................12.2主要数据结构说明..................................23.课程设计报告内容......................................53.1模块功能..........................................53.2详细流程图........................................63.3实现思路说明......................................73.4程序清单..........................................73.5注释..............................................84.总结.................................................19附录：.................................................19程序使用说明........................................19程序测试思想........................................20程序测试结果........................................20参考书目：.............................................2111.课程设计任务描述与要求1.1任务描述编写一个线程安全的双向链表，所谓线程安全，就是该链表能够实现多个线程同时正确的增删改链表结点，也就是能够实现对链表这个临界资源的保护。1.2任务要求需要实现的函数包括：（1）InitList函数：初始化一个空的双向链表，并初始化各个用于保护链表的信号量。（2）Insert函数：向链表指定位置插入一个结点。（3）Erase函数：删除指定位置的结点。（4）Clear函数：删除链表中的所有结点。（5）Find函数：查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回NULL。（6）Print函数：打印当前链表中的所有元素。完成该链表后，自己编写一个测试程序，生成多个线程同时读写该链表，验证链表执行是否正确，并给出测试报告。2.系统总体结构描述与主要数据结构说明2.1系统总体结构描述系统总体结构设计的任务，是根据系统分析的逻辑模型设计应用软件系统的物理结构。系统物理模型必须符合逻辑模型，能够完成逻辑模型所规定的信息处理功能。这是物理设计的基本要求。系统应具有可修改性，即易读，易于进行查错、改错、可以根据环境的变化和用户的要求进行各种的改变和改进。系统是否具有可修改性，对于系统开发和2维护影响极大。据统计，在系统生命周期中各阶段的应用软件费用及人力投入大体分布如下：系统开发：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;//定义双向链表结构体3typedefstructDuLinkList{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];//创建写者传参变量4WA[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);//关闭信号量句柄53.课程设计报告内容3.1模块功能此程序包含6个模块，分别是初始化兼创建模块，插入模块，删除模块，清空模块，查找模块和打印模块。先是有进程自动初始化并随机产生一个链表，然后创建多个线程，线程同时进行插入结点，删除指定位置结点，查找指定元素及打印链表操作，为清楚区分读和写的操作这里分出了两个线程一个为读者线程一个为写者线程，前者具有查找指定元素功能，后者具有插入和删除兼打印链表功能。对于所有的查找，插入和删除数都是随机产生的，更具有代表性。如下图程序工作原理：图3.1程序工作原理图开始运行程序初始化并创建链表读者线程查找地址写者线程删除数据清空链表插入数据打印链表63.2详细流程图图3.2系统流程图是否还有线程开始显示选择菜单初始化链表创建链表删除数据插入数据查找地址清空控制台信息1或2清空链表打印链表结束21是否73.3实现思路说明第一步，构建双向链表的基本属性。包括结点结构体，链表结构体，初始化及创建链表函数，插入函数，删除函数，清空函数，查找函数，打印函数。第二步，创建三个线程分别进行插入、删除和查找操作，主函数内创建完链表后通过传参结构体向线程传递链表参数，在线程内使用互斥量对链表的修改操作进行保护。运行过程中所有变量给定固定初始值，测试多线程同步的正确性。第三步，构建两个线程分别为读者线程（执行查找操作），写者线程（执行插入和删除操作），所有变量使用随机数定义，利用互斥量对读者数的修改操作进行保护，利用信号量对链表的修改操作进行保护，从而实现读读共享，读写互斥，写写互斥的读者写者问题。并测试读者优先状态下链表多线程操作的正确性。3.4程序清单#includestdio.h//c语言标准输入输出头文件#includemalloc.h//动态存储分配函数头文件#includestdlib.h//标准库头文件（malloc(),rand(),srand()等等）#includeprocess.h//包含用于和宏指令的作用声明与螺纹和过程一起使用的C标头文件（线程的创建和终结等等）#includewindows.h//win32头文件#includetime.h//日期和时间头文件voidInitList(DLLL)//初始化一个空的双向链表并创建链表voidInsert(DLLL,inti,ElemTypee)//在链表指定位置插入一个结点voidErase(DLLL,inti)//删除指定位置的结点voidClear(DLLL)//删除链表中所有结点DLNFind(DLLL,ElemTypee)//查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回NULL8voidPrint(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动态分配内存失败则跳出该段代码。}9e=random(earea);//变量e取范围0~earea内的随机整数p-data=e;//将变量e的值送入结点p的数据域p-next=p-p