- 操作系统导论
- 操作系统基础
- 进程
- CPU Scheduling
- Synchronization
- Address Translation
- Paging
- Demand Paging
- Linux Memory Management
- IO
- Storage
- File System
Appendix: Quiz
Chapter 1 - 操作系统导论
计算机系统的结构:
- 硬件
- 提供基础计算资源
- CPU, 内存, IO
- 操作系统
- 控制、协调 多应用/多用户 对于硬件的使用
- 应用程序
- 定义系统资源的使用方法，用于解决计算问题
- 用户
- 人、机器、其他计算机…
操作系统:
使计算机正确、高效运行且易于使用的软件集。
A group of software that makes the computer operate correctly and efficiently in an easy-to-use manner.
操作系统包含一个称为内核的程序
- 管理所有物理设备：CPU、RAM、硬盘……
- 提供诸如系统调用的函数
操作系统包含其他的”helper”程序
- 例如shell，提供了命令行用户接口
- 例如GUI，提供了有图标的用户友好的接口
- 例如浏览器，提供网页浏览服务
操作系统是资源管理器
- 管理CPU、内存、硬盘、I/O设备
- 管控公平高效的资源使用，协调资源冲突
操作系统是控制程序
- 控制程序的执行，避免错误或对计算机的不当使用
操作系统都做些什么:
虚拟化 Virtualization
- CPU虚拟化：单个CPU上运行多个程序
- 内存虚拟化：为进程(程序)分配相互独立的虚拟内存地址空间
并发性 Concurrency
- 运行多线程程序，保证其正确运行
持久化 Persistence
- 从RAM写入数据到持久内存
- 性能，崩溃恢复能力
操作系统的历史:
……
进程:
进程(process)是在运行中的程序(program)
- 程序是
进程需要资源来完成任务
- CPU、内存、I/O、文件
- 进程终止，需要回收所有可再利用资源
进程顺序执行指令，一次一个，直到结束
- 单线程进程由PC指定下一条执行的指令位置
- 多线程进程的每个线程都有一个PC
一般而言，计算机系统有多个进程，若干用户，若干操作系统在一个或多个CPU上运行
- 通过在进程/线程之间复用(multiplexing)CPU来实现并发性
进程管理:
创建/删除用户和系统进程
暂停/恢复进程
为进程同步(process synchronization)提供机制
为进程通信(process communication)提供机制
为死锁处理(deadlock handling)提供机制
内存：
动态随机访问内存DRAM
CPU在执行时只和主存交互
- 处理前后数据都在内存里
- 执行的指令都在内存里
操作系统管理内核和进程的主存，哪个进程用哪块内存
内存管理:
内存管理决定，当优化CPU利用率、回应用户时内存中存储什么
内存管理活动
- 记录哪些内存正在被哪些进程使用
- 决定哪些进程和数据要移入/移出内粗
- 按需申请/释放内存空间
存储管理:
操作系统提供信息存储的统一、逻辑的情况
将物理属性抽象为逻辑存储单元：文件
每个介质都由设备控制
可变的性质包括访存速度、容量、数据传输率、访问方法(顺序/随机访问)
文件系统管理
- 文件通常分目录管理
- 访问控制：决定谁能访问什么
- 操作系统活动，包括：
- 创建/删除文件和目录
- 操作文件和目录的原语(primitives)
- 将文件映射到二级存储
- 将文件备份到稳定存储介质
I/O 子系统:
操作系统的一个目的是向用户隐藏硬件设备的特殊性
- 包含I/O的内存管理
- 缓存(buffering)，传输时临时存储数据
- 缓存(caching)，将部分数据放入高速缓存以提高性能
- 通用的设备-驱动接口
- 特殊硬件设备的驱动
保护与安全:
保护：由操作系统定义，控制进程或用户对资源的访问的机制
安全：抵御内外对系统的攻击
操作系统决定哪个用户能做什么
- 用户标识符：用户名，ID
- 将用户ID与该用户的所有文件、进程联系起来，以控制访问
- 组标识符(group ID)允许定义一组用户并管理控制权，与进程、文件相联系
- 特权升级允许用户改变ID以获得更多权利
Chapter 2 - 操作系统基础
双模式操作(Dual-mode Operations):
硬件支持至少两种模式
- 内核模式：运行内核代码
- 用户模式：运行常规程序
为实现双模式操作，硬件提供：
一个
state比特位一些只能在内核模式执行的操作/行为
用户态→内核态，设置系统模式，并保存用户PC
操作系统将用户资源谨慎搁置，执行必要操作
内核态→用户态，清除系统模式，并恢复用户PC
一些例子：
- x86 Ring 0 对应内核态，Ring 3对应应用态
- RISC-V User/Supervisor/Machine 三种模式，应用态-内核态-固件态
三种模式转换的情形:
- 系统调用(system call)
进程请求系统服务
类似函数调用，但在进程外
- 系统函数没有地址可供调用
- 向寄存器写入系统调用ID和参数，执行系统调用
- 中断(interrupt)
- 外部异步事件触发上下文切换(context switch)，如时钟、I/O设备
- 与用户进程独立
- 陷阱(trap)或异常(exception)
- 进程的内部同步事件触发上下文切换，如段错误、除以0…
系统调用:
由操作系统提供的服务的程序接口，以高级语言编写
每个系统调用都会有一个ID，映射关系表由系统调用接口维护
系统调用接口 调用 操作系统内核中对应的系统调用，返回系统调用的状态及返回值
调用者无需了解具体实现，只需要遵守调用规则，理解调用功能即可
大多数操作系统接口的细节通过library API隐藏，对使用者不可见
由运行时支持库（run-time support library, 包含在编译器中的库中的一组功能）管理
系统调用类型:
- 进程控制: fork, exit, wait
- 文件管理: open, read, write, close
- 设备管理: ioctl, read, write
- 信息维护: getpid, alarm, sleep
- 通信: pipe, shmget, mmap
- 保护: chmod, umask, chown
异常和中断:
异常(同步)应对非正常状况
- 将swapped-out页映射回memory内
- 非法内存访问
- 除以0……
中断(异步)抢占正常执行
- 外部设备的通知
- 抢占式调度
- 另一个CPU的通知
处理异常和中断
- 停止执行当前程序
- 执行handler程序
- 处理器通过中断描述符表(Interrupt Descriptor Table, IDT)访问handler
- 每种中断对应一个数字
内核结构:
宏内核:
宏内核(Monolithic Kernel)是一个操作系统软件框架，拥有访问所有I/O设备、内存、硬件中断、CPU栈的权限
宏内核包含很多组件，例如内存子系统、I/O子系统等，通常很大
宏内核是Linux, Unix, MS-DOS的基础
微内核:
微内核(Micro Kernel)将操作系统功能外包给用户进程，灵活性、安全性、容错性增强
用户级服务器收到内核信任(通常以root身份运行)
保护机制保留在内核，资源管理转移到用户级服务器
代表性微内核操作系统：Mach, seL4
优点：
- 内核响应速度更快：内核功能在可抢占的用户级进程种
- 稳定性和安全性提高：操作系统中代码更少
- 更好地支持并发性和分布式操作系统
缺点：
- 需要更多进程间通信(IPC)，带来更多上下文切换，更慢
杂交内核:
杂交内核(Hybrid Kernel)是宏内核和微内核的结合，例：Windows
外内核:
外内核(Exokernel)将抽象与安全分开
- 内核相当小：安全复用(security multiplexing)
- Library OS作为进程运行：操作系统抽象化
优点：
- 直接管理资源，高效
- 易于进行新内核设计的实验
缺点：
- 通常只是个概念
变种：nanokernel, picokernel
虚拟化和管理程序:
管理程序(Hypervisor, virtual machine manager/monitor, VMM)强调虚拟化和隔离
- 操作系统可以在管理程序上几乎不做修改地运行
- 不同虚拟机之间资源隔离
- 微内核和外内核可用于实现管理程序
操作系统设计原则:
不同操作系统内部结构五花八门
- 从设置目标和规格开始
- 收到硬件选择和系统类型的影响
用户目标和系统目标
- 用户目标：易于使用，易于上手，可靠安全高效
- 系统目标：易于设计、实现、维护，灵活可靠无错，高效
操作系统区分开政策和机制
- 政策(Policy)：哪个软件可以在什么时候访问什么资源
- 机制(Mechanism)：政策是如何实现的
- 分离政策和机制提供了灵活性，更换政策后选择对应机制即可
操作系统服务:
用户接口(UI)：几乎所有操作系统都有UI，CLI vs. GUI
程序执行：将程序载入内存并运行，结束执行，无论正常或异常
I/O操作：运行程序可能需要I/O，可能涉及文件操作或I/O设备
文件系统控制：创删读写查文件目录，权限管理
通信：进程间通信，网络通信
错误检测：时刻关注可能的错误，硬件/外设/用户程序…，恰当处理，调试功能
资源分配：多用户/多任务并行，各自分配各类资源(CPU，主存，文件存储)
账户管理：哪些用户使用了哪些计算机资源
保护与安全：多用户/网络计算机系统的权限需要管理，并行进程应互不干扰
系统程序:
为程序开发和执行提供方便的环境，被分为：
- 文件操作：创建、删除、复制、重命名、打印、转存、列表，操纵文件和目录
- 状态信息：日期、可用内存、性能、用户数量、调试信息…(注册表)
- 文件修改：文本编辑器，对文本进行修改
- 编程语言支持：编译器、汇编器、调试器、翻译器
- 程序加载与运行
- 通讯：提供虚拟连接的机制，供进程间、用户间、计算机系统间通信。
- 应用程序
Chapter 3 - 进程
Appendix - Quiz
Which of the following is/are correct about von Neumann architecture?
❌It has better performance than Harvard architecture
- 实际上哈佛架构把指令和数据分开之后，效率相对会高一点
✔️It is a widely used architecture in modern computers
- 确实，相当一部分计算机使用冯诺依曼架构
✔️It use a shared memory for programs and data
- 冯诺依曼架构特色
❌It was first described in 1958
- 冯诺依曼架构的名词提出于1945
Which of the following is/are true about dual-mode operation?
❌The operating system must maintain a global bit to represent the current execution mode
- 这个是CPU维护的
❌Certain operations are not permitted in the kernel mode and will be trapped to the user mode
- 反过来就是对的
✔️Three ways to transit from user to kernel mode: system call, interrupt, and exception
- U→K: 系统调用，中断，异常
❌Dual-mode operations are needed because applications need to be protected from OS
- 反过来就是对的
What are the differences between an interrupt and an exception?
✔️Interrupts are usually asynchronous with the program execution, but exceptions are usually synchronous
- 中断是外部设备接入等与程序运行异步的事件产生的，异常则是于程序运行时同步产生的
❌Interrupts may happen due to an abnormal condition, but exceptions are typically caused by normal conditions
- 异常是对于异常(abnormal)情况的反馈，中断抢占正常执行。
❌Interrupts and exceptions are handled in different ways
- 都是到被捕获后由handler处理，具体不一样
✔️Interrupts include notifications from devices or hardware components (e.g., APIC) but exceptions do not
- 设备/硬件的异步通知造成中断，而不是异常
Which of the followings belong to operating system services?
✔️Error detection and handling
✔️Inter-process communication and networking
❌CPU scheduling
- 虽然CPU调度是进程管理的重要方面，但它并不被视为操作系统提供的独立服务
✔️User interface
Which of the followings is/are true about state transition(s) in a process life cycle?
✔️Waiting->ready upon I/O completion
✔️Ready->running when it is dispatched by the CPU scheduler
❌Waiting->running when return from I/O requests
❌Running->waiting when it has used up its CPU quota and begin to wait until its next turn
Which of the followings is/are true about fork() and exec()?
❌In the parent process, fork() returns 0; in the child process, fork() returns its own pid.
✔️The parent and child process share the same program counter, memory content, and opened files.
✔️Copy-on-write means the address space of the parent and child processes are only copied when updated
❌Calling exec() to load the same program into the memory is equivalent to not calling exec() at all
Which of the followings is/are true about exit() and wait()?
✔️Exit() is always invoked when the process terminates.
❌Exit() sends SIGCHLD to the parent process if the parent process is already waiting by calling wait().
✔️Exit() frees allocated kernel memory and everying on the userspace memory.
✔️A process becomes a zombie process when it is terminated but not yet cleaned up by its parent process.
Which of the following is/are true about user-level and kernel-level thread?
✔️Many-to-many mapping requires thread implementation on both user-level and kernel-level.
❌The benefit of one-to-many mapping is that when a user thread blocks on I/O, it may use other kernel thread to run.
✔️Kernel-level thread is an implementation of the thread abstraction in the OS kernel.
❌With many-to-one mapping, the OS kernel can schedule user threads independently.
Which of the followings is/are true about preemptive scheduling?
✔️If scheduler is invoked when a process switches from running to ready state, it is preemptive scheduling.
❌RR is non-preemptive because the scheduler is not invoked when a process switches from waiting to ready.
❌A scheduler is preemptive if it is invoked when a process switches from waiting to running.
✔️If the running process only gives up the CPU when it terminates or blocks on I/O, the scheduler is non-preemptive.
Which of the following is/are true about race condition and mutual exclusion?
✔️Implementation of critical sections require mutual exclusion, bounded-waiting and progress.
✔️Race condition may happen when two processes concurrently access shared variables.
❌Priority inversion may happen when two processes are synchronized with semaphores.
✔️Peterson’s solution satisfies all the three requirements of critical section implementation.
Which of the following is/are true about semaphores?
❌A binary semaphore could only have two values whereas a counting semaphore could have more than two values.
✔️Semaphores must be implemented in the kernel.
❌When solving producer-consumer problem with semaphores, it is OK to swap the order of wait(&fill) and wait(&mutex).
❌In the correct solution to dining philosopher problem, semaphore is used to model a chopstick.