进程

1. 定义：是一个程序及其数据在处理机上执行时所发生的活动。
2. 程序与进程的区别：程序是一组有序指令的集合，是静态的。而进程是动态的，由创建而产生，由调度而执行，由撤销而消亡。进程具有并发性，可并发执行。进程具备独立性，是接受资源和接受调度的基本单位（是资源分配的最小单位，而调度的最小单位是线程）。进程具有异步性，即按各自独立和不可预知的速度向前推进。

进程的三种基本状态：

1. 就绪：已获取除cpu执行权以外的所有资源，只要获得cpu执行权，便可立即执行。就绪线程通常放到一个就绪队列中。
2. 执行：获取cpu执行权，处于执行状态中。
3. 阻塞：当进程执行被打断时，处理器会发起调度，把执行权给予其他就绪进程，而当前进程进入阻塞状态。阻塞状态的进程，会被放进系统的阻塞队列中，等待被唤醒。导致阻塞的几种情况。
   1. 向系统请求共享资源失败。
   2. 等待某种操作完成。发起IO-》阻塞-》需等IO任务执行完成-》中断处理程序唤醒-》就绪
   3. 等待新任务到达。

进程的挂起与唤醒：当系统资源不足的时候，会去挂起就绪或堵塞进程，把它们放入外存以释放内存资源。同时执行挂起原语suspend能主动挂起进程。就绪进程挂起变为静态就绪状态，阻塞进程挂起变为静态阻塞状态，执行中的进程被挂起进入静态就绪状态。当静态就绪状态被激活，加载到内存中，就恢复到活动就绪状态。静态阻塞被激活醒就变为活动阻塞。

状态转换如下图：

进程状态转换.png

阻塞与唤醒过程：

进程阻塞唤醒过程.png

挂起与激活过程：

进程挂起激活过程.png

进程控制块PCB

pcb的作用

1. 作为进程实体的一部分，记录了操作系统所需的，用于描述进程当前情况及管理进程运行的全部信息，是操作系统中最中最重要的记录型数据结构。
2. 能实现间断性运行方式，能保存运行的上下文，用于下次执行。
3. 提供进程管理所需的信息。记录了程序和数据在内存或外存中的地址指针。
4. 提供进程调度所需的信息，进程优先级、所处状态等。
5. 实现与其他进程同步与通信。如果使用信号量，进程中必须都设置相应的用于同步的信号量。关于通信，pcb中有用于实现进程通信的区域或通信队列指针等。

pcb中的信息

1. 进程唯一标识符，外部标识符（用户调用）和内部标识符（系统调用）。
2. 处理机状态，也称处理机上下文。主要由处理机的各种寄存器中的内容组成的。寄存器类型包括：1.通用寄存器，用于暂存信息。2.指令计数器，存放下一条指令的地址。3.程序状态字PSW，包含状态信息（条件码、执行方式、中断屏蔽标志）。4.用户栈指针，指向的栈中，存放调用参数和调用地址。

当进程被切换时，处理机信息都必须保存在pcb中，当再次运行的时候，能从原状态恢复。同时，如果进程频繁切换，带来的时空开销是很大的。

进程同步

临界资源：一次只允许一个进程使用的资源。例如一些硬件资源，打印机、磁带机等。进程间应采用互斥方式，实现对这种资源的共享。

临界区：访问公共资源的代码片段。

原则：

1. 空闲让进：无程序处于临界区时，代表临界资源空闲，允许请求进入的进程访问。
2. 忙则等待：如果临界资源被访问中，请求访问必须等待，实现互斥。
3. 有限等待：保证在有限时间内能进入自己的临界区，避免死等。
4. 让权等待：当进程无法进入临界区时，释放处理机，避免陷入忙等。此原则应该是在有限等待无法实现的情况下执行。

信号量机制

wait(s),signal(s)基本操作，属于原子操作，执行过程不可中断。当s = 1的时候可以实现互斥同步功能。

semaphore mutex = 1;
    ...
    wait(mutex);    
    //临界区
    signal(mutex);
    ...

通过wait，signal能保证临界区同时只能允许一个进程进入。当临界区繁忙时，其他行程访问临界区，执行wait操作会失败，同时进程会进入阻塞。

进程通信

1. 管道系统pipe,接收发送通过共享文件（pipe文件）的方式进行通信。
2. 消息传递系统，send(receiver,message),receive(sender,message)
3. 客户机-服务器系统，通过socket套接字

死锁

死锁：如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程是死锁的。

进程饥饿：进程一直获取不到资源。

可抢占资源：能被其他线程抢占的资源。该类资源的抢占不会导致死锁的产生。如处理机、内存空间等。

不可抢占资源：一旦被分配了，不能强行回收，只能等线程释放。如打印机、刻录机等。

死锁产生的几种情况：

1. 竞争不可抢占资源，导致互相等待对方释放资源。双方都必须拥有对方要访问的资源。不能通过调整代码顺序解决。
2. 竞争可消耗资源（中断信号、系统通知等）。循环等待消息的接受，才执行消息的发送，导致死锁。能通过调整代码的执行顺序解决。大家都想获取到消息资源，而等待的消息资源，只有其他人能发出。由于循环等待，导致消息无法发出。属于可消耗资源的竞争。
3. 程序的推进顺序非法。该情况不属于资源使用，但导致死锁也就是出现互相等待的局面或则循环等待的局面。

死锁产生的条件：

1. 互斥条件：分配的资源，同一时间只能被一个进程访问，直到其释放。
2. 请求和保存条件：请求新的资源，同时保存自己已拥有的某个资源不释放,这个不释放的资源就是别人要获取的资源。
3. 不可抢占条件：访问的资源不可被抢占。这样就无法通过抢占的方式解决阻塞。
4. 循环等待条件：这是出现死锁的一个结果，由于前面的几个条件的同时存在才有可能出现这个循环等待的结果，如果这个结果出现，那么意味着出现死锁。

死锁的处理方法：

1. 预防死锁：通过某些限制条件破坏死锁的四个条件，防止死锁的产生。属于事先预防。
2. 避免死锁：在系统资源动态分配的过程中，通过某种方式，防止进程进入不安全区域，避免死锁的发生。输入事先预防。
3. 检测与解除死锁：使用某些方式检测死锁的产生并解除死锁。可通过撤销进程，终止进程等方式，释放资源。

线程

20世纪60年代OS系统引入进程解决程序并发问题，80年代提出比进程更小的单位线程。90年代出现多核处理机，线程能更好的发挥处理机的性能。线程是为了提高并发性以及进行相互之间合作而创建的。而现在进程更多的是作为线程的容器，程序的并发执行通过线程来实现。

进程与线程的比较：
1.调度角度： 进程过重，是独立运行的基本单位，进程每次调度都需要切换上下文，时空开销大。而线程切换仅仅需要保持和设置少量的寄存器内容，切换代价远低于进程。

2. 资源角度：作为资源调度的基本单位，进程拥有独立资源。而线程本身不拥有系统资源，其仅有一点必不可少的能保证独立运行的资源（TCB、程序计数器、保留局部变量、状态参数、返回地址等一组寄存器和堆栈）。
3. 独立性角度：进程间相对独立，出了通过少量的全局变量实现共享。线程资源允许别的线程共享，同一进程的所有线程共享同一个内存地址空间和进程资源。
4. 稳定性：进程之间除了共享全局变量外，不允许其他进程访问。而线程因为共享同一个进程的内存地址空间和资源，甚至其线程堆栈都能被其他线程读取和清楚。多进程比多线程稳定，但协同能力多线程更强。

线程控制块TCB

包含信息：

1. 线程标识符
2. 线程运行状态（就绪、阻塞、执行）
3. 优先级
4. 堆栈指针（调用过程的局部变量和返回地址）
5. 线程专有存储区，用于保存切换时的线程上下文和一些统计信息。
6. 信号屏蔽，对某些信号加以屏蔽。
7. 一组寄存器，程序计数器寄存器PC、通用寄存器。
   1. 程序计数器寄存器，用于存储下一条程序指令地址。
   2. 通用寄存器，用于存送和暂存数据，也可参与算术逻辑运算并保存结果。
8. 两个指向堆栈的指针，执行自己堆栈的指针和指向核心栈的指针。前者是当线程运行在用户态时使用自己的堆栈来保存局部变量和函数返回地址，后者是线程运行在核心态的时候使用系统核心栈。

线程的实现

内核支持线程

创建、阻塞、撤销和切换都在内核空间实现。

优点：

1. 对多处理器系统来说，内核能调度同一进程中的多个线程实现真正意义的并发执行。
2. 当进程中的一个线程阻塞了，能调度进程中的其他线程执行，甚至能调度其他进程中的线程执行，前提是这个线程必须是核心态。
3. 内核线程具有很小的数据结构和堆栈，切换开销小。

缺点：
用户如果要切换进程中的线程，需要把线程从用户态切换到核心态，因为线程调度由内核控制，系统开销较大。

用户级线程

在用户空间中实现。用户级线程的一切操作对内核都是透明的。但是这种线程就不能实现真正意义的并发，系统调度以进程为单位。如果A进程实现了1个用户级线程，而B进程实现了100个用户级线程，那么A中线程获得的执行时间是B中线程的100倍。而内核支持线程，以线程为调度单位。

组合方式

1. 一对多。用户线程映射到一个核心线程。如果核心线程阻塞了，就无法正常工作。
2. 一对一。核心线程的数据与用户线程的数量一样，一一映射。发送阻塞能调度其他线程，但每个用户线程就对应一个核心线程，导致系统开销大，需要全局限制线程的数量。
3. 多对多。存在多个核心线程用于映射用户线程，避免了系统开销过大，也避免了阻塞导致不能正常工作的问题。集合了1和2的优点。

内核支持线程的实现

创建进程的时候，分配一个PTDA(per task data area),其中包含若干线程控制块TCB空间。当一个新内核线程被创建时，系统会分配TCB和相关资源。线程销毁时资源被回收，但也可以先不回收，等候新的线程被创建时服用其TCB。

用户级线程的实现

在用户空间实现的，线程运行在运行时系统上（runtime system）。线程切换时不需要切换到核心态，切换速度快。申请资源需要通过runtime system间接申请。

内核控制线程：又称lwp（light weight process）。lwp可通过系统调用来获得内核提供的服务，当用户级线程连接到lwp上，就能具有内核支持线程的所有属性（调度方式，按线程调度）。lwp是用户线程与内核线程沟通得桥梁，同时起到用户线程与内核线程的隔离作用。用户线程可能很多，为了节省系统开销，不能设置过多的lwp，通过多路复用的方式实现lwp线程池，如果没有可用lwp那么用户线程进入等待。lwp阻塞可用去连接别的lwp，就算lwp全部阻塞也不妨碍线程执行任务，但不能访问内核了。

优先级倒置

当优先级高的线程访问临界资源，而这个临界资源被优先级低的线程占用。此时就会发生优先级倒置。如果此时存在三个优先级a,b,c,c 为低优先级且占用临界资源，a为高优先级需要访问临界资源，b为中优先级不需要访问临界资源。当a去访问资源的时候，发现无法访问，因为被c占用了，同时又存在b线程，b优先级比c高，系统调度去执行b，b执行完毕后，才有可能执行c，c释放临界资源后a才有可能执行。但如果存在多个如b2,b3,b4，那么a线程执行的时刻就会被大大延长。且a的执行被延长的时间不可预知和无法限定。

解决方案1：如果线程正在访问临界资源，设定为不可被抢占，这样其就能更快的退出临界区。但如果这样，当线程访问临界区时，调度对他是失效的。就算有很多优先级比他高的不需要访问临界资源的线程都没机会执行。如果其临界区很长，那么必然是不能接受和不合理的。

解决方案2：当高优先级线程因为访问临界资源被阻塞时，拥有临界资源的低优先级的线程继承高优先级线程的优先级，直到其退出临界区。这样既能不影响系统的正常调度，比他们更高的优先级的线程依然能执行，同时能避免介于他们中间的优先级的线程插入执行。

相比两个方案，方案二更优。