本文已收录到：清华大学操作系统课程笔记 专题
同步互斥
并发多线程，如果不用锁的话，每次运行结果都可能不同。
如果对多并发进程之间要求每次结果应该一样，就需要考虑同步互斥问题；有时候却还需要多进程不同运行时候的结果不一样，例如在通信的时候，就期望不同，这时候就不需要考虑这种问题。
这就会出现间歇性问题。但进程并发执行有很多好处，我们不能抛弃它。
进程并发的好处
好处一：共享资源
好处二：提高速度：IO和CPU计算可以重叠。多处理机执行。
好处三：模块化：多个进程完成一个功能。
并发 创建进程 时的标志分配
这是我们所期望的结果。下面是可能出现的一种错误：
出现了错误，分配的进程pid相同。
然后进程B执行 INC Reg1，next_pid变为101
切换到进程A，执行INC reg1，next_pid变为101。
我们发现，next_pid被赋值了两次。
原子操作
同步问题与解决方案
下面来解决原子性问题。举个例子：
如何解决？
上面这种办法也行，但似乎傻fufu的
方案一：
如果是计算机的思维来看：
进程A发现现在没面包也没便签，这时候B来了，他也看见没有面包没有便签，这时候A出门买面包并留下标签了。B接下来也离开了去买面包留下便签。——最后md… …留下两个便签，买回来两个面包。
方案二：
哈哈哈哈，都不买了。
方案三：
这下倒好，都不检查有面包没，就直接结束了。。。（双方都认为对方去买）
方案四：
这种方法是有效的。虽然方法是有效的，但很复杂，因为进程A一直在while等待，例如如果有更多的进程怎么办？md … …这问题更复杂。还有个缺点就是A一直在等待，它没法去做其他事。
还有个问题就是他很复杂，需要枚举所有的情况，只有枚举完所有的情况后才能确保有效。写代码的时候需要绞尽脑汁的想。
方案五：利用两个原子操作实现一个锁
互斥：一个进程占用资源，其他进程需要等待这个进程释放资源。
死锁：多个进程各自占用部分资源，形成循环等待。（哲学家就餐）
饥饿：一个进程轮流占用资源，某个进程永远得不到资源。
临界区
进入区：检查进程进入临界区的条件是否成立（即访问规则），设立标志。
临界区：保护的需要互斥执行的代码。
退出区：清除标志。
Ps：我怎么感觉临界区的概念有点像铁路上的闭塞区间。
临界区的访问规则：
- 空闲让进：当无进程处于临界区，表明临界资源处于空闲状态，允许请求进去临界区的进程进去临界区
- 忙则等待：当有进程处于临界区，表明临界资源正在访问，其他请求进入临界区的进程必须等待。
- 有限等待：应使在等待的进程在有限的事件内进入自己的临界区，避免”死等”状态
- 让权等待：当进程不能进入自己的临界区，应立即释放处理机，以避免进入”忙等”状态
下面介绍三类临界区的实现方法，分别是禁用中断、软件方法、更高级的抽象方法。不同实现方法的比较可以根据并发效率衡量。
临界区的实现方法——禁用中断（一般不用）
基本思路是：
- 第二个进程发现临界区被上锁了，就直接让第二个进程陷入内核态去等待。
- 因为没有中断就没有上下文切换，自然没有并发。
- 现代计算机都提供的有禁用中断的指令。
在计算机中，目前是不能不用，才会用，是下下策。这就相当于霸占整个电脑。
临界区的实现方法——软件方法，设置共享变量
基本思路：通过共享变量的访问来控制同步。
第一次尝试
搞一个共享变量用于表示谁能够进入临界区：
此方法满足了互斥，但有个问题就是一个进程不能连续两次进入临界区。即满足的忙则等待，但是不满足“空闲则入”，即不完全满足临界区的访问规则。
方法二：改进使得进程可以交替进入临界区，进入后贴标签
设置两个变量即数组
这样改造后交替进行也没问题。但有缺点，就像前面的贴标签买面包一样，如果第一个进程判断后，这时候第二个进程来打岔，这就会导致两个进程都进入了临界区。这样不满足忙则等待的临界区规则。
方法三：先贴标签
有可能导致两个进程都觉得自己进不去，结果谁也没进。就像之前两个人都觉得对方会去买面包一样。
Peterson算法——满足两个进程互斥访问
Peterson算法可以实现有限等待，但仍然是while循环，不能够在不满足条件的时候主动让出处理机，即没有实现让权等待。
Dekkers算法——换一种形式写两个进程互斥算法
原理跟上面的Peterson算法一样。
Dekkers算法——多个进程互斥算法
临界区的实现方法——更高级的抽象办法，使用锁这个抽象的数据结构
软件级别是可以做到多进程互斥访问的，但基于软件的同步算法很繁琐，并且需要重复的查找状态。如果有多个临界区，情况会更加棘手。接下来引入锁的概念。
锁这个抽象的数据结构一个二进制变量和两个操作原语组成：
二进制变量表示是锁定还是解锁，两个原语表示操作。
原子操作指令由CPU底层硬件的实现。内部基于原子操作指令，是CPU所提供的原子操作指令——这一部分请参考CPU自制实验。确保不会出现 部分执行 的情况。现代CPU体系结构中都提供了一些特殊的原子操作指令。例如：测试和置位（Test-and-Set）指令：
用伪代码的形式表示出：
（这里的原子操作指令，，我没懂。等回头看看系统结构视频里的同步互斥。感觉这里应该更偏近底层的东西，可能是纯硬件实现的吧。）
解答：确实是，上面的 TestAndSet 伪代码在CPU内存是一坨，在CPU指令集中会将这三个指令糅合在一起，确保原子性操作，中间不会暂停。
交换指令：功能是交换内存中的两个值，伪代码如下
CPU会保证上面的操作是原子操作。
基于上面两个原子指令，我们可以实现锁。接下来先用TS指令实现自旋锁。
什么是自旋锁？
第二个进程对第一个进程的独占区想要进行操作的时候发现独占区的二进制变量被定义为锁上了，那么第二个进程就会通过while语句不断的询问判断这个独占区是否被解锁。（Ps：CPU不会将第二个进程放置在内核态，而是一直在用户态运行）
使用TS指令实现自旋锁
test-and-set()伪指令作用是试图读取、判断是否为1并写入1。
会有两种返回结果：
- 返回1表示当前TS指令读取到的是0，表示锁忙，需要等待。
- 返回0表示锁闲，while语句失效，可直接往下执行，并上锁（置为1）。
自旋锁需要语言层面支持原子操作，也就是说不能在我上锁过程中还会有进程来打断我。这一部分的实现是基于CPU底层的交换指令的，这部分等我写CPU的时候再来看看——参考自制CPU实验。
无忙等待锁
之前的自旋锁如果遇到锁忙的情况就会一直执行while语句以阻断进入临界区，这会导致消耗CPU的时间。
以上swap和TS指令都可以有效的实现进程互斥，但均不能实现让权等待。接下来的信号量方法可以实现让权等待。
