Operating Systems

Virtualization and File System

Dr. Pradeep K V
Associate Professor (Sr.)
School of Computer Science and Engineering
VIT - Chennai

Dr. Pradeep K V Operating Systems 1/ 75

Contents...!

Introduction to Virtual Machines

History
Benefits and Features
Building Blocks
Types of Virtual Machines and Their Implementations
Virtualization and Operating-System Components
File (Attributes, Access Methods)
Disk and Directory Structure
Memory Mapping Files

Dr. Pradeep K V Operating Systems 2/ 75

Introduction to Virtual Machines I

Virtual Machine
It is a virtual environment which functions as a virtual computer system
with its own CPU, memory, network interface, and storage, created on a
physical hardware system.
VMs are isolated from the rest of the system, and multiple VMs can exist
on a single piece of hardware, like a server.
It has its own operating system and software that will facilitate the
resources to virtual computers.

Characteristics of virtual machines

Multiple OS systems use the same hardware and partition resources
between virtual computers.
Separate Security and configuration identity.
Ability to move the virtual computers between the physical host computers
as holistically integrated files.

Dr. Pradeep K V Operating Systems 3/ 75

Introduction to Virtual Machines II

Benefits:
The multiple OS environments exist simultaneously on the same machine,
which is isolated from each other.
VM offers an instruction set architecture which differs from real computer.
Using VM’s, It’s easy to maintenance, application provisioning, availability
and convenient recovery.

Dr. Pradeep K V Operating Systems 4/ 75

Overview of VM
Fundamental idea : Abstract hardware of a single computer into several
different execution environments
- Similar to layered approach, in turn each layer creates virtual system (virtual
machine, or VM) on which operation systems or applications can run
Several components
- Host – underlying hardware system
- Virtual machine manager (VMM) or Hypervisor – creates and runs VM’s
by providing interface that is identical to the host
- Guest – process provided with virtual copy of the host Usually an operating
system
Single physical machine can run multiple operating systems concurrently,
each in its own virtual machine

Dr. Pradeep K V Operating Systems 5/ 75

Hypervisor

It is also known as a Virtual Machine Monitor (VMM). It is a piece of

software that allows us to build and run virtual machines which are
abbreviated as VMs.
Itr allows a single host computer to support multiple virtual machines
(VMs) by sharing resources including memory and processing.

Dr. Pradeep K V Operating Systems 6/ 75

Types of Hypervisor

Type 0 : Hardware-based solutions that provide support for virtual

machine creation and management via firmware.
Example : IBM LPARs and Oracle LDOMs.
Type 1 : OS like software built to provide virtualization
Example : VMware ESX, Joyent SmartOS, and Citrix XenServer
Type 1 : Also includes general-purpose OS that provide standard
functions as well as VMM functions
Example : Including Microsoft Windows Server with HyperV and RedHat
Linux with KVM
Type 2 : Applications that run on standard OS but provide VMM features
to guest OS.
Example : VMware Workstation and Fusion, Parallels Desktop, and
Oracle VirtualBox.
Other Variations Include - Para-virtualization, Programming Environment
Virtualization, Application Containment and Emulator

Dr. Pradeep K V Operating Systems 7/ 75

History

First appeared in IBM mainframes in 1972.

Allowed multiple users to share a batch-oriented system
Formal definition of virtualization helped move it beyond IBM
1 A VMM provides an environment for programs that is essentially identical
to the original machine
2 Programs running within that environment show only minor performance
decreases
3 The VMM is in complete control of system resources

In late 1990s Intel CPUs fast enough for researchers to try virtualization
on general purpose PCs Xen and VMware created technologies, still used
today Virtualization has expanded to many OSes, CPUs, VMMs

Dr. Pradeep K V Operating Systems 8/ 75

Benefits and Features

Host system protected from VMs, VMs protected from each other
- i.e., A virus less likely to spread
- Sharing is provided though via shared file system volume, network
communication
Freeze, suspend, running VM
- Then can move or copy somewhere else and resume
- Snapshot of a given state, able to restore back to that state Some VMMs
allow multiple snapshots per VM
- Clone by creating copy and running both original and copy
Great for OS research, better system development efficiency
Run multiple, different OSes on a single machine
- Consolidation, app dev, . . .
Templating – create an OS + application VM, provide it to customers,
use it to create multiple instances of that combination
Live migration – move a running VM from one host to another!
- No interruption of user access
All those features taken together -> cloud computing
- Using APIs, programs tell cloud infrastructure (servers, networking, storage)
to create new guests, VMs, virtual desktops

Dr. Pradeep K V Operating Systems 9/ 75

 Figure: Server and Storage Virtualization

Figure: Desktop and Network Virtualization

Dr. Pradeep K V Operating Systems 10/ 75

Figure: Container Virtualization

Dr. Pradeep K V Operating Systems 11/ 75

 Operating Systems

File System

Dr. Pradeep K V
Associate Professor (Sr.)
School of Computer Science and Engineering
VIT - Chennai

Dr. Pradeep K V Operating Systems 12/ 75

Introduction to File System I

A file system is a method an operating system uses to store, organize, and

manage files and directories on a storage device. Some common types of file
systems include:
FAT (File Allocation Table): An older file system used by older versions of
Windows and other operating systems.
NTFS (New Technology File System): A modern file system used by
Windows. It supports features such as file and folder permissions,
compression, and encryption.
ext (Extended File System): A file system commonly used on Linux and
Unix-based operating systems.
HFS (Hierarchical File System): A file system used by macOS.
APFS (Apple File System): A new file system introduced by Apple for
their Macs and iOS devices.

Dr. Pradeep K V Operating Systems 13/ 75

Introduction to File System II

Advantages:
Organization: A file system allows files to be organized into directories
and subdirectories, making it easier to manage and locate files.
Data protection: File systems often include features such as file and
folder permissions, backup and restore, and error detection and correction,
to protect data from loss or corruption.
Improved performance: A well-designed file system can improve the
performance of reading and writing data by organizing it efficiently on disk.
Disadvantages:
Compatibility issues: Different file systems may not be compatible with
each other, making it difficult to transfer data between different operating
systems.
Disk space overhead: File systems may use some disk space to store
metadata and other overhead information, reducing the amount of space
available for user data.
Vulnerability: File systems can be vulnerable to data corruption, malware,
and other security threats, which can compromise the stability and security
of the system.
Dr. Pradeep K V Operating Systems 14/ 75
Introduction to File System III

File...!
It is a collection of related information that is recorded on secondary storage.
or
A File is a collection of logically related entities. From the user’s perspective, a
file is the smallest allotment of logical secondary storage.

The name of the file is divided into two parts

name
extension, separated by a period.

File Operations :
• Creating/Writing/Reading/Deleting/Repositioning/Truncating

File Attributes :
• Name/Identifier/Type/Location/Size/Protection/DateTime/UID

Dr. Pradeep K V Operating Systems 15/ 75

Introduction to File System IV

File type Usual extension Function

Read to run machine language
Executable exe, com, bin
program
Compiled, machine language
Object obj, o
not linked
Source Code C, java, pas, asm, a Source code in various languages
Commands to the command
Batch bat, sh
interpreter
Text txt, doc Textual data, documents
Word Processor wp, tex, rrf, doc Various word processor formats
Related files grouped into
Archive arc, zip, tar
one compressed file
For containing audio or
Multimedia mpeg, mov, rm
video information
It is the textual data and
Markup xml, html, tex
documents
It contains libraries of routines
Library lib, a ,so, dll
for programmers
It is a format for printing or
Print or View gif, pdf, jpg
viewing an ASCII or binary file.

Dr. Pradeep K V Operating Systems 16/ 75

Introduction to File System V

Table: File Attributes and their Operations

Attributes Types Operations

Name Doc Create
Type Exe Open
Size Jpg Read
Creation Data Xis Write
Author C Append
Last Modified Java Truncate
protection class Delete
Close

Dr. Pradeep K V Operating Systems 17/ 75

File Access Methods I

File access methods are needed to efficiently read and write data to and
from files.
Each method has its own advantages and disadvantages, and the choice of
method depends on the specific needs of the application.
Using an appropriate file access method can improve the performance and
efficiency of an application.

File Access Methods (5 Types)

Sequential access
Direct access or Relative Access
Indexed sequential access

Dr. Pradeep K V Operating Systems 18/ 75

File Access Methods II

Sequential Access Method :

It is the simplest access methods and is widely used in editors and

compilers. (Example : Audio cassettes)
The files are a collection of records. Accessing the file is equivalent to
accessing the records. In the sequential access method, each record is
accessed sequentially, one after the other.

Dr. Pradeep K V Operating Systems 19/ 75

File Access Methods III

The sequential access method has three operations:

Read next: It will read the next record in the file. The file pointer (current
pointer) will advance to the next record. It is similar to how we traverse
the nodes in a linked list.
Write next: It is used when some more information is to be included in
the file. A new node (a record) will be added at the end of the file. The
end pointer will now point to the node that has been added, marking it as
the new end of the file. It is similar to adding a new node at the end of a
linked list.
Rewind: It will bring the read & write pointers to the beginning of the file.

Analysis of Sequential Access Method :

It is very simple to implement. The work is similar to a linked list.
Since the records cannot be randomly accessed, it is not a very efficient
method.
It is a slow method.

Dr. Pradeep K V Operating Systems 20/ 75

File Access Methods IV
Merits of Sequential Access Method :
Simple and easy to implement, requiring minimal H/W & S/W support.
Low cost, as it doesn’t require complex indexing or search algorithms.
Highly efficient for dealing with large data sets, as data is stored in a linear
fashion and can be accessed in a predictable manner.
Suitable for applications that require processing of data in the order it was
written, such as backup systems or data archival.
Sequential access devices, such as magnetic tape, have a high storage
capacity and can store data for long periods of time, making them suitable
for archival storage.
Demerits of Sequential Access Method :
Inefficient for random access
Limited concurrency : Concurrent access to a sequential file can be
challenging, as only one process can access the file at a time.
Inflexible data retrieval: Since data must be retrieved in the order it was
stored, sequential access can be inflexible for applications that require
accessing data in a non-linear fashion.
Limited real-time access : is not suitable for real-time systems, as data
retrieval time can be unpredictable
Dr. Pradeep K V Operating Systems 21/ 75
File Access Methods V

Direct (Relative) Access Method :

The files are considered as a sequence of blocks or records, just like the
disk was considered to be divided into equal-sized blocks.
The benefit of this method is that we can access any block randomly. The
direct access method is known as the relative access method.
When a user wants to access a particular block, he/she provides the
relative block number, which the operating system then uses to find the
exact block address.

Dr. Pradeep K V Operating Systems 22/ 75

File Access Methods VI

Advantages of Direct Access Method

Random access to specific data within a file allows for quick and efficient
data retrieval.
High concurrency, enabling multiple processes to access the same file
simultaneously and efficiently share data. Flexible data retrieval, suitable
for accessing data in a non-sequential fashion.
Efficient data modification, as changes to specific data can be made
without rewriting the entire file.
Suitable for real-time systems that require fast and predictable data access.
Disadvantages of Direct Access Method
Inefficiency for Small Requests: It is inefficient when you need to
retrieve small pieces of data frequently. Because, It is optimized for
accessing larger chunks of data.
Space Management Challenges: Managing the available space can be
complex. It’s like arranging things in a box – if you’re not careful, things
can get disorganized and jumbled up. This can lead to wasted space and
difficulties in keeping track of where data is stored.

Dr. Pradeep K V Operating Systems 23/ 75

File Access Methods VII

Fragmentation Issues: It can happen when there are gaps between stored
data blocks. These gaps can result from adding, updating, or deleting
records. Like a jigsaw puzzle with missing pieces, fragmentation makes it
less efficient to use the available space.
Varied Record Lengths: It might not work well when dealing with records
of different lengths. Imagine trying to fit objects of different sizes into
fixed compartments – it can be challenging and lead to inefficiencies in
storage and retrieval.
Suboptimal Performance Patterns: Certain data access patterns might
not work optimally with it. It’s like taking different routes to your
destination – sometimes, the method might not be the fastest or most
efficient way to retrieve the data you need.

Analysis of Direct Access Method

Faster than the sequential access method.
Allows random access. Therefore there is no need to traverse all the
blocks.
Implementation is easy.

Dr. Pradeep K V Operating Systems 24/ 75

File Access Methods VIII

Indexed Sequenctial Access / Index Access Method

It incorporates the benefits of both sequential and direct file access.
It involves creating an index file that maps logical keys or data elements to
their corresponding physical addresses within the file. Moreover, the
system stores the index separately from the data file, enabling quick access
to locate the desired data.
In this method, there is an index that holds the pointers to various blocks
of the file. In order to access any block of the file, one has to first access
the index, and from there, we can get the pointers to various blocks.

Analysis of Index Access Method

It is a modification of the sequential access method. It allows random
access.
Apart from the file records, an extra index is required to keep track of the
blocks.
In case file size increases, the index may not be able to hold all the
pointers due to memory constraints. Hence in such a case multi-level
index may be used

Dr. Pradeep K V Operating Systems 25/ 75

File Access Methods IX

Dr. Pradeep K V Operating Systems 26/ 75

File Access Methods X

Advantages of Index Access Method

It provides fast access to all the data blocks within the file as we can
directly locate the data block easily.
It is very efficient for large files as it saves a lot of searching time.
It has better memory management as it allocation space to the index and
data blocks separately. And this will prevent memory overflow.
It will improve data integrity by maintaining a separate index for each file.

Disadvantages of Index Access Method

There can be index overhead with creating and maintaining the index. As
we have to update the index every time a record is modified or updated.
The storage requirements increase as the additional storage space to store
the index
The concurrent access is limited as multiple users cannot modify the same
index simultaneously.
The complexity will increase due to the addition of an index in the file
management system.

Dr. Pradeep K V Operating Systems 27/ 75

Directory Structure I

What is the Directory Structure?

It is a container that stores files and folders, organizing them hierarchically. It
manages entries of files, including file names, locations, protection info, and
more. This structure enables efficient file retrieval.

Dr. Pradeep K V Operating Systems 28/ 75

Directory Structure II

Directory Structure Operations

Creating: Allows to create new files and directories, providing unique
names for directories.
Searching: can search for specific files / directories within a directory.
Deleting: Unwanted files or empty directories can be deleted.
Listing: Users can retrieve a list of files in a directory.
Renaming: Files & directories can be renamed to reflect content changes.
Linking: Files can be linked to appear in multiple directories.
Unlinking: Removing links from files in multiple directories.

Types of Directory Structure

1 Single Level Directory Structure
2 Two-level Directory Structure
3 Tree-Structured Directory
4 Acyclic-Graph Directory Structure
5 General-Graph Directory Structure

Dr. Pradeep K V Operating Systems 29/ 75

Directory Structure III

Dr. Pradeep K V Operating Systems 30/ 75

Directory Structure IV

Advantages of Single-Level Directory Structure

Simple to Implement and easier as compared to other directory structures.
If the file size is smaller, then the searching of such files with the this
becomes simpler.
It allows the operations such as searching, creation, deletion and updating.

Disadvantages of Single-Level Directory Structure

As several users can log in at the same system to log their files
maintaining a unique name becomes difficult leading to a collision. This
also means that if the file with the same name is created then the old file
will get destroyed first, then the new file (having the same name ) created
will replace it.
If the size of the files is bigger then searching the files in single-level
directory structure will become time-consuming and hence difficult.
It restricts the grouping of the same type of files together.

Dr. Pradeep K V Operating Systems 31/ 75

Directory Structure V

Advantages of Two-Level Directory Structure:

This structure in OS different users have the right to have the same
directory as well as a file name as the user has its own USD which can
give a filename that can match other users but won’t cause an issue.
We can also see that searching for files become much simpler.
As we have a user-defined directory this also provides privacy related to
files stored as no user can enter the other user’s directory without
permission.
Here, we cannot group the files which are having the same name into a
single directory for a specific user.

Disadvantages of Two-Level Directory Structure

Here, a user is not allowed to share files with other users.
We also find that scalability is not present in a two-level directory structure
as two files of the same type cannot be grouped together in the same user.
Here users cannot create subdirectories only one user file directory can be
defined under one master file directory.

Dr. Pradeep K V Operating Systems 32/ 75

Directory Structure VI

Dr. Pradeep K V Operating Systems 33/ 75

Directory Structure VII

Advantages of Tree Directory Structure

In the Tree-structured directory structure searching is quite effective where
we use the current working concept that is we can access the file by using
two kinds of paths that are either absolute or relative.
Here we can group the same type of files into one directory.
In this directory structure the chances of collision of names/types etc are
less and hence we can say that the directory structure in OS is scalable.

Disadvantages of Tree Directory Structure:

In the tree-structure directory structure in OS the files cannot be shared
between users. Also, the users cannot modify/update the root directory of
other users.
This directory structure in OS as we have to go under multiple directories
to access a file we can say that it is said to be inefficient.
Here each file does not fit into the hierarchal model and so we have to
save the files into multiple directories.

Dr. Pradeep K V Operating Systems 34/ 75

Directory Structure VIII

Dr. Pradeep K V Operating Systems 35/ 75

Directory Structure IX

Advantages:
In the Acyclic Graph directory structure in OS we can share files between
users.
Here we can search the files easily as compared to the tree-structured
directory structure as here we have different-different paths to one file.

Disadvantages:
In the Acyclic Graph directory structure in OS as we can share the files via
linking, so there are chances that in the case when we want to delete a file
in a directory it may create a problem. a. Also, even if the link is a soft
link then after deleting the file we are left with a dangling/suspended
point of the link. b. But in the case of hardlink, when we delete a file we
have to vanish all the references associated with it, which can lead to
issues associated with referring back to files in case a requirement arises.

Dr. Pradeep K V Operating Systems 36/ 75

Directory Structure X

Dr. Pradeep K V Operating Systems 37/ 75

Directory Structure XI

Advantages:
The General Graph directory structure allows the cycle or creation of a
directory within a directory.
This directory structure is known to be a flexible version compared to
other directory structures.

Disadvantages:
The main issue that can overpower this structure is to calculate the total
size or space that the directories will take up.
As this directory structure allows the creation of multiple sub-directories a
lot of garbage collection can be required.
If compared to the other directory structure in OS the General Graph
directory structure is a costly structure to be chosen.

Dr. Pradeep K V Operating Systems 38/ 75

Directory Implementation

An individual subdirectory will typically contain a list of files.

The choice of a suitable algorithm for directory implementation is critical
since it has a direct impact on system performance.
Based on the data structure, we may classify the directory implementation
algorithm.

It can be implemented with the following approaches:

Linear List: It contains a list of names, each of which has a pointer to the
file’s data blocks. It requires a costly search on large directories.
Hash Table: It is a hashed linear list that decreases search time, but is
more complex to implement. We can identify the key and key points to
the relevant file that is stored in a directory using the hash function on the
respective file name.

Dr. Pradeep K V Operating Systems 39/ 75

File Allocation Methods I

The File allocation methods(5) in OS are different ways that are used for
storing the file on the hard disk, in such a manner that there is efficient
utilization of disk space and the file can be accessed faster by the OS.

File Allocation Methods :

Contiguous File allocation
Linked File Allocation
Indexed File Allocation
File Allocation Table (FAT)
Inode Table

Dr. Pradeep K V Operating Systems 40/ 75

File Allocation Methods II

Contiguous Allocation :
The block is allocated in such a manner that all the allocated blocks in the
hard disk are adjacent.
Example : Assuming a file needs ’n’ number of blocks in the disk and the
file begins with a block at position ’x’, the next blocks to be assigned to it
will be x+1, x+2, x+3,..., x+n-1 so that they are in a contiguous
manner.
Advantages
It is very easy to implement and Seek Time is Minimal.
The disk head movement is minimum, so Memory access is faster.
It supports sequential as well as direct access.
Disadvantages
At the time of creation, the file size must be initialized.
As it is pre-initialized, the size cannot increase.
Due to its constrained allocation, it is possible that the disk would
fragment internally or externally.

Dr. Pradeep K V Operating Systems 41/ 75

File Allocation Methods III

Dr. Pradeep K V Operating Systems 42/ 75

File Allocation Methods IV

Linked File Allocation :

It overcomes the drawback of contiguous file allocation.
Here, the file which we store on the hard disk is stored in a scattered
manner according to the space available on the hard disk.
In this allocation, the pointers are used to point to the next block of the
same file, therefore along with the entry of each file each block also stores
the pointer to the next block.

Figure: Linked File Allocation

Dr. Pradeep K V Operating Systems 43/ 75

File Allocation Methods V

Advantages
There is no external fragmentation.
The directory entry just needs the address of starting block.
The memory is not needed in contiguous form, it is more flexible than
contiguous file allocation.

Disadvantages
It does not support random access or direct access.
If pointers are affected so the disk blocks are also affected.
Extra space is required for pointers in the block.

Dr. Pradeep K V Operating Systems 44/ 75

File Allocation Methods VI

Indexed File Allocation :

It is somewhat similar to linked file allocation as indexed file allocation
also uses pointers but the difference is here all the pointers are put
together into one location which is called index block.
In Linked File allocation, the blocks and pointers were spread over the
memory in the Linked Allocation method, where retrieval was
accomplished by visiting each block sequentially. But here in Indexed
allocation, it becomes easier with the index block to retrieve.
Advantages
It reduces the possibilities of external fragmentation.
Rather than accessing sequentially it has direct access to the block.
Disadvantages
Here more pointer overhead is there.
If we lose the index block we cannot access the complete file.
It becomes heavy for the small files.
It is possible that a single index block cannot keep all the pointers for
some large files.

Dr. Pradeep K V Operating Systems 45/ 75

File Allocation Methods VII

Figure: Indexed File Allocation

Dr. Pradeep K V Operating Systems 46/ 75

File Allocation Methods VIII

Single index block cannot keep all the pointers for some large files.

To resolve this issue, we can use the following approaches:

Linked scheme : If the file is big then more blocks are required so one
index block is insufficient to store all the pointers, therefore to store the
pointers two or more index blocks are used where these index boxes are
connected using linked file allocation that is each index block stores the
pointer to the next index block.
Multilevel Index : Here, the multiple indexes blocks along with the levels
of these blocks. Here, the level 1 block is used for pointing to the level 2
block which points to the blocks occupied by the file. These index blocks
can be extended to three or more levels according to the size of the file.
Combined Scheme : A special block called inode (Information Node) is
used to store all the information related to the file like name, authority,
size, etc. Some space of this special block is used to store and the
remaining space is used to store the addresses of blocks that contain the
actual file.

Dr. Pradeep K V Operating Systems 47/ 75

File Allocation Methods IX

File Allocation Table (FAT) :

It overcomes the drawback of Linked File allocation.
The random(direct) access of a particular block is not possible in the
linked file allocation. i.e.,To access a particular block it is necessary to
access all its previous blocks.
Advantages
Random Access to the block is possible in FAT.
One bad/corrupted disk block cannot corrupt all the other blocks.
It uses all the disk blocks for data as in linked file allocation it needs extra
space for pointers.
Disadvantages
If entries increase so the FAT size also increases.
Each entry requires the FAT entry.
If Entries increase the FAT size increases which increases the size of a
block so there are chances of internal fragmentation.

Dr. Pradeep K V Operating Systems 48/ 75

File Allocation Methods X

Figure: File Allocation Table

Dr. Pradeep K V Operating Systems 49/ 75

File Allocation Methods XI

Inode (Information Node) :

In UNIX based OS, every file is indexed using Inode(information-node).
It is the special disk block, i.e., created with the creation of the file system.
It is used to store all the information related to the file like name,
authority, size, etc along with the pointers to the other blocks where the
file is stored.
The first few pointers in Inode point to direct blocks, i.e they contain the
addresses of the disk blocks containing the file data. A few pointers in
inode point to the indirect blocks. There are three types of indirect blocks:
single indirect, double indirect, and triple indirect.
A single indirect block contains nothing but the address of the block
containing the file data, not the file itself as shown in the figure below.
Furthermore, the double indirect block points to the pointers which again
point to the pointers which point to the data blocks. Further, it goes in a
similar way for triple indirect block.

Dr. Pradeep K V Operating Systems 50/ 75

File Allocation Methods XII

Figure: Inode

Dr. Pradeep K V Operating Systems 51/ 75

File Allocation Methods XIII

Advantages
Accessibility of file becomes easy as all the information like metadata and
block address is stored inside inode.
Read-write and creation timestamps are stored inside the inode.
Filenames do not affect inodes. In other words, a single file can be copied
and renamed without losing its address
.
Disadvantages
All new files and folders will be rejected as soon as a file system runs out
of inodes.
Upon 100% utilization of the inodes system will start to notice OS
restarting, data loss, applications crashing, and more OS-related issues.

Dr. Pradeep K V Operating Systems 52/ 75

File Allocation Methods XIV

Figure: Inode Structure - Unix

Dr. Pradeep K V Operating Systems 53/ 75
Free Space Management I

The OS works to allocate free space to the files when a file is created. It
also creates a free void space when a file is deleted from the system.
For doing all these tasks and managing spaces in our system, the
operating system works with the help of a free space management system
and allocates and de-allocates memory spaces simultaneously.
It is a system software in an OS that manipulates and keeps a track of free
spaces to allocate and de-allocate memory blocks to files.
When a file is created, the operating system searches the free space list for
the required space allocated to save a file. While deletion a file, the file
system frees the given space and adds this to the free space list.

Figure: Free Space Management Methods

Dr. Pradeep K V Operating Systems 54/ 75

Free Space Management II

Bitmap or Bit Vector :

It is a most frequently used method to implement the free space list.
It is a series or collection of bits in which each bit represents a disk block.
The values taken by the bits are either 1 or 0.
If the block bit is 1, it means the block is empty and if the block bit is 0,
it means the block is not free.
It is allocated to some files. Since all the blocks are empty initially so,
each bit in the bit vector represents 0.

Figure: Bitmap or Bit Vector

Dr. Pradeep K V Operating Systems 55/ 75

Free Space Management III

"Free block number" can be defined as that block which does not contain any
value, i.e.i.e., they are free blocks. The formula to find a free block number is :

Block number = (number of bits per words) * (number of 0-value word)

+ Offset of first 1 bit

Advantages of Bit vector method

Simple and easy to understand and Consumes less memory.
It is efficient to find free space.

Disadvantages of the Bit vector method

The OS goes through all the blocks until it finds a free block. (block
whose bit is ’0’).
It is not efficient when the disk size is large.

Dr. Pradeep K V Operating Systems 56/ 75

Free Space Management IV
Linked List :
It is another approach for free space management in an OS. Where, all the
free blocks inside a disk are linked together in a linked list together by a
pointer.
These pointers of the free block contain the address of the next free block
and the last pointer of the list points to null which indicates the end of the
linked list. T
This technique is not enough to traverse the list because we have to read
each disk block one by one which requires I/O time.

Figure: Linked List Free Space Management Method

Dr. Pradeep K V Operating Systems 57/ 75

Free Space Management V

Advantage of the Linked list

In this method, available space is used efficiently.
As there is no size limit on a linked list, a new free space can be added
easily.
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
In this method, the overhead of maintaining the pointer appears.
The Linked list is not efficient when we need to reach every block of
memory.
There is no provision for random or direct memory access in linked list
allocation

Dr. Pradeep K V Operating Systems 58/ 75

Free Space Management VI
Grouping :
It is also called the "modification of a linked list technique".
In this method, first, the free block of memory contains the addresses of
the n-free blocks. And the last free block of these ’n’ free blocks contains
the addresses of the next ’n’ free block of memory and this keeps going on.
This technique separates the empty and occupied blocks of space of
memory.

Figure: Grouping Free Space Management Method

Dr. Pradeep K V Operating Systems 59/ 75

Free Space Management VII
Suppose we have a disk with some free blocks and some occupied blocks. The
free block numbers are 3,4,5,6,9,10,11,12,13 and 14. And occupied block
numbers are 1,2,7,8,15 and 16 i.e. they are allocated to some files.

Figure: Grouping Free Space Management Method

Advantages :
The addresses of a large number of free blocks can be found quickly. And
is simple to locate the addresses of a collection of free blocks.
No need to traverse the whole list.
Disadvantages
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 need to change the entire list if one block gets occupied.
There is an overhead in maintaining the index of blocks.
Dr. Pradeep K V Operating Systems 60/ 75
Free Space Management VIII

Counting :
It takes advantage of the fact that several contiguous blocks may be
allocated or freed simultaneously.
Here, 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-
A pointer to the next free block.
The number of free contiguous blocks following it.
Advantages of counting
Fast allocation of higher number of consecutive free blocks.
Random access to the free block can be performed.
Entire list is generally smaller in size.
Disadvantages of counting
Every free block requires huge space to keep the count in the disk.
To perform traversal operations, we have to store the entries in B-tree.
Whole area got reduced in counting.

Dr. Pradeep K V Operating Systems 61/ 75

Free Space Management IX

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

Figure: Counting Free Space Management Method

Dr. Pradeep K V Operating Systems 62/ 75

File System Implementation I

It refers to how the file system manages the storage and retrieval of data on a
physical storage device such as a hard drive, solid-state drive, or flash drive.

It includes several components

File System Structure: It refers to how the files and directories are
organized and stored on the physical storage device. Includes the layout of
file systems data structures such as the directory structure, file allocation
table, and inodes.
File Allocation: It determines how files are allocated on the storage
device. This can include allocation techniques such as contiguous
allocation, linked allocation, indexed allocation, or a combination of these
techniques.
Data Retrieval: It determines how the data is read from and written to
the physical storage device. This includes strategies such as buffering and
caching to optimize file I/O performance.
Security and Permissions: The file system implementation includes
features for managing file security and permissions. This includes access
control lists (ACLs), file permissions, and ownership management.

Dr. Pradeep K V Operating Systems 63/ 75

File System Implementation II

Recovery and Fault Tolerance: It includes features for recovering from

system failures and maintaining data integrity. This includes techniques
such as journaling and file system snapshots.

Figure: File System Layers

Dr. Pradeep K V Operating Systems 64/ 75

File System Implementation III

Advantages
Duplication of code is minimized and each file system can have its own
logical file system.
File system implementation provides several advantages, including:
Efficient Data Storage
Data Security
Data Recovery
Improved Performance
Scalability
Flexibility
Cross-Platform Compatibility

Disadvantages
Boot Control Block : It is usually the first block of volume and it
contains information needed to boot an operating system. In UNIX it is
called the boot block and in NTFS it is called the partition boot sector.
Volume Control Block : It has information about a particular partition
ex:- free block count, block size and block pointers, etc. In UNIX it is
called superblock and in NTFS it is stored in the master file table.

Dr. Pradeep K V Operating Systems 65/ 75

File System Implementation IV

Directory Structure : They store file names and associated inode

numbers. In UNIX, includes file names and associated file names and in
NTFS, it is stored in the master file table.
Per-File FCB : It contains details about files and it has a unique identifier
number to allow association with the directory entry. In NTFS it is stored
in the master file table.
Mount Table : It contains information about each mounted volume.
Directory-Structure cache : This cache holds the directory information of
recently accessed directories.
System-wide open-file table : It contains the copy of the FCB of each
open file.
Linear List It maintains a linear list of filenames with pointers to the data
blocks. It is time-consuming also. To create a new file, we must first
search the directory to be sure that no existing file has the same name
then we add a file at the end of the directory. To delete a file, we search
the directory for the named file and release the space. To reuse the
directory entry either we can mark the entry as unused or we can attach it
to a list of free directories.

Dr. Pradeep K V Operating Systems 66/ 75

File System Implementation V

Per-process open-file table : It contains information opened by that

particular process and it maps with the appropriate system-wide open-file.
Hash Table : The hash table takes a value computed from the file name
and returns a pointer to the file. It decreases the directory search time.
The insertion and deletion process of files is easy. The major difficulty is
hash tables are its generally fixed size and hash tables are dependent on
the hash function of that size.

Implementation Issues :
Management of disc space: To prevent space wastage and to guarantee
that files can always be stored in contiguous blocks, file systems must
manage disc space effectively. Free space management, fragmentation
prevention, and garbage collection are methods for managing disc space.
Checking for consistency and repairing errors: The consistency and
error-free operation of files and directories must be guaranteed by file
systems. Journaling, checksumming, and redundancy are methods for
consistency checking and error recovery. File systems may need to perform
recovery operations if errors happen in order to restore lost or damaged
data.

Dr. Pradeep K V Operating Systems 67/ 75

File System Implementation VI

Locking files and managing concurrency: To prevent conflicts and

guarantee data integrity, file systems must control how many processes or
users can access a file at once. File locking, semaphore, and other
concurrency-controlling methods are available.
Performance optimization: File systems need to optimize performance by
reducing file access times, increasing throughput, and minimizing system
overhead. Caching, buffering, prefetching, and parallel processing are
methods for improving performance.

Key Steps involved in File System Implementation : It is a crucial

component of an OS, as it provides an interface b/w the user and the physical
storage device.

Here are the key steps involved in file system implementation:

Partitioning the storage device: It is to partition the physical storage
device into one or more logical partitions. Each partition is formatted with
a specific file system that defines the way files and directories are
organized and stored.

Dr. Pradeep K V Operating Systems 68/ 75

File System Implementation VII

File system structures: They are the data structures used by the OS to
manage files and directories. It includes the superblock, inode table,
directory structure, and file allocation table.
Allocation of storage space: It must allocate storage space for each file
and directory on the storage device. There are several methods such as
contiguous, linked, and indexed allocation.
File operations: provides a set of operations that can be performed on
files and directories, including create, delete, read, write, open, close, and
seek. These operations are implemented using the file system structures
and the storage allocation methods.
File system security: must provide security mechanisms to protect files
and directories from unauthorized access or modification. This can be
done by setting file permissions, access control lists, or encryption.
File system maintenance: must be maintained to ensure efficient and
reliable operation. This includes tasks such as disk defragmentation, disk
checking, and backup and recovery.

Dr. Pradeep K V Operating Systems 69/ 75

File System Recovery

Files and directories are kept both in main memory and on disk, and care must
taken to ensure that system failure does not result in loss of data or in data
inconsistency.
Consistency checking – compares data in directory structure with data
blocks on disk, and tries to fix inconsistencies.
• Can be slow and sometimes fails
Use system programs to back up data from disk to another storage device
(magnetic tape, other magnetic disk, optical)Recover lost file or disk by
restoring data from backup

Dr. Pradeep K V Operating Systems 70/ 75

Log Structured File Systems

Log structured (or journaling) file systems record each metadata update to
the file system as a transaction.
All transactions are written to a log
A transaction is considered committed once it is written to the log
(sequentially)
Sometimes to a separate device or section of disk
However, the file system may not yet be updated
The transactions in the log are asynchronously written to the file system
structures
When the file system structures are modified, the transaction is removed
from the log
If the file system crashes, all remaining transactions in the log must still be
performed
Faster recovery from crash, removes chance of inconsistency of metadata

Click here, to know more

Dr. Pradeep K V Operating Systems 71/ 75

Distributed File System I

DFS (distributed file system), as the name suggests, is a file system that is
distributed across multiple file servers or multiple locations. Its primary
purpose is to reliably store data or, more specifically, files.
It is composed of several servers connected via a computer network – like
ethernet or the internet:

Dr. Pradeep K V Operating Systems 72/ 75

Distributed File System II

DFS has two critical components:

Location transparency : this means users will see a single namespace for
all the data files, regardless of which computer they’re using to access or
store the files. Users won’t be able to tell where the file was initially stored
and can move files around within the folders as needed without having to
change the path name.
Redundancy – through a file replication feature, DFS spreads copies of a
file across the nodes of the cluster, which means data stays highly
available, even in the event of a server failure.

Features of Distributed File Systems

Access transparency – users access files as if they are stored locally on
their own workstations
Location transparency – host machines don’t need to know where the file
data actually is because the DFS manages that
File locking – the system locks down files in use across locations to
prevent two users from different locations making changes to the same file
at the same time

Dr. Pradeep K V Operating Systems 73/ 75

Distributed File System III

Encryption for data in transit – DFS protects data by encrypting it as it

moves through the system
Support for multiple protocols – hosts can access files using a range of
protocols, such as Server Message Block (SMB), Network File System
(NFS), and Portable Operating System Interface (POSIX).

Benefits of DFS
Data resiliency – because files reside in more than one location, a server
failure won’t signal disaster
Network efficiency – heavy workloads won’t slow down the system
because DFS can grab data from the next available node
Access to latest information – changes made to shared folders or files are
visible and available instantly to everyone who uses the DFS
Simple scalability – growing the system simply means adding more nodes
High reliability – data loss becomes much less of a concern with files
replicated across hosts

Dr. Pradeep K V Operating Systems 74/ 75

Dr. Pradeep K V Operating Systems 75/ 75