操作系统课设-线程安全的双链表

#define random(x)(rand()%x) #define ins 1 #define del 0 volatile int readcount = 0; const int listarea = 10000; const int earea = 10000; const int sum = 10000; int thd = 0; int thd_query = 1; int thd_ins = 1; int thd_del = 1; HANDLE h_Mutex; HANDLE mutex; typedef int ElemType; typedef struct DulNode* PNode; #include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<process.h> #include<Windows.h> #include<time.h> typedef struct DulNode { ElemType data; PNode prior; PNode next; }DulNode, * DLN; typedef struct DuLinkList { DLN head; int length; }DuLinkList,*DLL; struct Readerarg { DLL List; ElemType e; }; struct Writerarg { DLL List; int add; ElemType e; int flag; }; void InitList(DLL L) { int c, i, e; DLN p; L->head = 0; L->length = 0; printf("链表初始化完成！\n"); srand((int)time(0)); c = random(listarea); if (!c) { printf("链表创建失败！！\n"); exit(0); } else { p = (DulNode*)malloc(sizeof(DulNode)); if (!p) { printf("节点p动态分配内存失败！！\n"); exit(0); } e = random(earea); p->data = e; p->next = p->prior = p; L->head = p; L->length++; for (i = 1; i < c; i++) { p = (DulNode*)malloc(sizeof(DulNode)); if (!p) { printf("节点p动态分配内存失败！！\n"); exit(0); } e = random(earea); p->data = e; p->next = L->head; p->prior = L->head->prior; L->head->prior->next = p; L->head->prior = p; L->length++; } } } void Insert(DLL L, int i, ElemType e) { DLN p,q; int j; if (i<1 || i>L->length + 1) { printf("请求不合理！！插入位置超出链表范围\n\n"); } else { printf("插入成功！\n\n"); p = (DulNode*)malloc(sizeof(DulNode)); if (!p) { printf("节点p动态分配内存失败！！\n"); exit(0); } q = L->head; p->data = e; if(!L&&i==1) { p->next = p->prior->prior = p; L->head = p; L->length++; } else { if (i == 1 || i == (L->length + 1)) { q = q->prior; p->next = q->next; p->prior = q; q->next->prior = p; q->next = p; L->length++; if (i == 1) { L->head = p; } else { for (j = 1; j < i; j++) { q = q->next; } q->prior->next = p; p->prior = q->prior; q->prior = p; p->next = q; L->length++; } } } } } void Delete(DLL L, int i) { DLN q; int j; q = L->head; if (i<1||i>L->length||L->length==NULL) { printf("删除操作异常，请选择合理的节点位置！\n\n"); } else { printf("删除成功！\n\n"); for (j = 1; j < i; j++) { q = q->next; } q->prior->next = q->next; q->next->prior = q->prior; if (i == 1) { L->head = q->next; } L->length--; if (L->length == 0) { L->head = NULL; } free(q); } } void Deleteall(DLL L) { DLN q, tmp; int i, j; i = L->length; tmp = q = L->head; for (j = 0; j < i; j++) { q = q->next; free(tmp); tmp = q; L->length--; } L->head = NULL; printf("链表节点全部删除！"); } DLN Query(DLL L, ElemType e) { DLN q; q = L->head; if (!q) { printf("链表为空！查询元素%d失败\n\n",e); } else { while (q->data!=e&&q->next!=L->head) { q = q->next; } if (q->data == e) { printf("查询元素%d成功！\n\n", e); return q; } else { printf("查询元素%d失败！\n\n", e); return NULL; } } } void Print(DLL L) { DLN p; if (L->head = NULL) { printf("链表为空！"); } else { p = L->head; printf("%d", p->data); p = p->next; while (p != L->head) { printf("%4d", p->data); p = p->next; } } printf("\n"); printf("长度为：%d\n", L->length); printf("Press any key to continue"); } //读者线程 unsigned __stdcall ReaderThread(void* arg) { Readerarg* Ra; Ra = (Readerarg*)arg; int e; WaitForSingleObject(h_Mutex, -1); readcount++; if (readcount == 1) { WaitForSingleObject(mutex, INFINITE); } ReleaseMutex(h_Mutex); e = Ra->e; printf("读者线程%d正在查找%d中\n", thd_query, e); Query(Ra->List, e); thd_query++; WaitForSingleObject(h_Mutex, -1); readcount--; if (readcount == 0) { ReleaseSemaphore(mutex, 1, NULL); } ReleaseMutex(h_Mutex); return 0; } //写者线程 unsigned __stdcall WriterThread(void* arg) { Writerarg* Wa; Wa = (Writerarg*)arg; int f,add,e; f = Wa->flag; add = Wa->add; e = Wa->e; if (f) { WaitForSingleObject(mutex, INFINITE); printf("写者线程%d正在插入元素%d，插入位置：%d\n", thd_ins, e, add); Insert(Wa->List, add, e); thd_ins++; Print(Wa->List); ReleaseSemaphore(mutex, 1, NULL); } else { WaitForSingleObject(mutex, INFINITE); printf("写者线程%d正在删除，删除位置为%d\n", thd_del, add); Delete(Wa->List, add); thd_del++; Print(Wa->List); ReleaseSemaphore(mutex, 1, NULL); } return 0; } int main() { char ch; while (true) { printf("***********************************\n"); printf(" 1: Reader Priority\n"); printf(" 2: Exit to Windows\n"); printf("***********************************\n"); printf("Enter your choice (1 or 2): "); //如果输入信息不正确，继续输入 do { ch = (char)getchar(); } while (ch != '1' && ch != '2'); system("cls"); //清除控制台显示的信息 //选择2，返回 if (ch == '2') return 0; //选择l，读者优先 else { HANDLE hThread[sum]; 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); mutex = CreateSemaphore(NULL, 1, 1, NULL); srand((int)time(0)); for (i = 0; i < sum; i++) { j = random(3); if (j == 0) { Readerarg* Ra = new Readerarg[1]; Ra[0].List = L; Ra[0].e = random(earea); hThread[i] = (HANDLE)_beginthreadex(NULL, 0, ReaderThread, (void*)&Ra[0], 0, &threadID[i]); } else { Writerarg* Wa = new Writerarg[2]; Wa[0].List = L; Wa[0].add = random(listarea); Wa[0].e = random(earea); Wa[0].flag = del; Wa[1].List = L; Wa[1].add = random(listarea); Wa[1].e = 0; Wa[1].flag = del; 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); for (i = 0; i < sum; i++) { CloseHandle(hThread[i]); } CloseHandle(h_Mutex); CloseHandle(mutex); thd = (thd_query + thd_ins + thd_del) - 3; printf("当前有%d位读者正在进行查询操作\n", thd_query); printf("当前有%d位写者正在进行插入操作\n", thd_ins); printf("当前有%d位写者正在进行删除操作\n", thd_del); printf("总线程数量为：%d\n", thd); Deleteall(L); Print(L); printf("Press any key to continue!\n"); } return 0; } } } }