进程管理

进程

早期的计算机一次只能执行一个程序（如 MS-DOS），这种程序完全控制系统，并且访问所有系统资源。

相比之下，现代计算机系统允许加在多个程序到内存，以便并发执行。这种改进要求：对各种程序提供更严格的控制和划分。这些需求导致了进程（Process）概念的产生，即进程为执行程序。进程是现代分时操作系统的工作单元。

进程概念

一个进程就是一个运行程序的实例，其由以下两个部分组成：

  • 当前状态（Current state）

    • 内存信息（Memory contents）

    • 程序计数器（Program counter）

    • 堆栈指针（Stack / Heap pointers）

    • ...

  • 系统资源（System resources）

我们强调：程序本身不是进程。程序只是被动（passive）实体，进程是活动（active）实体。
当一个可执行文件（executable file）被加载到内存时，这个程序就成为进程。

进程状态

二状态模型 & 排队模型

在任何时刻，一个进程要么在执行中，要么未执行，因此我们可以简单将线程构建为最简单的两个状态：

  • 执行中（Running）
  • 未执行（Not running）

Two-State Process Model

Queuing diagram

  • Enter

    即产生新的进程，进入队列。

  • Dispatch

    Dispatch 在这里是调度器的意思，即进行进程切换，处理器将处理新的进程。

  • Pause

    当前运行的进程被中断，操作系统的调度器将选择一个新的进程运行。

    这里中断的原因有很多，最常见的原因就是超过了操作系统的指令周期。

    假设操作系统为了避免任何一个进程独占处理器时间，仅允许一个进程最多连续执行 6 个指令周期：

    若进程 A 有 12 条指令，且刚刚出队列进入运行状态，则其执行完前 6 条指令后则会超时而重新入队，同时处理器切换到下一个进程。进程 A 在下一次出队后执行完接下来的 6 条指令后结束，然后退出该系统。

  • Exit

    即进程结束退出系统。

二状态模型具有很大的漏洞，即如果存在一些处于运行状态但已经就绪等待执行的进程，同时还存在一些阻塞状态例如等待 I/O 结束的进程，又由于该模型使用单队列，因此无法区分出未被阻塞的进程从而在阻塞状态的进程上浪费大量处理器资源。具体来说就是若进程 A 处于 I/O 阻塞状态，则在需要的 I/O 结束之前进程 A 会一直参与到进程排队的循环中，既浪费了处理器的工作时间，也增加了其他正常可执行的进程的排队时间。

五状态模型

为了解决以上二状态模型的问题，又提出了五状态模型：

  • 新的（New）

    New 状态用于存储那些暂时不能进入 Ready 队列的进程，一方面可能是资源问题，另一方面可能是优先级问题。

  • 运行（Running）

  • 阻塞（Blocked）

  • 就绪（Ready）

  • 退出（Exit）

Five-state Process Model

五状态模型在二状态模型的基础上新增了阻塞态，可以理解为用于存放等待 I/O 的阻塞态进程的队列。

当相关的 I/O 发生后，处于阻塞态的进程将会进入就绪态。

Queuing diagram

五状态模型依然存在潜在的问题。对于一般的计算机而言，处理器远快于 I/O，会出现内存中所有进程都在等待 I/O 的现象，此时处理器多数时间处于空闲状态，且需要大量的空间来维护处于阻塞状态的进程。

被挂起的进程

为了解决以上问题，操作系统会将部分进程挂起（Suspend），即把内存内存中某个进程的一部分或者全部移动到磁盘中。

当内存中不存在就绪态的进程时，操作系统就会把被阻塞的进程换出到磁盘的挂起队列（Suspend queue），即临时从内存中移除的进程队列。操作系统从此要么从挂起队列中取出一个进程，要么接受一个新的进程，将其放在内存中运行。

特别说明：

  • Blocked \(\to\) Blocked/Suspend

    若没有就绪进程，则至少换出一个阻塞进程，以便为另外一个未阻塞进程腾出空间。

  • Blocked/Suspend \(\to\) Ready/Suspend

    若等待的时间发生 I/O，则处于 阻塞/挂起 状态的进程可以转化到 就绪/挂起 状态。

  • Ready/Suspend \(\to\) Ready

    若内存没有就绪态进程，则操作系统需要调入一个进程来执行。处于 就绪/挂起 状态的进程与处于就绪状态的进程相比优先级更高。

  • Ready \(\to\) Ready/Suspend

    通常，操作系统更倾向于挂起阻塞态进程而非就绪态进程，因为就绪态进程可以立即执行，而阻塞态进程虽然占用了空间却不能执行。若释放内存来得到足够空间的唯一方式是挂起一个就绪态进程，则这种转化是必须的。

操作系统的控制结构：

操作系统为了管理进程和资源，必须掌握每个进程和资源的当前状态。

普遍采用的方法是：OS 构造并维护其管理的每个实体的信息表。我们称其为 OS control table，如下图。

  • 内存表（Memory table）

    用于跟踪内存和外存。

  • I/O 表（I/O table）

    管理计算机的 I/O 设备和通道。

  • 文件表（files table）

    用于提供文件信息。

  • 进程表（Process table）

    用于管理计算机进程。

进程控制块（PCB）

操作系统在管理和控制进程时，首先要知道进程的位置，其次要知道进程的属性（如 PID，进程状态等）。

为了维护进程的这些值，我们采用进程控制块（Process Control Block, PCB），它包括许多与某个特定进程相关的消息：

  • 进程状态（Process state）

  • 程序计数器（Program counter，PC）

    计数器表示进程将要执行的下个指令的地址。这里可以理解为 8086 CPU 中的 CS 和 IP 寄存器指向的地址。

  • CPU 寄存器（CPU register）

    包括累加器、索引寄存器、堆栈指针、通用寄存器、条件码寄存器等等。

  • CPU 调度信息（CPU-sheduling information）

    这类信息包括进程优先级、调度队列的指针和其他参数。

  • 内存管理信息（Memory-management information）

    根据操作系统使用的内存系统，这类信息可以包括基地址和界限寄存器的值、页表或段表。

  • 记账信息（Accounting information）

    这类信息包括 CPU 时间、实际使用时间、时间期限、记账数据、作业或进程数量等。

  • I/O 状态信息（I/O status information）

    这类信息包括分配给进程的 I/O 设备列表、打开文件列表等等。

Linux 操作系统的进程控制块采用 C 语言结构体 task_struct 来表示，它位于内核源码目录内的头文件 <linux/sched.h> 内。

linux/sched.h 内核源码

进程控制

执行模式

大多数处理器至少支持两种执行模式。某些指令只能在特权模式下运行，包括读取或改变诸如程序状态字之类的控制寄存器的指令、原始 I/O 指令和与内存管理相关的指令。另外，部分内存区域仅能在特权模式下访问。

非特权模式通常称为用户模式（User mode），特权模式通常称为内核模式（Kernel mode），后者也常常被称为系统模式（System mode）或者控制模式（Control mode），内核模式指的是操作系统的内核，它是操作系统中包含重要系统功能的部分。

Typical Functions of an OS Kernel

使用两种模式的原因是保护操作系统和重要的操作系统表（如 PCB）不受用户程序的干扰。在内核模式下，软件会完全控制处理器及其所有指令、寄存器和内存。为了安全起见，这种级别的控制对用户程序而言没有必要。

在给出两种模式后，我们就遇到了两个问题：

  1. 处理器如何区分当前的进程是以什么模式来运行的？

    我们通常在程序状态字中设定几个指示执行模式的位。

    当用户调用一个操作系统服务或中断来触发系统例程的执行时，执行模式被置为内核模式；而当从系统服务返回到用户进程时，执行模式将被置为用户模式。

    例如 64 位 IA-64 体系的 Intel Itanium 处理器中，就有一个包含 2 位 CPL（Current Privilege Level）字段的处理器状态寄存器（PSR）。级别 0 表示内核模式，是最高特权级别，其他级别（1 ~ 3）则是用户模式。

  2. 模式如何转变？

    • User \(\to\) Kernel

      开启内核模式，并存储当前的用户 PC 指针。

    • Kernel \(\to\) User

      清空内核模式，将 PC 指针指向合适的用户进程。

进程创建 ☁️

操作系统创建一个新进程时，会按照如下步骤操作：

  1. 为新进程创建一个唯一标识符

  2. 为进程分配空间

  3. 初始化 PCB

  4. 设置正确的链接

    若操作系统将每个调度队列都维护为一个链表，则新进程必须放在就绪或者 就绪/挂起 链表中。

  5. 创建或扩充其他数据结构

    例如为每个进程维护一个记账文件。

进程切换

基于此，我们可以得到进程切换的一般过程：

  1. 存储当前进程的 PC、SP 指针与寄存器等（统称 Context）
  2. 更新当前进程的 PCB
  3. 将当前进程移动到等待队列（具体状态视情况而定）
  4. 从进程队列中选取一个新的进程来执行，从其 PCB 中读取信息

...

何时切换进程？进程切换可能在操作系统从当前正在运行进程中获得控制权的任何时刻发生。

由于进程切换需要内核模式的权限，所以进程切换的过程中一般都会发生执行模式的改变。

其一般有 3 种原因：

  1. 中断（Interrupt）

    与当前正运行进程无关的某种外部事件相关，如：

    • 时钟中断（Timer interrupt）

      当前进程运行时间已经达到最大允许时间段（Time slice）。若超时，进程就切换到就绪态，并调入另一个进程。

    • I/O 中断（I/O interrupt）

      操作系统确定是否已发生 I/O 活动。若 I/O 活动是一个或多个进程进程正在等待的事件，则操作系统就会把所有处于阻塞态的进程转化为就绪态，此时操作系统必须决定是继续执行当前处于运行态的进程还是让优先级更高的就绪态进程抢占该进程。

  2. 陷阱（Trap）

    与当前正在运行的进程相关，一般指当前进程出现错误或者异常条件时发生的进程切换。

    此时，操作系统会判断该进程的错误或异常条件是否致命，致命时会直接进入退出态，并切换进程；若不致命，操作系统的动作取决于错误的性质和操作系统本身的设计。

    Trap 有很多例子，比如常见的 Segmentation fault（段错误）、Divide by zero Exception（除 0 异常）等等。

  3. 系统调用（System call）

    类似于函数调用，不过在当前进程之外。例如，当用户执行了一个 I/O 操作的指令，如打开一个文件，这时该调用会转移到操作系统代码一部分的一个例程。使用系统调用会将用户进程置为阻塞态。

    Linux 常见系统调用的 C 语言接口：

    • fork() ：

      创建一个新的子进程，该子进程是当前进程的复制。子进程和父进程将在不同的地址空间中运行，但它们会共享相同的代码和文件描述符。用于创建新进程。

    • wait() 和 waitpid() ：

      用于等待子进程的终止，并获取子进程的终止状态。这些函数通常与 fork() 配合使用，用于处理子进程的退出状态。

    • exec() 系列函数（如 execve() 、execl() 、execp() 等）：

      用于加载并执行新的程序。这些函数会替代当前进程的映像，将其替换为一个新的程序。exec() 函数允许传递参数、环境变量和命令行参数给新程序。

    • open() 和 close() ：

      用于打开和关闭文件。open() 函数用于打开文件，并返回文件描述符，close() 函数用于关闭文件。

    • read() 和 write() ：

      用于从文件描述符读取数据和将数据写入文件描述符。它们是输入和输出的基本系统调用。

进程调度

知道了进程的工作模式，OS 就需要采取合适的策略进行进程调度（Process scheduling）。进程调度有以下目标：

  1. 响应时间（Response time）：降低任务的响应时间，以满足实时要求或减少用户感知的等待时间。低延迟对于需要快速响应的应用程序非常重要。
  2. 高吞吐量（High Throughput）：确保系统可以同时运行多个任务，并且能够高效地处理大量的工作负载。这对于服务器和数据中心等高负载环境至关重要。保证处理器在一定的时间内可以尽可能处理更多任务。
  3. 资源利用率（Resource Utilization）：最大化系统资源的利用率，以确保资源得到有效利用，同时避免浪费。这包括处理器时间、内存、I/O 设备等资源的有效管理。
  4. 避免进程饥饿（Process starvation）：不要出现某个进程长时间等待而没有执行。
  5. 公平性（Fairness）：确保每个进程都有平等的机会获得处理器时间和其他系统资源。
批处理进程和交互式进程

  • 批处理进程（Batch processes，CPU-intensive）

    批处理进程通常用于执行大量相似的、非交互性的任务，这些任务按照一定的顺序依次执行，而不需要用户的交互或实时响应。

    对于批处理进程而言，吞吐量（Throughput）最重要。

  • 交互式进程（Interactive processes，I/O-intensive）

    交互式进程是需要与用户进行实时交互的进程。它们等待用户的输入并立即做出响应，通常以图形用户界面（GUI）或命令行界面的形式展示给用户。

    对于交互式进程而言，响应时间（Response time）最重要。

Two types of processes

绝大多数进程的 CPU 峰值时间都很短（Short CPU burst）。

FCFS 策略

先来先服务（First-Come-First-Served）策略，顾名思义就是让进程按照排队的策略进行调度。

FCFS 策略十分容易实现，只需要维护一个就绪进程的队列结构，让每个新进程入队，将要执行的进程出队即可。

FCFS / FIFO

优点：

  • 易于实现；
  • 当所有进程耗时差不多时 FCFS 策略的效果会很好。

缺点：

  • 一些短进程可能需要长时间的等待，可能造成进程饥饿。
SJF 策略

SJF 策略即最短作业优先策略（Shortest-Job-First）策略，在 SJF 策略中，操作系统会选择等待队列中最短的作业（最短的执行时间）来执行，以期望最小化平均等待时间，提高系统的性能。

非抢占性策略和抢占性策略

非抢占性策略（Non-Preemptive Scheduling）：

  • 特点：在非抢占性策略中，一旦一个进程开始执行，它将一直运行，直到完成。其他进程无法强制中断正在执行的进程，除非当前进程主动放弃 CPU（Voluntarily gives up the CPU），例如等待 I/O 操作完成。
  • 优点：非抢占性策略通常比抢占性策略具有较低的上下文切换开销，因为不需要频繁地切换执行的进程。
  • 适用性：这种策略适用于不需要实时性要求的场景，如批处理系统或一些传统的桌面应用程序。它也可以简化并发编程，因为无需处理抢占和竞争条件。

以上讨论的 FCSF、SJF 调度策略都属于非抢占性策略。

抢占性策略（Preemptive Scheduling）：

  • 特点：在抢占性策略中，操作系统可以强制中断当前正在执行的进程，并将 CPU 分配给其他等待的进程。这种策略允许更灵活地管理进程，根据进程的优先级、时间片或其他条件来决定进程的执行。
  • 优点：抢占性策略可以提高系统的响应性，因为操作系统可以在需要时迅速切换到更高优先级的进程，以满足实时性要求或更紧急的任务。
  • 适用性：抢占性策略通常适用于需要实时性、响应性和更精细的调度控制的场景，如操作系统内核、服务器应用、多媒体处理和实时系统。
RR 策略

轮转调度（Round Robin，RR）是一种抢占性的进程调度策略。在 RR 调度中，操作系统将 CPU 时间分成固定大小的时间片（也称为时间量或量子），然后按照先来先服务（FCFS）的顺序将这些时间片分配给就绪队列中的进程。每个进程在一个时间片内运行，然后如果它还没有完成，就被移到队列的末尾等待下一个时间片。

RR 调度比 FCFS 更加公平，特别是对于时间差别较大的进程。

时间片的选择：

选择一个合适长度的时间片对于 RR 策略而言至关重要，太长或者太短都不合适。

  • 太长：
    • 响应性差（Poor responsiveness）。
  • 太短：
    • 过于频繁的上下文切换（Overhead of context switching）可能造成较大的时间开销。

Virtual Round Robin

备用队列（Auxiliary queue）：

  • 用于存放那些从 I/O 阻塞状态释放的进程；
  • 相对于那些在就绪队列中的进程而言拥有更高的优先级。
优先级调度策略

优先级调度策略（Scheduling with Priorities）根据进程的优先级来决定下一个执行的进程。具有较高优先级的进程先执行。这可以用于根据进程的重要性和紧迫性来调度。其会给每个进程设定一个优先级（Priority value），调度器总是先选择优先级更高的进程来运行。

优先级可分为静态和动态两种，对于动态优先级而言，OS 可以动态调整进程的优先级。

实现方式：对于不同优先级的进程，使用不同的队列来维护。

如下图，RQ0 级别的队列优先级最高，然后随着编号增加，优先级递减。则每次处理器会先从优先级高的队列选择进程运行。

Priority Queuing

多级反馈队列

多级反馈队列（Multi-Level Feedback Queue，MLFQ）特别是用于多任务处理系统。MLFQ 结合了多个队列和反馈机制，以实现灵活的进程调度，同时考虑了进程的优先级、等待时间和历史执行表现。

MLFQ 包含多个队列，每个队列具有不同的优先级。通常，系统会维护一个队列数组，其中队列的优先级逐渐降低。高优先级队列中的进程在低优先级队列中的进程之前执行。在每个队列中，通常会使用一种基本的调度策略，如先来先服务（FCFS）或轮转调度（Round Robin）。不同队列可以使用不同的基本调度策略。

MLFQ

  • 反馈机制：

    MLFQ 使用反馈机制来动态调整进程的优先级。

    如果一个进程在高优先级队列中等待了一段时间但没有完成，它将被移到较低优先级的队列中，从而允许其他进程有机会获得 CPU 时间。

    如果一个进程在低优先级队列中等待了很长时间而没有被执行，系统可能会提高其优先级。这是为了防止饥饿现象，即确保所有进程最终都能获得处理器时间。

  • 解决饥饿问题：

    MLFQ 调度中如果频繁有新的进程进入系统，可能导致优先级低的进程频繁被抢占，从而造成进程饥饿问题。

    这个问题有很多解决方案，比如对于不同的优先级的队列，我们设置不同的抢占时间。

    例如，对于 \(RQ_i\) 队列，我们将抢占时间设定为 \(2 ^ i\)，从而给低优先级队列的进程更多执行时间。

抢占时间（Preemption time）是指一个进程在被操作系统抢占（即中断并停止执行）之前能够持续执行的时间长度。这个概念在抢占式进程调度策略中非常重要，因为它决定了操作系统何时可以选择停止当前正在执行的进程，以分配 CPU 时间给其他等待的进程。

进程优先级在 Unix/Linux 操作系统的具体体现 —— Niceness

在 Unix 和类 Unix 操作系统中，Niceness（也称为 Nice 值）是一个用于表示进程优先级的概念。Niceness 值通常在 -20 到 19 之间，默认是 0，其中 -20 表示最高优先级，19 表示最低优先级。更负的 Niceness 值表示更高的优先级，而更正的 Niceness 值表示更低的优先级。

我们可以使用 ps 指令打印进程信息，从而看到进程的 Nice 值。

  • ps aux：显示所有用户的详细进程列表。
  • ps aux | grep <进程名>：通过管道和grep命令来筛选特定进程。
  • ps -e：显示所有进程，包括系统进程。
  • ps -ef：以全格式显示所有进程。
  • ps -u <用户名> : 查看某个用户的进程。
CFS

CFS（Completely Fair Scheduler）是 Linux 操作系统中的一种进程调度算法，用于在多任务环境中公平地分配 CPU 时间给不同的进程。CFS 的目标是实现公平的 CPU 时间分配，确保每个进程在一定时间内获得相同比例的 CPU 时间，而不受其他进程的干扰。

底层实现原理 —— 红黑树。

Ubuntu 实操

其实也不一定得是 Ubuntu，其他类 Unix 系统如 MacOS，本身就可以完成以下实验。

使用 Python 的 os 模块实现部分 System call

Python 的 os 模块提供了标准 UNIX 库接口与不少 POSIX 系统调用，如 fork() ，exec() 系列函数等等。

fork()

fork() 函数用于创建一个新进程。fork() 函数不接收任何参数，当 fork() 被调用后，其会复制一份相同的进程，对于两个相同的进程，fork() 函数返回不同的值，对于当前进程，返回子进程的 pid，对于子进程，会返回 0。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
import os

def main():
    pid = os.fork()

    if pid == 0:
        print("Child process")
    else:
        print(f"Father process, child pid = {pid}")

if __name__ == '__main__':
    main()

运行结果：

1
2
Father process, child pid = 37012
Child process
waitpid()

os.waitpid() 是 Python 中用于等待子进程结束的函数之一，它允许你在父进程中等待指定的子进程完成执行。这个函数通常与 os.fork() 一起使用，以管理子进程的执行。

1
os.waitpid(pid, options)
  • pid ：要等待的子进程的进程 ID（Process ID）；
  • options：控制等待行为的选项标志，有以下取值：
    • os.WNOHANG：如果没有子进程退出，立即返回，不会阻塞。
    • os.WUNTRACED：如果子进程进入暂停状态（例如，收到了 SIGTSTP 信号），也会返回。
    • 0，表示在子进程结束前，父进程始终是阻塞状态。
  • os.waitpid() 的返回值是一个包含两个值的元组 (pid, status)，其中：
    • pid 是已经退出的子进程的进程 ID。
    • status 包含有关子进程退出状态的信息，可以使用 os.WIFEXITED(status)、os.WEXITSTATUS(status)、os.WIFSIGNALED(status)、os.WTERMSIG(status) 等函数来提取这些信息。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
import os

def main():
    pid = os.fork()

    if pid == 0:
        print("Child process")
    else:
        os.waitpid(pid, 0) # 等待子进程完成
        print(f"Father process, child pid = {pid}")

if __name__ == '__main__':
    main()

输出：

1
2
Child process
Father process, child pid = 37267
操作系统
#操作系统 #进程 #进程管理
进程管理
https://goer17.github.io/2023/09/24/进程管理/
作者
Captain_Lee
发布于
2023年9月24日
许可协议