FILE SYSTEMS

MODULE 5
 File Systems
• File system is the part of the operating system which is responsible for
file management.
• It provides a mechanism to store the data and access to the file contents
including data and programs.
• The File system takes care of the following issues:
• File Structure
• Recovering Free space
• Disk space assignment to the files
• Tracking data location

NVV’s 2
 File Concepts
• A file is a named collection of related information that is recorded on
secondary storage.

• A file has a certain defined structure, which depends on its type.

• A text file is a sequence of characters organized into lines (and possibly pages).

• A source file is a sequence of functions, each of which is further organized as

declarations followed by executable statements.

• An executable file is a series of code sections that the loader can bring into
memory and execute.

NVV’s 3
 File Attributes
• A file’s attributes vary from one operating system to another but
typically consist of these:
• Name: The symbolic file name is the only information kept in humanreadable
form.
• Identifier: This unique tag, usually a number, identifies the file within the file
system; it is the non-human-readable name for the file.
• Type: This information is needed for systems that support different types of files.
• Location: This information is a pointer to a device and to the location of the file
on that device
• Size: The current size of the file
• Protection: Access-control information determines who can do reading, writing,
executing, and so on.
• Time, date, and user identification: This information may be kept for creation, last
modification, and last use. These data can be useful for protection, security, and
usage monitoring.

NVV’s 4
 File Attributes

A file info window on windows and Mac OS X 5

NVV’s
 File Operations
• The operating system can provide system calls to create, write, read,
reposition, delete, and truncate files.
• Creating a file
• Two steps are necessary to create a file.
• First, space in the file system must be found for the file.
• Second, an entry for the new file must be made in the directory
• Writing a file
• The system must keep a write pointer to the location in the file where the next write is
to take place. The write pointer must be updated whenever a write occurs
• Reading a file
• System needs to keep a read pointer to the location in the file where the next read is
to take place.
• Must be updated whenever a read occurs
• The current operation location can be kept as a per-process current file-position
pointer.
NVV’s 6
 File Operations

• The operating system can provide system calls to create, write, read,
reposition, delete, and truncate files.

• Repositioning within a file

• This file operation is also known as a file seek.

• Deleting a file

• Truncating a file
• Erase the contents of a file but keep its attributes

NVV’s 7
 File Types

• Ordinary files
• These are the files that contain user information.
• These may have text, databases or executable program.
• The user can apply various operations on such files like add, modify,
modify, delete or even remove the entire file.
• Directory files
• These files contain list of file names and other information related to
these files.

NVV’s 8
 File Types

• Special files
• These files are also known as device files.
• These files represent physical device like disks, terminals, printers,
networks, tape drive etc.
• These files are of two types
• Character special files − data is handled character by character as in case of
terminals or printers. –
• Block special files − data is handled in blocks as in the case of disks and tapes.

NVV’s 9
 File Types

NVV’s 10
 File Structure
• A File Structure should be according to a required format that the operating
system can understand.

• A file has a certain defined structure according to its type.

• A text file is a sequence of characters organized into lines.

• A source file is a sequence of procedures and functions.

• An object file is a sequence of bytes organized into blocks that are

understandable by the machine.

• When operating system defines different file structures, it also contains the
code to support these file structure. Unix, MS-DOS support minimum number
of file structure.
NVV’s 11
 File Access Methods
• Sequential Access
• Information in the file is processed in order, one record after the other.
• File operations are:
• read next()—reads the next portion of the file and automatically advances a file
pointer
• write next()—appends to the end of the file and advances to the end of the newly
written material
• reset to the beginning.
• skip forward or backward n records for some integer n

NVV’s Sequential-access file. 12

 File Access Methods

• Direct Access(Relative access)

• A file is made up of fixed-length logical records that allow programs to
read and write records rapidly in no particular order.

• The file is viewed as a numbered sequence of blocks or records

• No restrictions on the order of reading or writing for a direct-access file

• Useful for immediate access to large amounts of information

NVV’s 13
 File Access Methods
• Direct Access(Relative access)
• File operations are:
• read(n), where n is the block number
• write(n)
• position file(n)
• read(n) is equivalent to position file(n) and then read next()
• The block number provided by the user to the operating system is
normally a relative block number.
• A relative block number is an index relative to the beginning of the file.
• Relative block numbers allows the operating system to decide where the
file should be placed (called the allocation problem) and helps to prevent
the user from accessing portions of the file system that may not be part of
her file.
NVV’s • Some systems start their relative block numbers at 0; others start at 1. 14
 File Access Methods
• Direct Access(Relative access)

Simulation of sequential access on a direct-access file

NVV’s 15
 File Access Methods

• Other Access methods

• It can be built on top of a direct-access method.
• Involves the construction of an index for the file
• An index contains pointers to the various blocks
• To find a record in the file, 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.

NVV’s 16
 Directory structures
• A collection of nodes containing information about all files
• Both the directory structure and the files reside on disk

NVV’s 17
 A Typical File-system Organization

NVV’s 18
 Directory organization

• The directory is organized logically to obtain

• Efficiency – locating a file quickly
• Naming – convenient to users
• Two users can have same name for different files
• The same file can have several different names
• Grouping – logical grouping of files by properties, (e.g., all Java programs, all
games, …)

NVV’s 19
 Directory structures

• The directory can be viewed as a symbol table that translates file names into
their directory entries.
• The organization of a directory must allow us to insert entries, to delete
entries, to search for a named entry, and to list all the entries in the directory.
• operations performed on a directory:
• Search for a file
• Create a file
• List a directory
• Rename a file
• Traverse the file system

NVV’s 20
 Directory structures

• Types of Directory Structures:

• Single-Level Directory
• Two-Level Directory
• Tree-Structured Directories
• Acyclic-Graph Directories
• General Graph Directory

NVV’s 21
 Single-Level Directory
• The simplest directory structure
• All files are contained in the same directory

NVV’s 22
 Single-Level Directory
• Advantages :
• Since it is a single directory, so its implementation is very easy.
• If the files are smaller in size, searching will become faster.
• The operations like file creation, searching, deletion, updating are very
easy in such a directory structure
• Disadvantages :
• Naming Problem - Since all files are in the same directory, they must
have unique names
• Grouping Problem - can not possible group the same type of files
together
• Searching will become time taking if the directory is large.

NVV’s 23
 Two-Level Directory
• Each user has his own user file directory(UFD).
• The UFDs have similar structures, but each lists only the files of a single user.
• When a user job starts or a user logs in, the system’s master file directory(MFD) is
searched.
• The MFD is indexed by user name or account number, and each entry points to the
UFD for that user

NVV’s 24
 Two-Level Directory
• When a user refers to a particular file, only his own UFD is searched

• Different users may have files with the same name, as long as all the file names
within each UFD are unique.

NVV’s 25
 Two-Level Directory
• Advantages :
• we can give full path like /User-name/directoryname/.
• Different users can have the same directory as well as the file
name.
• Searching of files becomes easier due to pathname and user-
grouping
• Disadvantages :
• User is not allowed to share files with other users.
• Still, it not very scalable, two files of the same type cannot be
grouped together in the same user.

NVV’s 26
 Tree-Structured Directory
• Directory is maintained in the form of a tree of arbitrary height.
• This generalization allows the user to create their own subdirectories and to
organize their files accordingly.
• A tree structure is the most common directory structure.
• The tree has a root directory, and every file in the system has a unique path
name.
• A directory (or subdirectory) contains a set of files or subdirectories.
• All directories have the same internal format.
• One bit in each directory entry defines the entry as a file (0) or as a
subdirectory (1).
• Special system calls are used to create and delete directories.

NVV’s 27
 Tree-Structured Directory

NVV’s 28
 Tree-Structured Directory
• Path names can be of two types:
• Absolute and Relative.
• An absolute path name begins at the root and follows a path down to the
specified file, giving the directory names on the path.
• A relative path name defines a path from the current directory.

• Approaches to deletion – 2 type :

• To delete a directory, the user must first delete all the files in that directory
• To delete a directory, all that directory’s files and subdirectories are also to be
deleted(rm command in UNIX)

NVV’s 29
 Tree-Structured Directory
• Advantages
• Very general, since full pathname can be given
• Very scalable, the probability of name collision is less.
• Searching becomes very easy, we can use both absolute paths 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.

NVV’s 30
 Acyclic-Graph Directory

• An acyclic graph —is, a graph with no cycles—allows directories to share

subdirectories and files
• The same file or subdirectory may be in two different directories.
• The acyclic graph is a natural generalization of the tree-structured directory
scheme.
• With a shared file, only one actual file exists, so any changes made by one
person are immediately visible to the other.
• When people are working as a team, all the files they want to share can be
put into one directory.
• The UFD of each team member will contain this directory of shared files as
a subdirectory.

NVV’s 31
 Acyclic-Graph Directory

• Shared files and subdirectories can be implemented in

several ways as :
• 1. Creating a new directory entry called a link.
• A link is effectively a pointer to another file or subdirectory.
• A link may be implemented as an absolute or a relative path name.

• 2. Implementing shared files by simply duplicating all

information about them in both sharing directories.
• A major problem with duplicate directory entries is maintaining
consistency when a file is modified.

NVV’s 32
 Acyclic-Graph Directory

NVV’s 33
 Acyclic-Graph Directory

• Advantages
• We can share files
• Searching is easy due to different-different paths.
• Disadvantages
• More complex
• If the files are shared through linking, there may be a problem in the case
of deleting.
• If the link is a soft link: –
• A soft link (also known as Symbolic link) acts as a pointer or a
reference to the file name. It does not access the data available in the
original file. If the earlier file is deleted, the soft link will be pointing to
a file that does not exist anymore.
• Then after deleting the file, we left with a dangling pointer.
NVV’s 34
 Acyclic-Graph Directory

• If the link is a Hard link: –

• Hard link acts as a copy (mirrored) of the selected file.
• It accesses the data available in the original file.
• If the earlier selected file is deleted, the hard link to the file will still
contain the data of that file.
• To delete a file, we must delete all the references associated with it.

NVV’s 35
 General-Graph Directory

• In this type of directory, within a directory we can create cycle of the

directory where we can create multiple directories from more than one
parent directory.

• The main problem with this kind of directory structure is to calculate the
total size or space that has been taken by the files and directories.

NVV’s 36
 General-Graph Directory

NVV’s 37
 General-Graph Directory

• Advantages
• More flexible than the other directory structures
• Cycles are allowed
• Disadvantages
• Garbage collection is required.
• More costly, among other directory structures

NVV’s 38
 File Allocation Methods

• The allocation methods define how the files are stored in the disk
blocks.
• There are three main disk space or file allocation methods:
1. Contiguous Allocation
2. Linked Allocation
3. Indexed Allocation

• The main idea behind these methods is to provide:

• Efficient disk space utilization.
• Fast access to the file blocks.

NVV’s 39
 Contiguous Allocation
• Contiguous allocation requires that each file occupy a set of contiguous
blocks on the disk.

• Contiguous allocation of a file is defined by the disk address and length

(in block units) of the first block.

• If the file is n blocks long and starts at location b, then it occupies blocks
b, b+1,b+2,...,b+n−1.
• The directory entry for each file indicates
• Address of the starting block
• Length of the area allocated for this file .

NVV’s 40
 Contiguous Allocation

NVV’s 41
 Contiguous Allocation

• Both sequential and direct access can be supported by contiguous

allocation.
• For sequential access, the file system remembers the disk address of the last
block referenced and, when necessary, reads the next block.
• For direct access to block i of a file that starts at block b, we can
immediately access block b+i.

NVV’s 42
 Contiguous Allocation

• All these algorithms suffer from the problem of external fragmentation

• One strategy for preventing loss of significant amounts of disk space to
external fragmentation is to copy an entire file system onto another disk.
• The original disk is then freed completely, creating one large contiguous
free space.
• We then copy t he files back onto the original disk by allocating contiguous
space from this one large hole.
• It is called compaction and it takes more time

NVV’s 43
 Contiguous Allocation

• In modified contiguous-allocation scheme(Extent-based) a contiguous

chunk of space is allocated initially.

• Then, if that amount proves not to be large enough, another chunk of

contiguous space, known as an extent is added.

• The location of a file’s blocks is then recorded as a location and a block

count, plus a link to the first block of the next extent.

NVV’s 44
 Contiguous Allocation
• Advantages
• Both the Sequential and Direct Accesses are supported by this method.
• Extremely fast since the number of seeks are minimal because of contiguous
allocation of file blocks.
• Disadvantages
• Finding space for a new file is difficult.
• 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 Increasing file size is
difficult because it depends on the availability of contiguous memory at a
particular instance.

NVV’s 45
 Linked Allocation

• Linked allocation solves all problems of contiguous allocation.

• Each file is a linked list of disk blocks; the disk blocks may be scattered
anywhere on the disk.
• The directory contains a pointer to the first and last blocks of the file
• Each block contains a pointer to the next block.
• These pointers are not made available to the user.

NVV’s 46
 Linked Allocation

The last block 25 contains -1

indicating a null pointer and
does not point to any other
block.
NVV’s 47
 Linked Allocation

• To create a new file, simply create a new entry in the directory.

• Each directory entry has a pointer to the first disk block of the file.
• This pointer is initialized to null to signify an empty file.
• The size field is also set to 0.
• A write to the file causes the free-space management system to
find a free block, and this new block is written to and is linked to
the end of the file.
• To read a file, simply read blocks by following the pointers from
block to block.

NVV’s 48
 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.
• No external fragmentation
• This relatively better in terms of memory utilization.

NVV’s 49
 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.
• Need more space to maintain pointers.
• The usual solution to this problem is to collect blocks into multiples, called
clusters, and to allocate clusters rather than blocks.
• Reliability
• Causes error if a pointer were lost or damaged.
NVV’s 50
 Indexed Allocation
• Linked allocation solves the external-fragmentation and size-declaration
problems of contiguous allocation.

• Linked allocation cannot support direct access.

• Indexed allocation solves this problem by bringing all the pointers together
into one location called index block.

• In this scheme, a special block known as the Index block contains the
pointers to all the blocks occupied by a file.

NVV’s 51
 Indexed Allocation

NVV’s 52
 Indexed Allocation
• Each file has its own index block, which is an array of disk-block addresses.

• The ith entry in the index block points to the ith block of the file

• The directory contains the address of the index block

• When the file is created, all pointers in the index block are set to null.

• When the ith block is first written, a block is obtained from the free-space
manager, and its address is put in the ith index-block entry.

NVV’s 53
 Indexed Allocation
• An index block is normally one disk block. Thus, it can be read and written
directly by itself.
• 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:
• Linked scheme.
• This scheme links several index blocks together for large files
• Every index block would then contain a pointer or the address to the next
index block
• Example:
• An index block might contain a small header giving the name of the file
and a set of the first 100 disk-block addresses. The next address (the last
word in the index block) is null(for a small file)or is a pointer to
another index block.

NVV’s 54
 Indexed Allocation

• Multilevel index
• It uses a first-level index block to point to a set of second-level index
blocks, which in turn point to the file blocks.

• To access a block, the operating system uses the first-level index to find a
second-level index block and then uses that block to find the desired data
block.

• This approach could be continued to a third or fourth level, depending on

the desired maximum file size.

NVV’s 55
 Indexed Allocation

• Combined 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
• 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, ie, 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.

NVV’s 56
 Indexed Allocation

• Combined scheme
• 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.

• 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.

NVV’s 57
 Indexed Allocation

NVV’s
The UNIX inode 58
 Indexed Allocation
• Advantages
• Supports direct access to the blocks occupied by the file and therefore
provides fast access to the file blocks.
• No 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.
• In linked allocation we lose the space of only 1 pointer per block.

NVV’s 59
 Protection

• Users want to protect the information stored in the file system from
improper access(Protection) and physical damage(Reliability).

• Reliability is generally provided by duplicate copies of files

• Protection mechanisms provide controlled access by limiting the types of

file access that can be made.

NVV’s 60
 Protection

• Types of Access
• The files which have direct access of the any user have the need of
protection.
• The files which are not accessible to other users doesn’t require any
kind of protection.
• The mechanism of the protection provide the facility of the controlled
access by just limiting the types of access to the file.
• Access can be given or not given to any user depends on several
factors, one of which is the type of access required.

NVV’s 61
 Protection

• Types of Access
• The operations that can be controlled by access control are:
• Read - Read from the file.
• Write - Write or rewrite the file.
• Execute - Load the file into memory and execute it.
• Append - Write new information at the end of the file.
• Delete - Delete the file and free its space for possible reuse.
• List - List the name and attributes of the file

NVV’s 62
 Access Control

• There are numerous ways to access any file

• One of the prominent way is to associate identity-dependent access with

all files and directories.

• A list is created called the access-control list(ACL) which enlists the names
of users and the type of access granted to them.

NVV’s 63
 Access Control

• The main problem with access lists is their length.

• This technique has two undesirable consequences:

• Constructing such a list may be a tedious and unrewarding task, especially if we do

not know in advance the list of users in the system.
• The directory entry, previously of fixed size, now must be of variable size, resulting in
more complicated space management

NVV’s 64
 Access Control

• These problems can be resolved by use of a condensed version

of the access list.
• To condense the length of the access-control list, many systems
recognize three classification of users in connection with each
file:
• Owner – Owner is the user who has created the file.
• Group – A group is a set of members who has similar needs, and they
are sharing the same file.
• Universe – In the system, all other users are under the category called
universe.

NVV’s 65
 Access Lists and Groups

• Mode of access: read, write, execute

• Three classes of users on Unix / Linux
RWX
a) owner access 7  111
RWX
b) group access 6  110
RWX
c) public access 1  001

• For a particular file (say game) or subdirectory, define an appropriate access.

chmod: change file access permissions

Windows 7 Access-Control List Management
A Sample UNIX Directory Listing