File -logical storage unit
file system organized into layers-layered file system(分层文件系统）
file control block-storage structure consisting of information about a file
File-system Implementation分为on-disk和in memory
Directory Implementation
1.线性列表实现--Linear list of file names with pointer to the data blocks
耗时
2.Hash Table--linear list with hash data structure
效率高，有冲突
Allocation Methods
Contiguous allocation(连续分配）
块的起始地址,块的长度
LogicalAddress/512 = Q. . . . . . R
Block to be accessed = Q + starting address Displacement into block = R
优点:
支持随机访问，顺序访问
访问速度快
缺点：
external fragmentation
files cannot grow-->extent-based systems(use a modified contiguous allocation scheme)
Linked Allocation
1.implicit(隐式链接）
目录包含了一个只想第一个和最后一个块的指针（最后一个可选）
每个块block包含了指向下一个块的指针
优点：
解决了contiguous所有问题，
离散分布，不会浪费空间，
有效用于文件的顺序访问
缺点：
No random access,不适用与直接访问，随机访问，效率低
链接指针占据磁盘空间
2.explicit(显式链接）
File Allocation table (FAT)：只存指针，不存数据
FAT存在beginning of each partition
each disk block one entry
directory entry contains the first block number
优点：某种程度上support random access,效率不高
缺点：result in a significant disk head seeks (solution:cached fat)
Indexed Allocation(索引分配）
index block:bring all pointers together into one location
优点：
支持random access
dynamic access without external fragmentation
缺点：
have overhead of index block
file size limitation,since one index block can contains limited pointers(一级索引远无法满足存储需求--->用多级索引）
Free-Space Management
Bit vector
copy in memory and disk may differ
cannot get contiguous space easily
Linked list
link together all the free disk blocks(first free block and next pointer)
cannot get contiguous space easily
no waste of space
Counting:
网友评论