第1页：第七章文件系统
- 7.1文件与文件系统
- 文件
- 具有符号名而且在逻辑上具有完整意义的信息项的序列。
- 文件系统
- 文件与管理文件的程序集合。信息项信息项…信息项…信息项读(写)指针
第2页：UNIX文件分类
- UNIX文件分类
- 普通文件
- 内容可以是程序、数据、图象、MP3等，保存在磁盘块中
- 目录文件
- (文件名，文件号)序列，保存在磁盘块中
- 特殊文件
- 设备
- 设备作为文件管理的好处
- 界面统一，使用文件与使用设备命令相同，申请设备open,释放close,读read,写write
- 利用文件保护功能可以保护设备
第3页：7.2 文件的访问方式
- 顺序访问
- 从文件起始位置开始顺序访问
- 从文件中间某处开始顺序访问
- 随机访问
- 按记录编号随机访问
- 按关键字(key)随机访问
第4页：7.3 文件的组织
- 逻辑组织
- 用户看到的文件组织形式
- 记录式文件
- 记录的序列
- 等长记录（优点
- 处理方便，速度快；缺点：空间浪费）
- 不等长记录（优点
- 省空间；缺点：处理不便，速度慢）
- 流式文件
- 字节的序列(UNIX, Windows, etc)
- 物理组织
- 逻辑组织到磁盘块的映射
- 文件
- 记录(字节)序列
- 磁盘
- 块(block)序列变换关系
第5页：7.3.2 文件的物理组织
- 考虑因素
- 记录格式
- 等长或不等长,流式不必考虑
- 空间开销
- 除保存文件内容之外的存储开销
- 访问速度
- 随机访问速度
- 长度变化
- 动态增长
第6页：顺序结构
顺序结构：一个文件占有若干连续的磁盘块。优点：速度快，节省空间缺点：长度变化困难…块18块19块20块21块22...磁盘空间…首块=18块数=5...FCB
第7页：链接结构
链接结构：一文件可存于不连续块中，块间以指针相连。优点：节省空间，长度变化容易。缺点：随机访问速度慢。…块18...块80...块92...磁盘空间…首块=18块数=3...FCB
第8页：索引结构
索引结构：一文件可存于不连续块中，块号记在索引块中。优点：速度快，长度变化容易。缺点：索引块占空间。磁盘空间…索引块=29块数=4...FCB…块18块19...块26...块30...索引块29
第9页：Hash结构
Hash结构：计算地址：hash(key)=addr (在磁盘或文件中的存放位置)问题：给定key1key2hash(key1)=addr1;hash(key2)=addr2;addr1=addr2 (conflict)Conflict resolution:顺序探查法：如发生冲突，则在冲突位置开始顺序探查第一个空闲的存储位置。
第10页：......文件空间空闲标志冲突记数记…
......文件空间空闲标志冲突记数记录内容空闲标志冲突记数Hash(key)=addr起始位置计算addr=hash(key)对应冲突记数加1本记录空闲顺取下一个标记为占用填记录内容保存记录：TF记录内容
第11页：查找记录
查找记录：计算addr=hash(key)取addr对应记录的冲突记数→countcount=0无此记录本记录空闲顺取下一记录key相等找到hash(key)相等count:=count-1count=0无此记录顺取下一记录TFFTTFTFTF
第12页：删除记录
删除记录：调用查找过程(key)找到错误返回置空闲标志(找到记录)冲突记数-1对应hash(key)特点：按关键字检索速度非常快。用途：常用于目录检索。注意：文件可循环使用，满时保存失败。FT
第13页：删除记录（续）
UNIX文件物理结构(索引+链接)…i_addr[0]...i_addr[9]i_addr[10]i_addr[11]i_addr[12]...inode.....................最大=10+256+2562+2563(块)
第14页：7.4 文件目录
- 文件控制块与目录项
- 文件控制块(FCB)
- 文件存在的标志，其中保存系统管理文件需要的全部信息
- 目录项
- 目录文件中的一项，内容为FCB
- 文件目录与目录文件
- 文件目录
- 用于检索文件的目录
- 目录文件
- 内容为目录项的文件
第15页：文件控制块FCB（File Contr…
文件控制块FCB（File Control Block）文件名文件号文件主文件类型文件属性共享说明文件长度文件地址建立日期最后修改日期最后访问日期口令其它FCB创建：建立文件时FCB撤消：删除文件时
第16页：文件控制块FCB（File Contr
单级目录(Single-Level Directory)A single directory for all users.缺点:1.Naming problem2.Grouping problem3.Protection problem
第17页：文件控制块FCB（File Co…（续）
两级目录(Two-Level Directory)Separate directory for each user.特点:1. Path name2. Can have the samefile name for different user3. Efficient searching4. No grouping capability
第18页：文件控制块FCB（File Co
rootbinusrlibdevetcunixlpccviusersLiWangd1d2f1consolepasswdbinyaccsf2多级目录(Multi-Level Directory as in UNIX)clibflib
第19页：文件目录的查找
- 文件目录的查找
- 查找路径
- 由根目录开始查找
- 由当前目录开始查找
- 查找算法
- 顺序查找（UNIX）
- hash查找（Solo）
- 对分查找（要求文件名排序）
第20页：文件目录的改进
- 文件目录的改进
- FCB
- 次部：(文件名,文件号)
- (UNIX 16 bytes)
- 保存在目录文件中
- 主部：(其它,链接记数)
- (UNIX 32 bytes)
- 保存在外存inode区域,打开时读入内存.
- 改进的好处
- 可以提高查找速度(顺序查找)
- 可以实现文件链接(link)
第21页：起依次编号文件存储区域
UNIX文件卷(volume)组织形式：0 1 2…k k+1…n-1导引块超级块inode区域每块16个inode,从
第22页：7.5 文件的共享
- 共享目的
- 节省存储空间
- (cc,vi,yacc)
- 进程相互通讯
- UNIX pipe()
- 文件共享模式
- 不同时使用
- 根据共享说明
- 同时使用
- 根据共享说明和(relaxed)R/W规则
第23页：文件的共享
- 文件的共享
- 文件共享的实现
- 公共目录
- 共享说明
- 连接d1userswanglif1f2i_number=15f2 15f1 15link(“/usr/users/wang/d1/f1”,“/usr/users/li/f2”)unlink(“/usr/users/wang/d1/f1”)usrroot
第24页：7.6 文件的保护、保密与安全
- 保护
- 防止用户对文件进行非授权的访问
- 保密
- 防止文件内容泄露
- 安全
- 防止文件被破坏
- 自然因素
- 人为因素
第25页：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
第26页：1.存取控制矩阵f1 …… fj ………
1.存取控制矩阵f1 …… fj …… fnu1 a11….… a1j……. a1n… … …… … …… ...ui ai1…… aij….… ain… … …… … …… ...um am1….. amj….… amnR W E A M Daij:特点：权限规定细，过于繁琐，占较多存储空间
第27页：2.访问权限说明（UNIX）i_mod…
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)特权用户
第28页：7.6.2 文件保密
- 口令
- 使用
- 创建文件时用户规定一个口令，系统将其记在FCB中
- 访问文件要求给出口令，并与FCB中口令比较
- 特点
- 简单
- 保密性不强(eg.对系统操作员不保密)
- 密码
- 特点
- 对文件内容加密，速度慢，效果好
- 使用
- 保存时加密(key)
- 读取时解密(key)
第29页：@B1@保存时
- 保存时：
- 用一个key启动一个随机数发生器，产生一个随机数序列，将其依此加到文件的各个字中。
- 读取时：
- 用同一个key启动同一个随机数发生器，产生相同随机数序列，将其依次由文件的各个字中减去。线性同余法产生伪随机数：Procedure random(Var key:integer);Beginkey:=(key*C1+C2)MOD C3End;
第30页：7.6.3 文件系统的安全
- Backup(备份)
- 定期将磁盘上文件复制到磁带上
- 发生故障时由磁带恢复(limited recovery)
- 实现方法
- 完全转储
- 定期将磁盘上文件全部复制到磁带上
- 恢复：最后一次转储磁带
- 优点：恢复容易
- 缺点：大量冗余
- 增量转储（incremental backup)
- 每次只复制上次转储以来修改部分
- 恢复：由初始转储磁带起，利用第二次转储磁带、第三次转储磁带、…、最后一次转储磁带，逐步恢复到最终版本
- 优点：每次转储数据少
- 缺点：实现麻烦，某次转储磁带发生问题将使恢复困难
第31页：7.6.3 文件系统的安全（续）
- 差分转储（differential backup)
- 开始进行一次完全转储
- 以后每次备份当天与开始第一次备份不同的数据
- 恢复：利用第一次转储磁带和最后一次转储磁带
- 优点：实现简单，恢复容易
- 磁盘整理
- 利用转储和恢复可以对磁盘进行整理(使文件物理块连续，空闲盘块连续)
第32页：7.7 文件系统的实现
- 7.7.1内存所需表目
- 系统打开文件表(系统一个)修改标志共享计数文件号FCB主部
第33页：7.7 文件系统的实现（续）
- 7.7.1内存所需表目
- 用户打开文件表(每个进程一个)系统打开文件表入口读写指针打开方式文件描述符
第34页：7.7 文件系统的实现（续3）
7.7文件系统的实现系统打开文件表入口读写指针打开方式………………系统打开文件表入口读写指针打开方式………………FCB主部文件号共享计数修改标志系统打开文件表2…文件描述符文件描述符用户打开文件表15
第35页：外存空间的管理
- 外存空间的管理
- 空闲块表
- 空闲块链
- 位示图(bit map)
- Linux,分给一个文件的磁盘块连续
- UNIX:成组连接
第36页：空闲块管理(成组连接)
空闲块管理(成组连接)：100个空闲块为一组，组之间相互链接，最前面的组记在超级块中，安装后缓冲到内存。…s_nfree=66s_free[0]s_free[1]...s_free[65]...Super block...............特点：速度快，空间省。
第37页：空闲块管理
空闲块管理：申请时：(1) s_nfree>1,分配s_free[--s_nfree]所指的块;(2) s_nfree=1,将s_free[0]所指的连接块读入内存缓冲区,前202字节复制到filesys,分配s_free[0]所指的块.释放时:(1) s_nfree<100, s_free[s_nfree++]=释放块号;(2) s_nfree=100,将s_nfree和s_free拷贝到释放块中,写回外存, s_free[0]=释放块号, s_nfree=1.
第38页：7.8 文件系统的界面
- 创建文件
- 命令形式:creat(path_name, fcb_args)
- 参数说明
- Path_name:文件路径名
- Fcb_args: FCB参数
- 执行步骤:
- (1)为此文件分配一个FCB主部,初始化(文件主、共享说明、创建时间、长度等)
- (2)将文件名和文件号作为FCB次部填到末级目录中
- (3)以写方式打开
- 例如: creat(“/usr/li/d1/f1”, mode)
第39页：7.8 文件系统的界面（续）
- 打开文件
- 命令形式:fd=open(path_name, mode)
- 参数说明
- path_name:文件路径名;
- mode:打开方式.
- 执行步骤
- (1)根据文件路径名查目录找到文件号，和FCB主部;
- (2)合法性检查(根据打开方式、共享说明、用户身份);
- (3)根据文件号查系统打开文件表看该文件是否已被打开,如是共享计数加1;否则取一个空闲的系统打开文件表项并将外存中FCB主部等信息填入此表项,共享计数置为1;
- (4)在用户打开文件表中取一空表项,填写打开方式和读写指针,并指向系统打开文件表的对应表项.
- 返回信息:fd:文件描述符(在用户打开文件表中的入口),它是一个非负整数.
第40页：7.8 文件系统的界面（续3）
- 关闭文件
- 命令形式: close(fd)
- 参数说明
- fd:文件描述符.
- 执行步骤:
- (1)由fd查用户打开文件表,找到系统打开文件表入口;
- (2)系统打开文件表中共享计数减1,如减1后的值为0且修改标志为1,则将此FCB由内存写回外存FCB主部;
- (3)将fd所对应的用户打开文件表项置为空闲.
第41页：7.8 文件系统的界面（续4）
- 指针定位
- 命令形式: seek(fd,offset)
- 参数说明:
- fd:文件描述符;
- offset:新的指针位置.
- 执行步骤:
- (1)由fd查用户打开文件表,得系统打开文件表入口;
- (2)查系统打开文件表,得文件长度;
- (3)检查参数合法性；
- (4)将用户打开文件表中文件读写指针位置设定为offset,后继读写命令由该指针处存取文件内容.
第42页：7.8 文件系统的界面（续5）
- 读文件
- 命令形式: read(fd,nrd,buf)
- 参数说明:
- fd:文件描述符;
- nrd:读入记录个数;
- buf:内存起始位置.
- 步骤:
- (1)由fd查用户打开文件表,找到对应的入口;
- (2)合法性检查(用户打开文件表中所记录的打开方式、存取方式);
- (3)查系统打开文件表,找到文件的地址;
- (4)根据逻辑地址(offset)和物理结构计算物理地址;
- (5)如在缓冲区中;所需字节复制到进程空间buf起始位置;
- (6)否则申请缓冲区(可能多个),链入设备IO队列,若设备空闲启动设备,等待IO传输完成(切换进程),所需字节复制到进程空间buf起始的位置.
第43页：7.8 文件系统的界面（续6）
- 写文件
- 命令形式: write(fd,nwt,buf)
- 参数含义:
- fd:文件描述符;
- nwt:写出记录个数;
- buf:内存起始位置.
- 执行步骤:
- (1)由fd查用户打开文件表,找到对应的入口;
- (2)合法性检查(用户打开文件表中所记录的打开方式、存取方式);
- (3)查系统打开文件表,找到文件的地址;
- (4)根据逻辑地址(offset)和物理结构计算物理地址;
- (5)如果需要,分配磁盘块;
- (6)将内存中由buf起始的nwt个记录复制到缓冲区中(可能多个),缓冲区链入磁盘IO队列,如设备空闲启动设备.
第44页：7.8 文件系统的界面（续7）
- 建立连接
- 命令形式: link(old_name,new_name)
- 参数含义:
- old_name:已存在的文件路径名;
- new_name:欲连接的文件路径名.
- 执行步骤:
- (1)查目录找到文件old_name的FCB主部,由此得到文件号;
- (2)查目录找到文件new_name的末级目录;
- (3)将文件号与new_name中末级名字合起来构成一个新的目录项,将其填入new_name的末级目录文件中;
- (4)将FCB主部中的连接计数加1.
- 如: link(“/usr/Li/f1”,“/usr/Zhang/d2/f2”)
第45页：7.8 文件系统的界面（续8）
- 断开连接
- 命令形式: unlink(path_name)
- 参数含义:
- path_name:文件路径名.
- 执行步骤:
- (1)查目录找到文件path_name的FCB主部;
- (2)将连接计数i_nlink减1;
- (3)如减1后的值为0,则归还该文件所占用的全部存储块,该文件将被撤销;
- (4)将FCB次部由上级目录中清除.
- 如: unlink(“/usr/Zhang/d2/f2”)
第46页：UNIX文件系统的实现
- UNIX文件系统的实现
- 内存所需表目(UNIX)
- 用户打开文件表
- u_ofile(每个进程一个)
- file(整个系统一个)
- 系统打开文件表
- Inode(整个系统一个)
- 外存空间的管理
- 空闲块表
- 位示图(bit map, Linux)
- 成组连接(UNIX approach)
第47页：1. u_ofile (每进程一个)
1. u_ofile (每进程一个)struct user{…int u_ofile[NOFILE];…}#define NOFILE 152. file (系统一个)struct file{char f_flag;
第48页：1. u_ofile (每进程一…（续）
UNIX系统的FCBstruct inode(外存){int i_mode;char i_nlink;char i_uid;char i_gid;char i_size0;char *i_size1;int i_addr[8];int i_atime[2];int i_mtime[2];}struct inode (内存){int i_flag;char i_count;char i_dev;char i_number;char i_mode;char i_nlink;char i_uid;char i_gid;char i_size0;char *i_size1;int i_addr[8];int i_lastr;}inode[NINODE];
第49页：表间联系
表间联系：u_ofile→file(n) (1)file→inode(n) (1)
第50页：表间联系（续）
write(4,…)write(4,…)…read(2,…)用户空间u_ofileu_ofilefileinode磁盘空间系统空间...数据块……...i_list表间联系
第51页：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中。
第52页：UNIX外存空间管理（续）
Struct filesys {int s_isize;
第53页：空闲块管理
空闲块管理：100个空闲块为一组，组之间相互链接。…s_nfree=88s_free[0]s_free[1]...s_free[87]...Super block...............特点：速度快，空间省。
第54页：空闲块管理（续）
申请时：(1) s_nfree>1,分配s_free[--s_nfree]所指的块;(2) s_nfree=1,将s_free[0]所指的连接块读入内存缓冲区,前202字节复制到filesys,分配s_free[0]所指的块.释放时:(1) s_nfree<100, s_free[s_nfree++]=释放块号;(2) s_nfree=100,将s_nfree和s_free拷贝到释放块中,写回外存, s_free[0]=释放块号, s_nfree=1.空闲块管理：
第55页：s_inode最多可以记载100个空闲…
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,丢弃。空闲inode管理：
第56页：文件系统界面(UNIX系统调用)
- 文件系统界面(UNIX系统调用)
- creat
- open
- close
- seek
- read
- write
- link
- unlink
- pipe
- mknode
- smount
- sumount
- chmod
- chowner
- state
- fstate
- chdir
第57页：文件系统界面(UNIX系统调用)（续）
- fd=creat(pathname,mode)pathname:路径名；mode:共享说明；
- 1.分配一个inode,初始化(i_size=0, i_mode=mode,i_nlink=1,i_uid=u_uid, i_gid=u_gid );
- 2.填写目录项(name, i_number)；
- 3.以写方式打开(填写inode表、file表和u_ofile表)；
- 4.返回文件描述符。例子：creat(“d1/d2/f1”, mode)假定分配i_number=15, (f1,15)→d2中(??????????????,-1)
第58页：文件系统界面(UNIX系统调用)（续3）
- fd=open(pathname,mode)pathname:路径名；mode:打开方式；fd:文件描述符(u_ofile表的入口)
- 1.查目录找到i_number;
- 2.由i_number查inode表；
- 3.查到, i_count++;否则inode移入内存，i_count=1；
- 4.权限检查(mode打开方式, i_mode共享说明, i_uid, i_gid文件主(组), u_uid, u_gid用户身份);
- 5.在file表中分配一个表项(f_count==0的),初始化f_count=1; f_offset=0; f_flag=mode, f_inodep指向inode;
- 6.在u_ofile中取一空闲表目，指向file表中对应表目;
- 7.返回文件描述符fd(在u_ofile表中的入口)。
第59页：close(fd)fd
- close(fd)fd:文件描述符；
- 1.由fd查u_ofile找到对应入口；
- 2.由u_ofile[fd]找到file表对应入口；3. f_count--,如>0转6;
- 4.由f_inode找到对应inode, f_inode指向空；5. i_count--,如为0，i_flag标志有修改，写回外存inode区；6.u_ofile[fd]=-1(空闲标志)。
第60页：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指针。
第61页：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.若缓冲区有,所需字节复制到进程空间由buf起始位置(iomove)；
- 6.若缓冲区无,申请空缓冲(可能多个),缓冲区链入设备IO队列，若设备空闲启动设备(切换进程),缓冲区信息复制到进程空间(iomove)；
- 7.返回实际传输字节数nrd。
第62页：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。
第63页：close(fd)fd（续5）
- pipe(fd)int fd[2];
- 1.分配一个inode，(i_count=2);
- 2.分配2个file表目(f_flag分别为PipeR和PipeW，读/写指针offset为0）
- 3.分配2个u_ofile表目,分别指向2个file表目；
- 4.返回2个文件描述符fd[0],fd[1],分别为u_ofile中的2个入口。
第64页：close(fd)fd（续6）
i_addr[ ]…i_count (2)…f_flag (Rpipe)f_offsetf_inodepf_count (1)f_flag (W pipe)f_offsetf_inodepf_count (1)………内存inode表内存file表fd[0]fd[1]u_ofile表………进程执行pipe(fd)之后
第65页：close(fd)fd（续7）
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表fd[0]fd[1]u_ofile表………fork创建子进程1之后fd[0]fd[1]………父进程:子进程1:
第66页：close(fd)fd（续8）
i_addr[ ]…i_count (2)…f_flag (R pipe)f_offsetf_inodepf_count (3)f_flag (W pipe)f_offsetf_inodepf_count (3)………内存inode表内存file表fd[0]fd[1]u_ofile表………fork创建子进程2之后fd[0]fd[1]………父进程:子进程1:………子进程2:fd[0]fd[1]
第67页：close(fd)fd（续9）
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表fd[0]fd[1]u_ofile表………父进程close(fd[0]),close(fd[1])fd[0]fd[1]………父进程:子进程1:………子进程2:fd[0]fd[1]
第68页：close(fd)fd（续10）
i_addr[ ]…i_count (2)…f_flag (R pipe)f_offsetf_inodepf_count (2)f_flag (W pipe)f_offsetf_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]
第69页：close(fd)fd（续11）
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表fd[0]fd[1]u_ofile表………子进程2(写者) : close(fd[0])fd[0]fd[1]………父进程:子进程1:………子进程2:fd[0]fd[1]
第70页：close(fd)fd（续12）
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(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],…)盘块(有缓冲)
第71页：close(fd)fd（续13）
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(fd[1])父进程:子进程1:子进程2:fd[0]fd[1]………………fd[0]fd[1]fd[0]fd[1]………close(fd[1])read(fd[0],…)盘块(有缓冲)
第72页：close(fd)fd（续14）
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])
第73页：Pipe文件同步与互斥
- Pipe文件同步与互斥
- pipe读写同步
- 写满：写者等待，读出后唤醒
- 读空：读者等待，写入后唤醒
- 读写关闭
- 所有读者关闭：写时返回错误信号
- 所有写者关闭：读者立即返回
- 读写互斥
- i_flag|ILOCK
第74页：管道通讯的局限性
- 管道通讯的局限性
- 只有相关进程(同一家族进程)能通讯
- 先创建管道
- 再创建子进程,子进程继承父进程打开的文件(包括管道文件)
- 管道是没有名字的文件
- 所有进程都关闭后即被撤销
第75页：命名管道(FIFO)
- 命名管道(FIFO)
- 长久性通讯机构
- 具有文件名
- 可被打开、读写、关闭和删除
- 任何进程都能找到它
- 即使是不同祖先的进程，也可以利用命名管道进行通信。
- 读取和写入遵循FIFO原则
- 阻塞：
- 管道读:假如没有线程实行写管道操作，读线程将一直阻塞，直到有线程往里面写为止；
- 管道写:假如没有线程实行读操作，写线程将一直阻塞，直到有线程读数据为止。
- 不阻塞：
- 管道读：假如没有线程实行写管道操作，读线程将立即返回；
- 管道写：假如没有线程实行读操作，写线程将立即返回，返回不正确码-1。
第76页：系统调用mkfifo
- 系统调用mkfifo
- int mkfifo(pathname,mode)
- pathname：FIFO文件名
- mode:权限说明
- 0666,所有用户可读可写
- 返回值：正常0,失败-1
- 一旦创建了一个FIFO，就可用open打开它，一般的文件访问函数（close、read、write等）都可用于FIFO，但lseek不可以（为什么？）
第77页：FIFO例子
- FIFO例子
- include <sys/types.h>
- include <sys/stat.h>
- include <fcntl.h>
- main()
- {
- unlink(FIFO);
- mkfifo(FIFO, 0666);
- if(fork()>0)
- {
- char s[]=“hello!\n”;
- fd=open(FIFO, O_WRONLY);
- write(fd, s, sizeof(s));
- close(fd);
- }
- else
- {
- fd=open(FIFO, O_RDONLY);
- read(fd, buffer, 80);
- printf(“%s”, buffer);
- close(fd);
- }
第78页：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:不存在，
第79页：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)
第80页：FIFO例子（续4）
- mknode(pathname, type and permissions, dev)pathname:节点名；type and permissions:节点类型和访问权限；dev:主次设备号；功能:创建特殊文件.1.如非特权用户，失败；
- 2.建立一个i_node,初始化(i_mode=type and permission;i_addr[0]=dev);
- 3.填写目录项。
第81页：FIFO例子（续5）
struct mount{int m_dev;struct buf *m_bufp;
第82页：FIFO例子（续6）
bit: 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0Set gidSet uid大文件00普通01字符10目录11块型i_mode:i_flag:ILOCKIUPDIACCIMOUNTIWANTITEXT执行该文件进程的身份暂时改为文件主的身份即: u_uid = i_uid; u_gid = i_gid文件主权限同组用户权限其他用户权限
第83页：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.安装节点inode的i_addr[0]=设备文件i_addr[0]; (dev)
- 7.读入super block到buf，按filesys格式解释.8.分配一个mount表项，填写（m_dev，m_bufp，m_inodep），9安装节点inode的i_flag =| IMOUNT.
第84页：FIFO例子（续8）
例子：smount(“/dev/disk1”,“/usr/d1”,0)安装之前：disk1只能作为特殊文件(块序列文件)访问(raw IO)；安装之后：d1成为disk1文件卷的根目录。disk1的super block读入内存缓冲区中，按filesys格式解释，根目录inode读入内存inode区中；内存中inode区是所有安装文件卷共用的，因而在内存inode中有i_dev指明inode对应的卷，用于回写。
第85页：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表项。
第86页：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
第87页：FIFO例子（续11）
- chown(pathname,owner, group)pathname:文件路径名owner:新文件主group:新文件组
- 1.查目录找到文件(inode)；
- 2.权限检查(文件主,特权用户)；
- 3.更新owner和group(i_uid, i_gid)；4. inode写回。
第88页：FIFO例子（续12）
- chmode(pathname, newmode)pathname:路径名；newmode:新权限说明；
- 1.查目录找到文件(inode)；
- 2.权限检查(文件主,特权用户)；
- 3.更新i_mode(=newmode)；4. inode回写。
第89页：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;
第90页：7.9 日志结构文件系统
- 背景
- CPU速度越来越快
- 内存容量以接近指数级速度增长
- 磁盘容量,更大更便宜
- 磁盘速度的提高却相对较慢
- 成为系统效率的瓶颈
第91页：7.9 日志结构文件系统（续）
- 在UNIX系统中创建一个文件(1)(文件名,文件号)写入目录中；(2)新文件inode更新；(3)目录文件inode更新(长度变化)；(4)写入文件内容.
- 小量写(small write)
- 一次写修改磁盘块上的一小部分数据
- 假定一次写需要10ms寻道时间, 4ms旋转延迟, 50µs读写，磁盘访问效率≈0.36%.
- 延迟写
- 发生故障给一致性带来威胁
第92页：7.9 日志结构文件系统（续3）
- Log Structured File System
- 日志结构文件系统
- UC Berkeley的研究人员提出
- 一种全新的文件系统
第93页：日志结构文件系统
- 日志结构文件系统
- LSFS将整个磁盘看做一个日志，周期性地追加新日志。写操作并非直接反映到磁盘上，而是被暂时存到内存缓冲区中，其中包括新写的数据，也包括更新数据。当积累到一定规模时，作为一个segment追加到日志的末尾。
第94页：日志结构文件系统（续）
LSFS结构图segment1segmentknew segment…… …segment结构summaryInodes, directories, data blocks
第95页：日志结构文件系统（续3）
- 日志结构文件系统
- Inode map:
- Inode存储位置不能由其编号确定，系统维持一个Inode map，以实现i-number到磁盘inode的映射。
- 清洁线程(cleaner)
- 循环扫描磁盘并对segment进行压缩。Cleaner首先读入第一个segment，舍弃过时内容，仍有用的inode和数据块与内存当前segment合并作为新的segment写回磁盘，旧segment被标记为空闲，然后顺序处理下个segment.
第96页：7.10 内存映射文件
- 背景
- 文件保存于外存，存取速度慢
- 访问之前需要打开
- 每次访问需要经过“打开文件表”
- 读写需要经过I/O传输
- 缓冲可以提高速度，但首次访问需要I/O
- 内存容量增加，利用率不充分
- 进程虚拟空间大，只使用较小的一部分
- 提示：将文件映射到内存
- 以访问内存的方式访问文件
- Open, mmap,使用, mumap, close
第97页：7.10 内存映射文件（续）
P1页表012345Memory Mapped FileBlock 2Block 0Block 3Block 1文件f1内存空间mapunmapP2页表0123
第98页：的话，就映射文件的
- Linux内存映射文件
- 1．将文件映射到内存区域
- void *mmap(void *addr, size_tlen, intprot, intflag, intfd, off_toff);
- addr为映射区首地址，一般使用NULL，然后系统自动分配一个合适地址
- len为映射的长度，单位byte
- prot说明映射区访问属性: PROT_READ(读)、PROT_WRITE(写)、PROT_EXEC(执行)
- flag为MAP_SHARED表示映射文件共享，MAP_PRIVATE表示映射文件不共享
- fd为打开文件返回的文件描述符
- off为映射位置的偏移量，设置为
第99页：失败返回负数
- Linux内存映射文件
- 2.取消文件映射
- int munmap(caddr_taddr,size_tlen);
- addr为内存映射的地址，即mmap返回的地址
- len为映射的字节数。
- 成功返回
第100页：Linux内存映射文件
- Linux内存映射文件
- 3.内存映射与文件同步
- int msync(void *addr, size_tlen, intflags);
- addr为内存映射地址
- len为长度
- flags为MS_ASYNC, MS_SYNC
- MS_ASYNC：异步写，调用后就返回不等待写完
- MS_SYNC：等待写完后才返回
- 成功返回
第101页：内存映射文件例子
- 内存映射文件例子
- 将一个文本文件映射到内存。
- 将所有小写字母改变为大写字母。
- 将其写回该文件。
第102页：内存映射文件例子（续）
- 内存映射文件例子
- 打开文件。
- 利用系统调用mmap()将文件映射到内存。
- 扫描内存映射区，将所有小写字母改变为对应的大写字母。
- 调用msync将内存映射区内容回写到文件
- 调用系统调用munmap解除对源文件的内存映射。
- 关闭文件。
第103页：内存映射文件例子（续3）
