2.1 进程与线程

2.1.1 进程的概念与特征

1. 概念：
   1. 程序是一段指令的集合，而在多道批处理机上，为了让程序并发的、独立的运行起来，在内存中就将程序整合为一个特定的数据结构：
      1. PCB：进程控制块，用于描述进程的基本情况和运行状态，进而控制和管理进程；PCB是进程存在的唯一标志；（与进程管理相关的数据均存放在此中）
      2. 相关数据段：程序运行所需的或者产生的相关数据，并发执行程序时需要将这些数据不停地保存又恢复
      3. 程序段：执行的程序可能只是外存中存储程序的一部分，独立运行程序时可直接执行执行指令子集

以上三个部分构成进程映像（进程实体）

1. 进程就是进程实体的运行过程，是系统进行资源分配和调度的独立单位
   1. 进程的特征：
2. 
   1. 进程的组织
3. 系统中的PCB几百上千个，进程的组织要解决的问题是多个进程之间的组织方式，即通过何种方式寻找到不同状态的PCB
4. 

   2.1.2 进程的状态与转换

1. 进程的五种状态
   1. 运行态：占有CPU及其他资源，程序实际被处理机接收并运行的状态
   2. 就绪态：占有其他资源，等待CPU空闲的进程状态
   3. 阻塞态：进程在运行过程中被某个事件中断，不再占用CPU和资源，如系统调用或者等待事件
   4. 创建态：创建进程，分配资源并初始化PCB
   5. 结束态：撤销进程，回收资源和PCB

2. 进程的状态切换

   1. 
   2. 运行态到阻塞态，通过系统调用或自身请求，是一种主动行为；而阻塞态向就绪态，是一种被动的等待行为
   3. 阻塞态只能经过就绪态被重新调度后才能进入运行态；就绪态也不能不经过自身主动的中断行为，跳过运行态进入阻塞态；即这里的箭头方向不可逆

      2.1.3 进程控制

3. 基本概念：进程控制即是要实现进程的状态转换，一般用原语来执行这些操作

4. 相关原语：
   1. 创建原语：
      1. 分配唯一进程标识号，并申请PCB（PCB有限）
      2. 分配资源，若资源不足就转为阻塞态，等待资源分配
      3. 初始化PCB，包括标志信息，处理机状态，控制信息等等
      4. 插入就绪队列
   2. 撤销原语
      1. 终止进程，并将资源还给父进程或者操作系统
   3. 阻塞与唤醒原语
      1. block状态：自我调用事件发生后，保护现场至PCB中，插入到相关事件的等待队列中
      2. wakeup状态：唤醒事件发生后，在该事件的等待队列中找到相应进程的PCB，插入到就绪队列中
      3. 两原语作用相反，需要成对出现

5. 进程切换：从一个进程切换到另一个进程，任何进程操作与内核都紧密联系

   1. 进程切换与进程调度：一个是进程与进程之间的切换的过程，一个是系统为一个进程分配CPU的过程，后者的出现应当更早；即进程调度发生后，如果CPU此时正在运行某进程，这时就出现进程的切换

      2.1.4 进程的通信

6. 高级通信方式：

   1. 共享存储
      1. 访问必须互斥，操作系统只提供P、V操作和共享空间
      2. 分类：
         1. 低级通信：基于数据结构；数据内容限制大，吞吐量小
         2. 高级通信：基于存储区；数据类型自由，交换速度快
   2. 管道通信
      1. 半双工通信，同一时间只能一个方向；要全双工需要两根管道
      2. 一般缓冲区为4KB，写完才能读，读空才能写，互斥访问
      3. 写进程可以有多个，读进程只能有一个，读完就内容就消失
   3. 消息传递
      1. 以格式化的message传递信息，不需要共享空间，依靠发送和接受两个原语实现传递
      2. 分类：
         1. 直接通信：发送至另一进程的消息缓冲队列上
         2. 间接通信：发送到中间实体中（信箱），另一进程在信箱中取走

7. 低级通信方式：PV操作原语

   2.1.5 线程和多线程模型

   2.1.5.1 线程的概念

8. 线程的基本概念：进程是为了更好的实现多程序的并发，而线程更进一步，在进程中又细分为多个线程，提高了并发性

9. 线程的特点与属性：

   1. 线程是独立调度的基本单位，是处理机的分配单元；进程只是资源分配的基本单位
   2. 线程不拥有系统资源，但可以使用进程所拥有的所有资源
   3. 多CPU计算机中，不同的线程甚至能在不同的CPU中运行；不同线程的通信甚至不需要系统的参与
   4. 同进程中线程的切换不会引起进程切换，时空代价很小；而不同进程中的线程切换需要进程切换实现
   5. 通过进程就可以实现所有功能，例如多个相同程序的并发，进程切换可以实现，但是时空代价很大，而引入线程后，就可以在一个进程中通过创建不同的线程实现此功能，切换线程时空代价小；这种轻量化，精细化的操控方式很常见

      2.1.5.2 线程模型

10. 线程的实现方式

    1. 用户级线程：
    2. 内核级线程：
    3. 组合方式：
11. 多线程模型：组合方式引申出不同的线程模型
    1. 多对一
    2. 一对多
    3. 多对多

2.2 处理机调度

2.2.1 调度的概念与层次

1. 调度：系统中进程的数量远远多于处理机的个数，而要实现并发操作就需要一定的调度能力；即在源有限的情况下，如何按照一定的算法让处理机为进程分配工作，即为调度

2. 调度的三个层次：

   1. 高级调度：即作业调度；决定将外存中的哪个作业调入内存，并建立相应的进程，一个作业只会被调入、调出一次
   2. 中级调度：即内存调度；决定将哪个处于挂起态的进程重新调入内存，一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高
      1. 挂起与七状态模型：
         1. 挂起：将暂时用不到的进程重新调回外存中，以提高内存利用率和吞吐量；挂起时PCB仍然在内存中用以管理、监控进程；进程被挂起后，其PCB会被排在挂起队列中等待被激活
         2. 七状态模型：
            1. 将挂起态细分为“就绪挂起”和“阻塞挂起”
            2. 内存不足时，就将处于就绪态的，阻塞态的进程挂起，或者创建完成就挂起，运行完成就挂起等等
            3. 挂起队列等待激活重新进入内存，不同阻塞原因的阻塞挂起队列用以实现多级反馈队列
            4. 
   3. 低级调度：即进程调度；决定将就绪队列中的哪个进程分配到处理机上，频率很高
   4. 三者关系：

      2.2.2 进程调度的时机、切换与过程

3. 时机

   1. 

      1. I/O操作优先于CPU计算操作，原因有二：I/O操作一般比较急迫，如果不及时输入或者输出，保存在寄存器中的值可能会丢失；其次，具有通道的计算机在工作时与CPU可以并行的工作，当一个I/O操作较多的进程在运行时发出I/O操作请求，CPU在处理完I/O中断后，可能就会调度到其他进程，而由通道并行的完成I/O操作

      2. 当进程中出现系统调用时，进程并没有被切换，PCB并没有被更改，进程只是由用户态转变为内核态，在系统调用完成后回到用户态，这时系统会主动执行进程调度程序，若有优先级更高的进程则将会被调换

   2. 调度方式

      1. 剥夺
      2. 非剥夺

4. 切换与过程

   1. 

      2.2.3 进程调度的评价指标

5. 

   2.2.4 经典调度算法

6. 旧的批处理机上调度算法

   1. 先来先服务（FCFS）：
   2. 短作业优先（SJF）：
      1. 非抢占式：最短进程优先（SPF）
      2. 抢占式：最短剩余时间优先（SRTN）
      3. 
   3. 高响应比优先：
7. 交互式系统的调度算法
   1. 时间片轮转
   2. 优先级调度
   3. 多级反馈队列调度算法

2.3 进程同步

2.3.1 基本概念

临界资源：共享但互斥的资源叫做临界资源；打印机，缓冲区，全局变量，可以与其他进程共享，但是不可以不上锁使用，因此是临界资源；而私有数据，不共享；磁盘，纯程序段（可重入代码）共享但不上锁；这些都不是临界资源

2.3.2 实现临界区互斥的方法

2.3.2.1 软件实现方法

1. 
2. 
3. 

4. 

   2.3.2.2 硬件实现方法

5. 

6. 
7. 

   2.3.3 信号量

   
   只要用while来检查进程，防止访问临界区的，都不满足“让权等待”，因为while会一直占用CPU，检查状态是否满足要求；真正的让权等待是，如果此时进程无法被满足，应当被阻塞，不再占用CPU
   
   S设成0，如果先P就会被阻塞，所以需要执行一次V操作使S变成1，这样P才能执行，因此就实现了先V后P的同步操作；
   S设成1，代表该资源只有1个，用P-V操作夹起来，就可以保证上锁加解锁，即互斥过程的实现

2.3.4 经典同步、互斥问题

写的时候不能读，不能写：写操作的时候，P了，rw变成0，当有读操作时（一定是第一个读操作，count==0），也会申请P操作，此时读操作被阻断，直到写操作完成后V了才能继续读里面的P
读的时候可以读，不能写：读操作的时候，第一个读操作会让rw变成0，count++，接下来的读操作都会绕过判断语句直接去读，而写操作被阻断

2.3.5 管程

1. 概念：实现共享或者互斥功能的特殊软件模块，可看做java中的class —— 定义了一个类，并在其中设定了共享数据结构，和一些函数，只有这些规定的函数才能对class做出修改

2. 特点：

   1. 一次只允许一个进程进入管程，这是由编译器决定的，它跑不了那么多程序，也就是说它自身功能的限制实现了互斥这一目标
   2. 定义了monitor后，只需要调用其中的函数就可以简便的实现共享数据的互斥同步操作，封装思想的运用可以简化编程

      条件变量和信号量之间的区别：

      1. 条件变量是管程中的概念，指的是当该变量被满足时就阻塞；信号量一般指的P/V操作，对记录型信号量进行+1/-1，当P为0时就阻塞；
      2. 从上可以看出，管程中的wait( )操作是在条件变量被满足时，只执行阻塞操作
      3. 而P/V操作不仅执行信号量的加减，还同时完成阻塞操作；信号量的值反映了资源数和等待数
      4. 管程中的剩余资源数用共享数据结构表示

3. 实例

   1. 

2.4 死锁

2.4.1 死锁的基本概念

1. 概念：互相争夺对方手中的资源，导致各进程都发生了阻塞，无法推进

   1. 死锁一定发生在两个及以上的进程之间，此时进程一定处于阻塞态
   2. 饥饿可能只发生在一个进程中，比如就绪态的长进程在最短优先算法中一直等待，或者读者写者模型中写操作由于读操作而一直被阻塞
   3. 死循环一般就是一个进程，它一般来说是一种错误，不归操作系统管

2. 死锁的四个条件：

   1. 互斥条件：互斥访问的资源才会需要各进程之间互相争抢，而互相都抢不到才会死锁阻塞
   2. 不可剥夺条件：不能强行夺走，只能自己释放
   3. 请求和保持条件：进程得到至少一个资源后，仍然请求新的资源，而又保持现有资源
   4. 循环等待：循环等待链，一个进程要的资源被下一个进程所持有

      1. 发生循环等待时不一定发生死锁，发生死锁时一定发生循环等待
      2. 成环+资源数等于1=>死锁

3. 死锁发生的一些情况

   1. 系统资源的竞争
   2. 进程推进顺序不合法
   3. 信号量使用不当

      2.4.2 死锁的处理策略

      2.4.2.1 死锁预防

4. 破坏互斥条件：将互斥的资源改造为共享使用的

   1. 缺点：并不是所有的资源都可以改造成可共享使用的资源，互斥在某些场景下是必要的
5. 破坏不剥夺条件：当某个进程资源请求得不到满足时，立即主动释放保持的所有资源（自我放弃算法）；或者当某个进程需要某种资源时强行剥夺其他进程的占用（剥夺调度算法）
   1. 缺点：实现起来比较复杂；释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。反复地申请和释放资源会增加系统开销，降低系统吞吐量。若一直自我放弃可能导致进程饥饿。
6. 破坏请求和保持条件：进程在运行前一次申请完它所需要的全部资源
   1. 缺点：有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也有可能导致某些进程饥饿。

7. 破坏循环等待条件：可采用顺序资源分配法，规定每个进程必须按编号递增的顺序请求资源

   1. 缺点：不方便增加新的设备，因为可能需要重新分配所有的编号；进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；必须按规定次序申请资源，用户编程麻烦。

      2.4.2.2 死锁避免

8. 系统安全状态：能找到一种不会死锁的进程排序（安全序列）的状态就是安全状态；如果找不出安全序列就是不安全状态；安全状态下，一定不会死锁；不安全状态下，可能会死锁

9. 银行家算法：Max - Allocate = Need ；Available + Allocate = Available ；

   2.4.2.3 死锁检测与解除

10. 资源分配图和死锁定理：

    1. 找到不阻塞且非孤点的进程Pi，释放相关资源
    2. 释放资源即去掉边，如果消去所有边，则不会死锁
11. 死锁解除
    1. 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
    2. 撤销进程法（或称终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
    3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

       杰杰专用
       愿逐月华流照君