操作系统(全)
第一章 操作系统概述
1.1 概念
是计算机系统中最基本的软件, 对于设计者来说, 操作系统是资源的管理者, 对于普通终端用户来说是一个操作环境, 是执行各种操作的一个平台。主要功能是管理系统各个部件,给上层应用软件提供一个易于理解和编程的接口。
并发：指两个或多个事件在同一时间间隔内发生。宏观上是同时发生的，但微观上是交替发生的。
并行：指两个或多个事件在同一时刻同时发生。
区别图:
互斥共享方式: 虽然可以提供给 多个进程使用，但一个时间段内只允 许一个进程访问该资源
原语: 具有原子性。也就是说， 这段程序的运行必须一气 呵成，不可被“中断”
操作系统特征:
1) 并发
2) 共享 (与并发互为存在条件, 两个最基本特征)
3) 虚拟 (时分复用-如虚拟处理器, 空分复用-如虚拟存储器)
4) 异步
宏内核与微内核图:
大内核: 又名宏内核, 单内核, 操作系统的主要功能模块都作为系统内核, 高性能(不用频繁变态), 但代码庞大, 难维护。
微内核: 只把最基本的功能留在内核, 结构清晰, 低性能, 可靠与安全, 可移植
操作系统结构--分层结构:
操作系统结构--模块化结构:
模块化结构衡量标准:
内聚性: 模块内部各部分间的紧密程度。内聚性越高, 模块独立性越好
耦合度: 模块间相互联系和影响的程度。耦合度越低, 模块独立性越好
总结:
操作系统引导:
- 激活CPU, 读取ROM中的boot程序, 执行BIOS的指令
- 硬件自检
- 加载带有操作系统的硬盘
- 加载主引导记录MBR, 即告诉CPU去硬盘的那个主分区去找操作系统
- 扫描硬盘分区表, 加载硬盘活动分区, 识别含有操作系统的硬盘分区(活动分区)
- 加载分区引导记录PBR
- 加载启动管理器, 加载操作系统
开机原理图:
虚拟机:
1.2 操作系统的发展与分类
手工操作阶段:
批处理阶段 (单道批处理系统) :
批处理阶段 (多道批处理系统) : CPU与设备并行, 但多缺少交互性
分时操作系统:
实时操作系统:指计算机能及时响应外部事件, 在规定的严格时间内完成对该事件的处理。
区别与联系:
1.3 系统调用
即用户程序通过访管指令或陷阱指令, 来请求操作系统为其提供某种功能的服务
工作流程:
1) 将系统调用号和所需参数压入栈, 执行陷入指令(变核心态), 硬件和操作系统保护被中断进程的现场(PC, PSW, 通用寄存器内容入堆栈)
2) 根据系统调用入口表, 找到系统调用入口地址
3) 系统调用结束后, 恢复现场(中断返回指令--特权指令)
原理图:
变态:
内核态---->用户态：执行一条特权指令——修改PSW(程序状态字寄存器)的标志位为“用户态”，这个动作意味着操作系统 将主动让出CPU使用权
用户态---->内核态：由“中断”引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺 回CPU的使用权, 用户堆栈切换成系统堆栈(也属于该进程)。
1.4 中断机制
作用: 使操作系统内核前行夺回CPU控制权, 使CPU从用户态变为内核态
分类:
内中断: 陷入(软中断), 异常, 在执行指令时发生。
外中断: 时钟中断, I/O中断请求, 每个指令周期末尾检查是否有中断信号需要处理。
中断类型图:
第二章 进程管理
2.1 进程的简介
进程与程序:
程序是一个静态的概念, 由代码和数据组成, 进程是一个动态概念, 由程序和运行上下文组成。
进程的组成:
1) 进程控制块PCB
2) 程序段
3) 数据段
进程控制块PCB:
进程的状态图:
备注: PCB是有限的, 申请失败即创建失败, 若有PCB而资源不足(如内存)则处于创建态
进程的切换:
进程创建的原因:
1) 用户登录
2) 高级调度
3) 系统处理用户程序的请求
4) 用户程序的应用请求
2.2 线程的简介
"轻量级进程"。可以提高资源利用率和系统吞吐量
区别:
- 进程是系统资源分配的单位, 进程是CPU的调度单位。
- 线程的创建时间比进程短, 同一进程内的线程可以共享内存和文件资源。
- 一个进程中可以有多个线程, 进一步提高并发性。
- 线程同样有就绪, 阻塞, 和执行三种基本状态。
区别图:
线程控制块TCB:
2.3 线程的实现
2.3.1 用户线程
由一组用户级线程函数来完成线程的管理, 包括线程的创建, 终止, 同步和调度等。
特点:
- 由线程库函数来维护, 可以用于不支持线程技术的多进程操作系统。
- 不需要从用户态切换到内核态, 速度快。但调度仍然是进程为单位
- 当进程某个线程发出系统调用的请求时, 会把整个进程都阻塞起来, 影响其他线程的正常运行。
- 对线程的调度算法可以自定义
2.3.2 内核线程
在操作系统的内核实现线程机制, 由操作系统内核来完成线程的创建, 终止, 管理。
特点:
- PCB和TCB都存在内核空间中, 由内核维护, 一般的用户程序不能访问。
- 线程的创建, 终止和切换都是通过系统调用的方式来进行, 需要从用户态转换到系统态, 开销较大。
- 某个线程引起的系统调用而被阻塞, 不会影响到其他线程的运行。
- 线程是CPU调度的基本单位, 时间片是分配给线程的, 进程内线程越多, 获得的CPU时间就越多。
原理图:
2.4 进程间的通信
低级通信: 进程之间只能传递少量的控制信息, 如: 信号量。
高级通信: 进程之间可以传送任意数量的数据, 如: 共享内存, 消息传递, 管道。
2.4.1 共享内存
操作系统提供一些API函数, 运行多个进程把自己地址空间的某部分共享出来, 映射到相同的一块物理内存区域。分为基于数据结构的共享(低级通信)和基于存储区的共享
基于存储区的原理图:
基于数据结构的原理图:
2.4.2 消息传递
进程之间通过发送和接受消息来交换信息, 由操作系统来维护, 调用发送和接受操作来交换消息。
直接通信方式原理图:
间接通信方式:
2.4.3 管道
UNIX系统首创, 连接两个进程之间的一个打开的共享文件夹, 专门用于进程之间的数据通信。发送与接收互斥(半双工)。可多写进程, 但仅一个读进程。
原理图:
2.5 进程的互斥与同步
如果当前有一个进程正在使用共享数据, 那么其他进程暂时不能去访问该共享数据。
互斥的原因: CPU只有一个, 多个进程竞争的访问同一个共享资源。
临界区: 对共享内存或文件的访问, 可能会引起竞争状态的那段程序。
临界资源: 需要互斥访问的共享资源。
互斥访问原理图:
原则:
- 空闲让进: 临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
- 忙则等待: 当已有进程进入临界区时，其他试图进入临界区的进程必须等待；
- 有限等待: 对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
- 让权等待: 当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
2.5.1 软件实现互斥
单标志法:
主要问题: 违背空闲让进, 轮到p1使用时, p1不使用, 则p0一直不能使用
双标志先检查法:
主要问题：违反“忙则等待”原则, 检查和上锁不是原子操作。
双标志后检查法:
主要问题: 违背了“空闲让进”和“有限等待”, 两者都进不去。
Peterson 方法:
2.5.2 硬件实现互斥
1) 中断屏蔽方法: 利用 “开/关中断指令” 实现（与原语的实现思想相同), 不适用于多处理机；只适用于操作系统内核进程。
2) TestAndSet指令: 用硬件实现，执行的过程不允许被中断，只能一气呵成。
逻辑原理:
3) Swap指令: 用硬件实现，执行的过程不允许被中断，只能一气呵成。
逻辑原理图:
Swap 和 TSL 缺点：都是自旋锁（spin lock）, 不满足“让权等待”原则。
2.5.3 进程的同步
指在在多个进程中发生的事件之间存在某种时序关系, 即谁先做什么, 谁后做什么。
B优先A执行原理图:
2.5.4 信号量
由操作系统来维护, 用户进程只能通过初始化和两个标准原语(P, V)进行访问。信号量的正值表示空闲资源。负值表示正在等待进入临界区的进程个数。
原语: 在管态下执行, 执行过程中不会被中断的。
整形信号量: 会使进程处于忙等的状态
记录型信号量: 不存在忙等的现象, 有一个链表连接所有等待该资源的进程
示例图:
2.5.5 管程
定义: 代表共享资源的数据结构, 及对该共享数据结构实施操作的一组过程(函数)所组成的资源管理程序
组成:
- 管程的名称
- 局部于管程内部的共享数据结构说明
- 对该数据结构进行操作的一组过程
- 对局部与管程内部的共享数据设置的初始值
特征:
- 只能通过管程提供的特定入口才能访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程
- 各进程互斥访问管程由编译器实现
- 与信号量的区别在于信号量有值, 管程的条件变量是没有值(wait/signal)的。
2.6 经典的IPC问题
2.6.1 生产者 - 消费者问题
实现伪代码:
备注: 两个P操作不能顺序写反, 两个V操作顺序可以交换
2.6.2 多生产者-多消费者
问题:
实现:
备注: 缓冲区为1, 可以不设置互斥访问变量mutex。
2.6.3 哲学家就餐问题
问题描述: 每一位哲学家的动作只有两种: 进餐和思考, 进餐时哲学家会试图去获得左手和右手的筷子, 两只筷子到手后才能进餐, 思考时放回筷子。
实现思路:
1) 最多同时允许4个哲学家拿筷子
2) 要求奇数号哲学家先拿左边的筷子, 偶数号哲学家刚好相反
3) 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子
实现伪代码:
#define N 5 //哲学家个数
#define LEFT //第i个哲学家的左边
#define RIGHT //第i个哲学家的右边
#define THINKING //思考状态
#define HUNGRY //饥饿状态
#define EATING //就餐状态
int state[N]; //第i个哲学家的状态
semaphore mutex; //互斥信号量, 初始化为1
semaphore s[N]; //第i个哲学家的信号量, 初始为0
void philosopher(int i){
while(true){
think(); //思考中....
take(i); //拿筷子
eat(); //就餐
put(i); //放下筷子
}
}
void take(int i){
P(mutex); //进入临界区
state[i] = HUNGRY; //我饿了!
test(i); //试图拿两只筷子
V(mutex); //退出临界区
P(s[i]); //没有筷子则阻塞
}
void test(int i){
if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){
state[i]= EATING; //两把筷子到手
V(s[i]); //第i个人可以吃饭了
}
}
void put(int i){
P(mutex); //进入临界区
state[i] = ThINKING; //放下两只筷子
test(LEFT); //尝试唤醒左邻居
test(RIGHT);
V(mutex); //退出临界区
}
2.6.4 读者 - 写者问题
问题描述: 写者只允许一个, 读者可以有多个, 读写互斥。
读优先实现伪代码:
读写公平法伪代码:
reader (){
while(1){
P(w);
P(mutex);
if(count==0)
P(rw);
count++;
V(mutex);
V(w);
读文件…
P(mutex);
count--;
if(count==0)
V(rw);
V(mutex);
}
}
writer (){
while(1){
P(w);
P(rw);
写文件…
V(rw);
V(w);
}
}2.7 进程调度
CPU繁忙的进程: 大部分时间处于运行状态和就绪状态。
I/O繁忙的进程: 大部分时间处于阻塞状态。
不可抢占调度方式: 一个进程若被选中, 就一直运行下去, 直到被阻塞或主动交出CPU。
可抢占调度方式: 进程在运行时, 调度程序可以随时打断它。
三层调度:
高级调度: 作业调度(调入内存)
中级调度: 内存调度(7状态模型), 挂起, 调出外存, 但保留PCB
低级调度: 进程调度(调度算法)，处理机调度。
三层调度对比图:
7状态模型图:
调度与切换的时机:
1) 创建新进程后
2) 进程正常结束或异常终止后
3) 因I/O请求, 信号量等被阻塞时
4) I/O设备完成后发出I/O中断
调度算法的评价指标:
CPU利用率: CPU忙碌时间 / 总时间
系统吞吐量: 作业总数 / 总时间
周转时间: 作业完成时间 - 作业提价时间 (小作业比大作业小,体现不出, 因此有带权周转时间)
平均周转时间: 各周转时间总和/作业数 (排队上厕所例子, 一定时间内上厕所人数越多越好)
带权周转时间图:
等待时间: 等待处理机状态的时间之和
响应时间: 首次响应时间 - 提交时间
2.7.1 先来先服务(FCFS First Come First Serve)
按照作业到达的先后次序进行调度, 是一种不可抢占的调度方式。
特点:
- 对长作业有利, 对短作业不利
- 不会导致饥饿
2.7.2 短作业优先算法 （SJF, Shortest Job First）
要求作业在开始执行时, 必须实现预计好它的执行时间, 从中选择较短的作业优先分派处理器。
不可抢占方式: 即使来了一个更短的作业, 也不会被打断。
可抢占方式: 新的短作业到来, 当其运行时间小于正在运行的作业的剩余时间, 则立即抢占CPU。即 最短剩余时间优先算法（SRTN, Shortest Remaining Time Next）
特点:
- 平均等待时间短,平均周转时间最少
- 对短作业有利, 对长作业不利
- 会导致进程饥饿
2.7.3 高响应比优先（HRRN, Highest Response Ratio Next）
在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务 。
响应比: 等待时间+要求服务时间 / 要求服务时间
特点:
- 综合考虑了等待时间和运行时间,
- 对于长作业来说，等待时间越来越久，响应比越大，避免了长作业饥饿
三者对比图:
2.7.4 时间片轮转法（RR, Round-Robin）
就绪进程按照先来先服务的原则. 排成一个队列, 调度时, 将CPU执行权给队首进程, 执行一段时间片后, 将其送入到就绪队列队尾。在时间片用完前被阻塞或执行完时, 会立即让出CPU。
特点:
- 公平性, 各个就绪进程平均的分配CPU的使用时间。
- 时间片长度不好确认, 太长, 退化为先来先服务, 太短, 则增加系统开销。
2.7.5 优先级算法
每个进程都设置一个优先级, 然后在所有就绪的进程中选择优先级最高的运行。类似短作业优先算法, 以运行时间长短定优先级。优先级相同的采用优先级队列, 进行时间片轮转法。
静态优先级: 创建进程是确定进程的优先级并一直保持不变。缺点是低优先级可能一直处于饥饿状态。
动态优先级: 有初始优先级, 可根据进程的等待时间的增加而增加优先级, 或用完时间片后降低进程的优先级。
特点:
- 会导致饥饿
- 系统进程优先级 高于 用户进程, 更偏好 I/O型进程（或称 I/O繁忙型进程）
原理图:
2.7.6 多级反馈队列算法
引入多个就绪队列, 通过各个队列进行区别对待, 把CPU时间按比列分配给不同的队列。
原理图:
备注: 如果一个进程的时间片用完前被阻塞, 应当增加一个优先级。
特点:
- 抢占式的算法, 上级队列进程来到会抢占下级队列进程的处理机。
- 对各类型进程相对公平（FCFS的优点）
- 每个新到达的进程都可以很快就得到响应（RR的优点）
- 短进程只用较少的时间就可完成 （SPF的优点）
- 会导致饥饿
交互式系统调度算法的区别图:
2.7.7 实时系统的调度算法
硬实时系统: 有一个绝对的时间期限, 计算机的反应动作必须在此期限之前完成, 如: 火箭飞行控制系统。
软实时系统: 系统运行过程中, 偶尔超过基础期限是可以容忍的, 如: 影碟播放系统。
2.7.8 多级队列调度算法
示例图:
2.8 死锁
2.8.1 死锁概念
进程之间对资源的竞争访问所引发的相互等待, 相互妨碍的现象。
生活中的示例:
死锁定义: 在一组进程中, 每一个进程都占用着若干资源, 同时它又在等待另外一个进程所占用的其他资源, 从而造成所有进程都无法进行下去的现象。 这一组相关的进程称为死锁进程。
可抢占的资源: 进程正在使用资源时, 可以把它拿走而不会对该进行造成任何不良影响。
不可抢占的资源: 进程正在使用这种类型资源时, 强行拿走将导致该进程运行失败, 如光盘刻录机。
死锁发生的4个必要不充分条件:
- 互斥条件: 任何时刻, 每一个资源最多只能被一个进程所使用。
- 请求和保持条件: 进程在占用若干资源的同时有同时可以去申请新的资源。
- 不可抢占条件: 进程占用的资源, 不会被强行拿走, 必须由进程主动释放。
- 循环等待条件: 存在一条由两个或多个进程所组成的环路链, 每一个进程都在等待环路链中下一个进程所占用的资源。死锁一定有环。
2.8.2 死锁的检测
检测死锁的算法：在资源分配图中，找出既不阻塞又不是孤点的进程。消去它所有的请求边和分配变，使之称为孤立的结点。重复以上步骤。若能消去途中所有的边，则称该图是可完全简化的。
死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁
示例图:
死锁的解除:
进程回退: 类似快照功能, 回退的实现需要系统定期进行备份, 增加系统开销。
剥夺资源: 把资源从一个进程中剥夺出来, 被剥夺的进程付出的代价取决于资源自身性质。
撤销进程: 杀死进程, 尽可能选择那些能够安全重新运行的进程。
2.8.3 死锁的避免
当一个进程来申请一个资源时, 系统需先确认分配出资源时会不会有死锁的威胁, 没有才分配给进程。
银行家算法示例图:
备注: 系统处于安全状态，就一定不会发生死锁。不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态。
2.8.4 死锁的预防
破坏死锁产生的4个必要条件之一。
破坏互斥条件: 如给打印机设置打印队列, 解决了打印机的互斥访问。但这种方法不普遍。
破坏不剥夺条件: 某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。
破坏环路等待条件： 为资源编号, 进程只能申请已有资源编号之后的资源。
破坏请求和保持条件: 一种是要求进程一次性申请所有资源, 操作系统要么全部一次性分配, 要么一个也不分配。另一种是一个进程请求新资源时, 需释放所有占用的资源并重新申请。
优缺点:
第三章 内存管理
3.1 概述
存储管理, 就是对存储器进行管理, 通常说的存储管理, 主要指对内存的管理。
补充: 正文段存放常量值和全局变量。
冯 · 诺依曼体系结构:
存储器的层次结构:
内存分区的布局:
物理地址: 即内存地址, 只有通过物理地址, 才能对内存单元进行直接访问。
物理地址编号: 物理内存划分很多大小相等的存储单元, 如字节或字, 每个单位有一个编号, 如0x0000000到0xFFFFFFF
逻辑地址: 即相对地址或虚地址, 用户的源程序编译后形成目标代码, 首地址为0开始。
地址映射: 将用户程序中的逻辑地址转换为运行时有机器直接寻址的物理地址
3.1.1程序的装入和链接
1) 编译: 将用户源代码编译成若干目标模块
2) 链接: 将编译后形成的一组目标模块及它们所需的库函数链接在一起, 链接后形成逻辑地址
3) 装入: 由装入程序将装入模块装入内存
步骤图:
程序的三种链接:
1) 静态链接: 将目标模块及它们所需的库函数链接成一个完整的装配模块, 以后不在拆开
示意图:
2) 装入时动态链接: 装入内存时, 采用边装入边链接的方式, 便于修改和更新, 便于实现对目标模块的共享
示意图:
3) 运行时动态链接: 在程序执行中需要该目标模块时才进行, 能加快程序的装入过程, 节省内存空间
示意图:
装入的三种方式:
1) 绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。只适用于单道程序环境。
2) 静态重定位：又称可重定位装入。根据内存的当前情况，将装入模块装入 到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址。特点是必须分配其要求的全部内存空间, 在运行期间就不能再移动。
3) 动态重定位：又称动态运行时装入。把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址。这种方式需要一个重定位寄存器的支持。特点是允许程序在内存中发生移动。
3.1.2 内存保护
防止一个用户进程去访问其他用户进程的内存区域,
方法一：在CPU中设置一对上、下限寄存器，存放 进程的上、下限地址。
方法二：采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。重定 位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。
原理图:
3.1.3 覆盖技术***
把程序按照自身逻辑结构, 划分为若干功能上相对独立的程序模块。使任意时刻程序只有一部分内容放在内存中。但必须由程序员声明覆盖结构
具体原理:
- 将程序必要部分常驻内存
- 将程序的可选部分, 平时放在外存中, 需要才装入到内存
- 对于不存在相互调用关系的模块, 可以共用一个内存分区
示意图:
3.1.4 交换技术***
通过换入换出, 将一些暂时不能运行的进程送到外存中。即中级调度（内存调度）
换出: 把一个进程整个地址空间保存到外存的一个交换区中。
换入: 将外存中某个进程的地址空间读入到内存。
示意图:
3.1.5 程序的局部性原理
程序在执行过程中的一个较短时期内, 所执行的指令地址和指令操作数地址具有时间局部性和空间局部性。
时间局部性: 一条指令的一次执或数据的一次访问行和下一次执行或访问, 都集中在一个较短时期内。
空间局部性: 当前正在执行的指令和它邻近的几条指令, 正在访问的数据与邻近的几个数据, 都集中在一个比较小的区域内。
说明: 程序的运行过程中, 某一段时间内只有小部分内容处于活跃状态, 其他大部分内容可能处于休眠状态。TLB(快表),CPU中的高速缓存Cache便是基于局部性原理。
3.2 连续分配
3.2.1 单一连续分配
把内存分为两个区域: 系统区和用户区。每次把一个应用程序装入到用户区运行, 该进程始终独占整个用户区。
特点:
- 无外部碎片, 有内部碎片, 存储器利用率极低。
- 适合单用户, 单任务操作系统, 实现简单, 易于管理, 内存回收容易。
三种实现方式:
备注:
第二种方式中, 操作系统放在内存地址的最高端, 放在只读存储器中, 主要用于嵌入式系统
第三种方式中, 是早期个人计算机系统采用的方法, 操作系统分为两部分, 一部分在ROM中, 开机首先会被执行, 进行一些硬件检测和初始化工作, 然后把操作系统装入内存。
3.2.2 固定分区存储管理
把用户区分为若干个分区, 分区大小固定不变。
两种分区方式图:
分区不相等的两种实现方式 ***:
1) 多个输入队列: 为每个分区设置一个输入队列, 缺点是小分区队列容易满, 大分区的队列往往是空的。
2) 单个输入队列: 设置一个统一的输入队列, 某个分区空闲时, 选择合适的进程装入。
原理图:
单个输入队列算法***
1) 最先匹配法:选择距离队首最近的, 能够装入该分区的进程。装入小进程时会产生较大内部碎片。
2) 最佳匹配法: 选择能够装入该分区的最大进程, 尽可能少浪费空间。
固定分区的数据结构:
内部碎片:
外部碎片:
3.2.3 可变分区存储管理
不预先划分好固定的区域, 而是动态创建, 系统根据进程需求和内存使用情况来决定是否分配。
原理图:
可变分区的数据结构:
使用分区链表, 按照地址的递增顺序排列, 每个结点对应一个分区, 分区包含各种信息。
分区链表原理图:
基于顺序搜索分配算法:
1) 最佳适应: 从头开始找, 第一个符合的空闲结点, 尽量保证高地址部分的大空闲区。综合性能最好, 算法开销小
2) 临近适应 : 在上个分配结点继续往下找, 较大空闲分区不易保留。算法开销小
3) 最佳适应: 优先装入到大小最为接近的空闲分区, 缺点是可能产生太小碎片无法使用, 从而无法使用到。算法开销大
4) 最坏适应: 优先将最大的空闲区分割使用, 避免产生太小碎片, 但大分区也将没有。算法开销大
基于索引搜索分配算法:
1) 快速适应: 根据进程常用空间划分, 对空闲分区链表建议索引表
2) 伙伴系统: 分区大小均为的k次幂, 需要空间n时, 先在 中找, 没有则在
中找, 若有, 将大小为
分为2个分区, 一个用于分配,一个加入到空闲分区中。
3) 哈希算法: 建立以空闲分区大小为关键字的哈希表
内存紧缩技术:
把所有进程尽可能往内存地址的低端移动, 地址高端形成一个较大的空闲分区, 但需要大量CPU时间及会出现地址重定位问题。
原理图:
分区回收算法原理图:
3.3 非连续分配
3.3.1 页式存储管理
把内存划分为许多固定大小的内存快, 称为物理页面（页框=页帧=内存块=物理块), 把逻辑地址空间也划分为大小相等的快, 称为逻辑页面或简称页面, 页。
页面大小一般是2的整数次幂。以页面单位进行分配, 分配的物理页面不一定的连续的。
原理图:
页表: 一张一维的表格, 数组下标为逻辑页面号, 下标对应的是物理页面号。
页表图:
逻辑地址:
物理页面表: 使用位视图描述内存空间分配情况
地址映射:
逻辑页面号 = 逻辑地址 / 页面大小
页内偏移 = 逻辑地址 % 页面大小
原理图:
快速查找硬件(TBL):
基于程序的局部性原理, 存放最近一段时间内最常用的页表项, 减少访问内存次数, 提高效率。
示意图:
特点:
- 没有外碎片, 内碎片大小不超过页面大小。
- 页表必须连续存放
- 页面较大, 能装下一整个程序时, 退化为固定分区分配
多级页表: 一级页表结构下, 以页面4KB为例, 一个进程最多能有页表需占4MB(1048576个页表项)。进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。多级页表则可以避免这个问题。
示意图:
备注: 一般来说各级页表的大小不能超过一个页面
反置页表***: 物理页面号为索引, 逻辑页面号与进程标识符为内容。通过页号与进程标识符来找到块号, 从而找到物理地址。
示意图:
3.3.2 段式存储管理
在逻辑地址空间中, 对于程序中的每一个逻辑单元(如程序, 全局变量, 栈, 库函数等), 设立一个完全独立的地址空间, 称为段, 以段为单位进行可变分区分配。
分段对用户是可见的，用户编程时需要显式地给出段名。
原理图:
段表图:
地址映射图:
特点:
- 没有内部碎片
- 分段比分页更容易实现信息的共享和保护。如共享不能被修改的代码称为纯代码或可重入代码
- 存在外部碎片。
- 段的个数为1时, 退化为可变分区分配
分页与分段的区别:
1) 页是信息的物理单位, 段是信息的逻辑单位
2) 页的大小固定由系统决定, 段的长度不固定
3.3.3 段页式存储管理
在分段的基础上, 对段进行分页。
原理图:
段页式存储管理的逻辑地址:
示意图:
地址映射图:
3.4 虚拟存储技术
把物理内存与外存相结合; 装入程序时, 将当前需要执行的部分页面或段装入到内存即可执行, 当需要执行的指令或数据不在内存中, 称为缺页或缺段, 会产生一个硬件中断, 在中断处理程序中, 即可将相应的页面或段调入到内存。采用全相联映射和回写法。
3.4.1 虚拟存储管理
在页式存储管理的基础上, 增加请求调页和页面置换功能。
虚拟内存原理图:
页表表项图:
缺页中断原理图:
虚拟段页式存储管理的地址映变换机构图:
3.4.2 页面置换算法
即交换技术延伸。
1) 最优页面置换算法(OPT, Optimal): 优先淘汰等待时间最长的呗作为置换的页面。最优算法, 无法实现, 作为其他算法性能的评价依据。
2) 最近最久未使用算法(LRU, Least Recently Used): 基于程序局部性原理, 从内存中选择最近一段时间内最久没有被使用的页面。(维护一个页面链表, 缺页中断则淘汰链表末尾页面, 实现时系统开销大。)
3) 最不常用算法(LFU, Least Frequently Used): 选择访问次数最少的页面将其置换。
4) 先进先出算法(FIFO, First-In First-Out): 选择驻留时间最长的页面将其置换。可能出现Belady现象(配的物理页面越多, 反而缺页率越高的异常现象)
5) 时钟页面置换算法(CLOCK): 使用循环链表, 增访问位, 从驻留时间最长的开始, 将从未被访问过的淘汰出局, 被扫描过的则将访问位设为0。但未考虑是否被修改过。
改进型时钟页面置换算法规则:
第一轮：从当前位置开始扫描到第一个（0, 0）的帧用于替换。本轮扫描不修改任何标志位
第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。本轮将所有扫描过的帧访问位设为0。
第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0, 0）的帧用于 替换。本轮扫描不修改任何标志位。( 淘汰(1,0) )
第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0, 1）的帧用于替换。( 淘汰(1,1) )
备注: 选择一个淘汰页面最多会进行四轮扫描
原理图:
3.4.3工作集与驻留集模型
工作集: 指进程当前正在使用的逻辑页面的集合, 使用二元函数W( t , △ )来表示, 其中 t 表示当前执行的时刻, △表示工作集窗口。
工作集示意图:
驻留集: 分配给进程的页框集合。工作集是驻留集的子集, 则进程将会顺利运行, 反之会造成很多缺页中断。
抖动: 因频繁在内存与外存间替换页面, 从而使进程的运行速度非常慢,
缺页率算法:
3.4.4 页框分配
局部置换：发生缺页时只能选进程自己的物理块进行置换。
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换 到外存，再分配给缺页进程
固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即驻留集大小不变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。 即驻留集大小可变
知识补充图:
内存分配策略:
1) 固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。发生缺页，则只能从该进程在内存中的页面中选出一页换出
2) 可变分配全局置换：只要缺页就给分配新物理块, 空闲块用完时, 会选择调出系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
3) 可变分配局部置换：要根据发生缺页的频率来动态地增加或减少进程的物理块
预调页策略: 进程运行前, 成功率仅50%
请求调页策略: 进程运行时, 每次仅调入一页, 增加磁盘I/O开销
调入调出(对换区大):
调入调出(对换区小):
调入调出原理图(基于UNIX方式):
内存映射文件:
第四章 文件管理
4.1 文件目录
4.1.1 单级目录结构
系统中只建立一张目录表，每个文件占一个目录项。但是不允许文件重名。
单级目录图:
4.1.2 两级目录结构
分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory）。允许不同用户的文件重名。
两级目录结构图：
4.1.3 多级目录结构
又称树形目录结构, 不同目录下的 文件可以重名。
多级目录结构图:
4.1.4 无环图目录结构
在树形目录结构的基础上, 增加 一些指向同一节点的有向边，使整个目录成为一个有向无环图。以更方便地实现多个用户间的文件共享。需为每个共享结点设置一个共享计数器。
无环图目录示例图:
4.2 文件的逻辑结构
无结构文件：又称“流式文件”, 文件内部的数据就是一系列二进制流或字符流组成。如 Windows的.txt文件
有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录由若干个数据项组成。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录(无法实现随机存取)两种。
4.2.1 顺序文件
文件中的记录一个接一个地顺序排列（逻辑上） , 又分为串结构(无序), 顺序结构(关键字有序)
4.2.2 索引文件
可以用不同的数据项建立多个索引表。缺点是如果记录项短, 则空间利用率低
示例图:
4.2.3 索引顺序文件
一组记录对应一个索引表项。
索引顺序文件:
4.3 文件的物理结构（文件分配方式）
4.3.1 连续分配
即顺序结构, 把文件的各个逻辑块安装顺序存放在连续的物理块中。FCB中字段为<起始块号, 块数 或 结束块号>
特点: 磁盘访问最快, 存储空间利用率低。
示意图:
4.3.2 隐式链接分配
除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。
特点: 是访问文件只能顺序访问, 不能随机访问。
示意图:
4.3.3 显示链接分配
用于链接文件各物理块的指针显 式地存放在一张表中。即 文件分配表（FAT，File Allocation Table） 一个磁盘仅设置一张FAT。 开机时，将FAT读入内存，并常驻内存。
特点: 支持随机访问(访问第i个结点时, 不用访问前i个结点的物理块), 但文件分配表的需要占用一定的内存空间。
示例图:
4.3.4 索引结构
把文件的每一个逻辑块对应的物理块编号直接记录在一个物理块中, 此物理块做索引块。
特点: 支持随机访问。缺点是索引表需要占用一定的存储空间
示意图:
Unix文件系统的iNode(简化举例)
多级索引图:
混合索引：对于小文件，可以将盘块地址直接放入FCB, 较少的读磁盘次数就可以访问目标数据块。
示例图:
总结对比图:
4.4 文件存储空间管理
逻辑卷与物理盘的关系图:
4.4.1 空闲表法
适用于 “连续分配方式”, 可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
示例图:
4.4.2 空闲链表法
4.4.3 位示图法
4.4.4 成组链接法
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且要保 证内存与外存中的“超级块”数据一致。
分配: 根据空闲盘块号栈的指针, 若指向栈底的盘块号, 则该盘块号保存的是下一组空闲盘块号。
回收: 存入栈顶, 同时移动指针, 空闲盘块数满时, 将满的第一块地址存入新回收的盘块号, 并将其做为栈底。
4.5 文件概述
文件控制块(FCB): 存放控制文件需要的各种信息的数据结构, 实现按名存取, FCB的有序集合称为文件目录, 一个FCB就是一个文件目录项。
FCB:
磁盘索引结点: 存放在磁盘上的索引结点, 每个文件有一个唯一的磁盘索引结点。
内存索引结点: 存放在内存中的索引结点, 文件被打开时, 要将磁盘索引结点复制到内存的索引结点中。
4.5.1 文件保护
1) 口令保护: 为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”。“口令”存放在系统内部，不够安全。
2) 加密保护: 使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。保密性强, 加密解密需要时间。
异或加密示例图:
3) 访问控制: 在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-Control List, ACL），该表中记录了各个用户可以对该文件执行哪些操作。
示例图:
4.5.2 文件共享
基于索引结点的共享方式（硬链接）
基于符号链的共享方式（软链接）
软链接: 只有主文件才拥有指向其索引结点的指针, 共享文件只有该文件的路径名, 较硬链接查找速度慢。
4.5.3 文件系统结构
例子：假设某用户请求删除文件“D:/工作目录/学生信息…xlsx”的最后100条记录。
- 用户需要通过操作系统提供的接口发出请求――文件基本操作
- 由于用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项――文件目录
- 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限一文件保护
- 验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址――文件逻辑结构
- 知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址—文件物理结构
- 要删除这条记录，必定要对磁盘设备发出请求――磁盘管理
- 删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收――文件存储空间
4.5.4 文件系统布局
示意图:
MBR: 主引导记录, 用来启动计算机。分区表记录磁盘分区的地址大小
引导块: 功能是将该分区中存放的操作系统程序装入到内存(操作系统不一定需要在C盘)。
超级块: 包含文件系统的所有关键信息, 如分区的块数量, 块大小, 空闲块的数量和指针, 空闲的FCB数量和指针等
i结点: 存放所有索引结点
备注: 计算机启动后, 主板上的BIOS程序被执行, 检查并设置系统中各种硬件资源。将MBR当中的引导程序装入到内存中运行, 将活动分区(装有操作系统的分区)的引导块当中的程序装入到内存中运行, 即操作系统程序。
4.5.5 文件基本操作
创建文件:
- 在外存中找到文件所需的空间
- 根据文件的存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项
删除文件:
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
- 根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。
- 从目录表中删除文件对应的目录项。
打开文件:
- 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
- 将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。
示意图:
示例图:
备注: 对于访问打开文件表的索引, UNIX称为文件描述符, Windows称为文件句柄。
关闭文件:
- 将进程的打开文件表相应表项删除。
- 回收分配给该文件的内存空间等资源。
- 系统打开文件表的打开计数器 count 减1，若count = 0，则删除对应表项。
4.6 虚拟文件系统
普通的文件系统:
虚拟文件系统:
虚拟文件系统的特点：
①向上层用户进程提供统一标准的 系统调用接口，屏蔽底层具体文件系统的实现差异
②VFS要求下层的文件系统必须实现某些规 定的函数功能
③每打开一个文件，VFS就在主存中新建一个 vnode，用统一的数据结构表示文件
文件挂载:
①在VFS中注册新挂载的文件系统。
②新挂载的文件系统，要向VFS提供 一个函数地址列表
③将新文件系统加到挂载点（mount point），也就是将新文件系统挂载 在某个父目录下
第五章 I/O管理
5.1 I/O设备概述
即输入输出(Input/Output)设备, 如键盘, 鼠标, 打印机, 显示器, 磁盘网卡等。
分类图:
机械部件: 如我们看得见摸得着的鼠标/键盘的按钮。
电子部件: 通常是一块插入主板扩充槽的印刷电路板。
机械/电子示意图:
I/O控制器组成图:
设备控制器与CPU接口: 用于实现CPU与控制器之间的通信。
I/O逻辑: 负责识别CPU命令, 并向设备发出命令
控制器与设备的接口: 用于实现控制器与设备之间的通信, 一个设备控制器可以连接多个设备。
5.2 I/O 地址
每个设备控制器里面都有寄存器, 用于CPU通信, 如控制寄存器, 状态寄存器, 数据寄存器等。
5.2.1 I/O独立编址
给所有设备控制器中的每一个寄存器分配一个唯一的I/O端口地址。
特点: 需要专门的输入输出指令, 但易区分是对内存访问还是对I/O设备访问。缺点是增加控制电路的复杂性(需要I/O设备读写控制信号)
5.2.2 内存映像编址
把设备控制器中的寄存器都映射为一个内存地址, 用统一的访存指令就可以访问I/O端口。
特点: 编程方便, 无需专门I/O指令, 依靠不同地址判断访问的是内存还是I/O。缺点是占用了内存地址空间, 使主存地址空间变小, 且外设寻址时间长。
区别图:
5.2.3 混合编址***
把以上两种情况结合起来, 对于设备控制器中的寄存器, 采用独立编址, 对于设备缓冲区, 采用内存映像编址。
5.3 I/O 控制方式
即对设备控制器中的各种寄存器进行通信。
5.3.1 程序循环检测
独占查询: 即繁忙等待方式， 一直占用CPU
定时查询: CPU周期性查询接口状态
原理图:
5.3.2 中断驱动方式
即依赖硬件支持, 使用中断驱动方式, 在I/O操作完成后发送中断信号, 防止死等。
主程序和服务程序抢占CPU示意图:
程序中断方式:
5.3.3 DMA方式
数据的传送单位是“块”, 增加硬件, 独立于CPU运行, 可直接访问系统总线, 每一次的读写由DMA控制器来完成, CPU通过写操作对其发送命令。
原理图:
数据寄存器(DR): 暂存从设备到内存，或从内存到设备的数据。
数据计数器(DC): 表示剩余要读/写的字节数。
内存地址寄存器(MAR): 内存地址
命令/状态寄存器(CR): : 放CPU发来的I/O命令，或设备的状态信息。
中断方式与DMA方式图:
三种方式的CPU工作效率比较图:
5.3.4 通道控制方式
通道是一种硬件, 可以理解为是 “弱鸡版的CPU”。通道可以识别并执行一系列通道指令, 使CPU、通道、I/O设备可并行工作。
示意图:
字节多路通道: 用作连接大量的低速或中速设备
四种控制方式对比图:
5.4 I/O软件层次结构
软件的层次图:
用户层软件: 库函数与Spooling技术(实现对独占设备的共享, 如打印机的共享)。
设备独立性软件: 又称设备无关性软件。逻辑设备-物理设备映射、向用户层提供统一接口、数据缓冲区管理，执行所有设备公共操作, 如设备的分配与回收、I/O调度、设备保护, 差错处理。
设备驱动程序: 控制设备运行的程序, 由设备的生产厂商提供。负责实现系统对设备发出操作命令, 以及读取设备状态。
中断处理程序: I/O设备完成一次操作, 设备控制器向中断控制器发信号, 进而中断控制器向CPU发信号, 从而触发一次中断, 执行中断处理程序。
Spooling技术原理图:
输入缓冲区: 用于暂存从输入设备输入的数据，之后再转存到输入井(在磁盘中)中
输出缓冲区: 用于暂存从输出井(在磁盘中)送来的数据，之后再传送到输出设备上
备注: CPU将要打印数据经内存存放到磁盘, 待打印机空闲后再打印, 节省CPU时间。
5.5 设备分配与回收
静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源, 破坏了请求和保持, 不会死锁
动态分配：进程运行过程中动态申请设备资源
安全分配方式：为进程分配一个设备后就将进程阻塞，本次I/O完成后才将进程唤醒。破坏了请求和保持, 不会死锁, 但CPU和I/O设备只能串行工作。
不安全分配方式：分配I/O设备后，进程可继续执行，还可以发出新的I/O请求。只有某个I/O请求得不到满足时才将进程阻塞。进程与I/O并行处理, 但可能会死锁。
设备、控制器、通道关系图:
设备控制表（DCT）：系统为每个设备配置一张DCT，用于记录设备情况。
控制器控制表（COCT）：每个设备控制器都会对应一张COCT。每个控制器由一个通道控制。
通道控制表（CHCT）：每个通道都会对应一张CHCT。一个通道可为多个控制器服务。
系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目。
备注：只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动I/O设备进行数据传送
分配步骤:
①根据进程请求的逻辑设备名查找SDT
②分配设备, 从SDT中找出该设备的DCT
③分配控制器。根据DCT找到COCT，若控制器忙碌则将进程PCB挂到控制器等待队列中，不忙碌则将控制器分配给进程。
④分配通道。根据COCT找到CHCT，若通道忙碌则将进程PCB挂到通道等待队列中，不忙碌则将通道分配给进程。
逻辑设备表(LUT): 逻辑设备名与物理设备名的映射机制，用户编程时只需提供逻辑设备名。操作系统可以采用整个系统设置一张LUT和为每个用户设置一张LUT (类似于单级目录与两级目录)。
5.6 缓冲区管理
缓冲区是一个存储区域, 可缓解CPU与I/O设备之间速度不匹配。
1) 单缓冲: 当缓冲区数据非空时，不能往缓冲区冲入数据; 必须把缓冲区充满以后，才能从缓冲区把数据传出。
示例图:
2) 双缓冲
示例图:
结论：采用双缓冲策略，处理一个数据块的平均耗时为 Max (T, C+M)
双缓冲在通讯时:
3) 循环缓冲区: 将多个大小相等的缓冲区链接成一个循环队列。
示例图:
4) 缓冲池: 由系统中共用的缓冲区组成。
三个缓冲队列：空缓冲队列、装满输入数据的缓冲队列（输入队列）、装满输出数据的缓冲队列（输出队列）。
四种工作缓冲区：用于收容输入数据的工作缓冲区（hin）、用于提取输入数据的工作缓冲区（sin）、用于收容输出数据的工作缓 冲区（hout）、用于提取输出数据的工作缓冲区（sout）
示例图:
收容输入: 输入进程从空缓冲队首取空缓冲区, 将数据输入后挂到输入队列队尾
提取输入: 计算进程从输入队首取一个缓冲区, 提取数据后挂到空缓冲队列队尾
收容输出: 计算进程从空缓冲队首取空缓冲区, 将数据输入后挂到输出队列队尾
提取输出: 输出进程从输出队首取一个缓冲区, 提取数据后挂到空缓冲队列队尾
5.7磁盘
磁盘高速缓存: 在内存开辟一部分区域, 写磁盘是按"蔟"进行的, 可以避免频繁用小块数据写盘。
磁记录方式: 调频制(FM)和改进型调频制(MFM)
磁盘容量: 分非格式化容量(可利用磁化单元总数)和格式化容量(按照某种特定的记录格式所能存储信息的总量)。格式化后的容量比非格式化容量要小。
RAID(独立冗余磁盘阵列): 利用磁盘廉价的特点提高存储性能、可靠性和安全性。主要有以下几种:
RAID0: 提高存取速度, 没有容错能力
RAID1: 镜像磁盘互为备份
RAID2~5: 通过数据校验提高容错能力
磁盘初始化:
低级格式化: 即物理格式化, 将磁盘的各个磁道划分为扇区。检测坏扇区并替换(对操作系统透明)
磁盘分区: 如C盘、D盘、E盘(同柱面为一个区)
逻辑格式化: 创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如 位示图、 空闲分区表）
引导块:
计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序 (自举程序) 完成的。
初始化程序 ( 自举程序 ) 如果直接放在ROM（只读存储器）中。ROM中的数据在出厂时就写入了。并且以后不能再修改，会很不方便。
解决方法：
- 完整的自举程序放在磁盘的启动块(即引导块/启动分区）上，启动块位于磁盘的固定位置。
- ROM中只存放很小的 “ 自举装入程序 ”。
- 开机时计算机先运行 “ 自举装入程序 ”，通过执行该程序就可找到引导块，并将完整的 “ 自举程序 ” 读入内存，完成初始化。
- 拥有启动分区的磁盘称为启动磁盘或系统磁盘（C盘）
磁盘地址:
5.7.1 磁盘的组成
由磁盘驱动器, 磁盘控制器和盘片组成。
柱面: 由所有盘面上, 半径相同的所有磁道组成。
扇区: 对于每一个磁道, 平均划分为一个个的小格子, 每个小格子就是一个扇区。
磁盘结构图:
盘面结构:
磁盘的读写: 以扇区为单位, 一般为512B, 修改一个字节也需一个扇区整体重写。
固定头磁盘:
5.7.2 磁盘调度算法(决定寻道时间)
访问一个磁盘扇区时间 = 寻道时间 (移动磁头)+ 旋转延迟时间(找扇区) + 数据传输时间
先来先服务（FCFS）: 效率不高, 但公平。
最短寻找时间优先算法（SSTF）: 优先选择从当前磁头出发, 移动距离最短的先访问。如果需要访问的扇区位于磁盘中间, 会比较有利; 位于磁盘两端, 则不利。可能产生“饥饿”
扫描算法（SCAN）: 从当前位置出发, 先沿一个方向, 然后再换一个方向, 对于任何一组访问, 磁头移动距离最多为柱面的总数的两倍。
循环扫描算法（C-SCAN）: 返回时直接快速移动至起始 (默认LOOK调度, 即磁头移动到请求中最外侧即可) 端而不处理任何请求。
5.7.3减少磁盘延迟时间
交替编号:
错位命名:
5.7.4 固态硬盘
数据以页为单位读写, 只有一页所属的整个块被擦除后, 才能写这一页, 因此随机写较慢。(以块为单位擦除)
擦写次数限制: 浮栅晶体管擦写的过程中，电子反复在隧穿层反复进出，导致隧穿层损坏，不能有效的阻拦电子，失去了隧穿层应有的作用。
磨损均衡技术:
1) 动态磨损均衡: 写入数据时, 优先选择累计擦除次数少的
2) 静态磨损均衡: SSD监测并自动进行数据分配、迁移、让老旧的闪存块承担以读为主的存储任务。(优于动态磨损)
原理图:
备注: 隧穿层本质上也相当于绝缘体，所以电子们只能被关押着, 但随着时间的流逝，不断地有电子“越狱”成功。即固态硬盘能够存储数据的年限。
原理参考: SSD原理
注: 以上内容图片主要参考王道计算机网络!!!
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
63
0- 0
已为社区贡献3条内容
所有评论(0)