2.进程
[TOC]
1.进程
状态
- 1)运行态（该时刻进程实际占用CPU）。
- 2)就绪态（可运行，但因为其他进程正在运行而暂时停止）。
- 3)阻塞态（除非某种外部事件发生，否则进程不能运行）。
转换2和3是由进程调度程序引起的，进程调度程序是操作系统的一部分，进程甚至感觉不到调度程序的存在。
PCB
每个进程在操作系统内用进程控制块（PCB）表示。
- 进程状态 新建、就绪、停止、运行、等待
- 程序计数器
- CPU寄存器
- CPU调度信息
- 进程优先级、调度队列指针、调度参数
- 内存管理信息
- 基址、界限寄存器的值、页表、段表
- I/O状态信息
- IO设备列表、打开的文件列表等
2.线程
进程和线程的区别?
进程是资源分配的最小单位，线程是程序执行的最小单位。
进程有自己的独立地址空间。线程是共享进程中的数据的，使用相同的地址空间，因此CPU切换一个线程的花费远比进程要小很多，同时创建一个线程的开销也比进程要小很多。
线程之间的通信更方便，同一进程下的线程共享全局变量、静态变量等数据，而进程之间的通信需要以通信的方式（IPC)进行。不过如何处理好同步与互斥是编写多线程程序的难点。
但是多进程程序更健壮，多线程程序只要有一个线程死掉，整个进程也死掉了，而一个进程死掉并不会对另外一个进程造成影响，因为进程有自己独立的地址空间。
线程访问权限
私有的存储空间：
- 栈
- 线程局部存储（Thread Local Storage）
- 寄存器
并发与并行
并发的关键是你有处理多个任务的能力，不一定要同时。
并行的关键是你有同时处理多个任务的能力。所以我认为它们最关键的点就是：是否是『同时』。
实现
在用户空间中
- 优点：
- 用户级线程包可以在不支持线程的操作系统上实现
- 它允许每个进程有自己定制的调度算法
- 缺点：
- 如果一个线程开始运行，那么在该进程中的其他线程就不能运行，除非第一个线程自动放弃CPU。在一个单独的进程内部，没有时钟中断，所以不可能用轮转调度（轮流）的方式调度进程
- 阻塞系统调用，进程会被阻塞
多对一模型，例如Green thread、GNU Portable thread
线程管理由线程库在用户空间进行，效率高。但是如果一个线程执行了阻塞系统调用，任意时刻只有一个线程能够访问内核，多个线程不能并行的运行在多处理器上，所以整个进程会被阻塞。
在内核中间中
在内核中有用来记录系统中所有线程的线程表。
-
优点：
- 更好的并发功能
-
缺点：
- 每创建一个用户线程就需要创建一个内核线程
一对一模型，Linux和Windows
混合实现
多对多模型多路复用了用户线程到同样数量或更小数量的内核线程上。
线程状态
- 运行
- 就绪
- 等待
线程调度
都带有优先级调度和轮转法
一般IO密集型比CPU密集型线程更容易得到优先级提升。
可抢占式线程和非可抢占式线程
同步与锁
- 锁
- 信号量
- 互斥量
- 和信号量不同的是，信号量可以被一个线程获取后，另一个线程释放。而互斥量是哪个线程获取，哪个线程释放。
- 临界区
- 读写锁
volatile
3.调度
抢占式和非抢占式
-
非抢占式
- 让进程运行直到结束或阻塞的调度方式
- 容易实现 适合专用系统，不适合通用系统
-
抢占式
- 允许将逻辑上可继续运行的在运行过程暂停的调度方式
- 可防止单一进程长时间独占CPU 系统开销大
进程调度
批处理系统调度
-
先来先服务 first-come first-severd （FCFS）
- 优点 简单
- 缺点 不够灵活，尤其是前面有占用时间很长的任务，而后面的任务耗时较短
-
最短作业优先 shortest job first （SJF）
-
最短剩余时间优先 shortest remaining time next
调度程序总是选择剩余运行时间最短的那个进程运行。再次提醒，有关的运行时间必须提前掌握
交互系统调度
- 轮转调度
轮转调度做了一个隐含的假设，即所有的进程同等重要
每个进程被分配一个时间段，称为时间片（quantum），即允许该进程在该时间段中运行。如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程。
从一个进程切换到另一个进程是需要一定时间进行管理事务处理的——保存和装入寄存器值及内存映像、更新各种表格和列表、清除和重新调入内存高速缓存等。假如进程切换（process switch），有时称为上下文切换（context switch），需要1ms，包括切换内存映像、清除和重新调入高速缓存等。
- 优先级调度
- 多级队列
分成多个队列，队列优先级不同，每个队列有自己的调度算法
最短进程优先保证调度彩票调度公平分享调度
线程调度
4.进程通信
- 共享内存
- 消息传递
- 例如 socket、RPC、RMI
5.进程同步
5.1 概念
竞争条件
两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件（race condition）
临界区
在某些时候进程可能需要访问共享内存或共享文件，或执行另外一些会导致竞争的操作。我们把对共享内存进行访问的程序片段称作临界区域（critical region）或临界区（critical section）。如果我们能够适当地安排，使得两个进程不可能同时处于临界区中，就能够避免竞争条件。
- 1)任何两个进程不能同时处于其临界区。
- 2)不应对CPU的速度和数量做任何假设。
- 3)临界区外运行的进程不得阻塞其他进程。
- 4)不得使进程无限期等待进入临界区。
5.2 同步方法
5.2.1 屏蔽中断
最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断，并在就要离开之前再打开中断。屏蔽中断后，时钟中断也被屏蔽。CPU只有发生时钟中断或其他中断时才会进行进程切换，这样，在屏蔽中断之后CPU将不会被切换到其他进程。于是，一旦某个进程屏蔽中断之后，它就可以检查和修改共享内存，而不必担心其他进程介入。
缺点：
- 因为把屏蔽中断的权力交给用户进程是不明智的
屏蔽中断对于操作系统本身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。
5.2.2 锁变量
5.2.3 严格轮换法
浪费CPU时间，所以通常应该避免。
只有在有理由认为等待时间是非常短的情形下，才使用忙等待。用于忙等待的锁，称为自旋锁（spin lock）。
整型变量turn，初始值为0，用于记录轮到哪个进程进入临界区，并检查或更新共享内存。开始时，进程0检查turn，发现其值为0，于是进入临界区。进程1也发现其值为0，所以在一个等待循环中不停地测试turn，看其值何时变为1。连续测试一个变量直到某个值出现为止，称为忙等待（busy waiting）。
5.2.4 Perterson解法
5.2.5 TSL指令
测试并加锁（Test and Set Lock）
Peterson解法和TSL或XCHG解法都是正确的，但它们都有忙等待的缺点。这些解法在本质上是这样的：当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止。
这种方法不仅浪费了CPU时间，而且还可能引起预想不到的结果。考虑一台计算机有两个进程，H优先级较高，L优先级较低。调度规则规定，只要H处于就绪态它就可以运行。在某一时刻，L处于临界区中，此时H变到就绪态，准备运行（例如，一条I/O操作结束）。现在H开始忙等待，但由于当H就绪时L不会被调度，也就无法离开临界区，所以H将永远忙等待下去。这种情况有时被称作优先级反转问题（priority inversion problem）。
5.2.6 信号量
参考Java的信号量
5.2.7 互斥量
如果不需要信号量的计数能力，有时可以使用信号量的一个简化版本，称为互斥量（mutex）。
5.2.8 屏障
可以参考Java的CyclicBarrier
5.3 管程
https://zh.wikipedia.org/wiki/%E7%9B%A3%E8%A6%96%E5%99%A8_(%E7%A8%8B%E5%BA%8F%E5%90%8C%E6%AD%A5%E5%8C%96)
管程 (英语：Monitors，也称为监视器) 是一种程序结构，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。这些共享资源一般是硬件或一群变量。管程实现了在一个时间点，最多只有一个线程在执行管程的某个子程序。与那些通过修改数据结构实现互斥访问的并发程序设计相比，管程实现很大程度上简化了程序设计。
管程提供了一种机制，线程可以临时放弃互斥访问，等待某些条件得到满足后，重新获得执行权恢复它的互斥访问。
6.死锁
死锁预防
死锁条件
- 1)互斥条件。每个资源要么已经分配给了一个进程，要么就是可用的。
- 2)占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。
- 3)不可抢占条件。已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
- 4)环路等待条件。死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源。
通过限制资源申请，确保四个条件之一不会发生。缺点是低设备使用率和设备吞吐率。
死锁避免
获得以后如何申请资源的附加信息。动态的检测资源的分配状态以确保循环等待的条件不成立。
安全状态
通过跟踪哪一个状态是安全状态，哪一个状态是不安全状态，可以避免死锁。安全状态就是这样一个状态：存在一个事件序列，保证所有的进程都能完成。不安全状态就不存在这样的保证。银行家算法可以通过拒绝可能引起不安全状态的请求来避免死锁。
死锁避免从本质上来说是不可能的，因为它需要获知未来的请求，而这些请求是不可知的。
- 资源分配图算法
- 银行家算法
死锁检测
- 每种类型一个资源的死锁检测
- 每种类型多个资源的死锁检测
死锁恢复
- 进程终止
- 终止所有进程
- 一次只终止一个进程
- 资源抢占
- 逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止。
活锁和饥饿
7.线程同步
Java并发编程实践
链接:https://pan.baidu.com/s/1ukIEcJzUzPufJZFF7Rsrhg 密码:szwe
8.经典问题
8.1 哲学家进餐
可参考
https://zhuanlan.zhihu.com/p/34553097