《操作系统课程设计报告(网络121朱正杰)》由会员分享，可在线阅读，更多相关《操作系统课程设计报告(网络121朱正杰)（23页珍藏版）》请在金锄头文库上搜索。
1、 操作系统课程设计报告题目： 线程安全型双向链表的实现 专 业： 网络工程 班 级： 网络121 学 号： 5 姓 名： 朱正杰 上海海事大学信息工程学院2014年 12月 15日目录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参考书目：211.课程设计任务描述与要求1.1任务描述编写一个线程安全的双向链表，所谓线程安全，就是该链表能够
2、实现多个线程同时正确的增删改链表结点，也就是能够实现对链表这个临界资源的保护。1.2任务要求需要实现的函数包括：（1） InitList函数：初始化一个空的双向链表，并初始化各个用于保护链表的信号量。（2） Insert函数：向链表指定位置插入一个结点。（3） Erase函数：删除指定位置的结点。（4） Clear函数：删除链表中的所有结点。（5） Find函数：查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回NULL。（6） Print函数：打印当前链表中的所有元素。完成该链表后，自己编写一个测试程序，生成多个线程同时读写该链表，验证链表执行是否正确，并给出测试报告。2
3、.系统总体结构描述与主要数据结构说明2.1系统总体结构描述系统总体结构设计的任务，是根据系统分析的逻辑模型设计应用软件系统的物理结构。系统物理模型必须符合逻辑模型，能够完成逻辑模型所规定的信息处理功能。这是物理设计的基本要求。系统应具有可修改性，即易读，易于进行查错、改错、可以根据环境的变化和用户的要求进行各种的改变和改进。系统是否具有可修改性，对于系统开发和维护影响极大。据统计，在系统生命周期中各阶段的应用软件费用及人力投入大体分布如下：系统开发：20%；系统维护：80%。由于程序功能简单，未用数据库辅助存储技术，本程序只供实现对双向链表的插入，删除，查找和打印等功能。2.2主要数据结构说明
4、宏定义部分：#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=; /线程运行总次数int th=0; /初始化当前线程总数int th_cz=1; /初始化当前查找线程总数int th_cr=1; /初始化当前插入线程总数int th_sc=1; /初始化当前删除线程总数HANDLE
5、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 Le
6、ngth; /定义链表长度DuLinkList,*DLL;/定义读者传参结构体struct ReadargDLL List; /定义链表ElemType e; /定义查找元素;/定义写者传参结构体struct WriteargDLL List; /定义链表int add; /定义插入或删除的位置ElemType e; /定义插入元素int Flag; /定义传入标示符（cr执行插入操作，sc执行删除操作）;线程函数部分：WaitForSingleObject(h_Mutex,-1);/等待互斥量信号WaitForSingleObject(mutex,INFINITE);/等待信号量信号Rele
7、aseMutex(h_Mutex);/释放互斥量信号ReleaseSemaphore(mutex,1,NULL);/释放信号量信号主函数部分：HANDLE hThreadsum;/定义线程句柄unsigned threadIDsum;/定义sum个线程h_Mutex=CreateMutex(NULL,FALSE,NULL); /创建互斥量h_Mutexmutex=CreateSemaphore(NULL,1,1,NULL); /创建信号量mutexReadarg *RA=new Readarg1;/创建读者传参变量RA0.List=L;/传参变量赋值RA0.e=random(100);/传参变
8、量赋值Writearg *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; /传参变量赋值hThreadi=(HANDLE)_beginthreadex(NULL,0,ReaderThread,(void*)&RA0,0,&threadIDi)
9、;/创建线程函数WaitForSingleObject(hThreadi,INFINITE);/等待线程执行完毕CloseHandle(hThreadi);/关闭线程句柄CloseHandle(h_Mutex);/关闭互斥量句柄CloseHandle(mutex);/关闭信号量句柄3.课程设计报告内容3.1模块功能此程序包含6个模块，分别是初始化兼创建模块，插入模块，删除模块，清空模块，查找模块和打印模块。先是有进程自动初始化并随机产生一个链表，然后创建多个线程，线程同时进行插入结点，删除指定位置结点，查找指定元素及打印链表操作，为清楚区分读和写的操作这里分出了两个线程一个为读者线程一个为写者
10、线程，前者具有查找指定元素功能，后者具有插入和删除兼打印链表功能。对于所有的查找，插入和删除数都是随机产生的，更具有代表性。如下图程序工作原理：开始运行程序初始化并创建链表读者线程查找地址写者线程删除数据清空链表插入数据打印链表图3.1 程序工作原理图3.2详细流程图是否还有线程开始显示选择菜单初始化链表创建链表删除数据插入数据查找地址清空控制台信息1或2清空链表打印链表结束21是否图3.2系统流程图3.3实现思路说明第一步，构建双向链表的基本属性。包括结点结构体，链表结构体，初始化及创建链表函数，插入函数，删除函数，清空函数，查找函数，打印函数。第二步，创建三个线程分别进行插入、删除和查找操
11、作，主函数内创建完链表后通过传参结构体向线程传递链表参数，在线程内使用互斥量对链表的修改操作进行保护。运行过程中所有变量给定固定初始值，测试多线程同步的正确性。第三步，构建两个线程分别为读者线程（执行查找操作），写者线程（执行插入和删除操作），所有变量使用随机数定义，利用互斥量对读者数的修改操作进行保护，利用信号量对链表的修改操作进行保护，从而实现读读共享，读写互斥，写写互斥的读者写者问题。并测试读者优先状态下链表多线程操作的正确性。3.4程序清单#include/c语言标准输入输出头文件#include/动态存储分配函数头文件#include/标准库头文件（malloc(),rand(),s
12、rand()等等）#include/包含用于和宏指令的作用声明与螺纹和过程一起使用的C标头文件（线程的创建和终结等等）#include/win32头文件#include/日期和时间头文件void InitList(DLL L)/初始化一个空的双向链表并创建链表void Insert(DLL L,int i,ElemType e) /在链表指定位置插入一个结点void Erase(DLL L,int i) /删除指定位置的结点void Clear(DLL L) /删除链表中所有结点DLN Find(DLL L,ElemType e) /查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；
13、若无，返回NULLvoid Print(DLL L) /打印当前链表中的所有元素unsigned _stdcall ReaderThread(void *arg) /读者线程(查找)unsigned _stdcall WriterThread(void *arg) /写者线程（包括插入和删除）3.5注释宏定义和主函数内部分代码的详细注释已经在前面章节阐述，下面主要为函数内容注释。/初始化一个空的双向链表并创建链表void InitList(DLL L)int c,i,e;/定义三个整型变量c，i，eDLN p;/定义结点p/初始化操作L-head=0;/链表头结点置零L-Length=0;/链表长度置零/创建操作printf(双向链表初始化完毕n);srand(int)time(0);/随机数时间种子设置c=random(lsarea);/变量c取范围0Lsarea内的随机整数if(!c)printf(链表创建失败！n);exit(0);/ 异常处理，如果用户未输入结点个数则跳出该段代码。elsep=(DuLNode*)malloc(sizeof(DuLNode); /p动态分配存储空间if(!p)printf(结点p动态分配内存失败！n);exit(0); /异常处理，如果节点p动态分配内存失败则跳出该段代码。e=random(earea);/变量
