操作系统课程设计报告（网络121朱正杰）

操作系统课程设计报告

题目： 线程安全型双向链表的实现

专 业： 网络工程 班 级： 网络121 学 号： 201210314005 姓 名： 朱正杰

上海海事大学信息工程学院

2014年 12月 15日

目录

1.课程设计任务描述与要求 ................................. 1 1.1任务描述 .......................................... 1 2.系统总体结构描述与主要数据结构说明 ..................... 1 2.1系统总体结构描述 .................................. 1 2.2主要数据结构说明 .................................. 2 3.课程设计报告内容 ...................................... 5 3.1模块功能 .......................................... 5 3.2详细流程图 ........................................ 6 3.3实现思路说明 ...................................... 7 3.4程序清单 .......................................... 7 3.5注释 .............................................. 8 4.总结 ................................................. 19 附录： ................................................. 19 程序使用说明 ........................................ 19 程序测试思想 ........................................ 20 程序测试结果 ........................................ 20 参考书目： ............................................. 21

1

1.课程设计任务描述与要求

1.1任务描述

编写一个线程安全的双向链表，所谓线程安全，就是该链表能够实现多个线

程同时正确的增删改链表结点，也就是能够实现对链表这个临界资源的保护。 1.2任务要求

需要实现的函数包括：

（1） InitList函数：初始化一个空的双向链表，并初始化各个用于保护链表

的信号量。

（2） Insert函数：向链表指定位置插入一个结点。 （3） Erase函数：删除指定位置的结点。 （4） Clear函数：删除链表中的所有结点。

（5） Find函数：查找链表中是否有指定的元素，若有，返回能够访问该结点

的指针；若无，返回NULL。

（6） Print函数：打印当前链表中的所有元素。

完成该链表后，自己编写一个测试程序，生成多个线程同时读写该链表，验证链表执行是否正确，并给出测试报告。

2.系统总体结构描述与主要数据结构说明

2.1系统总体结构描述

系统总体结构设计的任务，是根据系统分析的逻辑模型设计应用软件系统的

物理结构。系统物理模型必须符合逻辑模型，能够完成逻辑模型所规定的信息处理功能。这是物理设计的基本要求。

系统应具有可修改性，即易读，易于进行查错、改错、可以根据环境的变化

和用户的要求进行各种的改变和改进。系统是否具有可修改性，对于系统开发和

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 DuLNode{

ElemType data; //定义数据域 PNode prior; //定义前驱指针 PNode next; //定义后继指针

}DuLNode,*DLN; //定义双向链表结构体

2

typedef struct DuLinkList{

DLN head; //定义头结点 int Length; //定义链表长度

}DuLinkList,*DLL; //定义读者传参结构体 struct Readarg{ };

//定义写者传参结构体 struct Writearg{ };

线程函数部分：

WaitForSingleObject(h_Mutex,-1);//等待互斥量信号 WaitForSingleObject(mutex,INFINITE);//等待信号量信号 ReleaseMutex(h_Mutex);//释放互斥量信号

ReleaseSemaphore(mutex,1,NULL);//释放信号量信号 主函数部分：

HANDLE hThread[sum];//定义线程句柄 unsigned threadID[sum];//定义sum个线程

h_Mutex=CreateMutex(NULL,FALSE,NULL); //创建互斥量h_Mutex mutex=CreateSemaphore(NULL,1,1,NULL); //创建信号量mutex Readarg *RA=new Readarg[1];//创建读者传参变量 RA[0].List=L;//传参变量赋值 RA[0].e=random(100);//传参变量赋值

Writearg *WA=new Writearg[2];//创建写者传参变量

3

DLL List; //定义链表 ElemType e; //定义查找元素

DLL List; //定义链表

int add; //定义插入或删除的位置 ElemType e; //定义插入元素

int Flag; //定义传入标示符（cr执行插入操作，sc执行删除操作）

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);//关闭信号量句柄

4

3.课程设计报告内容

3.1模块功能

此程序包含6个模块，分别是初始化兼创建模块，插入模块，删除模块，清

空模块，查找模块和打印模块。先是有进程自动初始化并随机产生一个链表，然后创建多个线程，线程同时进行插入结点，删除指定位置结点，查找指定元素及打印链表操作，为清楚区分读和写的操作这里分出了两个线程一个为读者线程一个为写者线程，前者具有查找指定元素功能，后者具有插入和删除兼打印链表功能。对于所有的查找，插入和删除数都是随机产生的，更具有代表性。

初始化并创建链表 打印链表 如下图程序工作原理：

读者线程 开始运行程序 查找地址 插入数据 写者线程 删除数据 清空链表 图3.1 程序工作原理图

5

3.2详细流程图

开始 显示选择菜单 2 1或2 1 清空控制台信息 初始化链表 创建链表 插入数据 删除数据 查找地址 打印链表 是 是否还有线程 否 清空链表 结束 图3.2系统流程图

6

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) //查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回NULL

7

void 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，e DLN p;//定义结点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动态分配内存失败则跳出该段代

码。

}

8

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

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;//将当前链表尾结点的后继指针指向结

点p }

//在链表指定位置插入一个结点

void Insert(DLL L,int i,ElemType e){

DLN p,q;//定义结点p，q

9

}

}

L->head->prior=p;//将当前链表头节点的前驱指针指向结点p L->Length++;//链表长度加1

int j;//定义整型变量j //下面判断插入位置是否合法 if(i<1||i>L->Length+1){

printf(\对不起，您插入的位置超过了链表范围！\\n\\n\

}else{

printf(\恭喜你，插入成功！\\n\\n\

p=(DuLNode*)malloc(sizeof(DuLNode)); //p动态分配存储空间 if(!p){ }

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

printf(\结点p动态分配内存失败！\\n\

exit(0); // 异常处理，如果用户未输入结点个数则跳出该段代码。

}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;//将当前链表头结点的前驱指针指向结

点p

q->next=p;//将当前链表尾结点的后继指针指向结点p L->Length++;//链表长度加1

if(i==1)//判断插入位置是否是头结点

L->head=p;//将结点p置为链表头结点

10

}else {

for(j=1;j

q->prior->next=p;//将当前链表尾结点的后继指针指向结点p p->prior=q->prior;//将结点p的前驱指针指向当前链表的尾

q=q->next;

结点

}

}

}

q->prior=p;//将当前链表头结点的前驱指针指向结点p p->next=q;//将结点p的后继指针指向当前链表头结点 L->Length++;//链表长度加1

}

//删除指定位置的结点 void Erase(DLL L,int i){

DLN q;//定义结点q int j;//定义整型变量j

q=L->head;// q指向当前链表头结点 if(i<1||i>(L->Length)||L->head==NULL){

printf(\对不起，您删除的位置超过了链表范围或者链表为空！\\n\\n\

}else{

printf(\恭喜你，删除成功！\\n\\n\for(j=1;j

q->prior->next=q->next;//将结点q前一个结点的后继指针指向q的后

q=q->next;

一个结点

11

q->next->prior=q->prior;//将结点q后一个结点的前驱指针指向q的

前一个结点 }

//删除链表中所有结点 void Clear(DLL L){ }

12

}

if(i==1){//判断删除的位置是否是链表头结点 }

L->Length--;//链表长度减1

if(L->Length==0){//判断当前链表是否为空 }

free(q);//释放结点q的物理内存

L->head=NULL;//将当前链表头结点置空

L->head=q->next;//将当前链表的头结点指向第二个结点

DLN q,temp;//定义结点q，temp int i,j;//定义整型变量i，j i=L->Length;//将链表长度赋给i

temp=q=L->head;//结点q和temp指向当前链表头结点 for(j=0;j

L->head=NULL;//链表头结点置空 printf(\链表已清空！\

q=q->next; free(temp); temp=q; L->Length--;

//查找链表中是否有指定的元素，若有，返回能够访问该结点的指针；若无，返回NULL

DLN Find(DLL L,ElemType e){

DLN q;//定义结点q

q=L->head;//将q指向链表头结点 if(!q){

printf(\链表为空！找不到元素%d\\n\\n\

}else{

//控制q指针后移逐个比较查找元素，当知道最后一个元素并且未找到

时退出循环

while(q->data!=e&&q->next!=L->head){ }

//判断是否找到指定元素

}

//打印当前链表中的所有元素 void Print(DLL L){

DLN p;//定义结点p if(L->head==NULL){

printf(\链表为空！\

13

q=q->next;

}

if(q->data==e){

printf(\元素%d已找到！指针已返回！\\n\\n\return q;

}else{ }

printf(\元素%d未找到！返回空\\n\\n\return NULL;

}else{

p=L->head;

printf(\p=p->next;

//当p重新指到链表头节点的时候跳出循环

}

while(p!=L->head){ }

printf(\p=p->next;

printf(\

printf(\长度为：%d\\n\printf(\打印完毕！\\n\\n\

//读者线程(查找)

unsigned __stdcall ReaderThread(void *arg){

WaitForSingleObject(h_Mutex,-1);//等待互斥量信号 readcount++; if(readcount==1){ }

ReleaseMutex(h_Mutex);//释放互斥量信号 e=RA->e;

printf(\查找操作：读者%d开始查找%d\\n\

14

Readarg *RA; RA=(Readarg*)arg;

int e;

WaitForSingleObject(mutex,INFINITE);//等待信号量信号

}

Find(RA->List,e);

th_cz++; //执行完一遍查找读者数加1

WaitForSingleObject(h_Mutex,-1); readcount--; if(readcount==0){ }

ReleaseMutex(h_Mutex); return 0;

ReleaseSemaphore(mutex,1,NULL);//释放信号量信号

//写者线程（包括插入和删除）

unsigned __stdcall WriterThread(void *arg){

if(f){

WaitForSingleObject(mutex,INFINITE); printf(\插入操作：写者%d开始在第%d位置插入元int f,add,e; f=WA->Flag; add=WA->add; e=WA->e; Writearg *WA; WA=(Writearg*)arg;

素%d\\n\

Insert(WA->List,add,e);

th_cr++;//执行完一遍插入写者数加1 Print(WA->List);

15

}

ReleaseSemaphore(mutex,1,NULL);

}else{ }

return 0;

WaitForSingleObject(mutex,INFINITE);

printf(\删除操作：写者%d开始删除第%d个位置\\n\Erase(WA->List,add);

th_sc++;//执行完一遍删除写者数加1 Print(WA->List);

ReleaseSemaphore(mutex,1,NULL);

int main(){

HANDLE hThread[sum];

16

char sr;

printf(\printf(\读者优先\\n\printf(\退出窗口\\n\

printf(\printf(\请输入你的选择（1或者2）：\do{

sr=(char)getchar();

}while(sr!='1'&&sr!='2'); //system(\if(sr=='2')

return 0;

else{

unsigned threadID[sum];

int i,j,k,m;

DLL L;

L=(DuLinkList*)malloc(sizeof(DuLinkList)); InitList(L); Print(L);

h_Mutex=CreateMutex(NULL,FALSE,NULL); //创建互斥量h_Mutex mutex=CreateSemaphore(NULL,1,1,NULL); //创建信号量mutex

srand((int)time(0)); for(i=0;i

j=random(3);//在0,1,2这三个数内随机取一个值决定该次循环执行哪

一个操作（0为查找，1为插入，2为删除）

hThread[i]=(HANDLE)_beginthreadex(NULL,0,ReaderThread,(void*)&RA[

if(j==0){

Readarg *RA=new Readarg[1]; RA[0].List=L;

RA[0].e=random(earea); //创建读者线程

0],0,&threadID[i]);

}else{

Writearg *WA=new Writearg[2]; WA[0].List=L;

WA[0].add=random(lsarea); WA[0].e=random(earea);

17

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操作，

及时收回线程

CloseHandle(h_Mutex); CloseHandle(mutex);

th=(th_cz+th_cr+th_sc)-3; //统计总线程数

printf(\当前查找读者人数为：%d；当前插入写者人数为：%d；当前删除写

18

}

for(i=0;i

CloseHandle(hThread[i]);

者人数为：%d；当前总人数为：%d\\n\ }

Clear(L); Print(L);

printf(\所有线程都执行完毕了。\\n\}

return 0;

4.总结

通过本次课设的编写，熟练掌握了双向链表的基本操作，熟悉了线程创建和

传参的基本操作，对于线程同步和调度机制有了深入的了解。通过学习和使用互斥量信号量对于读者写者问题有了脱离课本的理解。这是一次理论与实践相结合的尝试，在这二周左右的时间里，我遇到了许多的问题，诸如双向链表构建，线程传参，互斥量保护以及读者写者问题，在老师的悉心指导以及同学的耐心解答下，我解决了问题，并就问题本身进行了总结，梳理出了链表的基本结构和自己的理解，在后期加入多线程读写问题是得益于老师提供的材料，例子丰富，备注详细，帮助我由浅入深地理解并编写出自己的代码，非常感谢老师的指导。综上所述，本次课设受益匪浅。

附录：

程序使用说明

本程序点击exe文件后跳出下图：

19

选择1以读者优先原则运行本程序如下图：

选择2则退出窗口。

程序测试思想

第一步，测试纯手动输入操作的双向链表的6个基本函数运行是否正确。 第二步，测试手动创建自动运行操作的包含多线程和互斥量的双向链表是否正确。 第三步，测试随机数自动创建自动运行操作的包含读者写者问题多线程的双向链表是否正确。

程序测试结果

第一步测试结果如下图：

20

第二步测试结果如下图：

第三步测试结果如下图

参考书目：

［1］ 严蔚敏，吴伟民，《数据结构（c语言版）》，北京，清华大学出版社，2007年

21

本文来源：https://www.bwwdw.com/article/h0m7.html