TIP
《计算机操作系统》课程笔记
# 1 操作系统引论
配置在计算机硬件上的第一层软件
# 1.1 操作系统的目标和作用
# 1.1.1 操作系统的目标
- 方便性 避免用户书写机器语言
- 有效性 防止大部分设备处于空闲状态,在操作系统的调度下各部分的协调恰如其分
- 可扩充性 能方便地增添新的功能和模块
- 开放性 按照某些标准开发,以便软硬件的兼容等等
# 1.1.2 操作系统的作用
OS 作为用户与计算机硬件系统之间的接口
OS 作为计算机系统资源的管理者
- 处理器上可执行的指令分为
- 特权指令
- 非特权指令
- 处理器状态划分为
- 管态(管理态)
- 目态(用户态)
处理器状态保证了特权指令的正确使用,把 OS 与用户程序区别开来
- 处理器上可执行的指令分为
OS 实现了对计算机资源的抽象
# 1.1.3 推动操作系统发展的主要动力
- 不断提高计算机资源利用率
- 方便用户
- 器件的不断更新换代
- 计算机体系结构的不断发展
- 不断提出新的应用要求
# 1.2 操作系统的发展过程
# 1.2.1 未配置操作系统的计算机系统
人工操作方式
人工装填纸带,CPU 大多数时间在等待,浪费了大量的资源
脱机输入/输出(Off-Line I/O)方式
在手工与 CPU 之间加上了一个磁带,以优化 I/O 与 CPU 速度不匹配的问题
# 1.2.2 单道批处理系统
单道批处理系统(Simple Batch Processing System)的处理过程
用监督程序来解放装填纸带人员的双手,并进一步解决了 I/O 与 CPU 之间速度不匹配的问题
单道批处理系统的特征
- 单道性 内存中仅有一道程序运行
- 自动性
- 顺序性
# 1.2.3 多道批处理系统
多道程序设计的基本概念
用户提交的作业形成队列,按一定算法将若干作业调入内存
多道程序设计的优点
- 提高 CPU 利用率
- 提高内存和 I/O 设备利用率
- 增加系统吞吐量
多道程序设计的缺点
- 平均周转时间长
- 依然无交互能力
# 1.2.4 分时系统
分时系统产生的动力
- 人们亟需可以实现人机交互的处理机以便调试运行程序
- 共享主机
分时系统实现中的关键问题
- 及时接收 及时接收各个用户终端的输入
- 及时处理 及时处理用户键入的命令
=> 分时系统,将 CPU 的时间分片,每个作业每次只能运行一个时间片
分时系统的特征
- 多路性
- 独立性 每个人都好像独占资源
- 及时性
- 交互性
# 1.2.5 实时系统
需求
- 实时控制
- 实时信息处理
实时任务
- 按任务执行时是否呈现周期性来划分
- 周期性实时任务
- 非周期性实时任务
- 根据对截止时间的要求来划分
- 硬实时任务
- 软实时任务
- 按任务执行时是否呈现周期性来划分
实时系统与分时系统特征的比较
- 多路性
- 独立性
- 交互性
- 及时性
- 可靠性
# 1.2.6 微机操作系统的发展
单用户单任务操作系统
- CP/M
- MS-DOS
单用户多任务操作系统
各种 Windows
多用户多任务操作系统
UNIX
- Solaris
- Linux ❤️
# 1.2.7 其它操作系统
- 网络操作系统
- 分布式操作系统 可独立也可协同,对用户来说相当于一个操作系统
- 嵌入式操作系统
# 1.3 操作系统的特征
# 1.3.1 并发性
并行和并发的区别,组原就有提到,并行是真的多处理器处理多数据,并发是利用时分技术实现的,其微观本质上还是串行
为了实现并发,引入了进程的概念,其作为资源分配的基本单位,可在系统中能独立运行
为了进一步提高并发程度,在进程内引入了线程,其作为独立运行和独立调度的基本单位,并不会拥有系统资源,开销就会小很多
# 1.3.2 共享性
互斥共享技术
保证各个进程之间不会混淆
同时访问方式
各个进程可以同时访问同一个设备,比如磁盘
# 1.3.3 虚拟技术
- 时分复用技术
- 虚拟处理机技术
- 虚拟设备技术
- 空分复用技术
- 虚拟磁盘技术 磁盘分区
- 虚拟存储器技术
# 1.3.4 异步性
各个进程停停走走……
# 1.4 操作系统的五大功能
# 1.4.1 处理机管理
- 进程控制
- 进程同步
- 进程通信
- 调度
# 1.4.2 存储器管理功能
- 内存分配
- 内存保护
- 地址映射
- 内存扩充
# 1.4.3 设备管理功能
- 缓存管理
- 设备分配
- 设备处理
# 1.4.4 文件管理功能
- 文件存储空间的管理
- 目录管理
- 文件的读/写管理和保护
# 1.4.5 操作系统与用户之间的接口
- 用户接口
- 程序接口
# 1.4.6 现代操作系统的新功能
- 系统安全
- 网络的功能和服务
- 支持多媒体
# 1.5 OS 结构设计
# 1.5.1 传统的操作系统结构
- 无结构操作系统
- 模块化结构操作系统 分解成一个一个模块
- 分层式结构 OS 有序分层
# 1.5.2 客户/服务器(C/S)模式简介
便于集中管理,但会有瓶颈问题和不可靠性
# 1.5.3 面向对象的程序设计(OOP)简介
# 1.5.4 微内核 OS 结构
足够小的内核
将操作系统中最基本的部分放入微内核,其他部分放在外面作为服务器
基于 C/S 模式
应用”机制与策略分离“原理
采用面向对象技术
# 2 进程管理
# 2.1 进程的基本概念
# 2.1.1 程序的顺序执行及其特征
程序的顺序执行是指程序可以保证其按照其顺序执行
特征
- 顺序性
- 封闭性
- 可再现性
# 2.1.2 程序的并发执行及其特征
多道程序并发执行
特征
- 间断性
- 失去封闭性
- 不可再现性 (资源共享,可能使用时被其他程序所修改)
# 2.1.3 进程的特征与状态
定义
- 进程是程序的一次执行
- 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
- 进程是程序在一个数据集合上运行的过程,它是系统进行资源分配和调度的一个独立单位
特征
- 结构性
- 动态性
- 并发性
- 独立性
- 异步性
状态
- 活动进程的三种状态
- 就绪
- 执行
- 阻塞
- 另外两种状态
- 创建
- 终止
- 挂起状态(将进程内存 外存)
N 核 CPU ,共有 M 个进程
- 就绪态用户进程最多几个?最少几个?
- M-N, 0
- 执行态用户进程最多几个?最少几个?
- N, 0
- 阻塞态用户进程最多几个?最少几个?
- M, 0
- 活动进程的三种状态
# 2.1.4 进程控制块 PCB
系统是根据进程的 PCB 感知到该进程的存在的,PCB 是进程存在的唯一标志,因此系统总是通过 PCB 对进程进行控制的
PCB 中的信息
- 进程标识信息
- 内部标识号 PID ,操作系统分配
- 外部标识号 由字母数字组成的,创建者提供
- 处理机状态信息
- 通用寄存器
- 指令计数器
- 程序状态字 PSW
- 用户栈指针
- 进程调度信息
- 进程状态
- 进程优先级
- 进程调度所需的其它信息
- 事件
- 进程控制信息
- 程序和数据的地址
- 进程同步和通信机制
- 资源清单
- 链接指针(当然,索引方式应该是没有的)
- 进程标识信息
PCB 组织方式
链接方式 组织成链表
索引方式 额外建立一个索引表,更快,但是额外消耗一部分内存
# 2.2 进程控制
通过原语来实现
原语是原子操作,是不可分割的基本单位,要么全做、要么全不做
# 2.2.1 进程的创建
进程图
是一种树状的家族关系,子进程继承父进程资源,如 UNIX
Windows 不是这种关系,Win 的各个进程之间是平等的,并不是层次关系,进程之间的关系是通过获取句柄来调节的
引起创建进程的事件
- 用户登录
- 作业调度
- 提供服务
- 应用请求
进程的创建原语(Create)
- 申请空白 PCB
- 为新进程分配资源
- 初始化 PCB
- 将新进程插入就绪队列
# 2.2.2 进程的终止
引起进程终止的事件
- 正常结束
- 异常结束
- 越界错
- 保护错
- 非法指令
- 特权指令错
- 运行超时
- 等待超时
- 算术运算错
- I/O 故障
- 外界干预
- 操作员或操作系统干预
- 父进程请求
- 父进程中止
进程的终止原语(termination)
- 根据被终止进程的标识符,检索出 PCB ,读取进程状态
- 若处于执行状态,则立即终止
- 若还有子孙进程,则递归终止
- 将资源归还其父进程或者系统
- 将被终止进程 PCB 从所在队列中移出
# 2.2.3 进程的阻塞与唤醒
引起进程阻塞和唤醒的事件
- 请求系统服务
- 启动某种操作
- 新数据尚未到达
- 无新工作可做
进程阻塞原语(block)
进程唤醒原语(wakeup)
# 2.2.4 进程的挂起和激活
- 进程挂起原语(suspend)
- 进程激活原语(active)
# 2.3 进程同步
本章节 Python 实现 (opens new window)
# 2.3.1 进程同步的基本概念
- 两种形式的制约关系
- 间接相互制约关系(互斥) 多个进程共享系统资源
- 直接相互制约关系(同步) 多个进程之间共同访问缓冲区
问题的根源就在于 临界资源
临界资源 就是发生冲突的部分 比如共享的系统资源(硬件临界资源)、共享的缓冲区(软件临界资源)
临界区 每个进程中访问临界资源的那段代码,我们将一个访问临界资源的循环进程描述如下
while (TRUE) { 进入区(entry section) 临界区(critical section) 退出区(exit section) 剩余区(remainder section) }
1
2
3
4
5
6各进程对自己的临界区访问是互斥的
同步机制应遵循的规则
- 空闲让进
- 忙则等待
- 有限等待
- 让权等待
# 2.3.2 硬件同步机制
- 关中断 但是会引发一系列问题
- 利用 Test-and-Set 指令实现互斥 将“测试并建立”作为一条原语
- 利用 Swap 指令实现进程互斥 使用 lock 和 key 两个变量
他们虽然都实现了互斥,但是都有一个很大的问题,就是尝试访问资源是连续测试的(如 while TS(&lock);
),仍然浪费 CPU 资源,不符合“让权等待”原则
# 2.3.3 信号量机制
整型信号量
wait(S) { while (S <= 0); S--; } signal(S) { S++; }
1
2
3
4
5
6
7
8问题当然是,还是不符合“让权等待”原则
记录型信号量
typedef struct { int value; struct process_control_block *list; } semaphore; wait (semaphore *S) { S->value--; if (S->value < 0) block(S->list); } signal(semaphore *S) { S->value++; if (S->value <= 0) wakeup(S->list); }
1
2
3
4
5
6
7
8
9
10
11
12
13
14与前面不同的是,我们现在定义了一个数据结构,增加了一个列表,这个列表干嘛呢?
由于我们要在无法获取资源的时候将 CPU 资源让出去,所以 while 轮询是不可行的了,我们可以使用 block 原语将自己阻塞起来,等到有资源的时候让别人唤醒自己,当然,为了保证别人能唤醒自己,就要把自己存储到一个列表中,就是我们新的数据结构中的那个列表啦
另外,我们可以将 value 当做资源数,初始化的数量就是资源的总数量
AND 型信号量
当一个进程需要多个资源才能执行怎么办呢?比如进程一二都需要资源一二,进程一请求资源一成功,进程二请求资源二成功,这时候进程一继续请求资源二,把自己阻塞起来了,进程二请求资源一,也把自己阻塞起来了,结果……死锁了……
如何解决?如果我们将某个进程请求一系列资源作为一个原语就可以啦,这样就不需要担心请求一部分另一部分没请求到的问题啦,这时候使用
Swait(S1, S2, ..., Sn)
和Ssignal(S1, S2, S3, ..., Sn)
,S1
到Sn
表示该进程所需要的所有资源信号量集
在 AND 型信号量的基础上增加 和 , 表示资源的分配下限值, 才予以分配, 表示资源的需求量,对应格式变为 - -
有以下几个特殊用法:
Swait(S, d, d)
每次申请 d 个资源,低于 d 个不予申请Swait(S, 1, 1)
一般的记录型信号量Swait(S, 1, 0)
时,允许多个进程进入特定区, 时,将阻止任何进程进入特定区
有个细节需要注意下,就是
Swait
结束后被唤醒并不能直接进入临界区,还需要重新尝试请求资源,因为这个时候并不能保证所有资源都就绪,而wait
只需要一个资源,这就保证了被唤醒后资源一定全部就绪,所以可以直接进入临界区
# 2.3.4 信号量的应用
使用信号量实现互斥
(两个进程为例)使用 mutex 作为互斥信号量,它可以取
{-1, 0, 1}
,初始化为 1- mutex = 1,表示两个进程均未进入临界区
- mutex = 0,表示一个进程进入临界区
- mutex = -1,表示一个进程进入临界区,另一个尝试进入临界区失败,阻塞并存入队列
为了实现互斥,就需要两个进程进入临界区前调用
wait(mutex)
,出临界区后调用signal(mutex)
,否则会引发错误利用信号量实现前趋关系
如何保证一个进程运行到命令 B 的时候另一个进程已经将命令 A 运行完了?比如一个进程要读取另一个进程写完的文件,怎么保证在这之前另一进程写操作已经完成?
仍然使用这个套路,不过将 mutex 初值置为 0 ,我们在后继任务前调用
wait(mutex)
,在前趋任务完成后调用signal(mutex)
,这样就可以保证后继任务先到达的话会阻塞,而前趋任务完成后,就会“通知”后继任务可以开始做啦管程机制
是使用面向对象将共享变量、条件变量以及各种方法等等封装起来,同时只能有一个进程进入管程,这就保证了对临界资源的访问是互斥的
当调用管程的进程被阻塞时,其它进程也就不能进入管程使用资源,为了解决该问题,管程内设了条件变量,当进程因为条件 x 而发生阻塞时,进程调用
x.wait
方法,将自己加入阻塞队列,直到条件 x 发生了变化,其它进程(当时正在管程内的进程)调用x.signal
将队列 x 下的进程唤醒
# 2.4 经典进程的同步问题
# 2.4.1 生产者-消费者问题
使用记录型信号量解决该问题
- 生产者先后使用
wait(empty)
wait(mutex)
signal(mutex)
signal(full)
- 消费者先后使用
wait(full)
wait(mutex)
signal(mutex)
signal(empty)
注意
wait
的先后顺序,如果wait(mutex)
wait(empty)
可以想象下满了或者空的情况,会出现死锁……- 生产者先后使用
利用 AND 信号量解决该问题
- 生产者先后使用
Swait(empty, mutex)
Ssignal(mutex, full)
- 消费者先后使用
Swait(full, mutex)
Ssignal(mutex, empty)
解决死锁问题
- 生产者先后使用
利用管程解决该问题
定义好管程内要做的,生产者用
PC.put(x)
, 消费者用PC.get(x)
即可
一些变体
- 缓冲区无限大,那么我们就不需要
wait(empty)
signal(empty)
了- 生产者生产者互斥、消费者消费者互斥,但生产者消费者不互斥,我们只需要设两个互斥信号量即可
# 2.4.2 哲学家进餐问题
The_Dining_Philosophers.py (opens new window)
利用记录型信号量解决该问题
防止他们同时拿起左侧筷子造成的死锁,需要有一定的改进方案
利用 AND 信号量机制解决该问题
很容易想到这个方法解决上述问题
# 2.4.3 读者-写者问题
Writer_and_Reader.py (opens new window)
需要注意的是,当一个 Writer 进程在写的时候,不允许任何 Reader 进程和 Writer 进程访问该对象
但是要怎么实现呢?
- 写者的话,直接用一个互斥信号量
wmutex
就好了 - 读者需要考虑的比较多
- 首先,读者之间是不互斥的,我们是要解决读者使写者不能读的问题,所以当读者在读的时候,
wait(wmutex)
- 但是,如果直接
wait(wmutex)
的话,所有“者”都互斥了,可是多个读者是可以同时读的 - 我们判断下是否已经有人在读了,当无人在读的情况下也就是第一个读者才
wait(wmutex)
,相应地,最后一个读者才signal(wmutex)
- 为了判断读者数量,额外引进了一个变量,这个变量会成为临界资源,所以需要使用
rmutex
包裹,以保证读者读写该变量时互斥
- 首先,读者之间是不互斥的,我们是要解决读者使写者不能读的问题,所以当读者在读的时候,
另外,可以利用信号量集以更巧妙的方法实现(注意 Swait(S, 1, 0)
,只检查资源,不消耗)
Writer_and_Reader.py (opens new window)
# 2.4.4 其他问题(习题)
- 购物问题 Shopping.py (opens new window)
- 进程同步 Processes.py (opens new window)
- 独木桥问题 Single-plank_Bridge.py (opens new window)
# 2.5 进程通信
共享存储器系统
- 基于共享数据结构的通信方式
- 基于共享存储区的通信方式 中等信息传递,用户解决同步问题
管道(pipe)通信系统 大量信息传递,系统解决同步问题
消息传递系统 少量信息传递,系统解决同步问题
客户机-服务器系统
- socket
- RPC
# 2.6 线程的基本概念
# 2.6.1 线程与进程的对比
- 调度的基本单位 切换开销小
- 并发性 线程之间也可以并发执行
- 拥有资源 并不拥有系统额外分配的资源,享有父进程的资源,故创建开销小
- 独立性 同一进程的不同线程之间可以共享资源,独立性不明显
- 系统开销 创建与切换都远比进程快
- 支持多处理机系统 一个进程的多个线程可在多个核心上运行,这使得多个线程之间实现了真的并行,大大提高了该进程的完成速度
# 2.6.2 线程的状态和线程控制块
- 线程的三个状态 和进程一样 执行、就绪、阻塞
- 线程控制块 TCB 类似于 PCB
# 2.7 线程的实现
# 2.7.1 线程的实现方式
内核支持线程 KST
内核所“承认”的线程,可获得内核分配的 CPU 时间片,也可在多核 CPU 上实现并行
- 优点
- 更轻量的结构
- 进程中一个线程阻塞后,其余线程可正常运行
- 多核心可并发执行
- 优点
用户级线程 ULT
使用函数库就可以实现,内核并不知道用户级线程的存在,所以内核给它分配的时间片是按其父进程分配的,各个线程将争夺进程的时间片执行
- 优点
- 线程切换不需要到内核空间(不需要用户态与核心态的切换)
- 调度算法可以是进程专用的
- 用户级线程的实现与 OS 平台无关
- 优点
组合方式
用户级线程与内核支持线程的组合(多对一、一对一、多对多)
# 3 处理机调度与死锁
# 3.1 处理机调度的层次
调度程序 | 调度对象 | 分配资源 | 调度频率 | 适宜的调度算法 |
---|---|---|---|---|
长程调度(作业) | 后备作业 | 内存、设备 | 低 | 资源搭配、先进先出、优先数、短作业优先、最高响应比优先 |
中程调度(交换) | 就绪进程、等待进程 | 内存、外存 | 中 | 优先算法、FIFO |
短程调度(进程) | 就绪进程、就绪线程 | CPU | 高 | 轮转法、多级反馈 |
# 3.1.1 高级调度
作业 = JCB + 作业说明书 + 程序 + 数据
作业步 作业的各个相对独立步骤
作业控制块 JCB
调度算法
- 先来先服务算法
- 短作业优先调度算法
- 响应比高者优先的调度算法 综合考虑上面两种算法
- 基于作业优先级的调度算法
# 3.1.2 低级调度
基本机制
- 排队器
- 分派器
- 上下文切换机制 (两对上下文切换操作)
进程调度方式
- 非抢占方式
- 抢占方式(按一定原则抢占 CPU)
- 优先权原则
- 短作业(进程)优先原则
- 时间片原则
# 3.1.3 中级调度
将内存上的进程转换到外存上或相反的过程,也就是进程的挂起与唤醒,提高了内存的利用率
# 3.2 调度队列模型和调度准则
# 3.2.1 调度队列模型
仅有进程调度的调度队列模型
具有高级和低级调度的调度队列模型
同时具有三级调度的调度队列模型
# 3.2.2 选择调度方式和调度算法的若干原则
面向用户的原则
- 周转时间快 (使用平均周转时间评估)
- 响应时间快
- 截止时间的保证
- 优先权准则
面向系统的准则
- 系统吞吐量高
- 处理机利用率好
- 各类资源的平衡利用
# 3.3 调度算法
- 周转时间:作业等待的时间
- 带权周转时间:周转时间 / 服务时间
# 3.3.1 先来先服务算法
很明显, FCFS 的周转时间会很长
# 3.3.2 短作业(进程)优先调度算法
SJF 算法极大地提高了系统吞吐量,但是会出现长作业长期不被调度的情况
# 3.3.3 高优先权优先调度算法
优先权调度算法的类型
- 非抢占式优先权算法
- 抢占式优先权调度算法
优先权的类型
- 静态优先权 不可改变的
- 动态优先权 可随着进程的等待时间而改变,我们可以规定,在就绪队列的进程,随其等待时间的增长,其优先权以速率 a 提高
高响应比优先调度算法
优先权 = (等待时间 + 要求服务时间) / 要求服务时间
# 3.3.4 基于时间片的轮转调度算法
时间片大小的确定
- 时间片太大会使得算法退化,时间片太小会增大切换上下文的开销,故可以取略大于一次典型交互所需要的时间作为时间片
# 3.3.5 多队列调度算法
分成不同的队列,为不同就绪队列设置不同的调度算法
# 3.3.6 多级反馈队列调度算法
- 设置多个就绪队列
- 为每个队列设置一个优先级
- 仅当优先级高的队列空闲时才能调度优先级低的队列
# 3.4 实时调度
# 3.4.1 实现实时调度的基本条件
- 提供必要的信息 就绪时间等等
- 系统处理能力强
- 采用抢占式调度机制
- 具有快速切换机制
# 3.4.2 实时调度算法的分类
- 非抢占式调度算法
- 非抢占式轮转调度算法
- 非抢占式优先调度算法 将实时任务放在队首
- 抢占式调度算法
- 基于时钟中断的抢占式优先权调度算法 时钟周期的整数倍时刻才能抢占
- 立即抢占的优先权调度算法
# 3.5 产生死锁的原因和必要条件
# 3.5.1 产生死锁的原因
竞争资源(竞争非剥夺性资源) 资源数量不足需求 形成环路
进程间推进顺序非法
# 3.5.2 产生死锁的必要条件
- 互斥条件
- 请求和保持条件 所需资源使用完之前不释放已有资源
- 不剥夺条件 只能主动释放资源,其他人不可抢占
- 环路等待条件 发生死锁时,必然存在资源的环路链
# 3.5.3 处理死锁的基本方法
- 预防死锁
- 避免死锁
- 检测死锁
- 解除死锁
# 3.6 预防死锁
由于死锁时必要条件一定满足,所以破坏了死锁的必要条件就可以防止死锁,当然,互斥条件我们不应该破坏,因为我们需要它来保证进程的同步问题
# 3.6.1 摒弃“请求和保持”条件
由动态分配改为静态分配,在所有进程运行之前一次性将所有所需资源申请下来
但是,这大大降低了资源的利用率
# 3.6.2 摒弃“不剥夺”条件
新的资源请求会剥夺已占有的资源
很复杂很复杂,打印机写一半怎么处理呢?增加了系统开销
# 3.6.3 摒弃“环路等待”条件
资源有序分配,将各个资源标号,每次申请资源都要按序号递增的次序来申请,避免了环路的产生
比如一个进程已经拥有了一个序号比较高的资源,此时想申请序号比较低的资源的话,必须先释放序号比较高的资源
相比前两种是比较好的策略,但仍有一些不足,比如序号的分配等等问题
# 3.7 避免死锁
# 3.7.1 系统安全状态
如果为进程分配资源后系统会进入不安全状态,那么就不给它分配资源
所谓安全状态,就是指系统存在某种进程顺序来为每个进程分配其所需资源,使得所有进程都能顺利完成,否则即为不安全状态
当然,不安全状态只是不安全,可能发生死锁,并不是一定发生死锁,而安全状态保证了不会发生死锁
Example
进程号 总共需求 已分配 还需 剩余 P1 10 5 5 3 P2 4 2 2 P3 9 2 7 很明显,存在安全序列 <P2, P1, P3> 使得进程全部执行完毕
那么,P3 申请一个资源的话,我们要不要给呢?
首先,假如分配的话,会变成如下状态
进程号 总共需求 已分配 还需 剩余 P1 10 5 5 2 P2 4 2 2 P3 9 3 6 嗯,找不出来那样的一个序列了,也就是系统会进入不安全状态,所以,拒绝!不给分配!
# 3.7.2 利用银行家算法避免死锁
(万能的 Dijkstra)
银行家算法中的数据结构
n 为进程数, m 为资源数
- 可利用资源向量 Available ()
- 最大需求矩阵 Max ()
- 分配矩阵 Allocation ()
- 需求矩阵 Need ()
具体算法的话,就是上面例子里的一个资源换成多个资源就好啦
# 3.8 死锁的检测与解除
# 3.8.1 死锁的检测
由于死锁的预防的资源利用率太低,而死锁的避免又消耗了大量的计算资源来实现,所以在死锁发生的并不频繁的情况下,可以使用死锁的检测 + 解除,当然,我们可以选择在 CPU 利用率比较低的时候才检测,以降低对 CPU 的使用
- 资源分配图
与前面的环路图是一样的,只不过这里资源结点可以代表多个资源,进程指向资源仍旧代表进程请求资源,资源指向进程仍旧代表资源以分配给该进程,只不过每条线代表一个资源
我们可以尝试通过对资源分配图进行简化来判断是否发生死锁,非死锁情况下资源分配图可简化为各个独立的结点
# 3.8.2 死锁的解除
- 剥夺资源 从其他进程剥夺足够数量的资源给死锁进程
- 撤销进程 kill 掉死锁进程
# 4 存储器管理
# 4.1 存储器的层次结构
# 4.1.1 多级存储器结构
# 4.1.1 主存储器与寄存器
嗯……就是主存储器和寄存器……
# 4.1.2 高速缓存和磁盘缓存
高速缓存 Cache
解决 Memory 与 CPU 速度不匹配的问题
磁盘缓存
解决磁盘 I/O 与 Memory 速度不匹配的问题,使用 Memory 部分空间作为磁盘的缓存区,用于暂存频繁使用的磁盘数据
# 4.1.3 内存管理
(概述,后面详细阐述)
- 内存的分配与回收
- 直接分配 程序内地址为固定值
- 静态分配 作业装入内存后地址固定不变
- 动态分配 作业装入内存后地址可变
- 地址转换
- 逻辑地址:源程序内的变量等地址经过编译或汇编后生成逻辑地址
- 物理地址:程序由操作系统装入内存后所指的真实内存地址
- 内存保护
- 防止进程的数据被非法访问
- 防止越界
- 上下界寄存器
- 基址、限长寄存器
- 内存共享
- 多个进程共享内存中的同一段信息
- 内存扩充
- 覆盖 让常用功能常驻内存,非常用功能按需装入
- 对换 挂起不用的程序段
- 虚拟存储器 利用程序的局部性原理,将部分程序装入
# 4.2 程序的装入和链接
# 4.2.1 程序的装入
即上面的三种分配方式
- 绝对装入方式 直接
- 可重定位装入方式
- 静态重定位 程序执行之前地址转换完毕
- 动态重定位 程序执行期间进行地址转换
# 4.2.2 程序的链接
- 静态链接 程序运行前链接
- 装入时动态链接 运行前将所有可能需要运行的模块装入链接
- 便于修改和更新
- 便于实现对目标模块的共享
- 运行时动态链接 运行时按需装入链接(如
dll
)
# 4.3 连续分配方式
# 4.3.1 单一连续分配
单用户、单任务,只需要考虑系统区和用户区,用户区也只有一个任务……
# 4.3.2 固定分区分配
一个分区一道作业,所以就需要划分分区咯
# 4.3.3 动态分区分配
根据进程的实际需要,动态地为之分配内存空间
数据结构
- 空闲分区表
- 空闲分区链 (就是个链表)
分区分配算法
- 首次适应算法 从头找,能放下该作业就放
- 循环首次适应算法 使用一个指针,这样就不会每次都从头找啦
- 最佳适应算法 每次找满足条件的最小分区
- 易形成碎片
- 最坏适应算法 每次找最大的分区,分割出一部分分配给该作业使用
- 使得存储器中缺乏大的空闲分区
- 查找效率高
- 产生碎片少
- 内碎片 分区内部未利用的空间
- 外碎片 分区之间未利用的空间
- 分区回收算法
- 看上下有没有空闲区咯,有的话当然要合并~
# 4.3.4 可重定位分区分配
依赖于 4.1.3 中提到的动态分配技术,这样分区就可以移动啦,然后我们就可以将分区进行拼接、使之紧凑起来
# 4.4 基本分页存储管理方式
将内存分为好多好多页,支持不连续分配,使用页表形成地址映射,每个进程一个页表
- 可实现虚存
- 避免移动
- 避免外部碎片
# 4.4.1 页面与页表
- 页面就是将逻辑地址空间分为大小相等的片,其大小应为
- 物理块是物理地址空间对应的与页面大小相同的存储块
- 页表就是将页(面)号与(物理)块号对应起来的映射表
当然,现在寻址的话需要两部分地址号了,一部分是页号,一部分是页内号(位移量),一般情况下页内大小为 ,故页内号需要使用 的地址,如果是 系统的话,那么剩下 就是页号地址空间啦,即最多 个页
# 4.4.2 地址变换机构
基本的地址变换机构
那么我们如何将逻辑地址转换成物理地址呢?
首先,获取页号和位移量,然后根据页表寄存器中的页面始址与页号获得该页的实际物理地址(开始位置),然后再加上页内的偏移量就得到了要找的物理地址
但是,我们的页表已经非常大了,寄存器是肯定放不下了,需要放到内存中去,也就是说,我们每次访存需要先访问内存中的页表,然后据此再得到真正想要访问的地址,也就是访存次数多了一倍,效率大大降低……
具有快表的地址变换机构
根据局部性原理,我们增加一个快表(联想寄存器),存储最近访问过的页表项,据统计,快表命中率可达 90% 以上,大大降低了页表方式带来的效率降低影响
# 4.4.3 两级和多级页表
我们的页表方式实现了非连续存储,但是我们的页表本身却也是放在内存里的,而且其大小也超过了一页的大小(),这样问题就来了,页表到底是要如何存储呢?
回到最初,我们是如何将离散存储的内存页组织起来的?很明显是通过页表,但是现在要求连续存储的页表也要离散存储了,我们如何将其组织起来呢?那就再加一层页表咯,这就形成了两级页表
事实上,在 系统下,三级页表都是不够的,但是我们事实上也用不上那么大的地址空间(等内存能那么大得多少年后啊……),所以暂时使用三级页表也是能满足现在的需求的
# 4.4.4 页式管理的分配与回收
根据位示图进行分配与回收即可
# 4.4.5 页式管理的特点
- 优点
- 分配与回收简单
- 消除外碎片
- 可实现虚存、共享
- 缺点
- 页面划分不考虑程序的逻辑结构
- 共享受限
- 二次访内,速度慢
# 4.5 分段存储管理方式
分页实现了对内存的高效利用,消除了外碎片,但是其对于用户来说仍然只是取某个地址,然后操作系统根据后 作为页内地址,前 为页号,实际过程对用户并不可见,用户只需要按原来的方式取某个地址就好
所以说,分页存储可以说是在底层的一种管理实现方式,大多是与硬件相耦合的,可以做到对内存的更高效利用
引入本节的分段存储方式,并不是说分页存储不好,因为它们根本是在两种层级上的问题,后面会介绍它们相互结合的方式——段页式存储——就很好地结合了两者的优点,在底层仍然使用分页式存储,上层逻辑存储使用分段式存储,但是这里,我们底层仍然使用的是连续存储方式哦
那么分段有什么优点呢?
# 4.5.1 分段存储管理方式的引入
- 方便编程 我们可以为某一段程序(比如一个函数)分配一段连续的空间,这样就可以很方便地使用段内的偏移量进行编程了
- 信息共享 我们很容易分出一个段来供进程来共享
- 信息保护
- 动态增长
- 动态链接
# 4.5.2 分段系统的基本原理
既然逻辑空间仍然划分为不等长的几段,这几段也是分别放在不同的位置,所以,我们还是需要一个表建立索引关系,只不过这次我们需要记录的有段号、段长、基址(某段的首地址)三个信息,因为我们现在每段不等长了,形成的表格称为段表,也放在内存内
相应地,我们现在给出的地址必须由段号和段内偏移两部分组成(真的是二维的寻址方式,而分页仍然使用一维寻址,两个号由操作系统自动计算得出),当然,我们仍然是两次访存,想要快点也是要建立快表
# 4.5.3 信息共享
比如一个多用户操作系统运行一个文本编辑进程,但多个用户每人一个数据区,如果是分页式是如何的呢?
emmm 虽说共用一个进程吧,但是每个页表都要记录该进程的各个页
相对来说,下面的分段式就很好看啦~
# 4.5.4 段式管理的特点
缺点的话,就是连续式存储的一些缺点,但这个的话我们下面的段页式可以解决
优点就不用说了,前面介绍好久了都~
# 4.5.5 段页式存储管理方式
使用分段的逻辑存储方式,加之以底层分页式存储方式,每个进程建立一个段表,每个段建立一个页表,当然,我们现在需要三次访存咯,不建立快表没法用的说
共享的实现
段页式和分段式是同样容易实现共享的,因为我们在逻辑层面上使用相同的段存储一段共享数据,在段表内只需要一项,而页表内也没有重复的,只需要该段与实际存储地址之间的映射关系
很好地结合了两者的优点,所以说,两者根本不冲突嘛,他们是两种层级上的方案,或者我们这么看
逻辑\物理 | 连续 | 分页 |
---|---|---|
不分段 | 连续分配 | 分页式 |
分段 | 分段式 | 段页式 |
嗯,我们所学的四种,大概就是这样的关系~
只不过逻辑分段与物理分页有着相似的实现方式,所以我们可能会认为他们是相同层级的方式,从原因与涉及的层面来看,它们并无太大关系
# 4.6 虚拟存储器的基本概念
前面所述的存储方式虽然实现了非连续存储,进而提高了内存的利用率,但每次都还是将整个进程装入内存,下面有个更逆天的方式,极大地提高内存利用率,那就是虚拟存储器
为什么需要虚拟存储器?因为我们的整个程序往往是很大的,很容易就将内存撑爆了,根据局部性原理,我们可以只将当前运行的部分调入内存,这样就可以大大降低内存臃肿的状态啦
# 4.6.1 虚拟存储器的引入
局部性原理
- 时间局部性
- 空间局部性
虚拟存储器定义
基于局部性原理,应用程序在运行之前,没有必要全部装入内存,仅需将那些单前要运行的少数页面或段先装入内存便可运行,其余部分暂留在盘上
- 请求调页 如果要访问的页(段)在内存则直接执行;否则需要发生请求调页中断
- 页面置换 若内存已满,则将暂时不用的页调入硬盘
虚拟存储器特征
- 多次性 多次调入
- 对换性
- 虚拟性 从逻辑上扩充内存容量
# 4.7 请求分页存储管理方式
需要扩展页表以支持请求分页存储
页号 | 物理块号 | 状态位 P | 访问字段 A | 修改位 M | 外存地址 |
---|---|---|---|---|---|
0 | 10 | 1 | 1 | 0 | 120 |
1 | 14 | 1 | 0 | 0 | 123 |
2 | 15 | 1 | 2 | 0 | 134 |
3 | - | 0 | - | - | 135 |
# 4.7.1 请求分页中的硬件支持
页表机制
其中各字段说明:
- 状态位 P :该页是否调入内存
- 访问字段 A : 本页在一段时间内被访问的次数,作为选择换出页面参考
- 修改位 M : 记录调入内存后是否被修改过,如果被修改过,换出时需要重新写入内存
- 外存地址
缺页中断机构
请求分页时,需要的页不在内存时,产生缺页中断
与一般中断的区别
- 在指令执行期间产生和处理中断信号
- 一条指令在执行期间可能产生多次缺页中断,比如该指令本身跨两个页,所需要的两个数据块分别又跨两个页,共产生 6 次缺页中断
地址变换机构
# 4.7.2 内存分配策略和分配算法
最小物理块数的确定
保证进程正常运行的最小物理块数
内存分配策略 分配策略分为固定和可变分配策略,而置换时还有全局置换和局部置换两种置换策略
固定分配局部置换
每个进程分配固定数量的物理块
可变分配全局置换
进程的物理块数可动态调整,当所需页不在内存时,从空闲内存或者其他进程内存选择一块换出,即该进程内存空间会增加
可变分配局部置换
进程物理块数仍可动态调整,发生缺页中断从该进程内存中选择一页换出,当频繁发生缺页中断时,才可以为该进程增加物理块数,反之,若缺页率特别低,则可适当减少该进程物理块数
物理块分配算法
- 平均分配算法 所有进程分配的物理块数一样,很明显不公平
- 按比例分配算法 按照进程大小按比例分配
- 考虑优先权的分配算法 在按比例分配算法基础上考虑重要的紧急的任务,可为该类任务额外分配物理块以使之更快地完成任务
# 4.7.3 调页策略
调入页面的时机
- 预调页策略 额外调入连续的几页
- 请求调页策略 当发现不在内存时,调入该页
确定从何处调入页面
TIP
外存分为
- 文件区 离散的分配方式,读写慢
- 对换区 连续的分配方式,读写快
- 系统拥有足够的对换区空间,可全部从对换区调入所需页面
- 系统缺少足够的对换区空间,需要修改的放到对换区,以便需要时从对换区调入
- UNIX 方式,未运行的从文件区调入,运行过换出到对换区,下次可直接从对换区调入(甚至可能已经被其他进程调入内存)
页面调入过程
访问需考虑是否缺页、换出需考虑是否修改过
缺页率
# 4.8 页面置换算法
# 4.8.1 最佳置换算法和先进先出算法
最佳(Optimal)置换算法
每次换出的页应该是以后永不使用的或在最长(未来)时间内不再被访问的页面,很明显,我们并无法得知这样的页面是哪个,所以该算法仅仅是理论上的算法,虽然无法实现,但可以据此评估其他算法
先入先出(FIFO)页面置换算法
顾名思义,每次换出在内存中驻留时间最久的页面,可以为内存中的页面设置一个链表很容易地实现
# 4.8.2 最近最久未使用(LRU)置换算法
选择最近最久未使用的页面予以淘汰,可为每个页面赋予一个访问字段进行实现
- 硬件支持
- 寄存器 用位记录最近访问行为,每次右移,若该次访问了则将最左位置 1 ,故每次只需淘汰值最小的即可
- 栈 用于记录访问页面,访问之后放到栈顶,置换时从栈底置换
# 4.8.3 Clock 置换算法
简单的 Clock 置换算法
LRU 算法的一种近似算法,在页表内设一个访问位,另外设一替换指针,以免每次从头扫描
- 访问页面后,将该页面访问位置 1
- 缺页导致需要扫描时,从替换指针向后扫描,若该页面访问位为 1 ,则将其置 0,若为 0 ,则替换出去
改进型 Clock 置换算法
由于修改过的页需要写回磁盘,所以置换修改过的页代价相对会高些,所以该算法在考虑访问位的基础上,考虑到了修改位,在访问位一致的情况下,优先淘汰修改位为 0 的页面
具体实现就是多扫描几次,开销增大不少
# 4.9 请求分段存储管理方式
类似于请求分页,但是有少许的区别,该方式会更容易实现共享与保护
# 4.9.1 分段的共享与保护
共享
可使用共享段表来实现,可内记录共享段以及相应进程信息
保护
- 越界检查
- 存储控制检查 在段表表项中设存取控制字段
# 5 设备管理
# 5.1 I/O 系统
I/O 很容易成为系统性能的瓶颈,而且多而杂,甚至一个操作系统的 2/3 代码都是 I/O 相关代码
# 5.1.1 I/O 设备
- 分类
- 按设备的使用特性分类
- 存储设备
- 输入/输出设备
- 按传输速率分类
- 低速设备
- 中速设备
- 高速设备
- 按信息交换的单位分类
- 字符设备 以字节为单位,如打印机
- 块设备 以块为单位,如磁盘
- 按设备的共享属性分类
- 独占设备(临界资源)
- 共享设备
- 虚拟设备
- 按设备的使用特性分类
# 5.2 I/O 控制(数据传输)方式
- 四种 I/O 控制方式(组原里讲的那些)
- 程序 I/O 方式(循环等待,Polling)
- 中断驱动 I/O 方式(Interrupts)
- 直接存储器存取(DMA)
- I/O 通道控制方式(Channel)
# 5.3 缓冲管理
# 5.3.1 缓冲的引入
- 缓和 CPU 与 I/O 设备间速度不匹配的矛盾
- 减少对 CPU 的中断频率,放宽对 CPU 中断响应时间的限制
- 提高 CPU 和 I/O 设备之间的并行性
# 5.3.2 单缓冲和双缓冲
- 单缓冲
- 双缓冲
# 5.3.3 循环缓冲
# 5.3.4 缓冲池
# 5.4 I/O 软件
# 5.4.1 I/O 软件的设计目标和原则
- 与具体设备无关 上层的操作不应该考虑底层到底是什么设备
- 统一命名 对设备进行统一逻辑命名
- 对错误的处理 低层软件能够解决的错误就不让高层软件感知
- 缓冲技术 向高层提供相同大小的数据块或字符单元
- 设备的分配和释放 进程管理问题,防止死锁的发生
- I/O 控制方式 I/O 软件应向高层软件提供统一的操作接口
# 5.4.2 用户层的 I/O 软件
需要通过系统调用获得操作系统服务(可通过库函数实现)
# 5.4.3 设备独立性软件
应用程序独立于具体使用的物理设备
- 在应用程序中,使用逻辑设备名称来请求使用某类设备
- 系统在实际执行时,还必须使用物理设备名称
这就需要操作系统能够完成这种转换功能
这可以带来以下好处
- 设备分配时的灵活性
- 易于实现 I/O 重定向
设备独立性软件功能主要有
- 执行所有设备的公有操作
- 向用户层(或文件层)软件提供统一接口
逻辑设备名到物理设备名映射的实现
使用逻辑设备表(LUT),内含逻辑设备名、物理设备名、设备驱动程序的入口地址
# 5.4.4 设备驱动程序
I/O 进程与设备控制器之间的通信程序
功能:
- 接收由设备独立性软件发来的命令和参数
- 检查用户 I/O 请求的合法性
- 发出 I/O 命令
- 及时响应由控制器或通道发来的中断请求
- 对于设置有通道的计算机系统,驱动程序还应能够根据用户的 I/O 请求,自动地构成通道程序
特点:
- 设备驱动程序主要是指在请求 I/O 的进程与设备控制器间的一个通信和转换程序
- 驱动程序与设备控制器和 I/O 设备的硬件特性紧密相关,因而对不同类型的设备一个配置不同而驱动程序
- 驱动程序与 I/O 设备所采用的 I/O 空盒子方式紧密相关
- 由于驱动程序与硬件紧密相关,因而其中的一部分必须用汇编语言书写
# 5.4.5 中断处理程序
- 唤醒被阻塞的驱动(程序)进程
- 保护被中断进程的 CPU 环境
- 转入相应的设备处理程序
- 中断处理
- 恢复被中断进程的现场
# 5.5 设备分配
# 5.5.1 设备分配中的数据结构
- 系统设备表(SDT, 整个系统一张):设备名、设备控制块指针
- 设备控制块(DCT, 每设备一张):设备状态、分配状态、等待队列、控制器控制块指针
- 控制器控制块(COCT, 每控制器一张):控制器状态、等待队列、通道控制块、指针
- 通道控制块(CHCT, 每通道一张):通道状态、等待序列
# 5.5.2 设备分配时应考虑的因素
设备的固有属性
- 独占性(是否是临界资源)
- 共享性
- 可虚拟设备
设备分配算法
- 先来先服务
- 优先级高者优先
# 5.5.3 独占设备的分配程序
- 基本的设备分配程序
- 分配设备
- 分配控制器
- 分配通道
- 设备分配程序的改进
- 增加设备的独立性 使用逻辑设备名而非物理设备名
- 考虑多通路情况
# 5.5.4 SPOOLing 技术
为了缓和 CPU 的高速性与 I/O 设备低速型之间的矛盾而引入了脱机输入、脱机输出技术,使用专门控制的外围机将低速 I/O 设备上的数据传送到高速磁盘上
SPOOLing 技术由脱机输入输出技术发展而来,使用输入进程和输出进程替代其中的输入处理器和输出处理器
- 组成
- 输入井和输出井
- 输入缓冲区和输出缓冲区
- 输入进程 和输出进程
- 特点
- 提高了 I/O 的速度
- 将独占设备改造为共享设备
- 实现了虚拟设备功能
# 5.6 磁盘存储器的管理
# 5.6.1 磁盘性能简述
数据的组织和格式
- 每个磁盘片分一个或两个存储面
- 每个磁盘面被组织成若干个同心环,这种环称为磁道(同一半径的磁道总和称为柱面)
- 每条磁道又被逻辑上划分为若干个扇区
当然,这样的话,就会有一个三维的物理地址 与一维的块号 之间的转换关系,简单的进制转换算法,不赘述
磁盘的类型
- 固定头磁盘 每个磁道一个磁头,不需移臂
- 移动头磁盘 只在每个盘面配有一个磁头,需要移臂
磁盘访问时间
地址:柱面号、磁头号、扇区号
- 柱面定位时间 花费时间最多
- 旋转延迟时间
- 数据传送时间
# 5.6.2 磁盘调度
先来先服务 FCFS
最短寻道时间优先 SSTF
每次都找离当前磁头最近的磁道
扫描 SCAN
为避免 SSTF 所带来的“饥饿”现象,使用类似于电梯的算法,每次都先沿一个方向走到最后一个(并非尽头),然后再改变方向
# 5.6.3 磁盘高速缓存
磁盘高速缓存的形式
将内存上的一部分存储空间作为磁盘的 Cache 使用,会缓存一些最近用过的从磁盘中取出的盘快,逻辑上属于磁盘、物理上是驻留在内存中的盘块
数据交付方式
- 缓存中有,则从缓存中取
- 若无,则从盘中取出,并存入缓存
置换算法 类似于请求调页算法中的置换算法,比如 LRU,下面列举一些不同点
- 访问频率 对联想寄存器的访问频率远远高于对高速缓存的访问频率
- 可预见性 高速缓存中对于哪些数据是会再次访问是有一定的可预见性的
- 数据的一致性 出现问题时使得缓存与磁盘之间未同步的问题
- 周期性地写回磁盘 按照 LRU 算法,经常使用的数据块是不会写回磁盘的,如果此时发生了故障,数据是会丢失的,所以我们可以周期性地写回磁盘以避免该问题
# 5.6.4 提高磁盘 I/O 速度的其他方法
- 提前读 当要读取文件的时候,由于大多采用顺序访问,故可提前读取下一个盘块数据
- 延迟写 有很大概率在不久之后再次访问
- 优化物理块的分布
# 6 文件管理
# 6.1 文件与文件系统
# 6.1.1 文件的概念
定义
文件是计算机系统中信息存放的一种组织形式
文件的属性
用于系统对文件进行管理,常见属性如下
- 保护信息
- 创建者
- 只读标志位
- 隐藏标志位
- 系统标志位
- 创建时间、最后访问时间、最后修改时间
- 文件长度
# 6.1.2 文件的类型
- 以文件的性质和用途分类
- 系统文件
- 库文件
- 用户文件
- 按文件的存取控制属性分类
- 只读文件
- 读写文件
- 执行文件
- 按文件的组织形式分类
UNIX 依此组织文件
- 普通文件
- 目录文件 由文件目录项组成的文件
- 特别文件 将设备作为文件进行管理
# 6.1.3 文件的操作
- 建立文件
- 打开文件
- 读文件
- 写文件
- 关闭文件
- 删除文件
- 文件指针定位
# 6.1.4 文件系统
OS 中负责处理文件相关事宜的程序和数据结构,包括文件的查找、存放、保护、共享、命名、文件常用操作的实现以及文件存储器的管理等等
# 6.2 文件结构与存储设备
# 6.2.1 文件的逻辑结构
- 流式文件(无结构文件) 基本信息单位是字节或字,其长度是所含字节的数量
UNIX 中,所有的文件都被看做是流式文件,即便是有结构文件,也被视为流式文件,系统不对文件进行格式处理
- 记录式文件(有结构文件) 是一种结构文件,由若干个记录组成
- 定长记录 处理方便,开销小
- 变长记录
# 6.2.2 文件的存取方法
- 顺序存取
- 随机存取(直接存取)
- 按键存取 使用 Hash 进行索引存取
# 6.2.3 文件的物理结构
连续结构 文件的全部信息存放在外存的一片连续编号的物理块中
- 优点 简单,支持顺序存取和随机存取
- 缺点 文件不易动态增长,预留空间浪费,不利于文件的插入和删除,存在外部碎片问题
串联结构(链接结构) 非连续的结构,存放文件信息的每一物理块中有一个指针,指向下一个物理块
优点
- 提高了磁盘空间利用率
- 有利于文件插入和删除
- 有利于文件动态扩充
缺点
- 存取速度慢,不适合随机存取
- 链接指针占用一定的空间
- 可靠性问题,如指针出错
索引结构 文件信息存放在若干不连续物理块中,系统为每个文件建立一个专用数据结构——索引表,并将这些块的块号存放在索引表中
注意,索引表也是存在物理块中的,我们使用
open
(比如C
啦,Python
啦)操作实际是将该文件的索引表加载到内存中优点
- 保持了链接结构的优点又解决了其缺点,能顺序存取,又能随机存取
- 满足了文件动态增长,插入删除的要求
- 能充分利用外存空间
缺点
索引表本身带来了系统开销,如:内外存空间,存取时间开销等
当索引表本身很大时,可考虑建立多级索引
混合索引结构(多重索引,UNIX 采用)
首先假设一个磁盘块
512 Bytes
,可存储128
个4 Bytes
的索引号,我们将主索引表分为以下区域- 直接地址 使用 10 个直接地址项,如果文件小于
10 * 512 Bytes
,就用不到后面的啦 - 一次间接地址 当超过十个直接地址项所能索引的大小时,一次间接地址指向一个磁盘块,将其作为索引表,很明显,我们又可以索引
128
个磁盘块,此时最大索引10 + 128
个磁盘块 - 多次间接地址 上述地址不足,则需要继续使用更高级的索引表……
- 直接地址 使用 10 个直接地址项,如果文件小于
# 6.2.4 文件的存储设备
磁带、磁盘、光盘、闪存 ……
# 6.3 文件目录管理
# 6.3.1 文件控制块与文件目录
目录项(文件控制块,FCB) 用于记录文件相关信息
将真正的文件属性存储在 iNode 中,更容易实现文件共享的操作
如果只有根目录 inode 在内存,那么还需要读取根目录的目录文件,s1 i_node ,s1 目录的目录文件,...,经过 6 次磁盘读取得到 file1 i_node ,之后需要读取 5 次磁盘,即最多共 11 次,如果 file1 i_node 已经在内存,只需要读取 5 次磁盘即可
# 6.3.2 目录结构
- 单级目录结构
- 二级目录结构
- 多级目录结构 树形
# 6.4 文件存储空间管理
# 6.4.1 空闲表法
每个文件分配一块连续的存储空间,外存的所有空闲区建立一张空闲表
# 6.4.2 空闲链表法
用链表来表示磁盘的空闲空间列表
空闲盘块链
空闲盘区链
# 6.4.3 位示图
以位示图来表征空闲区,可分配连续的区域,但是占用额外的空间
# 6.4.4 成组链接法
UNIX 内采用的方法,使用空闲盘块号栈进行分配回收
# 6.5 文件的共享
- 外存共享 (用户)
- 内存共享 (进程)
# 6.6 文件的保护、保密与安全
# 6.6.1 文件的存取控制
- 存取控制矩阵 存储占用大,验证费时
- 存取控制表
# 6.6.2 文件的保密
- 口令
- 密码
# Experiment
# References
- 杨志豪老师课程及其配套课件 (opens new window)
- 《计算机操作系统》 汤小丹 梁红兵 哲凤屏 汤子瀛