Multi-threading with long linked-list

Question

I have a algorithm question here. There are 10 threads in the system and you are given a link list with 10 K elements in it. How do you do the thread synchronization (addition deletion etc.) so that it is optimized for performance? Using a mutex for the list is not advisable as it will slow down performance.

Answer 1

If all the positions are accessed with the same frequency and you can modify the list node, you can add a mutex for every node:

typedef struct node{ 
   char* data;
   struct listNode *next;
   pthread_mutex_t lock; 
} listNode ;

Also depends on the size of the data of the node. If it´s very small, this may cause an overhead due to the mutex storage, creation and deletion.

If it´s an overhead or can´t modify the node, you can split the list in (for example) 100 groups of 100 elements and use a mutex for each group

Answer 2

linked list data struct assumes all operations follow sequential rules. Take a look at concurrent linked list

No matter what kind of machinery you use to implement it, the interface and expected behavior imply sequential logic.