File Management

File
• A file is a named collection of related
information that is recorded on secondary
storage
 File Attributes
• Name
• Identifier
• Type
• Location
• Size
• Protection
• Time, date and user identification
 File operations
• Create • Delete
• Open • Truncate
• Write • Close
• Read • Append
• Reposition or seek • Rename
File Types
 Access Methods
• There are three ways to access a file into a computer
system:
– Sequential-Access
– Direct Access
– Index sequential Method
 Sequential Access
• It is the simplest access method. Information in the
file is processed in order, one record after the other.
This mode of access is by far the most common; for
example, editor and compiler usually access the file
in this fashion.
 Key Points
• Data is accessed one record right after another record in an
order.
• When we use read command, it move ahead pointer by one
• When we use write command, it will allocate memory and
move the pointer to the end of the file
• Such a method is reasonable for tape.
 Advantages of Sequential Access Method :

• It is simple to implement this file access mechanism.

• It uses lexicographic order to quickly access the next
entry.
 Disadvantage

• If the file record that needs to be accessed next

is not present next to the current record, this
type of file access method is slow.
 Direct Access Method
• Direct access method also known as relative access
method. A fixed-length logical record that allows the
program to read and write record rapidly in no
particular order.
 Advantages
• The files can be immediately accessed decreasing the average
access time.
• In the direct access method, in order to access a block, there is
no need of traversing all the blocks present before it.
 Index Sequential Method
• It is the other method of accessing a file that is built on the top
of the sequential access method. These methods construct an
index for the file. The index, like an index in the back of a
book, contains the pointer to the various blocks. To find a
record in the file, we first search the index, and then by the
help of pointer we access the file directly.
 Directory Structure
• Single level directory
• Two level directory
• Tree-structured directory or Hierarchical
directory
 Single Level Directory
• It is the simplest directory structure. In a
single-level directory, there is only one
directory in the system, meaning there is only
one folder, and all the files are stored in that
single directory. There is no way to segregate
important files from non-important files.
• Implementation of a single-level directory is
the simplest.
 Two Level Directory
• In a two-level directory structure, there is a
master node that has a separate directory for
each user. Each user can store the files in that
directory. It can be practically thought of as a
folder that contains many folders, each for a
particular user, and now each user can store
files in the allocated directory just like a single
level directory.
 Tree-structured directory or Hierarchical
directory
• This type of directory is used in our PCs. The
biggest disadvantage of a two-level directory was
that one could not create sub-directories in a
directory. The tree-structured directory solved
this problem. In a tree-structured directory,
there is a root directory at the peak. The root
directory contains directories for each user. The
users can, however, create sub directories inside
their directory and also store the files.
 Acyclic Graph Directory
• In this type of directory, we can access a file or
a subdirectory from multiple directories.
Hence files can be shared between directories.
It is designed in such a way that multiple
directories point to a particular directory or
file with the help of links.
 General Graph Directory
• This is an extension to the acyclic-graph
directory. In the general-graph directory, there
can be a cycle inside a directory.
 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.
• Contiguous Allocation
• Linked Allocation
• Indexed Allocation
• The main idea behind these methods is to
provide:
• Efficient disk space utilization.
• Fast access to the file blocks.
 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.
• The directory entry for a file with contiguous
allocation contains
• Address of starting block
• Length of the allocated portion.
 Advantages
• Both the Sequential and Direct Accesses are
supported by this. For direct access, the
address of the kth 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 List 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.
 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.
 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.
• 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:
 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.
 Free Space Management
• Free space management is a critical aspect of
operating systems as it involves managing the
available storage space on the hard disk or
other secondary storage devices. The
operating system uses various techniques to
manage free space and optimize the use of
storage devices
 Free Space Management Techniques
• Bit vector
• Linked List
• Grouping
 Bit vector
• A Bitmap or Bit Vector is series or collection
of bits where each bit corresponds to a disk
block. The bit can take two values: 0 and 1: 0
indicates that the block is allocated and 1
indicates a free block.
 Linked List
• It is another approach for free space
management. This approach suggests linking
together all the free blocks and keeping a
pointer in the cache which points to the first
free block.
• Therefore, all the free blocks on the disks will
be linked together with a pointer. Whenever a
block gets allocated, its previous free block
will be linked to its next free block.
 Grouping
• This approach stores the address of the free
blocks in the first free block. The first free
block stores the address of some, say n free
blocks. Out of these n blocks, the first n-1
blocks are actually free and the last block
contains the address of next free n blocks.
An advantage of this approach is that the
addresses of a group of free disk blocks can be
found easily.
 Directory Implementation
• Directory Implementation using Singly Linked
List
– The implementation of directories using a
singly linked list is easy to program but is time-
consuming to execute. Here we implement a
directory by using a linear list of filenames with
pointers to the data blocks.
• To create a new file the entire list has to be checked such
that the new directory does not exist previously.
• The new directory then can be added to the end of the list
or at the beginning of the list.
• In order to delete a file, we first search the directory with
the name of the file to be deleted. After searching we can
delete that file by releasing the space allocated to it.
• To reuse the directory entry we can mark that entry as
unused or we can append it to the list of free directories.
• To delete a file linked list is the best choice as it takes less
time.
 Disadvantage
• The main disadvantage of using a linked list is
that when the user needs to find a file the
user has to do a linear search.
Directory Implementation using Hash Table

• In this method, we use a hash table along with

the linked list. Here the linked list stores the
directory entries, but a hash data structure is
used in combination with the linked list.
• In the hash table for each pair in the directory
key-value pair is generated. The hash function
on the file name determines the key and this
key points to the corresponding file stored in
the directory. This method efficiently decreases
the directory search time as the entire list will
not be searched on every operation. Using the
keys the hash table entries are checked and
when the file is found it is fetched.
 Disadvantage
• The major drawback of using the hash table is
that generally, it has a fixed size and its
dependency on size.