FCB

Single Level Directory

The simplest method is to have one big list of all the files on the disk. The entire
system will contain only one directory which is supposed to mention all the files
present in the file system. The directory contains one entry per each file present
on the file system.

This type of directories can be used for a simple system.

Advantages
 1. Implementation is very simple.
2. If the sizes of the files are very small then the searching becomes faster.
3. File creation, searching, deletion is very simple since we have only one directory.

Disadvantages
1. We cannot have two files with the same name.
2. The directory may be very big therefore searching for a file may take so much
time.
3. Protection cannot be implemented for multiple users.
4. There are no ways to group same kind of files.
5. Choosing the unique name for every file is a bit complex and limits the number of
files in the system because most of the Operating System limits the number of
characters used to construct the file name.

1Single Level Directory:

===================
=> A single directory for all users

Root Directory

F1 F2 F3 F4

Adv:
Simple to implement
Dis:
=>Naming Conflict
=>Grouping Problem
Two Level Directory
In two level directory systems, we can create a separate directory for each user.
There is one master directory which contains separate directories dedicated to
each user. For each user, there is a different directory present at the second
level, containing group of user's file. The system doesn't let a user to enter in
the other user's directory without permission.

Characteristics of two level directory system

1. Each files has a path name as /User-name/directory-name/
2. Different users can have the same file name.
3. Searching becomes more efficient as only one user's list needs to be traversed.
4. The same kind of files cannot be grouped into a single directory for a particular
user.

Every Operating System maintains a variable as PWD which contains the

present directory name (present user name) so that the searching can be done
appropriately.

2.Two Level Directory:

==================
=> Separate directory for each user
Root Directory

User1 User2 User3

F1 F2
F1 F3

F4
Adv:
=> Can have same file name for different users
=>Efficient searching

Disadvantage:
Grouping Problem

Tree Structured Directory

In Tree structured directory system, any directory entry can either be a file or
sub directory. Tree structured directory system overcomes the drawbacks of two
level directory system. The similar kind of files can now be grouped in one
directory.

Each user has its own directory and it cannot enter in the other user's directory.
However, the user has the permission to read the root's data but he cannot
write or modify this. Only administrator of the system has the complete access
of root directory.
Searching is more efficient in this directory structure. The concept of current
working directory is used. A file can be accessed by two types of path, either
relative or absolute.

Absolute path is the path of the file with respect to the root directory of the
system while relative path is the path with respect to the current working
directory of the system. In tree structured directory systems, the user is given
the privilege to create the files as well as directories.

Permissions on the file and directory

A tree structured directory system may consist of various levels therefore there
is a set of permissions assigned to each file and directory.

The permissions are R W X which are regarding reading, writing and the
execution of the files or directory. The permissions are assigned to three types
of users: owner, group and others.

There is a identification bit which differentiate between directory and file. For a
directory, it is d and for a file, it is dot (.)

The following snapshot shows the permissions assigned to a file in a Linux based
system. Initial bit d represents that it is a directory.
3.Tree Structured Directory:
=======================
Or Hierarchical Directory

Root Directory

User directories

Each user directory can have files and sub

directories.

Adv: Efficient Searching

Grouping Capability

Dis:

No Shared Files or Directories: In a strict tree

structure, each file or directory can have only
one parent. This restriction prevents sharing
files or subdirectories between different users
or groups, which can be limiting in collaborative
environments.

Acyclic-Graph Structured Directories

The tree structured directory system doesn't allow the same file to exist in
multiple directories therefore sharing is major concern in tree structured
directory system. We can provide sharing by making the directory an acyclic
graph. In this system, two or more directory entry can point to the same file or
sub directory. That file or sub directory is shared between the two directory
entries.

These kinds of directory graphs can be made using links or aliases. We can have
multiple paths for a same file. Links can either be symbolic (logical) or hard link
(physical).

If a file gets deleted in acyclic graph structured directory system, then

1. In the case of soft link, the file just gets deleted and we are left with a
dangling pointer.

2. In the case of hard link, the actual file will be deleted only if all the references
to it gets deleted.
File Access Methods:
=================

1.Sequential Access
2.Direct Access/Relative Access/Random Access
3.Indexed Access

1. Sequential Access:
===============
Information in file is accessed in sequential
manner that is record by record.
Ex : File containing 100 records, currently at
50th record and access 75th record. To
access 75th record, we need to access all the
records from 50th record to 75th record
sequentially one by one.
It require more time

Current Position
Read next
Write next
Reset/Rewind

Ex: Magnetic Tape

1. Direct Access:
===========
In direct access, we can access any record
directly.
Suppose file has 100 records. Assume we are
at 50th record, and access 75th record. In
this case, we can directly access 75th record.

Ex: CD ROM , DVD

 Read n ( n is the block number)
Write n
Position to n
Ex: Seek
position to 75

Reset:
cp =0

Read:
Read cp
cp = cp+1

Write:
write cp
cp =cp+1

3.Indexed Access:
===============
Hard Disk Blocks
# of File blocks in F1 = 2^11 B/2^9 B = 4 Blocks

Placing the logical file blocks in physical disk

blocks

File Size =2049B

Allocation Method

 An allocation method refers to how disk blocks are

allocated for files:

 Contiguous

 Linked

 Indexed
1.Contiguous Allocation Method:

In this technique, files are stored in a contiguous block in disk space.

Advantages:
=>It is simple to implement
=> It is suitable for sequential files.

Disadvantages:
=> It's difficult to find contiguous blocks
=>External fragmentation

2.Linked Allocation Method:

In this technique, files are stored in a linked list manner in disk blocks. Each block
contains the address to the next block.
Advantages:
==========
=>No external fragmentation
=>Suitable for sequential files
Disadvantages:
============
=>Pointer occupies some space within each block
=>It need more access time

3.Indexed Allocation Method:

=======================
Each file has its own index block which is an array of
disk-block addresses.

Advantages:
==========
=> It supports both sequential and direct access
=>No external fragmentation
=> When file size increases, we can easily add new
blocks to the index block.
Free Space Management
The main responsibility of file system is to
allocate free disk blocks to files.
=>Keeps track of free disk blocks

1.Bitmap
2.Linked List

Free Space Management

A file system is responsible to allocate the free blocks to the file therefore it has
to keep track of all the free blocks present in the disk. There are mainly two
approaches by using which, the free blocks in the disk are managed.

1. Bit Vector
In this approach, the free space list is implemented as a bit map vector. It
contains the number of bits where each bit represents each block.

If the block is empty then the bit is 1 otherwise it is 0. Initially all the blocks are
empty therefore each bit in the bit map vector contains 1.

LAs the space allocation proceeds, the file system starts allocating blocks to the
files and setting the respective bit to 0.

2. 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.
Methods of Free Space Management in OS
There are four methods of doing free space management in operating systems. These
are as follows-
 Bit Vector
 Linked List
 Grouping
 Counting

First, we will discuss the Bit Vector method.

Bit Vector
The first method that we will discuss is the bit vector method. Also known as the bit
map, this is the most frequently used method to implement the free space list. In this
method, each block in the hard disk is represented by a bit (either 0 or 1). If a block has
a bit 0 means that the block is allocated to a file, and if a block has a bit 1 means that
the block is not allocated to any file, i.e., the block is free.
For example, consider a disk having 16 blocks where block numbers 2, 3, 4, 5, 8, 9, 10,
11, 12, and 13 are free, and the rest of the blocks, i.e., block numbers 0, 1, 6, 7, 14 and
15 are allocated to some files. The bit vector for this disk will look like this-
We can find the free block number from the bit vector using the following method-
Block number = (Number of bits per word )* (number of 0-value words) + (offset of
first bit)
We will now find the first free block number in the above example.
The first group of 8 bits (00111100) constitutes a non-zero word since all bits are not 0.
After finding the non-zero word, we will look for the first 1 bit. This is the third character
of the non-zero word. Hence, offset = 3.
Therefore, the first free block number = 8 * 0 + 3 = 3.
Advantages
The advantages of the bit vector method are-
 It is simple to understand.
 It is an efficient method.
 It occupies less memory.
Disadvantages
The disadvantages of the bit vector method are-
 For finding a free block, the operating system may need to search the entire
bit vector.
 To detect the first 1 in a word that is not 0 using this method, special
hardware support is needed.
 Keeping the bit vector in the main memory is possible for smaller disks but
not for larger ones. For example, a 1.3 GB disk with 512-byte blocks would
need a bit vector of over 332 KB to track its free blocks. Giving away 332 KB
just to maintain its free block space is not so efficient in the long run.
Linked List
Another method of doing free space management in operating systems is a linked list.
In this method, all the free blocks existing in the disk are linked together in a linked list.
The address of the first free block is stored somewhere in the memory. Each free block
contains a pointer that contains the address to the next free block. The last free block
points to null, indicating the end of the linked list.
For example, consider a disk having 16 blocks where block numbers 3, 4, 5, 6, 9, 10,
11, 12, 13, and 14 are free, and the rest of the blocks, i.e., block numbers 1, 2, 7, 8, 15
and 16 are allocated to some files. If we maintain a linked list, then Block 3 will contain a
pointer to Block 4, and Block 4 will contain a pointer to Block 5.
Similarly, Block 5 will point to Block 6, Block 6 will point to Block 9, Block 9 will point to
Block 10, Block 10 will point to Block 11, Block 11 will point to Block 12, Block 12 will
point to Block 13 and Block 13 will point to Block 14. Block 14 will point to null. The
address of the first free block, i.e., Block 3, will be stored somewhere in the memory.
This is also represented in the following figure-
Advantages
The advantages of the linked list method are-
 External fragmentation is prevented by linked list allocation. As opposed to
contiguous allocation, this prevents the wasting of memory blocks.
 It is also quite simple to make our file bigger. All we have to do is link a new
file block to our linked list. The file can so expand as long as memory blocks
are available.
 Since the directory only needs to hold the starting and ending pointers of the
file, linked list allocation places less strain on it.
Disadvantages
The disadvantages of the linked list method are-
 This method is inefficient since we need to read each block to traverse the
list, which takes more I/O time.
 There is an overhead in maintaining the pointer.
 There is no provision for random or direct memory access in linked list
allocation. We must search through the full linked list to locate the correct
block if we wish to access a certain file block.
You can also read about the Multilevel Queue Scheduling.
Grouping
The third method of free space management in operating systems is grouping. This
method is the modification of the linked list method. In this method, the first free block
stores the addresses of the n free blocks. The first n-1 of these blocks is free. The last
block in these n free blocks contains the addresses of the next n free blocks, and so
on.
For example, consider a disk having 16 blocks where block numbers 3, 4, 5, 6, 9, 10,
11, 12, 13, and 14 are free, and the rest of the blocks, i.e., block numbers 1, 2, 7, 8, 15
and 16 are allocated to some files.
If we apply the Grouping method considering n to be 3, Block 3 will store the addresses
of Block 4, Block 5, and Block 6. Similarly, Block 6 will store the addresses of Block 9,
Block 10, and Block 11. Block 11 will store the addresses of Block 12, Block 13, and
Block 14. This is also represented in the following figure-

This method overcomes the disadvantages of the linked list method. The addresses of a
large number of free blocks can be found quickly, just by going to the first free block or
the nth free block. There is no need to traverse the whole list, which was the situation in
the linked list method.
Advantages
The advantages of the grouping method are-
 The addresses of a large number of free blocks can be found quickly.
 This method has the benefit of making it simple to locate the addresses of a
collection of empty disk blocks.
 It's a modification of the free list approach. So, there is no need to traverse
the whole list.
Disadvantages
The advantages of the grouping method are-
 The space of one block is wasted in storing addresses. Since the nth block
is used to store the addresses of next n free blocks.
 We only save the address of the first free block since we are unable to
maintain a list of all n free disk addresses.
 There is an overhead in maintaining the index of blocks.
Counting
This is the fourth method of free space management in operating systems. This method
is also a modification of the linked list method. This method takes advantage of the fact
that several contiguous blocks may be allocated or freed simultaneously. In this method,
a linked list is maintained but in addition to the pointer to the next free block, a count of
free contiguous blocks that follow the first block is also maintained. Thus each free
block in the disk will contain two things-
1. A pointer to the next free block.
2. The number of free contiguous blocks following it.

For example, consider a disk having 16 blocks where block numbers 3, 4, 5, 6, 9, 10,
11, 12, 13, and 14 are free, and the rest of the blocks, i.e., block numbers 1, 2, 7, 8, 15
and 16 are allocated to some files.
If we apply the counting method, Block 3 will point to Block 4 and store the count 4
(since Block 3, 4, 5, and 6 are contiguous). Similarly, Block 9 will point to Block 10 and
keep the count of 6 (since Block 9, 10, 11, 12, 13, and 14 are contiguous). This is also
represented in the following figure-

This method also overcomes the disadvantages of the linked list method since there is
no need to traverse the whole list.
Advantages
The advantages of the counting method are-
 Fast allocation of a large number of consecutive free blocks.
 Random access to the free block is possible.
 The overall list is smaller in size.
Disadvantages
The disadvantages of the counting method are-
 Each free block requires more space for keeping the count in the disk.
 For efficient insertion, deletion, and traversal operations. We need to store
the entries in B-tree.
 The entire area is reduced.