Module 5

Chapter 1
File System
 File Concept
• File Attributes
Different OS keep track of different file attributes,
including:
– Name -
– Identifier ( e.g. inode number )
– Type - Text, executable, other binary, etc.
– Location - on the hard drive.
– Size
– Protection
– Time & Date
– User ID
 File Concept
• File Operations
The file ADT supports many common operations:
– Creating a file,Writing a file,Reading a file,Repositioning within a file,Deleting a
file,Truncating a file.

• Most OSes require that files be opened before access and closed after all access is
complete. Information about currently open files is stored in an open file table,
containing for example:
– File pointer - records the current position in the file, for the next read or write
access.
– File-open count - How many times has the current file been opened
( simultaneously by different processes ) and not yet closed? When this counter
reaches zero the file can be removed from the table.
– Disk location of the file.
– Access rights

• Some systems provide support for file locking.

– A shared lock is for reading only.
– A exclusive lock is for writing as well as reading.
– An advisory lock is informational only, and not enforced. ( A "Keep Out" sign,
which may be ignored. )
– A mandatory lock is enforced. ( A truly locked door. )
– UNIX used advisory locks, and Windows uses mandatory locks.
File Concept
 File Concept
File Structure
• Some files contain an internal structure, which may or may
not be known to the OS.
• For the OS to support particular file formats increases the
size and complexity of the OS.
• UNIX treats all files as sequences of bytes, with no further
consideration of the internal structure. ( With the exception
of executable binary programs, which it must know how to
load and find the first executable statement, etc. )
• Macintosh files have two forks - a resource fork, and a data
fork.
a. The resource fork contains information relating to the UI,
such as icons and button images, and can be modified
independently of the
b. data fork, which contains the code or data as appropriate.
 File Concept
File Types
Types of Files
• File type refers to the ability of the operating
system to distinguish between different kinds
of files such as text files, source files, and
binary files.
• Most operating systems (e.g., MS-DOS, UNIX)
support the following types of files:
 File Concept
File Types
1. Ordinary Files
Contain user information
May store text, databases, or executable
programs
Users can perform operations such as create,
read, write, modify, and delete
 File Concept
File Types
2. Directory Files
• Contain a list of file names and their related information
• Help in organizing and managing files in the system
3. Special Files (Device Files)
• Represent physical devices such as disks, printers,
terminals, etc.
• Types of Special Files:
• Character Special Files
– Handle data character by character
– Example: Keyboard, printer
• Block Special Files
– Handle data in blocks
– Example: Disk drives, tapes
 File Concept
Internal File Structure
• Disk files are accessed in units of physical blocks, typically
512 bytes or some power-of-two multiple thereof.
• Larger physical disks use larger block sizes, to keep the
range of block numbers within the range of a 32-bit
integer.
• Internally files are organized in units of logical units, which
may be as small as a single byte, or may be a larger size
corresponding to some data record or structure size.
• The number of logical units which fit into one physical block
determines its packing, and has an impact on the amount
of internal fragmentation ( wasted space ) that occurs.
 File Access Methods
1. Sequential Access
2. Direct Access
[Link] Sequential Access Method
 Access methods
• Access methods determine the way that files are accessed
and read into memory.
1. Sequential Access
✦ The most common method used by editors and compilers.
 Sequential Access
• Reads and writes make up the bulk of the operations on a file.
• A read operation—read next—reads the next portion of the
file and automatically advances a file pointer, which tracks the
I/O location.
• Similarly, the write operation—write next—appends to the
end of the file and advances to the end of the newly written
material (the new end of file).
• Such a file can be reset to the beginning; and on some
systems, a program may be able to skip forward or backward n
records for some integer n—perhaps only for n = 1.
• Sequential access, as shown in the figure is based on a tape
model of a file and works as well on sequential-access devices
as it does on random-access ones.
 Access Methods
[Link] Access File
File is made up of fixed-length logical records that allow
programs to read and write records in no particular order.
■ The files is viewed as a numbered sequence of blocks or
records.

■ Direct Access
{n = relative block number}
read n
write n
position to n
read next
write next
rewrite n
 [Link] Access File

• The direct-access method is based on a disk model of a

file, since disks allow random access to any file block.
For direct access, the file is viewed as a numbered
sequence of blocks or records. Thus, we may read
block 14, then read block 53, and then write block 7.
There are no restrictions on the order of reading or
writing for a direct-access file.
• Direct-access files are of great use for immediate
access to large amounts of information. Databases are
often of this type. When a query concerning a
particular subject arrives, we compute which block
contains the answer and then read that block directly
to provide the desired information
Access Methods
[Link] Sequential Access Method (ISAM) –
uses Index Sequential Access Method (ISAM) indexes in a
hierarchy to point to records in a file
 [Link] Sequential Access Method
(ISAM) –
• These methods generally involve the construction of an
index for the file. The index, like an index in the back
of a book, contains pointers to the various blocks. To
find a record in the file, we first search the index and
then use the pointer to access the file directly and to
find the desired record.
• With large files, the index file itself may become too
large to be kept in memory. One solution is to create an
index for the index file. The primary index file would
contain pointers to secondary index files, which would
point to the actual data items.
 Directory Structures
Storage Structure
• A disk can be used in its entirety for a file system.
• Alternatively a physical disk can be broken up into
multiple partitions, slices, or mini-disks, each of
which becomes a virtual disk and can have its
own file system. ( or be used for raw storage,
swap space, etc. )
• Or, multiple physical disks can be combined into
one volume, i.e. a larger virtual disk, with its own
file system spanning the physical disks.
Directory operations
Directory Design Goals
 Types of Directory Structures
1. Single level
[Link] Level
[Link] structured
Single level Directory
Two Level Directory
 Two Level Directory
Advantages
✦ Solves the name-collision problem.
✦ Isolates users from one another - a form of
protection.
✦ Efficient searching.
Disadvantages
✦Sharing of files
✦Not scalable
Tree Structured Directory
Tree Structured Directory
 Tree Structured Directory
• There is an own directory of each user, and
any user is not allowed to enter into the
directory of another user.
• Although user can read the data of root, the
user cannot modify or write it.
• The System admin has full access to the root
directory.
• Access files using Absolute or Relative paths
 Tree Structured Directory
Advantages:
• Very generalize, since full path name can be given.
• Very scalable, the probability of name collision is less.
• Searching becomes very easy, we can use both
absolute path as well as relative.
Disadvantages:
• Every file does not fit into the hierarchical model, files
may be saved into multiple directories.
• We can not share files.
• It is inefficient, because accessing a file may go under
multiple directories.
 File-System Structure
• Hard disks have two important properties that
make them suitable for secondary storage of files
in file systems:
(1) Blocks of data can be rewritten in place, and
(2) they are direct access, allowing any block of data
to be accessed with only ( relatively ) minor
movements of the disk heads and rotational
latency.
Disks are usually accessed in physical blocks, rather
than a byte at a time. Block sizes may range from
512 bytes to 4K or larger.
File system Structure
 File-System Structure
File systems organize storage on disk drives, and can be viewed as a layered
design:

• At the lowest layer are the physical devices, consisting of the magnetic
media, motors & controls, and the electronics connected to them and
controlling them. Modern disk put more and more of the electronic controls
directly on the disk drive itself, leaving relatively little work for the disk
controller card to perform.

• I/O Control consists of device drivers, special software programs ( often

written in assembly ) which communicate with the devices by reading and
writing special codes directly to and from memory addresses corresponding
to the controller card's registers.

• The basic file system level works directly with the device drivers in terms
of retrieving and storing raw blocks of data, without any consideration for
what is in each block. Depending on the system, blocks may be referred to
with a single block number, ( e.g. block # 234234 ), or with head-sector-
cylinder combinations.
 File-System Structure
• The file organization module knows about files and their
logical blocks, and how they map to physical blocks on
the disk.
• In addition to translating from logical to physical blocks,
the file organization module also maintains the list of free
blocks, and allocates free blocks to files as needed.

• The logical file system deals with all of the meta data
associated with a file ( UID, GID, mode, dates, etc ), i.e.
everything about the file except the data itself.
• This level manages the directory structure and the
mapping of file names to file control blocks, FCBs,
which contain all of the meta data as well as block
number information for finding the data on the disk.
 Directory Implementation
• Directories need to be fast to search, insert, and delete,
with a minimum of wasted disk space.
1 Linear List
• A linear list is the simplest and easiest directory structure
to set up, but it does have some drawbacks.
• Finding a file ( or verifying one does not already exist upon
creation ) requires a linear search.
• Deletions can be done by moving all entries, flagging an
entry as deleted, or by moving the last entry into the newly
vacant position.
• Sorting the list makes searches faster, at the expense of
more complex insertions and deletions.
• A linked list makes insertions and deletions into a sorted list
easier, with overhead for the links.
• More complex data structures, such as B-trees, could also
be considered.
 Directory Implementation
• The real disadvantage of a linear list of
directory entries is that finding a file requires
a linear search. Directory information is used
frequently, and users will notice if access to it
is slow
 Directory Implementation

[Link] Table
• A hash table can also be used to speed up searches.
• Hash tables are generally implemented in addition to a
linear or other structure.
• 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. Insertion and deletion are also
fairly straightforward, although some provision must
be made for collisions—situations in which two file
names hash to the same location
 Directory Implementation

• The major difficulties with a hash table are its generally

fixed size and the dependence of the hash function on
that size.
• For example, assume that we make a linear-probing
hash table that holds 64 entries. The hash function
converts file names into integers from 0 to 63, for
instance, by using the remainder of a division by 64. If
we later try to create a 65th file, we must enlarge the
directory hash table—say, to 128 entries. As a result,
we need a new hash function that must map file names
to the range 0 to 127, and we must reorganize the
existing directory entries to reflect their new hash-
function values.
 Directory Implementation

• Alternatively, a chained-overflow hash table can

be used.
• Each hash entry can be a linked list instead of an
individual value, and we can resolve collisions by
adding the new entry to the linked list.
• Lookups may be somewhat slowed, because
searching for a name might require stepping
through a linked list of colliding table entries. Still,
this method is likely to be much faster than a
linear search through the entire directory
 Allocation Methods

1. contiguous
[Link]
[Link].
 Contiguous Allocation
In this scheme,
• each file occupies a contiguous set of blocks on the disk.
• For example, if a file requires n blocks and is given a block b
as the starting location, then the blocks assigned to the file will
be:
b, b+1, b+2,……b+n-1. This means that given the starting block
address and the length of the file (in terms of blocks required), we
can determine the blocks occupied by the file.
The directory entry for a file with contiguous allocation contains
• Address of starting block
• Length of the allocated portion.
Contiguous Allocation
 Contiguous Allocation
Advantages:
• Both the Sequential and Direct Accesses are supported by
this.
• For direct access, the address of the k block of the file
which starts at block b can easily be obtained as (b+k).
• This is extremely fast since the number of seeks are
minimal because of contiguous allocation of file blocks.
Disadvantages:
• This method suffers from both internal and external
fragmentation. This makes it inefficient in terms of memory
utilization.
• Increasing file size is difficult because it depends on the
availability of contiguous memory at a particular instance.
 Linked Allocation
• In this scheme, each file is a linked list of disk
blocks which need not be contiguous.
• The disk blocks can be scattered anywhere on the
disk.
• The directory entry contains a pointer to the
starting and the ending file block. Each block
contains a pointer to the next block occupied by
the file.
• The file ‘abc’ in following image shows how the
blocks are randomly distributed. The last block
(25) contains -1 indicating a null pointer and
does not point to any other block.
Linked Allocation
 Linked Allocation
Advantages:
• This is very flexible in terms of file size. File
size can be increased easily since the system
does not have to look for a contiguous chunk
of memory.
• This method does not suffer from external
fragmentation. This makes it relatively better
in terms of memory utilization.
 Linked Allocation
Disadvantages:
• Because the file blocks are distributed randomly on the
disk, a large number of seeks are needed to access
every block individually. This makes linked allocation
slower.
• It does not support random or direct access. We can
not directly access the blocks of a file. A block k of a file
can be accessed by traversing k blocks sequentially
(sequential access ) from the starting block of the file
via block pointers.
• Pointers required in the linked allocation incur some
extra overhead.
 Indexed Allocation
• In this scheme, a special block known as
the Index block contains the pointers to all the
blocks occupied by a file.
• Each file has its own index block. The ith entry
in the index block contains the disk address of
the ith file block.
• The directory entry contains the address of
the index block as shown in the image:
Indexed Allocation
 Indexed Allocation
Advantages:
• This supports direct access to the blocks occupied by the
file and therefore provides fast access to the file blocks.
• It overcomes the problem of external fragmentation.
Disadvantages:
• The pointer overhead for indexed allocation is greater than
linked allocation.
• For very small files, say files that expand only 2-3 blocks,
the indexed allocation would keep one entire block (index
block) for the pointers which is inefficient in terms of
memory utilization.
• However, in linked allocation we lose the space of only 1
pointer per block.
 Indexed allocation
For files that are very large, single index block may not be
able to hold all the pointers.
Following mechanisms can be used to resolve this:
[Link] scheme: This scheme links two or more index
blocks together for holding the pointers.
• Every index block would then contain a pointer or the
address to the next index block.
[Link] index: In this policy, a first level index block
is used to point to the second level index blocks which in
turn points to the disk blocks occupied by the file.
• This can be extended to 3 or more levels depending on
the maximum file size.
 Indexed Allocation
[Link] Scheme:
• In this scheme, a special block called the Inode (information
Node) contains all the information about the file such as the
name, size, authority, etc and the remaining space of Inode is
used to store the Disk Block addresses which contain the actual
file.
• The first few of these pointers in Inode point to the direct
blocks i.e the pointers contain the addresses of the disk blocks
that contain data of the file.
• The next few pointers point to indirect blocks. Indirect blocks
may be single indirect, double indirect or triple indirect.
• Single Indirect block is the disk block that does not contain the
file data but the disk address of the blocks that contain the file
data. Similarly, double indirect blocks do not contain the file
data but the disk address of the blocks that contain the address
of the blocks containing the file data.
Indexed Allocation
Combined Scheme