并发笔记-给数据上锁（二）

核心挑战 (The CRUX)

并发数据结构设计的核心在于如何在保证线程安全（正确性）的前提下，实现高性能和高可伸缩性。

• 正确性 (Correctness): 如何向数据结构中添加锁，以确保在多线程环境下操作的原子性，避免数据竞争和不一致状态？
• 性能与可伸缩性 (Performance & Scalability): 如何设计锁的策略，以最小化锁的开销（如获取、释放锁的时间）和锁竞争（多个线程等待同一把锁的情况），从而允许多个线程尽可能地并行访问数据结构，使得数据结构在多核处理器上能有效扩展其处理能力？

这通常需要在锁的粒度 (granularity)、锁的数量以及锁的持有时间之间进行权衡。

29.1 并发计数器 (Concurrent Counters)

计数器是最简单的数据结构之一，通常提供 increment, decrement, get 等接口。

1. 简单非并发计数器 (Figure 29.1)

typedef struct counter_t {
    int value;
} counter_t;

void init(counter_t *c) {
    c->value = 0;
}

void increment(counter_t *c) {
    c->value++; // 非原子操作：读取-修改-写回
}

void decrement(counter_t *c) {
    c->value--; // 非原子操作
}

int get(counter_t *c) {
    return c->value;
}

问题：

• 非线程安全: value++ 和 value-- 并非原子操作。它们通常分解为三个步骤：1. 从内存读取 value 到寄存器；2. 寄存器中的值加/减1；3. 将寄存器中的新值写回内存。
• 竞争条件 (Race Condition): 如果多个线程同时执行这些操作，它们的步骤可能会交错执行，导致更新丢失和最终计数值不正确。例如，两个线程都读取了值为5，都将其加1得到6，然后都写回6，而正确的结果应该是7。

2. 同步计数器（单锁版本 - Coarse-Grained Lock, Figure 29.2）

通过引入一个互斥锁来保护对共享 value 的所有访问。

typedef struct counter_t {
    int value;
    pthread_mutex_t lock; // 为整个计数器添加一把锁
} counter_t;

void init(counter_t *c) {
    c->value = 0;
    pthread_mutex_init(&c->lock, NULL); // 初始化互斥锁
}

void increment(counter_t *c) {
    pthread_mutex_lock(&c->lock);    // 获取锁
    c->value++;
    pthread_mutex_unlock(&c->lock);  // 释放锁
}

void decrement(counter_t *c) {
    // 类似 increment，加锁、操作、解锁
    pthread_mutex_lock(&c->lock);
    c->value--;
    pthread_mutex_unlock(&c->lock);
}

int get(counter_t *c) {
    pthread_mutex_lock(&c->lock);
    int rc = c->value;
    pthread_mutex_unlock(&c->lock);
    return rc;
}

优点：

• 线程安全/正确性： 通过互斥锁确保了任何时刻只有一个线程能修改 value，从而避免了竞争条件。

缺点：

• 可伸缩性差 (Poor Scalability)： 这是典型的粗粒度锁 (coarse-grained lock)。无论线程想执行何种操作（增、减、读），都必须竞争同一把锁。
• 性能瓶颈： 在多核 CPU 环境下，随着并发线程数量的增加，对这把单锁的竞争会变得非常激烈，导致线程频繁等待，无法发挥多核的优势。访问实际上被序列化了。书中实验数据显示，从1个线程增加到2个线程，完成同样数量的更新操作，时间从约0.03秒飙升到超过5秒。

3. 可伸缩计数：近似/懒惰计数器 (Approximate/Sloppy Counter, Figure 29.4)

为了提高可伸缩性，采用分散竞争的思想，允许一定程度的近似。

思想：

• 维护一个全局计数器 (global) 和多个局部计数器 (local)，通常每个 CPU 核心对应一个局部计数器。
• 线程更新时，首先更新其对应 CPU 的局部计数器（需要对局部计数器加锁，以防同一核心上的多个线程竞争）。
• 当一个局部计数器的值达到一个预设的阈值 S (threshold/sloppiness) 时，才将该局部计数器的值累加到全局计数器中（此时需要对全局计数器加锁），并将局部计数器清零。
• 读取计数值时，通常只读取全局计数器的值，这是一个近似值，因为它可能没有包含所有局部计数器中尚未转移的最新更新。

#define NUMCPUS 4  // 假设系统中的 CPU 核心数

typedef struct counter_t {
    int             global;            // 全局计数值
    pthread_mutex_t glock;             // 保护全局计数的锁
    int             local[NUMCPUS];    // 每个 CPU 核心的局部计数值
    pthread_mutex_t llock[NUMCPUS];    // 保护每个局部计数的锁
    int             threshold;         // 阈值 S
} counter_t;

void init(counter_t *c, int threshold) {
    c->threshold = threshold;
    c->global = 0;
    pthread_mutex_init(&c->glock, NULL);
    int i;
    for (i = 0; i < NUMCPUS; i++) {
        c->local[i] = 0;
        pthread_mutex_init(&c->llock[i], NULL);
    }
}

// 线程 threadID 对计数器增加 amt
void update(counter_t *c, int threadID, int amt) {
    // 简单地将 threadID 映射到 CPU 索引
    // 实际系统中可能有更复杂的 CPU 亲和性或获取当前 CPU ID 的方法
    int cpu = threadID % NUMCPUS;

    pthread_mutex_lock(&c->llock[cpu]); // 获取对应局部计数器的锁
    c->local[cpu] += amt;               // 更新局部计数
    if (c->local[cpu] >= c->threshold) {  // 检查是否达到阈值
        // 达到阈值，需要将局部值转移到全局
        pthread_mutex_lock(&c->glock);     // 获取全局锁
        c->global += c->local[cpu];      // 更新全局计数
        pthread_mutex_unlock(&c->glock);   // 释放全局锁
        c->local[cpu] = 0;                 // 重置局部计数
    }
    pthread_mutex_unlock(&c->llock[cpu]); // 释放局部锁
}

// 获取近似的全局计数值
int get(counter_t *c) {
    pthread_mutex_lock(&c->glock);
    int val = c->global;
    pthread_mutex_unlock(&c->glock);
    return val;  // 返回的是近似值，可能不包含最新的局部更新
}

性能与准确性的权衡 (Threshold S)：

• 低 S (阈值小)： 局部计数器很快达到阈值，频繁地将更新转移到全局计数器。
  • 优点： 全局计数值相对更接近真实值（更准确）。
  • 缺点： 对全局锁 glock 的竞争更频繁，可伸缩性受到影响。
• 高 S (阈值大)： 局部计数器累积更多更新后才转移到全局。
  • 优点： 对全局锁 glock 的竞争减少，显著提高可伸缩性（如图29.5所示，近似计数器的性能几乎不随线程数增加而下降）。
  • 缺点： get() 操作返回的全局计数值与真实值之间的差距可能更大（更“懒惰”或“近似”）。
• 局部锁 llock 的必要性： 如果一个 CPU 核心上可能运行多个线程，并且这些线程都可能更新这个核心的局部计数器，那么 llock 是必需的，以防止这些线程之间的竞争。如果能保证每个核心只有一个线程（或一个特定的线程集合）更新其局部计数器，则可以考虑优化掉 llock。

29.2 并发链表 (Concurrent Linked Lists)

链表操作（插入、删除、查找）通常涉及对多个指针的修改或遍历。

1. 简单同步链表（单锁版本 - Coarse-Grained Lock）

使用一把锁保护整个链表的所有操作。

节点和链表结构定义：

typedef struct __node_t {
    int key;
    struct __node_t *next;
} node_t;

typedef struct __list_t {
    node_t *head;
    pthread_mutex_t lock; // 单个锁保护整个链表
} list_t;

void List_Init(list_t *L) {
    L->head = NULL;
    pthread_mutex_init(&L->lock, NULL);
}

初始插入和查找实现 (Figure 29.7 - 有改进空间):

// 插入操作 (初始版本)
int List_Insert(list_t *L, int key) {
    pthread_mutex_lock(&L->lock); // 操作开始即加锁
    node_t *new = malloc(sizeof(node_t));
    if (new == NULL) {
        perror("malloc");
        pthread_mutex_unlock(&L->lock);  // 错误路径1：释放锁
        return -1; // 插入失败
    }
    new->key = key;
    new->next = L->head;
    L->head = new;
    pthread_mutex_unlock(&L->lock); // 成功路径：释放锁
    return 0; // 插入成功
}

// 查找操作 (初始版本)
int List_Lookup(list_t *L, int key) {
    pthread_mutex_lock(&L->lock);
    node_t *curr = L->head;
    while (curr) {
        if (curr->key == key) {
            pthread_mutex_unlock(&L->lock); // 找到元素，释放锁并返回
            return 0;
        }
        curr = curr->next;
    }
    pthread_mutex_unlock(&L->lock); // 未找到元素，释放锁并返回
    return -1;
}

问题与改进 (Figure 29.8):

• 错误处理与锁的释放： 在 List_Insert 的初始版本中，如果 malloc 失败，需要在错误返回路径上显式释放锁。多条退出路径（成功、失败）都涉及解锁，容易遗漏，导致死锁。
• 代码结构优化：
  • 插入优化： 将 malloc 操作移到获取锁之前。如果 malloc 失败，则直接返回，无需处理锁。只有在 malloc 成功后，才获取锁执行链表修改这一真正的临界区 (critical section)。
  • 查找优化： 将查找结果存储在一个临时变量中，循环结束后，在单一的返回点之前释放锁。这样可以确保无论是否找到元素，锁都会在函数退出前被正确释放，减少了因控制流复杂而出错的可能。

改进后的插入和查找实现：

// 插入操作 (改进版)
int List_Insert(list_t *L, int key) {
    node_t *new = malloc(sizeof(node_t)); // 1. 先分配节点
    if (new == NULL) {
        perror("malloc");
        return -1; // 若失败，直接返回，不涉及锁
    }
    new->key = key;

    pthread_mutex_lock(&L->lock);     // 2. 获取锁，保护链表结构
    new->next = L->head;
    L->head = new;
    pthread_mutex_unlock(&L->lock);   // 3. 释放锁
    return 0;
}

// 查找操作 (改进版)
int List_Lookup(list_t *L, int key) {
    int rv = -1; // 默认返回值：未找到
    pthread_mutex_lock(&L->lock);
    node_t *curr = L->head;
    while (curr) {
        if (curr->key == key) {
            rv = 0; // 找到元素
            break;  // 跳出循环
        }
        curr = curr->next;
    }
    pthread_mutex_unlock(&L->lock); // 统一的解锁点
    return rv;
}

好处： 改进后的代码结构更清晰，减少了因忘记在特定路径释放锁而导致的bug。
可伸缩性： 仍然是单锁，性能瓶颈与同步计数器类似。

2. 可伸缩链表：逐手传递锁/锁耦合 (Hand-over-Hand Locking / Lock Coupling)

思想：

• 为了提高并发性，不再使用单个全局锁，而是为链表中的每个节点分配一个锁。
• 当线程遍历链表时，它采用“手递手”的方式获取和释放锁：在访问下一个节点之前，先获取下一个节点的锁，然后再释放当前持有节点的锁。
  • 例如，要从 curr 移动到 curr->next (设为 next_node)：
    1. 获取 curr 节点的锁。
    2. (如果需要访问 curr->next) 获取 next_node 的锁。
    3. 一旦安全地持有了 next_node 的锁，就可以释放 curr 节点的锁。
    4. 现在 curr 指向 next_node，并持有其锁。
• 插入或删除操作会更复杂，需要小心地锁定相关节点（通常是待操作节点的前一个节点和待操作节点本身）。

优点（理论上）：

• 更高的并发度： 不同的线程可以同时在链表的不同部分进行操作，只要它们操作的节点不相邻或不冲突。

缺点（实践中）：

• 高昂的锁开销： 每次遍历一个节点都需要至少一次（甚至多次）锁获取和释放操作。这些操作本身是有成本的，尤其是在高争用情况下。
• 复杂性增加： 实现正确且高效的逐手锁链表非常具有挑战性，容易出错，尤其是在处理删除和边界条件时。
• 性能可能更差： 除非链表非常长，并且线程访问的局部性非常好（即很少冲突），否则频繁的锁操作开销往往会超过并发带来的收益，导致其性能甚至不如简单的单锁链表。
• 书中提到：“即使对于非常大的列表和大量的线程，通过允许多个正在进行的遍历所启用的并发性也不太可能比简单地获取单个锁、执行操作并释放它更快。”

29.3 并发队列 (Concurrent Queues)

队列是先进先出 (FIFO) 的数据结构，常见操作是入队 (enqueue) 和出队 (dequeue)。

Michael and Scott 并发队列 (Two Locks, Figure 29.9)

这是一种经典的并发队列实现，使用两个独立的锁分别保护队列的头部和尾部，以允许多个入队和出队操作在一定程度上并行。

结构定义：

// 节点结构与链表类似
typedef struct __node_t {
    int value;
    struct __node_t *next;
} node_t;

typedef struct __queue_t {
    node_t          *head;      // 指向队列头部的哑元节点或前一个节点
    node_t          *tail;      // 指向队列尾部的最后一个实际节点
    pthread_mutex_t  head_lock;  // 保护对 head 指针的访问
    pthread_mutex_t  tail_lock;  // 保护对 tail 指针的访问
} queue_t;

初始化与哑元节点 (Dummy Node / Sentinel Node)：

void Queue_Init(queue_t *q) {
    node_t *tmp = malloc(sizeof(node_t));  // 1. 创建一个哑元节点
    tmp->next = NULL;                      // 哑元节点的 next 为 NULL
    q->head = q->tail = tmp;               // 2. 初始化时，head 和 tail 都指向这个哑元节点
    pthread_mutex_init(&q->head_lock, NULL);
    pthread_mutex_init(&q->tail_lock, NULL);
}

• 哑元节点的作用：
  • 简化边界条件： 使得空队列和非空队列的处理逻辑更统一。例如，队列中总有一个节点（哑元节点），即使队列逻辑上为空。
  • 分离头尾锁： 允许入队操作（主要涉及 tail 和 tail_lock）和出队操作（主要涉及 head 和 head_lock）在大多数情况下可以独立进行，从而提高并发性。head 指针实际上指向的是“即将被出队元素的前一个元素”（即当前的哑元节点），而 tail 指针指向的是“最后一个已入队的元素”。

入队操作 (Queue_Enqueue):

void Queue_Enqueue(queue_t *q, int value) {
    node_t *tmp = malloc(sizeof(node_t)); // 1. 为新元素分配节点
    assert(tmp != NULL); // 生产代码中应有更健壮的错误处理
    tmp->value = value;
    tmp->next  = NULL;

    pthread_mutex_lock(&q->tail_lock);   // 2. 获取尾锁，保护 tail 指针和原尾节点的 next 指针
    q->tail->next = tmp;                 // 3. 将新节点链接到当前尾节点的 next
    q->tail       = tmp;                 // 4. 更新 tail 指针指向新的尾节点
    pthread_mutex_unlock(&q->tail_lock); // 5. 释放尾锁
}

• 入队操作仅涉及 tail_lock，与出队操作的 head_lock 不冲突。

出队操作 (Queue_Dequeue):

int Queue_Dequeue(queue_t *q, int *value) {
    pthread_mutex_lock(&q->head_lock);   // 1. 获取头锁，保护 head 指针
    node_t *tmp       = q->head;         // 2. tmp 指向当前的哑元节点 (或旧的头部)
    node_t *new_head  = tmp->next;       // 3. new_head 指向实际要出队的第一个元素

    if (new_head == NULL) {              // 4. 检查队列是否为空 (即哑元节点的 next 为 NULL)
        pthread_mutex_unlock(&q->head_lock); // 如果为空，释放锁并返回错误
        return -1; // 队列为空
    }
    *value   = new_head->value;        // 5. 获取出队元素的值
    q->head  = new_head;               // 6. 更新 head 指针，使其指向刚刚出队的元素 (这个元素成为新的哑元节点)
    pthread_mutex_unlock(&q->head_lock); // 7. 释放头锁

    free(tmp);                         // 8. 释放旧的哑元节点 (之前 head 指向的节点)
    return 0;                          // 成功出队
}

• 出队操作仅涉及 head_lock，与入队操作的 tail_lock 不冲突。

优点：

• 并发性提高： 通过使用分离的头锁和尾锁，入队和出队操作在不为空或不为满（对于有界队列）的情况下可以并行执行，显著优于单锁队列。

局限性与后续讨论：

• 有界队列的处理： 书中指出的这种队列（仅使用锁）不能完全满足需要线程在队列为空（尝试出队时）或队列已满（尝试在有界队列上入队时）进行等待的需求。这自然地引出了下一章关于条件变量 (Condition Variables) 的讨论，条件变量可以与互斥锁结合使用来实现这种等待/通知机制。

29.4 并发哈希表 (Concurrent Hash Table, Figure 29.10)

哈希表通过将键映射到桶 (bucket) 来实现快速查找、插入和删除。并发哈希表的关键在于如何安全高效地处理对这些桶的并发访问。

实现思路：

• 哈希表由一个桶数组组成。
• 每个桶本身是一个独立的并发数据结构，用于处理哈希到该桶的所有键值对。书中示例使用前面讨论的并发链表 (单锁版本) 作为每个桶的实现。
• 对哈希表的操作（插入、查找）首先通过哈希函数确定键对应的桶索引，然后将操作委托给该特定桶的并发链表实例。

结构与操作：

#define BUCKETS (101)  // 哈希桶的数量，通常选择一个素数

// 假设 list_t, List_Init, List_Insert, List_Lookup
// 是前面定义的并发链表 (使用单锁保护每个链表实例)

typedef struct __hash_t {
    list_t lists[BUCKETS];  // 每个桶都是一个独立的并发链表实例
} hash_t;

void Hash_Init(hash_t *H) {
    int i;
    for (i = 0; i < BUCKETS; i++) {
        List_Init(&H->lists[i]); // 初始化每个桶的并发链表
    }
}

int Hash_Insert(hash_t *H, int key) {
    int bucket = key % BUCKETS; // 计算哈希桶索引
    // 将插入操作委托给对应桶的并发链表
    // 该链表的 List_Insert 内部会处理其自身的锁
    return List_Insert(&H->lists[bucket], key);
}

int Hash_Lookup(hash_t *H, int key) {
    int bucket = key % BUCKETS; // 计算哈希桶索引
    // 将查找操作委托给对应桶的并发链表
    return List_Lookup(&H->lists[bucket], key);
}

优点：

• 高可伸缩性 (Excellent Scalability, Figure 29.11)： 这是并发哈希表的核心优势。
  • 只要不同的键通过哈希函数映射到不同的桶，对这些键的操作就可以完全并行执行，因为每个桶（并发链表）有其自己独立的锁。
  • 锁的竞争被分散到了各个桶上，而不是集中在整个哈希表的一个全局锁上。
  • 书中实验显示，这种简单的并发哈希表性能远超单锁链表，并且随着并发更新数量的增加，性能扩展得非常好。

局限性与进一步的复杂性：

• 固定大小与调整大小 (Resizing)： 书中示例的哈希表是固定大小的（BUCKETS 是常量）。在实际应用中，当哈希表中的元素过多导致冲突增加（每个桶的链表过长）时，需要进行调整大小 (resizing) 操作（即创建一个更大的桶数组，并将所有元素重新哈希到新数组中）。
  • 并发环境下的哈希表调整大小是一个非常复杂的问题。它需要协调所有正在进行的插入、删除、查找操作，并确保在调整过程中数据的一致性和可用性，同时还要尽量减少对性能的影响。这通常需要更高级的并发控制技术。
• 哈希函数的质量： 一个好的哈希函数对于并发哈希表的性能至关重要。如果哈希函数导致大量键映射到少数几个桶，那么这些桶就会成为新的性能瓶颈，并发优势将大打折扣。

重要提示和经验教训 (Tips and Lessons Learned)

提示：当心锁和控制流 (Be Wary Of Locks And Control Flow)

• 问题： 在并发编程中，错误地管理锁（例如，忘记在某个代码路径释放锁）是常见的bug来源，可能导致死锁或资源泄漏。
• 场景： 许多函数会在开始时获取锁，然后执行一系列操作（可能包括内存分配、I/O等），这些操作可能会失败或有多个成功/失败的返回路径。
• 风险： 如果在每个可能的退出点都手动管理锁的释放，代码会变得复杂且容易出错。
  • 例如，在 malloc 失败后忘记释放锁，或者在循环中找到元素提前返回时忘记释放锁。
• 建议：
  • 简化控制流： 尽量构造代码，使得锁的获取和释放在逻辑上清晰配对，最好有单一的加锁点和单一的解锁点（或尽可能少的解锁点）。
  • RAII (Resource Acquisition Is Initialization) / Scope Guards： 在支持RAII的语言（如C++）中，可以使用栈上的锁对象，在其构造函数中获取锁，析构函数中释放锁。这样，无论函数如何退出（正常返回、抛出异常），锁都能被自动释放。其他语言可能有类似的 try-finally 或 defer 机制来确保资源释放。
  • 最小化临界区： 只在真正需要保护共享资源访问的代码段（临界区）内持有锁。将不依赖共享资源的操作（如内存分配、复杂计算）移到锁区域之外。

提示：更多并发不一定更快 (More Concurrency Isn’t Necessarily Faster)

• 误区： 认为通过增加锁的数量（例如，使用更细粒度的锁）或设计更复杂的并发方案，总能获得更好的性能。
• 现实：
  • 锁的开销： 获取和释放锁本身是有开销的（CPU周期、内存屏障等）。如果锁操作过于频繁，这些开销可能会抵消并发带来的好处。
  • 复杂性成本： 更复杂的并发方案通常更难设计、实现和调试。
  • 阿姆达尔定律 (Amdahl’s Law)： 程序中可并行的部分是有限的，性能提升受限于串行部分的执行时间。
• 建议：
  • 从简单开始： 对于新的并发数据结构，可以先从一个简单的、粗粒度的锁策略开始（例如，一个全局锁）。这更容易实现正确。
  • 性能分析驱动： 只有当性能分析（profiling）表明当前的锁策略确实是瓶颈时，才考虑更复杂的、更细粒度的锁方案。
  • 权衡利弊： 评估更复杂的方案带来的潜在性能提升是否值得其增加的实现难度和维护成本。
  • 实际测试： 实现不同并发程度的方案，并在目标负载下进行基准测试，以数据来决定哪种方案更好。书中提到：“一种获得真知的办法：实现两种方案（简单但少一点并发，复杂但多一点并发），测试它们的表现。”

提示：避免过早优化 (Knuth’s Law: “Premature optimization is the root of all evil”)

• 这是上述“更多并发不一定更快”提示的一个延伸和普遍原则。
• 核心思想： 在没有充分证据（通常来自性能分析）表明某个特定部分是性能瓶颈之前，不要花费时间和精力去优化它，尤其是当这种优化会增加代码复杂性或牺牲可读性时。
• 在并发数据结构中的应用：
  • 先保证正确性： 使用最简单直接的方法（如单锁）确保数据结构在并发环境下是线程安全的。
  • 再考虑性能： 如果（且仅当）这个简单方案在高并发下表现不佳，成为系统瓶颈时，才去寻找更优化的并发策略（如细粒度锁、无锁算法等）。
  • Linux BKL 示例： 书中提到，许多操作系统（包括早期的Linux）在向多处理器过渡时，最初也使用了单一的“大内核锁 (Big Kernel Lock, BKL)”。这种简单的方法在当时是有效的，但随着多核CPU系统成为主流，BKL成为了严重的性能瓶颈，才促使其被逐步分解为更细粒度的锁。这体现了先生效，再优化的过程。

总结与展望

1. 锁与控制流的谨慎处理： 是编写健壮并发代码的基础。
2. 并发性与性能的平衡： 理解锁的开销和竞争是关键。
3. 迭代优化的重要性： 从简单、正确的设计开始，通过性能分析驱动优化，避免不必要的复杂化。
4. 本章的局限性： 书中介绍的主要是基于锁的并发数据结构。在现代并发编程中，还有更高级的技术，如非阻塞数据结构 (Non-blocking Data Structures)（通常基于硬件原子操作如CAS），它们可以提供更好的可伸缩性和避免与锁相关的某些问题（如死、优先级反转），但设计和实现更为复杂。