Transcript File system implementation

Computer Studies
File Management
File Implementation
Reference

Silberschatz, Galvin, Gagne “Operating
System Concepts 6th edition”, 2003, Wiley
Content









File system structure
File system implementation
Directory Implementation
Allocation Methods
Free-Space Management
Efficiency and Performance
Recovery
Log-Structured File System
NFS
File system structure



The file system provides the mechanism for online storage and access to file contents, including
data and programs
Usually, the file system resides permanently on
secondary storage.
To provide an efficient and convenient access to
the disk, the OS imposes one or more file systems
to allow the data to be stored, located and
retrieved easily.
File system structure

The file system itself is generally
composed of many different levels.
Application programs
Logical file system
File-organization module
Basic file system
I/O control
devices
File system structure

I/O controls


Basic file system


Device drivers and interrupt handlers
It needs only to issue generic commands to the
appropriate device driver to read and write physical
blocks on the disk.
File-organization module

By knowing the type of file allocation used and
location of file, it can translate logical block address
to physical block address for the basic file system to
transfer.
File system structure

Logical file system


Manage metadata information, includes all
the file-system structure, excluding the actual
data.
File control block (FCB) contains
information about the file, including
ownership, permissions, and location of file
content; security
Overview: File system
implementation


Several on-disk and in-memory
structure are used to implement
a file system.
The on-disk structures include:

Boot control block

Partition control block
 Size of block, freeblock count,
 In NTFS, Master file
table

A directory structure

File control block (FCB)
 File’s details,
permissions, size, etc

The in-memory structures include:

An in-memory partition
table

An in-memory directory
structure
 Recent access directory

System-wide open file table
 A copy of the FCB of
each open file

Per-process open-file table
 Contain pointer to the
appropriate entry in the
System-wide open file
table
Typical file control block
File permissions
File dates (create, access, write)
File owner, group
File size
File data blocks
Partitions and Mounting

A disk can be sliced into multiple partitions,
or a partition can span multiple disks.


Root partition contains the OS kernal and
potentially other system files. (mount at boot
time)
Other partitions can be manually or
automatically mounted at boot by OS.
Directory Implementation

Linear list implementation



Linear list of file names with pointers to the data
blocks.
Simple, but time consuming to execute
Hash table implementation



Both linear list and hash table are used
Compute a value from file name and return a pointer.
Faster than linear list but collision may occur.
Allocation methods 1

Contiguous allocations





Each file to occupy a set of contiguous blocks on the
disk.
Disk addresses define a linear ordering on the disk
The length of block should be defined
Support both sequential and direct access
Major difficulties:



Finding space for a new file.
As files are allocated and deleted, external
fragmentation occurs
Determine how much space is needed for a file
Allocation methods 2


Linked allocation

Each file is a linked list of disk blocks

The disk blocks may be scattered anywhere on the disk

The size of a file does not need to be declared when that file is
created
Major difficulties:

It can be used effective only for sequential-access files (from
beginning to nth blocks)

Space required for the pointers
 Solution: collect blocks into multiples called clusters
 OS allocate the clusters rather than blocks
 Improve disk throughput (access time)
File allocation table (FAT)

Vary from linked allocation




A section of disk at the beginning of each partition is
set aside to contain the table
The table has one entry for each disk block, indexed
by block number
The FAT is used like a linked list. The directory entry
contains the block number of the first block of the
file
The table entry indexed by that block number then
contains the block number of the next block in the
file, until the last block with a special end-of-file
value 0
Directory entry
test
name
…
217
0
Start block
217
618
339
eof
618
339
FAT
Allocation methods 3

Indexed allocation




Note that linked allocation solves the externalfragmentation and size-declaration, but only effective
on sequential access
Indexed allocation solve this problem by index block
(bring all pointers into one location)
Each file has its own index block, which is an array
of disk-block addresses.
When the file is created, all pointers in the index
block are set to nil. When the ith block is first written,
a block is obtained from the free-space manager, and
its address is put the ith index-block entry
Allocation methods 3 (Con’t)

For large file, several mechanism may be
implemented:



Linked scheme (linked index block)
Multilevel index
Combined scheme
Free space Management



To keep track o free disk space, the system
maintains a free-space list
Frequently, the free-space list is
implemented as a bit vector
Each block is represented by 1 bit, if block
is free, the bit is 1, else 0
Recovery


Since files and directories are kept both in
main memory and on disk, care must taken
to ensure that system failure does not result
in loss of data or in data inconsistency.
The consistency checker compares the data
in the directory structure with the data
blocks on disk, and tries to fix any
inconsistencies it finds.
Backup and restore

A typical backup schedule may be as follows:





Day 1: copy to a backup medium all files a full
backup
Day 2: copy to another medium all files changed
since day 1. This is an incremental backup
Day 3: copy to another medium all files changed
since day 2
….
Day N: copy to another medium all files changed
since day N-1. Then go back to Day 1.
Log-Structured File system




Similar to database system, a log-based-recovery
algorithm can be applied to consistency checking.
All metadata changes are written sequentially to a
log.
Each set of operations that perform a specific task
is a transaction. Once the changes are written to
this log, they are considered to be committed, and
the system call can return to the user process,
allowing it to continue execution
When an entire committed transaction is
completed, it is removed from the log file.