第二章进程¶

【考纲内容】¶

Note

进程与线程：
进程/线程的基本概念；
进程/线程的状态与转换；
线程的实现：内核支持的线程；线程库支持的线程；
进程与线程的组织与控制；
进程间通信：共享内存；消息传递；管道；信号
CPU调度与上下文切换：
调度的基本概念；
调度的目标；
调度的实现：调度器/调度程序(scheduler)；调度的时机与调度方式（抢占式/非抢占式)；闲逛进程；内核级线程与用户级线程调度；
CPU调度算法；
多处理机调度；
上下文及其切换机制
同步与互斥：
同步与互斥的基本概念；
同步与互斥的基本方法：软件实现方法；硬件实现方法；
锁；
信号量；
条件变量；
经典同步问题：生产者-消费者问题；读者-写者问题；哲学家进餐问题
死锁：
死锁的概念；
死锁预防；
死锁避免；
死锁检测和解除

【考频统计】

年份	考点	分值
2009	进程调度算法、死锁必要条件、\(P/V\)操作（生产者消费者）	4+7=\(11\)分
2010	进程控制(进程的创建)、进程调度、信号量机制、临界区互斥	4*2=\(8\)分
2011	线程和多线程模型(线程共享)、进程调度算法、同步机制、银行家算法、\(P/V\)操作（叫号问题）	4*2+8=\(16\)分
2012	进程和线程的基本概念、进程的调度与切换、处理机调度的概念、银行家算法	4*2=\(8\)分
2013	进程调度(进程优先级)、银行家算法、\(P/V\)操作（生产者消费者）	4+7=\(11\)分
2014	进程状态及概念、进程通信（管道）、进程调度算法（饥饿）、死锁必要条件、\(P/V\)操作（生产者消费者）	8+8=\(16\)分
2015	进程状态与转换、死锁避免、死锁检测、\(P/V\)操作（生产者消费者）	2*2+9=\(13\)分
2016	进程调度、互斥机制、临界区互斥的硬件实现方法、管程、死锁原因、进程调度与饥饿(大题)	5*2+6=\(16\)分
2017	进程调度(时间片)、进程调度算法、\(P/V\)操作、进程状态转换与CPU模式	4+8+3=\(15\)分
2018	进程控制(进程的阻塞)、进程的调度与切换、调度算法的评价指标(等待时间、平均周转时间) 进程的组织、进程的同步、管程与条件变量、同步机制(让权等待)、实现互斥的基本方法、银行家算法	6*2=\(12\)分
2019	用户级线程与内核级线程、进程控制(进程唤醒)、进程调度算法、调度算法的评价指标(平均等待时间)、死锁（死锁原因、银行家算法、死锁预防、死锁解除）、\(P/V\)操作（哲学家进餐问题）	4*2+8=\(16\)分
2020	进程调度算法（多级队列反馈）、银行家算法、进程创建之父进程与子进程、临界区互斥与临界资源、\(P/V\)操作（同步问题）	4*2+7=\(15\)分
2021	进程控制之进程创建、进程调度算法、进程组织之进程控制块、进程调度（的发生原因）、临界资源（死锁）、实现临界区互斥的方法（信号量、开关中断）	4*2+7=\(15\)分
2022	进程调度算法、银行家算法、进程状态转换、\(P/V\)操作（同步问题）	3*2+8=\(14\)分
2023	进程状态转换、进程虚拟空间、进程调度算法、调度算法的评价指标(平均周转时间)、临界区互斥实现（大题）	3*2+8=\(14\)分

2.1 进程与线程¶

2.1.1进程的概念¶

Note

我们知道，程序主要是存放在磁盘中的指令和数据，为了执行程序，需要将程序的指令和数据放入内存，并为它分配CPU和堆栈等资源支持它运行。

所谓进程，就是一个正在运行的程序某一时刻的所有状态信息，它包括了

内存空间：程序代码，程序处理的数据（包括全局变量）和栈（包括临时数据，如函数参数、返回地址和局部变量）、堆(进程运行时动态分配的内存)等
CPU内部状态信息：一组通用寄存器的当前值，程序计数器PC，SP（堆栈指针）
进程占用的其他系统资源：打开文件、已分配内存、设备等

进程与程序的联系

进程是操作系统处于执行状态程序的抽象

程序 = 文件（静态的可执行文件）

进程 = 执行中的程序 = 程序 + 执行状态

同一个程序的多次执行和过程对应为不同的进程（例如同一用户可以调用\(web\)浏览器的多个副本，但是每个都是单独进程，虽然文本段相同，都是数据、堆及堆栈段却不同。进程在运行时也经常会生成许多进程。）

为了使参与并发执行的每个程序都能独立地运行，必须为之配置一个专门的数据结构，即进程控制块(\(Process \ Control \ Block,PCB\))，系统利用PCB来描述进程的基本情况和运行状况，从而控制和管理进程。

进程实体(进程映像)：由程序段、相关数据段和PCB三部分构成。创建进程实质上是创建进程实体中的PCB，而撤销进程实质上是撤销进程的PCB。

引入进程实体的概念后，我们可以把进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

2.1.2 进程的组织¶

进程控制块PCB（最核心的）
PCB是进程存在的唯一标志，进程创建后该结构常驻内存，并在进程结束时删除,操作系统通过PCB来管理和控制进程,因此管理和控制所需的参数一定是放在PCB中的。
包含的内容

类别	说明
进程描述信息	进程标识符\(PID\)（系统内的每个进程都有一个唯一的PID），用户标识符\(UID\)（表示进程归属的用户，主要为共享和保护服务）
进程控制和管理信息	进程状态、进程优先级（代码运行入口地址、程序的外存地址、进入内存时间、处理机占用时间、信号量使用）等
资源分配清单	内存/虚存地址、进程文件目录打开表、IO设备信息等(分别对应着代码段指针、数据段指针、堆栈段指针、文件描述符、键盘鼠标等)
处理机相关信息（处理机的上下文）	保存处理机的寄存器各值，用于进程间切换（包括通用寄存器值、地址寄存器值、控制寄存器值、标志寄存器值、状态字、累加器、索引寄存器以及其他条件码信息寄存器等等）

PCB还包括程序计数器PC（一般放在里面的context上下文信息结构体之中）、CPU调度信息(包括进程优先级、调度队列的指针和其他调度参数)、内存管理信息(可以包括基地址和界限寄存器的值)等等。

进程标识符是对进程的唯一标识，类似于进程的编号，每个进程在创建时，都会产生对应的 pid 并装入其 PCB。pid 是由操作系统分配的有限资源，即可分配的 pid 个数往往是固定的，该个数对应了系统中允许同时存在的最大进程数。若进程创建无法申请到 pid，则该进程的创建会失败。

PCB包含的信息

PCB的相关核心源码

xv6 中的 PCB（struct proc）

//进程状态枚举
enum procstate { 
  UNUSED,     // 进程槽位未使用（初始状态）
  USED,       // 进程已分配，但未初始化完成（过渡状态）
  SLEEPING,   // 进程在休眠（等待事件或资源）
  RUNNABLE,   // 进程可运行（在就绪队列中等待调度）
  RUNNING,    // 进程正在运行（占用 CPU）
  ZOMBIE      // 进程已终止，等待父进程回收（僵尸状态）
};
//内核态下进程上下文
struct context {
  uint64 ra;   // 返回地址（指令指针），即PC程序计数器
  uint64 sp;   // 栈指针
  uint64 s0;   // callee-saved 寄存器 s0-s11
  uint64 s1;
  ...
};
// xv6 源码片段（RISC-V 版本）：
struct proc {
    struct spinlock lock;       // 进程锁（用于同步）
    enum procstate state;       // 进程状态（UNUSED, SLEEPING, RUNNABLE 等）
    int pid;                    // 进程 ID
    struct proc *parent;        // 父进程指针
    void *chan;                 // 休眠等待的通道（用于同步）
    int killed;                 // 是否被终止
    uint64 kstack;             // 内核栈地址
    uint64 sz;                 // 进程内存大小，和下面的页表指针一起可以找到页表，这就是该进程的地址空间
    pagetable_t pagetable;     // 页表指针（RISC-V 页表）
    struct trapframe *trapframe; // 陷阱帧（保存用户态寄存器状态,用于从内核态返回到用户态）
    struct context context;     // 内核态上下文（用于进程上下文切换）
    struct file *ofile[NOFILE]; // 打开的文件表
    // ... 其他字段（当前目录、进程名等）
};

Linux 中的 PCB（task_struct）

// Linux 内核源码片段（简化版）：
struct task_struct {
    volatile long state;       // 进程状态（运行、睡眠、停止等）
    int exit_state;             // 退出状态
    pid_t pid;                  // 进程 ID
    pid_t tgid;                // 线程组 ID（主进程 PID）
    struct task_struct *parent; // 指向父进程的指针
    struct list_head children;  // 子进程链表
    struct mm_struct *mm;       // 内存管理信息（地址空间、页表等）
    struct files_struct *files; // 打开的文件描述符表
    struct thread_struct thread; // CPU 寄存器状态（上下文切换时保存）
    // ... 其他字段（调度策略、信号处理、资源限制等）
};

把一个运行中的程序（进程）想象成一个“厨师”，代码段就是他的“菜谱”（一系列动作指令），而数据段就是他手边的各种“食材和厨具”（需要处理的数据）。

代码段：代码段是静态的、只读的，存放着程序要执行的“指令”。它主要包含两样东西：

1) 二进制机器码：这是程序的核心，是你写的C、C++、Java等代码被编译器转换成的CPU能够直接理解和执行的二进制指令序列（比如加法、移动数据、跳转等）。 2) 只读常量 (Read-Only Data)： * 虽然不属于严格意义上的代码，但常常和代码段放在一起，因为它也是只读的。 * 最典型的就是字符串字面量，例如 printf("Hello, World!"); 中的 "Hello, World!"。 * 以及被 const 关键字修饰的全局常量。

核心特点：

只读 (Read-Only)：防止程序意外地修改了自己的指令而导致崩溃。

可共享 (Sharable)：如果你的电脑上同时运行了多个相同的程序（比如打开了多个Word文档），它们在内存中会共享同一份代码段，以此来节省宝贵的内存空间。

数据段：数据段存放程序运行中需要用到的所有“数据”，它是动态的、可读可写的。为了更高效地管理，数据段在逻辑上被细分为以下几个区域：

1) .data段 (已初始化数据段)：存放那些在代码中已经被赋了初始值的全局变量和静态变量。

示例：int global_var = 100;``static int static_var = 50;

特点：这些初始值会随着程序一起被保存在可执行文件中，程序加载时，这些值会被直接复制到内存中。

.bss段 (未初始化数据段)：存放那些没有被赋初始值（或被初始化为0）的全局变量和静态变量。

示例：int global_array[100];``static int static_zero_var;

特点：为了节省可执行文件的体积，这些变量并不会真的在文件中存一大堆“0”。文件只记录“需要XXX大小的空间”，当程序加载时，操作系统会分配这块内存并将其全部清零。

堆 (Heap)：存放程序在运行时动态申请的内存。这是最大、最灵活的一块内存区域。

示例：在C语言中使用 malloc() 或在C++中使用 new 申请的内存都在堆上。

特点：由程序员手动管理，需要自己申请，也需要自己手动释放（free() / delete），忘记释放会导致“内存泄漏”；空间大，使用灵活，通常从低地址向高地址增长。

栈 (Stack)：这是一块用于管理函数调用的区域，由编译器自动管理，效率极高。

函数的局部变量：void func() { int local_var = 10; }

函数的参数

函数调用的返回地址：记录函数执行完后应该跳回到哪里继续执行。

特点：

自动管理，无需程序员操心。函数调用时，系统会自动在栈顶为它分配一块内存（称为“栈帧”）；函数返回时，这块内存会自动被释放。

空间有限，如果函数调用层次太深（如无限递归），会导致“栈溢出”（Stack Overflow）。

通常从高地址向低地址增长。

PCB组织形式：（为了方便进程的调度和管理，将各进程的PCB用适当的方法组织起来）

线性表：将系统中的所有PCB都组织在一张线性表中，将这张表的起始地址存放在内存的特定位置或存放在专用寄存器里。
链表队列：进程的不同状态对应着PCB挂在不同的队列(阻塞队列、就绪队列)
索引表：进程的不同状态对应着PCB挂在不同的索引表内(阻塞索引表、就绪索引表)。

进程的封闭性：进程的执行结果只取决于进程的本身，而不受外界(推进速度)影响，无论该进程是一鼓作气执行完，还是走走停停，都不影响执行的结果，若进程失去了封闭性，那么它的推进速度（是否被阻塞）便会影响它的执行结果。

2.1.3 进程的状态¶

运行态(running)：在单处理机下只有一个处于执行态，多处理机下可以有多个进程处于执行态
就绪态(ready)：进程获得了除了处理机外所需的一切资源，一旦得到处理机，便可立即执行
阻塞态(等待态waiting)：等待某资源可用(不包括处理机)或等待I/O完成，即使处理机空闲，该进程也不能运行

进程处于就绪态的原因只有还没有分配到 CPU，但是进程处于阻塞态的原因可能是多种多样的，因此每一类原因造成阻塞的进程都会单独构建一个 PCB 等待队列，就绪队列只有一个。

创建态：进程正在创建的状态，此时进程已经分配好了PCB正在分配进程执行所需要的除了CPU外的其他资源。

除了第一个进程，操作系统中的进程均是由另一个进程创建的，创建进程的进程和被创建的进程互为父进程和子进程。父进程在创建子进程的过程中会为子进程申请 pid 和 PCB，并申请其它子进程所需要的资源，创建过程中的进程处于创建态。

退出态：进程运行终止后，操作系统会回收其所占用的资源和 PCB 等，被回收过程中的进程处于退出态。

运行态→阻塞态：一种进程自身做出的主动行为，进程用“系统调用”的方式申请某种系统资源，或者请求等待某个事件发生；
阻塞态→就绪态：申请的资源被分配或等待的事件发生，是一种被动行为,需要其他相关进程的协助.
注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转变为阻塞态，因为进入阻塞态是进程主动请求的，必然需要进程在运行时(获得CPU)能发出该请求.
为何要区别就绪态与阻塞态:也即为何把处理机和其他资源分开,是因为在分时系统的时间片轮转机制中,每个进程分到的时间片是若干毫秒,也就是进程得到处理机的时间很短且很频繁,进程在运行过程中是频繁地转换到就绪态的,其他资源(如外设)的使用与分配或某一事件的发生(如I/O操作的完成)对应的时间相对来说很长,进程转换到阻塞态的次数也相对较少.这样来看,这两种状态是进程生命周期中两种完全不同的状态,显然需要加以区分.

【2023-27】下列给出当前线程引起的事件或执行的操作中，可能导致该线程由执行态变为就绪态的是（）。

A. 键盘输入

B. 缺页异常

C. 主动出让CPU

D. 执行信号量的wait()操作

答案

本题选C；

【补充】：挂起态

计算机的内存空间是有限的，当内存空间不足时，操作系统需要将一部分短时间内可能不执行的进程换回到外存中，这种操作叫挂起，同时把更有可能执行的进程从外存中放入内存，这种操作叫激活。

挂起状态可以分为两种：

阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

这两种挂起状态加上前面的五种状态，就变成了七种状态变迁，见如下图：

七状态转换图

低优先级进程不仅要给高优先级进程让出处理机资源，还会为其让出内存资源让其运行

运行状态->就绪挂起状态：这里发生在客户在程序正在运行时直接挂起程序。注意这里的箭头是单向的，所以在就绪挂起状态结束以后实际上是执行激活步骤，进入就绪状态，等待处理机调度。
阻塞状态->阻塞挂起状态：当内存空间比较紧缺的时候，如果有存在在内存中的，而且是处于阻塞状态的进程，那么就让他更需要内存的程序占用内存，自己进入阻塞挂起状态。因为现在这个进程也不能进入就绪状态，这个程序在内存中是没有什么作用的。
阻塞挂起状态->就绪挂起状态：当阻塞状态等待的IO事件或其他事件到来的时候状态发生改变。
就绪挂起状态->就绪状态：如果内存中没有就绪态进程，操作系统需要调入一个进程继续执行。此外，当处于就绪挂起状态的进程比处于就绪态的任何进程的优先级都要高时，也可以进行这种转换。这种情况的产生是由于操作系统设计者规定，调入高优先级的进程比减少交换量更重要。
就绪状态->就绪挂起状态：通常，操作系统更倾向于挂起阻塞态进程而不是就绪态进程，因为就绪态进程可以立即执行，而阻塞态进程占用了内存空间但不能执行。但如果释放内存以得到足够空间的唯一方法是挂起一个就绪态进程，那么这种转换也是必需的。并且，如果操作系统确信高优先级的阻塞态进程很快就会就绪，那么它可能选择挂起一个低优先级的就绪态进程，而不是一个高优先级的阻塞态进程。

2.1.4 进程控制¶

主要功能:对系统中的所有进程实现有效的管理,具有创建新进程、撤销已有进程、实现进程状态切换等功能．

2.1.4.1 进程的创建¶

Note

除了第一个进程，操作系统中的进程均是由另一个进程创建的，创建进程的进程和被创建的进程互为父进程和子进程。父进程是在自己的内核空间创建子进程的。

在操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都会引起进程的创建。操作系统创建一一个新进程的过程如下:

为新进程分配一个唯一的进程标识号pid，并申请一个空白 PCB (PCB 是有限的)。若 PCB 申请失败，则创建失败。
为进程分配其运行所需的资源，如内存、文件、I/O 设备和 CPU 时间等(在 PCB 中体现)。这些资源或从操作系统获得，或仅从其父进程获得。如果资源不足(如内存),则并不是创建失败，而是处于创建态，等待内存资源。此时，创建该进程的父进程会被阻塞。
初始化 PCB,主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息，以及设置进程的优先级等。
若进程就绪队列能够接纳新进程，则将新进程插入就绪队列，等待被调度运行。

大多数操作系统对进程的识别采用的是唯一的进程标识符pid, 这通常是一个整数值,系统内的每个进程都有一个唯一的pid, 它可以作为一个索引, 以便访问内核中的进程的各种属性.

下面是扩展了解部分，有兴趣可以看一下

Linux 进程创建的核心源码

Linux 通过 fork() 或 clone() 系统调用创建进程，最终由内核函数 kernel_clone()实现。以下是关键源码和步骤：

(1) 入口函数：kernel_clone()

定义在 kernel/fork.c：

// kernel/fork.c
pid_t kernel_clone(struct kernel_clone_args *args) {
    // 1. 分配并初始化进程描述符（task_struct）
    struct task_struct *p;
    p = copy_process(
        args->flags,          // 克隆标志（如 CLONE_VM、CLONE_FILES）
        args->stack,          // 用户栈地址
        args->stack_size,     // 栈大小
        args->parent_tidptr,  // 父进程的 TID 指针
        args->child_tidptr,   // 子进程的 TID 指针
        args->tls,            // 线程本地存储
        args->pidfd,          // PID 文件描述符
        args->exit_signal     // 退出信号
    );

// 2. 唤醒子进程，加入就绪队列
wake_up_new_task(p);
return pid; // 返回子进程 PID


}

(2) 核心复制逻辑：copy_process()

// kernel/fork.c
static __latent_entropy struct task_struct \*copy_process(
unsigned long clone_flags,
unsigned long stack_start,
unsigned long stack_size,
int __user \*parent_tidptr,
int __user \*child_tidptr,
unsigned long tls,
int pidfd,
int exit_signal
) {
// 1. 分配 task_struct 结构体（即分配PCB）
struct task_struct \*p = dup_task_struct(current);

// 2. 复制父进程资源
retval = copy_files(clone_flags, p);  // 文件描述符表
retval = copy_fs(clone_flags, p);     // 文件系统信息
retval = copy_mm(clone_flags, p);     // 地址空间（COW 机制）
retval = copy_thread(clone_flags, args-&gt;stack, args-&gt;stack_size, p); 
// 通过 copy_thread() 初始化子进程的 thread_struct（指令指针、栈指针）。

// 3. 分配 PID 并加入进程树
pid = alloc_pid(p-&gt;nsproxy-&gt;pid_ns_for_children);
p-&gt;pid = pid_nr(pid);
attach_pid(p, PIDTYPE_PID);


}

此外注意，父进程创建子进程后，将其加入就绪队列，然后需要检查它的优先级是否更大，是的话需要打上需要调度的标签，在中断/异常/系统调用的服务例程执行完的返回路径会检查该标志，如需要调度，就会触发调度器开始调度新进程。

void wake_up_new_task(struct task_struct \*p) {
struct rq_flags rf;
struct rq \*rq;

// 1. 获取当前 CPU 的运行队列（runqueue）
rq = __task_rq_lock(p, &amp;rf);

// 2. 初始化新进程的调度状态
p-&gt;state = TASK_RUNNING; // 标记进程为可运行状态

// 3. 将进程加入调度器的就绪队列
activate_task(rq, p, ENQUEUE_NOCLOCK); // 将 p 加入红黑树（CFS 调度类）

// 4. 检查是否需要触发抢占（preemption）
check_preempt_curr(rq, p, 0); // 对比新进程与当前进程的优先级

// 5. 释放运行队列锁
task_rq_unlock(rq, p, &amp;rf);


}

(3) 关键设计：写时复制（Copy-On-Write）

内存复制优化：在 copy_mm() 中，子进程共享父进程的地址空间，仅当写入时才复制物理页。

源码实现：通过设置页表项的只读标志触发缺页异常，具体逻辑在 mm/memory.c 的 do_wp_page() 函数中。

xv6 (教学用的操作系统，实现较简单)进程创建的核心源码

xv6 通过 fork() 系统调用创建进程，核心函数是 fork() 和 allocproc()。以下是关键代码：

(1) 用户态调用 fork()

用户程序调用 fork()，触发系统调用进入内核，最终调用 sys_fork()（定义在 kernel/sysproc.c）：

uint64 sys_fork(void) {
    return fork();
}

(2) 内核函数 fork()

int fork(void) {
    // 1. 分配进程结构体即PCB
    struct proc *np = allocproc();
    if (np == 0) return -1;

// 2. 复制父进程内存（直接复制，无 COW，为了简化实现）
if (uvmcopy(p-&gt;pagetable, np-&gt;pagetable, p-&gt;sz) &lt; 0) {
    freeproc(np);
    return -1;
}

// 3. 复制文件描述符表
for (int i = 0; i &lt; NOFILE; i++)
    if (p-&gt;ofile[i]) np-&gt;ofile[i] = filedup(p-&gt;ofile[i]);

// 4. 设置子进程上下文
np-&gt;sz = p-&gt;sz;
np-&gt;parent = p;
*(np-&gt;trapframe) = *(p-&gt;trapframe); // 复制陷阱帧
np-&gt;trapframe-&gt;a0 = 0;             // 子进程 fork 返回 0

// 5. 分配 PID 并加入就绪队列
acquire(&amp;np-&gt;lock);
np-&gt;state = RUNNABLE;
release(&amp;np-&gt;lock);
return np-&gt;pid;


}

(3) 分配进程结构体：allocproc()

static struct proc \*allocproc(void) {
// 1. 遍历进程表，找到 UNUSED 槽位（即找到空白PCB并分配）
for (p = proc; p < \&proc[NPROC]; p++) {
if (p->state == UNUSED) goto found;
}
return 0;

found:
// 2. 初始化进程控制块（PCB）
p->pid = allocpid();
p->state = USED;
p->kstack = KSTACK((int)(p - proc)); // 分配内核栈

// 3. 设置陷阱帧和上下文
p-&gt;trapframe = (struct trapframe *)p-&gt;kstack;
p-&gt;context.ra = (uint64)forkret;     // 返回到 forkret 函数
p-&gt;context.sp = p-&gt;kstack + PGSIZE;  // 内核栈指针
return p;


}

【2010-24】下列选项中，导致创建新进程的操作是（）。

I. 用户登录成功

II. 设备分配

III. 启动程序执行

A. 仅I和II B. 仅II和III C. 仅I和III D. I、II和III

答案

本题选C

【2021-24】下列操作中，操作系统在创建新进程时，必须完成的是（）。

Ⅰ. 申请空白的进程控制块

Ⅱ. 初始化进程控制块

Ⅲ. 设置进程状态为执行态

A. 仅Ⅰ

B. 仅Ⅰ、Ⅱ

C. 仅Ⅰ、Ⅲ

D. 仅Ⅱ、Ⅲ

答案

本题选B；

2.1.4.2 进程的终止¶

引起进程终止的事件主要有:

① 正常结束，表示进程的任务已完成并准备退出运行。

② 异常结束，表示进程在运行时，发生了某种异常事件，使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、运行超时、算术运算错、I/O 故障等。

③ 外界干预，指进程因外界的请求而终止运行，如操作员或操作系统干预、父进程请求和父进程终止。操作系统终止进程的过程如下:

根据被终止进程的标识符，检索出该进程的 PCB，从中读出该进程的状态。
若被终止进程处于运行状态，立即终止该进程的执行，将处理机资源分配给其他进程。
将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统。
将该 PCB 从所在队列(链表)中删除。

注意，不同操作系统的实现对进程终止的处理不完全相同，以上操作属于各OS共有的操作；（例如windows操作系统在进程终止时会终止其所有子进程，而类unix操作系统则不会）

Linux 进程终止的核心源码

Linux 进程终止通过 exit() 系统调用触发，最终由内核函数 do_exit() 处理。以下是关键源码和步骤：

(1) 入口函数：do_exit()

定义在 kernel/exit.c：

// kernel/exit.c
void __noreturn do_exit(long code) {
    struct task_struct *tsk = current;

// 1. 标记进程为僵尸状态（EXIT_ZOMBIE）
tsk-&gt;exit_state = EXIT_ZOMBIE;

// 2. 释放资源
exit_mm(tsk);        // 释放内存管理结构（mm_struct）
exit_files(tsk);     // 关闭打开的文件描述符
exit_fs(tsk);        // 释放文件系统资源
exit_thread(tsk);    // 清理线程上下文
//驱动层负责设备资源释放

// 3. 通知父进程（通过信号 SIGCHLD）
exit_notify(tsk);

// 4. 调度到其他进程（永不返回）
schedule();
panic(&quot;do_exit returned&quot;);


}

(2) 父进程通知与僵尸进程处理

exit_notify()通知父进程子进程已终止，若父进程已退出，则交由 init 进程（PID 1）接管：（由此可见父进程终止，不一定会终止所有的子进程）

// kernel/exit.c
static void exit_notify(struct task_struct \*tsk) {
struct task_struct \*parent = tsk->real_parent;
if (thread_group_empty(tsk)) {
// 父进程未等待子进程，则子进程成为僵尸进程
tsk->exit_signal = SIGCHLD;
list_add_tail(\&tsk->ptrace_entry, \&parent->ptraced);
} else {
// 父进程已终止，子进程由 init 接管
reparent_to_init(tsk);
}
}

xv6 进程终止的核心源码

xv6 的进程终止通过 exit() 系统调用触发，核心逻辑在 exit() 函数中实现。

(1) 入口函数：exit()

定义在 kernel/proc.c：

void exit(int status) {
    struct proc *p = myproc();

// 1. 关闭所有打开的文件
for (int fd = 0; fd &lt; NOFILE; fd++) {
    if (p-&gt;ofile[fd]) {
        fileclose(p-&gt;ofile[fd]);
        p-&gt;ofile[fd] = 0;
    }
}

// 2. 释放用户内存（页表和物理页）
uvmunmap(p-&gt;pagetable, 0, p-&gt;sz / PGSIZE, 1);
p-&gt;sz = 0;

// 3. 通知父进程
acquire(&amp;p-&gt;parent-&gt;lock);
if (p-&gt;parent-&gt;state == SLEEPING &amp;&amp; p-&gt;parent-&gt;chan == p) {
    wakeup(p-&gt;parent); // 唤醒等待的父进程
}
release(&amp;p-&gt;parent-&gt;lock);

// 4. 标记进程为僵尸状态（ZOMBIE）
acquire(&amp;p-&gt;lock);
p-&gt;state = ZOMBIE;
p-&gt;exit_status = status;
release(&amp;p-&gt;lock);

// 5. 调度到其他进程（永不返回）
sched();
panic(&quot;exit returned&quot;);


}

(2) 关键资源释放逻辑

释放内存（uvmunmap）
遍历进程页表，释放所有用户态物理页：

// kernel/vm.c
void uvmunmap(pagetable_t pagetable, uint64 va, uint64 size, int free_pages) {
for (uint64 a = va; a < va + size; a += PGSIZE) {
pte_t \*pte = walk(pagetable, a, 0);
if (pte && (\*pte & PTE_V)) {
uint64 pa = PTE2PA(*pte);
kfree((void*)pa); // 释放物理页
}
}
}

父进程唤醒
若父进程正在等待子进程退出（如调用 wait()），通过 wakeup() 唤醒父进程：

// kernel/proc.c
int wait(uint64 addr) {
for (;;) {
// 查找僵尸子进程
for (struct proc *np = proc; np < \&proc[NPROC]; np++) {
if (np->parent == p && np->state == ZOMBIE) {
// 复制子进程退出状态到用户空间
copyout(p->pagetable, addr, (char*)\&np->exit_status, sizeof(int));
freeproc(np); // 释放子进程资源
return np->pid;
}
}
sleep(p, \&p->lock); // 等待子进程退出
}
}

(3) 僵尸进程的最终清理

父进程调用 wait() 时，回收僵尸进程的资源（如 freeproc()）：

// kernel/proc.c
static void freeproc(struct proc *p) {
if (p->trapframe) kfree((void*)p->trapframe); // 释放陷阱帧
p->trapframe = 0;
if (p->pagetable) proc_freepagetable(p->pagetable, p->sz); // 释放页表
p->state = UNUSED; // 标记进程槽位为空闲
}

僵尸进程和孤儿进程(扩展了解)

僵尸进程（Zombie Process）

定义 : 僵尸进程是指 已经终止运行但尚未被父进程回收资源的进程。其进程描述符（PCB）仍保留在系统进程表中，以便父进程查询其终止状态。
产生原因 : 父进程创建子进程后，子进程执行完毕并通过 exit() 终止。父进程未调用 wait() 或 waitpid() 来获取子进程的终止状态。
特点

占用进程表资源：僵尸进程的 PID 和退出状态信息仍占用系统进程表。
无法被终止：僵尸进程已经死亡，无法通过信号（如 SIGKILL）杀死。
长期存在：如果父进程一直不回收，僵尸进程会持续存在，可能导致进程表耗尽。

解决方法

父进程调用 wait() 或 waitpid()：主动回收子进程资源。
忽略 SIGCHLD 信号：通过 signal(SIGCHLD, SIG_IGN) 通知内核无需保留子进程状态。
父进程终止：当父进程终止时，僵尸进程会被 init 进程接管并清理。

孤儿进程（Orphan Process）

定义 : 孤儿进程是指父进程提前终止，导致子进程被 init 进程（PID 为 1）接管。操作系统自动处理孤儿进程的资源回收。
产生原因 : 父进程在子进程终止前意外退出（如崩溃或被终止）。
特点 : 由 init 进程接管：操作系统将孤儿进程的父进程设为 init。自动回收：当孤儿进程终止时，init 进程会调用 wait() 回收其资源。无资源泄漏：不会长期占用进程表。
处理机制 : 操作系统自动将孤儿进程的父进程设置为 init。init 进程周期性调用 wait() 回收终止的子进程。

总结：

僵尸进程可能导致进程表资源耗尽，需及时处理。孤儿进程由系统自动管理，无需干预。

僵尸进程：父进程未及时回收的子进程残留，需手动处理。

孤儿进程：父进程意外终止后的子进程，由 init 自动接管。

以下是可能引起进程终止的事件的分类总结表格：

分类	事件/原因	描述	示例
正常终止	1. 主动退出	进程完成所有任务后主动调用退出函数。	调用 `exit()`或 `return`（C语言中从 `main`返回）。
	2. 主函数返回	程序从 `main`函数返回，操作系统隐式调用 `exit()`。	`int main() { return 0; }`
异常终止	1. 编程错误	代码逻辑错误导致进程崩溃。	除零操作、空指针解引用、内存越界访问（段错误 `SIGSEGV`）。
	2. 信号终止	接收到操作系统或其他进程发送的终止信号。	`SIGKILL`（强制终止）、`SIGTERM`（请求终止）、`SIGABRT`（程序主动中止）。
	3. 资源耗尽	进程所需资源超过系统限制。	内存不足（`ENOMEM`）、文件描述符耗尽。
外部干预	1. 用户强制终止	用户通过命令行或工具发送终止命令。	在终端按 `Ctrl+C`（发送 `SIGINT`）或使用 `kill -9 PID`（发送 `SIGKILL`）。
	2. 父进程终止	父进程终止后，子进程可能被操作系统终止（依赖系统实现，这样的OS有windows）。	父进程未处理子进程的终止状态，操作系统可能清理子进程（如部分嵌入式系统）。
系统级事件	1. 操作系统关闭	系统关机或重启时，所有用户进程被终止。	`shutdown -h now`或 `reboot`命令触发进程终止。
	2. 作业控制终止	作业控制命令终止进程（如 Shell 中的作业管理）。	在 Shell 中使用 `kill %1`终止后台作业。
进程间协作	IPC 终止信号	其他进程通过进程间通信（IPC）发送终止请求。	通过管道、信号或共享内存传递终止指令。

父进程与子进程¶

由上面学习的进程创建我们可知，若P1进程创建了P2进程，则P1是P2的父进程，P2是P1的子进程。

Note

父进程和子进程共享部分全局资源

某些操作系统全局资源是存在父子继承的，例如后面会学到的文件、管道、设备等，对这些特定的全局资源来说，子进程通常会继承父进程对它们的访问权限。

但是注意父子进程是两个不同的进程，因此其pid和PCB都不同，也不会共享地址空间，我们知道进程具有独立性，是一个能独立运行、独立获得资源和独立接受调度的基本单位，要是可以共享地址空间，父进程进程执行的过程中发生了中断，但是在它由于中断而被暂停执行的过程中，其子进程还在执行，并且更改了内存里的部分信息，这就破坏了父进程的现场，因此二者不会共享地址空间。

从进程创建的源码中我们可以看到：

在linux操作系统中，当父进程创建子进程时，使用fork()的话，子进程会复制父进程的地址空间，也就是虚拟地址空间的副本，其代码段、数据段、堆栈等完全相同（之后通过执行exec()系统调用替换子进程的代码段，加载新程序）。不过通常会使用写时复制（Copy-On-Write，COW）技术，也就是说，在fork之后，父子进程的虚拟地址空间映射到相同的物理内存页，但一旦任一进程试图修改某个页，就会触发复制，生成该页的副本，这样他们就不会共享同一物理页。不过，从虚拟地址空间的角度来看，初始时他们的地址空间内容是一样的，但各自独立，不是共享的。共享的话意味着一个进程修改了数据，另一个进程能看到变化，但fork后的子进程在修改数据时会有自己的副本，所以虚拟地址空间并不是共享的。

linux中的COW原理示意图

在xv6这种操作系统中，父进程创建子进程时，将父进程的 虚拟地址空间 完整复制到子进程的地址空间中，包括：代码段（Text）、数据段（Data）、堆（Heap） 和 栈（Stack）。但是每个虚拟页对应的物理页会被 逐页复制（非共享），确保父子进程内存完全独立。

Note

由以上两种操作系统创建进程的过程可知，父子进程在创建之初具有相同且独立的地址空间。父进程和子进程可以共享相同的代码和数据，但又能保持各自的独立性，使得进程间的数据隔离和安全性得以保证。

【2020-29】下列关于父进程与子进程的叙述中，错误的是（）。

A. 父进程与子进程可以并发执行

B. 父进程与子进程共享虚拟地址空间

C. 父进程与子进程有不同的进程控制块

D. 父进程与子进程不能同时使用同一临界资源

答案

本题选B

【2024-24】下列选项中，操作系统在终止进程时不一定执行的是

A. 终止子进程

B. 回收分配的内存资源

C. 撤销进程 PCB

D. 回收进程占用的设备

答案

本题选A，父进程终止时，终止子进程这一般是windows操作系统的操作，在linux操作系统中，父进程终止，子进程由 init 接管，可以从上面创建子进程和终止进程的源码看出；

父进程创建子进程和主程序调用子程序有什么不同?

区别	说明
并发性	子进程是父进程的一个完全独立的副本，它们有各自独立的地址空间，并且它们可以并发地（可能是并行地）运行。而子程序（也称为函数或方法）是主程序的一部分，当主程序调用子程序时，主程序需要等待子程序完成后才能继续执行
资源隔离	父进程和子进程有各自独立的地址空间，它们之间的数据是隔离的，一个进程的修改不会影响到另一个进程。而主程序和子程序共享同一个地址空间，子程序可以修改主程序中的数据
生命周期	子进程的生命周期独立于父进程，父进程可能在子进程之前结束，或者父进程可以决定何时结束子进程。而子程序的生命周期是被主程序所控制的，当主程序结束时，子程序也就结束了
创建和调用开销	创建子进程的开销通常比调用子程序的开销要大得多。这是因为创建子进程需要复制父进程的地址空间，并且需要在操作系统中进行进程调度。而调用子程序只需要分配一些栈空间和设置一些CPU寄存器即可
通信方式	父进程和子进程需要通过进程间通信（IPC）机制（如管道、信号、消息队列、共享内存等）来进行通信。而主程序和子程序由于在同一个地址空间中，可以直接通过参数传递、全局变量等方式来进行通信

在撤销父进程时,通常也会同时撤销其所有的子进程,这句话对吗?

这个问题的答案取决于具体的操作系统。

在Unix和类Unix系统（如Linux）中，当父进程结束时，并不会自动结束其所有的子进程。而是这些子进程会被init进程（进程ID为1）接管，这些被接管的子进程被称为孤儿进程（Orphaned Process）。孤儿进程会继续运行，直到它们自己结束。

在Windows系统中，父进程和子进程的关系与Unix类系统不同。在Windows中，父进程创建子进程时可以选择创建一个进程组，如果父进程结束，那么同属于一个进程组的所有子进程也会被结束。

2.1.4.3 进程的阻塞与唤醒¶

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新任务可做等，进程便通过调用阻塞原语(Block), 使自己由运行态变为阻塞态。可见，阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程(获得 CPU),才可能将其转为阻塞态。阻塞原语的执行过程如下:

找到将要被阻塞进程的标识号对应的 PCB.
若该进程为运行态，则保护其现场，将其状态转为阻塞态，停止运行。
把该 PCB 插入相应事件的等待队列，将处理机资源调度给其他就绪进程。

当被阻塞进程所期待的事件出现时,如它所期待的 I/O 操作已完成或其所期待的数据已到达，由有关进程(比如，释放该 I/O 设备的进程，或提供数据的进程)调用唤醒原语 (Wakeup), 将等待该事件的进程唤醒。唤醒原语的执行过程如下:

在该事件的等待队列中找到相应进程的 PCB.
将其从等待队列中移出，并置其状态为就绪态。
把该 PCB 插入就绪队列，等待调度程序调度。

注意：阻塞操作通常会与进程的调度和切换操作成对出现，进程如果在用户态下触发阻塞条件，也会经历类似于进程切换中的“用户态-内核态-内核态-用户态”的过程变化。

Linux 进程阻塞与唤醒的核心源码

Linux 通过 等待队列（Wait Queue） 和 调度器状态切换 实现进程的阻塞与唤醒。以下是关键源码和机制：

(1) 阻塞进程

当进程需要等待某个条件（如 I/O 完成、信号量释放）时，会主动调用阻塞函数。
核心函数：wait_event（定义在 include/linux/wait.h）

// kernel/sched/wait.c
void __sched wait_event(wait_queue_head_t wq, condition) {
    DEFINE_WAIT(__wait); // 定义等待队列条目
    for (;;) {
        prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE); // 标记进程为不可中断睡眠
        if (condition) // 检查条件是否满足
            break;
        schedule(); // 主动让出 CPU，触发调度
    }
    finish_wait(&wq, &__wait); // 从等待队列移除
}

关键步骤：

标记阻塞态：将进程状态设为 TASK_UNINTERRUPTIBLE（不可中断睡眠）或 TASK_INTERRUPTIBLE（可中断睡眠）。

首先，这两种状态均属于阻塞态。

TASK_INTERRUPTIBLE（可中断睡眠）：进程等待事件时，可以响应信号（如SIGKILL、SIGTERM）。

若接收到信号，进程会被唤醒并处理信号（如终止或执行信号处理函数）。

典型场景：用户空间的系统调用（如read()等待输入、sleep()等待超时）。

TASK_UNINTERRUPTIBLE（不可中断睡眠）：进程等待事件时，不响应任何信号（包括强制终止信号SIGKILL）。

内核强制确保关键操作完成后再处理信号（保证操作的原子性），避免系统状态不一致。

典型场景：内核必须完成的关键操作（如磁盘I/O、硬件交互）。

加入等待队列：通过 prepare_to_wait 将进程加入指定的等待队列。（不同事件有不同的等待队列）
调度切换：调用 schedule() 触发调度器，切换到其他进程。

(2) 唤醒进程

当条件满足（如数据到达、资源可用）时，唤醒等待队列中的进程。
核心函数：wake_up（定义在 kernel/sched/wait.c）

// kernel/sched/wait.c
void wake_up(wait_queue_head_t *wq) {
    struct wait_queue_entry *curr, *next;
    list_for_each_entry_safe(curr, next, &wq->head, entry) {
        // 遍历等待队列，唤醒每个进程
        curr->func(curr, TASK_NORMAL, 0, NULL); // 调用默认唤醒函数
    }
}

关键步骤：

遍历等待队列：找到所有需要唤醒的进程。
修改进程状态：将进程状态设为 TASK_RUNNING（就绪态）
加入就绪队列：通过 enqueue_task 将进程加入调度队列，等待被调度。

Linux 中的等待队列使用

// 驱动中等待数据到达的示例
DECLARE_WAIT_QUEUE_HEAD(data_ready_queue); // 定义等待队列

// 阻塞：等待数据
wait_event(data_ready_queue, data_available);

// 唤醒：数据到达后
wake_up(\&data_ready_queue);

Note

进程阻塞（Block）通常是由以下事件或操作引起的（408考试范围内）：

进程发起 I/O 操作等待 I/O 设备分配或等待其完成的过程中；
申请临界资源；
进程对值小于等于 0 的信号量执行 P 操作；
对管程中的条件变量执行 wait()操作；
试图创建进程却无法申请到足够的资源。

【该考点真题】¶

【2014-26】一个进程的读磁盘操作完成后，操作系统针对该进程必做的是（）。

A. 修改进程状态为就绪态

B. 降低进程优先级

C. 给进程分配用户内存空间

D. 增加进程时间片大小

答案

本题选A

【2015-25】下列选项中，会导致进程从执行态变为就绪态的事件是（）。

A. 执行 P (wait) 操作

B. 申请内存失败

C. 启动I/O设备

D. 被高优先级进程抢占

答案

本题选D，选项ABC都会进入阻塞态

【2018-27】下列选项中，可能导致当前进程 P 阻塞的事件是

Ⅰ. 进程 P 申请临界资源

Ⅱ. 进程 P 从磁盘读数据

Ⅲ. 系统将 CPU 分配给高优先权的进程

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅱ

D. Ⅰ、Ⅱ、Ⅲ

答案

本题选C

【2019-24】下列选项中，可能会将进程唤醒的事件是（）。

Ⅰ. I/O结束

Ⅱ. 某进程退出临界区

Ⅲ. 当前进程的时间片用完

A. 仅Ⅰ

B. 仅Ⅲ

C. 仅Ⅰ、Ⅱ

D. Ⅰ、Ⅱ、Ⅲ

答案

本题选C

【2022-28】下列事件或操作中，可能导致进程P由执行态变为阻塞态的是（）。

Ⅰ. 进程P读文件

Ⅱ. 进程P的时间片用完

Ⅲ. 进程P申请外设

Ⅳ. 进程P执行信号量的wait()操作

A. 仅Ⅰ、Ⅳ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅲ、Ⅳ

D. 仅Ⅰ、Ⅲ、Ⅳ

答案

本题选D

2.1.4.4 进程的调度与切换¶

进程调度指的是从就绪进程队列中选择一个进程作为目标切换进程，进程调度的结果通常是选出目标进程的 PCB。
进程切换指的是改变当前 CPU 中运行的进程的过程。在进程切换的过程中，当前状态将从运行态变为其它状态，目标就绪进程将从就绪态变更为运行态，目标进程通过进程调度来找到。
进程切换的具体过程

Note

进程除了寄存器以外的还有很多其他状态，它有变量，堆中的数据等等，但是所有的这些数据都在内存中，并且会保持不变。我们没有改变进程的任何栈或者堆数据。所以进程切换的过程中，cpu 中的寄存器是唯一的不稳定状态，且需要保存并恢复。而所有其他在内存中的数据会保存在内存中不被改变，所以不用特意保存并恢复。我们只是保存并恢复了cpu 中的寄存器，因为我们想在新的进程中也使用这组寄存器。
上图忽略了一小部分细节，P1进程在触发调度条件后，会切换到调度器进程，因此这里需要把P1的上下文保存到PCB1中，再去将调度器进程的上下文恢复到cpu里的寄存器中，之后执行schedu()即调度程序选择一个进程P2上处理机，保存schedu()的上下文并且切换P2的上下文到cpu的寄存器里。

【2024-25】在支持页式存储管理的系统中，进程切换时操作系统要执行的操作是

Ⅰ. 更新程序计数器的值

Ⅱ. 更新栈基址寄存器的值

Ⅲ. 更新页基地址寄存器的值

A. 仅Ⅲ

B. 仅I、Ⅱ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

答案

本题选D；具体解析自己看图；

一次完整的切换过程示例：进程 P0 响应时钟中断从用户态进入了内核态，其用户态上下文保存在了内核堆栈中。时钟中断会检查并更新当前进程 P0 的时间片，当发现该时间片用完时，操作系统会将 P0 从运行态变更为就绪态，并通过进程调度从就绪队列中选择出就绪进程 P1 的 PCB，随后，操作系统将当前进程 P0 的上下文保存在 PCB0 中，并从 PCB1 中取出记录的 P1 上下文放入各寄存器中（包括地址空间和堆栈地址等），此时 P1 处于什么状态呢？我们可以想象到，P1 在 PCB 中存入的上下文内容也类似于 P0 存入的内容，PCB1 中保存的上下文一定对应于 P1 上次刚刚发生切换时的状态，即处于某一次中断处理的内核态中。此后，P1 会继续执行，处理完各种中断异常后从 P1 的内核堆栈中取出 P1 的用户态上下文，中断返回 P1 的用户态，这便是从 P0 用户态切换到 P1 用户态的完整过程。

Note

中断响应与进程切换的上下文切换区别

中断响应保存和恢复上下文是分开进行的，分别位于中断响应和中断返回的过程中；而进程切换的上下文保存与恢复是连续进行的（两个不同进程之间）。
中断响应保存的上下文是中断前进程执行的上下文，进程切换保存的是当前中断服务程序正在执行过程中的上下文。更进一步说，中断响应维护的上下文可能是用户上下文（这个可能是因为多重中断的存在），进程切换维护的一定是内核态下的上下文。
中断响应不涉及地址空间切换（仅切换了内核态以及由用户堆栈切换到内核堆栈，中断前后仍然属于同一地址空间），进程切换涉及地址空间切换。
中断响应可能发生特权级切换，进程切换全程在内核态下进行。

注意区分CPU模式切换和进程切换

进程切换与模式切换都涉及到上下文的保存与恢复，但是它们有本质的不同。
模式切换发生在用户态下响应中断或异常（用户态->核心态）和处理完用户态下的中断异常后返回用户态（核心态->用户态）这两种情况下，本质工作是处理中断异常和中断异常返回。
模式切换是同一进程在自身用户态和内核态下的切换，二者共用地址空间，涉及到特权级的切换以及用户栈与内核栈的切换，而且只需要保存和恢复用户态的上下文（主要就是通用寄存器，PC、PSW和SP等，即所谓的断点和现场信息）不需要保存和恢复内核态的上下文。而进程切换发生在内核态，以上图 P0 切换到 P1 为例。在进程切换发生之前，一定存在某些事件使 P0 进程离开运行态，而这一处理本来就是在内核态下完成的，因此进程切换 P0 保存在 PCB 中的是 P0 处于内核态下的上下文，同样的道理，从 P1 的 PCB 中获取的上下文一定也是 P1 位于内核态下时存放的上下文。所以，进程的调度和切换均发生在内核态下，是从一个进程的内核态切换到另一个进程的内核态。

典型错误认知¶

错误理解: 认为进程切换是直接在用户态间切换，或PCB中保存的是用户态上下文
正确认知:
切换永远发生在两个进程的内核态之间
PCB保存的是进程在内核态被切换时的完整状态
用户态恢复依赖中断返回机制，不是进程切换的直接结果

进程调度和切换的一些Linux相关源码（帮助理解）

调度入口：__schedule

// kernel/sched/core.c
static void __sched notrace __schedule(bool preempt) {
    struct task_struct *prev, *next;
    // 1. 获取当前进程和下一个待运行进程
    prev = rq->curr;
    next = pick_next_task(rq, prev, &rf); // 通过调度类（如 CFS）选择下一个进程

// 2. 执行进程切换，如果调度程序选择的下一个进程仍然是该进程，就不用切换了
if (prev != next) {
    rq-&gt;curr = next;
    // 上下文切换
    context_switch(rq, prev, next, &amp;rf);
}


}

上下文切换：context_switch

// kernel/sched/core.c
static __always_inline struct rq \*
context_switch(struct rq \*rq, struct task_struct \*prev,
struct task_struct \*next, struct rq_flags \*rf) {
// 1. 切换地址空间（MMU 页表），中断处理就不用切换地址空间，
//而进程切换需要，因此我们说中断处理程序的执行不算进程切换
struct mm_struct \*mm = next->mm;
if (mm != prev->active_mm) {
switch_mm_irqs_off(prev->active_mm, mm, next);
}

// 2. 切换寄存器上下文（CPU 状态）
switch_to(prev, next, prev);
return rq;


}

struct mm_struct {
struct vm_area_struct \*mmap;        // 指向虚拟内存区域（VMA）链表的头节点
struct rb_root mm_rb;               // VMA 红黑树根节点（用于快速查找内存区域）
pgd_t \*pgd;                         // 页全局目录（Page Global Directory）指针（页表根）
atomic_t mm_users;                  // 使用该地址空间的进程数（如线程共享时计数）
atomic_t mm_count;                  // mm_struct 的引用计数（生命周期管理）
struct rw_semaphore mmap_sem;       // 读写信号量（保护 VMA 操作的并发访问）

unsigned long start_code, end_code; // 代码段起始和结束地址
unsigned long start_data, end_data; // 数据段起始和结束地址
unsigned long start_brk, brk;       // 堆的起始地址和当前堆顶
unsigned long start_stack;          // 栈的起始地址（栈向下增长）
unsigned long arg_start, arg_end;   // 命令行参数的起始和结束地址
unsigned long env_start, env_end;   // 环境变量的起始和结束地址

unsigned long total_vm;             // 总虚拟内存页数
unsigned long locked_vm;            // 被锁定（不可换出）的物理内存页数
unsigned long pinned_vm;            // 被固定（不可移动）的物理内存页数

struct list_head mmlist;            // 所有 mm_struct 的全局链表（用于系统级内存管理）
// ... 其他字段（如内存策略、反向映射、内存统计等）


};

在 Linux 操作系统中，__schedule() 是内核调度器的核心函数，负责实际的进程切换操作。触发 __schedule() 的情况可以分为 主动调度 和 被动调度 两类。以下是详细的触发场景及对应的源码分析

主动调度：进程主动让出 CPU，通常发生在需要等待资源（如 I/O、锁、信号量）时。

例如在执行P操作后，发现信号量≤ 0 时，会触发调度（阻塞自己）

// 用户态代码
sem_wait(sem); // 调用信号量等待函数

// 内核态流程（简化）
SYSCALL_DEFINE1(sem_wait, ...) {
// 1. 检查信号量状态
if (sem->count <= 0) {
// 2. 将进程状态设为阻塞，并加入等待队列
current->state = TASK_INTERRUPTIBLE;
add_wait_queue(\&sem->wait_queue, \&wait);
// 3. 主动触发调度
schedule(); // 调用调度程序
}
// 4. 信号量可用时恢复执行
sem->count--;
return 0;
}

被动调度：由外部事件（如中断、时间片耗尽）强制触发调度。

时间片耗尽(即上面图片中的例子)，通过定时器中断（scheduler_tick()）检测进程时间片是否耗尽，触发重新调度。

// kernel/sched/core.c
void scheduler_tick(void) {
struct rq \*rq = cpu_rq(cpu);
struct task_struct \*curr = rq->curr;

curr-&gt;sched_class-&gt;task_tick(rq, curr, 0); // 检查时间片
if (curr-&gt;sched_class == &amp;fair_sched_class) {
    if (check_preempt_tick(rq, curr)) // 是否需要抢占
        resched_curr(rq); // 标记需要调度
}


}

static void resched_curr(struct rq \*rq) {
set_tsk_need_resched(curr); // 设置需要调度标志
}

触发时机：

进程的时间片（time_slice）用完。
更高优先级的进程进入就绪队列。

在中断处理完成之后，检查是否需要调度（异常/系统调用执行完成也是如此）

// kernel/entry/common.c
static __always_inline void __syscall_exit_work(int ret, unsigned int flags) {
if (unlikely(flags & (_TIF_SIGPENDING | _TIF_NOTIFY_SIGNAL | _TIF_NEED_RESCHED)))
do_notify_resume(regs, flags); // 处理信号和调度
}

// 中断返回前检查是否需要调度
void irq_exit(void) {
if (!in_interrupt() && local_softirq_pending())
invoke_softirq();
tick_irq_exit();
rcu_irq_exit();
preempt_enable_no_resched();
if (need_resched()) // 检查是否需要调度
preempt_schedule_irq(); // 触发调度
}

唤醒高优先级进程（如 wake_up()）当高优先级进程被唤醒时，可能抢占当前进程。

// kernel/sched/core.c
void wake_up_new_task(struct task_struct \*p) {
if (p->prio < rq->curr->prio)
resched_curr(rq); // 触发抢占
}

2.1.5 进程间通信¶

Note

考纲原话：进程间通信(共享内存，消息传递，管道，信号)

由于每个进程的用户空间都是独立的，不能相互访问，这时就需要借助内核空间来实现进程间通信，原因很简单，每个进程都是共享一个内核空间。

Linux 内核提供了不少进程间通信的方式，其中最简单的方式就是管道，这里介绍匿名管道。匿名管道是特殊文件只存在于内存，没有存在于文件系统中，shell 命令中的「|」竖线就是匿名管道，通信的数据是无格式的流并且大小受限，通信的方式是单向的，数据只能在一个方向上流动，如果要双向通信，需要创建两个管道，再来匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失。另外，进程写入的数据都是缓存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时通信数据都遵循先进先出原则，不支持 lseek 之类的文件定位操作。

消息队列克服了管道通信的数据是无格式的字节流的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体是可以用户自定义的数据类型，发送数据时，会被分成一个一个独立的消息体，当然接收数据时，也要与发送方发送的消息体的数据类型保持一致，这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的，毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。

共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。

那么，就需要信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源，这种方式就是互斥访问。信号量不仅可以实现访问的互斥性，还可以实现进程间的同步，信号量其实是一个计数器，表示的是资源个数，其值可以通过两个原子操作来控制，分别是 P 操作和 V 操作。

与信号量名字很相似的叫信号，它俩名字虽然相似，但功能一点儿都不一样。信号是异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令），一旦有信号发生，进程有三种方式响应信号 1. 执行默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SIGSTOP，这是为了方便我们能在任何时候结束或停止某个进程。

前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。

以上，就是进程间通信的主要机制了。你可能会问了，那线程通信间的方式呢？

同个进程下的线程之间都是共享进程的资源，只要是共享变量都可以做到线程间通信，比如全局变量，所以对于线程间关注的不是通信方式，而是关注多线程竞争共享资源的问题，信号量也同样可以在线程间实现互斥与同步：

互斥的方式，可保证任意时刻只有一个线程访问共享资源；
同步的方式，可保证线程 A 应在线程 B 之前执行；

下面是对考纲中的IPC机制的详细介绍

2.1.5.1 共享内存¶

现代操作系统，对于内存管理，采用的是虚拟内存技术，也就是每个进程都有自己独立的虚拟内存空间，不同进程的虚拟内存映射到不同的物理内存中。所以，即使进程 A 和进程 B 的虚拟地址是一样的，其实访问的是不同的物理内存地址，对于数据的增删查改互不影响。

而共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要拷贝来拷贝去，传来传去，大大提高了进程间通信的速度, 这个过程需要通过特殊的系统调用实现。

段式及段页式内存共享原理示意图

共享内存通信工作过程

创建共享内存
系统调用：进程通过调用shmget（System V）或 shm_open（POSIX）创建共享内存。
内核在物理内存中分配一块连续区域，指定共享内存的访问权限（如读写权限）和大小。
附加共享内存到进程地址空间
系统调用：进程调用 shmat（System V）或 mmap（POSIX）将共享内存映射到自己的虚拟地址空间。
页表映射：内核修改进程的页表，将指定的虚拟地址范围映射到共享内存的物理页框。多个进程的虚拟地址可以不同，但最终指向同一物理内存。
进程获得共享内存的虚拟地址，一般来说，共享内存位于进程的用户地址空间，可直接通过虚拟地址访问。
读写共享内存
直接访问：进程像操作普通内存一样读写共享内存区域，无需系统调用，实现零拷贝高效通信。
数据可见性：一个进程的写入操作会立即对其他附加到该共享内存的进程可见（无缓存一致性协议时需手动同步）。
同步机制
必要性：共享内存（属于临界资源）本身不提供同步，需结合信号量、互斥锁等机制避免竞态条件。
示例：进程A写入数据前获取信号量锁，进程B在读取前等待同一信号量锁释放，确保数据一致性。
分离共享内存
系统调用：进程调用 shmdt（System V）或 munmap（POSIX）解除虚拟地址与共享内存的映射。
页表更新：内核移除该进程页表中对应的映射关系，但共享内存的物理内存仍保留。
销毁共享内存段
系统调用：通过 shmctl（System V）或 shm_unlink（POSIX）标记共享内存为待删除。
内核回收：当所有附加进程分离且无引用时，内核释放物理内存。

Note

共享内存位于进程的用户空间，而不是在内核空间
建立共享内存的操作在内核态，因为只有内核态下才可以修改页表
访问共享数据的操作是在用户态下进行，因为共享数据属于用户的用户地址空间。
特点：高效（省去数据在内核和用户空间之间的复制开销）、低延迟（直接内存访问速度接近本地内存操作）、使用时需要处理并发问题

【2023-30】进程R和S共享数据data，若date在R和S中所在页的页号分别为p1和p2，两个页所对应的页框号分别为f1和f2，则下列叙述中，正确的是（）。

A. p1 和 p2 一定相等，f1 和 f2 一定相等

B. p1 和 p2 一定相等，f1 和 f2 不一定相等

C. p1 和 p2 不一定相等，f1 和 f2 一定相等

D. p1 和 p2 不一定相等，f1 和 f2 不一定相等

解析

答案：C

本题考查的是分页存储管理中的内存共享机制。

物理框号（f1 和 f2）： “共享数据”在物理层面上意味着什么？意味着进程 R 和进程 S 的指针，最终都指向了内存条（物理内存）上的同一块绝对物理地址。既然是同一块物理内存，那么它们对应的物理页框（Page Frame）必然是同一个。因此，f1 一定等于 f2。
逻辑页号（p1 和 p2）： 操作系统为每个进程提供了一个独立的、隔离的虚拟地址空间。进程 R 和 S 都有各自独立的页表。共享的数据可以映射到进程 R 虚拟地址空间的任意一页（比如第 5 页，p1=5），同时也可以映射到进程 S 虚拟地址空间的任意一页（比如第 10 页，p2=10）。这两个进程怎么规划自己的虚拟空间是自由的，互不干涉。因此，p1 和 p2 不一定相等。

总结： 共享页的本质是“不同的逻辑页号映射到相同的物理页框号”。所以选 C：p1 和 p2 不一定相等，f1 和 f2 一定相等。

【2019-28】在分段存储管理系统中，用共享段表描述所有被共享的段。若进程P1和P2共享段S，下列叙述中，错误的是（）。

A. 在物理内存中仅保存一份段S的内容

B. 段S在P1和P2中应该具有相同的段号

C. P1和P2共享段S在共享段表中的段表项

D. P1和P2都不再使用段S时才回收段S所占的内存空间

解析

答案：B

本题考查的是分段存储管理系统中的段共享机制。你可以把“段”和上一题的“页”作类比，原理是高度一致的。

我们逐个选项来分析：

A. 在物理内存中仅保存一份段S的内容（正确）： 这是“共享”的根本目的。为了节省内存空间，无论有多少个进程共享这段代码或数据，物理内存中都只需要保存一份真正的副本。
B. 段S在P1和P2中应该具有相同的段号（错误，故选此项）： 和上一题的逻辑页号同理，进程 P1 和 P2 拥有各自独立的二维逻辑地址空间（段号 + 段内偏移）。进程 P1 可以把共享段 S 编为自己的 0 号段，而进程 P2 可以把它编为自己的 3 号段。它们在各自段表中的“段号”是独立的，不需要也不一定相同。它们只需要在各自的段表项中，将该段的物理基址指向同一块物理内存即可。
C. P1和P2共享段S在共享段表中的段表项（正确）： 为了管理共享段，操作系统通常会维护一张共享段表。当 P1 和 P2 都共享段 S 时，系统会在共享段表中为段 S 建立一个表项，记录该段的物理基址、长度以及当前的共享计数，P1 和 P2 都会关联到这个表项。
D. P1和P2都不再使用段S时才回收段S所占的内存空间（正确）： 承接 C 选项，共享段表项中有一个“共享计数”。P1 使用时计数器 +1，P2 使用时再 +1。当 P1 结束运行，计数器 -1；此时由于 P2 还在用，计数器不为 0，物理内存不会被回收。只有当所有共享该段的进程都不再使用它（计数器降为 0）时，操作系统才会真正回收该段占用的物理内存。

Warning

小 tips： 无论是分页还是分段，“共享”的核心原则永远是：物理地址唯一（必须同源），逻辑地址独立（可以不同）。记住这个原则，这类题目就能迎刃而解。

基于内核空间的共享内存：

上面的共享内存通信，所建立的用于进程通信的空间位于进程的用户地址空间，因此可以直接在用户态下读写；而我们之前提到过，用户的虚拟地址空间分为用户空间和内核空间，事实上，每个进程的虚拟地址空间中，内核空间部分映射到相同的物理内存区域，即操作系统的代码和全局数据。无论哪个进程切换到内核态，访问的内核代码和全局数据（如中断向量表、系统调用表、设备驱动、内存管理结构等）都是同一份物理内存的映射；

映射方式：通过页表机制，所有进程的内核空间页表项指向相同的物理页框。
优势：避免了内核代码和数据的冗余拷贝，节省内存并保持一致性。

Note

注意，虽然说内核空间是共享的，但是每个进程在内核态执行时需要使用独立的内核栈，用于保存进程处于内核态时内核函数调用的返回地址、局部变量和中断上下文，每个进程的内核栈指针位于该进程的PCB中；

2.1.5.2 消息传递¶

直接通信

在通信进程之间建立直接通信链路，一条通信链路对应一对通信进程，链接可以是单向/双向的；

send(p1,message)，发送信息给进程P1;

receive(P0,message)，接收进程P0发来的消息；

间接通信

不一定非要通过消息队列来间接通信，也可以在内核空间里创建一个共享中间实体“信箱”，每次发送和接收消息都通过信箱以此完成进程间的通信

通过操作系统维护的消息队列实现进程间的消息接收和发送

- 每个消息队列都有一个唯一的标识
- 只有共享了相同消息队列的进程，才能够通信

通信链路的属性

- 只有共享了相同消息队列的进程，才建立连接
- 连接可以是单向或双向
- 消息队列可以与多个进程相关联
- 每对进程可以共享多个消息队列

消息队列示意原理

消息传递还有两种模式，即阻塞模式和非阻塞模式：

阻塞模式：也被称为同步操作。在这种模式下，发送者在发送了消息之后会被阻塞，直到接收者收到消息；接收者如果没有收到消息也会被阻塞，直到有消息可以接收。

非阻塞模式：也被称为异步操作。在这种模式下，发送者在发送了消息之后可以直接进行其他操作，不会被阻塞；同样，接收者在没有收到消息的情况下也可以进行其他操作。

缺点分析：

消息队列不适合比较大数据的传输，因为在内核中每个消息体都有一个最大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。在 Linux 内核中，会有两个宏定义 MSGMAX 和 MSGMNB，它们以字节为单位，分别定义了一条消息的最大长度和一个队列的最大长度。
消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据到用户态的过程。

2.1.5.3 管道通信¶

Note

自测判断题：（都会了就不用看了）

管道位于进程的用户空间之中，可直接在用户态下读管道；
管道与共享内存这两种IPC机制都自己实现了同步/互斥机制，使用的时候用户不需要考虑用信号量/互斥锁等机制保证同步互斥。
管道是存放在磁盘中的一种“特殊的文件”。
管道作为一种特殊的“文件”，和文件一样，支持定位到某个具体位置进行读或写操作。
在操作系统中，管道这个内核数据结构包含有互斥锁、两个等待队列、读/写指针等元素
对管道的读操作需要互斥进行，因为读完数据就消失了，因此同一时刻只能有一个读进程对管道执行读操作；但是对管道进行写操作就不用互斥进行了，支持多个写进程同时写管道。
在利用管道文件通信时，可以使用一部分操作系统为文件提供的系统调用接口，如write()、read()、close()
当所有引用管道的文件描述符都被关闭后，管道内未被读取完的数据会被持久化到磁盘之中；
管道支持进程之间的单向数据传输；
一般来说，利用管道进行通信的进程之间具有血缘关系；
父进程在创建了管道之后又创建了两个子进程，子进程之间利用管道进行通信，当父进程被撤销时，这两个子进程之间的管道也被内核撤销；
管道通信是以消息为单位进行写入和读出的；

答案

错误管道文件位于内核区中，读写操作需要通过系统调用在内核态下读或写；
错误，管道自身以及通过mutex互斥锁和两个等待队列实现了同步与互斥，但是共享内存自身没有同步互斥机制，一般需要和信号量一同使用；
错误，管道在内存之中；
错误，管道只能读head(读指针)指向的数据，只能在tail（写指针）指向的区域写入数据（队尾写入，队头读出），不支持 lseek 之类的文件定位操作。
正确，管道（Pipe）的同步与互斥机制就是通过mutex互斥锁，等待队列（rd_wait 和 wr_wait）实现，读写操作需要用到读写指针（也可以理解为循环队列的队头、队尾指针）；
错误，对管道的读写操作都需要互斥进行，同一时刻，管道只允许一个读进程对管道执行读操作或一个写进程对管道执行写操作；
正确；
错误，当所有引用管道的文件描述符都被关闭后，内核直接回收管道的缓冲区资源；
正确；
正确；
错误，在此情景之下，持有管道读/写端文件描述符的进程数量都不为0，只有当 readers 和 writers 均为 0 时，内核才会销毁管道并释放其缓冲区内存
错误，管道通信是以字符流为单位进行写入和读出的；

管道有两种类型：匿名管道与有名管道，这里我们着重介绍一下匿名管道，了解原理之后记住相应的特点即可。

匿名管道是 Linux 系统中一种基于内核缓冲区的进程间通信（IPC）机制，主要用于具有亲缘关系的进程（如父子进程、兄弟进程）之间的单向数据流通信。其核心原理是通过共享的内核缓冲区和文件描述符继承实现数据传输。下面介绍具体工作流程及原理：

创建管道
系统调用：通过 pipe(int pipefd[2]) 创建管道，返回两个文件描述符：
pipefd[0]：读端，用于从管道读取数据。
pipefd[1]：写端，用于向管道写入数据。
内核数据结构：内核为每个管道分配一个 环形缓冲区（即循环队列）和两个文件描述符（读端和写端）。
进程间共享
继承文件描述符：父进程调用 pipe() 创建管道后，通过 fork() 创建子进程。由前面的创建进程的学习我们可以知道，子进程会复制父进程的地址空间，因此子进程继承父进程的文件描述符表，从而共享同一管道的读写端。如下图所示

如图实现了父子两个进程使用一个管道可以完成半双工通信。此时，父进程可以通过fd[1]给子进程发消息，子进程通过fd[0]读。子进程也可以通过fd[1]给父进程发消息，父进程用fd[0]读。

首先区分一下全双工与半双工通信，在半双工通信中，通信双方可以在同一信道上轮流发送和接收数据，但是不能同时进行发送和接受数据。也就是说，某一时刻信道只能用于一个方向的传输，例如对讲机就是典型的半双工，当一个人按下通话键说话时，对面只能听不能同时说话；只有当另一方停止发送并释放信道，才可以发送信息；而全双工允许通信双方在同一时刻同时发送和接受数据，例如打电话就是全双工。

Note

例如在上图中，父进程将想要发送给子进程的数据写入管道之后，必须等子进程将数据全部读取完毕（注意从管道读数据是一次性操作,读完就失效），之后父进程才能执行读数据操作，如果不这样的话，父进程会读取自己写入的数据使其失效，从而使通信出错；因此父进程和子进程通过管道进程信息传递是半双工的，在同一时间段时间内只能单向传输数据；

因此为了方便，一般在Linux中，父进程关闭写端（close(pipefd[1])），子进程关闭读端（close(pipefd[0])），形成单向数据流（父写子读或子写父读）。

若需要双向通信（全双工），需创建两个管道。

两个管道实现进程之间的全双工通信

数据读写机制
写入操作（write）：数据从用户空间拷贝到内核缓冲区。若缓冲区满，写操作阻塞，直到有空间。
读取操作（read）：数据从内核缓冲区拷贝到用户空间。若缓冲区空，读操作阻塞，直到有数据。
原子性：小于 PIPE_BUF（通常 4096 字节）的写入保证原子性（即多个进程同时写时，数据不会交叉混合）。
生命周期
依赖进程：管道随进程的终止而销毁。当所有引用管道的文件描述符被关闭后，内核回收缓冲区资源。
自动销毁：即使某些进程未正确关闭描述符，当所有进程终止时，内核仍会清理管道。

以上便是匿名管道的核心工作原理。

匿名管道的核心源码（伪代码，展示原理）

/**
 * 本代码并非真实的内核源码，而是一个用户态的模拟程序，用于清晰地展示匿名管道的几个关键组成部分和工作流程：
 * 1. 环形缓冲区 (Circular Buffer): 用于在内存中暂存数据。
 * 2. 互斥锁 (Mutex): 保证在任何时刻只有一个进程能读或写管道，确保数据一致性。
 * 3. 条件变量 (Condition Variable): 模拟内核中的等待队列，用于实现进程的同步。
 * - 当管道为空时，读者在此等待。
 * - 当管道为满时，写者在此等待。
 * 4. 引用计数: 跟踪有多少文件描述符指向管道的读/写端，用于决定何时释放管道资源。
 * 5. fork() 继承: 演示子进程如何继承父进程的文件描述符，从而实现父子通信。
 */

#define PIPE_SIZE 4096 // 内核中管道的默认大小通常是4KB或更大

typedef struct {
    char buffer[PIPE_SIZE]; // 1. 环形缓冲区，用于存放数据
    size_t head;            // 读指针 (指向队头)
    size_t tail;            // 写指针 (指向队尾)
    size_t data_size;       // 管道中当前的数据量

    int readers_count;      // 2. 指向读端的打开的文件描述符数量 (读引用计数)
    int writers_count;      //    指向写端的打开的文件描述符数量 (写引用计数)

    pthread_mutex_t mutex;  // 3. 互斥锁，保护整个管道数据结构
    pthread_cond_t not_full; // 4. 条件变量，当管道不满时通知写者
    pthread_cond_t not_empty;//    条件变量，当管道不空时通知读者
} pipe_buffer;

/**
 * 模拟 pipe() 系统调用：创建并初始化管道的核心数据结构。
 * @return pipe_buffer* 指向新创建的管道缓冲区的指针
 */
pipe_buffer* create_pipe() {
    pipe_buffer* p = (pipe_buffer*)malloc(sizeof(pipe_buffer));
    if (!p) return NULL;

    p->head = 0;
    p->tail = 0;
    p->data_size = 0;
    // 刚创建时，有一个读端和一个写端被打开
    p->readers_count = 1;
    p->writers_count = 1;

    pthread_mutex_init(&p->mutex, NULL);
    pthread_cond_init(&p->not_full, NULL);
    pthread_cond_init(&p->not_empty, NULL);

    printf("[Kernel] 管道创建成功，位于内存地址 %p\n", p);
    return p;
}

/**
 * @param p 管道缓冲区
 * @param data 要写入的数据
 * @param len 要写入的长度
 * @return ssize_t 实际写入的字节数
 */
ssize_t write_to_pipe(pipe_buffer* p, const char* data, size_t len) {
    pthread_mutex_lock(&p->mutex); // --- 获取互斥锁,进入临界区 ---

    // 如果没有进程在读取管道，继续写入没有意义。
    // 内核会向写进程发送 SIGPIPE 信号，这里我们简单地返回错误。
    if (p->readers_count == 0) {
        printf("[Writer] 错误：所有读端都已关闭！\n");
        pthread_mutex_unlock(&p->mutex);//释放互斥锁
        return -1; // Broken pipe
    }

    size_t total_written = 0;
    while (total_written < len) {
        // 等待管道有可用空间
        while (p->data_size == PIPE_SIZE) {
            printf("[Writer] 管道已满，等待读者...\n");
            // 阻塞写者，并原子地释放锁
            pthread_cond_wait(&p->not_full, &p->mutex);

            // 被唤醒后，再次检查读端是否已关闭
            if (p->readers_count == 0) {
                printf("[Writer] 等待时读端关闭，写入失败。\n");
                pthread_mutex_unlock(&p->mutex);
                return -1;
            }
        }

        // 计算本次可以写入多少数据
        size_t write_len = PIPE_SIZE - p->data_size;
        if (write_len > (len - total_written)) {
            write_len = len - total_written;
        }

        // 写入数据到环形缓冲区(其数据结构是一个循环队列)
        for (size_t i = 0; i < write_len; ++i) {
            p->buffer[p->tail] = data[total_written + i];
            p->tail = (p->tail + 1) % PIPE_SIZE;
        }

        p->data_size += write_len;
        total_written += write_len;

        printf("[Writer] 成功写入 %zu 字节, 管道中现有 %zu 字节\n", write_len, p->data_size);

        // 唤醒可能正在等待的读者
        pthread_cond_signal(&p->not_empty);
    }

    pthread_mutex_unlock(&p->mutex); // --- 退出临界区 ---
    return total_written;
}

/**
 * @param p 管道缓冲区
 * @param buffer 用于存放读取数据的缓冲区
 * @param len 希望读取的长度
 * @return ssize_t 实际读取的字节数，0表示EOF (所有写者关闭)
 */
ssize_t read_from_pipe(pipe_buffer* p, char* buffer, size_t len) {
    pthread_mutex_lock(&p->mutex); // --- 进入临界区 ---

    // 等待管道中有数据可读
    while (p->data_size == 0) {
        // 如果管道为空，且已经没有任何进程会向里写入数据，
        // 那么表示读到了文件末尾(EOF)。
        if (p->writers_count == 0) {
            printf("[Reader] 管道为空且所有写端都已关闭，读取结束(EOF)。\n");
            pthread_mutex_unlock(&p->mutex);
            return 0; // EOF
        }
        printf("[Reader] 管道为空，等待写者...\n");
        // 阻塞读者，并原子地释放锁
        pthread_cond_wait(&p->not_empty, &p->mutex);
    }

    // 计算本次可以读取多少数据
    size_t read_len = p->data_size;
    if (read_len > len) {
        read_len = len;
    }

    // 从环形缓冲区读取数据
    for (size_t i = 0; i < read_len; ++i) {
        buffer[i] = p->buffer[p->head];
        p->head = (p->head + 1) % PIPE_SIZE;
    }

    p->data_size -= read_len;
    printf("[Reader] 成功读取 %zu 字节, 管道中剩余 %zu 字节\n", read_len, p->data_size);

    // 唤醒可能正在等待的写者
    pthread_cond_signal(&p->not_full);

    pthread_mutex_unlock(&p->mutex); // --- 退出临界区 ---
    return read_len;
}

/**
 * @param p 管道缓冲区
 * @param is_reader true表示关闭读端, false表示关闭写端
 */
void close_pipe_end(pipe_buffer* p, int is_reader) {
    pthread_mutex_lock(&p->mutex);
    if (is_reader) {
        p->readers_count--;
        printf("[Kernel] 一个读端关闭，剩余 %d 个读端。\n", p->readers_count);
        // 如果最后一个读端关闭，需要唤醒所有可能在等待的写者，
        // 让它们知道写入已无意义，从而返回错误。
        if (p->readers_count == 0) {
            pthread_cond_broadcast(&p->not_full);
        }
    } else {
        p->writers_count--;
        printf("[Kernel] 一个写端关闭，剩余 %d 个写端。\n", p->writers_count);
        // 如果最后一个写端关闭，需要唤醒所有可能在等待的读者，
        // 让它们知道不会再有新数据，从而读到EOF。
        if (p->writers_count == 0) {
            pthread_cond_broadcast(&p->not_empty);
        }
    }
    pthread_mutex_unlock(&p->mutex);
}

int main() {
    // 1. 父进程在内核中创建一个管道
    //    pipe() 系统调用返回两个文件描述符: fds[0]为读端, fds[1]为写端
    pipe_buffer* pipe = create_pipe();
    if (!pipe) {
        perror("创建管道失败");
        return 1;
    }

    pid_t pid = fork();

    if (pid < 0) {
        perror("fork失败");
        return 1;
    }

    if (pid > 0) { // --- 父进程 ---
        printf("--- 进入父进程 (PID: %d) ---\n", getpid());
        // 父进程打算写入数据，所以它应该关闭自己的读端。
        // 这是一个非常重要的实践，可以确保在子进程关闭写端后，
        // 内核能正确判断所有写端都已关闭。
        close_pipe_end(pipe, 1); // 关闭读端

        const char* msg = "你好，子进程！我来自父进程。";
        printf("[Parent] 准备写入消息: \"%s\"\n", msg);
        write_to_pipe(pipe, msg, strlen(msg));

        // 父进程写完后，关闭自己的写端。
        // 这会向管道的读端发送一个 EOF 信号。
        close_pipe_end(pipe, 0); // 关闭写端

        // 等待子进程结束
        wait(NULL);
        printf("--- 父进程结束 ---\n");

    } else { // --- 子进程 ---
        printf("--- 进入子进程 (PID: %d) ---\n", getpid());
        // fork() 后，子进程继承了管道的所有文件描述符。
        // 子进程打算读取数据，所以它应该关闭自己的写端。
        close_pipe_end(pipe, 0); // 关闭写端

        char read_buffer[100];
        ssize_t bytes_read;

        // 循环读取，直到读到EOF(返回0)
        bytes_read = read_from_pipe(pipe, read_buffer, sizeof(read_buffer) - 1);
        if (bytes_read > 0) {
            read_buffer[bytes_read] = '\0'; // 添加字符串结束符
            printf("[Child] 读取到消息: \"%s\"\n", read_buffer);
        }

        // 子进程读完后，关闭自己的读端。
        close_pipe_end(pipe, 1); // 关闭读端

        printf("--- 子进程结束 ---\n");
        exit(0);
    }

    // 最后的资源清理
    // 当所有读写端都关闭后，内核会释放管道缓冲区
    free(pipe);

    return 0;
}

struct pipe_inode_info {
    struct mutex mutex;          /* 互斥锁，保护管道操作 */
    wait_queue_head_t rd_wait;   /* 读等待队列 */
    wait_queue_head_t wr_wait;   /* 写等待队列 */
    unsigned int head;           /* 缓冲区写入位置 */
    unsigned int tail;           /* 缓冲区读取位置 */
    struct page *pages;          /* 指向物理页的指针（环形缓冲区） */
    unsigned int bufs;           /* 缓冲区数量 */
    unsigned int bufsize;        /* 每个缓冲区的大小 *
    unsigned int readers;        /* 读引用计数 */
    unsigned int writers;        /* 写引用计数 */
    unsigned int waiting_writers;/* 等待写入的进程数 */
    struct pipe_buffer *bufs;    /* 管道缓冲区数组 */
     ......
};

管道（Pipe）的同步与互斥机制通过mutex互斥锁，等待队列（rd_wait和wr_wait）实现：

mutex互斥锁确保同一时间只有一个进程（或线程）可以修改管道的缓冲区状态（如更新 head 和 tail 指针）；保护缓冲区分配、释放和环形队列的完整性
例如在读管道pipe_read() 和写管道pipe_write() 函数中，所有对缓冲区的操作都需先获取 mutex；
管道通过等待队列管理因缓冲区空或满而阻塞的进程：
rd_wait：读等待队列，当管道空时，读取进程加入此队列并休眠。
wr_wait：写等待队列，当管道满时，写入进程加入此队列并休眠。
唤醒机制：
- 写入数据后，唤醒 rd_wait 中的读进程。
- 读取数据后，唤醒 wr_wait 中的写进程。
在读写操作中，内核通过循环检查缓冲区状态，结合互斥锁和等待队列实现同步：

此外，还需要保证读写操作的原子性，例如P1通过管道写数据想要发送给P2，则在写入数据的过程中，不能被其他进程打断，并且只有当进程P2将该数据完全读完，其他进程才能读或写，否则会导致P2接收的数据有误。

上面介绍的匿名管道只能在有亲缘关系的进程之间通信，而命名管道则可以在无亲缘关系的进程之间通信，不过那个不重要，这里不做过多介绍；

Note

通过上面介绍的管道的原理，我们可以总结以下特点（考点）

管道通信双方可以按照生产者-消费者模型进行通信，管道中写入的数据一旦读出就会从管道消失（可以理解为从队列中出队）；
管道是一种特殊的文件，是在内核中的环形数据缓冲区（数据结构为循环队列）；
管道只能读head(读指针)指向的数据，只能在tail（写指针）指向的区域写入数据（队尾写入，队头读出），不支持 lseek 之类的文件定位操作。
读空管道，进程阻塞；写满管道，进程阻塞；
同一时刻，管道仅支持半双工通信，若要实现全双工通信，需要在进程之间建立两个管道；
对管道的读写操作需要互斥进行，当有一个进程对管道进行读/写时，其他想要读/写的进程会被阻塞；

管道之所以被称为“特殊的文件”，是因为它在操作方式上类似于文件，需要通过文件描述符和系统调用进行读写（可以像操作普通文件一样使用read()、write()、open()等）；但是它与文件又有以下不同之处：

管道存储在内存之中，而普通文件通常存放在磁盘之中；

普通文件可以支持多个进程同时读，而管道的读写操作都需要互斥，同一时刻管道只允许一个进程读管道或者写管道；

管道中的数据读完就失效了，而普通文件读操作不会对它产生影响；

【2014-31】下列关于管道(Pipe)通信的叙述中，正确的是（）。【可以看一下我对D选项的解释】

A. 一个管道可实现双向数据传输

B. 管道的容量仅受磁盘容量大小限制

C. 进程对管道进行读操作和写操作都可能被阻塞

D. 一个管道只能有一个读进程或一个写进程对其操作

解析

本题选择C；

A，一个管道仅支持半双工通信，若想实现双向数据传输，可以在进程之间建立两个管道；

B，管道位于内存的内核区域，与磁盘容量无关系；

C，读空管道和写满管道都会阻塞；

D，缺少条件在同一时刻，如果D选项改为在同一时刻只能有一个读进程进程或一个写进程对管道操作，那么则正确；事实上，一个管道允许多个读进程或写进程对其操作，例如一个父进程在创建完管道之后，fork（）了若干个子进程，那么这些子进程都拿到了这个管道的文件描述符，因此它们都可以通过管道进行通信，只不过如果某个进程对管道执行读操作或者写操作的时候，会拿到管道的互斥锁mutex，别的进程如果还想操作管道，由于获取锁失败，就只能等待，只有当前进程操作完之后释放了锁，别的进程才有机会读或者写管道。

2.1.5.4 信号（2025年大纲新增考点）（待更新）¶

信号的概念
信号是一种异步的、非阻塞的通信机制（进程不需要通过任何操作等待信号到达），用于通知接收进程某个事件已经发生。例如，SIGINT信号通常由 Ctrl+C触发，用于终止进程。
信号（Signal）也叫“用户态中断”，用于异步通知进程某个事件的发生，每个信号都有一个唯一的编号和一个对应的处理动作。当某个信号发生时，内核会向相应的进程发送该信号，并触发预设的信号处理函数或执行默认操作。Linux信号也可以称为软中断，是在软件层次上对中断机制的一种模拟。在原理上，一个进程收到一个信号与处理器收到一个中断请求可以说是一样的
信号通常用于简单的事件通知，如终止进程、暂停执行等，而不适合用于复杂的数据传输任务。
信号可以直接进行用户空间进程和内核进程之间的交互，内核进程也可以利用它来通知用户空间进程发生了哪些系统事件
信号的来源
硬件来源：
- 硬件信号触发：某些硬件操作可能会触发特定的信号。例如，浮点除零操作会触发SIGFPE信号。
- 硬件异常：硬件异常，如内存访问越界（段错误，SIGSEGV）或非法指令，也会导致信号的产生。
软件来源：
- 系统调用：通过系统提供的函数，如kill()、raise()、alarm()和setitimer()等，可以显式地向进程发送信号。
- 用户输入：用户通过终端输入特定的字符组合（如Ctrl+C），操作系统会向当前前台进程发送SIGINT信号。
- 系统事件：系统内部发生的事件，如子进程退出，会导致父进程收到SIGCHLD信号。
- 定时器：通过alarm()或setitimer()设置的定时器到期时，会向进程发送SIGALRM信号。
信号的特点
简洁性：信号是一种轻量级的进程间通信方式，不涉及复杂的数据传输。
异步性：信号可以在任何时间发送给进程，不需要进程主动去检查或等待。
可配置性：进程可以指定对信号的处理方式，包括忽略、捕获并自定义处理函数或执行默认操作。
实际应用中的使用场景：
程序终止：通过发送SIGTERM信号来请求进程正常退出，给予进程机会进行资源释放和状态保存。
用户交互：通过发送SIGINT信号来中断长时间运行的命令行程序，使用户能够及时终止不必要的操作。
守护进程管理：在服务管理系统中，通过发送不同信号来控制守护进程的启动、停止和重启。
错误检测与处理：利用信号来报告和处理程序运行时遇到的严重错误，如段错误（SIGSEGV）。
信号分类

在linux系统中，通过kill -l命令，可以查看所有的信号

常见的信号：

- `SIGINT`：终端中断信号，通常由用户输入中断字符（如Ctrl+C）产生。
- `SIGKILL`：强制终止信号，无法被捕获或忽略。
- `SIGTERM`：默认的终止信号，进程可以捕获并进行清理工作。
- `SIGCHLD`：子进程终止时，父进程收到的信号。
- `SIGALRM`：定时器信号，由alarm函数设置。

6. 信号传递和响应

在 Linux 中，信号的传递流程通常遵循以下步骤：

信号产生：信号可以由内核、操作系统或者应用程序生成。常见的信号产生方式包括用户在终端按下键盘快捷键产生的信号，以及系统调用执行过程中出现的异常情况。
信号传递：一旦信号被产生，内核会把信号传递给目标进程。目标进程可以是正在等待信号的进程，或者正在执行的进程。如果信号没有被阻塞并且未被忽略，内核将会将信号传递给进程。
信号处理：一旦进程接收到信号，内核会检查信号的处理方式。根据注册的信号处理方式，可以有以下几种情况：
- 忽略信号：即对信号不做任何处理，但是两个信号不能忽略: SIGKILL 以及 SIGSTOP 。
- 捕捉信号：当信号发生时，执行用户自定义的信号处理函数。
- 执行默认操作：对于大多数信号，操作系统定义了默认的行为。这些默认行为通常是终止进程，生成核心转储文件，或暂停进程执行等。当进程收到信号时，如果没有设置信号的自定义处理函数，将会执行操作系统默认的行为。
信号处理过程：如果信号的处理方式是执行自定义的信号处理函数，进程将会调用该函数来处理信号。处理函数可以完成一系列操作，比如修改全局变量、执行清理操作等。在信号处理函数执行期间，进程可能会被阻塞在信号处理函数中。
信号返回：一旦信号处理函数执行完毕，程序将会从信号处理函数中返回，程序恢复执行之前的代码。

注：信号传递不支持排队，当在很短时间内传递多个相同信号，该信号只会被处理一次。

在 Linux 中，信号的传递流程通常是由内核负责进行管理和调度，确保信号被准确传递给目标进程，并按照指定的处理方式进行处理。对于开发人员来说，可以通过信号处理函数来实现对信号的处理和响应，以应对不同的信号产生场景

2.1.5.5 IPC机制对比¶

特性	共享内存	消息传递（eg消息队列）	（匿名）管道	信号（Signal）
数据形式	原始字节流（直接内存访问）	结构化消息（带类型/优先级）	字节流（无结构）	简单整数信号（无数据或少量数据）
通信方向	双向	双向（消息队列）	单向（半双工）	单向（发送→接收）
同步需求	需要（如信号量、互斥锁）	部分需要（如阻塞接收）	内核自动同步（缓冲区阻塞）	无（异步通知）
性能	极高（零拷贝）	中（数据拷贝开销）	中（内核缓冲区拷贝）	极高（无数据传输）
复杂度	高（需管理同步和内存映射）	中（需处理消息格式）	低（API简单）	低（API简单）
进程关系	任意进程	任意进程（消息队列）	仅亲缘进程（父子/兄弟）	任意进程（需知道PID）
持久性	进程分离后需重新映射	内核维护（消息队列）	随进程终止销毁	无（瞬时触发）
典型应用场景	高频数据交换（eg视频处理）	微内核	简单线性通信（Shell管道）	事件通知（进程终止、用户中断）

2.1.6 线程和多线程模型¶

2.1.6.1 线程的基本概念：¶

引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量；而引入线程的目的是减少程序在并发执行时所付出的时空开销，提高操作系统的并发性能。\ 对于多进程的方式，存在以下问题：
进程之间如何通信，共享数据？
维护进程的系统开销较大，如创建进程时，分配资源、建立 PCB；终止进程时，回收资源、撤销 PCB；进程切换时，保存当前进程的状态信息；

那到底如何解决呢？需要有一种新的实体，满足以下特性：

- 实体之间可以并发运行；
- 实体之间共享相同的地址空间；

这个新的实体，就是线程( Thread )，线程之间可以并发运行且共享相同的地址空间

线程可以理解为“轻量级进程”，它是一个基本的CPU执行单元，也是程序执行的最小单元，由线程ID（操作系统用于识别和管理线程的唯一标识符）、程序计数器（表示线程当前正在执行的代码地址)、寄存器集合（包含线程当前的工作状态）、栈（每个线程都有自己的栈，用于存储局部变量和函数调用的上下文信息。这是线程之间不共享的部分）组成。这些即是线程自己的线程上下文。

在同一进程中的所有线程共享大部分进程资源，包括以下内容：
代码段 (.text)：所有线程执行的是同一份程序代码，就像所有工人都看着同一份蓝图工作。
数据段 (.data/.bss)：所有线程共享进程的全局变量和静态变量。一个线程修改了全局变量，其他线程能立刻看到变化。
堆 (Heap)：整个进程的堆内存是共享的。一个线程分配的内存（通过 malloc 或 new），其他线程只要能获得其指针，就可以访问。
系统资源：进程持有的资源对所有线程都可见，例如：
- 打开的文件描述符
- 网络套接字
- 信号处理程序
- 进程ID和父进程ID

【2011-25】在支持多线程的系统中，进程P创建的若干个线程不能共享的是（）。

A. 进程P的代码段

C. 进程P的全局变量

B. 进程P中打开的文件

D. 进程P中某线程的栈指针

答案

本题选D；

【2024-28】若进程 P 中线程 T 先打开文件，得到文件描述符 fd，再创建线程 Ta 和 Tb，则下列资源中，线程 Ta 与 Tb 可共享的是

Ⅰ. 进程 P 的地址空间

Ⅱ. 线程 T 的栈

Ⅲ. 文件描述符 fd

A. 仅I

B. 仅I、Ⅲ

C. 仅Ⅱ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

答案

本题选B；

2.1.6.2 线程的上下文切换：¶

在前面我们知道了，线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。

所以，所谓操作系统的任务调度，实际上的调度对象是线程，而进程只是给线程提供了虚拟内存、全局变量等资源。

对于线程和进程，我们可以这么理解：

当进程只有一个线程时，可以认为进程就等于线程；
当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源，这些资源在上下文切换时是不需要修改的；

另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。

线程上下文切换的是什么？

这还得看线程是不是属于同一个进程：

当两个线程不是属于同一个进程，则切换的过程就跟进程上下文切换一样；
当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据；(与进程相比，线程之间的上下文切换有一点主要区别：地址空间保持不变(即不需要切换当前使用的页表))

所以，线程的上下文切换相比进程，开销要小很多(因为页表切换在上下文切换花销中占比较大)。

2.1.6.3 线程与进程的比较：¶

	进程	线程
定义	进程是操作系统资源分配的基本单位，是程序在一个数据集上的一次动态执行过程。	线程是程序执行流的最小单位，是进程中的一个实体，是被系统独立调度和分派的基本单位。
调度	操作系统负责进程的调度。	在用户空间的线程库可以进行线程调度，也可以由操作系统负责调度。（同一进程，线程切换不引起进程切换；不同进程，线程切换则进程切换）
资源	资源分配的单位（进程是拥有资源的基本单位)，每个进程有自己独立的内存空间和系统资源。	线程自己不拥有系统资源，只拥有一点在运行在必不可少的资源；同一进程中的所有线程共享进程的所有资源如内存、文件描述符等。
地址空间	进程间地址空间相互独立（内存保护）	同一进程内的线程共享进程的地址空间（线程之间可通过地址空间相互通信）
并发性	进程间是独立的，一个进程的执行不会影响到其他进程。	同一进程内，不同进程间的线程都可以并发，由于线程切换(保留CPU现场)比进程切换(保留进程现场)开销小，因此引入线程后系统并发度提高，吞吐量更大
系统开销	进程切换需要保存进程现场，开销大	线程切换只需要保存少量CPU寄存器内容，开销小(线程包含CPU现场)
通信方式	进程间通信(IPC)复杂，通常需要操作系统提供的机制，如管道、消息队列、信号量等。	线程间通信相对简单，可以直接读写属于同一进程的数据
独立性	进程间是独立的，一个进程的崩溃不会影响其他进程。	一个线程的崩溃可能会导致整个进程崩溃。
相似之处	进程控制块PCB；进程标识号；有就绪态/运行态/阻塞态；父进程创建/撤销子进程；不同进程可以执行相同程序；	线程控制块TCB；线程标识号；有就绪态/运行态/阻塞态；父线程创建/撤销子线程；不同线程可以执行相同程序；
支持多处理机系统	对于传统单线程进程，不管有多少处理机，进程只能运行在一个处理机上。	对于多线程进程，可以将一个进程的多个线程分配到多个处理机上执行

线程和进程之间的另一个主要区别在于栈，在简单的传统进程地址空间模型(单线程进程)中只有一个栈，通常位于地址空间的底部；然而，在多线程的进程中，每个线程独立运行，因此每个线程都有一个栈，假设有一个多线程的进程它有两个线程，结果地址空间看起来不同。

从图中我们可以看到，两个栈跨越了进程的地址空间。因此，所有位于栈上的变量、参数、返回值和其他放在栈上的东西，将被放置在线程本地存储的地方，即相关线程的栈。

由于每一个线程都有自己的栈，因此，线程局部变量应该是线程私有的，其他线程不应该访问。线程之间共享数据，值要在堆(heap)或者其他全局可访问的位置。

由于线程之间共享地址空间，其实同一进程的不同线程甚至可以修改别的线程的栈里面的数据，但是同一进程的线程属于同一用户，一般来说，用户在编程时会自己主动避免多个线程之间修改栈数据的行为；

对于，线程相比进程能减少开销，体现在：

线程的创建时间比进程快，因为进程在创建的过程中，还需要资源管理信息，比如内存管理信息、文件管理信息，而线程在创建的过程中，不会涉及这些资源管理信息，而是共享它们；
线程的终止时间比进程快，因为线程释放的资源相比进程少很多；
同一个进程内的线程切换比进程切换快，因为线程具有相同的地址空间（虚拟内存共享），这意味着同一个进程的线程都具有同一个页表，那么在切换的时候不需要切换页表。而对于进程之间的切换，切换的时候要把页表给切换掉，而页表的切换过程开销是比较大的；
由于同一进程的各线程间共享内存和文件资源，那么在线程之间数据传递的时候，就不需要经过内核了，这就使得线程之间的数据交互效率更高了；\ 所以，不管是时间效率，还是空间效率线程比进程都要高。

2.1.6.4 线程的组织、状态与转换¶

线程控制块TCB(记录控制和管理线程的信息)：

名称	说明
线程标识符TID	为每一个线程赋予一个唯一的线程标识符
一组寄存器	包括程序寄存器PC、状态寄存器和通用寄存器的内容
线程运行状态	用于描述线程正处于何种运行状态
优先级	描述线程执行的优先程度
线程专有存储区	用于线程切换时存放现场保护信息，和与该线程相关的统计信息
栈指针	指向用户自己栈的指针和指向核心栈的指针

与进程一样，线程在运行时，也具有执行态、就绪态、阻塞态三种基本状态；

2.1.6.6 线程的实现方式：¶

用户级线程(ULT):

用户级线程是指由用户程序自己管理和调度的线程，而不是由操作系统内核来管理和调度。用户级线程的创建、同步、调度等操作都是由运行在用户空间的线程库（如 POSIX Pthreads库或 Java线程库）来完成的，而不需要内核的介入。

用户级线程

用户级线程的特征

不依赖于操作系统的内核
内核不了解用户线程的存在
可用于不支持线程的多进程操作系统
在用户空间实现的线程机制
每个进程有私有的线程控制块（TCB）列表，用来跟踪记录它各个线程状态信息（PC、栈指针、寄存器等）
TCB由线程库函数维护
同一进程内的线程操作的效率更高
因为用户级线程的管理和调度完全在用户空间进行，用户线程的切换是由线程库函数来完成的, 所以不需要进行用户态到内核态的切换，也就不需要系统调用的开销。这使得用户级线程的创建、销毁和切换等操作比内核级线程更快
允许每个进程拥有自已的线程调度算法
用户可以根据自己的程序需求，自定义线程的调度策略。例如，一些实时系统可能需要优先级调度，而某些计算密集型任务可能需要采用时间片轮

然而，用户级线程也有一些缺点：

因为用户级线程对操作系统内核是不可见的，所以如果一个线程阻塞（例如，它正在等待I/O操作完成），那么整个进程（包括所有的线程）都会被阻塞。
不利于多处理器：因为操作系统不知道用户级线程的存在，那么它就不能把不同的线程调度到不同的处理器上运行，从而无法利用多处理器的并行处理能力。
当一个线程开始运行后，除非它主动地交出 CPU 的使用权，否则它所在的进程当中的其他线程无法运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用户线程不是由操作系统管理的。
由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢；
需要程序员管理：程序员需要明确管理这些线程的生命周期和调度，这增加了编程的复杂性。
内核级线程(KLT):

内核级线程，或者称为内核线程，是由操作系统内核来管理和调度的线程。内核线程的创建、同步和调度等操作都是由内核来完成的，因此，内核线程可以直接利用操作系统提供的调度算法、优先级管理等机制。内核空间为每一个内核级线程设置一个线程控制块，内核根据该控制块感知某线程的存在，并对其加以控制。

内核级线程

内核级线程的特征：

由内核维护PCB和TCB
线程执行系统调用而被阻塞不影响其他线程
线程的创建、终止和切换相对较大
因为线程的管理和调度是由内核完成的，所以创建、销毁和切换线程等操作需要通过系统调用来进行。这意味着这些操作需要在用户态和内核态之间进行切换，因此比用户级线程的相应操作更为耗时
因为内核了解并控制所有的内核级线程，所以它可以将不同的线程调度到多个处理器上运行，从而充分利用多处理器的并行处理能力
以线程为单位进行CPU时间分配
多线程的进程可获得更多CPU时间

【2012-31】下列关于进程和线程的叙述中，正确的是（）。

A. 不管系统是否支持线程，进程都是资源分配的基本单位

B. 线程是资源分配的基本单位，进程是调度的基本单位

C. 系统级线程和用户级线程的切换都需要内核的支持

D. 同一进程中的各个线程拥有各自不同的地址空间

答案

本题选A；

【2019-23】下列关于线程的描述中，错误的是（）。

A. 内核级线程的调度由操作系统完成

B. 操作系统为每个用户级线程建立一个线程控制块

C. 用户级线程间的切换比内核级线程间的切换效率高

D. 用户级线程可以在不支持内核级线程的操作系统上实现

答案

本题选B；

解答：

A正确。在内核级线程中，调度由操作系统负责，包括线程的创建、切换和终止等。

B错误。操作系统并不总是为每个用户级线程建立一个独立的线程控制块。在某些实现中，操作系统可能只为内核级线程建立线程控制块，而不为用户级线程建立独立的线程控制块。内核级线程由操作系统直接支持和管理。操作系统为每个内核级线程建立一个线程控制块，用于存储和管理线程的状态、上下文和其他相关信息，以便进行调度和资源分配等操作。用户线程与内核线程的对应关系包括多对一、一对一、多对多。

C正确。用户级线程的切换通常比内核级线程的切换效率高，因为用户级线程的切换只涉及用户空间的操作，无需涉及内核态和内核切换的开销。

D正确。用户级线程通常是在用户空间中实现和管理的，而不依赖于操作系统的直接支持。用户级线程库负责管理用户级线程的创建、调度和同步等操作。在这种情况下，用户级线程的控制块是由用户级线程库维护的，而不是由操作系统创建和维护。因此用户级线程可以在不支持内核级线程的操作系统上实现。

本题选B。

组合方式：

有些系统使用组合方式的多线程实现。在组合实现方式中，内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程。一些内核级线程对应多个用户级线程，这是用户级线程通过时分多路复用内核级线程实现的。同一进程中的多个线程可以同时在多处理机上并行运行，且在阻塞一个线程时不需要将整个进程阻塞，所以这种组合方式能结合KLT和ULT的优点，并且克服各自的不足。

简单来说，进程的一部分线程依赖用户线程库来实现，在用户态下管理；一部分线程通过内核态实现，由操作系统管理。

2.1.6.8 多线程模型¶

多对一模型
将多个用户级线程映射到一个内核级线程，且一个进程只被分配一个内核级线程，这些用户级线程一般属于一个进程，线程的调度和管理由用户空间的线程库完成，仅当用户级线程需要访问内核时才将其映射到一个内核级线程上，因此效率更高，但是任一时刻只允许一个线程进行映射。
如果一个线程执行阻塞系统调用，那么整个进程将会阻塞；
一对一模型
对每个线程都用一个内核线程来管理，该模型在一个线程执行阻塞系统调用时，能够允许另一个线程继续执行，所以它提供了比多对一模型更好的并发功能；它也允许多个线程并行运行在多处理器系统上。这种模型的唯一缺点是，创建一个用户线程就要创建一个相应的内核线程。由于创建内核线程的开销会影响应用程序的性能，所以这种模型的大多数实现限制了系统支持的线程数量。
多对多模型
将n个用户级线程映射到m个内核级线程，要求n>m;

2.2 处理机调度¶

2.2.1 调度的概念¶

调度的层次：

调度策略在操作系统中起着非常关键的作用，主要可以分为三类：高级调度（也被称为作业调度）、中级调度（也被称为内存调度）以及低级调度（也被称为进程调度或CPU调度）。

高级调度（作业调度）：这是最高级别的调度。其主要任务是控制“作业池”（即用户提交的一系列作业）中等待执行的进程数量。当一个新作业（即程序）提交给系统执行时，作业调度器决定是否接受这个作业，并决定何时将其从作业池移入内存，进行执行。这种调度主要在多道批处理系统中使用。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。
中级调度（内存调度）：中级调度器负责把暂时不运行的进程调度到硬盘上（即换出），此时进程的状态为挂起态，以便为新的、即将运行的进程释放内存。需要运行的进程则从硬盘换入内存，这个过程被称为换入/换出（Swapping）。
低级调度（进程调度或CPU调度）：这是最低级别的调度。其主要任务是选择内存中的一个进程，分配给CPU进行执行。

三层调度的联系、对比

	要做什么	调度发生在…	发生频率	对进程状态的影响
高级调度(作业调度)	按照某种规则从后备队列中选择合适的作业将其调入内存，并为其创建进程	外存→内存(面向作业)	最低	无→创建态→就绪态
中级调度(内存调度)	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存→内存(面向进程)	中等	挂起态→就绪态等等
低级调度(进程调度)	按照规则从就绪队列中选择一个进程为其分配处理机	内存→CPU	最高	就绪态→运行态

2.2.2 调度的实现（调度器/调度程序(scheduler)）¶

调度程序（Scheduler）是操作系统中负责管理进程执行的关键组件。它的主要任务是根据特定的调度算法决定就绪队列中的哪个进程应该获得CPU资源。调度程序通常包括三个主要部分：排队器（Queuing），分派器（Dispatcher），和上下文切换器（Context Switcher）。

排队器（Queuing）：排队器负责管理进程队列，根据进程的优先级、到达时间等因素对进程进行排序。排队器可以将进程分为不同的队列，如就绪队列、等待队列、阻塞队列等。就绪队列中的进程已准备好运行，等待分派器将它们分配给CPU。等待队列和阻塞队列中的进程则因为I/O操作或其他资源需求而暂时无法执行。

排队器会根据调度算法（如先来先服务、短作业优先、优先级调度等）对进程进行排序，以便分派器能够根据这些排序决策分配CPU资源。

分派器（Dispatcher）：执行完调度程序根据调度算法从就绪队列中选出一个进程之后，将处理机资源分配给它。
上下文切换器（Context Switcher）：将当前进程的内核上下文保存到它的PCB中，然后从刚被分配到处理机的进程的PCB中取出上下文，之后便切换到了新进程，可以继续执行；

2.2.3 调度的时机与调度方式（抢占式/非抢占式）¶

非抢占式调度
定义：一个进程除非运行结束或者自己主动放弃CPU，否则不会被其它进程抢占CPU。
调度时机：进程运行结束；进程由于发起I/O等主动阻塞，主动放弃处理机使用权；

若不考虑进程执行yield系统调用主动释放处理机资源，那么非抢占式调度只会出现运行态到退出态或阻塞态的转变，不可能会发生运行态到就绪态的转变；

特点：
调度不太频繁，CPU利用率一般更高；（没有运行态与就绪态的切换开销）
实时性比较差，一般用于批处理操作系统，不能用于大部分实时操作系统和分时操作系统。
系统开销小，整体吞吐量更大；
抢占式调度
定义：进程在执行过程中，可能因为时间片用完或者有更高优先级进程进入就绪态而被抢占CPU。
调度时机：
当前进程主动放弃CPU（运行结束或者进入阻塞态）
当前进程时间片用完或有更高优先级的进程进入就绪态。
特点：
频繁调度，实时性强；
可以防止一个进程长时间独占处理器的恶意行为
可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。
等待时间和响应时间更短，用户体验好，适用于分时操作系统，实时操作系统。

抢占式调度的具体实现方式（介绍了调度的时机）

在进程的PCB中，为进程设置一个标志位，例如linux中PCB里的TIF_NEED_RESCHED（记作NEED_RESCHED）标志位，其含义为“需要重新调度”，当某个进程的 TIF_NEED_RESCHED 标志被设置时，表示内核需要尽快触发调度器scheduler，重新选择下一个要运行的任务。

什么时候设置这个标志位？
时间片耗尽：当前任务的时间片用完时，内核会设置 NEED_RESCHED，以便让其他任务运行。

时间片到期，触发抢占式调度

当有更高优先级的进程进入就绪态，会设置 NEED_RESCHED
例如当前进程fork()一个优先级更高的子进程

系统调用创建优先级更高的子进程触发抢占调度

处理I/O后唤醒阻塞进程，发现其优先级比当前运行进程优先级更高，设置NEED_RESCHED

I/O完成唤醒对应阻塞进程，发现优先级更高触发抢占调度

内核什么时候响应该标志（抢占点的触发时机）？

在中断/异常/系统调用处理结束返回用户空间时，内核会检查当前进程的 NEED_RESCHED 标志，若有效则触发调度；

中断处理返回的宏观流程

中断服务程序（ISR）主体执行完毕：这是中断处理的业务逻辑部分，比如处理一个磁盘读写完成的信号。

准备退出中断 (ret_from_intr)：当中断服务程序的主体完成后，会跳转到一个通用的、体系结构相关的退出路径。在Linux中，这个入口点通常被称为ret_from_intr或类似的名字。

检查need_schedule标志并决定是否调度

执行调度或返回原进程：

如果需要调度：则执行调度程序（schedule()），选择下一个要运行的进程，并进行上下文切换。

如果不需要调度：则直接准备返回到被中断的进程。

恢复现场和屏蔽字。

执行iret(或eret等) 指令，真正从硬件上返回。

什么时间点不能进行调度？
当前进程处于中断处理过程中；（中断处理通常涉及到操作系统的核心功能和关键资源，是系统工作的一部分，逻辑上不属于某一进程，不应被剥夺处理机资源。）
进程在访问操作系统内核临界区中；(注意在用户级别的临界区中可以进行进程调度)
禁用中断（屏蔽中断过程中）
原语执行过程中；（如加锁、解锁、中断现场保护、恢复等原子操作。原子操作不可中断一气呵成，连中断都要屏蔽，更不应该进行进程调度与切换。）

【2012-30】若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（）。

A. 在进程结束时能进行处理机调度

B. 创建新进程后能进行处理机调度

C. 在进程处于临界区时不能进行处理机调度

D. 在系统调用完成并返回用户态时能进行处理机调度

答案

本题选C；

A 进程结束，下处理机，触发调度选择一个就绪进程上处理机，正确；

B 创建新进程后，将其修改为就绪进程，如果新进程优先级更高，且当前调度为抢占式调度，那么会触发调度；

C 进程处于内核临界区不能进行调度，但是如果是用户级临界区，例如进程请求打印机打印，获取打印机资源成功并开启打印，由于打印机是临界资源，因此此时进程处于临界区，但是进程会由于等待I/O主动阻塞，触发调度，因此C错误；

D，在中断/异常/系统调用的返回路径，会检查当前进程的 NEED_RESCHED 标志，若有效则触发调度，因此D正确；

【2021-27】下列事件中，可能引起进程调度程序执行的是（）。

Ⅰ. 中断处理结束

Ⅱ. 进程阻塞

Ⅲ. 进程执行结束

Ⅳ. 进程的时间片用完

A. 仅Ⅰ、Ⅲ

B. 仅Ⅱ、Ⅳ

C. 仅Ⅲ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ和Ⅳ

答案

本题选D。

Ⅰ正确。在中断/异常/系统调用处理结束返回用户空间时，内核会检查当前进程的 NEED_RESCHED 标志，若有效则触发调度；

Ⅱ正确。进程阻塞进入阻塞队列，让出CPU，触发调度；

III正确。例如某进程执行结束后，就绪队列中有尚未执行的进程，CPU会执行进程调度程序调度该处于就绪态的进程。

IV正确。例如进程的时间片用完，就绪队列中有尚未执行的进程，CPU会执行进程调度程序调度该处于就绪态的进程。

综上，Ⅰ、Ⅱ、Ⅲ和Ⅳ正确。

临界区的不同调度策略

访问内核临界区：eg调度器访问就绪队列，这就是访问内核临界区，就绪队列就是内核数据结构，只能操作系统内核才可以访问。\ 在操作系统中，无论是在内核级别还是用户级别，临界区的基本概念都是相同的：它是一段访问共享资源或数据的代码，这段代码必须被互斥地执行。这是为了防止并发访问导致的数据不一致和其他并发问题。\ 然而，内核临界区和用户级别的临界区在一些方面有所不同：

不同之处	说明
关键性和影响范围	内核临界区通常涉及到操作系统的核心功能，如文件系统操作、内存管理、设备驱动等。如果在这些区域出现错误，可能会导致整个系统崩溃。相反，用户级别的临界区通常只影响单个应用程序的行为
同步机制	在内核临界区中，通常使用更底层的同步机制，如禁用中断、自旋锁（spinlock）等，来保证临界区的互斥访问。而在用户级别的临界区中，通常使用操作系统提供的高级同步原语，如互斥量（mutex）、信号量（semaphore）等
调度策略	当进程在内核临界区中运行时，通常不会进行进程调度，以防止数据不一致和系统不稳定。但在用户级别的临界区中，操作系统通常会根据需要进行进程调度，以提高系统的响应性和性能。(例如如果当前进程请求使用打印机这一临界资源，进程当前处于临界区，进程在等待I/O的过程中阻塞自己，从而可以进行处理机调度，这样可以提高系统性能)

闲逛进程()：（Idle Process），又称为空闲进程或空闲任务，是操作系统中一种特殊的进程，用于在系统中没有其他进程需要运行时占据CPU资源。闲逛进程的主要目的是确保CPU始终有任务可执行，从而避免CPU处于空闲状态。

闲逛进程的特点如下：

优先级最低：闲逛进程的优先级通常设置为最低，这意味着只有在没有其他进程需要运行时，闲逛进程才会被调度执行。一旦有其他进程需要CPU资源，闲逛进程会立即让出CPU，让其他进程执行。
持续运行：闲逛进程通常会持续运行，直到有其他进程需要CPU资源。在某些操作系统中，闲逛进程可能会执行一些简单的任务，如清理内存或执行系统维护操作。但在大多数情况下，闲逛进程仅执行一个空循环，不执行任何实际操作。
只运行在内核态下；
资源占用最小：不需要CPU以外的资源，不会阻塞；

2.2.4 调度算法的评价指标(调度准则)¶

CPU 利用率：使CPU尽可能地忙碌。 \(CPU利用率 =\frac{CPU有效工作时间 }{总时间}\)
系统吞吐量：吞吐量表示的是单位时间内 CPU 完成进程的数量，长作业的进程会占用较长的 CPU 资源，因此会降低吞吐量，相反，短作业的进程会提升系统吞吐量； \(系统吞吐量 =\frac{总共完成了多少道作业}{ 总共花费时间}\)
作业周转时间：周转时间是指从进程提交到进程完成的时间段 (即进程运行+阻塞时间+等待时间的总和），一个进程的周转时间越小越好；周转时间 = 作业完成时间 – 作业提交时间 (对于用户来说，更关心自己单个作业的周转时间)
平均周转时间 =\(\frac{各作业周转时间之和 }{作业数}\) (对于操作系统来说，更关心系统的整体表现，因此更关心所有作业周转时间的平均值)
带权周转时间 =\(\frac{作业周转时间}{作业实际运行的时间}\)(必然大于等于1，也是越小越好，对于实际运行时间相同的两个作业周转时间短的带权周转时间更短，用户满意度越高；周转时间相同的作业实际运行时间更长的，用户越满意)
平均带权周转时间 =\(\frac{各作业带权周转时间之和}{作业数}\)
等待时间：CPU调度算法并不影响进程运行和执行I/O的时间，它只影响进程在就绪队列中因等待所需的时间。等待时间为进程处于就绪态的时间之和；
响应时间：用户提交请求到系统第一次产生响应所花费的时间，在交互式系统中，响应时间是衡量调度算法好坏的主要标准。

对于作业在后备队列（也被称为作业池）中等待的时间，通常被称为等待进入内存的时间，或者进入就绪队列的等待时间。这个时间通常被视为另一个指标，因为进程在后备队列中等待是因为当前内存资源不足，无法将更多的进程载入内存。在这种情况下，进程还未达到可以被执行的就绪状态。所以，通常说的等待时间是指进程已经进入就绪队列，但是由于CPU正在执行其他进程，还未轮到该进程执行的时间。

2.2.5 典型的调度算法¶

首先介绍一下CPU繁忙型作业和I/O繁忙型作业：

CPU繁忙型作业和I/O繁忙型作业是两种不同类型的计算任务，它们在资源需求和执行特性上有所差异。

CPU繁忙型作业（CPU-bound）：\ CPU繁忙型作业主要依赖于CPU的计算能力，这类作业的执行速度受到CPU性能的限制。这些作业通常包含大量的计算任务，如数学运算、数据处理、图形渲染等。在这类作业中，CPU的使用率较高，而I/O操作相对较少。

举例：科学计算、图像处理、机器学习训练等。

I/O繁忙型作业（I/O-bound）：\ I/O繁忙型作业主要依赖于输入/输出（I/O）操作的速度，这类作业的执行速度受到I/O设备性能的限制。这些作业通常涉及大量的数据读写操作，如文件读写、网络通信、数据库查询等。在这类作业中，I/O操作频繁，而CPU计算任务相对较少。

举例：文件传输、Web服务器、数据库操作等。

【2012-29】一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它们的计算和I/O操作顺序如下：

P1：计算60ms，I/O80ms，计算20ms

P2：计算120ms，I/O40ms，计算40ms

若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。

A. 240ms

B. 260ms

C. 340ms

D. 360ms

答案

P2比P1晚5ms到达，P1先占用CPU。设P1到达时刻为0，画出作业运行的甘特图如下：

采用图(a)或图(b)的画法都可以。

本题选B。

【2016-24】某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是（）。

A. 15ms

B. 17ms

C. 22ms

D. 27ms

答案

设3个作业分别为P1、P2、P3。设初始时刻为0，P1先执行，画出作业运行的甘特图（也称横道图）如下：

采用图(a)或图(b)的画法都可以。

本题选B。

先来先服务调度算法¶

先来先服务（First-Come, First-Served，FCFS）调度算法是一种最简单的调度算法，属于不可剥夺（非抢占式）算法，它既可用于作业调度，也可用于进程调度。

在作业调度中，该算法每次从后备队列中选择最先进入该队列的一个或几个作业，将它们调入内存分配必要的资源，创建进程并放入就绪队列中。

在进程调度中，该算法按照进程到达的先后顺序，依次将进程分配给执行，直到进程执行完毕或者被阻塞(例如请求I/O)。在FCFS算法中，进程的等待取决于它前面的进程时间和到达时间。

FCFS算法的优点是简单易实现，公平，适用于长作业和低交互型进程，不会导致饥饿。

缺点是：

排在长作业(进程)后面的短作业(进程)需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好，即对长作业有利，对短作业不利（相对于SJF和高响应比）。
I/O资源和CPU资源的利用率较低：CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也等待

为什么说FCFS算法有利于CPU繁忙型作业，不利于I/O繁忙型作业？

FCFS（先来先服务）调度算法对长作业有利，因为它按照作业到达的顺序进行调度，不考虑作业的长度。对于CPU繁忙型作业，因为它需要大量的CPU时间进行计算，而很少请求I/O操作，FCFS可以确保这种作业得到足够的CPU时间来完成，避免了因为被频繁中断或上下文切换而导致的执行效率低下。而I/O繁忙型作业在CPU处理时，需频繁地请求I/O操作，导致操作完成后还要重新排队等待调度。因此这样看来CPU繁忙型作业更接近于我们所说的长作业，I/O繁忙型作业在短暂地上处理机运行后又因为等待I/O处理而排到队尾等待，等待时间过长。

短作业优先(SJF)调度算法¶

短作业优先（SJF，Shortest Job First）调度算法是一种基于作业执行时间的非抢占式调度算法。它的基本思想是优先调度执行时间最短的作业，以最小化平均等待时间和平均周转时间。

该调度算法既可用于作业调度也可用于进程调度。短作业优先(SJF)是从后备队列中选择一个或若干估计运行时间最短的作业，将它们调入内存运行；短进程优先(SPF, process)是从就绪队列中选择一个估计运行时间最短的进程将处理机分配给它，使之立即执行，直到完成或因某事件阻塞时，才释放处理机。(注意，一个更为恰当的表示是最短下次CPU执行(shortest-next-CPU-burst)算法，这是因为调度取决于进程的下次CPU执行的长度，而不是其总的长度)。

优点：它可以最小化平均等待时间和平均周转时间，因为它优先调度执行时间最短的作业。这可以减少作业的等待时间和完成时间，提高系统的性能。

缺点：

首先，它需要知道每个作业的执行时间，但在实际情况下，作业的执行时间通常是未知的, 作业/进程的执行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。
其次，SJF算法可能导致长作业等待时间过长，因短作业总是优先执行。这可能会导致长作业出现饥饿现象。
最后该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。

该调度算法也有抢占式的版本，即最短剩余时间优先（SRTN，Shortest Remaining Time Next）算法，这是一种基于作业剩余执行时间的抢占式调度算法。在SRTN算法中，当一个新的作业到达系统时（即每当有进程加入就绪队列改变时就需要调度），操作系统会比较该作业的剩余执行时间和当前正在执行的作业的剩余执行时间。如果该作业的剩余执行时间比当前作业的剩余执行时间更短，那么操作系统会暂停当前作业，将CPU分配给新到达的作业。如果两个作业的剩余执行时间相同，那么可以使用先来先服务（FCFS）调度算法来决定哪个作业先执行。

SRTN算法的优点在于它可以最小化平均等待时间和平均周转时间，因为它优先调度剩余执行时间最短的作业。这可以减少作业的等待时间和完成时间，提高系统的响应速度和吞吐量。

408考试注意的细节：

若题目未特殊说明，所提到的“短作业/进程优先算法” 默认是非抢占式的
在有前提条件“所有进程可同时运行”或“所有进程几乎同时到达”的情况下，我们可以说采用SJF的调度算法的平均等待时间、平均周转时间最少，若未加该前提条件，则应该说“抢占式的短作业/进程调度算法(SRTN)的平均等待时间、平均周转时间最少。
如果选择题中遇到”SJF的平均等待时间、平均周转时间最少“的选项，最好先判断别的选项是否有明显错误，若无更合适选项，那也应该选择该选项。

高响应比优先(HRRN）调度算法¶

由于FCFS算法是在每次调度的时候选择一个等待时间最长的作业/进程为其服务，但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题；

SJF算法只考虑执行时间完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会出现饥饿现象。

高响应比优先调度算法（Highest Response Ratio Next，HRRN）是一种基于响应比的非抢占式调度算法,是对这两种调度算法的平衡，同时考虑了每个作业的等待时间和估计的运行时间。

该算法用于作业/进程调度，在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务；

响应比 =\(\frac{等待时间+计算时间}{计算时间}\)

该算法是非抢占式的算法，因此只有当前运行的作业/进程主动放弃处理机（正常/异常完成，或主动阻塞）时，才需要调度，才需要计算响应比；

优缺点：

该算法综合考虑了等待时间和运行时间(要求服务时间)。等待时间相同时，要求服务时间短的优先(SJF的优点)；要求服务时间相同时，等待时间长的优先(FCFS的优点)；
对于长作业来说，随着等待时间越来越长，其响应比越来越大，从而避免了长作业饥饿的问题；
然而，HRRN算法也存在一些问题。首先，它需要知道每个作业的执行时间，但在实际情况下，作业的执行时间通常是未知的。

【2009-24】下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）。

A. 时间片轮转调度算法

B. 短进程优先调度算法

C. 先来先服务调度算法

D. 高响应比优先调度算法

答案

本题选D；

【2011-23】下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（）。

A. 先来先服务

B. 高响应比优先

C. 时间片轮转

D. 非抢占式短任务优先

答案

本题选B；

A错误。先来先服务调度算法不会发生发生饥饿现象，但不一定满足短任务优先。

B正确。高响应比优先调度算法兼具先来先服务调度算法和短任务优先调度算法的有点。响应比=作业响应时间/作业执行时间 = (作业执行时间+作业等待时间)/作业执行时间。高响应比算法，在等待时间相同情况下，作业执行时间越少，响应比越高，优先执行，满足短任务优先。随着等待时间增加，响应比也会变大，执行机会就增大，所以不会产生饥饿现象。

C错误。时间片轮转调度算法不会发生发生饥饿现象，但不一定满足短任务优先。

D错误。非抢占式短任务优先调度算法满足短任务优先，但可能发生饥饿现象。

本题选B。

Note

注：

以上三种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对用户来说交互性很糟糕。因此这三种算法一般适用于早期的批处理系统。

当然FCFS算法经常结合其他算法一起使用。另外我们是不能事先知道一个进程/作业的运行时间(要求服务时间)的，只能近似预测(例如，下次CPU运行时间通常预测为以前CPU执行的测量长度的指数平均)，因此不准确，高响应比优先调度算法是「理想型」的调度算法，现实中是实现不了的。

时间片轮转(RR，Round-Robin)调度算法¶

时间片轮转调度算法（Round Robin ）是一种基于时间片的抢占式调度算法。在这种算法中，每个进程被分配一个固定的时间片(20ms~50ms)，当时间片用完后，操作系统会将该进程挂起，并将CPU分配给下一个进程。如果一个进程在时间片结束之前完成了它的任务，那么它会被从就绪队列中移除，否则它会被重新加入到就绪队列的末尾，等待下一次调度。

该调度算法用于进程调度，只有作业放入内存建立了相应的进程后，才能被分配处理机时间片；

属于抢占式算法，若进程未能在时间片内运行完，将被强行剥夺处理机使用权，由时钟装置发出时钟中断来通知CPU时间片已到。

优点：公平，响应快， 适用于分时操作系统，可以确保每个进程都能够获得一定的CPU时间，从而避免了长时间等待的情况，不会到导致饥饿；

缺点：由于高频率的进程切换，因此导致了不小的开销；另外不区分任务的紧急程度；

Note

时间片设置太大或太小会导致什么问题？

在该算法中，时间片大小对系统性能的影响很大。

若时间片足够大，以至于所有进程都可以在一个时间片内执行完毕，则时间片轮转调度算法就退化为先来先服务调度算法；

若时间片很小，则处理机将在进程间过于频繁地切换，使处理机的开销增大，而真正用于运行用户进程的时间将减少。

因此时间片的大小应选择适当。一般来说设计时间片时要让切换进程的开销占比不超过1%，根据经验，80%的CPU执行应该小于时间片。

时间片的长短通常由以下因素决定：系统的响应时间、就绪队列的进程数目和系统的处理能力。

注意：

若进程在时间片内提前完成，则进程本身自动释放CPU，则会发生调度
如果当前进程的CPU执行时间大于一个时间片，那么定时器会中断，进而中断操作系统。然后进行上下文切换，再将进程加入到就绪队列的队尾，接着CPU会选择就绪队列的下一个进程
在做题时，若某一时刻进程P1下处理机，同一时刻进程P2到达，那么默认新到达的进程先进入就绪队列；

Note

时钟中断是计算机系统中的一种重要中断类型，主要用于计时和控制时间相关的操作。它由系统时钟（通常是一个硬件定时器）周期性地发出，用来中断当前正在执行的程序，转而执行特定的中断处理程序。时钟中断在操作系统中的作用至关重要，以下是详细介绍。

时钟中断的工作原理

硬件定时器：计算机系统中有一个专门的硬件定时器，它根据设定的时间间隔周期性地产生时钟中断。
中断信号：当定时器达到设定的时间间隔时，会向CPU发送中断信号。
中断处理：CPU收到时钟中断信号后，会暂停当前执行的任务，保存当前的CPU状态，然后转到中断向量表中对应的中断处理程序。
中断服务程序（ISR - Interrupt Service Routine）：时钟中断的ISR由操作系统提供，负责处理各种时间相关的任务。

时钟中断的主要功能

更新系统时间：
时钟中断的一个主要任务是更新系统时钟。每次时钟中断发生时，ISR会更新系统维护的时间变量，这样系统时间才能准确反映当前时间。
时间片管理和进程调度：
在多任务操作系统中，时钟中断用于时间片的管理。每个进程分配一个时间片，时钟中断会检查当前进程的时间片是否用完。如果用完，操作系统会触发进程调度，将CPU分配给其他进程。

时钟中断的实现细节

硬件初始化：
在系统启动时，操作系统会初始化硬件定时器，设定时钟中断的频率。例如，设置定时器每10毫秒产生一次中断。
中断向量表：
中断向量表是一个数据结构，其中包含了各类中断的入口地址。时钟中断对应的ISR地址也保存在这里，当中断发生时，CPU会跳转到该地址执行ISR。
ISR的实现：
时钟中断的ISR实现包括更新系统时间、处理进程调度、执行定时任务等。ISR通常是操作系统内核的一部分，需要高效和快速地执行，以减少中断处理时间对系统性能的影响。

【2018-29】当定时器产生时钟中断后，由时钟中断服务程序更新的部分内容是

Ⅰ. 内核中时钟变量的值

Ⅱ. 当前进程占用 CPU 的时间

Ⅲ. 当前进程在时间片内的剩余执行时间

A. 仅Ⅰ、Ⅱ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅲ

D. Ⅰ、Ⅱ、Ⅲ

答案

本题选D；

【2017-27】下列有关基于时间片的进程调度的叙述中，错误的是（）。

A. 时间片越短，进程切换的次数越多，系统开销也越大

B. 当前进程的时间片用完后，该进程状态由执行态变为阻塞态

C. 时钟中断发生后，系统会修改当前进程在时间片内的剩余时间

D. 影响时间片大小的主要因素包括响应时间、系统开销和进程数量等

答案

本题选B；

【2021-25】下列内核的数据结构或程序中，分时系统实现时间片轮转调度需要使用的是（）。

Ⅰ. 进程控制块

Ⅱ. 时钟中断处理程序

Ⅲ. 进程就绪队列

Ⅳ. 进程阻塞队列

A. 仅Ⅱ、Ⅲ

B. 仅Ⅰ、Ⅳ

C. 仅Ⅰ、Ⅱ、Ⅲ

D. 仅Ⅰ、Ⅱ、Ⅳ

答案

本题选C。

Ⅰ正确。进程控制块是记录和管理每个进程相关信息的数据结构，它包含了进程的状态、优先级、程序计数器等信息。在时间片轮转调度算法中，进程控制块用于保存进程的当前状态和调度信息，以便在每个时间片结束时恢复和切换进程。

Ⅱ正确。时间片轮转调度是通过时钟中断来触发的。时钟中断处理程序负责中断当前运行的进程，更新时间片，以及发现时间片用完之后设置调度标志NEED_RESCHED触发调度；

Ⅲ正确。在时间片轮转调度算法中，当一个进程被中断或时间片用尽时，将其放回就绪队列的末尾，然后从就绪队列队头取出下一个进程来执行。

Ⅳ错误。进程阻塞队列用于存储因等待某些事件而被阻塞的进程。时间片轮转调度只会涉及处于运行态和就绪态的进程，不会涉及处于阻塞态的进程。

【2024-30】假设某系统使用时间片轮转调度算法进行 CPU 调度，时间片大小为 5 ms，系统共有 10 个进程，初始时均处于就绪队列，执行结束前仅处于执行态或就绪态。若队尾的进程 P 所需 CPU 时间最短，时间为 25 ms。在不考虑系统开销的情况下，则进程 P 的周转时间为

A. 200 ms

B. 205 ms

C. 250 ms

D. 295 ms

答案

本题选C。

在时间片轮转 (Round Robin，RR) 调度算法中，进程轮流执行一个固定的时间片。如果一个进程在时间片结束时还没有完成，它将被放到就绪队列的末尾，等待下一轮调度。

根据题目条件，时间片大小为 5 ms，进程 P 所需 CPU 时间为 25 ms，需要 25 ms / 5 ms = 5 个时间片才能完成其执行，即需要 5 轮才能完成。

又因为系统共有 10 个进程，初始时均处于就绪队列，每轮每个进程占用一个时间片，每轮总时间 10 × 5 ms = 50 ms，因为进程 P 所需 CPU 时间最短，所以进程 P 第一个执行完毕，即在 P 执行完毕前，别的进程还有时间片待分配，又进程 P 位于队尾，所以每轮进程 P 最后一个执行，也就是 P 所在轮占用时间片结束时，这个轮次结束。根据之前的分析，该过程总共需要 5 轮，总计 5 × 50 ms = 250 ms。

进程P的完成时间为250ms，到达时时间为0ms，因此进程 P 的周转时间 = 完成时间 - 到达时间 = 250 ms - 0 ms = 250 ms。

优先级调度算法¶

随着计算机的发展特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序；每个进程/作业都有各自的优先级，调度时选择优先级最高的作业/进程；可用于作业 / 进程 / I/O调度；

根据新的更高优先级进程能否抢占正在执行的进程，可将其分为两种：

非抢占式优先级调度算法：只需在进程主动释放处理机时进行调度即可；若在执行过程中有更高优先级地进程到来，只需将其加入到就绪队列的队头即可；
抢占式优先级调度算法：在就绪队列发生变化时检查是否会发起抢占，若有更高优先级进程进入则立即暂停正在运行的进程将处理机分配给它；

补充：就绪队列未必只有一个，可以按照不同优先级来组织。另外可以把优先级更高的进程排在更靠近就绪队列队头的位置；

根据进程创建后其优先级是否可以改变，可以将进程优先级分为以下两种：

静态优先级：创建进程后确定，之后一直不变。其主要依据有进程类型、进程对资源的要求、用户要求等；
动态优先级：创建进程后有一个初始值，之后会根据情况动态地调整优先级；其调整优先级的主要依据有进程占用CPU时间的长短、就绪进程等待CPU时间的长短等。

优点：用优先级区分紧急程度、重要程度，适用于实时操作系统；可灵活地调整对各种作业/进程的偏好程度。

缺点：若源源不断地有高优先级进程到来，则可能导致饥饿；

如何合理地设置各类进程的优先级：

响应时间原则：系统进程优先级高于用户进程；(系统进程作为系统管理者理应拥有更高的优先级)
交互型进程 > 非交互型进程(或前台进程 > 后台进程)
系统资源利用率原则：I/O繁忙型进程 > 计算型进程(CPU繁忙型进程)

I/O设备和CPU可以并行运行，并且I/O设备的处理速度比CPU慢得多，因此若将I/O繁忙型进程的优先级设置的很高的话，就越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升；(I/O繁忙型进程只要执行很短的cpu时间就转去处理IO了，这时cpu就可以让其他进程上来处理，这样不仅提升了并行处理的时间，还可以让io设备尽快投入工作)

此外I/O繁忙型进程通常与用户交互密切相关，例如读取文件、处理网络请求等。提高这类进程的优先级可以使它们更快地响应用户请求，从而提高系统的响应速度和用户体验。

如果采用的是动态优先级，什么时候进行调整：

可以从追求公平、提升资源利用率等角度考虑，如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级；如果某进程占用处理机运行了很长时间，则可以适当降低其优先级；如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级

【2010-26】下列选项中，降低进程优先级的合理时机是（）。

A. 进程的时间片用完

B. 进程刚完成I/O，进入就绪列队

C. 进程长期处于就绪列队中

D. 进程从就绪态转为运行态

答案

解答：

A正确。当一个进程的时间片用完时，操作系统会将其重新放回就绪队列，此时可以通过调度算法降低该进程优先级，然后调度其他进程执行。

B错误。进程完成 I/O 操作后重新进入就绪队列，这通常意味着进程现在准备好执行。在这种情况下，并不需要降低进程的优先级。

C错误。当一个进程长期处于就绪队列中无法得到调度执行时，该进程饥饿，为了让该进程能够得到响应，应该提高该进程优先级，而不是降低该进程优先级。

D错误。当进程从就绪态转为运行态时，它已经被调度为下一个可执行的进程。因此，此时降低进程优先级是不合理的。

本题选A。

【2013-31】某系统正在执行三个进程 P1、P2 和 P3，各进程的计算 (CPU) 时间和 I/O 时间比例如下表所示。

\(\begin{array}{|c|c|c|}\hline \text{进程}&\text{计算时间}&\text{I/O时间}\\\hline \text{P1}&90\%&10\%\\\hline \text{P2}&50\%&50\%\\\hline \text{P3}&15\%&85\%\\\hline \end{array}\)

为提高系统资源利用率，合理的进程优先级设置应为（）。

A. P1>P2>P3

B. P3>P2>P1

C. P2>P1=P3

D. P1>P2=P3

答案

本题选B。

从I/O时间占比角度分析：

在I/O密集型进程中，I/O操作的速度和效率是主要瓶颈，因为它更多的时间花在等待 I/O 操作完成上，而不是在需要持续 CPU 计算的任务上，CPU的处理能力往往有闲置。因此，为了有效利用系统资源，应当给予这类进程较高的优先级。

当一个进程在等待 I/O 操作完成时，操作系统可以将 CPU 时间分配给其他可执行的进程，从而实现资源的更有效利用。这种情况下，给予 I/O 占比高的进程较高的优先级，有助于确保系统能够更灵活地响应 I/O 操作，从而提高整体的系统资源利用率。

在本题中，P1的I/O时间占比<P2的I/O时间占比<P3的I/O时间占比，因此合理的进程优先级设置应P3>P2>P1。

从CPU时间占比角度分析：

类比短进程优先算法，将I/O时间不占用CPU，计算时间占用CPU，可以让计算时间较短（或计算时间占比较少）的进程优先执行，从而降低平均周转时间，提高CPU和I/O设备的并行度。

在本题中，P1的计算时间占比>P2的计算时间占比>P3的计算时间占比，因此合理的进程优先级设置应为P3>P2>P1。

综上，综合考虑进程的计算 (CPU) 时间和 I/O 时间，合理的进程优先级设置应为P3>P2>P1。

【2018-24】某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1μs。在T时刻就绪队列中有3个进程P1、P2和P3，其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。

\(\begin{array}{|c|}\hline \text{进程}&\text{等待时间}&\text{需要的CPU时间}&\text{优先权}\\\hline \text{P1}&\text{30μs}&\text{12μs}&10\ \text{P2}&\text{15μs}&\text{24μs}&30\ \text{P3}&\text{18μs}&\text{36μs}&20\\\hline \end{array}\)

若优先权值大的进程优先获得CPU，从T时刻起系统开始进程调度，则系统的平均周转时间为（）。

A. 54μs

B. 73μs

C. 74μs

D. 75μs

答案

本题选D。

因优先权值大的进程优先获得CPU，进程的执行顺序为P2, P3, P1。

进程Pi的周转时间 = 进程Pi的等待时间 + 一次进程调度和进程切换的系统时间开销 + 进程Pi需要的CPU时间。

进程Pi的等待时间 = 进程Pi初始时在就绪队列中的等待时间 + 之前进程需要的CPU时间+之前进程调度和进程切换的系统时间开销。

P2的周转时间（单位：μs）为：15+0+1+24=40；

P3的周转时间（单位：μs）为：18+1+24+1+36=80；

P1的周转时间（单位：μs）为：30+1+24+1+36+1+12=105。

系统的平均周转时间（单位：μs）为：(40+80+105) / 3 = 225 / 3 =75。

【2022-25】进程P0、P1、P2和P3进入就绪队列的时刻、优先级（值越小优先权越高）及CPU执行时间如下表所示。

\(\begin{array}{|c|}\hline \text{进程}&\text{进入就绪队列的时刻}&\text{优先级}&\text{CPU执行时间}\\\hline \text{P0}&\text{0 ms}&15&\text{100 ms}\ \text{P1}&\text{10 ms}&20&\text{60 ms}\ \text{P2}&\text{10 ms}&10&\text{20 ms}\ \text{P3}&\text{15 ms}&6&\text{10 ms}\\\hline \end{array}\)

若系统采用基于优先权的抢占式进程调度算法，则从0ms时刻开始调度，到4个进程都运行结束为止，发生进程调度的总次数为（）。

A. 4

B. 5

C. 6

D. 7

答案

本题选C。

按时间序列进程分析：

0ms时刻，只有P0进入就绪队列，开始运行P0。
10ms时刻，P1、P2进入就绪队列，P0运行了10ms-0ms=10ms，其CPU执行时间为100ms，剩余CPU执行时间为100ms-10ms=90ms。就绪队列中存在P0、P1、P2三个进程。系统采用基于优先权的抢占式进程调度算法，三个进程中P2的优先级值最小，值越小优先权越高，P2抢占执行。
15ms时刻，P3进入就绪队列，P2运行了15ms-10ms=5ms，其CPU执行时间为20ms，剩余CPU执行时间为20ms-5ms=15ms。就绪队列中存在P0、P1、P2、P3四个进程，此时所有进程都以就绪，系统采用基于优先权的抢占式进程调度算法，值越小优先权越高，优先级值从小到大依次为P3、P2、P0、P1，此时P3抢占执行。

综上，从0ms开始到4个进程都运行结束为止，进程执行序列为P0、P2、P3、P2、P0、P1，发生进程调度的总次数为6。

【2023-29】进程P1、P2和P3进入就绪队列的的时刻，优先值（越大优先权越高）以及CPU的执行时间如下表所示。

\(\begin{array}{|c|}\hline \text{进程名}&\text{进入就绪队列的时刻}&\text{优先级}&\text{CPU执行时间}\\\hline \text{P1}&\text{0 ms}&1&\text{60 ms}\ \text{P2}&\text{20 ms}&10&\text{42 ms}\ \text{P3}&\text{30 ms}&100&\text{13 ms}\\\hline \end{array}\)

系统采用基于优先权的抢占式CPU调度算法，从0ms时刻开始进行调度，则P1、P2和P3的平均周转时间为（）。

A. 60 ms

B. 61 ms

C. 70 ms

D. 71 ms

答案

本题选B。

按时间序列进程分析：

0ms时刻，只有P1进入就绪队列，开始运行P0。
20ms时刻，P2进入就绪队列，P1运行了20ms-0ms=20ms，其CPU执行时间为60ms，剩余CPU执行时间为60ms-20ms=40ms。就绪队列中存在P1和P2两个进程。系统采用基于优先权的抢占式进程调度算法，P2优先级值比P1优先级值大，值越大优先权越高，P2抢占执行。
30ms时刻，P3进入就绪队列，P2运行了30ms-20ms=10ms，其CPU执行时间为42ms，剩余CPU执行时间为42ms-10ms=32ms。就绪队列中存在P1、P2、P3三个进程，此时所有进程都以就绪，系统采用基于优先权的抢占式进程调度算法，值越大优先权越高，优先级值从大到小依次为P3、P2、P1，此时P3抢占执行。
30ms+13ms=43ms时刻，P3执行完毕，P2执行。
43ms+32ms=75ms时刻，P2执行完毕，P1执行。
75ms+40ms=115ms时刻，P1执行完毕，此时所有进程均已执行完毕。

进程周转时间 = 进程完成时刻-进程进入就绪队列的时刻。

P1周转时间 = P1进程完成时刻-P1进程进入就绪队列的时刻 = 115ms-0ms = 115ms；
P2周转时间 = P2进程完成时刻-P2进程进入就绪队列的时刻 = 75ms-20ms = 55ms；
P3周转时间 = P3进程完成时刻-P3进程进入就绪队列的时刻 = 43ms-30ms = 13ms；
P1、P2和P3的平均周转时间 = (P1周转时间 + P2周转时间 + P3周转时间)/3 = 61ms。

【2016-46】（6分）某进程调度程序采用基于优先数 (priority) 的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。请回答下列问题。

(1) 若调度程序只将nice的值作为进程的优先数，即priority=nice，则可能会出现饥饿现象，为什么？

(2) 使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。

答案

(1) nice为静态优先数，若采用nice作为进程优先数，对于就绪队列中某一个尚未运行的nice值较大的进程，若有比该进程nice值小的进程源源不断进入就绪队列，则该进程将一直无法运行，从而导致饥饿现象。

注：在操作系统中，nice 值并不是表示优先级，而是表示优先级的修正数值，它与优先级 (priority) 的关系是这样的：priority(new) = priority(old) + nice。内核中，priority 的范围是 0~139，值越低，优先级越高，其中前面的 0~99 范围是提供给实时任务使用的，而 nice 值是映射到 100~139，这个范围是提供给普通任务用的，因此 nice 值调整的是普通任务的优先级。

nice 值越小，优先数就越小，任务的优先级就越高。

(2) 为了避免产生饥饿现象，需要将静态优先数调整为动态优先数，引入运行时间cpuTime和等待时间waitTime，根据高响应比优先调度算法，响应比=(等待时间＋要求服务时间)/要求服务时间，waitTime视为等待时间，cpuTime视为要求服务时间。

cpuTime越大，响应比越小，优先级越低，优先数越大，采用乘法权重，设权值为k1 > 0，可以增加k1 · cpuTime。
waitTime越大，响应比越大，优先级越高，优先数越小，采用乘法权重，设权值为k2 > 0，可以减少k2 · waitTime。

综上所述，优先数 = nice + k1 · cpuTime - k2 · waitTime，其中k1表示cpuTime的权重，k2表示waitTime的权重，k1、k2均为大于0的常数。

waitTime的使用保证若waitTime越大，则优先数越小，从而避免出现饥饿现象。

多级队列调度算法¶

   前面所述的各种调度算法通常只设置一个就绪队列，即调度算法是固定且单一的，无法满足系统中不同用户对进程调度策略的不同要求。在多处理机中这种单一调度策略实现机制的缺点更加突出。

在进程容易分成不同组的情况下，可以有另一类调度算法。

例如，进程通常分为前台进程(或交互进程) 和后台进程(或批处理进程)，这两种类型的进程具有不同的响应时间要求，进而也有不同的调度需要。另外与后台进程相比，前台进程可能要有更高的优先级(外部定义)。

Note

多级队列调度算法将就绪队列分成多个单独队列(在系统中设置多个就绪队列，将不同类型或性质的进程固定分配到不同的就绪队列)，根据进程属性，如内存大小、进程优先级、进程类型等，一个进程永久分配到一个队列。每个队列有自己的调度算法。

在多处理机系统中，可以很方便地为每一个处理机设置一个单独的就绪队列，每个处理机可实施各自不同的调度策略，这样就能根据用户需求将多个线程分配到一个或多个处理机上运行。

此外，队列之间应有调度，通常采用固定优先级抢占调度，例如前台队列可以比后台队列具有绝对的优先。

来看个实例，这里有五个队列，按优先级从高到低分别是系统进程、交互进程、交互编辑进程、批处理进程、学生进程，每个队列与更底层队列相比具有绝对的优先。例如只有系统进程、交互进程、交互编辑进程都为空时，批处理队列内的进程才可以运行。如果在一个批处理队列内的进程运行时来了一个交互进程进入就绪队列，那么该批处理进程就会被抢占。

另外一种可能是在队列之间划分时间片。每个队列都有一定比例的CPU时间可用于调度队列内的进程。例如对于前台—后台队列的例子，前台队列可以有80%的CPU时间，用于在进程之间进行RR调度，而后台队列可以有20%的CPU时间，用于按FCFS算法来调度进程。

多级反馈队列调度算法¶

在使用上面所说的多级队列调度算法时，进程在进入系统时被永久地分配到某个队列，虽然调度开销低，但是不够灵活。相反，多级反馈队列调度算法允许进程在队列之间迁移。多级反馈队列调度算法（Multilevel Feedback Queue Scheduling）是一种动态优先级的进程调度算法，它结合了优先级调度和时间片轮转调度的特点，以适应不同类型的进程需求。该算法将进程分为多个队列，每个队列具有不同的优先级和时间片大小。

以下是多级反馈队列调度算法的主要特点：

多级队列：进程被分配到不同优先级的队列中。通常情况下，新到达的进程被放入最高优先级的队列。每个队列具有不同的时间片大小，优先级越高的队列，时间片越短
时间片轮转：在每个队列中，进程按照时间片轮转和FCFS的方式进行调度。这样可以确保每个进程都能获得一定的CPU时间，并且避免长时间占用CPU的进程导致其他进程无法运行
反馈机制：如果一个进程在当前队列中运行的时间超过了时间片大小，那么它将被降级到下一个优先级的队列中。这样可以确保高优先级的进程能够尽快获得CPU资源，从而提高系统的响应速度。同时，如果一个进程在当前队列中完成了其任务而未用完时间片，它可以在下次调度时保持在当前队列
一定程度上避免饥饿：通过多级队列和反馈机制，可以避免低优先级进程长时间得不到调度的问题。即使一个进程被降级到最低优先级的队列，它仍然有机会获得CPU资源，从而避免饥饿现象的发生。此外，在较低优先级队列中等待时间过长的进程会被移到更高优先级队列，这种形式的老化阻止饥饿的发生（极端情况下仍有可能发生饥饿）

多级反馈队列调度算法的优点在于它可以适应不同类型的进程需求，如I/O密集型和CPU密集型进程(例如可以将因I/O阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）。它可以确保高优先级的进程能够快速响应，同时避免低优先级进程饥饿。

例如，考虑一个多级反馈队列的调度程序，它有3个队列，从0到2；调度程序首先执行队列0内的所有进程。只有当队列0为空时，它才能执行队列1内的进程。类似地，只有队列0和队列1都为空时，队列2里的进程才能被执行。另外到达队列0或队列1的进程会抢占队列2的进程，原来在队列2运行的进程放回队列2队尾(被抢占处理机的进程重新放回原队列队尾)。

每个进程在进入就绪队列后都会被添加到队列0的队尾，队列0里的每个进程都有8ms的时间片；如果一个进程不能在这8ms内完成，那么它会被移到队列1的队尾。如果队列0为空，队列1头部的进程会得到16ms的时间片，如果它不能完成将会被抢占，并添加到队列2的队尾。只有当队列0和队列1都为空时，队列2里的进程才会按照FCFS和时间片轮转来运行。若队列2里的进程在时间片内没运行完继续插入到队列2队尾。

这种调度算法将给那些CPU执行时间不超过8ms的进程最高优先级。这类进程可以很快得到CPU，完成CPU执行，并且处理下个I/O执行。所需时间超过8ms但小与24ms的进程也会很快得到服务，但是他们的优先级会低一些。长进程会自动沉入队列2。

通常，多级反馈队列调度算法可由以下参数来定义：

就绪队列数量
每个队列的调度算法
就绪队列的优先级
用以确定何时升级到更高优先级的方法
用以确定何时降级到更低优先级的方法
用于确定进程在需要服务时将会进入哪个队列的方法(指多级反馈队列调度算法如何根据进程的特征和需求将其分配到合适的队列)

【2019-27】系统采用二级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用短进程优先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程；新创建的进程首先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2。若当前Q1、Q2为空，系统依次创建进程P1、P2后即开始进程调度，P1、P2需要的CPU时间分别为30ms和20ms，则进程P1、P2在系统中的平均等待时间为（）。

A. 25ms

B. 20ms

C. 15ms

D. 10ms

答案

本题选C。

P1、P2需要的CPU时间分别为30ms和20ms，就绪队列Q1采用时间片轮转调度算法，时间片为10ms，依次执行P1和P2一个时间片10ms，此时P1、P2需要的CPU时间分别为20ms和10ms，就绪队列Q2采用短进程优先调度算法，优先执行P2剩余的10ms，再执行P1的20ms。画出进程运行的甘特图如下：

进程P1的等待时间为30ms-10ms=20ms，进程P2的等待时间为10ms-0ms=10ms。进程P1、P2在系统中的平均等待时间为(20ms+10ms)/2=15ms。

【2020-26】下列与进程调度有关的因素中，在设计多级反馈队列调度算法时需要考虑的是（）。

Ⅰ. 就绪队列的数量

Ⅱ. 就绪队列的优先级

Ⅲ. 各就绪队列的调度算法

Ⅳ. 进程在就绪队列间的迁移条件

A. 仅Ⅰ、Ⅱ

B. 仅Ⅲ、Ⅳ

C. 仅Ⅱ、Ⅲ、Ⅳ

D. Ⅰ、Ⅱ、Ⅲ和Ⅳ

答案

本题选D。

I正确。就绪队列的数量需要合理设置，数量过多会浪费系统资源，数量过少会导致进程无法充分执行。

Ⅱ正确。不同就绪队列具有不同的优先级。较高优先级的队列中的进程将被优先选择执行，而较低优先级的队列则是后备队列。

Ⅲ正确。对于每个就绪队列，可以使用不同的调度算法来选择下一个要执行的进程。通常，较高优先级的队列使用抢占式调度算法，而较低优先级的队列使用非抢占式调度算法。这些调度算法的选择与各就绪队列的特性和调度目标密切相关。

Ⅳ正确。多级反馈队列调度算法允许进程在不同的就绪队列之间迁移。迁移条件可以是时间片用尽、优先级的变化、等待时间等。这些条件决定了一个进程何时从一个队列迁移到另一个队列，以便重新调度和执行。

综上，Ⅰ、Ⅱ、Ⅲ和Ⅳ正确。

【例题】系统采用三级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用时间片轮转调度算法，时间片为20ms；就绪队列Q3采用先来先服务先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程，当Q2为空时系统才会调度Q3中的进程；新创建的进程首先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2；Q2中的进程执行一个时间片后，若未结束，则转入Q3。若当前Q1、Q2、Q3为空，系统依次创建进程P1、P2、P3后即开始进程调度，P1、P2、P3需要的CPU时间分别为60ms、60ms和60ms，则进程P1、P2、P3在系统中的平均等待时间为（）。

答案

90ms

Note

由于现在的交互式操作系统(包括分时操作系统、实时操作系统)更注重系统的响应时间、公平性、平衡性等指标，因此后面提到的这几种算法适用于交互式系统。

调度算法	优点	缺点
先来先服务（FCFS）	公平，实现简单，对长作业有利	对短作业不利
短进程优先（SPF）	对短作业有利所有进程同时到达情况下，平均等待时机最短	对长作业不利，可能导致饥饿
高响应比优先（HRRN）	综合考虑进程等待时间和执行时间	-
时间片轮转（RR）	公平，响应快	如果时间片过小，会导致频繁的上下文切换，增加系统开销
优先级	考虑进程优先级	可能导致饥饿
多级队列	设置多个就绪队列，针对不同进程需求，设置不同调度策略	-
多级反馈队列	可以动态调整进程优先级和时间片大小，兼顾多方面系统目标	-

【2014-23】下列调度算法中，不可能导致饥饿现象的是（）。

A. 时间片轮转

B. 静态优先数调度

C. 非抢占式短作业优先

D. 抢占式短作业优先

答案：

本题选A。

饥饿现象是指一个进程或任务由于得不到执行的机会而无法完成的情况。调度算法的设计应该避免饥饿现象的发生，确保公平地分配处理器时间给各个进程或任务。

A正确。时间片轮转调度算法是一种循环调度算法，在每个时间片内，每个进程或任务都有机会执行一段时间。因为时间片是有限的，所以没有一个进程会长时间占用处理器，从而避免饥饿现象的发生。

B错误。静态优先数调度算法根据每个进程或任务的静态优先级进行调度。属于优先级调度算法，饥饿现象可能发生在优先级较低的进程，只要有源源不断的优先级比该进程高的进程在其执行前到来，则该进程将一直被推迟，可能导致饥饿现象。

C错误。非抢占式短作业优先调度算法将优先执行估计运行时间短的作业。属于短作业优先调度算法。饥饿现象可能发生在运行时间较长的作业，只要有源源不断的运行时间比该作业短的作业在其执行前到来，则该作业将一直被推迟，可能导致饥饿现象。

D错误。抢占式短作业优先调度算法中，运行时间相对较短的作业可以抢占正在执行的剩余运行时间相对较长的作业。属于短作业优先调度算法。饥饿现象可能发生在运行时间较长的作业，只要有源源不断的运行时间比该作业短的作业在其执行前到来，则该作业将一直被推迟，可能导致饥饿现象。

【2016-24】某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是（）。

A. 15ms

B. 17ms

C. 22ms

D. 27ms

答案

本题选B。

设3个作业分别为P1、P2、P3。设初始时刻为0，P1先执行，画出作业运行的甘特图如下：

采用图(a)或图(b)的画法都可以。

【2017-23】假设4个作业到达系统的时刻和运行时间如下表所示。

系统在t=2时开始作业调度。若分别采用先来先服务和短作业优先调度算法，则选中的作业分别是（）。

A. J2、J3

B. J1、J4

C. J2、J4

D. J1、J3

答案

本题选D。

系统在t=2时开始作业调度，此时已经到达的作业有J1、J2和J3。

先来先服务调度算法优先选择到达时刻早的作业，J1、J2和J3中J1到达时刻最早。若采用先来先服务调度算法，则选中J1。

短作业优先调度算法优先选择运行时间短的作业，J1、J2和J3中J3的运行时间最短。若采用短作业优先调度算法，则选中J3。