Ch 1 计算机系统概述
1.1 OS基本概念
概念
- 负责管理协调硬件、软件等计算机资源
- 为上层用户、应用程序提供简易服务
- 是一种系统软件
功能和目标
资源的管理者
- 处理机管理
- 存储器管理
- 文件管理
- 设备管理
向上层提供服务
给普通用户的
GUI
命令接口
- 联机命令接口
- 脱机命令接口
给软件/程序员的
程序接口（系统调用）
是什么？
- os对应用程序/程序员提供的接口
与库函数区别
系统调用实现的功能
设备管理
- 完成设备的 请求/释放/启动 等功能
文件管理
- 完成文件的 读/写/创建/删除 等功能
进程控制
- 完成进程的 创建/撤销/阻塞/唤醒 等功能
进程通信
- 完成进程之间的 消息传递/信号传递 等功能
内存管理
- 完成内存的 分配/回收 等功能
系统调用的过程
- 传参
- 陷入指令/Trap/访管
- 由OS内核程序处理系统调用请求
- 返回应用程序
对硬件机器的扩展
- 扩充机器
特征
并发
共享
- 互斥共享方式
- 同时共享方式
虚拟
- 时分复用技术
- 空分复用技术
异步
1.2 OS发展
手工操作阶段
- 缺点：人机速度矛盾
批处理阶段
单道批处理系统（引入脱机I/O技术）
- 优点：缓解人机速度矛盾
- 缺点：资源利用率依然低
多道批处理系统（OS开始出现）
- 优点：多道程序并发执行，资源利用率高
- 缺点：不提供人机交互功能
分时OS
- 优点：提供人机交互
- 缺点：不能优先处理紧急任务
实时OS
硬实时系统
- 必须在绝对严格的规定时间内完成处理
软实时系统
- 能偶尔接受违反时间规定
优点：能优先处理紧急任务
网络OS
分布式OS
个人计算机OS
1.3 OS运行环境
OS运行机制
两类程序
- 内核程序
- 应用程序
两类指令
- 特权指令
- 非特权指令
两种处理器状态
- 内核态/核心态/管态
- 用户态/目态
内核（内核(Kernel)是OS最重要最核心的部分，由很多内核程序组成）
时钟管理
- 实现计时功能
中断处理
- 负责实现中断机制
原语
- 是一种特殊的程序
- 处于OS最底层，最接近硬件的部分
- 具有原子性——其运行只能一气呵成，不可中断
- 运行时间较短、调用频繁
对系统资源进行管理的功能
- 进程管理
- 存储器管理
- 设备管理
如何变态
内核态–>用户态
- 一条修改PSW的特权指令
用户态–>内核态
- 由中断引起，硬件自动完成
中断和异常
中断的作用
- 让操作系统强行夺回CPU控制权
- 使CPU从用户态变为内核态
中断的分类
内中断（异常/例外）
- 陷阱、陷入（trap）
- 故障（fault）
- 终止（abort）
外中断
- 时钟中断
- I/O请求中断
中断机制的基本原理
检查中断信号
- 内中断：CPU在执行指令时会检查是否有异常发生
- 外中断：每个指令周期末尾，CPU都会检查是否有外部中断信号需要处理
找到相应的中断处理程序
- 通过“中断向量表”实现
1.4 OS体系结构
大内核
- 将OS的主要功能模块都作为系统内核，运行在核心态
- 优点：高性能
- 缺点：内核代码庞大，结构混乱，难以维护
微内核
- 只把最关键的功能保留在内核
- 优点：内核功能少，结构清晰，方便维护
- 缺点：需要频繁地在核心态和用户态之间切换，性能低
Ch 2 进程管理
2.1 进程与线程
进程
概念
- 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
进程实体（进程映像）的组成
PCB
进程描述信息
- 进程标识符PID
- 用户标识符UID
进程控制和管理信息
- CPU、磁盘、网络流量使用情况统计…
- 进程当前状态：就绪态？阻塞态？…
资源分配清单
- 正在使用哪些文件
- 正在使用哪些内存区域
- 正在使用哪些I/O设备
处理机相关信息
- 如PSW、PC等各种寄存器的值（用于实现进程切换）
程序段
- 程序的代码（指令序列）
数据段
- 运行过程中产生的各种数据（如程序中定义的变量）
特征
动态性
- 最基本特征
并发性
独立性
- 进程是独立运行、独立获得资源、独立接受调度的基本单位
异步性
- 各进程以不可预知的速度向前推进，可能导致运行结果的不确定性
结构性
组织方式
链接方式
- 按照进程状态将PCB分为多个队列
- OS持有指向各个队列的指针
索引方式
- 根据进程状态的不同，简历几张索引表
- OS持有指向各个索引表的指针
状态与转换
状态
运行态（Running）
- 占有CPU, 并在CPU上运行
- CPU✅其他所需资源✅
就绪态(Ready)
- 已经具备运行条件，但由于没有空闲CPU, 而暂时不能运行
- CPU❌其他所需资源✅
阻塞态（Waiting/Blocked, 又称等待态）
- CPU❌其他所需资源❌
创建态（New, 又称 新建态）
- 进程正在被创建，OS为进程分配资源、初始化PCB
终止态（Terminated, 又称结束态）
- 进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB
挂起态
- 为减轻系统负载，提高资源利用率，暂时不执行的进程会被调到外存，从而变为“挂起态”
状态间的转换
就绪态➡运行态
- 进程被调度
运行态➡就绪态
- 时间片到
- CPU被其他高优先级的进程抢占
运行态➡阻塞态（主动行为）
- 等待系统分配资源
- 等待某件事件发生
阻塞态➡就绪态（被动行为）
- 资源分配到位
- 等待的事件发生
创建态➡就绪态
- 系统完成创建进程的相关工作
运行态➡终止态
- 进程运行结束
- 运行过程遇到不可修复的错误
进程控制
基本概念
进程控制就是要实现进程状态的转换
进程控制用原语实现
- 原语用关/开中断来实现
- 原语是一种特殊的程序
- 源于的执行必须一气呵成，不可中断
相关原语
进程的创建
创建原语
- 申请空白PCB
- 为进程分配所需资源
- 初始化PCB
- 将PCB插入就绪队列
引起进程创建的事件
用户登录
- 分时系统中，用户登陆成功，系统会为其建立一个新的进程
作业调度
- 多道批处理系统中，有的信作业放入内存是，会为其建立一个新的进程
提供服务
- 用户向OS提出某些请求时，会建立一个进程处理该请求
应用请求
- 由用户进程主动请求创建一个子进程
进程的终止
撤销原语
- 从PCB中找到终止进程的PCB
- 若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
- 终止其所有子进程
- 将该进程拥有的所有资源归还给父进程或OS
- 删除PCB
引起进程终止的事件
正常结束
- 进程自己请求终止（exit系统调用）
异常结束
- 整数除以0，非法使用特权指令，然后被OS强行杀掉
外界干预
- Ctrl+Alt+delete, 用户选择杀掉进程
进程的阻塞
阻塞原语
- 找到要阻塞进程的PCB
- 保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
- 将PCB插入阻塞队列
引起进程阻塞的事件
- 需要等待系统分配某种资源
- 需要相互合作的其他进程完成工作
进程的唤醒
唤醒原语
- 在等待队列中找到PCB
- 将PCB从等待队列中移除，设置进程状态为就绪态
- 将PCB插入就绪队列，等待被调度
引起进程唤醒的事件
- 等待事件的发生
进程的切换
切换原语
- 将运行环境信息存入PCB
- PCB移入相应队列
- 选择另一个进程执行，并更新其PCB
- 根据PCB回复新进程所需的运行环境
引起进程切换的事件
- 当前进程的时间片到
- 有更高优先级的进程到达
- 当前进程阻塞
- 当前进程终止
进程通信
共享存储
设置一个共享空间
要互斥的访问共享空间
两种方式
- 基于数据结构（低级）
- 基于存储区的共享（高级）
管道通信
- 设置一个特殊的共享文件（管道），其实就是一个缓冲区
- 一个管道只能实现半双工通信
- 实现双向同时通信要建立两个管道
- 各进程要互斥的访问管道
- 写满时，不能再写；读空时，不能再读
- 没写满，不能读；没读空，不能写
消息传递
传递结构化的消息（消息头/消息体）
系统提供“发送/接受原语”
两种方式
直接通信方式
- 消息直接被挂到接收方的消息队列里
间接（信箱）通信方式
- 消息先发到中间体（信箱）
线程
引入线程带来的变化
资源分配、调度
- 传统进程机制中，进程是资源分配的基本单位
- 引入线程后，进程时资源分配的基本单位，线程是调度的基本单位
并发性
- 传统进程机制中，只能进程间并发
- 引入线程后，各线程间也能并发，提高了并发度
系统开销
- 传统的进程间并发，需要切换进程的运行环境，系统开销很大
- 线程间并发，如果是同一进程的线程切换，则不需要切换进程环境，系统开销小
- 引入线程后，并发带来的系统开销减小
线程的属性
- 线程是处理机调度的单位
- 多CPU计算机中，各个线程可以占用不同的CPU
- 每个进程都有一个线程ID，线程控制块TCB
- 线程也有就绪、阻塞、运行三种基本状态
- 线程几乎不拥有系统资源
- 同一进程的线程间共享进程的资源
- 由于共享内存地址空间，同一进程的线程间通信甚至无需系统干预
- 同一进程中的线程切换，不会引起进程切换；不同进程中的线程切换，会引起进程切换
- 切换同进程内的线程，系统开销很小；切换进程系统开销大
实现方式
用户级线程（ULT）
- 用户视角能看到的线程，由线程库实现
内核级线程(KLT)
- OS视角看到的线程（由OS实现的内核级线程才是处理机分配的单位
组合方式
多线程模型
一对一模型
- 一个用户级线程映射到一个内核级线程
- 优点：各个线程可分配到多核处理机并行执行，并发度高
- 缺点：线程管理都需要OS支持，开销大
多对一模型
- 多个用户级线程映射到一个内核级线程
- 优点：线程管理开销小效率高
- 缺点：一个线程阻塞会导致整个进程都被阻塞（并发度低）
多对多模型
- n个用户级线程映射到m个内核级线程（n>=m）
- 集两者之所长
2.2 处理机调度
基本概念
- 按照某种算法选择一个进程将处理机分配给他们
三个层次
高级调度（作业调度）
- 按照某种规则，从后备队列中选择合适的进程将其数据调回内存
- 外存->内存（面向作业）
- 发生频率：最低
中级调度（内存调度）
- 按照某种规则，从挂起队列中选择合适的进程将其数据调回内存
- 外存->内存（面向进程）
- 发生频率：中等
低级调度（进程调度）
- 按照某种规则，从就绪队列中选择一个进程为其分配处理机
- 内存->CPU
- 发生频率：最高
时机
什么时候需要进程调度
主动放弃
- 进程正常终止
- 运行过程发生异常终止
- 主动阻塞（如：等待I/O）
被动放弃
- 时间片用完
- 有更紧急的事情需要处理（如：中断）
- 有更高优先级的进程进入就绪队列
什么时候不能进行进程调度
- 处理中断时
- 进程在OS内核程序临界区
- 原子操作过程中（原语）
方式
非剥夺调度方式（非抢占式）
- 只能由当前运行的进程主动放弃CPU
剥夺调度方式（抢占式）
- 可由OS剥夺当前进程的CPU使用权
调度算法的评价指标
CPU利用率
- 利用率=忙碌时间/总时间
系统吞吐量
- 系统吞吐量=总共完成了多少道作业/总共花费时间
周转时间
- 周转时间=作业完成时间-作业提交时间
- 平均周转时间=各作业周转时间之和/作业数
- 带权周转时间=作业周转时间/作业实际运行时间
- 平均带权周转时间=各作业带权周转时间之和/作业数
等待时间
- 进程/作业等待被服务的时间
响应时间
- 从用户提交请求到首次产出相应所用时间
调度算法
先来先服务（FCFS）
算法思想
- 主要从“公平”角度考虑
算法规则
- 按照作业先后到达顺序进行服务
可用于作业/进程调度
非抢占式
优缺点
- 优点：公平，算法实现简单
- 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即对长作业有利，对短作业不利
不 会导致饥饿
短作业优先（SJF）
算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的 平均平均带权周转时间
算法规则：最短的作业/进程优先得到服务（所谓“最短”，是指要求 服务时间最短）
可用于作业/进程调度（短进程优先SPF）
非抢占（也有抢占式版本：短剩余时间优先算法SRTN, Shortest Remaining Time Next)
优缺点
- 优点：“最短的”平均等待时间、平均周转时间
- 缺点：不公平。对短作业有利，对长作业不利。
会 导致饥饿
高相应比优先（HRRN）
算法思想
- 综合考虑作业/进程的等待时间和要求服务的时间
算法规则
- 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
- 相应比=（等待时间+要求服务时间）/ 要求服务时间
可用于作业/进程调度
非抢占
优缺点
- 综合考虑了等待时间和运行时间。等待时间相同时，要求服务时间短的优先（SJF 的优点） 要求服务时间相同时，等待时间长的优先（FCFS 的优点） 对于长作业来说，随着等待时间越来越久，其响应比也会 越来越大，从而避免了长作业饥饿的问题。
不会 导致饥饿
时间片轮转调度算法(RR)
算法思想
- 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
算法规则
- 按照各进程到达就绪队列的顺序，轮流让各个进程执行一 个时间片（如 100ms）。若进程未在一个时间片内执行完， 则剥夺处理机，将进程重新放到就绪队列队尾重新排队
用于进程调度
抢占式
优缺点
- 优点：公平；响应快，适用于分时操作系统
- 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
不会 导致饥饿
注：时间片大小要合适
优先级调度算法
算法思想
- 随着计算机的发展，特别是实时操作系统的出现，越来越 多的应用场景需要根据任务的紧急程度来决定处理顺序
算法规则
子主题 1
- 调度时选择优先级最高的作业/进程
可用于作业/进程调度
抢占/非抢占都有
- 区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
优缺点
- 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
- 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
会 导致饥饿
多级反馈队列调度算法
算法思想
- 对其他算法的折中权衡
算法规则
- 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
- 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时 间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。 如果此时已经是在最下级的队列，则重新放回该队列队尾
- 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
用于进程调度
抢占式
- k 级队列的进程运行过程中，若更上级的队列（1~k-1级）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾
优缺点
对各类型进程相对公平（FCFS的优点）
每个新到达的进程都可以很快就得到响应（RR的优点）
短进程只用较少的时间就可完成（SPF的优点）
不必实现估计进程的运行时间（避免用户作假）
可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程
- 拓展：可以将因I/O而阻塞的进程重新放回原队列，这样
I/O型进程就可以保持较高优先级
- 拓展：可以将因I/O而阻塞的进程重新放回原队列，这样
会 导致饥饿
2.3 进程同步与互斥
进程互斥
概念
- （也称 间接制约关系）对临界资源的访问，需要互斥的进行。即同一时间段只能允许一个进程访问该资源
对临界资源的访问过程
四个部分
进入区
- 检查是否可以进入临界区，若可，需“上锁”
临界区
- 访问临界资源
退出区
- 解锁
剩余区
- 其余代码
需遵循的原则
空闲让进
忙则等待
优先等待
让权等待
- 当进程不能进入临界区时，应立即释放处理器，防止进程忙等
实现互斥的基本方法
软件实现方法
单标志法
在进入区只做检查，不上锁；在退出区把临界区的使用权转交给另一个进程（相当于在退出区给另一进程“解锁”，给自己上锁）
问题
- 不遵循“空闲让进”原则
双标志先检查法
在进入区先“检查”后“上锁”，退出区“解锁”
问题
- 不遵循“忙则等待”原则
双标志后检查法
在进入区先“上锁”后“检查”，退出区“解锁”
问题
- 不遵循“空闲让进、有限等待”原则
Peterson算法
在进入区“主动争取-主动谦让-检查对方是否想进&己方是否谦让”
问题
- 不遵循“让权等待”原则，会发生“忙等”
硬件实现方法
中断屏蔽方法
- 使用“开/关中断”指令实现
- 优点：简单高效
- 缺点：只适用于单处理机；只适用于OS内核进程
硬件指令方法
TestAndSet(TS指令/TSL指令)
相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点
- 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞
- 适用于多处理机环境
缺点
- 不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
Swap指令（XCHG指令）
- 逻辑同TSL
信号量机制
信号量类型
整型信号量
用一个整形变量作为信号量，数值表示某种资源数
与普通整型变量区别：对信号量只能执行初始化、P、V操作
问题
- 不满足”让权等待”原则
记录型信号量
- S.value 表示某种资源数，S.L指向等待该资源的队列
信号量机制实现进程互斥、同步、前驱关系
实现进程互斥
- 分析问题，确定临界资源
- 设置互斥信号量，初值为1
- 临界区之前对信号量执行P操作
- 临界区之后对信号量执行V操作
实现进程同步
- 分析问题，找出哪里需要实现”一前一后”的同步关系
- 设置同步信号量，初始值为0
- 在”前操作”之后执行V操作
- 在“后操作”之前执行P操作
实现进程的前驱关系（本质:多级同步问题）
- 分析问题画出前驱图，把每一对前驱关系都看成一个同步问题
- 为每一对前驱关系设置同步信号量，初始值为0
- 在”前操作”之后执行V操作
- 在“后操作”之前执行P操作
进程同步
概念
- （也称直接制约关系）为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系
经典同步问题
- 生产者-消费者问题
- 多生产者-多消费者问题
- 吸烟者问题
- 读者-写者问题
- 哲学家进餐问题
管程
为什么引入
- 解决信号量机制的编程麻烦、易出错的问题
组成
- 共享数据结构
- 对数据结构初始化的语句
- 一组用来访问数据结构的过程
基本特征
- 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程
补充
- 可在管程中设置条件变量及等待/唤醒操作以解决同步问题
2.4 死锁
概念
- 各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进
死锁、饥饿、死循环区别
- 死锁：至少两个进程，进程处于阻塞态
- 饥饿：可以只有一个进程饥饿，饥饿进程可能阻塞也可能就绪
- 死循环：可能只有一个进程死循环，死循环的进程可上处理机
- 死锁和饥饿是OS要解决的问题，死循环是程序员要解决的问题
死锁产生的必要条件
互斥条件
不剥夺条件
请求和保持条件
循环等待条件
- 存在一种进程资源的循环等待链
- 循环等待未必死锁，死锁一定有循环等待
什么时候发生死锁
对不可剥夺资源的不合理分配
- 对系统资源的竞争
- 进程推荐顺序非法
- 信号量的使用不当
死锁的处理策略
不允许死锁发生
预防死锁（静态策略）
破坏互斥条件
- 将临界资源改造为可共享使用的资源（SPOOLing技术）
- 缺点：可行性不高，很多时候无法破环互斥条件
破坏不剥夺条件
方案1：申请的资源得不到满足时，立即释放拥有的所有资源
方案2: 申请的资源被其他进程占用时，由OS协助剥夺(考虑优先级)
缺点
- 实现复杂
- 剥夺资源可能导致部分工作失效
- 反复申请和释放导致系统开销大
- 可能导致饥饿
破坏请求和保持条件
- 预先静态分配法：运行前分配好所有需要的资源，之后一直保持
- 缺点：资源利用率低; 可能导致饥饿
破坏循环等待条件
顺序资源分配法：给资源编号，必须按编号从小到大的顺序申请资源
缺点：
- 不方便增加新设备
- 会导致资源浪费
- 用户编程麻烦
避免死锁（动态策略）
银行家算法
- 避免系统进入不安全状态
允许死锁发生
死锁的检测和解除
如何检测
数据结构：资源分配图
两种结点
- 资源结点
- 进程结点
两种边
- 请求边（进程结点->资源结点）
- 分配边（资源结点->进程结点）
死锁检测算法
- 依次消除与不阻塞进程相连的边，直到无边可消
- 死锁定理：若资源分配图是可不完全简化的，说明发生了死锁
如何解除
- 资源剥夺法
- 撤销进程法（终止进程法）
- 进程回退法
ch 3 内存管理
3.1 进程运行的基本原理
从写程序到程序运行
编译
- 由源代码文件生成目标文件（高级语言“翻译为机器语言”）
链接
由目标模块生成装入模块，链接后形成完整的逻辑地址
三种链接方式
静态链接
- 装入前链接成一个完装入模块
装入时动态链接
- 运行前边装入边链接
运行时动态链接
- 运行时需要目标模块才装入并链接
装入
由装入模块装入内存，装入后形成物理地址
三种装入方式
绝对装入
- 编译时产生绝对地址
可重定位装入
- 装入时将逻辑地址转换为物理地址
动态运行时装入
- 运行时将逻辑地址转换为物理地址，需要设置重定位寄存器
3.2 内存空间的分配与回收
连续分配方式
连续分配：为用户进程分配的必须是一个连续的内存空间。
单一连续分配
只支持单道程序；
内存被分为系统区和用户区。 系统区通常位于内存的低地址部分，用于存放操作系统 相关数据；用户区用于存放用户进程相关数据。优点
- 实现简单；
- 无外部碎片；
- 可以采用覆盖技术扩充内存；
- 不一定需要采取内存保护（eg：早期的 PC 操作 系统 MS-DOS）
缺点
- 只能用于单用户、单任务的操作系统中；
- 有内部碎片；
- 存储器利用率极低
固定分区分配
支持多道程序。将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业
两种分区方式
分区大小相等
- 缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
分区大小不等
- 增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分
优点
- 实现简单；
- 无外部碎片
缺点
- a. 当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能
- b. 会产生内部碎片，内存利用率低
动态分区分配（可变分区分配）
支持多道程序，在进程装入内存时，根据进程大小动态地建立分区
优缺点
- 无内部碎片，有外部碎片(外部碎片可用“紧凑技术来解决”)
回收内存分区时的四种情况
总之，相邻的空闲分区要合并
- 回收之后有相邻的空闲分区
- 回收之前有相邻的空闲分区
- 回收前后都有相邻的空闲分区
- 回收前后都无相邻的空闲分区
动态分区分配算法
首次适应算法（First Fit）
算法思想
- 从头到尾找适合的分区
分区排序顺序
- 空闲分区以 地址 递增次序排列
优点
- 综合看性能最好。算法开销小，回收分区后一般不需要对空闲分区队列重新排序
最佳适应算法（Best Fit）
算法思想
- 优先使用更小的分区，以保留更多大 分区
分区排序顺序
- 空闲分区以 容量 递增次序排列
优点
- 会有更多的大分区被保留下来，更能满足大进程需求
缺点
- 会产生很多太小的、难以 利用的碎片；
算法开销大， 回收分区后可能需要对空 闲分区队列重新排序
- 会产生很多太小的、难以 利用的碎片；
最坏适应算法（Worst Fit）
算法思想
- 优先使用更大的分区，以防止产生太小的不可用的碎片
分区排序顺序
- 空闲分区以 容量 递减次序排列
优点
- 可以减少难以利用的 小碎片
缺点
- 大分区容易被用完，不利于大进程；
算法开销大 （原因同上）
- 大分区容易被用完，不利于大进程；
邻近适应算法（Nest Fit）（循环首次适应）
算法思想
- 由首次适应演变而来，每次从上次查找结束位置开始查找
分区排序顺序
- 空闲分区以 地址 递增次序排列 （可排列成循环链表）
优点
- 不用每次都从低地址 的小分区开始检索。
算法开销小（原因同首次适应算法）
- 不用每次都从低地址 的小分区开始检索。
缺点
- 会使高地址的大分区也被用完
非连续分配方式
非连续分配：为用户进程分配的可以是一些分散的内存空间。
基本分页存储管理
基本概念
基本分页存储管理的思想：把进程分页，各个页面可离散地放到各个内存块中
易混淆概念
- “页、页面”VS“页框、页帧、内存块、物理块、物理页”
- “页号、页面号”VS“页框号、页帧号、内存块号、物理块号、物理页号”
页表
- 页表记录了页面和实际存放的内存块之间的映射关系
- 一个进程对应一张页表，进程的每一页对应一个页表项，每个页表项由“页号”和块号组成
- 每个页表项的大小相同，页号是“隐含”的
- i号页表存放地址=页表始址+i*页表项大小
逻辑地址结构—【页号P，页内偏移量W】
- 页号=逻辑地址/页面大小
- 页内偏移=逻辑地址%页面大小
地址转换
- 计算出逻辑地址对应的【页号，页内偏移】
- 找到对应页面在内存中的存放位置（查页表）
- 物理地址=页面始址+页内偏移量
基本地址变换机构
页表寄存器的作用
- 存放页表起始地址
- 存放页表长度
地址变换过程
- 根据逻辑地址算出页号、页内偏移量
- 检查页号是否合法（对比页表长度），不合法产生越界中断
- 若页号合法，再根据页表起始地址、页号找到对应页表项
- 根据页表项中的内存块号、页内偏移量 得到最终物理地址
- 访问物理内存对应的内存单元
访存次数
- 两次
其他注意点
- 页内偏移量位移与页面大小之间的关系（要能用其中一个条件退出另一个条件）
- 页式管理中地址是一维的
- 实际应用中，通常使一个页框恰好能放入整数个页表项
- 为了方便找到页表项，页表一般是放在连续的内存块中
具有快表的地址变换机构
快表（又称联想寄存器 TLB， translation lookaside buffer）
一种访问速度比内存快很多的高速缓存（TLB不是内存！）
用来存放最近访问的页表项的副本，可以加速地址变换的速度。
与此对应，内存中的页表常称为慢表
TLB 和 普通 Cache 的区别
- TLB 中只有页表项的副本，而普通 Cache 中可能会有其他各种数据的副本
地址变换过程
- ①算页号、页内偏移量
- ②检查页号合法性
- ③查快表。
若命中，即可知道页面存放的内存块号，可直接进行⑤ ；若未命中则进行④ - ④查页表，找到页面存放的内存块号，并且将页表项复制到快表中
- ⑤根据内存块号与页内偏移量得到物理地址
- ⑥访问目标内存单元
访存次数
- 快表命中，只需一次访存快表未命中，需要两次访存
两级页表
单级页表存在的问题
- 所有页表必须连续存放，页表过大时需要很大的连续空间
- 在一段时间内并非所有的页面都用得到，因此没必要让整个页表常驻内存
两级页表
- 将页表再分页
- 逻辑地址结构：（一级页号，二级页号，页内偏移量）
- 注意术语：页目录表/外层页表/顶级页表
如何实现地址变换
- ①按照地址结构将逻辑地址拆分成三部分
- ②从PCB 中读出页目录表始址，再根据一级页号查页目录 表，找到下一级页表在内存中的存放位置
- ③根据二级页号查二级页表，找到最终想访问的内存块号
- ④结合页内偏移量得到物理地址
几个细节
- 多级页表中，个几页表的大小不能超过一个页面。若两级页表不够，可以分更多级
- 多级页表的访存次数（无快表机构时）：N级页表访问一个逻辑地址需要N+1次访存
基本分段存储管理
分段
- 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址
- 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
- 逻辑地址结构：（段号，段内地址）
段表
- 每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称 “基址”）和段的长度。
- 各个段表项的长度是相同的。
地址变换
分段VS分页
- 分页对用户不可见，分段对用户可见
- 分页的地址空间是一维的，分段的地址空间是二维的
- 分段更容易实现信息的共享和保护（纯代码/可重入代码可以共享）
- 分页（单级页表）、分段访问一个逻辑地址都需要两次访存，分段存储也可以引入快表机构
段页式存储管理
分段+分页
- 将地址空间按照程序自身的逻辑关系划分为若干个段，再将各段分为大小相等的页面
- 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
- 逻辑地址结构：（段号，页号，页内偏移量）
段表、页表
- 每个段对应一个段表项。各段表项长度相同，由段号（隐含）、页表长度、页表存放块号（页表起始 地址）组成。
- 每个页面对应一个页表项，各页表项长度相同，由页号（隐含）、页面存放的内存块号组成。
地址变换
访问一个逻辑地址所需访存次数
- 第一次：查段表、第二次：查页表、第三次：访问目标单元
- 可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存
3.3 内存空间的扩充
覆盖与交换
覆盖技术
一个固定区
- 存放最活跃的程序段
- 固定区中的程序段在运行过程中不会被调入调出
若干覆盖区
- 不可能同时被访问的程序段可共享一个覆盖区
- 覆盖区中的程序段在运行过程中会根据需要调入调出
必须由程序员声明覆盖结构，OS完成自动覆盖
缺点：对用户不透明，增加了用户编程负担
交换技术
- 内存紧张时，换出某些进程以腾出内存空间，再换入某些进程
- 磁盘分为文件区和对换区，换出的进程放在对换区
覆盖与交换的区别
- 覆盖是在同一进程或程序中的
- 交换在不同的进程（或作业）中
虚拟存储技术
传统存储管理方式的特征和缺点
- 一次性：作业数据必须一次全部调入内存
- 驻留性：作业数据整个运行期间都会常驻内存
局部性原理
- 时间局部性：现在访问的指令、数据不久之后很可能再次访问
- 空间局部性：现在访问的内存单元周围的内存空间，很可能在不久之后会被访问
- 高速缓存技术：使用频繁的数据放到更高速的存储器中
虚拟内存的定义和特征
程序不需要全部装入即可运行，运行时根据需要动态调整调入数据，若内存不过，还需换出一些数据
特征
- 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
- 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换 入、换出
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
如何实现虚拟内存技术
【请求调页功能】：当所访问的信息不在内存时，由OS负责将所需信息从外存调入内存
【页面置换功能】：若内存空间不够，由操作系统负责将内存 中暂时用不到的信息换出到外存
虚拟内存的实现
请求分页存储管理
页表机制（在基本分页基础上增加了4个表项）
- 状态位: 是否已调入内存
- 访问字段：可记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
- 修改位：页面调入内存后是否被 修改过
- 外存地址：页面在外存中的存放位 置
缺页中断机构
- 找到页表后，检查页面是否已在内存中，若不在，产生一个缺页中断
- 缺页中断处理中，需要将目标页面调入内存，有必要时还要换出页面
- 缺页中断属于内中断中的“故障”，即可能被系统修复的异常
- 一条指令执行过程中可能产生多次缺页中断
地址变换机构
页面置换算法
页面的换入、换出需要磁盘 I/O，会有较大的开销，因
此好的页面置换算法应该追求更少的缺页率最佳置换算法（OPT）
- 算法规则：优先淘汰最长时间内不会被访问的页面
- 优缺点：缺页率最小，性能最好； 但无法实现
先进先出置换算法（FIFO）
- 算法规则：优先淘汰最先进入内存的页面
- 优缺点：实现简单；但性能很差， 可能出现Belady异常
最近最久未使用算法（LRU）
- 算法规则：LRU 优先淘汰最近最久没访问的页面
- 优缺点：性能很好；但需要硬件（寄存器和栈）支持，算法开销大
时钟置换算法（CLOCK）
- 算法规则：循环扫描各页面，第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第一轮没选中，则进行第二轮扫描
- 优缺点：实现简单，算法开销小； 但未考虑页面是否被修改过。
改进型的时钟置换算法
- 算法规则：
若用（访问位, 修改位）的形式表述，则
第一轮：淘汰（0, 0）
第二轮：淘汰（0, 1），并将扫描过的页面访问位都置为0
第三轮：淘汰（0, 0）
第四轮：淘汰（0, 1） - 优缺点：算法开销较小，性能也不错
- 算法规则：
页面分配策略
驻留集
- 指请求分页存储管理中给进程分配的物理块的集合
页面分配、置换策略
- 固定分配 VS 可变分配：区别在于运行期间驻留集大小是否可变
- 局部置换 VS 全局置换：区别在于发生缺页时是否只能从进程自己的页面中选择一个换出
- 固定分配局部置换：进程运行前就分配一定数量的物理块，缺页时只能换出进程自己的某一页
- 可变分配全局置换：只要缺页就分配，可能来自空闲物理块，也可能需要换出别的进程的页面
- 可变分配局部置换：频繁却页的进程多分配一些物理块；缺页率低的进程，回收一些物理块。直到缺页率合适
何时调入页面
- 预调页策略：一般用于进程运行前
- 请求调页策略：进程运行时，发现缺页再调页
从何处调入页面
- 对换区：读/写 速度更快，采用连续分配方式
- 文件区：读/写 速度更慢，采用离散分配方式
- 对换区足够大：运行前将数据从文件区复制到对换区，之后所有页面的调入、调出都是在内存与对换区之间进行
- 对换区不够大：凡是不会被修改的数据都直接从文件区调入；可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
- UNIX方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都从文件区调入。被使用过的页面写回对换区，下次需要时从对换区调入
抖动（颠簸现象）
- 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸
- 产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）
工作集
- 指在某段时间间隔里，进程实际访问页面的集合
- 一般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页
请求分段存储管理
请求段页式存储管理
3.4 地址转换
OS负责实现逻辑地址到物理地址的转化
三种方式
绝对装入
- 编译器负责地址转换（单道程序，无OS）
可重定位装入
- 装入程序负责地址转换（早期多道批处理阶段）
动态运行时装入
- 运行时才进行地址转换（现代OS）
3.5 存储保护
保证各进程在自己的内存空间内运行，不会越界访问
两种方式
- 设置上下限寄存器
- 利用重定位寄存器、界地址寄存器进行判断
ch 4 文件管理
4.1 文件的基本概念
文件的属性
- 文件类型
- 文件长度
- 文件的物理位置
- 文件的创建信息
文件名
- 文件名
- 扩展名
文件类型
按用途分类
- 系统文件
- 用户文件
- 库文件
按文件中的数据类型分类
- 源文件
- 目标文件
- 可执行文件
按存取控制属性分类
- 只执行文件
- 只读文件
- 读写文件
按组织形式和处理方式分类
- 普通文件
- 目录文件
- 特殊文件
4.2 文件的逻辑结构
有结构文件
- 文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。
无结构文件
由一组相似的记录组成，又称“记录式文件”
逻辑结构
顺序文件
- 串结构：记录顺序与关键字无关
- 顺序结构：记录按关键字顺序排序
- 可变长记录的顺序文件无法实现随机存取，定长记录可以
- 定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速记录）
- 最大缺点：不方便增加/删除记录
索引文件
- 建立一张索引表，每个记录对应一个表项。个记录不用保持顺序，方便增加/删除记录
- 索引表本身就是定长记录的顺序文件，一个索引表就是一条定长记录，因此，索引文件可以支持随机存取
- 若索引表按关键字顺序排列，则可只是快速检索
- 解决了文件不方便增/删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间
顺序索引文件
- 将记录分组，每组对应一个索引表项
- 检索记录时先顺序查索引表，找到分组，在顺序查找分组
- 当记录过多时，可建立多级索引表
4.3 文件目录
文件目录的实现
- 一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录
- 对目录的操作：搜索、创建、删除文件、显示文件、修改文件
目录结构
单机目录结构
- 一个系统只有一张目录表，不允许文件重名
两级目录结构
- 不同用户的文件可以重名，但不能对文件进行分类
多级（树形）目录结构
- 不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
- 系统根据”文件路径”找到目标文件
- 从根目录出发的路径是“绝对路径”
- 从“当前目录”出发的路径是“相对路径”
无环图目录结构
- 在树形目录结构的基础上，增加一些指向同一节点的有向边，是整个目录成为一个DAG
- 为共享结点设置一个共享计数器，计数器为0时才真正删除该节点
索引节点
- 除了文件名之外的所有信息都放到索引节点
- 目录项中只包含文件名、索引结点指针，因此目录项的长度答复减少
- 由于目录项长度减少，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘的I/O次数就少了很多
4.4 OS需要对磁盘块进行哪些管理？
对非空闲磁盘块的管理：文件的物理结构（文件的分配方式）
连续分配
- 连续分配方式要求每个文件在磁盘上占有一组连续的块
- 优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快
- 缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片
链接分配
隐式链接
- 除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针
- 优点：很方便文件拓展，不会有碎片问题，外存利用率高。
- 缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。
显式链接
- 把用于链接文件各物理块的指针显式地存放在一张表中，即 文件分配表（FAT，File Allocation Table）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内 存
- 优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接 来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
- 缺点：文件分配表的需要占用一定的存储空间。
索引分配
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块 。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
文件太大，索引表项太多时的解决方案
- 链接方案
- 多层索引
- 混合索引
优点：支持随机访问，易于实现文件的拓展
缺点：索引表需占用一定的存储空间。访问数据块前需要先读入索引块。若采用链接方案，查找索引块时可能需要很多次读磁盘操作
对空闲磁盘块的管理：文件存储空间管理
存储空间的划分与初始化
- 文件卷（逻辑卷），目录区、文件区的概念
- 目录区包含文件目录、空闲表、位示图、超级块等用于文件管理的数据
空闲表法
- 空闲表中记录每个连续空闲区的起始盘块号、盘块数
- 分配时可采用首次适应、最佳适应等策略；回收时注意表项的合并
空闲链表法
空闲盘块链
- 以盘块为单位组成的一条空闲链
- 分配时从链头依次取出空闲块，回收时将空闲块插到链尾
空闲盘区链
- 以盘区为单位组成的一条空闲链
- 分配时可采用首次适应、最佳适应等策略；回收时注意相邻空闲盘区合并的问题
位示图法
- 一个二进制位对应一个盘块。（字号，位号）或（行号，列号）与盘块号一一对应
- 注：盘块号 与 （字号，位号）的相互转换
成组链接法
- UNIX采用的策略，适合大型文件
4.5 文件的基本操作
创建文件（ Create 系统调用）
- 分配外存空间，创建目录项
删除文件（Delete 系统调用）
- 回收外存空间，删除目录项
打开文件（open 系统调用）
- 将目录项中的信息复制到内存中的打开文件表中，并将打开文件表中的索引号返回给用户
- 打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作
- 每个进程都有自己的打开文件表，系统中也有一张总的打开文件表
- 进程打开文件表中的特有属性：读写指针、访问权限（只读？只写？）
- 进程打开文件表中的特有属性：打开计数器（有多少个进程打开了该文件）
关闭文件（Close 系统调用）
- 将进程打开文件表中的相应表项删除
- 系统打开文件表的打开计数器-1，若打开计数器=0，则删除系统表的表项
读文件（read系统调用）
- 根据读指针、读入数据量、内存位置将文件数据从外存读入内存
写文件（write 系统调用）
- 根据写指针、写出数据量、内存位置 将文件数据从内存写出外存
4.6 文件共享
硬链接
- 各个用户的目录项指向同一个索引节点
- 索引结点中需要有链接计数count
- 某用户删除文件时，只是删除该用户的目录项，且count–
- 只用count==0时，才真正删除文件数据和索引结点，否则会导致指针悬空
软链接（符号链接）
- 在一个Link型的文件中记录共享文件的存放路径（Windows快捷方式）
- OS根据路径一层层查找目录，最终找到共享文件
- 即便软链接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败（找不到对应目录项）
- 由于通过软连接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问共享文件的速度要比硬链接更慢
4.7 文件保护
口令保护
- 为文件设置一个“口令”，用户请求访问该文件时必须提供“口令”，由系统验证口令是否正确
- 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
- 缺点：正确的“口令”一般存放在文件对应的 FCB 或索引结点中，即系统内部，不够安全。
加密保护
- 使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密
- 优点：保密性强，不需要在系统中存储“密码”
- 缺点：编码/译码（加密/解密）要花费一定时间。
访问控制
- 在每个文件的FCB（或索引结点）中增加一个访问控制列表（ACL），记录各个用户（或各组用户）对文件的访问权限
- 对文件的访问类型：读/写/执行/执行/删除…
- 实现灵活可以实现复杂的文件保护功能
4.8 文件系统的层次结构
4.9 磁盘
基本概念
磁盘、磁道、扇区
盘面、柱面
磁盘的物理地址
- （柱面号，盘面号，扇区号）
磁盘的分类
根据磁头是否可移动
- 固定头磁盘（每个磁道有一个磁头）
- 移动头磁盘（每个盘面只有一个磁头）
根据盘片是否可更换
- 固定盘磁盘
- 可换盘磁盘
一次磁盘读/写操作需要的时间
- 寻道时间：启动磁臂，移动磁头所花的时间
- 延迟时间：将目标扇区转到磁头下面所花的时间
- 传输时间：读/写 数据花的时间
减少寻道时间：磁盘调度算法
先来先服务（FCFS）
- 根据进程请求访问磁盘的先后顺序进行调度。
- 优点：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去
- 缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长
最短寻道时间优先（SSTF）
- 优先处理的磁道是与当前磁头最近的磁道
- 优点：性能较好，平均寻道时间短
- 缺点：可能导致饥饿
扫描算法（电梯算法，SCAN）
只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动
优点：性能较好，平均寻道时间较短，不会产生饥饿现象
缺点：对各个位置磁道的响应频率不平均
改进算法
- LOOK算法：只要在磁头移动方向不再有请求，就立即改变磁头方向
循环扫描算法（C-SCAN）
规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。
改进算法
- C-LOOK算法：只要在磁头移动方向不再有请求，就立即改变磁头方向
减少延迟时间的方法
交替编号
- 让编号相邻的扇区在物理上不相邻
- 原理：读完一个扇区后需要一段时间处理才可以继续读下一个扇区
错位命名
- 让相邻盘面的扇区编号“错位”
- 原理：读完一个扇区后需要一段时间处理才可以继续读下一个扇区
磁盘的管理
磁盘初始化
- 低级格式化/物理格式化：划分扇区
- 磁盘分区（C盘，D盘…）
- 逻辑格式化：建立文件系统（建立根目录文件、建立用于管理存储空间的数据结构）
引导块
- 计算机启动时需要运行初始化程序（自举程序）来完成初始化
- ROM中存放很小的自举装入程序
- 完整的自举程序存放在初始化块（引导块）中
坏块的管理
- 简单的磁盘：逻辑格式化时将坏块标记出来
- 复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区
ch 5 I/O管理
5.1 I/O设备的概念和基本分类
概念
- 将数据输入/输出计算机的外部设备
分类
按使用特性分
- 人机交互类外部设备
- 存储设备
- 网络通信设备
按传输速率分
- 低速设备
- 中速设备
- 高速设备
按信息交换的单位分
- 块设备（传输快，可寻址）
- 字符设备（传输慢，不可寻址，常采用中断驱动方式）
5.2 I/O设备
机械部件
- 键盘、鼠标…（用来执行具体I/O操作）
电子部件
I/O控制器（又称 设备控制器）
主要功能
接受和识别CPPU发出的命令
- 如CPU发来的 read/write 命令，I/O控制器中会有相应的 “控制寄存器“ 来存放命令和参数
向CPU报告设备的状态
- I/O控制器中会有相应的 ”状态寄存器“ ，用于记录I/O设备的当前状态。如：1表示空闲，0表示忙碌
数据交换
- I/O控制器中会设置相应的 ”数据寄存器“。输出时，数据寄存器用于暂存CPU发来的数据，之后再由控制器传送设备。输入时，数据寄存器用于暂存设备发来的数据，之后CPU从数据寄存器中取走数据
地址识别
- 类似于内存的地址，为了区分设备控制器中的各个寄存器，也需要给各个寄存器设置一个特定的“地址”。I/O控制器通过CPU提供的“地址”来判断CPU要读/写的是哪个寄存器
组成
- CPU与控制器的接口
- I/O逻辑
- 控制器与设备的接口
两种寄存器编址方式
内存映射I/O
- 控制器中的寄存器与内存地址统一编址
- 优点：简化了指令。可以采用对内存进行操作的指令来对控制器进行操作
寄存器独立编址
- 控制器中的寄存器使用单独的地址
- 缺点：需要设置专门的指令来实现对控制器的操作，不仅要指明寄存器的地址，还要指明控制器的编号
5.3 I/O控制方式
程序直接控制方式
- CPU干预频率：极高
- 每次I/O的数据传输单位：字
- 数据流向：设备->CPU->内存（内存->CPU->设备）
- 优点：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可
- 缺点：CPU和I/O设备只能串行工作，CPU需要一直轮询检查，长期处于“忙等”状态 ，CPU利用率低。
中断驱动方式
- CPU干预频率：高
- 每次I/O的数据传输单位：字
- 数据流向：设备->内存（内存->设备）
- 优点：CPU和I/O设备可并行工作，CPU利用率得到明显提升
- 缺点：每个字在I/O设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。
DMA方式
- CPU干预频率：中
- 每次I/O的数据传输单位：块
- 数据流向：设备->内存（内存->设备）
- 优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/O设备的并行性得到提升。
- 缺点：CPU每发出一条I/O指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU要分别发出多条I/O指令，进行多次中断处理才能完成。
通道控制方式
- CPU干预频率：低
- 每次I/O的数据传输单位：一组块
- 数据流向：设备->内存（内存->设备）
- 缺点：实现复杂，需要专门的通道硬件支持
- 优点：CPU、通道、I/O设备可并行工作，资源利用率很高。
5.4 I/O软件层次结构
用户层软件
用户层软件实现了与用户交互的接口，用户可直接使用该层提供的、与I/O操作相关的库函数对设备进行操作
假脱机技术（SPOOLing技术）
- 用软件的方式模拟脱机技术
- 输入井/输出井——模拟脱机输入/输出时的磁带
- 输入进程/输出进程——模拟脱机输入/输出时的外围控制机
- 输入缓冲区/输出缓冲区——内存中的缓冲区，输出输出时的中转站
- 实例：共享打印机（用SPOOLing技术将独占式的打印机”虚拟“成共享打印机）
设备独立性软件
①向上层提供统一的调用接口（如 read/write 系统调用）
②设备保护
③差错处理
④设备的分配与回收
应考虑的因素
固有属性
- 独占设备、共享设备、虚拟设备
分配算法
- 先来先服务、优先级、短任务优先
安全性
- 安全分配方式
- 不安全分配方式
静态分配与动态分配
- 静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源（破坏”请求和保持“条件）
- 动态分配：进程运行过程中动态申请设备资源
设备分配管理中的数据结构
设备控制表（DCT）
- 系统为每个设备配置一张DCT，用于记录设备情况
控制器控制表（COCT）
- 每个设备控制器都会对应一张COCT。操作系统根据COCT的信息对控制器进行操作和管理。
通道控制表（CHCT）
- 每个通道都会对应一张CHCT。操作系统根据CHCT的信息对通道进行操作和管理。
系统设备表（SDT）
- 记录了系统中全部设备的情况，每个设备对应一个表目
设备分配的步骤
①根据进程请求的物理设备名查找SDT;
②根据SDT找到DCT，若设备忙碌则将进程PCB挂到设备等待队列中，不忙碌则将设备分配给进程;
③根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程;
④根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。缺点
- ①用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程 ②若换了一个物理设备，则程序无法运行；③若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待
改进
- 建立逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名
- ①根据进程请求的逻辑设备名查找SDT（注：用户编程时提供的逻辑设备名其实就是“设备类型”）
②查找SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项。
③根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
④根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
⑤数据缓冲区管理
缓冲区概念
- 一般用内存作为缓冲区
- 缓解CPU与设备的速度矛盾、减少CPU的中断频率、解决数据粒度不匹配的问题、提高CPU与I/O设备之间的并行性
单缓冲
- 设备—(T)—缓冲区—(M)—工作区—©—处理
- 处理一块数据平均耗时Max(C, T)+M
- 分析的初始状态：工作区满，缓冲区空
双缓冲
- 处理一块数据平均耗时Max(T，C+M)
- 分析的初始状态：工作区空，一个缓冲区满，另一个缓冲区空
循环缓冲区
- 多个缓冲区链接成循环队列，in指针指向第一个空缓冲区，out指针指向第一个满缓冲区
缓冲池
三个队列：空缓冲队列、输入队列、输出队列
四种工作缓冲区
- 用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区
- 用于收容输出数据的工作缓冲区、用于收容输出数据的工作缓冲区
⑥建立逻辑设备名到物理设备名的映射关系；
根据设备类型选择调用相应的驱动程序逻辑设备表（LUT）
- 整个系统只有一张LUT：各用户所用的逻辑设备名不允许重复，适用于单用户操作系统
- 每个用户一张LUT：不同用户的逻辑设备名可重复，适用于多用户操作系统
I/O调度
设备驱动程序
- 主要负责对硬件设备的具体控制，将上层发出的一系列命令（如read/write）转化成特定设备“能听得懂”的一系列操作。包括设置设备寄存器；检查设备状态等
中断处理程序
- 进行中断处理