【操作系统】第十二章：文件系统和I/O设备

青衣

　　
　　OS.StudyLog.Ch12.File Syste.文件系统

• 基本概念
  
• 文件描述符
  
• 数据缓存
  
• 文件分配
  
• 空闲空间列表
  
• RAID 多磁盘管理-冗余磁盘阵列
  
• 磁盘调度
  
• 
  
  
  
  • FIFO先进先出
    
  • 最短服务优先
    
  • SCAN扫描法
    
  
  

　　
OS中很重要的子系统。用于完成永久存储介质中数据的保存与恢复，能够更加方便地访问存储介质中的数据。文件系统和IO是计算机原理中的知识，这里可能会有一些重叠，可以选择性参照
文件系统章节是一个了解性的章节，没有深入探讨。基本概念

　　文件系统是用于持久性存储（硬盘、闪存等掉电后数据不消失的存储介质///内存掉电会丢失内存中数据）的系统抽象。简单来说就是要把数据更加方便的存在我们硬盘上。
文件系统要给用户提供便捷方便的数据访问手段，要考虑如何组织、控制、查询、访问等。大到服务器，小到嵌入式系统，通常用的WIN图形界面机，要保存数据到永久储存介质上就一定会用到文件系统，只是针对不同的应用特征和物理介质特征，文件系统相应特点不同而已。
文件是文件系统中表示数据的基本单元，对于OS而言是抽象的，一个文件系统有一堆文件。
　　文件是展现给用户看到的抽象的概念，对应到永久存储，对于硬盘而言，文件是什么呢？

文件有文件名、存储的数据、位置等各种属性构成，在磁盘空间里，为了能够有效抽象文件，需要文件块。类似于PCB进程控制块一样，需要文件块来管理文件的内容、空间的管理（内容放在哪）、如果有分配需要从哪取得文件信息及分配算法等）。
从用户层面，用户访问文件需要定位文件、命名文件（通过文件名和路径能够找到文件）、分层文件系统系统 （类似于图书馆，找具体一本书需要一级一级去找）。因为文件是放在硬盘上的数据，数据本身是可以被其他进程访问到的，那么要提供一定程度的保护来保证某些特定用户的文件不被其他人访问，以及设置共享文件等。主要是关于文件读写的可靠性也是文件系统需要考虑的内容，是否支持同时写等。
　　站在文件角度：一个文件为了更好的表征数据内容（名称类型位置大小）在文件粒度上的保护措施和属性都应该有，便于检索。这属于文件信息，这些信息我们称之为语言数据信息，会保存在文件头或者文件控制块里，用于表征文件的基本属性。
文件分为两种状态，一种是存储时的组织和描述方式，一种是打开在内存的组织和描述方式。
文件描述符

　　文件描述符不是用户直接看到，而是编程者角度。我们打开一个文件，可以取名（字符串），而为了方便读写处理，会在编程时返回一个文件描述符，是一个整形的数。这个数就代表一个文件，这个f是一个整形数，read会读出文件的内容，close会关掉文件。这个流程里很重要的参数就是文件描述符，它代表文件给应用程序做各种各样的访问和控制。这个整数f是对应到OS内核里的【打开文件表】。打开文件表包含了所有进程打开的文件。这个文件描述符就是一个索引，指出了文件表中的某一项，每一个项包含了文件的元素和信息。
　　为了更好地管理文件，需要内核中的：

文件的元数据信息：
文件指针：指向当前最近的一次读写的位置。
文件打开计数：多少进程打开了这个文件，记录了文件打开的次数。一般来说打开了文件就不能把文件信息从内存中抹去，只有当所有进程关闭这个文件，没有进程要访问这个文件时，我们才允许把文件相关的信息从打开文件表里去掉。因为文件是共享资源，允许多个进程打开同一个文件。
文件磁盘位置：打开文件一般是读写文件，我们需要知道文件的位置才能进一步访问磁盘扇区的内容，把内容读入内存来完成对文件的读写。
访问权限：一个程序是否有权限读或写这个文件。

系统视角：字节集合。读写对于字节，在高层OS是不关心存在位置，open read write只不过读写一块缓存。最后由文件系统来把堆在内存中的缓存对应到磁盘中，把关系建立好，来完成对磁盘的读写，从而体现用户对数据的持久访问。
在操作系统内部，很重要的信息就是如何建立磁盘块和文件建立映射关系。一般扇形可能是512byte，对于内存来说，是页（一般4K）。真正读写时更多以字节为单位读写，但是对于磁盘而言是以扇区为单位读写，这种差异性由文件系统管理并屏蔽掉。使得用户角度和高层系统角度不需要关心者之间的关系。

　　例子：

OS不会把磁盘上的2-12字节读出来，文件存储到磁盘上，而磁盘访问的基本单位是扇区，OS会把包含2-12字节的扇区读入内存，读会读1~N个扇区，然后再从缓存中将需要的数据传给用户。这是OS做到事情。

即使完成以字节为单位读写一个字节，也会涉及到读磁盘块。这个需要注意，OS看到是磁盘块，用户看到的是数据（一维的线性空间）
　　访问模式
用户访问文件也存在不同访问模式。
顺序访问：几乎所有访问都是这种方式。
随机访问：可能跳跃性的到处访问文件中不同位置的数据，一些特定的应用也会这样处理。需要考虑的是如何加快访问效率。
基于内容的访问：类似数据库，建议好索引，根据索引查数据。

通过索引找到记录项，为此会访问两个文件。一般文件系统不会做到这一步，如果要完成工作，会把工作交给数据库，数据库或者特定应用来通过不同功能的文件来完成基于内容的查找。
　　文件内部结构：

复杂结构由应用程序识别，对于OS无论是哪种结构，需要一种统一简洁的方式来理解文件内容——字节流。 把它理解为没有任何意义的字节流来完成读写操作，使得OS和应用程序的工作分开 。可以有很复杂的文件，但是这个文件和 特定应用相关和OS无关，大大简化了OS的实现并且使得OS有更多的功能性，并让应用程序根据自己的特定来选择最适合的文件面向应用的表现方式。

在文件访问时，由于文件是共享资源，需要访问控制。对于用户而言能否访问就需要文件访问控制列表来管理。
Unix中比较简单，对于用户会有几个bit来表示读、写、执行来表示可读可写可执行。对于用户有三类，owner,group,others.的权限意味着对于不同的用户可以有不同的访问权限。

语义：简单来说，你写了数据后别人什么时候可以读到，能不能读
多个用户/进程如何同时访问共享文件：文件是资源，如果处理不当会出现死锁，参考读写者问题。
会话语义：打开到关闭这整个过程是一个会话，只有当一个文件做了关闭操作，我们才把它的数据写回硬盘，使得接下来打开文件的进程可以读出这个数据，确保会话结束之前的信息 能够被后来的访问者访问到。
锁：支持共享，锁的粒度不同，锁粒度足够小，只要块之间不重叠，并发写操作也可以执行。OS会提供文件锁来令用户写出更高效的应用程序。

　　目录

　　文件越来越多，如果把所有文件堆在一起形成一个一维展示环境，对于用户访问而言过于困难。所以通过分层的方式，空间整洁有层次，便于查找和组织不同类型的结构。
　　目录可以执行的操作：

可以通过数据结构中不同的对数据组织方式来完成对一个目录中文件的组织。

随着目录一层层深入，这个路径遍历的开销比较大。前工作目录做了缓存，通过这一级开始遍历可以减少开销。
　　文件系统挂载：

系统里，特别是unix系统，不同的文件系统要挂在不同的目录下来形成一个分层次的跨文件系统访问。挂载点在用户看来是一个目录，这个目录比较特别，这是用户视角上的根目录。
　　文件别名

一个文件在不同的用户里有不同的命名，这样便于对文件更好的分类和查找。这种方式在UNIX系统中有两种实现方式，一种是硬链接，一种是软链接。
硬链接：在不同目录中，存的是文件项，文件项虽然不同但是他们指向的都是同一个硬件位置的文件。文件内容是指向文件
软链接：快捷方式。文件的内容存的是另一个文件的路径名

在不同情况下的删除：
软链接：如果是删除了快捷方式的源文件，形成悬空指针。
硬链接：文件包含了特殊的数据结构，记录了引用计数（有多少个不同文件名指向同一个文件），当删除了一个别名文件，只不过是引用计数-1.只有这个计数为0，文件才会彻底删除。

　　循环问题：

文件系统类别

根据不同的应用需求而诞生出不少文件系统。
磁盘文件系统：不多说，最常用的
数据库：WinFS，把文件系统作为数据库的形式展示出来，想法很不错但是很没有成功。
日志文件系统：相对于FAT的掉电丢失数据， NTFS，ext2/3等文件系统增加了日志文件系统的功能，不同于FAT的每次重启check文件系统内容一致性，确保掉电后快速回复。一个读操作或者写操作，如果不能正确完成则不完成。
网络：局域网范围内可以很方便的访问另一个机器的文件。
分布式：典例谷歌文件系统，做一个很大规模的数据存储访问解锁等。利用的网络/计算/数据中心进行高速、高吞吐率、容错的访问。是在网络背景下面向不同系统适应不同应用需求。
虚拟：这种系统不是为了存数据，而是以文件的方式展示读写接口，来交互和访问内核中的数据。想知道当前OS内核里有多少进程，使用了几个CPU时，在UNIX里有专门的文件系统存着所有的这些信息，只要进入就可以看到。

分布式文件系统的传输介质包括网络，网络意味着延迟大，不可靠，访问事件不可控，和单机文件系统中的内部总线相比差多了。这使得网络文件系统需要更好的考虑访问延迟，读写一致性，可靠问题，安全问题等。使得设计和实现上更加复杂，也是当前的热点之一，有兴趣可以找论文拓展学习。
数据缓存

　　访问硬盘的速度和访问内存的速度相差极大，所以为了提高速度，我们会在内存中放一块缓存，把经常用的或者接下利用的放入缓存，可以提高效率。
数据缓存的方式：

延迟写可以减少写操作的次数，提高效率

希望将缓存和页式管理结合，形成分页缓存机制，使得数据更好的给上层应用程序来使用。读写的是内存单元，避免了传统的系统调用带来的开销。

打开文件的数据结构


当某一个进程做打开操作，会返回一个index，index会指出在进程的打开文件表的哪个位置，把项取出后，再基于这个项找到系统层面的打开文件表（因为可能不同进程打开同一个文件）。进一步找到目录或者文件，文件的节点信息会包含这个文件信息到底在什么地方。
可以通过锁保持情况或者拒绝访问，进程可以查找锁的状态来决定怎么做。
文件分配　　对文件数据空间的管理。

　　对于用户而言，文件有多大决定了接下来怎么分配。针对不同类型的文件，我们希望能够兼容的方法，既可以支持访问大文件也可以访问小文件。

分配方法有多种，这里讲一下常见的三类。指标是高效（访问性能：访问速度，读写速度，删除是否很快），空间利用率高不高（为了存这些数据是否需要其他更多的数据来辅助存储）
1.连续分配

他会指出文件头的起始位置和块的长度，这两个信息就可以表示连续的文件存储方式了。
存在的问题：
因为文件存在是连续的，所以如果要对其中一个文件块做扩展时，需要较大的开销来挪动位置或增加内存。灵活添加删除扩展，开销极大。虽然组织方式简单，但是效率很糟糕。对于数据块的分配，可以对连续分配内存的算法来适用，比如FIFO。
优势：读很方便，特别适合高效的顺序读取
缺点：挪位置会出现碎片，文件扩展时开销大。

链式分配：数据块是以链表的形式组织起来的。（前面的是数组组织），有了链表，增加删除就很方便了。
问题：
优点：创建，扩展，缩小容易，只可能在最后部分文件删扇区没有用满而产生的内碎片，没有外水平。
缺点: 一个串行访问，使得它不能实现高效的随机访问。文件系统存在硬盘上，如果掉电，则链接信息可能会丢失，一旦断一处，可能整个文件就崩了，无法后续访问。

　　索引分配：把特定磁盘块数据块作为索引。每一个索引项指向一个数据块，索引数据块指出了文件需要的数据、所在磁盘块的位置。一般会把索引数据放在头部，使得一旦得到索引就可以调入内存并进行接下来的查找。不像链式存储，使得顺序和随机访问都能高效实现。
优点：没有碎片。
缺点：当文件很小时（比一个数据块还小），储存索引的本身也是一个数据块，那么冗余信息比例就会比较大。
对于大文件，会出现索引块的容量限制内不够表示出数据块的个数。那么其他的数据块怎么管理？如果扩展索引块用什么方式？如果用数组和链表不就又回到顺序和链表分配了吗~

对于大文件的索引分配，多级索引来实现对大文件的支持。但是会引入很多开销，需要读多个索引块才能查到数据块。
链式索引块：仍然会出现万一断链的问题。
这些使得多级索引块成为更加适用于大小文件都能管理的方式。

　　inode是一个磁盘块里的项，里面存了一级索引、二级索引、三级索引各一项。然后每一级索引再针对不同索引。
问题：

大文件需要多次间接访问才能找到数据块，要优化这个问题，就要把间接访问的索引块先读入内存，使得对硬盘的访问变成对内存的访问，可以减少开销。
空闲空间列表

空闲空间是站在磁盘的角度来看，针对一个文件要分配数据块，数据块一定来自于空闲磁盘块，而空闲磁盘块不属于具体的文件，但是要被文件系统管理起来。

我们假定一个数据块就是一个磁盘扇区，我们可以用位图（一个bit）来代表一个磁盘扇区是空闲还是被使用了。1被使用0空闲。有效利用一个紧凑空间来表示当前文件系统管理磁盘块的空闲与否。
首先一点：整个位图空间要导入内存，定期还要把信息更新到硬盘内，才能保证数据的一致性。否则断电会导致无法写回硬盘会导致数据的不一致性。
160GB DISK-40M个块，每个需要1bit，就是40Mb（8bit=1byte）
所以是5MB个位图空间。

如果已经用了这一块内存块但是没有及时写会硬盘，导致硬盘中对应位置接下来就会出现不一致的现象。
确保某一个bit置1的操作要在硬盘上先完成再去分配空间。但是会有一种极端情况，置1后掉电，硬盘实际上没使用但是从逻辑上来看已经被使用，但是数据没有丢失。
这都是一些常见的组织方式来快速查找空闲块的位置，不用像位图一样扫描，根据链表顺序查找即可。各有各的好处，应该根据需要不同选择。

RAID 多磁盘管理-冗余磁盘阵列

首先理解磁盘：磁盘是机械设备，通过分区来较少寻道。盘面会旋转，磁头则会来回寻道。寻道后在这一圈里面会有不同的扇区，探针会读取磁盘中的数据并把数据读入内存。这里最慢的部分是磁头的前后挪动。

一个典型的文件系统由分区组成。 磁盘可以分不同的分区，不同分区由不同文件系统组成。卷比分区功能更多，把多个disk变成一个卷来管理，这样可以把文件系统扩展到多个磁盘上去。文件系统是位于不同磁盘上的，那么让两个磁盘并行工作能否提高文件系统访问效率？如果让给两个磁盘存一个文件的同样内容，是否能提高可靠性 ？

　　早期的磁盘经常坏，而且效率和速度不佳。为此想要让多个性能不太高的磁盘通过并行的方式工作，提高冗余的方式提高数据可靠性，实现又可靠又高速的存储介质，这就是RAID产生的原理。
软RAID：OS里面，文件系统之下，磁盘驱动之上，有个RAID层来完成磁盘阵列的管理。或者把他实现在芯片里，放在硬件的控制单元里，主板上，对于OS而言看不到是个RAID而是一个大硬盘，这样OS干涉就会很简单，正常的当做硬盘管理即可。

数据放在相对独立的硬盘里，而每个硬盘可以相对独立的并行工作，这样可以实现数据并行访问。
RAID-0：把磁盘块数据均匀分配在 相对独立的硬盘里，访问数据时就可能实现并行操作。这就是提高吞吐率的方法。

　　RAID-1：提高可靠性。写数据时向两个硬盘里写同样一块数据，如果一个硬盘崩了，第二个硬盘可以代替第一个硬盘继续正常工作。当然一次操作要变成两次操作，开销变大。

RAID-4：结合0和1的好处，提高性能且提高可靠性。有一些额外的硬盘啊用来做奇偶校验（纠错）。如图5个盘，1~4盘是起到RAID0的功能，把不同数据分配到不同盘上，实现并行访问。
如果1~4盘有一个坏了，我们希望通过第五个盘Parity盘恢复过来。当某个盘坏掉后，P盘存的数据其实是1234的奇偶校验，这样可以反推出坏的盘数据内容是多少。只有出现一个硬盘故障的时候可以恢复。
这种方式的问题在于P盘的读写非常频繁，可能会带来瓶颈。

RAID-5：把P盘的功能负担给均匀分配不到不同的盘中，这样使得每个硬盘的开销是类似的。校验开销是均匀的且访问是并行的，既保证可靠性又提高效率，这是目前磁盘阵列中常用的组织方式。
这种方式仍然只能纠1个错。

做奇偶校验的单位：bit和byte和block。
RAID 0 4 5的常用方式是block为单位。
RAID 3 是以bit为单位做奇偶校验，但是bit做奇偶校验粒度太小，实现起来不如RAID4和5 实用。理论上可行但是实际上没有具体产品。

为了支持更多的容错，可以通过raid6（两个冗余块实现）

可以分层，来完成效率和可靠性的提升，不像RAID5/6那样复杂但是还能实现高效和容错，这也是分层嵌套的对的组织方式。
磁盘调度　　磁盘调度是OS层面通过重新组织IO请求顺序来有效减少磁盘的访问开销。

对于硬盘而言，每个硬盘有多个盘片，所有的机械操作（旋转，前后移动）比起内存的电子访问速度不是一个数量级。 所以优化机械访问的开销是提高性能很重要的一个因素。

前后移动的磁头要固定在一个特定的磁道上，磁道上会有一些扇区，然后去读数据。定位到磁道的时间称为寻道时间。 旋转延迟如图。


　　N是磁道的bit数，r是磁盘的转速，b/rN得到了大致完成一个数据访问的时间。
寻道时间相比其他开销更大，对于单个磁盘而言希望减少寻道开销。

FIFO先进先出

应用程序会发出IO访问请求，按照发出请求的顺序，交给磁盘去访问。由于应用程序本身的访问随机性导致请求序列也有很大的随机性，就会导致磁头的总移动距离会很长，开销很大。
这种算法简单不高效

最短服务优先
　　移动的位置是移动量最少的IO请求的位置， 下次访问要移动到的位置是离当前位置距离最短的位置。

问题：如果请求频繁出现在当前位置附近，导致磁头会在当前位置不断来回走，远处的访问请求会持续无法得到访问，会导致饥饿。访问的不公平性和不均匀性会体现出来。

SCAN扫描法

有一个约束：磁头的移动方向是先朝一个方向移动到头，再逆方向移动到头，如此往复。又称为电梯算法，类似电梯，不会上到中间又下去。这种方式可以比较公平得让所有访问请求都得到访问。
问题：限制一个方向
C-SCAN：当磁头读到头后，磁头返回到另一端顶点，保证了访问方向始终是一个方向。有些请求位于靠近0的位置可能被访问的时间要长一些，而这种方式由低到高的序列来完成IO访问请求，对请求的位置建立有序的过程，先满足低序再满足高序。
C-LOOK：磁头到达该方向上的最后一个请求处立刻反转跳回，而不是先到达最后点路径上的终点。

结合了FIFO和SCAN的特点，把访问请求分区，每个区以FIFO实现，区域内部以SCAN算法实现。这种算法的出现原因是上述的算法中或多或少会出现磁头在某小范围内往复移动，这种磁臂粘着现象。为了公平性，采取这种方法来取消这种情况的出现。

因为输入的随机性，没有一种算法比其他算法都要好。所以根据情况选择合适的算法来更好的减少寻到开销，这些算法大多数是课本上的内容，对于真实系统或许还要设计更复杂的算法。又因为DISK不断的变化，SSD硬盘已经不是传统的机械硬盘；硬盘内部的硬盘控制器会自动调整，在软件层面做调整对于现在这种高性能或者智能硬盘效果并不显著。所以这部分内容以理解为主，针对具体情况还有很多课本上没有的内容，课本知识永远落后实际第一线理论。