21.6 文件分配慕课视频播放-操作系统-MOOC慕课视频教程-柠檬大学

下面我们来讨论文件分配

文件分配是指我们把哪些块

分配给一个文件来存它的数据

在具体讨论分配方法之前呢

我们有必要来分析一下文件的大小

也就是说我分配的方法

跟文件的大小是有直接关系的

那首先我们来看

文件大小的分布情况

在我们现在想象里头

或者说在我们现在

实际数据统计里头

可以发现这样一些情况

就是大多数的文件都是很小的

所以在我们的分配方法里头呢

那个数据块的大小不能太大

因为如果说你的大部分数据

放到一块里有很大的剩余的话

那么这时候呢

它的存储效率是比较低的

所以我们在这儿呢

需要对小文件提供很好的支持

当然这个文件小呢实际上也是相对的

比如说在我们用计算机早期

我的数据呢你比如说像邮件

通常情况下就是几百个字节

几千个字节就已经算是比较少的了

但是现在的邮件呢

实际上我们上头有一图片签名

这一下子就是多少K出去了

所以这个大小呢也是一种相对的

并且随着时间的变化

和应用的变化而不同

与此同时我们还有一些非常大的文件

所以在我们分配办法里头呢

必须考虑到如何能支持这些大的文件

比如说我们来描述

分配给一个文件的数据块有多少个

那这时候呢你有一个标识

这个标识呢比如说用个整数来表示

整数有多少位

就跟你这儿能表示的

最大个的文件的大小是直接相关的

如果说你不足以表示

实际用到的最大文件的大小

那么你这个文件系统就没法来使用了

所以我们需要对大文件有很好的支持

要考虑到这个文件可能会比较大

比如说像我们现在

看到的一张光盘映像

这个映像文件通常是几个G

如果说我是一个虚拟机的镜像

那这个镜像

可能会是几十个G或者更多了

那对于这种情况呢我们也需要做考虑

所以针对这种文件大小的分布呢

我们来看如何来进行文件分配

分配是指说

我把哪些数据块给一个文件

但实际上这种分配的办法呢

它背后的本质实际上是

用什么样的方法来表示

一个文件的数据块的位置和顺序

因为这个位置和顺序的表示方法

直接决定着你如何来分配

那我们看有怎样一些分配方法

这些分配方法呢在这儿

一个是连续分配

我分配一个起点

然后连续的若干个数据块

用来存在这个文件

也可以用链式分配

我告诉你在第一块里记第二块的位置

一直到最后一块

也可以采用索引分配

我分配一块里头专门用来存序号

说我这里都有哪些块存了数据

这些块的顺序是啥样子

这是几种常见的办法

这几种办法呢

我们在选择的时候

考虑的因素呢一个是存储效率

一个是读写性能

存储效率呢是说

我每次分配的最小单位是一块

所以内碎片我们就没办法进行处理了

我们在这里能做的处理就是

你在选择数据块大小的时候做些考虑

假定这个问题我们忽略

我们来看外碎片

也就相当于如果我是连续分配

中间块数不够的时候

你想表示大文件就是不行的

所以在这儿呢

你的选择算法有存储效率的问题

当然我们说后两种算法

它就没有外碎片

所以这个问题就没有了

但是它有后面的问题

读写性能问题

说如果我是顺序分配

那我知道起点

然后我就按照序号往下算

我就能知道

我要访问的任何一个位置在哪

这样的话我的随机读取的速度会很快

但是如果说你是链式分配的话

那么这时候我要想找中间某一块

我必须从头往后去找

去遍历这个链表

那这时候呢它的读写性能就会比较差

这些都是我们在这里讨论

文件分配的时候必须考虑的指标

那我们对三种分配办法呢

做一个简要的描述

首先是连续分配

连续分配呢是在文件头也就是

我们所说的文件控制块里头呢

记录起始第一块的位置和长度

因为我是连续的

所以我知道第一块和长度之后

那么能说清楚每一块这个文件分配的

所有的块都在什么位置

我们用一个图示来表示

这就是你的索引结点

也就说文件控制块

里头有一个指针指向第一块

并且里头记录了它的长度在这儿

就从这儿到这儿

这是我的一个文件所占用的数据块

那在这里头我怎么去找

这个连续的这块区域呢

最先匹配最佳匹配

我们在前面跟内存分配

也有类似的讨论

那些讨论的特征在这儿

都有一定程度的体现

在这儿我们就不仔细去讨论了

这些做法它的特点有什么样呢

文件的读取性能表现非常好

也可以有很好的顺序

和随机读取的性能

它的麻烦是什么

它的麻烦是碎片

我想分配十块结果现在就剩五块了

那这五块没法用了

如果说我在这里头碎片很多

实际上这时候

它的存储效率会比较差的

再有一个问题

这是我们在前面

内存分配里不太遇到的

或者说不是很重要的问题

就是文件长度的变化

我减少长度这事还好说

增加长度如果说分配的正好是这一块

你给它增加

那后面块已经被其它文件占用了

那这时候怎么办

因为我们是持久数据保存

那这个保存完之后

这数据长度会增加这是极有可能的

对于这个问题呢我们不能忽视

那怎么办在这里说到

我可以后面预留几块

还是说我分配的时候再把它整个搬

所以从这个角度来讲呢

这个长度发生变化特别是增加

对于它来说是一个比较棘手的事

这是第一种做法

接下来我们讨论第二种做法链式分配

链式分配呢是指说

我用一个数据块的链表来表示

在文件头里头有指向第一块的指针

然后第一块有指向第二块的指针

这时候呢顺序走下去

同时呢在头里头呢

再加上一个指向最后一块的指针

这样一来我们就可以表示清楚

一个文件所占用的数据块

第一块是在哪都占用哪些块

它的这些块的顺序是什么样子

这种做法它有什么样的特征呢

优点是这时候说我在这里头

增加删除占用的数据块

这都会比较方便

由于任何一个数据块我都可以

插到这里头来所以它没有外碎片

但是它有什么问题

它没有办法很方便地实现随机访问

我想找第一块最后一块

那这是你是直接从文件控制块里头

就可以找到的

但是我想找中间这一块怎么办

我只能找到第一块然后顺序往后找

我才能找到后面这一块

由于我是单向的链表

我想找倒数第二块

我只能从正着数的第一块一直找过去

从这个角度来讲呢

它的访问特征呢是比较差的

再有一条呢是它的可靠性

我们在这里存到磁盘上

数据放一段时间之后

或者说多次读写之后

里头数据可能会出错的

如果说我在这里头

指向下一块这个指针出了错

那么从这个指针往后的数据你就丢了

所以从这个角度来讲呢

它的可靠性是比较差的

这是第二种做法链式分配

第三种做法呢是索引分配

也就说为每一个文件

创建一个索引数据块

里头来存都有哪些数据块我存了数据

这时候这是这个索引数据块里的内容

是指向所有数据块的指针的列表

然后在你文件头里头

有一个指向索引数据块的指针

那么这样的话

从文件头就知道这个索引块在哪

然后在索引块里呢

我能知道每一块的位置

和它们之间的顺序

从这个角度来说

这种做法好像不错

这是它的图示

我在文件头里指向索引块

索引块里呢

有每一块的序号和它们的顺序

这时候说它的好处有什么

创建增加缩小都比较容易

然后也没有碎片

你想直接访问哪一块呢

我读到这一块索引块也就行了

所以这样一来它也可以支持直接访问

那它有什么缺点

这时候说如果我的文件很小

它一块就能存得下

你还分配一个索引块

那么这时候我又得要两块

这时候呢它的存储开销是很大的

这是文件比较小的时候

如果文件比较大呢大到什么程度

大到我索引块里存的这些序号

它也用一块存不下了

那这时候呢

我这地方就得再加索引块

如果说你在你这里头

不支持加多个索引块的话

那么这时候

对大文件的表示呢也会有麻烦

所以这是我们这几种办法呢

我们看下来

它都各自有各自的优点和缺点

那在实际用的时候呢

我们基本上会把这几种呢

组合到一起来用

那这时候对于大个的索引文件呢

我们又可以在这里呢

再往下组合新的方式

链式索引块

也就是各个索引块之间它怎么来组织

总体上来说它是索引分配方法

指向这里的块

然后这地方是索引块

索引块之间呢我用一个链式

或者索引块之间呢再做一个索引

这就变成了多级索引块

这是对大文件的表示方法

我们下面呢

来看一个实际的索引分配方法

看它怎么做的

怎么来把我们前面说到的

各种算法的优点集中到一起

把缺点都去掉

这就是我们这里的UFS的多级索引分配

UFS是unix file system

unix文件系统

它的做法是什么呢

在这个文件控制块里头

我前面10个是直接索引

你直接这10块的位置都标在这里头

如果说你存的数据比较少

只有10块以内

我就索引直接到文件对应的数据块

如果说大于10块

那这时候呢我第11个指针呢

写的是一个一级间接索引

那在这儿呢它指向一个索引块

这个索引块里头呢

再指向实际的数据块

这是一个间接索引

这时候我在间接索引块里

能放多少个序号呢假定说能放N个

根据你每一个序号所占用的空间不同

和你块的大小呢这个地方是不一样的

有了一级索引

那这时候我只需要11个指针在前面

如果说你仍然加一个一级索引

和前面十块加在一起还不够用怎么办呢

不是我在这里再给你加一个一级索引

它是加一个二级索引

这是索引块的索引这是二级索引

那么只要你大到一定程度之后

我就不再采用一级索引了

我采用二级索引

那二级索引如果仍然不够用怎么办呢

它会再加一级三级索引

相当于这是索引块

然后这是一级索引

然后这是二级索引

那这时候我们看到后面这一块的话

你要想访问到实际的数据块

它前面是有大量要查询的

这是我们多级索引它所面临的麻烦

但是把这几个搁到一个实际系统里头

我们就看到

它表示文件的大小比较小的时候

它的效率呢是直接索引

文件比较大的时候呢

它也能表示

当然这个效率它是会有一定下降的

我们看到在这里头呢

这就把前面讲的几种办法呢

很好地组合到一起

从而呢变成一个实际的索引分配方案

这是我们用一个实际的例子来说情况

说10个然后在这里呢

文件控制块里呢只有13个指针

那下面我们看一下它所带来的效果

这时候对于文件大小的限制

我由于有三级索引

那我可以表示很大的文件

具体有多大

我们会在练习里来进行计算

然后说我对于动态分配

我增加缩小都比较容易

那这是索引分配方案的好处

然后我对付小文件呢

它的开销也比较小

因为我直接在控制块里头

填这个数据块的序号

而对于大文件来说呢

我使用间接索引

所以这样它也能表示大文件

只是说它的查询速度呢会有所下降

到这个地方呢

我们就把文件分配的几种方法呢

有了一个大致的介绍

也说明了它们各自的

适用场景和优缺点

操作系统课程列表：

第零讲在线教学环境准备

-0.1 Piazza讨论区

--piazza访问和使用

--html

-0.2 在线实验平台

-0.2在线实验平台

第一讲操作系统概述

-1.1 课程概述

--视频

-第一讲操作系统概述--练习

-1.2 教学安排

--视频

-1.3 什么是操作系统

--Video

-1.4 为什么学习操作系统，如何学习操作系统

--Video

-1.5 操作系统实例

--视频

-1.6 操作系统的演变

--视频

-1.7 操作系统结构

--视频

第二讲实验零操作系统实验环境准备

-2.1 前言和国内外现状

-2.2 OS实验目标

-2.3 8个OS实验概述

-2.4 实验环境搭建

-2.5 x86-32硬件介绍

-2.6 ucore部分编程技巧

-2.7 演示实验操作过程

--Q6

--Q7

--Q10

第三讲启动、中断、异常和系统调用

-3.1 BIOS

--3.1 BIOS

-3.2 系统启动流程

--3.2 系统启动流程

-3.3 中断、异常和系统调用比较

--3.3 中断、异常和系统调用比较

-第三讲启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较

-3.4 系统调用

--3.4 系统调用

-第三讲启动、中断、异常和系统调用--3.4 系统调用

-3.5 系统调用示例

--3.5 系统调用示例

-3.6 ucore+系统调用代码

--3.6 ucore+系统调用代码

第四讲实验一 bootloader启动ucore os

-4.1 启动顺序

-4.2 C函数调用的实现

-4.3 GCC内联汇编

-4.4 x86中断处理过程

-4.5 练习一

-4.6 练习二

-4.7 练习三

-4.8 练习四练习五

-4.9 练习六

第五讲物理内存管理: 连续内存分配

-5.1 计算机体系结构和内存层次

-5.2 地址空间和地址生成

-5.3 连续内存分配

-5.4 碎片整理

-5.5 伙伴系统

-第五讲物理内存管理: 连续内存分配--5.6 练习

第六讲物理内存管理: 非连续内存分配

-6.1 非连续内存分配的需求背景

-6.2 段式存储管理

-6.3 页式存储管理

-6.4 页表概述

-6.5 快表和多级页表

-6.6 反置页表

-6.7 段页式存储管理

-第六讲物理内存管理: 非连续内存分配--6.8 练习

第七讲实验二物理内存管理

-7.1 了解x86保护模式中的特权级

--7.1 了解x86保护模式中的特权级

-第七讲实验二物理内存管理--7.1 了解x86保护模式中的特权级

-7.2 了解特权级切换过程

--7.2 了解特权级切换过程

-第七讲实验二物理内存管理--7.2 了解特权级切换过程

-7.3 了解段/页表

--7.3 了解段/页表

-第七讲实验二物理内存管理--7.3 了解段/页表

-7.4 了解UCORE建立段/页表

--7.4 了解ucore建立段/页表

-第七讲实验二物理内存管理--7.4 了解UCORE建立段/页表

-7.5 演示lab2实验环节

--7.5 演示lab2实验环节

第八讲虚拟存储概念

-8.1 虚拟存储的需求背景

-8.2 覆盖和交换

-8.3 局部性原理

-8.4 虚拟存储概念

-8.5 虚拟页式存储

-8.6 缺页异常

第九讲页面置换算法

-9.1 页面置换算法的概念

--9.1 页面置换算法的概念

-9.2 最优算法、先进先出算法和最近最久未使用算法

--9.2 最优算法、先进先出算法和最近最久未使用算法

-第九讲页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法

-9.3 时钟置换算法和最不常用算法

--9.3 时钟置换算法和最不常用算法

-第九讲页面置换算法--9.3 时钟置换算法和最不常用算法

-9.4 Belady现象和局部置换算法比较

--9.4 Belady现象和局部置换算法比较

-第九讲页面置换算法--9.4 Belady现象和局部置换算法比较

-9.5 工作集置换算法

--9.5 工作集置换算法

-第九讲页面置换算法--9.5 工作集置换算法

-9.6 缺页率置换算法

--9.6 缺页率置换算法

-第九讲页面置换算法--9.6 缺页率置换算法

-9.7 抖动和负载控制

--9.7 抖动和负载控制

第十讲实验三虚拟内存管理

-10.1 实验目标：虚存管理

--10.1 实验目标：虚存管理

-第十讲实验三虚拟内存管理--10.1 实验目标：虚存管理

-10.2 回顾历史和了解当下

-- 10.2 回顾历史和了解当下

-第十讲实验三虚拟内存管理--10.2 回顾历史和了解当下

-10.3 处理流程、关键数据结构和功能

--10.3 处理流程、关键数据结构和功能

-第十讲实验三虚拟内存管理--10.3 处理流程、关键数据结构和功能

-10.4 页访问异常

--10.4 页访问异常

-第十讲实验三虚拟内存管理--10.4 页访问异常

-10.5 页换入换出机制

--10.5 页换入换出机制

-第十讲实验三虚拟内存管理--10.5 页换入换出机制

第十一讲进程和线程

-11.1 进程的概念

--11.1 进程的概念

-第十一讲进程和线程--11.1 进程的概念

-11.2 进程控制块

--11.2 进程控制块

-第十一讲进程和线程--11.2 进程控制块

-11.3 进程状态

--11.3 进程状态

-第十一讲进程和线程--11.3 进程状态

-11.4 三状态进程模型

--11.4 三状态进程模型

-11.5 挂起进程模型

--11.5 挂起进程模型

-第十一讲进程和线程--11.5 挂起进程模型

-11.6 线程的概念

--11.6 线程的概念

-第十一讲进程和线程--11.6 线程的概念

-11.7 用户线程

--11.7 用户线程

-第十一讲进程和线程--11.7 用户线程

-11.8 内核线程

--11.8 内核线程

-第十一讲进程和线程--11.8 内核线程

第十二讲进程控制

-12.1 进程切换

--12.1 进程切换

-第十二讲进程控制--12.1 进程切换

-12.2 进程创建

--12.2 进程创建

-第十二讲进程控制--12.2 进程创建

-12.3 进程加载

--12.3 进程加载

-第十二讲进程控制--12.3 进程加载

-12.4 进程等待与退出

--12.4 进程等待与退出

-第十二讲进程控制--12.4 进程等待与退出

第十三讲实验四内核线程管理

-13.1 总体介绍

-13.2 关键数据结构

-13.3 执行流程

-13.4 实际操作

第十四讲实验五用户进程管理

-14.1 总体介绍

--14.1 总体介绍

-14.2 进程的内存布局

--14.2 进程的内存布局

-14.3 执行ELF格式的二进制代码-do_execve的实现

--14.3 执行ELF格式的二进制代码-do_execve的实现

-14.4 执行ELF格式的二进制代码-load_icode的实现

--14.4 执行ELF格式的二进制代码-load_icode的实现

-14.5 进程复制

--14.5 进程复制

-14.6 内存管理的copy-on-write机制

--14.6 内存管理的copy-on-write机制

第十五讲处理机调度

-15.1 处理机调度概念

--15.1 处理机调度概念

-第十五讲处理机调度--15.1 处理机调度概念

-15.2 调度准则

--15.2 调度准则

-15.3 先来先服务、短进程优先和最高响应比优先调度算法

--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-第十五讲处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法

-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架

-第十五讲处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc

-15.5 实时调度和多处理器调度

--15.5 实时调度和多处理器调度

-第十五讲处理机调度--15.5 实时调度和多处理器调度

-15.6 优先级反置

--15.6 优先级反置

-第十五讲处理机调度--15.6 优先级反置

第十六讲实验六调度器

-16.1 总体介绍和调度过程

-16.2 调度算法支撑框架

-16.3 时间片轮转调度算法

-16.4 Stride调度算法

第十七讲同步互斥

-17.1 背景

--17.1 背景

-17.2 现实生活中的同步问题

--17.2 现实生活中的同步问题

-第十七讲同步互斥--17.2 现实生活中的同步问题

-17.3 临界区和禁用硬件中断同步方法

--17.3 临界区和禁用硬件中断同步方法

-第十七讲同步互斥--17.3 临界区和禁用硬件中断同步方法

-17.4 基于软件的同步方法

--17.4 基于软件的同步方法

-第十七讲同步互斥--17.4 基于软件的同步方法

-17.5 高级抽象的同步方法

--17.5 高级抽象的同步方法

-第十七讲同步互斥--17.5 高级抽象的同步方法

第十八讲信号量与管程

-18.1 信号量

--18.1 信号量

-第十八讲信号量与管程--18.1 信号量

-18.2 信号量使用

--18.2 信号量使用

-第十八讲信号量与管程--18.2 信号量使用

-18.3 管程

--18.3 管程

-第十八讲信号量与管程--18.3 管程

-18.4 哲学家就餐问题

--18.4 哲学家就餐问题

-18.5 读者-写者问题

--18.5 读者-写者问题

第十九讲实验七同步互斥

-19.1 总体介绍

--19.1 总体介绍

-19.2 底层支撑

--19.2 底层支撑

-第十九讲实验七同步互斥--19.2 底层支撑

-19.3 信号量设计实现

--19.3 信号量设计实现

-第十九讲实验七同步互斥--19.3 信号量设计实现

-19.4 管程和条件变量设计实现

--19.4 管程和条件变量设计实现

-第十九讲实验七同步互斥--19.4 管程和条件变量设计实现

-19.5 哲学家就餐问题

--19.5 哲学家就餐问题

第二十讲死锁和进程通信

-20.1 死锁概念

--20.1 死锁概念

-第二十讲死锁和进程通信--20.1 死锁概念

-20.2 死锁处理方法

--20.2 死锁处理方法

-第二十讲死锁和进程通信--20.2 死锁处理方法

-20.3 银行家算法

--20.3 银行家算法

-第二十讲死锁和进程通信--20.3 银行家算法

-20.4 死锁检测

--20.4 死锁检测

-第二十讲死锁和进程通信--20.4 死锁检测

-20.5 进程通信概念

--20.5 进程通信概念

-第二十讲死锁和进程通信--20.5 进程通信概念

-20.6 信号和管道

--20.6 信号和管道

-第二十讲死锁和进程通信--20.6 信号和管道

-20.7 消息队列和共享内存

--20.7 消息队列和共享内存

-第二十讲死锁和进程通信--20.7 消息队列和共享内存

第二十一讲文件系统

-21.1 文件系统和文件

--21.1 文件系统和文件

-第二十一讲文件系统--21.1 文件系统和文件

-21.2 文件描述符

--21.2 文件描述符

-第二十一讲文件系统--21.2 文件描述符

-21.3 目录、文件别名和文件系统种类

--21.3 目录、文件别名和文件系统种类

-第二十一讲文件系统--21.3 目录、文件别名和文件系统种类

-21.4 虚拟文件系统

--21.4 虚拟文件系统

-第二十一讲文件系统--21.4 虚拟文件系统

-21.5 文件缓存和打开文件

--21.5 文件缓存和打开文件

-第二十一讲文件系统--21.5 文件缓存和打开文件

-21.6 文件分配

--21.6 文件分配

-第二十一讲文件系统--21.6 文件分配

-21.7 空闲空间管理和冗余磁盘阵列RAID

--21.7 空闲空间管理和冗余磁盘阵列RAID

-第二十一讲文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID

第二十二讲实验八文件系统

-22.1 总体介绍

--22.1 总体介绍

-第二十二讲实验八文件系统--22.1 总体介绍

-22.2 ucore 文件系统架构

--22.2 ucore 文件系统架构

-第二十二讲实验八文件系统--22.2 ucore 文件系统架构

-22.3 Simple File System分析

--22.3 Simple File System分析

-第二十二讲实验八文件系统--22.3 Simple File System分析

-22.4 Virtual File System分析

--22.4 Virtual File System分析

-第二十二讲实验八文件系统--22.4 Virtual File System分

-22.5 I/O设备接口分析

--22.5 I/O设备接口分析

-第二十二讲实验八文件系统--22.5 I/O设备接口分析

-22.6 执行流程分析

--22.6 执行流程分析

第二十三讲 I/O子系统

-23.1 I/O特点

--视频

-第二十三讲 I/O子系统--23.1 I/O特点

-23.2 I/O结构

--816C80A0F5E3B8809C33DC5901307461

-第二十三讲 I/O子系统--23.2 I/O结构

-23.3 I/O数据传输

--C58221E14388B9DB9C33DC5901307461

-第二十三讲 I/O子系统--23.3 I/O数据传输

-23.4 磁盘调度

--567A3F1FCBFB3F4C9C33DC5901307461

-第二十三讲 I/O子系统--23.4 磁盘调度

-23.5 磁盘缓存

--C327536B80D25CE79C33DC5901307461

-第二十三讲 I/O子系统--23.5 磁盘缓存

html

-html

--html

21.6 文件分配在线视频