操作系统笔记

操作系统概述

可执行文件如何存储在计算机中？——存储

可执行文件如何加载到内存，并在CPU中运行——程序的加载与运行

可执行文件如何将字符输出到屏幕——IO输出

两个程序如何同时在一个CPU中运行？——程序如何并行？

os有两个职责

对硬件进行管理和抽象
为应用提供服务并进行管理

总之，就是作为中间层，对下进行抽象，对上提供服务与管理（服务和管理中当然也包括安全内容）

硬件资源是复杂的、异构的、对开发者来说不友善且容易暴露安全问题的。操作系统需要对其进行管理。典型流程：1.识别 2.管理 3.抽象成服务

1.比如先识别不连续的、有限的内存 2.通过内存分配器对其进行管理 3.对上层提供连续无限的内存服务

对于其他硬件也是如此。外设通过驱动进行管理。把有限的资源抽象成无限的服务

但是，总的来说，操作系统的设计是服务于使用场景的；或者说，服务于应用的。其上运行的应用如果是多种多样，最终演化的形式就是如Windows，Linux这种面向用户的。如果运行的应用是专用场景，有各种各样的要求，那其架构和形式也将不同。场景决定取舍，取舍决定形态

广义的操作系统可以分为操作系统内核+操作系统框架两层。

操作系统内核提供对硬件的管理和抽象，为操作系统框架提供基础的系统服务
操作系统框架基于kernel，为不同的应用领域提供编程接口与运行环境

可以这样理解：内核是通用底座，框架是针对不同领域的适配

操作系统接口

kernel提供系统调用接口。这种系统调用接口在pwn中常用甚至LoOS中进行过编写。kernel如何提供系统调用是值得深入学习的

由于每个操作系统提供的系统调用接口都各不相同，为了让同一个实例可以在不同的OS上运行，就衍生出了所谓的POSIX接口。POSIX是一种规范，规范最终能提供统一的接口；libc 是它在用户态的实现。所以针对不同的OS，系统调用接口不同，实现不同的libc，由libc来提供相同的POSIX接口，最终能够实现跨平台。

我对微内核和宏内核的理解，根本区别在于框架与kernel的比重。如果kernel比重大则是宏内核；如果大部分该由OS提供的服务运行在框架层，则是微内核。

硬件结构

冯诺依曼结构 IO - CPU - 存储器

其根本特征在于，数据与指令同存同取。一方面带来著名的冯诺依曼瓶颈，即取指与取数会抢夺通信资源；一方面带来安全问题，如shellcode的可乘之机

对于ARM架构，其特权级有EL0 - 3

EL0 即用户态

EL1 即内核态

EL2 hyperviser

EL3 TrustZone相关普通世界/安全世界

从EL0到EL1有三种方式：

系统调用指令主动执行 svc指令
异常指令出错导致异常缺页、非法、权限错、除零
中断外设打断，与当前指令无关

前两种都是同步指令（因为都是由当前指令引起的），可以被沉睡，可以放置在一旁不管，不会影响最终的执行过程；

第三种是异步。问题只要涉及异步就会变得很复杂，这个可以慢慢讨论

在从EL0 进入EL1时，基于CPU负责保存当前执行状态，目的为在处理完EL1的任务后能够恢复之前的执行流。CPU保存的主要状态有：

触发异常的指令地址这就是返回的依据
异常原因内核据此会去不同的异常处理函数
切换栈指针，此时会从用户栈切换到内核栈；同时也会把之前的寄存器状态保存到内核栈中
ARM类CPU中的一些特殊状态，保存到特殊寄存器中。为了回复状态
缺页异常触发的那个内存地址。对其进行后续的处理，比如调整映射表

可以看到，这个过程既涉及硬件CPU的参与，也有软件内核的参与，并不是一方全包。

在内核启动时，会把异常向量表的地址写入VBAR_EL1。之后每次特权级切换时，CPU就去读这个寄存器。然后CPU会先把该它保存的事情做完，然后执行流进入异常向量表中对应的地址

每个目标流程开始前，都会先把通用寄存器压成pt_regs，保存入内核栈，然后判断具体原因，然后分发给真正的处理函数。是系统调用还是异常。处理完恢复现场。

关于哪些是硬件做，哪些是软件做——硬件只负责事发瞬间不可替代的原子动作

寄存器

在AArch64中，有31个64位通用寄存器，X0-X30。X31专门用来保存栈指针SP

这31个通用寄存器是用来“计算和调用”的寄存器

X0-X7用来传参和返回值

X8是Linux系统调用号

X9-X15 所谓caller-saved，即让调用者自己保存好，被调用的函数可以在运行过程中随意修改，已帮助自己进行运算

X16 X17 这两个寄存器是链接器和动态链接器的跳板专用。为什么会出现这个设计？因为AArch64指令定长32位，要把目标地址编码进入指令，射程只有+-128MB，多了就去不了。同时也没有内存间接跳转指令，所以必须用寄存器保存一下地址然后再跳过去。所以本质上是存地址的工具

X19-X28 用于跨调用存活变量。callee-saved，被调用者想用先自行备份。其实是用来存长生命变量的，由于会可能从父函数头到尾都要用到，所以子函数用这个寄存器时，要现在序言保存它数据，然后在尾声恢复数据，以保证父函数数据不丢失。

对比X9-X15，就是存短生命变量的，其存取频率很高；而对于X19-X28，就是存长生命变量的，其存取频率相对来说没那么高。

X29 FP，帧指针，指向当前栈帧基地址，类似x86中的bp

X30 保存返回地址；ARM将返回地址放在寄存器中，而X86将返回地址放在栈上。对于ARM来说，当ret时从寄存器中取数据。但是由于这个寄存器全局只有一份，所以一旦遇到非叶子函数就会丢失信息，即函数内部调用别的函数，此时这个寄存器数据会丢失。所以非叶子函数必须手动保存它。其实到最后大部分情况依然与X86的差不多

除此以外，还有两个页表基地址寄存器——TTBR0_EL1，TTBR1_EL1——现在理解起来有点复杂，需要综合数据结构、OS后续的学习内容来展开

设备与中断

内存映射输入输出（Memory-Mapped I/O，即MMIO）。其核心原理：统一编址。即将设备和物理内存放在同一个物理地址空间，将设备的内存与寄存器都分配上一个地址。在这种情况下，可以看作为CPU提供了一个统一的物理内存模型，CPU就可以用和访问内存相同的指令来访问设备。相应的也会有代价，代价就是正常物理内存模型中的一部分地址在意义上就必须用来提供给外设。

MIMO能够解决CPU如何访问设备的问题，即CPU从设备中写入和取值，但是设备无法主动通知CPU。在这种情况下，就引入中断控制器这个硬件，通过硬件的形式衍生出中断这个操作。

操作系统结构

前文说过，需求决定形态，而形态实则上是由结构决定的。在构建复杂系统时，必须合理考虑其内部结构。

设计系统结构需要满足一定的设计目标，这些目标可以分为以下三种：

1.外部目标：即系统被设计出来要解决的问题

2.内部目标：易于实现和维护、灵活可靠、稳定、可扩展等目标

3.商业目标：需要衡量这个系统实现和维护所需要的成本

操作系统的机制和策略

如何有效控制操作系统设计的复杂度？控制复杂度的第一性原理——将策略和机制相分离。即将“做决策”和“提供能力”拆开。策略表示做什么，策略表示如何做。

即设计成什么样，与底层如何实现，拆开。但是要实现这个目标，引入抽象层是会带来开销的。

分离本身也要进行设计：机制太薄，策略被迫重复造轮子；机制太厚，策略失去灵活性。所以真实系统是混合的：快路径常故意不分离

操作系统复杂度管理方法

管理复杂系统的重要方法模块化抽象分层层级

模块划分不是越细越好，过多的模块会导致模块之间联系过多，无益于复杂度的控制；划分则要考虑高内聚低耦合，使模块具有独立性

一个好的抽象应尽量依从模块间的自然边界，尽量减少模块间的交互，以减少错误在模块间的传递。安全边界上不应遵循“宽进严出”原则，宽容应当放在兼容/适配层，但是在核心接口上要走窄接口。

对于复杂系统而言，当规模上去之后，就可能会导致模块过多，交互关系爆炸。此时引入分层和层级就可以进一步管理复杂度。

分层和层级是两种给交互关系做拓扑约束的组织方式。分层——约束交互的对象，只能和同层和上下级交互，不能跨层；层级——功能相近的模块聚合成一个自包含子系统

感觉这里就很接近中国政府的条条块块形态

操作系统内核架构

1.简要结构

如MS-DOS、FreeRTOS、uCOS等操作系统。MS-DOS是早期操作系统，而RTOS这种则是现在还运行在许多场景中的操作系统。这种结构不区分内核态用户态，直接跑在同一个地址空间上，底层也不提供复杂的内存管理等功能，任何一个模块出问题都可能导致整个模块出问题。也因此不适用于复杂度高的场景，但是好处就是快。在不需要高复杂度且对实时性能要求高的场景好。往往运行在微控制单元MCU这种相对简单的硬件上

2.宏内核架构

特征是操作系统的所有模块都运行在内核态，具备直接操作硬件的能力。代码中有类似arch/arm/的目录，用于封装与体系结构相关的功能实现。

这种内核为了管理复杂度，也采用了许多管理复杂度方法

模块化：采用模块化策略组织各个功能，还提供了可加载内核模块LKM机制。当前大部分设备驱动都以这种形式存在

抽象：如Linux中的一切皆文件。将数据、设备、内核对象等都抽象成文件，并为上层应用提供统一接口

分层：如文件系统的分层结构。存储设备——设备驱动——块设备层——数据缓存——虚拟文件系统

层级：如调度子系统中对进程优先级的分类，控制组对进程层级的分类；内存分配器对不同内存的分类等

目前Linux的通用、适用于大部分场景的设计正在向专业化场景迁移，许多较大的创新开始向用户态迁移，正在向微内核转变。

其余还有微内核、外核架构

操作系统框架结构

Android系统框架以Linux内核为kernel，在此之上进一步搞了一个硬件抽象层，此举受限于开源协议与接口限制，目的是为了Android框架的独立演进，可以不依赖于kernel版本。在硬件抽象层之上，提供新的库（方便应用开发，替代glibc）与Android运行环境（将应用从字节码转为可执行代码）。在此之上，又提供了一个Android应用框架，提供了应用运行所需要的基础服务，包括服务管理活动管理包管理窗口管理等。

可以看到，这个框架的设计类似于微内核架构，将许多重要且专业的业务放到了内核之外来运行

ROS系统框架 Robot Operating System 即机器人操作系统

运行在Linux内核或其他兼容POSIX接口的kernel之上，提供了一系列面向机器人场景应用的系统级服务。这个架构本身很有意思，类似于机器人版本的云原生基础设施，可以后来回来看看

内存管理

现代操作系统在物理内存上进行抽象，产生了虚拟内存，提供了三个优点：

高利用率。以页级细粒度进行物理内存的高效利用
隔离。不同进程的内存访问互相隔离，安全
统一且连续。提供给应用程序的服务

在提供虚拟内存抽象时，OS面对利用率x速度的矛盾，需要在不同场景下进行取舍。所以现代操作系统会使用不止一种分配器进行分配。

物理地址如何被抽象为虚拟地址

CPU中的MMU（内存管理单元）负责虚拟地址到物理地址的转换。CPU取指，此时发出的是指令的虚拟地址，通过MMU被翻译成物理地址，该请求被发送到物理内存设备，然后返回对应的内容。

为了加速翻译，现代CPU都有TLB机制。转址旁路缓存 Translation Lookaside Buffer。属于MMU内部的单元

MMU翻译的机制主要是两种：分段分页

分页已经成为历史胜出者。

一、分段机制：按逻辑块切分

VA 结构：段号 | 段内偏移
翻译

段表基址寄存器 → 找到段表；用段号索引 → 取出该段的起始地址 + 段长
段起始物理地址 + 段内偏移 = 物理地址；段长用于越界检查

特点：分配单位是变长、逻辑上有意义的块（代码段、数据段、栈）；虚拟相邻的段可以映射到物理不相邻的段 → 支持离散分配
隐含优点：与程序逻辑结构天然对应（代码只读、数据可写——保护语义按段设置）
致命伤——外部碎片：总量够 ≠ 能分配
历史：8086 引入 → 80286 用于虚拟内存 → x86-64 后基本弃用（兼容保留，FS/GS 是残余：用作 TLS 指针）

二、分页机制：按等长格子切分

VA 结构：虚拟页号 | 页内偏移（常见 4KB 页）
翻译：页表基址寄存器（x86 的 CR3 / AArch64 的 TTBR）→ 用页号查页表 → 得物理页号（PFN）→ PFN 基址 + 页内偏移 = 物理地址
特点：虚拟页与物理页等长；任意虚拟页可映射到任意物理页
好处：

外部碎片消失：任何空闲物理页都能用——“总量够就能分配”
分配极简：找任意空闲页帧即可
映射完全可编程：共享库（一页映到多个地址空间）、COW、按需分页、换出、大页——全部高级内存机制都建立在这个自由度上
页表规则化 → 可实现多级树、支持稀疏的大地址空间

代价：内部碎片（页内浪费）、页表空间开销、多一次翻译（靠 TLB 缓存）

分页取得胜利的本质原因，将“变长问题”转化为“定长问题”，是消灭外部碎片的通用手段。这种思想用在了很多分配器中

分页策略的具体机制：

多级页表取代单级页表的必要性：对于64位的虚拟地址空间，假设页大小为4KB，一张页表的大小就是2^64/4KB*8即3355432 GB。为了压缩页表大小从而引入多级页表。本质上是一种用时间换空间的思想。那么多级页表的建立可以很自然引入之前的页号与偏移的递归逻辑。每次查询都用虚拟页号+页内偏移量实现。

同时，引入多级页表还可以将不存在的子级页表的空间节省下来。

虚拟地址（48 位，4 级）

┌────┬────┬────┬────┬──────────┐

│VPN3│VPN2│VPN1│VPN0│ 页内偏移 │ （每段 9 位）

└────┴────┴────┴────┴──────────┘

│ │ │ └─→ L3 表 → 4KB 页

│ │ └─→ L2 表

│ └─→ L1 表

└─→ L0 表（根，地址来自 TTBR/CR3）

核心规则：某一级的条目为空 → 它下面的一整棵子树都不存在。那么就可以按需创建，同时整个页表只占几十KB 一种稀疏表示

一个地址一共64位，高16位要么全1要么全0，区分用户态还是内核态；低48位，从高往低4x9=36位从L0-L3级页表的索引，最后12位表示页内偏移

容易理解的是，由于虚拟地址空间是针对每个进程都抽象出来一份的，所以每个进程都会有一份属于自己的页表。但是内核页表只有一份，用户态列表每个进程都有一份，维护是由OS来维护的

TLB：

多级页表用时间换空间，TLB则能挽回一些时间性能上的损失。

可以看到TLB有L1,L2两级缓存。L1的缓存区分指令与数据，L2则不区分。

TLB的引入带来了一个新的问题：如何处理两个进程访问同一个虚拟地址时带来的冲突问题。A进程访问某个虚拟地址，于是在TLB中留下了缓存。此时B进程也访问该地址，一下就在TLB中也命中了该地址，就会导致两个进程可能同时对一个物理内存地址进行读写，导致数据写坏。

为了处理该问题，ASID/PCID 技术给虚拟地址打上标签：每条TLB表项存了一个标识当前地址空间的编号，就可以在访问到不属于当前地址空间的表项时进行跳过

换页与缺页异常

对于每个进程来说，其所看到的内存空间都是平坦且无限的。但是实际的物理空间却是有限的。为了解决这个冲突，分配给每个进程的物理内存不一定有许诺的那么多，往往是要用到才通过页表置换的形式实时分配给它。极端情况下，当物理内存不够时，如果是已经保存的数据，都可以存入硬盘的虚拟空间中，直到要用时再回收回来继续使用。这种技术被称为page swapping。衍生的操作有swap out。具体来说，当OS希望从程序A那里回收物理页P时，操作系统需要将物理页P的内容写入到磁盘上的一个位置，并且在A的页表中去除对虚拟页V的映射，同时记录该物理页杯换到磁盘上的对应位置。此时页P就处于已分配但未被映射至物理内存的情况。

缺页异常page fault与page swapping机制密不可分，也是换页机制能运行的前提。即当进程访问已分配但未映射至物理内存的虚拟页P时，就会触发page fault。此时会进入先前提到的处理异常流程，进入对应的handler，找到一个空闲的物理页，将磁盘上的页P进行加载并替换页表表项。该过程即换入 page in。之后继续正常运行

由于换页过程涉及磁盘IO操作，为了减少IO耗时，OS往往引入预取机制进行优化，当换入操作发生时，预测还有哪些页即将被访问，并一次性完成换入操作。

另外，虚拟内存还遵循按需页分配机制，即当进程申请内存时，新分配的虚拟页都会被标记为已分配但未映射的状态，直到真正被访问时会触发page fault。此时才有真正的映射。这个机制虽然确实很大程度上节约了物理内存资源，但是在首次访问时仍然会引入延迟开销，此时也可以用相同的思路引入局部性原理，将相临的页也提前做好映射，来减少page fault发生的次数。

页替换算法

空置

虚拟内存功能

除开为进程提供一个平坦连续无限独立的内存空间之外，虚拟内存还有其他功能

共享内存允许同一个物理页被不同的进程所共享。即将不同进程的虚拟地址映射到同一个物理地址上，就形成了一个共享空间，可以用来传递数据。还衍生出写时拷贝，内存去重等功能
写时拷贝如两个程序共用一个库，就可以通过调整映射来共享一个物理内存的数据。等到某方真要写时，才为它单独复制一份。本质是把"复制"这个昂贵动作推迟到不得不做的那一刻。一旦要写时，会触发缺页异常，然后OS会发现缺页异常的原因是尝试写只读内存，而相应的内存区域又是被OS标记成写时拷贝的。然后OS就会进行写时拷贝
内存去重即定期扫描内存中具有相同内容的物理页，然后去除多余的映射，只保留一个物理页
内存压缩即对不常用的内存页，压缩其中数据，等到要用时再解压。如linux中的zswap技术
大页即通过扩大页的大小，变相提高TLB的缓存命中率，也可以减少页表的级数。不过提高粒度也可能导致物理内存资源浪费，大页与小页共存也会增加内存管理复杂度，引入相应攻击面

物理内存分配与管理

内存分配设计的评价维度

内存资源利用率：内存碎片（无法被利用的内存）分为内部碎片和外部碎片。内部碎片是"分给你的比你需要的多，多的那部分浪费在块内部"；外部碎片是"空闲内存总量够，但碎成小块凑不出你要的连续一块"。对于外部碎片，可以通过对内存进行等长划分来解决，但这样又会引入内部碎片。

性能。如果过度注重内存资源利用率，通过精密的算法提高利用率则会带来性能的开销。

所以优秀的内存分配器就是在做内存资源利用率和性能的取舍

Buddy system 内存分配器

buddy system在现代OS中被广泛应用于分配连续的物理内存页。

1.以块为基本单位进行分配

2.每个块都由一个或多个连续的物理页组成，但是页的数量必须是2的n次幂

3.维护一个全局数组free_area[i]，第i项挂一条链表，链上全是2的i次幂数量的物理页组成的的空闲块

这是这个分配器的基础框架。操作：

1.分配当请求m页，那么这个m会落在2^(i−1) < m ≤ 2^i中（i = ⌈log₂m⌉），然后就去查找free_area[i]，如果该项为空则找i+1，i+2…，取到一个大块后一路对半劈，每次把剩下的另一半放到对应的链表去，直到取到合适大小的块为止。

2.释放释放出一个块，看看其对应大小的链表下有无同样空闲的块（伙伴）。找到伙伴则合并成更大的块，拿着更大的块再找对应的伙伴，如此级联向上。直到找不到伙伴，插入对应链表，结束。

buddy system的高妙之处：

互为伙伴的两个块的物理地址仅有一位不同，且由块大小决定。也就是说，伙伴之间的拓扑关系被藏在了地址的第K位里，本质上是一个二叉树模型。只需要经过简单的运算就可以直接寻找到伙伴，而不需要维护复杂的数据结构

slab分配器

如果说buddy负责页级的内存分配，slab就负责字节级的内存分配，用于消除buddy导致的内存内部碎片。两者往往共同作用，是一个管道的上下两头

20世纪90年代，slab分配器被实现。在使用过程中，衍生了许多问题：维护太多队列，实现日趋复杂，存储开销也由于复杂的设计而增大等

于是，在slab分配器的基础上设计了slub分配器，极大简化了slab的设计和数据结构，在降低复杂度的基础上能够提供更好的性能，也继承了slab的接口。

此外，slab家族中还有一种最简单的分配器slob。其需求空间在于内存稀缺资源场景（如嵌入式设备），有最小的存储开销，但在碎片问题的处理方面比不上其他两种分配器。

Linux默认使用slub

slub会：

从buddy那里申请来块（一个或多个连续物理页）
把这个块进行等长切片：[元数据头][对象][对象][对象]…
将空闲对象用在其内部的freelist串起来，形成一个物理上相邻但逻辑上是链表的结构

结构大概如下：

slab大小不同，可能在同一个池里，只要切分出来的对象大小相同即可

slub会维护许多许多池，每个池都有不同的身份，状态，生命周期，以供给内核不同对象进行使用

可以从状态机角度描述三个层次中的主体。

一个slab可能处于三种状态，即全空闲（满），部分空闲，全被取走（忙）

而一个slab会被两种指针追踪，一个是current，该指针指向当前主要取对象的slab；一个是partial链，该指针链的是拥有空闲块的slab

而当slab处于第三种状态，全被取走时，其必然处于无人追踪状态。

行为描述：释放：

先查释放的对象属于哪个slab
去对应的slab，先记录下挂上这个对象之前的还剩的对象数量
把该对象挂上去
判断挂上去之后是不是满了
如果满了，则直接将该slab还给buddy
如果没满，且之前该slab上已经没有剩下的对象了（此时无人追踪），那么现在挂上去就有了，把它挂入partial链
如果没满，还有一种情况，那就是之前该slab上有空闲对象，意味着此时其可能是current，也可能在partial上。都是什么都不做

总之，绕了一大圈，就一个原则：满了就归还给buddy，没满就维持原样。最终目的是维护这个数据结构的基本状态

数据结构 = 几条不变式（invariants）+ 一组"事件发生时把它们重新摆正"的操作。

从安全视角看，一个结构永远会有一些基本规则，即无论如何不能变的，在这里就是：

对象唯一归属每个对象要么在某个 slab 的 freelist 上（空闲），要么已分配；不能两处都在，也不能哪儿都不在
计数与结构一致 free_count 等于 freelist 实际长度；empty/partial/full 由它推出
current 永远可用 current 不能是满 slab——分配必须能从 current 直接拿到对象
partial 链语义链上只放"部分空闲"的 slab；满的不上链，全空的也不上链
满 slab 不追踪满 slab 不占任何池侧结构（没有可分配资源，追踪无收益）
全空必归还 free_count == total 的 slab 必须脱离管理结构并还给 buddy
单一归属一个 slab 至多出现在一个位置（current 槽位或 partial 链之一）
地址可反查任意对象地址能唯一推导出所属 slab 与 cache（free 路径的依赖）

而复杂的行为的每个分支，实际上都是在维护这组基本规则。漏洞就是想办法破坏某条规则

从这个原则出发，也可以推导分配对象时slub的行为

我认为，一个数据结构能否达到它被设计出来的目的，主要在于其设计的规则；而一个数据结构是否能高效地解决问题，主要在于其行为的复杂度。行为为了维护其规则而产生，但行为本身实现的复杂程度决定其运行效率。

buddy和slub是内核分配器。除此之外，还有用户态的分配器。如glibc malloc。这类分配器其具体形式或许有差别，但设计目的都遵循同样的一些原则。围绕这些根本性的东西来把握其具体实现，会更容易搞明白设计者的考量与妥协，也更能从范式或某种更高级的角度思考漏洞产生的原因，并按照所谓“清单式”的方式寻找每个角度的漏洞

这些分配器还有一部分设计没有讨论，即如何在多核/多节点环境下运行，如何做并发防护

进程与线程

物理事实：CPU 是一条执行流，内存是一块线性空间，机器只有一套寄存器和一套硬件

目标：要让它看起来在同时跑很多程序

这个问题本质上是一个虚拟化问题，即：如何把物理资源虚拟成多个可共存逻辑实体

任何虚拟化like的场景都必须解决这三个问题，也就是虚拟化三要素：

表示 = 主体/载体
切换 = 时分复用
隔离 = 空间边界

有必要读一下虚拟化领域的相关论文综述

最终抽象出来的结构就是进程：一个正在执行的程序+其拥有的全部资源与状态

从状态机的角度来讲：

new 已创建，但未初始化完。在调度器眼里不可见
ready 万事俱备，只差CPU。调度器眼里可见，可选中
running 被调度器选中，正在CPU上运行。在调度器眼中就是被选中的
blocked 需要等待外部事件（IO、定时器、信号）不在运行队列，在调度器眼中不可见
terminated 已结束，不再执行。在调度器眼中不可见，接下来会被父进程回收。

进程相关的结构：

课本上一般将进程抽象为一个PCB，但Linux具体的实现并非只有一个PCB。

Linux中，是一个以 task_struct 为中心，用指针连接起来的结构体群

本质上，是做了去耦合的工作：把需要共享的资源（如mm、files、fs、sighand），生命周期与进程不同（mm内存回收再分配、cred RCU延迟回收）、需要原子替换（cred、nsproxy、mm）、工程上体积大或是不常用的冷数据（mm带一整颗VMA树）进行了外置化。

task_struct结构体：

字段组	关键内容	对应的资源
状态/调度	state、prio、policy、sched_entity	CPU时间
内存	mm、active_mm	地址空间
文件	files、fs	fd表、cwd/root
信号	signal、sighand、pending	异步通知
身份	cred（real_cred/cred）	权限
隔离	nsproxy	namespace
关系	real_parent、children、slbling、group_leader 、thread_group	进程树与线程组
执行现场	stack（内核栈）、thread_info、arch的thread_struct	切换的物理载体
索引	task_list节点、pid、se.run_code	被各子系统“查找”的方式

task_struct结构体相当大，约10kb；slub会为其专门开个池子进行分配（ ls /sys/kernel/slab | grep task_struct）

sched_entity（调度实体）是挂在runqueue红黑树上的节点，包含 load_weight（权重）、vruntime（CFS 虚拟时间），EEVDF 之后还带 deadline/vlag。它是"进程能参加调度"的凭证。与进程调度相关的实现密切相关
内核栈 + thread_info / thread_struct
1. task->stack 指向内核栈；当进程触发异常/中断/系统调用时，从用户态陷入内核态。此时会把所有用户可见的寄存器存到内核栈顶（固定偏移的pt_regs）
2. 当进程从进程A切换到进程B时，要完成这个“被调度”的过程，进程A首先要trap到内核态，在这个过程中将用户态现场保存到内核栈顶。当A的执行流被交出时，此时A一定处于内核态，正在执行内核态代码；然后切换到B，此时B也走在B的内核路径上。上面的过程由于在内核态进行切换，所以我们要关注内核现场的保存。内核现场如何保存？将相关的内核寄存器保存到thread_struct中即可。恢复时也从这里取。对于进程AB来讲，虽然其寻找内核栈顶的pt_regs偏移都是相同的，但是由于虚拟内存技术，他们指向的真实物理地址却不相同。

A 用户态
│ svc #0
▼
[内核] kernel_entry → ① 用户现场写进 A 的内核栈顶 pt_regs（此后一动不动）
│  sys_read → 等磁盘 → schedule()
│  ② 内核现场写进 A->thread.cpu_context（x19–x28/fp/sp/pc）
▼
[内核] B 恢复（从 B 的 cpu_context 装载）→ 继续 B 自己的内核路径
│
│  ③ B 的用户现场从哪里恢复？→ 从 B 自己栈顶的 pt_regs（B 早先陷入时存的）
▼
B 用户态     ← 到这一刻，B 的用户现场才被恢复

wait_queue_entry（阻塞的载体）。当进程不应该被调度器看到时，就会被挂到对应事件的wait_queue_head上。事件域可见性的数据结构本体
mm_struct 地址空间描述符。记录了pgd（页表根，符合之前每个进程一套页表的知识）、mmap索引根（红黑树，用于快速查找地址X落在虚拟地址空间中的哪一段里）、mmap_base（mmap区域的起点，与mmap操作密切相关）、mmap_lock（读写锁）、context（ASID TLB用，即前文讲过的给TLB表项打上一个标签。这个标签在这里要存一份）、rss_stat，以及一对经典的引用计数：
1. mm_users 有多少任务在使用这个地址空间，支持线程的技术。进程死亡前起码先清除所有线程
2. mm_count 有多少“主引用”指向mm_struct本身——支持内核线程的技术
vm_area_struct （VMA：一段连续映射）。由于页表本身只描述页粒度，而OS有在多个页组成的一个连续空间上，描述不同段的属性（来源、权限、语义）的需求，因此需要VMA来充当一个地址空间目录
files_struct（文件表）描述打开了哪些文件
fs_struct（文件系统上下文）描述当前工作目录，与路径相关
信号三件套 sighand_struct signal_struct task→pending
cred 凭据
nsproxy 命名空间集合
struct pid + PID哈希表 struct pid记录该进程在每一级PID namspace里的编号；全局PID哈希表负责find_task_by_vpid()之类的查找，即支持命名空间虚拟化功能的结构体

大概了解了一下进程相关的结构体，我们可以了解进程相关的操作：

fork 复制当前执行流

pid = fork();
父进程：pid = 子进程的 PID（>0）
子进程：pid = 0
失败：  pid = -1（errno = EAGAIN/ENOMEM）

子进程从fork返回处继续执行，接着之前的执行流继续执行下去，只有返回值不同。

task_struct里面有的资源，子进程几乎都会一比一复刻一份，但是与锁相关的不会继承。PCB、内核栈、地址空间mm、页表等都会被复制，但PID不同。

当fork()时，具体到内核态，copy_thread()会在子进程内核栈上人工构造两份现场，但是pt_regs的返回值寄存器的内容会被修改，这也是为什么最后会返回两个不同的返回值

由于fork产生的两个进程所享受的资源一模一样，许多资源通过间接引用资源完全指向了同一份，如文件资源。在这种情况下，如何处理两个并行的程序对同一资源的使用带来的并发问题就是重点问题。

同时由于使用的虚拟内存空间不同，COW 写时拷贝，对于fork来说就是相当有效的一个技术。新fork出来的进程被分配了与父进程完全相同的虚拟地址空间，但OS却不用急着真的分配相应的物理空间，而是等子进程跑到那儿要用了才分配。考虑一个情况，当fork出新进程后立即在子进程中运行exec载入了新程序，那么这种情况下刚分配好的物理地址空间又得重新分配，COW技术很好地减少了此时的开销。

execve 进程的执行

execve的语义：用新进程替换当前进程的程序映像

当执行execve时：

执行态全部换掉。地址空间、页表、VMA、TLS这些全部换掉
身份态全部保留：PID、fd表、命名空间、cgroup等，属于进程本身的属性
行为态清零：信号处理函数、信号、定时器等清楚
安全态收紧：根据参数进行凭据替换与一系列安全清理

fork与execve，一个复制程序，一个借尸还魂。这两个原语是一组正交原语。用近世代数来理解：

若进程状态 P = （身份I，上下文C，内容M）

fork: P → P × P （复制，共享关系由 clone flags 决定）

exec: M → M′ （只换内容；I、C 原样保留）

窗口: 任意 syscall 序列 f: P → P （fork 与 exec 之间的用户代码）

组合子: 顺序(;) 、并行(|) 、递归（子进程内再 fork/exec）

语义空间 = 由 {fork, exec, 窗口, 组合子} 生成的全部表达式集合。

在Linux中，进程都是由fork创建的。在这种情况下，必然有第一个进程不是由fork创建的，即PID 0；这个进程是被编译进kernel image的静态数据结构init_task。然后由init_task被内核由kernel中的fork部分（即抛开系统调用入口的fork内部函数部分）给创建出PID 1(init)和PID 2(kthreadd)

除开这特殊的插曲以外，所有进程都是通过fork创建的，因此OS可以通过fork来追踪进程之间的关系。在task_struct中，每个进程都会记录自己的父进程和子进程，进程之间因此构成了树结构。

OS正是通过该树结构对进程进行管理的。

当OS启动时，PID 1的init会将kthreadd进程fork出来，然后所有由内核创建和管理的进程都是由它（kthreadd）fork出来的。等到一切准备就绪之后，init会fork出一个login进程来要求用户登录。当登陆通过后，会fork出一个shell来与用户交互。

通过进程树结构，kernel在此基础上有了监控、回收、信号分发等一系列行为。

进程间监控：wait。实则进程的监控需要从多个方面进行考虑，监控其状态、资源、行为、关系、历史等。wait关注的则是进程的状态。wait只能由父进程对子进程施加，并回收进程占用的资源和终止时的status。如果一个进程没有被wait，则其是zombie进程

进程组：诞生的目的是面向用户态，即帮助用户态进行作业控制。在用户态眼中，a | b | c作为一个作业整体，被单独视作一个作业单位。为了描述这个用户眼中的作业的基本单位，于是有了进程组

在默认情况下，父子进程属于同一个进程组。但Linux为子进程提供了脱离当前进程组的接口setpgid，可以创建新进程组或在进程组之间进行移动。在对用户提供的服务上，进程组提供了作业控制服务，但是其底层实现原理是控制信号的传播范围（比如发送kill信号，kill被给到整个进程组的进程）

而会话SID则是进程组的集合，由一个或多个进程组构成。同时要认识到，Session是对用户无感的，整个结构中完全不存在uid的成分。SID主要作用是将进程组区分为前台进程组和后台进程组，在这种划分下，才可以确定前台用户输入的信号到底是给正在运行的诸多程序中的哪个程序。可以说是“计算机表现出来的并行”为了“人类思考与输入的串行”而定制的一个中间接口。

综上，在每个进程的task_struct中都会有PID GID SID三个属性，用于构建相关的数据结构

要继续深入，可以讨论fork的局限性，fork的替代、fork的进一步包装等等内容

线程

随着多核处理器的普及，并发能力逐渐充裕。在资源贵，并发/处理能力充裕的这种背景下，衍生出了对进程原本“资源+执行”耦合系统的一次分离：即将资源与执行分离开来。进程保留资源，线程成为执行单位。

最终，即可以在减少内存资源开销的情况下支持并发

一个进程内的线程共享原进程的所有资源，只有执行状态（寄存器/栈）、task_struct、内核栈要新建。为什么还有task_struct？因为其内嵌的部分就是执行状态所必需的内容。

从根本来思考，如果从进程到线程，是把资源与执行的原本耦合给分离开来。要支持这种分离，就需要内核在相关层次上提供语义？在内核眼中是多个task，但这多个task在宏观上属于同一个任务，所以要将微观的并发多个任务通过中间的组在宏观上统一成一个任务，这就是内核提供的组语义？顺理成章，这个组语义应当是用来权限控制、资源控制等等的；但是我想，为什么不直接用进程套壳呢？kernel原本就已经对进程实现好了资源控制等内容，在进程中嵌入多个线程不就可以直接搞定吗？但是这里我又想到，这样在内核那里就无法区分可调度的多个任务，无法灵活调度了。但要解决这个问题，把调度实体从进程中单独拆开来不就好了吗？也就是说，我只要对进程task_struct做一些改动就可以让进程概念成为原生的组语义啊

经过进一步了解发现，我提出的这个路线实际上就是Mach、Windows、Solaris等OS的思路，但不是Linux的思路。

由于Linux对各个资源域进行了单独的抽象，再观察task_struct的结构实现，会发现这种中心结构+结构群的表达方式，其实天生就是资源与执行解耦的。现在只是将原本解耦又耦合的对象进行了重新的解耦而已。很自然的思路就是直接修改task_struct中的映射关系，直接将代表资源的属性映射到同一份上，将代表执行的属性进行独立生成，就能很自然地实现线程的基本模型。

在这里回头看，mm_users、mm_struct等属性的作用就很明显了，即在大家共享同一份资源时，谁来负责释放所有的资源。就好像大家共用同一个教室进行学习，最后一个走的要关灯锁门一样。

这种可共享域的架构其实在最开始没有预料到线程的出现，但是这种架构在历史的长度中被证明是具有前瞻性的架构。往后当新资源类型出现时，Linux的默认做法就是新增一个可共享域。同样的架构后来又兑现了命名空间，进一步产生了容器技术

在linux kernel眼中，从进程到线程，从来都只有task而已。

关于“用户级线程”与“内核级线程”

其根本区别在于，到底是否被内核的任务调度器所看见。上文提到过，Linux kernel中只有一种task，其n个线程在内核调度器眼中也体现为n个任务，这种线程是真正能够在多核处理器上进行并行的

而用户级线程则不同，其常由用户态的各种库所实现，也有自己的用户态调度器，但在内核调度器眼中实则只有一个task。这种用户级线程实际根本无法在多核处理器上达成“并行”的效果，只能做到“并发”，即让用户觉得多个线程在同时推进。但用户级线程由于不被内核调度器看到，也有其好处：

避免内核调度器进行任务调度导致的性能开销，通过汇编原语实现用户级线程切换，只需要换一个栈（毕竟栈只是用户内存空间中的一个区域），保存几个寄存器的数据即可。创建和销毁的开销等也几乎免费，非常轻量化。
策略自由：用户态线程可以高度定制化

但是坏处如下：

不被内核调度器所看到，无法在多核处理器上真正并行
由于被内核调度器观测为一个task，一旦有任何一个线程进行了阻塞操作（IO等），会导致整个task中的所有其他线程也被丢进等待队列进行冻结。

只用用户级线程和只用内核级线程属于N：1和1：1模型；而在此之外还有n：N模型，即用户态创建n个用户级线程，同时在内核调度器眼中有N个task，这个模型是现代普遍使用的线程模型。

线程控制块TCB 线程本地存储TLS

TCB在教科书中被描述为与PCB相似的线程控制块。在上文说过，Linux中不论线程还是进程，统一被抽象成task_struct。而在用户态中，用户态线程的TCB其具体实现多由用户态库自行决定。

对于Linux平台上的库pthread线程库来说，pthread结构体就是用户态的TCB。

线程在概念上实现了资源与执行的解耦，Linux的资源域概念也一定程度上支持了这种解耦，但是仍然有一部分执行是依赖于全局变量的，这部分全局变量放在静态存储区中.data而不是栈中，无法成为每个线程的私有资源（历史包袱）。这部分无法做到完全解耦，于是这部分资源必须要随着执行而独立出来，变成每个线程一份的资源。而实现这个思路的技术就是TLS

TLS能够将这部分资源复制出来进行私有化，让每个线程使用相同的全局变量名，通过相同的偏移（但不同的基址）访问和修改实质上私有的数据，而不会对其他线程造成影响。

基于x86的Linux，对于每个线程的TLS，在其task_struct.thread.fsbase都会保存一份自己的TLS基地址，当切换到该thread后，会将基地址载入FS寄存器，实现相关变量的快速存取

操作系统的任务调度

任务调度的本质是资源配置，操作系统的任务调度本质上是对各种操作系统内部资源的实时配置，以最大程度达到系统设计目标

在OS语境里，只涉及CPU的时间资源，也就是说，内核调度器本质上是在对CPU时间资源进行实时配置。OS中的稀缺资源：内存、I/O、网络等，都有自己的一套分配/调度机制。而cgroup这类控制框架，可以将各种资源统一变成”可控制配额“

要最大化达到系统设计目标，就要在多个互相冲突的目标之间按策略权衡——所谓仲裁

要进行时间资源的配置，首先要完成对时间资源的量化——时间片。可以将一份时间片理解为一份资源。时间片的粒度大小会影响资源再分配频率，同时分配本身也会有性能开销，所以需要在矛盾间协调

在Linux中，任务调度的基本单位是task，其结构是task_struct 其内部的__state、on_rq、prio、 sched_class，以及 se、rt、dl等字段都与任务调度相关，记录一个任务的状态及其所属调度类（这个任务按哪组规则调度）

用htop可以显示当前操作系统中任务调度的情况：

可以看到，有98个task，有1个task正在running，这个指标一般可以反应当前正在工作的CPU核心数量。

调度器的主要作用是做决策：

从运行队列中选择下一个运行的任务
决定该任务具体在哪个CPU核心上执行
分配多少时间片给该任务

做完决策后，相应机制便会将任务执行在对应的CPU核心上。

那么对于调度器的设计，就有一些设计目标，这些设计目标会受到现实条件的约束，在不同设计目标之间进行取舍，就衍生出多种多样的调度决策。接下来就介绍这些具体的设计目标或者说是调度指标

在不同场景需要不同的目标来知道调度策略的选择，常用的调度指标包括：

与性能相关的吞吐量（单位时间能完成多少任务）、周转时间（任务从到达到完成花了多久：完成时刻-到达时刻）、响应时间（任务到达后多久第一次得到服务：首次运行时刻-到达时刻）
非性能指标，如公平性（各任务得到的CPU是否符合约定的份额或权重）、资源利用率（是否所有硬件资源得到充分利用）
特有的需求，如实时性，能耗

这些指标在不同场景下的取舍，基本覆盖了时间资源调度的经典目标

具体到使用场景上来说，比如批处理任务（如复杂的科学计算、模型的训练）这种任务，被执行时无须与用户进行交互，主要调度指标是吞吐量，需要让吞吐量尽可能高，让周转时间尽量短

对于交互式任务（例如程序调试）来说，需要对用户进行相应，因此需要确保响应时间，这是主要指标

对于与物理世界进行交互的任务，如车载系统的传感器等，需要满足实时性

对于能耗极端场景，如移动终端设备，则重点考虑能耗

有一些指标是所有场景通用的，如资源利用率。最后，系统使用调度器但不能够让调度器本身造成过大开销，所以调度器做决策时间需要尽量短

以上只描述了调度指标多样性，实际调度器还面临以下挑战：

基于有限信息做决策。调度器可获取的信息有限，没有上帝视角
任务间的复杂关系。许多任务间可能存在互相依赖的关系，因此调度器不能把它们拆开看

由于调度器获得的信息并非所有，我认为其是在有限信息下做局部最优决策。而宏观场景上的调度指标策略选择，则是矫正这种短时间局部最优决策，让其在长时间场景上整体符合相对较优结果。

更准确地说：调度器是在有限信息下做在线决策；长期指标规定它希望整段运行历史达到什么结果；调度策略利用当前状态和过去的记账，尽量让局部动作服务于长期目标，但通常不保证全局最优。

本质在不确定信息下逼近长期目标

Linux为用户提供了不同的调度策略，允许用户根据任务的种类自由挑选合适的策略（很难得到一个各方面都完美的调度策略的侧面印证）

调度机制

进程从生命周期角度讲，是一个状态机模型。对于这个状态机模型，进程调度机制则负责状态间的转换。

进程调度根据职责的不同，具体分为长期、中期、短期调度

长期调度。负责控制哪些任务可以由新生状态到预备状态。这一步的现实考量是，将一个进程从新生状态到预备状态，需要创建进程并为其初始化分配资源。如果大量进程短时间被通过该管道，会造成各种资源短时压力剧增。可以将其看作一个阀门，被放入池子的任务才具备被调度的资格。
短期调度。负责控制任务在预备、运行、阻塞状态间的转换。被长期调度阀门放进池子里的任务，已经进入了预备状态。此时这些任务是事实上可以被调度的。短期调度也是事实上做出调度决策的主体。
中期调度。实际上是换页机制的一部分。将内存资源考虑进调度的考量，如果当前内存总量不足，则中期调度会挂起被短期调度管理的任务，目的是降低任务占用的内存总量。该进程会被设置为挂起状态，无法被短期调度看见。换页机制会倾向于将被挂起的任务所用的物理页换入磁盘，并在适当时期重新激活它。

单核调度策略

到达时间：任务进入任务队列时的时间

运行时间：任务第一次被调度执行到任务完成总花费时间（更准确地说，是完成该任务所需消耗的CPU时间）

对于单核上的时间调度问题，可以将其拆解成两个正交问题：

当前选择哪个任务进行调度
被调度的任务应该执行多久

在这两个正交问题的视角下，调度策略的设计可以看成一张二维坐标系：

先到先得：First Come First Served 只需要维护一个队列就可以实现该策略。不需要预知任务信息，也没有将许多重要因素纳入考量，因此很难被直接应用在复杂系统中。在长短混合任务中对短任务不友好；在IO密集型任务中对所有任务都不友好。对计算密集型任务比较友好，单可能导致IO密集型任务长时间无法执行
最短任务优先：Shortest Job First 必须预知任务的运行时间。所以只能应用在一些比较固定的应用场景。对于难以预知确切运行时间的任务的场景则不友好。同时由于无法重新做选择，因此表现严重依赖于任务到达时间点。消耗时间短的多的任务可能晚于首次调度决策时间点到达，因此无法被重新选择优先执行，从而无法完全发挥最短任务优先的策略。
最短完成时间任务优先：Shortest Time-to-Completion First 利用抢占思路修复最短任务优先的弊端，使得后到的短任务可以通过抢占的方式被优先执行。FCFS与SJF都是非抢占式，而STCF是抢占式。弊端：长任务饥饿。
时间片轮转：Round Robin。重点考虑响应时间，无需预知任务的运行时间，也不会出现长任务饥饿情况。需要重点考虑时间片粒度大小——在调度器开销与小时间片带来的收益之间权衡。同时相应来说，保证公平性的情况下，对任务的周转时间不友好
优先级调度：选择函数（根据优先级确定选谁） + 重决策函数（何时重决策）每个调度算法的本质就是如何定义优先级。对于FCFS，先到的任务优先级最高；对于STCF，所需时间最短的任务优先级最高；对于RR，每种任务优先级相同。
- 多级队列：Multi-Level Queue，MLQ
  - 选择函数：构建一组优先级不同的队列，每个任务预先分配优先级，落入不同的队列中。选择任务时优先选择高优先级任务的队首任务。
  - 重决策函数：跨队列抢占（高优先级队列有任务就绪就会进行抢占）、队列内部可以针对性的选择不同策略，如FCFS或RR
  - 弊端：1.高优先级任务源源不断可能导致低优先级任务饿死；2.优先级反转问题。由于任务之间可能存在依赖/并发关系，引入这些关系后可能会导致低优先级任务先于高优先级任务而执行。可以通过优先级继承解决 ;3.需要提前预知任务类型，进行优先级分配
- 多级反馈队列：Multi-Level Feedback Queue, MLFQ。对比MLQ即引入“反馈”，可以动态设置优先级：
  - 选择函数：与MLQ不同的是，优先级为动态推算，而非预先分配。如何推算优先级：新任务预设为“短”，直接放进最高优先级队列；每层设置时间预算，单个任务花光预算就降级。最后导致：短任务始终在高位，长任务逐渐下移到低位
  - 重决策函数：跨队列抢占、队内RR换任务、时间预算花光时降级、定时全员提升到最高级（防止长任务被饿死，也能够适应复杂任务在时间尺度上行为的变化）
  - 如此一来，交互类的短任务能够保证交互；CPU密集型的长任务随时间被调度到底层队列，享受更长的时间片
  - 需要对系统的具体细节深入了解，才能调整好对应的参数，实现高效的MLFQ策略。

公平共享调度

上面介绍的调度策略，都是从单任务角度去迎合各项指标（周转时间、响应时间等）。但接下来要引入更高层级：多个任务聚合为单个group或user，在这种情况下，虽然执行角度依然是单个任务，但是调度角度已然上升到更高层次。

在这种情况下，迎合的首要指标变为：高层次组织在总资源中的占有比例

为了满足该指标，公平共享调度 fair-share scheduling应运而生。这类调度器会量化任务对系统资源的占有比例，从而实现对资源的公平调度。

从另一个角度看待问题。经典调度是在(选谁 × 何时收回) 的二维平面上研究调度问题，而现在引入了第三根轴：配比/归属轴。于是调度设计空间变成三维：谁跑、何时换、凭什么身份分多少；

引入第三维后，空间结构便自然衍生出层级或组织概念。

在实际场景中，为了方便管理，将任务分组（称为任务组），以组为单位分配份额。在组内进一步进行任务调度以分配资源。

所以实际上，公平共享调度策略和经典任务调度策略是共存的。

彩票调度拥有更多份额的组在进行任务调度时，有更大的机会被选中。本质上是通过概率进行单次选择，在大数定律的作用下使得概率逼近份额分配的期望
- 彩票转让优先级继承的彩票调度版，通过彩票转让的方式避免高优先级任务被低优先级任务以锁等方式卡住
- 彩票货币组的总份额变化时，等比例扩大内部子组的份额，类似于发行自己的货币，通过增加一层货币的抽象，将绝对数字转变为相对单位，带来诸多好处
- 彩票通胀在彩票货币的机制下，铸币权掌握在父层/管理员手中；而如果将一部分铸币权下放到任务本身，则任务可能狂印货币，稀释其他所有任务的份额，最坏情况下会占用组内绝大部分的CPU时间。这种机制必须依赖于任务信任，即不能存在恶意任务。
- 随机数带来的问题：由于选择任务时依靠概率进行选择，其前置是随机数生成，所以可以从随机数生成角度思考其缺陷与对应的安全问题。
步幅调度确定性的公平共享调度策略。假设A与B的权重为6：3，则设定A的stride为3，B的stride为6。每次被调度相当于走一步，如果双方走相同的距离，则能够保证A一定被调度的次数是B的两倍。

通过设置虚拟时间的方式，让每次任务被调度时增加一定的虚拟时间，维护服务对象的虚拟时间相同。任务的份额之比对应了任务步幅的倒数之比。

实时调度

服务指标是实时性：在确定的时间范围内处理完任务。

根据任务超过截至时间的后果，实时任务可以分为两类：

硬实时任务系统无法承担任务处理超过截止时间的后果
软实时任务偶尔可以超过截止时间完成，其结果是可接受的

根据被触发的时间，实时任务可以分为三类：

周期任务任务到达时间遵循一定周期规律
偶发任务非周期，但同一任务两次到达有最小间隔
非周期任务随机到达，无最小间隔

一种通用的调度策略：借用虚拟时间。同时处理批处理、交互式与实时任务

步幅调度策略，通过虚拟时间的概念达成公平共享调度。在步幅调度中，选取下一个任务的策略是选择当时虚拟时间最少的任务。换句话说，虚拟时间在当时情况下代表了优先级。在这种基于虚拟时间的公平共享调度基础上，通过一定程度上自由设置任务的虚拟时间，就可以引入优先级调整。

BVT如何实现优先级+公平？

AVT actual virtual time 实际虚拟时间
EVT effective virtual time 有效虚拟时间

EVT = AVT - warp(借的时间份额) x Flag(1or0 是否借账)

调度器永远选择EVT最小者

若有A B，avtA与avtB都是100s，则当A借20s，此时evtA为80s，那么调度器就会一直执行A，直到evtA = evtB = 100s为止，此时avtA为120s， avtB为100s，然后flag复位，evtA会直接变为120s，相当于把未来属于自己的20s跑了

从安全角度考虑，会限制warp大小。

原始论文：Duda & Cheriton, “Borrowed-Virtual-Time Scheduling”, SOSP 1999

思想血缘：后续 CFS 的唤醒抢占（wakeup preemption）、sleeper fairness、EEVDF 的 latency-nice

多核调度策略

在多核系统中，任务会同时在多个CPU核心上并行执行，因此多核调度策略需要考虑：

当前应该调度哪个/哪些任务
每个调度的任务应该在哪个CPU核心上执行
每个调度的任务应该执行多久？

之前的单核调度问题，是在一个资源上进行排序，本质上只有一个时间维度；而现在的多核调度问题，则是在时间基础上演化为了【时间x空间】

单核调度问题的解决思路，是将“在一个资源上进行排序”的问题，分解成了两个正交语义，并在引入分配约束后演变为三个正交语义，并在这三个正交语义构成的向量空间中寻找解，也就是相应的策略。

单核调度问题：在时间轴上，有正交语义：选择(f) x 触发(T) x 份额(q)

多核调度问题：时间 x 空间正交，所以在时间轴上可以采取相同的问题分解思路；空间上也可以用相同的正交分解：选择（放哪） x 触发（迁移/再平衡） x 份额（分哪些核）

负载分担：多核维护一个全局共享队列，哪个核空了就直接从里面取。即空间域上的FCFS
- 由于多核维护一个队列数据结构，为了维护该结构必须处理同步问题，随着核数量的增加该部分开销不可忽视
- 任务在不同CPU之间切换带来的开销，如重新载入缓存，TLB刷新等
协同调度：当想把一个任务切分为多个子任务（之间可能具有依赖或必须同时在场有通信关系），放在多核上进行并行计算时，如何良好地处理这种关系？这个问题显然发生在parallel computing场景。在paralell computing场景中，整体同步并行 Bulk Synchronous Parallelism BSP计算模型将长须的执行分为以下部分：1. 并发计算：每个CPU核心独立计算自己的子任务 2. 通信：CPU核心之间通过通信交换数据 3. 同步：一个CPU核心在到达程序设置的某个屏障点时，需要等待其他CPU核心也到达这个屏障点，才能执行后续代码逻辑。

协同调度的目的是：尽可能让一组能并行的任务并行执行，避免调度有依赖关系的任务

协同调度的一个经典策略是群组调度 gang scheduling。将“可并行或需要共时“的任务设置为一组，并且以组为单位同时上CPU进行执行。如同AE中，AE并不负责处理订单中原料的依赖关系，只将一组可并行的原料输入可并行的机器，提高产出效率，至于依赖关系在时间上依然是串行的。
两级调度：每个CPU核心维护一个本CPU的本地调度器，所有本地调度器由一个全局调度器进行管理。全局调度器会追踪每个CPU的负载，并根据CPU负载将task进行分配。当一个task被分配至per-cpu-run-quene时，它将一直在这个队列中，不会迁移到别的CPU上执行。好处是局部性很强，不会引入任务切换CPU带来的一系列开销；坏处是可能造成负载不均

负载追踪

由于两级调度可能会造成负载不均问题，为了解决该问题，两级调度引入了负载均衡策略：

通过追踪每个CPU核心当前的负载情况，将处于高负载的CPU核心队列的任务迁移到低负载的CPU核心上，尽可能保证每个CPU核心的负载大致相同。在这个问题上，负载均衡与局部性是矛盾的，所以要进行取舍。在负载均衡收益>局部性收益时，选择负载均衡策略。而负载均衡的前提是准确追踪per cpu的负载

过于精确追踪负载情况会带来高开销。如何保持低开销的同时对负载进行精确追踪是调度器设计的一大挑战。

运行队列粒度的负载追踪。即追踪per cpu run queue的长度，长度越长负载越高。这种策略在Linux 3.8版本以前被使用。由于缺乏任务本身的信息，导致负载追踪既不够精确也无法直到负载均衡进行任务迁移
调度实体粒度的负载追踪。per-entity load tracking PELT 当前Linux正在用的负载均衡算法

以1024微妙为一个周期，记录任务处于可运行状态的时间（正在运行+等待被运行）记为x微秒（唯一能从行为上衡量负载的数据，等待被运行时间越多说明当前CPU越忙），该任务在第i个周期对当前cpu的利用率为x/1024，而对应的负载Li为scale_cpu_capacity (量化的CPU能力)* x / 1024

这个数据代表task在每个周期内的负载，但PELT需要计算一段时间内任务所有周期的累计负载记为L。对于计算任务当前负载的PELT来说，过于久远的历史负载信息没有太大参考意义，距离当前时间点越近的周期应当有更大贡献，所以采取衰减系数y来衰减之前周期的负载：

计算周期 P = 1024 µs = 2^10 µs （记一"笔账"的时间粒度）

衰减因子 γ = (1/2)^(1/32) = 2^(−1/32) ≈ 0.9785720620…

（由"半衰期 = 32 个周期"定义：γ^32 = 1/2）

衰减 n 周期 γ^n = 2^(−n/32)

半衰期 32 × 1024µs = 32.768ms（文档常写 32ms）

归一化常数 Σγ^k = 1/(1−γ) ≈ 46.67（内核整数化：LOAD_AVG_MAX = 47742 ≈ 1024×46.62）

$L_i = \text{scale\_cpu\_capacity} \times \frac{x}{1024}, \qquad x \in [0, 1024]\,\mu s$

$L = L_0 + L_1\gamma + L_2\gamma^2 + L_3\gamma^3 + \cdots$

无穷的历史被压缩为一个滚动更新的数

总的来说，PELT通过这种方式计算出每个任务的负载，从而计算出每个运行队列的负载

开销小且效果好，目前是Linux底层所使用的负载追踪算法

负载均衡

PELT提供了相对准确的负载追踪，但同时也要设计一个高效的负载均衡策略。需要考虑

CPU核心间不对等
任务跨CPU迁移会引入开销

由于这种多核CPU负载均衡调度策略必须与底层硬件架构充分嵌合，所以必须考虑到现在真实的多核架构

以服务器CPU架构代表NUMA Non-Uniform Memory Access 非一致性内存访问架构为代表：UMA 一致内存访问，所有核通过一条总线访问同一份内存，延迟一致但总线抢占

NUMA：把内存按节点分区，每个节点有自己的内存控制器+本地内存。代价是非一致访问延迟，即访问非本地内存会带来大延迟（1.3x - 2x 甚至更多）

如果OS将一个task从一个NUMA节点迁移到另一个NUMA节点，会严重影响任务的执行效率。

另外，以超线程为例，一个物理核在逻辑上被分为两个逻辑核。task在同属一个物理核的逻辑核之间切换的开销，会比在不同物理核的两个逻辑核间切换的开销小很多。

以下介绍Linux的负载均衡策略。Linux的负载均衡策略维护两个数据结构，以这两个抽象的数据结构层次，适应不同类型不同架构的物理CPU拓扑

sched_domain 调度域。是拥有相同特性CPU核心的集合，在这些CPU核心间可以进行负载均衡。一个调度域保存一个或多个调度组
调度组。调度组是一个调度域内进行负载均衡的整体单位。

这两个概念是互相嵌套的。一个调度域中的N个调度组，其N个调度组本身又可以视作N个第二层调度域。最后，会自然形成一个多层结构

在这个多层结构中，理所当然的，越近的调度域/组，task migration的开销越小，越远开销越大。所以任务迁移应当积极在近组，消极在远组。遍历域内【所有】组 → 每组算账本（组负载 = 成员负载之和；组算力 = 成员算力之和）→ 选【最忙】的组 → 组内选【最忙】的 runqueue

而进行任务迁移的方式也分两种：

轻负载core pull 重负载core的任务到本地；重负载core push自己的任务到轻负载core。显然应该采取前者，因为不应该由本来就重负载的core继续承担调度的开销

Linux的能耗感知调度

在嵌入式设备等场景下，引入能耗作为硬约束，在这种情况下需要实现调度保证提供足够好的性能。在这种设备上，混合处理器架构为主流，大核（处理速度更快，能耗更高）与小核（能耗较低，处理速度更慢）共存。调度器可以将任务调度到不同的CPU核心上以达到节省能耗的目标。

我的想法是这样的：要进行调度，就要收集到足够的信息。EAS需要收集的信息是哪些？这些信息是如何收集、如何被计算、如何代表相应性质的？这些信息收集到之后，如何结合硬件本身的性质进行调度的？

进程间通信

把单个进程理解成一个系统，则系统与系统之间，如果要构程更大的系统，产生“涌现”，则必须明确系统与系统间的边界，确立系统与系统间的接口与通信。前者已经被数据结构与内核划下的界限所解决；后者在我们提出进程间通信前则还未解决。

为什么是进程间通信？要实现两个系统间的跨系统信息交流与协作，在我眼中有两种方法：1. 两个系统外构建一个更大的结构，对这两个系统同时具有管辖权限，可以通过这个更大的结构进行中转通信。我认为现实世界中中国的行政系统就是基于这种方式解决问题的； 2.在系统与系统间设计好接口直接通信

由于在OS中，有权限同时访问多个进程的内存空间的系统，只有内核，同时为了保证安全性，第一种方式，即在多个进程外设置更大的结构，是不可行的；第二个方式则衍生出所谓进程间通信。

如果是所有通信都交由内核中转，必然造成内核负载加大，同时随着系统构建复杂性增加，所有需要用户态进程解决的问题都会慢慢上移到内核，那么用户态进程实际存在的意义就不大了。因此必然是内核态做审核与通道构建，而进行信息交流是用户态进程自己的任务

以上都是我自己的理解，不对其负责。

通信是隔离的对偶。而隔离是抽象的地基，所以任何系统中都存在隔离，那自然也存在通信。子系统所构建出的更大的系统，其系统性质 = f（子系统自身性质，通道语义，拓扑，协议）

以上都是我自己的理解。

在具体开始了解Linux的进程间通信策略与机制前，我们需要先对通信本身做认识。先建立一个与具体机制无关的要素模型

通信的非平凡定义：在两个隔离的执行流之间，建立一条受控的信息路径，并协调两端的时间

隔离是通信的前提，通信问题是“在不破坏隔离的前提下传递信息”
受控：传递信息需要跨越边界、跨越边界的过程需要被控制。如何找到对方+谁被允许。这是通信的安全面
信息路径：信道、数据面。物理上只有两种可能：复制或共享。
协调时间：如何规定动作，时序，因果

六要素：

隔离：边界是什么？在Linux里体现为地址空间/mm、namespace
表示：传什么，如何编码？在Linux里体现为字节流本身，至于译码解码都在用户态
通道（数据面）：信息如何传递？在Linux中体现为复制+共享（会被侧信道攻击）
同步（控制面）：何时传，何时收？在Linux中体现为队列、阻塞、锁等内容
会合（命名）：怎么找到对方？在Linux里体现为fd、路径、抽象名等
授权与失败：允许通信、通信失败的处理。在Linux中有配套的权限、EOF等

由于在Linux中，正规进行信息传递的数据面只有复制 + 共享两条路可走，因此所有IPC都基于这两种方式进行实现。

基于共享的通信机制

假设内核已给两个进程共享了一块共享内存。有了共享内存，两个进程相当于有了一个可以交流的中间缓冲区，可以通过这个缓冲区进行通信。一个简单的模型是A和B在这块内存中各有一个独立的消息槽，双方可以往自己的槽内写内容，可以往对方的槽内读内容。对于每个槽，其是一个单工信道，两个槽组合起来就是一个半双工信道。每个槽都是一个两态状态机（无效+就绪）；用更学术的话说，这是一条每方向深度为1的单生产者-单消费者（SPSC）缓冲 + 忙等状态位协议。

对于每个槽内部的数据，一种常见的通信数据的抽象是消息 message，包含头部与数据段。该模型即依靠message中的头部的数据位来设置自身所在槽状态的：发送者会将消息拷贝到对应的槽中，完成后依次设置头部中的状态，而接收者会持续轮询头部，一旦观测到状态信息为ready，即可以开始读取，然后发送者会轮询接受者的槽，等待接收者用相同的方式给一个response

深入了解，要问通信带宽和时延表现、消息数据段长度设置、除了轮询有无更高效的通知方式

上述是《现代操作系统原理与实现》中描写“一个简单的通信模型”的大致内容。

我是这样思考的：由于共享机制提供的服务及其简单，即只提供一块共享内存，不保证其他任何事务，所以如果要在共享提供服务的前提下，考虑剩下的六要素，必须要将表示（即传递的字节流）的内容与其他要素做耦合。所以消息这种针对字节流的复杂格式协议封装就刚好嵌合进了需求？

所以基于共享的通信机制，要支持复杂的信息传递，只能是在共享的基础上进行消息传递，甚至将许多控制面内容下移到用户态，让用户态来实现，我相信也因此一定有对应的安全问题。

而基于复制的通信机制，则可以数据抽象粒度的不同，被划分为几种：

通知/事件（只搬“一声响”）：信号、eventfd
字节流（连续的水流、无边界）：管道、流式socket
消息（一件一件的包裹，有边界）：消息队列、数据报socket
调用（一问一答，连配对都包了）：RPC、binder、D-Bus

基于复制的通信机制，则需要操作系统内核提供相关的接口。因此针对上述四种，甚至内部更加细分的数据抽象粒度，衍生出了多套不同的内核接口。

而由于有了kernel这个第三者介入，之前提到的可以替代轮询的高效通知方式也就有了眉目：可以借内核对任务的调度来入手，当一个任务等待消息时，将其设置为阻塞态，避免CPU空转；而当任务等待的消息到达时，将其设置为ready。而由于整个信息的传递过程经过内核，可以在相关的执行路径上设置hook来完成任务状态的转换。

IPC也分为同步与异步。同步IPC，在宏观上表现为函数调用，因为消息发送者往往等待接收者进行回应后才能脱离阻塞状态，在宏观上就表现为好像进行了一次函数调用。而异步IPC，其在发起异步请求时，不等待其最终结果，可以继续执行其他不具有依赖性的动作，等到事件到达后，内核再通知等待者，由程序处理结果。一般来说，IPC是否维护相关的缓冲数据结构，就会在一定程度上决定IPC设计是同步还是异步的。

进程间的隔离为通信带来的一个问题是：通信的双方很难确认对方的状态，但IPC本身又代表了任务间存在一定的依赖关系，一旦在依赖关系的上游恶意进行阻塞，很可能会导致正常任务停摆。为了处理这种无意或恶意的消息等待问题，需要引入超时机制，允许发送者/接收者指定其发送/接收请求的等待事件，如果超时仍无反馈，则由kernel介入：1.对该过程收尾 2.返回一个错误。在实践中，超时机制很难确定好这个合理的超时时间，但也暂时没有更好的替代方案。

容易理解的，通信也分为一对一通信与一对多广播，用另一种说法是直接通信与间接通信。前者需要指定某一个确定的对象进行信息传递，而后者则需要一个中间的信箱来完成通信，多个对象间通过信箱来传递信息，消息的发送者眼中只有信箱。

System V 进程间通信权限管理

这里讲IPC身份识别+权限管理，后续再结合文件系统回来补充

自底向上地构建文件系统：MYFS

最底层，存储设备提供的能力：按地址读写

在常见的块设备接口中，可以把SSD/磁盘堪称一串带编号的逻辑块：

块号： 0 1 2 3 …

内容： [数据] [数据] [数据] [数据]

这里先假设每块是 4096 字节，方便推演；实际设备和文件系统的单位可能不同。

设备接口在概念上允许操作系统发出这样的请求：读取从第 100 块开始的 2 个块、把这 4096 字节写入第 200 块

接下来，上层如何对这些数据进行组织？

由于内存的数据会在断电后丢失，因此想在内存中存储数据来对文件系统进行组织是不可行的，或者说不能只靠内存中的数据。

要将组织文件系统的元数据长久保存下来，其存储本身也得被保存在磁盘中。

重启后，操作系统需要一个位置已知，格式可识别的入口，从它开始逐步找回整个文件系统。

先约定：从哪里开始读取

假设设备有1024个块，每块4096字节。那么规定，0号块为超级块，用于描述整个文件系统；1号块为空间位图，记录块是否被占用。2 - 9号块为文件记录表，描述每个文件；10 - 1023块用于存放文件和目录的内容

这些约定由文件系统实现定义。格式化，就是按照相关约定，写入初始管理信息，建立一个可以使用的空文件系统（自然，不必把设备上每个字节都清零）

超级块：让系统知道后面该怎么读

超级块中可以存储这样的信息：

{格式标识：MYFS、格式版本：1、块大小：4096字节、总块数：1024、空间位图位置：第一块、文件记录表位置：第2块、根目录的文件记录编号：1}

这类描述整个文件系统的元数据，就称为超级块

挂载时，文件系统驱动读取约定位置，检查格式标识和参数，再根据其中的地址找到其他结构。

此时获得的能力：重新识别并解释这片空间。

空间位图：知道哪些块还能用

给每个块安排一个二进制位，0表示空闲，1表示已占用。1024个块只需要1024位即128字节就能记录占用状态。格式化时，元数据存放的相关块就需要标记为已占用。以后分配空间时，就可以在为途中寻找空闲块，将其标记为已占用，然后把块地址交给文件组织层。

文件记录：把块归属到一个文件

因此每个文件还需要一份记录，例如：

{文件记录编号：2、类型：普通文件、有效长度：6000字节、内容块：11、12}

两个块能够容纳8192字节，但有效文件长度仍然是6000字节，最后一块多余的空间不属于文件的有效内容。在许多Unix风格文件系统里，这种文件描述结构叫inode。

此时获得的能力是：通过文件编号，找到文件的内容和长度。

文件名：如何通过文件名（人类认知的符号），索引到对应的文件编号

即，我们应该建立一条链：文件名 - 文件编号 - 文件的地址、内容和长度

只需要在根目录保存一张映射表就可以了。

刚才提到，我们通过“文件记录”，将块以文件的抽象形式组织了起来。很关键的是，内容块是有顺序的，这里我们的MYFS姑且将其实现为一个列表[11、12]

对于上层来说，文件是从偏移0开始的一串字节。MYFS根据数据块列表，将这串字节映射到设备位置：

文件内的字节偏移：0 - 4095 对应块11，块内偏移0-4095

文件内的字节偏移：4096 - 5999 对应块1200，块内偏移0-1903

虽然两个设备块相距很远，文件内的字节偏移仍然是连续的。这个连续性来自MYFS保存的顺序。

到这里，MYFS向上提供一种新的操作：read(文件编号，文件内偏移，字节数)

然而，我们应该建立一个文件名到文件编号的映射，这样一种映射就叫目录项。把一组目录项放在一起，就构成一个目录：

名字	文件编号
hello.txt	2
photo.jpg	5
notes.txt	8

MYFS把目录也作为一种文件保存，文件类型中有一项为：目录。把目录也看成一份文件，那么一个目录项也可以指向另一个目录，这样，目录层级就建立起来了：

例如，我们希望支持路径：/docs/hello.txt

MYFS 可以保存以下三份文件记录：

文件编号	类型	数据块列表
1	目录	[10]
2	普通文件	[800, 1200]
3	目录	[20]

其中，文件1是根目录，文件3是docs目录，文件2是hello.txt。而根目录的数据块10中保存了根目录下目录（即文件名到文件编号的映射表），docs的数据块20中保存了docs下目录。

当要按照/docs/hello.txt开始查找，OS会先分析语法，然后开始查找：

路径从/开始，因此从根目录文件1开始
读取根目录内容，读取到映射表，在映射表中查找“docs”，得到文件编号3
读取文件编号3下的块内容，又读到映射表，在映射表中查找“hello.txt”，得到文件编号2
读取文件记录2，得到文件编号2的一系列文件信息，可以开始读取

即：每个目录都有属于自己的块，而在块中存储了一份目录映射表；在文件记录那里又存储了一份所有文件的文件编号-文件信息的表。

这时，只要MYFS规定，除根目录外，每个文件或目录都只属于一个父目录，就形成了一颗以根目录为起点的树

到这里，这个文件系统已经可以向上提供一种能力：组织文件，并根据文件名读写数据

由于处理方式和内存限制等因素，应用常常分多次读写文件。为了支持这种持续访问，操作系统提供打开文件的机制，保存访问对象、访问方式和当前偏移等状态；应用则负责具体的处理流程。因此，向上增加一层：打开文件并建立一份临时的访问状态。

操作系统因此提供open借口：open("/docs/hello.txt"，READ);

MYFS会解析路径，找到文件编号2，然后在内存中建立一份“打开文件记录”：{目标文件编号：2；访问方式：只读；当前偏移：0}

这份记录描述“这一次打开产生的访问状态”，而不记录文件本身的属性（如长度类型数据块位置），两者的生命周期也不同

接下来，OS给应用一个整数作为这份打开状态的入口，例如 7 。这个整数叫文件描述符

文件描述符7和文件编号2是两种编号。至此，应用程序可以调用read(7, buffer, 100);

访问结束时，可以调用close(7)，结束这份访问状态的生命周期。到这里，就提供了我们熟知的open、read、close等系统调用接口。