1. 进程概念

进程是一个具有一定独立能力的程序对某个数据集合上的一次动态执行过程和资源分配过程

2. 进程的状态与转换

  • 运行状态Running
  • 就绪状态Ready
  • 等待/阻塞状态Blocked

image.png

五状态模型

  • 创建
  • 终止

七状态模型

  • 就绪挂起
  • 阻塞挂起

处理机调度

1. 调度的基本概念

作业从进入系统成为后备作业开始，知道运行结束退出系统为止，需经历不同级别的调度

2. 选择调度算法的原则

  1. 资源利用率

image.png

  1. 响应时间

交互式进程从提交一个请求到接受到响应之间的时间间隔。

  1. 周转时间

批处理用户从作业提交给系统开始，到作业完成为止的时间间隔。
平均作业周转时间
image.png
image.png

  1. 吞吐率

单位时间内处理的作业数

  1. 公平性

确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饿死的情况

3. 常见的调度算法

  • 不可抢先方法（非剥夺式）和可抢先式（剥夺式）

    1. 先来先服务算法FCFS

    2. 最短作业优先算法SJF

    3. 最短剩余时间优先算法SRTF

    4. 最高相应比优先算法HRRF

  • 响应比 ＝1+已等待时间/估计运行时间

    5. 时间片轮转算法

    6. 优先级（权）调度算法

    7. 多级反馈队列调度算法

    同步与互斥

    1. 程序顺序执行的特点

  • 执行的顺序性、环境的封闭性、结果的确定性、过程的可再现性

    2. 程序并发执行的特点

  • 失去了程序的封闭性

    3. 并发程序的表示

  • 有向图

image.png

  • 伪码
    1. cobegin
    2.   S1,S2,S3...
    3. coend
    image.png

4. 并发进程常见错误及原因

  1. 与时间有关：结果不唯一和永远等待
    • 一组并发进程执行的相对速度无法相互控制
  2. 对于共享资源的使用过程不封闭

    5. 进程的交往：竞争（互斥）协作

  • 竞争（互斥）
    • 原本不存在逻辑关系的进程因共享资源而产生的交互和制约的问题
    • 两个问题：饥饿与死锁
  • 协作
    • 某些进程为完成同一任务需要分工协作而产生的关系
    • 需要保证同步：这些线程需要基于某个条件来协调他们的活动，在某些位置上排定执行人的先后次序而等待、传递信号或消息所产生的协作制约关系
  • 同步和互斥比较

image.png

6. 临界区管理

并发进程中与共享变量有关的程序段叫“临界区”，共享变量代表的资源叫“临界资源”。

临界区调度原则
  1. 一次至多一个进程能够进入临界区内执行
  2. 如果已有进程在临界区，其他试图进入的线程应等待
  3. 进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入
    实现个进程互斥进入临界区的方式：进入区和退出区
    1. while(1){
    2.  // 进入区代码
    3.  // 临界区代码
    4.  // 退出区代码
    5.  // 其余代码
    6. }
    具体地：可以分为软件PeterSon算法和硬件关中断，硬件指令方法（TS指令、swap指令）

7. 信号量与PV操作

信号量：一种软件资源，除初始化以外，仅能由两个同步原语对其进行操作的整型变量

  • 分类：
    • 二元信号量：取值仅为0、1
    • 一般信号量：信号量取值允许为非负整数，主要用于一般线程间的同步
  • 物理意义

image.png
信号量的变化范围：可用资源数为m，进程数为n，阻塞等待：-(n-m)<=S<=m
PV操作：

  • 原语：内核中执行时不可被中断的过程：P、V

  • 一般信号量

    • 设s为一个记录型数据结构，一个分量为整形量value，另一个为信号量队列queue
    • P(s)：将信号量s减去1，如果结果小于0，则调用P(s)的进程被置成等待信号量s的状态
    • V(s)：将信号量s加上1，如果结果不大于0，则释放一个等待信号量s的进程
      信号量实现互斥
      image.png
      信号量初始值为m，m不是0时代表资源空闲，m为0代表资源繁忙（m小于0时绝对值代表阻塞队列中的进程数量）

  • P、V操作在一个线程中成对使用

    信号量实现同步

  • P、V操作在一个线程中不一定成对使用。

image.png
**

生产者与消费者问题
  • 一个生产者、一个消费者共享一个缓冲区
    • 信号量：可以使用的空缓冲区数量、缓冲区内可以使用的产品数
    • image.png
  • 多个生产者、多个消费车共享多个缓冲区

读者、写者问题

哲学家就餐问题

8. 管程

  • 管程是由过程、变量和数据结构等组成，他们共同构成了一个特殊的模块和软件包
  • 管程中在任一时刻只能有一个活跃进程，这一特殊性可以帮助管程有效地实现互斥
  • 管程与进程的区别
    1. 虽然二者都定义了数据结构，但进程定义的是私有数据结构PCB，而管程定义的是公共数据结构，如条件变量等
    2. 二者都存在对各自数据结构上的操作，但进程是顺序执行的，而管程则是进行同步操作和初始化操作
    3. 进程是为了保证系统并发而设计的，管程则是为了解决共享资源的互斥
    4. 进程通过调用管程中的过程来进行共享数据结构的操作，该过程就表现为进程的子程序，因此进程是主动的，管程是被动的
    5. 进程间可并发，管程作为其子程序不能与其调用者并发
    6. 进程具有动态性和生命周期，而管程只是一个资源管理模块，供进程调用

利用管程解决生产者消费者问题

参考java中阻塞队列的原理，使用Condition来标记线程。

进程通信

  • 进程通信是指进程间的信息交换
  • 实现方法：管道、信箱、缓冲、中断

    死锁

    死锁产生的根本原因：

  1. 进程竞争资源而导致的资源不足

  2. 进程推进的顺序不一致

    死锁产生的四个必要条件

  3. 互斥条件：一个资源一次只能被一个进程所使用

  4. 不可抢占条件：一个线程获得的资源不可以被其他线程抢占
  5. 部分分配条件：每个线程都占有了完全运行所需要的一部分资源，但仍然需要其他的资源
  6. 循环等待条件：在系统中存在一个由若干个进程形成的环形请求链，其中的每个进程均占有若干种资源中的一种，同时需要下一个线程所占用的资源

设系统某类资源有m个，有n个进程，每个进程需要k个资源，则当满足m>n(k-1)时系统不会发生死锁。

处理死锁的基本方法

  • 死锁的预防：破坏四个必要条件
    • 互斥条件：资源可以多进程同时访问
    • 部分分配条件：预先静态资源分配法，一次性给够所有资源
    • 不可抢占条件：采用剥夺式调度方法
    • 循环等待条件：有序资源使用法

image.png

  • 死锁的避免
  • 死锁的检测和恢复

利用银行家算法避免死锁