操作系统(第七章)

蓝Q曦 included in 操作系统

2024-04-25 5425 words 11 minutes

Contents

文件管理

文件构成

数据项$\rightarrow$记录$\rightarrow$文件

数据项
1. 基本数据项
  1. 用于描述一个对象的属性的字符集,是数据组织中可以命名的最小逻辑数据单位,即原子数据,又称为数据元素或字段
  2. 如描述一个学生:学号、姓名、年龄、班级
2. 组合数据项
  1. 由若干个基本数据项组成,简称组项
  2. 如工资包括基本工资、工龄工资、奖金等
基本数据项除数据名外,还应有数据类型
记录
1. 记录是一组相关数据项的集合,用于描述一个对象在某方面的属性
2. 一个记录应包含哪些数据项,取决于需要描述对象的哪个方面
3. 一个对象,由于他所处的环境不同可把他作为不同的对象
4. 能惟一标识一个记录的数据项称为关键字(key)
文件
1. 文件是指由创建者所定义的、具有文件名的一组相关元素的集合
2. 可分为有结构文件和无结构文件
  1. 有结构文件由若干个相关记录组成,如上例中学生文件
  2. 无结构文件则被看成是一个字符流,如C语言源程序
3. 文件在文件系统中是一个最大的数据单位,它描述了一个对象集
  
  例如,可以将一个班的学生记录作为一个文件
4. 一个文件必须要有一个文件名,它通常是由一串ASCII码或(和)汉字构成

文件的分类

按用途分类
1. 系统文件
2. 有关操作系统及其它系统程序的信息所组成的文件。这类文件对用户不直接开放,只能通过系统调用为用户服务
3. 用户文件
4. 由用户委托操作系统保存的文件,如源程序文件,目标程序文件,以及由原始数据、计算结果等组成的文件
5. 库文件
6. 由标准子程序及常用的应用程序组成的文件。这类文件允许用户调用,但不允许用户修改
按文件中数据的形式分类
1. 源文件
2. 目标文件
3. 可执行文件
按存取控制属性分类
1. 只执行文件
2. 只读文件
3. 允许文件主及核准的用户读,但不允许写的文件
4. 读写文件允许文件主及核准的用户读、写,但禁止未核准的用户读、写的文件

文件的模型

文件操作

文件结构

逻辑(用户组成)
物理(磁盘分配)

逻辑结构(记录为单位)

有结构文件
无结构文件

有结构文件

顺序文件
索引文件
索引顺序文件

连续分配

要求：一组相邻的盘块

优点：操作简单，实现随机存取

缺点：对磁盘存储容量相对比较高，产生碎片(空间浪费)

链接分配

隐式链接

要求：下一个盘块的盘块号存储在上一个盘块中(相当于一个单链表)

缺点：只能顺序访问，不能实现随机访问
显示链接

FCB：文件的第一个盘块号

FAT：顺序表，盘块号，内存(计算容量)
1. 表项：盘块的数量
2. 每个表项大小：存放盘块号
FAT容量：
1. 表项：盘块数
2. 每个表项的字节数(8位)(二进制位数，最大盘块号)
例：有一个长度为3200的流式文件要存储在磁盘上，磁盘的每块可以存放512B,则存放该文件至少需要多少块磁盘？

3200$\div$ 512$\approx$7

至少需要7块磁盘

例：假设盘块的大小为1KB,硬盘的大小为500MB，采用显示链接分配方式时，其FAT需要占用多少存储空间？

500MB/1KB=500K个

500K个表项

最大的盘块号500K$\rightarrow$ 19bit$\stackrel{(扩展到半个字节的整数(4))}\rightarrow$ 20bit=2.5B

$\Rightarrow$ 500K$\times$ 2.5B=1250KB

大约需要1250KB空间
索引分配

要求：盘块$\rightarrow$ 索引块$\rightarrow$ 索引表

每个表项存储一个盘块号

例：若每个盘块大小为1KB,每个盘块号占4B则表项为

1KB$\div$ 4B=256个

文件大小为：256$\times$ 1KB=256KB (单极索引)

文件大小为：256$\times$256 $\times$ 1KB (两级索引)

文件大小为：256$\times$256 $\times$256 $\times$ 1KB (三极索引)
混合索引分配(13个地址)

假设每个盘块大小为4KB，每个盘块占4B$\Rightarrow$ 4KB/4B=1K个

0~9：直接寻址：10个盘块：4KB$\times$10=40KB

10：一次寻址：一级索引1K个盘块：4KB$\times$ 10=40KB

11：二次寻址：二级索引：1M个盘块：4KB$\times$ 1MB=4GB

12：三次寻址：三级索引：1G个盘块：4KB$\times$ 1GB=4TB

$\Rightarrow$ 文件总长度：40KB+4MB+4GB+4TB

例：存放在某个磁盘上的文件系统，采用混合索引方式，其中FCB共有13个地址项，第0-9个地址项为直接地址，第10个地址项为一次间址，第11个地址项为二次间址，第12个地址项为三次间址。如果每个盘块的大小为510字节，若盘块号需要用3个字节来描述：

该文件系统允许文件的最大长度是多少？

510/3=170

(10+170+170*170+170*170*170)*510
将文件的字节偏移量5000，15000，150000转化为物理块号和块内偏移量。

5000/510=9…..410

9:为物理块号，410:为偏移量

15000/510=29……210 29:为物理块号，210:为偏移量

150000/510=294……60

294:为物理块号，60:为偏移量
假设某个文件的FCB已在内存，但其他信息均在外存为了访问该文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次访问磁盘？

由于FCB已在内存，为访问文件中某位置的内容，最少需1次访问磁盘（即可通过直接地址直接读文件块）；最多需4次访问磁盘（第1次为读3次间址，第2次为读2次间址，第3次为读1次间址，第4次为读文件盘块）

目录管理

目录管理的任务是为每个文件建立目录项,并对众多的目录加以组织,以实现方便的按名存取,实现文件的共享,提供快速的目录查询手段,提高文件的检索速度。

文件控制块和索引结点

文件控制块(FCB)
1. 是用于描述和控制文件的数据结构
2. 文件管理程序可借助FCB中的信息对文件施以各种操作
3. 文件控制块的有序集合称为文件目录,即一个文件控制块就是一个文件目录项
4. 通常,一个文件目录本身也被看作是一个文件,称为目录文件
文件控制块中的信息
1. 基本信息类
  1. 文件名
  2. 文件物理位置
  3. 文件逻辑结构
  4. 文件的物理结构
2. 文件控制信息类
  1. 文件拥有者权限
  2. 核准用户权限
  3. 一般用户权限
3. 使用信息类
  1. 文件建立日期
  2. 文件修改日期

索引结点
1. 索引结点的引入
  1. 文件目录通常放在磁盘上,当文件很多时,占用大量磁盘空间
  2. 检索文件过程中,只需使用文件名,而不用其他信息
2. 将文件描述信息单独形成一个数据结构,称为索引结点,也称为i结点
3. 在文件目录中的每个目录项,仅包含文件名和指向索引结点的指针
4. 引入索引结点后,使文件的目录项更小,占用磁盘空间少,检索速度加快
5. 磁盘索引结点
  1. 文件主标识符
    
    拥有该文件的个人或小组的标识符
  2. 文件类型
    
    正规文件、目录文件或特别文件
  3. 文件存取权限各类用户对该文件的存取权限
  4. 文件物理地址
    
    13个地址项,给出文件所在盘块编号
  5. 文件长度
    
    以字节为单位的文件长度
  6. 文件连接计数
    
    指向该文件的指针的个数
  7. 文件存取时间
    
    指出最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间
6. 内存索引结点:文件打开时调入内存的,增加了:
  1. 索引结点编号。用于标识内存索引结点
  2. 状态。指示i结点是否上锁或被修改
  3. 访问计数。每当有一进程要访问此i结点时,将该访问计数加1,访问完再减1。
  4. 文件所属文件系统的逻辑设备号。
  5. 链接指针。设置有分别指向空闲链表和散列队列的指针

目录结构

单级目录结构

整个系统只建立一张目录表,每个文件占一个目录项
1. 单级目录优点
  1. 易于实现,管理简单
  2. 能实现按名存取
2. 单级目录缺点
  1. 查找速度慢(顺序查找,N/2)
  2. 不允许重名(在多道程序设计下,很难保证)
  3. 不便于实现文件共享(所有用户必须用同一个名字共享一个文件)
3. 单级目录只实现了目录管理的第一项功能 ,即“按名存取”,只能适用于单用户环境
两级目录

为每个用户建立一个单独的用户文件目录UFD(User File Directory),由用户所有文件的FCB组成在系统中建立主文件目录MFD(Master File Directory),每个用户目录文件在主文件目录中占一个目录项
多级目录结构
1. 目录结构
  
  多级目录结构又称为树形目录结构 主目录称为根目录,数据文件称为树叶,其他目录作为树的结点
  
  为提高文件系统的灵活性,允许一个目录文件中的目录项既作为目录文件的FCB,又是数据文件的FCB
1. 路径名
  1. 在树形目录结构中,从根目录到任何数据文件,都只有一条惟一的通路。在该路径上从树的根(即主目录)开始,把全部目录文件名与数据文件名,依次地用“/”连接起来,即构成该数据文件的路径名(path name)
  2. 系统中的每一个文件都有惟一的路径名
  3. 例如,在图6-18中用户B为访问文件J(15),应使用其路径名/B/F/J来访问。
2. 当前目录
  1. 为每个进程设置一个“当前目录”,又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行
  2. 把从当前目录开始直到数据文件为止所构成的路径名,称为相对路径名(relative path name)
  3. 把从树根开始的路径名称为绝对路径名(absolute path name)
增加和删除目录

删除目录的两种处理方法:
1. 不删除非空目录
  1. 当目录(文件)不空时,不能将其删除,而为了删除一个非空目录,必须先删除目录中的所有文件,使之先成为空目录,后再予以删除。
  2. 在MS-DOS中就是采用这种删除方式。
2. 可删除非空目录
  1. 当要删除一目录时,如果在该目录中还包含有文件,则目录中的所有文件和子目录也同时被删除
  2. 在Windows中就是采用这种删除方式。
特点
1. 层次清楚
2. 解决了用户文件重名问题
3. 搜索速度快

目录查询技术

线性检索法(顺序检索法)
Hash方法
1. 系统利用用户提供的文件名并将它变换为文件目录的索引值,再利用该索引值到目录中去查找,提高检索速度
一种处理此“冲突”的有效规则是:
1. 在利用Hash法索引查找目录时,如果目录表中相应的目录项是空的,则表示系统中并无指定文件
2. 如果目录项中的文件名与指定文件名相匹配, 则表示该目录项正是所要寻找的文件所对应的目录项,故而可从中找到该文件所在的物理地址
3. 如果在目录表的相应目录项中的文件名与指定文件名并不匹配,则表示发生了“冲突”,此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质),形成新的索引值,再返回到第一步重新开始查找

位示图法

位示图
1. 用二进制的一位来表示磁盘中一个盘块的使用情况
2. “0"表示盘块空闲,“1"表示盘块已分配
盘块的分配

找“0”(先行后列)
1. i行号
2. j列号
生成：盘块号：b=n(i-1)+j(n是每行二进制的位数)
盘块的回收

已知盘块号b生成

i=(b-1)DIV n+1

j=(b-1)MOD n+1

将“1”变成”0“

例题

选择题

在下列文件的外存分配方式中,不利于文件长度动态增长的文件物理结构是(A )。

A.连续分配 B.链接分配C.索引分配D.以上都不对
文件系统中若文件的外存分配方式采用连续分配,则文件控制块FCB中有关文件的物理位置的信息应包括( B )。

(Ⅰ)起始块号 (Ⅱ)文件长度 (Ⅲ)索引表地址 A.全部 B.(Ⅰ)和(Ⅱ) C.(Ⅰ)和(Ⅲ) D.(Ⅱ)和(Ⅲ)
操作系统为保证未经文件拥有者授权,任何其他用户不能使用该文件所提供的解决方法是( A)。

A.文件保护 B.文件保密 C.文件转储 D.文件共享

文件系统最基本的目标是((1) A ),它主要是通过( (2) B )功能实现的,文件系统所追求的最重要目标是( (1) D)。

  (1)A.按名存取		B.文件共享	
       C.文件保护		D.提高对文件的存取速度
 (2)	A.存储空间管理	B.目录管理
C.文件读写管理	D.文件安全管理

按逻辑结构可把文件分为( E )和( F )两类。

A.读、写文件 B.只读文件 C.索引文件 D.链式文件 E.记录式文件 F.流式文件

下面关于顺序文件和链接文件的论述中正确的是( C )。

A.顺序文件只能于建立在顺序存储设备上,而不能于建立在磁盘上。
B.在显式链接文件中是在每个盘块中设置一链接指针,用于将文件的所有盘块链接起来。
C.顺序文件采用连续分配方式,而链接文件和索引文件则都可采用离散分配方式。
D.在MS-DOS中采用的是隐式链接文件结构

下面关于索引文件的论述中正确的是( B )。

A.在索引文件中,索引表的每个表项中必须含有相应记录的关键字和存放该记录的物理地址。
B.对顺序文件进行检索时,首先从FCB中读出文件的第一个盘块号,而对索引文件进行检索时,应先从FCB中读出文件索引表始址。
C.对于一个具有三级索引表的文件,存取一个记录必须要访问三次磁盘。
D.在文件较大时,进行顺序存取比随机存取快

在存取文件时,如果利用给定的记录值对链表或索引表进行检索,以找到指定记录的物理地址,则上述文件分别称为 ( B )或( C ),如果根据给定的记录键值直接获得指定记录的物理地址,则把这种文件称为( D )。

A.顺序文件 B.链接文件 C.索引文件 D.直接文件

在文件管理中,位示图主要是用于( B )。

A.磁盘的驱动调动		B.磁盘空间的分配和回收
C.文件目录的查找		D.页面置换

在随机存取方式中，用户以___D__为单位对文件进行存取和检索。

A.字符串 B.字节 C.数据项 D.逻辑记录
文件物理结构一般有 a,d,e 。

a. 连续结构 b. 流式结构 c. 记录式结构 d. 链接结构 e. 索引结构
两级目录结构由 c 和 d 组成。

a. 根目录 b. 子目录 c. 主文件目录 d. 用户文件目录 e. 当前目录

计算题

文件分配表FAT是管理磁盘空间的一种数据结构，用在以链接方式存储文件的系统中记录磁盘分配和跟踪空白磁盘块。其结构如图所示
1. 对于540M硬盘，其FAT要占多少存储空间
  
  磁盘共有盘块540M/1k=540k个，需要20位二进制表示，
  
  即FAT的每个表项应占2.5字节，
  
  2.5B*540k=1350KB
2. 对于1.2G硬盘，其FAT要占多少空间
  
  1.2G/1k=1.2M个盘块，需要21位二进制数表示，
  
  即每个FAT表项占3字节
  
  3B*1.2M=3.6MB
有一计算机系统利用途中所示的位示图来管理空闲盘块，盘块的大小为1KB，现要为某文件分配两个盘块，试具体说明盘块的分配过程。（假设可以离散开）
1. 顺序检索位示图，
  
  从中找到第一个值为0的二进制位，行号$i_1$=3，列号$j_1$=3；
  
  第二个值为0的二进制位，行号$i_2$=4，列号$j_2$=7。
2. 空闲盘号为：
  
  $b_1$ = n(i1 - 1) + j1 = 16 × 2 + 3 = 35；
  
  $b_2$ = n(i2 - 1) + j2 = 16 × 3 + 7 = 55
3. 修改位示图
  
  令map[$i_1, j_1$] = map[3, 3] = 1;
  
  map[$i_2, j_2$] = map[4, 7] = 1。