2.5 临界区管理

1. 临界区及其使用原则
2. 临界区管理软件方法
3. 临界区管理硬件方法
4. 软硬件方法的优缺点

一、临界区及其使用原则

（1）临界资源：

一般指多个进程共同使用的共享变量，一个进程对该变量的使用会影响到别的进程；

进程中涉及临界资源的程序段成为临界区；
多个进程的临界区则称为相关临界区；

（2）使用原则：

• 有空让进（临界区没进程时，允许进程进入）
• 无空等待（临界区有进程时，其他进程不能进来，需要等待）
• 多中择一（多个进程想进入临界区时，临界区只会根据某一种规则选择一个进程进入）
• 有限等待（指的是不会让想进入临界区的进程无限等待）

二、临界区管理软件方法 （$Dekker$算法）

软件方法，既通过代码来管理；

样例一（失败的管理方法, 基于 C++ 语言）：

bool flag_1 = false;    // 布尔类型，true 代表这个进程想进临界区，false 代表这个进程不想进临界区
bool flag_2 = false;

P1()   // 进程一
{
    while( flag_2 == true ) ;   
    flag_1 = true;              
    P1 进入临界区并做相关操作;
    flag_1 = false;
}

P2()   // 进程二
{
    while( flag_1 == true ) ;
    flag_2 = true;
    P2 进入临界区并做相关操作;
    flag_2 = false;
}

在理想情况下：

• 一开始 flag_1 和 flag_2 都赋初值为 $false$。

• 若先开始执行进程 $P1$，那么它会直接跳出 $while$ 循环语句。然后将 flag_1 赋值为 $true$。然后进入临界区。

• 这时在进程 $P2$ 中，发现 flag_1 值为 true，那么 $P2$ 就会一直在 $while$ 语句中循环执行。

• 只有当 $P1$ 执行完后，将 flag_1 重新赋值为 $false$ 后，$P2$ 才能跳出循环，然后进入临界区。

• 依次类推

但是由于进程是并发执行的，进程并发导致进程执行时间不确定，有可能在将flag_1更新为true之前，系统就开始执行进程$P2$。
这样的话，由于flag_1未被修改，进程$P2$不会被循环所阻拦，这样临界区资源的互斥性就无法保证了

样例二（失败的管理方法）：

bool flag_1 = false;    // 布尔类型，true 代表这个进程想进临界区，false 代表这个进程不想进临界区
bool flag_2 = false;

P1()   // 进程一
{
    flag_1 = true;              
    while( flag_2 == true ) ;   
    P1 进入临界区并做相关操作;
    flag_1 = false;
}

P2()   // 进程二
{
    flag_2 = true;
    while( flag_1 == true ) ;
    P2 进入临界区并做相关操作;
    flag_2 = false;
}

在理想情况下：

• 一开始 flag_1 和 flag_2 都赋初值为$ false$。

• 若先开始执行进程$ P1$，它将先把 flag_1 赋值为 $true$，然后跳出 $while$循环，再进入临界区。

• 这时在进程 $P2$ 中，发现 flag_1 值为 $true$，那么 $P2$ 就会一直在 $while$ 循环语句中循环执行。

• 只有当 $P1$ 执行完后，将 flag_1 重新赋值为 $false$ 后，$P2$ 才能跳出循环，然后进入临界区。

• 以此类推…

但是又由于两个进程是并发执行的，进程并发导致进程执行时间不确定，有可能系统在执行$P1$时将flag_1 更新为$true$之后，转而去执行$P2$进程，这样会导致flag_1和flag_2都被更新为$true$，导致$CPU$空转（都无法进入临界区）；

$Dekker$算法：

bool flag_1 = false;                // 布尔类型，true 代表这个进程想进临界区，false 代表这个进程不想进临界区
bool flag_2 = false;
int turn = 1;                       // turn 的值为 1 时代表 P1 该进临界区，值为 2 时代表 P2 该进临界区(我们初值假设为 1)

P1()
{
    进程 P1：
    flag_1 = true;                  // P1 想进临界区
    while( flag_2 == True )         // P2 也想进临界区
    {
        if( turn == 2 )             // 而且 P2 也该进临界区(注：一开始 turn 初值为 1) 
        {
            flag_1 = false;         // 那么, P1 就说：“既然 P2 想进临界区而且该进，那我先不想了”
            while( turn == 2 ) ;    // 然后 P1 一直等 P2 搞完
            flag_1 = true;          // P1 等 P2 搞完后再 “想进临界区”
        }
    }
    P1 进入临界区并做相关操作;
    turn = 2;                       // P1 执行完了，就把 “turn(轮次)” 交给 P2
    flag_1 = false;                 // 并且 P1 搞完后也就 “不想进临界区”
}

P2()   //   进程 P2
{
    flag_2 = true;                  // P2 想进临界区
    while( flag_1 == True )         // P1 也想进临界区
    {
        if( turn == 1 )             // 而且 P1 也该进临界区
        {
            flag_2 = false;         // P2 说：“既然 P1 想进临界区而且该进，那我先不想了”
            while( turn == 1 ) ;    // 然后 P2 一直等 P1 搞完
            flag_2 = true;          // P2 等 P1 搞完后再 “想进临界区”
        }
    }
    P2 进入临界区并做相关操作;
    turn = 1;                       // P2 执行完了，就把 “turn(轮次)” 交给 P1
    flag_2 = false;                 // 并且 P2 搞完后也就 “不想进临界区”
}       // 结束并发进程;

• 一开始 flag_1 和 flag_2 都赋初值为 $false$。
• 若先开始执行进程 $P1$，那么它会直接跳出 $while$ 循环。然后将 flag_1 赋值为 $true$。然后进入临界区。
• 这时在进程 $P2$ 中，发现 flag_1 值为 $true$，那么 $P2$ 就会一直在 $while$中循环执行。
• 只有当 $P1$ 执行完后，将 flag_1 重新赋值为 $false$ 后，$P2$ 才能跳出循环，然后进入临界区。
• 以此类推 …

$Dekker$算法的本质是用一个变量（$turn$）来控制该进入哪个进程的临界区，变量$turn$的值只能有一个，因此系统只能允许一个进程访问临界区资源。
虽然用一个$turn$就可以保证进程访问的互斥性，但是任然需要flag_1、flag_2等变量辅助控制。假如没有这两个变量，则两个进程$P1$和$P2$必须得交替执行才能保证对临界区资源的访问。一旦某一进程要连续执行两次，就会造成$CPU$的空转；

详细可以借鉴这篇博客： https://www.nhooo.com/note/qa01nb.html

三、临界区管理硬件方法

软件方法管理临界区的算法较为复杂，使用硬件方法会更加简单；

所谓用硬件的方法，就是说硬件的指令的方法来控制对临界区代码的执行。

$TS$指令（$Test Set$）：

$TS$指令的功能可以由如下代码段表示：

// 如果参数st是true，则将参数st变为false并返回false
// 如果st是false，则直接返回false
bool TS(bool &st) 
{
    if(st) 
    {
        st = false;
        return false;
    }
    else return false;
}

bool s = true;      // 初始化全局bool变量s
process Pi              // 开始并发执行进程 Pi , i = 1,2,3,...
{
    do
    {
        flag = TS(s);
    }while(flag == true);
    Pi 进入临界区并做相关操作;
    status = true;
}                       

可以发现，如果先执行P1进程，一开始$s$是$true$，那经过$TS$操作之后变量$s$为 $false$，而 $flag$ 为 $true$。如果此时系统并发执行进程$P2$，则$P2$将会一直在 $do while$ 中空转，直到 $P1$ 离开临界区并将 $s$ 重新赋值为 $true$ 时，$P2$ 才能跳出那个循环。同样的，对于 $P3$、$P4$、…也是这样。

交换指令$SWAP$

$SWAP$指令可以交换两个参数的值；

我们设置一个公共变量 $lock$ ，用它来表示临界区是否 “上锁 ”。而且每个进程还有一个私有的变量 $key$，它可用于与 $lock$ 进行数值交换。

bool 所有Pi的key = true;
bool lock = false;

process Pi()        // 开始并发执行进程 Pi , i = 1,2,3,...
{
    do
    {
        SWAP(&lock, pi的key);
    }while(Pi的key);
    Pi进入临界区并做相关操作;
    lock = false;
}   

具体步骤如下：

• 假设先执行$P1$进程，那么经过$dowhile$循环后，$lock$变为$true$，$P1$进程开始执行临界区代码。

• 此时如果系统并发执行别的进程，别的进程会被卡在$dowhile$循环处，直至$P1$进程将$lock$恢复为$false$；

这样也完成了对临界区代码的互斥执行；

开关中断指令方法：

当某个进程进入临界区时，执行 “关中断” 指令。（由于关闭中断指令，进程在访问临界区的过程中不会被中断）

当该进程离开临界区后，执行 “开中断” 指令。（离开临界区后进程才能被中断）

这样也能控制进程互斥地进入临界区。

四、软硬件方法的优缺点

• 软硬件方法（除 “开关中断指令” 方法外）都采用了 “忙等待” 的方式。（即未执行的等待进程都是在 while 循环中空转）
• 软件方法实现起来比较复杂，需要一定编程的技巧。
• 硬件指令方法的代码简洁有效。
• 硬件中断屏蔽的方法的代价较高。（关闭终端的方法相当于将并发的系统变为了顺序执行的系统，代价较高）