CODEWITHSUNDEEP
cmultithreadingdata-structuresconcurrencysynchronization
wub
wub

Reputation: 485

Is one-insert-multi-read list safe without lock?

I have a problem about synchronization between threads. I know the normal synchronization method and lock-free list. But I have a strange (maybe) idea.

I have a normal singly list in C language, linked by next pointer.

There is only 1 thread who just insert items into this list, but never delete items. The way to add item:

new_item->next = list_head;
list_head = new_item;

There are some other threads who just traverse this list (read only).

There is no lock at all.

I think that this should be safe, because the read-only-threads will never get an invalid pointer. Am I right?

I do not know how to search this on internet. What I get is all about lock-free list by CAS or something. So I ask it here.

Thanks in advance

Upvotes: 2

Views: 68

Answers (1)

Daniel Langr
Daniel Langr

Reputation: 23497

You didn't specify the language and data types, but generally, that could be a data race (undefined behavior in C++), since one thread may modify list_head and other threads may read it at the same time.

If these reads/writes are atomic, then there is no data race. To my best knowledge, on x86 architecture, reads and writes are atomic automatically. But this may not hold for other architectures.

Moreover, reordering issues may broke things here, that's what memory fences are for, which are typically generated by the compiler when (sequentially consistent) atomic operations are involved. You update values of 2 pointers and, e.g., in C++ with relaxed memory ordering, threads are permitted to "see" these updates in a different order (generally due to compiler optimizations, out-of-order execution, CPU store buffers, etc.). See http://en.cppreference.com/w/cpp/atomic/memory_order for more details.

In C++11, you need std::atomic to ensure atomic operations on list_head. With OpenMP, there is #pragma atomic read/write (seq_cst) directive.

Upvotes: 1

Related Questions