CSCI3150 L13 线程与竞争

课程：CSCI3150 Introduction to Operating Systems · 2022未核本讲：L13 线程与竞争，第 1 部分 / 共 2 部分 · 原件 L13-线程与线程API-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.1–37 定位：把多个线程的寄存器状态与同一份共享内存分开追踪，定位丢失更新。前后：前接 L12；后接线程API。

逐页伴读

p.1是讲题；p.2把线程放在内存与并发控制之间；p.3是Part I标题。

p.4–6：共享地址空间，分别保存执行位置

p.4 A new abstraction for a single running process

Multi-threaded program

A multi-threaded program has more than one point of execution.

Multiple PCs (Program Counter)

They share the same address space.

p.5 Each thread has its own program counter and set of registers.

One or more thread control blocks(TCBs) are needed to store the state of each thread.

When switching from running one (T1) to running the other (T2),

The register state of T1 be saved.

The register state of T2 restored.

The address space remains the same.

p.6 The heap segment: contains malloc’d data dynamic data structures (it grows downward)

p.6 (it grows upward)

The stack segment: contains local variables arguments to routines, return values, etc.

一个进程可有多个执行流，每个线程有自己的PC和寄存器。切换线程时保存T1、恢复T2的状态，通常不必更换同进程的地址空间。TCB保存线程状态，不能把TCB和共享堆数据混为一物。

图p.6左侧单栈，右侧两栈共享代码和堆。每线程的函数调用、局部变量、返回地址需要各自栈，但“有自己的栈”不表示其他线程绝对不能通过指针访问它；生命周期与同步仍须正确。

补充：线程私有的是执行状态，不是一个隔绝的“小进程”。 同一进程的两个线程能通过共享指针访问同一个堆对象，也可以访问另一个线程仍然有效的栈对象。各有一份栈的意义是调用链互不覆盖，不是硬件按线程把栈地址全部隔离。把局部变量地址传给线程时，必须保证原函数未返回、对象仍有效，并避免并发无同步修改。

对比fork：两个普通进程的同名局部变量通常是私有副本；两个线程通过同一个对象地址访问的则是同一存储。做题先画“对象有几份”，再画“执行流有几个”。只数函数被调用几次却不确定它们在访问哪份数据，无法判断有没有共享竞争。

p.7–9：两个worker同时改一个counter

p.7 The OS is juggling many things at once, first running one process, then another, and so forth.

Modern multi-threaded programs also exhibit the concurrency problem.

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

1   #include <stdio.h>
2   #include <stdlib.h>
3   #include <pthread.h>
4
5   volatile int counter = 0;
6   int loops;
7
8   void *worker(void *arg) {
9       int i;
10      for (i = 0; i < loops; i++) {
11          counter++;
12      }
13      return NULL;
      }

p.9 The main program creates two threads.

Thread: a function running within the same memory space. Each thread start running in a routine called worker().

worker(): increments a counter

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

16  int
17  main(int argc, char *argv[])
18  {
19      if (argc != 2) {
20          fprintf(stderr, "usage: threads <value>\n");
21          exit(1);
22      }
23      loops = atoi(argv[1]);
24      pthread_t p1, p2;
25      printf("Initial value : %d\n", counter);
26
27      pthread_create(&p1, NULL, worker, NULL);
28      pthread_create(&p2, NULL, worker, NULL);
29      pthread_join(p1, NULL);
30      pthread_join(p2, NULL);
31      printf("Final value : %d\n", counter);
32      return 0;
33  }

原例的共享变量是 volatile int counter=0; int loops;，每个worker执行：

for (i = 0; i < loops; i++) {
    counter++;
}

main从参数读取loops，创建p1、p2，分别join后输出counter。创建让两个worker有机会交错；join仅保证main打印前它们已结束，不保证worker之间互斥。volatile也不会把“读、加、写”合成原子更新。

p.10–12：理想计数与观测值为何不同

p.10 loops determines how many times each of the two workers will increment the shared counter in a loop.

loops: 1000.

loops: 1000000000

.

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

prompt> gcc -o thread thread.c -Wall -pthread
prompt> ./thread 1000
Initial value : 0
Final value : 2000

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

prompt> ./thread 1000000000
Initial value : 0
Final value : 1997974414 // huh??
prompt> ./thread 1000000000
Initial value : 0
Final value : 1997940107 // what the??

p.11 Increment a shared counter  take three instructions.

Load the value of the counter from the memory into a register.

Increment it

Store it back into the memory

These three instructions do not execute atomically.  Problem of concurrency happen.

原课件输入1000时观测2000；输入1,000,000,000时两次观测1,997,974,414和1,997,940,107。顺序原子累加的数学目标是2,000,000,000，分别少2,025,586和2,059,893。这些是课件记录，不是所有机器的确定输出。

下面用课件的简化机器指令模型解释一次丢失更新：初值50，T1读50加到51但未写回；切到T2，T2仍读50、加到51并写回；切回T1，它把自己寄存器里的51写回，最终51而非52。语言层补充：对普通共享C整数进行无同步并发读写属于数据竞争，不能把这个教学模型的数值范围当作C程序的完整保证。

p.13–15：T1取指与读取共享值

p.14 Step 1: Fetch instruction from the memory (PC->Address=100)

图p.13初始PC100、eax0、内存counter50。p.14把地址100的load取进指令寄存器，这一步还没有修改counter。p.15执行load，eax变50，内存仍50。要分别看“指令从哪里取”和“数据读到哪里”。

p.16–18：T1加的是寄存器

p.16 Step 4: Increase PC (pointed to the next instruction in the memory)

p.17 Step 1: Fetch instruction from the memory (PC->Address=105)

p.16 PC前进到105；p.17取出加一指令；p.18执行后eax51而counter仍50。源码看起来已经做了 ++ 的一部分，另一个线程却还看不到新值，因为store没有发生。

p.19–21：保存T1，恢复T2

p.19 Step 3: Increase PC (pointed to the next instruction in the memory)

p.19 PC变108，下一条应是store。p.20中断把T1的PC108与eax51存到线程状态区。p.21恢复T2的PC100、eax0；共享counter没有随上下文一起回滚或复制，它仍是50。

p.22–24：T2读到旧counter

p.22 T2从100取load，p.23读到仍未更新的50，p.24 PC变105。T1保存区里的51不会自动传给T2的eax，这正是把寄存器与共享内存分开看的理由。

p.25–27：T2独立算出51

p.25取add，p.26使T2的eax50→51，p.27 PC走到108。现在两个线程各自持有一个51，但共享counter还是50；没有哪个操作计算过52。

p.28–30：T2率先写回

p.28 Step 1: Fetch instruction from the memory (PC->Address=108)

p.28取store，p.29把T2的51写入counter，p.30 PC前进113。一份共享状态完成了一次递增。图中靠近代码地址的额外“113”属于执行位置注记，不能读成counter的新数值。

p.31–33：切回T1时，旧寄存器值仍在

p.31保存T2的113和51；p.32恢复T1的108和51；p.33取T1尚未执行的store。图p.33部分T2保存区又显示初始100/0，与前一页保存值不一致；实际因果链应保留p.31的113/51，该图错置不影响T1即将覆盖counter的关键状态。

p.34–35：最后的store覆盖同一个51

p.34 T1执行store，counter从51写成51；p.35 PC变113，两次递增都完成，但共享结果只有51。若从T1的load到store期间不允许另一个线程进入相同更新区，第二次就会读51并写52。

p.36–37：临界区应包住整个不变量维护过程

p.36 A piece of code that accesses a shared variable and must not be concurrently executed by more than one thread.

Multiple threads executing critical section can result in a race condition.

Need to support atomicity for critical sections (mutual exclusion)

p.37 Ensure that any such critical section executes as if it were a single atomic instruction (execute a series of instructions atomically).

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

1    lock_t mutex;
2    . . .
3    lock(&mutex);
4    balance = balance + 1;
5    unlock(&mutex);

课件用 lock(&mutex); balance=balance+1; unlock(&mutex); 表达互斥。不能只锁store，因为读和计算仍可基于旧值；也不能让两个线程各锁一把不同的锁。所有竞争访问必须遵守同一保护协议，才能让这段更新对其他线程表现得不可分割。

补充：从一次失败轨迹到正确性要求。 原课件展示 T1、T2 都读 50，再先后写 51。这一条合法交错已经足以反驳“无锁更新总能得到 52”；无需证明每次运行都错。相反，某次恰好先完整运行 T1、再运行 T2 而得到 52，只说明这一条交错没暴露错误，不能证明其他交错安全。

加锁的证明目标也不应只写“这次输出正确”。应说明：所有访问共享计数的竞争者使用同一把有效的锁；一次读取、计算、写回之间没有其他受该协议保护的更新插入；每次成功更新都使值增加一；所有线程的更新次数合计决定最终计数。C 中未同步的冲突读写还可能构成数据竞争，课件的三指令交错是帮助理解的一种机器级失败示意，不能把它当成错误 C 程序所有可能行为的完整清单。

用不变量选择临界区，而非看到赋值就加锁（补充）

自取一个两账户例子：A=10、B=20，把3从A转给B，需要先A减3再B加3。若要求任何观察者都看到总额30，两个更新必须作为一个整体保护；仅分别锁住两个赋值，会允许观察者在中途看到A=7、B=20，总额27。并发错误可以发生在多个变量的关系上，不只是单个counter自增。

锁本身也属于共享协议：写者和需要一致视图的读者都须遵守相同规则。持锁期间可以被OS暂停，另一个线程甚至可以在别核运行；只是它不能越过同一锁进入受保护区域。因此“临界区原子”指其他遵约访问看不见其部分状态，并不等于CPU关闭一切中断。

自测：把balance声明为volatile，能否让两账户转账不可分割？

不能。volatile不提供互斥，也不把多次访问合成一次事务。需要先说明不变量、有哪些参与者及它们用什么同步关系，再证明所有观察都在正确边界上发生。

本讲核心考点

[C] 区分线程私有寄存器、栈与共享地址空间。
[C] 沿load/add/store交错逐步写出寄存器和counter。
[C] 解释join与volatile为什么不能代替互斥。
[C] 找出必须整体保护的临界区，而非只锁最后赋值。

附录

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

来源与证据

原件：L13-线程与线程API-2022未核.pptx（本地课件）；PDF副本（本地课件） p.1–37。本文页码均为 PDF 页号。
考试证据：读了课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无
2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。