并发：死锁和饥饿
1. 死锁原理
死锁定义为一组互相竞争资源或进行通信的进程的“永久”阻塞。当一组进程中的每个进程都在等待某个事件，而仅有这组进程中的被阻塞的其他进程才可触发事件，就称这组进程发生了死锁。因为没有事件能够被触发，故死锁是永久性的。
资源通常分为两种，可重用资源和可消耗资源。
1.1 可重用资源
可重用资源是指一次仅供一个进程安全使用且不因使用而耗尽的资源。包括处理器、I/O通道、内存和外村、设备以及文件、数据库和信号量等数据结构。
1.2 可消耗资源
可消耗资源是指可被创建（生产）和销毁（消耗）的资源，比如中断、信号、消息和I/O缓冲区中的信息。
1.3 死锁的条件
- 互斥 一次只有一个进程可以使用一个资源
- 占有且等待 当一个进程等待其他进程时，继续占有已分配的资源
- 不可抢占 不能强行抢占进程已占有的资源
- 循环等待 存在一个必须的进程链，每个进程至少占有此链中下一个进程所需的一个资源。
2. 死锁预防
2.1 互斥
一般来说，此条件不可能禁止。
2.2 占有且等待
可以通过一次性占有所需的所有资源，这是一种比较低效的办法。
2.3 不可抢占
占有某些资源的一个进程在申请进一步的资源时若被拒绝，则改进程必须释放已其最初占有的资源，必要时可以再次申请这些资源或其他资源。其次，在任意两个进程的优先级不同的条件下，一个进程请求当前被另一个进程占有的资源时，操作系统可以抢占另一个进程，要求其释放资源。
2.4 循环等待
可通过定义资源类型的先行顺序来预防。也是比较低效的。
3. 死锁避免
3.1 进程启动拒绝
若一个进程的请求会导致死锁，则不启动改进程。
3.2 资源分配拒绝
资源分配拒绝又称为银行家算法。该方法类似于银行业务。从银行贷款的顾客对应于进程，贷出的钱对应于资源。作为银行业务问题，银行能贷出的钱的有限，每名顾客都有一定的银行信用额，顾客可以选择借一部分，但不能保证顾客取得大量贷款后一定能偿还，银行没有足够的本金放贷时也会拒绝贷款给顾客。
4. 死锁检测
死锁检测可以频繁在每个资源请求发生时，也可以进行的少一些。检测到死锁时，可以采取一些策略恢复：
- 取消所有的死锁进程
- 进程回滚。回滚到前面定义的检查点，然后重新启动所有进程
- 连续取消死锁进程直到不再存在死锁
- 连续抢占资源直到不再存在死锁
5. 哲学家就餐问题
有五位哲学家住在一栋房子里，他们的面前有一张餐桌。每位哲学家的生活就是思考和吃饭。就餐的安排很简单：一个圆桌上有一大碗面和5个盘子，每位哲学家有一个盘子，还有5把叉子。每位想吃饭的哲学家需要使用盘子盘子两侧叉子，取面和吃面。要保证两位哲学家不能同时使用同一把叉子，同时还要避免死锁和饥饿。
可以的两种解决方案：
- 基于信号量的解决方案
- 基于管程的解决方案
6. UNIX并发机制
6.1 管道
UNIX对操作系统开发最重要的贡献之一就是管道。管道是一个环形缓冲区，它允许两个进程以生产者/消费者的模型进行通信。因此，这是一个先入先出（FIFO）的队列，一个进程负责写，一个进程负责读。
- 管道在创建的时候获得一个固定大小的字节数。
- 当一个进程试图往管道中写时，如果有足够的空间，则立即执行写请求，否则该进程被阻塞。
- 一个读进程试图读区的字节数多余当前管道中的字节数时，它也被阻塞，否则立即执行读请求。
- 操作系统强制实施互斥，即一次只能有一个进程可以访问管道。
管道分为两类：命名管道和匿名管道。只有具有父子关系的进程才可以共享匿名管道，而不相关的进程只能共享命名管道。
6.2 消息
消息是有类型的一段文本。UNIX为参与消息传递的进程提供msgsnd和msgrcv系统调用。每个进程都有一个与之相关联的消息队列，其功能类似信箱。
6.3 信号量
UNIX为信号量提供了多个操作，递增和递减操作的值可以大于1。内核自动完成所有需要的操作，在所有操作完成前，任何其他进程都不能访问该信号量.
6.4 信号
信号是用于向另一个进程通知发生异常事件的机制。信号类似于硬件中断，但没有优先级。对于同时发生的信号，一次只给进程一个信号，没有特定的次序。
进程间可以相互发送信号，内核也可以在内部发送信号。常用的信号如下：
| 信号名称 | 信号数 | 描述 |
|---|---|---|
| SIGHUP | 1 | Hang up detected on controlling terminal or death of controlling process |
| SIGINT | 2 | Issued if the user sends an interrupt signal (Ctrl + C). |
| SIGQUIT | 3 | Issued if the user sends a quit signal (Ctrl + D). |
| SIGFPE | 8 | Issued if an illegal mathematical operation is attempted |
| SIGKILL | 9 | If a process gets this signal it must quit immediately and will not perform any clean-up operations |
| SIGALRM | 14 | Alarm Clock signal (used for timers) |
| SIGTERM | 15 | Software termination signal (sent by kill by default). |
7. Linux内核并发机制
Linux包含了UNIX系统中出现的所有的并发机制。Linux还支持一种特殊类型的信号——实时信号（RT signals），这种信号是POSIX.1b实时扩展中的一个特性。实时信号和标准的UNIX信号相比，有三个主要的不同点：
- 支持按优先级顺序排列的信号进行传递
- 多个信号能进行排队
- 在标准信号机制中数值和信号只能视为通知，不能发送给目标进程，但是实时消息机制可以讲数值（一个整数或指针）随信号发送过去。
Linux还包含一套为内核线程并发准备的机制。
7.1 原子操作
原子操作在执行时不会被打断或干扰。在单处理器上，原子操作从开始到结束的这段时间内不能被中断，在多处理器系统中，原子操作所针对的变量将被锁住，以避免被其他进程访问，直到原子操作结束。
7.2 自旋锁
在Linux中保护临界区的常用技术时自旋锁（spinlock）。在同一时刻，只有一个线程能获得自旋锁。其他试图获得自旋锁的线程将一直进行尝试（即自旋），直到获得了该锁。
本质上，自旋锁建立在内存区上的一个整数上，任何线程进入临界区前都必须检查改整数，如果改置为0，则线程将改值设置为1，然后进入临界区。若改值为1，则线程继续检查直到该值为0。
自旋锁很容易实现，但是有个缺点，锁外面的线程会以忙等待的方式继续执行，在获得锁所需的事件较短时会很高效。
读写自旋锁机制允许在内核中达到比基本自旋锁更高效的并发读。读写自旋锁允许多个线程以只读的方式访问同一数据，只有当一个线程想要更新数据时才会互斥的访问该自旋锁。
7.3 信号量
Linux在内核中提供三种信号量：二元信号量、计数信号量和读写信号量。
7.4 屏障
为保障指令执行的顺序，Linux提供了内存屏障（memory barrier）设施。