操作系统（简化版）
2025-04-07 08:33:12 0 举报AI智能生成
操作系统是计算机硬件与软件资源的管理者和协调者，控制程序运行并提供用户操作界面。核心内容包括进程管理、内存管理、文件系统和输入输出系统。操作系统文件类型多样，如Linux下的`.bin`、`.sys`、`.conf`，Windows下的`.exe`、`.dll`、`.ini`，以及适用于多个平台的脚本文件如`.sh`、`.bat`。修饰语可能强调其功能性，如“多任务处理的操作系统”，或描述其用户友好度，“直观易用的操作系统界面”。
作者其他创作
大纲/内容
计算机概述
基本概念
特征
并发
两个事件或多个事件在同一“时间间隔”内发生
共享
互斥共享方式
规定在一段时间内只允许一个进程访问该资源
同时访问方式
资源允许在一段时间内由多个进进程同时访问，例如磁盘
虚拟
时分复用技术
例如处理器的分时共享
空分复用技术
例如虚拟存储器
异步
多道程序环境允许多个程序并发执行，但由于资源有限，进程的执行并不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进，这就是进程的异步性
功能
处理机管理
处理机的分配和运行都是以进程为基本单位，因而对处理机的管理可归结为对进程（或线程）的管理
存储器管理
方便用户使用及提高内存的利用率，主要包括内存分配与回收，地址映射、内存保护与共享和内存扩充等功能
文件管理
计算机中的信息都是以文件的形式存在的，文件管理包括文件存储空间的管理，目录管理以及文件读写管理和保护等
设备管理
设备管理的主要任务是完成用户的I/O请求，方便用户使用各种设备，主要包括缓冲管理、设备分配、设备处理和虚拟设备等功能
作业管理
向用户提供接口
命令接口
联机命令接口（交互式命令接口）
说一句，做一句
脱机命令接口（批处理命令接口）
说一堆，做一堆
程序接口
程序接口由一组系统调用（也称广义指令）组成，用户通过在程序中使用这些系统调用来请求操作系统为其提供服务。
发展与分类
手工操作阶段
缺点：1.用户独占全机，资源利用率低 2.CPU等待手工操作，CPU的利用不充分
批处理阶段
单道批处理系统
自动性：磁带上的一批作业能自动的逐个运行
顺序性：磁带上的各道作业顺序的进入内存，先调入内存的作业先完成
单道性：内存中仅有一道程序运行
多道批处理系统
特点
多道
宏观上并行
微观上串行：多道程序轮流占有CPU，交替执行
优点
资源利用率高：多道程序共享计算机资源，各种资源得到充分利用<br>
系统吞吐量大：CPU和其他资源保持忙碌状态<br>
缺点
用户响应的时间较长<br>
不提供人机交互能力：用户既不能了解自己的程序的运行情况，又不能控制计算机<br>
分时操作系统
同时性：允许多个终端用户同时使用一台计算机
交互性：能够方便的与系统进行人机对话<br>
独立性：多个用户可以在同一时间内独立使用计算机资源
及时性：请求能在很短时间内获得响应<br>
实时操作系统
硬实时系统：某个动作必须绝对的在规定的时刻发生或规定的时间范围，如飞行自动控制系统<br>
软实时系统：接受偶尔违反时间规定，且不会引起任何永久性的损害，如飞机订票系统、银行管理系统<br>
特点
及时性
可靠性
网络操作系统<br>
计算机网络中的各台计算机有机地结合起来，实现各台计算机之间数据的互相传送
分布式操作系统
分布式操作系统与网络操作系统的本质不同是分布式操作系统，中的若干计算机相互协同完成同一任务
个人计算机操作系统
中断
中断的分类
内中断
自愿中断
指令中断
强迫中断
硬件故障
软件中断
外中断（强迫中断）
外设请求
人的干预
中断处理的过程
1.关中断
2.保存断点
3.中断服务程序寻址
4.保存现场和屏蔽字
5.开中断
6.执行中断服务程序
7.关中断
8.恢复现场和屏蔽字
9.开中断、中断返回
体系结构
大内核<br>
大内核系统将操作系统的主要功能模块都作为一个紧密联系的整体运行在核心态
微内核
为解决操作系统的内核代码难以维护的问题，提出了微内核的体系结构。它将内核中最基本的功能（如进程管理等）保留在内核，而将那些不需要再和心态执行的功能移到用户态执行，从而降低了内核的设计复杂性
缺点：微内核结构的最大问题是性能问题，因为需要频繁的在核心态和用户态之间进行切换，操作系统的执行开销偏大
进程管理
进程
概念：进程是程序的一次执行过程，是一个程序及其数据在处理机上顺序执行时所发生的活动
特征<br>
动态性<br>
进程是程序的一次执行，他有着创建、活动、暂停、终止等过程
并发性<br>
指多个进程实例同时存于内存中，并在一段时间内同时运行
独立性<br>
指进程实体，是一个能独立运行、独立获得资源和独立接受调度的基本单位
异步性<br>
进程按各自独立的、不可预知的速度向前推进
结构性
从结构上看，进程实体是由程序段、数据段和进程控制块三部分组成
状态
运行态<br>
在处理机环境下，每个时刻最多只有一个进程处于运行态
就绪态<br>
进程获得了除处理之外的一切所需资源，一旦得到处理器便可立即运行
阻塞态
进程正在等待某一事件而暂停运行，即使处理机空闲该进程也不能运行
创建态<br>
进程正在被创建，尚未转到就绪态
结束态
进程正在从系统中消失，首先将该进程设置为结束态，然后进一步处理资源释放和回收等
结构
进程控制块PCB
进程描述信息：1、进程标识符标志各个进程 2、用户标识符主要为共享和保护服务
进程控制和管理信息：1、进程当前状态 2、进程优先级<br>
资源分配清单：说明有关内存地址空间或虚拟地址空间的状况<br>
处理机相关信息：寄存器的值
程序段<br>
程序段就是能被进程调度程序调度到CPU执行的程序代码段
数据段
一个进程的数据段可以是进程对应的程序加工处理所需要的原始数据，也可以是程序执行时产生的中间或最终结果
进程间通信
共享存储
通过对一个空共享空间进行写/读操作，实现进程之间的信息交换
消息传递
直接通信方式<br>
发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息
间接通信方式
发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息。例如邮箱
管道通信
半双工管道
某一时刻只能单向传输，并且写完才能读，读完才能写
全双工管道
某一时刻只能单向传输
线程
线程的实现分类
用户级线程<br>
用户及线程指所有工作都有应用程序完成，内核意识不到线程的存在。
内核级线程
内核及线程是指线程管理的所有工作由内核完成
组合方式<br>
用户及线程与内核级线程相结合
多线程模型
多对一模型
定义：将多个用户级线程映射到一个内核极线程
优点：线程管理是在用户空间进行的，因而效率比较高<br>
缺点：一个线程在使用内核服务时被阻塞，整个进程都会被阻塞。多个线程不能并行的运行在多处理机上
一对一模型：
定义：将每个用户级线程映射到一个内核线程<br>
优点：当一个线程被阻塞后，允许另一个线程继续执行。所以并发能力强
缺点：每创建一个用户一线程，都需要创建一个内核的线程与其对应，这样创建线程开销比较大，会影响到应用程序的性能
多对多模型
集两者之所长
进程调度
调度层次<br>
作业调度(高级调度)
从外存给作业(程序任务)分配内存等资源，建立相应进程并给予争夺处理机的权力。
内存调度(中级调度)<br>
将暂时不能运行的进程调至外存等待，将此时进程状态称为挂起态
，即内存调往外存
进程调度(低级调度)
按照某种方法、策略，从就绪队列中选取一个进程，将处理机分配给它
调度时机<br>
可以进行切换
主动放弃<br>
正常终止
程序运行完了
发生异常<br>
地址越界、除零异常、算数溢出等
请求阻塞<br>
(如 I/O请求)有事件未满足，转为阻塞态
被动放弃<br>
时间片用完<br>
优先级处理<br>
中断处理结束
不能进行切换
中断处理过程中(关中断,原语)<br>
进程在操作系统内核程序临界区中<br>
完全屏蔽中断的原子操作(原语)<br>
进程调度的方式
非剥夺方法/非抢占式<br>
正在执行的进程处理完成或发生某种事件而进入阻塞态时，才把处理机分配给更为重要或紧迫的进程
剥夺方法/抢占式方法<br>
优先权处理
短进程优先<br>
时间片原则
调度的性能标准<br>
CPU利用率
CPU使用时间占总时间的比例。
系统吞吐量<br>
单位时间内CPU完成作业数量
周转时间
定义：作业提交到作业完成的时间间隔
平均周转时间<br>
总周转时间/作业数
带权周转时间<br>
作业周转时间 / 实际运行时间
平均带权周转时间
对每一个作业求出带权周转时间，再对其求平均值
等待时间<br>
进程等待调度的时间片总和
响应时间<br>
从用户提交请求到系统首次产生响应所使用的时间
经典调度算法<br>
先来先服务 FCFS<br>
短作业优先 SJF/SPN
优先级调度
非剥夺式优先级调度算法
当某个更为重要或紧迫的进程进入就绪队列，仍然运行正在运行的进程，直到其自身的原因而主动让出处理机时，才把处理机分配给更为重要和紧迫的进程
剥夺式优先级调度算法
当某个更为重要或紧迫的进程进入就绪，队列立即暂停正在运行的进程，将处理器分配给更重要或紧迫的进程
静态优先级
优先级始终保持不变
动态优先级<br>
根据进程情况的变化动态调整优先级
高响应比优先 HRRN<br>
是对先来先服务调度算法和短作业优先调度算法的一种综合平衡
时间片轮转调度<br>
先来先服务的原则，但仅能运行一个时间片
多级反馈队列调度<br>
动态调整进程优先级和时间片大小，时间片从小到大，优先级从大到小
完全公平调度器 CFS
进程同步/互斥
基本概念
临界资源：一次只允许一个进程使用的资源，例如：打印机等<br>
临界区：访问临界资源的代码，又称临界段
同步/<font color="#B71C1C">直接</font>制约关系：进程之间有先后工作次序
互斥准则
空闲让进
允许进程访问空闲的临界资源
忙则等待<br>
不能同时进入临界区
有限等待
进入临界区时间有限，不能让其他进程一直等待
让权等待<br>
进程不能进入临界区时，应立即释放处理器（进程等待事件发生时，应该放弃CPU）
临界区互斥实现方法
软件实现
单标志法
两个进程交替进入临界区
双标志先检查
先检查后上锁访问
双标志后检查<br>
“礼让算法”，先表明自身访问意图，再检查对方访问意图，如果对方想要访问，则进行礼让。
皮特森算法<br>
礼让算法的改进
硬件实现<br>
中断屏蔽(关中断)<br>
因为CPU只在发生中断时引起进程切换，所以在临界区中禁止一切中断发生，称之为屏蔽中断、关中断
硬件指令方式
TestAndSet指令<br>
Swap指令
信号量<br>
类型<br>
整型信号量<br>
记录型信号量<br>
操作<br>
利用信号量实现互斥<br>
利用信号量实现同步
利用信号量实现前驱关系
管程
引入管程的原因：解决信号量机制编程麻烦，易出错的问题
功能：管程是用来实现资源的同步和互斥的资源管理程序（一个类）
条件变量condition
两种操作
wait：阻塞（相当于P操作）
signal：唤醒（相当于V操作）
进程死锁<br>
定义
<font color="#B71C1C">两个或以上</font>的进程（或线程）在执行过程中，因争夺资源而造成的一种<font color="#B71C1C">互相等待</font>的现象，若无外力作用，它们都将无法推进下去
死锁产生的必要条件
互斥<br>
不可剥夺
进程所获得的资源在未使用之前不能被其他进程强行夺走，只能由获得该资源的进程自己来释放
请求与保持<br>
进程已经保持了至少一个资源，但又提出新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己获得的资源保持不放
循环等待
指的是存在一种进程资源的循环等待链，链中每个进程已获得的资源都被链中下一个进程所需求
死锁的处理策略
预防
破坏互斥条件
允许系统资源都能被共享使用
破坏不可剥夺条件
某资源可以抢占其他程序正在使用的资源
破坏请求与保持条件
进程在运行之前申请完需要的全部资源
破坏循环等待条件
可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源。同类资源（即编号相同的资源）一次申请完
避免
银行家算法<br>
前提：手里掌握100亿
系统安全状态
安全性算法
相关数据结构
可利用资源向量Available：剩余多少向量可以使用
最大需求矩阵Max：n个进程中，对m类资源的最大需求<br>
分配矩阵Allocation：对于当前n个进程(列下标)所对应m个资源已经分配的数量<br>
需求矩阵Need：表示每个进程接下来还需要多少资源
请求向量Request：某个进程请求需要多少向量
算法描述
检测与解除
死锁定理（检测是否死锁）
某状态下的资源分配图是不可完全简化（按一定次序消除所有边）的
资源分配图
死锁解除<br>
资源剥夺法
挂起某些死锁进程，并抢占他的资源，将这些资源分配给其他的死锁进程（挂起进程抢资源）
进程撤销法
强制撤销部分甚至全部死锁进程，并剥夺这些进程的资源（撤销进程抢资源）
进程回退法
让一个或多个进程回到足以回避死锁的地步（回退进程抢资源）
内存管理
基本概念
原因和概念：计算机不可能将所有用户进程和系统所需的全部程序与数据放入储存，因此操作系统必须对内存空间进行合理的划分和有效的动态分配。操作系统对内存的划分和动态分配就是内存管理的概念
功能
内存空间的分配和回收<br>
由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率
地址转换<br>
在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此，存储管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址
内存空间的扩充(虚拟技术)
利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存
存储保护<br>
保证各道作业在各自的存储空间内运行，互不干扰
程序执行过程
链接模块<br>
静态链接<br>
在程序运行前，先将目标模块以及库函数链接成一个完成的可执行程序模块
装入时动态链接
在用户源程序编译后得到的目标模块装入内存时，边装入便链接
运行时动态链接
在程序执行中需要该目标模块时才链接
装入内存<br>
绝对装入<br>
程序的逻辑地址与内存地址完全相同，不需要对程序和数据的地址进行修改
可重定位装入/静态重定位
一次性装入内存，同时分配全部内存空间，装入时对目标程序中指令和数据进行一次性修改
动态运行时装入/动态重定位<br>
地址转换推迟到程序真正要执行时才进行
内存保护的两种方法
上、下限寄存器
在CPU中设置一对上、下线寄存器，存放用户作业在主存中的下限和上限地址。每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界
重定位寄存器和界地址寄存器<br>
内存管理机构动态的将逻辑地址与界地址寄存器进行比较，若未发生地址越界，再加上重定位寄存器的值后映射成物理地址再送交内存单元
扩充内存
覆盖
由于程序运行时，并非任何时候都要访问程序及数据的各个部分。因此可以把用户空间分成一个固定区和若干覆盖区，将经常活跃的部分放在固定区域，其余部分按调动关系分段。首先将那些即将要访问的段放入覆盖区，其他不常访问的段都放在外存中，在需要调用前，系统再将其调入覆盖区替换覆盖区中原有的段
交换<br>
交换的基本思想是把处于等待状态的程序从内存移到辅存，把内存空间腾出来，这一过程又称换出，把准备好竞争CPU运行的程序从辅存移到内存，这一过程又称换入
内存分配方式
连续分配方式<br>
单一连续分配
内存在此方式下分为系统区和用户区。系统区仅供操作系统使用，通常在低地址部分，用户区是为用户提供的内存空间。用户区中的内存永远只能存放一道程序
固定分区分配
是一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业
动态分区分配/可变分区分配<br>
是一种动态划分内存的分区方法。这种分区方法不预先划分内存，而是在进程装入内存时，根据进程的大小动态的建立分区，并使分区的大小正好适合进程的需要
非连续分配方式
基本分页存储
三个基本概念
页面和页面大小：进程中的块称为页，内存中的块称为页框，页和页框一一对应；页面太小会使进程页面数过多，列表就会过长，占用大量内存，增加硬件地址转换的开销。页面过大又会使业内碎片增多，降低内存的利用率<br>
逻辑地址结构
页号：页在进程中的页号
页内偏移量：在进程中某逻辑地址相对于页面起始位置的偏移量<br>
页表
页号：为页表中每个块按顺序编号
块号：对应内存物理地址块号
页表项：一个页表项由一个页号和一个块号组成，一个页表项占三个字节
基本地址变换机构
具有快表的地址变换机构：将经常访问的页表项存储在CPU的高速缓存器（快表）中，下次要访问某个页表项时现在高速缓存器中查找，如果没有再去主存中的页表（慢表）中查找。
两级页表：一般情况下一个进程的页表项是成千上万的，如果将进程的页表全部存放在内存的话会占用许多内存，所以衍生出了二级页表，将二级页表的顶级页表常驻内存，而二级页表存放在外存，在寻找页表项的时候根据顶级页表找到对应二级页表的页表项（编号），然后将该二级页表从外存中调入内存，再在二级页表中索引具体要找的页表项。（视情况可以构造多级页表）
基本分段存储
分段<br>
将地址空间按照程序自身的逻辑关系划分为若干个段，每段从0开始编址<br>
每个段在内存中占据连续空间，但各段之间可以不相邻<br>
逻辑地址：（段号，段内地址）<br>
段表
记录逻辑段到实际存储地址的映射关系<br>
每个段对应一个段表象。各段表象长度相同，由段号（隐含）段长、基址组成<br>
地址变换机构
分页VS分段
分页对用户不可见，分段对用户可见
分页的地址空间是一维的，分段的地址空间是二维的<br>
分段更容易实现信息的共享和保护（纯代码，可重入代码可共享）<br>
分页（单机列表）、分段访问一个逻辑地址都需要2次保存；分段存储中也可以引入快表机构<br>
段页式存储
分段+分页<br>
将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面
将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
逻辑地址结构:(段号，页号，页内偏移量)
段表、页表<br>
每个段对应一个段表项。各段表项长度相同，由段号(隐含) 、页表长度、页表存放地址 组成
每个页对应一个页表项。各页表项长度相同，由页号隐含) 、页面存放的内存块号 组成<br>
地址变换<br>
访问一个逻辑地址所需访存次数<br>
第一次一-查段表、第二次一一查页表、第三次一一访问目标单元<br>
可引入快表机构，以段号和页号为关键字查询快表，即可直接找到最终的目标页面存放位置。引入快表后仅需一次访存<br>
虚拟内存
定义：程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据
页面置换算法
最佳置换算法
算法规则：优先淘汰最长时间内不会被访问的页面
优缺点：缺页率最小，性能最好;但无法实现
先进先出页面置换算法
算法规则:优先淘汰最先进入内存的页面
优缺点：实现简单:但性能很差可能出现Belady异常
最近未使用置换算法
算法规则：优先淘汰最近最久没访问的页面
优缺点：性能很好:但需要硬件支持，算法开销大
时钟置换算法
算法规则：循环扫描各页面第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第一轮没选中，则进行第二轮扫描
优缺点：实现简单，算法开销小:但未考虑页面是否被修改过
改进时钟置换算法
算法规则：若用(访问位,修改位) 的形式表述，则第一轮:淘汰 (00)第二轮:淘汰 (0,1)，并将扫描过的页面访问位都置为0第三轮:淘汰 (0,0)第四轮:淘汰 (0, 1)
优缺点：算法开销较小，性能也不错
抖动(点颠簸) 现象：页面频繁换入换出的现象。主要原因是分配给进程的物理块不够
文件管理
文件的概念
文件的定义:一组有意义的信息的集合
文件的属性:文件名、标识符、类型、位置、大小、保护信息...
文件的基本操作
创建文件 (create系统调用）
删除文件 (delete系统调用)
读文件 (read系统调用)
写文件 (write系统调用）
打开文件 (open系统调用）
关闭文件 (close系统调用）
文件的逻辑结构
无结构文件：由一系列二进制或者字符流组成，例如文本文件
有结构文件
顺序文件
结构
串结构
记录之间的顺序与关键字无关（相当于数组有下标，但下标无序）
顺序结构
记录之间的顺序按关键字顺序排列（相当于数组有下标）
存储方式
链式存储
无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找
缺点：无法实现随机存储
顺序存储
可变长记录
无法实现随机存取。每次只能从第一个记录开始依次往后查找
定长记录
若采用串结构，无法快速找到某关键字对应的记录
若采用顺序结构，可实现随机存取。记录长度为L，则第 i 个记录存放的相对位置是 i*L；也可以快速找到某关键字对应的记录 (如折半查找)
缺点：增加/删除一个文件比较困难
索引文件
建立一张索引表，每个表项指向一个记录。各记录不用保持顺序（想当于数组没有下标），方便增加/删除记录
索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取
若索引表按关键字顺序排列（想当于数组有下标），则可支持快速检索
解决了顺序文件不方便增删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间（因为可能有很多个记录对应很多个表项占用大量空间）
索引顺序文件
将多个记录形成一个分组，然后对应一个表项
检索记录时先顺序查索引表，找到分组，再顺序查找分组
当记录过多时，可建立多级索引表
文件目录
目录结构
单级目录结构
一个系统只有一张目录表，不允许文件重名
两级目录结构
不同用户的文件可以重名，但不能对文件进行分类
多级 (树形)目录结构
不同目录下的文件可以重名，可以对文件进行分类，不方便文件共享
系统根据“文件路径”找到目标文件
从根目录出发的路径是“绝对路径”(“/照片/2015-08/自拍.jpg")
从“当前目录"出发的路径是“相对路径”(“/2015-08/自拍2.jpg”)
无环图目录结构
在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，方便共享
为共享结点设置一个共享计数器，计数器为0时才真正删除该结点
文件的物理结构
连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。
优点:支持顺序访问和直接访问(即随机访问);连续分配的文件在顺序访问时速度最快
缺点:不方便文件拓展:存储空间利用率低，会产生磁盘碎片
链接分配
隐式链接
除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针
优点:很方便文件拓展，不会有碎片问题，外存利用率高
缺点:只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量
显示连接
把用于链接文件各物理块的指针显式地存放在一张表中，即 文件分配表 (FAT，FileAllocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。
优点:很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高
缺点:文件分配表的需要占用一定的存储空间
索引分配
若文件太大，索引表项太多，可以采取以下三种方法解决
链接方案
如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放
缺点:若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入 O~i-1号索引块，这就导致磁盘I/0次数过多，查找效率低下。
多层索引
建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K 层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作
缺点:即使是小文件，访问一个数据块依然需要K+1次读磁盘
混合索引
多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。优点:对于小文件来说，访问一个数据块所需的读磁盘次数更少。
文件存储空间管理
空闲表法
空闲表中记录每个连续空闲区的起始盘块号、盘块数
分配时可采用首次适应、最佳适应等策略;回收时注意表项的合并问题
空闲链表法
空闲盘块链
以盘块为单位组成一条空闲链
分配时从链头依次取出空闲块，回收时将空闲块查到链尾
空闲盘区链
以盘区为单位组成一条空闲链
分配时可采用首次适应、最佳适应等策略;回收时注意相邻空闲盘区合并的问题
位示图法
一个二进制位对应一个盘块。 (字号，位号)或(行号，列号) 与盘块号一一对应
重要考点:要能够自己推出盘块号(字号，位号)之间的相互转换公式
需要注意的题目条件
二进制位 0/1 到底哪个代表空闲，哪个代表不空闲
字号、位号、盘块号到底是从0开始还是从1开始
成组链接法
UNIX 采用的策略，适合大型文件系统。
文件共享
硬链接
各个用户的目录项指向同一个索引结点
索引结点中需要有链接计数 count，count表示有几个目录项指向了该结点
某用户想删除文件时，只是删除该用户的目录项，且cownt--
只有 count == 0 时才能真正删除文件数据和索引结点，否则会导致指针悬空
软链接 (符号链接)
在一个 Link 型的文件中记录共享文件的存放路径 (Windows 快捷方式)
操作系统根据路径一层层查找目录，最终找到共享文件
即使软链接指向的共享文件已被删除，Link 型文件依然存在，只是通过 Link 型文件中的路径去查找共享文件会失败 (找不到对应目录项)
由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O因此用软链接访问
文件保护
口令保护
为文件设置一个“口令”，用户想要访问文件时需要提供口令（密码），由系统验证口令是否正确
实现开销小，但“口令”一般存放在FCB或索引结点中(也就是存放在系统中)因此不太安全
加密保护
用一个“密码”对文件加密，用户想要访问文件时，需要提供相同的“密码”才能正确的解密
安全性高，但加密/解密需要耗费一定的时间 (Eg:异或加密)
访问控制
用一个访问控制表 (ACL) 记录各个用户 (或各组用户) 对文件的访问权限
对文件的访问类型可以分为: 读/写/执行/删除 等
实现灵活，可以实现复杂的文件保护功能
文件的层次结构
文件系统的全局结构
文件系统在外存中的结构
文件系统在内存中的结构
虚拟文件系统
设备管理
I/O控制器
主要功能
接受和识别CPU发出的命令
(要有控制寄存器)
向CPU报告设备的状态
(要有状态寄存器)
数据交换
(要有数据寄存器，暂存输入/输出的数据)
地址识别<br>
(由I/O逻辑实现，I/O控制器通过CPU提供的“地址”来判断CPU要读/写的是哪个寄存器)
组成
两种寄存器编址方式
内存映射I/O
寄存器独立编址
I/O控制方式
程序直接控制方式
图例
完成一次读/写的过程：CPU发出I/O命令后需要不断轮询（CPU和I/O控制器串行执行，不能并行）
CPU千预频率：极高，在等待I/O控制器完成的过程中，CPU需要不停的轮询检查
每次I/O的数据传输单位：字
数据流向：设备>CPU>内存；内存>CPU>设备
优点：实现简单。在读/写指令之后，加上实现循环检查的一系列指令即可 (因此才称为“程序直接控制方式”)
缺点: CPU和I/0设备只能串行工作，CPU需要一直轮询检查长期处于“忙等”状态，CPU利用率低
中断驱动方式
完成一次读/写的过程：CPU发出I/0命令后可以做高其他事，本次I/0完成后设备控制器发出中断信号（CPU和I/O控制器并行执行）
CPU千预频率：高，等待I/O完成的过程中CPU可以切换到别的进程执行
每次I/O的数据传输单位：字
数据流向：设备>CPU>内存；内存>CPU>设备
优点:：CPU和I/O设备可并行工作，CPU利用率得到明显提升。
缺点：每个字在I/0设备与内存之间的传输，都需要经过CPU。而频繁的中断处理会消耗较多的CPU时间。
DMA方式
图例
完成一次读/写的过程
CPU千预频率：中，仅在传送一个或多个数据块的开始和结束时，才需要CPU干预
每次I/O的数据传输单位：块，(注意：读多个块时，每次读写的只能是连续的多个块且这些块读入内存后在内存中也必须是连续的）
数据流向：设备>内存内存>设备
优点：数据传输以“块”为单位，CPU介入频率进一步降低。数据的传输不再需要先经过CPU再写入内存，数据传输效率进一步增加。CPU和I/0设备的并行性得到提升
缺点：CPU每发出一条I/0指令，只能读/写一个或多个连续的数据块
通道控制方式
图例
完成一次读/写的过程
CPU千预频率：低，通道会根据CPU的指示执行相应的通道程序（任务清单），只有完成一组数据块的读/写后才需要发出中断信号，请求CPU干预
每次I/O的数据传输单位：一组快
数据流向：设备>内存内存>设备
优点： CPU、通道、I/0设备可并行工作，资源利用率很高
缺点：实现复杂，需要专门的通道硬件支持
I/O软件的层次结构<br>
I/O应用程序接口
阻塞I/O
应用程序发出/O系统调用进程需转为阻塞态等待。eg:字符设备接口--从键盘读一个字符 get
非阻塞I/O
应用程序发出I/O系统调用，进程无需阻塞等待。系统调用可迅速返回，eg:块设备接口--往磁盘写数据 write
I/O驱动程序接口
输入输出机制的发展
手工输入 阶段
脱机技术
假脱机技术
共享打印机
设备的分配与回收
应考虑的因素
固有属性
独占设备
一个时段只能分配给一个进程(如打印机)
共享设备
可同时分配给多个进程使用(如磁盘)，各进程往往是宏观上同时共享使用设备而微观上交替使用
虚拟设备 (SPOOLing)
采用 SPOLing 技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用(如采用 SPOOLing 技术实现的共享打印机)
分配算法
先来先服务
优先级高者优先
短任务优先
安全性
安全分配方式
为进程分配一个设备后就将进程阻塞，本次/0完成后才将进程唤醒。 (eg:考虑进程请求打印机打印输出的例子)
不安全分配方式
进程发出/0请求后，系统为其分配/0设备，进程可继续执行，之后还可以发出新的I/0请求。只有某个I/0请求得不到满足时才将进程阻塞
分配方式
静态分配
进程运行前为其分配全部所需资源，运行结束后归还资源
动态分配
进程运行过程中动态申请设备资源
设备分配管理中的数据结构
设备控制表 (DCT)：每个设备对应一张DCT，关键字段: 类型/标识符/状态/指向COCT的指针/等待队列指针
控制器控制表 (COCT)：每个控制器对应一张COCT，关键字段: 状态/指向CHCT的指针/等待队列指针
通道控制表 (CHCT)：每个控制器对应一张CHCT，关键字段: 状态/等待队列指针
系统设备表 (SDT)：记录整个系统中所有设备的情况，每个设备对应一个表目，关键字段: 设备类型/标识符/DCT/驱动程序入口
设备分配的步骤
1、根据进程请求的物理设备名查找SDT; 2、根据SDT找到DCT并分配设备;3、 根据DCT找到COCT并分配控制器;4、根据COCT找到CHCT并分配通道
注:只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可启动1/O设备进行数据传送
缺点:用户编程时必须使用“物理设备名"，若换了一个物理备，则程序无法运行。若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻寒等待
设备分配步骤的改进
用户编程时使用逻辑设备名申请设备，操作系统负责实现从逻辑设备名到物理设备名的映射(通过LUT)
逻辑设备表的设置问题
整个系统只有一张LUT: 各用户所用的逻辑设备名不允许重复
每个用户一张LUT:各个用户的逻辑设备名可重复
缓冲区管理
缓冲区的概念
-般利用内存作为缓冲区
缓解CPU与设备的速度矛盾、减少对CPU的中断频率、解决数据粒度不匹配的问题、提高CPU与I/O设备之间的并行性
单缓冲
设备一(T)一缓冲区-(M)一工作区-(C)一处理
处理一块数据平均耗时 Max(C,T)+M
分析问题的初始状态:工作区满，缓冲区空
双缓冲
处理一块数据平均耗时 Max(T,C+M)
分析问题的初始状态:工作区空，一个缓冲区满，另一个缓冲区空
循环缓冲
多个缓冲区链接成循环队列，in指针指向第一个空缓冲区，out指针指向第一个满缓冲区
缓冲池
三个队列:空缓冲队列、输入队列、输出队列
四种工作缓冲区
用于收容输入数据的工作缓冲区、用于提取输入数据的工作缓冲区
用于收容输出数据的工作缓冲区、用于提取输出数据的工作缓冲区
磁盘相关
磁盘的结构
磁盘、磁道、扇区 的概念
磁盘由表面涂有磁性物质的圆形盘片组成
每个盘片被划分为一个个磁道，每个磁道又划分为一个个扇区
如何在磁盘中读/写数据
磁头移动到目标位置，盘片旋转，对应扇区划过磁道才能完成读/写
盘面、柱面的概念
磁盘有多个盘片“摞”起来，每个盘片有两个盘面
所有盘面中相对位置相同的磁道组成柱面
磁盘的物理地址
(柱面号，盘面号，扇区号)
磁盘的分类
根据磁头是否可移动
固定头磁盘 (每个磁道有一个磁头)
移动头磁盘 (每个盘面只有一个磁头)
根据盘片是否可更换
固定盘磁盘
可换盘磁盘
一次磁盘读/写操作需要的时间
寻找时间(寻道时间):启动磁臂，移动磁头所花的时间
延迟时间: 将目标扇区转到磁头下面所花的时间
传输时间: 读/写 数据花费的时间
磁盘调度算法
先来先服务 (FCFS)
按访问请求到达的先后顺序进行处理
最短寻找时间优先(SSTF)
每次都优先响应距离磁头最近的磁道访问请求
贪心算法的思想，能保证眼前最优，但无法保证总的导道时间最短
缺点:可能导致饥饿
扫描算法(电梯算法、SCAN)
只有磁头移动到最边缘的磁道时才可以改变磁头移动方向
缺点: 对各个位置磁道的响应频率不平均
LOOK 算法
SCAN 算法的改进，只要在磁头移动方向上不再有请求，就立即改变磁头方向
循环扫描算法(C-SCAN)
只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不响应任何请求
C-LOOK 算法
C-SCAN 算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回
减少延迟时间的方法
交替编号
具体做法:让编号相邻的扇区在物理上不相邻
原理: 读取完一个扇区后需要一段时间处理才可以继续读入下一个扇区
错位命名
具体做法:让相邻盘面的扇区编号“错位”
原理:与“交替编号”的原理相同。“错位命名法”可降低延迟时间
固态硬盘
原理：基于闪存技术 Flash Memory，属于电可擦除ROM，即EEPROM
组成
闪存翻译层
负责翻译逻辑块号，找到对应页 (Page)
存储介质
多个闪存芯片 (Flash Chip)
每个芯片包含多个块 (block)
每个块包含多个页 (page)
与机械硬盘相比的特点
SSD读写速度快，随机访问性能高，用电路控制访问位置;机械硬盘通过移动磁臂旋转磁盘控制访问位置，有寻道时间和旋转延迟
SSD 安静无噪音、耐摔抗震、能耗低、造价更贵
SSD的一个“块”被擦除次数过多 (重复写同一个块) 可能会坏掉而机械硬盘的扇区不会因为写的次数太多而坏掉
磨损均衡技术
思想:将“擦除”平均分布在各个块上，以提升使用寿命
动态磨损均衡
写入数据时，优先选择累计擦除次数少的新闪存块
静态磨损均衡
SSD监测并自动进行数据分配、迁移，让老旧的闪存块承担以读为主的储存任务，让较新的闪存块承担更多的写任务
0 条评论
下一页
