跳转至

Synchronization Examples⚓︎

约 2539 个字 164 行代码 预计阅读时间 15 分钟

Classic Problems on Synchronization⚓︎

本节将介绍一些经典的同步问题，这些问题通常用于测试新提出的同步方案。

下面主要通过信号量来解决这些问题，因为这是比较传统的一种方式。当然前面介绍的同步工具也可以用，比如互斥锁。

The Bounded-Buffer Problem⚓︎

假设生产者和消费者进程共享以下数据结构：

int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0
  • 假设缓存池中有 n 个缓冲区，每个缓冲区都能包含一项
  • 二元信号量 mutex 提供了缓存池的互斥访问，初始化为 1
  • 信号量 empty 和 full 分别记录空的和满的缓冲区的数量，并分别初始化为 n 和 0

生产者进程和消费者进程的代码分别如下：

producer
while (true) {
        // ...
    /* produce an item in next produced */
        // ...
    wait(empty);
    wait(mutex);
        // ...
    /* add next produced to the buffer */
        // ...
    signal(mutex);
    signal(full);
}
consumer
while (true) {
    wait(full);
    wait(mutex);
        // ...
    /* remove an item from buffer to next consumed */
        // ...
    signal(mutex);
    signal(empty);
        // ...
    /* consume the item in next consumed */
        // ...
}

可以看到两段代码是对称的：生产者为消费者产生满的缓冲区，而消费者为生产者产生空的缓冲区。

The Readers-Writers Problem⚓︎

假如有一个数据库在多个并发进程中共享，其中一些进程仅读取数据库，另一些进程则可能更新数据库。我们分别用读者(reader) 和写者(writer) 来表示这两类进程。显然，如果两个读者同时访问共享数据，那么无事发生；但如果存在一个写者和另外的进程（无论是读者还是写者）同时访问数据，那就要出现问题了。

为避免问题发生，我们要求写者在向数据库写入时对数据库有独占访问权(exclusive access)。这样的同步问题就是读者 - 写者问题(readers-writers problem)。这类问题有多个变体，但都考虑了优先级：

  • 第一读者 - 写者问题：除非有写者已经获取对共享数据的权限，否则不该有任何读者处于等待状态
    • 也就是说读者之间无需相互等待对方
  • 第二读者 - 写者问题：一旦写者就绪，那它就应当尽快执行写操作
    • 也就是说当写者在等待访问数据时，没有新的读者开始读操作

任何对这些问题的解决方案都会导致饥饿(starvation)——第一种情况下，写者会饥饿；一种情况下，读者会饥饿。下面仅给出第一读者 - 写者问题的解决方案。假如读者进程共享以下数据结构：

semaphore rw mutex = 1;
semaphore mutex = 1;
int read_count = 0;
  • ru_mutex 同时用于读者进程和写者进程，作为写者的互斥信号量的同时，也为第一个 / 最后一个进入 / 退出临界区的读者进程所用
  • mutex 用于在 read_count 更新时确保互斥
  • read_count 跟踪并发读取对象的进程数

写者进程和读者进程的代码分别如下所示：

writer
while (true) {
    wait(rw_mutex);
        // ...
    /* writing is performed */
        // ...
    signal(rw_mutex);
}
reader
while (true) {
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);
    signal(mutex);
        // ...
    /* reading is performed */
        // ...
    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex);
    signal(mutex);
}
  • 若写者在临界区，且有 n 个读者等待，那么只有一个读者排队使用 rw_mutex，剩余 n - 1 个读者排队使用 mutex
  • 当写者执行 signal(rw_mutex) 时，调度器既可选择执行等待中的读者（们）或继续执行单个的写者

在一些系统上，这一问题被泛化至一种读者 - 写者锁上。获取该锁时需指明模式：读访问或写访问。多个并发进程可同时被授予读模式的读者 - 写者锁，但只有一个进程能获得写模式下的锁。这种锁在以下场景最有用：

  • 在容易识别出对共享数据只读和只写的进程的应用中
  • 在读者比写者更多的应用中

The Dining-Philosophers Problem⚓︎

哲学家就餐问题(dining-philosohpers problem) 是 OS 中经典的并发同步模型，大致内容如下：五位哲学家（进程）围坐在一张圆桌旁，相邻哲学家之间放着一根筷子，哲学家需要两根筷子才能进餐。这种比喻生动描述了以无死锁和无饥饿方式为多个进程分配资源的需求。

解决方案有：

  • 基于信号量：每根筷子就是一个信号量

    • 对于上面的问题，进程间的共享数据就是：

      semaphore chopstick[5];

    • 哲学家 i 的结构为：

      while (true) {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
        // ...
    /* eat for a while */
        // ...
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
        // ...
    /* think for awhile */
        // ...
}

    • 尽管上述方案保证没有两位邻居同时进食，但我们不应该用这个方法，因为死锁仍然可能会出现（每个人拿左手边的筷子后，如果有人想去拿右手边的筷子 ...）

    • 一些补救措施：
      • 至多允许 4 名哲学家坐在桌子旁
      • 规定仅当两边的筷子都可用时，哲学家才能去拿筷子
      • 使用非对称解决方案：奇数号哲学家先拿左手边的筷子，后拿右手边的筷子；偶数号哲学家的顺序相反

  • 基于管程

    • 管程提供了之前所说的一条限制：仅当两边的筷子都可用时，哲学家才能去拿筷子

    • 我们为哲学家规定了 3 中状态：

      enum {THINKING, HUNGRY, EATING} state[5];
      • 因此 state[i] = EATING（哲学家 i 可以进食）成立当且仅当 (state[(i+4) % 5] != EATING) && (state[(i+1) % 5] != EATING)（i 的两位邻居不在进食）

    • 另外声明以下变量，使得哲学家 i 在饥饿却无法获得所需筷子时能够延迟自己的行动

      condition self[5];

    • 筷子的分布由管程 DiningPhilosophers 控制，其定义如下：

      monitor DiningPhilosophers {
    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];

    void pickup(int i) {
        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();
    }

    void putdown(int i) {
        state[i] = THINKING;
        test((i + 4) % 5);
        test((i + 1) % 5);
    }

    void test(int i) {
        if ((state[(i + 4) % 5] != EATING) &&
            (state[i] == HUNGRY) &&
            (state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
        }
    }

    initialization code() {
        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }
}

      • 每位哲学家在开始进食前必须调用 pickup()，这会让哲学家进程挂起；完成操作后哲学家方可进食，随后哲学家调用 putdown()

        DiningPhilosophers.pickup(i);
    // ...
    // eat
    // ...
DiningPhilosophers.putdown(i);

Sychronization within the Kernel⚓︎

在 Linux 内核中，最简单的同步技术是原子整数(atomic integer)，用类型 atomic_t 表示。顾名思义，所有使用原子整数的数学运算不得被打断。下面展示部分运算：

atomic t counter;
int value;
原子运算 效果
atomic_set(&counter,5); counter = 5
atomic_add(10,&counter); counter = counter + 10
atomic_sub(4,&counter); counter = counter - 4
atomic_inc(&counter); counter = counter + 1
value = atomic_read(&counter); value = 12

由于没有锁机制产生的开销，因此使用原子整数会非常高效，但也仅限于部分情况（复杂的情况还是需要更精密的锁工具）。

Linux 支持互斥锁，相应提供的操作有 mutex_lock() 和 mutex_unlock()。

另外 Linux 也提供自旋锁和信号量（以及这两类锁的读者 - 写者版本）。

  • 对于单核处理器，只需启用 / 禁用抢占策略就能实现锁的效果，对应的系统调用为 preempt_disable() 和 preempt_enable()
  • 对于多核处理器，需要获取 / 释放自旋锁

Linux 中自旋锁和互斥锁都是非递归的，即线程不能连续获取两个相同的锁（在中间没有释放锁的前提下）。

POSIX Synchronization⚓︎

前面讲的同步方法都是偏底层的。下面介绍用户层的 POSIX API 提供的同步工具。

Mutex Locks⚓︎

#include pthread.h

pthread_mutex_t mutex;

/* create and initialize the mutex lock */
pthread_mutex_init(&mutex,NULL);

/* acquire the mutex lock */
pthread_mutex_lock(&mutex);

/* critical section */

/* release the mutex lock */
pthread_mutex_unlock(&mutex);

Semaphores⚓︎

POSIX 提供两类信号量：命名(named) 信号量和无名(unnamed) 信号量。本质上两者是相似的，但区别在于它们的创建以及在进程间的共享。

  • 命名信号量：多个无关进程可通过指代信号量名称来使用公共的信号量

    #include semaphore.h
sem_t *sem;

/* Create the semaphore and initialize it to 1 */
sem = sem_open("SEM", O_CREAT, 0666, 1);
    • 该信号量名为 SEM
    • O_CREAT 表示信号量不存在时会自动创建
    • 0666 表示授予其他进程对其的读写权限
    /* acquire the semaphore */
sem_wait(sem);

/* critical section */

/* release the semaphore */
sem_post(sem);

  • 无名信号量

    #include semaphore.h
sem_t sem;

/* Create the semaphore and initialize it to 1 */
sem_init(&sem, 0, 1);

/* acquire the semaphore */
sem_wait(&sem);

/* critical section */

/* release the semaphore */
sem_post(&sem);

Condition Variables⚓︎

pthread_mutex_t mutex;
pthread_cond_t cond_var;

pthread_mutex_init(&mutex,NULL);
pthread_cond_init(&cond var,NULL);

/**
pthread_mutex_lock(&mutex);
while (a != b)
    pthread_cond_wait(&cond var, &mutex);

pthread_mutex_unlock(&mutex);
**/

pthread_mutex_lock(&mutex);
a = b;
pthread_cond_signal(&cond var);
pthread_mutex_unlock(&mutex);

Alternative Approaches⚓︎

Transactional Memory⚓︎

事务内存(transactional memory) 的概念起源于数据库理论，它为进程同步提供了一种策略。

  • 内存事务 (memory transaction) 是一系列原子性的内存读写操作
  • 如果事务中的所有操作都完成，则事务被提交 (committed)
  • 否则，操作必须被中止 (aborted) 和回滚 (rolled back)

这种方法不使用传统的锁（如 acquire() 和 release()），而是使用如 atomic{S} 这样的语言结构，来确保 S 中的操作作为事务原子性地执行。

优点：

  • 由事务内存系统（而非开发人员）负责保证原子性
  • 因为不涉及锁，所以不可能出现死锁
  • 系统可以识别出 atomic 块中的哪些语句可以并发执行（例如对共享变量的并发读取），这在多线程应用中用读写锁手动实现会很困难

实现方式：

  • 软件事务内存(software transaction memory, STM)：完全在软件中实现，通过编译器插入“检测代码”到事务块中来进行管理
  • 硬件事务内存(hardware transaction memory, HTM)：使用硬件缓存层次结构和缓存一致性协议来管理和解决冲突
    • 由于不需要特殊的代码检测，因此开销更小，但需要修改硬件

OpenMP⚓︎

OpenMP 是一套编译器指令和 API ，用于支持共享内存环境中的并行编程。

  • 代码遵循 #pragma omp parallel 编译器指令后，即被标识为并行区域(parallel region)，由多个线程执行
  • 线程的创建和管理由 OpenMP 库处理，而不是应用程序开发人员

同步支持：

  • OpenMP 提供了 #pragma omp critical 编译器指令，用于指定一个临界区，确保一次只有一个线程可以在该区域中活动
  • 这可以防止对共享变量（例如 counter += value）的竞争条件
  • 该指令的行为很像二元信号量或互斥锁

优点：通常比标准互斥锁更容易使用。

缺点：

  • 开发人员仍必须识别可能的竞争条件，并使用该指令充分保护共享数据
  • 由于其行为类似互斥锁，当识别出两个或多个临界区时，仍然可能发生死锁

Functional Programming Languages⚓︎

大多数主流语言都是命令式(imperative) 或过程式语言，它们是基于状态的 (state-based)，其状态（如变量）是可变的 (mutable)。而函数式(functional) 编程语言遵循一种完全不同的范式 ：

  • 不维护状态
  • 变量是不可变的(immutable)：一旦被定义和赋值，其值就不能改变
  • 由于函数式语言不允许可变状态，它们不必担心竞争条件和死锁等问题

评论区

如果大家有什么问题或想法，欢迎在下方留言~