GBS 3 Parallele Systeme und Synchronisation 并行系统与同步

Einführung

因为（单核）系统无法做到真正的并行进程，所以所谓的parallel的活动会导致不确定性（Nichtdeterminismus），即系统在相同的初始条件和相同的输入下表现出不同的行为。

例子：

假设现在我们有一个变量 $x = 2$，以及2个进程：

进程1：$x = x + 5$

进程2：$x = x \cdot 2$

那么如果先运行进程1再运行2就会得到 $x = 14$，先运行进程2再运行1就会得到 $x = 9$ 。

介绍几个概念：

竞态条件（Race Condition）：至少两个进程在读取或写入共享资源。这个时候最终结果会依赖于进程执行的顺序。
临界区（Kritischer Abschnitt，critical section/region）：进程会在临界区中访问共享资源，而对于只能被独占使用的资源，访问将被顺序化/串行化（sequentialisiert）。

所有跟共享资源相关的操作都会在临界区里执行。
互斥（Wechselseitiger Ausschluss，Mutual Exclusion）：确保同一时间只有一个进程/线程能访问临界资源（critical section）。

互斥的实现一共需要注意以下几点：

临界区必须是互斥访问的（wechselseitig ausgeschlossen），即同一时间只有一个进程可以进入临界区（kritischer Abschnitt）
互斥的实现不得依赖于进程执行临界区的顺序假设。
互斥的实现不得依赖于进程执行时间的假设。
不能让某个进程无限期地阻止另一个进程进入临界区，即避免Starvation。

图解：

在以下几个层面都有对应的办法来实现互斥/同步：

硬件层面
- 通过禁止中断（Interrupts sperren）实现互斥（如中断屏蔽）
- 使用原子机器指令（如 TSL、cmpxchg）保障操作不可分割（atomic）
简单的系统层面
- 主动等待（如：Spin-Lock，busy waiting）
- 被动等待（如：sleep/wakeup，节省 CPU）
更高级的操作系统层面
- 信号量（Semaphore）：支持主动或被动等待
- 互斥锁（Mutex）
编程语言层面
- 监视器（Monitor）概念：语言层级的同步抽象

硬件层面

中断屏蔽（Unterbrechnungssperre）

中断（Interrupt, Unterbrechung ）是通过专用的中断线路发出的信号，例如：

I/O 设备发出信号表示任务已完成
定时器发出信号表示时间片已用尽

而中断会打断当前的活动进程，将其转为就绪/等待状态（rechenwillig/wartend），然后Interrupt Handler会来处理这个中断。

所以我们可以通过屏蔽中断来实现互斥访问：让 CPU 暂时禁止处理中断（temporarily prevent the CPU from responding to interrupts），防止当前进程在执行期间被强制让出 CPU，这样一来进程就可以不被打扰地完成其临界区操作。

只不过这个方法（中断屏蔽）只适用于单处理器系统来实现临界区，因为在多处理器系统中，即使一个 CPU 禁用了中断，其他 CPU 仍然可以访问共享资源。

并且实施时需要注意几点：

确保由中断屏蔽保护的临界区必须很短。

因为所有中断都是有意义的，随便屏蔽的话系统容易出问题。
该机制最多只应在操作系统内核中使用。

为了安全性考虑。

原子性机器指令（Atomare Maschinenbefehle）

大多数计算机架构都具备专门用于原子操作的机器指令，我们这里以其中的 TSL（Test-and-Set Lock）为例子。

具体实现的话需要先定义2个函数：enter_crit_region和leave_crit_region 。（见下方代码）

具体流程：

通过共享变量 lock 对内存访问进行同步
在进入临界区之前，进程 P 会调用 enter_crit_region
如果 lock == 0，则进程 P 可以执行其临界区代码
否则，进程必须主动等待（忙等，busy waiting），直到 lock 被重置为 0
临界区结束后，进程 P 必须重置共享变量 lock，调用 leave_crit_region

enter_crit_region：

enter_crit_region:
  tsl rax, [lock]          ; 将 lock 的值读入 rax，并将 lock 设置为 1（原子操作）
  cmp rax, $0              ; 判断原值是否为 0（锁是否空闲）
  jne enter_crit_region    ; Busy Waiting（一直等）
  ret                      ; 如果是 0，表示可以进入临界区

leave_crit_region：

1
2
3

leave_crit_region:
  mov [lock], $0           ; 将 lock 重置为 0，释放锁
  ret

简单的系统层面

主动等待（Aktives Warten）

刚才提到的同步概念被叫做自旋锁（Spin-Lock）：进程会在一个循环中不断检查资源是否仍然被占用，也就是所谓的主动等待（Aktives Warten）。

但是一直在这里等的话效率非常低下。

示例：

/* busy waiting emulation */
int main () {
    while (shouldWait) {
        // 什么都不做，只是一直干等
    }
}

Passives Warten（被动等待）

相比之下 Passives Warten（被动等待） 就要高效很多：会使用系统服务（比如说 sleep）让进程进入等待状态（wartend），或者使用系统服务（比如说 wakeup ）让进程进入可运行状态（echenbereit）。

比如说2个进程传输数据，A传给B。A传的时候让B进入等待状态，等A传完了再把B叫起来让它处理数据。

例子：生产者消费者问题（Erzeuger-Verbraucher-Problem）

在这个例子中我们会有2个并行的进程：一个生产者（Erzeuger，producer）和一个消费者（Verbraucher，consumer）。两者共用一个缓存区（Puffer，Buffer）。对缓冲区的访问必须实现互斥。

先给一个反例，后续会慢慢看到如何正确解决这个问题：

void producer(void) {
    int item = 0;
    while (true) {
        item = produce_item();
        if (count == N)
            sleep();
        insert_item(item);
        count = count + 1;				// 注意这里
        if (count == 1)
            wakeup(consumer);
    }
}

void consumer(void) {
    int item = 0;
    while (true) {
        if (count == 0)
            sleep();
        item = remove_item();
        count = count - 1;				// 注意这里
        if (count == N - 1)
            wakeup(producer);
        consume_item(item);
    }
}

可以看到这里希望通过 count 来实现互斥，但问题是 count 本身就是一个共享变量。

更高级的操作系统层面

信号量（Semaphore）

定义：

信号量（Semaphore）是一个整数控制变量 s
在这个变量上定义了三种操作：
- 初始化（Initialisierung）
- P（down、wait）
- V（up、signal）
控制变量的值表示：允许多少个进程同时进入临界区

（P和V代表的是Proberen 和 Verhogen，是荷兰语，因为提出信号量这个概念的是Dijkstra，他是荷兰人。）

那么这两个操作具体是怎么定义的呢：

down 操作（P）：

控制变量 s 会被减一
如果 s < 0，当前进程必须等待
而在使用被动等待的实现中：
- 进程会被转为“等待状态”，并被加入等待队列（Wait-Queue）中管理

up 操作（V ）：

控制变量 s 会被加一
如果使用的是被动等待：
- 如果等待队列不为空，则唤醒其中一个进程（变为就绪状态，rechenbereit ）

代码示例：

void down(semaphore *wa) {
    int* s = &wa->s;					// 访问wa这个结构体中s的值，简单来讲就是访问当前s的值。
    *s -= 1;
    if (*s < 0) {
        thread_yield(wa->wait_queue);  // 把当前线程挂起，放入等待队列
    }
}

void up(semaphore *wa) {
    int* s = &wa->s;					// 访问wa这个结构体中s的值，简单来讲就是访问当前s的值。
    *s += 1;
    if (*s <= 0) {
        thread_wakeup(wa->wait_queue);  // 从等待队列中唤醒一个线程
    }
}

那么我们该怎么使用这个信号量呢？

首先定义一个信号量对象 wa
将控制变量 s 初始化为 1（或更大的 n）

取决于我们希望有多少个进程同时进入临界区

用 P/V 操作包裹临界区代码：

1
2
3

down(&wa);                     // P操作：尝试进入
execute_crit_region();        // 临界区操作
up(&wa);                      // V操作：释放信号量

ok，我们现在拥有更高级的工具了，再回来看一下刚才没有完全解决的生产者-消费者-问题。

还是先看一个反例：

只使用一个信号量 wa 来控制对缓冲区的访问，初始化为1。

/* Producer */
while (true) {
    element = produce();           // 生产一个元素
    down(&wa);                     // 请求进入临界区
    write_to_buf(W, element);      // 写入缓冲区
    up(&wa);                       // 释放临界区
}

/* Consumer */
while (true) {
    down(&wa);                     // 请求进入临界区
    element = read_from_buf(W);    // 从缓冲区读取元素
    up(&wa);                       // 释放临界区
    consume(element);             // 消费数据
}

问题出在没有能够反应当前缓冲区是否满或者是空的状态。

假如Producer进入了满的缓冲区，那么它无法进行写入操作，也就无法进行后续的 up(&wa) 。它会卡在这里，并且Consumer也无法进来读取数据。

那么该如何正确地解决这个问题呢：

我们需要在此基础上添加2个信号量：

一个用于表示当前的缓冲区已满：voll，初始化为0
一个用于表示当前的缓冲区剩余的位置：leer，初始化为n，n 是缓冲区大小。

/* Producer */
while (true) {
    element = produce();           // 生产数据
    down(&leer);                   // 等待有空位
    down(&wa);                     // 请求进入缓冲区（互斥）
    write_to_buf(W, element);      // 写入缓冲区
    up(&wa);                       // 释放互斥锁
    up(&voll);                     // 增加“已满”计数
}

/* Consumer */
while (true) {
    down(&voll);                   // 等待有数据可读
    down(&wa);                     // 请求进入缓冲区（互斥）
    element = read_from_buf(W);    // 读取数据
    up(&wa);                       // 释放互斥锁
    up(&leer);                     // 增加“空位”计数
    consume(element);             // 消费数据
}

互斥锁（Mutex）

Mutex类似于二进制信号量（binary semaphore），只有2个状态：unlocked 和 locked。

注意：可以将Mutex当成2元信号量来理解，但是要清楚他们严格来讲并不一样。最大的区别便是拥有权：

互斥锁（Mutex）只能由获取锁的实体（Entity）进行解锁（也就是说，它有一个Owner）。
信号量（Semaphore）没有 Owner 的概念。

编程语言层面

监视器（Monitore）

属于比信号量（Semaphore）更高级的抽象层级。

监视器将数据和对数据的访问操作封装在一起，实现自动同步，编译器则负责生成底层的信号量及其使用代码。

简单来讲就是监视器（Monitore）会把互斥访问这一部分封装成一个黑盒（Black Box），使用时只需调用接口，不需要关心底层是怎么加锁、解锁的。这样一来也更不容易出错。

一般使用定义好的操作 Produce 和 Consume 来调用监视器（Monitore）。

例子：Speisende Philosophen（Dining Philosophers）

死锁（Deadlock）

死锁（Deadlock）描述的是一组进程里每个进程都在等待一个事件发生，但这个事件只能由其他等待中的进程触发。

比如说A和B去图书馆借书，A已经借了x，B已经借了y。但现在A想借y，B想借x。只不过双方都希望借到新书了之后再把手上现有的这本还回去。这样就会陷入僵局，也就是死锁。

例子：

void process_A(void) {
    down(&sema_resource_1);     // 请求资源 R1
    down(&sema_resource_2);     // 请求资源 R2
    use_both_resources();       // 使用两个资源
    up(&sema_resource_2);       // 释放 R2
    up(&sema_resource_1);       // 释放 R1
}

void process_B(void) {
    down(&sema_resource_2);     // 请求资源 R2
    down(&sema_resource_1);     // 请求资源 R1
    use_both_resources();       // 使用两个资源
    up(&sema_resource_1);       // 释放 R1
    up(&sema_resource_2);       // 释放 R2
}

出现死锁（Deadlock）的充要条件（Notwendige und hinreichende Bedingungen）：

互斥使用资源（Exklusiv nutzbare Ressource，Mutual Exclusion）

共享资源不可同时被多个进程访问。
占有且等待（Belegen und Anfordern，Hold and Wait）

进程已经持有资源，还要继续请求其他资源。
不可抢占（Nicht Entziehbar，No Preemption）

资源不能被强行拿走（被系统抢回），只能自己释放。
循环等待（Zyklische Wartebedingung，Circular Wait）

至少两个或更多进程形成一个循环，每个进程都在等待另一个进程所持有的资源。

（死锁是等价于这4个条件同时满足的。）

建模有向图 Belegungsanforderungsgraphen：

点
- 圆圈表示进程，
- 方形表示资源
边
- 进程A占用（belegt）资源R：R到A的边
- 进程A想要（fordert）资源R：A到R的边

例子：

Deadlocks的应对策略

主要有4种策略：

忽视（Ignorieren）
检测（Deadlock-Detection ，Erkennung）
- 分配资源后检测/模拟是否会产生死锁，如果会的话就回档。
避免（Deadlock-Avoidance，Vermeidung）
- 分配资源前模拟是否会产生死锁
- 使用 Bankier-Algorithmus
预防（Deadlock-Prevention，Verhinderung）
- 设计的时候就避免死锁出现，确保上面的4个条件至少有一条不会出现。

对比：

策略类型	方法	优点	缺点
识别（Erkennung）	周期性检测（Periodischer Aufruf）	可交互式响应（Interaktive Reaktion）	可能通过中止造成损失（Verlust durch Abbruch）
避免（Vermeidung）	银行家算法（Bankiers-Algorithmus）	无需资源抢占（Kein Ressourcenzug）	需要提前知道未来资源需求（Zukünftiger Bedarf muss bekannt sein）
预防（Verhinderung）	资源分配采用固定顺序（Feste Reihenfolge bei Zuteilung）	无需运行时检查（Keine Laufzeitprüfungen）	静态、不灵活（Statisch, inflexibel）
	一次性分配所有资源（Alle Ressourcen auf einmal zuteilen）	不需要资源抢占（Kein Ressourcenzug notwendig）	效率低（Ineffizient）

例题

例题1

假设现在有2个线程并行运行，并且共享内存（Shared Memory）中的x和y被初始化为0：

// Thread 1
if (y >= 0){
    x = x+1;	//atomic
}

// Thread 2
while (x <= 0 && y > -3){
    y = y-1;	//atomic
}

问题1：给出所以可能的结果组合。（Was sind alle möglichen Kombinationen der Werte für x und y nach der nicht-deterministsichen Ausführung der obenstehenden Threadds?）

首先假设一开始先只运行Thread 2，等结束了之后在运行Thread 1，这时 $y=-3$，已经不满足Thread 1里的 if 条件了，所以结果为 $(x,y)=(0,-3)$ 。
假设先只运行Thread 1，等完全结束了之后再运行Thread 2，这时 $x=1$ ，已经不满足Thread 2里的 while 条件了，所以结果为 $(x,y)=(1,0)$ 。
假设Thread 1，2先读取了 $x,y=0$ ，然后各自运行了一次，这时 $(x,y)=(1,-1)$ ，都不满足判断条件了，所以2个都结束，结果为 $(x,y)=(1,-1)$。
假设Thread 1，2先读取了 $x,y=0$ ，然后 Thread 2 先运行了2次（这时 $y=-2$），然后 Thread 1 运行了1次，那么结果为 $(x,y)=(1,-2)$ 。
假设Thread 1，2先读取了 $x,y=0$ ，然后 Thread 2 先运行了3次（这时 $y=-3$），然后 Thread 1 运行了1次，那么结果为 $(x,y)=(1,-3)$ 。

所以答案为：

x	y
0	-3
1	0
1	-1
1	-2
1	-3

问题2：现在该怎么利用Semaphoren和Mutex（限量3个及以内）使得最终结果为 $x=1, y=-1$？

回顾一下上面的逻辑，想要得到这个结果需要让 Thread 1，2先读取 $x,y=0$ ，然后各自运行一次。

我们这里需要利用Mutex设置2道坎：

在做 if 或者 while 判断前设置一道
在 Thread 2 的while循环内的结尾设置一个

这样一来可以确保双方都先读取 $x,y=0$ ，然后运行一次 Thread 2之后运行 Thread 1。最终得到 $x=1, y=-1$ 。

答案：

Innitialisierungsblock

1 2	block_t1(0) block_t2(0)

Codeblock

// Thread 1

if (y >= 0){
    up(block_t2);		// 先等Thread 1 通过的if的判断再放行 Thread 2
    down(block_t1);
    
    x = x + 1;
        
    up(block_t2);
}

// Thread 2

down(block_t2;)
while (x <= 0 && y > -3){
    y = y-1;
        
    up(block_t1);
    down(block_t2);		// 先等 Thread 2 运行了一次之后再运行 Thread 1
}

先让t1通过if判断，然后blockieren。这时t2通过wihle判断并进行一轮操作，接着再进行t1的操作。t1操作完再通知t2可以进行后续操作（即进行第二次的while的判断）。