亿图脑图MindMaster计算机操作系统思维导图
导图社区 计算机操作系统思维导图
- 相似推荐
- 大纲
操作系统
第一章概述
基本概念
控制和管理整个计算机系统的硬件和软件资源，合理组织，调度计算机的工作与资源分配，为用户提供方便接口与环境的程序集合
特征
并发
多个事件在同一个时间间隔里发生
与并行不同 并行是在同一个时刻里并行
共享
互斥共享
规定时间内只允许一个进程访问资源
只有在进程访问完并且释放资源后，另一个进程才可以对此资源访问
临界资源
一段时间内只允许一个进程访问
如：物理设备，栈，变量，表格等
同时访问
允许一段时间内由多个进程“同时”访问
同时是宏观上的同时， 在微观上它们可能是交替地访问资源（分时共享）
资源共享是以程序的并发为条件的，若不允许程序并发，则不存在资源共享
两大基本特征
虚拟
实体变为逻辑上的对应物
通过多道程序并发执行
利用多道程序设计技术把一个物理CPU分为多个逻辑上的CPU
虚拟技术
时分复用技术
分时共享
空分复用技术
虚拟存储
异步
进程执行不是一步到位的，是走走停停的，因为资源有限
操作系统作为用户和计算机硬件系统的接口
用户使用计算机的方式
1）命令接口
通过命令解释器
shell命令解析器也属于命令接口
联机命令接口
适用于分时，实时系统
强调用户的交互性
脱机命令接口
无需人工操作
用于批处理系统
连同预先准备好的作业一起交给系统，到调度作业时，系统的命令解释程序控制执行
2）程序接口
由系统调用组成
利用系统调用请求操作系统为其提供服务
操作系统不提供系统缓存的系统调用，缓存对用户是透明的
发展历程
1）手工操作阶段
此时没有操作系统，所有工作由人工完成
2）批处理阶段
单道批处理系统
1）顺序性
2）自动性
3）单道性
内存仅有一道程序执行
多道批处理系统
通过多道程序设计技术
多个程序同时进入内存，在CPU内交替进行
共享硬/软件
一道程序因IO而暂停运行时，CPU便立即运行另一道程序
通过中断
优点
1）多道
2）宏观并行
3）微观串行
4）利用率高，吞吐量大
缺点：响应时间长，不提供人工交互，不能控制计算机
3）分时操作系统
多个用户通过终端同时共享一台主机
通过时间片轮转方式
实现人机交互
1）同时性
2）交互性
3）独立性
多用户独立操作，互不干扰
4）及时性
很短时间内获得响应
4）实时操作系统
在某个限制时间内完成紧急任务（抢占式高优先级任务）， 不需要时间片排队
5）网络操作系统与分布式计算机系统
网络操作系统
各台计算机有机结合
分布式计算机系统
每台计算机有同等地位
6）个人计算机操作系统
win，Linux，Mac OS
运行环境
处理机运行模式
1）特权指令
不允许用户直接使用的指令
IO指令，置中断指令，送状态字，存寄存器，置时钟
只能在内核态执行
2）非特权指令
允许用户直接使用的指令
不能直接访问系统的软硬件资源
只允许访问用户地址空间
系统调用
陷入指令（trap）又称访管指令，用来发起系统调用，请求系统提供服务
是在用户态使用的， 所以不属于特权指令
程序运行在用户态
内核程序运行在内核态
切换到用户态的指令是特权指令
应用程序向操作系统请求服务通过访管指令，产生中断事件转换操作系统为内核态
广义指令（系统调用命令）的执行过程一定在内核态， 而它的调用有可能在用户态也可能在内核态
用户态切换到内核态必定通过中断
只要发生中断，必然会切换到内核态
子程序调用
只保存断点
下一条指令地址
用户态→核心态
例子
请求系统服务
发生中断
用户程序发生错误
用户程序想要执行特权指令
用户态到核心态的转化由硬件完成
必定会通过中断实现
只要发生中断，就要对其处理，也必定会转化到内核态
用户态进入核心态，不仅状态切换，堆栈也会转换为系统堆栈
时钟管理
通过时钟中断的管理，实现进程切换
时钟中断
处理和时间有关的信息，决定是否执行调度程序
系统时间，时间片，延时，使用CPU的时间，定时器等
中断和异常
中断 （外中断）
操作系统不能没有中断
只有小部分功能属于内核，保护和恢复中断现场信息， 转移控制权至相关处理程序
保存的数据
硬件保存
PC
状态字PSW
操作系统保存
通用寄存器x
异常 （内中断）
非法操作码，地址越界，溢出，缺页，自陷等
系统调用，访管指令
异常不能被屏蔽，一旦出现立即处理
原语
是一种程序
1）处于操作系统最底层
2）程序运行具有原子性
3）程序运行时间短，调用频繁
4）内核的组成部分
管理方式
设备管理
进程管理
存储器管理
操作系统结构
分层法
各层定义比较困难
模块化
模块间接口很难满足实际需求
宏内核
主要功能模块都作为一个紧密联系的整体运行在内核态
win，Linux，iOS，android
微内核
主要功能保留在内核，不必要在内核态执行的功能转移到用户态
文件服务运行在用户态
主要缺点是性能问题
鸿蒙OS
操作系统引导
激活CPU
执行JMP 指令跳转到BIOS
登记BIOS中断程序的入口地址
硬件自检
加载带有OS的硬盘
加载主引导记录MBR
MBR 包含硬件分区表
MBR 检查分区表，查找活动分区将分区的启动程序调入内存执行
扫描硬盘分区
加载引导记录PBR （分区引导记录）
寻找并激活分区根目录下用于引导操作系统的程序
加载启动管理器
位于硬盘，用于引导操作系统
加载OS
虚拟机
第二章进程与线程
进程与线程
概念
进程控制块 PCB
使参与并发执行的每个程序（含数据）都能独立运行
PCB是进程存在的唯一标志
进程实体（映像）
由程序段，相关数据段和PCB三部分构成
进程是进程实体的运行过程
是系统进行资源分配和调度的一个独立单位
特征
是由多道程序的并发执行引出的
动态性
并发性
独立性
异步性
进程状态与转换
运行态→阻塞态
保护现场
进程组成
PCB
程序段
能被进程调度到CPU执行的程序代码段
数据段
进程控制
进程控制用的程序称为原语
每个父进程与子进程都拥有自己的PCB
父进程子进程共享一部分资源，但不共享虚拟地址空间
进程终止
事件
正常结束
异常结束
外界干预
过程
检索出PCB，读状态
终止运行
将资源让给其他进程
或归还给操作系统
终止所有子进程
删除PCB
进程通信
进程间的信息交换
低级通信
PV操作
不可被中断
高级通信
共享存储
进程内的线程自然共享进程空间 进程之间通过特殊的系统调用实现共享进程空间
消息传递
数据交换以格式化的消息为单位
直接通信方式
间接通信方式
中间实体为信箱
管道通信
数据在管道中是先进先出
管道文件存在于内存中
如果数据被读空，则读进程阻塞
管道只能由创建进程所访问
普通管道只允许单向通信
线程与多线程
是一个基本的CPU执行单元
是程序执行流的最小单元
线程控制块TCB 组成
线程ID
程序计数器
寄存器集合
堆栈组成
线程专有存储区
同一进程中，多个线程可以并发执行
引入线程后
进程作为CPU外的系统资源的分配单元
线程作为处理机的分配单元
进程是系统中拥有资源的基本单位，线程不拥有系统资源
线程实现
分类
用户级线程
所有工作由应用程序在用户空间中完成
线程切换不需要内核空间，开销小
根据需要选择不同的调度算法
某个用户级线程被阻塞，则整个进程也被阻塞
内核级线程
在操作系统支持下完成
同一进程的线程切换，需要从用户态转为内核态，开销较大
可以同时调度同一进程的多个线程在CPU上并行执行
多线程模型
多对一
多用户映射到一个内核
一对一
多对多
处理机调度
调度概念
从就绪队列按照一定算法，选择进程并将处理机分配给它
作业和进程
作业是用户提交，以用户任务为单位 进程是操作系统生成，是资源分配和独立运行的基本单位
调度层次
高级调度
作业调度
作业调度是内存与辅存之间的调度
每个作业只调入一次，调出一次
中级调度
内存调度
程序调出调入
提高内存利用率和系统吞吐量
暂时不运行的进程调度至外存，挂起态
低级调度
进程调度
进程调度频率高
最基本，不可或缺
性能指标
CPU利用率
CPU有效工作时间 /（有效+等待）
周转时间
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = ∑周转时间 / n
带权周转时间 = 作业周转时间 / 作业实际运行时间
平均带权周转时间 = ∑带权周转时间 / n
等待时间
响应时间
调度实现
调度程序
排队器
分派器
上下文切换器
执行大量load/store指令，保存寄存器内容
调度时机，切换和过程
不能调度和切换的情况
1）处理中断的过程中
2）进程在系统内核临界区中
进入临界区后，加锁， 在解锁之前不应该切换进程
3）原子过程中
原子过程中，连中断都屏蔽
能调度和切换的情况
非剥夺调度
发生调度条件，且当前进程无法继续下去
剥夺调度
中断处理结束
自陷trap结束
调度方式
非抢占式
即使有紧急进程在就绪，仍然让当前进程继续
抢占式
紧急事件优先级更高
闲逛进程
系统没有其他进程运行时，开启闲逛idle
两种线程的调度
用户级
线程切换在同一进程中，使用少量机器指令
内核级
内核选择特定的线程运行，赋予时间片
调度算法
先来先服务
不可剥夺算法
算法简单，效率低
有利于CPU繁忙作业 不利于IO繁忙作业
短作业优先
运行时间最短的作业优先
对长作业不利
未完全考虑作业的紧急程度
平均等待时间，平均周转时间最少
优先级调度
按作业优先级来执行
既可用于进程调度，也可用于作业调度
优先级
静态优先级
一旦决定不可改变
动态优先级
可根据情况调整优先级
原则
1）系统进程＞用户进程
2）交互进程＞非交互进程
3）IO进程＞计算进程
因为IO设备比CPU慢
高响应比优先
响应比 = （等待时间+要求服务时间）/ 要求服务时间
时间片轮转
用于分时系统
如果时间片很大，以至于所有作业都可以在一个时间片内执行完毕， 时间片轮转算法就退化为先来先服务
多级队列
不同类型或不同性质的进程分配到不同的就绪队列
多级反馈队列
多个就绪队列，每个队列不同优先级
每个队列的进程时间片大小不同
每个队列采用先来先服务
队列按优先级调度
比较
进程切换
上下文切换
上下文是指：某一时刻CPU寄存器和程序计数器内容
CPU切换到另一个进程，需要保存当前进程的状态并且恢复另一个进程的状态
更新PCB
模式切换
用户态和内核态的切换
同步与互斥
概念
临界资源
一次只允许一个进程使用
如打印机，变量，数据
进入区
检查是否可进入临界区
临界区
进程中访问临界资源的那段代码
退出区
将正在访问临界区的标志清除
剩余区
代码的剩余部分
进程同步
直接制约关系
进程之间直接协同的关系，进程的并发是异步的
互斥
间接制约关系
一个进程访问临界资源时，另一个进程必须等待
准则
空闲让进
忙则等待
有限等待
保证在有限的时间内进入临界区
让权等待
进程不能进入临界区时，立即释放处理器，防止进程忙等待
互斥的方法
软件实现方法
单标志法
双标志法先检查
双标志法后检查
peterson algorithm
防止两个进程进入临界区而无限等待，设置了变量turn
硬件实现方法
中断屏蔽法
硬件指令法
testandset
swap
硬件实现方法优点
适用于任何数目的进程
缺点
可能会产生饥饿现象
互斥锁
acquire
获得锁
release
释放锁
信号量
PV操作实际上是两个不可中断的过程组成
p操作即wait操作，表示等待到资源可用， 若资源不可用，则进入阻塞态， p操作时的进程处于运行态
V操作即single操作，表示进程释放一个资源，使系统中可供分配的资源数+1
整型信号量
记录型信号量
利用信号量实现进程同步
利用信号量实现进程互斥
互斥量初值一般为1，表示每次只允许一个进程进入临界区 为0时，表示临界区已有一个进程进入，临界区外尚无进程等待 当互斥量小于0时，表示临界区有一个进程，互斥量的绝对值表示在临界区外等待的进程数
利用信号量实现前驱
管程
进程同步工具
保证了进程互斥
能实现进程间的同步与互斥
每次仅有一个进程使用共享资源
代表共享资源的数据结构，以及由对该共享数据结构实时操作的一组过程所组成的资源管理程序
signal与V操作不同，如果不存在因条件而阻塞的进程，则signal不产生影响
同步问题
生产者消费者问题
读者写者问题
读优先
写优先
哲学家进餐问题
可能存在的问题，当大家都去抢筷子的时候（贪心算法），可能会发生死锁
吸烟者问题
死锁
定义
多个进程竞争一个资源造成的僵局
若无外力，这些进程将无法继续进行
产生原因
1）系统资源的竞争
系统中不可剥夺资源，数量不足以满足多个进程
2）进程推进顺序非法
请求和释放资源的顺序不当
产生死锁的必要条件
1）互斥条件
在某一段时间内某资源仅为一个进程所占用
2）不剥夺条件
不能被其他进程抢占
3）请求并保持条件
进程已经占用一个资源，同时请求另一个资源，并且对此资源占用不释放
4）循环等待
每个进程占用的资源同时被下一个进程请求
死锁的处理策略
1）死锁预防
破坏必要条件四个中的一个或几个
1. 破坏互斥条件
允许系统资源共享
2. 破坏不剥夺条件
释放那些占用资源又无法继续执行的进程
3. 破坏请求并保持条件
一次性申请所有需要的资源，在它资源未满足前，不把它投入运行
4. 破坏循环等待
采用顺序资源分配法
2）死锁避免
防止系统进入不安全状态
1. 系统安全状态
系统在进行资源分配前，应该先计算此次分配的安全性
安全状态
一定无死锁
非安全状态
可能会进入死锁
2. 银行家算法
避免系统进入非安全状态
3）死锁检测与解除
检测出死锁的发生，采取某种措施解除死锁
如果系统为进程分配资源时不采取任何措施，应该提供死锁检测和解除手段
资源分配图
框中的圆代表资源
进程到资源的有向边叫请求边
死锁解除
1）资源剥夺
挂起死锁的进程，将其资源抢占，分配给其他死锁的进程
2）撤销进程
强制撤销部分甚至全部的死锁进程，并剥夺其资源
3）进程回退
让一个死锁进程回退到足以回避死锁的地步
比较
死锁和饥饿的区别
饥饿
一个进程的执行被无限期推迟
进入饥饿的进程可以只有一个
可以是就绪太也可以是阻塞态
死锁
进程陷入僵局，无法继续推进
进入死锁的进程必须等于或大于两个
发生死锁的进程一定是阻塞态
第三章内存管理
概念
内存管理是为了更好的支持多道程序的并发执行
程序的链接和装入
链接
静态链接
库函数链接成一个装入模块，修改相对地址
装入时动态链接
在装入内存时，边装入边链接
运行时动态链接
在执行过程中未被用到的目标模块不会被调入内存或链接成模块
装入
绝对装入 （静态）
在编程阶段
适用于单道程序，逻辑地址和内存地址完全相同
可由程序员给出，也可由编译或汇编给出
可重定位装入
静态重定位
装入时对目标程序中的指令和数据地址的修改过程叫重定位
装入后不改变
装入时 将逻辑地址修改为最终物理地址
动态运行时装入
动态重定位
装入程序把模块装入内存后，不立即把装入模块的相对地址转化为绝对地址，而是把转化过程推迟到执行时进行
装入后可能会换出
装入内存后的地址均为相对地址
内存保护
逻辑地址加上重定位的值得到物理地址
界地址寄存器判断是否越界
加载重定位寄存器和界地址寄存器必须使用特权指令，由操作系统内核完成，不允许用户修改
内存共享
只有只读的区域才可以共享
可重入代码（纯代码）允许多个进程访问但不允许被任何进程修改
可重入技术减少了代码的调入调出，减少对换次数来提高系统性能
覆盖与交换
覆盖
即将访问的程序段放入覆盖区，其他段放入外存，需要调用前系统再将其调入覆盖区，替换原有的段
交换
把等待态程序从内存调入辅存，为中级调度
连续分配管理
单一连续分配
系统区供操作系统使用，放在低地址部分
用户区内存中，只有一道用户程序
采用覆盖技术
分区管理
满足多道程序设计的最简单的存储管理方案，代价最小
固定分区分配
用户内存分为若干个固定大小的区域，每个分区只装入一道作业
问题
1）程序过大放不进任何一个分区，利用覆盖技术
2）程序过小放入分区会产生内部碎片
动态分区分配
随时间推移，内存中会产生许多小的内存块，称为外部碎片
通过紧凑技术解决，操作系统对进程进行移动和整理
分配策略
首次适应算法
以地址递增的次序链接
邻近适应算法
分配内存时从上一次查找结束的位置开始查找
最佳适应算法
空闲分区按容量递增的次序形成空闲分区链
产生最多的外部碎片
最坏适应算法
按容量递减次序形成空闲分区链
回收内存
通过拼接技术实现对空闲区的合并
1）回收区与插入点的前一空闲分区相邻
将两个分区合并，并修改前一分区表项的大小为两者之和
2）回收区与插入点的后一空闲分区相邻
修改后一分区表项的大小为两者之和
3）回收区与插入点前、后两个分区相邻
修改前一分区表项大小为三者之和
取消后一分区表项
4）回收区没有相邻的空闲分区
为回收区新建一个表项，填写始址，大小，插入空闲分区链
系统提供给用户的物理地址空间为总空间大小减去页表或段表的长度
分页管理
分页管理产生内部碎片，不会产生外部碎片
进程中的块称为页面，内存的块称为页框
地址结构决定了虚拟内存的寻址空间大小
系统为每个进程建立一张页表，页表存放在内存中
页表的始址放在页表基址寄存器中
页大小一旦确定，所有的页大小都相同（2的整数幂）
地址变换机构
分段管理
产生外部碎片
段内连续，段间不要求连续
分段是在用户编程时，将程序按照逻辑划分为几个逻辑段
与逻辑结构有关
有利于程序的动态链接
段页式管理
产生内部碎片
系统为进程建立段表，每个分段有一张页表
分段方法来管理和分配用户地址空间 分页方法来管理和分配物理地址空间
进行一次访问实际需要三次访问主存
虚拟内存管理
特征
多次性
作业被分为多次调入内存
对换性
将暂不使用的程序和数据调出内存
虚拟性
逻辑上扩充内存容量
虚拟内存的实际容量 ≤ 内存容量 + 外存容量
虚拟内存的最大容量 ≤ 计算机的地址位数能容纳的最大容量
实现方法
1）请求分页管理
需要硬件支持
内存、外存、中断机构、地址变换等
页表机制
页号，物理块号，状态位，访问字段，修改位，外存地址
缺页中断机制
访问的页面不在内存中时，产生一个缺页中断，请求系统调入内存
缺页率受到页面大小，分配的物理块数，置换算法，程序编制的影响
地址变换机构
页框分配
驻留集
给一个进程分配的页框的集合
分配给一个进程的页框越少驻留在主存的进程就越多，提高了CPU利用率
一个进程在主存中的页面过少，缺页率相对较高
内存分配策略
1）固定分配局部置换
给进程分配一定数量的物理块，发生缺页后，从分配给此进程在内存的页面选择一页调出
2）可变分配全局置换
分配一定数目的物理块，可适当增加减少 全局置换：从空闲的物理块选出一块分配给进程，将缺页的调入
3）可变置换局部置换
缺页时，只允许从此进程在内存的页面中选一页调出
物理块调入算法
固定分配策略
1）平均分配算法
2）按比例分配
根据进程大小按比分配
3）优先权分配
根据紧迫程度分配
调入页面时机
运行前调入
运行期间调入
置换算法
1）最佳置换算法
淘汰以后永不使用的页面或最长时间不使用的页面
2）先进先出算法
会发生贝拉蒂belady异常
分配的物理块数增大，页面故障数不减反增
3）最近最久未使用
需要寄存器和栈的硬件支持
因为要计算出最近未访问的页面，因此开销大
4）时钟算法
5）改进型时钟算法
增加了修改位
优先考虑未使用过又未修改过的页面
根据访问位A和修改位M判断
抖动和工作集
抖动
刚刚换出的页面立马又要换入（频繁的调出调入页面）
缺页率高
原因
系统中同时运行的进程太多，分配给每个进程的物理块太少
工作集
在某段时间内进程要访问的页面的集合
防止出现抖动现象
2）请求分段管理
3）请求段页式管理
第四章文件管理
文件属性
名称
类型
创建者
所有者
位置
大小
保护
时间
文件是一种抽象数据类型，数据结构
文件控制块 FCB
文件目录项
存放控制文件所需的各种信息的数据结构
按名存取
包含：基本信息、存取控制信息、使用信息
索引结点 inode
文件目录放在磁盘上
磁盘索引结点
每个文件有唯一的磁盘索引结点
主标识符，类型，权限，物理地址，长度，链接计数，存取时间
内存索引结点
存放在内存的索引结点
文件打开时，磁盘索引结点复制到内存索引结点中
结点编号，状态，访问计数，逻辑设备号，链接指针
文件操作
打开与关闭
打开
调用open根据文件名搜索目录，将指明文件的属性（包括物理位置），从外存复制到内存打开文件表的表目中，并将表目编号返回给用户
将FCB存入内存文件目录表
关闭
调用close，系统将打开文件表中删除此表目
read调用中，如果文件不在内存，进程进入休眠
文件保护
口令保护
口令存在系统内部，不够安全
加密保护
防止文件被窃取
访问控制
控制用户对文件的访问方式
文件的逻辑结构
无结构文件（流式文件）
顺序组织成记录（有序集合）
有结构文件（记录式文件）
顺序文件
串结构
按存入时间排列
顺序结构
按关键字顺序排列
索引文件
定长记录文件
变长记录文件
顺序查找
索引顺序文件
N条记录分为 √N 组，索引表中有√N个表项，共需要查找√N/2 + √N/2次
直接文件/散列文件
给出记录的键值或散列函数转换的键值决定记录的物理地址
文件的物理结构
分配方式
连续分配
支持顺序访问 / 随机访问
存取速度快
反复删文件产生外部碎片
不方便增删改
文件的目录项中文件物理地址字段包括第一块的地址和此文件分配区域的长度
链接分配
离散分配方式
消除了外部碎片
不方便查
隐式链接
只适合顺序访问
目录包含文件第一块的指针和最后一块的指针
产生内部碎片
显式链接
把链接指针显性存放在内存的链接表，称为文件分配表FAT 每个表项存放下一个盘块号
FAT在整个磁盘就这一张，也是一种数据结构
FAT的表项与物理盘块一一对应，可以用特殊数字-1表示为最后一块，又可以用其他数字表示盘块为空闲的，FAT不仅记录了各块的链接关系，也标记了空闲盘块
索引分配
支持随机访问
访问速度不如连续分配
没有外部碎片
混合索引分配
目录
目录结构
单目录结构
按名存取
查找速度慢，不允许重名，不方便共享
二级目录结构
解决了重名问题
不能对文件分类，缺乏灵活性
树形目录结构
进程对文件的访问都是相当于当前目录进行的
需要按路径名逐级访问中间结点，增加了磁盘访问次数
无环图目录结构
对于共享文件，只存在一个真正的文件，任何改变都会为其他用户所见
目录实现
线性列表
采用文件名和指针的线性列表
采用链式结构可以减少删除文件的时间
查找费时
哈希表
查找迅速
需要避免冲突
文件共享
静态共享
硬链接（基于索引结点）
文件的物理地址以及文件属性信息，不再放在目录项，而是放在索引结点
索引结点还有一个计数count，表示几个用户共享
软链接（利用符号链）
创建一个link型文件，根据文件中的路径名找到文件
只有 文件主 拥有指向其索引结点的指针 其他用户只有此文件的路径名
每次访问文件时要多次读盘，开销大
在对网络文件共享时，只需要提供文件所在的机器网络地址及文件路径名
动态共享
几个用户同时对一个文件操作
文件系统
文件系统在外存的结构
物理格式化
划分扇区，检查坏扇区，替换坏扇区
逻辑格式化
磁盘分区，完成各分区文件系统初始化
产生
主引导记录MBR
确定活动分区，读入引导块
引导块
MBR执行引导块中的程序，启动操作系统
超级块
包含文件系统所有关键信息，文件系统首次启动时，超级块读入内存
空闲空间管理
如：位示图
i结点区
索引结点连续存放，大小相同
根目录
文件系统在内存的结构
用户区
文件描述符/文件句柄
内核区
目录缓存
系统打开文件表
仅有一张
用户打开文件表
包含系统打开文件表索引
虚拟文件系统
向上层用户提供统一标准的系统调用接口 屏蔽底层具体文件系统的实现差异
要求下层文件必须实现某种函数功能
每一个被打开的文件都会在主存创建一个vnode，用统一的数据结构表示
vnode只存在于主存 inode既会被调入主存，也会在外存中存储
文件系统的挂载（安装）
在虚拟文件系统注册新挂载的文件系统， 内存挂载表包含每个文件系统的信息
新挂载的文件系统，要向虚拟文件系统提供一个函数地址列表
将文件系统加载到挂载点（父目录）
文件空间管理
存储空间划分
将物理磁盘划分为一个个文件卷（逻辑盘，逻辑卷）
一个文件卷可以由多个物理磁盘组成
存储空间初始化
文件卷初始化
目录区
存放文件目录信息FCB，用于磁盘存储空间管理的信息
文件区
存放文件数据
空间管理
空闲表法
属于连续分配方式
为文件分配连续的存储空间
可采用首次适应，最佳适应，最坏适应
回收方式与动态分配相同
空闲链表法
空闲盘块链
将空闲盘块像链表一样链接起来
空闲盘块中保存指向下一个空闲盘块的指针
分配
通过适应算法找到符合条件的盘块
回收
将回收的盘块挂到链尾
分配回收简单，但效率低
空闲盘区链
几个连续的空闲盘块构成一个空闲盘区
盘区中第一个空闲盘块里记录盘区长度，指向下一个盘区的指针
分配
通常采用首次适应
回收
将回收区与相邻的空闲盘区合并
分配回收麻烦，但效率高
位示图法
利用二进制位bit来表示一个盘块是否使用
盘块号b = n×i + j
n表示字长
i表示字号（行号）
i = b/n
除
j表示位号（列号）
j = b%n
取余
连续分配和离散分配都适用
成组链接法
成组链块（超级块）用来存放空闲盘块的块号以及下一组空闲盘块数
空闲盘块的块号为成组块（盘区）的第一个盘块号
一个分组的数量有限，比如：只允许100个空闲盘块组成一个组
若没有下一组的空闲盘块，则块号设为-1
分配
从最后盘块开始分配，并更改超级块中空闲盘块数
若某一快内存放了下一组的信息，则要将信息复制到超级块后，再进行分配
回收
若超级块没满
则直接将回收块插入到超级块后
若超级块已满
类似链表的头插法
磁盘
结构
磁盘
磁道
扇区
就是磁盘块
每个扇区容量相同，最内层扇区密度最大
盘面
每个盘面对应一个磁头
柱面
所有盘面的相对位置相同的磁道组成柱面
磁盘地址用（柱面号-盘面号-扇区号）表示
磁盘调度算法
一次读写需要的时间
寻道时间
启动磁头臂
用时s
移动磁头
跨越一条磁道用时m，需要跨越n条磁道
= s + m×n
传输时间
读/写时间
转速r，读写的字节数为b，每个磁道上的字节数为N
= b /（r N）
延迟时间
磁盘转速为r
= 1/（2r）
磁盘调度算法
会直接影响寻道时间
先来先服务
最短寻找时间优先
可能产生饥饿现象
扫描算法
只有磁头移动到最内或者最外层磁道时才可以往反方向移动
即使最外层或者最内层没有处理请求也依然要移动到此才可以开始反方向移动
不会产生饥饿现象
look算法
扫描算法的改进
如果在磁头移动方向没有了其他的请求，则可以直接改变方向
循环扫描 （电梯调度）
解决扫描算法对于各个位置的响应不平均
在返回时不响应任何请求，直接移动至起始端
只有在移动到最边缘后才改变方向（与扫描算法相同）
c-look算法
循环扫描的改进
不需要移动到边缘才改变方向，移动方向没有其他请求就可改变方向
减少延迟的方法
交替编号
让逻辑上相邻的扇区在物理上有一定间隔
错位命名
让同一扇面内各个扇区相错开（如0扇区与1扇区之间隔着其他号扇区）
地址结构设计
柱面号-盘面号-扇区号
减少了磁头移动时间
磁盘管理
磁盘初始化
物理格式化
将磁盘各个磁道划分为扇区
分区
将磁盘分区，每个分区由若干柱面组成
逻辑格式化
创建文件系统
引导块
计算机开机要进行一系列初始化工作，通过执行自举程序完成初始化工作
完整的自举程序存放在磁盘的启动块（引导块）上，启动块位于磁盘的固定位置
坏块处理
坏块属于硬件故障
对于简单磁盘
坏块对操作系统不透明（会被标记）
对于复杂磁盘
扇区备用
对复杂的磁盘，磁盘控制器会维护一个坏块链表，在物理格式化时，进行初始化，利用备用扇区替换坏块
固态硬盘SSD
原理
基于闪存flash 属于电可擦ROM（EEPROM）
组成
闪存翻译层
翻译逻辑块号
找到对应的页
存储介质
多个闪存芯片
每个芯片包含多个块（blocks）
每个块包含多个页
读写性能
以页为单位
以块为单位
支持随机访问
读速度快 写速度慢
与机械硬盘的对比
SSD读写比机械硬盘快，随机访问
SSD安静无噪音
SSD的某个块多次擦除后会坏掉 机械硬盘的扇区不会因为写的多而坏掉
磨损均衡
将擦除操作平均到各个块上
动态磨损均衡
写数据时，优先选择累计擦除少的闪存块
静态磨损均衡
老旧的块担任 读操作 为主的任务 新块担任 写操作 为主的任务
静态比动态更加优秀
第五章IO管理
设备分类
块设备
数据交换以块为单位
传输速率高
字符设备
数据交换以字符为单位
传输速率低，不可寻址
低速设备
鼠标键盘
中速设备
打印机
高速设备
磁盘机，光盘机
io接口
设备控制器
位于CPU和设备之间
设备控制器与cpu的接口
包含数据线地址线控制线
设备控制器与设备的接口
控制器中有一个或多个设备接口
io逻辑
实现对设备的控制
设备控制器功能
接受识别CPU的命令
数据交换
标识和报告设备状态
地址识别
数据缓冲
差错控制
io端口
设备控制器中可以直接被CPU访问的寄存器
换句话说多个io端口组成了io接口
数据寄存器
状态寄存器
控制寄存器
CPU与io端口通信方法
独立编址
为每个端口分配一个端口号，只有操作系统使用特殊io指令才能访问端口
统一编址
每个端口被分配唯一的内存地址
io控制方式
程序直接控制方式
CPU循环检查外设状态，直到确定该字在io控制器的数据寄存器中
中断驱动方式
允许io设备主动打断CPU的运行并请求服务， 从而解放CPU
在每个数据需要传输时中断CPU
DMA方式
io设备和内存之间开辟直接的数据交换通路
在所要求的一批数据传送结束时中断CPU
CPU发出指令时，只能读或者写连续的数据块
通道控制方式
专门负责输入输出的处理机
是一种硬件
CPU发出io指令，指明通道程序的位置指明执行的io设备
通道执行内存中的通道程序
通道与CPU共享内存
io软件层次结构
用户io软件
实现假脱机技术spooling
虚拟设备技术
提高独占设备的利用率
将独占设备变为共享设备
缓和CPU高速与io设备低速的矛盾
通过软件方式
需要多道程序设计技术支持
系统在磁盘固定区开辟两个区域，输入输出井
在内存中开辟两个缓冲区：输入缓冲区 输出缓冲区
共享打印机
独占式设备
允许各个进程串行使用的设备
采用静态分配
共享设备
允许多个进程共同使用的设备
宏观意义上的同时使用 微观上仍然交替进行
采用动态分配
共享打印原理
系统将各个用户需要的打印请求放到磁盘的输入井，利用磁盘与内存与CPU的速度差来实现微观上的交替，宏观上的同时
设备独立软件（设备无关软件）
独立性
用户编程时使用的设备与实际设备无关
功能
管理逻辑设备表
只设置一张系统逻辑设备表LUT
为每个用户设置逻辑设备表LUT
差错控制
设备分配回收
分配考虑的因素
设备固有属性
设备分配算法
设备分配安全性
安全分配方式
进程发出io请求后就进入阻塞，直到完成io操作才解除
CPU与io设备变成了串行工作
不安全分配方式
进程发出io请求后，继续运行，并仍可发出io请求，只有在io请求得不到满足才进入阻塞
可能出现死锁
分配策略
静态分配
一开始就将所需的全部资源分配
动态分配
在进程执行过程中根据需要继续分配
设备分配的数据结构
通道，控制器，设备关系
设备控制表DCT
表示某一个设备，表项内容为设备的各个属性
控制器控制表COCT
通道控制表CHCT
每个通道对应一张CHCT
系统设备表SDT
包含全部设备的情况
分配步骤改进
用户提供逻辑设备名
通过逻辑设备名与物理设备名的映射（逻辑设备表LUT）
LUT表项包括逻辑设备名，物理设备名，设备驱动程序入口地址
缓冲管理
目的
解决输入输出速度比CPU处理速度慢而造成的数据堆积的问题
单缓冲
计算每块数据的处理时间
假设一个初始状态，计算下一次到达此状态花费的时间
输入到缓冲区的时间为T，缓冲区传送到工作区的时间为M，处理数据的时间为C
初始状态：工作区满，缓冲区空
处理每块数据用时：MAX（C，T）+M
公式供参考，具体问题具体分析，用甘特图
双缓冲
工作区空，一个缓冲区空一个缓冲区满
处理每块数据用时：MAX（C+M，T）
缓冲池
使并发进程有效地输入输出
实现io调度
用某种算法确定一个好的顺序来处理io请求
设备保护
设备被看作为特殊的文件，每个文件分配FCB，设置权限
设备驱动程序
对硬件设备的具体控制
计算数据所在磁盘的柱面号，磁头号，扇区号等
不同的设备需要不同的驱动程序
io应用程序接口
字符设备接口
get/put调用，向字符设备读写一个字符
块设备接口
read/write系统调用：读写字符 seek：修改
网络设备接口
网络套接字接口 socket系统调用：创建网络套接字，指明网络协议 bind：将套接字绑定到本地端口 connect：将套接字连接到远程地址 read/write：从套接字读写数据
阻塞/非阻塞io
阻塞io
程序发出io系统调用，进程转为阻塞态等待
非阻塞io
程序发出io系统调用，系统调用可迅速返回，进程无需阻塞等待
操作系统
第一章概述
基本概念
控制和管理整个计算机系统的硬件和软件资源，合理组织，调度计算机的工作与资源分配，为用户提供方便接口与环境的程序集合
特征
并发
多个事件在同一个时间间隔里发生
与并行不同 并行是在同一个时刻里并行
共享
互斥共享
规定时间内只允许一个进程访问资源
只有在进程访问完并且释放资源后，另一个进程才可以对此资源访问
临界资源
一段时间内只允许一个进程访问
如：物理设备，栈，变量，表格等
同时访问
允许一段时间内由多个进程“同时”访问
同时是宏观上的同时， 在微观上它们可能是交替地访问资源（分时共享）
资源共享是以程序的并发为条件的，若不允许程序并发，则不存在资源共享
两大基本特征
虚拟
实体变为逻辑上的对应物
通过多道程序并发执行
利用多道程序设计技术把一个物理CPU分为多个逻辑上的CPU
虚拟技术
时分复用技术
分时共享
空分复用技术
虚拟存储
异步
进程执行不是一步到位的，是走走停停的，因为资源有限
操作系统作为用户和计算机硬件系统的接口
用户使用计算机的方式
1）命令接口
通过命令解释器
shell命令解析器也属于命令接口
联机命令接口
适用于分时，实时系统
强调用户的交互性
脱机命令接口
无需人工操作
用于批处理系统
连同预先准备好的作业一起交给系统，到调度作业时，系统的命令解释程序控制执行
2）程序接口
由系统调用组成
利用系统调用请求操作系统为其提供服务
操作系统不提供系统缓存的系统调用，缓存对用户是透明的
发展历程
1）手工操作阶段
此时没有操作系统，所有工作由人工完成
2）批处理阶段
单道批处理系统
1）顺序性
2）自动性
3）单道性
内存仅有一道程序执行
多道批处理系统
通过多道程序设计技术
多个程序同时进入内存，在CPU内交替进行
共享硬/软件
一道程序因IO而暂停运行时，CPU便立即运行另一道程序
通过中断
优点
1）多道
2）宏观并行
3）微观串行
4）利用率高，吞吐量大
缺点：响应时间长，不提供人工交互，不能控制计算机
3）分时操作系统
多个用户通过终端同时共享一台主机
通过时间片轮转方式
实现人机交互
1）同时性
2）交互性
3）独立性
多用户独立操作，互不干扰
4）及时性
很短时间内获得响应
4）实时操作系统
在某个限制时间内完成紧急任务（抢占式高优先级任务）， 不需要时间片排队
5）网络操作系统与分布式计算机系统
网络操作系统
各台计算机有机结合
分布式计算机系统
每台计算机有同等地位
6）个人计算机操作系统
win，Linux，Mac OS
运行环境
处理机运行模式
1）特权指令
不允许用户直接使用的指令
IO指令，置中断指令，送状态字，存寄存器，置时钟
只能在内核态执行
2）非特权指令
允许用户直接使用的指令
不能直接访问系统的软硬件资源
只允许访问用户地址空间
系统调用
陷入指令（trap）又称访管指令，用来发起系统调用，请求系统提供服务
是在用户态使用的， 所以不属于特权指令
程序运行在用户态
内核程序运行在内核态
切换到用户态的指令是特权指令
应用程序向操作系统请求服务通过访管指令，产生中断事件转换操作系统为内核态
广义指令（系统调用命令）的执行过程一定在内核态， 而它的调用有可能在用户态也可能在内核态
用户态切换到内核态必定通过中断
只要发生中断，必然会切换到内核态
子程序调用
只保存断点
下一条指令地址
用户态→核心态
例子
请求系统服务
发生中断
用户程序发生错误
用户程序想要执行特权指令
用户态到核心态的转化由硬件完成
必定会通过中断实现
只要发生中断，就要对其处理，也必定会转化到内核态
用户态进入核心态，不仅状态切换，堆栈也会转换为系统堆栈
时钟管理
通过时钟中断的管理，实现进程切换
时钟中断
处理和时间有关的信息，决定是否执行调度程序
系统时间，时间片，延时，使用CPU的时间，定时器等
中断和异常
中断 （外中断）
操作系统不能没有中断
只有小部分功能属于内核，保护和恢复中断现场信息， 转移控制权至相关处理程序
保存的数据
硬件保存
PC
状态字PSW
操作系统保存
通用寄存器x
异常 （内中断）
非法操作码，地址越界，溢出，缺页，自陷等
系统调用，访管指令
异常不能被屏蔽，一旦出现立即处理
原语
是一种程序
1）处于操作系统最底层
2）程序运行具有原子性
3）程序运行时间短，调用频繁
4）内核的组成部分
管理方式
设备管理
进程管理
存储器管理
操作系统结构
分层法
各层定义比较困难
模块化
模块间接口很难满足实际需求
宏内核
主要功能模块都作为一个紧密联系的整体运行在内核态
win，Linux，iOS，android
微内核
主要功能保留在内核，不必要在内核态执行的功能转移到用户态
文件服务运行在用户态
主要缺点是性能问题
鸿蒙OS
操作系统引导
激活CPU
执行JMP 指令跳转到BIOS
登记BIOS中断程序的入口地址
硬件自检
加载带有OS的硬盘
加载主引导记录MBR
MBR 包含硬件分区表
MBR 检查分区表，查找活动分区将分区的启动程序调入内存执行
扫描硬盘分区
加载引导记录PBR （分区引导记录）
寻找并激活分区根目录下用于引导操作系统的程序
加载启动管理器
位于硬盘，用于引导操作系统
加载OS
虚拟机
第二章进程与线程
进程与线程
概念
进程控制块 PCB
使参与并发执行的每个程序（含数据）都能独立运行
PCB是进程存在的唯一标志
进程实体（映像）
由程序段，相关数据段和PCB三部分构成
进程是进程实体的运行过程
是系统进行资源分配和调度的一个独立单位
特征
是由多道程序的并发执行引出的
动态性
并发性
独立性
异步性
进程状态与转换
运行态→阻塞态
保护现场
进程组成
PCB
程序段
能被进程调度到CPU执行的程序代码段
数据段
进程控制
进程控制用的程序称为原语
每个父进程与子进程都拥有自己的PCB
父进程子进程共享一部分资源，但不共享虚拟地址空间
进程终止
事件
正常结束
异常结束
外界干预
过程
检索出PCB，读状态
终止运行
将资源让给其他进程
或归还给操作系统
终止所有子进程
删除PCB
进程通信
进程间的信息交换
低级通信
PV操作
不可被中断
高级通信
共享存储
进程内的线程自然共享进程空间 进程之间通过特殊的系统调用实现共享进程空间
消息传递
数据交换以格式化的消息为单位
直接通信方式
间接通信方式
中间实体为信箱
管道通信
数据在管道中是先进先出
管道文件存在于内存中
如果数据被读空，则读进程阻塞
管道只能由创建进程所访问
普通管道只允许单向通信
线程与多线程
是一个基本的CPU执行单元
是程序执行流的最小单元
线程控制块TCB 组成
线程ID
程序计数器
寄存器集合
堆栈组成
线程专有存储区
同一进程中，多个线程可以并发执行
引入线程后
进程作为CPU外的系统资源的分配单元
线程作为处理机的分配单元
进程是系统中拥有资源的基本单位，线程不拥有系统资源
线程实现
分类
用户级线程
所有工作由应用程序在用户空间中完成
线程切换不需要内核空间，开销小
根据需要选择不同的调度算法
某个用户级线程被阻塞，则整个进程也被阻塞
内核级线程
在操作系统支持下完成
同一进程的线程切换，需要从用户态转为内核态，开销较大
可以同时调度同一进程的多个线程在CPU上并行执行
多线程模型
多对一
多用户映射到一个内核
一对一
多对多
处理机调度
调度概念
从就绪队列按照一定算法，选择进程并将处理机分配给它
作业和进程
作业是用户提交，以用户任务为单位 进程是操作系统生成，是资源分配和独立运行的基本单位
调度层次
高级调度
作业调度
作业调度是内存与辅存之间的调度
每个作业只调入一次，调出一次
中级调度
内存调度
程序调出调入
提高内存利用率和系统吞吐量
暂时不运行的进程调度至外存，挂起态
低级调度
进程调度
进程调度频率高
最基本，不可或缺
性能指标
CPU利用率
CPU有效工作时间 /（有效+等待）
周转时间
周转时间 = 作业完成时间 - 作业提交时间
平均周转时间 = ∑周转时间 / n
带权周转时间 = 作业周转时间 / 作业实际运行时间
平均带权周转时间 = ∑带权周转时间 / n
等待时间
响应时间
调度实现
调度程序
排队器
分派器
上下文切换器
执行大量load/store指令，保存寄存器内容
调度时机，切换和过程
不能调度和切换的情况
1）处理中断的过程中
2）进程在系统内核临界区中
进入临界区后，加锁， 在解锁之前不应该切换进程
3）原子过程中
原子过程中，连中断都屏蔽
能调度和切换的情况
非剥夺调度
发生调度条件，且当前进程无法继续下去
剥夺调度
中断处理结束
自陷trap结束
调度方式
非抢占式
即使有紧急进程在就绪，仍然让当前进程继续
抢占式
紧急事件优先级更高
闲逛进程
系统没有其他进程运行时，开启闲逛idle
两种线程的调度
用户级
线程切换在同一进程中，使用少量机器指令
内核级
内核选择特定的线程运行，赋予时间片
调度算法
先来先服务
不可剥夺算法
算法简单，效率低
有利于CPU繁忙作业 不利于IO繁忙作业
短作业优先
运行时间最短的作业优先
对长作业不利
未完全考虑作业的紧急程度
平均等待时间，平均周转时间最少
优先级调度
按作业优先级来执行
既可用于进程调度，也可用于作业调度
优先级
静态优先级
一旦决定不可改变
动态优先级
可根据情况调整优先级
原则
1）系统进程＞用户进程
2）交互进程＞非交互进程
3）IO进程＞计算进程
因为IO设备比CPU慢
高响应比优先
响应比 = （等待时间+要求服务时间）/ 要求服务时间
时间片轮转
用于分时系统
如果时间片很大，以至于所有作业都可以在一个时间片内执行完毕， 时间片轮转算法就退化为先来先服务
多级队列
不同类型或不同性质的进程分配到不同的就绪队列
多级反馈队列
多个就绪队列，每个队列不同优先级
每个队列的进程时间片大小不同
每个队列采用先来先服务
队列按优先级调度
比较
进程切换
上下文切换
上下文是指：某一时刻CPU寄存器和程序计数器内容
CPU切换到另一个进程，需要保存当前进程的状态并且恢复另一个进程的状态
更新PCB
模式切换
用户态和内核态的切换
同步与互斥
概念
临界资源
一次只允许一个进程使用
如打印机，变量，数据
进入区
检查是否可进入临界区
临界区
进程中访问临界资源的那段代码
退出区
将正在访问临界区的标志清除
剩余区
代码的剩余部分
进程同步
直接制约关系
进程之间直接协同的关系，进程的并发是异步的
互斥
间接制约关系
一个进程访问临界资源时，另一个进程必须等待
准则
空闲让进
忙则等待
有限等待
保证在有限的时间内进入临界区
让权等待
进程不能进入临界区时，立即释放处理器，防止进程忙等待
互斥的方法
软件实现方法
单标志法
双标志法先检查
双标志法后检查
peterson algorithm
防止两个进程进入临界区而无限等待，设置了变量turn
硬件实现方法
中断屏蔽法
硬件指令法
testandset
swap
硬件实现方法优点
适用于任何数目的进程
缺点
可能会产生饥饿现象
互斥锁
acquire
获得锁
release
释放锁
信号量
PV操作实际上是两个不可中断的过程组成
p操作即wait操作，表示等待到资源可用， 若资源不可用，则进入阻塞态， p操作时的进程处于运行态
V操作即single操作，表示进程释放一个资源，使系统中可供分配的资源数+1
整型信号量
记录型信号量
利用信号量实现进程同步
利用信号量实现进程互斥
互斥量初值一般为1，表示每次只允许一个进程进入临界区 为0时，表示临界区已有一个进程进入，临界区外尚无进程等待 当互斥量小于0时，表示临界区有一个进程，互斥量的绝对值表示在临界区外等待的进程数
利用信号量实现前驱
管程
进程同步工具
保证了进程互斥
能实现进程间的同步与互斥
每次仅有一个进程使用共享资源
代表共享资源的数据结构，以及由对该共享数据结构实时操作的一组过程所组成的资源管理程序
signal与V操作不同，如果不存在因条件而阻塞的进程，则signal不产生影响
同步问题
生产者消费者问题
读者写者问题
读优先
写优先
哲学家进餐问题
可能存在的问题，当大家都去抢筷子的时候（贪心算法），可能会发生死锁
吸烟者问题
死锁
定义
多个进程竞争一个资源造成的僵局
若无外力，这些进程将无法继续进行
产生原因
1）系统资源的竞争
系统中不可剥夺资源，数量不足以满足多个进程
2）进程推进顺序非法
请求和释放资源的顺序不当
产生死锁的必要条件
1）互斥条件
在某一段时间内某资源仅为一个进程所占用
2）不剥夺条件
不能被其他进程抢占
3）请求并保持条件
进程已经占用一个资源，同时请求另一个资源，并且对此资源占用不释放
4）循环等待
每个进程占用的资源同时被下一个进程请求
死锁的处理策略
1）死锁预防
破坏必要条件四个中的一个或几个
1. 破坏互斥条件
允许系统资源共享
2. 破坏不剥夺条件
释放那些占用资源又无法继续执行的进程
3. 破坏请求并保持条件
一次性申请所有需要的资源，在它资源未满足前，不把它投入运行
4. 破坏循环等待
采用顺序资源分配法
2）死锁避免
防止系统进入不安全状态
1. 系统安全状态
系统在进行资源分配前，应该先计算此次分配的安全性
安全状态
一定无死锁
非安全状态
可能会进入死锁
2. 银行家算法
避免系统进入非安全状态
3）死锁检测与解除
检测出死锁的发生，采取某种措施解除死锁
如果系统为进程分配资源时不采取任何措施，应该提供死锁检测和解除手段
资源分配图
框中的圆代表资源
进程到资源的有向边叫请求边
死锁解除
1）资源剥夺
挂起死锁的进程，将其资源抢占，分配给其他死锁的进程
2）撤销进程
强制撤销部分甚至全部的死锁进程，并剥夺其资源
3）进程回退
让一个死锁进程回退到足以回避死锁的地步
比较
死锁和饥饿的区别
饥饿
一个进程的执行被无限期推迟
进入饥饿的进程可以只有一个
可以是就绪太也可以是阻塞态
死锁
进程陷入僵局，无法继续推进
进入死锁的进程必须等于或大于两个
发生死锁的进程一定是阻塞态
第三章内存管理
概念
内存管理是为了更好的支持多道程序的并发执行
程序的链接和装入
链接
静态链接
库函数链接成一个装入模块，修改相对地址
装入时动态链接
在装入内存时，边装入边链接
运行时动态链接
在执行过程中未被用到的目标模块不会被调入内存或链接成模块
装入
绝对装入 （静态）
在编程阶段
适用于单道程序，逻辑地址和内存地址完全相同
可由程序员给出，也可由编译或汇编给出
可重定位装入
静态重定位
装入时对目标程序中的指令和数据地址的修改过程叫重定位
装入后不改变
装入时 将逻辑地址修改为最终物理地址
动态运行时装入
动态重定位
装入程序把模块装入内存后，不立即把装入模块的相对地址转化为绝对地址，而是把转化过程推迟到执行时进行
装入后可能会换出
装入内存后的地址均为相对地址
内存保护
逻辑地址加上重定位的值得到物理地址
界地址寄存器判断是否越界
加载重定位寄存器和界地址寄存器必须使用特权指令，由操作系统内核完成，不允许用户修改
内存共享
只有只读的区域才可以共享
可重入代码（纯代码）允许多个进程访问但不允许被任何进程修改
可重入技术减少了代码的调入调出，减少对换次数来提高系统性能
覆盖与交换
覆盖
即将访问的程序段放入覆盖区，其他段放入外存，需要调用前系统再将其调入覆盖区，替换原有的段
交换
把等待态程序从内存调入辅存，为中级调度
连续分配管理
单一连续分配
系统区供操作系统使用，放在低地址部分
用户区内存中，只有一道用户程序
采用覆盖技术
分区管理
满足多道程序设计的最简单的存储管理方案，代价最小
固定分区分配
用户内存分为若干个固定大小的区域，每个分区只装入一道作业
问题
1）程序过大放不进任何一个分区，利用覆盖技术
2）程序过小放入分区会产生内部碎片
动态分区分配
随时间推移，内存中会产生许多小的内存块，称为外部碎片
通过紧凑技术解决，操作系统对进程进行移动和整理
分配策略
首次适应算法
以地址递增的次序链接
邻近适应算法
分配内存时从上一次查找结束的位置开始查找
最佳适应算法
空闲分区按容量递增的次序形成空闲分区链
产生最多的外部碎片
最坏适应算法
按容量递减次序形成空闲分区链
回收内存
通过拼接技术实现对空闲区的合并
1）回收区与插入点的前一空闲分区相邻
将两个分区合并，并修改前一分区表项的大小为两者之和
2）回收区与插入点的后一空闲分区相邻
修改后一分区表项的大小为两者之和
3）回收区与插入点前、后两个分区相邻
修改前一分区表项大小为三者之和
取消后一分区表项
4）回收区没有相邻的空闲分区
为回收区新建一个表项，填写始址，大小，插入空闲分区链
系统提供给用户的物理地址空间为总空间大小减去页表或段表的长度
分页管理
分页管理产生内部碎片，不会产生外部碎片
进程中的块称为页面，内存的块称为页框
地址结构决定了虚拟内存的寻址空间大小
系统为每个进程建立一张页表，页表存放在内存中
页表的始址放在页表基址寄存器中
页大小一旦确定，所有的页大小都相同（2的整数幂）
地址变换机构
分段管理
产生外部碎片
段内连续，段间不要求连续
分段是在用户编程时，将程序按照逻辑划分为几个逻辑段
与逻辑结构有关
有利于程序的动态链接
段页式管理
产生内部碎片
系统为进程建立段表，每个分段有一张页表
分段方法来管理和分配用户地址空间 分页方法来管理和分配物理地址空间
进行一次访问实际需要三次访问主存
虚拟内存管理
特征
多次性
作业被分为多次调入内存
对换性
将暂不使用的程序和数据调出内存
虚拟性
逻辑上扩充内存容量
虚拟内存的实际容量 ≤ 内存容量 + 外存容量
虚拟内存的最大容量 ≤ 计算机的地址位数能容纳的最大容量
实现方法
1）请求分页管理
需要硬件支持
内存、外存、中断机构、地址变换等
页表机制
页号，物理块号，状态位，访问字段，修改位，外存地址
缺页中断机制
访问的页面不在内存中时，产生一个缺页中断，请求系统调入内存
缺页率受到页面大小，分配的物理块数，置换算法，程序编制的影响
地址变换机构
页框分配
驻留集
给一个进程分配的页框的集合
分配给一个进程的页框越少驻留在主存的进程就越多，提高了CPU利用率
一个进程在主存中的页面过少，缺页率相对较高
内存分配策略
1）固定分配局部置换
给进程分配一定数量的物理块，发生缺页后，从分配给此进程在内存的页面选择一页调出
2）可变分配全局置换
分配一定数目的物理块，可适当增加减少 全局置换：从空闲的物理块选出一块分配给进程，将缺页的调入
3）可变置换局部置换
缺页时，只允许从此进程在内存的页面中选一页调出
物理块调入算法
固定分配策略
1）平均分配算法
2）按比例分配
根据进程大小按比分配
3）优先权分配
根据紧迫程度分配
调入页面时机
运行前调入
运行期间调入
置换算法
1）最佳置换算法
淘汰以后永不使用的页面或最长时间不使用的页面
2）先进先出算法
会发生贝拉蒂belady异常
分配的物理块数增大，页面故障数不减反增
3）最近最久未使用
需要寄存器和栈的硬件支持
因为要计算出最近未访问的页面，因此开销大
4）时钟算法
5）改进型时钟算法
增加了修改位
优先考虑未使用过又未修改过的页面
根据访问位A和修改位M判断
抖动和工作集
抖动
刚刚换出的页面立马又要换入（频繁的调出调入页面）
缺页率高
原因
系统中同时运行的进程太多，分配给每个进程的物理块太少
工作集
在某段时间内进程要访问的页面的集合
防止出现抖动现象
2）请求分段管理
3）请求段页式管理
第四章文件管理
文件属性
名称
类型
创建者
所有者
位置
大小
保护
时间
文件是一种抽象数据类型，数据结构
文件控制块 FCB
文件目录项
存放控制文件所需的各种信息的数据结构
按名存取
包含：基本信息、存取控制信息、使用信息
索引结点 inode
文件目录放在磁盘上
磁盘索引结点
每个文件有唯一的磁盘索引结点
主标识符，类型，权限，物理地址，长度，链接计数，存取时间
内存索引结点
存放在内存的索引结点
文件打开时，磁盘索引结点复制到内存索引结点中
结点编号，状态，访问计数，逻辑设备号，链接指针
文件操作
打开与关闭
打开
调用open根据文件名搜索目录，将指明文件的属性（包括物理位置），从外存复制到内存打开文件表的表目中，并将表目编号返回给用户
将FCB存入内存文件目录表
关闭
调用close，系统将打开文件表中删除此表目
read调用中，如果文件不在内存，进程进入休眠
文件保护
口令保护
口令存在系统内部，不够安全
加密保护
防止文件被窃取
访问控制
控制用户对文件的访问方式
文件的逻辑结构
无结构文件（流式文件）
顺序组织成记录（有序集合）
有结构文件（记录式文件）
顺序文件
串结构
按存入时间排列
顺序结构
按关键字顺序排列
索引文件
定长记录文件
变长记录文件
顺序查找
索引顺序文件
N条记录分为 √N 组，索引表中有√N个表项，共需要查找√N/2 + √N/2次
直接文件/散列文件
给出记录的键值或散列函数转换的键值决定记录的物理地址
文件的物理结构
分配方式
连续分配
支持顺序访问 / 随机访问
存取速度快
反复删文件产生外部碎片
不方便增删改
文件的目录项中文件物理地址字段包括第一块的地址和此文件分配区域的长度
链接分配
离散分配方式
消除了外部碎片
不方便查
隐式链接
只适合顺序访问
目录包含文件第一块的指针和最后一块的指针
产生内部碎片
显式链接
把链接指针显性存放在内存的链接表，称为文件分配表FAT 每个表项存放下一个盘块号
FAT在整个磁盘就这一张，也是一种数据结构
FAT的表项与物理盘块一一对应，可以用特殊数字-1表示为最后一块，又可以用其他数字表示盘块为空闲的，FAT不仅记录了各块的链接关系，也标记了空闲盘块
索引分配
支持随机访问
访问速度不如连续分配
没有外部碎片
混合索引分配
目录
目录结构
单目录结构
按名存取
查找速度慢，不允许重名，不方便共享
二级目录结构
解决了重名问题
不能对文件分类，缺乏灵活性
树形目录结构
进程对文件的访问都是相当于当前目录进行的
需要按路径名逐级访问中间结点，增加了磁盘访问次数
无环图目录结构
对于共享文件，只存在一个真正的文件，任何改变都会为其他用户所见
目录实现
线性列表
采用文件名和指针的线性列表
采用链式结构可以减少删除文件的时间
查找费时
哈希表
查找迅速
需要避免冲突
文件共享
静态共享
硬链接（基于索引结点）
文件的物理地址以及文件属性信息，不再放在目录项，而是放在索引结点
索引结点还有一个计数count，表示几个用户共享
软链接（利用符号链）
创建一个link型文件，根据文件中的路径名找到文件
只有 文件主 拥有指向其索引结点的指针 其他用户只有此文件的路径名
每次访问文件时要多次读盘，开销大
在对网络文件共享时，只需要提供文件所在的机器网络地址及文件路径名
动态共享
几个用户同时对一个文件操作
文件系统
文件系统在外存的结构
物理格式化
划分扇区，检查坏扇区，替换坏扇区
逻辑格式化
磁盘分区，完成各分区文件系统初始化
产生
主引导记录MBR
确定活动分区，读入引导块
引导块
MBR执行引导块中的程序，启动操作系统
超级块
包含文件系统所有关键信息，文件系统首次启动时，超级块读入内存
空闲空间管理
如：位示图
i结点区
索引结点连续存放，大小相同
根目录
文件系统在内存的结构
用户区
文件描述符/文件句柄
内核区
目录缓存
系统打开文件表
仅有一张
用户打开文件表
包含系统打开文件表索引
虚拟文件系统
向上层用户提供统一标准的系统调用接口 屏蔽底层具体文件系统的实现差异
要求下层文件必须实现某种函数功能
每一个被打开的文件都会在主存创建一个vnode，用统一的数据结构表示
vnode只存在于主存 inode既会被调入主存，也会在外存中存储
文件系统的挂载（安装）
在虚拟文件系统注册新挂载的文件系统， 内存挂载表包含每个文件系统的信息
新挂载的文件系统，要向虚拟文件系统提供一个函数地址列表
将文件系统加载到挂载点（父目录）
文件空间管理
存储空间划分
将物理磁盘划分为一个个文件卷（逻辑盘，逻辑卷）
一个文件卷可以由多个物理磁盘组成
存储空间初始化
文件卷初始化
目录区
存放文件目录信息FCB，用于磁盘存储空间管理的信息
文件区
存放文件数据
空间管理
空闲表法
属于连续分配方式
为文件分配连续的存储空间
可采用首次适应，最佳适应，最坏适应
回收方式与动态分配相同
空闲链表法
空闲盘块链
将空闲盘块像链表一样链接起来
空闲盘块中保存指向下一个空闲盘块的指针
分配
通过适应算法找到符合条件的盘块
回收
将回收的盘块挂到链尾
分配回收简单，但效率低
空闲盘区链
几个连续的空闲盘块构成一个空闲盘区
盘区中第一个空闲盘块里记录盘区长度，指向下一个盘区的指针
分配
通常采用首次适应
回收
将回收区与相邻的空闲盘区合并
分配回收麻烦，但效率高
位示图法
利用二进制位bit来表示一个盘块是否使用
盘块号b = n×i + j
n表示字长
i表示字号（行号）
i = b/n
除
j表示位号（列号）
j = b%n
取余
连续分配和离散分配都适用
成组链接法
成组链块（超级块）用来存放空闲盘块的块号以及下一组空闲盘块数
空闲盘块的块号为成组块（盘区）的第一个盘块号
一个分组的数量有限，比如：只允许100个空闲盘块组成一个组
若没有下一组的空闲盘块，则块号设为-1
分配
从最后盘块开始分配，并更改超级块中空闲盘块数
若某一快内存放了下一组的信息，则要将信息复制到超级块后，再进行分配
回收
若超级块没满
则直接将回收块插入到超级块后
若超级块已满
类似链表的头插法
磁盘
结构
磁盘
磁道
扇区
就是磁盘块
每个扇区容量相同，最内层扇区密度最大
盘面
每个盘面对应一个磁头
柱面
所有盘面的相对位置相同的磁道组成柱面
磁盘地址用（柱面号-盘面号-扇区号）表示
磁盘调度算法
一次读写需要的时间
寻道时间
启动磁头臂
用时s
移动磁头
跨越一条磁道用时m，需要跨越n条磁道
= s + m×n
传输时间
读/写时间
转速r，读写的字节数为b，每个磁道上的字节数为N
= b /（r N）
延迟时间
磁盘转速为r
= 1/（2r）
磁盘调度算法
会直接影响寻道时间
先来先服务
最短寻找时间优先
可能产生饥饿现象
扫描算法
只有磁头移动到最内或者最外层磁道时才可以往反方向移动
即使最外层或者最内层没有处理请求也依然要移动到此才可以开始反方向移动
不会产生饥饿现象
look算法
扫描算法的改进
如果在磁头移动方向没有了其他的请求，则可以直接改变方向
循环扫描 （电梯调度）
解决扫描算法对于各个位置的响应不平均
在返回时不响应任何请求，直接移动至起始端
只有在移动到最边缘后才改变方向（与扫描算法相同）
c-look算法
循环扫描的改进
不需要移动到边缘才改变方向，移动方向没有其他请求就可改变方向
减少延迟的方法
交替编号
让逻辑上相邻的扇区在物理上有一定间隔
错位命名
让同一扇面内各个扇区相错开（如0扇区与1扇区之间隔着其他号扇区）
地址结构设计
柱面号-盘面号-扇区号
减少了磁头移动时间
磁盘管理
磁盘初始化
物理格式化
将磁盘各个磁道划分为扇区
分区
将磁盘分区，每个分区由若干柱面组成
逻辑格式化
创建文件系统
引导块
计算机开机要进行一系列初始化工作，通过执行自举程序完成初始化工作
完整的自举程序存放在磁盘的启动块（引导块）上，启动块位于磁盘的固定位置
坏块处理
坏块属于硬件故障
对于简单磁盘
坏块对操作系统不透明（会被标记）
对于复杂磁盘
扇区备用
对复杂的磁盘，磁盘控制器会维护一个坏块链表，在物理格式化时，进行初始化，利用备用扇区替换坏块
固态硬盘SSD
原理
基于闪存flash 属于电可擦ROM（EEPROM）
组成
闪存翻译层
翻译逻辑块号
找到对应的页
存储介质
多个闪存芯片
每个芯片包含多个块（blocks）
每个块包含多个页
读写性能
以页为单位
以块为单位
支持随机访问
读速度快 写速度慢
与机械硬盘的对比
SSD读写比机械硬盘快，随机访问
SSD安静无噪音
SSD的某个块多次擦除后会坏掉 机械硬盘的扇区不会因为写的多而坏掉
磨损均衡
将擦除操作平均到各个块上
动态磨损均衡
写数据时，优先选择累计擦除少的闪存块
静态磨损均衡
老旧的块担任 读操作 为主的任务 新块担任 写操作 为主的任务
静态比动态更加优秀
第五章IO管理
设备分类
块设备
数据交换以块为单位
传输速率高
字符设备
数据交换以字符为单位
传输速率低，不可寻址
低速设备
鼠标键盘
中速设备
打印机
高速设备
磁盘机，光盘机
io接口
设备控制器
位于CPU和设备之间
设备控制器与cpu的接口
包含数据线地址线控制线
设备控制器与设备的接口
控制器中有一个或多个设备接口
io逻辑
实现对设备的控制
设备控制器功能
接受识别CPU的命令
数据交换
标识和报告设备状态
地址识别
数据缓冲
差错控制
io端口
设备控制器中可以直接被CPU访问的寄存器
换句话说多个io端口组成了io接口
数据寄存器
状态寄存器
控制寄存器
CPU与io端口通信方法
独立编址
为每个端口分配一个端口号，只有操作系统使用特殊io指令才能访问端口
统一编址
每个端口被分配唯一的内存地址
io控制方式
程序直接控制方式
CPU循环检查外设状态，直到确定该字在io控制器的数据寄存器中
中断驱动方式
允许io设备主动打断CPU的运行并请求服务， 从而解放CPU
在每个数据需要传输时中断CPU
DMA方式
io设备和内存之间开辟直接的数据交换通路
在所要求的一批数据传送结束时中断CPU
CPU发出指令时，只能读或者写连续的数据块
通道控制方式
专门负责输入输出的处理机
是一种硬件
CPU发出io指令，指明通道程序的位置指明执行的io设备
通道执行内存中的通道程序
通道与CPU共享内存
io软件层次结构
用户io软件
实现假脱机技术spooling
虚拟设备技术
提高独占设备的利用率
将独占设备变为共享设备
缓和CPU高速与io设备低速的矛盾
通过软件方式
需要多道程序设计技术支持
系统在磁盘固定区开辟两个区域，输入输出井
在内存中开辟两个缓冲区：输入缓冲区 输出缓冲区
共享打印机
独占式设备
允许各个进程串行使用的设备
采用静态分配
共享设备
允许多个进程共同使用的设备
宏观意义上的同时使用 微观上仍然交替进行
采用动态分配
共享打印原理
系统将各个用户需要的打印请求放到磁盘的输入井，利用磁盘与内存与CPU的速度差来实现微观上的交替，宏观上的同时
设备独立软件（设备无关软件）
独立性
用户编程时使用的设备与实际设备无关
功能
管理逻辑设备表
只设置一张系统逻辑设备表LUT
为每个用户设置逻辑设备表LUT
差错控制
设备分配回收
分配考虑的因素
设备固有属性
设备分配算法
设备分配安全性
安全分配方式
进程发出io请求后就进入阻塞，直到完成io操作才解除
CPU与io设备变成了串行工作
不安全分配方式
进程发出io请求后，继续运行，并仍可发出io请求，只有在io请求得不到满足才进入阻塞
可能出现死锁
分配策略
静态分配
一开始就将所需的全部资源分配
动态分配
在进程执行过程中根据需要继续分配
设备分配的数据结构
通道，控制器，设备关系
设备控制表DCT
表示某一个设备，表项内容为设备的各个属性
控制器控制表COCT
通道控制表CHCT
每个通道对应一张CHCT
系统设备表SDT
包含全部设备的情况
分配步骤改进
用户提供逻辑设备名
通过逻辑设备名与物理设备名的映射（逻辑设备表LUT）
LUT表项包括逻辑设备名，物理设备名，设备驱动程序入口地址
缓冲管理
目的
解决输入输出速度比CPU处理速度慢而造成的数据堆积的问题
单缓冲
计算每块数据的处理时间
假设一个初始状态，计算下一次到达此状态花费的时间
输入到缓冲区的时间为T，缓冲区传送到工作区的时间为M，处理数据的时间为C
初始状态：工作区满，缓冲区空
处理每块数据用时：MAX（C，T）+M
公式供参考，具体问题具体分析，用甘特图
双缓冲
工作区空，一个缓冲区空一个缓冲区满
处理每块数据用时：MAX（C+M，T）
缓冲池
使并发进程有效地输入输出
实现io调度
用某种算法确定一个好的顺序来处理io请求
设备保护
设备被看作为特殊的文件，每个文件分配FCB，设置权限
设备驱动程序
对硬件设备的具体控制
计算数据所在磁盘的柱面号，磁头号，扇区号等
不同的设备需要不同的驱动程序
io应用程序接口
字符设备接口
get/put调用，向字符设备读写一个字符
块设备接口
read/write系统调用：读写字符 seek：修改
网络设备接口
网络套接字接口 socket系统调用：创建网络套接字，指明网络协议 bind：将套接字绑定到本地端口 connect：将套接字连接到远程地址 read/write：从套接字读写数据
阻塞/非阻塞io
阻塞io
程序发出io系统调用，进程转为阻塞态等待
非阻塞io
程序发出io系统调用，系统调用可迅速返回，进程无需阻塞等待