UNIT - 5

File System

File Systems:
File systems are a crucial part of any operating system, providing a structured way to store, organize and
manage data on storage devices such as hard drives, SSDs and USB drives.

 User Application: The programs or software that request file operations like read, write, or
delete.
 Logical File System: Manages metadata, file names, directories, and access permissions.
 Virtual File System (VFS): Acts as a bridge, allowing different file systems to work under a
single interface.
 Physical File System: Handles the actual storage of data blocks on the disk.
 Partition 1, Partition 2, Partition 3: Divisions of the storage device where files are stored
physically.

Popular File Systems

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.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
1 of 38
  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.

Access methods:
File access methods are techniques used by an OS to read and write data in files. They define
how information is organized, retrieved, and modified. Choosing the right method is important for
performance and data management.

There are three ways to access a file in a computer system:

 Sequential-Access
 Direct Access
 Index sequential Method

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
2 of 38
 Key Points related to Sequential Access
 Data is accessed from one record right after another record in an order.
 When we use the read command, it moves ahead pointer by one.
 When we use the 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.
 It is less prone to data corruption as the data is written sequentially and not randomly.
Disadvantages of Sequential Access Method
 Slow for searching specific records.
 Inserting/updating in the middle is difficult.
 Can waste storage if records have varying lengths.
Direct Access Method
A file access method that allows data to be read or written directly at any block or record, using
its address (block number). It supports random access without scanning previous records.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
3 of 38
 Advantages of Direct Access Method
 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.
Disadvantages of Direct Access Method
 Complex Implementation : Implementing direct access can be complex, requiring sophisticated
algorithms and data structures to manage and locate records efficiently.
 Higher Storage Overhead : Direct access methods often require additional storage for
maintaining data location information (such as pointers or address tables), which can increase the
overall storage requirements.

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.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
4 of 38
 Key Points Related to Index Sequential Method
 It is built on top of Sequential access.
 It control the pointer by using index.
Advantages of Index Sequential Method
 Fast Searching: Index enables quick lookups.
 Flexible: Supports both sequential and random access.
 Reduced Access Time: Quickly locates data in large files.
Disadvantages of Index Sequential Method
 Complexity: Harder to implement and maintain than sequential access.
 Extra Storage: Requires additional space for indexes.
 Slower Updates: Both data and index must be updated during insertions, deletions, or
modifications.
 Maintenance Overhead: Indexes need frequent updates in dynamic environments.

Directory Structure:
The operating system uses directories to track where files are stored, just like using folders to
organise papers.
 Different directory structures can be used to suit various organisational needs.
 Understanding directory structures helps in organising and accessing files more easily.
By using these structures, it becomes simpler to manage and navigate files on your computer.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
5 of 38
 Different Types of Directories in OS
In an operating system, there are different types of directory structures that help organise and
manage files efficiently. Each type of directory has its own way of arranging files and directories,
offering unique benefits and features. These are
 Single-Level Directory
 Two-Level Directory
 Tree Structure/ Hierarchical Structure
 Acyclic Graph Structure
 General-Graph Directory Structure
1) Single-Level Directory
The single-level directory is the simplest directory structure. In it, all files are contained in the
same directory which makes it easy to support and understand.
A single level directory has a significant limitation, however, when the number of files increases or
when the system has more than one user. Since all the files are in the same directory, they must have
a unique name. If two users call their dataset test, then the unique name rule violated.

 Since it is a single directory, so its implementation is very easy.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
6 of 38
  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.
Advantages
 Logical Organization: Arrange files hierarchically for easy navigation.
 Efficiency: Faster file searching and access.
 Security: Restrict access at directory level to protect data.
 Backup & Recovery: Simplifies locating and restoring files.
 Scalability: Easily supports growth with new files and directories
Disadvantages
 There may chance of name collision because two files can have the same name.
 Searching will become time taking if the directory is large.
 This can not group the same type of files together.
2) Two-Level Directory
In a two-level directory structure, each user has a separate User File Directory (UFD) containing
only their files. A Master File Directory (MFD) stores entries for all users and points to their
respective UFDs, preventing filename conflicts between users.

Advantages
 The main advantage is there can be more than two files with same name, and would be very
helpful if there are multiple users.
 A security would be there which would prevent user to access other user's files.
 Searching of the files becomes very easy in this directory structure.
Disadvantages
 As there is advantage of security, there is also disadvantage that the user cannot share the file
with the other users.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
7 of 38
  Unlike the advantage users can create their own files, users don't have the ability to create
subdirectories.
 Scalability is not possible because one user can't group the same types of files together.
3) Tree Structure/ Hierarchical Structure
The tree directory structure is the most common in personal computers. It resembles an upside-down
tree, with the root directory at the top containing all user directories. Each user can create files and
subdirectories within their own directory but cannot access or modify the root or other users’
directories.

Advantages
 This directory structure allows subdirectories inside a directory.
 The searching is easier.
 File sorting of important and unimportant becomes easier.
 This directory is more scalable than the other two directory structures explained.
Disadvantages
 As the user isn't allowed to access other user's directory, this prevents the file sharing among
users.
 As the user has the capability to make subdirectories, if the number of subdirectories increase the
searching may become complicated.
 Users cannot modify the root directory data.
 If files do not fit in one, they might have to be fit into other directories.

4) Acyclic Graph Structure

In the earlier directory structures, a file could only be accessed from the directory it was stored in.
The acyclic graph directory structure solves this by allowing a file or subdirectory to be shared

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
8 of 38
 across multiple directories using links. Changes made by one user are visible to all users sharing that
file.
In the below figure, this explanation can be nicely observed, where a file is shared between multiple
users. If any user makes a change, it would be reflected to both the users.

Advantages
 Sharing of files and directories is allowed between multiple users.
 Searching becomes too easy.
 Flexibility is increased as file sharing and editing access is there for multiple users.
Disadvantages
 Because of the complex structure it has, it is difficult to implement this directory structure.
 The user must be very cautious to edit or even deletion of file as the file is accessed by multiple
users.
 If we need to delete the file, then we need to delete all the references of the file inorder to delete
it permanently.
5) General-Graph Directory Structure
Unlike the acyclic-graph directory, which avoids loops, the general-graph directory can have cycles,
meaning a directory can contain paths that loop back to the starting point. This can make navigating
and managing files more complex.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
9 of 38
 In the above image, you can see that a cycle is formed in the User 2 directory. While this structure
offers more flexibility, it is also more complicated to implement.
Advantages of General-Graph Directory
 More flexible than other directory structures.
 Allows cycles, meaning directories can loop back to each other.
Disadvantages of General-Graph Directory
 More expensive to implement compared to other solutions.
 Requires garbage collection to manage and clean up unused files and directories.

File System Implementation

A file is a collection of related information. The file system resides on secondary storage and
provides efficient and convenient access to the disk by allowing data to be stored, located, and
retrieved. File system implementation in an operating system 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.

Components of File System Implementation

The file system implementation includes several components, including:

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
10 of 38
  File System Structure: The file system structure refers to how the files and directories are organized and
stored on the physical storage device. This includes the layout of file systems data structures such as the
directory structure, file allocation table, and inodes.
 File Allocation: The file allocation mechanism 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: The file system implementation 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.
 Recovery and Fault Tolerance: The file system implementation includes features for recovering from
system failures and maintaining data integrity. This includes techniques such as journaling and file system
snapshots.
Different Types of File Systems
There are several types of file systems, each designed for specific purposes and compatible with
different operating systems. Some common file system types include:
 FAT32 (File Allocation Table 32): Commonly used in older versions of Windows and
compatible with various operating systems.
 NTFS (New Technology File System): Used in modern Windows operating systems, offering
improved performance, reliability, and security features.
 ext4 (Fourth Extended File System): Used in Linux distributions, providing features such as
journaling, large file support, and extended file attributes.
 HFS+ (Hierarchical File System Plus): Used in macOS systems prior to macOS High Sierra,
offering support for journaling and case-insensitive file names.
 APFS (Apple File System): Introduced in macOS High Sierra and the default file system for
macOS and iOS devices, featuring enhanced performance, security, and snapshot capabilities.
 ZFS (Zettabyte File System): A high-performance file system known for its advanced features,
including data integrity, volume management, and efficient snapshots.
Implementation Issues
 Management of Disc pace: 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.
 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.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
11 of 38
 File-System Structure File System
A file system in an operating system is organized into multiple layers, each responsible for different
aspects of file management and storage. Here are the key layers in a typical file system:

 Application Programs: This is the topmost layer where users interact with files through
applications. It provides the user interface for file operations like creating, deleting, reading,
writing, and modifying files. Examples include text editors, file browsers, and command-line
interfaces.
 Logical File system - It manages metadata information about a file i.e includes all details about a
file except the actual contents of the file. It also maintains via file control blocks. File control
block (FCB) has information about a file - owner, size, permissions, and location of file contents.
 File Organization Module - It has information about files, the location of files and their logical
and physical blocks. Physical blocks do not match with logical numbers of logical blocks
numbered from 0 to N. It also has a free space that tracks unallocated blocks.
 Basic File system - It Issues general commands to the device driver to read and write physical
blocks on disk. It manages the memory buffers and caches. A block in the buffer can hold the
contents of the disk block and the cache stores frequently used file system metadata.
 I/O Control level - Device drivers act as an interface between devices and OS, they help to
transfer data between disk and main memory. It takes block number as input and as output, it
gives low-level hardware-specific instruction.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
12 of 38
  Devices Layer: The bottommost layer, consisting of the actual hardware devices. It performs the
actual reading and writing of data to the physical storage medium. This includes hard
drives, SSDs, optical disks, and other storage devices.

File-system Operations:
File operations within an operating system (OS) encompass a set of essential tasks and actions
directed at files and directories residing within a computer's file system. These operations are
fundamental for the effective management and manipulation of data stored on various storage
devices.

File Creation and Manipulation

File Creation and Manipulation encompasses essential operations within an operating system that
involve creating, modifying, and organizing files and directories. These actions are vital for
managing data efficiently and are integral to the functioning of computer systems.

File Operation Description System Calls / APIs

 open() (Linux-like
Creating Files Create a new file for data storage. systems)
 CreateFile() (Windows)

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
13 of 38
 File Operation Description System Calls / APIs

 mkdir() (Linux systems)

Create a new directory for
Creating Directories  CreateDirectory()
organizing files.
(Windows)

Open a file that you already have  open() (Linux systems)

Opening Files
open to read or write from.  CreateFile() (Windows)

 read() (Linux systems)

Reading Files Retrieve data from an open file.
 ReadFile() (Windows)

 write() (Linux systems)

Writing Files Store data in an open file.
 WriteFile() (Windows)

 rename() (Linux
Renaming Files and If you want to rename a file or
systems)
Directories directory,.
 MoveFile() (Windows)

 unlink() (Linux
systems)
 remove() (Linux
Deleting Files and
Remove files or directories. systems)
Directories
 DeleteFile() (Windows)
 RemoveDirectory()
(Windows)

File Organization and Search

File organization and search are key OS operations for arranging files systematically and swiftly
locating specific data, optimizing file management and user efficiency.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
14 of 38
 File Operation Description System Calls / APIs

Create duplicates of files in another  cp (Linux systems)

Copying Files
location.  CopyFile() (Windows)

Relocate files from one location to  mv (Linux systems)

Moving Files
another.  MoveFile() (Windows)

 find (Linux systems)

Searching for Locate files based on specific
 FindFirstFile() and FindNextFile()
Files criteria.
(Windows)

File Security and Metadata

File Security and Metadata are vital components of file management, encompassing access control
and crucial file information preservation within an operating system. They are essential for data
security and efficient organization.

File Operation Description System Calls / APIs

File Control access rights to files and  chmod (Linux systems)

Permissions directories.  SetFileSecurity (Windows)

Assign specific users or groups as file  chown (Linux systems)

File Ownership
owners.  SetFileSecurity (Windows)

 stat (Linux systems)

File Metadata Retrieve and manipulate file information.  GetFileAttributesEx
(Windows)

File Compression and Encryption

File Compression and Encryption are essential for optimizing storage and enhancing data security.
Compression reduces file sizes, while encryption safeguards data privacy by making it unreadable
without the correct decryption key.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
15 of 38
 File
Operation Description System Calls / APIs

File Reduce file sizes to save storage  gzip, zip, tar (Linux systems),
Compression space.  Compress-Archive (Windows)

 openssl, gpg (Linux systems)

File Protect data by converting it into
Encryption
 Windows provides encryption libraries
an unreadable format.
and APIs for encryption operations.

Directory implementation:
Directory implementation in the operating system can be done using Singly Linked List and Hash
table. The efficiency, reliability, and performance of a file system are greatly affected by the
selection of directory-allocation and directory-management algorithms. here are numerous ways in
which the directories can be implemented.

The below are two ways of implementing the directory in the operating system :
 Directory Implementation using Singly Linked List
 Directory Implementation using Hash Table

Steps to Implement the Directory Using Singly Linked List

The steps are given below for the implementation of the directory:

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
16 of 38
  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.

Advantages
 Simple Implementation: Easy to implement with low memory overhead.
 Dynamic Structure: Grows or shrinks as needed without fixed size constraints.
 Efficient for Small Directories: Works well when the number of files is small and manageable.
 Low Complexity: No need for collision handling or resizing, making it simpler.

Disadvantages
 Lookup Time : File lookup requires a linear search, which can be time-consuming.
 Impact of Frequent Access : Directory information is accessed frequently, leading to slow access times
with larger directories.
 Solution: Caching : Operating systems maintain a cache of recently accessed entries to enable quicker
access without full traversal.
Directory Implementation using Hash Table
An alternative data structure that can be used for directory implementation is a hash table. It
overcomes the major drawbacks of directory implementation using a linked list. 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.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
17 of 38
 Steps to Implement the Directory Using Hash Table
The following steps are taken for the implementation of the directory using the hash table :
 Combine a hash table with a linked list to implement the directory structure.
 Generate a key-value pair for each file using a hash function on the file name.
 Insert the file into the linked list and store the key-pointer pair in the hash table.
 To search, compute the key using the file name and look it up in the hash table.
 Fetch the file directly using the pointer from the hash table, avoiding full list traversal.
 This hybrid method significantly reduces search time and improves efficiency.

Advantages
 Fast File Lookup: Provides average O(1) time complexity for quick search and retrieval.
 Efficient for Large Directories: Handles large directories with many files without significant
performance loss.
 Scalable: Easily accommodates an increasing number of files without degrading access speed.
 Reduced Search Time: Eliminates the need for full traversal, making directory operations faster.

Disadvantage
 Fixed Size: Limited scalability due to a fixed size, affecting performance as data grows.
 Size Dependent Performance: Performance degrades as the table becomes full (high load
factor).
 Collision Handling Complexity: Collisions add complexity and can slow down performance.
 Performance Trade off: Despite drawbacks, hash tables are faster than linked lists for lookups .
Comparison of Singly Linked List and a Hash Table Directory
Implementation

Feature Singly Linked List Hash Table

Slow to find something, you

Fast , you can quickly find things because of
need to check each item one
how it's organized (O(1) on average).
Search Efficiency by one O(n).

Fast and easy , you can add

Also fast O(1) , usually takes constant time,
items at the beginning or end
but can be slower if collisions happen.
Insertion easily O(1).

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
18 of 38
 Feature Singly Linked List Hash Table

Higher , uses more memory because it stores

Low , it only stores the data
both data and additional space for handling
and pointers.
Memory Usage collisions or empty slots.

Not great for large data , as

Good for large data , even as the data grows,
the list gets bigger, searching
it remains fast at finding things.
Scalability takes longer.

Implementation Simple , easy to build and More complex , you need to manage how
Complexity use. data is hashed and handle collisions.

Not needed , each element Needed , when two elements hash to the
Collision Handling has its own place. same spot, you need a way to handle it.

Easy to expand , just keep Not as flexible , resizing and rehashing can
Adaptability adding elements. be costly if the table gets too full.

Small lists with not too many Large lists or databases where speed is
Best Use Case elements. important.

Small systems with limited

Large databases, file systems, or
memory (like embedded
applications needing fast lookups.
Example Use devices).

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
19 of 38
 Allocation method
OR

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. This means that given the
starting block address and the length of the file (in terms of blocks required), we can determine the
blocks occupied by the file. The directory entry for a file with contiguous allocation contains:
 Address of starting block
 Length of the allocated portion.
 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.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
20 of 38
 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)(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 Allocation
In this scheme, each file is a linked list of disk blocks which need not be contiguous. Here,
 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.
 Example: 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.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
21 of 38
 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. 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.
 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. Here,
 Each file has its own index block.
 The ith entry in the index block contains the disk address of the i th file block.
 The directory entry contains the address of the index block as shown in the image.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
22 of 38
 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.
However, in linked allocation we lose the space of only 1 pointer per block.

Free space management:

Free space management involves managing the available storage space on the hard disk or other
secondary storage devices. To reuse the space released from deleting the files, a free space list is

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
23 of 38
 maintained. The free space list can be implemented mainly as:

 Bitmap or Bit vector

 Linked List
 Boundary Tags
 Free List

Bitmap or Bit vector:

In this approach, 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 free and 1 indicates an allocated block.
 The given instance of disk blocks on the disk in Figure 1 can be represented by a bitmap of 16
bits as: 1111000111111001.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
24 of 38
 Bitmap or Bit vector
Advantages:
 Simple to understand.
 Finding the first free block is efficient. It requires scanning the words (a group of 8 bits) in a
bitmap for a non-zero word. (A 0-valued word has all bits 0). The first free block is then found
by scanning for the first 1 bit in the non-zero word.

Disadvantages:
 For finding a free block, Operating System needs to iterate all the blocks which is time
consuming.
 The efficiency of this method reduces as the disk size increases.

Linked List
In this approach, Free blocks are linked together in a list. Each free block stores the address of the
next free block. The list is maintained dynamically as blocks are allocated and freed.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
25 of 38
 Linked List
Advantages:
 The total available space is used efficiently using this method.
 Dynamic allocation in Linked List is easy, thus can add the space as per the requirement
dynamically.
Disadvantages:
 When the size of Linked List increases, the headache of miniating pointers is also increases.
 This method is not efficient during iteration of each block of memory.
 I/O IS required for free space list traversal.
Boundary Tags
In this approach, Each block contains a boundary tag indicating its size and whether it is free or
occupied. Adjacent free blocks are merged during deallocation to reduce fragmentation.

Advantages:
 Useful in memory management systems.
 Simplifies coalescing of adjacent free blocks.
Disadvantages:
 Slight overhead in storing tag information.
 More complex than bitmap or linked list.
Free List
In this approach, The free blocks are maintained in a list (array or linked list). Each entry in the free
list points directly to a free block on disk.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
26 of 38
 Advantages:
 Fast allocation as free blocks are known upfront.
 Easy to traverse and maintain .
Disadvantages:
 Extra memory needed to store the list.
 May suffer from fragmentation over time.

File-System Internals: File-System Mounting:

File-System Mounting:
Mounting is a process in which the operating system adds the directories and files from a storage
device to the user’s computer file system. The file system is attached to an empty directory, by
adding so the system user can access the data that is available inside the storage device through the
system file manager. Storage systems can be internal hard disks, external hard disks, USB flash
drivers, SSD cards, memory cards, network-attached storage devices, CDs and DVDs, remote file
systems, or anything else.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
27 of 38
 Terminologies used in File System Mounting
 File System: It is the method used by the operating system to manage data storage in a storage device. So,
a user can access and organize the directories and files in an efficient manner.
 Device name: It is a name/identifier given to a storage partition. In windows, for example, “D:” in
windows.
 Mount point: It is an empty directory in which we are adding the file system during the process of
mounting.

Mounting Indifferent Operating Systems

1. Linux-Unix based OS
We want to mount /dev/sdb1 to an existing directory /mnt.

sudo mount /dev/sdb1 /mnt/mydisk

After mounting, we have to unmount after use

sudo umount /mnt/mydisk

before and after mounting

2. Windows OS
In windows mounting is very easy for a user. When we connect the external storage devices,
windows automatically detect the file system and mount it to the drive letter. Drive letter may
be D: or E:.
Steps:
 Connect an external storage device to your PC.
 Windows detects the file system on the drive (e.g., FAT32 or NTFS) and assigns it a drive letter,
such as "E:".

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
28 of 38
  You can access the derive by going through, THIS PC --> FILE EXPLORER -->"E:" drive
 Access the data.

3. Mac OS
In Mac OS when we connect an external storage it will automatically mount, and it will be
accessible via Finder. As an advanced mounting method user can also use the command diskutil in
Terminal.
Method 1:
Steps:
 Connect an external storage device to your MAC.
 MS OS detects the file system and automatically mount it.
 You can access the drive by opening Finder, and it will appear in the sidebar.

Method 2(Using diskutil):

To mount a drive with a known identifier: disk2s1

diskutil mount /dev/disk2s1

To unmount:
diskutil unmount /dev/disk2s1
Partitions and Mounting:
A partition is a logical subdivision of a physical hard disk drive that enables the operating system to
manage data efficiently. When a disk is partitioned, it is divided into one or more independent
sections, each functioning as if it were a separate physical disk. Every partition can have its own file
system, which allows users to install multiple operating systems or store different types of data
separately. Partitioning is one of the most important processes in storage management because it helps
in organizing data, improving performance, and ensuring data safety.

Purpose and Importance of Partitioning

Partitioning serves several key purposes:

1. Efficient Data Management: It helps in organizing data by separating system files,

application files, and user data into different partitions.
2. Multiple Operating Systems: It allows the installation of multiple operating systems on the
same disk, where each OS can occupy a separate partition.
3. Improved Performance: Smaller partitions reduce file system overhead and improve access
times.
4. Data Security: In case of a system crash or corruption in one partition, other partitions remain
unaffected.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
29 of 38
 5. Backup and Recovery: It simplifies backup and recovery processes since data can be stored in
a dedicated partition.

Types of Partitions

There are three major types of partitions:

1. Primary Partition:
A primary partition is a basic type of partition that can directly host an operating system. A
disk can have up to four primary partitions, and one of them can be marked as active, meaning
the computer can boot from it. The active partition contains the boot loader and system startup
files.
2. Extended Partition:
Since only four primary partitions are allowed, an extended partition is created to overcome
this limitation. An extended partition does not directly store data but serves as a container for
multiple logical partitions.
3. Logical Partition:
Logical partitions are subdivisions created within the extended partition. They are used to store
user data, applications, or backups. Logical partitions cannot be used for booting an operating
system directly, but they are useful for data storage and management.

For example, in a typical system:

 The C: drive (Primary partition) contains the operating system.

 The D: and E: drives (Logical partitions) may contain user data or backup files.

File System and Partition Relationship

Each partition is formatted with a specific file system, such as NTFS (Windows), ext4 (Linux), or FAT32
(used in portable drives). The file system determines how files are stored, named, and accessed within that
partition. The operating system interacts with the disk through these file systems, and each partition maintains
its own directory structure.

Mounting in Operating Systems

Mounting is the process of making a partition or storage device accessible to the operating system and its users.
When a device or partition is mounted, it becomes part of the file system hierarchy, allowing users and
programs to read from or write to it. In simple terms, mounting “attaches” a partition to a specific directory
known as a mount point.

The mount point acts as an entry in the directory structure where the contents of the partition become
visible. Once a partition is mounted, all files and folders within it can be accessed through that mount
point.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
30 of 38
 Mounting in Different Operating Systems

1. In Windows:
o Windows automatically mounts partitions as drive letters (e.g., C:, D:, E:).
o Each drive letter represents a separate partition or storage device.
o The C: drive usually contains the operating system, while other drives hold data or
applications.
2. In Linux/Unix:
o Linux uses a single root directory (/) and mounts all partitions under it.
o Common mount points include /home, /mnt, /media, and /boot.
o Mounting is done manually using the mount command.
Example:

mount /dev/sda1 /mnt/data

Difference Between Partitioning and Mounting (Short Ans):

Aspect Partitioning Mounting

Dividing a physical disk into logical Making a partition accessible to the
Definition
sections OS
Purpose Organize and manage data storage Access data through the file system

When Done Before formatting or installation During system boot or when needed

Example Assigning drive letters

Creating C:, D:, and E: drives
(Windows) automatically
Example (Linux) /dev/sda1, /dev/sda2 Mounting to /, /home, /mnt

File sharing. Protection :

File sharing protection in an operating system (OS) is achieved through built-in mechanisms like user permissions
and access control lists (ACLs), encryption, and features like Windows File Protection.

Goals of protection:

In computer systems, alot of user’s information is stored, the objective of the operating system is to
keep safe the data of the user from the improper access to the system. Protection can be provided in
number of ways. For a single laptop system, we might provide protection by locking the computer in
a desk drawer or file cabinet. For multi-user systems, different mechanisms are used for the
protection.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
31 of 38
 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. Several different types of operations can be controlled:
 Read - Reading from a file.
 Write - Writing or rewriting the file.
 Execute - Loading the file and after loading the execution process starts.
 Append - Writing the new information to the already existing file, editing must be end at the end
of the existing file.
 Delete - Deleting the file which is of no use and using its space for the another data.
 List - List the name and attributes of the file.
Operations like renaming, editing the existing file, copying; these can also be controlled. There are
many protection mechanism. each of them mechanism have different advantages and disadvantages
and must be appropriate for the intended application.
Access Control :

There are different methods used by different users to access any file. The general way of protection
is to associate identity-dependent access with all the files and directories an list called access-control
list (ACL) which specify the names of the users and the types of access associate with each of the
user. The main problem with the access list is their length. If we want to allow everyone to read a
file, we must list all the users with the read access. This technique has two undesirable
consequences:
Constructing such a list may be tedious and unrewarding task, especially if we do not know in
advance the list of the users in the system.
Previously, the entry of the any directory is of the fixed size but now it changes to the variable size
which results in the complicates space management. 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.

The most common recent approach is to combine access-control lists with the normal general owner,
group, and universe access control scheme. For example: Solaris uses the three categories of access
by default but allows access-control lists to be added to specific files and directories when more
fine-grained access control is desired.
Other Protection Approaches:

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
32 of 38
 The access to any system is also controlled by the password. If the use of password is random and it
is changed often, this may be result in limit the effective access to a file.

The use of passwords has a few disadvantages:

 The number of passwords are very large so it is difficult to remember the large passwords.
 If one password is used for all the files, then once it is discovered, all files are accessible;
protection is on all-or-none basis

Principles of protection:

Protection in an operating system refers to a mechanism that controls the access of programs,
processes, or users to system resources. It ensures that each process in the system uses resources only
in a legitimate manner as defined by the system’s policies.

Objectives of Protection

1. Prevent Unauthorized Access – Restrict access to files, devices, or memory to only

authorized users or processes.
2. Ensure Data Integrity – Prevent accidental or intentional modification of data.
3. Provide Controlled Resource Sharing – Allow sharing of resources in a controlled and
secure manner.
4. System Stability – Ensure that one faulty process does not affect the entire system.
5. Accountability – Keep track of who accesses what, to maintain audit trails.

Principles of Protection

1. Principle of Least Privilege

o Every user or process should operate with the minimum set of privileges necessary to
perform its task.
o Reduces damage from accidents or attacks by limiting access.
2. Principle of Separation of Privilege
o Access should depend on multiple conditions being satisfied.
o Example: Two keys or passwords may be required to open a secure file.
o Improves security by making unauthorized access more difficult.
3. Principle of Fail-Safe Defaults (Default Deny)
o By default, access should be denied, and only explicitly granted actions are allowed.
o Ensures that new or unrecognized users/processes cannot automatically gain access.
4. Principle of Economy of Mechanism
o The protection mechanism should be simple and small.
o Simplicity reduces the likelihood of design or implementation errors.
5. Principle of Complete Mediation

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
33 of 38
 o Every access request to a resource must be checked for authorization.
o Prevents caching or reusing previous permissions, ensuring up-to-date checks.
6. Principle of Open Design
o The protection mechanism should not depend on secrecy of design or
implementation, but only on the secrecy of keys or passwords.
o Encourages transparency and peer review for better security.
7. Principle of Least Common Mechanism
o Minimize the amount of shared mechanisms used by multiple users.
o Reduces the possibility that one user could affect another.
8. Principle of Psychological Acceptability
o Protection mechanisms should be easy to use and understand.
o If a system is too complex, users may bypass or misuse it, weakening security.

Protection Ring
In Computer Science, the ordered protection domains are referred to as Protection Rings. These mechanisms
help in improving fault tolerance and provide Computer Security. Operating Systems provide different levels
to access resources. Rings are hierarchically arranged from most privileged to least privileged.

Use of Protection Ring : Use of Protection Rings provides logical space for the levels of
permissions and execution. Two important uses of Protection Rings are :
1. Improving Fault Tolerance
2. Provide Computer Security

Levels of Protection Ring : There are basically 4 levels ranging from 0 which is the most privileged to 3
which is least privileged. Most Operating Systems use level 0 as the kernel or executive and use level 3 for
application programs. A resource that is accessible to level n is also accessible to levels 0 to n and the
privilege levels are rings.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
34 of 38
 Modes of Protection Ring : There are basically two modes : Supervisor Mode, and Hypervisor
Mode. These are explained as following below in brief.
1. Supervisor Mode : Supervisor Mode is an execution mode in some of processors which allows
execution of all instructions including privileged instructions. It also gives access to different
address space, to memory management hardware, and to other peripherals. Usually, Operating
System runs in this mode.
2. Hypervisor Mode : Modern CPUs offer x86 virtualization instructions for hypervisor to control
"Ring 0" hardware access. In order to help virtualization, VT and Pacifica insert new privilege
level below "Ring 0" and Both these add nine new "machine code" instructions that only work on
Ring −1 and intended to be used by hypervisor.

Implementation : Protection Rings are combined with processor modes against rule of slave in
some systems. Operating system running on hardware that supports such rules can use both methods
of protecting or only one of them. Efficient use of architecture of Protection Rings requires close
interaction between hardware and operating system. The operating system is designed such that they
have worked on a lot of platforms and may have different implementation mechanism rings on each
platform. The security model is generally simplified to two levels of access - first is level of "core"
and second is level of "user", even if hardware providing greater granularity of performance
levels. Features of Protection Ring :
 Protection Ring follows hierarchy.
 Protection Ring provides layered architecture.
 Protection Ring provides Computer Security.
 Protection Ring provides good Fault Tolerance.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
35 of 38
 Advantages of Protection Rings:
One of the biggest advantages of using Protection Rings is that it provides better control over the
access of system resources. It ensures that the users only have access to the resources they are
authorized to access, thus improving computer security. Additionally, the hierarchical arrangement
of rings helps in reducing the risk of faults, making the system more fault-tolerant.

Drawbacks of Protection Rings:

One of the major drawbacks of Protection Rings is that it can make the system more complex,
making it harder to manage and maintain. Additionally, it can also lead to decreased performance
due to the additional layers of security and processing involved.

Domain of protection: (VVV IMP):

 The protection policies limit the access of each process with respect to their resource handling. A
process is bound to use only those resources which it requires to complete its task, in the time
limit that it requires and also the mode in which it is required. That is the protected domain of a
process.
 A computer system has processes and objects, which are treated as abstract data types, and these
objects have operations specific to them. A domain element is described as <object, {set of
operations on object}>.
 Each domain consists of a set of objects and the operations that can be performed on them. A
domain can consist of either only a process or a procedure or a user. Then, if a domain
corresponds to a procedure, then changing domain would mean changing procedure ID. Objects
may share a common operation or two. Then the domains overlap.

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
36 of 38
 Access matrix:
An Access Matrix is a digital model utilized to control and manage permissions. This model defines
the rights each user has for different resources. In simple terms, it’s a table that shows what actions
an individual or a group of users can perform on specific objects within a system.
It represents the access control mechanism that specifies which actions (e.g., read, write, execute)
are allowed or denied for each subject on each object.
Different Types of Rights
There are different types of rights the files can have. The most common ones are:
1. Read- This is a right given to a process in a domain that allows it to read the file.
2. Write- Process in the domain can be written into the file.
3. Execute- The process in the domain can execute the file.
4. Print- Process in the domain only has access to a printer.
Sometimes, domains can have more than one right, i.e. combination of rights mentioned above.
Let us now understand how an access matrix works from the example given below.

F1 F2 F3 Printer

D1 read read

D2 print

D3 read execute

read
D4 read write
write

Observations of Above Matrix

 There are four domains and four objects- three files(F1, F2, F3) and one printer.
 A process executing in D1 can read files F1 and F3.
 A process executing in domain D4 has same rights as D1 but it can also write on files.
 Printer can be accessed by only one process executing in domain D2.
 A process executing in domain D3 has the right to read file F2 and execute file F3.
Mechanism of Access Matrix
The mechanism of access matrix consists of many policies and semantic properties. Specifically, we
must ensure that a process executing in domain Di can access only those objects that are specified in
row i. Policies of access matrix concerning protection involve which rights should be included in

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
37 of 38
 the (i, j)th entry. We must also decide the domain in which each process executes. This policy is
usually decided by the operating system. The users decide the contents of the access-matrix entries.
Association between the domain and processes can be either static or dynamic. Access matrix
provides a mechanism for defining the control for this association between domain and processes.
Switch operation: When we switch a process from one domain to another, we execute a switch
operation on an object(the domain). We can control domain switching by including domains among
the objects of the access matrix. Processes should be able to switch from one domain (Di) to another
domain (Dj) if and only if a switch right is given to access(i, j). This is explained using an example
below:
F1 F2 F3 Printer D1 D2 D3 D4

D1 read read switch

D2 print switch switch

D3 read execute

D4 read write read write switch

According to the above matrix, a process executing in domain D2 can switch to domain D3 and D4.
A process executing in domain D4 can switch to domain D1 and process executing in domain D1
can switch to domain D2.

*****

BIET College (A) Asst prof CSE Department [OS CSM, CSE , ALLIED BRANCHS R23 Regulation] perpared By SHAIK ARAFATH
38 of 38