张惠娟副教授Mszhj@163com.ppt

1,张惠娟 副教授M,实用操作系统概念,2,内容框架,概述 体系结构 进程管理 内存管理 文件管理 外设管理,3,内容,Chp 13:Mass storage Structure Chp 11:File system,4,Module 11:File-System,File Concept Directory Structure Free-Space Management File Implementation Efficiency and Performance Protection Recovery,5,引言 文件定义 文件系统定义 File Attributes File Operations File type File Structure Access Methods,File Concept,6,引言计算机应用程序都要：存储信息和检索信息 能够存储大量的信息 长期保存信息 可以共享信息,File Concept,7,解决方法文件 信息以一种单元，即文件的形式存储在磁盘或其他外部介质上。文件是通过操作系统来管理的，包括：文件的结构、命名、存取、使用、保护、实现方法。,File Concept,8,文件系统 负责信息组织、存储和访问，提供高效、快速和方便的信息存储和访问功能。,File Concept,9,用户观点 文件系统如何呈现在其面前，如：一个 文件由什么组成、如何命名，如何保护 文件、可进行何种操作等。操作系统观点 文件目录怎样实现、怎样管理存储空间、文件存储位置、磁盘实际运作方式(与设备管理的接口)等等,File Concept,10,文件定义是一组带标识的、在逻辑上有完整意义的信息项的序列。其中：标识是文件名 信息项是构成文件内容的基本单位 长度是单个字节或多个字节 文件内容由文件建立者和使用者解释,File Concept,11,文件的各信息项之间具有顺序关系,File Concept,12,文件系统是操作系统中统一管理信息资源的一种软件。管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。,File Concept,13,文件系统的功能统一管理文件的存储空间，实施存储空间的分配与回收。实现文件的按名存取 名字空间 映射 存储空间实现文件信息的共享，并提供文件保护和保密措施,File Concept,14,向用户提供方便使用的接口 如提供对文件系统操作命令、提供对文件的操作命令：信息存取、加工等系统维护及向用户提供有关信息文件系统的执行效率提供与I/O的统一接口,File Concept,15,File Attributes Information about files are kept in the directory structure,which is maintained on the disk.Name only information kept in human-readable form.Type needed for systems that support different types.Location pointer to file location on device.,File Concept,16,Size current file size.Protection controls who can do reading,writing,executing.Time,date,and user identification data for protection,security,and usage monitoring.,File Concept,17,File Operationscreatewritereadreposition within file file seekdeletetruncate,File Concept,18,open(Fi)search the directory structure on disk for entry Fi,and move the content of entry to memory.close(Fi)move the content of entry Fi in memory to directory structure on disk.,File Concept,19,File type分类目的 对不同文件进行管理,提高系统效率；提高用户界面友好性按信息保存期限分类 临时文件；永久文件；档案文件按文件保护方式分类 只读文件；读写文件；可执行文件,File Concept,20,按文件性质和用途分类系统文件用户文件库文件,File Concept,21,按文件的逻辑结构分类 流式文件；记录式文件按文件的物理结构分类 顺序（连续）文件；链接文件；索引文件,File Concept,22,File Concept,23,File Structure 逻辑结构 物理结构,File Concept,24,逻辑结构 是从用户角度研究文件的组织形式无结构文件有结构文件,File Concept,25,File Concept,26,无结构文件：流式文件 构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字符的集合。文件 一个无结构字节序列 好处 提供很大的灵活性,File Concept,27,有结构文件：记录文件 文件是由若干个记录组成，每个记录有一个键，可按键进行查找。文件 一个固定长度记录的序列，每条记录有其内部结构,File Concept,28,物理结构 从系统角度来看文件，从文件在物理介质上的存放方式来研究文件.连续（顺序）结构 链接结构 索引结构,File Concept,29,连续结构（顺序）文件信息存放在若干连续的物理块中,File Concept,30,File Concept,31,优点简单 支持顺序存取和随机存取顺序存取速度快所需的磁盘寻道次数和寻道时间最少,File Concept,32,缺点 文件不能动态增长 预留空间:浪费 重新分配和移动 不利于文件插入和删除 外部碎片问题 存储压缩技术,File Concept,33,链接结构 文件信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。,File Concept,34,File Concept,35,优点提高了磁盘空间利用率,不存在外部碎片问题有利于文件插入和删除有利于文件动态扩充,File Concept,36,缺点存取速度慢，不适于随机存取可靠性问题，如指针出错更多的寻道次数和寻道时间链接指针占用一定的空间,File Concept,37,索引结构文件信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中 一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块,File Concept,38,文件名 索引表地址,文件目录,Jeep 19,916 11025-1-1-1,19,39,优点保持了链接结构的优点,又解决了其缺点：即能顺序存取,又能随机存取满足了文件动态增长、插入删除要求能充分利用外存空间,File Concept,40,缺点较多的寻道次数和寻道时间索引表本身带来了系统开销 如：内外存空间，存取时间,File Concept,41,索引表组织链接模式 一个盘块一个索引表,多个索引表链接起来多级索引 将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中 综合模式 UNIX文件系统采用多级索引结构(综合模式)。,File Concept,42,综合模式每个文件索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址）如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址 UNIX采用了三级索引结构后，文件最大可达16兆个物理块,File Concept,43,44,Access Methods 顺序存取方式 随机(直接)存取方式,File Concept,45,File Concept,46,基本概念目录结构文件访问方法目录结构改进,Directory Structure,47,基本概念文件控制块（FCB）文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（文件属性）文件控制块是文件存在的标志,Directory Structure,48,文件控制块内容 Name TypeAddress Current lengthMaximum lengthDate last accessed(for archival)Date last updated(for dump)Owner ID(who pays)Protection information(discuss later),Directory Structure,49,文件目录 把所有FCB组织在一起，就构成了文件目录，即文件控制块的有序集合目录项 构成文件目录的项目（目录项就是FCB）目录文件 为实现对文件目录的管理，通常将文件目录以文件形式保存在外存，这个文件就叫目录文件。,Directory Structure,50,目录结构目的一级目录二级目录树型目录（多级目录）其它方法,Directory Structure,51,目的 Efficiency locating a file quickly.Naming convenient to users.Two users can have same name for different files.The same file can have several different names.Grouping logical grouping of files by properties,(e.g.,all Pascal programs,all games,),Directory Structure,52,一级目录结构 A single directory for all users.,Directory Structure,53,优点 简单、易实现 缺点 Naming problem Grouping problem,Directory Structure,54,二级目录结构 Separate directory for each user.,Directory Structure,55,优点Path nameCan have the saem file name for different userEfficient searchingNo grouping capability 缺点 增加系统开销,Directory Structure,56,树型目录结构,Directory Structure,57,优点层次结构清晰，便于管理和保护有利于文件分类解决重名问题提高文件检索速度能进行存取权限的控制 缺点 查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度,Directory Structure,58,其它方法哈希表算法目录项信息存在一哈希表中搜索时根据文件名计算哈希值得到一个指向表中文件的指针其他算法 如B+树,Directory Structure,59,文件访问方法目录检索 用户给出文件名，按名寻找目录项 根据路径名检索：全路径名：从根开始 相对路径：从当前目录开始,Directory Structure,60,文件寻址 根据FCB中文件物理地址等信息，求出文件的任意记录或字符在存取介质上的地址，称为文件寻址。,Directory Structure,61,目录改进改进目的 加快目录检索,Directory Structure,62,改进方法 采用目录项分解法，把FCB分成两部分。符号目录顶（次部）文件名，文件号 基本目录项（主部）除文件名外的所有项目 如：UNIX：I节点（索引节点）,Directory Structure,63,64,例：一个FCB有48个字节，符号目录项占 8字节，文件名6字节，文件号2字节，基本目录项占 48-6=42字节。假设，物理块大小512字节,Directory Structure,65,解：分解前：占512/48=10个FCB 分解后：占512/8=64个符号目录项或512/42=12个基本目录项 假设：目录文件有128个目录项 分解前：占13块 分解后：符号文件占2块 基本文件占11块,Directory Structure,66,查找一个文件的平均访盘次数 分解前：(1+13)/2=7次 分解后：(1+2)/2+1=2.5次 减少了访问硬盘的次数，提高了检索速度,Directory Structure,67,数据结构 管理方法,Free-Space Management,68,数据结构空闲块表 所有空闲块记录在一个表中空闲块链表 把所有空闲块链成一个链,Free-Space Management,69,管理方法位图法成组链接法,Free-Space Management,70,位示图 用一串二进制位反映磁盘空间中的分配使用 情况,每个物理块对应一位,分配物理块为1，否则为0。申请物理块时，在位示图中查找为0的位，返回对应物理块号；归还时，将对应位转置0 描述能力强，适合各种物理结构,Free-Space Management,71,计算公式 已知字号i，位号j 块号i字长j 已知块号 字号 块号/字长 位号块号 mod 字长,Free-Space Management,72,已知块号，则磁盘地址：柱面号块号/（磁头数扇区数）磁头号（块号mod（磁头数扇区数）/扇区数扇区号（块号mod（磁头数扇区数）mod 扇区数 已知磁盘地址：块号柱面号（磁头数扇区数）磁头号扇区数扇区号,Free-Space Management,73,成组链接法,Free-Space Management,74,75,76,Protection,File owner/creator should be able to control:what can be doneby whomTypes of accessReadWriteExecuteAppendDeleteList,77,File Implementation,数据结构 文件执行,78,数据结构 系统文件表 用户文件表 两种表间的关系,File Implementation,79,系统文件表系统打开文件表（整个系统一张）放在内存，用于保存已打开文件的FCB文件号、共享计数、修改标志,File Implementation,80,用户文件表 每个进程一个，进程的PCB中，记录了用户打开文件表的位置。,File Implementation,81,File Implementation,两种表间的关系用户打开文件表指向系统打开文件表多个进程共享同一个文件，则多个用户打开文件表目对应系统打开文件表的同一入口,82,83,文件执行文件操作执行过程文件共享,File Implementation,84,文件操作提供设置和修改对用户文件存取权限的服务提供建立、修改、改变、删除目录的服务提供文件共享、设置访问路径的服务提供创建、打开、读、写、关闭、撤消文件等服务文件系统维护文件系统的转储和恢复,File Implementation,85,文件执行 Create()Open()Read(),File Implementation,86,Create()实质是建立文件的FCB，并建立必要的存储空间，分配空FCB，根据提供的参数及需要填写有关内容，返回一个文件描述.,File Implementation,87,执行过程：检查参数的合法性检查同一目录下有无重名文件在目录中有无空闲位置填写目录项内容返回,File Implementation,88,Open()文件使用前都要先打开，即把FCB送到内存。fd=open（文件路径名，打开方式）,File Implementation,89,执行过程：根据文件路径名查目录，找到FCB主部；根据打开方式、共享说明和用户身份检查访问合法性；根据文件号查系统打开文件表，看文件是否已被打开；是共享计数加1，否则将外存中的FCB主部等信息填入系统打开文件表空表项，共享计数置为1；,File Implementation,90,在用户打开文件表中取一空表项，填写打开方式等，并指向系统打开文件表对应表项。返回信息 fd：文件描述符，是一个非负整数，用于以后读写文件。,File Implementation,91,Read()检查长度是否为正整数根据文件名查找目录，确定该文件在目录中的位置。根据隐含参数中的进程主和目录中该文件的存储权限数据，检查是否有权读？由文件内位置与要读的长度计算最末位置，将其与目录中的文件长度比较，超过否？,File Implementation,92,根据参数中的位置、长度和目录中的映射信息，确定块号、块数、块内位移与长度。（多次读盘）根据下一块号读块至内存缓冲区根据块内位移长度取出要读的内容，送至参数中的内存目的地址根据块内长度或起始块号+块数，确定还读下一块吗？同时确定下一块块号,File Implementation,93,文件共享定义 一个文件被多个用户或程序使用目的 节省时间和存储空间，减少了用户工作量 进程间通过文件交换信息,File Implementation,94,实现方法 由系统目录实现对文件的共享 对要共享的文件进行连接 通过“连接（Link）”命令，在用户自己的目录项中对要共享的文件建立起相应的表目，即建立两个文件的等价关系,File Implementation,95,96,Efficiency and Performance,Efficiency dependent on:disk allocation and directory algorithmstypes of data kept in files directory entry,97,Performancedisk cache separate section of main memory for frequently sued blocksfree-behind and read-ahead techniques to optimize sequential accessimprove PC performance by dedicating section of memroy as virtual disk,or RAM disk.,Efficiency and Performance,98,Various Disk-Caching Locations,Efficiency and Performance,99,一致性检查 安全性写方式 备份,Recovery,100,一致性检查 检查必要性 一种检查方法,Recovery,101,必要性磁盘块内存写回磁盘块在写回之前，系统崩溃，则文件系统出现不一致。因此，需要设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统。,Recovery,102,一种检查方法 两张表，每块对应一个表中的计数器，初值为0。,Recovery,103,104,105,106,107,安全性写方式谨慎写 对写操作进行逐个排序的写方式更新磁盘的请求按一定顺序完成几项子操作更新磁盘FAT文件系统：通写磁盘修改立即写到磁盘 可恢复性好速度性能差,Recovery,108,延迟写利用回写高速缓存的方法得到高速可恢复性差,Recovery,109,可恢复文件系统采用事务日志来实现文件系统的写入既考虑安全性，又考虑速度性能,Recovery,110,Recovery,备份Use system programs to back up data from disk to another storage device(floppy disk,magnetic tape).Recover lost file or disk by restoring data from backup.,