December 26, 2011

Lock free atomic operations

Filed under: Programming — Tags: , , — admin @ 8:03 pm

I would like to share another interview question in this article.

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

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#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;
}

Good luck for the interviews!

Powered by WordPress