一 什么是进程（Process）？

进程是一个具有独立功能的程序，关于某个数据集合的一次运行活动

进程是系统进行资源分配和调度的一个独立单位

进程是程序的一次执行

进程是一个程序及其数据在处理机上顺序执行时发生的活动

进程是程序在一个数据集合上运行的过程

进程是系统进行资源分配和调度的一个独立单位（基本单位）

1 进程的结构

• 控制块（PCB）（Process Control Block） 进程唯一标识

• 数据段 存放原始数据和中间数据，程序运行中产生的数据

• 程序段 存放在文本区域，可以多个进程共享

2 进程的特征

动态性 由创建而生，由撤销而亡

并发性 可以多个进程同时运行

独立性 独立资源分配

异步性 相互独立、互不干扰

3 进程与线程（Thread）

进程的轻型实体，也叫“轻量级进程”，是一系列活动按照实现设定好的顺序依次执行的过程，是一系列指令的集合。

是一条执行路径，不能单独存在，必须包含在进程中。

线程是OS中运算调度的最小单位（进程是资源分配，线程是资源调度）

为什么引入线程？

提高OS的并发性，多个线程间可以共享进程的资源，有效减少进程间通信的开销。

3.1 线程的特性：

轻型实体

独立调度和分配的基本单位

可并发执行

共享进程资源

3.2 进程和线程区别：

调度 处理机在线程间切换，不会引发进程切换，线程是最小的调度单位

*拥有资源 线程不拥有资源，所有资源由进程管理

*并发性 线程提高了资源利用率

系统开销 进程创建、切换开销较大，线程创建和切换开销小

地址空间和其他资源 每一个进程都是独立内存空间，线程共享进程的所有地址空间

通信

3.3 线程的实现方式

3.3.1 用户级线程（ULT）User Level Thread

在用户空间被创建，创建、调度、销毁都在用户空间

内核通过进程调度线程，内核感知不到用户级线程

系统调用会导致全部线程阻塞

时间片调度会按照进程分配运算时间片而不是线程数量

优点是线程间切换开销小

缺点是性能差

线程多对一

3.3.2 内核级线程（KLT）Kernel Level Thread 在内核中被创建

在内核级进行创建、管理、调度

优点是性能好

缺点是线程间切换开销大

线程一对一

3.3.3 组合方式

线程多对多

结合二者优点

二 进程是怎样运行的？

1 进程的状态

三种基本状态

• 就绪（Ready）: 当进程获得CPU执行权，就会进入Running状态，这个过程叫做进程调度

• 执行（Running）: 进行IO操作的时候会进入阻塞状态，时间片用完后，会回到Ready状态

• 阻塞（Blocked）: I/O完成后，回到Ready状态

创建和终止状态

• 创建（New）: 由用户或程序发起

• 终止（Terminated）: 标记为终止，回收资源，清理PCB

  • 进程终止的三种情况：正常、异常、外界干预

2 进程控制

即OS对进程实现有效的管理，博爱阔创建新进程、撤销已有进程、挂起、阻塞和唤醒、进程切换等多种操作。OS通过原语（Primitive）操作实现进程控制。

原语：对若干条指令的封装，完成特定的功能，是一种原子操作（Action Operation）

原子操作，要么全部完成，要么全不完成，执行过程不会中断

再内核态下执行，常驻内存

是内核三大支撑功能（中断处理/时钟管理/原语操作）之一

进程控制相关的原语：

• 创建原语：create，在New时执行

• 阻塞原语：block，在I/O的时候执行，对应Blocked状态

• 唤醒原语：wakeup，从Blocked回到Ready时执行

• 撤销原语：destroy，在终止时执行

挂起与激活：

为了系统和用户观察和分析进程

挂起和激活是操作不是状态

挂起后把进程放到外存中（交换内存 swap 虚拟内存）

• 挂起原语：suspend

  • 静止就绪：放外存，不调度

  • 静止阻塞：等待事件

• 激活原语：active

  • 活动就绪：等待调度

  • 活动阻塞：等待唤醒

3 进程调度

又叫处理机调度

更具一定的算法和原则将处理机资源进行重新分配的过程。

前提：作业/进程数远远大于处理机数

目的：提高资源利用率，减少处理机空闲时间

调度程序：要满足快速响应和系统平均周转时间和电镀算法本身的开销

3.1 调度层次

• 高级调度/作业调度

  • 把后背作业从外存调入内存（从磁盘调入RAM）

  • 只调用一次，调出一次（创建和销毁进程）

• 中级调度/内存调度

  • 将进程调入外存，条件符合再调入内存（Suspend/Active）

  • 在内存、外存交换区进行进程对换（可以有多次）

• 低级调度/进程调度

  • 从就绪队列选取进程分配给处理机

  • 最基本的调度，频率非常高（相当于一个时间片完成）

3.2 调度方式

• 剥夺式/抢占式调度

  • 调度时立即停止当前进程

  • 分配处理机给另外一个进程

  • 原则：优先权/短进程优先/时间片原则

• 非剥夺/非抢占式调度

  • 若有进程请求执行

  • 等待直到当前进程完成或阻塞

  • 缺点：适用于批处理系统，不适用于分时/实时系统

3.3 调度时机

• 进程运行完毕

• 进程时间片用完

• 进程请求I/O操作

• 执行某些原语操作

• 高优先级进程申请运行（剥夺式调度）

3.4 调度过程

1. 保存镜像：记录进程现场信息

2. 调度算法：确定分配处理机的原则

3. 进程切换：分配处理机给其他进程

4. 处理机回收：从进程回收处理机

3.5 调度算法指标

• CPU利用率：↑忙碌时间/总时间

• 系统吞吐量：↑完成作业数/总时间

• 周转时间：↓作业时间 - 提交时间

  • 带权周转时间：周转时间/实际运行时间

• 等待时间：↓作业等待处理机调度时间

  • 关注平均值

• 响应时间：↓提交请求到首次响应间隔

3.6 调度算法*

作业和进程调度算法：

• 先来先服务（FCFS，First Come First Served）

  • 算法内容：调度作业/就绪队列中最先入队者，等待操作完成或阻塞

  • 算法原则：按作业/进程到达顺序服务

  • 调度方式：非抢占式调度

  • 适用场景：作业/进程调度

  • 优缺点：

    • 有利于CPU密集型作业，充分利用CPU资源

    • 不利于I/O密集型作业，操作耗时

• 短作业优先（SJF，Shortest Job First）

  • 算法内容：所需服务时间最短的作业/进程优先服务

  • 算法原则：追求最少的平均（带权）周转时间

  • 调度方式：SJF/SPF非抢占式

  • 适用场景：作业/进程调度

  • 优缺点：

    • 平均等待少，周转时间最少

    • 长作业周转时间会增加或饥饿

    • 估计时间不准确，不能保证紧迫任务及时处理

• 高响应比优先调度（HRRN，highest Response Ratio Next）

  • 算法内容：结合FCFS和SJF综合考虑等待时间和服务时间计算响应比，高的优先调度

  • 算法原则：综合考虑作业/进程的等待时间和服务时间

  • 调度方式：非抢占式

  • 适用场景：作业/进程调度

  • 响应比计算：

    • 响应比 = (等待时间 + 服务时间) / 服务时间, ≥ 1

    • 只有当前进程放弃执行权（完成/阻塞）时，重新计算所有进程响应比

    • 长任务等待越久，响应比越高，越容易获得处理机

• 优先级调度（动态调度）（PAS，Priority-Scheduling Algorithm）

  • 算法内容：又叫优先权调度，按照作业/进程的优先级（紧迫程度）进行调度

  • 算法原则：优先级最高的作业/进程先调度

  • 调度方式：抢占/非抢占式

  • 适用场景：作业/进程调度

  • 优先级设置原则：

    • 金泰/动态优先级

    • 系统 > 用户; 交互型 > 非交互型; I/O型 > 计算型

    • 低优先级进程可能会产生饥饿

进程调度算法：

• 时间片轮转调度（RR，Round-Robin）

  • 算法内容：按照先入后出的顺序，轮流分配时间片去执行，时间用完剥夺

  • 算法原则：公平、轮流为每个进程，在一定时间内得到响应

  • 调度方式：抢占式，由时钟中断确定时间到

  • 适用场景：进程调度

  • 优缺点：

    • 公平，响应快，适用于分时系统

    • 时间片决定元素：系统响应时间、系统处理能力、就绪队列大小

    • 时间片太大相当于FCFS，时间片太小切换开销大

• 多级反馈队列调度（MFQ，Multileveled Feedback Queue）

  • 算法内容：设置多个优先级排序的就绪队列，优先级从高到低，时间片从小到大，新进程采用队列降级法

    • 进入第一个队列，按FCFS分时间片

    • 没有执行完，移到第二级，第三级...

  • 算法原则：结合前面所有调度算法的优势，相当于PAS+RR

  • 调度方式：抢占式

  • 适用场景：进程调度

  • 优缺点：

    • 对各类型相对公平；快速响应

    • 终端型作业用户：短作业优先

    • 批处理作业用户：周转时间短

    • 长作业会得到部分执行

    • 长批处理作业用户：在前几个队列部分执行