操作系统引论
操作系统的目标
- 方便性
- 有效性
- 可扩充性
- 开放性
操作系统的作用
作为用户与计算机硬件系统之间的接口
- 命令接口
- 程序接口（系统调用）
- 图形接口
作为计算机系统资源的管理者
- 处理机
- 存储器
- I/O 设备
- 文件（数据和程序）
实现了对计算机资源的抽象
- 扩充机器
推动操作系统发展的主要动力
- 不断提高计算机资源利用率
- 方便用户
- 器件的不断更新迭代
- 计算机体系结构的不断发展
- 不断提出新的应用需求（嵌入式等）
操作系统的发展过程
未配置操作系统的计算机系统
人工操作方式
- 串行
- 用户独占全机
- CPU 等待人工操作
- 人机矛盾
脱机输入 / 输出（Off-Line I/O）方式
并行
假脱机
优势
- 减少了 CPU 的空闲时间（外围机）
- 提高了 I/O 速度（高速磁带）
单道批处理系统
处理过程
- 监督程序
特点
- 自动
- 顺序
- 单道
缺点
- 系统中的资源得不到充分利用
多道批处理系统（Multiprogrammed Batch Processing System）
基本概念
- 后备队列
- 就绪队列
- 作业调度程序
- 调度算法
特点
- 多道
- 无序
- 调度
优缺点
- 资源利用率高
- 系统吞吐量大
- 平均周转时间长
- 无交互能力
解决问题
- 处理机争用问题
- 内存分配和保护问题
- I/O 设备分配问题
- 文件的组织和管理问题
- 作业管理问题
- 用户与系统的接口问题
引入操作系统定义
应在计算机系统中增加一组软件，用以对上述问题进行妥善、有效的处理。
这组软件应包括
- 能有效地组织和管理四大资源地软件
- 合理地对各类作业进行调度和控制它们运行的软件
- 方便用户使用计算机的软件
操作系统是一组能有效地组织和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。
分时系统
引入
- 人——机交互
- 共享主机
- 分时系统是指：在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互的方式使用计算机，共享主机中的资源。
问题
及时接收
- 多路卡
- 终端缓冲区
及时处理
- 作业直接进入内存
- 轮转运行
特征
- 多路性
- 独立性
- 及时性
- 交互性
实时系统
指系统能及时相应外部事件的请求，在规定时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。
类型
- 工业（武器）控制系统
- 信息查询系统
- 多媒体系统
- 嵌入式系统
实时任务的类型
- 周期性实时任务和非周期性实时任务
- 硬实时任务（HRT）和软实时任务（SRT）
与分时系统特征的比较
- 多路性
- 独立性
- 及时性
- 交互性
- 可靠性
微机操作系统的发展
- 单用户单任务 OS
- 单用户多任务 OS
- 多用户多任务 OS
操作系统的基本特征
并发
- 多个进程之间可以并发执行和交换信息
共享
- 互斥共享
- 同时访问
虚拟
时分复用技术
- 虚拟处理机技术
- 虚拟设备技术
- 多道程序技术
空分复用技术
虚拟存储技术
- 逻辑上扩大存储容量
- 单纯的空分复用存储器只能提高内存的利用率
异步
- 不可预知
- 进程同步机制
操作系统的主要功能
处理机管理功能
- 进程控制
- 进程同步
- 进程通信
- 调度
存储器管理功能
- 内存分配
- 内存保护
- 地址映射
- 内存扩充
设备管理功能
- 缓冲管理
- 设备分配
- 设备处理
文件管理功能
- 文件存储空间的管理
- 目录管理
- 文件的读 / 写管理和保护
OS 与用户之间的接口
用户接口
- 联机用户接口
- 脱机用户接口
- 图形用户接口
程序接口
现代 OS 的新功能
系统安全
- 认证技术
- 密码技术
- 访问控制技术
- 反病毒技术
网络的功能和服务
- 网络通信
- 资源管理
- 应用互操作
支持多媒体
- 接纳控制功能
- 实时调度
- 多媒体文件的存储
OS 结构设计
传统 OS 结构
- 无结构 OS
- 模块化结构 OS
- 分层式 OS
C/S 模式简介
- 由来、组成和类型
- 交互
- 优点
OOP 技术简介
- 基本概念
- 优点
微内核 OS 结构
基本概念
足够小的内核
基于 C/S 模式
- 消息传递
应用“机制与策略分离”原理
采用 OO 技术
基本功能
- 进程（线程）管理
- 低级存储器管理
- 中断和陷入处理
优点
- 提高了系统的可扩展性
- 增强了系统的可靠性
- 可移植性强
- 提供了对分布式系统的支持
- 融入了 OO 技术
存在的问题
效率降低
- 可以重新把一些常用的 OS 基本功能有服务器移入微内核中
进程的描述与控制
程序执行
程序顺序执行
- 顺序性
- 封闭性
- 可再现性
程序并发执行
- 间断性
- 失去封闭性
- 不可再现性
进程的描述
定义
引入
- 为了使程序并发执行，并且可以对并发执行的程序加以描述和控制
进程实体
程序段
相关的数据段
PCB
- 描述进程的基本状况和活动过程，系统进而控制和管里进程
定义
传统
引入进程实体
- 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
特征
- 动态性
- 并发性
- 独立性
- 异步性
进程的基本状态及转换
进程管理中的数据结构
OS 中用于管理控制的数据结构
PCB
记录了 OS 所需的，用于描述进程的当前情况以及管理进程运行的全部信息，是 OS 中最重要的记录型数据结构。
PCB 的作用是使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。
- 作为独立运行基本单位的标志
- 能实现间断性运行方式
- 提供进程管理所需要的信息
- 提供进程调度所需要的信息
- 实现与其他进程的同步与通信
PCB 中的信息
进程标识符
- 外部标识符
- 内部标识符
处理机状态
- 通用寄存器
- 指令寄存器
- 程序状态字 PSW
- 用户栈指针
进程调度信息
- 进程状态
- 进程优先级
- 进程调度所需的其他信息
- 事件
进程控制信息
- 程序和数据的地址
- 进程同步和通信机制
- 资源清单
- 链接指针
PCB 的组织方式
- 线性方式
- 链接方式
- 索引方式
进程控制
OS 内核
将一些与硬件紧密相关的模块、各种常用设备的驱动程序以及运行频率较高的模块，安排在紧靠硬件的软件层次中，常驻内存。
- 便于对这些软件进行保护，防止遭受其他应用程序的破坏
- 可以提高 OS 的运行效率
功能
支撑功能
中断处理
时钟管理
原语操作
- 原语是由若干条指令组成的、用于完成一定功能的一个过程
资源管理功能
- 进程管理
- 存储器管理
- 设备管理
进程的创建
进程的层次结构、进程图
引起创建进程的事件
- 用户登录
- 作用调度
- 提供服务
- 应用请求
进程的创建
进程的终止
引起进程终止的事件
正常结束
异常结束
- 越界错
- 保护错
- 非法指令
- 特权指令错
- 运行超时
- 等待超时
- 算术运算错
- I/O 故障
外界干预
- 操作员或 OS 干预
- 父进程请求
- 因父进程终止
进程的终止过程
进程的阻塞与唤醒
引起进程阻塞和唤醒的事件
- 向系统请求共享资源失败
- 等待某种操作的完成
- 新数据尚未到达
- 等待新任务的到达
进程阻塞过程
进程唤醒过程
进程的挂起与激活
进程同步
主要任务
- 对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序地执行具有可再现性。
两种形式的制约关系
- 间接相互制约关系
- 直接相互制约关系
临界资源
临界区
- 在每个进程中访问临界资源的代码
- 进入区
临界区
退出区
剩余区
同步机制应遵循的规则
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待
硬件同步机制
- 关中断
- TS
- Swap 指令
信号量（Semaphores）机制
整型信号量
- 为遵循“让权等待”
记录型信号量
AND 型信号量
- 需要多个共享临界资源
信号量集
信号量的应用
- 进程互斥
- 前趋关系
管程机制
信号量需要进程自备同步操作。使得大量的同步操作分散在各个进程中。不仅给系统的管理带来了麻烦，还会因同步操作使用不当而导致系统死锁。
管程的定义
可以利用共享数据结构抽象地表示系统中的共享资源，并将对该共享数据结构实施的特定操作定义为一组过程。
进程对共享资源的申请、释放和其他操作必须通过这组过程，间接地对共享数据结构实现操作。
对于请求访问共享资源的诸多并发进程，可以根据资源的情况接收或阻塞，确保每次仅有一个进程进入管程，执行这组过程，使用共享资源，达到对共享资源所有访问的统一管理，有效地实现进程互斥。
组成
- 管程名称
- 局部于管程的共享数据结构说明
- 对该数据结构进行操作的一组过程
- 对局部于管程的共享数据设置初始值的语句
语言角度的特性
- 模块化
- 抽象数据类型
- 信息掩蔽
和进程的不同
- 公共数据结构
- 进程使由顺序程序执行有关操作，管程主要进行同步操作初始化操作
- 设置进程在于实现系统的并发性，设置管程是解决共享资源的互斥使用问题
- 进程调用管程的过程，管程为被动工作方式
- 管程不能于其调用者并发
- 进程具有动态性，管程则是 OS 中的一个资源管理模块，供进程调用
条件变量
经典进程的同步问题
进程通信
指进程之间的信息交换
互斥与同步
- 效率低
- 通信对用户不透明
- 称为低级进程通信
高级通信工具的特点
- 使用方便
- 高效传送大量数据
高级通信
共享存储器系统
基于共享数据
- 少量数据
- 效率低下
- 属于低级通信
基于共享存储区
- 由进程负责
管道（pipe）通信系统
需提供以下协调能力
- 互斥
- 同步
- 确定对方是否存在
消息传递系统
- 直接通信
- 间接通信
C-S 系统
Socket
- 基于文件型
- 基于网络型
RPC
消息传递通信的实现方式
直接消息传递系统实例
线程的基本概念
引入
引入进程是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量；引入线程则是为了减少程序在并发执行时付出的时空开销，使 OS 具有更好的并发性。
进程的两个基本属性
- 是一个可拥有资源的基本单位
- 是一个可独立调度和分派的基本单位
程序并发执行所需付出的时空开销
- 创建
- 撤销
- 切换
线程——作为调度和分派的基本单位
比较
- 调度的基本单位
- 并发性
- 拥有资源
- 独立性
- 系统开销
- 支持多处理机系统
线程的状态和 TCB
状态
- 执行
- 就绪
- 阻塞
TCB
- 线程标识符
- 一组寄存器：PC、状态寄存器和通用寄存器的内容
- 运行状态
- 优先级
- 线程专有存储区
- 信号屏蔽
- 堆栈指针
多线程 OS 中的进程属性
- 是一个可拥有资源的基本单位
- 多个线程可并发执行，进程有一个或多个线程
- 进程已不再是可执行的实体
线程的实现
内核支持线程（KST）
在内核的支持下运行
调度以线程为单位
优点
- 在多处理机系统中，内核支持调度统一进程中的多个线程并行执行
- 进程中的一个线程阻塞时，内核可以调度该进程中的其他线程占有处理器，或运行其他进程中的线程
- 具有很小的数据结构和堆栈，线程切换开销小
- 内核本身也可以采用多线程技术，以提高系统的执行速度和效率
缺点
- 对于用户线程，切换开销大
用户级线程（ULT）
在用户空间实现，与内核无关
调度仍以进程为单位
优点
- 切换不需要转换到内核空间
- 调度算法可以是进程专用的
- 实现与 OS 平台无关，因为线程管理代码是用户程序的一部分。甚至可以实现在不支持线程机制的 OS 平台 ULT
缺点
- 系统调用的阻塞问题。同一进程的其他线程均阻塞
- 在单纯的 ULT 实现方式中，不能利用多处理机进行多重处理。内核每次分配各一个进程一个 CPU
组合方式
多对一模型
- 开销小
- 阻塞问题
- 多处理机问题
一对一模型
- 阻塞
- 多处理机
- 创建开销大
多对多模型
实现
创建和终止
处理机调度与死锁
处理机调度算法的目标
共同目标
- 资源利用率
- 公平性
- 平衡性
- 策略强制执行
批处理系统
平均周转时间短
- 平均周转时间
- 平均带权周转时间
系统吞吐量高
- 短作业
处理机利用率高
- 大作业
分时系统
- 响应时间快
- 均衡性
实时系统
- 截止时间的保证
- 可预测性
作业调度
批处理系统中的作业
- 作业
- 作业步
- JCB
- 三个阶段和状态
作业调度的主要任务
任务
调度时做出决定
接纳多少个作业
- 取决于多道作业度
接纳哪些作业
- 取决于调度算法
各系统的不同
调度算法
先来先服务（FCFS）调度算法
- 与其他调度算法结合使用
短作业优先（SJF）调度算法
缺点
- 须预知作业的运行时间
- 对长作业不利
- 无法实现人——机交互
- 完全为考虑作业的紧迫程度
优先级调度算法（PSA）
高响应比优先调度算法（HRRN）
- 既考虑作业的等待时间，又考虑运行时间
- Rp = (等待时间 + 要求服务时间) / 要求服务时间
= 响应时间 / 要求服务时间 - SJF、FCFS、长作业折中
- 调度前有系统开销
进程调度
进程调度
任务
- 保存处理机现场信息
- 按某种算法选取进程
- 把处理机分配给进程
机制
方式
非抢占方式
引起调度的因素
- 正在执行的进程完毕或无法继续运行
- 正在执行的进程提出 I/O 请求
- 进程通信或同步中，执行原语操作
实现简单，系统开销小
不适用于分时系统和大多数实时系统
抢占方式
广泛使用
抢占方式复杂，系统开销大
主要原则
- 优先权原则
- 短进程优先原则
- 时间片原则
调度算法
轮转调度算法
优先级调度算法
- 非抢占式和抢占式
- 静态优先级和动态优先级
多队列调度算法
- 多个就绪队列
多级反馈队列（multileved feelback queue）调度算法
- 不必事先知道进程所需的执行时间
- 多级
- 反馈
- 性能
基于公平原则的调度算法
保证调度算法
- 针对进程
公平共享调度算法
- 针对用户
实时调度
基本条件
提供必要的信息
- 就绪时间
- 开始截止时间和完成截止时间
- 处理时间
- 资源要求
- 优先级
系统处理能力强
- 及时处理
采用抢占式调度机制
具有快速切换机制
- 对中断的快速响应能力
- 快速的任务分派能力
调度算法分类
非抢占式
- 非抢占式轮转调度算法
- 非抢占式优先调度算法
抢占式
- 基于时钟中断
- 立即抢占
调度算法
最早截止时间优先（EDF）算法
分抢占式
- 用于非周期实时任务
抢占式
- 用于周期实时任务
最低松弛度优先（LLF）算法
- 松弛度 = 必须完成时间 - 运行时间 - 当前时间
优先级倒置（priority inversion problem）
- 动态优先级继承
死锁
资源问题
死锁起因
定义
必要条件
处理方法
预防死锁
避免死锁
检测死锁
- 死锁的充分条件
解除死锁
存储器管理
程序的装入
绝对装入（Absolute Loading Mode）
- 单道运行
- 逻辑地址与实际地址相同
可重定位装入（Relocation Loading Mode）
- 静态重定位
动态运行时装入（Dynamic Run-time Loading）
- 运行中改变位置
程序的链接
静态链接（Static Linking）方式
装配时
- 对相对地址进行修改
- 变换外部符号引用
装入时动态链接（Load-time Dynamic Linking）
- 便于修改和更新
- 便于实现对目标模块的共享
运行时动态链接（Run-time Dynamic Linking）
- 链接推迟到执行时
连续分配存储器管理方式
单一连续分配
- 单用户、单任务
固定分区分配
划分分区的方法
- 大小相等
- 大小不等
内存分配
- 分区使用表
造成空间浪费。适用于某些控制相同对象的系统
动态分区分配
数据结构
- 空闲分区表
- 或空闲分区链
分配算法
基于顺序搜索的动态分区分配算法
首次适应（FF）算法
- 将空闲分区链以地址递增链接
- 为大作业分配创造了条件
- 外零头，增加查找开销
循环首次适应（NF）算法
- 使空闲分区更均匀
- 缺乏大的空闲分区
最佳适应（BF）算法
- 将空闲分区按容量小到大形成空闲分区链
- 留下许多难以利用的碎片
最坏适应（WF）算法
- 缺乏大的分区
- 产生碎片的可能性小
- 查找效率高
基于索引搜索的动态分区分配算法
快速适应（quick fit）算法
- 容量分类
- 管理所有表
- 无碎片
- 查找效率高
- 分区归还算法复杂，系统开销大
- 空间浪费
伙伴系统（buddy system）
- 可以多次分割和合并
- 时间性能比快速适应差
- 空间性能优于快速适应
Hash 算法
分配操作
动态可重定位分区分配
紧凑
动态重定位
分配算法
- 紧凑功能
对换
分页存储管理方式
分段存储管理方式
虚拟存储器
常规存储管理方式的特征
一次性
- 大作用无法运行
- 无法进一步提高多道程序度
驻留性
- 进程阻塞，长期等待
- 不必要模块
局部性原理
在一段较短的时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。
顺序执行
- 存储单元，空间局限性
过程调用
- 调用深度，运行范围局限
循环结构
- 再次执行，时间局限性
数据结构
- 处理范围局限
虚拟存储器的定义和特征
指具有调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存和外存之和决定，运行速度接近于内存速度，每位成本接近于外存。
多次性
- 多次调入，逻辑上扩充
对换性
- 换进换出，提高利用率
虚拟性
逻辑容量
- 大作业
- 多道程序度
内存利用率
并发程度
- 系统吞吐量
分页请求系统
是在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统
实现方法
离散分配存储管理方式
硬件支持
- 请求分页的页表机制
- 缺页中断机构
- 地址变换机构
请求分页的软件
- 请求调页
- 页面置换
请求分页存储管理方式
硬件支持
请求页表机制
- 状态位 P
- 访问字段 A
- 修改位 M
- 外存地址
缺页中断机构
- 缺页中断在指令执行期间产生和处理中断信号
- 一条指令在执行期间可产生多次缺页中断
地址变换机构
内存分配
最小物理块数
内存分配策略
固定分配局部置换
- 物理块数难以确定
可变分配全局置换
- 易于实现
- 可能影响其他进程
可变分配局部置换
物理块分配算法
- 平均分配
- 按比例分配
- 考虑优先权
调入策略
何时调入页面
- 预调页策略
- 请求调页策略
从何处调入页面
对换区
- 足够对换空间
文件区
- 缺少对换空间
UNIX 方式
- 凡未运行过的页面均从文件区调页
- 运行过的页面和换出的页面均从对换区调页
页面调入过程
缺页率
页面置换算法
最佳（Optimal）置换算法
- 理论上的
FIFO 页面置换算法
最近最久未使用（LRU）置换算法
“向前看”近似将来
硬件支持
- 寄存器
- 栈
最少使用（LFU）置换算法
- 记录时间间隔内的使用
Clock 置换算法
LRU 的近似算法
简单的 Clock 置换算法
- 为每页设置访问位，将内存页面链接成循环队列
- 最近未使用算法或 NRU 算法
改进型 Clock 置换算法
- 增加修改位
页面缓冲算法（PBA）
影响页面换进换出效率的若干因素
- 页面置换算法
- 写回磁盘的频率
- 读入内存的频率
PBA
显著降低了页面换进、换出的频率
可采用较简单的置换策略，如 FIFO，它不需要特殊硬件支持
VAX/VMS OS
- 可变分配局部置换
- 空闲页面链表
- 修改页面链表
访问内存的有效时间
“抖动”与工作集
多道程序度和处理机的利用率
产生“抖动”的原因
工作集
基本概念
定义
- 指在某段时间间隔里，进程实际所要访问页面的集合。
“抖动”的预防方法
采取局部置换策略
- 把“抖动”的影响限制在较小的范围，效果不是很好
把工作集算法融入到处理机调度中
- 调入作业之前，检查每个进程在内存的驻留页面是否足够多
利用“L = S”准则调节缺页率
选择暂停的进程
- 优先级低的
- 不十分重要，但较大的
- 剩余执行时间最多的
输入输出系统
I/O 系统的功能、模型和接口
管理的主要对象
- I/O 设备
- 相应的设备管理器
- I/O 通道
最主要的任务
- 完成用户提出的 I/O 请求
- 提高 I/O 速率
- 提高设备的利用率
- 并能为更高层的进程方便地使用这些设备提供手段
基本功能
隐藏物理设备的细节
- 设备差异
- 需要的命令和参数
与设备的无关性
- 用户使用 I/O 抽象命令、逻辑设备名
- 提高 OS 的可移植性和易适应性
提高处理机和 I/O 设备的利用率
处理机和 I/O 设备并行工作
- 快速响应用户请求，使 I/O 设备运行起来
- 减少 I/O 设备运行时处理机的干预时间
对 I/O 设备进行控制
驱动程序
- 四种控制方式
I/O 软件应屏蔽方式的差异
确保对设备的正确共享
- 独占设备和共享设备
错误处理
- 临时性和持久性
层次结构和模型
I/O 系统接口
I/O 设备和设备控制器
I/O 设备
- 类型
- 设备与设备控制器之间的接口
设备控制器
内存映像 I/O
I/O 通道
中断机构和中断处理程序
- 中断简介
- 中断处理程序
设备驱动程序
概述
处理过程
- 将抽象 I/O 请求转换为具体要求，发送给设备控制器，或相反
对 I/O 设备的控制方式
使用轮询的可编程 I/O 方式（程序 I/O）
- CPU 种无中断机构
使用中断的可编程 I/O 方式
- 数据寄存器
直接存储器（DMA）访问
- 数据块
I/O 通道（IOP）控制方式
- 一组数据块
与设备无关的 I/O 软件
基本概念
与设备无关的软件
- 数据粒度
设备分配
映射实现
用户层的 I/O 软件
系统调用和库函数
假脱机（Spooling）系统
假脱机技术
- 外围控制机
- 联机实现
SPOOLing 的组成
建立在通道技术和多道程序技术的基础上
以高速随机外存（磁盘）为后援存储器
构成
- 输入井和输出井
- 输入缓冲区和输出缓冲区
- 输入进程和输出进程
- 井管理程序
SPOOLing 系统的特点
假脱机打印机系统
守护进程（daemon）
缓冲区管理
磁盘存储器的性能和调度
提高磁盘系统的性能的方式
- 调度算法，减少寻道时间
- 提高 I/O 速度，提高对文件的访问速度
- 冗余技术，提高可靠性
磁盘性能简述
调度算法
先来先服务 FCFS
- 请求进程少时
最短寻道时间优先 SSTF
- 不能保证平均寻道时间最短
扫描（SCAN）算法
- 考虑磁头移动方向
- 避免了“饥饿”现象
- 电梯调度算法
循环扫描（CSCAN）算法
- 减少延迟（越过请求）
NStepSCAN 算法
- 避免“磁臂粘着”现象
FSCAN 算法
文件管理
文件和文件系统
FS 层次结构
对象及其属性
- 文件
- 目录
- 磁盘（磁带）存储空间
对对象操纵和管理的软件集合
文件管理系统的核心部分
- 对文件存储空间的管理
- 对文件目录的管理
- 用于将文件的逻辑地址转换为物理地址的机制
- 对文件读和写的管理
- 对文件的共享和保护等功能
与 FS 有关的软件分为四个层次
- I/O 控制层
- 基本文件系统层
- 基本 I/O 管理程序
- 逻辑文件系统
文件系统接口
- 命令接口
- 程序接口
文件的逻辑结构
逻辑结构类型
是否有结构
有结构文件
- 定长记录
- 变长记录
无结构文件
- 流式文件
组织方式
顺序文件
- 存取效率
- 顺序存储设备
- 查找开销大
- 增删记录
索引文件
索引顺序文件
直接文件和 Hash 文件
文件目录
目录管理要求
- “按名存取”
- 提高对目录的检索速度
- 文件共享
- 允许文件重命名
FCB 和索引结点
文件目录：FCB 的有序集合。目录文件
FCB
索引结点
- 减少目录占用盘块
简单文件目录
- 单级
- 两级
树形文件目录
目录查询技术
文件共享
DAG 目录
- 不能共享新增的内容
利用索引结点（硬链接）
- 删除不便
利用符号链接（Symbolic Linking）（软链接）
- 访问删除文件时，删除符号链
- 会造成多次读盘
- 符号链占用索引结点
文件保护
影响文件安全性的主要因素
采取措施
保护域
访问矩阵
访问矩阵的修改
访问矩阵的实现
访问控制表（Access Control List）
- 按列（对象）划分
访问权限（Capabilities）表
- 按行（域）划分
磁盘存储器管理
对磁盘存储器管理的主要任务和要求
- 有效地利用存储空间
- 提高磁盘的 I/O 速度
- 提高磁盘系统的可靠性
外存的组织形式
连续组织方式
目录
- file
- start
- length
优点
- 顺序访问容易
- 顺序访问速度快
缺点
- 外部碎片
- 事先知道文件长度
- 灵活插入和删除数据
- 动态增长
链接组织方式
优点
- 消除外部碎片
- 插入、删除、修改记录
- 动态增长
隐式链接
目录
- file
- start
- last
缺点
- 随机访问低效
- 可靠性
- 可按簇分配，但增大了内部碎片
显示链接
FAT 表（File Allocation Table）
FAT 技术
NTFS 的文件组织方式
- 簇为单位，块大小的无关性
- 卷为单位，MFT
优点
- 提高了检索速度
- 减少了访问磁盘的次数
缺点
- 不支持高效直接存取
- FAT 需要较大内存
索引组织方式
单级索引组织方式
只将某个文件的盘块号调入内存
将每个文件的盘块号集中放在一起，即索引块（表）
目录
- file
- 索引块号
优点
- 支持直接访问
- 无外部碎片
缺点
- 对于中、小型文件，索引块利用率低
多级索引组织方式
优点
- 避免索引块过多
- 加快了大型文件的查找速度
缺点
- 启动磁盘的次数和级数有关，不利于小文件
增量式索引组织方式
文件存储空间的管理
引入
文件所占盘块
- 文件分配表
可分配存储空间
- 磁盘分配表（Disk Allocation Table）
盘块分配和回收的手段
空闲表法
- 连续分配
- 分配速度高，减少 I/O 频率
- 用于对换空间和较小文件
空闲链表法
- 空闲盘块链
- 空闲盘区链
位示图法
- NTFS
成组链接法
适用于大型文件系统
避免空闲表或空闲链表过长，将其结合
空闲盘块栈
- 文件卷
提高 I/O 速度的途径
改进文件的目录结构以及检索目录的方法，来减少对目录的查找时间
- 索引结点
- 当前目录
- 多级目录
选取好的文件存储结构，以提高对文件的访问速度
- 顺序存储结构
- 索引结构
提高磁盘的 I/O 速度，能将文件中的数据快速地从磁盘传送到内存中，或者相反
磁盘高速缓存
- 减少磁盘的启动次数
提前读
延迟写
优化物理块的分布
虚拟盘
调度算法
RAID
RAID
提高磁盘可靠性的技术
数据一致性控制
事务
检查点
并发控制
重复数据的数据一致性问题
重复文件的一致性
- 查找文件目录，获得其拷贝的索引结点号，修改文件
- 为新文件新建几个拷贝，取代原来的文件拷贝
链接数一致性检查
- 计数器表
小节
提高内存利用率的方法
整体对换（中级调度）
拼接（紧凑）
运行时动态链接
单一连续
分区（多道批处理）
- 分页 / 分段
SPOOLing 的工作原理
提高 I/O 速度的途径
算法
- 作业调度（四种）
- 进程调度（四 - 六种）
- 实时调度（三 - 八种）
- 避免死锁（一种）
- 动态分区分配算法（七种）
- 页面置换算法（六 - 七种）
- 磁盘调度算法（六种）
通过虚拟地址访问内存的优势
- A program can use a contiguous range of virtual addresses to access a large memory buffer that is not contiguous in physical memory.
- A program can use a range of virtual addresses to access a memory buffer that is larger than the available physical memory. As the supply of physical memory becomes small, the memory manager saves pages of physical memory (typically 4 kilobytes in size) to a disk file. Pages of data or code are moved between physical memory and the disk as needed.
- The virtual addresses used by different processes are isolated from each other. The code in one process cannot alter the physical memory that is being used by another process or the operating system.
XMind - Trial Version
