OS10 期末复习

期末复习

• 一些名词
• multiprocessing（多进程）：在多个CPU（或多核）上同时运行
• multiprogramming（多道程序）：单个CPU/核心上营造同时运行多个任务/进程的假象
• multithreading（多线程）：同时运行多个进程/线程
• concurrency（并发）：MTAO，交错地执行营造同时运行的假象，侧重针对并发程序对共享资源的保护（各种互斥锁）
• parallelism（并行）：在多核/多CPU上的并发，真的同时运行，侧重拆分工作任务使多核/多CPU能够并行计算

• 操作系统在初始化时设置陷阱表（陷阱表用于处理同步中断（trap），与用于处理异步中断（interrupt）的中断表不同）

• 用户程序调用系统调用时，首先跳转到C标准库的一些手工汇编的函数中，正确放置参数、设置陷阱号，之后陷入内核态，硬件将原先的寄存器值&标志位&PC存放在内核栈中，跳转到陷阱表的对应位置执行操作系统的系统调用处理程序（handler）；系统调用执行完毕后，处理程序将返回值放置于寄存器或栈中，执行return-from-trap，由硬件从内核栈中恢复寄存器状态，返回用户态、跳转到原函数中。

• FILE *fopen(const char *filename, const char *mode);返回一个指向FILE数据结构的指针；失败则返回空指针。

Mode 参数	描述
"r"	以只读方式打开文件。文件必须存在，否则打开失败。
"w"	以写入方式打开文件。如果文件存在，内容会被清空；如果文件不存在，会创建新文件。
"a"	以追加方式打开文件。如果文件存在，写入的数据会追加到文件末尾；如果文件不存在，会创建新文件。
"r+"	以读写方式打开文件。文件必须存在，否则打开失败。
"w+"	以读写方式打开文件。如果文件存在，内容会被清空；如果文件不存在，会创建新文件。
"a+"	以读写方式打开文件。如果文件存在，写入的数据会追加到文件末尾；如果文件不存在，会创建新文件。

• int fclose(FILE *f)

• int dup2 (int old, int new)

• int pipe (int pipefd[2])对pipefd[1]的写入可以从pipefd[0]中读出

• off_t lseek (int fd, off_t offset, int whence)改变文件数据结构中的一个值，不会触发磁盘寻道

• 目录中不同的可读文件名可以指向同一个inode号。inode数据结构中维护着对它的引用计数。ln file file2创建了一个新的可读文件名file2指向file指向的inode，将inode引用计数+1。rm file删除可读文件名file，同时将对应inode引用计数-1 。当引用计数清零时，文件才会真正被删除（释放inode）。这被称为硬链接

• 软链接：使用ln -s file file2创建一个软链接file2它只是一个指向符号file的符号链接，类型为l。可视为只是file的一个同名引用。若先rm file，就会导致file2的悬垂引用。

• 使用高层次I/O、高层次缓冲区的原因
• 减少系统调用（读写kernel buffer）的次数，降低开销（向user kernel的函数调用的开销明显小于syscall）
• 简化了kernel的设计
• 在用户层面提供对一些格式的控制。例如低层次I/O不关注数据类型，要实现getline方法只能使用高层次I/O，先通过syscall读入大块数据，再在用户态下找到第一个换行符

• 对于每个进程，内核维护从文件描述符（fd）到打开文件描述（Open File Description）的映射

• 打开文件描述 是内核中的一个数据结构，其中包含：文件存放在什么位置、当前读写位置、引用计数

• 当进程fork时，子进程的文件描述符继承了父进程的，它们均指向同一个打开文件描述，共享读写位置；内核将这个打开文件描述的引用计数+1

• 一个进程使用close关闭文件描述符时，将其指向的打开文件描述的引用计数-1；若降为0，则关闭该文件

• 当进程dup2时，进行文件描述符的复制：创建一个新的文件描述符，指向原来的打开文件描述，共享读写位置；同时引用计数+1

• 上下文切换频率：10-100ms；进程间切换开销：3-4us；线程间切换开销：100ns

• 超标量（superscalar）处理器可以在单个时钟周期内处理多个独立的指令

• 超线程（hyperthreading）处理器通过模拟多个逻辑核心和资源复用，允许单个物理核心同时执行多个线程

• 称调度器是不确定性的（Non-determinism），若其可以在任意时刻调度线程。这会使得测试非常的困难

• 一些同步术语
• 临界区：访问共享资源的一段代码
• 竞态条件（race condition）：多个线程先后同时进入临界区
• 不确定性（indeterminate）程序：由一个或多个竞态条件组成
• 互斥（mutual exclusion）原语：保证只有一个线程进入临界区

• 锁的类型
• 中断锁
• 睡眠锁（获取）：关中断，查询是否持有；若持有，将本线程放入等待队列，休眠同时开中断；若没有被持有，则标记为持有，开中断
• 自旋锁：朴素实现-不断test&set（浪费时钟周期，不适合单处理器）；改进实现-test&set用于获取小锁查看缓冲区，实际上与中断锁相同

• 条件变量：wait释放锁并休眠；signal唤醒线程并试图获取锁；broadcast唤醒所有线程。读者写者问题中，由于读者不会唤醒读者，因此写者离开时要负责唤醒所有读者
• Hoare-style：执行Signal的线程马上放弃硬件资源并移交给等待线程，后者马上执行；之后，后者在离开关键区/调用Wait时释放锁，硬件资源回交给前者。特点是被唤醒的线程会立即执行，条件变量对应的条件保证成立（例如，生产者生产后Signal，被唤醒的消费者可以确定缓冲区中一定有商品）。需要更多的上下文切换开销
• Mesa-style：执行Signal的线程继续占用硬件资源和锁，被唤醒的线程被放入READY队列，而前者继续执行。特点是被唤醒的线程不能肯定对应条件一定成立。因此需要在循环中检查条件

• 调度的评价指标
• 完成时间/周转时间（Completion Time）：最小化完成一项任务（提交任务到完成要经历的）需要的时间（例如响应），通常取平均值/中位数
• Makespan：完成一系列任务需要的总时间
• 响应时间（Waiting Time/Response Time）：从提交任务到任务开始被处理要经历的时间
• 吞吐量（Throughput）：最大化单位时间内处理的任务数量。可能需要更快的上下文切换。
• 主要方法：最小化开销（例如上下文切换）、更高效利用资源
• 可以为不同任务根据其规模大小给定权重，大任务大权重，完成收益也越大。
• 公平性（Fairness）：以合适的方式将CPU资源分配给不同用户

• 不同调度策略的优劣：
• FCFS：HOL（Head-of-Line） Blocking，短任务往往会被长任务所阻塞；也即“护航效应”（convey effect）
• RR：优点：相较于FCFS，公平性较好；缺点：频繁的上下文切换对长任务不友好；若时间片长度显著小于任务长度，哪怕不考虑上下文切换，平均完成时间也会很大；cache需要在不同线程之间切换，cache命中率低于FCFS
• 严格优先级调度：会造成低优先级任务的饥饿；会导致优先级逆转、从而导致死锁。解决方法：动态优先级控制
• SJF：非抢占最优策略（平均完成时间）
• STCF/SRTF：最优策略（平均完成时间），但不公平
• 彩票调度：一个优点是避免了极端情况，不会导致饥饿；其次是开销小、操作快；再次是轻量，不用维护任何状态。为了避免随机性带来的不确定结果，可以使用步长调度（stride scheduling）。
• MLFQ：改进1:不同queue之间按比例分配时间片；这样沉在底下的任务不会饥饿。改进2:每隔一段时间就将所有任务重新放入最高优先级队列。既能避免饥饿，又能正确处理CPU密集型任务转变为交互密集型任务的情况。改进3:修改任务在不同queue之间切换的逻辑：若任务用完了它在该队列的时间配额，就降低其优先级。既能避免饥饿，又能避免调度程序被愚弄。最终的规则：优先运行高优先级队列中的任务；任务进入时先放在最高优先级；一旦任务用完了所在优先级的时间配额，就将其移入下一个优先级；经过一段时间S，就将所有任务重新放入最高优先级。

• 多处理器调度：在实现上可以为每个核维护自己的数据结构；为了局部性和cache hit，OS尽量总将一个任务分配在一个CPU上（提高缓存亲和性）
• 单队列调度（Single Queue Multiprocessor Scheduling，SQMS）：简单公平，适合低并发；容易因为队列锁和缓存亲和性造成开销过大
• 多队列调度（Multi Queue Multiprocessor Scheduling，MQMS）：为每个CPU维护一个队列。可以有效避免锁开销，天生具有较高的缓存亲和性。但不同CPU之间容易产生负载不均。
• 改进：工作迁移（migration）：间或地将工作转移到空闲的或别的CPU
• 工作窃取（stealing）：负荷较少的CPU查看其他CPU并窃取工作
• O（1）和CFS使用多队列，而BFS使用单队列

• Gang Scheduling：当多核系统上多个线程彼此协作时，尽量让它们一起被调度，这会使得自旋等待更加高效。现代操作系统上，OS调度的单位是线程而非进程

• 实时调度（RTS）中的硬实时
• EDF：选ddl最近任务。最优性（若理论上可调度）。开销大（动态调整）
• RMS：周期越短优先级越高。利用率不超过69%可调度
• DM：截止时间越短优先级越高

• 工作保留：只要有可运行任务，CPU就不会空闲。默认只考虑这个。

• 饥饿：FCFS会，RR不会，严格优先级会（优先级反转），SRTF长任务会

• 现代OS调度策略：
• Linux O1:调度时间O1，双队列：active&expired，140个子队列，内核任务永远优先用户任务，动态优先级调整，长时间未运行提高优先级
• Linux CFS：类似步长调度，总是选择vruntime最小的任务（红黑树），优先级越高vruntime增长越慢

• 最优策略：
• 吞吐率（降低开销）：FCFS
• 平均完成时间/IO吞吐：SRTF
• 公平（CPU时间）：CFS
• 公平（等待时间）：RR
• ddl：EDF

• 死锁条件：互斥、持有并等待、非抢占、循环等待

• 防止死锁：预防死锁（偏序）；死锁恢复；死锁避免（提前预判，银行家算法）；重启；回滚；

• Tail Latency Service-Level Objectives：尾延迟SLO，以高百分位延迟（如P99、P999）作为服务质量达标指标。例如要求99%请求在100ms内完成。

• 调度论文：
• ZygOS：单队列、降低系统开销；工作窃取；控制尾延迟
• Shinjuku：动态调整时间片
• Tiresias：二维调度框架；解决深度学习GPU调度
• DRF：主导资源分配，使所有用户主导资源份额相等
• FairRide：缓存公平分配，阻塞虚假访问；共享多的文件阻塞几率小；保持隔离保证、策略无关，尽可能帕累托最优
• Jolteon：服务器无感知计算，细粒度调整资源，细粒度计费
• DistServe：解耦Prefill和Decode，打batch，提高LLM效率
• LoongServe：动态调整并行度，应对不同上下文长度

• VM动机：隔离、保护、权限

• VM翻译可能导致：访存、IO、通信、PF

• VM发展史：
• 朴素B&B：访存地址只能在Base和Bound之间
• 带翻译B&B：访存地址实际上是偏移量。简化加载（不需要重定位）
• BB缺点：碎片化；不支持稀疏地址空间；共享困难
• Segmentation：访存地址segnum+seg内偏移；支持地址保护、共享、稀疏地址空间；seg表非常小可以存储在CPU中，访存很快；缺点是容易碎片化、内部碎片、外部碎片、swapping受限
• Paging：支持地址保护、共享、稀疏地址空间；无外部碎片，；页表很大需要进行分级

• 多级页表：32位：10+10+12；48位：9+9+9+9+12；39位：9+9+9+12.优点：节省内存、降低开销、方便不同规模共享；缺点：访问开销大、设计复杂（以时间换空间）

• “当前特权级别”（Current Privilege Level，CPL）

• 倒置页表：仅维护全局哈希表，大小等于物理页帧数，通过哈希算法将ID+虚拟页号映射到物理页帧号。优点：内存高效、进程共享一张表；缺点：查找慢、共享处理复杂

• TLB：VPN-PPN（PTE）键值对。两种上下文切换方式（全部设为valid；TLBE加入PID）注意PTE中global位可使得不被刷出TLB

• cache未命中：强制性、容量（无法涵盖工具集）、冲突（缓存抖动）、一致性（其他进程更新了内存使得cache内容失效）

• TLB的缓存架构：128-512line，全相连映射、LRU替换策略、不支持写入、页表被修改时将TLB对应条目标记为失效

• 物理索引缓存：避免别名问题、上下文切换无需刷新cache；缺点是TLB处于关键路径上，可能延迟较高

• 虚拟索引缓存：TLB不在关键路径上，可能更快；可能存在别名问题（同一数据映射到多个位置）；上下文切换需要刷新缓存。

• Virtual Index Physical Tag；cache 的index+offset不大于12bit时，翻译和访问cache可以同步进行

• PF原因：
• invalid（未被分配/demand paging）
• Privilege Level Violation（CPL过低的用户态执行内核指令、访问内核空间）
• Access Violation（空指针、野指针、已释放的内存、只读内存）
• 对应的最低级页表未被创建
• PTE private COW

• 拓展堆栈时，触发PF分配新的匿名页，映射到磁盘中的全0页

• 进程fork时，复制一份页表并全部标记为COW

• backstore两类：swap space；file

• swap管理：分区或文件。分区是连续磁盘空间，性能更高，但需要提前分配；文件可以灵活调整大小。全局交换（所有进程共享）可能会引起抖动

• demand paging性能评估：
• miss rate：工作集大小、页面替换算法、prefetch
• miss penalty：更快存储、减少磁盘寻道（swap分区连续分配）

• 四类miss的解决方法：
• 强制：preload，huge pages，working set tracking（将所有工作集换入）
• 容量：增大PM，优化工作集，优化替换算法
• 冲突：/
• 一致性：多核间同步TLB无效化

• 替换策略：
• FIFO：公平，低效。可能换出频繁使用页
• Random：简单开销小；难以给出性能保证
• MIN：难以预知未来
• LRU：性能相对较好。完全LRU开销大（维护链表，访问页时取出移到头部）。在极少情况下表现极差（N+1个虚拟页N个页帧，顺序访问）

• Stack-Property：PM⬆️missrate⬇️
• LRU、MIN符合该性质
• FIFO不符合该性质。存在序列是的PM容量增加时miss-rate反而增加

• LRU：时钟算法。access位为1时置零；为0时victim。考虑同步时可能陷入死循环（A将bit置零后B马上置为1）。时钟转动越慢，内存空闲程度越高。

• N次机会版本：access 位为1时置为0，重置计数器；为0时计数器加一，达到N则victim。dirty page的N可以比较大

• Second-Chance List Algorithm（VAX/VMS）：active list（valid）和second chance （SC） list（invalid），FIFO组织
• page初始进入active
• 对SC中页的访问触发PF，将该页移入active队首，active队尾移入SC队首
• 对新页的访问触发PF，移入active队首，active队尾进入SC队首
• 优点：更少访问磁盘；缺点：PF handler开销大

• Free List：PF时直接从list中取victim；list在后台通过时钟算法填充（Page out Daemon），页进入list时被标记为invalid（dirty时预先写入磁盘），list中的页被访问时移除list

• 反向页映射：选中物理页帧要换出时，应该快速查询相应PTE并标记为invalid。每个物理页维护一个指针，多个指针同时指向一块地址空间，空间内维护一棵红黑树，查找红黑树得到所有映射物理页的VMA，再找到对应的页表。许多物理页共用一棵红黑树，降低开销

• 两种victim策略：Global（从所有进程所有页选取），Local（从当前进程所有页中选取）

• Equal：每个进程得到相同页帧配额

• Proportional：根据进程大小按比例分配页帧配额

• Priority：优先级高的进程可以从低优先级进程的页中选取victim

• PF Frequency：PF更多的进程分配到更多页帧

• VM抖动Thrashing：可以将一些进程挂起，整个换出PM，降低总工作集大小

• VM论文：
• FaRM：RDMA；对称模型；共享地址空间；抽象；无锁读，解决数据中心问题
• Infiniswap：RDMA为途径窃取内存，slab管理，远程分页，双随机负载均衡，解决内存分配不均、利用率低
• AIFM：用户态下RDMA绕开内核，RDMA时yield，按需取件，解决RDMA性能差问题
• PipeSwitch：流水线换模型，统一内存管理，主备工作器，解决GPU训练/推理问题
• TGS：生产任务和机会任务拼车，自适应速率控制，共享统一内存

• IO需求：
• 异构性-标准化
• 不可靠-可靠性
• 不可预知-速度

• CPU-（Hos桥）-PCI0-（PCI桥）-PCI1（外围组件互联）总线：图像控制器，IDE磁盘控制器，内存控制器，SCSI控制器，拓展总线接口

• 总线串联n个设备，PCI总线支持并行（复用多个请求）；PCIe是一簇电线，不并行，空分复用

• CPU通过两种方式访问控制器的寄存器：port-mapped（in/out）；memory-mapped（load/store）。它们映射在物理地址空间中（boot时设置），CPU直接写入以控制IO

• 不同IO性质：
• 数据粒度：单字节/block
• 访问：顺序/随机；
• 持续监测polling/触发中断。Polling不用频繁陷入内核，但若设备不常使用可能浪费周期

• Programmed IO：所有数据通过in/out/l/s指令进行。硬件简单，占用处理器周期

• DMA：控制器直接访问内存总线，绕开处理器

• 设备驱动：直接与硬件交互的代码。top half被系统调用访问，用于实现设备无关的指令，可能将线程挂起；bottom half被中断历程访问，用于获取引起中断的输入，在输入完毕后唤醒线程

• I/O请求的生命周期：
• 用户程序发起请求
• 陷入内核的I/O子系统，给设备驱动发送请求，在合适情况下阻塞进程。
• 进入驱动top half，处理请求、给控制器发送指令，配置控制器使其阻塞
• （控制器在硬件层面控制设备进行I/O，设备硬件持续监测，当I/O完成后发起中断）
• 进入驱动bottom half，接受中断、存储输入数据
• 进入驱动top half，判断哪个I/O完成了，向I/O子系统传输状态变化。
• 进入I/O子系统，向进程传输数据或报告错误。

• IO子系统：块设备（访问数据块、open/read/write、Raw IO、内存映射文件访问），字设备（访问单字、get/put、line-editing库函数）

• 发起IO请求后的操作：wait/dont wait（直接返回）/tell me later（安静填充缓冲区，结束后告知）

• 磁盘：扇区-轨道-柱面。SMR：重叠磁道提升容量，但随机读写性能下降（需要先擦相邻轨道）
• 扇区替换（sector sparing）重定向损坏扇区到备用扇区
• slip sharing：整体后移，维持连续性
• track skewing：相邻磁道起始扇区偏移，一次性访问时方便
• 磁盘控制器维护逻辑块地址（LBA）到实际三元组的翻译

• SSD：
• 写入：必须先擦出页所在块的所有页，再写入所有页。维护空闲块池以加速，新数据写入空闲页而非覆写，之后更新FTL映射
• 写入比读取慢10倍
• 每个块1k-100k擦写周期
• FTL（闪存翻译层）：LBA（逻辑块地址）-PBA（物理块地址）

• 文件系统指标：相应时间/延迟；带宽/吞吐量
• 利用率U=到达速率lambda/服务速率mu
• 排队时间：Tq=Tser (1+C)/2 u/(1-u)
• 队列长度：lambda Tq

• 提升性能：并行、overlap（等待时进行其他）、调度策略、重排序piggypack

• 磁盘调度：
• FIFO：公平、大量随机读写
• SSTF：开销最小请求。容易饥饿
• SCAN：不断从大到小从小到大遍历，选择最近请求
• C-SCAN：周游方向限定，更公平

• OS下文件系统的基本传输单位是block，4KB

• 文件系统：路径-（目录文件）-inum-（inode）-文件具体blocks
• 文件表中OFD为运行中的程序维护文件的inum
• 文件系统组成：目录、index（inode）、存储块、空闲块位图

• 案例分析：重点看如何存储文件逻辑块到实际块的映射。
• FAT（File Alloction Table）：将文件号+块号+偏移翻译成磁盘物理位置。结点数组，文件的不同结点按乱序链表组织。文件属性被记录在目录中。实现简单；开销为线性复杂度；随机访问块需要不断遍历链表
• UNIX FS：inode内部存放文件元数据和文件属性，使用多层次树结构维护文件块+偏移量到磁盘块的映射。直接指针12个48KB，间接指针指向中间块1024个指针4MB；双重间接指针4GB
• Berkeley FAST FS：inode分布在更靠近数据的轨道上，数据块、元数据、空闲表在同一个块组里。新文件块尝试连续分配，first-fit。空闲块位图。块组内预留空间方便增删查改。skip-sector positioning：同一个文件多个扇区交错存储，方便读写间隙处理器处理。缺点是对微文件低效；需要预留空间。
• NTFS：可变长度拓展。master FT维护文件号到磁盘位置的映射，每个条目最多1KB，几乎全是键值对，存放元数据（包括文件名，存放多个可实现硬链接），小文件直接存放文件数据，中文件存放磁盘块（起始，长度）二元对，大文件指向其他的MFT条目。目录通过B树实现。

• Buffer caching：LRU总体上表现良好，但对扫描磁盘行为低效；可以动态设置caching比例
• FS Prefetching：提早取出顺序块
• Delayed Writes：buffer cache满或周期性刷新（降低data loss）时，才最终写入磁盘。快速完成syscall；方便调度器使用电梯算法避免随机寻道；延迟块分配增强连续性；避免不必要的磁盘访问

• FS三bility：可用性、持久性、可靠性

• 持久性：
• 纠错码
• RAID（独立磁盘冗余阵列）
• RAID1:磁盘映像，一起写，并行读；热备盘
• RAID5:分布式校验，每个条带单元一个校验块
• RAID6:双备份，每个条带单元两个校验块
• 纠删码/纠错码几个冗余几个允许故障

• 可靠性
• 谨慎排序并恢复（FFS/fsck）：分配-写入数据块，分配-写入inode，更新空闲位图，更新目录映射，修改时间。故障恢复需要全盘扫描
• 版本化&写时复制（ZFS）：新旧版本通过指针结构关联，原子修改指针。缓存一定数量的写批量写入

• 事务：一串原子化的读写操作，start-execute-commit。
• 使用日志记录commit，NVRAM加速此过程
• Log-structed：始终以日志存储，大部分情况下追加。适合SSD
• Journaling：日志仅用于故障恢复。在寻找到空闲磁盘块、inode表项后，先在日志中写入再写入空闲位图、写入inode表项、写入目录，最后commit。无commit则截断。通常只记录元数据更新

• 2PC

• FS论文：
• 去冗余存储：将多个文件共有段移除，指纹技术，新数据到来时，先在index cache中检查新数据指纹是否已在cache中，如有则重复于对应ID的container中的某段；如没有，则进入summary vector中查找，若输出no，则一定是新数据，若输出yes，则可能重复，需要访问disk index查找是否有相同指纹。若认定是新数据，则在插入对应container中，要同时更新disk index、summary vector和index cache
• IOFlow：端到端SLA，分离控制面数据面，数据平面动态队列管理
• GFS：单master结点，数据分块，master协调客户端直接与chunkserver交互
• EC-cache：基于纠错码的集群缓存，选择最先到达的k个解码
• Chord：解决P2P数据定位问题，每个顶点维护后面一个的编号和一个指表