Skip to content

Process Synchronization

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

发生竞争的条件就是 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. 让权等待——不是必须的：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态

Synchronization Software

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

单标志法

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

turn 初始化为 0

\(P0\) 临界区操作后把 turn 置 1 ， \(P1\) 临界区操作后把 turn 置 0

但如果是 \(P1\) 先执行就完了（如果不能并行执行进程），而且是强制轮流访问

image-20241105143233358

双标志法

设置一个布尔变量数组 flag[2]，初始化两 bit 都是 false，哪个进程 ready to 访问临界资源就把哪位置 true，访问完再置 false

进程访问临界区前先检查对方的 bit 是否为 true，对方想访问就把资源让给对面，自己等待

双标志前检查法

先检查 flag 再上锁（修改 flag）

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

image-20241029153508192

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

双标志后检查法

image-20241029153034063

P0 和 P1 可能都进入不了临界区，P0 执行了 flag [0] := true ，然后 P1 执行了 flag [1] := true，这样两个进程都卡死循环

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

Peterson’s Solution

turn 和 flag[2] 都用上

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

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

image-20241029153652548

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

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

Bakery Algorithm (面包房算法)

//当前进程的进程号为 i
do { 
    /* 选号 */
    choosing[i] = true; 
    number[i] = max(number[0], number[1], …, number [n – 1])+1;
    choosing[i] = false;


    for (j = 0; j < n; j++){    
        while (choosing[j]) ; //对方还在取号就先等他，可能是同号的
        /* 如果没有这第一个 while，可能会出现 i 执行第二个 while 时             number [j] 还没被赋值，i 发现 number [j] 是 0 就访问了，然后 j          过来判断是同号但 j < i，这样 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 是一个指令（也可以理解为一个函数），其接收一个指针，包括两个子步骤：

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

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

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

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

进程需要一直占用 CPU 检查自旋锁 while(TAS(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 情况下, 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 ;
 }

Semaphores（信号量）

信号量就是一个整型计数器，记录当前可用资源的数量，S.value 初值为 1

  • 当它的值大于 0 时，表示当前可用资源的数量；
  • 当它的值小于 0 时，其绝对值表示等待使用该资源的进程个数

信号量 S 就是一个于代表资源数目的整型量，没有进程链表，无法实现“让权等待”的准则。

PV 操作

原子操作 wait(S)和 signal(S)，又常被称为 P、V 操作

  • P(S) wait 请求分配资源
    • 将信号量 S 的值减 1，即 S.value = S.value-1；
    • 如果 S.value≥0，则该进程继续执行
    • 否则该进程置为等待状态，排入等待队列。
  • V(S) signal 释放资源
    • 将信号量 S 的值加 1，即 S.value = S.value+1；
    • 如果 S.value > 0，则该进程继续执行；
    • 否则释放 S.L 中第一个的等待进程。

img

其它信号量

  • Counting semaphore （计数信号量）
    • value 随便取值
  • Binary semaphore（二值信号量）
    • value 只能取 0 和 1，也叫 mutex locks
    • 是一个 spinlock