void* count1m(void *arg){ int id = *(int*)arg; while (!ready) {} // wait for the ready signal for (int i=0; i<1000000; ++i) {} // go!, count to 1 million if (!winner.exchange(true)) { std::cout << "thread #" << id << " won!\n"; } returnNULL; };
intmain() { pthread_t threadIDs[10]; int ids[10]; std::cout << "spawning 10 threads that count to 1 million..." << std::endl; for(int i = 0; i < 10; i++) { ids[i] = i; pthread_create(&threadIDs[i], NULL, count1m, (void*)&ids[i]); } ready = true; for(int i = 0; i < 10; i++) { pthread_join(threadIDs[i], NULL); }
return0; }
p.s. at first, winner is false, when the first thread call exchange, it will set winner to true and return false, so the first thread will print “won”, and the other threads will not print anything because the value of winner is already true.
#define TABLE_SIZE 10007 // size of the hash table #define N_OPERATIONS 10000000 // total number of operations to perform #define N_THREADS 10 // number of threads to use #define READ_RATIO 0.8 // ratio of read operations (rest are write and delete)
typedefstructnode { int key; int value; structnode* next; } node_t;
node_t* table[TABLE_SIZE]; // array of linked lists, one for each hash bucket
voidhash_init(){ for (int i = 0; i < TABLE_SIZE; i++) { table[i] = NULL; } }
voidhash_insert(int key, int value){ int index = key % TABLE_SIZE; node_t* new_node = (node_t*)malloc(sizeof(node_t)); new_node->key = key; new_node->value = value; new_node->next = table[index]; table[index] = new_node; }
inthash_search(int key){ int index = key % TABLE_SIZE; node_t* current = table[index]; while (current != NULL) { if (current->key == key) { int value = current->value; return value; } current = current->next; } return-1; // key not found }
voidhash_delete(int key){ int index = key % TABLE_SIZE; node_t* current = table[index]; node_t* previous = NULL; while (current != NULL) { if (current->key == key) { if (previous == NULL) { table[index] = current->next; } else { previous->next = current->next; } free(current); break; } previous = current; current = current->next; } }
void* worker(void* arg){ srand(time(NULL) + (long)arg); // seed random number generator int n_reads = 0, n_writes = 0, n_deletes = 0;
#define TABLE_SIZE 10007 // size of the hash table #define N_OPERATIONS 10000000 // total number of operations to perform #define N_THREADS 10 // number of threads to use #define READ_RATIO 0.8 // ratio of read operations (rest are write and delete)
typedefstructnode { int key; int value; structnode* next; } node_t;
node_t* table[TABLE_SIZE]; // array of linked lists, one for each hash bucket pthread_mutex_t lock[TABLE_SIZE]; // mutex locks for each bucket
voidhash_init() { for (int i = 0; i < TABLE_SIZE; i++) { table[i] = NULL; pthread_mutex_init(&lock[i], NULL); // initialize mutex for each bucket } }
voidhash_insert(int key, int value) { int index = key % TABLE_SIZE; pthread_mutex_lock(&lock[index]); // acquire lock for the bucket node_t* new_node = (node_t*)malloc(sizeof(node_t)); new_node->key = key; new_node->value = value; new_node->next = table[index]; table[index] = new_node; pthread_mutex_unlock(&lock[index]); // release lock }
/// we need to unlock before return, so I change two return /// into only one return so that we can unlock the lock before return inthash_search(int key) { int index = key % TABLE_SIZE; pthread_mutex_lock(&lock[index]); // acquire lock for the bucket node_t* current = table[index]; int value = -1; while (current != NULL) { if (current->key == key) { value = current->value; break; } current = current->next; } pthread_mutex_unlock(&lock[index]); // release lock return value; }
voidhash_delete(int key) { int index = key % TABLE_SIZE; pthread_mutex_lock(&lock[index]); // acquire lock for the bucket node_t* current = table[index]; node_t* previous = NULL; while (current != NULL) { if (current->key == key) { if (previous == NULL) { table[index] = current->next; } else { previous->next = current->next; } free(current); break; } previous = current; current = current->next; } pthread_mutex_unlock(&lock[index]); // release lock }
void* worker(void* arg) { srand(time(NULL) + (long)arg); // seed random number generator int n_reads = 0, n_writes = 0, n_deletes = 0;
voidhash_delete(int key) { int index = key % TABLE_SIZE; pthread_spin_lock(&locks[index]); // 获取写锁 // delete the node
pthread_spin_unlock(&locks[index]); // 释放写锁 }
intmain() { hash_init();
// start working...
// destroy locks for (int i = 0; i < TABLE_SIZE; i++) { pthread_spin_destroy(&locks[i]); }
return0; }
spinlock:
1 2 3 4 5 6
... Benchmark finished in 8.171603 seconds ... Benchmark finished in 7.480587 seconds ... Benchmark finished in 7.168322 seconds
average time is about 7.607 seconds
conclusion
When read ratio is 80%, the average time of different locks is:
without lock
with mutex
with rwlock
with spinlock
7.467s
8.321s
7.945s
7.607s
without lock is the fastest, but it is not thread-safe.
mutex is the slowest, because it will block the thread which acquires kernel switch.
rwlock is faster than mutex, because it allows multiple threads to read at the same time.
spinlock is faster than mutex, because it is suitable for short time waiting. However, it is not suitable for long time waiting situation, because it will consume CPU resources.
When read ratio is 90%, the average time of different locks is:
without lock
with mutex
with rwlock
with spinlock
4.296s
4.631s
4.516s
4.595s
we can see that when read ratio get higher, the performance of rwlock improves.
// 创建线程 for (int i = 0; i < 10; i++) { thread_args[i] = i; if (pthread_create(&threads[i], NULL, thread_function, (void *)&thread_args[i])) { perror("Failed to create the thread"); } }
// 等待线程结束 for (int i = 0; i < 10; i++) { pthread_join(threads[i], NULL); }
// 销毁互斥锁 pthread_mutex_destroy(&lock);
// print Node *current = top; int count = 0; printf("content of stack:\n"); while (current != NULL) { count++; //printf("%d\n", current->value); current = current->next; // 假设每个节点都有一个指向下一个节点的指针 } printf("count = %d\n", count);
