09 第七章 文件系统.pptx

第1页：第七章文件系统

OS实现系统资源管理

硬件资源、软件资源;

软件资源

程序、数据;

文件管理

软件资源以文件形式存于外存空间,软件资源管理通常称为文件管理;

文件管理由文件系统来完成;

文件系统在设备管理之上。

第2页：1.文件的概念文件

1.文件的概念文件:具有符号名而且在逻辑上具有完整意义的信息项的有序序列。7.1文件与文件系统7.1.1文件n-1……k……10编号:信息项……信息项……信息项信息项文件名:符号名,文件创建时确定,访问时用;信息项:构成文件的基本单位;等长或不等长;有顺序关系;读/写指针:信息项的读/写位置;读/写指针

第3页：7.1.1 文件

• 2.文件分类
  • 系统文件,用户文件;
  • 临时文件,永久文件;
  • 只读文件,只写文件,读/写文件;
  • 磁盘文件,磁带文件,磁鼓文件;
  • 目录文件,普通文件;
  • 程序文件,数据文件;
  • 程序文件源文件,目标文件,可执行文件,头文件,库文件。

第4页：7.1.1 文件（续）

UNIX文件分类

普通文件

内容可以是程序、数据、图象等,保存在磁盘块中;

目录文件

文件描述信息(文件名,文件号)序列,保存在磁盘块中;

特殊文件

将各种设备作为文件处理。

界面统一,使用文件与使用设备命令相同,申请设备open,释放close,读read,写write;

利用文件保护功能可以保护设备。

第5页：7.1.2文件系统文件系统

• 7.1.2文件系统文件系统:文件与管理信息资源的程序集合称为文件系统。
  • 为用户提供按名存取文件的手段;
  • 文件的组织形式;
  • 外存空间的管理;
  • 处于设备管理上层。

第6页：7.2 文件的访问方式

• 7.2.1顺序访问:磁带
  • 从文件起始位置开始顺序访问;
  • 从文件中间某处开始顺序访问。7.2.2随机访问:磁盘、光盘
  • 按信息项编号随机访问;
  • 按关键字(key)随机访问。

第7页：7.3 文件的组织

文件的组织

又称文件结构;

逻辑组织

外部组织形式,用户看到的文件组织形式。

物理组织

内部组织形式,物理存储设备上的组织形式。

OS完成逻辑组织形式到物理组织形式的转换。

第8页：7.3.1 文件的逻辑组织

• 1.流式文件
  • 非结构形式的字节序列(UNIX, Windows, etc);
  • 构成文件的基本单位是字节。
  • 用户可以对非结构的流式文件按自定义的结构来处理。n-1……k……10编号:字节……字节……字节字节读/写指针

第9页：7.3.1 文件的逻辑组织（续）

• 2.记录式文件:记录的序列
  • 等长记录(优点:处理方便,速度快;缺点:空间浪费);
  • 不等长记录(优点:省空间;缺点:处理不便,速度慢);
  • 流式文件是记录式文件的特例。n-1……k……10编号:记录……记录……记录记录读/写指针

第10页：7.3.2 文件的物理组织

物理组织

逻辑组织到磁盘块的映射。文件:记录(字节)序列⇒磁盘:块(block)序列

考虑因素:

①记录格式

等长或不等长,流式不必考虑;

②空间开销

除保存文件内容之外的存储开销;

③访问速度

顺序/随机访问速度;

④长度变化

动态增长/减少。

组织形式

顺序结构、链接结构、索引结构、散列结构、倒排结构。

第11页：7.3.2 文件的物理组织（续）

7.3.2文件的物理组织⒈顺序结构又称连续结构。一个文件占有若干连续的磁盘块。FCB……首块号28块数4…………块28块29块30块31……磁盘空间优点:速度快,节省空间;缺点:长度变化困难。

第12页：⒉链接结构

⒉链接结构：又称串联结构,一文件可存于不连续块中,块间以指针相连。7.3.2文件的物理组织优点:长度变化容易。缺点:随机访问速度慢。FCB……首块号28块数4…………块28……块30……块45块46……磁盘空间

第13页：⒉链接结构（续）

7.3.2文件的物理组织⒊索引结构一文件可存于不连续块中,块号记在索引块中。优点:随机访问速度快;长度变化容易。缺点:额外需要索引块,存储开销大;FCB……索引块号28块数4…………块43……块87……块97块98……磁盘空间430871972983……4索引块28

第14页：⒉链接结构（续3）

• 7.3.2文件的物理组织⒋散列结构适用于定长记录和按键随机查找的访问方式;通常用于构造文件目录,一个记录内容就是一个目录项。
• 计算地址:hash(key)=addr(在磁盘或文件中的存放位置)

第15页：7.3.2 文件的物理组织

• 问题:给定key1≠key2 ,有hash(key1) = addr1 ,hash(key2) = addr2 ,若addr1=addr2 ,则发生conflict。
• Conflict resolution:
  • 顺序探查法:如发生冲突,则在冲突位置开始顺序探查第一个空闲的存储位置。
  • 记录中增加两个域:冲突计数;记录位置的空闲标志。

第16页：7.3.2 文件的物理组织（续）

7.3.2文件的物理组织⑴保存记录:保存记录的键值为key .冲突计数空闲标志地址……………21addr:键值key记录内容……1键值key1记录内容Hash(key)=addr文件空间保存记录key计算hash(key)⇒addr, adaddr对应的记录位置冲突记数加1位置ad空闲?ad指向下一个记录位置ad记录位置标记为占用记录key内容⇒ad记录位置保存记录key结束FT

第17页：7.3.2 文件的物理组织（续3）

7.3.2文件的物理组织⑵查找记录:查找键值为key的记录。查找记录keyhash(key)⇒ad,addr取ad对应记录的冲突记数→countad记录键值=keycount--count=0找到结束未找到结束ad记录空闲hash(ad.key)=addrcount=0ad指向下一个记录位置FFFFFTTTTT

第18页：7.3.2 文件的物理组织（续4）

7.3.2文件的物理组织⑶删除记录:删除键值为key的记录。删除记录key调用“查找记录key”找到key?记录key不存在返回addr=hash(key)ad.空闲标志=0addr.冲突计数减1删除记录key返回FT特点:按关键字检索速度快。用途:常用于目录检索。注意:Hash空间可循环使用,满时保存失败。

第19页：7.3.2 文件的物理组织（续5）

• 5.倒排结构
  • 键:记录中的域称为键;
  • 主键:记录中能唯一区分文件中所有记录的键称为主键;其它键称为次键。
  • 倒排结构:以键值和记录地址构成的索引结构称为倒排结构。
  • 主索引:键值为主键的索引称为主索引;
  • 次索引:键值为次键的索引称为次索引。

第20页：7.3.2 文件的物理组织表

7-1各种文件物理结构的主要特性按键随机访问速度按号随机访问速度顺序访问速度外存开销内存开销长度变化特性物理结构变长定长变长定长变长定长慢慢慢快快快小小难顺序结构慢慢慢慢快快小小易链接结构慢慢慢快快快大大易索引结构─快────小小易散列结构快快────大大易倒排结构

第21页：7.3.2 文件的物理组织

UNIX文件物理结构P389~390)……i_addr[0]……i_addr[9]i_addr[10]i_addr[11]i_addr[12]……i_node…………………………文件最大长度=10+256+2562+2563(块)多级索引+链接结构信息块索引块

第22页：7.3.2 文件的物理组织（续）

例：在UNIX系统中，设磁盘物理块大小为1KB，每个索引块可以保存256个索引项。假设某UNIX文件大小为1028KB。⑴请画出该UNIX文件的物理结构；⑵计算访问以下逻辑块号（逻辑块号从0开始）时，需要多少次I/O传输：①265；②266；③1025。解：⑴零级索引和一级索引能保存的块数＝10＋256＝266块；剩下的1028－266＝762块，可用二级索引。762＝256×2+250，即占用二级索引的3个索引项。该文件的UNIX物理结构如图所示。⑵根据文件的物理结构，访问逻辑块号①265需要2次I/O；②266需要3次I/O；③1025需要3次I/O

第23页：7.3.2 文件的物理组织（续3）

i_addr[0]……i_addr[9]i_addr[10]i_addr[11]i_addr[12]……i_nodenull。。。逻辑块0逻辑块9逻辑块10逻辑块265。。。逻辑块266逻辑块521逻辑块522逻辑块777逻辑块778逻辑块1027。。。。。。null250块256块256块256块给定的UNIX文件的物理结构

第24页：7.4 文件目录

• 7.4.1文件控制块与目录项1.文件控制块(FCB)
  • 文件存在的标志,其中保存系统管理文件需要的全部信息;
  • 每个文件一个FCB,保存在外存;
  • 建立文件时创建,删除文件时撤销。
• 2.目录项
  • 目录文件中的一项,内容为FCB;
  • 通常目录项名为文件名。

第25页：7.4.2 文件目录与目录文件

• 1.文件目录
  • 用于检索文件的目录;
  • 目录项构成的有序序列;
  • 给定一个文件名,通过查找文件目录找到相应的目录项(FCB)。
• 2.目录文件
  • 内容为目录项的文件,长度固定的记录式文件;
  • 实现文件目录的管理。

第26页：7.4.2 文件目录与目录文件（续）

• 文件控制块FCB文件名文件号用户名文件地址文件长度记录大小文件类型文件属性共享说明文件逻辑结构文件物理结构建立日期保存日期最后修改日期和时间最后访问日期和时间口令其它目录项1(FCB1)目录项2(FCB2)……目录项n(FCBn)目录文件
• 目录,文件图示:文件目录

第27页：7.4.3 单级目录与多级目录

1.单级目录(Single-Level Directory)整个系统只有一个目录,所有文件均登记在该目录中。FCBn……FCBi……FCB2FCB1file1file2fileifilen…………目录文件普通文件单级目录结构

第28页：7.4.3 单级目录与多级目录（续）

缺点:⑴Naming problem;⑵Grouping problem⑶Protection problem.单级目录例:

第29页：7.4.3 单级目录与多级目录（续3）

• 2.二级目录(Two-Level Directory)
  • 系统目录(公共目录),用户目录(私用目录);
  • 为每个用户单独设置目录。FCBj……FCB1……用户目录普通文件USERk……USERi……USER1FCBm……FCB1FCBn……FCB1……………………系统目录二级目录结构

第30页：7.4.3 单级目录与多级目录（续4）

二级目录例:特点:⑴Path name;⑵Can have the samefile name for different user;⑶Efficient searching;⑷No grouping capability.

第31页：7.4.3 单级目录与多级目录（续5）

• 3.多级目录(Multi-Level Directory)
  • 目录为树形结构;
  • 叶结点是一般文件或目录文件;
  • 非叶结节点是目录文件;
  • 根结点称作根目录文件。优点:
  • 便于文件分类;
  • 查找速度快(由于每个文件目录下文件少);
  • 可以实现文件连接(Link)。

第32页：27.4.3 单级目录与多级目录

多级目录例:rootUnixbinusrlibdevetcVIusersWangLiSd1d2f1flibclibCClpConsolebinYaccPasswordf

第33页：7.4.4 文件目录的改进

• 将FCB分为次部和主部两部分。
  • 次部:(文件名,文件号)
  • 长度固定(UNIX 16 bytes);
  • 保存在目录文件中。
  • 主部:(其它,连接记数)
  • 记录长度固定(UNIX 32 bytes);
  • 保存在外存固定区域,打开时读入内存;
  • 给定文件号,可计算主部位置。改进的好处
  • 可以提高查找速度(顺序查找)
  • 可以实现文件连接(link)

第34页：7.4.4 文件目录的改进（续）

改进的文件目录图示:FCB主部文件号FCB1主部1FCB2主部2……FCBn主部n目录项1(FCB1次部)目录项2(FCB2次部)……目录项n(FCBn次部)文件目录目录文件

第35页：17.4.4 文件目录的改进

• 顺序查找n个记录，找到一个记录的平均查找记录的次数=(1+2+……n)/n=(n+1)/2
• 设未分次部和主部的FCB构成的文件目录占n个磁盘块，则顺序查找文件目录，找到一个文件目录的平均访问磁盘块的次数=(n+1)/2
• 设次部构成的文件目录占m个磁盘块，则顺序查找文件目录，找到一个文件的平均访盘次数＝(m+1)/2+

第36页：7.4.5 根目录与当前目录

• 1.根目录树状结构(多级目录)文件系统中,根结点对应的目录称为根目录;根目录保存在外存空间固定位置。
• 2.当前目录目前正在使用的工作目录称为当前目录。

第37页：7.4.6 文件目录的查找

• 查找路径
  • 由根目录开始查找;
  • 由当前目录开始查找。
• 查找算法
  • 顺序查找(UNIX);
  • hash查找;
  • 对分查找(要求文件名排序)。

第38页：7.5文件的共享文件共享

• 7.5文件的共享文件共享:多个进程共用系统中的同一个文件;操作系统和文件使用者共同完成文件共享控制。7.5.1文件共享的目的⑴节省存储空间:cc, vi, yacc的共享;⑵进程相互通信7.5.2文件共享的模式
• 1.异步使用同一文件:任意时刻只能有一个进程使用一个文件;
• 2.同时使用同一文件:多个进程可以同时使用同一个文件(R/W规则)。

第39页：7.5.3 文件共享的实现

1.公共目录:系统设若干所有用户都能访问的公共目录,共享文件登记在公共目录中;

2.连接

通过连接使一个文件具有多个名字,不同用户通过不同名字访问同一个文件;

3.共享说明

创建文件时规定共享用户及其使用权限。7.5文件的共享

第40页：7.5.3 文件共享的实现（续）

7.5文件的共享文件共享实现链接例:rootusruserswanglid1d2f1f2, 15f1, 15i_number=15link(“/usr/users/wang/d2/f1”,“/usr/users/li/f2”);unlink(“/usr/users/wang/d2/f1”);

第41页：7.6 文件的保护、保密与安全

保护

防止用户对文件进行非授权的访问。

保密

防止文件内容泄露。

安全

防止文件被破坏。

自然因素

人为因素

第42页：7.6.1 文件的保护

• (Protection)
• File owner/creator should be able to control:
  • what can be done;
  • by whom .
• Types of access
  • Read
  • Write
  • Execute
  • Append
  • Delete
  • List

第43页：7.6.1 文件的保护（续）

(Protection)⒈存取控制矩阵:am×n, m个用户, n个文件。fn…fj…f1a1n…a1j…a11u1………………ain…aij…ai1ui………………amn…amj…am1umdmaewraij:特点:权限规定细,过于繁琐,占较多存储空间。

第44页：7.6.1 文件的保护（续3）

• (Protection)
• 用户分成若干类;
• 同类用户对同一文件访问权限相同;
• 不同类用户对同一文件访问权限不同;
• UNIX用户分类4类:文件主,同组用户,其它用户,特权用户。⒉访问权限说明EWREWREWR其他用户权限同组用户权限文件主权限特权用户权限访问权限说明

第45页：7.6.1 文件的保护（续4）

• (Protection)⒊分级目录
• 多级目录系统中,规定不同用户对同一子目录的访问权限;
• 如果用户不能访问某一目录,即该用户不能访问该目录下的任何文件。

第46页：7.6.2文件的保密⒈口令

• 7.6.2文件的保密⒈口令
• 创建文件时用户规定一个口令,系统将其记在FCB中;
• 访问文件要求给出口令,并与FCB中口令比较。特点:简单;保密性不强(eg.对系统操作员不保密)。⒉密码
• 保存时加密(key);
• 读取时解密(key).特点:对文件内容加密,速度慢;效果好。

第47页：@B1@文件加/解密简单实现

• 文件加/解密简单实现
  • 保存时,用一个key启动一个随机数发生器,产生一个随机数序列,将其依次“添加”到文件的各个字中。
  • 读取时,用同一个key启动同一个随机数发生器,产生相同随机数序列,将其依次由文件的各个字中”减去”。
• 线性同余法产生伪随机数：void random(int *key){ *key = ((*key)*C1+C2) % C3; }7.6.2文件的保密C1, C2是质数常量, C3是随机数范围(0～C3-1);key通常叫随机源,也叫种子,它决定产生的随机数序列的随机性。

第48页：7.6.3 文件系统的安全

Backup

定期将磁盘上文件备份到磁带上;

发生故障时由磁带恢复(limited recovery)。

实现方法转储

文件由磁盘备份到磁带的过程;

1.完全转储

定期将磁盘上文件全部备份到磁带上;

2.增量转储

开始时做一次完全转储;之后,每次只对与上次不同的数据进行备份。

3.差分转储

开始时做一次完全转储;之后,每次只对与第一次不同的数据进行备份。

磁盘整理

利用转储和恢复可以对磁盘进行整理。(使文件物理块连续,空闲盘块连续)

第49页：7.7 文件系统的实现

7.7.1内存所需的表目

⒈系统打开文件表(系统一个):存于OS空间修改标志共享计数文件号FCB主部……………………

①文件号

用于确定FCB主部在外存中的位置;

②共享计数

记录使用该文件的进程个数,为0时表示该表项为空表项;

③修改标志

若FCB被修改过,则关闭文件时需要把内存的FCB写回外存。

第50页：随着读写调整

• 7.7.1内存所需的表目⒉用户打开文件表<系统打开文件表>入口(地址)读写指针打开方式文件描述符0…………………n-1
• 文件描述符就是用户打开文件表项位置(非负整数),打开文件时返回给进程;
• 用户打开文件表位置存在进程PCB中;
• 系统可以单设<用户打开文件表>空间,也可以放在进程的PCB中。读写指针应该是文件的逻辑地址，初值应为

第51页：7.7.1 内存所需的表目

⒊用户打开文件表/系统打开文件表的联系<系统打开文件表>入口读写指针打开方式文件描述符…………………………………k………………………………l…………………用户打开文件表进程Pi……文件描述符k……进程Pj……文件描述符l……PCB其它共享计数…………2………系统打开文件表

第52页：7.7.2 外存空间的管理

• 表项:(首空闲块号,空闲块数);
• 表尾标记:空闲块数为0;
• 分配方式:最先适应,下次适应、最佳适应,最坏适应等;
• 存放位置:平时外存,使用时读入内存系统区。
• ⒈空闲块表:适于连续物理组织结构的文件系统。
• ⒉空闲块链
• 所有空闲块连成一个链;
• 申请/释放以块为单位,都对链头操作;
• 节省空间,但速度慢(申请/释放都需要1次I/O);

第53页：7.7.2外存空间的管理⒊位示图

7.7.2外存空间的管理⒊位示图:字位映像图

位示图的1位表示外存一块的状态;

申请

找到位示图中为0的字位,将该字位改为1 ,返回该字位对应的块号;

释放

将位示图中释放块号对应的字位置0;

存放位置

平时外存,使用时读入内存,若有修改写回外存。

第54页：7.7.2 外存空间的管理

• ⒋成组链接(Unix):空闲块链与空闲块表的结合。
• 多个(最多100个)空闲块为1组,组之间相互链接;
• 最前面的组缓冲到内存;该组称作超级块。
• 超级块结构(P393～394):struct filesys {…………int s_nfree;//组中空闲块个数(100);int s_free[100];//s_free[0]指向下一组;//其它为本组中空闲块号;…………} super_block;

第55页：2 外存空间的管理上述结构表示

空闲块的成组链接图示:……100s_nfrees_free[0]n11s_free[1]…………n199s_free[99]……100n21……n299……100n31……n399……K∧nj1……njK-1超级块空闲块组表空闲块的成组链接例:P394～图13.14空闲块组表空闲块组表7.7.

第56页：7.7.2 外存空间的管理

初始超级块如下：……1s_nfrees_free[0]nulls_free[1]…………nulls_free[99]……100n21……n299……100n31……n399……K∧nj1……njK-1超级块空闲块组表……空闲块组表空闲块组表……100n11……n199空闲块组表

第57页：7.7.2 外存空间的管理（续）

39s_nfree50s_free[0]40s_free[1]…12s_free[38]…100150149…51#50100350349…251#250100250249…151#15087NULL449…351#350#351#449#40#12#149#51#249#151#349#251内存超级块

第58页：7.7.2 外存空间的管理（续3）

成组链接的空闲块管理:超级块已读入内存。

申请

⑴s_nfree>1,取块号s_free[--s_nfree]分配;⑵s_nfree=1,将s_free[0]所指连接块读入内存(作为超级块),分配块号s_free[0]。

释放

⑴s_nfree<100, s_free[s_nfree++]=释放块号;⑵s_nfree=100,将s_nfree和s_free拷贝到释放块中,将该块号记录到s_free[0],写回外存, s_nfree=1。

第59页：7.8文件系统的界面⒈创建文件

• 7.8文件系统的界面⒈创建文件: creat(path_name, fcb_args)
• 参数说明
  • path_name:文件路径名;
  • fcb_args: FCB参数。
• 执行步骤:
• ①为此文件分配一个FCB主部,初始化;
• ②将文件名和文件号作为FCB次部填到末级目录中;
• ③以写方式打开。例如:creat(“/usr/li/d1/f1”, mode)

第60页：7.8 文件系统的界面

• ⒉打开文件: fd=open ( path_name, mode )
• 参数说明:path_name:文件路径名; mode:打开方式.
• 执行步骤
• ①根据文件路径名查目录找到FCB次部;
• ②合法性检查(根据打开方式、共享说明、用户身份);
• ③根据文件号查系统打开文件表看该文件是否已被打开,如是则共享计数加1;否则找一个空闲的系统打开文件表项,并将外存中FCB主部等信息填入此表项,共享计数置为1;
• ④在用户打开文件表中找一空表项,填写打开方式和读写指针(初值为0),并指向系统打开文件表的对应表项。
• 返回信息:fd:文件描述符(用户打开文件表入口),一个非负整数。

第61页：7.8 文件系统的界面（续）

• ⒊关闭文件: close ( fd )
• 参数说明:fd:文件描述符。
• 执行步骤:
• ①由fd查用户打开文件表,找到系统打开文件表入口;
• ②系统打开文件表中共享计数减1 ;如减1后的值为0且修改标志为1 ,则将此FCB由内存写回外存FCB主部;
• ③将fd所对应的用户打开文件表项置为空闲。

第62页：7.8 文件系统的界面（续3）

• ⒋指针定位: seek ( fd, offset )
• 参数说明:
  • fd:文件描述符;
  • offset:新的指针位置。
• 执行步骤:
• ①由fd查用户打开文件表,找到对应的入口;
• ②检查参数合法性;
• ③将用户打开文件表中文件读写指针位置设定为offset,后续读写命令由该指针处存取文件内容。

第63页：7.8 文件系统的界面（续4）

• ⒌读文件: read ( fd , nrd , buf )
• 参数说明:
  • fd:文件描述符;
  • nrd:读入记录个数;
  • buf:内存起始位置。
• 执行步骤:
• ①由fd查用户打开文件表,找到对应的系统打开文件表入口;
• ②合法性检查(用户打开文件表中所记录的打开方式、存取方式);
• ③根据读写指针和文件物理结构，计算读写指针对应的磁盘物理地址addr＝(物理块号,偏移);
• ④把从addr开始的nrd个记录读入内存中由buf起始的区域；
• ⑤调整文件读写指针为：当前读指针＋sizeof(记录结构)×nrd。

第64页：7.8 文件系统的界面（续5）

• ⒍写文件: write ( fd, nwt , buf )
• 参数说明:fd:文件描述符; nwt :写出记录个数; buf:内存起始位置。
• 执行步骤:
• ①由fd查用户打开文件表,找到对应的入口;
• ②合法性检查(用户打开文件表中所记录的打开方式、存取方式);
• ③根据读写指针及文件物理结构计算当前读写指针对应的磁盘物理地址(物理块号I, offset);
• ④如果：块号I=文件最末块号&&offset＋sizeof(记录结构)×nwt≥磁盘块大小;则需要：申请磁盘块;修改文件物理结构表；
• ⑤将内存中由buf起始的nwt个记录写到地址(物理块号, offset)起始的磁盘区域;
• ⑥调整读写指针：当前读写指针＋sizeof(记录结构)×nwt。

第65页：7.8 文件系统的界面（续6）

• ⒎建立连接: link (old_name , new_name )
• 参数说明:
  • old_name:已存在的文件路径名;
  • new_name:欲连接的文件路径名。
• 执行步骤:
• ①查目录找到文件old_name的FCB次部,由此得到文件号;
• ②查目录找到文件new_name的末级目录;
• ③将文件号与new_name中末级名字合起来构成一个新的目录项,将其填入new_name的末级目录文件中;
• ④将FCB主部中的连接计数加
• 1.例如:link(“/usr/Li/f1”, “/usr/Zhang/d2/f2”)

第66页：7.8 文件系统的界面（续7）

• ⒏断开连接: unlink ( path_name )
• 参数说明:path_name:文件路径名.
• 执行步骤:
• ①查目录找到文件path_name的FCB主部;
• ②将连接计数值减1;
• ③如减1后的值为0,则归还该文件所占用的全部存储块,该文件将被撤销;
• ④将FCB次部由上级目录中清除.例如:unlink(“/usr/Zhang/d2/f2”)

第67页：UNIX文件系统的实现

• UNIX文件系统的实现
• 内存所需表目(UNIX)
  • 用户打开文件表
• u_ofile(每个进程一个)
• file(整个系统一个)
  • 系统打开文件表
• Inode(整个系统一个)
• 外存空间的管理
  • 空闲块表
  • 字位映像图(Linux)
  • 成组连接(UNIX approach)

第68页：UNIX内存表目

UNIX内存表目：1. u_ofile (每进程一个)struct user {…int u_ofile[NOFILE];…}#define NOFILE 152. file (系统一个)struct file {char f_flag;

第69页：UNIX内存表目（续）

UNIX系统的FCBstruct inode

第70页：UNIX文件系统的实现

UNIX文件系统的实现struct inode (内存：P395～396 ){int i_flag;

第71页：表间联系

表间联系：u_ofile→file(n) (1)file→inode(n) (1)

第72页：表间联系（续）

read(4,…)read(4,…)…write(6,…)用户空间u_ofileu_ofilefilei_node磁盘空间系统空间...数据块……...i_list表间联系

第73页：UNIX外存空间管理

UNIX外存空间管理：0 1 2…k k+1…n-1导引块超级块inode区域每块16个inode,从0起依次编号文件存储区域(普通文件,目录文件)超级块(super block)：(1)记载文件卷上k+1块到n-1块中所有空闲块，(2) inode区中100个空闲inode. (缓存)文件安装(mount)后超级块读入内存。注：占用区域已经记载在各个文件的inode中。

第74页：UNIX外存空间管理（续）

Struct filesys {int s_isize;

第75页：空闲块管理

空闲块管理：100个空闲块为一组，组之间相互链接。…s_nfree=88s_free[0]s_free[1]...s_free[87]...Super block...............特点：速度快，空间省。

第76页：空闲块管理（续）

空闲块管理：申请时：(1) s_nfree>1,取s_free[--s_nfree];(2) s_nfree=1,将s_free[0]所指连接块读入内存,分配s_free[0].释放时:(1) s_nfree<100, s_free[n_free++]=释放块号;(2) s_nfree=100,将s_nfree和s_free拷贝到释放的块中,将该块号记录到s_free[0],写回外存.

第77页：空闲inode管理

空闲inode管理：s_inode最多可以记载100个空闲inode(编号)申请时：(1) s_ninode>0,取s_inode[--s_ninode];(2) s_ninode=0,由磁盘inode区顺取100个空闲I节点(i_nlink=0)将其编号填入s_inode表中，修改s_ninode，然后分配。释放时：(1) s_ninode<100, s_inode[s_ninode++]=i_number (释放的);(2) s_ninode=100,丢弃。

第78页：文件系统界面(UNIX系统调用)

• 文件系统界面(UNIX系统调用)
• creat
• open
• close
• seek
• read
• write
• link
• unlink
• pipe
• mknode
• smount
• sumount
• chmod
• chowner
• state
• fstate
• chdir

第79页：文件系统界面(UNIX系统调用)（续）

• fd=creat(pathname,mode)pathname:路径名；mode:共享说明；
• 1.在外存分配一个主部inode[i_number],初始化(i_size=0, i_mode=mode,i_nlink=1,i_uid=u_uid, i_gid=u_gid ),;
• 2.填写目录项(name,i_number)；
• 3.以写方式打开,填写系统打开文件表i_node[num]和用户打开文件表<u_ofile, file>、file[n2]表项：.f_inode=num; .f_flag=‘w’; .f_offset=0; f_count=1; u_ofile[fd]=n2；
• 4.返回文件描述符fd。例子：creat(“d1/d2/f1”, mode)假定分配i_number=15, (f1,15)→d2中(??????,-1)文件系统界面(UNIX系统调用)

第80页：文件系统界面(UNIX系统调用)（续3）

• fd=open(pathname,mode)pathname:路径名；mode:打开方式；返回值：fd:文件描述符(u_ofile表的入口, u_ofile的下标)
• 1.查目录找inode(移入内存i_count=1,如已在内存i_count++);
• 2.权限检查(mode打开方式, i_mode共享说明, i_uid, i_gid文件主（组）, u_uid, u_gid用户身份);
• 3.在file表中分配一个file[n]表项，指向该内存i_node;初始化f_count=1; f_offset=0; f_flag=mode;
• 4.取一空闲u_ofile[fd]表目，u_ofile[fd]=n指向file表中对应表目;
• 5.返回文件描述符fd(在u_ofile表中的入口)。文件系统界面(UNIX系统调用)

第81页：close(fd)fd

• close(fd)fd:文件描述符；
• 1.由fd查u_ofile找到对应入口；
• 2.由u_ofile[fd]找到file表对应入口；3. f_count--,如>0,则转6；(同一家族的其它进程还没结束)
• 4.由f_inode找到对应inode；4. i_count--,如为0，i_flag标志有修改，写回外存inode区；6.u_ofile[fd]=-1(空闲标志）文件系统界面(UNIX系统调用)

第82页：close(fd)fd（续）

• seek(fd, whence, offset)fd:文件描述符；whence:相对位置(0,1,2,3,4,5)=(头,尾,当前位置)offset:整数，移动量；
• 1.由u_ofile[fd]找到file表入口；
• 2.由f_inode找到内存inode;
• 3.检查参数合法性(i_size0, i_size1, f_offset, offset, whence);
• 4.按参数要求调整f_offset指针。文件系统界面(UNIX系统调用)Whence：0,1,2为字节，3,4,5为块

第83页：close(fd)fd（续3）

• nrd=read(fd,buf,count)fd:文件描述符；buf:进程空间接收区地址；count:读字节数；
• 1.由u_ofile[fd]，找到file表对应入口；
• 2.检查访问权限(f_flag, READ);
• 3.由f_inode找到内存inode入口；
• 4.由f_offset, count和i_addr计算访问磁盘块号(可能多个块) ; (bmap函数)
• 5.启动IO设备读取盘块到系统缓冲区中(如buffer无,切换进程);
• 6.缓冲区信息复制到进程空间(iomove)；
• 7.返回实际传输字节数nrd；
• 8.调整读写指针f_offset：f_offset+=nrd.文件系统界面(UNIX系统调用)

第84页：close(fd)fd（续4）

• nwt=write(fd,buf,count)fd:文件描述符；buf:进程空间发送地址；count:写字节数；
• 1.由u_ofile[fd]，找到file表对应入口；
• 2.检查访问权限(f_flag, WRITE);
• 3.由f_inode找到内存inode入口；
• 4.由f_offset, count和i_addr计算磁盘地址块号(可能分盘块）；
• 5.申请系统缓冲区，将buf起始count数据送到缓冲区(可多次)；
• 6.缓冲区链到设备IO链上,如设备空闲启动设备；
• 7.修改inode中文件长度i_size;(覆盖时可能不修改)
• 8.返回实际传输字节数nwt;
• 9.调整读写指针f_offset：f_offset+=nwt.文件系统界面(UNIX系统调用)

第85页：close(fd)fd（续5）

• pipe(fd)int fd[2];
• 1.分配一个inode(i_count=2);
• 2.分配2个file表目(f_flag分别为pipeR和pipeW，读/写指针f_offset为0）
• 3.分配2个u_ofile表目,分别指向2个file表目；
• 4.返回2个文件描述符fd[0],fd[1],分别为u_ofile中的2个入口。文件系统界面(UNIX系统调用)

第86页：Pipe文件同步与互斥

• Pipe文件同步与互斥
• pipe读写同步
• 写满：写者等待，读出后唤醒
• 读空：读者等待，写入后唤醒
• 读写关闭
• 所有读者关闭：写时返回错误信号
• 所有写者关闭：读者立即返回
• 读写互斥
• i_flag|ILOCK

第87页：Pipe文件同步与互斥（续）

i_addr[ ]…i_count (2)…f_flag (Rpipe)f_offset=0f_inodepf_count =1f_flag (W pipe)f_offset=0f_inodepf_count =1………内存inode表内存file表fd[0]fd[1]u_ofile表………进程执行pipe(fd)之后

第88页：Pipe文件同步与互斥（续3）

i_addr[ ]…i_count (2)…f_flag (R pipe)f_offset=0f_inodepf_count =2f_flag (W pipe)f_offset=0f_inodepf_count =2………内存inode表内存file表fd[0]fd[1]u_ofile表………fork创建子进程1（读者）之后fd[0]fd[1]………父进程:子进程1:

第89页：Pipe文件同步与互斥（续4）

i_addr[ ]…i_count (2)…f_flag (R pipe)f_offset=0f_inodepf_count =3f_flag (W pipe)f_offset=0f_inodepf_count =3………内存inode表内存file表fd[0]fd[1]u_ofile表………fork创建子进程2（写者）之后fd[0]fd[1]………父进程:子进程1:………子进程2:fd[0]fd[1]

第90页：Pipe文件同步与互斥（续5）

i_addr[ ]…i_count (2)…f_flag (R pipe)f_offsetf_inodepf_count =2f_flag (W pipe)f_offsetf_inodepf_count =2)………内存inode表内存file表fd[0]fd[1]u_ofile表………父进程close(fd[0]),close(fd[1])fd[0]fd[1]………父进程:子进程1:………子进程2:fd[0]fd[1]

第91页：Pipe文件同步与互斥（续6）

i_addr[ ]…i_count (2)…f_flag (R pipe)f_offset=0f_inodepf_count =2f_flag (W pipe)f_offset=0f_inodepf_count =1………内存inode表内存file表fd[0]fd[1]u_ofile表………子进程1(读者) : close(fd[1])fd[0]fd[1]………父进程:子进程1:………子进程2:fd[0]fd[1]

第92页：Pipe文件同步与互斥（续7）

i_addr[ ]…i_count (2)…f_flag (R pipe)f_offset=0f_inodepf_count =1f_flag (W pipe)f_offset=0f_inodepf_count =1………内存inode表内存file表fd[0]fd[1]u_ofile表………子进程2(写者) : close(fd[0])fd[0]fd[1]………父进程:子进程1:………子进程2:fd[0]fd[1]

第93页：Pipe文件同步与互斥（续8）

i_addr[ ]…i_count (2)…f_flag (R pipe)f_offset=count0f_inodepf_count =1f_flag (W pipe)f_offset=count1f_inodepf_count =1………内存inode表内存file表u_ofile表子进程2(写) : write(fd[1],buf1,count1)子进程1(读) : read(fd[0],buf0,count0)父进程:子进程1:子进程2:fd[0]fd[1]………………fd[0]fd[1]fd[0]fd[1]………write(fd[1],…)read(fd[0],…)盘块(有缓冲)

第94页：Pipe文件同步与互斥（续9）

i_addr[ ]…i_count (1)…f_flag (R pipe)f_offsetf_inodepf_count =1f_flag (W pipe)f_offsetf_inodepf_count =0………内存inode表内存file表u_ofile表子进程2(写完) :close(fd[1])父进程:子进程1:子进程2:fd[0]fd[1]………………fd[0]fd[1]fd[0]fd[1]………close(fd[1])read(fd[0],…)盘块(有缓冲)

第95页：Pipe文件同步与互斥（续10）

i_addr[ ]…i_count (0)…f_flag (R pipe)f_offsetf_inodepf_count (0)f_flag (W pipe)f_offsetf_inodepf_count (0)………内存inode表内存file表u_ofile表子进程1(读完) :close(fd[0])父进程:子进程1:子进程2:fd[0]fd[1]………………fd[0]fd[1]fd[0]fd[1]………close(fd[1])close(fd0])

第96页：Pipe文件同步与互斥（续11）

• Pipe文件同步与互斥
• pipe读写同步
• 写满：写者等待，读出后唤醒
• 读空：读者等待，写入后唤醒
• 读写关闭
• 所有读者关闭：写时返回错误信号
• 所有写者关闭：读者立即返回
• 读写互斥
• i_flag|ILOCK

第97页：管道通讯的局限性

• 管道通讯的局限性
• 只有相关进程(同一家族进程)能通讯
• 先创建管道
• 再创建子进程,子进程继承父进程打开的文件(包括管道文件)
• 管道是没有名字的文件
• 所有进程都关闭后即被撤销

第98页：命名管道(FIFO)

• 命名管道(FIFO)
• 长久性通讯机构
• 具有文件名
• 可被打开、读写、关闭和删除
• 任何进程都能找到它
• 即使是不同祖先的进程，也可以利用命名管道进行通信。
• 读取和写入遵循FIFO原则
• 阻塞：
• 管道读:假如没有线程实行写管道操作，读线程将一直阻塞，直到有线程往里面写为止；
• 管道写:假如没有线程实行读操作，写线程将一直阻塞，直到有线程读数据为止。
• 不阻塞：
• 管道读：假如没有线程实行写管道操作，读线程将立即返回；
• 管道写：假如没有线程实行读操作，写线程将立即返回，返回不正确码-1。

第99页：命名管道(FIFO)（续）

• link(oldpathname, newpathname)oldpathname:已存在文件名；newpathname:待连接文件名；
• 1.查目录找到oldpathname(inode);
• 2.查目录找到newpathname的末级目录；
• 3.检查操作合法性；4. Inode的i_nlink++；5. (name, i_number)→newpathname的末级目录。例子：link(“d1/d2/f1”,“d1/d3/f2”)d1,d2,f1:存在；d1,d3:存在，f2:不存在，文件系统界面(UNIX系统调用)

第100页：命名管道(FIFO)（续3）

• unlink(pathname)pathname:文件路径名；
• 1.查目录找到pathname(inode);2. i_nlink--;如结果为0,释放所有磁盘块(删除文件)；
• 3.清除末级文件名在末级目录中的登记。例子：unlink(“d1/d2/f1”)假定：f1文件号i_number=15;操作后：f1的i_nlink--,d2中原(f1, 15)改为(f1,-1)文件系统界面(UNIX系统调用)

第101页：命名管道(FIFO)（续4）

• mknode(pathname, type and permissions, dev)pathname:节点名；type and permissions:节点类型和访问权限；dev:主次设备号；
• 1.如非特权用户，失败；
• 2.建立一个i_node,初始化(i_addr[0]=dev);文件系统界面(UNIX系统调用)

第102页：命名管道(FIFO)（续5）

struct mount{int m_dev;int *m_bufp;

第103页：命名管道(FIFO)（续6）

bit: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0Set uidSet gid大文件00普通01字符10目录11块型i_mode:i_flag:ILOCKIUPDIACCIMOUNTIWANTITEXT执行该文件进程的身份暂时改为文件主的身份即: u_uid = i_uid

第104页：命名管道(FIFO)（续7）

• smount(special_pathname, directory_pathname, roflag)special_pathname:特殊文件名directory_pathname:目录文件名（安装节点）roflag:只读标志
• 1.检查是否超级用户；
• 2.找到special_pathname文件的inode(用mknode建立);
• 3.合法性检查（特殊块型文件）；
• 4.找到directory_pathname节点的inode;
• 5.如非目录或引用数大于１，错返；
• 6.读入super block到buf，按filesys格式解释.7.安装节点inode的i_addr[0]=设备文件i_addr[0]; (dev)
• 8.分配一个mount表项，填写（m_dev，m_bufp，m_inodep），9安装节点inode的i_flag =| IMOUNT.文件系统界面(UNIX系统调用)

第105页：命名管道(FIFO)（续8）

例子：smount(“/dev/disk1”,“/usr/d1”,0)安装之前：disk1只能作为特殊文件(块序列文件)访问(raw IO)；安装之后：d1成为disk1文件卷的根目录。disk1的super block读入内存缓冲区中，按filesys格式解释，根目录inode读入内存inode区中；内存中inode区是所有安装文件卷共用的，因而在内存inode中有i_dev指明inode对应的卷，用于回写。

第106页：命名管道(FIFO)（续9）

• sumount(special_file_name)special_file_name:待卸下卷的特殊文件名；
• 1.查目录找到inode，取dev(i_addr[0]);
• 2.释放特殊文件的inode;
• 3.由dev查mount表(m_dev)找到对应super block;
• 4.系统缓冲区延迟写块写回；
• 5.该卷所有更新i_node写回；6. super block写回；
• 7.释放super block所占用的缓冲区；
• 8.由m_inodep找到安装节点的inode;
• 9.安装节点i_flag =& ~IMOUNT;
• 10.释放mount表项。文件系统界面(UNIX系统调用)

第107页：命名管道(FIFO)（续10）

• chdir(pathname)pathname:目录路径名；
• 1.查目录找到pathname的inode;(不在内存读入,i_count=1；已在内存i_count++)；
• 2.检查权限；3. u_cdir当前所指inode的i_count--,如为0且修改过,写回外存;
• 4.新inode入口→u_cdir文件系统界面(UNIX系统调用)

第108页：命名管道(FIFO)（续11）

• chown(pathname,owner, group)pathname:文件路径名owner:新文件主group:新文件组
• 1.查目录找到文件(inode)；
• 2.权限检查(文件主,特权用户)；
• 3.更新owner和group(i_uid, i_gid)；4. inode写回。文件系统界面(UNIX系统调用)

第109页：命名管道(FIFO)（续12）

• chmode(pathname, newmode)pathname:路径名；newmode:新权限说明；
• 1.查目录找到文件(inode)；
• 2.权限检查(文件主,特权用户)；
• 3.更新i_mode(=newmode)；4. inode回写。文件系统界面(UNIX系统调用)

第110页：命名管道(FIFO)（续13）

• state(pathname, statbuffer)pathname:文件路径名；statbuffer:状态缓冲区；
• 1.查目录找到内存inode；2. inode信息(所有者、大小、权限、属性、链接数、inode号、访问时间等)→statbuffer;fstate(fd, statbuffer)
• 1.由u_ofile[fd]找到file表；
• 2.由file表找到i_node;3. i_node信息→statbuffer;文件系统界面(UNIX系统调用)

第111页：命名管道(FIFO)（续14）

• 7.9日志结构文件系统Log Structured File System: LSFSUC Berkeley的研究人员提出的一种全新的文件系统
• CPU速度越来越快;
• 内存容量以接近指数级速度增长;
• 磁盘容量,更大更便宜;
• 磁盘速度的提高却相对较慢,成为系统效率的瓶颈:
  • 缓存的增加,使大部分读盘操作可以在缓存中得到;
  • 写操作(多数为小量写)是影响文件系统效率的关键。

第112页：7.9 日志结构文件系统造成小量写

• 在UNIX系统中创建一个文件⑴文件名写入目录中;⑵新文件inode更新;⑶目录文件inode更新;⑷写入文件内容。
• 小量写(small write)
  • 一次写修改磁盘块上的一小部分数据;
  • 假定一次写需要10ms寻道时间, 4ms旋转延迟,50µs写操作,磁盘访问效率≈3.6‰。
• 延迟写:发生故障给一致性带来威胁

第113页：7.9 日志结构文件系统造成小量写（续）

• LSFS将整个磁盘看做一个日志,周期性地追加新日志;
• 写操作并非直接反映到磁盘上,而是被暂时存到内存缓冲区中,其中包括新写的数据,也包括更新数据;
• 当积累到一定规模时,作为一个segment追加到日志的末尾。7.9日志结构文件系统……segmentk……segment1LSFS结构New segmentInodes, directories, data blockssummarysegment结构

第114页：7.9 日志结构文件系统

Inode map

Inode存储位置不能由其编号确定,系统维持一个Inode map,以实现i-number到磁盘inode的映射。

清洁线程(cleaner)

循环扫描磁盘并对segment进行压缩。⑴读入一个segment ;⑵查找inode map确定inode;⑶segment的inode和数据块是新版并仍被使用,则与内存当前segment合并作为新的segment写回磁盘,旧segment被标记为空闲;否则舍弃该segment信息。⑷转⑴。

第115页：7.10 内存映射文件

• 文件保存于外存,存取速度慢
  • 访问之前需要打开
  • 每次访问需要经过“打开文件表”
  • 读写需要经过I/O传输缓冲可以提高速度,但首次访问需要I/O
• 内存容量增加,利用率不充分进程虚拟空间大,只使用较小的一部分
• 提示：将文件映射到内存以访问内存的方式访问文件Open, map,使用, umap, close

第116页：7.10 内存映射文件（续）

0内存映射文件Memory Mapped FilePi页表Pj页表……Blocki+2BlockiBlocki+3Blocki+1……文件索引内存空间

第117页：7.11 系统举例

• 7.11.1 Linux文件系统1.VFS(Virtual File System)文件系统
  • 并不是一个实际文件系统，而是多种实际文件系统的一个统一界面；
  • 为多种文件系统(Ext2fs, FAT)提供统一接口，也为各种外部设备提供统一接口。
  • Linux的核心是扩展的快速文件管理系统Ext2fs文件系统

第118页：7.11 系统举例（续）

VFS（Virtual File System）Ext2fsC缓冲B缓冲Network协议IO设备Block设备网络设备7.11.1 Linux文件系统⒉Ext2fs文件系统

第119页：7.11 系统举例（续3）

块组…块组…块组块组引导块文件块inode位示图组描述超级块一组相邻的柱面7.11.1 Linux文件系统

第120页：Ext2fs与VFS差别

• Ext2fs与VFS差别
• 存储块管理
  • VFS采用大块(large block, up to 8K)＋碎块（fragment）
  • Ext2fs采用统一长度块（1kb,2kb,4kb)
• 空闲块管理
  • Bit map
  • 使一个文件物理块尽量连续或临近
  • 预先分配，未用完盘块在文件关闭时释放7.11.1 Linux文件系统

第121页：Ext2fs与VFS差别（续）

• 1.2 Windows Vista的NTFS
• Windows支持两种文件系统:
  • FAT:File Allocation Table
  • NTFS:New Technology File System
• NTFS特性
  • 可恢复性:文件控制信息多副本存储;更新记录事务和日志;
  • 安全性:对文件对象访问的身份认证;文件加密;
  • 数据容错:保存数据镜像,支持数据分条;
  • 提供磁盘配额管理:为每个用户分配指定容量的磁盘空间;
  • 支持大磁盘、大文件名:2TB;最大路径名分量255个字符。

第122页：7.11.2 Windows Vist…

1.2 Windows Vista的NTFS文件对象类型：文件（type：file）对象类型文件名称（file name）文件属性设备类型（device type）字节偏移（byte offset）共享模式（share mode）打开模式（open mode）文件处置（file disposition）创建文件（creat file）文件操作打开文件（open file）读文件（read file）写文件（write file）查询文件信息（query file information）设置文件信息（set file information）查询扩展属性（query extended attribute）设置扩展属性（set extended attribute）锁字节范围（lock byte range）取消输入输出（cancel I/O）刷新缓冲（flush buffer）查询目录文件（query directory file）目录变化通报（notify caller when directory changes）获取卷信息（get volume information）设置卷信息（set volume information）

第123页：7.11.2 Windows Vist

1.2 Windows Vista的NTFS日志文件服务高速缓存管理虚拟存储管理NTFS驱动程序容错驱动程序磁盘驱动程序输入输出管理器磁盘磁盘核心系统服务NTFS的组织和层次结构

第124页：7.12 文件系统效率

• Caching:keep file blocks in core memory, whenever possible
  • keep read-in block buffers associated with file blocks
  • keep write-out block buffers associated with file blocks
• read ahead
  • for sequential accesscurrent file block #15, next possible #16(read ahead)
  • implementation1.access bit for each open file, open set to 0(sequential)2.seekturn over the flag(non sequential)

第125页：7.12 文件系统的效率

• delayed write:write is postponed untilabsolutelynecessary.
  • no free buffer
  • upon file close (all user close, i_count=0)
  • system flush
• reducing disk arm motion
  • allocating contiguous disk blocks to a file
  • request to access disk are served inscanorder