文件系统将其管理的程序和数据通过组织为一系列文件。
文件是具有文件名的若干相关元素的集合。
元素通常是记录。
记录是一组有意义的数据项的集合。

数据项
1）基本数据项（字段）：数据名+数据类型。
2）组合数据项：由若干个基本数据项组成。

记录
一组相关数据项的集合
关键字

文件
在有结构的文件中，文件由若干个相关记录组成
在无结构的文件，文件由字符流组成
文件的属性：
文件类型；文件长度；文件的物理位置；文件的建立时间（最后一次修改的时间）

文件名和扩展名

文件类型
按用途分：系统文件/用户文件/库文件
按文件中数据的形式分：源文件（ASCII码或汉字）/目标文件/可执行文件
按存取控制属性分：只执行文件/只读文件/读写文件
按组织形式和处理方式分：普通文件（由ASCII码或二进制组成的字符文件，一般用户建立的源程序文件，数据文件，操作系统自身代码文件，使用程序等都是普通文件）/目录文件（由文件目录组成，通过目录文件可以对其下属文件的信息进行检索）/特殊文件（只系统中的各类I/O设备，对这些文件的操作将由设备驱动器来完成）

pic
文件管理系统管理的对象：
文件
目录：方便用户对文件的存取和检索。每个目录项中必须含有文件名，对文件属性的说明，以及该文件所在的物理地址（指针）
磁盘（磁带）存储空间

对对象操纵和管理的软件集合
该层是文件管理系统的核心部分。
功能：（1）对文件存储空间的管理（2）对文件目录的管理（3）用于将文件的逻辑地址转换为物理地址的机制（4）对文件读和写的管理（5）对文件的共享与保护
把与文件系统有关的软件分为四层
1）I/O控制层（主要由磁盘驱动程序组成）
2）基本文件系统层（主要用于处理内存与磁盘之间数据块的交换）
3）基本I/O管理程序（完成与磁盘I/O有关的事务）
4）逻辑文件系统（处理与记录和文件相关的操作）

文件系统的接口
1）命令接口：用户与文件系统直接交互的接口，用户可通过键盘终端键入命令取得文件系统的服务。
2）程序接口：用户程序与文件系统的接口，用户可通过系统调用取得文件系统的服务。

文件操作
创建文件（分配外存空间，建立目录项）；删除文件；读文件；写文件；设置文件的读/写位置（通过设置文件读/写指针的位置，以便读/写文件时不再每次都从始端开始，而是从设置的位置开始，该顺序存取为随机存取）
文件的打开和关闭操作：当用户要求对一个文件实施多次读/写或其它操作时，每次都要从检索目录开始。为了避免多次重复低检索目录，引入了“打开”这一文件操作。
打开：系统将指明文件的属性（包括文件在外存上的位置），从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或索引号）返回用户。-》建立起一个连接，此后用户可通过该连接直接得到文件信息。
关闭：断开此连接，OS会把该文件从打开文件表中的表目上删掉。

有结构文件（记录式文件）：每个记录都用于描述实体集中的一个实体；分为定长记录（所有记录中的各数据项都处在记录中的相同位置，文件长度用记录数目表示）和变长记录（记录中所包含的数据项数目并不相同或数据项本身长度不定）；用于大量的信息管理系统和数据库系统中。
无结构文件（流式文件）：用于系统中运行的大量的源程序，可执行文件，库函数等；利用读写指针来指出下一个要访问的字符。

文件的逻辑结构（文件组织）
顺序文件：由一系列记录按某种顺序排列所形成的文件，其中的记录可以是定长记录或可变长记录。
索引文件：为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对记录的检索速度。
索引顺序文件：索引表中的表项并不是一个记录而是一组记录中的第一个记录（组索引，组内顺序）

顺序文件

顺序文件的排列方式：
1）串结构：通常按存入时间的先后进行排序，检索时每次都要从头开始，逐个记录的查找。
2）顺序结构：按关键字来排序，可有更高的检索速度和效率。

顺序文件的最佳应用场合是在对文件中的记录进行批量存取时；此外对于顺序存储设备（如磁带），也只有顺序文件才能被存储和有效工作；
在交互应用场合时，用户要求查找或修改单个记录，系统需要在文件的记录中逐个查找；
想增加或删除一个记录比较困难，为了解决这一问题可以为顺序文件配置一个运行记录文件（Log file）或称事务文件，把试图增加，删除或修改的信息记录于其中，每隔一定时间，将运行记录文件与原来的主文件合并，产生一个按关键字排序的新文件。

记录寻址
1）隐式寻址方式
对于定长记录的文件：读指针Rptr，指向下一个记录的首地址，每当读完一个文件Rptr+=L（记录长度），同理写指针Wptr
对于变长记录的文件：每次都需要从正在读写的记录中读出该记录的长度，然后+Li；如果要访问记录i，就必须扫描一遍0~i-1记录。

2）显式寻址方式
用于对定长记录文件实现直接或随机访问，因为任何记录的位置都很容易通过记录长度计算出来。
1）通过文件中记录的位置Ai=i*L
2）利用关键字（比如对目录的检索）

索引文件
建立一张索引表（记录在逻辑地址空间的首址+记录长度L）
索引表按关键字排序，因此其本身也是一个定长记录的顺序文件。
不同用户，为了不同的目的，希望按不同的属性来检索一条记录，需要为顺序文件建立多个索引表，每一种可能称为检索条件的域（属性或关键字）都配置一张索引表。

索引顺序文件
对顺序文件的一种改进，保留了顺序文件的记录按关键字的顺序组织起来的特征，又引入了文件索引表（实现随机访问）和溢出文件（记录新增加的，删除的和修改的记录）

一级索引顺序文件
将记录分为若干组，索引表的表项指向每组的第一个记录。平均查找记录数N/2-》根号N

两级索引顺序文件
低级索引表中的表项再分一次组-》高级索引表
根号N-》3/2*N^(1/3)

直接文件：根据给定的关键字直接获得指定记录的物理地址
典型的直接文件就是哈希文件，利用Hash函数（散列函数）
为了能实现文件存储空间的动态分配，通常由Hash函数所求得的并非是相应记录的地址，而是指向某一目录表相应表目的指针，该表目的内容指向相应的记录所在的物理块。

文件目录
一种数据结构，用于标识系统中的文件及物理地址，供检索时使用。
1）实现按名存取
2）提高对目录的检索速度
3）文件共享（在外存中保留一份该文件的副本供不同的用户使用）
4）允许文件重名
文件控制块的有序集合称为文件目录
一个文件目录也被看做一个文件，称为目录文件

文件控制块FCB
文件名；文件物理位置；文件逻辑结构（流式/记录式）；文件物理结构（顺序/链接式/索引）；存取控制信息（文件主的存取权限；核准用户的存取权限；一般用户的存取权限）；使用信息（建立日期和时间；上一次修改日期和时间；当前使用信息）

文件目录通常是存放在磁盘上的，在查找目录的过程，必须先将存放目录文件的第一个盘块中的目录调入内存，若未找到指定文件，还需将下一盘块的目录调入，假设目录文件占N个盘块，查找一个目录项平均需要调入盘块（1+N）/2次
目录文件中项是FCB，但实际上查找时只会用到FCB中的文件名，其它信息根本不需要被调入。
因此有的系统便把文件名与文件描述信息分开，使文件描述信息单独形成一个索引结点，目录项由文件名和指向对应结点的指针组成。
磁盘索引结点（包含FCB的一部分）
内存索引结点：存放在内存中的索引节点，当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中，并新增了一些内容（索引结点编号，状态，访问计数，文件所属文件系统的逻辑设备号，链接指针）

简单的文件目录

1.单级文件目录
整个文件系统中只建立一张目录表
2.两级文件目录
每个用户一个单独的用户文件目录UFD
系统中一个主文件目录MFD（用户名+指向该用户目录文件的指针）

树形目录
数据文件称为树叶，其它的目录均作为树的结点，或称为子目录。
一个目录文件中的目录项，即可以作为目录文件的FCB，又是数据文件的FCB
pic
路径名：比如1中的用户B访问文件J：/B/F/J
基于当前目录（工作目录）的相对路径名

目录操作
创建目录；删除目录（不删除非空目录，可删除非空目录）；改变目录；移动目录；链接操作（让指定文件有多个父目录，实现文件共享）；查找。

目录查询技术
1）线性检索法
pic

2）Hash方法
Hash索引文件目录，发生冲突时，再将Hash值加上一个常数。

文件共享
1）利用有向无循环图DAG
一个文件可以有多个父目录
由于记录的是文件的物理地址，当文件新增内容后，新增的盘块只会出现在执行了操作的目录中，即新增的这部分内容不能被共享。

2）利用索引结点
文件的物理地址以及其它的文件属性等信息，不再放在目录项中而是放在索引结点中，文件目录中只设置文件名及指向相应索引结点的指针。
这样就可以解决上面那个新增内容无法共享的问题。

3）利用符号链接
允许一个文件或子目录有多个父目录，但仅有一个作为主父目录（实线），其它几个父目录（虚线）都是通过符号链接方式与之相链接（链接父目录）
pic
只是文件主才拥有指向其索引结点的指针，而共享该文件的其它用户只有该文件的路径名。这样就不会发生文件主删除一共享文件后留下一悬空指针的情况。
但不太好的地方是，路径是从根开始的访问时要多次读盘，然后每个共享文件有多个文件名，遍历整个文件系统时会被遍历到多次。

文件保护
人为因素，系统因素，自然因素
通过存取控制机制，采取系统容错技术，建立后备系统

访问权：一个进程能对某对象执行操作的权力
常用有序对（对象名，权集）来表示，（F1，{R/W}）

保护域：进程对一组对象的访问权的集合（F1[R],F2[R]）

进程和域间的静态联系
一个进程只联系着一个域，在进程的整个生命周期中，其可用资源是固定的。
进程和域间的动态联系
一个进程可以联系着多个域。可将进程的运行分为若干个阶段，每个阶段联系着一个域。
增设了保护域切换功能。

具有域切换权的访问矩阵
当且仅当switch∈access(i,j)时，才允许进程从域i切换到域j

拷贝权
如果access(i,j)带星号的话可将在某个域中所拥有的访问权扩展到同列的其它域中
拷贝后的副本不具有拷贝权（限制拷贝）

所有权
如果access(i,j)拥有所有权（用O来表示）的话，则在Di上运行的进程可以增加或删除其在j列上任何项的访问权
pic

控制权
access(Di,Dj)：在Di运行的进程可以改变D3中的各项访问权

访问矩阵的实现
以上的矩阵形式会导致系数矩阵，浪费空间。可以将访问矩阵按列划分形成访问控制表，或按行划分形成访问权限表。
1）访问控制表ACL（谁可以控制我）：表项是有序对（域，权集），还可以定义缺省访问权集。
2）访问权限表（我可以控制谁）：表项是类型+权限+对象（指向相应对象的指针）
访问权限表不能允许直接被用户（进程）所访问。
当一个进程首次去访问一个对象时，先检查是否有访问权，有的话就建立一访问权限，进程直接利用这一返回的权限去访问该对象，当进程不需要对该对象进行访问时，撤销该访问权限。