操作系统的进程/线程同步问题
来自我的个人博客 Minecode.link
很多操作系统都提供了进程和线程的并发操作，他们可能在异步执行时访问共享数据，而并发访问共享数据可能带来数据不一致的同步问题，在此总结一下操作系统的进程/线程同步问题，以线程的并发为例。
问题简介
多线程实现原理(以iOS为例)
上图是多线程的状态(以iOS系统为例)。操作系统是通过CPU的时间片轮转来实现多线程的，每个线程有着对应的时间片，当其时间片到来时CPU会切换到该线程上下文并执行，待时间片结束后切换至下一线程，保存原线程的上下文并加载下一线程的上下文，依次循环。
但是，CPU何时切换并不是由用户决定，当时间片到达后会立即进行线程的切换，那么当多个线程并发进行读写操作时，就可能出现线程同步问题。
我们先重现一下这个问题，以下函数模拟了买票的操作，持续买票直到卖完，整型sum表示当前的票数，函数如下:
- (void)buyFunction {
// 有余票则继续购买
while (sum > 0) {
// 购买前打印当前票数
NSLog(@"线程%@准备买票 剩余:%d张票", [NSThread currentThread].name, sum);
// 模拟购买操作,票数-1
sum--;
}
// 票卖完则打印当前票数
NSLog(@"线程%@: 票已卖完 剩余:%d张票", [NSThread currentThread].name, sum);
}
现在我们开两个线程同时执行此操作，初始为10张票(sum = 10)，查看控制台输出:
线程2准备买票 剩余:10张票
线程1准备买票 剩余:10张票
线程1准备买票 剩余:9张票
线程2准备买票 剩余:8张票
线程1准备买票 剩余:7张票
线程2准备买票 剩余:6张票
线程1准备买票 剩余:5张票
线程2准备买票 剩余:4张票
线程1准备买票 剩余:3张票
线程2准备买票 剩余:2张票
线程1准备买票 剩余:1张票
线程2: 票已卖完 剩余:0张票
线程1: 票已卖完 剩余:-1张票
观察结果，我们发现了一些问题:
(1) 两次买票过程余票数相同
(2) 同一张票买了两次
(3) 没有余票之后仍然被买了一次
这样的结果已经体现出了线程不安全的危害，为什么会出现这种情况呢？
前面讲到，CPU会在时间片结束后保存当前线程上下文，并切换至下一线程。那么当前线程很可能在获取了数据还没来得及处理，时间片就已结束，而当该线程的下一时间片到来时，数据可能已经变化了。一种可能的过程如下图所示
线程同步出现问题
这便是进程/线程并发访问数据时会存在的同步问题，接下来我们讨论如何解决该问题。
临界区问题
为了并发访问数据的同步问题，我们介绍临界区的概念。
临界区: 一种代码段，在其中可能发生多个线程共同改变变量、读写文件等操作，其要求当一个线程进入临界区时，其他线程不能进入。从而避免出现同时读写的问题。(实际上，临界区只需保证可以有多个读者同时执行读取操作，或唯一写者执行写入操作)
进入区: 判断线程能否进入临界区的代码段。
退出区: 线程离开临界区后可能对其执行的某些操作。
剩余区: 线程完全退出临界区和退出区后的剩下全部代码。
对于上述的买票示例，买票的整个过程即为临界区代码，但我们缺失了进入区，无法保证临界区内线程的唯一，所以出现了同步问题。
临界区调度原则
所有临界区调度应当符合以下原则:
- 同一时间临界区内仅可有一个线程执行，如果有若干线程请求进入空闲临界区，一次进允许一个线程进入，如果临界区已有线程，则要求其他视图进入临界区的线程等待。
- 进入临界区的线程必须在有限时间内退出，以保证其他线程能进入该临界区。
- 如果线程不能进入临界区，应让出CPU，避免出现忙等现象。
- 从线程请求进入临界区到允许，有次数限制，避免让线程无限等待。
总结为三点: 互斥、前进、有限等待。
Tips: 在非抢占内核系统中进程会一直运行直到中断或退出，故不涉及进程同步问题。
临界区问题的解决方法
解决临界区问题，需要通过加锁的方式，类似于当一个线程进入临界区后即上锁，阻止其他线程进入，待运行完成后打开锁允许其他线程进入。
软件实现方法
解决临界区问题，主要在于保证资源的互斥访问，以及避免出现饥饿现象。
Peterson算法提供了一个合理的思路: 设置旗标数组flag标记请求进入临界区的线程，设置turn表示可以进入临界区的线程，在进入区进行双重判断，两个线程同时对turn赋值只会有一个保留下来，从而确保资源访问的互斥。
而在退出区，对flag旗标进行了false处理，从而保证了"前进"原则，避免了剩余区中的线程持续抢占造成其他线程饥饿。
硬件实现方法
Peterson算法是基于软件的实现，而从硬件层面也可以解决此问题，硬件方面的处理主要在于线程修改共享资源时是原子地，即不可被中断。比如机器提供了能够原子执行的指令，那么我们可以通过简单的修改布尔变量来实现互斥，因为加锁的过程是原子的。而对于可能造成饥饿的问题，只需在退出区对等待列表进行一定处理，保证"前进"原则即可。
简单来说，无论硬件还是软件的实现，本质都是通过加锁。只是通过硬件的特性，可以提高效率，同时也简化了临界区的实现难度。
信号量
临界区问题为我们解决线程同步提供了一种思路，而在实际使用中，要处理同一个实例有多个资源的情况，我们可以采用一种较为简单的方式——信号量，大多操作系统都提供了信号量的同步工具。
原理
简单来说，信号量是某个实例可用资源的计数，初始为该实例可用资源的数量，而每当线程需要使用，则调用wait()方法减少信号量，释放资源时调用signal()方法增加信号量，故信号量为0表示所有资源都在被使用，线程使用资源的请求不被允许。
信号量主要分为计数信号量和二进制信号量，前者主要针对一个实例有多个资源的情况，值域不受限制，而后者信号量仅为0或1，也就是说线程之间访问该资源是互斥的，也可称作互斥锁。
同临界区问题的前提: 必须保证执行信号量操作wait(),signal()是原子地。
以下是信号量的伪代码实现:
while (true) {
waiting(mutex); // 减少信号量(进入区)
// 临界区
signal(mutex); // 增加信号量(退出区)
// 剩余区
}
具体实现
由于基于临界区问题，那么信号量在具体实现中也要处理其缺点: 饥饿问题。同时其需要避免忙等问题和死锁问题。
在此之前我们先看一下其基本功能实现。
实现信号量需要维护一个信号量值和一个等待进程链表。
当信号量为0时，将请求进入临界区的进程放入等待列表中，并阻塞自己(避免出现频繁循环请求的忙等问题)。待其他临界区退出时，从等待列表中取出并唤醒。以下为实现的伪代码:
// 信号量定义
typedef struct {
int value;
struct process *list;
} semaphore;
// 减少信号量
void wait(semaphore *mutex) {
mutex->value--; // 减少信号量值
if (mutex->value < 0) {
addToList(list, mutex); // 将该进程添加至等待进程链表
block(); // 阻塞自己等待唤醒
}
}
// 增加信号量
void signal(semaphore *mutex) {
mutex->value++; // 增加信号量
if (mutex->value <= 0) {
process *p = removeFromList(list ,mutex); // 同等待链表中取出一个进程
wakeup(P); // 唤醒等待中的进程
}
}
饥饿问题
在信号量大于0时从队列中取出哪个进程是需要讨论的问题，选择合适的调度方式很重要。FIFO(先进先出)可以解决，但如果LIFO(后进先出)调度则可能会造成部分进程无限期阻塞，也就是饥饿问题。
忙等问题
当进程请求进入临界区而没有被允许时，如果此进程开始在进入区连续循环请求，则会消耗大量性能，浪费了部分CPU时间片。这种加锁方式称为自旋锁，即进程在等待锁时仍然在运行，此方法会造成忙等的性能浪费，但同时也比阻塞-唤醒机制效率更高，避免了阻塞到唤醒的上下文切换。
如果要克服忙等问题，可以在进入区增加当信号量小于0时，进程阻塞自己，进入等待队列；当临界区内的线程执行完毕后，唤醒等待队列中的进程。同时要保证等待队列调度的算法合理性，避免某进程无限期等待。
死锁问题
死锁问题就是多个进程无限等待某个事件，而该事件是由这些进程来产生的，这样就会造成"第二十二条军规"中的问题，进程之间互相等待，无法前进。在此不讨论死锁问题，只介绍可能出现的死锁情况。如下图所示:
信号量死锁的情况
解决死锁问题主要可以从死锁预防、死锁避免、死锁检测、死锁恢复四个方面入手，后面会专门写文章讲解。
不同处理器的解决方案
单个处理器: 单处理器时无须担心并行运算造成的同步问题，所以简单在wait()和signal()中禁止临界区中进程的中断即可。
多处理器: 操作系统对于多处理器调度分为SMP和非SMP的情况(SMP为对称多处理，处理器各自控制各自的调度，而非SMP为某一个处理器作为中控，管理其他处理器的调度)。
非对称多处理: 对于非对称多处理，由于有中央处理器来调度，可以简单使用自旋锁来进行忙等，系统来决策等待锁的进程的调度问题。
对称多处理: 对于对称多处理系统，就要自行实现上述的信号量等待列表，以及等待锁时的阻塞——唤醒机制。
经典同步问题
涉及到同步问题，有几种经典的问题，主要的有读者——写者问题和哲学家进餐问题，前者关注互斥问题，后者关注死锁问题。
读者——写者问题
仅进行读取操作的为读者，而读写操作均需要的为写者。仍然以刚才的买票问题为例，我们不难发现，当同时读取时，不会出现问题，当唯一写入时，也不会出现问题，但是当同时进行读写时，则发生了数据错误问题。
所以读者——写者问题应当保证同一时间写者的唯一性及读者要等待写者完成后再执行。
同时，在实际实现中，要着重处理读者或写者的饥饿问题，读者/写者优先的方案很可能造成对方的饥饿。
哲学家进餐问题
哲学家问题是一个经典的死锁问题，n个哲学家围坐在圆桌上，圆桌上放着n支筷子，也就是没人左右都有1支筷子。只有同时拥有两支筷子才能吃饭，吃完饭后会放下筷子。若同一时间每个哲学家都先拿起右手边的筷子再拿起左手的，那么就造成了死锁问题，每个人都在等待左手的筷子。
哲学家进餐问题
解决办法多种多样，可以限制哲学家的数量为n-1，也可以要求拿起筷子前判断是否左右手的筷子均空闲。而本质上，解决方法就是死锁的四种解决方法: 死锁预防、死锁避免、死锁检测、死锁恢复。
总结
进程/线程同步问题是操作系统在数据共享方面的一大问题，其不仅需要硬件及系统级的实现，同时还需要程序员在开发时避免死锁，同步问题与死锁问题密不可分，后面将会讨论死锁问题。
