Chapter 12: File System Implementation

File-System Structure

File control block–storage structure consisting of information about a file. 文件控制块放在硬盘上，内存中存放的有文件控制块所包含的内容，文件存放在硬盘，硬盘上的存储是非易失的。

File structure: Logical storage unit Collection of related information

Layered File System：

应程程序进行系统调用：open read write… 执行IO语句

逻辑文件系统：目录 FCB 文件具体放在block（logic）上

文件组织模块：逻辑块映射到物理块

基本文件系统：发出IO命令 磁盘地址

IO control：设备驱动

设备：以上都是软件层面，只有device是硬件

A Typical File Control Block: file permission, file dates, file owner,group,ACL ,file size ,file date blocks 抓住了文件控制块就抓住了文件

on-disk information:

boot control block,volume control block(每分区一个) directory structure(每个文件系统一个)

FCB i-node UFS (这些信息放在磁盘上，文件加载后有些信息会放在内存中)

In-Memory File System Structures：

Directory Implementation

• Linear list of file names with pointer to the data blocks ：

simple to program

time-consuming to execute

• Hash Table –linear list with hash data structure ：

decreases directory search time

collisions –situations where two file names hash to the same location

Allocation Methods

Contiguous Allocation

• Each file occupies a set of contiguous blocks on the disk.
• Simple –only starting location (block #) and length (number of blocks) are required.
• Random access.
• Wasteful of space 外部碎片
• Files cannot grow

Extent-Based Systems

Extent-based file systems allocate disk blocks in extents.

An extent is a contiguous block of disks. Extents are allocated for file allocation. A file consists of one or more extents。 类似于存储管理中的分段segement

Linked Allocation

Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk.

• Simple –need only starting address
• Free-space management system –no waste of space
• Files can grow
• No random access
• Each block contains a pointer, wasting space
• Blocks scatter everywhere and a large number of disk seeks may be necessary
• Reliability: what if a pointer is lost or damaged 不安全不可靠

File-Allocation Table FAT

FAT表在磁盘的最开始

实现了随机访问，更加安全可靠

Indexed Allocation

Brings all pointers together into the index block

A file’s directory entry contains a pointer to its index. Hence, the index block of an indexed allocation plays the same role as the page table.

• **Random access **
• 无外部碎片
• 不是安全可靠的
• 文件的grow是有限的

The indexed allocation suffers from wasted space. The index block may not be fully used

The number of entries of an index table determines the size of a file. To overcome this problem, we can have ：

• multiple index blocks, chain them into a linked-list
• multiple index blocks, but make them a tree just like the indexed access method
• A combination of both

4 128 84+2^16

Free-Space Management

How do we keep track free blocks on a disk? A free-list is maintained(维护).

When a new block is requested, we search this list to find one.

• Bit Vector
• Linked List
• Linked List + Grouping
• Linked List+Address+Count

Linked Free Space List on Disk:

Link+Grouping:

The first free block contains the addresses of n other free blocks.

For each group, the first n-1 blocks are actually free and the last (i.e., n-th) block contains the addresses of the next group.

Link+Address counting:

Blocks are often allocated and freed in groups

We can store the address of the first free block and the number of the following n free blocks.

Efficiency and Performance

Efficiency dependent on:

• disk allocation and directory algorithms
• types of data kept in file’s directory entry

Performance:

• disk cache
• free-behind and read-ahead 延后释放，提前读取
• improve PC performance by dedicating section of memory as virtual disk, or RAM disk 提升硬件性能