1、6.3.3 文件的物理结构,辑上的文件总得以不同方式保存到物理存储设备的存储介质上去，所以，文件的物理结构和组织是指逻辑文件在物理存储空间中存放方法和组织关系。这时，文件看作为物理文件，即相关物理块的集合。文件的存储结构涉及块的划分、记录的排列、索引的组织、信息的搜索等许多问题。因而，其优劣直接影响文件系统的性能。,第一类称计算法，其实现原理是设计一映射算法，例如线性计算法、杂凑法等，通过对记录键的计算转换成对应的物理块地址，从而找到所需记录。直接寻址文件、计算寻址文件，顺序文件均属此类。计算法的存取效率教高，又不必增加存储空间存放附加控制信息，能把分成布范围较广的键均匀地映射到一个存储区域中
2、。第二类称指针法，这类方法设置专门指针，指明相应记录的物理地址或表达各记录之间的关联。索引文件、索引顺序文件、连接文件、倒排文件等均属此类。,两类方法可用来构造文件的物理结构,顺序文件(连续文件 ),将一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块上便形成顺序结构，这类文件叫顺序文件，又称连续文件。这是一种逻辑记录顺序和物理记录顺序完全一致的文件，通常，记录按出现的次被读出或修改。,顺序文件的基本优点是：顺序存取记录时速度较快。顺序文件的主要缺点是：建立文件前需要能预先确定文件长度，以便分配存储空间；修改、插入和增生文件记录有困难；对直接存储器作连续分配，会造成少量空闲块的浪费。,紧凑
3、顺序文件扩展顺序文件连接顺序文件划分顺序文件,连接文件(串联文件),连接结构的特点是使用连接字，又叫指针来表示文件中各个记录之间的关系,连接文件结构示意图,引进指向其它数据的连接表示是计算机程序设计的一种重要手段，是表示复杂数据关系的一种重要方法。仅适宜于顺序存取。连接结构恰好克服了顺序结构不适宜于增、删、改等的固有缺点，对某些操作带来很大好处，但在其它方面又失去了一些性能。,l堆栈其所有记录的插入和删除操作只能在同一端进行，这一端称栈顶。堆栈中一个后进先出型数据结构，这是因为后进入栈的记录，一定比先进入栈的所有记录先退出栈。堆栈运算有特殊的名称，把一个新的记录插入栈中，使之成为栈的新顶项叫下
4、推运算；反之，删除栈顶记录叫上推运算，大多数上推需要读取顶项记录以便运算。l队列其记录的插入在后端进行，而删除在前端进行，又叫先进先出型数据结构。l两端队列左右两端均可进行插入和删除记录操作的队列。,直接文件,记录的关键字与其地址之间可以通过某种方式建立对应关系，利用这种关系实现存取的文件叫直接文件。,1. 选择转换(hash)函数,这里采用它文件名的各字符ASC2码值求和的方法,得到关键字k,再用取余数方法求出哈希值。 K=(a0+a1+an) mod 28 ai=文件名的各字符ASC2码值 a=(k) mod 43 取质数43除k可得到均匀的地址分布。,2. 建立目录文件,目录文件采用索引
5、结构，建立文件时根据hash函数求出a,凡a值相同的文件的文件目录项都存入同一个盘区内。,3 查找文件目录过程,按给定文件名,用hash函数求出哈希值a,再以a为位移找出该文件目录存放的物理块号,把这个块读进内存缓冲区,然后用文件名依次比较,找出要求的文件目录项。,4溢出处理,盘块中能存放的文件目录数有限，建立文件时，若a值相同的文件数超过一个盘块能容纳的数目时，产生冲突。这时，系统再申请一个盘区，该块号将存入位移为a+43表项内。依次类推。同理，若查找时，第一块找不到，可到a+43表项取出块号，读出第二块盘区继续比较。,索引文件,索引结构是实现非连续存储的另一种方法，适用于数据记录保存有随机
6、存取存储设备上的文件。 它使用了一张索引表，其中每个表目包含一个记录的键及其记录数据的存储地址，存储地址可以是记录的物理地址，也可以是记录的符号地址，这种类型的文件称索引文件。,索引文件在文件存储器上分两个区：索外区和数据区。访问索引文件需两步操作：第一步查找文件索引，第二步以相应键登记项内容作为物理或符号地址而获得记录数据。这样，至少需要两次访问辅助存储器，但若文件索引已预先调入主存储器，那么就可减少一次内外存信息交换。,索引结构是连接结构的一种扩展，除了具备连接文件的优点外，还克服了它只能作顺序存取的缺点，具有直接读写任意一个记录的能力，便于文件的增、删、改。索引文件的缺点是：增加了索引表
7、的空间开销和查找时间，索引表的信息量甚至可能远远超过文件记录本身的信息量。,索引文件中的索引项可以分为两类：,稠密索引 稀疏索引,索引顺序文件,提高查找速度的办法,做一个索引的索引，叫二级索引。二级索引表的表项列出一级索引表每一块最后一个索引项的键值及该索引表区的地址，也就是说，若干个记录的索引本身也是一种记录。查找时先查看二级索引表找到某键所在的索引表区地址，再搜索一级索引表找出数据记录。当记录数目十分大时，索引的索引也可能占用许许多多块，那样，可以做索引的索引的索引，叫三级索引。,Linux的多重索引结构,6.4文件的保护和保密,6.4.1 文件的保护文件保护是指防止文件被破坏，它包括两个
8、方面：一是防止系统崩溃所造成的文件破坏；二是防止其他用户的非法操作所造成的文件破坏。,定时转储,系统的管理员每隔一段时间，或一日、或一周、或一月、或一个期间，把需要保护的文件保存到另一个介质上，以备数据破坏后恢复。,把重要的数据存放在不同的物理磁盘、乃至不同的联网计算机上，这样系统崩溃造成文件破坏后，系统完全可以从另一个文件副本中读取数据。多副本技术的实现又分为静态多副本和动态多副本，静态多副本实现的代价较小，但不能做到多个副本的完全同步。基于文件的多副本技术的实现，特别是动态多副本的实现较为复杂，开销很大，因此现代操作系统和数据库系统往往采用磁盘冗余的方法实现多副本，即两个磁盘存放同样的信息
9、，如磁盘镜像技术和RAID5技术。,多副本技术,通过操作系统的安全性策略来实现，其基本思想是建立如下的三元组：（用户、对象、存取权限） 其中：l用户是指每一个操作系统使用者的标识。l对象在操作系统中一般是文件，因为操作系统把对资源的统一到文件层次，如通过设备文件使用设备、通过socket关联文件使用进程通信等。l存取权限定义了用户对文件的访问权，如：读、写、删除、创建、执行等等。一个安全性较高的系统权限划分的较多较细。,防止其他用户的非法操作所造成的文件破坏,存取控制矩阵,包括两个维，一维列出所有用户名，另一维列出全部文件，矩阵元素的内容是一个用户对于一个文件的存取权限,入存取控制表,为节省存
10、储、方便实现，可以把取控制矩阵线性化成存取控制表,更好的解决方案,可以把用户划分为几类，如：文件属主、合作者、其他用户，规定这几类用户对文件的存取权限并把它保存在文件目录项中，称之为文件属性。以Unix和Linux为例，它把用户分为属主、同组用户、其他用户三类，分别定义存取权限可读r、可写w、可执行x，目录项中的文件属性共有10位：-rwxrwxrwx,6.4.2文件的保密,文件保密的目的是防止文件被窃取。主要方法有设置口令和使用密码。,口令分成两种：文件口令是用户为每个文件规定一个口令，它可写在文件目录中并隐蔽起来，只是提供的口令与文件目录中的口令一致时， 才能使用这个文件。另一种是终端口令
11、，由系统分配或用户预先设定一个口令，仅当回答的口令相符时才能使用该终端。但是它有一个明显的缺点，当要回收某个用户的使用权时，必须更改口令，而更改后的新口令又必须通知其他的授权用户，这无疑是不方便的。使用密码是一种更加有效的文件保密方法，它将文件中的信息翻译成密码形式，使用时再解密。在网络上进行数据传输时，为保证安全性，经常采用密码技术；进一步还可以对在网络上传输的数字或模拟信号采用脉码调制技术，进行硬加密。,6.5文件系统其他功能的实现,6.5.1 文件操作的实现文件系统提供给用户程序的一组系统调用，包括：建立、打开、关闭、撤销、读、写和控制，通过这些系统调用用户能获得文件系统的各种服务。,建
12、立文件,当用户要求把一批信息作为一个文件存放在存储器中时，使用建立操作向系统提出建立一个文件的要求。用户使用建立系统调用时，通常应提供以下参数：文件名、设备类（号）、文件属性及存取控制信息，如：文件类型、记录大小、保护级别等。文件系统完成此系统调用的主要工作是：l根据设备类（号）在选中的相应调设备上建立一个文件目录，并返回一个用户文件标识，用户在以后的读写操作中可以利用此文件标识；l将文件名及文件属性等数据填入文件目录；l调用辅存空间管理程序，为文件分配第一个物理；l需要时发出装卷信息（如磁带或可磁盘组）；l在活动文件表中登记该文件有关信息，文件定位，卷标处理；操作系统中，可以隐含的执行建立操
13、作，即当系统发现有一批信息要写进一个尚未建立的文件中时，就自动先建立文件，完成上述步骤后，接着再写入信息。,打开文件,文件建立之后能立即使用，要通过打开文件操作建立起文件和用户之间的联系。打开文件常常使用显式、即用户使用打开系统调用直接向系统提出。用户打开文件时需要给出文件名和设备类（号）。文件系统完成此系统调用的主要工作是：l在主存活动文件表中目录申请一个空项，用以存放该文件的文件目录信息；l根据文件名查找目录文件，将找到的文件目录信息复制到活动文件表占用栏；l若打开的是共亨文件，则应有相应处理，如使用共亨文件的用户数加；l文件定位，卷标处理；文件打开以后，直至关闭之前，可被反复使用，不必多
14、次打开，这样做能减少查找目录的时间，加快文件存取速度，从而，提高文件系统的运行效率。,读写文件,文件打开以后，就可以用读写系统调用访问文件，调用这两个操作，应给出以下参数：文件名、主存缓冲地址、读写的记录或字节个数；对有些文件类型还要给出读写起始逻辑记录号。文件系统完成此系统调用的主要工作是：l按文件名从活动文件表中找到该文件的目录项：l按存取控制说明检查访问的合法性；l根据目录项指出的该文件的逻辑和物理组织方式将逻辑记录号或个数转换成物理块号；l向设备管理程序发I/O请求，完成数据交换工作。,关闭文件,当一个文件使用完毕后，使用者应关闭文件以便让别的使用者用此文件。关闭文件的要求可以通显式，
15、直接向系统提出；也可用隐含了关闭上次使用同一设备上的另外一个文件时，就可以认为隐含了关闭上次使用过的文件要求。调用关闭系统调用的参数与打开操作相同。文件系统完成此操作的主要工作是：l将活动文件表中该文件的当前使用用户减；若此值为，则撤销此表目；l若活动文件表目内容已被改过，则应先将表目内容写回文件存储器上相应表目中，以使文件目录保持最新状态；l卷定位工作。,撤销文件,当一个文件不再需要时，可向系统提出撤销文件，该系统调用所需的参数为文件名和设备类（号）。撤销文件时，系统要做的主要工作是：l若文件没有关闭，先做关闭工作；若为共亨文件，应进行联访处理；l在目录文件中删去相应目录项；l释放文件占用的
16、文件存储空间。,6.5.2 文件操作的执行过程,用户接口 接受用户发来的文件系统调用，进行必要的语法检查，根据用户对文件的存取要求，转换成统一的内部系统调用，并进入逻辑文件控制子系统。逻辑文件控制子系统 根据文件名或文件路径名，建立或搜索文件目录，生成或找到相应文件目录项，把有关信息复制到活动文件表中，获得文件内部标识，供后面存取操作使用。此外，根据文件结构和取方法，把指定的逻辑记录地址换成相对物理块内相对地址。文件保护子系统 根据活动文件表相应目录项识别调用者的身份，验证存取权限，判定本次文件操作的合法性。,物理文件控制子系统 根据活动文件表相应目录项中的物理结构信息，将相对块号及块内相对地
17、址转换为文件存储器的物理块号和块内相对地址。本子系统还要负责文件存储空间的分配，若为写操作，则动态地为调用者申请物理块；实现缓冲区信息管理。根据物理块号生成I/O控制系统的调用形式。I/O控制系统 具体执行I/O操作，实现文件信息的存取。这一层属于设备管理功能。,6.5.3 辅存空间管理,辅存空间分配常采用以下两种办法。l连续分配：文件被存放在辅存空间连续存储区中，在建立文件时，用户必须给出文件大小，然后，查找到能满足的连续存储区供使用；否则文件不能建立，用户进程必须等待。连续分配的优点是文件查找速度快，管理较为简单，但为了获得足够大的连续存储区。需定时进行碎片收集。因而，不适宜于文件频繁进行
18、动态扩充和缩小的情况，用户事先不知道文件长度也无法进行分配。l非连续分配：一种非连续分配方法是以块（或扇区）为单位，按文件动态要求分配给它若干扇区，这些扇区不一定要连续，属于同一文件的扇区按文件记录的逻辑次序用链指针连接或用位示图指示。另一种非连续分配方法是以簇为单位，簇是由若干个连续扇区组成的分配单位；实质上是连续分配和非连续分配的结合。各个簇可以用链指针、索引表，位示图来管理。非连续分配的优点是辅存空间管理效率高，访问文件执行速度快，特别是以簇为单位的分配方法已被广泛使用。,辅存空间管理,字位映象表（位示图）空闲区表空闲块链,Unix采用的是空闲块成组连接法,存储空间分成512字节一块。为讨论方便起见，假定文件卷启用时共有可用文件438块，编号从12至349。每100块划分一组，每组第一块登记下一组空闲块的盘物理块号和空闲总数。,
