1. 进程
1.1 概念
进程的经典定义是一个执行中的程序的实例。与每个进程相关的是地址空间，地址空间中存放有可执行程序、程序的数据以及程序的堆栈。与每个进程相关的还有资源集，通常包括寄存器（含有程序计数器和堆栈指针）等。进程基本上是容纳运行一个程序所需要所有信息的容器。
在许多操作系统中，与一个进程有关的所有信息，除了该进程自身地址空间的内容以外，均存放在操作系统的一张表中，称为进程表。
另补充一个概念：
- 并发：两个或多个事件在同一个时间段内发生
- 并行：两个或多个事件在同一时刻发生（同时发生），并行是并发的真子集
1.2 进程的创建与终止
在Unix中，父进程通过fork函数创建一个新的运行的进程。新创建的子进程几乎但不完全与父进程相同。子进程得到与父进程用户级虚拟地址空间相同的（但是独立的）一份副本，包括代码和数据段、堆、共享库以及用户栈。不可写的内存区是共享的，可写的内存区域通过写时复制共享。
由于fork的这一机制，操作系统的进程间是有层级关系的，init是所有进程的父进程。
当一个进程由于某种原因终止时，内核并不是立即把它从系统中清除，而是保持这一状态，直到被它的父进程回收。一个终止但还未回收的进程被称为僵尸进程。
1.3 进程的状态
就绪是由于没有被分到时间片导致的，一旦被分配到CPU资源即可运行。阻塞并不是因为没有CPU。只有就绪和运行是双向转换的。
1.5 进程控制块 PCB
为了实现进程模型，操作系统维护着一张表格，即进程控制块，每个进程占用一个进程表项。该表项包含了进程状态的重要信息，包括程序计数器、堆栈指针、内存分配状况、所打开的文件状态。当进程由运行态变为阻塞态或就绪态时，会将必要的信息保存在PCB中。
1.4 异常的处理
异常可以分为以下四类，
| 类别 | 原因 | 异步/同步 |
|---|---|---|
| 中断 | 来自I/O设备的信号 | 异步 |
| 陷阱 | 有意的异常，系统调用 | 同步 |
| 故障 | 潜在可恢复的错误 | 同步 |
| 终止 | 不可恢复的错误 | 同步 |
系统中为每一种可能的异常分配了一个唯一的非负整数的异常号，在系统启动时，操作系统分配和初始化一张异常表，异常表的起始位置放在一个叫异常表基址寄存器的特殊CPU寄存器里。
2. 线程
2.1 线程与进程的区别
-
进程是对运行时程序的封装，是系统进行
资源调度和分配的的基本单位，实现了操作系统的并发； -
线程是进程的子任务，是
CPU调度和分派的基本单位，用于保证程序的 实时性，实现进程内部的并发； -
一个程序至少有一个进程，一个进程至少有一个线程，线程依赖于进程而存在；
-
进程在执行过程中拥有独立的内存单元，多线程拥有相同的地址空间。（第一列是进程中线程共有的，第二列是每个线程中独占的）
-
线程创建和撤销消耗的代价更低
2.2 线程的实现方式
有两种线程实现方式，左图是用户级线程包；右图是由内核管理的线程包。
-
在用户空间中实现线程
该方法将线程包放在用户空间中，内核对线程包一无所知。每个进程都需要有专门的线程表。进行线程切换时不需要陷入内核，不需要上下文切换，并且它允许每个进程都有自己定制的调度算法。
-
在内核中实现线程
在内核中有用来记录系统中素有线程的线程表，当某个线程希望创建一个新线程或撤销一个已有线程时，它进行一个系统调用。由于在内核中创建或撤销线程的代价大，提出了线程池的概念。
线程的实现方式不同，线程的调度方式也不同。
考虑用户级线程，由于内核并不知道线程的存在，选取一个进程，给予A时间片，A中的线程调度程序决定哪个线程运行，A时间片可能会被A中的一个线程独占，也或者被A中多个线程分配。
如果是内核级线程，内核选择一个特定的线程运行，不用考虑线程属于哪个进程，不过如果有必要的话，可以这么做（跨进程调度线程开销大，内核会将这个开销考虑进去）
3. 进程同步
进程间通信需要解决三个问题：如果将消息传递给另一个，如何保证进程在关键活动中不会出现打叉，如何保证按照正确的顺序进行。
当两个或多个进程读写某些共享数据，而最后的结果取决于进程运行的精确时序，称为竞争条件。避免竞争条件的关键是创建临界区。保证同一时刻，只有一个进程访问共享资源，换言之，我们需要的是互斥。除了互斥之外，我们还需要保证多进程的执行按某种顺序执行，我们称之为同步。有许多方法可以创建临界区，其中最常见的一种是信号量和管程。
3.1 信号量
由Dijkstra提出，引入了一种新的变量类型，信号量。对于每一个信号量都有两种操作，up和down。up和down操作包括对信号量的检查、修改以及可能发生的睡眠操作，这几个步骤是不可分割的，即是原子操作。
使用信号量实现生产者-消费者问题
#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer() {
while(TRUE) {
int item = produce_item();
down(&empty);
down(&mutex);
insert_item(item);
up(&mutex);
up(&full);
}
}
void consumer() {
while(TRUE) {
down(&full);
down(&mutex);
int item = remove_item();
consume_item(item);
up(&mutex);
up(&empty);
}
}
信号量mutex用于互斥的访问缓冲区，full和empty是为了实现同步。
3.2 管程
管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。
管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。
联想一下，在Java中，synchronized的实现正是使用了管程的思想。synchronized 关键字修饰的代码块，在编译期会自动生成monitorenter和monitorexit这两个字节码指令，这两个字节码都需要一个reference类型的参数来指明要锁定和解锁的对象，在成员方法中默认是this，在静态方法中则默认是.class对象。而这个要被锁定的对象正是管程中的条件变量，只不过只有一个条件变量。
在同步代码块中我们可以使用wait方法和notify方法进行线程的同步
import java.util.*;
import java.util.concurrent.TimeUnit;
public class Test {
public static void main(final String[] args) throws Exception {
Thread t1 = new T1();
Thread t2 = new T2();
t1.start();
TimeUnit.SECONDS.sleep(2);
t2.start();
}
static Object lock = new Object();
public static class T1 extends Thread {
public void run() {
synchronized (lock) {
System.out.println(System.currentTimeMillis() + " :T1 启动！");
try {
System.out.println(System.currentTimeMillis() + " :T1挂起...");
lock.wait();
System.out.println("t1线程被唤醒...");
} catch (Exception e) {
e.printStackTrace();
}
System.out.println(System.currentTimeMillis() + " T1 end");
}
}
}
public static class T2 extends Thread {
public void run() {
synchronized (lock) {
System.out.println(System.currentTimeMillis() + " :T2 start! 随机通知一条线程。");
lock.notify();// 要object实例调用notify才行
System.out.println(System.currentTimeMillis() + " T2 end");
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
}
可以看到在调用wait后，会立刻释放锁，而在notify后则不会，直到走出synchronized同步块之后才会把锁释放。
4. 经典同步问题
4.1 哲学家进餐问题
#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N // 右邻居
#define THINKING 0
#define HUNGRY 1
#define EATING 2
typedef int semaphore;
int state[N]; // 跟踪每个哲学家的状态，需要互斥访问
semaphore mutex = 1; // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N]; // 每个哲学家一个信号量
void philosopher(int i) {
while(TRUE) {
think(i);
take_two(i);
eat(i);
put_two(i);
}
}
void take_forks(int i) {
down(&mutex);
state[i] = HUNGRY;
check(i);
up(&mutex);
down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}
void put_forks(i) {
down(&mutex);
state[i] = THINKING;
check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了
check(RIGHT);
up(&mutex);
}
void eat(int i) {
down(&mutex);
state[i] = EATING;
up(&mutex);
}
// 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行
void check(i) {
if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
state[i] = EATING;
up(&s[i]);
}
}
为每个哲学家设置一个信号量，用数组装填，再设置一个互斥量，互斥的访问状态数组state[i]
4.2 读者-写者问题
允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。
typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;
void reader() {
while(TRUE) {
down(&count_mutex);
count++;
if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
up(&count_mutex);
read();
down(&count_mutex);
count--;
if(count == 0) up(&data_mutex);
up(&count_mutex);
}
}
void writer() {
while(TRUE) {
down(&data_mutex);
write();
up(&data_mutex);
}
}
5. 进程的调度算法
5.1 批处理系统
批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。
1 先来先服务 first-come first-serverd（FCFS）
非抢占式的调度算法，按照请求的顺序进行调度。
有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。
2 短作业优先 shortest job first（SJF）
非抢占式的调度算法，按估计运行时间最短的顺序进行调度。
长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
5.2 交互式系统
交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。
1 时间片轮转
将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
时间片轮转算法的效率和时间片的大小有很大关系：
- 因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
- 而如果时间片过长，那么实时性就不能得到保证。
2 优先级调度
为每个进程分配一个优先级，按优先级进行调度。
为了防止低优先级的进程永远等不到调度（饥饿现象），可以随着时间的推移增加等待进程的优先级。
3 多级反馈队列
一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。
多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。
每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。
5.3 实时系统
实时系统要求一个请求在一个确定时间内得到响应。