ModernOS

现代操作系统

操作系统从主机计算时代，到个人计算时代，再到移动计算时代实现了两次重大变迁。从技术本质看，操作系统“向下管理各种计算资源”，向上为应用程序提供运行环境和开发支撑，为用户提供交互界面

好大学在线：https://www.cnmooc.org/portal/course/5610/14956.mooc
课程网站：https://ipads.se.sjtu.edu.cn/course/os
在线社区：https://ipads.se.sjtu.edu.cn/mospi/discussion

chapter1 操作系统概述

1.1 简约但不简单：从Hello World说起

从helloworld.c文件开始，需要思考的一些问题：

• hello这个可执行文件如何存储在计算机中的（gcc hello.c -o hello）
• hello这个可执行文件是如何加载到内存并在CPU运行的
• hello这个可执行文件是如何将“Hello World！”这行字符输出到屏幕的
• 两个hello程序如何同时在一个CPU中运行的（./hello & ./hello）

1.2 什么是操作系统

操作系统的指责：对硬件进行管理和抽象，为应用提供服务并进行管理

从硬件的角度看：

• 管理硬件：将复杂的、具备不同功能的硬件资源纳入统一的管理
  例如电脑里的内存区域，操作系统识别区域的信息，再使用物理内存分配起进行管理；同时还通过设备驱动来管理各种外部设备的运行并处理可能的错误情况
• 对硬件进行抽象：负责将硬件抽象成不依赖具体硬件特性的资源
  将有限的、离散的资源高效的抽象为无限的、连续的资源，并将硬件通过容易调用的接口提供给上层应用，从而使应用无需关心硬件的具体细节

从应用的角度看：

• 服务于应用：提供不同层次，不同功能的接口，满足应用的需求，还提供了不同类型的访问控制、应用间交互等服务
• 管理应用：负责对应用生命周期的管理，包括应用的加载、启动、切换、调度、销毁等

狭义的操作系统指操作系统内核加上一个Shell
广义的操作系统又可以分为操作系统内核与操作系统框架

内核负责对硬件资源的管理和抽象。为框架提供基础的系统服务
框架基于操作系统内核提供的服务为不同的应用领域提供编程接口与运行环境
（Android操作系统： Android框架 Linux内核）

1.3 操作系统简史

1.3.1 GM-NAA I/O：第一个批处理操作系统

实现对输入与输出的自动化管理，任务交给计算机，计算机工作到所有任务执行结束

1.3.2 OS/360：从专用走向通用

指令集架构，操作系统与计算机底层硬件实现相解耦，进入通用操作系统时代

1.3.3 Multics/UNIX/Linux：分时与多任务

Multiplexed Information and Computing Service ：多用户、多任务、多层次的操作系统，使用了分时概念，首次将文件与内存进行了分离，还提出和实现了文件系统、动态链接、CPU/内存/磁盘等硬件的热替换、特权级分层、命令处理器（后来的Shell）等开创性概念。
Multics也是最早用高级语言来变现的操作系统之一，PL/I语言

后来UNIX系统开发，引入了Shell（命令行解释器）执行不同的计算任务，并支持通过管道等进程间相互通信的方式将不同的计算任务连接起来。UNIX在第四版以前都是基于汇编语言构建，直到C语言的设计与实现，使用C重写了UNIX。

UNIX版权复杂且收费，被用于教学的MINIX操作系统被开源，但因为商用版权不友好，不能被自由的使用，经过学习，Linus Torvalds发布了Linux操作系统，成为了目前世界上最成功，使用范围最广的开源操作系统之一。

1.3.4 macOS/Windows：以人为本的人机交互

Shell只能用于专业的程序员，对于普通用户是非常大的挑战
最早的GUI（Graphical User Interface）操作系统出现（Xerox Alto），引入桌面概念，乔布斯也意识到了GUI的重要性，开始开发面向图形化的计算机与操作系统，苹果成功后，微软创始人盖茨也意识到了问题，发布了Window。

乔布斯当面训斥盖茨偷盗了他的技术，他回答：我们都有个有钱的邻居叫施乐。我闯进他们家准备偷电视机的时候，发现了你已经把他偷走了。

1.4 操作系统接口

• 系统调用接口（以hellowolrd 举例）
  • printf调用标准库libc中的write函数
  • libc库准备好相关参数执行svc指令使控制流从用户地址下陷到内核地址空间
  • 操作系统内核的下陷处理函数根据系统调用传入的第一个参数，识别需要os内核提供的sys_write函数
    系统调用是用户态应用向操作系统内核请求服务的方法
    svc指令：一条ARM指令，表示特权调用
• POSIX接口
  • Portable Operating System Interface for uniX：可移植操作系统接口标准
  • 为能同时在不同UNIX操作系统上运行的软件，定义了一套标准的操作系统API
  • POSIX标准通常通过libc来实现
  • 应用程序只需要调用libc提供的接口就可以实现对操作系统功能的调用，也实现了应用在类UNIX操作系统上的可移植性
• 领域应用接口
  • 在POSIX或者操作系统调用的基础上还可以封装面向不同领域的应用接口
  • 比如Android系统框架为开发人员在安卓操作系统上开发App定义了应用开发接口

1.5 ChCore：一个简单的实验操作系统

• 为本书教学开发
• 微内核架构

chapter2 硬件结构

冯 诺依曼结构

• 中央处理单元：负责运算和逻辑控制
• 存储器：负责存储程序指令和数据，保存程序执行的中间结果和最终结果。
• 输入输出：负责和外界进行交互，从外界获得输入，结果向外界输出。
  虽然今天的计算机翻天覆地，但宏观上看，现在主流计算机依旧采用此结构，本章也主要介绍一些硬件知识

2.1 CPU与指令集架构

主要知识点

• CPU提供给软件的状态和指令有哪些？
• 不同的软件场景，指令集架构提供哪些特权级别？
• 什么是异常？
• 虚拟内存和物理内存的区别？如何映射？
  ISA（Instruction Set Architecture）（指令集架构）是CPU和软件之间的桥梁，包含指令集、特权级、寄存器、执行模式、安全扩展、性能加速扩展等诸多方面

2.1.1 指令集

指令集是ISA的重要组成，CPU在运行操作系统或应用程序就是在执行他们被编译后所包含的指令，本书选择AArch64体系结构作为介绍主要平台，指令集属于RISC（Reduced Instruction Set Computer）
包括：

• 数据搬迁：如mov
• 寄存器计算：如add sub
• 内存读写：如内存写入指令str，内存加载指令ldr
• 跳转指令：如无条件跳转指令b
• 过程调用指令：如调用指令bl、返回指令ret
• 特权指令：如读取系统寄存器指令msr、写入系统寄存器指令mrs等
  x86-64属于复杂指令集计算机（CISC），指令编码长度可变，寻址方式多样

2.1.1 特权级

最低的特权级一般是应用程序运行的，也称为用户态
操作系统通常运行的特权集称为内核态
虚拟化场景需要的虚拟机监控器也有自己的特权级
与安全特性TrustZone相关，负责普通世界和安全世界之间的切换。
TrustZone是ARMv6体系结构开始引入的安全特性，普通世界不能访问被划分到安全世界的计算资源，安全世界可以不受限制的访问所有的计算资源。

需要从EL0切换到EL1的场景：

• 程序需要调用操作系统提供的系统调用，执行svc特权调用
• 应用程序执行了一条指令，但指令触发了异常
• 应用程序在执行过程中，CPU收到了一个来自外设的中断

发生特权级切换的时候，CPU负责保存当前执行状态，以便操作系统内核在处理异常时使用并在结束后能够恢复应用程序的执行，需要保存的状态包括：

• 触发异常的指令地址，保存在ELR_EL1 （Exception Link Register）
• 异常原因，保存在ESR_EL1 （Exception Syndrome Register）
• CPU将栈指针从SP_EL0切换到SP_EL1
• 一些其他状态，例如缺页异常的地址保存在FAR_EL1（Fault Address Register）

操作系统会在异常向量表中为不同的异常类型配置相应的异常处理函数，因此发生特权级切换时，CPU会读取VBAR_EL1（向量基地址寄存器）来获得异常向量表的几地址，根据异常原因调用相应的异常处理函数。

2.1.3 寄存器

在EL1特权级下有两个页表基地址寄存器，负责翻译虚拟地址空间中不同的地址段，负责的地址范围由另一个控制寄存器决定。

虚拟内存（分为用于内核的地址空间、保留空间、和用于应用程序的地址空间）通过页表翻译成物理内存中的地址空间

2.2 物理内存与CPU缓存

• 为什么要引入CPU缓存？直接访问内存的问题？
• CPU缓存的结构如何？
• 如何访问CPU缓存？

CPU在执行过程中可以通过访存指令向物理内存中写入数据或者从中读取数据，通过物理总线向物理内存发送请求

为了降低CPU访存的开销，现在的CPU通常引入了缓存，用于存放一部分物理内存中的数据，CPU需要向物理内存写入数据的时候，可以直接写在CPU缓存，读取时可以先从缓存查找，没找到再去物理内存中获取，并把取回的数据放入缓存中。

2.2.1 缓存结构

缓存结构，CPU缓存是由若干个缓存行组成的，每个缓存行包括一个有效位，一个标记地址（用于标识其对应的物理地址），一些其他状态信息。通常CPU以缓存行为单位把物理内存中的数据读取到CPU缓存中。

为了通过内存的物理地址找到对应的缓存，物理地址在逻辑上分为Tag，Set，Offset三段。

2.2.2 缓存寻址

具体内容见书p19，简单来说通过物理地址划分成Tag、Set和Offset并定位，检查Valid是否有效并进行访问。

2.3 设备与中断

2.3.1 内存映射输入输出（MMIO）

MMIO的原理是，把输入输出设备和物理内存放到同一个地址空间，为设备内部的内存和寄存器也分配相应的地址。CPU可以用这些地址访问和操作设备，可以用访问物理内存一样的指令去读写这些属于设备的地址，设备会通过总线监听CPU分配给自己的地址，然后完成CPU请求。

2.3.2 轮询与中断

• 轮询：让CPU不断去通过MMIO查看UART是否有输入，但会让CPU长时间都处于等待UART输入的状态，造成CPU资源浪费
• 中断：更为高效，赋予设备通知CPU的能力，通过向CPU发送中断来打断PCU的执行，让CPU处理中断，通过不同的中断处理函数来解决问题

中断机制除了使得设备能够主动通知CPU外，还包括让一个CPU核心去通知另一个CPU核心等用途

MMIO使得CPU可以主动地访问设备，中断使设备能够主动地通知CPU，这两种机制使CPU与设备间交互的重要方式

chapter3 操作系统结构

构建复杂系统，必须考虑内部结构，在不同的需求之间权衡。

操作系统的目标：

• 用户目标：方便学习、使用、学习、可靠、安全以及流畅等
• 系统目标：易于实现与维护、灵活、可靠、不易出错、高效等

本章围绕操作系统的设计方法和典型的操作系统结构展开介绍，从而帮助读者理解现代操作系统中的一些基础设计方法和架构。

3.1 操作系统的机制和策略

• 如何控制操作系统的复杂度？
• 什么是机制？什么是策略？为什么要将两者尽可能分离？
• 操作系统内核有哪些典型的架构？

设计原则：将策略与机制相分离以控制操作系统设计的复杂度

策略（policy）：要做什么
机制（mechanism）：怎么做

登陆举例：

• 策略（算法）：什么用户、什么权限
• 机制：调度队列的设计、调度实体的标识、调度的中断处理

通过机制与策略分离，操作系统一方面可以通过多种不同的策略来适应不同的应用需求，不需要重新实现对应的具体机制，另一方面可以通过持续优化具体的机制来完善策略。

一个策略对应一个机制，一个需求多种策略，机制可以不断优化

3.2 操作系统复杂度管理方法

M.A.L.H
即模块化（modularity），抽象（abstraction），分层（layering）和层级（hierarchy）

• 模块化：分而治之，将一个复杂系统通过明确定义的接口进行交互的模块，高内聚，低耦合

*高内聚是指一个软件模块是由相关性很强的代码组成，只负责一项任务，也就是常说的单一责任原则。 *

• 抽象：建立在模块化的基础上，将接口与内部实现分离，模块间通过抽象的接口进行互相调用，无需关心各个模块的内部实现。
  例如UNIX系列操作系统所提供的虚拟内存为物理内存提供了良好的抽象，使得应用程序无须关心物理地址的具体位置，只需要针对独立的，连续的虚拟地址空间进行设计。文件系统的抽象使得应用程序无需关心数据在物理介质（闪存or磁盘）中的具体位置，只需要通过定义好的文件系统接口操作响应的数据

• 分层：将模块按照一定的原则进行层次的划分，约束模块间的交互方式和跨层次模块间的交互方式，从而有效减少模块之间的交互。（通常只能和相邻的上层或下层进行交互，不能跨层，先构建底层的模块，后利用底层模块的功能服务进一步构建上层模块）

• 层级：是另外一种模块的组织方式，首先将一些功能相近的模块组成一个具有清晰接口的字包含子系统，然后将子系统递归地组成一个具有清晰接口的更大子系统。
  一个公司组织架构中，一个经理管理一组成员，一组经理构成一个部门，多个部门构成一个事业部，多个事业部构成一个公司。
  操作系统中，虚拟内存是一个子模块，与物理内存分配、缺页异常处理等构成内存管理模块，内存管理模块再和进程管理模块、设备驱动模块等一起构成操作系统内核

可以通过分层和层级组合的方式来降低模块的复杂度

3.3 操作系统内核架构

• 操作系统的内核有哪些常见的架构？
• DOS架构有什么优点和缺点？
• 一个应用能否运行在多个内核之上？
• 微内核和宏内核孰优孰劣？

3.3.1 简要结构

一些功能简单的操作系统会选择将应用程序与操作系统放置在一个地址空间中，如：DOS，优势在于应用程序对操作系统服务的调用可以通过函数调用高效完成，但同样如果应用或操作系统模块出现了问题，均有可能使整个系统崩溃

3.3.2 宏内核架构

宏内核又称单内核，操作系统内核所有模块（进程调度、内存管理、文件系统、设备驱动等）均运行在内核态，具备直接操作硬件的能力，包括UNIX/Linux等。随着日趋复杂，也采用了M.A.L.H的方法。

宏内核操作系统的基本结构：

• 用户态：应用 Shell
• 内核态：系统调用 进程调度 文件系统 内存管理 设备驱动等
• 硬件：…..

3.3.3 微内核架构

随着宏内核操作系统的内核功能不断增长，系统的复杂度也持续增加，在可靠性、安全性等方面导致了更多的问题。因为宏内核架构下，所有内核模块运行在特权空间，一个单点错误就可能会导致整个系统崩溃或者被攻破。

因此对宏内核架构进行解耦，将单个功能或模块（如文件系统、设备驱动等）从内核中拆分，作为一个独立的服务部署到独立的运行环境中，内核仅仅保留为这些服务通信，让他们能够写作完成功能。
他带来了机制与策略的进一步分离

微内核 vs. 宏内核
自宏内核与微内核这两种操作系统架构出现伊始，人们就两者的优劣与特点展开了多次深入的讨论。当前，随着一些新场景、新诉求的出现，使类似微内核架构的操作系统架构再次受到关注。

• 弹性扩展能力：对于一个宏内核来说，很难仅仅通过简单的裁剪或扩展，使其
  支持资源诉求从KB到TB级别的场景。
• 硬件异构性：异构硬件往往需要一-些定制化的方式来解决特定问题，这种定制
  化对于宏内核来说很难得到长期的支持。
• 功能安全：由于宏内核在故障隔离和时延控制等方面的缺陷，截至目前尚无通
  过高等级功能安全认证
• 信息安全：宏内核架构的操作系统存在较大的信息安全隐患，例如内核态驱动容易导致低质量的驱动代码入侵内核，粗粒度权限管理容易带来权限漏洞等。
• 确定性时延:由于宏内核架构资源隔离较为困难，且各模块耦合度高导致难以控制系统调用的时延，因此较难做到确定性时延;即便为时延做一些特定优化(例如Linux-RT补丁)，时延抖动仍然较大。

在真实世界中，正如体系结构领域的RISC与CISC之争一样，宏内核与微内核往往会互相借鉴。例如，Intel 处理器采用了CISC的指令集架构，但其微架构实现则采用了RISC架构;类似地，Linux等宏内核架构操作系统也采用了一些微内核的设计思想。例如，尽管Linux的创始人Linus Torvalds在20世纪90年代与AndrewTanenbaum论战°时表明将驱动放到用户态是个不靠谱的想法，但近期Linux也逐步采用了一些用户态驱动模型(如UIO与VFIO等); Android 操作系统在Treble项目中同样将部分驱动放到了用户态，并通过名为Binder的IPC机制来与这些驱动进行交互。

3.3.4 外核架构

操作系统内核在硬件管理方面的两个功能：资源抽象与多路复用。
对硬件资源的抽象导致的问题：

• 性能损失
• 对具体的应用如数据库、Web服务器来说往往不是最优的选择

在很多场景，应用比OS更了解该如何去抽象和使用硬件资源，因此由应用来尽可能控制对硬件资源的抽象，提出了库操作系统的概念（LibOS），将对硬件的抽象封装到LibOS中，与应用直接连接，降低应用开发复杂度。操作系统只负责对硬件资源在多个库操作系统之间的多路复用的支持，并管理这些LibOS的生命周期。优势如下：

• 可以按照领域特点和要求动态组装成最适合领域的LibOS
• 处于特权级别的操作系统内核可以做到很小，并且因为多个LibOS的强隔离，从而提升整个计算机系统的安全性和可靠性

微内核 vs. 外核
由于外核架构下运行在特权级的操作系统内核的功能与微内核类似，可以做到非常小，一些读者可能容易将外核架构与微内核架构混淆。然而，两者是具有明显区别的：

• 外核架构将多个硬件资源切分为一个个切片，每个切片中保护的多个硬件资源由LibOS管理并直接服务于一个应用;而微内核架构则是通过让一个操作系统模块独立运行在一个地址空间上来管理一个具体的硬件资源，为操作系统中所有的应用服务。
• 外核架构中，运行在特权级的内核主要为Libos提供硬件的多路复用能力并管理LibOSs;而微内核架构中，内核主要提供进程间通信(IPC)功能。
• 外核架构在面向一个功能与生态受限的场景时可通过定制化Libos获得非常高的性能;而微内核架构则需要更复杂的优化才能获得与之类似的性能。

3.3.5 其他操作系统内核架构

多内核架构：

• 一个服务器存在成百上千个处理器核，一个处理器上集成多种功能、性能甚至指令集结构各异的处理器核心，对操作系统内核的架构如何去管理异构众核心提出了挑战。
• 将其看成一个由多个独立处理器核通过网络互联而成的分布式系统，在每个核上运行一个独立的操作系统节点，节点交互由操作系统节点上的进程通信完成
• 节点存在状态冗余会对资源开销造成压力

混合内核架构：

• 苹果操作系统内核XNU是一个Mach微内核与BSD UNIX的混合体，被用于MacOSX中。
• Windos NT的操作系统也采用了微内核设计思想，但是将一些系统服务运行在内核态

Monolithic单庞大的内核负责资源管理:统系统调用层处理所有OS服务: 高耦合，低可靠性
Microkernel:内核只负责IPC模块化好，高可靠性，IPC成为性能瓶颈
Exokernel:资源管理和保护隔离，应用负责资源管理
Multikernel:通过多内核来管理异构多核设备

3.4 操作系统框架结构

3.4.1 Android系统框架

• 硬件抽象层：使设备驱动运行在内核态，因为开源，需要封装硬件实现细节
• Android库：提供Android应用开发的自定义库
• Android运行环境：主要开发语言为Java，需要字节码转化为可执行代码。
• Android应用框架：提供需要的基础服务，活动管理，包管理，窗口管理等

服务化架构与 Binder IPC
Android系统框架的设计整体应用了类似微内核架构的思想，将系统框架组件化与服务化，各个组件依赖于Android提供的Binder IPC进行通信。图3-11展示了Android应用框架的服务化架构:服务管理组件负责各个服务组件的注册与管理，应用通过服务管理组件进行服务发现，然后调用各个服务组件请求服务。所有的通信都是通过BinderIPC完成的。通过类似微内核架构的服务化框架，Android将各种不同的服务进行解耦，显著提升了系统的可扩展性与可维护性，并为应用开发提供了较为方便的接口。

3.4.2 ROS系统框架

Robot Operating System 机器人操作系统

• 每个组件设计以服务为中心：一个服务接受一个请求，执行并恢复
• 话题的方式是ROS比较新的处理方式，是一类单向的恶异步通信机制
• 引入数据分发服务以支持实时性
• 将计算任务组件化与服务化，形成独立的ROS节点，类似微内核设计的架构让他可以部署在不同的机器人平台，提升单个节点的可复用能力

chapter4 内存管理

多个应用程序同时运行时，操作系统该如何让他们共同使用物理内存资源？

现代操作系统的一个普遍做法是在应用程序与物理内存之间加入一个新的抽象:虚拟内存(virtualmemory)。应用程序是面向虚拟内存编写的而不再是面向物理内存编写的；应用程序在运行时只能使用虚拟地址，CPU 负责将虚拟地址翻译成物理地址，操作系统负责设置虚拟地址与物理地址之间的映射。

虚拟内存的设计具有如下三个方面的目标：

• 高效性：一方面，虚拟内存抽象不能在应用程序运行过程中造成明显的性能开销；虚拟内存抽象不应该占用过多的物理内存资源，从而导致物理内存的有效利用率(即存储应用程序数据的物理内存大小占总物理内存大小的比例)明显降低。

• 安全性：虚拟内存抽象需要使不同应用程序的内存互相隔离，即一个应用程序只能访问属于自己的物理内存区域。

• 透明性：虚拟内存抽象需要考虑到对应用程序的透明性，使得应用程序开发者在编程时无须考虑虚拟内存抽象。在提供虛拟内存抽象的同时，操作系统仍然需要把真实的物理内存分配给每个应用程序。在分配物理内存的时候，操作系统一方面要保证物理内存的利用率，另一方面要保证分配物理内存的速度。为此，现代操作系统通常会使用不止一种物理内存分配器进行物理内存资源的分配。

在本章中，我们将首先介绍虚拟内存的抽象与实现，然后介绍操作系统对虚拟内存和物理内存的管理方法。

4.1 虚拟地址与物理地址

• 什么是虚拟地址和物理地址
• 什么是地址翻译
• 地址翻译的主要机制有哪些

4.1.1 初识物理地址与虚拟地址

逻辑上可以把物理内存看成一个大数组，应用程序运行过程中，CPU通过总线发送访问物理地址的请求，从内存存or取数据，引入虚拟地址后，CPU会把虚拟地址先转换成物理地址，然后通过后者访问物理内存，虚拟地址转化为物理地址的过程被称为地址翻译

4.1.2 使用虚拟地址访问物理内存

CPU中的重要部件，内存管理单元（MMU）负责地址翻译。

例 helloworld.c：操作系统把程序从磁盘加载到物理内存，让CPU执行程序的第一条指令，此时指令存在于内存中，使用圩村的情况下，CPU取指令时发出的是指令的虚拟地址，被MMU翻译成物理地址，然后对该物理地址的读请求被发送到物理内存设备，然后物理内存设备把物理地址发送给CPU

为了加速地址翻译过程，现代CPU引入了转地旁路缓存（TLB），包含在MMU内部。

4.1.3 分段与分页机制

MMU将虚拟地址翻译成物理地址的方法有两种：分段机制和分页机制

• 分段机制

  • OS以段（一段连续的物理内存）形式管理/分配内存

  • 应用程序的虚拟地址空间由若干大小不同的段组成，代码段、数据段

  • CPU访问某段时MMU会查询段表来得到对应的物理内存区域

  • 虚拟地址的构成：段号 + 段内地址

  • 翻译步骤

    • MMU通过段表基址寄存器找到段表位置后结合段号定位该段起始地址
    • 后加上段内地址（偏移量）得到最终的物理地址

  • 实现物理资源的离散分配

  • 容易导致外部碎片（因为要以一段连续的物理内存分配，若不够长则外部碎片）

• 分页机制（现在被广泛采用）

  • 将应用程序的虚拟地址空间和物理内存都划分成连续的、等长的虚拟页

  • 操作系统可以为每个应用程序构造页表（虚拟页到物理页的映射关系表）

  • 虚拟地址的构成：虚拟页号 + 页内偏移量

  • 翻译步骤

    • 解析出虚拟地址中的虚拟页号
    • 通过虚拟页号在程序的页表（在页表基地址寄存器中） 中找到对应条目
    • 取出存储的物理页号，加上页内偏移量得到最终的物理地址

  • 任意虚拟页都可以被映射到物理内存中的任意物理页，物理内存资源离散分配

  • 俺咋熬固定页大小分配物理内存，让物理内存资源易于管理

  • 有效避免分段机制中的外部碎片问题

4.2 基于分页的虚拟内存

• 为什么需要多级页表？
• AArch64体系结构下的多级页表是什么样的？
• 为什么需要TLB？工作原理？
• 什么是换页/缺页？为何需要他们？
• 页替换策略？

为了压缩页表的大小，操作系统引入了多级结构的页表
一个虚拟地址中依然包括虚拟页号和页内偏移量，其中虚拟页号将被进一步划分成k个部分
用于对应虚拟地址在第i级页表中的索引
多级页表允许在整个页表结构中出现空洞，所以多级页表可以部分创建，从而极大节约所占空间。 具体计算见P47

4.2.1 AArch64架构下的四级页表

具体计算见P47

• 页内偏移量=log页大小
• 0级页表有且仅有一个页表页
• 一个页表包含的页表项数目=页大小/每个页表项大小
• 索引位=log页表项数目

翻译过程：
当MMU翻译一个虚拟地址的时候，首先根据页表基地址寄存器中的物理地址找
到第0级页表页，然后将虛拟地址的虚拟页号0(第47至39位)作为页表项索引，读取
第0级页表页中的相应页表项;该页表项中存储着下一级(第1级)页表页的物理地址，
MMU按照类似的方式将虛拟地址的虚拟页号1(第38至30位)作为页表项索引，继续
读取第1级页表页中的相应页表项。往下类推，MMU将在一个第3级页表页中的页表
项里面找到该虚拟地址对应的物理页号，再结合虚拟地址中的页内偏移量即可获得最终
的物理地址。

这样的4级页表结构允许页表内存在“空洞”，操作系统可以在虚拟地址被应用程序
使用之后再分配并填写相应的页表页。在这里我们举- -个极端的例子来说明多级页表在
内存占用方面的优势。假设整个应用程序的虚拟地址空间中只有两个虚拟页被使用，分
别对应于最低和最高的两个虚拟地址。在使用4级页表后，整个页表实际上只需要1个
0级页表页、2个1级页表页、2个2级页表页、2个3级页表页，合计7个页表页(即
整个页表中大部分都是“空洞”), 仅仅占用28 KB的物理内存空间，远小于单级页表的
大小。

4.2.2 加速地址翻译的重要硬件：TLB（一种缓存）

• 多级页表能显著压缩页表大小，但会导致地址翻译时长的增加（时间换取空间）。

• 每次地址翻译，MMU会先把虚拟页号作为键去查询TLB中的缓存项，值是物理页号。

• 若找到则可以直接获得物理页号无需查询页表。

• TLB缓存项数量有限，由MMU进行管理

• 硬件规定了页表基地址的位置以及页表的内部结构，操作系统只需按照硬件的规范来构造和配置页表。

• 当TLB未命中时，硬件将通过页表基地址查询页表，找到对应的页表项，并且将翻译结果填写到TLB中;若TLB已满，则根据硬件预定的策略替换掉某一项。之后若需再次翻译同样的虚拟页号，硬件就可以迅速地从TLB中直接找到对应的物理页号(TLB命中)。

因为应用程序的时间局部性和空间局部性，TLB获得了较高的命中率

• 时间：被访问过一次的内存位置通常会在未来被多次访问
• 空间：如果一个内存位置被访问，其附近的内存位置通常在未来也会被访问

为了保持TLB内容和页表的一致性，每次进行页表切换（应用程序切换），都要主动刷新TLB

操作系统每次切换应用程序都要刷新TLB，每次应用程序开始执行都会发生TLB未命中，需要避免切换时导致的TLB刷新开销。

操作系统可以为不同的应用程序分配不用的ASID作为应用程序的身份标签，再将这个标签写入应用程序的页表基地址寄存器中的空闲位。同时TLB中的缓存项也会包含ASID标签，从而使TLB中属于不同应用的缓存项可以被区分开。如此，切换页表的过程中，操作系统不需要清空TLB

不过，在修改页表内容之后，操作系统还是需要主动刷新TLB以保证TLB缓存和页表项内容一致。在AArch64体系结构中提供了多种不同粒度的刷新TLB的指令，包括刷新全部TLB、刷新指定ASID的TLB、刷新指定虚拟地址的TLB等。操作系统可以根据不同场景选用合适的指令，最小化TLB刷新的开销，以获得更好的性能。

4.2.3 换页与缺页异常

虚拟内存设计的目标之一：透明性
虚拟内存中的换页机制就是为了透明地满足这样的场景需要所设计的。

换页基本思想：当物理内存容量不够时间，操作系统应该把若干物理页的内容写到类似于磁盘这种容量更大更便宜的存储设备，就可以回收物理页并继续使用了。

缺页异常与换页机制密不可分，也是换页机制能够工作的前提，当应用程序访问已经分配但没有映射的物理内存的虚拟页时，就会出发缺页异常，此时CPU会运行操作系统预设的缺页异常处理函数，该函数会找到一个空闲的物理页，将之前在磁盘上的数据重新加载，并在页表虚拟地址到这一物理页的映射，被称为换入。

利用换页机制，操作系统可以把物理内存放不下的数据临时放到磁盘上，这一就可以在需要的时候放回物理内存，从而提供超过物理内存实际容量的内存。

由于换页过程涉及耗时的磁盘操作，因此OS往往会引入预取机制进行优化，当换入操作发生，预测还有哪些页即将被访问，减少缺页异常。

同时，虚拟内存的按需页分配机制会在应用程序申请分配内存时，操作系统选择将已经分配的虚拟页标记成已经分配但没有映射的状态，不必分配对应物理页，发生缺页异常再分配，解决物理内存，提高资源利用率。

最后，当虚拟页处于未分配状态或者已经分配单没有映射时都会缺页，OS通过一个数据结构（应用程序的虚拟地址空间被实现成由多个虚拟内存区域组成的数据结构），发生缺页时OS会判断虚拟页P是否属于该应用程序的某个虚拟内存区来区分所处状态

4.2.4页替换策略

当需要分配物理页，空闲的物理页小于某个阈值，OS会根据页替换策略选择一个或一些物理页换出到磁盘以便让出空间

• MIN / OPT策略（Optimal 最优策略）：优先换走未来不会再访问的页

• FIFO 策略（First-In Firsit-Out）：先来页先被换走

• Second Chance策略：FIFO改进版本，维护一个先进先出队列用于记录换入物理内存的页号，还要为每一个物理页维护一个访问标志位。

  • 若需要访问的页号已经在队列，就加上访问标志位置
  • 要换出先查看队头，若被置位，清置，并挪到队尾
  • 都有标记全部去掉并回到队尾
  • 无标记就是FIFO

• LRU策略（Least Recently Used）：优先选择最久未被访问的

• MRU策略（Most Recently Used）：优先选择最近访问的

• 时钟算法策略：类似Second Chance 单不需要将页号从对头移动到队尾 实现更高效

4.2.5 工作集模型

OS的原则是以最小的算法开销达到尽可能接近MIN策略的效果，如果选择的替换策略和实际的工作负载不匹配就可能导致颠簸（抖动），造成严重的性能损失。（局部性很强的场景下使用MRU）

工作集模型就可以有效避免此类现象的发生

• 一个应用程序在时刻t的工作集W为它在时间区间[ t-x , t ]使用的内存页集合，被视为一个他在未来（下一段x时间内）会访问的内存页集合。
• 他认为应当将应用程序的工作集同时保存在物理内存中，早期为all-or-nothing
• 优先换出非工作集中的页
• 如何高效追踪工作集
  • 工作集时钟算法：设计定时器，每经过固定时间间隔一个设置好的工作集追踪函数就会被调用
  • 追踪函数为每个内存页维护两个状态：
    • 上次使用时间和访问位，均初始化为0
    • 每次被调用，都会检查每个内存页的状态，如果是1，说明此次时间间隔内被访问过，函数会把当前的系统时间赋值给上次使用时间
    • 如果是0，会计算该页的年龄，超过预设x就不再属于工作集
    • 检查完一个页的状态之后追踪函数就会将访问位设置为0
• 通过类似工作集时钟算法相似设计的算法，OS可以有效预测工作集，灵活进行页替换。

4.3 虚拟内存功能

• 如何利用虚拟内存实现内存共享？

• 什么是写时拷贝？写时拷贝如何实现？

• 如何利用虚拟内存抽象解决物理内存（内存去重和内存压缩）？

• 什么是大页？为何要使用？

虚拟内存使应用程序拥有一个独立连续的虚拟你只空间，通过页表和硬件配合能够自动进行虚拟地址到物理地址的翻译。（让多个应用进程共同使用物理内存）此外其他功能如下

4.3.1 共享内存

允许同一个物理页在不同的应用程序间共享，让不同的应用程序之间相互通信，传递数据。
衍生出写时拷贝、内存去重

4.3.2 写时拷贝

场景：

• 两个应用程序拥有很多相同的内存数据
• fork系统调用创建子程序：初始父子程序的全部内存数据和地址空间完全一样

写时拷贝技术允许应用程序A 和应用程序B以只读的方式共享一段物理内存，如果某个应用程序对该内存区域进行修改，就会触发缺页异常

4.3.3 内存去重

基于写时拷贝机制，OS进一步设计了内存去重，OS可以定期在内存中扫描具有相同内容的物理页，并且找到映射到这些物理页的虚拟页，然后只保留一个物理页，将所有具有相同内容的其他虚拟页都用写时拷贝的方式映射到这个物理页，释放其他物理页，对用户态程序完全透明。

Linux实现了该功能，称为KSM，但会对程序访存时延进行影响，当程序写一个被去重的内存页，会发生缺页异常，又会导致内存拷贝，性能下降。

虽然节约空间，但会导致安全问题。攻击者可以通过在内存中穷举的方式构造数据后等待去重，通过访问是否延迟查看是否发生去重，检验是否存在敏感数据。一种可能的防御方法：OS仅仅在同一用户的应用程序内存进行去重，让攻击者无法猜测别的用户。

4.3.4 内存压缩

为了解决内存资源，当代OS引入了压缩算法来对内存数据进行压缩，基本原理：内存资源不充足，OS选择最近不太会使用的内存页压缩其中数据释放空闲内存。这样不仅可以快速腾出空闲内存，也可以快速回复被压缩数据。

Linux支持的zswap机制可以在换页过程中提供缓冲区，称为zswap区域，OS将即将换出的内存数据压缩并写入zswap区域，再次被放回会进行换入解压。

4.3.5 大页

大页机制可以有效缓解TLB缓存项不够的问题，大页可以时2MB甚至1GB，使用大页可以大幅度减少TLB的占用量。OS可以利用硬件提供的大页支持，在虚拟内存中以2MB甚至1GB的大页进行地址映射。Linux还提供了透明大页自动将连续内存合并。

优势：

• 减少TLB缓存项的使用，提高TLB命中率
• 减少页表级数，提升页表查询效率

弊端：

• 应用程序未使用整个大页使物理内存资源浪费
• 增加操作系统管理内存的复杂度

4.4 物理内存分配与管理

• 如何评价物理内存分配器的优劣？

• 广泛使用的伙伴系统分配器的工作原理？

• 为什么有伙伴系统分配起还需要SLAB分配起，以及SLAB分配器的工作原理？

• 分配器中会用到的关键数据结构：空闲链表是什么样的？

• 除了分配物理内存资源外，OS还要管理CPU缓存资源吗

4.4.1 目标与评价维度

评价维度：

• 追求更高的内存资源利用率，减少资源浪费
  • 内存碎片：无法被利用的内存，导致内存资源利用率的下降
  • 多次分配和回收后物理内存空闲部分处于离散分布的状态
  • 分为内部碎片和外部碎片
  • 看似可以的解决方案
    • 将物理内存以固定大小划分，然后每次用一个块服务一个分配请求
    • 当分配大于需要，自然浪费
• 追求更好的性能
  • 降低分配延迟和节约CPU资源
  • 不能使用算法细致解决内存利用率问题但增加分配器完成分配请求的时间

4.4.2 伙伴系统

在现代操作系统中被广泛用于分配连续的物理内存页。

将物理内存划分成连续的块，以块作为基本单位进行分配，不同块的大小可以不同但都是由一个或多个连续的物理页组成，数量必须时2的n次幂。

当一个请求需要分配m个物理页时，伙伴系统将寻找一个大小合适的块， 该块包含2^n个物理页，且满足2^(n-1)<m≤2^n。在处理分配请求的过程中，大的块可以分裂成两半，即两个小一号的块，这两个块互为伙伴。分裂得到的块可以继续分裂，直到得到-个大小合适的块去服务相应的分配请求。在一个块被释放后，分配器会找到其伙伴块，若伙伴块也处于空闲的状态，则将这两个伙伴块进行合并，形成一个大一号的空闲块，然后继续尝试向上合并。由于分裂操作和合并操作都是级联的，因此能够很好地缓解外部碎片的问题。

空闲链表
内存块分配：

• 全局有一个有序数组，每一项只想一条空闲链表，每条链表将其对应大小的空闲块连接起来（一条链表中的空闲块大小相同）
• 接收到分配请求后伙伴分配起酸楚分配多大，后查找空闲链表
• 不为空，取出空闲块进行分配
• 空则找到存储更大块的链表，进行分裂

释放块：

• 找到要被释放块的伙伴块，若不空闲，被释放的块插入对应大小的空闲链表
• 空闲则合并两个块，当成一个完整的块释放，重复过程

4.4.3 SLAB分配器

伙伴系统最小为一个物理页（4KB），但大多数情况下通常是几十个字节或是几百个，如果仅仅用伙伴系统进行内存分配，会产生严重的内部碎片问题，因此开发出用于分配小内存的SLAB分配器。

SLAB初始的设计和实现维护了太多队列，实现太复杂，存储开销增大，开发人员再此基础上设计了SLUB简化了设计并提供更好的性能，同时继承接口。SLAB家族中还有SLOB分配起，满足内存稀缺的场景。

SLUB分配起成为了Linux内核默认使用的分配器。

SLUB分配起为了满足OS频繁分配小对象的需求，依赖于伙伴系统进行物理页的分配，其把伙伴系统分配的大内存进一步细分成小块内存进行管理，因为需要被分配的对象大小比较固定，也为了避免外部碎片，SLUB只分配固定大小的内存块，通常为2^n字节。

具体实现过程中，程序员可以根据实际需要设置别的大小来减少内部碎片。

SLUB分配器向伙伴系统申请一定大小的物理内存块(一个或多个连续的物理页)，并将获得物理内存块作为一-个slab(slab在这里指代这个物理内存块对应的数据结构)。slab会被划分成等长的小块内存，并且其内部空闲的小块内存会被组织成空闲链表的形式。)一个内存资源池通常还有current和partial两个重要指针。current指针仅指向-一个slab,所有的分配请求都将从该指针指向的slab中获得空闲内存块。partial指针指向由所有拥有空闲块的slab组成的链表，当SLUB分配器接收到一个分配请求时，它首先定位到能满足请求大小且大小最接近的内存资源池，然后从current指针指向的slab中拿出一个空闲块返回即可。如果current指针指向的slab在取出一个空闲块后，不再拥有空闲块，即全部已分配完，则从partial指针指向的链表中取出一个slab交给current指针。如果partial指针指向的链表为空，那么SLUB分配器就会向伙伴系统申请分配新的物理内存作为新的slab。
这样的分配设计，一方面有效避免了外部碎片，另一方面通常分配速度很快(直接从current指针指向的slab取出第一个空闲块即可)。通过合理地设置不同大小的内存资源池，也能够尽可能地减少内部碎片导致的开销。

当SLUB分配器接收到一个释放请求时，它将被释放的块放人相应slab的空闲链表中。如果该slab原本已经没有空闲块，即全部分配完，则将其重新移动到partial指针指向的链表中;如果该slab变为所有内存块都是空闲的，即原来仅分配出去一块,那么可以将其释放，还给伙伴系统。
至于如何找到释放块所属于的slab,则可以通在slab头部加入元数据并且使得slab头部具有对齐属性等方式来实现。

4.4.4 常用的空闲链表

• 隐式空闲链表：空闲和非空闲的内存块混杂在同一条链表，通过内存块头部可以找到下一块，相邻空闲就合并，减少外部碎片

• 显式空闲链表：仅仅把空闲的内存块放在链表中。需要额外维护两个指针分别只想前后空闲块

• 分离空闲链表：在显式空闲链表的基础上构建，维护多条不同显式空闲链表，每条链表服务固定范围大小请求，类似于伙伴系统和SLAB。

4.4.5 物理内存与CPU缓存

计算机存储多级，CPU通过缓存间接访问内存中数据，因为比访内存块，但缓存很小很贵，，只能以缓存行为单位放进去，如果满或者存在冲突会根据预设的替换策略来替换掉缓存行。

• 软件方案：染色机制

  • 缓存着色机制：能够被放到缓存中不同位置的物理页标记上不同颜色，再为连续虚拟内存页分配物理页时优先选择不同颜色的物理页进行分配。
  • 机制的实现:假设缓存总大小可以放下4个连续的物理页，则该机制会把第1个物理页到第4个物理页分别染上4种不同的颜色，再把第5个到第8个物理页的颜色染成与前面4个页一致的颜色，依次往下。这种染色机制会导致物理页的分配变得复杂，但如果能够明确地得知应用对内存的访问模式，则可以有效提升内存访问的性能，FreeBSD、Solaris等操作系统中就运用了该机制

• 硬件方案：Intel CAT

• ARMv8-A MPAM

4.5 案例分析：ChCore 内存管理机制

见书P70，再此不详细解释。

chapter5 进程与线程

对用户态线程和内核态线程的理解
为了管理程序运行，OS提出了进程的抽象：每个进程都对应一个运行中的程序。有了进程的抽象，程序在运行时仿佛独占CPU，而不用考虑何时让出；

进程的管理、CPU资源分配等任务交给OS

为了让多个进程共同执行，OS进一步提出了上下文切换，通过保存和恢复进程在运行中的状态（即上下文）让进程可以暂停、切换和恢复，从而实现了CPU资源的共享。同时利用虚拟内存机制，OS为每个进程提供了独立的虚拟地址空间，让多个进程能安全高效共享物理内存

随着发展，单主机CPU数量不断增加，应用程序类型丰富，针对进程间数据不易共享、通信开销高等问题，OS引入了更轻量级的执行单元：线程，由于上下文切换需要进入内核，开销很大，又引入了纤程的抽象，允许上下文在用户态切换

5.1 进程

• 进程都有哪些状态？为什么要定义这些状态？
• 进程的虚拟地址空间是怎么样的结构？
• 进程是如何进行上下文切换的？

5.1.进程的状态

• 新生状态（new）
• 预备状态（ready）
• 运行状态（running）
• 阻塞状态（blocked）
• 终止状态（terminated）

以hello-name举例：在Shell中使用 ./hello-name

• 小明按下回车，Shell接受命令，请求内核创建进程处理命令。创建时未初始化，处于new

• 内核对进程初始化后交给调度器，加入运行队列，处于ready

• 调度器选择该进程执行，处于running，可以开始执行main（ 此部分可以跳转 1.4 ）

• 进程执行到fgets（等待用户输入），进程处于blocked，等待用户输入

• 小明输入 Xiaoming 并回车，进程重新回到running状态，输出Hello Xiaoming

• 进程执行完main函数，回到内核，变成终止状态，内核会回收进程资源

5.1.2 进程的内存空间布局

进程具有独立的虚拟内存空间，布局如下：

• 用户栈：保存进程需要的各种临时数据，栈自顶向下
• 代码库：进程执行的时候需要依赖共享的代码库，如（libc），他会被映射到用户栈下方的虚拟地址处，并标记为只读
• 用户堆：堆管理的是进程动态分配的内存，堆自底向上，需要更多内存时会向高地址扩展
• 数据与代码段：保存在进程需要执行的二进制文件中，执行前OS会将他们载入虚拟地址空间中，数据段主要保存全局变量（如 #define），代码段保存进程执行所需要的代码
• 内核部分：处于进程地址空间最顶端，每个进程的虚拟地址空间都映射了相同的内核内存。当进程在用户态，内核内存不可见，只有进入内核态时才能访问内核内存。
• 内核部分也有内核需要的代码和数据段，当进程又与中断or系统调用进入内核后会使用内核的栈

Linux中，可以cat /proc/PID/maps查看进程内存布局，由于内核地址空间堆用户态进程不可见，因此maps内容中没有包含内核部分的映射。另外进程也会映射一些匿名内存区域进行缓存和共享内存。

5.1.3 进程控制块和上下文切换

内核中，每个进程通过一个数据结构（进程控制块）来保存相关状态，如进程标识符（PID）、进程状态、虚拟内存状态、打开的文件等。不同OS中进程控制块包含内容可能有所不同。

进程的上下文包括进程运行时寄存器的状态，用于恢复和保存一个进程在处理器上运行的状态。

当OS需要切换到当前执行的进程，就会使用上下文切换机制。机制会将前一个进程的寄存器状态保存到PCB中，然后将下一个进程先前保存的状态下入寄存器，从而切换到该进程执行。

过程见P80 图5-3

5.2 案例分析：Linux的进程操作

5.2.1 进程的创建 fork

• 调用fork接口，从已有的进程中分裂出子进程，PID和虚拟内存空间不同，独立执行

• 不接收任何参数，返回子进程的PID

• fork() 返回给子进程的值为0

• 进程再运行过程中都会维护一张已打开文件的文件描述符（fd）表（PCB的一部分）

• 文件描述符是OS提供的对于某一文件引用的抽象：文件描述符会用偏移量来记录当前进程读取某一文件的某一位置

• Linux在实现read操作会对文件抽象加锁

• Windows使用CreateProcess函数创建进程，非常复杂，参数多，从头创建，灵活但接口复杂

系统的第一个进程如何产生？其实是由OS创建，特定且唯一，OS中所有所有的进程都由这个进程产生，具体在后续讲解进程树会介绍

5.2.2 进程的执行：exec

很多时候用户需要子进程和父进程完成不同的任务，比如用户在Shell中输入各种各样的命令，Shell会为命令调用fork创建出进程。这些进程需要用户指定二进制文件，而不是继续执行Shell程序，为实现本目标Linux提供了exec接口

exec实际上是由一系列接口组成的，有很多变种，较为全面的是execve

5.2.3 进程管理

• 进程间关系与进程树
  • 每个进程都会记录自己的父子进程，构成了进程树结构
  • 内核通过这种结构对进程进行管理
• 进程间监控：wait、同时回收已经结束的子进程并释放资源（父进程没调用wait会导致僵尸进程的产生，从而占用的资源也不会完全释放）
• 进程组和会话
  为了方便应用程序进行进程管理，内核定义了由多个进程组合成的小集体，即进程组和会话
  主要用于Shell环境中的进程管理
  • 进程组：进程的集合
  • 会话：进程组的集合（fork 子进程父进程一个会话）
    • 前台进程组（比如会被Shell Ctrl+C杀死）
    • 后台进程组

5.2.4 fork过时了吗？

• fork 优点
  • 简洁：不需要任何参数
  • 强调进程间关系，为进程管理提供了便利
  • Web服务器场景中，服务器会为每个请求单独创建进程，因为逻辑相似，因此可以通过fork方式一次创建多个进程来应对用户的请求
  • 在Shell中，虽然同一个Shell创建的进程功能不同，但都来自同一个用户，因此可以共享很多的状态
• fork 局限性
  • fork也变得复杂了，因为OS支持的功能越来越多，fork实现越发复杂
  • fork的实现与管理、内存管理等模块耦合度过高。不利于内核代码维护
  • 性能太差，因为要创建出原进程的一份拷贝，原进程越多，fork性能越差
  • 存在潜在安全漏洞，fork建立的父子进程联系会成为攻击者切入点。
  • 扩展性差、线程不安全、硬件不兼容….
• posix_spawn
• vfork
• rfork/clone

5.3 线程

• 为什么需要引入线程？
• 拥有多个线程的进程的虚拟地址空间结构是怎么样的？
• 用户态线程和内核态线程的区别和联系分别是什么？
• 针对线程的核心操作有哪些？

早期OS，进程是OS用来管理运行程序的最小单位，随着CPU核心增多，程序并行度提高，进程这一抽象很笨重。

• 进程创建开销很大，需要独立地址空间
• 进程有独立的虚拟地址空间，在进程间进行数据共享和同步比较麻烦

因此OS设计人员提出在进程内部添加可以独立执行的单元，共享进程地址空间，又保存运行状态，就是线程，接着线程取代了进程成为了操作系统调度和管理程序的最小单位。

5.3.1 多线程的地址空间布局

• 分离的内核栈与用户栈：每个线程执行相对独立，进程为每个线程准备了不同的栈以供存放临时数据，内核中，每个线程都有对应的内核栈，当线程切换到内核中执行，栈指针就会切换到对应的内核栈
• 共享的其他区域：进程栈以外其他区域由该进程的所有线程共享，包括堆，数据段，代码段等

5.3.2 用户态线程和内核态线程

根据线程是由用户态应用还是由内核创建和管理，分成用户态线程与内核态线程
内核态线程由内核创建，受到OS调度器直接管理

用户态线程由应用创建，内核不可见，更加轻量级，创建开销更小，但功能也受限制，与内核态相关的操作（如系统调用）需要内核态线程协助才能完成。

为了让用户态线程与内核态线程协作，OS会建立两类线程之间的关系，称为多线程模型。

• 多（用户态线程）对一：每次只有一个用户态线程能进入内核，其他需要内核服务的用户态线程会被阻塞
• 一对一：每个用户态线程都对应一个内核态线程，创建内核态线程的开销会随摄用户态线程数量的增加而不断增大，因此OS会对用户态线程总数有限制，放置内核态线程数量过多对应用性能造成不良影响。Linux 和 Windows系列OS都采用一对一模型。
• 多对多：N个用户态线程映射到M个内核态线程（ N > M ），减轻了因为1对多内核态线程过少而导致的阻塞问题，也解决了1对1模型中因为内核态线程过多而导致的性能开销过大，但会让内核态线程的管理变得复杂

5.3.3 线程控制块与线程本地存储

线程有自己的线程控制块（TCB），用户保存与自身相关的信息。在目前主流的一对一线程模型中，内核态线程和用户态线程会各自保存自己的TCB。用户态的TCB可以认为是内核态的国战，用来存储更多与用户态相关的信息，最重要的功能就是线程本地存储（TLS）

一个名字多份拷贝，一个线程对自己变量赋值时不会影响别人的，只会修改自己的拷贝，某个变量在每个线程的TLS中有相同的偏移量，但内存地址不同。

寻址：找到该线程TLS起始地址并存入段寄存器FS中，加偏移量寻址

5.3.4 线程的基本接口：以POSIX线程库为例

• 线程创建
• 线程推出
• 让出资源
• 合并操作
• 刮起与唤醒

5.4 案例分析：ChCore线程的上下文

不做赘述

5.5 纤程

• 为什么对纤程的需求近年来越发强烈？
• 什么是纤程？如何使用纤程？
• 纤程如何进行上下文切换？
• 纤程与进程、线程的区别有哪些？

5.5.1 对纤程的需求：一个简单的例子

生产者早就完成了数据生成但因为上下文切换的开销和调度器的选择，要经历长时间才能开始处理数据，为了消除延迟，应用程序可以使用纤程。

5.5.2 POSIX的纤程支持：ucontext

不做赘述

5.5.3 纤程的上下文切换

不做赘述

chapter6 操作系统调度

指在有限的资源下，通过对多个程序执行过程的管理，尽可能满足系统和应用的指标。

调度有很多类别：任务调度、I/O调度、内存调度

6.1 计算机调度简介

• 为什么需要研究计算机调度？
• 计算机如何进行调度的？
• 计算机调度应该达到什么样的效果？
• 设计实现计算机调度有何困难？

举例：在单核计算机运行一个需要执行30分钟的机器学习并听音乐，系统调度器会让小明等30分钟后听音乐。调度就是系统会同时处理多个请求，虽然资源有限，调度就是用来协调每个请求对资源的使用的方法。

• 调度中的优先级
• 调度中的时间片
• 调度中的截止时间

调度在计算机中的应用：

• 任务调度：负责调度可执行的任务对CPU的使用
• 换页机制：对哪部分物理页的内容可以留在内存中进行调度

6.1.1 操作系统调度

进程是资源隔离的单位，并不是执行的单位（因为同一计算）
一个进程可以有多个线程，可以在不同的CPU核心上并行执行。因此线程才是调度器调度的对象。Linux操作系统中常常用任务来描述线程

htop可以显示任务列表和CPU使用情况

调度器会通过维护运行队列的方式来管理任务，运行队列并非一定由先进先出队列，比如Linux会使用红黑树来实现运行队列，触发一定条件会停止执行：

• 执行了指定的时间片，应当让其他任务在当前CPU执行
• 任务发起I/O请求，等到I/O返回才会继续执行
• 任务主动停止or睡眠
• 任务被中断系统打断，系统有限处理中断而暂缓该任务的执行。

调度器的作用：作出调度抉择

• 从运行队列选择下一个运行的任务
• 决定执行该任务的CPU核心
• 决定任务被允许运行的时间（时间片）
• 作出决策后，系统中相应的机制会将任务执行在对应CPU核心

问题：

• 调度器应该作出怎样的调度决策？
• 调度器应该如何作出符合预期的调度决策？

6.1.2 调度指标

计算机应用场景很多，用户有不同预期，会有不同的指标来指导调度策略选择

• 与性能相关：吞吐量、周转时间、响应时间
• 非性能指标：公平性、资源利用率、实时性，能耗….

指标：

• 批处理任务：如机器学习的训练，复杂的科学计算，执行时无需和用户交互，目标就是尽可能完成，主要指标就是任务处理的吞吐量，同时要让任务的周转时间尽可能短。
• 实时任务：实时性
• 移动设备：能耗
• 资源被充分利用、每个任务都有执行的可能

调度器的挑战：

• 调度指标多样性
• 调度器可参考的信息有限
• 许多方面存在权衡
  • 开销与调度效果
  • 优先级与公平性
  • 性能和能耗

6.2 调度机制

• 任务是如何在计算机系统中被调度的？
• 长期、中期、短期调度的具体职责是什么？

6.2.1 长期、中期与短期调度

长期调度用于限制系统中真正被短期调度器管理的进程数量，避免短期调度开销过大

长期调度为某个程序创建了进程并设置为预备状态，会由短期调度进一步管理该进程，因此长期调度决定了当前真正可能被调度的进程的数量

根据进程主要使用的资源类型会把进程分为：计算密集型 和 I/O密集型
长期调度可以根据系统中I/O利用率和CPU利用率来选取适合的进程，交由短期调度管理
实际作出调度决策的是短期调度，负责在各种状态（预备，运行，阻塞）间的转换

长期调度与短期调度一般会从CPU、I/O资源的角度作出调度决策，然后OS中的内存没有被考虑。虽然长期调度限制了短期调度管理中进程数量，但内存使用量有可能超出，此时OS需要将内存使用也纳入考量，避免内存使用过多，这就是中期调度

中期调度实际上是换页机制的一部分，如果当前系统进程占用大量内存，中期调度会挂起某些被短期调度管理的程序，降低内存总量。（挂起状态表示它不会再被调度执行）

• 挂起预备状态
• 挂起阻塞状态

6.2.2 任务调度总览

进程调度中，长期、中期、短期调度相互协作，分别以不同的目标对进程进行调度。

• 长期调度触发间隔较长，负责增加系统中可被调度的进程的数量
• 中期调度触发相对频繁，辅助换页，限制系统中可被调度的进程的数量
• 短期调度触发最为频繁，负责细粒度地调度进程执行，作出响应调度决策。

示意图与解析见书P116

6.3 单核调度策略

• 单核场景有哪些调度策略？
• 不同的单核调度策略的优点和缺点分别是什么？

6.3.1 经典调度

非抢占：

• 先到先得 FCFS（FIFO）：对计算密集型任务更加友好，但可能会导致I/O密集型任务长时间内无法执行
• 最短任务优先 SJF：严重依赖于任务到达时间点
  抢占：
• 最短完成时间任务优先 STCF：长任务饥饿
• 时间片轮转 RR：在任务运行时间相似的场景下平均周转时间高

6.3.2 优先级调度

调度器应经量避免交互式任务（Shell）被批处理任务阻塞（RR下的例子）
如果OS可以区分交互式任务和批处理任务，可以设置一个让交互式人物先执行的调度策略，为此调度器引入了优先级概念，如此OS可以为用户提供更好的体验。

一个直观的静态优先级调度策略：多级队列 （MLQ）（图例见书P124）
每个任务会被分配到预设好的优先级，每个优先级对应着一个队列。
调度器会倾向于调度优先级较高的任务，一个任务必须等到所有优先级比他高的任务调度完才可以被调度，处于相同优先级队列的任务内部没有统一标准，可以针对性为不同队列采用不同调度策略

适合静态应用场景，任务信息可以提前获知，可以提前生成相应调度模型，算出每种任务适合的优先级进行调度。

注意将I/O密集型任务的优先级提高，否则会造成I/O资源利用率低下。（一般I/O密集型任务不会消耗大量CPU资源，可以提高优先级，率先发起I/O请求，充分利用空闲的I/O）

• 任务饥饿（大量高优先级的任务不断进入系统，低优先级任务无法被调度）：需要额外的机制来监控任务等待时间，为等待时间过长的任务提升优先级。
• 优先级反转：详见 chapter8（因为锁问题），用优先级继承的方法解决

多级反馈队列（MLFQ）

• 既能达到类似STCF策略的周转时间（最短完成时间任务优先）
• 又能像RR策略一样尽可能降低任务的响应时间
• 算法内容：
  • 维护多个优先级队列，任务根据优先级存于不同队列中
  • 相同优先级的任务采用RR策略执行（时间片轮转）
  • 短任务拥有高优先级（如I/O、交互式任务）
  • MLFQ会首先对任务运行时间进行评估，预计较短的放入优先级较高队列（会统计已执行时间）
  • MLFQ会为每个任务队列设置任务的最大运行时间（总时间不是时间片）
  • 如果总时间超过允许，优先级降低，动态评估任务运行时间
  • 短任务一般可以在预设时间片内完成，长任务优先级会随着执行次数的增多而降低
  • 低优先级任务采用更长的时间片，为了减少任务切换开销
  • 定时地将所有任务的优先级提升至最高，避免任务饥饿
  • 任务的优先级会被动态的提升（Boost）和降低（Penalty、惩罚）
  • 具体的实现中还有许多参数需要调整：如队列数量、时间片、最大运行时间、

6.3.3 公平共享调度

此类调度器会量化任务对系统资源的1占有比例，实现公平调度。以份额来量化任务对CPU时间的使用。其支持层级化的分配方式，可以直观的体现每个任务的理论资源使用情况。实际场景中可以将任务分组（称为任务组），以组为单位分配份额，任务会在组内进一步自己分摊拥有的份额。

优先级为了优化任务周转时间、响应时间和资源利用率。
基于份额的公平共享调度为了让每个应用获得应得的资源。

经典公平共享调度策略

• 彩票调度：根据随机数确定任务是否被调度
  • 彩票转让
  • 彩票货币
  • 彩票通胀 详见P131
• 步幅调度：
  • 虚拟时间

6.3.4 实时调度

• 硬实时任务
• 软实时任务
• 周期任务
• 非周期任务（一般是软实时任务，如按下键盘）
• 偶发任务

6.4 多核调度策略

• 多核场景下有哪些调度策略？优缺点？
• 负载均衡？
• 能耗？

6.3是单核调度策略，多核心时

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

6.4.1 负载分担

当一个CPU核心需要调度任务时，根据给定的调度策略决定全局运行队列中下一个由他执行的任务。只要有可以执行的任务，每个CPU核心都能获取到任务执行。

问题：

• 多核共享一个全局运行队列的同步开销
• 任务在多个CPU核心间来回切换的开销（TLB刷新，重新载入缓存）

6.4.2 协同调度

多线程程序为了利用多核处理器，通常会将一个工作量较大的任务切分成多个子任务，并将每个子任务交给不同的核心完成，子任务可能有依赖关系，某些倾向于同时执行。

协同调度适用于关联任务或任务间有依赖关系的场景，并非所有场地符合。

协同调度作为多核调度的一种，适用于并行计算。任务分为以下：

• 并发计算：每个CPU核心独立计算自己的子任务
• 通信：CPU核心之间通过通信交换数据
• 同步：一个CPU核心在执行到程序设定的某个屏障点时，需要等待其他CPU核心也到达，才能执行后续代码逻辑

群组调度：将关联任务设为一组，并以组为单位调度任务在多个CPU核心上执行，让他们开始时间和结束时间接近相同。详见 P143

6.4.3 两级调度

为每个CPU核心都引入一个本地调度器，并管理对应核心上执行的任务，这种调度策略使用全局调度器和本地调度器，构成了层级化结构，一般称之为两级调度

任务进入系统，全局调度器会根据系统当前信息（如CPU负载）决定任务该被那个CPU核心执行。

层级化设计让单核调度策略和多核调度进行解耦，调度器设计更加灵活。

6.4.4 负载追踪和负载均衡

两级调度引入了负载均衡策略，通过追踪每个CPU核心上的当前负载情况，将处于高负载的CPU核心管理任务迁移到低负载的CPU核心上，尽可能保证每个核心的负载大致相同。

• 调度实体颗粒度负载追踪
  • 运行队列粒度负载追踪
  • 调度实体粒度负载追踪
• 负载均衡
  • 追踪每个任务和核心上负载后，需要考虑多核间负载均衡
  • CPU核心越来越多，不能单单对全部CPU核心均衡
  • Linux通过自下而上方式进行负载均衡
  • 为了设计简单只允许触发负载均衡的CPU核心拉去其他CPU任务到本地
  • 如果当前核心触发，现在最底层调度域进行均衡，再进入更高一级

6.4.5 能耗感知调度

ARM大小核（计算单元）：大核处理速度快，能耗更高；小核相反

• 容量：当前CPU核心再当前频率下的处理能力
• 功率：CPU再当前频率下的功率
  详见P149

Linux中的EAS（能耗感知调度）：通过使用当前架构的能耗模型来选用不同的核心

每个CPU都有当前的剩余容量，新任务负载小于剩余容量时，新任务放置在该CPU核心上不会导致频率提升。

6.5 调度进阶机制

• 如何制定执行任务的CPU核心，提高数据处理的局部性？
• 如何设置与统一当前OS上不同的调度策略

6.5.1 处理器亲和性

为了让开发者控制自己程序的执行，OS提供了处理器亲和性的机制，允许程序对任务使用的CPU核心进行配置

6.5.2 调度策略设置

Linux主要提供完全公平调度器、实时调度器和截止时间调度器，支持对不同的任务设置不同的调度策略

6.6 案例分析：现代调度器

6.6.1 Linux 调度器

Linux：O(n) -> O(1) -> 完全公平调度

6.6.2 macOS/iOS 调度器

见书P162

chapter7 进程间通信

为了考试，先跳了

chapter8 同步原语

驱动为我们呈现块设备，文件系统看块设备：数组

chapter9 文件系统

Linux 最经典的一句话是：「一切皆文件」，不仅普通的文件和目录，就连块设备、管道、socket 等，也都是统一交给文件系统管理的。
解析

9.1 基于inode的文件系统

• 基于inode的文件系统如何保存常规文件、目录文件和其他类型的文件?
• 对每种类型的文件有哪些操作，如何实现这些操作?
• 基于inode的文件系统如何规划使用存储空间?
• 什么是硬盘格式化?为什么格式化后硬盘的空间减少了?

本节所有存储结构均直接保存在块存储设备之上（暂时不考虑内存缓存）

9.1.1 inode 与文件

inode是用来记录磁盘块的一种结构。inode是“index node”的简写，即“索引节点”，记录了一个文件所对应的所有存储块号（存储的索引），通过一个inode，就可以访问这个文件的所有数据。

• 直接指针：12个、每个指向4KB数据块
• 间接指针：3个、每个指向2MB数据块
• 二级间接指针：1个、指向1GB数据块
• 最大能管理48KB+6MB+1GB

inode和内存页表有何相似之处?
如果我们把文件看成一个虚拟地址空间(4GB的文件就是04GB的空间),把硬
盘看作物理地址空间(4TB的硬盘就是04TB的空间)，那么对文件某个偏移量的
访问，首先需要将该偏移量翻译成硬盘空间的地址，这个过程与前文提到的虚拟内存
地址翻译的过程十分相似一而 inode 则担任了页表的角色，负责两个地址空间之间
的映射

inode中除了了记录存储的索引，还记录了相关的元数据：文件模式、文件链接数量、文件拥有者、大小、时间等。

一个文件系统一般会支持多种文件类型，例如常规文件、目录文件和符号连接文件

9.1.2 文件名与目录

了对用户更加友好，文件系统加人了我们熟悉的字符串形式的文件名，从而增加了一层从文件名字符串到inode号之间的映射。字符串形式的文件名不但更方便记忆，也使文件名与文件具体的存储位置解耦。

但inode字段不包含文件名，文件名并不是文件的元数据，其存放在目录中。

• 目录是一种特殊类型的文件，记录了从文件名到inode号的映射。
• 目录本身就是文件，可以通过递归来结构化组织文件系统中的文件。
• 目录中保存特殊的数据结构——目录项：每个目录向代表一条文件信息，记录了文件名和inode号
• 目录项的结构包含文件名、文件名长度、文件名对应inode号和目录项长度

目录操作：

• 查找
• 便利
• 增加
• 删除

目录 -> 目录项 -> inode（包含存储索引以及相关信息）

9.1.3 硬链接与符号连接

• 硬链接
  • 一个文件可以对应多个文件名（In file link 创建另一个名字link 这里就是硬链接）
  • 不会创建新的inode，而是先找到目标文件的inode，再目录中增加目录项
  • 从文件系统角度看file和link没有区别
  • 删除要所有硬链接都被删除（元数据中的链接数量就代表着有几个目录项指向）
  • 当inode链接数为0，inode及其索引的结构和数据都可以被销毁
• 软连接（符号连接）
  • 特殊的文件类型（Ln -s file slink 创建名为slink的软连接）
  • 符号连接文件中保存一个字符串，是一个文件路径，路径所对的文件称为目标文件
  • 简单实现：路径字符串直接保存在inode中，占据原本用于保存数据块指针的空间
  • 只支持读取操作：找到符号链接文件中的内容返回保存路径
  • 如果要修改符号连接文件中的内容：删除原文件，用新的路径穿件一个名字相同的文件

符号链接与硬链接的比较
符号链接与硬链接均允许应用程序使用一个新的路径访问已有文件(目标文件)，但两者的原理有所不同。当应用程序访问一个以目标文件路径为内容的符号链接时，文件系统读取符号链接中保存的路径，并继续进行解析，最终找到目标文件。而当应用程序访问一个指向目标文件的硬链接时，其直接通过硬链接的目录项访问到目标文件的inode。

此外，由于符号链接有自己的inode结构，其有自己的权限、时间等元数据，且删除符号链接本身，不会影响其目标文件。

硬链接与目标文件共享同一个inode结构，两者是等价的，并没有主次之分;删除其中的任意一个，应用程序依然可以通过未删除的另一个路径对文件数据进行访问。

除此之外，符号链接与硬链接对目标文件的要求还有所差别。在一个符号链接中，用户可以随意存放目标路径，即使这个目标路径不存在。只有在跟随符号链接进行路径解析时，符号链接中的路径才会真正被使用。也只有此时，符号链接中的路径不存在等问题才会引发文件系统报错。而对于硬链接,其目标路径在创建时即被用于查找inode,因此用户无法成功地创建一个指向不存在的文件的硬链接。同时，硬链接还要求目标文件不能为目录。由于对目标文件的要求不同，符号链接不受文件系统边界的限制，即在一个文件系统中，可以创建一个指向其他文件系统的符号链接；而硬链接的目标文件只能与被链接的目标文件处于同一个文件系统中。

9.1.4 存储布局

文件系统以特定的存储布局将文件数据和元数据保存在存储设备之中。

为了高效管理这些文件数据和元数据，文件系统通常将存储空间划分成不同区域，分别用于不同功能。

一个存储设备被划分成超级块、块分配信息、indoe分配信息，inode表和文件数据块等区域。

**

• 超级块：文件系统存储布局中必不可少的结构，记录了整个文件系统全局的元数据
  • 魔法数字保存在其中，不同的文件系统会用不同的魔法数据
  • 通过魔法数字可以知道存储设备上文件系统的类型和存储布局
  • 还保存了文件系统版本，文件系统所管理空间的大小、一些统计信息
  • 统计信息包括最大inode数量、空闲inode数量、能支持最大以及空闲的块数量
• 块分配信息（位图：位图格式来标记文件数据块每个区域中各个块的使用）
• inode分配信息（inode表：记录每一个inode使用状况）
• 文件数据块区域：负责保存文件的数据
  • 在一个存储设备上创建一个新的文件系统后，文件系统显示的可用大小比存储设备总容量小
    **

硬盘就是一个扇区组成的大数组，是无法被我们使用的，需要经过分区、格式化和挂载三个步骤。分区是把所有的扇区按照柱面分割成不同的大块，格式化就把原始的扇区数组变成了可被Linux文件系统使用的inode、block等基本元素了。

　　高级格式化（逻辑格式化）是根据用户选择的文件系统（FAT32 / NTFS / EXT2等）在磁盘的特定区域写入特定数据，然后初始化磁盘或分区，并清除磁盘或分区。

9.2 虚拟文件系统

• 多个不同的文件系统如何工作在同一个OS上？
• 同一个文件系统如何工作在不同的OS上
• 为何应用程序能使用统一的接口访问多个不同文件系统上的文件？
• 伪文件系统？

虚拟文件系统（VFS）对多种文件系统进行管理协调，允许他们在同一个OS上工作。

其定义了一些列内存数据结构，并要求底层不同文件系统提供指定的方法，VFS通过这些方法将不同文件系统的元数据统一转换成VFS的内存数据结构。

VFS管理和调用多种文件系统，并为应用程序提供一个统一的文件系统抽象。

虚拟文件系统 是 Linux 内核中的一个软件层，它暴露统一的接口给用户空间的程序，同时向用户程序屏蔽不同文件系统的差异，所有的具体的文件系统
VFS

9.2.1 面向文件系统的接口

VFS定义了自己的内存数据结构并围绕这个数据结构设计了文件系统方法

这些结构和方法组成了VFS面向文件系统的接口

让不同的文件系统可以共同工作在VFS的管理之下

VFS定义的内存数据结构
Linux的VPS基于inode制定了内存数据结构，包括超级块，inode，目录项等。
这些统一的内存数据结构掩盖了多种文件系统在设计和实现上的不同，使一不同格式保存在存储设备中的数据以统一的格式出现在内存中。

• VFS中的超级块
  • 保存了文件系统的通用元数据信息：文件系统类型、版本、挂载点信息
  • 每个挂载文件系统实例均在内存中维护了一个VFS超级块结构
  • 预留一个指针指向特有的超级块信息
  • 达到了统一数据结构，保留了不同文件系统的特有信息，增加了VFS下文件系统的灵活性
• VFS中的inode
  • 保存文件元数据
  • 若文件系统想要在内存inode结构中记录额外信息，需要在VFS的inode结构多分配空间
  • VFS维护了一个inode缓存，用哈希表保存OS所有inode结构
  • 当应用程序或文件系统需要使用某个inode，可以直接从缓存访问（如果存在）
• VFS中的文件数据管理
  • 用一个基数树来表示一个文件的数据
  • 每个叶子结点是一个内存页，保存了文件数据的一部分，为文件的页缓存建立了索引
• VFS中的目录项

  • 在内存中保存文件名和目标inode号结构
    

  • 也在内存中为目录项维护了一个缓存，叫目录项缓存
    

vfs定义的文件系统方法

• 在Linux等宏内核中，文件系统通常作为操作锡荣内核的一部分对外提供服务
• 应用程序需要通过系统调用对文件系统进行访问
• OS向操作系统内核发出系统调用请求，OS调用VFS处理请求，调用文件系统的方法并返回应用程序 P268图

9.2.2 面向应用程序的接口

OS面试使用

9.2.3 页缓存、直接I/O与内存映射

chapter10 设备管理

chapter11 系统虚拟化