.. Kenneth Lee 版权所有 2017-2020
:Authors: Kenneth Lee :Version: 1.0
互斥算法设计
这个文档是写给内部团队的，但今天要出差，没有办法访问内部博客，反正是个通用知识 ，我就放在这里了。
互斥是个现代编程经常需要解决的问题，但实际上，不少人是基于编程API中的锁API来理 解互斥的，也有不少人是仅仅学习了操作系统教程中的形式逻辑的内容，对互斥实际要面 对的问题没有体会，本文尝试把这个逻辑梳理出来。
互斥解决的问题是让一组操作串行化。解决串行化的基础方法是线程，线程是一个串行化 执行序列的抽象。
也就是说，我们要让一个执行序列串行化，最基础的方法是把这个执行序列线程化，而不 是不少人以为的“使用互斥设计”，互斥是不得已而为之的辅助手段，不是串行化的基础。
这里的线程和串行化都是抽象的概念。所谓线程，可以是OS中创建的线程，进程，中断处 理向量，也可以是另一个CPU，IMU，MCU中的线程，启动程序等等。
而所谓线程的串行化，也是从目的上来的，比如你写：::
a=3;
b=4;
编译器，CPU，都可能认为这两者的先后顺序不影响你的结果，所以，执行上， 它们的执 行不一定是有先后关系的。就算编译器按正确的顺序发出这两条指令，这还要看总线（包 括Cache）系统的认知，这两个操作，作用到Cache和内存中的顺序也是没有保证的。
编译器，CPU，总线系统间，有很多额外的协议来保证你所需的串行化可以得到保证。比如 memory barrior指令，编译器优化禁止等等。
所以，如果你仅仅写一般算法，认为线程是完全串行化是没有问题的。但如果你对串行化 有非常specific的要求，你就必须理解编译器，CPU等平台组件的行为，保证它们真正串行 的。
当串行化的要求出现在多个线程上，这个问题就变得更复杂了。正如前面说到的，我们设 计串行化的基础是线程，但当部署完基础的串行化模型后，我们还会有辅助的串行化要求 ，这就需要互斥设计的支持了。
互斥设计的本质是在两个或者多个线程上制造一个“队列”，让并行的两个执行序列在这个 位置上排队。为了实现这一定，需要在线程的执行体（就是执行线程那些串行化指令的硬 件）上建立“原子化操作”的原则。
所谓“原子化执行的原则”，是说，当一个执行体在执行某个动作（或者序列）的时候，另 一个执行体必须能够停下来，等前者执行完后，再继续。
好比CPU更新内存中的值，CPU实际上是先更新近端cache的值（L1，L2，L3等），然后根据 一定的协议，同步给其他CPU的cache，然后又根据一定的协议，在总线上形成Burst（把多 个内存访问合并为一个），然后更新到总线上，进入DDR控制器，最后才实现完整的更新。 这种情况下，某个CPU对内存的更新，对于另一个CPU来说，是否是原子的，是需要结合这 两个执行体的行为来判断的，很多CPU都会支持CAS指令，目的都是为了让CPU间的互斥称为 可能。
所以，本质上，锁算法的基础是执行体间的一个协议，依赖执行体自身的行为。
我们通常用mutex锁来实现两个线程内部操作的互斥。但我们必须清楚，mutex锁的行为是 基于线程的实现的。pthread_mutex_t能提供的互斥是基于pthread_t的，不是pthread_t的 线程使用pthread_mutex_t并不能正常工作。
同理，spin_lock_t是基于SMP系统的，不能用于CPU和MCU的互斥。RCU是基于Linux Kernel 的调度模型的，并不能用于AMP不同异构系统之间互斥。这种问题是显而易见的。
这样就意味着，如果你要实现一个CPU和MCU之间的互斥算法，你就必须从CPU语义开始设计 ，而不能基于高级语言开始设计。
我们设想CPU和MCU共享内存和总线系统，它们要互斥访问一组全局变量。然后我们使用 spinlock类似的算法，如果spinlock=1，CPU可以访问，如果spinlock=0，MCU可以访问。
CPU的代码这样写：::
if(spinlock) {
a=read_global_data("a");
b=read_global_data("b");
spinlock=0;
}
MCU的代码这样写：::
if(!spinlock) {
write_global_data("a", 1);
write_global_data("b", 2);
spinlock=1;
}
好了，现在这个算法的要求就来了，首先，你要保证得了read/write_global_data()和 spinlock的先后顺序。这里需要增加memory barrior。mb如何加法，这需要根据流程以及 CPU和MCU的行为进行设计。
第二个要求是CPU一侧的代码必须是单线程的，否则如果两个CPU线程同时更新spinlock， 你就需要加两个CPU间互斥的算法
其他，根据你增加的其他行为，都要进行更新的。
说到底，你要做一个独立的互斥算法，没有库支持，你要做设计，而不是直接用一个变量 就说设计做完了。