Week 10 - File system & Device Drivers
File System
功能
主要用于存储永久数据。是速度瓶颈。
容量在如今并不是问题，因为存储很便宜，但是备份成了一个问题。
逻辑视角：是文件的树状结构。还有读写文件，创建目录的功能。
物理视角：一系列的块，可以读取和写入。操作系统必须将逻辑视图映射到物理视图，必须强加树结构并为每个文件分配块。
实现方法
主要有两种。
- 链表。问题：seek很慢，O(n)
- 索引分配（indexed allocation）：将指针存储在一个位置：所谓的索引块（类似于页表）。为了应对巨大不同的文件大小，可能会引入间接索引块。
在Linux中，index block叫作inodes
inodes中存储了文件的附加信息，例如size和权限
FAT
F(ile) A(llocation) T(able)，用于解释文件系统概念。现代的文件系统往往更复杂。这里采用FAT16讲解。
Sector扇区 = 磁盘单元（例如 512 字节），又称块blcok
Cluster = 多个sectores（因子为 1、2、4，...，128）
（这里：假设簇 = 1 扇区）
使用链表（“cluster chain”）将簇分组
这个图是其中boot sector的16进制实例。这里面红色的圈圈住的信息，所对应的位置都可以查表得到。
这个是FAT：
Root Directory下的文件：
FAT的一些限制：
最大卷大小（max volume size）: 2 GB (2^16 · 32 kB)
最大文件体积：2GB
最多文件数量：65460（32kB clusters）
最长文件名：8 + 3
FAT32 / exFAT有更高的限制
而新的文件系统，NTFS, ext4已经克服了这些limits, 使用了其他的DS，例如B-tree for dir structure, bitmap for allocation
Caching
缓存是在memory中用于存储目录或最近使用的文件缓存的磁盘块
这些内容会被定期写入磁盘，大大提升了效率。
当系统崩溃时会出现不一致性，所以说计算机必须正常关闭。
Journaling File System
为了在系统崩溃的时候最小化数据丢失，采用了和数据库一样的事务逻辑。
- 定义事务点Transaction points: 保证了文件系统状态的一致性，这意味着无论何时系统崩溃，文件系统都可以恢复到最后一次成功的事务点，确保了在该点之前的所有操作都已成功完成，且文件系统处于一致状态。
- 为每个写操作都保持log file. 记录足够的信息去揭开事务点之后发生的任何changes
Disk
磁盘访问被分为三个步骤
- 寻道Seek：head移到正确的磁道
- 延迟Latency：移到正确的block
- 传输Transfer：数据传输
硬盘驱动器（HDDs）：寻道和延迟所需时间远大于传输时间
⇒ 数据分布和调度算法对HDD性能有重要影响，对SSD影响较小
磁盘调度算法
- FCFS
- Shortest Seek Time First：选择磁头移动最短的。
- 缺点：starve，disk中间会被preferred
- SCAN-scheduling：电梯， continuously scans the disk from en to end (lift strategy)
- LOOK-scheduling：对SCAN的改进，不移动到头，而是移动到最后一块就往回走。
对于不同的任务，可以采用不同的访问算法。
对于内存和磁盘的Swap空间，我们就不使用间接访问方法，因为时间很crutial。
在这种情况下，系统设计者可能会选择一种算法，它以增加内部碎片（例如，不充分利用存储空间）为代价，来优化速度。这意味着为了获得更快的性能，系统可能会分配更多的空间而不是尽可能紧凑地存储数据。
File System Linux实现
Linux为所有的文件系统设计了通用接口，叫作virtual file system(VFS)
VFS维护了：
- inodes for files and directories
- Caches, in particular for directories
- Superblocks for file systems
所有的file system call (open read write close)首先访问VFS，在必要情况下，VFS从真正的文件系统中选择合适的操作。
Disk Scheduler Linux实现
内核使得不同FS使用不同scheduler成为可能。
默认的scheduler就是完全Fair Queuing based on lift strategy。此外，为每个进程的磁盘请求单独设置队列，队列以RR方式服务。
还有适用于SSD的No-op scheduler: FIFO
Drivers
见Week 5
\
Larry Shi