OS总结2
文件管理

文件定义
文件是操作系统在外部持久性存储设备上存储信息的基本单位
文件是文件系统的核心要素
文件系统是操作系统的核心模块
操作系统安装时,主要工作是:创建系统分区,并在系统分区建立根文件系统
根文件系统是内核启动时所mount的第一个文件系统,内核代码映像文件保存在根文件系统中,系统引导程序需要借助磁盘的启动扇区上的启动代码将内核加载。并且,系统引导启动程序会在根文件系统挂载之后将从中把一些基本的初始化脚本和服务等加载到内存中去运行。
文件属性:文件名、唯一标识、类型、位置、大小、保护信息等
文件系统的加载与保护
文件系统加载是文件系统初始化的关键步骤 文件系统加载操作,将本地磁盘或远程服务器的磁盘上的文件系统加载到根文件系统的特定加载点
文件保护:文件完整性验证 和 Linux文件访问权限控制
文件完整性验证:哈希机制——MD5、SHA-256
Linux文件访问权限控制:r(read),w(write),x(Execute,执行) 三类文件属主:user(拥有者),group(拥有者所在组),all(其他人)
文件的逻辑结构

无结构文件
文件数据在OS层面被看成字节流或字符流
逻辑地址以字节为单位编址
通过文件数据的逻辑地址访问具体文件内容
记录式文件(有结构文件)
记录按一定的顺序排列
可以根据记录的格式计算数据记录的地址(通常会为记录设定关键字,并以关键字建立记录索引)
定长记录:文件有固定长度
变长记录:多种记录类型(即多个关系表)在一个文件中存储;允许记录类型中包含一个或多个变长字段;允许记录类型中包含重复字段,如数组等。
顺序逻辑结构:文件中的记录一个接一个地排列
索引逻辑结构:使用定长记录的顺序文件作为索引文件,对记录进行索引
索引顺序逻辑结构:将记录分为一组一组,以组为单位建立索引;进行文件访问时,首先索引到记录组,再在组内顺序查找
分区
硬盘一般会分成多个分区,每个分区使用前需要格式化为某一类型的文件系统
单个磁盘可以分为多个区,多个磁盘可以构成一个区
文件目录

一个文件对应一个FCB,一个FCB对应一个目录项,每个目录有多个目录项组成
文件系统由一组目录和文件组成
目录结构
单级目录结构

所有文件存放在单一目录内
不支持文件重名、文件分组;文件检索效率低
两级目录结构

每个用户的文件放在单个目录下 一个主目录包含所有用户目录
允许不同用户目录下存在重名文件,不能支持灵活的分组,文件检索效率低
树状目录结构

每个目录中都可包含多个子目录,最终形成树状目录
不同目录下文件可以重名,可以对文件进行灵活分组 查找效率高
绝对路径:从根目录出发,一般以盘号或Home开头
相对路径:从当前目录出发,一般以./开头
有向无环图结构

文件的物理结构

文件的物理结构:描述如何对已经分配给文件的磁盘块进行组织
连续分配
为文件在外存上分配物理上连续的磁盘块

优点:顺序读写速度快,支持随机访问
缺点:不易于文件大小扩展,产生磁盘空间碎片
链式分配
分配离散的数据块,并以链表的形式进行组织

优点:便于文件的动态增长(扩展),不易于产生磁盘碎片,提高了外存利用率
缺点:查找效率低,指针占据额外空间,无法高效实现随机访问
代表:FAT文件系统
索引分配
为文件的所有数据块建立索引,并将索引置于独立的索引磁盘块

优点:便于文件的动态增长(扩展),支持随机访问
缺点:索引表占据额外空间
代表:Unix/Linux的多级索引
文件系统结构设计

逻辑文件系统:管理目录结构,创建FCB、建立文件名到FCB的映射
文件组织模块:建立文件逻辑块到磁盘物理块之间的映射,管理磁盘上的空闲物理块
基本文件系统:与磁盘驱动设备对接,以块为单位读写数据
IO控制软件层:磁盘设备控制器驱动是其核心
虚拟文件系统

虚拟文件系统(也称为虚拟文件系统开关)是内核中向用户空间程序提供文件系统接口的软件层。它还在内核中提供了一个抽象,允许不同的文件系统实现共存。
简而言之,虚拟文件系统的作用有:
1. 使用户应用能够访问不同类型的具体文件系统。比如,一个VFS能够用来访问一个本地或者网络存储设备且同时不会让用户应用知道区别;
2. 可以连接不同的操作系统的文件系统,使应用能够访问这些类型的本地文件系统上的文件,而不需要知道他们正在访问的是哪个文件系统;
3. 明确了内核和具体文件系统之间的接口,所以通过实现对应的接口,能够很轻松的给内核添加对新文件系统的支持;
4. 连接或者断开设备和合适的文件系统实体
一个虚拟文件系统的实例:

Linux中,用户进程发起的文件相关系统调用,都是发到VFS层 VFS会把系统调用请求翻译为具体文件系统的文件操作 执行VFS中的操作,为目标/物理文件系统的调用进行初始化 物理文件系统会将上层系统调用请求转给设备驱动程序 驱动程序驱动设备,完成I/O后返回结果
文件系统实现
磁盘数据结构

启动块(引导块、Boot Block):包括用于加载系统的初始代码
超级块:存储文件系统的总体信息,如文件系统的大小、块大小、inode数量、已使用和未使用块的数量等。
索引:即目录文件
数据块(组):文件数据
下边是一个Linux的ext4磁盘数据结构示例:

内存数据结构
磁盘I/O速度比内存访问速度要慢好几个数量级 利用内存,为频繁访问的目录或文件结构建立缓存。
为了提升文件系统效率,操作系统会准备多种内存数据结构(用于缓存关键和常用的文件系统数据)
·文件系统加载表:将分区控制块(比如Linux Ext文件系统的super block)中的文件系统元信息读入内存
·目录缓存:将常用目录项缓存在内存中,加速路径解析效率
·全系统打开文件表和进程打开文件表:每个进程打开的文件相关信息,会被记录在内存中
文件基本操作实现

文件创建
为新的文件创建FCB 更新目录 新的目录内容到磁盘(也可以缓存它)
文件打开

如果文件是首次被打开,将目录项的信息复制到内存中的目录项缓存,建立系统打开文件表项 建立进程文件打开表项,并将表项的索引返回给用户
调用 open()将文件名传给文件系统。系统调用open()会首先搜索系统范围内的打开文件表以确定某文件是否已被其他进程所使用。如果是,就在单个进程的打开文件表中创建一项,并指向现有系统范围内的打开文件表。 当打开文件时,根据给定文件名来搜索目录结构。一旦找到文件,其FCB就复制到系统范围内的打开文件表,该表不但存储FCB,而且还跟踪打开该文件的进程数量。
接着,在单个进程的打开文件表中会增加一个条目,并通过指针将系统范围内的打开文件表的条目和其他域相连。这些其他域可以包括文件当前位置的指针(用于下一次的读写操作)和文件打开模式等。调用 open()返回一个指向单个进程的打开文件表中合适条目的指针。所有之后的文件操作都是通过该指针进行的。文件名不必是打开文件表的一部分,因为一旦完成对FCB在磁盘上的定位,系统就不再使用文件名了。对于访问打开文件表的索引有多种名称。UNIX称之为文件描述符,Windows称之为文件句柄。因此,只要文件没有被关闭,所有文件操作都是通过打开文件表来进行的。
文件读操作

文件关闭
将文件对应的进程打开文件表项删除 系统打开表引用计数递减1如果该值变为0,则删除对应表项,更新复制回磁盘(如果需要)
磁盘空闲管理

空闲链表法

开销:为每个空闲磁盘块需要消耗一个指针大小的管理数据结构
成组链接法

位图法
开销:为每个空闲磁盘块需要消耗一个位( bit)来表示其状态 基本数据结构:位图(bitmap) 用位图中的1表示对应的块空闲;为0代表对应的块被占用
若磁盘容量为1TB,磁盘块大小为4KB,则块位图占据空间大小是多少? 块位图空间大小=1T/(4K*8)=32M
使用位图进行磁盘空间管理的典型示例:Linux Ext文件系统: 
整数数组实现位图法

大容量存储
磁带、机械磁盘是大容量存储的典型代表
传统机械磁盘结构由柱面、磁道、扇区组成
磁盘调度算法

应用访问磁盘,生成I/O请求 I/O请求进入I/O请求队列 操作系统在服务I/O请求时,充分考虑机械磁盘的特性,对I/O请求进行排序
通过对I/O请求的调度,最小化磁头寻道距离=>减少寻道距离,从而缩短总体寻道时间,进而优化IO效率
FCFS

先来先服务
SSTF

每次都寻找距离最近的轨道
会饥饿
Scan和CScan

Scan是扫到头再掉头扫一遍 CScan是扫到头再掉头回到另一端再扫一遍
二者区别:Scan返程中依旧进行IO请求,而CScan返程中不处理
Scan的缺点:对各个位置的响应频率不平均。
LOOK和CLOOK

LOOK是扫到请求队列中的最右(左)端再掉头扫到请求队列的最左(右)端 CLOOK是扫到请求队列中的最右(左)端再掉头回到请求队列的最左(右)端,继续向右(左)扫完剩下的请求
二者区别:LOOK返程中依旧进行IO请求,而CLOOK返程中不处理
磁盘交换空间管理
内存不管如何扩大,总是觉得拥挤 (内存大,应用体积也在变大;同时运行的任务也越来越多) 于是,引入磁盘交换空间,借助于磁盘空间,对内存做个扩充
磁盘空间的设计结构:交换文件(低效),代表:Windows交换文件;交换空间,代表:Linux交换分区
Windows

Linux

IO子系统
IO设备基本概念

IO设备:将数据输入到计算机,或者从计算机接收输出数据的外部设备
IO控制器

IO子系统基本功能
内核的I/O子系统与设备驱动程序和中断处理程序一起,对I/O设备进行管理,为应用层提供I/O相关的服务
设备控制器是IO设备的控制中枢 设备驱动程序,核心是对设备控制器进行编程
设备控制器是一个电子卡(PC)或一个单元(主机),它执行阻塞(来自串行比特流)、模拟信号生成(移动磁盘臂、驱动屏幕上的CRT管)、I/O命令的执行。
IO控制方式
通道控制IO、DMA、中断控制IO、程序控制IO
程序控制IO

中断控制IO

DMA控制IO

CPU 会对 DMA 控制器和 IO 接口进行初始化 设备接口向DMA控制器发送 “ DMA请求 ” ,即请求使用 DMA 进行数据传输 DMA 控制器向CPU申请 “ 总线占用 ”,DMA控制器和 CPU 只能有一个占用总线 CPU 批准使用总线,此时CPU会让出一个或者多个总线周期用于数据传输。在DMA数据传输期间,CPU 停止访问内存,无法执行需要占用总线的指令。 DMA 批准设备请求,此时 DMA控制器将掌握总线控制权。如果是单字节传送,一个总线周期后,DMA归还总线控制权;如果是块传送,连续占用若干个总线周期后,DMA才会归还总线控制权。 数据传送期间,DMA 控制器会向总线发送读/写命令、向 I/O 接口发响应信号。真正的数据交互是内存和设备接口,DMA 控制器只是负责控制整个数据传送流程。
通道控制IO
大型计算机系统中采用通道处理机使CPU摆脱繁重的IO处理负担并且共享IO接口
大型计算机系统中,如果仅采用程序控制、DMA等常规IO控制方式,在进行设备管理时,会面临如下问题 大量外围设备的I/O工作要由CPU管理,挤占CPU支持应用程序执行的时间 大型计算机系统中的外围设备很多,但一般不同时工作,为每个设备都配备一个接口,代价很高

IO软件
通过层次设计,利用低层I/O软件层屏蔽硬件细节; 以低层设备驱动软件接口为基础,形成设备无关的I/O软件中间层; 通过I/O系统调用将I/O系统服务提供给应用层;
中断处理程序

硬件中断和软件中断
硬件中断:由硬件引发
软件中断:使用INT指令调用中断
外部中断和内部中断
外部中断(设备中断):与当前执行的指令无关中断信号来源于cPU外部 如:鼠标被移动、输入一个键、网络数据包到达、硬盘完成读写操作等
内部中断:与当前执行的指令有关,中断信号来源于cPU内部 如:地址非法、页故障、内部时钟中断、浮点数协处理器错误
可屏蔽中断和不可屏蔽中断
可屏蔽中断(INTR):CPU可以不响应这个中断 大部分中断属于可屏蔽中断
不可屏蔽中断(NMI):CPU必须响应的中断 如:RAM奇偶校验错误、除零错误
硬中断和软中断
硬中断:由与系统相连的外设(比如网卡、硬盘)自动产生的,主要是用来通知操作系统系统外设状态的变化。 由外设引发的 由中断控制器提供
软中断:将那些处理事件比较长的工作,放到中断之后来完成,也就是软中断(softirq)来完成 由软件主动触发,执行中断指令产生的,无需外部施加中断请求信号 由指令直接指出,无需使用中断控制器
设备驱动程序
设备驱动程序分为:字符设备驱动、块设备驱动、网络设备驱动
设备驱动程序应具备的功能︰ 1)接收由设备独立性软件层发来的命令和参数,并将命令中的抽象要求转换为具体要求 2)检查用户I/O请求的合法性,了解I/O设备的状态,传递有关参数,设置设备的工作方式 3)发出I/O命令 4)及时响应由控制器或通道发来的中断请求,并根据其中断类型调用相应的中断处理程序进行处理
设备无关软件
设备无关软件:在应用程序中,使用逻辑设备名称来请求使用某类设备;将对物理设备访问的细节封装在I/O相关系统调用的实现内
逻辑设备名:是抽象的设备名,不直接对应具体的物理设备。系统内部通过逻辑设备表(LUT)将逻辑设备名映射到具体的物理设备名。
设备独立性: 设备独立性主要指用户使用设备的透明性。 应用程序按逻辑设备名访问设备,再经过驱动程序的处理来控制物理设备 以Linux系统为例,设备被视为特殊文件,可以使用文件名访问物理设备。 I/O子系统需要为此建立物理设备与逻辑设备之间的映射关系。
另外一种类似表述方式: 设备独立性是指用户程序独立于所使用的具体物理设备。 实现方式是系统为每个用户进程配置一张用于联系逻辑设备名和物理设备名的映射表,以实现使用逻辑设备名来请求物理设备。
错误处理: 操作系统可以从磁盘读取、设备不可用、瞬态写入失败中恢复 大多数在I/O请求失败时返回错误编号或代码 系统错误日志保存问题报告
IO保护: 所有I/O指令都是特权指令 所有I/O都是通过系统调用执行的。
SPOOLING: 独占设备,被改造为共享设备 借助于磁盘缓冲区,营造出多个虚拟设备的状态=>SPOOLING被称为“虚拟设备技术”
Device Reservation: 提供对设备的独占使用方式预防I/O操作的死锁
IO软件的层次

用户层软件(库函数):实现与用户交互的接口,向上提供方便易用的库函数
设备独立性软件(系统调用):①向上层提供统一的调用接口(如read/write系统调用);②设备的保护;③差错处理;④设备的分配与回收;⑤数据缓冲区管理;⑥建立逻辑设备名到物理设备名的映射关系;根据设备类型选择调用相应的驱动程序
设备驱动程序:设置设备寄存器、检查设备状态
中断处理程序:进行中断处理
硬件:执行I/o操作,有机械部件、电子部件组成
IO系统调用
阻塞IO

非阻塞IO

同步IO

异步IO

IO模型

SPOOLING技术(假脱机技术)(外部设备联机并行操作)

目的:缓解IO设备与CPU速度不匹配的矛盾,实现预输入、缓输出

工作原理: 当有进程需要进行I/O操作时,SPOOLING系统不会直接将独占设备(如打印机)分配给该进程,而是在共享设备(如磁盘或磁鼓)上的输出SPOOLING存储区中为其分配一块存储空间。 进程的输出数据以文件形式存放于该存储空间,即输出井中。这样,多个进程的输出文件形成了一个输出队列。 SPOOLING系统控制独占设备(如打印机),依次从输出队列中取出输出文件,进行实际的打印输出。
主要特征: 具有缓解CPU与I/O速度严重不匹配的矛盾的重要意义 具有将独占设备改造为共享设备的效果 实现了虚拟设备的效果(改造成的共享设备=虚拟设备)
通过设立输入井和输出井作为缓冲,从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作,使得CPU与I/O设备可以异步并发模式工作,解放了CPU
多个进程同时使用一独享设备,而对每一进程而言,都认为自己独占这一设备,从而实现了设备的虚拟分配

缓冲

目的:缓解CPU与I/O速度之间速度不匹配的矛盾
意义:减少对CPU的中断频率,解决数据粒度不匹配的问题,提高CPU与I/O设备的并行工作能力
单缓冲
-提供足够大的单个缓冲区,可以减少访问设备的频次,提升效率

双缓冲
-对单缓冲的优化,通过增加一个系统buffer来获得数据输入与数据处理的并发

双缓冲依旧存在的不足∶无法应对IO bursts(例如,网卡,可能突然有大量数据涌入,需要IO子系统处理)
环形缓冲
-有限环形缓冲,通过缓冲区数量的扩容,加上有限缓冲的并发处理,可以应对IO Bursts

缓冲池
缓冲池是由两个以上缓冲区组成的缓冲区集合。这些缓冲区被组织在一起,用于临时存储数据,以便在进程需要时能够迅速访问。
缓冲池可以被视为一个“大箱子”,其中包含多个“抽屉”,每个“抽屉”都是一个缓冲区。这些“抽屉”有的用于存储进来的数据(输入),有的用于存储要输出的数据(输出)。 进程在需要时可以向缓冲池申请缓冲区,并在使用完毕后将其释放回缓冲池,以供其他进程使用。这种机制实现了资源的有效管理和复用。