Function InterlockedExchange

Question

I'm working with a list that is shared among many threads.

I believe that to a good performance in this case, it will be good to use InterlockedExchange function to insert data in this list, but I have some doubts.

If a thread tries to read a variable that is being written by another thread with InterlockedExchange, What will be the reaction? The thread that is reading the variable will wait for the completion of writing or will continue running and can not read the variable?

is necessary to use InterlockedExchange to read the variable when it is being written with interlockedechange?

How to test this function to try to know what will be the reaction to a multiple access to a shared variable between threads?

Answer 1

The short answer is that InterlockedExchange is unlikely to help you. But it's important to understand why this is the case so you'll be able to have a better understanding of the situations where it may help.

Why is concurrent reading AND writing a problem?

First note that any number of threads may read the same data concurrently without concern. We only start to worry as soon as one thread is able to write concurrently. Now, there's nothing inherently risky with writing itself. The problem comes in when even the slightest bit of decision logic is applied to the shared data being used concurrently.

For example, you might have a list. One thread (the writer) deletes an element from the list, while other threads are reading elements in the list. If you are unlucky with the timing of your operations, a reader might confirm an element exists at the same time the writer deletes it. And then when the reader tries to use the no longer valid element, you get Access Violations at best, and data corruption at worst.

How to protect the data

The simplest way to protect the data (without architectural changes) is usually to introduce some form locking/blocking mechanism. Before one thread starts a critical operation, it says: "I'm busy with the shared data, all other threads must wait until I'm done if they want to use the data."

Note that the simplistic approach does introduce other problems:

• Performance can be significantly reduced if many threads spend the majority of their time waiting or 'fighting for locks'.
• Problems with lock management can cause two threads to block each other and effectively cause the system to hang (known as a deadlock).

(NOTE: There are many alternate ways you could protect your data, but that's beyond the scope of this post.)

InterlockedExchange

This routine and its other Interlocked*** siblings provide a simplified locking mechanism over the steps of a basic, generic write operation. NOTE It's still a locking mechanism as described above, and shares most of its problems.

The two-step operation that InterlockedExchange protects is:

• read the previous value and
• write the new value.

The reason this might need protection is that if two threads Exchange a shared value concurrently, there is a possibility of inconsistent behaviour.

E.g. Given initial value is A. Thread #1 exchanges setting the value to B. Thread #2 exchanges setting the value to C. If the threads run concurrently with #1 processing fractionally sooner than #2, there are 2 possible results.

• With locking #2 will be blocked until #1 finishes, and the final result will always be: Value is set to C. Thread #1 has a reference to A. Thread #2 has a reference to B.
• Without locking, we will usually get the same results as above, but there is the possibility we don't. The final result might be: Value is set to C. Thread #1 has a reference to A. Thread #2 has a reference to A <-- Discrepancy.

This won't always be a problem, but in some cases it might be. In which case InterlockedExchange serves as the simplest lock based protection mechanism.

Why InterlockedExchange is unlikely to work for you

You said your data was in a list, but didn't state what kind of list; so I'm assuming a standard Delphi TList. Inserting an item into a list is not a simple operation internally.

• An internal counter is automatically maintained.
• Existing items might need to be moved.
• The current capacity of the list needs to be checked, and might need to increase.

NB! Note: Even if you are using a list data structure that could itself benefit from InterlockedExchange, there are still other problems you need to be aware of.

You have two sets of data here. There is the internal data of the list structure (you might not think of it as such, but it is there). And then there's the data of your actual records.

Even after protecting your list structure, if you have any threads that can concurrently update your records, you have a potential problem. You need to protect your data - not just the act of adding it to a collection. This means you might need a locking mechanism that spans both sets of data; and there's no chance that any of the basic, generic Interlocked*** routines will achieve that.

Answer 2

If a thread tries to read a variable that is being written by another thread with InterlockedExchange, What will be the reaction? The thread that is reading the variable will wait for the completion of writing or will continue running and can not read the variable?

The reading thread will read either:

• The value stored in memory before the write operation is executed, or
• The value stored after the the write operation has executed.

In fact this is true for plain read/write contention, that is if you are not using atomic functions. Memory access of machine word sized (or smaller) data is atomic. That is you are guaranteed not to have partial reads or rights. It must be the case that your variable is aligned, since you are using InterlockedExchange. Ergo, there can be no partials reads or writes, and hence no tearing.

Now, if your variable was not aligned, then a data race can lead to the read thread receiving part of the pre-write value, and part of the post-write value. That is known as tearing.

Is necessary to use InterlockedExchange to read the variable when it is being written with InterlockedExchange?

No. In fact that would not work. Because InterlockedExchange modifies the variable. And a read operation does not. Read the value with a plain memory read. That's the only way. Of course, you have a data race with the write thread, but that's inevitable.

---

I have serious doubts that your code correctly implements a lock-free container. Inserting an item into a lock free container is not easy to implement. In fact lock free containers are fiendishly difficult to implement. You need more than just calls to InterlockedExchange whenever you mutate the container.