💻 CSC3150 Week 4 Concurrency & Synchronization

Lithos

CSC3150 Lecture6 Concurrency

⚠️ Threaded programs must work for all interleavings of thread instruction sequences.

Revision of Threads

回忆 Thread……

多线程并发的速度和资源复用的优势隐含着 race condition 的风险。

线程共享但内存需同步，进程独立但共享需通道。Tradeoff: protection vs. sharing

⚠️ 易混淆概念：

  • Multiprocessing：多进程就是多 CPU (多处理器)，意味着并行 (parallelism)
  • Multiprogramming：多个任务/进程共用 CPU，单核可行，代指并发 (concurrency)
  • Multithreading：进程含有多个线程，不保证并行或并发/单核或多核，仅描述程序组织方式。

依旧老生常谈的非原子操作 (non-atomic op.) —— 自增 (increment) 的例子：

pthread_t tid[2];
int counter = 0;
void *do_something(void *arg) {
    for (int i = 0; i < 1000; i++) counter += 1;
    return NULL;
}
int main(void) {
    pthread_create(&(tid[0]), NULL, &do_something, NULL);
    pthread_create(&(tid[1]), NULL, &do_something, NULL);
    pthread_join(&(tid[0]), NULL);
    pthread_join(&(tid[1]), NULL);
    printf(“Counter %d\n”, counter);
    return 0;
}

⚠️ 只有 global/static 变量会发生 race，因为它们处于同个进程中共享的堆上！比如 for 循环条件中的自增项 i 就在两个线程各自的栈上，不会冲突。

两个线程自增同个 counter 变量各 1000 次，但结果不必是 2000，每次运行都可能结果不一。+= 1 的本质是三个汇编命令：

LOAD counter → regn
ADD  regn, 1
STORE regn → counter

Scheduler 在切换时可能发生诸如以下的情况：

< Thread 1 >                   < Thread 2 >
... ...
load counter → r1
r1 = 5
           context switch →
                               load counter → r2
                               r2 = 5
                               r2 = r2 + 1
                               r2 = 6
           ← context switch
r1 = r1 + 1
r1 = 6
store r1 → counter = 6
           context switch →
                               store r2 → counter = 6

在线程写回前切换，发生了 Lost Update。理论上，以上代码运行结果很可能小于 2000，在极端交错下甚至可以落在 1～1000。

Concurrency 的核心是：

多个 execution sequences 的执行可能交错 (interleave) —— 单核也可以错。所以多线程需要 synchronization (同步机制) 协调，例如 mutex、semaphore、atomic operation 等。

Non-deterministic Interleaving：因为 threads 没有彼此隔离，而且共享 address space，scheduler 可以产生不同的 interleaving。线程内有顺序，但线程间没有自动规定顺序。

如此，程序结果依赖多个并发执行之间不可控的 timing / interleaving —— Race Condition



Tradeoff of Threads

为什么明知有风险还要线程？

处理庞大数据流时，如 ATM server、enrollment system、public database…如果只有一个 sequential execution，CPU 大量时间被浪费。即使只有一个 CPU，仍希望 overlap I/O & computation。

  • 如果不用线程，必须写成 Event-driven Style，即循环检测事件以触发对应操作。效率尚可，但程序逻辑被打碎 (deconstructing into non-blocking fragments)，对开发者不太友好。

  • 如果使用线程，程序员仍然可以用非常自然的 sequential code，OS scheduler 负责切换。所以 Threads 给我们：Sequential Programming Model + Concurrent Execution。

以银行 ATM Server 为例，每个 request 都作为一条线程，保持自身内部顺序逻辑，同时彼此 overlap。

while (TRUE) {
    receive_request(...);
    START_THREAD(
        process_request(...)
    );
}

由于线程的 race condition，两个人同时向同个账号汇款可能导致信息覆盖。不是说线程本身危险，而是 并发和共享可变数据 本身就潜在风险。



Atomic Operations

原子操作：只能一次性执行到底或完全不开始执行的指令 (集)

  • 不可分割——其内部对外部不可见 (invisible)，便不能在中间截断

  • 没有原子操作，线程无法安全合作

  • 大部分机器上记忆的按字读写 (word-sized load, store) 都是原子操作。

    word：4B on 32b machine, 8b on 64b, etc.

很多指令都不是原子的：“i = i + 1”、双精度浮点 (d-fp) store、VAX/IBM360 拷贝数组的命令…



Mutex and Locks

多线程代码必须适应所有 Interleaving 情况结果 (non-deterministic)

  • Synchronization：使用原子操作以协调多线程执行

  • Mutual Exclusion (Mutex)：一种特殊的 synch.，某件事情同时段只能一个线程做，用于保护关键代码段

  • Critical Section：同时段最多允许一个线程执行的代码区域 (互斥 Mutex 保护的对象)

  • Lock：同时段只能由一个线程持有的 object，用于实现 Mutex。提供给线程两个原子操作 API——

    lock.acquire(&lock)：等 lock free 后，调用该指令的线程占有 lock (hold the lock)，.acquire 尤其必须是 atomic —— 检查锁状态和上锁必须不可分割，否则多个线程都可能“抢到锁”。

    lock.release(&lock)：占锁的线程调用以释放 lock。

    在 CS 前后加 lock 指令使后续线程无法打断正在执行的线程。因此不会 overlap。

Lock 的初始化：

pthread_mutex_t lock;
pthread_mutex_init(&lock, NULL);

比如 ATM 存钱问题…

pthread_mutex_t lock;
pthread_mutex_init(&lock, NULL);
deposit(acctId, amount) {
    acquire(&lock);
    acct = get_account(acct_id); //
    acct->balance += amount;     // Critical Section
    store_account(acct);         //
    release(&lock)

Designing of Locks

检查锁状态和上锁必须不可分割，否则多个线程都可能“抢到锁” —— 比如检查有没有牛奶和留下“我去买了”纸条必须同时完成，不然第二个人可能在第一个人贴纸条前认为自己没看到纸条，然后也去买了。

  1. 如果不是原子操作，这个锁的方案会使问题更糟，因为无法确定哪次会失败 (fails intermittently) ——不可知性比必然失败更恶心。

    • “不确定是否安全还不如绝对不安全”

  2. 那如果我们先“留纸条” (声明上锁) 在“检查有无牛奶” (检查锁状态) 呢？呃…对于人类这个逻辑可能很清晰，但人机计算机 (字面意思) 就100% 不会运行 Critical Section了，因为检查时永远被自己上锁了…

    • “你就说绝对无法运行安全不安全吧”

  3. 如果先留纸条且署名呢？如果有纸条但不是我写的纸条就不买？那很谦让了：

    A：“I’m not getting milk, you’re getting milk.”

    B：“You said you are going, I’m not getting it"

    A：”But you also said you’re buying milk, so I shouldn’t"

    …… starvation, what a way to die

    A 声明上锁后切到 B 上锁，完了，谁也没法运行 Critical Section 了。

    • “安全但可能无法运行，这种最阴了”

  4. 多边不对称解法

    A：如果有 B 纸条：你想买？好，我等你。

    B：如果有 A 纸条：你想买？好，我不买了。

    相当于人为规定冲突时 B 让 A：

    leave note_A;           leave note_B;
while (note_B) { <----> if (no_note_A) {
    do nothing              if (no_milk) {
}                               buy_milk();
if (no_milk) {              }
    buy_milk();         }
}                       remove note_B;
remove note_A;

为何这正确？假设 Sequencial Consistency：There is a single, global order of loads and stores, and operations issued by each thread are processed in program order 即每个线程确定自己内部的执行顺序不能乱

  • 在这个前提下，线程不发生乱序执行，不考虑现代编译器/调度器的 ordering。

  • 如果 A 先留纸条，B 就会撕掉纸条让 A 干，如果 B 先看有没有纸条早于 A 留纸条，B 就不会撕纸条，A 就只能等 B 买完牛奶，无论如何，不冲突。

问题是这个不对称解法过于复杂，在现实机器中经常存在成百上千条多线程，怎么谁记每个线程不同的上锁协议？对代码长度负担太大，且不对称所需的等待会消耗大量 CPU 时间 (⚠️ busy-waiting)。

Leslie Lamport’s Bakery Algorithm (1974) 证明了理论上可以用 shared memory 的读写设计复杂的软件 mutual exclusion protocol…但这太复杂了。

说到底，我们本质上还是想要两个原子操作 API acquire & release 来确保 Synchronization。




CSC3150 Lecture7 Synchronization

comments powered by Disqus