Lecture 10 : File system implementation
File-Structure
on secondary storage(disk)
layers
file control block
layered file system
application programs
|
logical file system
|
file-organization module
|
basic file system
|
i/o control
|
devices
file-system implementation
On-disk structures
- boot control block
- volume control block
- directory structure
- Per-file FCB
Directory implematation
- 线性列表实现
哈希表实现
时间上提高了性能，效率高，但是会出现冲突，需要解决这之前的内容讲的巨快
Allocation methods
连续分配
块的起始地址,块的长度
LogicalAddress/512 = Q. . . . . . R
Block to be accessed = Q + starting address Displacement into block = R
优点:
- 支持随机访问，顺序访问
- 访问速度快
缺点：
- 可能出现外部碎片，浪费空间
- Files cannot grow ==解决方式=> Extent-Based Systems（use a modified contiguous allocation scheme）
链接分配
implicit
目录包含了一个指向第一个和（最后一个块）（可选）的指针 每个块包含了指向下一个块的指针 优点：离散分布，不会浪费空间 缺点：1.不能随机访问，必须从第一个开始找，访问效率低 2.链接指针占磁盘空间
explicit
内存上存一个File Allocation table, FAT，只存指针，不存数据 每个块都有一个entry 优点：某种程度上 support random access,仍然效率不太高 缺点：result in a significant disk head seeks ==solution=> cached FAT
索引分配
把所有的指针放在一个块里，索引块
而不是每一个
优点:支持随机访问
不会产生随机碎片
缺点：过度依赖索引块，块的大小有限，文件的大小就依赖于索引块的大小 =solution=> 多级索引
组合分配
给出文件b的路径，怎样才能找到它的FCB?
要先找b的根目录
根据映射关系，比如是索引方式，就可以找到子目录的块号，找到子目录的fcb，类似依次找下去，直到找到目标目录项，找到b的fcb
Free-Space management
algorithm:
- bit vector
- linked list
- counting
bit vector
0 - allocated
1 - free
bitmap length
how to find the 第一个空闲块？
找到第一个非0的字（假设是16位）
在这个非0的字里找到第一个是1bit的
看看够不够，然后继续往下走
If first K words is 0, & (K + 1)th word > 0,
the first (K + 1)th word's first 1 bit has offset L,
first free block number N = K × 16 + L
But copy in memory and disk may differ
Cannot get contiguous space easily
linked list
linked list
Link together al l the free disk blocks First free b lock
Cannot get contiguous space easily
No waste of space
counting
一个table里有许多 起始
Each = first free block number & a counter (number of free blocks)
Each = first free block number & a counter (number of free blocks)
Shorter than linked list