数据项
基本数据项 ：可命名的最小数据单位，原子数据，有数据类型。–数据库中的字段。如：学号、姓名、年龄等。
组合数据项：由若干数据项组成，如工资。
记录：
一组相关数据项集合，用于描述一个对象在某方面的属性。主关键字（关键字）用于标识一个记录。
文件
由创建者定义，具有文件名的一组相关元素的集合。文件名是文件的标识符号。
有结构文件由若干相关记录组成；无结构文件被看成是一个字符流。
标识符：一系统内各文件的标识符唯一，对用户而言没有可读性，因此标识符只是OS用于区分各个文件名的一种内部名称。
类型：表明文件类型
大小：指明文件大小
创建时间，上次修改时间，文件所有者信息
保护信息：对文件进行保护的访问控制信息
无结构文件(流式文件)
有结构文件(记录式文件)
数据项是文件系统中最基本的数据单位
使多个用户可以共享使用一个文件
如何保证不同的用户对文件有不同的操作权限
逻辑结构：用户角度，文件内部的数据应该是如何组织起来的。
物理结构：操作系统角度，文件数据应该如何存放在外存中。
文件内部数据是一系列二进制流或字符流组成。又称为流式文件。
有结构文件
由一组相似的记录组成。又称为记录式文件。每条记录由若干个数据项组成。一般来说，每条记录由一个数据项可作为关键字。
根据各条记录的长度(占用的存储空间)是否相等，可分为定长记录和可变长记录两种。
文件中记录一个接一个地顺序排列(逻辑上)，记录可以是定长或可变长。各个记录在物理上可以顺序存储或链式存储
默认各记录在物理上顺序存储
是否可以进行随机存取
链式存储：无论是定长还是可变长，都无法实现随机存取，每次只能从第一个记录开始依次向后查找
顺序存储
可变长记录：无法实现随机存取，每次只能从第一个记录开始依次往后查找
定长记录：
*考题中顺序文件：*物理上顺序存储的顺序文件。
顺序文件的缺点：增加/删除一个记录比较困难
结论：定长记录的顺序文件，若物理上采用顺序存储，则可实现随机存取；若再能保障记录的顺序结构，则可实现快速检索(根据关键字快速找到对应记录)
为了解决可变长记录在查找第i个记录，必须先查找前i-1个记录
建立一张索引表以加快文件索引速度。每条记录对应一个索引项。索引表项物理上连续存放
文件中的记录在物理上可以离散存放。
索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。
可将关键字作为索引号内容，若关键字顺序排列，则还可以支持按照关键字折半查找。
因此主要用于对信息处理的及时性要求比较高的场合。
此外，可以使用不同的数据项建立多个索引表。
每个记录对应一个索引表项，因此索引表可能会很大。
比如：文件的每个记录平均只占8b，而每个索引项占32字节，那么索引表比文件内容本身大，降低了存储空间利用率。
索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中，同样为文件建立一张索引表，但不像索引文件每个记录对应一个索引表项，而是一组记录对应一个索引表项。
索引表示定长记录的串结构顺序文件。
若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找，平均查找5000个记录
若采用索引顺序文件结构，可把10000个记录分为100组，每组100个记录。则需要先顺序查找索引表找到分组(100个分组，平均查50次)，找到分组后，再在分组中顺序查找记录(每组100个记录,平均查找50次)。可见使用索引顺序文件结构后，平均查找100次。
可以为顺序文件建立多级索引表。
FCB实现了文件名和文件之间的映射，使得用户可以实现按名存取
不使用与多用户操作系统
允许不同用户的文件重名，但是对应不同的文件
需要为每个共享结点设置一个共享计时器，用于记录此时有多少个地方在共享该结点。用户提出删除结点请求时，只是删除该用户的FCB，并使共享计数器减1，并不会直接删除共享结点。
当且仅当共享计时器减为0时，才删除结点。
差别：
共享文件不同于复制文件。在共享文件中，由于各用户指向同一个文件，因此只要其中一个用户修改文件数据，那么所有用户都可以看到文件数据变化。
索引结点：除了文件名之外的文件描述信息都放到索引结点中。每个文件都存在唯一索引结点
文件分配方式
即文件数据应该如何存放在外存中。
操作系统决定
类似于内存分页，磁盘中的存储单元也会被分为一个个"块/磁盘块/物理块"。很多操作系统中，磁盘块的大小与内存块、页面的大小相同
内存与磁盘之间的数据交换(即I/O)都是以块为单位进行的。即每次读入一块，或每次写出一块。
操作系统为文件分配存储空间都是以块为单位。
要求每个文件在磁盘上占有一组连续的块。
物理块号 = 起始块号 + 逻辑块号
当然，还要检查用户提供的逻辑块号是否合法(逻辑块号>=长度 就不合法)
优点
读取某个磁盘块时，需要移动磁头。访问两个磁盘块相隔越远，移动磁头所需的时间就越长。
缺点
物理上采用连续分配的文件不方便扩展。
采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片
可以使用紧凑来处理碎片，但是要耗费很大的时间代价。
采取离散分配的方式，可以为文件分配离散的磁盘块，分为显式链接和隐式链接两种。
题目中未指明显式或隐式则默认链接为隐式链接分配
除了文件的最后一个磁盘块外，每个磁盘块中都会保存指向像一个盘块的指针。这些指针对用户是透明的。
实现文件逻辑块号到物理块号的转变
读入i号逻辑块，总共需要i+1次磁盘I/O
*结论：*只支持顺序访问，不支持随机访问,查找效率低。另外，指向下一个盘块的指针也需要耗费少量存储空间。
需要扩展文件时,随便找到一空闲盘块，挂到文件的磁盘块链尾，并修改文件的FCB。
把用于链接文件各物理块的指针显式地存放在一章表中。即 文件分配表(FAT File Allocation Table)
一个磁盘仅设置一张FAT。开机时将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此物理块号字段可以是隐藏的。
实现文件的逻辑块号到物理块号的转变
结论：采用链式分配(显式链接)方式的文件，支持顺序访问，也支持随机访问，想访问i号块时无需访问之前的0 - i-1号逻辑块，由于块号转换的过程不需要访问磁盘，因此相较于隐式链接，访问速度快很多。
优点
缺点
允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表–建立逻辑页面到物理页面之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。
可以使用固定长度表示物理块号(如：假设磁盘总容量为1TB = 240B,磁盘大小为1KB，共有230个磁盘块，则可用4B表示磁盘块号)，因此索引表中的逻辑块号是隐含的。
实现文件的逻辑块号到物理块号的转换
*索引分配方式可以支持随机访问。文件扩展也很容易实现，(只需要给文件分配一个空闲块，并增加一个索引表项即可)*但是索引表需要占用一定的存储空间。
若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放256个索引项。
若一个文件的大小超过了256块，那么一个磁盘块时装不下文件的整张索引表的，解决问题方法。
链接方案
若索引表太大，一个索引块装不下，那么可以将多个索引表链接起来存放。
建立多层索引(类似于多级页表)。使第一层索引块指向第二层索引块。还可根据经文件大小的要求再建立第三层，第四层索引块。
若采用多层索引，各层索引表大小不能超过一个磁盘块
若某文件采用2层索引，则该文件的最大长度可以达到 256X256X1KB = 64MB
可根据逻辑块号算出应该查找索引表中的哪个表项。
如：要访问1026号逻辑块，则
1026/256 = 4 ,1026%256 = 2
因此可先将一级索引表调入内存，查询4号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号。访问目标数据块，需要3次磁盘I/O
结论：若采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。
缺点：即使是小文件也需要K+1次读磁盘。
若顶级索引表还未读入内存
访问0-7号逻辑块：读2次磁盘
访问8-263号逻辑块：读3次磁盘
访问264-65799号逻辑块：读4次磁盘
对于小文件，只需要较少的读磁盘次数就可以访问目标数据块。
逻辑结构：用户角度，文件内部的数据应该是如何组织起来的。 用户决定文件如何存储。
物理结构：操作系统角度，文件数据应该如何存放在外存中。**OS决定文件内容如何存在盘块上。
顺序文件可采用顺序存储/链式存储。
链式存储的顺序文件采用链接分配
对OS而言，盘块内容无意义。按照盘块大小拆分后，进行数据读取即可。
将物理磁盘划分为一个个的文件卷(逻辑卷，逻辑盘)。
文件区用于存放文件数据
适用于连续分配方式
如何分配磁盘块：与内存管理中的动态分区分配类似，为一个文件分配连续的存储空间。同样可以采用首次适应，最佳适应，最坏适应等算法来决定要为文件分配哪个区间。
如何回收磁盘块：与内存管理中的动态分区分配类似，当回收某个存储区时有4种情况。
注意表项合并问题
空闲盘块链
以盘块为单位组成一条空闲链
适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。
由操作系统保存链头，链尾指针。
如何分配：若文件申请K个盘块，则从头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
空闲盘区链
以盘区为单位组成一条空闲链
盘区：连续的空闲盘块
离散，连续分配都适用。为一个文件分配多个盘块时效率更高
由操作系统保存链头，链尾指针。
如何分配：
若某文件申请K个盘块，则可以采用首次适应，最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘块区，分配给文件。
若没有合适的连续空闲块，也可将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针，盘区大小等数据。
如何回收：
若会收区与某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若会收取没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
每个二进制位对应一个盘块。本例中，0代表盘块空闲，1代表盘块已分配。位示图一般用连续的字来表示，如本例中一个字的长度为16位。字中每个位对应一个盘块。因此可以用*(字号，位号)对应一个盘块号。有些题目中也称为(行号，列号)*
一个字长一行
连续分配，离散分配都适用
需要自己能推出盘块号与(字号，位号)相互转换的公式
*注意：*盘块号，字号，位号到底是从0开始还是1开始。
如何分配：
若文件需要K个块
如何回收
空闲表法，空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采取了成组链接法对磁盘空闲块进行管理。
空闲盘块的组织
每个超级块第一个位置存放下一个空闲盘块的盘块号；每个超级块内的空闲盘块号可不连续
最后一个超级块的容量比其他的少
如何进行磁盘块分配：
需要一个空闲块
需要100个空闲块
如何回收
假设每个分组最多100个空闲块，此时第一个分组已经有99个块，还要回收一块。
将空闲块插到第一组中
假设此时第一个分组已满，还要再回收一块。
需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。
调用Create系统调用
需要提供的参数：
OS在处理Create系统调用时的主要操作：
调用delete系统调用
需要提供的参数：
操作系统在处理Delete系统调用时的主要操作：
需要提供的参数：
操作系统在处理Open系统调用时的主要操作：
打开文件时，并不会吧文件数据直接读入内存。索引号也称为文件描述符
操作系统在处理Close系统调用时的主要操作：
需要指明是哪个文件，还需指明要读入多少数据，指明读入的数据要放在内存中的什么位置。
操作系统在处理Read系统调用时的主要操作：
需要指明是哪个文件，还需要指明要写出多少数据，写回外存的数据要放在内存中的什么位置。
操作系统在处理Write系统调用时的主要操作：
操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件。
基于索引结点的共享方式(硬连接)
基于符号链的共享方式(软连接)
多个用户共享同一个文件，意味着系统中只有一份文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。
多个用户都复制了同一个文件，那么系统中会有好几份文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。
基于索引结点的共享方式。
若count > 0 ，说明还有别的用户要使用该文件，暂时不能吧文件数据删除，否则会导致指针悬空。
若 count=0时，系统负责删除文件。
记录某个文件的存放路径。类似快捷方式。 Link类型
在一个Link型的文件中记录共享文件的存放路径
操作系统根据路径层层查找，最终找到共享文件。
即使软链接指向的共享文件已删除，Link类型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败。
保护文件数据安全
文件不受物理损坏
避免文件被非法访问
为文件设置一个口令，用户请求访问该文件时必须提供口令。
口令存放于系统中
口令一般存放在文件对应的FCB或者索引结点中。用户访问文件前需要先输入口令，操作系统会将用户提供的口令与FCB中存储的口令进行对比，若正确，则允许该用户访问文件。
优点：保存口令的空间开销不多，验证口令的时间开销也小。
缺点：正确的口令存放在系统内部，不够安全。
使用某个密码对文件进行加密，在访问文件时需要提供正确的密码才能对文件进行正确的加密。
*优点：*保密性强，不需要再系统中存储密码
*缺点：*编码/译码，或者说加密/解密需要花费一定时间。
在每个文件的FCB(或所有结点)中增加一个访问控制表(Access-Control List，ACL)，该表中记录各个用户可以对该文件执行哪些操作。
计算机中可能有多个用户，因此访问控制列表可能会很大，可以使用精简的访问列表解决该问题。
精简的访问列表：以组为单位，标记各组用户可以对文件执行哪些操作。
如：分为系统管理员，文件主，文件主的伙伴，其他用户 几个分组
当某用户想要访问文件时，系统就会检查该用户所属的分组是否有相应的访问权限。
需要非本组权限，则修改该文件分组。
*优点：*实现灵活可以实现复杂的文件保护功能。
**用户接口：**需要向上层的用户提供一些简单易用的功能接口。该层就是用于处理用户发出系统调用的请求(Read,Write等)。
**存取控制模块：**为了保证文件数据安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能。
磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。
磁道是一圈一圈的。
每个磁道被划分为扇区，每个扇区就是一个磁盘块。每个扇区的数据量相同。对应的每个磁道的数据量相同。越靠近内侧磁道密度越大。
所有盘面中相对位置相同的磁道组成柱面。
每个磁盘片的一面称为一个盘面。
可用*(柱面号，盘面号，扇区号)来定位任意一个磁盘块*，在文件的物理结构中，提到的文件数据存放在外存的几号块，就可以转换成(柱面号，盘面号，扇区号)。
可更换盘磁盘
固定盘磁盘
寻道时间：在读/写数据前，将磁头移动到指定磁道所花的时间。
启动磁头臂需要时间，假设耗时为s；
移动磁头也是需要时间的。假设磁头匀速移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道。
寻道时间 = s + mn
延迟时间：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。假设磁盘转速为r(转/s)，则
平均旋转延迟时间 = (1/2)*(1/r) = 1/2r
传输时间：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘的转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。
传输时间 = (1/r)*(b/N)
总的平均存取时间 = 寻道时间 + 平均旋转延迟时间 + 传输时间
延迟和传输时间 操作系统无法优化
根据进程请求访问磁道的先后顺序进行调度
*优点：*公平，如果请求访问的磁道比较集中的话，算法性能还可。
*缺点：*如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则FCFS在性能上很差，寻道时间长。
优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。贪心算法
*优点：*性能较好，平均寻道时间短；
*缺点：*可能产生饥饿现象。产生饥饿原因：磁头在一个小区域内来回地移动
SCAN算法思想：只有磁头移动到最外侧磁道时候才能往内移动，移动到最内侧磁道的时候才能往外移动。也叫电梯算法。
*优点：*性能较好，平均寻道时间较短，不产生饥饿现象
缺点：
如果在移动方向上已经没有别的请求，就可以立即改变磁头方向。(边移动边观察)。
*优点：*使得寻道时间进一步缩短。
解决对于各个磁道的响应频率不平均。
只有磁头朝特定方向移动时候才处理磁道访问请求，返回时直接快速移动至起始端而不处理任何请求。
优点：比起SCAN来，对于各个位置磁道的响应频率很平均
缺点： 只有到达最边上的磁道时才能改变磁头方向；并且返回时候不需要返回到最边缘的磁道。比起SCAN，平均寻道时间更长。
在C-SCAN算法的基础上，若磁头移动方向上已经无磁道访问请求，则立即让磁头返回。并且磁头只需要返回到有磁道访问请求的位置即可。
若无特别说明：SCAN就是LOOK算法 C-SCAN 就是 C-LOOK算法
采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。
问题：
结论：磁头读入一个扇区数据后需要1小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的延迟时间。
(00,000,000) - (00,000,111) 转2圈可读完
(00,001,000) - (00,001,111) 需要启动磁头臂，将磁头移动到下一个磁道
若相邻盘面的相对位置相同处扇区编号相同
会增加延迟时间。
采用错位命名时
计算机开机工作时，需要进行一系列初始化的工作，这些初始化工作是通过执行初始化程序(自举程序)完成的。
初始化程序可以存放在ROM中。ROM中的数据在出厂时候就写入了，并且以后不能再修改
完整的自举程序放在磁盘的启动块(即引导块/启动分区)上，启动块位于磁盘的固定位置。
无法正常使用的扇区就是坏块。属于硬件故障，操作系统无法修复。应将坏块标记出来，以免错误的使用到它。
简单的磁盘，进行逻辑格式化时(建立文件系统时)对整个磁盘进行坏块检查，标明哪些扇区是坏扇区。比如在FAT上标明。(坏块对OS不透明)
对于复杂的磁盘，磁盘控制器(磁盘设备内部的一个硬件部件)会维护一个坏块链表。在磁盘出厂前进行低级格式化(物理格式化)时就将坏块链进行初始化。
并保留一些备用扇区，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对OS透明
因篇幅问题不能全部显示，请点此查看更多更全内容