进程与线程

进程是操作系统进行资源分配与调度的基本单位。

进程的特征

• 动态性 -- 进程有明确的生命周期，执行状态存在变化
• 并发性 -- 多个进程可以在内存中存在于内存并在CPU中并发
• 独立性 -- 作为申请系统资源的独立单元存在
• 异步性 -- 进程间相互制约，申请CPU资源是先后进行的。这导致了实际执行的结果可能不可复现

并行的效率

Amdahl’s Law与 Gustafson’s Law 讨论了并行计算能提升多大的计算效率

Amdahl's Law

Amdahl's Law 讨论在等量任务的条件下，并行计算带来的计算效率优化上线。

假设一个程序中可并行部分的比例为 $p$, 可以 $N$ 路并行， 那么整体加速比为

$$S_N = \frac{1}{(1-p)+\frac{p}{N}}$$

Amdahl's law 指出了并行优化的效率上限 -- 串行部分的比例。当 $N\to \infty$ 时，加速比最大值为

$$S_\infty = \frac{1}{1-p}$$

Gustafson’s Law

Gustafson’s Law讨论在相等时间的情况下，并行计算得带来的计算任务量的效率优化上限。

假设一个程序的可并行部分为$p$. 则相同时间下并行的任务量（加速比）为

$$S_N = 1-p + Np = (N-1)p+1$$

这说明通过增加并行资源，能通过扩大并行任务规模并使并行部分占主导。

进程的构成

进程实体由三部分构成：

• 进程控制块(PCB)
• 程序段
• 相关数据段

进程控制块 (PCB)

PCB是进程存在的唯一标志，在进程的整个生命周期内，OS均依赖PCB进行进程管理。

PCB包含四类信息:

• 进程标志信息: 包含用户ID(UID)、进程ID(PID)与父进程ID(PPID), 作为进程标志编号；用户ID能标注进程所属用户，以提供资源与安全的保护
• 进程调度信息: 包含进程当前状态，进程优先级，CPU占用时间等进度相关调度信息
• 资源与内存信息: 包含进程内所使用的内存信息，包含代码指针、数据指针、堆栈指针、IO清单与文件描述符
• 处理机状态信息: 也称为CPU上下文， 包含物理寄存器状态参数，如通用寄存器值(PC)、程序计数器值、程序状态字(PSW)、 栈指针(SP)

进程的PCB是用户不透明的，我们能通过shell访问相应进程的PCB。

# Linux
cat /proc/[pid]         # 进程 PCB
cat /proc/[pid]/status  # 进程 PCB中的状态特征

# MacOS

ps -l -p [pid]          # 与 cat /proc/[pid]/status 一致

对于不同OS，父进程中断对子进程的影响都不同。Linux系统对父进程中断并不会中断子进程的执行，而是由init(PID=1)进程收养并正常运行。

PCB中的处理机状态信息与指令的相应状态信息相对应。当进程指令进入CPU时间片处理时，对应寄存器从内存中读取PCB处理机信息。

程序段

程序段是CPU可执行的代码部分，是代码的纯二进制指令部分。静态的二进制指令可以被多个进程共享。

程序段包含

• .init -- 主程序启动前的隐代码准备
• .text -- 程序的可执行部分
• .rodata -- 只读数据存储

数据段

数据段包含进程运行所需的数据，包含.data、.bss与堆、栈

.data用于放置已初始化的静态变量、.bss用于放置未初始化的静态变量

Tip: 关于变量存储的空间

int a = 1; // 在.data 数据段中
int b[10]; // 在.bss 数据段中

void main(){
    static int List[10]; // 函数中静态变量声明在.data数据段中
    int c = 1; // 在被调用的函数中声明的变量直接在栈中生成
    int *p_arr = (int*)malloc(10*sizeof(int)) // 被调用函数中声明动态申请空间时，变量生成在堆中

}

共享库的存储映射区

依赖库的加载，比如一些动态库.so/.dll

静态库通常加载到.text中

进程的生命周期

进程的生命周期分为

• 创建态
• 就绪态
• 运行态
• 阻塞态
• 终止态

满足图

创建态 -> 就绪态  <-> 运行态 -> 终止态
            |          |
            <------  阻塞态

进程的创建

在创建态下，OS通过创建原语建立新进程。

• 分配唯一标识并创建空白PCB
• 分配新进程所需的资源，如内存、文件、IO等，存入PCB
• 初始化PCB
• 插入就绪队列中

终端登录、作业调度系统启动任务、用户程序请求、系统提供服务等事件都会创建新的进程。

进程的终止

分为正常结束、异常结束与外界干预

• 正常结束 -- 进程完成任务后退出
• 异常结束 -- 异常或者中断导致退出
• 外界干预 -- 人工退出、系统资源不足或者安全原因导致退出

终止进程的流程

• 检索PCB并读取当前状态
• 剥夺CPU并调度下一个进程
• 释放相关的系统资源，归还给OS
• 根据系统设计中断相关子进程
• 清除并释放PCB

进程的阻塞与唤醒

进程因为外部事件无法进行时会主动调用阻塞原语(Block), 将进程从运行态转变为阻塞态。

阻塞原语与中断实现的逻辑相似。阻塞原语的实现过程

• 保存CPU现场(PC/状态寄存器)到PCB
• 修改PCB状态字段为阻塞态并放入等待队列
• 调度就绪队列的进程运行

阻塞进程的事件结束后，需要内核的中断处理程序或者合作进程调用**唤醒原语(Wakeup)**进行进程的唤醒

• 在等待队列找到对应PCB
• 移除队列并修改PCB中的状态字，此时从阻塞态转变为就绪态
• 将PCB插入就绪队列，并等待CPU资源执行

进程的通信

进程是独立的单元，进程间的通信通常需要申请内存区域搭建通信的介质进行信息交换。

根据通信效率与量的不同可以分为:

• 低级通信 -- 控制信息的传输
• 高级通信 -- 高效传输大量信息

高级通信面对大量的数据与地址的传递

• 共享传递 -- 划出独立的内存空间，使多个进程都能读写这个共享的空间以实现通信。 引入同步互斥机制规避同时读写共享空间的导致的数据不一致的问题

• 消息传递 -- 封装格式化的信息进行传递，格式化信息由内核实现，面向用户透明。分为直接通信方式与间接通信方式。直接通信方式是将格式化信息通过发送原语与接收原语到指定进程；间接通信方式通过维护一个信箱实体进行间接通信

• 管道通信
  维护一个固定大小的内存缓存区进行通信，管道是单向的。管道满足:

  • 互斥性: 同一时刻只有写端或者读端一个进程访问管道，以避免并发造成数据混乱
  • 同步性: 管道慢自动阻塞，读端释放后继续写入
  • 写端关闭检测后读端自动返回空

• 信号用于通知进程事件发生的情况，通过一个向量维护待处理的信号，一个向量维护被阻塞的信号。信号的来源分为:

  • 内核: 如SIGKILL(kill -9)
  • 进程：其他进程或者自身发送信号

仅当OS从内核态回到用户态的时候才会处理待处理的信号。处理信号的方式

• 执行系统默认的信号处理 -- 比如遇到SIGKILL杀死进程
• 执行用户自定义的信号处理程序 -- 相关定义函数的执行

线程

线程是程序执行流的最小单位，也是处理器调度的基本单位。

在单个进程中有多个执行线程。一个线程不拥有独立的系统资源，比如地址空间，但是运行基本的线程私有数据，比如线程ID、PC、寄存器组和栈寄存器(这些是指令执行的基本单位，线程独立执行一些指令组，因此拥有这些物理元件的数据独立性)。线程的控制块TCB用于记录线程的执行上下文(即对应物理元件的备份值，如PC值，栈指针等)

统一进程中的多个线程也能并发执行相同的程序代码。常见的，比如uWSGI创建的多线程后端服务，能访问同一个后端代码库。也能同时共享进程的资源与内存信息。

线程间的CPU调用与生命周期是独立的。多CPU系统的线程可以在不同的CPU核心上运行

线程间的调度的开销小于进程间的调度。

线程控制块(TCB)

TCB 包含

• 线程标志符(ID)
• 寄存器集合
• 线程状态
• 调度优先级
• 线程私有数据的局部存储区
• 线程的私有堆栈的指针

线程的实现

线程分为用户级线程(ULT)与内核态线程(KLT)，基于这两种线程存在多种进程实现方式。

• 用户级线程模式 -- 只由用户级线程执行线程，任务只需要库函数进行。这样的OS称为纯微内核系统，用户态线程只通过系统调用的方式执行一些内核操作(比如IO)
• 内核级线程模式 -- 指系统内核支持用户级与内核级线程。但是线程的用户态/内核态转换面临系统开销

组合方式分为多对一模式、一对一模式与多对多模式

一对一模式与内核级线程模式是一个模式的两个名字

多对一模式是指始终只有一个线程能从用户态切换至内核态，实现并发的内核态运行。多对一模式并不能完成多内核/多CPU多线程并行

多对多模式是能将实现多对多的内核态切换，同时避免一对一模型的全切换开销过大的问题。

线程库是用户态线程的管理方式，程序员通过线程库的库函数(API)进行线程的创建与生命周期的管理。同时，高级语言能通过线程池进行多用户线程的管理，例如SQLite的ThreadPoolExecutor

CPU调度

CPU调度是指当进程数远大于CPU核心数时，如何分配CPU资源以实现进程的高效、公平的运行，从而实现进程的高并发。

调度的层次

调度自外向内分为三个层次

• 高级调度(作业调度) -- 高级调度负责将作业从外存中提取进内存，分配内存/IO等资源，并创建相应的PCB。整个作业调度周期内高级调度只发生一次。
• 中级调度(内存调度) -- 中级调度是为了提高内存利用率，当内存紧张时，将阻塞态或者就绪态持续较长的进程挂起并放入外存；当系统资源支持对应进程继续运行时，中级调度将进程移回内存。
• 低级调度(进程调度) -- 低级调度按照规则给进程分配CPU资源。

进程调度的任务包括

• 保存CPU现场信息(如PC,PSM), 以确保上一个进程能断点运行
• 选取就绪的待运行进程，将进程PCB从就绪态改为运行态
• 移交CPU控制权，恢复断点，分配CPU

调度的实现

进程调度通过调度器实现，调度器分为排队器、分派器与上下文切换器。

• 排队器 -- 进程就绪态的排队序列
• 分派器 -- 根据调度算法选定进程进行CPU资源分配，并触发上下文的切换
• 上下文切换器 -- 进行当前CPU运行的进程的上下文切换写入PCB，再将分派进程的上下文写入CPU的相应寄存器中

上下文切换

上下文切换是进程调度的核心占用步骤，因为PCB就是进程的信息载体本身。上下文切换分为上一个进程PCB的保存与下一个进程PCB的恢复与写入CPU寄存器，完整流程为

• 挂起当前进程，将CPU上下文写入PCB
• 将当前进程的PCB放入就绪队列或者阻塞队列中
• 选择另外一个进程，更新相关PCB信息(从就绪态改为运行态)
• 将PCB的运行信息恢复进CPU
• 分配CPU资源，跳转到PC地址并执行

上下文切换涉及复杂的访存与指令的执行，时间与资源的开销都较大。

上下文切换是发生在进程间的，而模式切换是发生在进程或者线程内的状态变化。上下文切换只能由内核执行，因此当前进程切换必须为内核态。

调度的时机

进行进程调度的时刻有

• 创建新进程时，父进程与子进程都进入就绪态，调度器选择父进程/子进程分配CPU资源
• 进程正常结束或者终止的时候。如果没有就绪进程就挂起一个闲逛进程(PID=0,优先度最低)、
• 进程进入阻塞态时，为了提高CPU利用率，会进行进程调度
• IO就绪时，将阻塞态进程切换为就绪态进程

不能进行进程切换的场景(关中断状态)

• 处理中断的过程。
• 执行原子操作的情况，此时系统会进行屏蔽中断操作。

调度的方式

• 非抢占调度方式: 面对更加紧迫的或者优先级更高的进程，只有当前进程执行后才会进行调度
• 抢占调度方式: 出现优先级更高的进程进入就绪态，当前进程的CPU资源直接被剥夺，给新进程分配CPU资源

调度的目标

调度的目标是提高CPU的利用率，进程的调度目的是尽可能提高CPU的利用率。CPU利用率的计算公式为

$$\text{CPU利用率} = \frac{\text{CPU有效工作时间}}{\text{CPU有效工作时间}+\text{CPU空闲等待时间}}$$

系统吞吐量用于衡量系统的执行单个作业的平均速度。长作业通常占用CPU的时间，降低系统的吞吐量。

周转时间指作业从提交到完成的整个生命周期所消耗的时间，包括等待、就绪态排队、阻塞态等待IO以及实际CPU的执行时间。对于$n$个作业的平均周转时间为均值

调度算法

先来先服务(FCFS)算法

FCFS算法中的进程队列满足FIFO，即先来先执行，晚到晚执行的策略，属于非抢占式的算法。FCFS是公平算法但是对短进程不友好，效率较低；同时FCFS遇到高频IO的进程无法快速释放CPU资源，效率更低。

短作业优先(SJF)算法 / 短进程优先(SPF)算法

短作业优先算法会进行队列中的作业用时预测，将最短用时的作业分配CPU资源。

预测算法是简单的预测时间加权。对于上一次实际用时 $t_n$ 与预测用时 $\tau_n$, 以及预测因子 $\alpha$, 本轮的预测用时为

$$\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$$

SJF对于长作业不利，如果短作业频繁创建，长作业会始终得不到CPU资源而产生饥饿现象(调度策略使某一进程出现无限期等待)；同时SJF只考虑了作业长度作为优先级而没考虑进程的优先级，无法保证紧迫作业及时处理。

高响应比优先调度算法

基于响应比评估作业的整体优先级，综合考虑了作业的时效性与等候时间

$$\text{响应比} = \frac{\text{等待时间}+\text{估计运行时间}}{\text{估计运行时间}}$$

优先级调度算法

根据系统优先级进行作业的调度

优先级调度算法根据是否能在进程期间抢占CPU资源分为

• 抢占式优先调度算法
• 非抢占式优先调度算法

通常 系统进程 > 用户进程， 交互性进程 > 非交互性进程， IO进程 > 计算进程(IO设备的传输与处理优先级高，相关的数据信息无法暂存，处理速度也慢于CPU)

根据进程优先级是否可变可以分为静态优先级与动态优先级。其中静态优先级指进程优先级在创建时就固定不可变，调度简单但是有可能出现饥饿现象；动态优先级可以根据等待时间或者进程属性进行动态的改变。

时间片轮转(RR)算法

时间片一个执行窗口，如果进程执行时间长于时间片，就将进程CPU资源释放给下一个进程，并放入就绪队列。时间片轮转能保证进程的公平性，不会遇到饥饿现象，但是面临性能开销较大的问题。

当进程结束但是时间片未结束，此时也触发时间片的轮转，为下一个几次呢分配CPU资源

多级队列调度算法

将就绪进程分为多个不同优先级、不同或相同调度算法的进程队列，进行进程的调度与执行。潜在的问题为高级队列进程频繁创建的场景下，低等级队列的进程饥饿

多级反馈队列调度算法

相比多级队列调度算法， 多级反馈队列调度算法打通了不同优先级队列的通道。多级反馈队列的通常基于递增时间片的进程队列实现，通常越低级、越底层的队列的时间片越长，越接近FCFS。

新到达的进程通常先进入最高优先级队列。若进程在当前队列的时间片内未执行完，则被剥夺 CPU，并被移动到下一较低优先级队列的队尾继续等待；若进程已经处于最低优先级队列，则被剥夺 CPU 后通常回到该最低级队列队尾等待。、、

多处理机调度

多处理器系统分为非对称多处理器(AMP)和对称多处理器(SMP)。AMP有一个独立主CPU进行全部调度与决策，从CPU只执行任务；SMP的CPU是平等执行与调度进程的，调度程序可以将任意就绪进程分配给不同的CPU

在多核CPU/多CPU系统中，某个进程在CPU1运行，调度到CPU2时，相应的寄存器与Cache都要进行移动。因此系统应尽量使进程在单个CPU中调度，称为处理器亲和性

CPU多核性能平均化称为 性能均衡，因此需要进行CPU间的进程调度实现多核平均化。从这个角度看，处理器亲和性与性能均衡是相对矛盾的，性能均衡会抵消处理器亲和性的性能优化。

面向多处理机的调度方式可以分为公有队列调度与私有队列调度

• 公共就绪队列调度 -- 所有CPU共享一个进程队列，CPU的性能均衡但是处理器亲和性较差
• 私有就绪队列调度 -- 调度器控制私有队列进程，当CPU空闲时调用私有队列进程执行。CPU的处理器亲和性高但是性能不均衡

处理器的亲和性的提升方法分为软亲和与硬亲和。软亲和指调度器进行进程软绑定在某个CPU上，尽量向这个CPU调度；硬亲和指用户进程通过系统调度主动请求系统绑定在某个CPU上。

协程

协程是语言实现的，可以在线程内部执行、中断并恢复的程序控制结构，通过yield()自主管理CPU的调用，其性能开销小于线程的切换