基于锁的并发数据结构

使用单锁保护共享状态

将顺序数据结构转换为并发版本的一种直接方法是用一把互斥锁包裹每个公共操作。这确保同一时间只有一个线程能观察或修改内部状态，从而保持不变量。得到的结构是正确的，但可能过度串行化执行。

粗粒度锁定为何扩展性差

在多处理器上，运行在不同核心上的线程仍会争用同一把锁的缓存行，导致频繁的缓存失效和停顿。因此，增加线程数常常会增加总运行时间而不是减少它，远未达到理想的完美扩展，即额外核心能在相同墙上时钟时间内完成额外工作。

通过本地更新减少争用

近似计数器为每个处理器维护一个私有计数。大多数增量只在每核锁下触及本地变量，如果线程停留在其核心上则无争用。当本地计数达到阈值时，它被刷新到全局计数器。因此全局值略有过时，但该设计允许更高吞吐量，因为全局锁获取频率很低。

常见误区

• 忽略某些读取路径上的加锁会引入数据竞争。
• 粗粒度锁虽保证正确性却可能成为严重瓶颈。
• 在持有锁期间执行可能长时间阻塞的操作会加剧死锁可能性。

最低标准 C11 · 完整程序 · 下载 .c

#include <stdio.h>
#include <pthread.h>

#define NTHREADS 4
#define NINCS 1000

typedef struct {
    int val;
    pthread_mutex_t mtx;
} ctr_t;

void ctr_init(ctr_t *c) {
    c->val = 0;
    pthread_mutex_init(&c->mtx, NULL);
}

void ctr_inc(ctr_t *c) {
    pthread_mutex_lock(&c->mtx);
    c->val++;
    pthread_mutex_unlock(&c->mtx);
}

int ctr_get(ctr_t *c) {
    pthread_mutex_lock(&c->mtx);
    int v = c->val;
    pthread_mutex_unlock(&c->mtx);
    return v;
}

void *worker(void *arg) { (void)arg;
    ctr_t *c = arg;
    for (int i = 0; i < NINCS; i++)
        ctr_inc(c);
    return NULL;
}

int main(void) {
    ctr_t c;
    ctr_init(&c);
    pthread_t th[NTHREADS];
    for (int i = 0; i < NTHREADS; i++)
        pthread_create(&th[i], NULL, worker, &c);
    for (int i = 0; i < NTHREADS; i++)
        pthread_join(th[i], NULL);
    printf("Final counter: %d\n", ctr_get(&c));
    pthread_mutex_destroy(&c.mtx);
    return 0;
}

在本地编译

gcc -std=c11 -Wall -Wextra -Wpedantic -Werror -pthread ostep-29-locked-data-structures.c -o example && ./example

预期结果

Final counter: 4000

CHECK YOUR UNDERSTANDING

合上答案，试着解释。

单个全局锁保护的计数器为何无法随处理器数量线性扩展？

继续查证

• OSTEP chapter PDF

标准草案与官方章节会更新；版本标记只说明示例最低要求。