Skip to content

Latest commit

 

History

History
599 lines (528 loc) · 25.5 KB

os-course-outline.md

File metadata and controls

599 lines (528 loc) · 25.5 KB
Raw

教学日历（教学大纲）（48学时）

大纲修定历史：

  • v1
  • v2：2020年10月21日提交给系里的版本；
  • v3: 21 Oct 2020
  • v4: cooperate with 2021-spring labs
  • v5: 2021年秋季学期结束时更新教学内容部分
  • v6: 2022 spring
  • v7: 2022 autumn
  • v8: 2023 spring
  • v9: 2024 spring
  • v10: 2024 autumn

课程组织与基本目的

操作系统是计算机系统中负责管理各种软硬件资源的核心系统软件，掌握操作系统的基本原理及其设计实现技术是研究型大学计算机专业本科毕业生的基本要求。本课程是计算机专业核心课，从系统程序员的视角进行内容组织，强调实践教学以及对计算机软硬件系统的深入理解，教学操作系统以基于C语言的uCore Tutorial kernel、基于Rust语言的rCore Tutorial kernel和RISC-V处理器为实验环境，讲授操作系统的核心概念、基本原理、关键技术和设计实现方法，并介绍当前操作系统领域的研究热点、相关论文和开源项目，帮助学生了解和掌握大型复杂系统软件的分析方法和核心设计思路，并为学生充分利用操作系统功能进行应用软件研究和开发打下扎实的基础。

教学理念（原则/目标）

让同学重视实践和原理的结合，围绕OS的视角，结合编译/组原等，深入地理解计算机软硬件系统。

建议与要求（2023春）

  • 完善 第六讲：增加第四节 实践：虚存管理优化机制
  • 完善 第七讲和第八讲：增加内容：实践：调度算法的设计实现，COW
  • 完善 第九讲：增加内容：按需加载文件（Demand Paging）
  • 完善 第十三讲：改进第一/三节, 第二节选讲
  • 第十讲 线程与协程 <--> 第十一讲 进程间通信
  • 表明哪些是必讲内容，其它的就是选讲内容（即考试不涉及）
  • 提供rCore Tutorial Book v3中的一般问题的答案
  • 改进实验代码注释和文档
  • 改进基本实验：第4章（lab2），直接提供sbrk系统调用的实现，这样简化了mmap/munmap的实现
  • 增加OS实验陷阱系列的文档/视频
  • 在实验中添加基于rCore Tutorial v3 ch9的应用程序编写题目
  • 添加实验中的可选题目

评分

不参加大实验：

  • 期中： 15%， 期末： 50%，实验必做题目：35%
  • 加分项：做实验中可选题目（只选做一道题即可，多做不算）：加0~7分，总分能不超过100

参加大实验：

  • 实验必做题目（5周完成）:35%, 大实验：65% （代替期中/期末考试）

教学内容

下面的每一讲大约是三个课时左右

1. 操作系统概述

知识点：操作系统的定义、操作系统结构、Linux的基本使用、Linux C应用编程、rCore Tutorial应用编程
基本内容
  1. 课程概述&教学安排
  2. 什么是操作系统 定义/分类/抽象/特征
  3. 操作系统历史演化
  4. 操作系统结构
  5. 实践：UNIX/Linux/rCore类应用
核心学习成效
  1. 掌握操作系统的定义：能从软件角度、资源管理角度定义操作系统及其所属范围
  2. 掌握操作系统的抽象：理解进程、文件、地址空间的抽象对象以及与硬件关系
  3. 掌握操作系统的特征：理解并发/并行、共享、虚拟化、异步的含义
  4. 掌握操作系统的历史：理解单用户系统、批处理系统、多道程序系统、分时系统、个人计算机、SMP系统、VMM系统、分布式系统中的操作系统特征
  5. 掌握操作系统的架构：理解简单单体/分层单体/复杂单体/微/外/VMM kernel的特点
  6. 掌握 计算机硬件与操作系统的关系：理解硬件与操作系统之间的interface和各自的主要工作
  7. 掌握 应用与操作系统的关系：理解应用与操作系统之间的interface和各自的主要工作
能力检测方法
  1. 能分析硬件的哪些功能能够给操作系统提供哪些支持
  2. 能对一个计算机系统中的软硬件的特征、区别、关系、运行状态进行清晰判断
  3. 对操作系统有一个完整的总体分析
  4. 能编写/运行基本的UNIX类程序
  5. 能在Linux环境下进行操作和编程
  6. 能够完成 rt-v3::ch0的相关练习

2. 实践与实验介绍

知识点：计算机系统加电启动过程；编译与OS的关系；实验环境
基本内容
  1. 实践与实验简要分析（站在应用/OS的角度理解rt-v3）
    1. 库级支持
    2. 批处理支持
    3. 多道程序与分时多任务
    4. 支持地址空间
    5. 支持文件系统
    6. 支持进程间通信
    7. 并发支持
    8. 管理I/O设备
  2. Compiler与OS
    1. 通用的编译
  3. 硬件启动与软件启动
  4. 实践：裸机程序 -- LibOS
    1. 基本环境搭建
    2. RV基本组成
    3. QEMU模拟器
    4. QEMU启动
    5. 程序内存布局
    6. 编译流程
核心学习成效
  1. 理解操作系统实验设计的基本思路
  2. 理解操作系统提供的实验要达到的基本目标
  3. 理解函数调用的设计与执行细节
  4. 理解编译器与操作系统的共识
  5. 理解硬件与操作系统的共识
  6. 理解计算机加电后硬件和软件的启动过程
  7. 理解程序的执行过程
  8. 了解RV的SBI
  9. 了解当前的OS各部分的联系与交互
能力检测方法
  1. 能够搭建实验环境
  2. 能够Debug OS实例
  3. 能编写裸机程序
  4. 灵活应用目前掌握的操作系统知识解决裸机编程相关问题（功能、性能、安全性、便捷性等）
  5. 能够描述/分析 rt-v3::ch1的LibOS设计思路和实现的成效
  6. 能够完成 rt-v3::ch1的相关练习

3. 基于特权级的隔离与批处理

知识点：计算机的特权级/系统调用/异常、RV的特权级/系统调用/异常、批处理
基本内容
  1. 从 OS 角度看计算机系统
  2. 从 OS 角度看RISC-V
  3. 实践：批处理操作系统
    1. 应用程序设计
    2. 加载应用程序
    3. 特权级切换
核心学习成效
  1. 理解特权级
  2. 理解软件如何面向特权级进行编程
  3. 理解系统调用的概念、设计与实现、执行过程
  4. 理解批处理操作系统的设计与实现
  5. 理解程序/批处理操作系统的执行过程
  6. 了解当前的OS各部分的联系与交互
能力检测方法
  1. 描述基于RV硬件/和软件协调实现系统调用
  2. 分析RV中的异常与系统调用之间的关系
  3. 分析并编程举例如果不遵守特权级约束会产生的后果：异常
  4. 灵活应用目前掌握的操作系统知识解决批处理/特权级相关问题（功能、性能、安全性、便捷性等）
  5. 能够描述/分析 rt-v3::ch2的Batch OS设计思路和实现的成效
  6. 能够完成 rt-v3::ch2的相关练习

4. 多道程序与分时多任务

知识点：中断、上下文、任务/中断上下文、任务/中断上下文切换、任务/中断上下文切换的时机、任务生命周期、任务执行过程
基本内容
  1. 相关背景与基本概念
    1. 多道程序概念
    2. 分时多任务概念
    3. 协作式调度
    4. 抢占式调度
    5. 中断处理
  2. 实践：多道程序与分时多任务操作系统
    1. 上下文切换
    2. 协作式调度
    3. 中断机制
    4. 抢占式调度
核心学习成效
  1. 从开发者/应用/操作系统的角度来理解：什么是任务（进程的初级阶段）
  2. 理解任务生命周期的状态转换关系和时机
  3. 理解任务切换的概念与任务切换的设计实现之间的关系和差异
  4. 理解中断和异常的区别和关系
  5. 了解当前的OS各部分的联系与交互
能力检测方法
  1. 灵活应用目前掌握的操作系统知识解决多道程序/分时多任务/任务切换相关问题（功能、性能、安全性、便捷性等）
  2. 能够描述/分析 rt-v3::ch3的Multiprog OS和TimeSharing OS设计思路和实现的成效
  3. 能够完成 rt-v3::ch3的相关练习
  4. 能够完成实验一

5. 地址空间-物理内存管理

知识点：内存管理、连续物理内存分配、非连续物理内存分配
基本内容
  1. 地址空间
  2. 计算机体系结构和内存层次
  3. 内存分配
    1. 静态内存分配
    2. 动态内存分配
    3. 连续内存分配
    4. 非连续内存分配
      1. 段式存储管理
      2. 页式存储管理
      3. 段页式存储管理
  4. 实践：建立地址空间的操作系统
    1. 管理sv39多级页表
    2. 内核与应用的地址空间
    3. 基于地址空间的分时多任务
  5. 页表自映射（option）
核心学习成效
  1. 理解地址空间的概念
  2. 理解静态内存分配与动态内存分配的区别与关系
  3. 理解连续内存分配与不连续内存分配的区别与关系
  4. 理解段式存储管理的基本设计管理
  5. 理解页式存储管理的基本设计、多级页表、反置页表
  6. 基于RV，理解软硬件协同实现页式存储
  7. 了解当前的OS各部分的联系与交互
能力检测方法
  1. 能描述虚拟内存、地址空间在概念和设计实现上的联系和差异
  2. 能从不同角度（应用、内核、CPU）理解地址空间
  3. 掌握不同的内存分配策略，并灵活应用
  4. 能灵活掌握基于某种硬件页机制，设计页表，并掌握虚拟地址到物理地址的转换过程
  5. 能够描述/分析 rt-v3::ch4的Address OS设计思路和实现的成效
  6. 能够完成 rt-v3::ch4的页表/物理内存管理相关练习
  7. 能够完成实验二

6. 地址空间-虚拟存储管理

知识点：局部性原理、虚拟存储基本概念、Page Fault异常、局部页面置换算法、全局页面置换算法、Belady异常
基本内容
  1. 虚拟存储的基本概念
    1. 局部性原理
    2. 覆盖和交换
    3. 虚拟页式存储
    4. RISC-V 缺页异常
  2. 页面置换算法的概念
  3. 局部页面置换算法
    1. 最优算法、先进先出算法和最近最久未使用算法
    2. 时钟置换算法和最不常用算法
    3. Belady现象和局部置换算法比较
  4. 全局页面置换算法
    1. 工作集置换算法
    2. 缺页率置换算法
  5. 实践：基于虚存的优化
    1. 再理解Page Fault异常
    2. 惰性页面分配（Lazy page allocation）
    3. 相同页面共享（Same page sharing）
    4. 页面置换算法在OS中的具体实现
核心学习成效
  1. 理解虚拟存储的基本概念和目标
  2. 掌握如何结合Page Fault异常来设计实现虚拟存储
  3. 掌握各种局部页面置换算法和全局页面置换算法
  4. 理解Belady异常，以及Belady异常与页面置换算法的关系
能力检测方法
  1. 掌握局部性原理
  2. 采用覆盖技术管理应用在有限内存上的内存配置
  3. 采用交互技术管理应用换入换出
  4. 理解虚拟存储在RV上如何实现，以及虚拟存储部分涉及到的OS基本运行过程
  5. 能够使用局部页面置换算法和全局页面置换算法来分析缺页次数等
  6. 掌握Page Fault异常出现后的软硬件协同处理过程
  7. 了解基于虚存优化的各种机制
  8. 灵活应用目前掌握的操作系统知识解决虚拟存储相关问题（功能、性能、安全性、便捷性等）
  9. 能够完成 rt-v3::ch4的Page Fault/虚拟内存管理相关练习

7. 进程管理与单处理器调度

知识点：进程概念、进程运行状态、进程的管理、基本调度策略/算法
基本内容
  1. 进程管理
  2. 单处理机调度
    1. 处理机调度概念
    2. 调度准则
    3. 调度算法
  3. 实时调度
    1. 实时任务
    2. 实时调度算法
    3. 优先级反置问题与解决方法
  4. 实践：进程管理
    1. 应用示例
    2. 进程的数据结构
    3. 进程管理机制的实现
    4. 介绍Copy-on-Write技术
核心学习成效
  1. 理解进程管理的核心系统调用 fork, exec, exit, waitpid
  2. 理解进程管理的核心数据结构和大致处理过程
  3. 理解处理器调度各种调度算法
  4. 理解实时调度算法
  5. 理解优先级反转问题和相应的解决方法
  6. 了解当前的OS各部分的联系与交互
  7. 掌握Copy-on-Write技术
能力检测方法
  1. 掌握进程管理的核心系统调用 fork, exec, waitpid, wait
  2. 能运用调度算法来分配处理器时间
  3. 灵活应用目前掌握的操作系统知识解决进程管理相关问题（功能、性能、安全性、便捷性等）
  4. 能够描述/分析 rt-v3::ch5的Process OS设计思路和实现的成效
  5. 能够完成rt-v3::ch5的进程管理相关练习
  6. 能够完成实验三

8. 多处理器调度

知识点：多处理器调度策略/算法
基本内容
  1. 对称多处理与多核架构
  2. 多处理器调度策略
  3. 多处理器调度机制
  4. O(1) 调度（option）
  5. CFS调度（option）
  6. BFS调度算法（option）
  7. 实践：单处理器调度的实现
    1. 应用示例
    2. 调度相关数据结构
    3. 调度机制的具体实现
核心学习成效
  1. 理解对称多处理与多核架构
  2. 理解操作系统如何管理对称多处理与多核架构
  3. 掌握多处理器调度与其中的负载迁移技术
  4. 能够完成rt-v3::ch5的进程管理相关练习
  5. 能够完成实验三
能力检测方法
  1. 理解多核架构对软件的影响（好的方面，不好的方面）
  2. 能运用多核调度算法来分配处理器时间
  3. 了解RV硬件的多核启动过程和软件初始化过程

9. 文件系统

知识点：文件系统基本概念、文件组织、文件系统设计与实现
基本内容
  1. 文件系统概述
  2. 文件系统接口
  3. 文件系统实现(涉及 VFS，按需加载（Demand loading）等)
  4. 实验：文件系统
    1. easyfs简介
    2. 块设备接口
    3. 块缓冲层
    4. 磁盘布局与管理
    5. 索引节点
    6. 在内核中接入easy-fs
  5. 实例：进程文件系统 procfs（option）
核心学习成效
  1. 从不同的角度（应用、操作系统）理解文件系统
  2. 文件系统的核心系统调用
  3. 典型文件系统的设计实现
  4. 了解文件系统与OS其它部分的联系与交互
  5. 理解按需加载（Demand loading）的虚存与文件系统结合的优化技术
能力检测方法
  1. 掌握文件系统的基本概念
  2. 掌握文件系统的内部机制和组成
  3. 能设计简单的文件系统
  4. 能够描述应用发出文件系统相关系统调用后OS的处理过程
  5. 灵活应用目前掌握的操作系统知识解决文件系统相关问题（功能、性能、安全性、便捷性等）
  6. 能够描述/分析 rt-v3::ch6的Filesystem OS设计思路和实现的成效
  7. 能够完成rt-v3::ch6的相关练习
  8. 能够完成实验四

10. 线程与协程

知识点：线程、协程
基本内容
  1. 线程与协程
    1. 线程
      1. 用户线程、内核线程
    2. 协程
    3. 协程、线程与进程的关系
  2. 实践：线程实现
核心学习成效
  1. 理解进程、线程，协程的概念
  2. 理解进程、线程，协程的区别与联系
能力检测方法
  1. 能够在用户态和内核态设计并实现线程管理
  2. 灵活应用目前掌握的操作系统知识解决线程管理相关问题（功能、性能、安全性、便捷性等）
  3. 能够完成rt-v3::ch8的相关练习

11. 进程间通信

知识点： 信号、管道、消息队列、共享内存、I/O重定向
基本内容
  1. 进程通信概念
  2. 信号
  3. 管道
  4. 消息队列
  5. 共享内存
  6. 实验：进程间通信与I/O重定向
    1. 标准I/O
    2. 管道
    3. 命令行参数与I/O重定向
  7. D-Bus机制（option）
  8. Binder机制（option）
核心学习成效
  1. 理解进程--进程，进程--内核的通信机制和特点
  2. 理解不同IPC机制的特征和大致实现
  3. 掌握I/O重定向
  4. 了解IPC与OS其它部分的联系与交互
能力检测方法
  1. 能描述不同IPC机制的大致实现
  2. 能设计管道机制
  3. 能描述I/O重定向的设计实现思路和运行过程
  4. 灵活应用目前掌握的操作系统知识解决IPC相关问题（功能、性能、安全性、便捷性等）
  5. 能够描述/分析 rt-v3::ch7的IPC OS设计思路和实现的成效
  6. 能够完成rt-v3::ch7的相关练习

12. 同步互斥

知识点：基于软件的同步互斥方法、基于硬件的同步互斥方法、信号量、管程、基于信号量/管程的经典同步问题、死锁、死锁的解决方法、优先级反置与解决方法
基本内容
  1. 同步互斥基本概念
    1. 现实生活中的同步互斥问题
    2. 临界区
    3. 禁用硬件中断
    4. 基于软件的解决方法
  2. 更高级的抽象方法
    1. 信号量
    2. 管程(option)、条件变量
  3. 同步互斥问题
    1. 哲学家就餐问题（信号量/管程）
    2. 读者-写者问题（信号量/管程）
  4. 死锁
    1. 死锁概念
      1. 死锁的必要条件
    2. 死锁处理方法
    3. 银行家算法
    4. 死锁检测
  5. 实践：并发与同步互斥
    1. 锁机制实现
    2. 信号量机制
    3. 条件变量机制
  6. 并发错误检测（option）
  7. 同步互斥-RCU(option)
核心学习成效
  1. 理解同步互斥的基本概念
  2. 掌握各种同步互斥的操作手段
  3. 解决同步互斥问题
  4. 理解死锁概念
  5. 掌握各种死锁处理方法
  6. 理解各种死锁处理方法的局限性
  7. 了解当前的OS各部分的联系与交互
能力检测方法
  1. 能够采用不同的同步互斥手段（基于软件的方法、信号量、条件变量、禁用中断等）灵活解决各种同步互斥问题
  2. 能应用银行家算法
  3. 掌握如何进行死锁检测
  4. 灵活应用目前掌握的操作系统知识解决同步互斥/死锁相关问题（功能、性能、安全性、便捷性等）
  5. 能够描述/分析 rt-v3::ch8的SyncMutex OS设计思路和实现的成效
  6. 能够完成rt-v3::ch8的相关练习
  7. 能够完成实验五

13. I/O设备管理

知识点：I/O抽象、I/O特征、DMA/Interrupt/轮询机制、同步I/O、异步I/O
基本内容
  1. 设备概述
  2. 设备抽象
  3. 设备执行模型
  4. 实验：I/O设备管理
    1. 外设平台(option)
    2. 串口驱动(option)
    3. virtio设备驱动(option)
核心学习成效
  1. 理解设备的分类和特点
  2. 理解设备的各种抽象形式
  3. 理解设备执行模型（同步，异步....）
  4. 掌握设备驱动的设计与实现
  5. 掌握OS与外设的交互过程
  6. 了解当前的OS各部分的联系与交互
能力检测方法
  1. 能描述OS与外设的交互过程
  2. 能编写应用程序来与设备进行交互
  3. 能编写简单的设备驱动程序（如uart等）
  4. 灵活应用目前掌握的操作系统知识解决设备相关问题（功能、性能、安全性、便捷性等）
  5. 能够完成rt-v3::ch9的相关练习

14. 扩展主题（可选项：可靠文件系统，多核优化，高级语言支持，请外校专家讲）

知识点： 基于日志的文件系统设计
基本内容

OPTION1:可靠文件系统主题：

  1. 系统可靠性概述
  2. 基于日志的文件系统
  3. 实际文件习题
    1. FAT文件系统（option）
    2. EXT4文件系统（option）
    3. NTFS（option）
    4. Zettabyte File System (ZFS)（option）
    5. 数据库文件系统（option）
核心学习成效

无

能力检测方法

无

教学实验

实验一：操作系统的基本支持

覆盖：1/2/3章

知识点：计算机/OS启动、特权级切换、系统调用、应用程序/库/内核的关系、特权级相关异常、任务切换

用户态
  • 显示目录文件名
    • 实现一个Linux应用程序ls，能显示当前目录中的文件。
  • 显示调用栈
    • 实现一个linux应用程序，能打印出调用栈信息
  • 显示目录信息
  • 睡眠
    • 实现一个rcore应用程序，用sleep系统调用睡眠一段时间（in rcore tutorial v3 Branch 2022spring）
内核态
  • 显示调用栈
    • 实现裸机程序，能打印调用栈
  • 实现新系统调用get_taskinfo
    • 增加get_taskinfo系统调用，能显示task的id和task name
  • 统计系统调用
    • 实现内核扩展，能够统计应用执行过程中系统调用编号和次数
  • 统计时间
    • 实现内核扩展，能够统计应用执行的完成时间
  • 分析异常
    • 统计执行异常的程序的异常情况说明（主要是各种特权级涉及的异常）
    • 能够打印异常程序的调用栈

实验二：地址空间

覆盖：4章

知识点：地址空间、应用与内核之间在不同地址空间的数据交互/控制交互、内存/地址相关异常（如缺页异常）

提供系统调用sbrk 的实现

用户态
  • linux应用访问内存相关系统调用
    • 使用sbrk，mmap,munmap,mprotect系统调用
内核态
  • 改进系统调用sys_get_time
    • 引入虚存机制后，原来内核的 sys_get_time 函数实现就无效了。请你重写这个函数，恢复其正常功能。
  • 实现新系统调用mmap, munmap
    • 请实现 mmap 和 munmap 系统调用
可选题目
  • 惰性页面分配（Lazy page allocation）
  • 局部页面置换算法：改进的Clock页面置换算法
  • 全局页面置换算法：工作集置换策略
  • 全局页面置换算法：缺页率置换策略

实验三：进程管理与调度

覆盖：5章

知识点：进程管理的关联性和必要性、调度算法

用户态
  • 实现一个与进程管理相关的linux应用程序
    • 能用nice,fork,exec,spawn等系统调用
内核态
  • 实现新系统调用 spawn
  • 实现一个调度算法-如：stride
可选题目
  • 相同页面共享（Same page sharing）fork时的Copy on Write
  • 调度算法：可提升/降低优先级的多级反馈队列
  • 多核支持与多核调度（支持进程迁移和多核模式执行应用程序，但在内核中没有抢占和多核支持）

实验四：文件系统与进程间通信

覆盖：6，7章

知识点：文件系统的实现、进程间通信机制

用户态
  • 实现一个应用程序能体现文件/进程间通信的特点
内核态
  • 扩展文件系统功能
    • 扩大单个文件的大小
      • 支持三重间接inode
    • 扩展mmap系统调用，支持对文件的映射
      • 这样对内存读写，其实就是对文件读写
    • 支持crash一致性（hard）
      • 扩展log fs
  • 实现一个文件相关系统调用相关
    • 实现硬链接相关系统调用
    • 实现创建目录的系统调用
  • 实现一个新的重定向能力
    • 实现共享内存
可选题目
  • 按需加载机制
  • log-easyfs：实现基于日志的文件系统

实验五：同步互斥

覆盖：8章

知识点：线程，同步互斥的机制，解决同步互斥问题，死锁，优先级反转问题。

用户态
  • 实现一个Linux线程应用程序能体现线程属性和线程间同步互斥的特点
    • 使用了pthread_* 系统调用
内核态
  • 扩展内核功能：内核线程
    • 在内核中支持内核线程
  • 在内核线程中支持同步互斥机制
    • 实现内核线程用的mutex, semaphore, cond-var
  • 扩展内核功能：多核支持
    • 扩展rcore-tutorial-v3运行在多核系统中
  • 用银行家算法解决死锁问题
    • 设计某种资源申请导致死锁的例子
    • 设计银行家算法来避免死锁问题
  • 解决优先级反转问题
    • 实现RM实时调度算法
    • 设计优先级反转的实例
    • 实现优先级天花板和优先级继承方法
可选题目
  • 内核的协程支持
  • 基于多核的OS内核线程支持，内核支持抢占，支持多核方式下的同步互斥
  • 提升多核的OS内核性能，实现内核中的并行性能优化（fs中的缓冲区管理并行化, 物理内存分配的并行化）
  • 更通用的内核+应用的死锁检查
  • 支持简易网络协议栈和virtio_net device或e1000网卡驱动（需自学rCore Tutorial Book第九章）

扩展实验 （即大实验，课程设计）

前提条件：5周完成实验1~5并通过助教和老师的评审后，可选择完成扩展实验来代替期中和期末考试。

内容和要求：与全国大学生操作系统比赛要求基本一致：跑Linux应用，模块化OS设计（用OS比赛的测例）。