File Organization and Processing
Lecture 4
File System Implementation
Mohamed Mead
Introduction
File system resides on secondary storage
(disks)
Provided user interface to storage, mapping logical
to physical
Provides efficient and convenient access to disk by
allowing data to be stored, located retrieved easily
Layered File System
Application Programs The code that's making a file
request.
Logical File System This is the highest level in
the OS; it does protection, and security.
Translates file name into file number, file handle,
location by maintaining file control blocks (inodes in
UNIX).
Directory Management
Layered File System
File-organization Module understands files,
logical address, and physical blocks
Translates logical block # to physical block #
Manages free space, disk allocation.
Layered File System
Basic File System Knowing specific blocks to
access, we can now make generic requests to
the appropriate device driver.
IO Control They cause the device to
transfer information between that device and
CPU memory.
Layered File System
File System Structures
On-disk and in-memory structures are needed to
implement a file system:
On disk:
1. Boot control block: needed to boot OS from a disk partition.
2. Partition control block: holds details about partition (e.g., blocks
in partition, freeblock count, …)
3. Directory structure: to organize files.
4. FCB (or inode)
File Control Block
Per-file File Control Block (FCB) contains many details
about the file
File System Structures
In-memory:
1. Per-process open-file table: contains pointers to appropriate entries in
system-wide open-file table
2. System-wide open-file table: contains a copy of the FCB of each file
and other info
In-memory Mount Table
In-memory mount table contains the list of all the devices which are being
mounted to the system.
In-memory Directory structure cache
This is the list of directory which is recently accessed by the CPU.
File System Structures
File System Structures
When a new file is created, a new FCB is allocated and
filled out with important information regarding the new
file. The appropriate directory is modified with the new
file name and FCB information.
File System Structures
When a file is accessed during a program, the open( )
system call reads in the FCB information from disk, and
stores it in the system-wide open file table. An entry is
added to the per-process open file table referencing the
system-wide table, and an index into the per-process table
is returned by the open( ) system call. UNIX refers to this
index as a file descriptor, and Windows refers to it as a
file handle.
File System Structures
When a file is closed, the per-process table entry is freed,
and the counter in the system-wide table is decremented.
If that counter reaches zero, then the system wide table
is also freed.
Partitions
Physical disks are commonly divided into smaller units
called partitions.
Directory Implementation
The selection of directory-allocation and directory-
management algorithms affects the efficiency,
performance, and reliability of the file system.
Directory Implementation
The simplest method of implementing a directory is to use
a linear list of file names with pointers to the data blocks.
This method is simple to program but time-consuming to
execute.
To create a new file, we must first search the directory to be sure
that no existing file has the same name.
Then, we add a new entry at the end of the directory
Directory Implementation
To delete a file, we search the directory for the named
file and then release the space allocated to it.
To reuse the directory entry, we can do one of several
things.
We can mark the entry as unused (by assigning it a special name,
such as an all-blank name, assigning it an invalid inode number (such
as 0) ), or
we can attach it to a list of free directory entries.
Directory Implementation
The real disadvantage of a linear list of directory entries is
that finding a file requires a linear search.
Directory Implementation
Hash Table: Another data structure used for a file
directory is a hash table
The hash table takes a value computed from the file name and
returns a pointer to the file name in the linear list.
Therefore, it can greatly decrease the directory search time.
Allocation Methods
An allocation method refers to how disk blocks
are allocated for files:
Contiguous allocation
Chained/Linked allocation
Indexed allocation
