Click here to Skip to main content
15,881,516 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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:

C++
#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;

/*
 * a lock switch type.
 * refer to msdn and alter its codes.
 */
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) {
        //block until switch , according msdn.
    }
}
void Unlock(LOCK* pl) {
    _InterlockedExchange((long *)pl,LOCK_IS_FREE);//make the switch manually.
}

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) {
        //Lock(&p->lock);
        p->head=n;
        p->tail=n;
        //Unlock(&p->lock);
        
        /*
         * suppose there are multiple threads append new node to list.
         * the if clause way be true , p->tail is null at the execution time,
         * then the clause for assignment for p->tail, between these two statements, 
         * another thread append a new node into list. so the p->tail may not null right now.
         * if p->tail is still null, do the assignment, if not, you should repeat to access p->tail which
         * not null, and assign new value.
         */
         
    } else {
        //Lock(&p->lock);
        tail->next=n;
        p->tail=n;
        //Unlock(&p->lock);
    }
    
    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;
    
    //fetch each node in link list
    pNode tmp=p->head;
    pNode pre=NULL;
    while(tmp) {
        if(tmp==n) {
            if(pre&&tmp->next) { // delete item between head and tail
                pre->next=tmp->next;
            }
            if(pre==NULL) { //delete item head;
                p->head=tmp->next;
            }
            if(tmp->next==NULL) { //delete item tail
                p->tail=pre;
                if(pre) pre->next=NULL; //cut off the tail chain
            }
            if(p->head==p->tail&&p->head==tmp) {
                p->head=p->tail=NULL; //fix if no node item existed, not sure whether executed or not.
            }
            
            return tmp; // return the delete item from the link list.
        }
        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);
        //Lock(&public_list->lock);
        if(0!=Link_Append(public_list,new_node(name,value))) printf("Apennd failed.\n");
        //Unlock(&public_list->lock);
        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) {
        
        //Lock(&public_list->lock);
        
        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;// each round you just need to remove the first math.
            }
            tmp=tmp->next;
        }
        
        //Unlock(&public_list->lock);
        
        //Sleep(5);
    }
    
    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);
    //thread[2]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)Proc_A,public_list,0,NULL);
    
    WaitForMultipleObjects(2,thread,TRUE,10000);
    
    
    Link_Desc(public_list);
    Link_Release(public_list);
}

void main() {
    test_how_to_avoid_crash();
}
Posted
Updated 1-Apr-23 1:31am
v2

1 solution

No - you really need to lock because in C operations aren't atomic: they are compiled to multiple machine code instructions which means that the changes to actual memory do not all take place in a single instruction - so other threads can get in at any point and make their changes. And the system is at liberty to pause, or suspend any thread at any time - so unless you apply locks round critical memory manipulations at some point it is all going to go all wahoonie-shaped.

That's what locks are for: to protect critical memory from external changes while it is being manipulated.
 
Share this answer
 
Comments
Yount_0701 1-Apr-23 8:35am    
If I use the CAS check-and-update loop, could it avoid the concurrency problem?
Dave Kreskowiak 1-Apr-23 11:34am    
No, because both loops can be modifying the same node at the same time. One loop will be telling the (previously) last node the address of the (new) last node, and the other loop can be trying to delete the (previously) last node, thereby orphaning the (new) last node. You need the lock when either loop is making a change to prevent this.
Yount_0701 1-Apr-23 21:12pm    
how about if I use lock to wrap around the operation functions (Link_Delete/Link_Append) ?
like this :
Link_Delete(...) {
Lock(&p->lock);
//....;
Unlock(&p->lock);
}
Dave Kreskowiak 1-Apr-23 22:59pm    
That's exactly what I said, isn't it?
Yount_0701 2-Apr-23 1:47am    
there are some articles talk about ABA problems, I'm not sure it's OK or not.
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) {
//block until switch , according msdn.
}
}
void Unlock(LOCK* pl) {
_InterlockedExchange((long *)pl,LOCK_IS_FREE);//make the switch manually.
}

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900