FILE SYSTEM IMPLEMENTATION

1. File- System Structure

To provide an efficient and convenient access to the disk, the operating system imposes one or
more file systems to allow the data to be stored or retrieved such as FAT, FAT 32, NTFS, UFS etc

The file system generally composed of many different levels. The structure is shown in figure :

Each level in the design uses the features of lower levels to create new features for use by
higher levels.

The lowest level , the I/O control , consists of device drivers and interrupt handlers to transfer
information between main memory and disk.

The basic file system contains generic commands for read/write operations.

The file organization module knows about logical and physical blocks. it translate logical block
address to physical block address.

The logical file system manages metadata information which includes all file system structure,
without actual [Link] maintains file structure via file control blocks(FCB)

2. File-system implementation
On-disk and in-memory structures are used to implement a file system.\

The on-disk structures include:

 Boot Control Block-Information needed to boot an operating system from

partition.
 Partition Control Block-contains partition details such as no. of blocks in
partition, size of block, bfree-block count, free FCB count etc.
 Directory structure is used to organize the files
 FCB- contains file permissions, ownership, size and location of data blocks.
The in-memory structures include:

 In-memory partition table containing information about mounted partitions.

 In-memory directory structure that holds directory information about recently used directories
 System-wide open-file table- contains copy of FCB of each open file
 Per-process open-file table- contains pointer to the entry in system wide table.

3. Virtual file sytems

3 layers:

File system interface—open, read, write, and close calls, and , file descriptors.

VFS layer—has 2 functions:

1. distinguishes local file system from remote ones using vnode(designator for network wide
unique file) .

2. Local files are distinguished according to file system types.

File system types—implements file system types, or remote file system protocol.

DIRECTORY IMPLEMENETATION

There are mainly two algorithms which are used in these days.

1. Linear List
In this algorithm, all the files in a directory are maintained as singly lined list. Each file contains
the pointers to the data blocks which are assigned to it and the next file in the directory. The list
needs to be traversed in case of every operation (creation, deletion, updating, etc) on the files
2. Hash table

A key-value pair for each file in the directory gets generated and stored in the hash table. The
key can be determined by applying the hash function on the file name while the key points to the
corresponding file stored in the directory.

Allocation methods
There are various methods which can be used to allocate disk space to the files.

here are following methods which can be used for allocation.

1. Contiguous Allocation.
2. Linked Allocation
3. Indexed Allocation
1. Linked Indexed Allocation
2. Multilevel Indexed Allocation
3. Combined Scheme
1. Contiguous Allocation
If the blocks are allocated to the file in such a way that all the logical blocks of the
file get the contiguous physical block in the hard disk then such allocation scheme
is known as contiguous allocation.

In the image shown below, there are three files in the directory. The starting block
and the length of each file are mentioned in the table. We can check in the table
that the contiguous blocks are assigned to each file as per its need.

Advantages
1. It is simple to implement.
2. Supports Random Access into files.

Disadvantages
1. There will be external fragmentation.

2. 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 ‘jeep’ 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
 .

Advantages:
 This is very flexible in terms of file size.
 This method does not suffer from external fragmentation.
 Disadvantages:
 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 cannot directly access the blocks
of a file.

FAT-File Allocation Table

The main disadvantage of linked list allocation is that the Random access to a
particular block is not provided. In order to access a block, we need to access all its
previous blocks.

File Allocation Table overcomes this drawback of linked list allocation. In this
scheme, a file allocation table is maintained, which gathers all the disk block links.
The table has one entry for each disk block and is indexed by block number.
3. Indexed Allocation

Limitation of FAT-The more the number of blocks, the more will be the size of
FAT.

Therefore, we need to allocate more space to a file allocation table.

Instead of maintaining a file allocation table of all the disk pointers, Indexed
allocation scheme stores all the disk pointers in one of the blocks called as indexed
block. Indexed block doesn't hold the file data, but it holds the pointers to all the
disk blocks allocated to that particular file. Directory entry will only contain the
index block address.

Advantages
1. Supports direct access

Disadvantages
1. Size of a file depends upon the number of pointers, a index block can hold.
2. Having an index block for a small file is totally wastage.

4. Linked Index Allocation

In linked index allocation,

o Small header giving the name of the file

 o Set of the first 100 block addresses
o Pointer to another index block

For the larger files, the last entry of the index block is a pointer which points to
another index block. This is also called as linked schema.

Following mechanisms can be used to resolve this:

1. Linked 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.
2. Multilevel index: In this policy, a first level index block is used to point to the
second level index blocks which inturn points to the disk blocks occupied by the
file. This can be extended to 3 or more levels depending on the maximum file size.
3. 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 and the remaining space of Inode is used to store the Disk Block addresses
which contain the actual file as shown in the image below. 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.
 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

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.
The given instance of disk blocks on the disk in Figure 1 (where green blocks are allocated) can
be represented by a bitmap of 16 bits as: 0000111000000110.

2. Linked List

In this approach, the free disk blocks are linked together i.e. a free block contains a pointer to
the next free block. The block number of the very first disk block is stored at a separate location
on disk and is also cached in memory.

In Figure-2, the free space list head points to Block 5 which points to Block 6, the next free block
and so on. The last free block would contain a null pointer indicating the end of free list.
 3. 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.
4. Counting –
This approach stores the address of the first free disk block and a number n of free
contiguous disk blocks that follow the first block.
Every entry in the list would contain:
1. Address of first free disk block
2. A number n
For example, in Figure-1, the first entry of the free space list would be: ([Address of Block 5], 2),
because 2 contiguous free blocks follow block 5.

DISK STRUCTURE
The actual physical details of a modern hard disk may be quite complicated.
Simply, there are one or more surfaces, each of which contains several tracks,
each of which is divided into sectors.
There is one read/write head for every surface of the disk. Also, the same track on
all surfaces is known as a cylinder, When talking about movement of the
read/write head, the cylinder is a useful concept, because all the heads (one for
each surface), move in and out of the disk together.

We say that the “read/write head is at cylinder #2", when we mean that the top
read/write head is at track #2 of the top surface, the next head is at track #2 of
the next surface, the third head is at track #2 of the third surface, etc.
 DISK Scheduling

The operating system must be fare enough to satisfy each request and at the same time,
operating system must maintain the efficiency and speed of process execution.

The technique that operating system uses to determine the request which is to be
satisfied next is called disk scheduling.

Seek Time
Seek time is the time taken in locating the disk arm to a specified track where the
read/write request will be satisfied.

Rotational Latency
It is the time taken by the desired sector to rotate itself to the position from where it
can access the R/W heads.

Transfer Time
It is the time taken to transfer the data.

Disk Access Time

Disk access time is given as,

Disk Access Time = Rotational Latency + Seek Time + Transfer Time

Purpose of Disk Scheduling

The main purpose of disk scheduling algorithm is to select a disk request from the
queue of IO requests and decide the schedule when this request will be processed.

Disk Scheduling Algorithms

o FCFS scheduling algorithm
o SSTF (shortest seek time first) algorithm
o SCAN scheduling
o C-SCAN scheduling
o LOOK Scheduling
o C-LOOK scheduling

1. FCFS Scheduling Algorithm

It is the simplest Disk Scheduling algorithm. It services the IO requests in the order in
which they arrive.
Example
Consider the following disk request sequence for a disk with 100 tracks 45, 21, 67, 90, 4,
50, 89, 52, 61, 87, 25

Head pointer starting at 50 and moving in left direction. Find the number of head
movements in cylinders using FCFS scheduling.

Solution

2. SSTF Scheduling Algorithm

Shortest seek time first (SSTF) algorithm selects the disk I/O request which requires the
least disk arm movement from its current position regardless of the direction. It reduces
the total seek time as compared to FCFS.

It allows the head to move to the closest track in the service queue.

Example
Consider the following disk request sequence for a disk with 100 tracks

45, 21, 67, 90, 4, 89, 52, 61, 87, 25

Head pointer starting at 50. Find the number of head movements in cylinders using
SSTF scheduling.
Solution:

3. SCAN algorithm
It is also called as Elevator Algorithm. In this algorithm, the disk arm moves into a
particular direction till the end, satisfying all the requests coming in its path,and then it
turns backand moves in the reverse direction satisfying requests coming in its path.

It works in the way an elevator works, elevator moves in a direction completely till the
last floor of that direction and then turns back.

Example
Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78 of Java - Javatpoint

Head pointer starting at 54 and moving in left direction.

4. C-SCAN algorithm
In C-SCAN algorithm, the arm of the disk moves in a particular direction servicing
requests until it reaches the last cylinder, then it jumps to the last cylinder of the
opposite direction without servicing any request then it turns back and start moving in
that direction servicing the remaining requests.

Example
Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78

Head pointer starting at 54 and moving in left direction.

5. Look Scheduling
It is like SCAN scheduling Algorithm to some extant except the difference that, in this
scheduling algorithm, the arm of the disk stops moving inwards (or outwards) when no
more request in that direction exists. This algorithm tries to overcome the overhead of
SCAN algorithm which forces disk arm to move in one direction till the end regardless of
knowing if any request exists in the direction or not.

Example
Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78

Head pointer starting at 54 and moving in left direction. Find the number of head
movements in cylinders using LOOK scheduling.
 Disk management
Disk management of the operating system includes:
 Disk Formatting

 Boot block

 Bad block

Disk Formatting

Before a disk stores data, it is divided into sectors that the disk controller can
read and write. This process is called low-level formatting/physical formatting
The data structure for a sector consists of Header, data, trailer. Header and
trailer contains disk controlling information such as sector number and error
correction codes(ECC).

Boot block:

 When the computer is turned on or restarted, the program stored in the initial
bootstrap ROM finds the location of the OS kernel from the disk, loads the
kernel into memory, and runs the OS. start.
 To change the bootstrap code, you need to change the ROM and hardware
chip. Only a small bootstrap loader program is stored in ROM instead.
 The full bootstrap code is stored in the “boot block” of the disk.
 A disk with a boot partition is called a boot disk or system disk.
Bad Blocks:

 Disks are error-prone because moving parts have small tolerances.

 Most disks are even stuffed from the factory with bad blocks and are
handled in a variety of ways.
 The controller maintains a list of bad blocks.
 The controller can instruct each bad sector to be logically replaced with one
of the spare sectors. This scheme is known as sector sparing or transfer.
 A soft error triggers the data recovery process.
 However, unrecoverable hard errors may result in data loss and require
manual intervention.