绪论与文件系统
# 操作系统概述
# 概念、特征及功能
操作系统,OS,指控制和管理计算机系统资源(软件和硬件)、合理调度各类资源,提高系统效率,方便用户使用的系统软件
- 方便用户使用
- 硬件系统上的第一层软件:虚拟机
- 控制软硬件资源
- 合理调度资源,提高效率和吞吐量
基本特征
- 并发:同一时间段内执行两个或两个以上程序,通过资源复用实现,并发是操作系统最重要的特性
- 共享:即资源复用,根据资源属性常分为互斥共享和同时访问
- 互斥共享:如打印机,进程顺序执行
- 同时访问:如磁盘,进程交替访问
- 虚拟:将同一物理实体演变为若干逻辑物体(如实地址映射虚地址),常分为时分复用和空分复用
- 异步:多道程序环境下,各进程以不可预知的速度执行,导致运行结果可能存在差异
并发和共享是多用户操作系统最基本的两个特征,是操作系统所必备的特征
主要功能
- CPU 管理:以进程为单位进行 CPU 的分配,将对 CPU 的管理转化为对进程的管理和调度。进程管理包括进程的控制、同步和通信,包括进程控制和进程同步
- 存储器管理:为程序运行提供良好环境,提高内存利用率,逻辑扩充内存(虚拟存储器),包括内存分配、内存保护、地址映射和内存扩充
- 设备管理:将设备视作文件,分配 IO 设备,完成指定 IO 操作,包括缓冲管理、设备分配和设备处理
- 文件管理:对存放于外存的所有文件进行管理,包括系统文件和用户文件
- 接口管理:包括输入输出接口等
- 系统安全:认证技术、密码技术、访问控制技术及反病毒技术
# 操作系统发展历程
操作系统不是计算机必备的软件
无操作系统:人工操作方式,用户独占全部系统资源,CPU 等待人工操作,资源利用率低,人机交互矛盾突出
脱机输入 / 输出方式:事先将纸带上的指令和数据通过纸带机,在外围机的控制下输入磁带,CPU 从磁带上高速调入程序和数据
批处理操作系统:分为单道批处理和多道批处理,提高批处理操作系统形成和发展的主要动力是提高资源利用率和系统吞吐率
分时系统:允许一台主机为多个用户服务,并及时响应用户请求,一个计算机系统提供多个终端供用户使用
实时系统:在分时操作系统的基础上,主要解决快速响应问题,实现实时任务的处理,常见的实时系统包括工业控制系统、武器控制系统、信号查询系统、多媒体系统、嵌入式系统等
微机操作系统:单用户操作系统,仅允许一个用户存在,分为单用户单任务、单用户多任务(Windows)以及多用户多任务操作系统(UNIX / Linux)
# 操作系统结构
# 非内核结构
无结构
- 由众多过程直接构成,各过程可相互任意调用
- 系统高效,但大且杂乱,功能较简单
模块化结构
- 将功能分为若干模块,结构清晰,由繁到简,利于合作
- 模块和接口划分较困难,未区分共享资源和独占资源,系统结构可能不够清晰
分层结构:分为若干层次,像计网一样,由简到繁,下层向上层提供服务
# 内核结构
宏内核:也叫做大内核,基于模块化思想设计,各将一些和硬件紧密相关的、使用频率较高的功能及关键数据结构独立出来,形成常驻内存的内核,模块直接调用接口函数实现通信(如 UNIX / Linux)
- 可靠性和安全性随操作系统复杂性的增加而降低,且内核较大,包含较多功能,容错率低
微内核:操作系统常驻内存部分仅保留最核心的功能,如中断、CPU、存储管理,更复杂的功能,如程序管理,通过用户程序请求获取(如 Windows XP,Mac OS)
外核:分为内核和外核,内核负责资源分配,外核负责资源管理
# 引导和虚拟机
操作系统安装在外存,开机后自动加载到内存运行,其启动流程如下
- 通电启动 CPU
- 启动 BIOS
- 记录 BIOS 中断程序入口
- 进行硬件自检(由 BIOS 完成)
- 启动操作系统引导(MBR)
- 检查分区表(由 MBR 完成)
虚拟机
- 第一类虚拟机
- 第二类虚拟机:使用软件模拟的、运行在隔离环境中的、完整的操作系统
注意,所有能由软件实现的功能,一定可以由硬件实现,也就是说,虚拟机这一“程序”可以由硬件实现
# 程序运行环境
# 中断和异常处理
就像函数调用,主程序进入函数,主程序暂停,函数结束后返回继续执行
- 但不同点在于中断是出现异常情况或特殊请求时才发生,属于意外
小端存储和大端存储
- 小端存储指内存的低字节内容存储于内存低地址,如 0080H 存 12,0081H 存 34,则数据正确顺序为 3412
- 大端存储则反之,为 1234
中断常处理 CPU 外的事件,如 IO、定时器中断、硬件故障等
中断向量:中断服务程序的入口地址
- 表示为 CS:PC
- 其内存地址为 16CS + PC
- CS/PC 都是 16 位寄存器,中断向量 20 位,无法直接存储,只能以这种偏移的方式存储
中断源 / 中断类型号:8 位类型号用于标记不同的请求中断设备
中断向量表:记录中断向量的表,存于内存最底层的 1KB 空间
- 0000H - 03FFH 是系统内存空间,程序无法访问
- 这里实际上是间接寻址,存放的是中断程序的入口地址
- 对于中断向量来说,高位为 CS,低位为 IP,实际内存地址为 16CS+IP,如 12345678 则表示内存地址 1234x16+5678 = 25422H
中断隐指令:终端执行中的一些固定操作,功能类似于指令,但完全由硬件实现
- 保存断点
- 关中断
- 执行中断服务程序
中断服务程序流程
- 保护现场
- 开中断:为了响应更高级的中断
- 中断处理
- 关中断:这个环节已经处理完当前中断,防止被其他中断打扰
- 恢复现场
- 开放中断:开放中断隐指令关闭的中断
- 中断返回
异常,也叫内中断,由 CPU 执行的指令引发,分为
- 陷阱:主动型,try / catch,将程序交予操作系统执行(编程时使用系统调用也就是手动设置自陷异常的过程)
- 故障:如缺页
- 终止:不可恢复的错误引起
# 系统调用与地址映射
用户程序发送给操作系统,请求系统提供服务的方法或函数,同时是操作系统提供给用户程序调用其底层服务的方式,是用户访问内核的途径(如 java 的 native 函数,调用底层的 c++ 请求系统服务)
过程如下:用户执行系统调用,硬件完成用户态的转换,操作系统执行系统调用中断程序
程序运行时内存映像与地址空间:用户 — 源程序 — 库函数 — 模块 — 内存
- 符号名空间
- 目标地址空间:编译后的二进制形式代码
- 物理地址空间
# 程序的执行
编辑:使用无格式编辑软件创建用户源程序
编译:将用户源代码翻译为目标代码的过程
链接:将目标代码和所需库函数链接在一起
- 静态链接:程序运行前,将目标模块和库函数链接为完整的、从唯一零地址开始的装配模块
- 装入时动态链接:边装入边链接,便于修改更新以及对目标模块的共享
- 运行时动态链接:运行时用到目标模块时对其进行链接
装入:将装入模块放在内存某空间,构造进程控制块 PCB,形成可执行的进程
- 绝对装入方式:程序中使用绝对地址,指定每个程序装入固定的内存空间
- 重定位方式:程序均使用自己的零地址,在装入时通过硬件/软件实现对物理地址的重定位
- 静态重定位:装入时完成所有的地址变换
- 动态重定位:装入时不转换,执行时通过硬件自动变换
# CPU 运行模式
操作系统是基础的系统软件,运行时占据内存空间(内核空间),被所有程序共享;应用软件也占据内存空间(用户空间),软件所私有
- 为避免切换进程时间开销过大,内核空间和用户空间共存于同一地址空间,这就要求引入访问权限管理
用户程序运行时需要访问内核空间,这时进行运行模式的切换,而非切换进程
为保护数据安全,CPU 具有不同的运行模式,常见为内核模式和用户模式
- 内核模式又叫核心态/管态,是核心操作系统组件和大部分驱动程序运行时所处模式,这一状态下 CPU 可使用所有系统资源,所有内存地址、外部设备、寄存器、所有机器指令
- 通用指令:如访管指令
- 特权指令:只能由操作系统使用的指令,如 IO、内存清除、允许/禁止中断
- 用户模式又称为用户态或目态,只能访问私有虚拟地址空间和指定的寄存器,只能执行通用指令,不能执行特权指令
在核心态能执行除访管指令之外任意指令
运行模式的转换:由硬件完成用户态的转换
- 用户态切内核态:当需要输入输出、申请内存等底层操作时,必须使用系统调用,切换至内核态
- 访管指令
- 系统调用
- IO 控制命令
- 异常
- 内核态切用户态:操作系统执行中断返回指令
# 文件
# 文件与元数据
文件:放于外存,具有文件名的相关信息的集合;长久存放于外存;文件是输入输出的基本单位,对文件的操作由操作系统的文件系统提供
文件系统的基本概念(相当于一个数据表)
- 数据项:字段,列
- 基本数据项
- 组合数据项
- 记录:行
- 属性:文件(表)的属性
- 文件名:字符型,由用户命名,包括主文件名和扩展名
- 标识符:用于系统识别文件
- 类型:扩展名体现
- 大小:以字节计量
- 位置:外存地址
- 建立 / 修改时间
- 存放方式:权限,读写等
文件分类
- 按用途分类:系统文件、用户文件和库文件
- 按文件中的数据类型分类:源文件、目标文件和可执行文件
- 按存取控制属性分类:只执行文件、只读文件、读写文件和可读可写可执行文件
- 按组织形式和处理方式分类:普通文件、目录文件和特殊文件
元数据:文件的属性类数据(另一类为文件内容对应的数据),元数据主要用于编制目录,方便检索文件,用户操作文件前必须获得该文件的元数据
元数据的更改保存于日志文件
- 系统重启时去查日志而非文件系统,缩短系统恢复时间
- 日志文件还可以用于回滚文件数据
元数据的管理方式
- 集中式管理:将所有元数据存储在存储管理节点所在的存储设备,集群文件系统常采用集中式管理
- 管理简单;一致性维护容易
- 可靠性差,管理节点失效会造成整个系统瘫痪;操作频率受限,若操作过于频繁将制约系统性能
- 分布式管理:元数据可存放于系统的任意节点且运行动态迁移
- 可靠性高且操作频率不受限
- 管理实现复杂,一致性维护较难
# FCB 和索引
FCB:文件控制块,用于描述和控制文件的数据结构(参考进程控制模块 PCB,作业控制模块 JCB),文件管理程序借助 FCB 的信息对文件施以各种操作
FCB 包含以下信息
- 基本信息:文件名;物理位置(外存位置,外存设备名,起始盘块号、所用盘块数、长度);文件逻辑结构;文件物理结构
- 存取控制信息:文件主;核准用户;一般用户读、写、执行权限
- 使用信息:文件建立时间;修改时间;当前使用信息(打开该文件的进程数、是否被所著、是否在内存已被修改未同步至外存)
通过 FCB 可以感知文件在外存的所有状态,如微软 DOS 的文件控制块(占用 32 B)
| 主文件名 | 扩展名 | 属性 | 备用 | 时间 | 日期 | 第一块号 | 盘快数 |
|---|
索引结点:基于 FCB 实现,多级目录允许文件重名,解决了难命名问题,但也意味着一个目录文件中可能要存放大量的 FCB 文件,如一个目录下 100 个文件,这个目录文件就要存 100 个 FCB,3.2 KB
在检索文件时,需要
- 将目录文件调入内存
- 在目录中通过文件名查找指定文件
- 根据 FCB 将文件从外存调入内存
用于减少目录所占空间,同时提升检索 FCB 速度,于是引入索引结点
- FCB 文件只存储文件名和指向该文件索引结点的指针
- 索引结点中存储 FCB 中除了文件名的其余属性
相当于多建立一张索引表,纵向分表存储,将键和属性分开,用指针链接,提高检索效率:文件目录下只存文件名和指针的索引表,索引结点可以存放在任意位置,于是减少了目录所占空间
磁盘索引结点(存放在磁盘的索引节点):主标识符;类型;存取权限;物理地址;长度;链接次数(文件系统中指向该文件的指针数);存取时间
内存索引结点(存放在内存的索引节点):索引结点编号;状态(是否上锁、被修改);访问计数(进程访问结点计数);逻辑设备号;链接指针
# 文件操作与保护
文件的操作
- 创建:为文件建立目录表项(登记),分配外存空间等
- 删除:在目录文件下文件对应的记录增加删除标记;在需要时(空间不够或需要移动)回收文件所占外存空间
- 打开:通过系统调用完成,如函数
open(file_name, open_pattern) - 读 / 写:通过文件名检索目录,获取文件的外存地址,实施读写,打开的是属性,读写的是内容
- 关闭:将该文件在打开文件表中的条目删除,撤销文件的数据结构,释放内存空间
属性操作
- 普通文件:修改文件名、文件拥有者、改变文件访问权和查询文件状态等
- 目录文件:创建目录、删除目录和改变当前目录等
文件保护
- 对内存的保护:上下界寄存器,越界非法地址等
- 外存同样需要保护:首先不能越界,另外需要防止非法操作或物理损坏对文件数据造成的破坏
影响文件安全的因素
- 人为因素:如误删
- 系统因素:如磁盘故障
- 自然因素:磁盘数据会随时间的推移逐渐消失,消磁
安全措施
- 容错技术:冗余磁盘,多备份
- SFT-1 低级容错,备份一份控制信息
- SFT-2 中级容错,写后读校验,磁盘镜像
- SFT-3 高级容错,基于集群技术
- 后备系统:防止自然因素危险
- 访问控制:防止人为因素危险
具有域切换权、复制权、所有权、控制权的访问矩阵
| 域 | F1 | F2 | F3 | F4 | F5 | 域D1 | 域D2 | 域D3 |
|---|---|---|---|---|---|---|---|---|
| D1 | R* | R,W | S, Control | |||||
| D2 | R | W,O | S | |||||
| D3 | W | W,E |
- S 表示具有向某域的切换权,如第一行表示 D1 具有向 D2 的切换权,第二行表示 D2 具有向 D3 的切换权
- R,W,E 分别表示读、写、执行权限
- 带*的权限表示可复制权,可以将该权限赋予其他域
- O 表示所有权,可以增删该项目在任意域的访问权(在列上随意修改)
- Control 表示控制权,图示表示 D2 具有对 D1 行所有权限增删的权限
可以看到访问矩阵实际上是一个稀疏矩阵,Linux 使用三元组的方式表示,以节省空间
# 逻辑与物理结构
逻辑结构:逻辑组织,和设备无关,决定文件的检索速度
- 无结构文件:流式文件,以字节为单位,一个一个字符存,如源程序、可执行程序、库函数等
- 有结构文件:记录式文件,用记录描述对象
- 定长记录:格式化,整齐
- 不定长记录:常用于商业领域
- 顺序文件:记录按照某种顺序依次排列
- 索引文件:索引表(关键字,记录长度,磁盘起始位置)
- 索引顺序文件:将顺序文件分组,每组的第一个记录(首地址)在索引表中占一项,n 个记录的文件
- 直接文件:散列文件、Hash 文件,Hash 函数和冲突解决办法
物理结构:物理结构和磁盘介质和外存分配方式相关,通常一个文件系统只采用一种物理结构
- 连续方式 ——> 顺序结构
- 连接分配方式 ——> 链接式结构
- 索引方式 ——> 索引结构
不同的物理结构对应不同的文件
- 顺序文件:同一文件物理相邻存放,如文件 y 连续存放于 x,x+1 盘块
- 链接文件
- 隐式链接:物理块隐含指针,即每个盘块自己存储的有 next 指针
- 显式链接:链接各盘块的指针存放在链接表中,成为文件分配表 FAT
- 索引文件:每个文件对应一个索引表,记录分配给该文件的所有盘块号,单级索引直接记录物理盘块地址,多级索引对页面增加层层管理,如一级引向二级索引表,二级索引表引向物理地址
# 目录
目录:也是文件,用于管理(检索)文件
解决分类存放以及重名问题,目录,可以是
- FCB 的有序集合(FCB 太大,不这么存)
- 文件名 + inode 的有序集合(基于文件名查找)
文件作用
- 按名存取(不能查看内容)
- 提高文件检索速度
- 文件共享
- 运行文件重名
树形目录:最常用的目录结构
- 优点:查询速度快,结构层次清晰,方便防护
- 缺点:路径逐级访问会增加磁盘访问次数,影响查询速度
目录操作
- 创建
- 删除
- 改变目录
- 移动目录:调整目录结构
- 链接:指定文件可具有多个父目录,便于文件共享
- 查找
硬链接和软链接:链接的两种方式,静态共享方法
- 硬链接:基于索引节点的文件共享,将文件名和指向索引节点的指针添加到父目录项中。被硬链接后,文件的索引节点 inode 中引用计数 count 将 +1,只有 count 为 0(即表示文件不被任何父目录指向),此时文件才可被删除
- 软链接:基于符号链接,实际上是一个文件,存储的是共享文件的路径
软链接特点
- 没有悬空指针现象,失效将即使删除
- 可能误判,因为基于路径,即文件名,不能识别同名文件
- 时间开销较大
- 额外空间消耗
- 方便网络共享:超链接
# 文件系统
# 文件系统结构
# 全局结构
文件系统采用层次模型,上对用户,下对设备,这使得文件系统仅需要提供逻辑文件系统和基本 I/O 管理程序
文件系统接口:为用户提供的一组操作文件和记录的方法(上对用户)
- 命令接口
- 程序接口
操纵和管理对象的软件集合(核心层,下对设备),主要功能
- 文件存储空间管理
- 目录管理
- 文件逻辑地址和物理地址转换
- 文件读写管理
- 文件共享与保护
这些软件包括
- 逻辑文件系统:管理控制 FCB,处理文件系统结构性数据等,得到逻辑块号
- 基本 I/O 管理程序:和硬件相关,完成逻辑块号到物理块号的转换等
- 基本文件系统层
- I/O 控制层
对象及其属性:文件;目录;外村存储空间
# 外存结构
文件去和目录区,文件去用于存放数据信息,目录区存放控制信息,如 FCB
物理盘可以分成多个逻辑盘(卷),逻辑盘可以由多个物理盘组成
外存中不同的存储介质具有不同的文件系统,每个操作系统可以拥有多种文件系统
磁盘文件系统包括
- 引导控制块(Boot Control Block, BCB):又称引导块或引导扇区,若磁盘中没操作系统,则为空,否则存储 OS 的引导信息
- 卷控制块(Volume Control Block, VCB):又称超级块或主控文件表(Master File Table, MFT),记录卷的盘块数、块容量、空闲块地址和数量、空闲 FCB 地址和数量等
- 目录结构:用于组织和管理文件
- FCB:文件控制块,一个文件对应一个 FCB
# 内存结构
安装文件系统:即将外存的文件系统调入内存,挂载卷
当操作系统有多种文件系统,使用 VFS(虚拟文件系统)将不同文件系统环境相隔开
文件系统的超级结构块
- 系统打开文件表(System open File Table, SFT)
- 进程打开文件表(Process open File Table, PFT)
- 安装表
- 缓存
管理磁盘的目的:合理利用外存空间;提高磁盘 I/O 速度;提高磁盘系统的可靠性
# 外存组织
大题
文件的外存组织方式决定了文件的物理结构,为了方便管理,操作系统增加“簇”的概念,可包含 2、4、8、16、32、64 个扇区
# 连续方式
每个文件存储于磁盘的一组相邻盘块中(同一柱面)
文件名 + 起始位置 + 文件长度
# 链式方式
隐式链接:文件名 + 起始指针 + 终止指针
显式链接 FAT:文件名 + 起始指针
- 起始指针在 FAT 链接表寻找后继,直到碰到 EOF 终止符停止
- FAT1 / FAT2 属于系统区
# FAT 方式
FAT12:每个表项占 12 字节,1.5 个字(1.5B),同理 FAT32 占 32 字节,4 个字(4B)
- 主文件名最多 8 字符,扩展名最多 3 字符,以盘块为分配单位,最多 4096 个表项(4096x1.5=6044B)
- 文件的第一个盘块号存在文件的 FCB 中,其余均存储在 FAT 中,以 EOF 结束
FAT16:每个表项占 16 字节,2B,磁盘容量可达 2GB(64K簇 x 32KB/簇 = 2GB)
FAT32:每个表项占 4B,磁盘容量可达 2TB
不同扇区大小对应不同 FAT 文件系统的最大分区容量
| 扇区大小 | FAT12 | FAT16 | FAT32 |
|---|---|---|---|
| 512B | 2MB | ||
| 1KB | 4MB | ||
| 2KB | 8MB | 128MB | |
| 4KB | 16MB | 256MB | 1TB |
| 8KB | 512MB | 2TB | |
| 16KB | 1GB | 2TB | |
| 32KB | 2GB | 2TB |
# NTFS
全新文件系统:将所有文件信息、目录信息以及可用未分配空间信息均已文件记录的方式存储与主控文件表 Master File Table,主控文件表 MFT 为 NTFS 卷结构中心,记录大小固定为 1KB,每行(记录)都对应一个文件的元数据
# 索引方式
FCB:文件名 + 索引块序号
单级索引:建立一个索引表,每个文件分配一个索引块(这个索引块同样是一个外部磁盘块),索引块中记录的是存储该文件的块的顺序序列,如[2,41,23,5,-1,-1,-1,-1]表示该文件按顺序存放在磁盘块2,41,23,5中
- 注意每个文件只有一个唯一的索引块,记录了其文件所存储的磁盘块号集合
- 若一个盘块 1KB,一个盘块记录 4B,则索引块最多记录 256 个盘块,文件最大为 256KB
二级索引:在这唯一的索引块中,记录的是一级索引块的集合,一级索引块中记录的才是文件内容所存在的磁盘块号的集合
- 若一个盘块 1KB,一个盘块记录 4B,索引块最多记录 256 个盘块,文件最大为 256x256 = 64MB
增量式索引:假设一个盘块 4KB,一个文件至少有十个索引盘块,一个盘块号需要 4B 存储空间
- 当文件小于 40KB,直接使用这十个索引盘块存储文件
- 当文件较大,除了基础的十个索引盘,外加一个索引盘作一次间址,可以存储最大 1K 个盘块号,此时文件最大容量为 40KB + 1K x 4KB = 4MB + 40KB
- 更大时,再加一个索引盘作二次间接地址,此时最大容量为 4MB + 40KB + 1K x 1K x 4KB = 4GB + 4MB + 4KB
- 再大,增加一个索引盘作三次间址...扩大到 4TB
# 外存管理
重点
# 空闲表
用一张表记录所有外存中的空闲区,每个空闲区(一个空闲区包含若干个连续的空闲盘块)对应空闲表中一个表项
| 序号 | 第一个空闲盘块号 | 空闲盘块数 |
|---|
回收的时候需要考虑空闲区的合并问题
优点:分配速度快,I/O 频率较低
适用:小文件,对换空间,多媒体文件(连续)
# 空闲链表
隐式的,将所有空闲盘块串成一个链表
特点:链表较长,回收算法很简单
空闲盘区链:链表的一个节点从盘块变成一个盘区,即若干个连续的盘块
也可以使用 FAT 的方式显式管理链表
# 位示图
用一个二维数组表示各个盘块的占用情况,1 表示已占用,0 表示空闲,设数组每行 n 个,则盘块号为 m 的盘块在二维数组的坐标为bitmap[m/n][m%n]
在寻找空闲盘块时,顺序寻找位示图(从左往右,从上往下),直到找到连续的大小足够的空闲磁盘,返回其盘块号
当盘块被回收时,位示图置零
# 成组链接
空闲表 + 空闲链表
虚拟文件系统
文件系统挂载