不借助硬件支持，在【纯软件】层面实现【共享内存的互斥】：【Peterson算法】

在共享内存上实现互斥

thread: 人
共享内存：物理世界

失败的尝试

最开始没做任何努力
发现可能同时进入Alipay_withdraw的if

失败：处理器没有办法使得balance的load和store这两条指令原子的执行！

#include <thread>
#include <chrono>

unsigned long balance = 100;

#define LOAD(x) x
#define STORE(x, y) (x) = (y)


//  fail 原因
    //  balance 的 load 和 store 没有办法原子的完成！！！！

void Alipay_withdraw(int amt)
{
    // if(balance >= amt)      //  load
    if (LOAD(balance) >= amt)
    {
        //  可能两个thread都进入这里。unsigned -到<0后就会最大。
        std::this_thread::sleep_for(std::chrono::microseconds(1));
        // balance -= amt;     //  store
        STORE(balance, balance - amt);
    }
}

void Talipay()
{
    Alipay_withdraw(100);
}

int main()
{
    std::thread t1(Talipay);
    std::thread t2(Talipay);
    t1.join();
    t2.join();
    printf("balance = %lu\n", balance);
}

balance = 18446744073709551516
balance = 18446744073709551516
balance = 18446744073709551516
balance = 18446744073709551516
balance = 18446744073709551516
balance = 18446744073709551516
balance = 18446744073709551516
balance = 18446744073709551516
balance = 0
balance = 18446744073709551516

尝试用一个flag来标志，我们命名为lock

lock = LOCKED / lock = UNLOCKED

我们为什么要尝试lock？

因为 load , ++ , and store 原本不是原子的。

我们企图通过加入lock 来令这段code互斥，同一时刻只能有一个thread的pc在执行这段代码。使得处理器只能一次把他们执行完。即我们人为的把这些指令搞成原子的。
结果失败，失败原因

lock的load和store这两条指令没有办法原子的完成！！！，实际上和上面code的失败原因本质是一样的。

#include<thread>

#define UNLOCK 0
#define LOCK 1
int locked = UNLOCK;
unsigned long check = 0;

//  失败 原因
    //  lock的load和store这两条指令没有办法原子的完成！！！处理器办不到！

void critical_section()
{
    while(locked!=UNLOCK);      //  load lock
// retry:
//     if(locked!=UNLOCK)
//         goto retry;

    locked = LOCK;              //  store lock

    //  thread a 和 thread b可能同时进入这里
    //  load , ++ , and store 原本不是原子的。
    //  我们企图通过加入lock 来使得处理器只能一次把他们执行完、人为的把他们搞成原子的。
    //  结果失败
        //  失败原因
        //  lock的load和store这两条指令没有办法原子的完成！！！处理器办不到！
    ++check;

    locked = UNLOCK;
}


void thead_func()
{
    critical_section();
}

int main()
{
    std::thread t1(thead_func);
    std::thread t2(thead_func);
    t1.join();
    t2.join();
    printf("check = %lu\n",check);
}

// shc@DESKTOP-TVUERHD:~/Code/try/lock$ ./execute_try02.sh | head -2000 | uniq -c
//    1199 check = 2
//       1 check = 1
//     800 check = 2

Peterson

概述

Petetson算法本质上还是个自私的算法，
- 即便A/B在自己想进入临界区的时候都会先邀请对方上厕所。
- 但是这只是一种假客气
- 即便我们邀请了对方，一旦对方邀请了我们，那么我们就不客气，直接进入临界区。
  - 那么对方什么时候进入临界区？当我们离开临界区之后，对方检查到我们不想进入临界区（即离开了临界区），那么对方就会进入临界区）
Peterson 是不依赖硬件原子指令, 完全由软件实现的算法

流程

摘

A 和 B 争用[厕所的包厢] : 即[临界区]
想进入包厢之前，A/B 都要先举起自己的旗子 : x = 1 / y = 1(举旗子代表己方想要进入临界区)
- A 确认旗子举好以后，往厕所门上贴上 “B 正在使用” 的标签 : turn = B(贴对方的标签代表邀请对方先进入临界区(假客气))
- B 确认旗子举好以后，往厕所门上贴上 “A 正在使用” 的标签 : turn = A
然后，如果对方的旗子举起来 && 门上的名字不是自己，等待 : while(y == 1 && turn != A)
- 否则可以进入包厢
  - 如果对方的旗子没举起来,意味着对方不需要上厕所，我们可以直接进入临界区
  - 如果门上的名字是自己,意味着对方已经将我们的名字贴上去，我们的假客气被对方覆盖了，那么我们直接进入临界区。
出包厢后，放下自己的旗子 : x = 0 / y = 0
以下为总结

A和B有临界区func
0. : A想要进入func
- 0.1 : 先举起自己的旗子(举旗子代表己方想要进入临界区) : x = 1
- 0.2 : 并且在临界区上贴上对方B的标签。(贴对方的标签代表邀请对方先进入临界区(假客气)) : turn = B
1. : A在进入func之前, : while(y == 1 && turn != A)
- 1.1 检查对方是否想要进入临界区 : y == 1 ?
  - (对方的旗子是否举了起来) (对方的旗子举起来的话就代表对方会跟我们客气一下)
- 1.2 若 y != 1 , 则进入临界区
  - y!=1 ，即对方的旗子没举起来. 意味着对方不需要进临界区，我们可以直接进入临界区
- 1.3 若 y == 1 , 则观察临界区的标签是否是己方A : turn != A ? .
  - y==1 ，即对方想要进入临界区
  - turn != A 如果不是A的话，那么我们等待
    - 等待对方跟我们客气一下 , 即对方将我们的标签贴上去.（此时对方还没进入临界区,还没客气)。
    - 或者等待对方离开临界区, 放下旗子. (对方的假客气已经被我们的假客气覆盖了,对方会进入临界区,我们只能等待对方结束临界区使用)
  - turn == A 如果是A的话，那么我们可以直接进入临界区。
    - 如果门上的名字是己方,意味着对方已经将我们的名字贴上去，我们的假客气被对方覆盖了，那么我们直接进入临界区。
2. : 1中条件不满足时，进入临界区。
3. : 从临界区中出来之后，放下自己的旗 : x = 0。（自己不想进入临界区了）

code

Peterson算法

最后仍会出现错误是因为编译器会进行重排，处理器也会执行重排。不过我们的算法是没有错误的，正确的。经历了足足121778757次才发生错误

#include <atomic>
#include <thread>
#include <cassert>

std::atomic<int> check;     //  check设置成atomic 是因为我们要验证peterson算法。验证这个算法实现了互斥。那么就要保证目标的互斥代码段内没有破坏互斥的因素。
std::atomic<int> cnt;

#define A 0
#define B 1

int volatile x = 0, y = 0, turn = A;

void critical_section()
{
    ++cnt;
    ++check;
    if(check!=1)
    {
        printf("cnt = %d\n",cnt.load());
        exit(-1);           //  never reach
    }
    --check;
}

void thread_func_A()
{
    while(true)
    {
        /* PC1 */ x = 1;          //  A 举旗子
        /* PC2 */ turn = B;       //  贴 nameB （假客气一下hhh）
        /* PC3 */ while(y == 1 && turn != A);     //  此时B也要上厕所(y==1)，且B还没贴name--厕所的name不是A 那么A等等。因为A知道 B已经把旗子举了起来 B之后会将nameA贴上去。会覆盖掉A贴的nameB。所以A其实只是假客气一下 先把nameB贴上去 假意邀请B先上厕所，但如果B也客气一下（B如果要上厕所的话会先将nameA贴上去），那么A就不客气了，直接进入厕所。
        /* PC4 */ critical_section();             //  进入厕所
        /* PC5 */ x = 0;          //  A 放下旗子
    }
}

void thread_fund_B()
{
    while(true)
    {
        /* PC1 */ y = 1;          //  B举旗子
        /* PC2 */ turn = A;       //  贴nameA
        /* PC3 */ while(x == 1 && turn != B);     //  此时A要上厕所 且厕所的name不是B 那么B等等
        /* PC4 */ critical_section();
        /* PC5 */ y = 0;          //  B放旗子 
    }
}

int main()
{
    std::thread t1(thread_func_A);
    std::thread t2(thread_fund_B);
    t1.join();
    t2.join();
    return 0;
}

shc@DESKTOP-TVUERHD:~/Code/try/lock$ ./execute_peterson.sh
cnt = 121778757

model checker 工具

model checker的基本假设：每一行源代码的执行是原子的
列出所有状态及转移关系。
如图中红色区域：即为t1 t2都进入了临界区！

不落辰

并发-互斥算法-Peterson算法

在共享内存上实现互斥

失败的尝试

Peterson

概述

流程

code

model checker 工具