CSCI3150 L15 并发故障

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L15 并发故障，第 2 部分 / 共 2 部分 · 原件 L15-信号量与常见并发问题-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.31–55 定位：区分原子性、顺序与死锁问题，再针对其依赖关系选择修复。 前后：前接 信号量；可回到 阅读导航串联全课。

逐页伴读

p.31为Part II标题，原文Currency是Concurrency的拼写误差。

p.32–33：并发错误不全是死锁

p.32 More recent work focuses on studying other types of common concurrency bugs.

Take a brief look at some example concurrency problems found in real code bases.

Focus on four major open-source applications

MySQL, Apache, Mozilla, OpenOffice.

课件样本表MySQL为14非死锁/9死锁，Apache13/4，Mozilla41/16，OpenOffice6/2，总计74/31，共105项。非死锁占74/105≈70.48%，死锁29.52%。这是引用研究样本的分布，不能当成所有软件或当期考试的比例。随后重点拆分非死锁的原子性违反与顺序违反。

表（p.32）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

p.34–35：检查后使用需要共同保护

p.34 The desired serializability among multiple memory accesses is violated.

Simple Example found in MySQL:

Two different threads access the field proc_info in the struct thd.

课件程序与接口（p.34，原页片段）

1     Thread1::
2     if(thd->proc_info){
3       …
4   fputs(thd->proc_info , …);
5   …
6     }
7
8     Thread2::
9     thd->proc_info = NULL;

p.35 Solution: Simply add locks around the shared-variable references.

课件程序与接口（p.35，原页片段）

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

 Thread1::
 pthread_mutex_lock(&lock);
 if(thd->proc_info){
    …
    fputs(thd->proc_info , …);
    …
 }
 pthread_mutex_unlock(&lock);

 Thread2::
 pthread_mutex_lock(&lock);
 thd->proc_info = NULL;
 pthread_mutex_unlock(&lock);

原例T1执行 if(thd->proc_info) ... fputs(thd->proc_info,...)，T2可设 thd->proc_info=NULL。若T2插入检查与使用之间，检查通过不保证使用时仍非空。修复让T1从检查到使用全程持同一锁，T2赋值也用此锁；只给赋值或只给if上锁均不足。

p.36–38：互斥不能自动规定谁先发生

p.36 The desired order between two memory accesses is flipped.

i.e., A should always be executed before B, but the order is not enforced during execution.

Example:

The code in Thread2 seems to assume that the variable mThread has already been initialized (and is not NULL).

课件程序与接口（p.36，原页片段）

Thread1::
 void init(){
    mThread = PR_CreateThread(mMain, …);
 }

 Thread2::
 void mMain(…){
    mState = mThread->State
 }

p.37 Solution: Enforce ordering using condition variables

课件程序与接口（p.37，原页片段）

pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
 pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER;
 int mtInit = 0;

 Thread 1::
 void init(){
    …
    mThread = PR_CreateThread(mMain,…);

    // signal that the thread has been created.
    pthread_mutex_lock(&mtLock);
    mtInit = 1;
    pthread_cond_signal(&mtCond);
    pthread_mutex_unlock(&mtLock);
    …
 }

 Thread2::
 void mMain(…){
    …

课件程序与接口（p.38，原页片段）

// wait for the thread to be initialized …
    pthread_mutex_lock(&mtLock);
    while(mtInit == 0)
        pthread_cond_wait(&mtCond, &mtLock);
    pthread_mutex_unlock(&mtLock);

    mState = mThread->State;
    …
}

原例创建线程的返回值要赋给mThread，但新线程可能在赋值完成前运行并访问 mThread->State。它需要“初始化完成后才能用”的顺序保证。课件用mtInit谓词、mtLock与mtCond：初始化完成后持锁设1并通知；使用者持锁while等到1再继续。只各自加锁却允许使用者先抢到，仍不满足先后关系。

p.39–41：画出谁持有、谁等待

p.39 The presence of a cycle

Thread1 is holding a lock L1 and waiting for another one, L2.

Thread2 that holds lock L2 is waiting for L1 to be release.

p.40 Reason 1:

In large code bases, complex dependencies arise between components.

Reason 2:

Due to the nature of encapsulation

Hide details of implementations and make software easier to build in a modular way.

Such modularity does not mesh well with locking.

p.41 Example: Java Vector class and the method AddAll()

Locks for both the vector being added to (v1) and the parameter (v2) need to be acquired.

The routine acquires said locks in some arbitrary order (v1 then v2).

If some other thread calls v2.AddAll(v1) at nearly the same time  We have the potential for deadlock.

课件程序与接口（p.41，原页片段）

Vector v1,v2;
 v1.AddAll(v2);

两锁原例T1先L1后L2，T2先L2后L1；在各取得第一把后，图形成T1等L2、L2由T2持有、T2等L1、L1由T1持有的环。封装可能隐藏获取次序：v1.AddAll(v2) 与 v2.AddAll(v1) 看似对象方法，内部却以相反次序取两对象锁。

补充：用一张等待表把“程序不动了”变成可证明的死锁。 沿两锁原例，在T1成功取得L1、T2成功取得L2之后：

两线程都在阻塞式获取第二把锁，释放各自第一把锁的语句又位于后面，所以没有一方能执行解除对方等待的动作。若只是T1等待L2、T2正正常计算并最终释放，则不是这个死锁；等待需要结合持有关系与可执行路径判断。

统一锁序的证明也从表出发：所有线程只能持较小编号再请求较大编号，一条等待链的锁编号严格增加，有限集合中不可能沿链回到更小的起点。该证明依赖所有参与者遵守同一个顺序，嵌套函数内部获取的隐藏锁也算，不能只检查当前函数显式出现的两行。

p.42–44：破坏必要条件来预防

p.42 Four conditions need to hold for a deadlock to occur.

If any of these four conditions are not met, deadlock cannot occur.

p.43 Provide a total ordering on lock acquisition

This approach requires careful design of global locking strategies.

Example:

There are two locks in the system (L1 and L2)

We can prevent deadlock by always acquiring L1 before L2.

p.44 Acquire all locks at once, atomically.

This code guarantees that no untimely thread switch can occur in the midst of lock acquisition.

Problem:

Require us to know when calling a routine exactly which locks must be held and to acquire them ahead of time.

Decrease concurrency

课件程序与接口（p.44，原页片段）

1    lock(prevention);
2    lock(L1);
3    lock(L2);
4    …
5    unlock(prevention);

死锁四个必要条件是互斥、持有并等待、不可强制抢占、循环等待。全局锁序L1<L2让所有线程都先L1后L2，消除环。p.44用prevention锁串行化整批获取，意图避免多个线程各拿一部分再互等；所有参与者须遵守协议且预先知道所需锁。

课件说这种写法保证获取中不会发生不合时宜的线程切换，措辞不精确：mutex不禁止调度切换，它限制其他遵守同一prevention锁的线程同时进入获取阶段。持有业务锁的旧线程如何释放也须不依赖该prevention锁，否则仍可能另造依赖。

表（p.42）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

补充：用反证法说明全局锁序为什么能破环。 给所有参与锁设一致的严格顺序。线程只有在已经持有较小锁时才请求更大锁。若仍存在循环等待，从环上一把锁出发，沿每一条“持有后还请求”的关系，锁的序号必须严格变大；绕一圈回到起点，就要求同一个序号严格大于自身，矛盾。因此这一协议排除了这些锁组成的等待环。

证明的前提是所有路径都遵守同一顺序，包括错误恢复、辅助函数和回调；只检查主函数里的两行不够。该证明也只覆盖按这个规则获取的锁，不能顺便保证条件变量、I/O 或其他资源都不会形成等待依赖。最后，破坏死锁的一个必要条件能够排除相应死锁，但四个条件的术语同时出现，不等于某一时刻一定已经死锁；仍应画出具体资源与等待关系。

p.45–46：失败释放再试，仍可能活锁

p.45 Multiple lock acquisition often gets us into trouble because when waiting for one lock we are holding another.

trylock()

Used to build a deadlock-free, ordering-robust lock acquisition protocol.

Grab the lock (if it is available).

Or, return -1: you should try again later.

课件程序与接口（p.45，原页片段）

top:
    lock(L1);
    if( tryLock(L2) == -1 ){
        unlock(L1);
        goto top;
    }

p.46 livelock

Both systems are running through the code sequence over and over again.

Progress is not being made.

Solution:

Add a random delay before looping back and trying the entire thing over again.

原伪代码先L1，尝试L2失败就释放L1重试。它避免抱着L1阻塞等L2，却可能两线程同步重试、同步失败，忙着执行而无进展，即livelock。随机退避有助于打散节奏，但不是对任意调度的绝对完成证明。

课件把tryLock失败写-1，是其伪接口约定；pthread_mutex_trylock真实返回非零错误码，不能直接照抄 == -1。

p.47–48：CAS循环需正确原子和成功条件

p.47 wait-free

Using powerful hardware instruction.

You can build data structures in a manner that does not require explicit locking.

课件程序与接口（p.47，原页片段）

int CompareAndSwap(int *address, int expected, int new){
    if(*address == expected){
        *address = new;
        return 1; // success
    }
    return 0;
 }

p.48 We now wanted to atomically increment a value by a certain amount:

Repeatedly tries to update the value to the new amount and uses the compare-and-swap to do so.

No lock is acquired

No deadlock can arise

livelock is still a possibility.

课件程序与接口（p.48，原页片段）

void AtomicIncrement(int *value, int amount){
    do{
        int old = *value;
    }while( CompareAndSwap(value, old, old+amount)==0);
 }

CompareAndSwap原子比较当前值与expected，相等则改new并按本讲约定返回1，不等返回0。原增量例应不断读old、尝试old+amount，直到CAS成功。p.48把old声明在do块内却在while条件引用，普通C作用域不成立；下面是校正后的机制伪代码：

do:
    old = atomic_load(value)
while CAS(value, old, old + amount) == 0

CAS重试算法可能使某线程无限失败。课件用wait-free称呼过宽：wait-free要求每个线程在有限自身步骤完成，仅“没显式锁”不足以证明。原子类型和内存顺序也需按真实语言接口处理。

p.49–50：链表插入的两个修复与一处条件错误

p.49 More complex example: list insertion

If called by multiple threads at the “same time”, this code has a race condition.

课件程序与接口（p.49，原页片段）

void insert(int value){
    node_t * n = malloc(sizeof(node_t));
    assert( n != NULL );
    n->value    = value ;
    n->next     = head;
    head    = n;
 }

p.50 Solution:

Surrounding this code with a lock acquire and release.

wait-free manner using the compare-and-swap instruction

课件程序与接口（p.50，原页片段）

void insert(int value){
    node_t * n = malloc(sizeof(node_t));
    assert( n != NULL );
    n->value = value ;
    lock(listlock); // begin critical section
    n->next = head;
    head    = n;
    unlock(listlock) ;  //end critical section
 }

课件程序与接口（p.50，原页片段）

void insert(int value) {
    node_t *n = malloc(sizeof(node_t));
    assert(n != NULL);
    n->value = value;
    do {
        n->next = head;
    } while (CompareAndSwap(&head, n->next, n));
 }

原无锁插入先 n->next=head 再 head=n；两个线程读到同一个旧head时，最后写head的人会使另一新节点不可达。互斥版锁住这两步即可；节点私有初始化可在锁外做。

CAS版每次令n->next等于当前head，再尝试把head从该旧值改为n。按p.47“成功返回1”的约定，p.50的 while(CompareAndSwap(...)) 条件写反：应在 ==0 时重试。否则成功后再循环甚至可能令n->next指向n而形成自环。该校正只讨论插入核心机制，完整无锁结构还涉及内存回收等课件未展开问题。

补充：在 p.50 的错误重试条件上实际走两轮。 设初始链头为 H，新节点为 N，CAS 按本讲约定成功返回 1，且先假设没有其他线程干扰。

错误不需要另一线程才能触发。反过来，如果第 1 轮因别人改了 head 而失败，CAS 返回 0，原 while 恰好退出，N 又根本没插进去。因此校正必须是“失败重试、成功退出”。校正后仍要在每次失败后重新读取当前 head 并重写 N.next：例如别人先把 B 插入 H 前面，下一轮就应令 N.next=B，成功后得到 N→B→H，才能保留别人的更新。这段分析沿用课件的抽象原子操作，普通 C 指针读写不能直接代替实际的原子类型与发布规则。

p.51–53：避免法牺牲一部分并行度

p.51 In some scenarios deadlock avoidance is preferable.

Global knowledge is required:

Which locks various threads might grab during their execution.

Subsequently schedules said threads in a way as to guarantee no deadlock can occur.

p.52 Example of Deadlock Avoidance via Scheduling (1)

p.52 We have two processors and four threads.

Lock acquisition demands of the threads:

A smart scheduler could compute that as long as T1 and T2 are not run at the same time, no deadlock could ever arise.

p.53 Example of Deadlock Avoidance via Scheduling (2)

p.53 More contention for the same resources

A possible schedule that guarantees that no deadlock could ever occur.

The total time to complete the jobs is lengthened considerably.

第一张原需求表：T1、T2都用L1/L2，T3只用L2，T4无锁。使T1/T2不重叠，并让T3/T4在另一CPU运行，可避开二者相反取锁造成的环。第二张T3也需两锁，于是把T1、T2、T3串行，T4另核运行，并行机会更少。

图没有精确执行时长，不能按矩形宽度报一个数值总时间。补充等长情形：若各任务独立用时t且忽略锁等待，第一计划约2t，第二约3t，说明代价，不是原图实测值。方案依赖事先知道完整资源需求。

表（p.52）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

表（p.53）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

p.54–55：检测恢复与整讲回看

p.54 Allow deadlock to occasionally occur and then take some action.

Example: if an OS froze, you would reboot it.

Many database systems employ deadlock detection and recovery technique.

A deadlock detector runs periodically.

Building a resource graph and checking it for cycles.

In deadlock, the system need to be restarted.

p.55 Semaphore

Definition: sem_init(), sem_wait(), and sem_post()

Applications: Lock, Condition Variable, Producer/Consumer, Read/Write Locks, and Dinning Philoshpers

Common Concurrency Problems

Non-deadlock bugs

Atomicity Violation and Order Violation

Deadlock bugs

Conditions of deadlock

Prevention

Next: Review

检测允许死锁发生，再发现依赖环、选择恢复动作。单实例锁的等待环可证明死锁；多实例资源须更细判断，不能对任意资源图见环就下结论。课件举重启，数据库也可中止并回滚部分事务，未必重启整个系统。

最后按故障问诊：检查与使用被插队→原子性；初始化前使用→顺序；彼此占有并相互等待→死锁；一直重试无进展→活锁；某线程长期拿不到机会→饥饿。它们需要不同证据和修复。

本讲核心考点

• [C] 区分原子性违反与顺序违反并给出具体交错。
• [C] 列出死锁四条件，说明统一锁序破坏哪一条。
• [C] 区分死锁、活锁和饥饿。
• [C] 根据CAS返回约定判断重试条件并追踪失败插入。
• [C] 比较预防、避免、检测恢复及并行度代价。
• [C] 辨别lock-free/wait-free术语与课件示例代码缺陷，属于校正拓展。

附录

本份没有需要移至附录的长推导；计算过程已在对应页正文写全。

来源与证据

• 原件：L15-信号量与常见并发问题-2022未核.pptx（本地课件）；PDF副本（本地课件） p.31–55。本文页码均为 PDF 页号。

• 考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无

• 2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。