南京大学操作系统课程2

多处理器编程

c程序的状态机模型

初始状态为main(argc,argv,envp)

状态迁移：执行一条语句（指令）

多线程的状态机模型

增加一个特殊系统调用：spawn()增加一个状态机，有独立的栈，但共享全局变量。

在spawn后，一个进程就出现了俩个线程。可以随时让其中一个状态机执行下一条指令。

并发是逻辑上的同时执行，可以由操作系统运行库模拟出轮流执行。（也可以是真正同时执行）

并行：丧失确定性，顺序性，一致性

真正意义上的同时执行，有共享内存的多个处理器。同时执行指令(load/store访问共享内存)。

简化的线程api

  • spawn(fn)创建一个入口函数是fn的线程，并立即开始执行。
  • join()等待所有运行线程返回，main线程返回的时候默认会join所有线程。

多线程并发会导致确定性丧失。除了系统调用，程序的行为是确定性的。并发每次可能选一个程序运行，非确定性的程序理解起来相当困难。

在单线程时，程序通常假设没人能干涉程序的状态。编译器可以对一段顺序的程序做出任何它觉得合理的优化，但是多线程下这个优化可能就会成为问题。

如果想控制编译器的行为，可以通过插入不可优化的代码块来实现。比如

while(!flag){
    asm volatile("":::"memory")
}
//或者 标记变量不可优化
int volatile flag;
while(!flag)

顺序性

并发编程会失去全局顺序性。实际上这样的顺序性是不存在的。比如想象一个有多个cpu的主板，根据相对论每个cpu对其他cpu的操作实际顺序都有不同的看法。

为了性能，会选择宽松的内存模型，存储写入本地内存，再慢慢同步给其他处理器。允许load到local memory的旧值。

共享内存对其他处理器的可见时间点可能不同。

处理器内部也会乱序，对同一个地址的store/load允许bypass

不同地址的load/store允许重排。

乱序执行（out-of-order excution）是现代高性能处理器最值得骄傲的特性之一。

处理器本质上也会做类似的事情（改变指令执行的顺序）。现在处理器当发现俩个指令是没有绝对顺序的时候会乱序进行执行。cpu中有个叫分支预测期的东西，会猜到底会执行哪条指令（超过百分之99的准确率）。

CPU设计者面临了难题

x86把所有的写都排好顺序。arm的实现更简单，性能更好。

因此在ARM上模拟x86是很困难。

互斥

用lock和unlock标记一个代码块，标记的代码块multually exclusive。

被秒级的代码块的执行可以理解为一次状态迁移。

按照悲观的版本， 加入一半的代码不能被并行，即便有1万个处理器，也就加速了一倍。

任何操作都不能超过光速，所以局部性原理很重要。

最早的dekker的算法就是错的（证明有问题） 。还有Peterson算法，它们都非常复杂。

model checker能自动遍历状态机空间。是一个形式化验证的工具，核心思想是通过穷举状态空间来证明或者证反系统的正确性，无需人工构造证明。

但是直接实现peterson算法，因为指令重排序（关闭内存屏障），会出现错误。在加了内存屏障后，编译器会阻止一些指令重排等优化行为。

比如

  • x86的mfence
  • arm的dmb ish
  • risc-v的fence rw，rw

但是peterson算法只能解决俩个线程的访问。

实际上我们实现互斥是通过硬件解决方案。

计算机系统也是我们造的，我们可以在load和store上实现互斥。这是computer science和自然科学不同，许多游戏规则是我们定的。

有没有stop the world指令呢？

有的兄弟有的，最早单线程cpu就是用cli（x86）指令来陷入内核。

eflags里有一个bit是IF(0x200)，对于单机处理系统，死循环=计算机卡死。默认操作系统的中断是不允许关闭的。不然容易单线程死循环。

但是对于多处理器的情况来说，事情变得复杂。这时就需要硬件的帮忙。

因此实际上只需要实现can_go=√，然后设置为x的原子操作，就完成了stop the world

现代操作系统中，许多CPU都提供了原子的CAS指令，无需切换到内核态。

这就叫做原子指令。一个不会被打断的load+计算+store。同样的我们可以实现多把锁。

自旋锁的scalability问题：

除了获得锁的线程，其他线程都在空转，一核有难，八核围观。如果代码执行很久，不如把处理器让给其他线程。

应用程序，不能中断，持有自旋锁的线程被切换，导致100%的资源浪费。

java的synchronized的底层锁升级为重量级锁的时候，使用了systemcall。

在jvm中mutex的底层在linux的环境下就使用了pthread mutex lock。但要注意这个锁默认是不可重入的。

而atomicinteger等原子变量使用的是死循环。

public final int getAndAddInt(Object o, long offset, int delta) {
     int v;
     do {
         v = getIntVolatile(o, offset);
     } while (!weakCompareAndSetInt(o, offset, v, v + delta));
     return v;
 }

因此简单的实现是将锁的实现放到systemcall就好了

因此提供了pthread mutex lock

编程的时候直接用这个即可，没有争抢的时候性能很好，甚至都不需要trap进操作系统内核

更多线程争抢的时候也有相当好的scalability。

一般来说atomic相比mutex更快，但是mutex可以锁住更多的代码。其中spin是一个自旋锁。

futex（Fast Userspace muTEXes）是Linux内核提供的一种高效同步原语，用于实现用户空间的锁和同步机制。它结合了用户空间的快速路径和内核空间的慢速路径，在无竞争情况下完全在用户空间操作，有竞争时才进入内核。

同步，条件变量

synchronization同步的定义为，俩个或俩个以上岁时间变化的量在变化过程中保持一定的相对关系。

我们希望控制事件发生的先后顺序

比如a->b->c

互斥锁能确保分开abc，做不到顺序控制

我们希望形成受我们控制的happens-before关系。

一个简单的例子是合唱团。

什么是事件，什么是顺序。

每个乐手都是一个线程（状态机）

  • 事件：发出节拍、演奏节拍
  • 顺序：发出节拍i->演奏节拍i
  • 这个模型允许一个节拍的演奏时间过长

同一线程内的事件天然存在happends-bnefore的关系，在多处理器系统中可以并行执行。

那么如何在并发的情况下实现happends-before呢？

实现A->B

void T_player(){
    for(int i=0;i<n;i++){
        while(current_beat<i);
            play_beat(i);
    }
}

大致可用，但current_beat存在和sum++类似的问题。

因此我们想让操作系统替代自旋的循环。

while(!can_proceed)

发明条件变量机制。一个理想的API

wait_unit(cond)//把代码编译到内核里

条件不满足是等待（让出cpu），操作系统提供了以下api。

  • wait直接等待
  • signal/broadcast唤醒所有等待的线程。

我们可以让b先等待，等到a执行完成了，让a来唤醒b。条件变量通常需要和互斥锁一起使用。通常要先上锁在给条件变量。

条件变量（Condition Variable）是 C++ 中用于线程间同步的重要机制，它允许线程在某些条件不满足时挂起等待，直到其他线程改变了条件并通知它。

一个经典的同步问题是生产者消费者问题。99%的问题都可以用生产者消费者问题来解决。

  • 生产者：如果缓冲区有空位，放入，否则等待
  • 如果管抽取有数据，取走，否则等待。

一个等价的描述是先打印左括号，再打印右括号。

生产=打印左括号，消费=打印右括号。括号嵌套的深度等于缓冲区的数量。

pthread_cond_signal唤醒至少一个正在等待该条件变量的线程（具体唤醒哪个取决于调度策略）。

pthread_cond_broadcast:唤醒所有正在等待该条件变量的线程。

消费者的代码是类似的。只不过++变成了--。

总的来说流程是获得锁，判断条件是否成立。如果成立就做自己事情（消费或者生产）。最后唤醒其他线程。

计算图(Computational Graph)是描述计算任务的有向无环图(DAG)，其中节点表示操作或变量，边表示数据依赖关系。在分布式系统和深度学习框架中，计算图的并发执行与控制是关键优化技术。在计算图中，上一个节点就是生产者，下一个节点就是消费者。

信号量

互斥锁实际上也是happens-before。互斥锁的原语实际上是可以进入临界区当且仅当没有人持有这个锁。实际上实现了加锁和解锁的happens-before

  • 一个奇妙的想法是，创建锁时，立即获得它（总是成功）
  • 其他人需要获得锁的时候就会等待，此时release就实现了happens-before。

比如先有一个锁，A线程进行解锁操作，B线程进行上锁操作。B线程必须等待A线程解锁了才能上锁。这样就能实现类似join的语义

用互斥锁也可以实现计算图。可能当前线程加的锁需要在别的线程进行解锁。会让人觉得很奇怪。

在paxos线程库中的锁，必须同一个线程加锁和解锁。

Acquire-relise实现计算图过程如下

  • 每一条边都飞陪一个互斥锁
  • 初始时，全部处于锁定状态
  • 对于一个节点它，需要获得所有入边的所才能继续。可以直接计算的节点立即开始计算
  • 计算完成后，释放所有出边对应的锁。

因此我们实现了用release-acquire实现了happens-before

Acquire是等待信号，release是发出信号

信号可以理解为现实中的资源许可。

信号量(Semaphore)是操作系统提供的一种进程/线程同步机制，由荷兰计算机科学家Dijkstra在1965年提出，用于解决并发环境下的互斥与同步问题。

信号量分为P（prolaag）和V（Verhoog），其中P必须消耗一个信号量才能继续，而V则可以创建一个信号量。信号量是互斥锁的扩展，因此信号量可以直接当做互斥锁来用。

sem_t sem = SEM_INT(1); //声明并初始化一个名为 sem的 POSIX 信号量，初始值为 1
void lock(){
    P(&sem);
}
void unlock(){
    V(&sem);
}

信号量可以用来方便的管理计数型的资源。

信号量是一个整型计数器，用于控制对共享资源的访问。主要操作：

  • P操作（Proberen，测试/等待）：尝试获取资源，若信号量值≤0则阻塞。
  • V操作（Verhogen，释放/发送）：释放资源，唤醒等待的进程/线程。

技术上可以多次调用v，但会改变信号量的语义，每次V都会+1。

public class SemaphoreDemo {
    private static final int THREAD_COUNT = 30;
    private static ExecutorService threadPool = Executors.newFixedThreadPool(THREAD_COUNT);
    private static Semaphore semaphore = new Semaphore(10); // 允许10个并发
    
    public static void main(String[] args) {
        for (int i = 0; i < THREAD_COUNT; i++) {
            threadPool.execute(() -> {
                try {
                    semaphore.acquire(); // 获取许可
                    System.out.println("save data");
                    Thread.sleep(2000);
                    semaphore.release(); // 释放许可
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
        }
        threadPool.shutdown();
    }
}

java中使用信号量。

用途

  • Semaphore：用于控制对共享资源的访问线程数量（限流）

    • CountDownLatch：用于等待一个或多个线程完成操作

  • 计数机制：

    • Semaphore：可以动态增减许可证数量（通过acquire/release）
    • CountDownLatch：计数只能减少不能增加（countDown()）

  • 重用性：

    • Semaphore：可以重复使用（获取和释放许可证）
    • CountDownLatch：一次性使用，计数到0后不能再重置

信号量可以优雅的实现生产者和消费者问题。从生产者消费者的角度来看，信号量比条件变量更好用。

信号量，干净，优雅，的解决了生产者消费者问题。但count不总是能代表很好地同步条件

条件变量更加万能:适用于任何同步条件,代码里还会存在spin loop。条件变量中的判断表达式可以是任何的代码。

信号量不太好表达二选一。

信号量能解决哲学家问题（死锁）。信号量通过确定能上桌吃饭的人的数量来解决这个问题的。

另一个解决问题的方式是，给叉子编号，总是先拿小的。或者创建一个服务员线程，给这些哲学家发叉子。这就又把问题简化为了一个生产者消费者问题。

其实也可以用信号量实现一个条件变量。操作系统底层用的是futex。因此信号量难以解决更多的问题。

编发变成更多的是使用绝对正确的模型，然后直接使用。

信号量是互斥锁的推广，通过计数实现同步。符合这个抽象的时候能够带来优雅的代码。信号量不是万能的。

真实的并发

理论上对于一个数学中的函数，输出是确定的。但是并发编程打破了这一点。比如不同的线程访问同一内存，并只少有一个是写。这就构成了数据竞争（data race）

weak memory model允许不同观测者看到不同的结果。通过mutex锁就可以避免对一个变量的同时的访问。

c++11开始data race 是未定义行为。

实际系统内存可以是全部变量，可以是栈可以是队。访问可能发生在任何代码。

有序上锁能解决死锁的关键逻辑是因为，当有节点可以获得锁时，那么它一定可以向后执行。防止出现循环的资源等待问题。

一个简单的想法是，每次acquire/release都printf打一个日志。

  • 如果一个线程既有A->B也有B->A就报告死锁。
  • 但这是程序巨大的心智负担，必须避免

LockDep:另一个方法是动态维护以来图和环路检测。如果在有向图中检测到环路，那么就代表可能出现死锁。（但是可重入锁可能得用其他方法解决）。

97%的非死锁并发bug都是原子性问题。

如何避免在没有锁的情况下，访问相同的变量呢？

还可以用lockDep解决这个问题。比如每次访问变量时都输出当前有的锁，不允许访问内存时有不相交的锁。

c语言有个工具-fsanitize=thread。是GCC和Clang编译器提供的用于检测多线程中数据竞争的工具。

模拟物理的相同具有embarrassingly parallel特性。

javascript中不允许并行，但允许并发。允许网络访问请求和sleep在后台执行。

嵌套中嵌套代码会导致回调地狱。现在可以通过promise来描述计算图来解决这个问题。

js还可以定义async和await来等待promise的返回值。

CPU和GPU

CPU

CPU之间的所有程序都是并行的。CPU在能效和性能之间选择了后者。CPU中每个电路门的翻转都会产生热量。CPU里编译器会消耗巨量的能量，这些能量能够使计算快速完成。但不等同于单位时间内完成尽可能多的计算。

现在CPU进入了dark silicon，暗硅时代。

功耗墙：纵使有更大的电路，热功耗限制了性能上限。

一条指令浪费的大量大致是定数，处理的数据越多浪费越少。或者用更多更简单的处理器。

多处理器系统、异构多处理器，同等面积，处理器越简单数量越多。

SIMD（single instruction，multiple data）

可以让一条指令对连续操作做相同的运算。比如对四个float做4次乘法。

之后这个数越来越大被扩展到了128,258bit的操作。

MMX->SSE->AVX->AVX512

64（mm）->128(xmm)->256(ymm)->512(zmm)

比如512就可以放多个float64。著名的avx512中的512就是寄存器的宽度。

SIMD指令依然是在CPU里调度的，因此不能做的太宽。并行度有限。

因为单cpu运行受限，因此引入了多CPU。后面还引入了大小核。

GPU

同等面积，处理器越简单，数量越多。我们甚至不需要处理器有CPU指令集的计算能力。

因此有专用领域的 加速器

  • ISP image signal Processing（手机相机）
  • GPU: Graphics processing unit（图形渲染）
  • DPU:data processsing Unit（网络、数据处理）

DMA就是一个很好的例子。这个cpu的一部分只有很小的功能，就是进行内存拷贝。在早期的计算机中DMA通常是主板上的独立芯片如intel8237

现代的DMA控制器通常集成在CPU/Soc的内部。但是对于CPU来说渲染画面是不可能完成的任务。

比如NES中有256x240=61K个像素（256色）

60FPS-> 10K跳指令完成61K像素级的渲染。因此它的设计是不允许屏幕上所有像素运动。

以8x8的贴块为绘制的基本单位。

  • 背景画布+动态前景

之后我们有了2d的渲染管线。允许把一个图片拉伸到不同的位置然后进行投影等渲染。无论如何CPU只负责描述，让专用处理器来负责绘制。

由于任何一个面都可以绘制为三角形。然后经过fixed -function pipline。

本质上openGL这样的标准定义了一个函数，可以接受对当前图形的描述，这个描述中有顶点的关系，贴图，材质纹理，光照信息。然后就可以把图像算出来。

然后rendering pipline逐渐从固定功能到了可编程。可以单独为每个像素进行编程。

还有函数可以对每一个顶点来调用。这样就可以做出一些爆炸效果。英伟达在99年的时候实现了第一个着色器。

然后我们发现可以将俩个像素点通过矩阵进行叠加。可以叠加俩个图片。

SIMT

那么为什么不把shader实现为线程呢？

然而cpu去做shared memory很难实现，但是英伟达做到了。

在GeForce 8800中首个cuda GPU（首个支持cuda的cpu）

有128个cores此时桌面端的intel只有2C4T。

The frist GPU to utilize a scalar thread processor, eliminating the need for programmers to manually manage vector register.

5080现在有10752个cuda核心。

GPU底层是通过single instruction multiple threads做到的。

CPU中每个CPU核心都有自己的缓存。它们每个的程序计数器和register都可能是不一样的。它们在并行执行的时候可能还需要访问共享内存。

所有的核心执行相同的代码

ALU（算术逻辑单元，Arithmetic Logic Unit）是计算机CPU的核心组件之一，负责执行所有的算术运算（如加、减、乘、除）和逻辑运算（如与、或、非、异或等），是处理器完成实际计算的关键部分。

如果想要并ALU就不能省,寄存器也不能省。但是程序计数器可以省略，或者说要求所有的线程执行同样的代码。

假设row和col都在寄存器里，我们可以通过给每个gpu核心运行自增当前索引的值。就能得到不一样的结果。虽然程序计数器同步了，但是gpu核心中的值是不一样的。

其实底层就是转换成了单指令，多线程。这个操作变成了天生的向量运算。

显卡中内存的带宽可以比cpu大很多。cpu经常要做缓存行和内存的交换。

类似神经网络，就很适合用GPU进行计算。

Last modification：August 14, 2025
© Allow specification reprint
如果觉得我的文章对你有用，请随意赞赏