Skip to content

Chapter 6: Process Synchronization

:material-circle-edit-outline: 约 1454 个字 :fontawesome-solid-code: 63 行代码 :material-clock-time-two-outline: 预计阅读时间 6 分钟

Background

对共享数据的并行操作可能造成不一致

我们需要进行进程同步

Shared-memory solution to bounded-buffer problem allows at most n–1 items in buffer at the same time.

因为是通过取余判断是否满的

关于生产者与消费者非原子操作的模型带来的问题（count 的汇编代码可能交叉重叠）

image-20241029143329704

image-20241029143620649

可见原子操作的重要性

Race Condition（竞争条件）

上面的例题就是一个竞争，发生竞争的条件就是 Race Condition，我们通过同步来避免 Race Condition

The Critical-Section Problem

临界资源是一次只允许一个进程使用(访问)的资源

竞争使用共享资源的进程，在每个进程内都设计一块代码叫 critical section（临界区），专门用于访问临界资源

do {
    entry section           //进入区
    critical section        //临界区
    exit section            //退出区      
    reminder section        //剩余区
} while (1);

临界区规则

  1. Mutual Exclusion(互斥)：临界资源在任意时刻只允许一个临界区访问，此时其它进程不得执行他们的临界区代码
  2. Progress（空闲让进）：如果临界资源空闲，且有进程需要访问，则这些进程不能无限等待
  3. Bounded Waiting（有限等待）：如果超过某个特定时间当前进程访问还没结束，那么必须换人访问
  4. 让权等待——不是必须的
    1. ？？？？？？？？这是什么

image-20241029151805851

Synchronization Software

该算法用于解决两个进程的互斥，我们以下记为 \(P0\) 和 \(P1\)

假设 load 和 store 是原子的，即不能被中断

假设一次只能执行一条指令

单标志法

就是在两个进程的临界区加一个共享 int 变量 turn，其值有 0 和 1，表示当前临界资源允许 \(P0\) 还是 \(P1\) 访问

turn 初始化为 0， \(P0\) 临界区操作时把 turn 置 1 ， \(P1\) 临界区操作时把 turn 置 0

这个办法很简单，但如果是 \(P1\) 先执行就完了（如果不能并行执行进程）

而且是强制轮流访问，不太合理

image-20241105143233358

双标志法

设置一个两位布尔变量数组 flag[2]，初始化两位都是 false

哪个进程 ready to 访问临界资源就把哪位置 true，访问完再置 false

检查对面进程的位是否为 true，对方想访问就把资源让给对面，自己等待

根据检查位置分为两种

双标志前检查法

前检查是指先检查 flag 再上锁（修改 flag）

初始化 flag [0] = flag [1] = false

image-20241029153508192

image-20241105143542852

P0 和 P1 可能同时进入临界区，违反了互斥原则

双标志后检查法

初始化 flag [0] = flag [1] = false

image-20241029153034063

image-20241105143757968

P0 和 P1 可能都进入不了临界区

P0 执行了 flag [0] := true ，然后 P1 执行了 flag [1] := true，这样两个进程都无法进入临界区

违反了空闲让进和有限等待，会出现饥饿问题

Peterson’s Solution

turn 和 flag[2] 都用上

  • flag 表示哪个进程想访问
  • turn 表示哪个进程可以访问了

先用 flag 广播我想访问了，然后通过 turn “让”出访问机会给对面

image-20241029153652548

谁最后改了 turn，谁就把访问机会让给了对方，失去了访问机会

image-20241105143929406

Meets all three requirements; solves the critical-section problem for two processes.

Bakery Algorithm (面包房算法)

经典互斥问题：面包店算法

又叫 lamport 算法

面包房买面包的排队步骤：

step1: 有 n 个顾客进入面包房买巧克力面条蒸蛋糕，安排他们按照次序在前台登记签到的号码，号码依次加 1.

step2: 根据签到号码由小到大的顺序依次进店买蛋糕。

step3: 完成购物的顾客在前台把自己的签到号码归 0。如果完成购买的顾客要再次进店需要重新排队。

原理

  • 每个事件对应一个 Lamport 时间戳，初始值为 0
  • 如果事件在节点内发生，时间戳加 1
  • 如果事件属于发送事件，时间戳加 1 并在消息中带上该时间戳
  • 如果事件属于接收事件，时间戳 = Max(本地时间戳，消息中的时间戳) + 1
//当前进程的进程号为i
do { 
    //number 默认为 0
    choosing[i] = true; //表示进程i正在选号，可能会有同时选号号码一样的情况
    number[i] = max(number[0], number[1], …, number [n – 1])+1;
    choosing[i] = false;

    //先和所有进程比号码大小
    for (j = 0; j < n; j++){ 
        //对方还在取号就先等他，可能是同号的
// 如果没有这第一个while，可能会出现 i 执行第二个while时number[j]还没被赋值，i发现number[j]是0就访问了，然后j过来判断是同号但j<i，这样j也去访问了，互斥了
        while (choosing[j]) ; 
        while ((number[j] != 0) && (number[j],j) < (number[i],i)) ;
    }
    // number为0的表示没选号，就是不准备访问临界资源的，就不用管
    //(number[j],j) < (number[i],i)) 满足其一即为True，顺序从左到右
    //如果进程i号码大就需等待
    //如果号码相等就让进程号小的优先

    critical section;

    number[i] = 0;

    remainder section;
} while (1);

Synchronization Hardware

Test-and-Set（测试与设置）

硬件对同步的支持-TAS 和 CAS 指令 - 元思 - 博客园

TAS 是一个指令（也可以理解为一个函数），其接收一个指针

该指令包括两个子步骤，

  1. 把给定的内存地址设置为 TRUE（1）
  2. 返回修改前的值。

这两个子步骤在硬件上实现为一个 原子操作，执行期间不会被其他处理器打断。

诶 ☝️🤓，我设一个变量叫 lock，进程访问 critical section 前就先通过 while(TAS(lock)) 去 TSET 这个 lock; 访问的同时 SET 这个 lock，把门锁上，访问结束再 SET lock = false 不就行了

当一个进程欲访问已被其他进程锁定的资源时，进程循环检测该锁是否被释放，这种技术称为自旋锁（spin lock）。

 while(1) {
     while (TS(&lock)) ;
     critical section
     lock = false;
     remainder section
 };

Compare and Swap

CAS 和 TAS 逻辑差别不大，就是 TS 硬件换成了 Swap 硬件

while(1) {
    key = TRUE;
    while (key == TRUE) 
        Swap(&lock , &key);
    critical section
    lock = false;
    remainder section
}

硬件方法优缺点

优点

简单

缺点

等待要耗费 CPU 时间，不能实现 "让权等待"

可能“饥饿”：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上

可能 死锁：单 CPU 情况下, P1 执行特殊指令(swap)进入临界区，这时拥有更高优先级 P2 执行 并中断 P1, 如果 P2 又要使用 P1 占用的资源，按照资源分配规则拒绝 P2 对资源的要求，陷入忙 等循环。然后 P1 也得不到 CPU，因为 P1 比 P2 优先级低。

Bounded-waiting mutual exclusion with TAS

解决饥饿问题

Boolean waiting[n], lock ;  //to be initialize to false, waiting[]：排队队列
while(1) {
    waiting[i]=true;
    key= true;
    while ( waiting[i] && key )  key=TestAndSet(lock);
    waiting[i]=false;

    critical section;   

    //选择下一个进入临界区的进程，
    //选择下一个waiting[j]=false
    j= (i+1) % n ;
    while ( (j != i) && !waiting[j] )  j= (j+1) % n ;
    if (j == i)  lock = false ;
        else waiting[j] = false ;

    remainder section ;
 }

Review Question

image-20241105154118193

  1. 有时钟中断，应尽量减少中断屏蔽
  2. 进程需要一直占用 CPU 检查自旋锁（循环等待）