操作系统课程设计报告(网络121朱正杰).doc

操作系统课程设计报告题目： 线程安全型双向链表的实现 专 业： 网络工程 班 级： 网络121 学 号： 201210314005 姓 名： 朱正杰 上海海事大学信息工程学院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任务描述编写一个线程安全的双向链表，所谓线程安全，就是该链表能够实现多个线程同时正确的增删改链表结点，也就是能够实现对链表这个临界资源的保护。1.2任务要求需要实现的函数包括：（1） InitList函数：初始化一个空的双向链表，并初始化各个用于保护链表的信号量。（2） Insert函数：向链表指定位置插入一个结点。（3） Erase函数：删除指定位置的结点。（4） Clear函数：删除链表中的所有结点。（5） Find函数：查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回NULL。（6） Print函数：打印当前链表中的所有元素。完成该链表后，自己编写一个测试程序，生成多个线程同时读写该链表，验证链表执行是否正确，并给出测试报告。2.系统总体结构描述与主要数据结构说明2.1系统总体结构描述系统总体结构设计的任务，是根据系统分析的逻辑模型设计应用软件系统的物理结构。系统物理模型必须符合逻辑模型，能够完成逻辑模型所规定的信息处理功能。这是物理设计的基本要求。系统应具有可修改性，即易读，易于进行查错、改错、可以根据环境的变化和用户的要求进行各种的改变和改进。系统是否具有可修改性，对于系统开发和维护影响极大。据统计，在系统生命周期中各阶段的应用软件费用及人力投入大体分布如下：系统开发：20%；系统维护：80%。由于程序功能简单，未用数据库辅助存储技术，本程序只供实现对双向链表的插入，删除，查找和打印等功能。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执行插入操作，sc执行删除操作）;线程函数部分：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); /创建互斥量h_Mutexmutex=CreateSemaphore(NULL,1,1,NULL); /创建信号量mutexReadarg *RA=new Readarg1;/创建读者传参变量RA0.List=L;/传参变量赋值RA0.e=random(100);/传参变量赋值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);/创建线程函数WaitForSingleObject(hThreadi,INFINITE);/等待线程执行完毕CloseHandle(hThreadi);/关闭线程句柄CloseHandle(h_Mutex);/关闭互斥量句柄CloseHandle(mutex);/关闭信号量句柄3.课程设计报告内容3.1模块功能此程序包含6个模块，分别是初始化兼创建模块，插入模块，删除模块，清空模块，查找模块和打印模块。先是有进程自动初始化并随机产生一个链表，然后创建多个线程，线程同时进行插入结点，删除指定位置结点，查找指定元素及打印链表操作，为清楚区分读和写的操作这里分出了两个线程一个为读者线程一个为写者线程，前者具有查找指定元素功能，后者具有插入和删除兼打印链表功能。对于所有的查找，插入和删除数都是随机产生的，更具有代表性。如下图程序工作原理：开始运行程序初始化并创建链表读者线程查找地址写者线程删除数据清空链表插入数据打印链表图3.1 程序工作原理图3.2详细流程图是否还有线程开始显示选择菜单初始化链表创建链表删除数据插入数据查找地址清空控制台信息1或2清空链表打印链表结束21是否图3.2系统流程图3.3实现思路说明第一步，构建双向链表的基本属性。包括结点结构体，链表结构体，初始化及创建链表函数，插入函数，删除函数，清空函数，查找函数，打印函数。第二步，创建三个线程分别进行插入、删除和查找操作，主函数内创建完链表后通过传参结构体向线程传递链表参数，在线程内使用互斥量对链表的修改操作进行保护。运行过程中所有变量给定固定初始值，测试多线程同步的正确性。第三步，构建两个线程分别为读者线程（执行查找操作），写者线程（执行插入和删除操作），所有变量使用随机数定义，利用互斥量对读者数的修改操作进行保护，利用信号量对链表的修改操作进行保护，从而实现读读共享，读写互斥，写写互斥的读者写者问题。并测试读者优先状态下链表多线程操作的正确性。3.4程序清单#include/c语言标准输入输出头文件#include/动态存储分配函数头文件#include/标准库头文件（malloc(),rand(),srand()等等）#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) /查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回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);/变量e取范围0earea内的随机整数p-data=e;/将变量e的值送入结点p的数据域p-next=p-prior=p;/将结点p的前驱和后继指针指向它自己L-head=p;/将p结点作为链表头结点L-Length+;/链表长度加1/下面循环插入后续结点操作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;/将当前链表头节点的前驱指针指向结点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动态分配存储空间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+;/链表长度加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指针后移逐个比较查找元素，当知道最后一个元素并且未找到时退出循环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重新指到链表头节点的时候跳出循环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+; /执行完一遍查找读者数加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+;/执行完一遍插入写者数加1Print(WA-List);ReleaseSemaphore(mutex,1,NULL);elseWaitForSingleObject(mutex,INFINITE);printf(删除操作：写者%d开始删除第%d个位置n,th_sc,add);Erase(WA-List,add);th_sc+;/执行完一遍删除写者数加1Print(WA-List);ReleaseSemaphore(mutex,1,NULL);return 0;int main()char sr;printf(*n);printf( 1.读者优先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); /创建互斥量h_Mutexmutex=CreateSemaphore(NULL,1,1,NULL); /创建信号量mutexsrand(int)time(0);for(i=0;isum;i+) j=random(3);/在0,1,2这三个数内随机取一个值决定该次循环执行哪一个操作（0为查找，1为插入，2为删除）if(j=0)Readarg *RA=new Readarg1;RA0.List=L;RA0.e=random(earea);/创建读者线程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)/创建写者线程（插入）hThreadi=(HANDLE)_beginthreadex(NULL,0,WriterThread,(void*)&WA0,0,&threadIDi);else/创建写者线程（删除