atomic set bits in array of bytes

Question

How do you atomically set bits of a byte? The problem I am trying to solve concerns updating a huge array of bytes, say uchar data[262144]. I am setting only 2 bits of a byte at one time using SET(index,value), which means four threads could be setting values in one byte simultaneously. It is very rare that threads select the same byte to update but it does happen. What is the most efficient way to make these operations thread safe? Note that I can't use a lock per data entry which would be too big and too slow.

To make matters worse, sometimes another array of bytes, data1[131072], needs to be updated simultaneously with the previous data in a thread safe way too. But I am planning to merge these two arrays to simplify the problem so an atomic way of updating the first array is enough.

Answer 1

You have to use CompareExchange primitive. What exactly you need to write, depends on the compiler and the platform. However, in theory, it looks like the following.

Assume CompareExchange returns oldvalue and atomically changes value only if oldvalue is not changed.

    do {
        oldvalue = bitset;
        newvalue = oldvalue|bitvalue;
    } while ( oldvalue != CompareExchange(&bitset,newvalue,oldvalue) );

Since CompareExchange is atomic, it will set bits atomically. But you can set bits atomically only in maximum one processor word sized bitset.