互斥算法基础

   <p>互斥是个现代编程经常需要解决的问题，但实际上，不少人是基于编程API中的锁API来理解互斥的，也有不少人是仅仅学习了操作系统教程中的形式逻辑的内容，对互斥实际要面对的问题没有体会，本文尝试把这个逻辑梳理出来。</p>    <p>互斥解决的问题是让一组操作串行化。解决串行化的基础方法是线程，线程是一个串行化执行系列的抽象。</p>    <p>这里的线程和串行化都是抽象的概念。所谓线程，可以是OS中创建的线程，进程，中断处理向量，也可以是另一个CPU，IMU，MCU中的线程，启动程序等等。</p>    <p>而所谓线程的串行化，也是从目的上来的，比如你写：</p>    <p>a=3;</p>    <p>b=4;</p>    <p>编译器，CPU，都可能认为这两者的先后顺序不影响你的结果，所以，执行上， 它们的执行不一定是有先后关系的。就算编译器按正确的顺序发出这两条指令，这还要看总线（包括Cache）系统的认知，这两个操作，作用到Cache和内存中的顺序也是没有保证的。</p>    <p>编译器，CPU，总线系统间，有很多额外的协议来保证你所需的串行化可以得到保证。比如memory barrior指令，编译器优化禁止等等。</p>    <p>所以，如果你仅仅写一般算法，认为线程是完全串行化是没有问题的。但如果你对串行化有非常specific的要求，你就必须理解CPU的这些行为，保证它是真正串行的。</p>    <p>当串行化的要求出现在多个线程上，这个问题就变得更复杂了。我们通常用mutex锁来实现两个线程内部操作的互斥。但我们必须清楚，mutex锁的行为是基于线程的实现的。pthread_mutex_t能提供的互斥是基于pthread_t的，不是pthread_t的线程使用pthread_mutex_t并不能正常工作。</p>    <p>同理，spin_lock_t是基于SMP系统的，不能用于CPU和MCU的互斥。RCU是基于Linux Kernel的调度模型的，并不能用于AMP不同异构系统之间互斥。这种问题是显而易见的，所有的串行化，不过是基于内存访问的部分原子操作，重试，中断这样的行为实现的，这些设计都是一种对线程实现的依赖，如果锁算法不依赖线程的实现，CPU调度，总线系统优化都无法做了。</p>    <p>这样就意味着，如果你要实现一个CPU和MCU之间的互斥算法，你就必须从CPU语义开始设计，而不能基于高级语言开始设计。</p>    <p>我们设想CPU和MCU共享内存和总线系统，它们要互斥访问一组全局变量。然后我们使用spinlock类似的算法，如果spinlock=1，CPU可以访问，如果spinlock=0，MCU可以访问。</p>    <p>CPU的代码这样写：</p>    <pre>  <code class="language-cpp">if(spinlock)  {    a=read_global_data("a");    b=read_global_data("b");    spinlock=0;  }</code></pre>    <p>MCU的代码这样写：</p>    <pre>  <code class="language-cpp">if(!spinlock) {    write_global_data("a", 1);    write_global_data("b", 2);    spinlock=1;  }</code></pre>    <p>好了，这个算法的要求就来了，首先，你要保证得了read/write_global_data()和spinlock的先后顺序。这里需要增加memory barrior。mb如何加法，这需要根据流程进行设计。</p>    <p>第二个要求是CPU一侧的代码必须是单线程的，否则如果两个CPU线程同时更新spinlock，你就需要加两个CPU间互斥的算法</p>    <p>其他，根据你增加的其他行为，都要进行更新的。</p>    <p>说到底，你要做一个独立的互斥算法，没有库支持，你要做设计，而不是直接用一个变量就说设计zuo'wan</p>    <p> </p>    <p>来自：https://zhuanlan.zhihu.com/p/25534698</p>    <p> </p>