文章目录《操作系统:原理与实现》 创作背景操作系统是现代计算平台的基础与核心支撑系统,负责管理硬件资源、控制程序运行、改善人机交互以及为应用软件提供运行环境等。长期以来,我国信息产业处于“缺芯少魂”的状态,作为信息产业之“魂”的操作系统是释放硬件能力、构筑应用生态的基础,也是关键的“卡脖子”技术之一。当前,以华为海思麒麟与鲲鹏处理器、银河飞腾处理器等为代表的ARM平台在智能终端、服务器等应用场景的崛起,以及以开源为特色的RISC-V指令集架构的出现及其生态的蓬勃发展,逐步改变了x86处理器一统天下的局面。因此,需要结合ARM等指令集架构与体系结构来构筑新的操作系统或深入优化现有操作系统,从而充分发挥硬件资源的能力并给用户提供更流畅的体验。 操作系统是一个不断发展的学科。随着云计算、大数据、AIoT等新应用场景的兴起,以及非易失性内存、智能设备、各类加速器等新硬件的广泛应用,我国对操作系统人才的需求进一步扩大。我国对操作系统人才的需求进一步扩大,然而操作系统课程的内容却普遍相对陈旧,许多知识点和教授的方式还停留在上世纪90年代,教学与实际工业界研发脱节严重,高校毕业的应届生难以直接参与操作系统一线研发工作。因此,操作系统的教学亟需与时俱进的改革。首先,操作系统教材需要体现操作系统的核心原理与设计,从而帮助读者建立对操作系统的系统性认识;其次,操作系统教材需要反映国际的研究前沿,当前操作系统技术仍在迅猛发展,很多新的问题随着新处理器、新加速器架构、新应用场景的出现而不断涌现,同样,很多经典的问题也会出现新的解决方法,这些都给操作系统的设计与实现提供了新的思路;最后,操作系统教材需要反映工业界实践,操作系统是一门系统性与实践性非常强的学科,脱离实现来谈设计很容易陷入纸上谈兵的陷阱。当前操作系统领域的前沿研究与工业界实践结合得越来越紧密,在工业界新应用场景与需求的推动下,研究人员将前沿研究应用到工业界实践,再由工业界实践反馈进一步推动前沿研究,从而形成了良好的循环,并且循环的速度越来越快。 独创性上海交通大学陈海波教授多年以来一直辛勤坚守在操作系统研究与工业实践的第一线,取得了突出的研究成果并对产业界产生了重大影响,是国际计算机领域的知名青年学者。他从2009年开始一直在复旦大学、上海交通大学从事操作系统的教学工作,致力于将前沿研究与工业实践传递到人才培养与课堂教学中去,得到了广大学生的好评,培养了一批又一批在学术界与工业界崭露头角的青年计算机从业者。他和同事夏虞斌教授一起,与上海交通大学并行与分布式系统研究所及领域操作系统教育部工程研究中心的多位老师和博士研究生共同合作,将他们对操作系统的深入理解、多年来的科研体会与一线的教学实践加以总结,在教学实践与反馈的基础上,撰写了这本新的操作系统书籍:**《操作系统:原理与实现》****。**新书主要增强了原理与实现的解耦,先基于“第一性原理”,从具体问题“自然导出”抽象概念,然后再介绍具体实现。在原理方面,增加了微内核设计思想对不同抽象的影响;在实现方面,加强了教材与ChCore代码的对应。在配套实验方面,对实验做了同步调整,增加了在树莓派上实现硬件启动的实验。 作为操作系统教材的新尝试,该书融合了作者的教学经验与工业实践经验,以三个“面向”为导向,即面向经典基础理论与方法,面向国际前沿研究,面向最新工业界实践,深入浅出地介绍操作系统的理论、架构、设计方法与具体实现。本书将原理与实现解耦,从具体问题导出抽象概念,然后分析实现方法。全书内容以ARM架构为主,x86架构为辅;以微内核架构为主,同时兼顾宏内核与外核等架构。 除纸质版教材外,本书还配有网络章节、在线社区和课程实验。与本书配套的微内核架构教学操作系统ChCore由上海交通大学并行与分布式系统研究所设计并实现,通过ChCore相关实验,读者可在动手实践中获得第一手经验。 专家推荐软件是计算系统的“灵魂”,而操作系统则是软件运行和支撑技术的核心,“CPU+操作系统”更是成为信息产业生态的核心、信息时代安全的基石。自1956年第一个实用操作系统诞生以来,操作系统已历经60多年的发展。它的发展一方面伴随着以CPU为代表的硬件及其组成结构的发展,另一方面是为了支持多机、分布式和网络环境,以及满足新型计算模式和新型应用的需求。迄今,以20年左右为周期,操作系统已出现从主机计算时代到个人计算时代,再到移动计算时代的两次重大变迁,每次变迁均涉及计算设备及其用户两方面的数量级的跃升,同时诞生了新的“CPU+操作系统”生态。当然,从技术的本质来看,操作系统“向下管理各种计算资源,向上为应用程序提供运行环境和开发支撑,为用户提供交互界面”的角色定位未变。 以5G、人工智能、云计算与物联网等为代表的新一轮科技革命与产业变革正在重新定义我们的信息社会。构建新型信息社会的一个关键因素是坚实的计算机基础设施,这对计算机系统能力培养提出了新的要求,需要广大信息产业从业人员具有良好的系统分析、设计与验证能力。 作者简介目录目 录 丛书序言 序言一 序言二 前言 第一部分 操作系统基础 第1章 操作系统概述 2 1.1 简约不简单:从Hello World 说起 2 1.2 什么是操作系统 3 1.3 操作系统简史 5 1.3.1 GM-NAA I/O:第一个 (批处理)操作系统 5 1.3.2 OS/360:从专用走向通用 6 1.3.3 Multics/UNIX/Linux:分时与多任务 6 1.3.4 macOS/Windows:以人 为本的人机交互 7 1.3.5 iOS/Android:移动互联网 时代的操作系统 8 1.4 操作系统接口 10 1.5 思考题 12 参考文献 12 第2章 操作系统结构 13 2.1 操作系统的机制与策略 14 2.2 操作系统复杂性的管理方法 15 2.3 操作系统内核架构 17 2.3.1 简要结构 18 2.3.2 宏内核 18 2.3.3 微内核 20 2.3.4 外核 22 2.3.5 其他操作系统内核架构 24 2.4 操作系统框架结构 26 2.4.1 Android系统框架 26 2.4.2 ROS系统框架 28 2.5 操作系统设计:Worse is better? 29 2.6 ChCore:教学科研型微内核操作系统 31 2.7 思考题 32 参考文献 32 第3章 硬件环境与软件抽象 35 3.1 应用程序的硬件运行环境 35 3.1.1 程序的运行:用指令序列 控制处理器 36 3.1.2 处理数据:寄存器、运算和访存 38 3.1.3 条件结构:程序分支和 条件码 43 3.1.4 函数的调用、返回与栈 46 3.1.5 函数的调用惯例 50 3.1.6 小结:应用程序依赖的 处理器状态 52 3.2 操作系统的硬件运行环境 54 3.2.1 特权级别与系统ISA 54 3.2.2 异常机制与异常向量表 57 3.2.3 案例分析:ChCore启动与 异常向量表初始化 60 3.2.4 用户态与内核态的切换 61 3.2.5 系统调用 64 3.2.6 系统调用的优化 66 3.3 操作系统提供的基本抽象与 接口 67 3.3.1 进程:对处理器的抽象 69 3.3.2 案例分析:使用POSIX 进程接口实现shell 70 3.3.3 虚拟内存:对内存的 抽象 73 3.3.4 进程的虚拟内存布局 75 3.3.5 文件:对存储设备的 抽象 77 3.3.6 文件:对所有设备的 抽象 79 3.4 思考题 80 3.5 练习答案 81 参考文献 82 第4章 虚拟内存管理 83 4.1 CPU的职责:内存地址翻译 84 4.1.1 地址翻译 84 4.1.2 分页机制 85 4.1.3 多级页表 87 4.1.4 页表项与大页 91 4.1.5 TLB:页表的缓存 93 4.2 操作系统的职责:管理页表映射 96 4.2.1 操作系统为自己配置页表 96 4.2.2 如何填写进程页表 97 4.2.3 何时填写进程页表:立即映射 101 4.2.4 何时填写进程页表:延迟映射 104 4.2.5 常见的改变虚拟内存区域的接口 108 4.2.6 虚拟内存扩展功能 109 4.3 案例分析:ChCore虚拟内存 管理 112 4.3.1 ChCore内核页表初始化 112 4.3.2 ChCore内存管理 115 4.4 思考题 118 4.5 练习答案 119 参考文献 121 第5章 物理内存管理 122 5.1 操作系统的职责:管理物理 内存资源 122 5.1.1 目标与评价维度 122 5.1.2 基于位图的连续物理页 分配方法 123 5.1.3 伙伴系统原理 126 5.1.4 案例分析:ChCore中伙伴 系统的实现 127 5.1.5 SLAB分配器的基本设计 131 5.1.6 常用的空闲链表 133 5.2 操作系统如何获得更多物理内存资源 134 5.2.1 换页机制 134 5.2.2 页替换策略 137 5.2.3 页表项中的访问位与 页替换策略实现 140 5.2.4 工作集模型 141 5.2.5 利用虚拟内存抽象节约物理内存资源 142 5.3 性能导向的内存分配扩展机制 143 5.3.1 物理内存与CPU缓存 144 5.3.2 物理内存分配与CPU 缓存 146 5.3.3 多核与内存分配 147 5.3.4 CPU缓存的硬件划分 147 5.3.5 非一致内存访问 (NUMA架构) 149 5.3.6 NUMA架构与内存分配 150 5.4 思考题 151 5.5 练习答案 152 参考文献 152 第6章 进程与线程 154 6.1 进程的内部表示与管理接口 154 6.1.1 进程的内部表示— PCB 154 6.1.2 进程创建的实现 155 6.1.3 进程退出的实现 159 6.1.4 进程等待的实现 160 6.1.5 exit与waitpid之间的信息传递 162 6.1.6 进程等待的范围与父子 进程关系 164 6.1.7 进程睡眠的实现 166 6.1.8 进程执行状态及其管理 166 6.2 案例分析:ChCore微内核的 进程管理 169 6.2.1 进程管理器与分离式 PCB 169 6.2.2 ChCore的进程操作: 以进程创建为例 170 6.3 案例分析:Linux的进程创建 172 6.3.1 经典的进程创建方法: fork 172 6.3.2 其他进程创建方法 175 6.4 进程切换 179 6.4.1 进程的处理器上下文 180 6.4.2 进程的切换节点 180 6.4.3 进程切换的全过程 181 6.4.4 案例分析:ChCore的 进程切换实现 182 6.5 线程及其实现 191 6.5.1 为什么需要线程 191 6.5.2 用户视角看线程 192 6.5.3 线程的实现:内核数据 结构 194 6.5.4 线程的实现:管理接口 195 6.5.5 线程切换 200 6.5.6 内核态线程与用户态 线程 200 6.6 纤程 202 6.6.1 对纤程的需求:一个简单的例子 203 6.6.2 POSIX的纤程支持:ucontext 204 6.6.3 纤程切换 206 6.7 思考题 207 6.8 练习答案 208 参考文献 209 第7章 处理器调度 210 7.1 处理器调度机制 210 7.1.1 处理器调度对象 211 7.1.2 处理器调度概览 211 7.2 处理器调度指标 214 7.3 经典调度策略 216 7.3.1 先到先得 216 7.3.2 最短任务优先 218 7.3.3 最短完成时间优先 219 7.3.4 时间片轮转 220 7.3.5 经典调度策略的比较 221 7.4 优先级调度策略 222 7.4.1 高响应比优先 223 7.4.2 多级队列与多级反馈 队列 223 7.4.3 优先级调度策略的比较 229 7.5 公平共享调度策略 229 7.5.1 彩票调度 231 7.5.2 步幅调度 233 7.5.3 份额与优先级的比较 235 7.6 多核处理器调度机制 236 7.6.1 运行队列 236 7.6.2 负载均衡与负载追踪 237 7.6.3 处理器亲和性 238 7.7 案例分析:Linux调度器 239 7.7.1 O(N)调度器 240 7.7.2 O(1)调度器 241 7.7.3 完全公平调度器 242 7.7.4 Linux的细粒度负载 追踪 244 7.7.5 Linux的NUMA感知 调度 245 7.8 思考题 246 7.9 练习答案 247 参考文献 248 第8章 进程间通信 249 8.1 进程间通信基础 250 8.1.1 进程间通信接口 250 8.1.2 一个简单的进程间通信 设计 253 8.1.3 数据传递 255 8.1.4 通知机制 257 8.1.5 单向和双向 257 8.1.6 同步和异步 258 8.1.7 超时机制 259 8.1.8 通信连接 260 8.1.9 权限检查 261 8.1.10 命名服务 262 8.1.11 总结 263 8.2 文件接口IPC:管道 264 8.2.1 Linux管道使用案例 265 8.2.2 Linux中管道进程间通信的实现 267 8.2.3 命名管道和匿名管道 269 8.3 内存接口IPC:共享内存 270 8.3.1 共享内存 270 8.3.2 基于共享内存的进程间 通信 272 8.4 消息接口IPC:消息队列 273 8.4.1 消息队列的结构 274 8.4.2 基本操作 274 8.5 案例分析:L4微内核的IPC 优化 275 8.5.1 L4消息传递 275 8.5.2 L4控制流转移 277 8.5.3 L4通信连接 279 8.5.4 L4通信控制(权限 检查) 279 8.6 案例分析:LRPC的迁移线程 模型 280 8.6.1 迁移线程模型 281 8.6.2 LRPC设计 281 8.7 案例分析:ChCore进程间 通信机制 283 8.8 案例分析:Binder IPC 285 8.8.1 总览 286 8.8.2 Binder IPC内核 设计 286 8.8.3 匿名共享内存 290 8.9 思考题 291 8.10 练习答案 292 参考文献 292 第9章 并发与同步 294 9.1 同步场景 295 9.1.1 一个例子:多线程 计数器 295 9.1.2 同步的典型场景 297 9.2 同步原语 299 9.2.1 互斥锁 300 9.2.2 读写锁 302 9.2.3 条件变量 304 9.2.4 信号量 313 9.2.5 同步原语的比较 316 9.3 死锁 318 9.3.1 死锁的定义 318 9.3.2 死锁检测与恢复 320 9.3.3 死锁预防 321 9.3.4 死锁避免 322 9.3.5 哲学家问题 325 9.4 活锁 326 9.5 思考题 327 9.6 练习答案 330 参考文献 335 第10章 同步原语的实现 336 10.1 互斥锁的实现 336 10.1.1 临界区问题 336 10.1.2 硬件实现:关闭中断 337 10.1.3 软件实现:皮特森 算法 337 10.1.4 软硬件协同:使用原子 操作实现互斥锁 340 10.2 条件变量的实现 345 10.3 信号量的实现 346 10.3.1 非阻塞信号量 347 10.3.2 阻塞信号量 348 10.4 读写锁的实现 352 10.4.1 偏向读者的读写锁 353 10.4.2 偏向写者的读写锁 354 10.5 案例分析:Linux中的futex 356 10.6 案例分析:微内核中的同步 原语 360 10.7 思考题 361 10.8 练习答案 364 参考文献 364 第11章 文件系统 366 11.1 基于inode的文件系统 367 11.1.1 一个不用inode的简单 文件系统 367 11.1.2 inode与文件 368 11.1.3 多级inode 370 11.1.4 文件名与目录 374 11.1.5 存储布局 377 11.1.6 从文件名到链接 378 11.1.7 符号链接(软链接) 381 11.2 基于表的文件系统 382 11.2.1 FAT文件系统 382 11.2.2 NTFS 386 11.3 虚拟文件系统 392 11.3.1 文件系统的内存结构 392 11.3.2 面向文件系统的接口 394 11.3.3 多文件系统的组织和 管理 398 11.3.4 伪文件系统 400 11.4 VFS与缓存 402 11.4.1 访问粒度不一致问题和 一些优化 402 11.4.2 读缓存 403 11.4.3 写缓冲区与写合并 403 11.4.4 页缓存 403 11.4.5 直接I/O和缓存I/O 404 11.4.6 内存映射 405 11.5 用户态文件系统 405 11.5.1 为什么需要用户态文件系统 406 11.5.2 FUSE 406 11.5.3 ChCore的文件系统 架构 407 11.6 思考题 410 11.7 练习答案 411 参考文献 412 第12章 文件系统崩溃一致性 414 12.1 崩溃一致性 415 12.2 同步写入与文件系统一致性 检查 417 12.2.1 同步写入 417 12.2.2 文件系统一致性检查 418 12.2.3 fsck的局限和问题 420 12.3 原子更新技术:日志 421 12.3.1 日志机制的原理 421 12.3.2 日志的批量化与合并 优化 423 12.3.3 日志应用实例:JBD2 423 12.3.4 讨论和小结 427 12.4 原子更新技术:写时拷贝 427 12.4.1 写时拷贝的原理 428 12.4.2 写时拷贝在文件系统 中的应用 429 12.4.3 写时拷贝的问题与 优化 430 12.4.4 讨论和小结 430 12.5 Soft updates 431 12.5.1 Soft updates的三条 规则 432 12.5.2 依赖追踪 434 12.5.3 撤销和重做 435 12.5.4 文件系统恢复 437 12.5.5 讨论和小结 437 12.6 案例分析:日志结构文件系统 438 12.6.1 基本概念与空间布局 438 12.6.2 数据访问与操作 439 12.6.3 基于段的空间管理 441 12.6.4 检查点和前滚 444 12.6.5 小结 446 12.7 思考题 446 参考文献 447 第13章 设备管理 449 13.1 硬件设备基础 450 13.1.1 总线互联 451 13.1.2 设备的硬件接口 452 13.1.3 几种常见的设备 452 13.2 设备发现与交互 457 13.2.1 CPU与设备的交互方式概览 458 13.2.2 设备发现 460 13.2.3 设备寄存器的访问 463 13.2.4 中断 466 13.2.5 直接内存访问 470 13.3 设备管理的共性功能 475 13.3.1 设备的文件抽象 475 13.3.2 设备的逻辑分类 477 13.3.3 设备的缓冲区管理 478 13.3.4 设备的使用接口 482 13.4 应用I/O框架 484 13.4.1 应用层I/O库 484 13.4.2 用户态I/O 486 13.5 案例分析:Android操作系统的 硬件抽象层 488 13.6 思考题 490 13.7 练习答案 491 参考文献 491 第14章 系统虚拟化 493 14.1 系统虚拟化技术概述 494 14.1.1 系统虚拟化及其组成 部分 494 14.1.2 虚拟机监控器的类型 495 14.2 “下陷-模拟”方法 496 14.2.1 版本零:用进程模拟 虚拟机内核态 497 14.2.2 版本一:模拟时钟 中断 498 14.2.3 版本二:模拟用户态与 系统调用 500 14.2.4 版本三:虚拟机内支持 多个用户态线程 501 14.2.5 版本四:用线程模拟 多个vCPU 502 14.2.6 小结 504 14.3 CPU虚拟化 505 14.3.1 可虚拟化架构与不可 虚拟化架构 505 14.3.2 解释执行 506 14.3.3 动态二进制翻译 507 14.3.4 扫描-翻译 508 14.3.5 半虚拟化技术 509 14.3.6 硬件虚拟化技术 509 14.3.7 小结 512 14.4 内存虚拟化 513 14.4.1 影子页表机制 514 14.4.2 直接页表映射机制 517 14.4.3 两阶段地址翻译机制 518 14.4.4 换页和气球机制 521 14.4.5 小结 523 14.5 I/O虚拟化 523 14.5.1 软件模拟方法 524 14.5.2 半虚拟化方法 526 14.5.3 设备直通方法:IOMMU 和SR-IOV 528 14.5.4 小结 531 14.6 中断虚拟化 532 14.7 案例分析:QEMU/KVM 534 14.7.1 KVM API和一个简单的 虚拟机监控器 534 14.7.2 KVM和QEMU 536 14.7.3 KVM内部实现简介 538 14.8 思考题 539 参考文献 540 缩略语 541 在线章节 第二部分 操作系统进阶 第15章 多核与多处理器 第16章 可扩展同步原语 第17章 多场景文件系统 第18章 存储系统 第19章 轻量级虚拟化 第20章 网络与系统 第21章 操作系统安全 第22章 操作系统调测 第23章 形式化证明 第24章 云操作系统 第三部分 ChCore课程实验 实验1:机器启动 实验2:内存管理 实验3:进程与线程、异常处理 实验4:多核、多进程、调度与IPC 实验5:文件系统与shell 实验6:设备驱动与持久化 实验7:进阶实践 |
|