OS 操作系统

发表于 更新于

操作系统：原理与实现

Chapter3 操作系统结构

复杂度管理方法 M.A.L.H

Modularity: 模块化，分而治之
Abstraction: 抽象，接口与实现分离，遵循宽进严出原则。例如虚拟内存、文件系统

对于大型系统，只有模块化和抽象，可能导致划分模块太多，交互关系复杂，因此还需要引入分层和层次结构控制复杂度。

Layering: 分层，每个层级是一套完整机制。通常一个模块只能与本层和上下层交互，不能跨层。例如OSI、TCP/IP
Hierarchy: 层次结构，大的子系统由多个小的子系统组织成。即同级模块的分层

宽进严出原则：容忍各种输入（包括恶意输入），严格控制模块的对外输出

微内核

宏内核架构：单点bug使整个系统崩溃。
微内核：解耦单个功能/模块（如文件系统、设备驱动）作为独立服务隔离运行，使内核成为一个最小功能集。

微内核架构服务隔离，单点出问题系统不会崩溃

内核态部分，称为μkernel\mu kernel

微内核优势：

  1. 弹性硬件拓展能力
  2. 硬件异构实现
  3. 功能安全
  4. 信息安全
  5. 时延确定

现代操作系统特征：1）虚拟内存；2）用户态、内核态隔离。

抽象的缺点

  1. 过度抽象会损失性能（原则：abstract but don’t hide power)
  2. 通用的抽象对数据库、Web服务器来说不是最优抽象。（软件比操作系统更了解如何使用抽象来使用硬件资源）

外核 Exokernel

外核将硬件资源抽象为LibOS，按需最小化调用

外核的缺点：LibOS针对应用定制，不通用、复用差（增大内存开销）

开源的缺点：开放设备驱动源码会透露实现细节

策略与机制

重要的操作系统设计原则：分离 policy 与 mechanism

policy：做什么。就像房子。例如什么用户、什么权限
mechanism：怎么做。就像盖房子的砖块。例如输入处理、桌面加载

Chapter4 内存管理

虚拟内存

两种内存管理

  1. 一个程序占用全部内存。程序切换时，将内存的数据写入硬盘（写入慢）
  2. 程序共享内存。无需频繁写入硬盘（问题：隔离性、地址不连续）
    方法2更好，于是催生了虚拟内存这个中间层来解决隔离性和地址不连续的问题。

有了虚拟内存技术，程序连续地存储在硬盘里，通过页表映射的方式高效使用内存。

内存分段与分页

分段：早期内存划分成大小不一样的段。缺点是容易产生内存碎片，不能充分利用内存资源。
分页：按规格划分内存和硬盘，任意虚拟页可以被映射到物理页。

多级页表

如果每个程序只维护1张页表，那么每张页表的大小将会是3千万GB！

单级页表每一项都要存在：因为整个页表必须连续，没有用到的页也预留着。

TLB Translation Buffer

TLB缓存了虚拟页与物理页的映射关系。
其中，每项TLB有一个标签（ASID/PCID）来区别不同的程序，切换程序时只需要刷新那个程序的页表，无需全部刷新。

页表切换时，操作系统需要主动刷新TLB。

换页与缺页

打开PS，占用2G内存；打开游戏，占用3G内存。一共占用5G内存，却可以在总共4G的电脑上运行。

换页：物理内存容量不够，将物理页写入磁盘，并回收资源。

缺页异常：内存找不到页，从磁盘找到对应页，写入内存。

预取：预测即将被访问的页，提前换入内存，减少不命中。

按需页分配：程序申请内存，只标记不换入，等到缺页异常再换入，提高利用率。

工作集模型

将程序使用的内存页集合共同保持在物理页中，避免颠簸，优先换出非工作集的物理页。
原理：时钟算法。通过定时比较当前内存页与上次检测结果的访问位，判断出哪些内存是当前工作集。

写时拷贝

对于两个程序共用的物理页，只在内存保留1份数据，只读地映射到页表。当其中一个程序对共享部分修改时，再拷贝一份可读写的数据（由异常处理完成操作）来完成修改。

内存去重

操作系统定期扫描内存中的相同内容，只保留其中一份。缺点是修改时需要写时拷贝，加大了时延。

针对内存去重的攻击：伪造数据，如果被去重了（表现为时延变长）就说明内存中存在相同的数据。

大页

TLB中翻译每个内存页要占用1个TLB缓存项。使用大页来解决缓存不够用的问题，提高命中率。大页的大小可以是2MB到1GB（普通页仅为4KB）。

物理内存分配与管理

内存碎片：无法被利用的内存。

外部碎片：有足够的内存却不是连续的，无法被分配使用。解决方法是按规格切分并分配内存。

内部碎片：切分并分配内存后（解决外部碎片），每块内存都没有被充分使用。

伙伴系统

物理内存分块，每块由2n2^n个（1，2，4，8）物理页构成。2块相同大小的块为伙伴，可以合并成大一号的块；大块也可以分裂出2个小一号的伙伴块。

伙伴系统：一个块被释放后，自动寻找伙伴块向上合并成大块，直到没有伙伴块为止。

SLAB分配器

伙伴系统最小分配4KB，然而许多服务只需要几十、几百B，SLAB用于分配这些小内存。
SLAB后来被改进成SLUB；还有一个最小开销、用于嵌入式的SLOB，这三者共称“SLAB分配器”。

SLUB：2^n Byte(3\leq n \textless 12) 的伙伴系统。有2个指针，partial指向一块空闲内存slab，current指向slab中的空闲块。

软件着色（软件方案）

对放到不同位置的物理页标记不同颜色。对于连续虚拟内存，优先分别到不同颜色的位置，避免不命中。

Chapter5 进程与线程

进程：每个进程对应一个运行中的程序。

有了进程的抽象，应用程序再运行时仿佛独占了整个CPU。

上下文切换：通过保存/回复进程的运行状态（上下文），使进程可以暂停、切换、恢复，实现CPU资源共享。

操作系统为每个进程提供独立虚拟地址空间（页表）。

线程：更轻量的执行单元，解决进程间数据不易共享、通信开销问题。

纤程：允许上下文在用户态而非内核态切换，再次减小开销。

进程

名称 状态
new 进程被创建，未初始化，不能调度
ready 进程初始化完成，未被调度器选择
running 进程被调度器选择，在CPU上运行
blocked 进程需要等待外部事件，暂时无法被调度
terminated 进程完成执行，不会再被调度

进程内存空间布局

内核 最顶端
用户栈 自顶向下拓展
代码库 共享，只读
用户堆 自底向上拓展
数据、代码段 静态

cat /proc/PID/maps 可以查看某个进程的空间布局

进程控制块与上下文切换

进程通过一个数据结构来保存它的相关状态（PID、进程状态、VM状态、打开的文件…）。

这个数据结构称为PCB（Process Control Block）

上下文切换：将前一个进程的寄存器状态保存到PCB，将下一个进程之前保存的状态写入寄存器。

fork

fork创建一个与父进程一样子进程（PID与VM不同）。

Chapter6 操作系统调度

调度策略

  • FCFS，First Come First Served
    先到先服务。用时短的服务需要等待，用户体验不好。

  • SFJ， Shortest Job First
    最短运行时间先服务。依赖到达时间，如果长时间任务先到，仍然是长时间任务占用系统。

  • STCF，Shortest Time-to Completion First
    最短剩余时间先服务。容易饿死长时间服务。

  • RR，Round Robin
    时间片循环服务。平均把时间放在所有任务上。

  • MLQ，Multi-Level Queue
    多级队列，高优先级的队列执行完后，才执行低优先级队列。同级别的队列，随机选择。同样，低优先级会饿死。而且一个任务锁定内存时，高优先级实质上执行不了。

  • MLFQ，Multi-Level Feedback Queue
    多级队列加上反馈。假设所有任务是短时间任务，优先执行，超过一定时间后降级，处理其他事务。定时刷新，重设任务为高优先级，防止饿死。

上面的所有调度方案，都是单用户下的调度；对多用户的调度和分配，我们需要引入份额。

  • 彩票调度
    生成随机数，例如生成32，则份额为10的不会执行，份额为20-40的会执行。
    这个方法显然不是完全按概率调度的。

  • 彩票货币
    A任务份额10，B任务份额5。在实际执行过程中，B可能会锁死A需要的内存，这时就需要A转让份额，让B快点执行完。
    通过在份额上，再增加一层抽象货币，即A分配1/3的份额给B时，转换成A给B100货币，更容易计算。

  • 步幅调度
    步幅调度设置虚拟时间T，严格按照1：3的分配执行两个任务。

OSTEP

Three Easy Pieces

  • 虚拟化：虚拟内存、CPU资源等，让程序认为自己有独立的、无限的资源。
  • 并发：让计算机在时间间隔内同时处理程序。
  • 持久性：IO、日志等。

虚拟化

Chap4 进程

进程可以看作正在运行的程序。
操作系统通过虚拟化CPU来提供一种假象：CPU资源无限，进程可以随意使用。

机制Mechanism

操作系统的低级机制（如上下文切换）帮助CPU实现虚拟化。

策略Policy

操作系统的高级智能策略帮助CPU高效调度程序。如各种调度策略。

进程API

所有现代操作系统都提供这些API：

  • 创建：现代操作系统使用懒加载方式加载程序到内存
  • 销毁
  • 等待
  • miscellaneous control
  • 状态
    • 运行
    • 就绪
    • 阻塞

Chap5 进程API

  • fork()
    fork()的子进程不会从main()开始执行，而是直接从fork()系统调用返回，就像它自己调用了fork()一样。
  • wait()
    wait()延迟自己的执行，直到子进程执行完毕，wait()才返回父进程。
  • exec()
    exec()不是创建新进程，而是直接将当前运行的程序替换为目标程序，exec()执行后，父进程就像从未运行过一样。对exec()的调用永远不会返回。

上面三个API使Unix Shell的构建（例如管道等功能）非常方便。
当用户向shell输入一个命令，它会做几件事：

  1. 在文件系统（PATH）中找到这个文件
  2. 调用fork()创建新进程
  3. 调用exec()的变体来执行该进程
  4. 调用wait()等待子进程结束
  5. 子进程结束，shell从wait()返回并再输出一条prompt string，提示用户输入
wc pc3.c > newfile.txt

由于fork()与exec()分离，exec()之前shell关闭标准输出，打开newfile.txt。这样，程序结果就不是打印在屏幕上，而是输出到文件中。

Chap6 Mechanism：受限直接运行

虚拟化有两个问题：

  1. 性能：如何在虚拟化的同时，不增加系统开销？
  2. 控制权：怎么确保操作系统的控制权，而不让某个程序无限制执行？

对于问题1，OS使用limited direct execution。程序可以在用户态直接执行，需要特权指令时（如IO请求），调用trap陷入内核态，用完返回用户态return-from-trap，继续直接执行。

另外一个问题是，要让所有程序共享CPU，因此不是无限制地让程序执行，操作系统要实现进程上下文切换。

  • 被动（协作方式）：等待程序yield，将控制权还回OS

对于程序的非法操作，控制权也会移交会OS，OS对这些非法程序一击出局。

  • 主动：利用硬件的时钟中断，定时拿回控制权
    上下文切换就是保存一些寄存器的值