参考链接 Race condition https://blog.csdn.net/weixin_41042404/article/details/81430283

一、什么是竞态条件？

竞态条件 Race condition，它旨在描述一个系统或者进程的输出依赖于不受控制的事件出现顺序或者出现时机。此词源自于两个信号试着彼此竞争，来影响谁先输出。
举例来说，如果计算机中的两个进程同时试图修改一个共享内存的内容，在没有并发控制的情况下，最后的结果依赖于两个进程的执行顺序与时机。而且如果发生了并发访问冲突，则最后的结果是不正确的。

二、Critical Section 临界区

critical section 是每个线程中访问临界资源的那段代码，不论是硬件临界资源，还是软件临界资源，多个线程必须互斥地对它进行访问。
要阻止出现 race condition 情况的关键就是不能让多个进程同时访问有限的共享资源。
访问共享资源的那段代码就是critical section。所有的解决方法都是围绕这个critical section来设计的。
想要成功的解决race condition问题，并且程序还可以正确运行，从理论上应该满足以下四个条件：

  1. 不会有两个及以上进程同时出现在他们的critical section；
  2. 不要做任何关于CPU速度和数量的假设；
  3. 任何进程在运行到critical section之外时都不能阻塞其他进程；
  4. 不会有进程永远等在critical section之前。

三、互斥

方法 效果 介绍 优缺点
Disabling interrupts
中断禁止		 只对单核cpu有效 禁止中断后，破坏了CPU调度机制，电脑可能会很卡，不可取
Lock variables
锁定变量		 错误 使用锁定变量lock代表资源是否被占用。
lock为1时，表示资源空闲，占用的线程（线程1）将lock修改为0后进入critical section，其他线程等待，线程1退出critical section后，将lock修改为0。		 这种方法是错误的，因为进入critical section时对lock的修改，引入了对于lock 变量的race condition
Strict alternation
严格轮转法		 有缺陷 遵循严格轮转法的代码维护变量turn来代表哪个线程可以进入critical section。
turn取值的数量n与线程的数量n对应，线程进入critical section时会对turn轮询，只有turn为线程对应的值时，线程才会执行critical section，否则就要一直堵塞，退出critical section时，线程修改turn（turn=(turn+1)%n），下一个线程才能进入critical section。		 严格轮转法使得n个线程严格地按顺序使用共享资源，这可能造成严重的阻塞，某线程获得共享资源的占用权后，迟迟不进入critical section，导致后面的线程堵塞，此时共享资源是闲置的，这违背了“任何进程在运行到critical section之外时都不能阻塞其他进程”的原则
Perterson’s solution 对两个线程有效 Perterson’s solution使用变量 turn 和 flag 数组 在纯软件层面实现互斥。
turn 的值代表是哪个进程最后访问。
flag 数组代表不同线程是否准备进入critical section。
turn和flag数组的值的排列组合足以应对两个线程的各种情况。
具体可以参考下文的代码。		 Perterson’s solution是锁定变量的进阶，除了turn（lock）变量 外引入了flags数组，只对两个线程有效，更多的线程需要拓展，是纯软件的有效的互斥算法
但有忙等待的缺陷
Perterson’s solution的拓展
Filter算法		 有效 对多个线程有效，使用 level 数组和 waiting 数组在纯软件层面实现互斥。
level 数组的大小为线程数 N，存储不同线程的优先级（0—N-2）。
waiting 数组的大小为 N-1 ，模拟了一个阻塞（忙等待）的线程队列，从位置0为入队列，位置越大则入队列的时间越长。每个线程为了进入critical section，需要在队列的每个位置都经过一次，如果①其他线程的优先级＜当前线程（考察数组level）或者②被其他线程把阻塞当前线程的waiting[l]修改（waiting[l] ≠ i），则当前线程在队列中向前走过一个位置。
具体可以参考下文的代码。		 Filter算法 vs Perterson’s solution
flags数组——level数组，表示线程的等待等级
turn——waiting数组，模拟堵塞队列，表示当前哪个进程需要被堵塞
但有忙等待的缺陷

| | Test and set lock 测试并上锁 | 有效 | TSL RX,LOCK
TLS指令表示将内存字LOCK读入寄存器RX，读字和写字是原子的，这个特性是由硬件支持的，执行TSL指令时会锁住内存总线，禁止其他CPU在该指令结束前访问LOCK内存

硬件的支持下，就可以使用Lock variables 锁定变量了
代码见下文 | 硬件支持
但有忙等待的缺陷 | | Semaphores 信号量
https://blog.csdn.net/qq_20176001/article/details/100080054 | 有效 | Semaphores(信号量)是一个特殊的锁变量用来记录wakeup的数量。
对信号量有两个原子性的操作，DOWN 和UP（注意原子性）：
DOWN：如果信号量的值大于0，DOWN将信号量的值减1，并返回。如果信号量=0，DOWN操作被阻塞。
UP：如果有任何进程被阻塞在DOWN操作，选择一个唤醒，如果没有进程被阻塞在DOWN，那么就将信号量加1。 | 代码部分感觉有问题？
先不管了 | | Mutexes | 有效 | Semaphore的简化版本 | 略 |

严格轮转法

  1. //线程0
  2. while(True){
  3.     while(turn!=0);
  4.     critical_section();
  5.     turn = 1;
  6.     noncritical_section();
  7. }
  8. //线程1
  9. while(True){
  10.     while(turn!=1);
  11.     critical_section();
  12.     turn = 0;
  13.     noncritical_section();
  14. }

Perterson’s Solution

  2. #define FALSE 0
  3. #define TRUE 1 
  4. #define N 2 /* number of processes */
  5. int turn; /* whose turn is it? */
  6. int flags[N];/* all values initially 0 (FALSE)*/
  7. void enter_region(int process) /* process is 0 or 1 */
  8. {
  9.     int other; /* number of the other process */
  10.     other = 1 - process;  /* the opposite of process */
  11.     flags[process] = TRUE; /* show that you are interested */
  12.     turn = process;/* set flag */
  13.     while (turn == process && flags[other] == TRUE) /* null statement */;
  14. }
  16. void leave_region(int process) /* process: who is leaving */ 
  17. {
  18.     [process] = FALSE; /* indicate departure from critical region */ 
  19. }

Perterson’s Solution 的拓展

  1. // initialization
  2. level[N] = { -1 };     // current level of processes 0...N-1
  3. waiting[N-1] = { -1 }; // the waiting process of each level 0...N-2
  5. // code for process #i
  6. for(l = 0; l < N-1; ++l) {
  7.     level[i] = l;
  8.     waiting[l] = i;
  9.     while(waiting[l] == i &&
  10.           (there exists k ≠ i, such that level[k] ≥ l)) {
  11.         // busy wait
  12.     }
  13. }
  15. // critical section
  17. level[i] = -1; // exit section

Test and set lock 测试并上锁

  1. enter_region:
  2.         TSL REGISTER,LOCK  //TSL指令，将LOCK中的值copy到寄存器REGISTER中，并将LOCK置为1
  3.         CMP REGISTER,#0    //CMP指令，比较REGISTER的值和0，CMP指令实际上是做减法，不存储结果，只影响标志位，相等 ZF（零标志位）置为1，不等ZF置为0
  4.         JNE ENTER_REGION   //JNE指令，ZF=0就跳转，即上一步比较中如果不相等就跳转
  5.         RET                // 返回，进入临界区
  7. leave_region:
  8.         MOVE LOCK,#0
  9.         RET

Semaphores 信号量

  1. #define N 100
  2. typedef int semaphore;
  4. //mutex：用来控制生产者消费者不会同时访问buffer
  5. semaphore mutex = 1;
  7. //empty：还可以生产的物品的数量，也就是buffer中空闲的数量，初始为N 
  8. semaphore empty = N;
  10. //full: 未被消费掉的物品的数量，也就是buffer中物品量，初始为0 
  11. semaphore full = 0;
  13. void producer(void) {
  14.      int item;
  15.      while (TRUE){
  16.           item = produce_item();
  17.           down(&empty);
  18.           down(&mutex);
  19.           insert_item(item);
  20.           up(&mutex);
  21.           up(&full);
  22. } }
  23. void consumer(void) {
  24.      int item;
  25.      while (TRUE){
  26.           down(&full);
  27.           down(&mutex);
  28.           item = remove_item();
  29.           up(&mutex);
  30.           up(&empty);
  31.           consume_item(item);
  32. } }