CAS and concurrent access to a simple C++ array of pointers

(Some 2010 MS interviewer asked me about this concurrency hazard.) This array could be part of a hash table.

Thread 1 is about to remove an element from a hash table. It needs to first substitute a NULL address into the array to prevent Thread 2 from seeing the to-be-deleted entry. Then it will delete on the obsolete ptr … but actually it has to save that address before storing the NULL.

The critical operation is the atomic load-and-store — “load current element and substitute a NULL”. XCHG is the way to go. But what if another thread is doing the same operation? I feel a CAS loop is better — Thread 1 first loads current value into a register. Then it attempts to compareAndSet. If current value is unchanged, it puts in the NULL. Otherwise it should retry.

Q: What if in the same clock cycle, 2 threads (on separate processors) succeed in the load-and-store. Both loads the obsolete address and both try to delete on it… double-free
%%A: I think the hardware spec should cover this scenario. Should not be left to chances.

This situation is virtually impossible to test. But if they don’t happen in the same clock cycle, then the slow thread will see a NULL in the array – lock-free thread safety.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s