suppose there are two threads, thread A and thread B. Both of these two threads have operations on a link list concurrently.
thread A: it only do one job, insert new node to the link list, to be more accurate, new node always should be append on the end of the link list.
thread B: loop the link list all the time , check the node value ,if math a specific value , then delete this node.if match ,the deleting operation should follow the order from head to end, head node first, then next ,... , then the last.
my question is , normally there would be some conflicts when these two threads do the job above concurrently.
so further for, WITHOUT LOCK mechanism , is there some special and tricky data structure designing which could avoid the conflict on these two threads ?
There is a lot references about CAS(compare and swap) articles. I have written a simple code , according the results, there seemed no much difference ( the confliction not occurred) , I'm not sure my code describe the problem properly.
And another question is , if there are more other threads appending and deleting nodes concurrently, with or without CAS , Can the shared resource work OK , in theoretically? if CAN NOT, is there a proper alter version of codes below to show the concurrent operation problems?
What I have tried:
#include <windows.h>
#include <intrin.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct node {
char name[256];
int value;
void* data;
node* next;
}Node,*pNode;
typedef enum {
LOCK_IS_FREE = 0,
LOCK_IS_TAKEN = 1
} LOCK;
void Lock(LOCK* pl) {
while(_InterlockedCompareExchange((long*)pl,LOCK_IS_TAKEN,LOCK_IS_FREE)== LOCK_IS_TAKEN) {
}
}
void Unlock(LOCK* pl) {
_InterlockedExchange((long *)pl,LOCK_IS_FREE);}
typedef struct link_list {
pNode head;
pNode tail;
LOCK lock;
}link,*plink;
void Link_Desc(plink p);
static plink public_list;
pNode new_node(char* name,int value) {
pNode p=(pNode)calloc(sizeof(Node),1);
if(p) {
strcpy(p->name,name);
p->value=value;
p->data=NULL;
p->next=NULL;
}
return p;
}
void free_node(pNode p) {
if(p) {
if(p->data) free(p->data);
free(p);
}
}
plink Link_New() {
plink link=(plink)calloc(sizeof(link),1);
if(link) {
link->head=NULL;
link->tail=NULL;
link->lock=LOCK_IS_FREE;
}
return link;
}
int Link_Append(plink p,pNode n) {
if(!n||!p) return -1;
pNode tail=p->tail;
if(tail==NULL) {
p->head=n;
p->tail=n;
} else {
tail->next=n;
p->tail=n;
}
printf("%s:%d appended\n",n->name,n->value);
return 0;
}
pNode Link_Delete(plink p,pNode n) {
if(!n||!p) return NULL;
if(p->head==NULL) return NULL;
pNode tmp=p->head;
pNode pre=NULL;
while(tmp) {
if(tmp==n) {
if(pre&&tmp->next) { pre->next=tmp->next;
}
if(pre==NULL) { p->head=tmp->next;
}
if(tmp->next==NULL) { p->tail=pre;
if(pre) pre->next=NULL; }
if(p->head==p->tail&&p->head==tmp) {
p->head=p->tail=NULL; }
return tmp; }
pre=tmp;
tmp=tmp->next;
}
return NULL;
}
void Link_Release(plink p) {
if(p==NULL) return;
pNode tmp=p->head;
while(tmp) {
pNode cur=tmp;
tmp=tmp->next;
free_node(cur);
}
free(p);
}
void Link_Desc(plink p) {
printf("#####Desc link list.######\n");
if(!p) {
printf("<null>\n");
return;
}
pNode tmp=p->head;
if(!tmp) {
printf("<NON-ITEM>.\n");
}
while(tmp) {
printf(" %s:%d\n",tmp->name,tmp->value);
tmp=tmp->next;
}
printf("#####Desc End.######\n");
}
int is_match(pNode p) {
if(!p) return -1;
if(p->value >=10 &&p->value <=99) return 0;
return -1;
}
int exit_flag=0;
unsigned int __stdcall Proc_A(void* param) {
int idx=0;
srand((time(NULL)%1024));
while(exit_flag==0) {
int value=rand()%100;
char name[256]="";
sprintf(name,"round %d random value",idx);
if(0!=Link_Append(public_list,new_node(name,value))) printf("Apennd failed.\n");
Sleep(3);
idx=(++idx)%99999999;
if(idx>=1000) exit_flag=1;
}
printf("#########[A]Proc_A Exit.###########\n");
return 0;
}
unsigned int __stdcall Proc_B(void* param) {
while(1) {
pNode tmp=public_list->head;
while(tmp) {
if(0==is_match(tmp)) {
pNode p=Link_Delete(public_list,tmp);
if(p) {
printf("%s:%d <deleted>.\n",p->name,p->value);
free_node(p);
}
break; }
tmp=tmp->next;
}
}
printf("#########[B]Proc_B Exit.###########\n");
return 0;
}
void test_how_to_avoid_crash() {
public_list=Link_New();
HANDLE thread[3];
thread[0]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)Proc_A,public_list,0,NULL);
thread[1]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)Proc_B,public_list,0,NULL);
WaitForMultipleObjects(2,thread,TRUE,10000);
Link_Desc(public_list);
Link_Release(public_list);
}
void main() {
test_how_to_avoid_crash();
}