操作系统课程复习
考查目标：
- 掌握操作系统的基本概念、基本原理和基本功能，理解操作系统的整体运行过程。
掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。
能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言或其他高级语言描述相关算法。
以西北工业大学801计算机专业基础为考纲，虽然当时考试未选这门课，但可以以此作为作为学习基础。
一、操作系统概述
1.1 操作系统的概念、特征、功能和提供的服务
1.2 操作系统的发展与分类
1.3 操作系统的运行环境
（内核态与用户态、中断、异常、系统调用）
1.4 操作系统体系结构
二、进程管理
2.1 进程与线程
2.1.1 进程概念、进程的状态与转换、进程控制、进程组织
2.1.2 进程通信
（共享存储、消息传递、、信箱通信、管道通信）
2.1.3 线程概念与多线程模型
2.2 处理机调度
2.2.1 调度的基本概念，调度的基本准则，调度时机、切换与过程、调度方式
2.2.2 典型调度算法
先来先服务、短作业（短进程、短线程）优先、时间片轮转、优先级、最高响应比优先、多级反馈队列调度算法
2.3 进程同步与互斥
2.3.1 进程同步的基本概念
2.3.2 实现临界区互斥的基本方法：软件实现方法、硬件实现方法
2.3.3 信号量、管程
2.3.4 经典同步问题：生产者-消费者问题、读者-写者问题、哲学家进餐问题等
2.4 死锁
2.4.1 死锁的概念、死锁处理策略
2.4.2 死锁预防
2.4.3 死锁避免：系统安全状态、银行家算法
2.4.4 死锁检测和解除
三、内存管理
3.1 内存管理基础
程序执行前需要先放到内存中才能被CPU处理——缓和CPU与硬件之间的速度矛盾。
给内存的存储单元编地址
每个地址对应一个存储单元
| 按字节编址 | 按字编址（设字长16位） |
|---|---|
| 每个存储单元大小为1字节 | 每个存储单元大小为1个字 |
| 1B，即8个二进制位 | 16个二进制位 |
| 字节是寻址的最小单位 | 字长是计算机一次处理数据的最大单位 |
补充知识
指令的工作原理
指令的工作基于‘地址’。每个地址对应一个数据的存储单元。
我们写的代码要翻译成CPU能识别的指令，这些指令会告诉CPU应该去内存的哪个地址读写数据。（所以引入程序装入？）
3.1.1 内存管理概念
内存空间的分配与回收
- 连续分配管理方式
- 非连续分配管理方式
内存空间的扩充
- 覆盖技术（解决“程序大小超过物理内存总和”的问题）
- 交换（对换）技术
- 虚拟存储技术
地址转换
逻辑地址到物理地址的转换（这个过程称为地址重定位，有3种装入方式）应该有操作系统负责，这样就保证了程序员写程序时不需要关注物理内存的实际情况。
存储保护（内存保护），保证各进程在各自存储空间内运行，互不干扰
内存保护可采取两种方法：
- 方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
- 方法二：采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。
3.1.2 程序装入与链接、逻辑地址与物理地址空间、内存保护
- 装入的三种方式
| 方式 | 内容 | 特点 | 区别 |
|---|---|---|---|
| 绝对装入 | 在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存。 | 只适用于单道程序环境 | 程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。通常情况下都是编译或汇编时再转换为绝对地址。 |
| 静态重定位（可重定位装入） | 编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的） | 在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。 用于早期的多道批处理操作系统 |
作业一旦进入内存后，在运行期间就不能移动，也不能再申请内存空间。 |
| 动态重定位（动态运行时装入） | 编译、链接后的装入模块的地址都是从0开始的。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。 | 需要一个重定位寄存器的支持，用来装入模块存放的起始位置。 现代操作系统 |
允许程序在内存中发生移动。并且可将程序分配到不连续的存储区中；在程序运行前只需装入它的部分代码即可投入运行，然后在程序运行期间，可动态申请分配内存；便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间 |
编译
由编译程序将用户源代码编译成若干个目标模块（将高级语言翻译为机器语言）
链接
由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块
装入（装载）
由装入程序将装入模块装入内存运行
链接的三种方式
| 方式 | 内容 |
|---|---|
| 静态链接 | 在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不在拆开 |
| 装入时动态链接将 | 将各目标模块装入内存时，边装入边链接。（在内存中连续吗？） |
| 运行时动态链接 | 在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。（如何共享？） |
3.1.3 交换与覆盖
覆盖技术（解决“程序大小超过物理内存总和”的问题）
思想：将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。
内存中分为一个“固定区”和若干个“覆盖区”。
需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）；不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。
按照自身逻辑结构，让那些不可能同时被访问的程序段共享同一个覆盖区。必须由程序员声明覆盖结构，操作系统完成西大覆盖。缺点：对用户不透明，增加了用户编程复旦。覆盖技术只用于早期的操所系统。
交换（对换）技术
思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）
中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。
暂时换出外存等待的进程状态为挂起状态（Suspend），挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。
应该在外存（磁盘）的什么位置保存被换出的进程？具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式；对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）。总之，对换区的I/O速度比文件区的更快。
什么时候应该交换？交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程：如果缺页率明显下降，就可以暂停换出。
应该换出哪些进程？可优先换出阻塞进程；可换出优先级低的进程：为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间。（注意：PCB会常驻内存，不会被换出外存）
3.1.4 连续分配管理方式
连续分配：指为用户进程分配的必须是一个连续的内存空间。
单一连续分配
固定分区分配
动态分区分配
动态分区分配算法
- 首次适应算法（First Fit）
- 最佳适应算法（Best Fit）
- 最坏适应算法（Worst Fit）
- 邻近适应算法（Next Fit）
3.1.5 非连续（离散）分配管理方式
分页管理方式、分段管理方式、段页式管理方式
- 基本分页存储管理的基本概念
- 基本分段存储管理
- 段页式存储管理
3.2 虚拟内存管理
3.2.1 虚拟内存基本概念
3.2.2 请求分页管理方式
3.2.3 页面置换算法
最佳置换算法（OPT）、先进先出置换算法（FIFO）、最近最少使用置换算法（LRU）、时钟置换算法（CLOCK）等
3.2.4 页面分配策略
3.2.5 工作集、抖动
四、文件管理
4.1 文件系统基础
4.1.1 文件概念、文件的逻辑结构
4.1.2 文件的结构：顺序文件、索引文件、索引顺序文件
4.1.3 目录结构：文件控制块和索引节点，单级、两级和树形目录结构，图形目录结构
4.1.4 文件共享
4.1.5 文件保护：访问类型、访问控制
4.2 文件系统实现
4.2.1 文件系统层次结构
4.2.2 目录实现
4.2.3 文件实现
4.3 磁盘组织与管理
4.3.1 磁盘的结构
4.3.2 磁盘调度算法
先来先服务（FCFS）、最短寻道时间优先（SSTF）、电梯算法（SCAN）
4.3.3.磁盘的管理
五、输入输出（I/O）管理
5.1 I/O管理概述
5.1.1 I/O控制方式
5.1.2 I/O软件层次结构
5.2 I/O核心子系统
5.2.1 I/O调度概念
5.2.2 出错处理
5.2.3 高速缓存与缓冲区
5.2.4 假脱机技术（SPOOLing）
5.3 设备分配与回收
六、参考书目
《计算机操作系统》汤子瀛等主编 西安电子科技大学出版社；
《操作系统教程》徐甲同、陆丽娜等编 西安电子科技大学出版社。
