导图社区 《计算机操作系统（第四版）》-导图
- 242
- 2
- 1
- 举报
《计算机操作系统（第四版）》-导图
《计算机操作系统（第四版）》-导图，包括操作系统接口、进程的描述与控制、处理机调度与死锁、虚拟存储器等等。
编辑于2022-08-10 11:43:58 上海- 计算机操作系统
- 相似推荐
- 大纲
操作系统
引论
操作系统的目标和作用
计算机系统的组成
操作系统是硬件基础上的第一层软件
配置OS的目标
方便用户使用
有效性
提供系统的资源利用率和吞吐量
可扩展性
开放性
OS的作用
作为用户与计算机硬件系统之间的接口
作为计算机系统资源的管理者
硬件资源
软件资源
处理机管理
存储器管理
I/O设备管理
文件管理
是对计算机资源的抽象
操作系统的发展过程
发展过程和典型的OS
无操作系统的计算机系统：真空管、纸带
脱机输入/输出
减少了CPU空闲时间
提高I/O速度
（单道）批处理系统
作业控制
自动性、顺序性、单道性
批处理方式
联机批处理
CPU直接处理输入输出
脱机批处理
卫星机完成输入/输出，与主机并行工作
缓冲技术的一种
集成电路时代的操作系统
多道批处理系统
多道程序设计的出现标志操作系统的形成 应用：计算、商业。IBM360
作业调度程序将作业从后备队列调入内存
建立在中断等硬件基础上的CPU与I/O设备并行
作业周转时间长，不能交互计算/调试程序困难
分时系统
公共计算服务系统：MULTICS Unix
每个用户依次轮流使用时间片
特点
多路性：多个用户同时工作，提高资源利用率
独立性：各用户独立操作，互不干扰
及时性：系统能及时对用户的操作进行响应，提高debug效率，缩短周转时间
交互性：支持人机对话，交互式应用
批处理&分时
区别
目标不同：前者资源利用率，后者及时反应
适用作业类型不同
资源利用率不同
作业控制方式不同
思想结合
分时有限，任务分前/后台
前台：需频繁交互的作业
后台：时间性要求不强的作业
实时系统
应用需求
实时控制
实时信息处理
实时任务
截止时间
开始截止时间
完成截止时间
按任务执行时是否呈现周期性来划分
周期性实时任务
非周期性实时任务
根据对截止时间的要求来划分
硬实时任务
软实时任务
微机，网络
单用户单任务
单用户多任务
多用户多任务
移动计算机
其他OS
分布式操作系统
特征
统一的操作系统、资源进一步共享
透明性
自治性：各主机处于平等地位、无主从关系
优点
处理能力增强
速度更快
可靠性增强
嵌入式操作系统
非通用微型化
实时性、可靠性
可定制、易移植
成本低、占用资源少
个人操作系统
命令处理程序
DOS
不支持虚拟存储，没有存储保护，文件系统为FAT
BIOS
中小型机操作系统
常见的操作系统
操作系统的基本特性
并发性（Concurrence）
最基本的特征
并发：在同一时间间隔内发生
并行：在同一时刻发生
共享（Sharing）
互斥共享方式
互斥资源/独占资源（打印机）
同时访问方式
通常是宏观上的同时（磁盘、文件）
并发和共享是基本特征 共享以并发为前提条件 并发度受共享管理影响
虚拟（Virtual）
将实体物理设备映射为逻辑设备（一对多或多对一等）
时分复用
虚拟处理机技术
虚拟设备技术
虚拟存储技术
空分复用
利用存储器的空闲时间分区域存放和运行其他的多道程序，提高内存的利用率
异步（Asynchronsim）
进程是以人们不可预知的速度向前推进的，需要一定的进程同步机制
操作系统的主要功能
为多道程序提供良好的运行环境 以保证多道程序高效运行，最大程度利用系统资源 方便用户使用
处理机管理功能
进程控制
进程同步
进程互斥方式
进程同步方式
信号量机制
进程通信
调度
作业调度
进程调度
存储器管理功能
内存分配
静态分配方式
动态分配方式
内存保护
保护用户互不干扰
保护操作系统不被用户干扰
地址映射
在硬件支持下：将逻辑地址转换为内存空间中的物理地址
内存扩充
借助虚拟存储技术
请求调入功能
置换功能
设备管理功能
缓冲管理
缓和CPU与I/O设备间的速度不匹配
单缓冲机制
双缓冲机制
公用缓冲池机制
设备分配
设备处理（设备驱动程序）
文件管理功能
文件存储空间的管理
目录管理
文件的读/写管理
文件保护
防止未经核准的用户存取文件
防止冒名顶替存取文件
防止以不正确的方式使用文件
用户接口
命令接口
为了便于用户直接或间接地控制自己的作业
联机用户接口
脱机用户接口
图形用户接口
程序接口
为用户程序在执行中访问系统资源而设置的
用户程序取得操作系统服务的唯一途径
其他新功能：安全、网络功能与服务、支持多媒体
操作系统的结构设计
有效 系统高效率、资源高利用率 公平合理 易于使用和维护 上述目标通常是矛盾的
无结构操作系统
一组过程的集合
模块化结构OS
无序模块法
优
提高了OS设计的正确性、可理解性和可维护性
增强了OS的可适应性
加速了OS的开发过程
缺
对模块的划分和接口规定可能不精确
各模块设计齐头并进，可能存在管理上的差异
分层式结构OS
有序分层法
优
保证系统正确性
易扩充和易维护性
缺
通信开销大、系统效率低
传统操作系统结构
微内核OS结构
提高正确性、灵活性、易维护性和可扩充性
基本概念
足够小的内核
与硬件处理紧密相关的部分
一些较基本的功能
客户和服务器之间的通信
基于C/S模式
将操作系统中最基本的部分放入内核 而把绝大部分功能放在内核外的一组服务器（进程）中实现 运行在用户态，通过微内核提供的消息传递机制来实现信息交互
机制与策略分离
机制
实现某一功能的具体执行机构（放在内核中）
策略
在机制的基础上借助于某些参数和算法来实现该功能的优化 或达到不同的功能目标
采用面向对象技术
抽象、隐蔽、对象、封装等等
基本功能
进程管理
微内核：进程调度
管理服务器：调度策略
低级存储器管理
微内核：地址映射
存储管理服务器：虚拟存储管理
中断和陷入处理
微内核：响应中断
服务器：处理中断
优
提高了系统可扩展性
增强系统可靠性
消息传递机制，服务器错误不会蔓延
可移植性
内核负责硬件，服务器硬件无关
支持分布式
进程可以在任何机器上
采用面向对象技术
缺
效率降低：C/S模式带来更多上下文切换，传统OS一般只有两次
现代结构的OS
操作系统的硬件环境
受保护的指令（特权指令）
管态（内核态）
目态（用户态）
对资源和指令的使用权限划分处理机状态
X86举例，R0-R3特权环
程序状态字PSW
CPU判断当前运行的程序是系统程序还是用户程序 通过修改PSW可以实现管态/目态之间的转换
CPU的工作状态码（管态还是目态）
条件码
反映指令执行后的结果特征
中断屏蔽码
指出是否允许中断
系统调用
CPU执行访管指令，引起访管中断
CPU保存上下文环境，切换到管态
中断处理程序工作，调用系统服务
中断处理结束，恢复上下文环境，CPU恢复为目态，继续执行
内存保护
基址寄存器（存基址）
边界寄存器（存边界）
界限寄存器
地址映射
硬件提供虚、实地址映射的机制
中断（interrupt）机制
某个可以改变正在CPU上执行的指令的顺序的事件 对应于CPU芯片内部或外部的硬件电路所生成的电信号
中断处理：暂停、保留现场--中断处理--返回断点、继续执行
中断类型
同步中断
由CPU控制单元所发出的中断，也称为“异常”
CPU检测到的异常
程序设定的异常
软中断
异步中断
由其他的硬件设备在任意的时刻所发出的中断，简称为“中断”
可屏蔽中断
不可屏蔽中断
中断向量
每个中断都用一个0-255之间的整数来标识 系统根据中断向量来为中断指定相应的处理程序
I/O操作系统
完成信息的输入输出功能
时钟操作
分时系统：时间片轮转
实时系统：按要求的间隔输出正确的事件信号给实时的控制设备
记录用户和系统所需的绝对时间
操作系统的基本服务
用户界面
程序执行
I/O操作
文件系统操作
通信（进程，网络）
错误检测
资源分配
统计
保护和安全
进程的描述与控制
基本概念
前驱图（Precedence Graph）
描述进程之间执行的前后关系 必须为DAG
前驱关系：在x开始执行之前y必须完成
初始结点（Initial Node）：没有前驱
终止结点（Final Node）：没有后继
程序执行
程序是指令或语句序列
顺序执行
程序各部分（程序段或指令）依次顺序执行 当前操作完成后才能执行其后继操作
顺序性
严格依次运行指令
封闭性
独占全机资源
执行结果不受外界影响
可再现性
运行结果与程序执行速度无关，初态相同、结果相同
并发执行
一组逻辑上相互独立的程序或程序段在执行过程中 其执行时间在客观上互相重叠 提高资源利用率--提高系统效率
间断性
等待资源或程序间相互制约
失去封闭性
资源共享，不再是独占
不可在现性
由上两点导致
进程
程序
无法描述执行过程的随机性、并发性 无法反映资源共享
顺序性
静态性
孤立性
进程
提出
刻画系统的动态性
解决共享性
描述程序的动态执行过程和使用共享资源的基本单位
特征
结构性
程序、数据集和PCB
动态性
进程是程序在数据集合上的一次执行过程，具有生命周期
并发性
多进程实体同存内存，在一段时间内同时执行
进程的执行可被打断
独立性
资源分配的基本单位
独立运行的基本单位
异步性
进程独立地按不可预知的速度推进
程序与进程的区别
静态&动态
程序是有序代码的集合 进程是程序的执行
程序长久保存，进程是暂时的
进程可并发，程序不可
组成结构不同
一个程序多次执行可对应多个进程
进程是系统资源分配的基本单位
进程的状态
三种基本状态及转换
运行态（Running）
就绪态（Ready）
就绪队列
等待态（阻塞/睡眠）
即指CPU空闲，该进程也不可运行
阻塞队列
其他状态
满足完整性要求以及增强管理的灵活性
创建状态（new）
申请空白PCB，填写信息，申请资源，转入就绪队列
创建完成后才能被调度
完整性
系统可控制创建进程的提交，控制系统内进程数量和系统负载
灵活性
终止状态（exit）
不再有执行资格
回收除PCB之外的其他资源，让其他进程从PCB收集信息
信息不再被需要，进程被删除（包括将PCB清零）
引入挂起（Suspend）操作
引入目的
终端用户的请求
调试程序的需要，在挂起时读写地址空间
父进程的请求
考察修改或协调各子进程
负荷调节的需要
实时系统负荷重时挂起不重要进程
换出等待进程以满足就绪进程的资源要求
操作系统的需要
挂起进程以检查系统资源使用情况
新增进程状态
挂起（静止）状态
静止就绪
不再被调度执行
静止阻塞
当进程期待的事件出现后，进入静止就绪
非挂起（活动）状态
活动就绪
活动阻塞
新增状态转换
进程管理中的数据结构
进程的静态描述：程序段+数据集+PCB
操作系统中用于管理控制的数据结构
内存表
设备表
文件表
进程表（PCB）
PCB的作用
PCB是系统感知进程存在的唯一标志 进程与PCB一一对应 通过系统调用访问
作为独立运行基本单位的标志
能实现间断性运行方式
提供进程管理所需要的信息
提供进程调度所需要的信息
实现与其它进程的同步与通信
PCB中的信息
进程标识符
外部标识符
方便用户（进程）对进程的访问，由创建者提供
内部标识符
方便系统对进程的使用，唯一，通常是一个整数
处理机状态
处理机的上下文
通用寄存器
用户可视寄存器
指令计数器
程序状态字PSW
用户堆栈指针
进程调度信息
进程当前状态
优先级
调度所需其他信息
事件（阻塞原因）
进程控制信息
程序和数据的地址
进程同步和通信机制
资源清单
链接指针
指向本进程所在队列的下一个进程的PCB首地址
PCB的组织方式
PCB表 表的大小决定系统的并发度
线性方式
所有PCB组成线性表
链接方式
将具有相同状态的进程通过PCB链接指针链接成队列
就绪队列、阻塞队列、空白队列等
索引方式
根据进程的不同状态建立索引表，表中存PCB对应PCB表中的地址
进程控制
处理机管理 协调执行并发进程 实现资源共享 进程控制程序段采用原语形式
操作系统内核
支撑功能
中断处理
时钟管理
原语（primitive）操作
原子操作
机器指令级
功能级：作为原语的程序段不允许并发执行
资源管理功能
进程管理
存储器管理
设备管理
进程创建
进程图：描述进程家族关系的有向树
引起创建进程的事件
用户登录
作业调度
提供服务
应用请求
应用进程自己创建新进程
创建原语Creat
申请空白PCB，获得统一进程标识符
分配资源
初始化PCB
标志信息
处理机状态
处理机控制信息
...
设置链接（如是否插入就绪队列）
进程终止
引起终止的事件
正常结束
异常结束（进程内部错误）
外界干预
操作员/操作系统
父进程的干预
终止原语
根据标识符检索PCB、读出进程状态
若仍在执行，则终止该进程的执行，修改调度标志
递归终止子孙进程
将资源归还原处
将终止进程PCB移除队列等待其他程序收集信息
进程的阻塞和唤醒
引起阻塞/唤醒的事件
请求系统服务未果
启动某操作，操作未完成前
新数据尚未到达
当前工作完成，无新工作可做
阻塞原语block
停止执行
修改PCB插入阻塞队列
重新调度，切换处理机
唤醒原语wakeup
移出阻塞队列
修改PCB进入就绪队列
挂起与激活
挂起
引起挂起的事件
自己挂起
被父进程挂起
被系统挂起
挂起原语suspend
若在执行：转向调度程序重新调度
活动就绪->静止就绪
活动阻塞->静止阻塞
激活
引起激活的事件
父进程或用户进程指定激活
内存空间足够
激起原语activate
从外存调入内存
静止就绪->活动就绪
抢占式调度还需要检查优先级 判断是否需要重新调度
静止阻塞->活动阻塞
进程同步
进程同步机制使具有异步性的进程按先序关系执行 共享资源，相互合作，使程序的执行具有可再现性
基本概念
制约关系
间接相互制约关系
源于共享资源
直接相互制约关系
源于相互合作
临界资源（critical resource）
互斥方式使用
临界区（critical section）
访问临界资源的代码
进入区-临界区-退出区
进入区检查欲访问的临界变量是否可访问 退出区将临界区访问的标志恢复为未被访问
同步机制规则
空闲让进
忙则等待
有限等待
等待时间有限（不死等）
逗留时间有限
让权等待
不能进入临界区则释放处理机，不允许忙等
硬件同步机制
为标志看成锁 测试和关锁的操作必须是连续的，不允许分开
关中断
进入锁测试之前关闭中断，直到完成测试并上锁后再开启
不会引起进程调度，没有进程切换
缺点
滥用中断可能导致严重后果
关中断时间过长，影响效率
关中断不适用于多CPU系统
TSL指令
测试并建立指令：Test-and-Set TSL RX, LOCK （读入内存变量LOCK的值，保存在寄存器RX中，将非零值存到LOCK中）
每轮都尝试加锁，循环测试直到成功加上锁
Swap指令
key初值为ture，对换lock和key的值，指导key为false说明可以进入临界区
信号量机制
整型信号量
记录型信号量
AND型信号量
信号量集
信号量的应用
共享资源互斥访问
控制进程的前驱关系
管程机制
管程定义
进程通过调用管程、间接访问共享资源
模块化
抽象数据类型
信息掩蔽
管程与进程的区别
条件变量
wait后释放管程，以便其他进程调用
经典进程的同步问题
生产者-消费者
mutex/empty/full
哲学家进餐
解决死锁
读者-写者
rmutex/wmtex，由读者控制写者wmutex
进程通信
进程通信的类型
共享存储器系统
共享数据结构
低级通信
状态或值
共享存储区
管道通信系统
互斥
同步
确定对方是否存在
消息传递系统
直接通信
间接通信（信箱）
C/S系统
嵌套字
远程过程调用/远程方法调用
消息传递通信的实现
直接消息传递（利用原语）
信箱通信
私用
公用
共享
直接消息传递的实现
建立链路
消息格式
定长
变长
进程的同步方式
线程
线程的基本概念
减少程序在并发执行时所付出的时空开销
引入线程
进程的两个基本属性
资源分配的基本单位
调度的基本单位
抽象出线程的概念
进程的时空开销
创建进程
撤销进程
进程切换
将线程作为调度的基本单位
线程与进程
调度性
并发性
拥有资源
独立性
系统开销
支持多处理机系统
进程可以同时运行在不同的处理机上
线程的状态与TCB
多线程OS中的进程属性
进程是一个可拥有资源的基本单位
多个线程并发执行
进程已不是可执行实体
线程的实现
线程的实现方式
内核支持线程
所有线程由内核管理
优
同进程多线程并行
线程被阻塞，进程不一定阻塞
KST数据量小，切换线程开销小
内核也可多线程，提高速度
缺
切换线程需要换模式此开销较大
用户级线程
用户程序自己管理线程，内核不知道线程的存在
优
切换线程不需要换模式
进程自定调度算法
OS平台无关
缺
线程阻塞、进程阻塞
不能利用多处理机加速进程执行
KST+ULT组合方式
多对一
一对一
多对多
线程的实现
内核支持线程的实现
每个进程，任务数据区PTDA
用户级多线程的实现
借助中间系统完成系统调用
运行时系统
驻留在用户空间作为接口
内核控制线程
用户级线程-LWP（轻型进程）-内核级线程
LWP线程池
线程的创建和终止
初始化线程的概念
处理机调度与死锁
处理机调度
处理机调度的层次与调度算法的目标
处理机调度层次
高级调度【作业调度/长程调度】
主要用于多道批处理系统中
中级调度【内存调度/中程调度】
低级调度【进程调度/短程调度】
即对换（swap）
处理机调度算法的目标
共同目标
资源利用率
CPU：有效工作时间/（有效工作时间+等待时间）
公平性
平衡性
策略强制执行
比如安全策略
批处理系统
平均周转时间短
平均周转时间：周转时间平均值
周转时间：完成时间-提交时间
带权周转时间
周转时间/服务时间
系统吞吐量高
单位时间内完成的作业数
处理机利用率高
分时系统
响应时间快
均衡性
系统响应时间快慢与服务复杂性相适应
实时系统
截止时间的保证
可预测性
如多媒体系统
作业与作业调度
用于多道批处理系统中
作业和作业步
作业控制块JCB
作业在系统中存在的标志
作业运行的三个阶段/状态
收容状态
尚未调入内存前，还在作业后备队列中
运行状态
终止状态
作业调度（接纳调度）的主要任务
接纳多少作业【多道程序度】
接纳哪些作业【调度算法】
作业调度算法
先来先服务FCFS
短作业优先SJF
需要预知运行时间
不利于长作业
无法实现人机交互
未考虑作业的紧迫程度
优先级调度算法PSA
基于作业的紧迫程度
高响应比优先HRRN
同时考虑作业运行时间和等待时间
优先权=（等待时间+要求服务时间）/要求服务时间
计算优先权将增加系统开销
进程调度
进程调度相关概念
任务
保存处理机现场信息
按调度算法选取进程
把处理机分配给进程
机制
排队器
分派器
上下文切换器
第一次：保存现场，装入分派程序上下文
第二次：移除分派程序，装入新选进程上下文
方式
非抢占式
一般不适用于分时和实时系统
抢占式
常见原则
优先权原则
短进程优先原则
时间片原则
轮转RR调度算法
常见于分时系统
时间片略大于一次典型的交互所需的时间
优先级调度算法
非抢占式
抢占式
见于实时性较高的系统
静态优先级
动态优先级
多队列调度算法
不同队列不同调度算法
不同队列不同优先级
多级反馈队列调度算法
不必预先知道各进程所需的时间
原理
设置多个就绪队列
每个队列都采用FCFS，最后一个采用RR
按队列优先级调度，前面的队列空了才能调后面的
性能
终端用户
短批处理作业用户
长批处理作业用户
基于公平原则的调度算法
保证调度算法
性能公平
公平分享算法
使用户获得相同的处理机时间
实时调度
实时调度基本条件
提供必要信息
系统处理能力：满足可调度条件
采用抢占式调度机制
具有快速切换机制
快速响应中断
快速任务分派
实时调度算法分类
非抢占式式
轮转调度
优先调度
抢占式
基于时钟中断的抢占式优先级调度
立即抢占的优先级调度
最早截止时间优先EDF
任务的截止时间越早，优先级越高
最低松弛度优先LLF
松弛度=必须完成时间-还需运行时间-当前时间
类似于数据结构中的学过的关键路径起讫时间计算
优先级倒置问题
形成
优先级低的进程与优先级高的进程间存在共享变量
解决方法
进入临界区后进程处理机不能被抢占
动态优先级继承
死锁
死锁概述
资源分类
可重用性资源
打印机
消耗性资源
进程间的通信消息
可抢占资源
CPU/主存
不可抢占资源
打印机/磁带机
引起死锁的原因
竞争不可抢占性资源
资源分配图存在环路
竞争可消耗资源
都在等其他进程的消息
进程推进顺序不当
不安全状态
死锁定义
Deadlock
一组进程中的每个进程都在等待仅由该组中其他进程引起的事件
产生死锁的必要条件
互斥条件
请求与保持条件
不可抢占条件
循环等待条件
处理死锁的方法
死锁预防
破坏死锁的必要条件
死锁避免
防止进入不安全状态
死锁检测
死锁解除
预防死锁
破坏请求-保持条件
一次性申请资源
分块申请资源并释放
破环不可抢占条件
没请求到资源就释放已有的资源
破坏循环等待条件
设置静态资源序号，从低到高请求
静态不便扩展、浪费、限制编程自由
避免死锁
数据结构
Available
Max
Allocation
Need
银行家算法
Request大于Need->出错
Request大于Available->出错
尝试分配-安全性测试
安全则分配，不安全则拒绝
安全性算法
Work（可用资源）和Finish（进程是否完成）
找到可完成的进程，直到找不到这样的进程
进程都完成了才是安全的，否则不安全
死锁的检测与解除
可行性：死锁不常出现时
死锁检测
死锁定理：资源分配图不可完全简化
找到不阻塞又不独立的结点，删除出边和入边
算法：类银行家算法
死锁解除
抢占资源
终止进程
终止所有死锁进程
逐个终止进程
付出最小代价的死锁解除算法（全局最优解）
使用贪心法每次找局部最小代价进程终止
处理机管理功能
存储器管理
存储器的层次结构
CPU寄存器
高速缓存
主存储器（内存）
磁盘缓存
主存储器中的一部分
可执行存储器
固定磁盘
可移动存储介质
程序的装入与链接
编译
链接
静态链接
装之前打包成整体模块
装入时动态链接
边装入边链接
便于修改和共享模块
运行时动态链接
用的时候再装入和链接
装入
绝对装入方式
可重定位装入方式
静态重定位
动态运行时的装入方式
存在对换
重定位寄存器
连续分配存储管理方式
单一连续分配
固定分区分配
用于控制多个相同对象的控制系统中
分区大小相等
分区大小不等
分区使用表
动态分区分配（可变分区分配）
数据结构
空闲分区表
空闲分区链
算法
基于顺序搜索
首次适应FF
每次从低址开始找到满足条件的
低址碎片多，高位有连续大空间
循环首次适应NF
从上一次分配的的地方向后寻找
最佳适应BF
找到大小最相近的，需要排序遍历
最坏适应WF
与BF相反，排序找到最大的切割分配
基于索引搜索
快速适应算法（分类搜索法）
按分区大小分类，一次分配一整个 缺点：存在浪费
预先划好分区
伙伴系统
以2的幂次切割区域，先找空闲分区，没有则切割大分区
哈希算法（普遍采用）
构造一张以空闲分区大小为关键字的哈希表
分配与回收
分配：分配后剩余分区≥阈值
回收
若相邻则合并分区
新建表项
动态可重定位分区分配
紧凑
动态重定位
运行时动态链接+重定位寄存器
硬件支持
算法：相较动态分区分配多了一个紧凑功能
对换（swapping）
引入
类型
整体对换（进程对换）
页面（分段）对换
实现虚拟存储器功能
对换空间的管理
采用连续分配方式，与动态分区分配类似
内存紧张时才启用换出
进程的换出
选择被换出的进程
首选阻塞或睡眠
可能考虑进程已在内存中的驻留时间
换出
只能换出非共享的程序和数据段
先申请对换空间
进程的换入
就绪且换出的进程
分页存储管理方式
提高内存利用率
基本原理
页面与物理块（页框）一一对应
将进程的逻辑地址按固定页面大小分页 最后一页可能存在页内碎片
地址结构：页号+页内地址
页表
每个进程都有自己的页表
地址变换机构
页表寄存器
快表
可能放在cache中
高速
并行
存放当前访问的页表项
首先访问快表
访问内存的有效时间
一般访问一到两次内存
快表命中率
两级页表和多级页表
为页表分页 只将需要的部分页表项调入内存
两级页表
外层页表
页表
多级页表
反置页表
按物理块号进行排序，查找页表时直接对应物理块号 只对调入内存的页表提供检索
分段存储管理方式
引入
便于编程
信息共享
信息保护
动态增长
动态链接
原理
分段：段号+段内地址
段表：段号+段长
段长不固定
地址变换机构
其他概念
分页与分段的区别
页是物理单位，段是逻辑单位
页的大小固定，段的大小不等
分页的用户程序地址是一维的，分段的地址是二维的
信息共享
页表有多项，段表项目数更少
可重入代码
允许多个进程同时访问 不允许进程对它进行修改
段页式存储管理
原理：段号+段内页号+页内地址
地址变换机构需要三次访问内存
离散分配方式
虚拟存储器
从逻辑上扩容
概述
传统存储管理方式和程序局部性
传统存储器
一次性
驻留性
局部性原理
时间局限性
空间局限性
虚拟存储器的工作
部分调入
缺页（段）中断
置换
虚拟存储器特征
具有请求调入和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统 运行速度接近于内存，每位成本接近于外存
多次性
对换性
在离散分配的基础上
虚拟性
虚拟存储器实现
分页请求系统
分段请求系统
请求分页存储管理方式
调入调出长度固定
硬件支持
请求页表机制
状态位（存在位）P
访问字段A
修改位M
缺页中断机构
在指令执行期间产生和处理
一条指令执行期间可能产生多次中断
地址转换机构
内存分配
最小物理块数
能保证进程正常执行的最小的物理块数
分配策略
固定分配局部置换
可变分配全局置换
可变分配局部置换
分配算法
平均分配算法
按比例（进程页数）分配算法
必须大于最小物理块数
考虑优先权的分配算法
页面调入策略
何时调入
预调页策略
工作集
请求调页策略
何处调入
文件区
对换区
如何调入
换出的如有修改需要写回
页面置换算法
最佳置换算法
将来最久才会被使用的
先进先出FIFO置换算法
最近最久未使用LRU算法
每次查找，t值++，选取t最大的
寄存器计数或栈结构存放
最少使用LFU算法
按频率，最高位置1再右移，取求和值最小的
Clock置换算法
最多两轮遍历，找未访问的
改进Clock算法
最多四轮遍历，找未访问，最好也未修改的
第一轮不修改访问位，第二轮才修改
A=0，M=0
A=0，M=1
A=1，M=0
A=1，M=1
页面缓冲算法PBA
多页修改，一次写入
空闲页面链表
修改页面链表
访问内存时间计算EAT
注意计算更新快表的时间
“抖动”与工作集
多道程序度与处理机利用率
出现抖动，利用率随多道程序度上升而大幅下降
抖动的产生原因
物理块数不够，频繁缺页
工作集
窗口尺寸
在过去一段时间内访问的页面（窗口尺寸范围内）
抖动的预防
局部置换
将工作集融入处理机调度
L=S
L：平均缺页时间
S：缺页处理时间
选择暂停进程
请求分段存储管理方式
硬件支持
段表机制
增补位：本段是否在运行过程中有过动态增长
缺段中断机构
对换之前紧凑技术的使用
地址转换机构
分段的共享与保护
共享段表
共享进程计数count
存取控制字段
段号
分配
第一个请求进程，分配内存，填自己的段表，填共享段表
回收
count=0，由系统回收内存
分段保护
越界检查
存取控制检查
环保护机构
内环调外环数据
外环调内环服务
存储器管理功能
内存管理
输入输出系统
I/O系统的功能、模型和接口
I/O系统基本功能
隐藏物理设备细节
与设备无关性
提高处理机和I/O设备利用率
对I/O设备进行控制
确保对设备的正确共享
错误处理
临时性错误
持久性错误
I/O系统的层次
设备独立性软件
设备驱动程序
中断处理程序
I/O系统接口
块设备接口
块设备
磁盘
隐藏磁盘二维结构
将抽象命令映射为低层操作
流设备（字符设备）接口
字符设备
get和put操作
in-control指令
网络通信接口
I/O设备和设备控制器
I/O设备：执行操作的机械部分 I/O设备控制器：执行控制的电子部件
I/O设备
分类
按使用特性
存储设备
I/O设备
按传输速率
低速设备
中速设备
高速设备
按传输单位
块设备
字符设备
与控制器接口
数据信号线
状态信号线
控制信号线
设备控制器
控制一个或多个I/O设备
基本功能
接受和识别命令
数据交换
标识和报告设备的状态
地址识别
地址译码器
数据缓冲
差错检测
组成
设备控制器与处理机的接口
设备控制器与设备的接口
I/O逻辑
内存映像
利用特定的I/O指令（独立编址）
内存映像I/O（统一编址）
混合编址
独立编址寄存器
统一编址数据缓冲区
I/O通道
是一种特殊的处理机 指令单一 没有自己的内存（共享主机内存）
引入
类型
字符多路通道
传输单位字节
多通道时间片轮转
数组选择通道
共享一个通道
传输单位为块
数组多路通道
传输单位为块
多通道时间片轮转
瓶颈
增加【通路】数
中断机构和中断处理程序
中断
分类
外中断：中断
内中断：陷入
中断向量表 & 中断优先级
多源中断处理方式
屏蔽（禁止）中断
一个一个顺序处理
嵌套中断
递归处理优先级较高的中断
中断处理程序
检测是否有未响应的中断
保护CPU现场
转入相应的设备处理程序
处理中断
恢复CPU现场，并退出中断
屏蔽中断
中断嵌套
返回原进程
设备驱动程序（设备处理程序）
一类设备一个
概述
功能
接受由与设备无关软件发来的命令
检查用户I/O合法性
发出I/O命令
响应中断
特点
沟通与设备无关的软件和设备控制器
与硬件特性相关
与I/O设备采用的I/O控制方式相关
部分固化
可重入
提供并发性
设备处理方式
一类设备一个进程
所有设备一个进程
不设进程
处理过程
启动I/O操作后会自我阻塞，直至中断到来被唤醒
将抽象要求转换为具体要求
对服务请求进行校验
检查设备状态
状态寄存器
传送必要参数
命令寄存器
方式寄存器
启动I/O设备
对I/O设备控制方式
轮询
极大浪费CPU
中断
一字一传
DMA（直接存储器存取）
传输单位为块
直接与内存传输
CPU只在开始和结束几个块干预
I/O通道控制方式
是DMA的发展 对一个数据块的干预减少为对一组数据块的干预 提高并行性
与设备无关的I/O软件
基本概念
物理设备名使用不灵活，引入逻辑设备名
与设备无关的软件包括
设备驱动程序的统一接口
缓冲管理
差错控制
暂时性错误由驱动程序处理
对独立设备的分配与回收
提供大小统一的逻辑数据块
设备分配
数据结构
设备控制表
控制器控制表
通道控制表
系统设备表
设备分配考虑的因素
设备的固有属性
独占设备
共享设备
虚拟设备
分配算法
先来先服务FCFS
优先级高者优先PF
安全性
安全分配
进程发出I/O就自我阻塞
CPU与I/O顺序工作
不安全分配
进程发出I/O还继续运行
加速推进
分配流程
设备->控制器->通道
以逻辑设备名提出I/O请求
逻辑设备名与物理设备名映射
逻辑设备表LUT
整个系统只设一张LUT
逻辑设备名-物理设备名-驱动程序入口地址
为每个用户设置一张LUT
逻辑设备名-系统设备表指针
用户层的I/O软件
系统调用与库函数
假脱机（Spooling）系统
假脱机技术
设备虚拟
SPOOLing组成
井管理系统
输入井与输出井
输入程序与输出程序
输入缓冲区与输出缓冲区
SPOOLing系统特点
提高I/O速度
独占设备可共享
实现虚拟设备功能
假脱机打印机系统
磁盘缓冲区
打印缓冲区
假脱机管理进程和假脱机打印进程
守护进程
假脱机文件队列
缓冲区管理
引入原因
速度不匹配
粒度不匹配
减少CPU中断次数
提高并行性
单缓冲区
单工
双缓冲区
双工
环形缓冲区
Nexti与Nextg两指针互相追上时，说明需要阻塞对应进程（计算进程/输入进程）
缓冲池
包含了管理数据结构和管理机制 管理多个缓冲区
空白缓冲队列
输入队列
输出队列
磁盘存储器的性能和调度
磁盘性能简述
磁盘数据的组织和格式
盘面-磁道-扇区（盘块）
磁盘的类型
固定头磁盘
移动头磁盘
磁盘访问时间
寻道时间
旋转延迟时间
传输时间
磁盘调度算法
早期
先来先服务FCFS
平均寻道距离较大
最短寻道时间优先SSTF
距离最近的优先级最高
基于扫描
扫描SCAN算法
避免饥饿，电梯调度算法
循环扫描CSCAN算法
减少最大等待时间，单向扫描
NStepSCAN
避免磁臂黏着
子队列间FCFS，子队列内SCAN
子队列长度为N
FSCAN
NStepSCAN简化，只分两个队列
正在调度的队列
等待队列
设备管理功能
文件管理
文件和文件系统
文件组成
数据项
基本数据项
组合数据项
记录
数据项的有序集合 关键字-key
定长记录
不定长记录
文件
文件类型
有结构文件
记录
无结构文件
字符流
文件长度
文件的物理位置
文件的建立时间
文件类型和文件名
文件名
文件名
扩展名
文件类型
按用途分
系统文件
用户文件
库文件
按数据形式分
源文件
目标文件obj
可执行文件.exe
按存取控制属性分
只执行文件
只读文件
读写文件
按组织形式和处理方式分
普通文件
目录文件
特殊文件
文件系统的层次结构
对象及其属性
文件
目录
磁盘存储空间
对对象操纵和管理的软件集合
I/O控制层
基本文件系统层
基本I/O管理程序
逻辑文件系统
文件系统接口
命令接口
提供给用户
程序接口
通过系统调用使用
文件操作
文件的打开
内存中的打开文件表
对文件属性的操作
有关目录的操作
文件的逻辑结构
文件逻辑结构-文件组织 文件物理结构-存储结构
文件逻辑结构分类
1. 检索效率 2. 存储效率 3. 便于修改
结构
有结构文件
无结构文件
组织
顺序文件
索引文件
索引顺序文件
一组文件一个索引
顺序文件
排列方式
串结构
顺序结构
随机存取
优缺点
批量存取时，存取效率高
修改、删增不便
运行记录文件（事务文件）
记录寻址
隐式寻址
读指针自增到下一记录处
显式寻址
支持机构
计算文件中记录的位置
利用关键字
索引文件
将不定长记录统一为定长记录进行检索
多个索引表
增加了存储开销
顺序索引文件
分组，为顺序文件建索引表
文件索引表
对索引顺序文件的随机访问
溢出文件
记录增删改的记录
直接文件
哈希
文件目录
文件控制块的有序集合
目录管理要求
按名存取
提高检索速度
文件共享
允许重命名
文件控制块FCB
基本信息
文件名
物理位置
逻辑结构
物理结构
存取控制信息
存取权限等
使用信息
建立时间、修改时间等
索引结点
为减少启动磁盘次数（为目录块减重）
每个目录项：文件名-索引结点指针
磁盘索引结点
存放在磁盘上的索引结点
文件类型、连接计数、权限等
内存索引结点
存放在内存中的索引结点
访问计数、索引结点编号等
简单文件目录
单级目录结构
查找速度慢
不允许重名
不便共享
两级文件目录（系统+用户）
提高了检索速度
允许不同用户的文件重名
无法共享文件
树形文件目录
目录查询技术
线性检索法（顺序）
按路径读目录
Hash方法
目录表相应表项与文件名不匹配时，Hash值加上一个常数再查找
文件共享
基于DAG实现共享
文件目录中存放索引结点的指针
基于符号链接实现共享
新建LINK文件，其中存放符号链（路径名）
优点：不会因删除文件产生悬空指针
问题：多次读盘；增加存储开销；遍历文件系统拷贝时会有多份
文件保护
影响文件安全性
人为因素
存取控制机制
系统因素
系统容错技术
自然因素
建立后备系统
文件备份
批量备份
全量转储
增量转储
同步备份
镜像备份
对镜像磁盘施以相同的操作
双机动态文件备份
把写操作分派给两台机器，两机器对称工作
文件访问保护
口令保护
加密保护
访问控制
访问权
进程 对 对象 的访问权
R
W
E
保护域
访问权的集合
静态域
动态域-随进程运行阶段不同，保护域也不同
保护域切换功能
访问矩阵
访问矩阵的修改
拷贝权
所有权
控制权
访问控制表
按列划分访问矩阵 每个对象在不同域中的被访问权
访问权限表
按行划分访问矩阵 每个域对对象的访问权
文件管理功能
外存管理
磁盘存储器的管理
外存的组织方式
连续组织方式
目录中存放文件的起始盘块号和总盘块个数
优点
顺序访问容易
顺序访问快
缺点
需要分配连续空间
容易产生外存碎片
需要事先预估文件大小
不能灵活地删除和插入
无法良好处理动态增长的文件
链接组织方式
概念
隐式链接
盘块里放链接
显示链接
统一放在链接表中
优点
离散分配，消除磁盘外部碎片
对插入、删除和修改记录都容易
能使用动态增长
举例
FAT
File Allocation Table
FAT X：X代表FAT表项的位数
文件FCB中放第一个盘块的序号，之后每个盘块表项放下一个盘块序号
以簇为单位进行分配（簇含多个块）
NTFS
New Technology File System
特征
64位磁盘地址
支持长文件名
具有系统容错功能
保证数据一致性
磁盘组织
以簇为单位进行分配与回收
逻辑簇号LCN
虚拟簇号VCN
文件的组织
主控文件表MFT
索引组织方式
每个文件一个索引块 解决FAT：直接存取 && 占内存空间大的问题
单级索引组织方式
多级索引组织方式
增量式索引组织方式
文件存储空间的管理
空闲表和空闲链表
空闲表
类似内存的动态分配
空闲链表
空闲盘块链
空闲盘区链
位示图法
位示图
二维01数组
分配
查图、找空盘块
计算盘块号：b=n(i-1)+j
修改位示图
回收
计算盘块号
修改位示图
成组链接法
空闲盘块号栈
提高磁盘I/O速度的途径
文件访问速度的三个方面
对目录的查找时间
文件的存储结构->对文件的访问速度
提高磁盘的I/O速度
提高磁盘的I/O速度
磁盘高速缓存
在内存中为磁盘盘块设置一个缓冲区
数据交付方式
数据交付
指针交付
置换算法
周期性写回磁盘
LRU链，周期性写回磁盘
防止发生数据不一致现象
提高磁盘I/O速度的其他方法
提前读
延迟写
优化物理块分布
虚拟盘
廉价磁盘冗余阵列RAID
并行交叉存取
RAID分级
RAID优点
可靠性
I/O速度
性价比高
提高磁盘可靠性的技术
第一级容错技术
第二级容错技术
基于集群技术的容错技术
后备系统
数据一致性控制
事务
检查点
并发控制
操作系统接口（自学）