Lock free atomic arithmetic operations -

Lock-free atomic arithmetic operations

You can find an interview question and its solution related to a lock free arithmetic operation as a concurrent application in this article.

Q : x as a global variable, provide these operations x++; x%=20; atomically without using locks.

The sample code below shows the solution along with its test routine as conditional compilation options.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <pthread.h>
#include <sys/types.h>
 
#define THREAD_NUM 9
#define INC_NUM 32767
 
#define ATOMIC
//#define NON_ATOMIC
//#define MUTEX_LOCK /*this is for verification*/
 
volatile int x = 0;
 
void *thread_func(void *ptr);
#ifdef MUTEX_LOCK
pthread_mutex_t thread_mutex = PTHREAD_MUTEX_INITIALIZER;
#endif
 
int main(int argc, char **argv) 
{
    pthread_t thread[THREAD_NUM];
    int iret[THREAD_NUM];
    long nt;

    for (nt = 0; nt<THREAD_NUM; nt++) {
	    if ((iret[nt] = pthread_create( &thread[nt], NULL, thread_func, (void *)nt))) {
             fprintf(stderr, "Thread creation error!\n");
             return EXIT_FAILURE;
        }
    }
 
    for (nt = 0; nt<THREAD_NUM; nt++)
        pthread_join(thread[nt], NULL);
 
    printf("counter val = %d\n", x);
    return 0;
}
 
void *thread_func(void *ptr) 
{
    int cnt;
#ifdef ATOMIC
    __typeof__(x) tempx;
#endif
    printf("Thread %lu started.\n", (unsigned long)ptr);
    for (cnt = 0; cnt<INC_NUM; cnt++) {
#ifdef ATOMIC
    	do{
    	   tempx = x;
    	}while (!__sync_bool_compare_and_swap(&x, tempx, (tempx+1)%20));
#endif
#ifdef NON_ATOMIC
    	x++;
    	x %= 20;
#endif
#ifdef MUTEX_LOCK
        pthread_mutex_lock(&thread_mutex);
        x++;
    	x %= 20;
        pthread_mutex_unlock(&thread_mutex);
#endif
    }
    printf("Thread %lu finished.\n", (unsigned long)ptr);
    return NULL;
}

For more details, I encourage you to refer XCHG (for x86 architecture), and LDREX, STREX (for ARM architecture) instructions. These instructions help you understand what happens under the hood once you use APIs that support lock-free operations.

References: