Skip to main content

进程与线程

概念​

tip

由于多道程序可以并发执行，其具有间断性的特征，因此引入了进程（Process）的概念，方便实现系统的并发性和共享性。

系统利用 进程控制块（Process Control Block，PCB） 描述进程的基本情况和运行状态，进而控制和管理进程，具体的 进程实体 由 程序段、相关数据段和 PCB 构成；创建撤销进程指的就是创建和撤销 PCB。

进程的定义一般有：

  1. 程序的一次执行过程；
  2. 一个程序及其数据在处理机上顺序执行时所发生的活动；
  3. 具有独立功能性的程序在一个数据集合上运行的过程，是系统进行资源分配和调度的独立单位。

特征​

进程由多道程序的并发执行所引出，有如下特征：

  1. 动态性，是程序的一次执行，具有一定的生命周期；
  2. 并发性，多个进程可同时存在于内存，并发运行；
  3. 独立性，作为独立运行、获取资源、接受调度的基本单位；
  4. 异步性，以不可预知的速度推进。

进程的状态与转换​

进程的生命周期内有以下状态：

  1. 运行态，正在处理机上运行；
  2. 就绪态，获取了除了处理机的一切所需资源，一般系统的就绪进程有很多，通常将其排成队列，成为 就绪队列；
  3. 阻塞态，又称等待态，进程正在等待某一事件而暂停运行，如等待资源释放、I/O 等‘
  4. 创建态，正在被创建，如申请 PCB、填写控制信息、分配资源等；
  5. 终止态，正在从系统中退出。

组成​

程序控制块：主要组成部分：

  1. 进程描述信息，有进程标识符（PID）和用户标识符（UID）；
  2. 进程控制和管理信息，有进程当前状态、进程优先级、代码入口地址、程序外存地址、进入内存时间、处理机占用时间和信号量使用；
  3. 资源分配清单，代码段、数据段、堆栈段指针，文件描述符、键盘和鼠标；
  4. 处理机相关信息，通用、地址、控制、标志寄存器值和状态字。

程序段：能被进程调度程序调度到 CPU 执行的程序代码段、可被多个进程共享；

数据段：包括进程对应的原始数据、中间数据或最终结果。

进程控制​

创建​

父进程 可以创建 子进程，后者可以继承前者的所有资源，当子进程被撤销时，需要返还资源；撤销父进程时也会撤销其所有子进程；创建流程为（创建原语）：

  1. 分配唯一的进程标识号，申请空 PCB（PCB 是有限的）；
  2. 分配资源，若不足则处于创建态，等待资源；
  3. 初始化 PCB；
  4. 加入就绪队列；

终止​

三类情况：正常结束、异常结束和外界干预；终止过程为：

  1. 根据标识符检出 PCB、读取进程状态；
  2. 若处于运行状态，则终止执行；
  3. 终止其所有子孙进程；
  4. 释放其所占用资源；
  5. 将 PCB 从所在队列删除；

阻塞和唤醒​

通过阻塞原语（Block）将状态从运行态转为阻塞态，是一种 主动行为，执行过程：

  1. 通过标识符找到 PCB；
  2. 若为运行态则保护现场，转为阻塞态；
  3. 插入相应事件的等待队列；

当被阻塞进程所等待事件出现后，相关进程会调用唤醒原语（Wakeup），流程如下：

  1. 从该时间的等待队列中找到相应进程的 PCB；
  2. 移出等待队列，变为就绪态；
  3. 插入就绪队列、等待调度程序调度。

进程通信​

PV 操作是低级通信方式，高级通信方式是指以 较高效率传输大量数据 的通信方式，主要有三种：

  1. 贡献存储，通信进程间存在一块共享内存（通过同步互斥工具进行访问）实现信息交换；具体可分为基于数据结构的共享和基于存储区的共享；操作系统仅提供存储空间和同步互斥工具，数据交换要由用户实现；
  2. 消息传递，以格式化的消息（Message）为单位，主要有直接和间接两种方式，前者直接将消息发送到目标进程的消息缓冲队列，后者将消息发送到某个实体（一般称为信箱），接收进程从该实体中取得消息；
  3. 管道通信，允许两个进程按照 生产者 - 消费者 模型进行通信，生产者向管道一端写，消费者从管道另一端读，若数据满、写进程会被阻塞；若数据空，读进程会被阻塞；Linux 中管道是一种非常常用的通信机制，缓冲区的大小一般为 4KB。
caution

从管道读数据是一次性操作，数据一旦被读取，就释放空间；管道只允许单向通信。

线程和多线程模型​

tip

引入线程是为了减小程序在并发执行时所付出的时空开销，提供系统的并发性能。

线程可以理解为轻量级进程，是一个基本的 CPU 执行单元，也是程序执行流的最小单元，有线程 ID、程序计数器、寄存器集合和堆栈组成，是进程中的一个实体，是被系统独立调度和分派的基本单位，其本身并不拥有系统资源，其可以与一个进程中的所有线程共享该进程的全部资源；线程同样可以创建撤销另一个线程，也可以并发执行，并且也有就绪、阻塞和运行三态。

进程与线程的比较​

  1. 调度，同一进程的线程切换开销远小于进程开销；
  2. 并发性，同一进程的多个线程同样可以并发执行；
  3. 多处理机系统，同一进程的多个线程可以分配到多个处理机上执行。
  4. 共享，不同进程只可共享全局变量，而同一进程间的线程完全共享进程变量，线程甚至可以读写另一个线程的堆栈；

其余与进程基本类似，如线程控制块（TCB）、线程创建、终止和阻塞等。

线程的实现方式​

分为用户级线程（ULT）和内核级线程（KLT）；

前者对内核 不可见，因此操作系统对进程调度时容易导致不公平，如某进程拥有大量线程，但所分配的时间片和其他进程一致；优点是进程切换不用转换到内核空间、不同进程可以为线程实现调度方法、与操作系统平台无关；缺点是当线程执行系统调用时，进程内的所有线程都被阻塞，不能发挥多处理机的优势，因为每个进程只能分配到一个 CPU；

后者内核可以以线程为单位进行调度，并且阻塞时会切换到其他线程运行；内核支持线程具有很小的数据结构和堆栈、线程切换快；内核本身也可以才用多线程技术；缺点是统一进程的线程切换需要从用户态转为核心态；

两种方式还可以组合实现，内核允许创建内核级线程，也允许用户管理用户级线程。

多线程模型​

对于同时支持内核级和用户级线程的系统，由于用户级线程和内核级线程 连接方式 不同，形成了三种多线程模型：

  1. 多对一：多个用户级线程映射到一个内核级线程，这些用户线程一般属于一个进程，当其需要访问内核时，会映射到内核级线程上，但是每次只允许一个线程映射，优点是线程管理在用户态进行，效率高；但是会发生阻塞，不支持多处理机；
  2. 一对一：并发能力强，但是开销大；
  3. 多对多：混合模型，一般用户级线程数量大于等于内核级线程数量，拥有上述各自的优点。

处理机调度​

tip

处理机调度时多道程序操作系统的基础，是操作系统设计的核心问题；其遵循 公平、高效 的原则。

三层调度​

  1. 高级调度（作业调度）：内存与外存之间的调度，用于创建线程；
  2. 中级调度（内存调度）：提高内存利用和系统吞吐，将暂时不能运行的进程调至外存等待，称为 挂起态；
  3. 低级调度（进程调度）：按照某种算法从就绪队列中选取进程，将处理机分配给他，进程调度的频率很高，一般几十毫秒一次。

调度指标​

  1. CPU 利用率，有效工作时间除以所有时间（有效 + 等待）；
  2. 系统吞吐量，单位时间 CPU 完成作业的数量，对调度算法比较敏感；
  3. 周转时间，作业从提交到完成所经历的时间，可以取平均或带权计算，主要体现系统及时性；
  4. 等待算法，所有进程等待时间之和；
  5. 相应时间，用户提交请求到系统首次相应的时间，在交互式系统中是衡量调度算法的重要准则之一。

调度器（程序）​

调度程序通常由三部分组成：

  1. 排队器：将所有 就绪进程 按一定算法排成一个或多个队列，便于选择，每当有一个进程转为就绪态，排队器就会将其插入相应队列；
  2. 分派器：根据调度程序所选择的进程，从就绪队列取出，为其分配 CPU；
  3. 上下文切换器，保存当前进程上下文到 PCB，再装入分派器（程序）的上下文；移出分派器上下文，将新进程上下文装入。
info

上下文切换会执行大量的 load 和 store 指令，因此现在通常才用两组寄存器，分别供内核和用户使用，上下文切换只需改变指针，指向对应寄存器组计科。

调度的时机、切换与过程​

tip

现代操作系统中不能进行进程调度与切换的情况有以下几种：

  1. 处理中断过程中，其不属于任一进程，因此不可被剥夺处理机资源；
  2. 进程在内核临界区，因为其需要 独占式 访问，理论上必须加锁，防止并行线程进入，因此解锁前不应切换、以加快临界区释放；
  3. 原子操作过程。
调度和进程切换的区别

调度是决定将系统资源分配给哪个进程，进程切换是实际分配系统资源。

进程调度方式​

当有优先级更高的进程进入就绪队列，通常有两种进程调度方式：

  1. 非抢占调度方式，又称非剥夺式，指让当前正在运行进程继续运行直到阻塞；该方法实现简单、系统开销小，但是不能用于分时系统和大多是实时系统；
  2. 抢占调度方式，又称剥夺方式，指立即暂停当前进程，有利于提高系统吞吐和响应效率。

闲逛进程​

进程切换时，若就绪队列没有进程，则会调度闲逛进程（idle），执行时不断测试中断，优先级最低，并且只需要 CPU 资源、不会被阻塞。

线程调度​

  1. 用户级线程和进程一致，因为其对内核不可见；
  2. 内核级线程通常不需考虑其属于哪个进程；其切换需要完整的上下文切换、修改内存映像、使 Cache 失效，会导致延迟。

经典调度算法​

先来先服务（FCFS）​

tip

即可用于作业调度，也可用于进程调度；直到进程被阻塞才进行下次调度。

若一个长作业先到达系统，会使后面的很多短作业等待很长时间，因此不能作为分时系统和实时系统的主要调度策略，但其常被结合在其他调度策略中；有利于 CPU 繁忙型，而非 I/O 繁忙型。

短作业优先（SJF）​

tip

直到阻塞才释放处理机。

对长作业不利，周转时间会很长，并可能处于长期饥饿状态；完全未考虑作业的紧急程度；作业长短由用户所估计，不一定准确。

SJF 的平均等待时间和平均周转时间最少。

优先级调度​

分为抢占式和非抢占式两种，并且其优先级也分为静态和动态，一般来说有如下策略：

  1. 系统进程高于用户进程；
  2. 交互进程高于非交互进程；
  3. I/O 进程高于计算进程，以便于让 I/O 尽早开始工作。

高响应比优先调度​

tip

主要用于作业调度，每次调度时，先计算队列中每个作业的响应比，计算公式为（等待时间 + 要求服务时间）/ 要求服务时间。

由公式，有利于短作业、并且缓解了长作业的饥饿现象。

时间片轮转​

tip

主要用于分时系统，按照 FCFS 排成就绪队列，每个进程仅运行一个时间片（如 50ms），使用完毕立即剥夺，进程返回队列尾；对时间片大小 敏感，若时间片太大，相当于 FCFS，若太小，开销太大；因此时间片大小由 响应时间、进程数目和处理机能力决定。

多级队列调度​

一定程度上弥补调度算法单一的问题，通过设置多个就绪队列，将不同类型或性质的进程固定分配到不同队列，可实施不同的调度算法，也可以设置不同的优先级，策略多变。

多级反馈队列调度​

tip

融合了前几种算法，是时间片轮转和优先级调度的综合，使用几个优先级队列，进程在低优先级队列中的时间片大，优先级越高时间片越小，每个队列采用 FCFS，每次调度后进程会进入高优先级队列中，直到最高优先级，采用时间片轮转算法。

优点：

  1. 终端型用户：短作业优先
  2. 短批处理作业用户：周转时间短
  3. 长批处理作业用户：缓解饥饿现象

同步与互斥​

用于制约进程的关系、可以保证进程的执行顺序，对资源的互斥访问等。

临界资源​

一次只能被一个进程使用的资源，访问过程可分为四部分：

  1. 进入区：检查是否可进入临界区，若能，设置访问标志，以阻止其他进程；
  2. 临界区：进程中访问临界资源的代码，又称临界段；
  3. 退出区：清除访问标志；
  4. 剩余区：代码中的其余部分。

同步​

又称直接制约关系，用于协调工作次序；

互斥​

间接制约关系，如多个进程同时访问临界资源，原则为：

  1. 空闲让进，临界区空闲可允许一个进程立即进入；
  2. 忙则等待，不空闲则其余进程等待；
  3. 有限等待，保证等待进程在有限时间能访问临界资源；
  4. 让权等待，等待过程中应立即释放处理器。

实现临界区互斥的基本方法​

软件实现​

单标志法：设置一个公共变量，不同值对应不同进程，若有进程离开临界区，则另一进程不能再进入临界区，陷入死循环；

双标志先检查法：进入前先查看资源是否被访问，不会陷入死循环，但是可能两个进程都进入临界区，因为检查对方 flag 和切换自己 flag 有一段时间；

双标志后检查法：先设置自己的标志，再检查对方的标志；

Peterson's Algorithm：额外设置了一个变量，要进入的进程先设置自己的标志再设置该公共变量，然后检测另一个变量对应的标志和该公共变量。

硬件实现​

中断屏蔽方法：关中断即可，因为进程切换只在中断时产生；但是将关中断的权利交给用户很危险，若一个程序关中断后不再开中断；

硬件指令方法：TestAndSet 方法，这是一个原子操作，作用是读出指定标志置为真，函数签名为 boolean TestAndSet(boolean *lock)；Swap 方法，原子操作，用于交换两个变量的值，签名为 Swap(boolean *a, boolean *b.

硬件方法可以适用于任意数目的进程，单多处理机，但是不能实现 让权等待，从等待进程中随机选择一个进入，可能导致饥饿。

互斥锁​

最简单的工具，进入临界区获得锁，离开释放，锁只能由一个进程拥有。

信号量​

功能较强的机制，提供两个标准原语 wait 和 signal，也称为 P 操作和 V 操作。

后面略。

管程​

管理程序（monitor）保证了进程互斥，降低死锁可能，提供条件变量，让程序员灵活地实现进程同步。

管程内部维护一个共享数据结构，并提供对其操作的方法，每次只允许一个进程进入管程，从而允许进程互斥；当管程内的进程被阻塞时，其他进程同样不能进入管程，因此引入了 条件变量，用于表示阻塞原因，管程中设置多个条件变量，每个条件变量保存了一个等待队列，包含所有相关的阻塞进程，对条件变量只有两种操作——wait 和 signal，前者将进程插入队列，释放管程，后者唤醒。

经典同步问题​

略

死锁​

只有对 不可剥夺资源 的竞争才会导致死锁，请求和释放资源的顺序、信号量使用不当都会等待死锁。

必要条件

  1. 互斥条件，占用资源是互斥的；
  2. 不剥夺；
  3. 请求并保持，请求资源时已获得的资源不释放；
  4. 循环等待条件，构成一个循环等待链。

处理策略

  1. 预防，破坏必要条件，如一次请求所有资源，资源剥夺等，但是效率低，进程初始化时间长；
  2. 避免，寻找可能的安全顺序，不必剥夺，但是必须知道将来的资源需求，不能被长时间阻塞；
  3. 检测及解除，定期检查，通过剥夺解除死锁，但会造成损失。

预防​

破坏互斥条件：允许共享资源，但有些资源不可共享；

破坏不剥夺条件：实现复杂，反复申请资源会增加系统开销，常用于易于保存和恢复的资源，如 CPU 寄存器即内存资源，一般不用于打印机等；

破坏请求并保持条件：才用预先静态分配方法，一次申请，但导致资源严重浪费，可能某些资源等到运行结束才使用，或者根本不使用，可能导致饥饿；

破坏循环等待条件：采用顺序资源分配法，给资源编号，每个进程必须按照递增的序号请求资源，相同序号一并请求，这样就不会产生循环；缺点：

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

避免​

安全状态：分配资源前先计算此次分配的安全性，不安全则等待，并非所有不安全状态就会导致死锁。

银行家算法：通过可利用资源量、最大需求矩阵、分配矩阵和需求矩阵来检测安全性，不安全则不分配，具体过程略。

检测和解除​

通过资源分配图进行化简来判断是否存在死锁，检出死锁则：

  1. 资源剥夺法：挂起进程，抢占资源；
  2. 撤销进程法；
  3. 进程回退法，回退时自愿释放资源而非剥夺，要求系统设置还原点。