操作系统：07（左老师）第七章_文件系统

1、第七章第七章 文件系统文件系统n7.1 文件与文件系统文件与文件系统n文件文件n具有符号名而且在逻辑上具有完整意义的信息项的序列。具有符号名而且在逻辑上具有完整意义的信息项的序列。n文件系统文件系统n文件与管理文件的程序集合。文件与管理文件的程序集合。 信息项信息项 信息项信息项 信息项信息项 信息项信息项读读(写写)指针指针 UNIX文件分类文件分类n普通文件普通文件n内容可以是程序、数据、图象、内容可以是程序、数据、图象、MP3等，保存在磁等，保存在磁盘块中盘块中n目录文件目录文件n(文件名，文件号文件名，文件号)序列，保存在磁盘块中序列，保存在磁盘块中n特殊文件特殊文件n设备设备n设备作

2、为文件管理的好处设备作为文件管理的好处n界面统一，使用文件与使用设备命令相同，申请设备界面统一，使用文件与使用设备命令相同，申请设备open, 释放释放close, 读读read, 写写writen利用文件保护功能可以保护设备利用文件保护功能可以保护设备7.2 文件的访问方式文件的访问方式n顺序访问顺序访问n从文件起始位置开始顺序访问从文件起始位置开始顺序访问n从文件中间某处开始顺序访问从文件中间某处开始顺序访问n随机访问随机访问n按记录编号随机访问按记录编号随机访问n按关键字按关键字(key)随机访问随机访问7.3 文件的组织文件的组织n逻辑组织逻辑组织n用户看到的文件组织形式用户看到的文件

3、组织形式n记录式文件：记录的序列记录式文件：记录的序列n等长记录（优点：处理方便，速度快；缺点：空间浪费）等长记录（优点：处理方便，速度快；缺点：空间浪费）n不等长记录（优点：省空间；缺点：处理不便，速度慢）不等长记录（优点：省空间；缺点：处理不便，速度慢）n流式文件：字节的序列流式文件：字节的序列(UNIX, Windows, etc)n物理组织物理组织n逻辑组织到磁盘块的映射逻辑组织到磁盘块的映射n文件：记录文件：记录(字节字节)序列序列n磁盘：块磁盘：块(block)序列序列变换关系变换关系7.3.2 文件的物理组织文件的物理组织n考虑因素考虑因素n记录格式记录格式n等长或不等长等长或不

4、等长, 流式不必考虑流式不必考虑n空间开销空间开销n除保存文件内容之外的存储开销除保存文件内容之外的存储开销n访问速度访问速度n随机访问速度随机访问速度n长度变化长度变化n动态增长动态增长顺序结构：顺序结构： 一个文件占有若干连续的磁盘块。一个文件占有若干连续的磁盘块。优点：速度快，节省空间优点：速度快，节省空间缺点：长度变化困难缺点：长度变化困难块块18块块19块块20块块21块块22.磁盘空间磁盘空间首块首块=18块数块数=5.FCB链接结构：链接结构： 一文件可存于不连续块中，块间以指针相连。一文件可存于不连续块中，块间以指针相连。优点：节省空间，长度变化容易。优点：节省空间，长度变化容

5、易。缺点：随机访问速度慢。缺点：随机访问速度慢。块块18.块块80.块块92.磁盘空间磁盘空间首块首块=18块数块数=3. FCB索引结构：索引结构： 一文件可存于不连续块中，块号记在索引块中。一文件可存于不连续块中，块号记在索引块中。优点：速度快，长度变化容易。优点：速度快，长度变化容易。缺点：索引块占空间。缺点：索引块占空间。磁盘空间磁盘空间索引块索引块=29块数块数=4. FCB块块18块块19.块块26.块块30.索引块索引块29Hash结构：结构： 计算地址：计算地址：hash(key)=addr (在磁盘或文件中的存放位置在磁盘或文件中的存放位置)问题：给定问题：给定key1 ke

6、y2 hash(key1)=addr1; hash(key2)=addr2; addr1=addr2 (conflict)Conflict resolution: 顺序探查法：顺序探查法：如发生冲突，则在冲突位置开始顺序探查第一个空闲的存储如发生冲突，则在冲突位置开始顺序探查第一个空闲的存储位置。位置。.文件空间文件空间空闲标志空闲标志冲突记数冲突记数记录内容记录内容空闲标志空闲标志冲突记数冲突记数Hash(key)=addr起始位置起始位置计算计算addr=hash(key)对应冲突记数加对应冲突记数加1本记录空闲本记录空闲顺取下一个顺取下一个标记为占用标记为占用填记录内容填记录内容保存记录

7、：保存记录：TF记录内容记录内容查找记录：查找记录：计算计算addr=hash(key)取取addr对应记录的冲突记数对应记录的冲突记数countcount=0无此记录无此记录本记录空闲本记录空闲顺取下一记录顺取下一记录key相等相等找到找到 hash(key)相等相等count:=count-1count=0无此记录无此记录顺取下一记录顺取下一记录TFFTTFTFTF删除记录：删除记录：调用查找过程调用查找过程(key)找到找到错误返回错误返回置空闲标志置空闲标志(找到记录找到记录)冲突记数冲突记数-1对应对应hash(key)特点：特点：按关键字检索速度非按关键字检索速度非常快。常快。用途

8、：用途：常用于目录检索。常用于目录检索。注意：注意：文件可循环使用，满文件可循环使用，满时保存失败。时保存失败。FTUNIX文件物理结构文件物理结构(索引索引+链接链接)i_addr0.i_addr9i_addr10i_addr11i_addr12.inode.最大最大=10+256+2562+2563(块块)7.4 文件目录文件目录n文件控制块与目录项文件控制块与目录项n文件控制块文件控制块(FCB)n文件存在的标志，其中保存系统管理文件需要的文件存在的标志，其中保存系统管理文件需要的全部信息全部信息n目录项目录项n目录文件中的一项，内容为目录文件中的一项，内容为FCBn文件目录与目录文件文

9、件目录与目录文件n文件目录文件目录n用于检索文件的目录用于检索文件的目录n目录文件目录文件n内容为目录项的文件内容为目录项的文件文件控制块文件控制块FCB（File Control Block）文件名文件名文件号文件号文件主文件主文件类型文件类型文件属性文件属性共享说明共享说明文件长度文件长度文件地址文件地址建立日期建立日期最后修改日期最后修改日期最后访问日期最后访问日期口令口令其它其它FCB创建：建立文件时创建：建立文件时FCB撤消：删除文件时撤消：删除文件时单级目录单级目录( (Single-Level Directory) )A single directory for all user

10、s.缺点缺点:1. Naming problem2. Grouping problem3. Protection problem两级目录两级目录( (Two-Level Directory) )Separate directory for each user.特点特点: 1. Path name2. Can have the same file name for different user3. Efficient searching4. No grouping capabilityrootbinusrlibdevetcunixlpccviusersLiWangd1d2f1consolepas

11、swdbinyaccsf2多级目录多级目录( (Multi-Level Directory as in UNIX)clibflib文件目录的查找文件目录的查找n查找路径查找路径n由根目录开始查找由根目录开始查找n由当前目录开始查找由当前目录开始查找n查找算法查找算法n顺序查找（顺序查找（UNIX）nhash查找查找（Solo）n对分查找（要求文件名排序）对分查找（要求文件名排序）文件目录的改进文件目录的改进nFCBn次部：次部：(文件名文件名, 文件号文件号) n(UNIX 16 bytes)n保存在目录文件中保存在目录文件中n主部：主部：(其它其它, 链接记数链接记数)n(UNIX 32 b

12、ytes)n保存在外存保存在外存inode区域区域, 打开时读入内存打开时读入内存.n改进的好处改进的好处n可以提高查找速度可以提高查找速度(顺序查找顺序查找)n可以实现文件链接可以实现文件链接(link)UNIX文件卷文件卷(volume)组织形式：组织形式： 0 1 2 k k+1 n-1导导引引块块超超级级块块 inode区域区域每块每块16个个inode, 从从0起依次编号起依次编号 文件存储区域文件存储区域(普通文件普通文件,目录文件目录文件)7.5 文件的共享文件的共享n共享目的共享目的n节省存储空间节省存储空间n(cc,vi,yacc)n进程相互通讯进程相互通讯nUNIX pip

13、e()n文件共享模式文件共享模式n不同时使用不同时使用n根据共享说明根据共享说明n同时使用同时使用n根据共享说明和根据共享说明和(relaxed)R/W规则规则文件的共享文件的共享n文件共享的实现文件共享的实现n公共目录公共目录n共享说明共享说明n连接连接d1userswanglif1f2i_number=15f2 15f1 15link(“/usr/users/wang/d1/f1”, “/usr/users/li/f2”)unlink(“/usr/users/wang/d1/f1”)usrusrrootroot7.6 文件的保护、保密与安全文件的保护、保密与安全n保护保护n防止用户对文件进

14、行非授权的访问防止用户对文件进行非授权的访问n保密保密n防止文件内容泄露防止文件内容泄露n安全安全n防止文件被破坏防止文件被破坏n自然因素自然因素n人为因素人为因素7.6.1文件的保护文件的保护(Protection)nFile owner/creator should be able to control:nwhat can be donenby whomnTypes of accessnReadnWritenExecutenAppendnDeletenList1. 存取控制矩阵存取控制矩阵 f1 fj fnu1 a11. a1j . a1n .ui ai1 aij . ain . um a

15、m1 . amj . amn R W E A M D aij:特点：特点：权限规定细，过于繁琐，占较多存储空间权限规定细，过于繁琐，占较多存储空间2. 访问权限说明（访问权限说明（UNIX）i_modeR W E R W E R W E文件主文件主同组用户同组用户其他用户其他用户文件主判别：访问进程文件主判别：访问进程u_uid=i_uid同组用户判别：访问进程同组用户判别：访问进程u_gid=i_gidi_mode在创建文件时给出，在创建文件时给出，creat(filename, mode)其后文件主可以修改：其后文件主可以修改：chmod(filename, new_mode)特权用户特权

16、用户7.6.2 文件保密文件保密n口令口令n使用使用n创建文件时用户规定一个口令，系统将其记在创建文件时用户规定一个口令，系统将其记在FCB中中n访问文件要求给出口令，并与访问文件要求给出口令，并与FCB中口令比较中口令比较n特点特点n简单简单n保密性不强保密性不强(eg. 对系统操作员不保密对系统操作员不保密)n密码密码n特点特点n对文件内容加密，速度慢，效果好对文件内容加密，速度慢，效果好n使用使用n保存时加密保存时加密(key)n读取时解密读取时解密(key)n保存时：保存时：n用一个用一个key启动一个随机数发生器，产生一个随机启动一个随机数发生器，产生一个随机数序列，将其依此加到文件

17、的各个字中。数序列，将其依此加到文件的各个字中。n读取时：读取时：n用同一个用同一个key启动同一个随机数发生器，产生相同启动同一个随机数发生器，产生相同随机数序列，将其依次由文件的各个字中减去随机数序列，将其依次由文件的各个字中减去。线性同余法产生伪随机数：线性同余法产生伪随机数： Procedure random(Var key:integer); Begin key:=(key*C1+C2)MOD C3 End;7.6.3 文件系统的安全文件系统的安全nBackup(备份备份)n定期将磁盘上文件复制到磁带上定期将磁盘上文件复制到磁带上n发生故障时由磁带恢复发生故障时由磁带恢复(limit

18、ed recovery) n实现方法实现方法n完全转储完全转储n定期将磁盘上文件全部复制到磁带上定期将磁盘上文件全部复制到磁带上n恢复：最后一次转储磁带恢复：最后一次转储磁带n优点：恢复容易优点：恢复容易n缺点：大量冗余缺点：大量冗余n增量转储（增量转储（incremental backup)n每次只复制上次转储以来修改部分每次只复制上次转储以来修改部分n恢复：由初始转储磁带起，利用第二次转储磁带、第三次转储磁带、恢复：由初始转储磁带起，利用第二次转储磁带、第三次转储磁带、最后一次转储磁带，逐步恢复到最终版本最后一次转储磁带，逐步恢复到最终版本n优点：每次转储数据少优点：每次转储数据少n缺点：

19、实现麻烦，某次转储磁带发生问题将使恢复困难缺点：实现麻烦，某次转储磁带发生问题将使恢复困难7.6.3 文件系统的安全文件系统的安全n差分转储（差分转储（differential backup)n开始进行一次完全转储开始进行一次完全转储n以后每次备份当天与开始第一次备份不同的数据以后每次备份当天与开始第一次备份不同的数据n恢复：利用第一次转储磁带和最后一次转储磁带恢复：利用第一次转储磁带和最后一次转储磁带n优点：实现简单，恢复容易优点：实现简单，恢复容易n磁盘整理磁盘整理n利用转储和恢复可以对磁盘进行整理利用转储和恢复可以对磁盘进行整理(使文使文件物理块连续，空闲盘块连续件物理块连续，空闲盘块连

20、续)7.7 文件系统的实现文件系统的实现n7.7.1 内存所需表目内存所需表目n系统打开文件表系统打开文件表(系统一个系统一个)FCB主部主部文件号文件号共享计数共享计数 修改标志修改标志7.7 文件系统的实现文件系统的实现n7.7.1 内存所需表目内存所需表目n用户打开文件表用户打开文件表(每个进程一个每个进程一个)打开方式打开方式 读写指针读写指针 系统打开文件表入口系统打开文件表入口文件描述符文件描述符7.7 文件系统的实现文件系统的实现打开方打开方式式读写指读写指针针系统打开文系统打开文件表入口件表入口 打开方打开方式式读写指读写指针针系统打开文系统打开文件表入口件表入口 FCB主部主

21、部 文件号文件号 共享计数共享计数 修改标志修改标志 系统打开文件表系统打开文件表2文件描文件描述符述符文件描文件描述符述符用户打开文件表用户打开文件表15外存空间的管理外存空间的管理n空闲块表空闲块表n空闲块链空闲块链n位示图位示图(bit map)nLinux, 分给一个文件的磁盘块连续分给一个文件的磁盘块连续nUNIX:成组连接成组连接空闲块管理空闲块管理(成组连接成组连接)：100个空闲块为一组，组之间相互链接，最前面的组个空闲块为一组，组之间相互链接，最前面的组记在超级块中，安装后缓冲到内存。记在超级块中，安装后缓冲到内存。s_nfree=66s_free0s_free1.s_fre

22、e65.Super block .特点：速度快，空间省。特点：速度快，空间省。空闲块管理：空闲块管理：申请时：申请时： (1) s_nfree1, 分配分配s_free-s_nfree所指的块所指的块; (2) s_nfree=1, 将将s_free0所指的连接块读入内存所指的连接块读入内存缓冲区缓冲区, 前前202字节复制到字节复制到filesys,分配分配s_free0所指的所指的块块.释放时释放时: (1) s_nfree1, 分配分配s_free-s_nfree所指的块所指的块; (2) s_nfree=1, 将将s_free0所指的连接块读入内所指的连接块读入内存缓冲区存缓冲区, 前

23、前202字节复制到字节复制到filesys,分配分配s_free0所所指的块指的块.释放时释放时: (1) s_nfree0, 取取s_inode-s_ninode; (2) s_ninode=0, 由磁盘由磁盘inode区顺取区顺取100个空闲个空闲I节点节点(i_nlink=0) 将其编号填入将其编号填入s_inode表中，修改表中，修改s_ninode，然后分配。，然后分配。释放时：释放时： (1) s_ninode0转转6;4. 由由f_inode找到对应找到对应inode, f_inode指向空；指向空；5. i_count-, 如为如为0，i_flag标志有修改，写回外存标志有修改

24、，写回外存inode区；区；6. u_ofilefd=-1(空闲标志空闲标志)。seek(fd, whence, offset)fd: 文件描述符；文件描述符；whence: 相对位置相对位置(0,1,2,3,4,5)=(头，当前位置，尾头，当前位置，尾)offset: 移动量；移动量；1. 由由u_ofilefd找到找到file表入口；表入口；2. 由由f_inode找到内存找到内存inode;3. 检查参数合法性检查参数合法性(i_size0, i_size1, f_offset, offset, whence);4. 按参数要求调整按参数要求调整f_offset指针。指针。nrd=rea

25、d(fd,buf,count)fd: 文件描述符；文件描述符；buf: 进程空间接收进程空间接收区区地址；地址；count: 读字节数；读字节数；1. 由由u_ofilefd，找到，找到file表对应入口；表对应入口；2. 检查访问合法性检查访问合法性(f_flag, READ);3. 由由f_inode找到内存找到内存inode入口；入口；4. 由由f_offset, count和和i_addr计算访问磁盘块号计算访问磁盘块号(可能多个块可能多个块) 和块内字节；和块内字节； (bmap函数函数)；5. 若缓冲区有若缓冲区有, 所需字节复制到进程空间由所需字节复制到进程空间由buf起始位置起

26、始位置(iomove)；6. 若缓冲区无若缓冲区无, 申请空缓冲申请空缓冲(可能多个可能多个), 缓冲区链入设备缓冲区链入设备IO队列，若设备空闲队列，若设备空闲 启动设备启动设备(切换进程切换进程), 缓冲区信息复制到进程空间缓冲区信息复制到进程空间(iomove)；7. 返回实际传输字节数返回实际传输字节数nrd。nwt=write(fd,buf,count)fd: 文件描述符；文件描述符；buf:进程空间发送地址；进程空间发送地址；count: 写字节数；写字节数；1. 由由u_ofilefd，找到，找到file表对应入口；表对应入口；2. 检查访问合法性检查访问合法性(f_flag,

27、WRITE);3. 由由f_inode找到内存找到内存inode入口；入口；4. 由由f_offset, count和和i_addr计算磁盘地址块号计算磁盘地址块号(可能分配盘块可能分配盘块）；）；5. 申请系统缓冲区，将申请系统缓冲区，将buf起始起始count字节送到缓冲区字节送到缓冲区(可多次可多次)；6. 缓冲区链到设备缓冲区链到设备IO链上链上, 如设备空闲启动设备；如设备空闲启动设备；7. 修改修改inode中文件长度中文件长度i_size;8. 返回实际传输字节数返回实际传输字节数nwt。pipe(fd)int fd2;1. 分配一个分配一个inode，(i_count=2);2

28、. 分配分配2个个file表目表目(f_flag分别为分别为PipeR和和PipeW，读读/写指针写指针 offset为为0）3. 分配分配2个个u_ofile表目表目, 分别指向分别指向2个个file表目；表目；4. 返回返回2个文件描述符个文件描述符fd0,fd1, 分别为分别为u_ofile中的中的2个入口。个入口。 i_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count (1)f_flag (W pipe)f_offsetf_inodepf_count (1)内存内存inode表表内存内存file表表fd0fd1u_ofile

29、表表进程执行进程执行pipe(fd)之后之后 i_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count (2)f_flag (W pipe)f_offsetf_inodepf_count (2)内存内存inode表表内存内存file表表fd0fd1u_ofile表表fork创建子进程创建子进程1之后之后fd0fd1父进程父进程:子进程子进程1: i_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count (3)f_flag (W pipe)f_offsetf_inodepf_cou

30、nt (3)内存内存inode表表内存内存file表表fd0fd1u_ofile表表fork创建子进程创建子进程2之后之后fd0fd1父进程父进程:子进程子进程1:子进程子进程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count (2)f_flag (W pipe)f_offsetf_inodepf_count (2)内存内存inode表表内存内存file表表fd0fd1u_ofile表表父进程父进程close(fd0),close(fd1)fd0fd1父进程父进程:子进程子进程1:子进程子进程2:fd0fd1 i

31、_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count (2)f_flag (W pipe)f_offsetf_inodepf_count (1)内存内存inode表表内存内存file表表fd0fd1u_ofile表表子进程子进程1(读者读者) : close(fd1)fd0fd1父进程父进程:子进程子进程1:子进程子进程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count (1)f_flag (W pipe)f_offsetf_inodepf_count

32、(1)内存内存inode表表内存内存file表表fd0fd1u_ofile表表子进程子进程2(写者写者) : close(fd0)fd0fd1父进程父进程:子进程子进程1:子进程子进程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count (1)f_flag (W pipe)f_offsetf_inodepf_count (1)内存内存inode表表内存内存file表表u_ofile表表子进程子进程2(写写) : write(fd1,buf1,count1)子进程子进程1(读读) : read(fd0,buf0,co

33、unt0)父进程父进程:子进程子进程1:子进程子进程2:fd0fd1fd0fd1fd0fd1write(fd1,)read(fd0,) 盘块盘块(有缓冲有缓冲) i_addr i_count (1) f_flag (R pipe)f_offsetf_inodepf_count (1)f_flag (W pipe)f_offsetf_inodepf_count (0)内存内存inode表表内存内存file表表u_ofile表表子进程子进程2(写完写完) :close(fd1)父进程父进程:子进程子进程1:子进程子进程2:fd0fd1fd0fd1fd0fd1close(fd1)read(fd0,)

34、 盘块盘块(有缓冲有缓冲) 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(fd0)父进程父进程:子进程子进程1:子进程子进程2:fd0fd1fd0fd1fd0fd1close(fd1)close(fd0)Pipe文件同步与互斥文件同步与互斥npipe读写同步读写同步n写满：写者等待，读出后唤醒写满：写者等待，读出后唤醒n读空：读者等待，

35、写入后唤醒读空：读者等待，写入后唤醒n读写关闭读写关闭n所有读者关闭：写时返回错误信号所有读者关闭：写时返回错误信号n所有写者关闭：读者立即返回所有写者关闭：读者立即返回n读写互斥读写互斥ni_flag|ILOCK管道通讯的局限性管道通讯的局限性n只有相关进程只有相关进程(同一家族进程同一家族进程)能通讯能通讯n先创建管道先创建管道n再创建子进程再创建子进程, 子进程继承父进程打开的文子进程继承父进程打开的文件件(包括管道文件包括管道文件)n管道是没有名字的文件管道是没有名字的文件n所有进程都关闭后即被撤销所有进程都关闭后即被撤销命名管道命名管道(FIFO)n长久性通讯机构长久性通讯机构n具有

36、文件名具有文件名n可被打开、读写、关闭和删除可被打开、读写、关闭和删除n任何进程都能找到它任何进程都能找到它n即使是不同祖先的进程，也可以利用命名管道进行通信。即使是不同祖先的进程，也可以利用命名管道进行通信。n读取和写入遵循读取和写入遵循FIFO原则原则n阻塞：阻塞：n管道读管道读: 假如没有线程实行写管道操作，读线程将一直阻塞，直假如没有线程实行写管道操作，读线程将一直阻塞，直到有线程往里面写为止；到有线程往里面写为止；n管道写管道写: 假如没有线程实行读操作，写线程将一直阻塞，直到有假如没有线程实行读操作，写线程将一直阻塞，直到有线程读数据为止。线程读数据为止。n不阻塞：不阻塞：n管道读

37、管道读：假如没有线程实行写管道操作，读线程将立即返回；：假如没有线程实行写管道操作，读线程将立即返回；n管道写管道写：假如没有线程实行读操作，写线程将立即返回，返回不：假如没有线程实行读操作，写线程将立即返回，返回不正确码正确码-1。系统调用系统调用mkfifonint mkfifo(pathname,mode)npathname：FIFO文件名文件名nmode: 权限说明权限说明n0666, 所有用户可读可写所有用户可读可写n返回值：正常返回值：正常0, 失败失败-1n一旦创建了一个一旦创建了一个FIFO，就可用，就可用open打开它，打开它，一般的文件访问函数（一般的文件访问函数（clos

38、e、read、write等）都可用于等）都可用于FIFO，但，但lseek不可以（为什不可以（为什么？）么？）FIFO例子例子ninclude ninclude ninclude nmain()nn unlink(FIFO);n mkfifo(FIFO, 0666);n if(fork()0)n n char s=“hello!n”;n fd=open(FIFO, O_WRONLY);n write(fd, s, sizeof(s);n close(fd);nn nelsenn fd=open(FIFO, O_RDONLY);n read(fd, buffer, 80);n printf(“%

39、s”, buffer);n close(fd);nlink(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:

40、存在；存在；d1,d3: 存在，存在，f2: 不存在，不存在，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)mknode(pathname

41、, type and permissions, dev)pathname: 节点名；节点名；type and permissions: 节点类型和访问权限；节点类型和访问权限；dev: 主次设备号；主次设备号；功能功能: 创建特殊文件创建特殊文件.1. 如非特权用户，失败；如非特权用户，失败；2. 建立一个建立一个i_node, 初始化初始化(i_mode=type and permission; i_addr0=dev);3. 填写目录项。填写目录项。struct mount int m_dev; struct buf *m_bufp; /超级块超级块 struct inode *m_ino

42、dep;mountNMOUNT;#define NMOUNT 5devrootrk05makenode创建创建usrLid01安装安装: smount(“/dev/rk05”, “/usr/Li/d01”, 0)卸下卸下: sumount(“/dev/rk05”)i_flag =| IMOUNTbit: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Set gidSet uid大文件大文件00普通普通01字符字符10目录目录11块型块型i_mode: i_flag:ILOCKIUPDIACCIMOUNTIWANTITEXT执行该文件进程的身份暂时改为文执行该文件进

43、程的身份暂时改为文件主的身份件主的身份即即: u_uid = i_uid; u_gid = i_gid文件主权限文件主权限同组用户权限同组用户权限其他用户权限其他用户权限smount(special_pathname, directory_pathname, roflag)special_pathname: 特殊文件名特殊文件名directory_pathname: 目录文件名（安装节点）目录文件名（安装节点）roflag: 只读标志只读标志1. 检查是否超级用户；检查是否超级用户；2. 找到找到special_pathname文件的文件的inode(用用mknode建立建立);3. 合法性检

44、查（特殊块型文件）；合法性检查（特殊块型文件）；4. 找到找到directory_pathname节点的节点的inode;5. 如非目录或引用数大于，错返；如非目录或引用数大于，错返；6. 安装节点安装节点inode的的i_addr0=设备文件设备文件i_addr0; (dev) 7. 读入读入super block到到buf，按，按filesys格式解释格式解释.8. 分配一个分配一个mount表项，填写（表项，填写（m_dev，m_bufp，m_inodep），），9 安装节点安装节点inode的的i_flag =| IMOUNT.例子：例子：smount(“/dev/disk1”,“/u

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

46、_name)special_file_name: 待卸下卷的特殊文件名；待卸下卷的特殊文件名；1. 查目录找到查目录找到inode，取，取dev(i_addr0);2. 释放特殊文件的释放特殊文件的inode;3. 由由dev查查mount表表(m_dev)找到对应找到对应super block;4. 系统缓冲区延迟写块写回；系统缓冲区延迟写块写回；5. 该卷该卷所有所有更新更新i_node写回；写回；6. super block写回；写回；7. 释放释放super block所占用的缓冲区；所占用的缓冲区；8. 由由m_inodep找到安装节点的找到安装节点的inode;9. 安装节点安装节

47、点i_flag =& IMOUNT;10. 释放释放mount表项。表项。chdir(pathname)pathname: 目录路径名；目录路径名；1. 查目录找到查目录找到pathname的的inode; (不在内存读入不在内存读入,i_count=1；已已在内存在内存i_count+)；2. 检查权限；检查权限；3. u_cdir当前当前所指所指inode的的i_count-, 如为如为0且修改过且修改过,写回外存写回外存;4. 新新inode入口入口u_cdirchown(pathname,owner, group)pathname: 文件路径名文件路径名owner: 新文件主新

48、文件主group: 新文件组新文件组1. 查目录找到文件查目录找到文件(inode)；2. 权限检查权限检查(文件主文件主,特权用户特权用户)；3. 更新更新owner和和group(i_uid, i_gid)；4. inode写回。写回。chmode(pathname, newmode)pathname: 路径名；路径名；newmode: 新权限说明；新权限说明；1. 查目录找到文件查目录找到文件(inode)；2. 权限检查权限检查(文件主文件主,特权用户特权用户)；3. 更新更新i_mode(=newmode)；4. inode回写。回写。state(pathname, statbuff

49、er)pathname: 文件路径名；文件路径名；statbuffer: 状态缓冲区；状态缓冲区；1. 查目录找到内存查目录找到内存inode；2. inode信息信息(所有者、大小、权限、属性、链接数、所有者、大小、权限、属性、链接数、 inode号、访问时间等号、访问时间等)statbuffer;fstate(fd, statbuffer)1. 由由u_ofilefd找到找到file表；表；2. 由由file表找到表找到i_node;3. i_node信息信息statbuffer;7.9日志结构文件系统日志结构文件系统n背景背景nCPU速度越来越快速度越来越快n内存容量以接近指数级速度增长

50、内存容量以接近指数级速度增长n磁盘容量磁盘容量, 更大更便宜更大更便宜n磁盘速度的提高却相对较慢磁盘速度的提高却相对较慢 n成为系统效率的瓶颈成为系统效率的瓶颈 7.9日志结构文件系统日志结构文件系统n在在UNIX系统中创建一个文件系统中创建一个文件 (1)(1)(文件名文件名, ,文件号文件号) )写入目录中；写入目录中； (2)(2)新文件新文件inodeinode更新；更新； (3)(3)目录文件目录文件inodeinode更新更新( (长度变化长度变化) )； (4)(4)写入文件内容写入文件内容. .n小量写小量写(small write)n一次写修改磁盘块上的一小部分数据一次写修改

51、磁盘块上的一小部分数据n假定一次写需要假定一次写需要10ms寻道时间寻道时间, 4ms旋转延迟旋转延迟, 50s读写，读写，磁盘访问效率磁盘访问效率0.36%.n延迟写延迟写n发生故障给一致性带来威胁发生故障给一致性带来威胁Log Structured File Systemn日志结构文件系统日志结构文件系统nUC Berkeley的研究人员提出的研究人员提出 n一种全新的文件系统一种全新的文件系统日志结构文件系统日志结构文件系统nLSFS将整个磁盘看做一个日志，周期性将整个磁盘看做一个日志，周期性地追加新日志。写操作并非直接反映到地追加新日志。写操作并非直接反映到磁盘上，而是被暂时存到内存缓

52、冲区中，磁盘上，而是被暂时存到内存缓冲区中，其中包括新写的数据，也包括更新数据。其中包括新写的数据，也包括更新数据。当积累到一定规模时，作为一个当积累到一定规模时，作为一个segment追加到日志的末尾。追加到日志的末尾。LSFS结构结构图图segment1 segmentk new segment segment结构结构 summary Inodes, directories, data blocks 日志结构文件系统日志结构文件系统nInode map:nInode存储位置不能由其编号确定，系统维持一个存储位置不能由其编号确定，系统维持一个Inode map，以实现，以实现i-number

53、到磁盘到磁盘inode的映的映射。射。n清洁线程清洁线程(cleaner)n循环扫描磁盘并对循环扫描磁盘并对segment进行压缩。进行压缩。Cleaner 首先读入第一个首先读入第一个segment，舍弃过时内容，仍有用，舍弃过时内容，仍有用的的inode和数据块与内存当前和数据块与内存当前segment合并作为新合并作为新的的segment写回磁盘，旧写回磁盘，旧segment被标记为空闲，被标记为空闲，然后顺序处理下个然后顺序处理下个segment.7.10 内存映射文件内存映射文件n背景背景n文件保存于外存，存取速度慢文件保存于外存，存取速度慢n访问之前需要打开访问之前需要打开n每次访

54、问需要经过每次访问需要经过“打开文件表打开文件表”n读写需要经过读写需要经过I/O传输传输n缓冲可以提高速度，但首次访问需要缓冲可以提高速度，但首次访问需要I/On内存容量增加，利用率不充分内存容量增加，利用率不充分n进程虚拟空间大，只使用较小的一部分进程虚拟空间大，只使用较小的一部分n提示：将文件映射到内存提示：将文件映射到内存n以访问内存的方式访问文件以访问内存的方式访问文件nOpen, mmap, 使用使用, mumap, closeP1页表页表012345Memory Mapped FileBlock 2Block 0Block 3Block 1文件文件f1内存空间内存空间mapunm

55、apP2 页表页表0123Linux内存映射文件内存映射文件n1将文件映射到内存区域将文件映射到内存区域nvoid *mmap(void *addr, size_t len, int prot, int flag, int fd, off_t off);naddr为映射区首地址，一般使用为映射区首地址，一般使用NULL，然后系统自动分配一，然后系统自动分配一个合适地址个合适地址nlen为映射的长度，单位为映射的长度，单位bytenprot说明映射区访问属性说明映射区访问属性: PROT_READ(读读)、PROT_WRITE(写写)、 PROT_EXEC(执行执行)nflag为为MAP_SHA

56、RED 表示映射文件共享，表示映射文件共享，MAP_PRIVATE 表示映射文件不共享表示映射文件不共享nfd为打开文件返回的文件描述符为打开文件返回的文件描述符noff为映射位置的偏移量，设置为为映射位置的偏移量，设置为0的话，就映射文件的的话，就映射文件的0-len个个字节字节n返回值为映射到内存返回值为映射到内存空间的首地址空间的首地址Linux内存映射文件内存映射文件n2. 取消文件映射取消文件映射nint munmap(caddr_t addr,size_t len);naddr为内存映射的地址，即为内存映射的地址，即mmap返回的地返回的地址址nlen为映射的字节数。为映射的字节数

57、。n成功返回成功返回0，失败返回负数。，失败返回负数。Linux内存映射文件内存映射文件n3. 内存映射与文件同步内存映射与文件同步nint msync(void *addr, size_t len, int flags);naddr为内存映射地址为内存映射地址nlen为长度为长度nflags为为 MS_ASYNC, MS_SYNCnMS_ASYNC：异步写，调用后就返回不等待写完：异步写，调用后就返回不等待写完nMS_SYNC：等待写完后才返回：等待写完后才返回n成功返回成功返回0，失败为负。，失败为负。内存映射文件例子内存映射文件例子n将一个文本文件映射到内存。将一个文本文件映射到内存。n将所有小写字母改变为大写字母。将所有小写字母改变为大写字母。n将其写回该文件。将其写回该文件。内存映射文件例子内存映射文件例子n打开文件。打开文件。n利用系统调用利用系统调用mmap()将文件映射到内存。将文件映射到内存。n扫描内存映射区，将所有小写字母改变为对应扫描内存映射区，将所有小写字母改变为对应的大写字母。的大写字母。n调用调用msync将内存映射区内容回写到文件将内存映射区内容回写到文件n调用系统调用调用系统调用munmap解除对源文件的内存解除对源文件的内存映射。映射。n关闭文件。关闭文件。内存映射文件例子内存映射文件例子n#include / for mmap a