UNIT - V

 

UNIT-V

 

File System: File System Interface: File concept, Access methods, Directory Structure; File system Implementation: File-system structure, File-system Operations, Directory implementation, Allocation method, Free space management; File-System Internals: File- System Mounting, Partitions and Mounting, File Sharing. Protection: Goals of protection, Principles of protection, Protection Rings, Domain of protection, Access matrix.

 

FILE SYSTEM INTERFACE:

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.

 

Note: It acts as a bridge between the operating system and the physical storage hardware, allowing users and applications to perform CRUD Operations on files in an organized and efficient manner.

 

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.

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

 

 

1. Name

2. Extension, separated by a period.

 

Issues Handled By File System

• A free space is created on the hard drive whenever a file is deleted from it.

• To reallocate them to other files, many of these spaces may need to be recovered.

• Choosing where to store the files on the hard disc is the main issue with files one block may or may not be used to store a file.

 

File Directories

The collection of files is a file directory and contains information about the files, including attributes, location, etc. Much of this information is managed by the operating system.

Note: The directory is itself a file, accessible by various file management routines. 

 

File Types and Their Content

 Note: It may be kept in the disk's non-contiguous blocks. We must keep track of all the blocks where the files are partially located.

 

Advantages of Maintaining Directories 

• Efficiency: A file can be located more quickly.

• Naming: It becomes convenient for users as two users can have same name for different files or may have different name for same file.

• Grouping: Logical grouping of files can be done by properties e.g. all java programs, all games etc.

Structures of Directory

• Single-Level Directory: In this, a single directory is maintained for all the users. 

• Two-Level Directory: In these separate directories for each user is maintained. 

• Tree-Structured Directory: The directory is maintained in the form of a tree. Searching is efficient and also there is grouping capability. We have absolute or relative path name for a file. 

  

INTRODUCTION TO FILE SYSTEM

 

A file system is a method used by the operating system to store, organize, retrieve, and manage data on storage devices such as HDD, SSD, USB, CD, DVD, etc.

It provides an interface between the user/program and the physical storage device.

 

FILE CONCEPT

 

A file is a named collection of related information stored on secondary storage.

Characteristics of a File

• Stored permanently (non-volatile storage)
• Has a name and metadata
• Managed by OS
• Can be of different types (text, binary, program, audio, etc.)

File acts as the basic unit of storage in an operating system.

 

FILE ATTRIBUTES (File Metadata)

The OS stores extra information about each file known as file attributes.
These attributes help OS manage and protect files.

Common File Attributes:

1. Name – Human-readable name (e.g., notes.txt)
2. Identifier – Unique number assigned by OS
3. Type – Text, binary, executable, etc.
4. Location – Pointer to file blocks on disk
5. Size – Current and maximum size
6. Protection – Read, write, execute permissions
7. Timestamps – Creation, last modification, last access
8. Owner/User ID – Who owns the file
9. Group ID – Group access
10. Flags – Hidden, system, archive, etc.

These attributes are kept in the file control block (FCB) or i-node.

 

FILE OPERATIONS

Files support different types of operations.
These operations are performed through system calls.

Basic File Operations

1. Create
• Allocates space for a new file
• Adds entry in directory
2. Open
• Makes file available for reading/writing
• Returns a file descriptor
3. Read
• Transfers data from file to memory
4. Write
• Writes data from memory to file
• May increase file size
5. Seek
• Moves file pointer to a specific position
• Supports random access
6. Close
• Releases file descriptor
• Ensures data is saved
7. Delete
• Removes file from directory
• Frees storage blocks

 

FILE STRUCTURE

Files can be organized in three main ways:

Byte Sequence

• Sequence of bytes
• No structure enforced by OS
• Used by UNIX/Linux
• Programs interpret meaning

Example: .txt, .cpp, .pdf

Record Sequence

• File is divided into fixed or variable-size records
• Used in databases and transaction systems

Example:
Employee records, student database

Tree Structure

• Hierarchical structure inside file
• Used in compound documents and indices

Example: XML, JSON, index blocks

 

FILE TYPES

File Formats with Types and Extensions

File Formats store a large variety of raw information in a structured format so that the data can be easily stored, processed, and harnessed. A file format is a standard way of storing data in a computer file. There are multiple types of file formats present which can be used to store and retrieve data efficiently.

• Defines how data is structured and stored in a file.

• Many types of file formats exist to serve different needs.

• Each format is designed to handle specific types of data, such as text, images, or audio.

• The right file format helps with easy storage, retrieval, and processing of data.

 

1. Text File Formats

Text file formats are some of the most basic and widely used formats for storing textual data. They don’t include additional formatting or media. These formats are easily editable and can be opened with any text editor.

Extension	Full Form	Description
.txt	Plain Text	The most basic text file format, containing only ASCII characters and carriage returns to separate lines.
.rtf	Rich Text Format	A more advanced text file format that allows basic formatting like bold, italics, and font styles.
.docx	Word Open XML Document	Commonly used by Microsoft Word for storing and saving documents
.csv	Comma-Separated Values	A simple format for storing tabular data, with each row representing a data record and commas separating fields.
.doc	Word Document	Used for word processing documents stored in Microsoft Word Binary File Format
.wps	WPS Office Word Document	A proprietary document file format developed by Kingsoft Office.
.wpd	WordPerfect Document	A document file format associated with WordPerfect, a word processing software.
.msg	Message	Microsoft Outlook message format; contains email messages with formatting, attachments, and other information.

 

2. Image File Formats

Image file formats determine how pictures are saved and shown. Choosing the right format affects the file size, quality, and how well it works with different devices, especially for photography, websites, and design.

Extension	Full Form	Description
.jpg	Joint Photographic Experts Group	A lossy compression format that is commonly used for photographs and other images with a lot of detail.
.png	Portable Network Graphics	A lossless compression format that is commonly used for images with sharp edges or text.
.webp	Web Picture Format	It Supports both lossy and lossless image compression with support of 24-bit RGB color.
.gif	Graphics Interchange Format	The limited-color format is commonly used for animations and small images.
.tif	Tagged Image File Format	High-quality format that is commonly used for professional photography and printing.
.bmp	Bitmap	An uncompressed format that is commonly used by Microsoft Windows.
.eps	Encapsulated PostScript file	A vector format that is commonly used for print graphics.

 

 

3. Audio File Formats

Audio files come in different formats based on how much they need to be compressed, their quality, and file size. Whether you need top-quality sound or streaming, there are many formats to pick from.

Extension	Full Form	Description
.mp3	MP3 Audio File	Commonly used for storing and distributing music.
.wma	Windows Media Audio	Developed by Microsoft for audio compression, often used for streaming and downloading music.
.snd	Sound	A generic file extension for sound files, often associated with audio data.
.wav	WAVE Audio File	Commonly used for storing and recording audio.
.ra	RealAudio	It's a playlist file format that is commonly used for storing and distributing playlists.
.au	Audio	Used for storing audio data, commonly associated with Sun Microsystems.
.aac	Advanced Audio Coding	Used as an in-vogue sound field design for packed virtual sound and tune data.

 

4. Video File Formats

Video files need special formats to store both the video and audio. Knowing the different video formats can help you pick the best one for quality, file size, and compatibility.

Extension	Full Form	Description
.mp4	MPEG-4 Video File	Multimedia container format that commonly stores video and audio data.
.3gp	3GPP Multimedia File	Multimedia container format that is commonly used for mobile phones.
.avi	Audio Video Interleave File	An older multimedia container format that is still supported by many devices.
.mpg	MPEG Video File	Older video compression format that is still supported by some devices.
.mov	Apple QuickTime Movie	The format that is commonly used by Apple devices.
.wmv	Windows Media Video File	The format that is commonly used by Microsoft devices.

 

5. Program File Formats

Program file formats are used to store source code and scripts written in various programming languages. They allow developers to write, compile, and run programs.

Extension	Full Form	Description
.c	C/C++ Source Code File	General-purpose programming language developed by Dennis Ritchie at Bell Labs between 1969 and 1972.
.cpp	C++ source Code File	A general-purpose programming language developed by Bjarne Stroustrup as an extension to the C programming language.
.java	Java Source Code File	Programming language created by Sun Microsystems that is now owned by Oracle Corporation.
.py	Python script	The programming language was developed by Guido van Rossum and first released in 1991.
.js	JavaScript	A scripting language that is primarily used to add interactivity to web pages.
.ts	TypeScript	A superset of JavaScript that adds optional static typing.
.cs	C# Ssource Code File	A programming language developed by Microsoft as part of the .NET framework.
.swift	Swift Source Code File	Programming language developed by Apple for developing iOS, macOS, watchOS, tvOS, and Linux applications
.dta	Document Type Definition File	A data storage format commonly used by Stata, a statistical software program.
.pl	Perl Script	A programming language developed by Larry Wall at the University of California, Santa Cruz in the early 1980s.
.sh	Bash Shell Script	A shell scripting language commonly used to automate tasks on Unix-like operating systems
.bat	Batch file	Batch file format used to automate tasks on Windows systems; contains a series of commands to be executed by the command interpreter.
.com	Command file	A COM file is an executable file format used for programs on older Windows systems. COM files have limited functionality compared to modern formats.
.exe	Executable file	An executable file is a type of computer file that contains compiled code that can be run directly by the operating system. Executable files are commonly used to run programs.

 

 

6. Compressed/Archive File Formats

Compressed or archive file formats reduce the size of files and group multiple files into one archive. These formats are used for file transfer and storage efficiency.

Extension	Full Form	Description
.rar	WinRAR Compressed Archive	A proprietary file archiver developed by Eugene Roshal.
.zip	Zipped File	A lossless data compression format that packages multiple files into a single archive file.
.hqx	BinHex	A Macintosh binary-to-text encoding format often used to transfer binary files through email.
.arj	Archived by Robert Jung	A file compression format, similar to ZIP and RAR, used to compress and archive files.
.tar	Compressed Tarball File	This file archiving format groups multiple files into a single archive file.
.arc	ARC archive file	An ARC file is an archive file format used for compressing and storing files. ARC is an outdated format and has been replaced by ZIP and other newer options.
.sit	StuffIt archive file	A SIT file is an archive file format used on Macintosh systems. SIT is similar to ARC but is specific to Macs.
.gz	GZIP compressed file	A GZ file is a file format created with gzip compression. Gzip shrinks the size of files for storage and transmission.
.z	Compressed file	A Z file is a compressed file format associated with the "compress" compression program on Unix systems.

 

7. Web page File Formats

Web page file formats are used to create and style web pages. They include markup languages, style sheets, and scripts that determine how web pages are structured and presented.

Extension	Full Form	Description
.html	Hyper Text Markup Language File	HTML is the standard markup language for creating web pages.
.htm	Hyper Text Markup Language File	Hypertext Markup Language (HTML) document format with the less common file extension; identical to .html files.
.xhtml	Extensible Hypertext markup language File	This is a markup language that combines HTML with XML.
.asp	Active Server page	A web development technology that allows developers to create dynamic web pages using server-side scripting.
.css	Cascading Style Sheet	This is a style sheet language used to describe the presentation of a web page.
.aspx	Active Server Page Extended File	This allows developers to create dynamic web pages using server-side scripting in ASP.NET.
.rss	Rich Site Summary	This is a web feed format that allows users to subscribe to updates from websites.

 

8. Features of File Formats

• Structure Data: File Formats have a basic structure of how data should be stored in the file.

• Extension: Extensions are useful so that the operating system can check which type of file is being used.

• Metadata: This is the data that stores useful information about the file such as author name, license, etc.

• Interoperability: This feature enables multiple systems to use the same file format.

 

FILE ACCESS METHODS

How data in a file is accessed:

1. Sequential Access
• Read data in order
• Simple and most common
2. Direct (Random) Access
• Jump to any location
• Uses file pointer
3. Indexed Access
• Uses index table
• Combines sequential + direct access

 

Types of File Access Methods in the Operating System

1. Sequential Access

The operating system reads the file word by word in a sequential access method of file accessing. A pointer is made, which first links to the file's base address. If the user wishes to read the first word of the file, the pointer gives it to them and raises its value to the next word. This procedure continues till the file is finished. It is the most basic way of file access. The data in the file is evaluated in the order that it appears in the file and that is why it is easy and simple to access a file's data using a sequential access mechanism. For example, editors and compilers frequently use this method to check the validity of the code.

Advantages of Sequential Access:

• The sequential access mechanism is very easy to implement.
• It uses lexicographic order to enable quick access to the next entry.

Disadvantages of Sequential Access:

• Sequential access will become slow if the next file record to be retrieved is not present next to the currently pointed record.
• Adding a new record may need relocating a significant number of records of the file.

 

2. Direct (or Relative) Access

A Direct/Relative file access mechanism is mostly required with the database systems. In the majority of the circumstances, we require filtered/specific data from the database, and in such circumstances, sequential access might be highly inefficient. Assume that each block of storage holds four records and that the record we want to access is stored in the tenth block. In such a situation, sequential access will not be used since it will have to traverse all of the blocks to get to the required record, while direct access will allow us to access the required record instantly.

The direct access mechanism requires the OS to perform some additional tasks but eventually leads to much faster retrieval of records as compared to sequential access.

 

Advantages of Direct/Relative Access:

• The files can be retrieved right away with a direct access mechanism, reducing the average access time of a file.
• There is no need to traverse all of the blocks that come before the required block to access the record.

Disadvantages of Direct/Relative Access:

• The direct access mechanism is typically difficult to implement due to its complexity.
• Organizations can face security issues as a result of direct access as the users may access/modify the sensitive information. As a result, additional security processes must be put in place.

 

3. Indexed Sequential Access

            It's the other approach to accessing a file that's constructed on top of the sequential access mechanism. This method is practically similar to the pointer-to-pointer concept in which we store the address of a pointer variable containing the address of some other variable/record in another pointer variable. The indexes, similar to a book's index (pointers), contain a link to various blocks present in the memory. To locate a record in the file, we first search the indexes and then use the pointer-to-pointer concept to navigate to the required file.

Primary index blocks contain the links of the secondary inner blocks which contain links to the data in the memory.

 

 

Advantages of Indexed Sequential Access:

• If the index table is appropriately arranged, it accesses the records very quickly.
• Records can be added at any position in the file quickly.

 

Disadvantages of Indexed Sequential Access:

• When compared to other file access methods, it is costly and less efficient.
• It needs additional storage space.

 

DIRECTORY STRUCTURE

Structures of Directory in Operating System

The operating system uses directories to track where files are stored, just like using folders to organize papers.

• Different directory structures can be used to suit various organizational needs.

• Understanding directory structures helps in organizing and accessing files more easily.

By using these structures, it becomes simpler to manage and navigate files on your computer.

 

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.

• 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 change of name collision because two files can have the same name.

• Searching will become time taking if the directory is large.

• This cannot 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.

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

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.

File system implementation is a critical aspect of an operating system as it directly impacts the performance, reliability, and security of the system. Different operating systems use different file system implementations based on the specific needs of the system and the intended use cases. Some common file systems used in operating systems include NTFS and FAT in Windows, and ext4 and XFS in Linux.

Components of File System Implementation

The file system implementation includes several components, including:

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

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. In this article, we will learn different file operations and what are the system calls and APIs used to perform them in a Linux / Windows-based OS.

 

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
Creating Files	Create a new file for data storage.	open() (Linux-like systems) CreateFile() (Windows)
Creating Directories	Create a new directory for organizing files.	mkdir() (Linux systems) CreateDirectory() (Windows)
Opening Files	Open a file that you already have open to read or write from.	open() (Linux systems) CreateFile() (Windows)
Reading Files	Retrieve data from an open file.	read() (Linux systems) ReadFile() (Windows)
Writing Files	Store data in an open file.	write() (Linux systems) WriteFile() (Windows)
Renaming Files and Directories	If you want to rename a file or directory,.	rename() (Linux systems) MoveFile() (Windows)
Deleting Files and Directories	Remove files or directories.	unlink() (Linux systems) remove() (Linux systems) 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.

File Operation	Description	System Calls / APIs
Copying Files	Create duplicates of files in another location.	cp (Linux systems) CopyFile() (Windows)
Moving Files	Relocate files from one location to another.	mv (Linux systems) MoveFile() (Windows)
Searching for Files	Locate files based on specific criteria.	find (Linux systems) FindFirstFile() and FindNextFile() (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 Permissions	Control access rights to files and directories.	·             chmod (Linux systems) ·             SetFileSecurity (Windows)
File Ownership	Assign specific users or groups as file owners.	·             chown (Linux systems) ·             SetFileSecurity (Windows)
File Metadata	Retrieve and manipulate file information.	·             stat (Linux systems) ·             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.

File Operation	Description	System Calls / APIs
File Compression	Reduce file sizes to save storage space.	gzip, zip, tar (Linux systems), Compress-Archive (Windows)
File Encryption	Protect data by converting it into an unreadable format.	openssl, gpg (Linux systems) Windows provides encryption libraries 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. There are numerous ways in which the directories can be implemented. But we need to choose an appropriate directory implementation algorithm that enhances the performance of the system. 

The below are two ways of implementing the directory in the operating system :

• Directory Implementation using Singly Linked List

• Directory Implementation using Hash Table

Directory Implementation using Singly Linked List

The implementation of directories using a singly linked list is easy to program but is time-consuming to execute. Here we implement a directory by using a linear list of filenames with pointers to the data blocks.

Steps to Implement the Directory Using Singly Linked List

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

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

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.

 

 

ALLOCATION METHOD:

What is File Allocation in OS?

Whenever a hard disk is formatted, a system has many small areas called blocks or sectors that are used to store any kind of file. File allocation methods are different ways by which the operating system stores information in memory blocks, thus allowing the hard drive to be utilized effectively and the file to be accessed. Below are the types of file allocation methods in the Operating System.

Types of File Allocation Methods in Operating System.

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

 

Let's have an in-detail explanation about each of them,

Contiguous File Allocation.

First, let's understand the meaning of contiguous, here contiguous means adjacent or touching. Now let's understand what contiguous file allocation is.

What is Contiguous File allocation?

In contiguous file allocation, the block is allocated in such a manner that all the allocated blocks in the hard disk are adjacent.

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.

Let's understand this diagrammatically.

Example

We have three different types of files that are stored in a contiguous manner on the hard disk. 

In the above image on the left side, we have a memory diagram where we can see the blocks of memory. At first, we have a text file named file1.txt which is allocated using contiguous memory allocation; it starts with the memory block 0 and has a length of 4 so it takes the 4 contiguous blocks 0,1,2,3. Similarly, we have an image file and video file named sun.jpg and mov.mp4 respectively, which you can see in the directory that they are stored in the contiguous blocks. 5, 6, 7 and 9, 10, 11 respectively.

Here the directory has the entry of each file where it stores the address of the starting block and the required space in terms of the block of memory.

Advantages and Disadvantages

Advantages

• It is very easy to implement.
• There is a minimum amount of seek time.
• The disk head movement is minimum.
• 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. As
• Due to its constrained allocation, it is possible that the disk would fragment internally or externally.

 

Linked File Allocation.

What is Linked File Allocation?

The Linked file allocation 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. Now, you must be thinking about how the OS remembers that all the scattered blocks belong to the same file. So as the name linked File Allocation suggests, 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.

Let's understand this better diagrammatically by taking an example.

Example

Here we have one file which is stored using Linked File Allocation.

 

 

In the above image on the right, we have a memory diagram where we can see memory blocks. On the left side, we have a directory where we have the information like the address of the first memory block and the last memory block.

In this allocation, the starting block given is 0 and the ending block is 15, therefore the OS searches the empty blocks between 0 and 15 and stores the files in available blocks, but along with that it also stores the pointer to the next block in the present block. Hence it requires some extra space to store that link.

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.

 

Indexed File Allocation.

What is Indexed File Allocation?

The indexed file allocation 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. That means we will get all the locations of blocks in one index file. 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.

Let's take an example to explain this better.

Example

As shown in the diagram below block 19 is the index block which contains all the addresses of the file named text1. In order, the first storage block is 9, followed by 16, 1, then 10, and 25. The negative number -1 here denotes the empty index block list as the file text1 is still too small to fill more blocks.

 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.

 

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

 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.

 Note: The free space list head points to Block 5 which points to Block 6, the next free block and so on. The last free block would contain a null pointer indicating the end of free list.

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.

 

Advantages:

• Fast allocation as free blocks is known upfront.

• Easy to traverse and maintain.

Disadvantages:

• Extra memory needed to store the list.

• May suffer from fragmentation over time.

 

FILE-SYSTEM INTERNALS

 

Topics:

1.      File-System Mounting

2.      Partitions and Mounting

3.      File Sharing

1. FILE-SYSTEM MOUNTING

File-System Mounting is the process by which the operating system makes a file system available for use.

A file system stored on a disk cannot be used immediately.
The OS must attach (mount) it to a directory in the existing directory structure.

1.1 Need for Mounting

·         To access files stored on a new disk/device

·         To integrate multiple file systems under a single directory tree

·         To provide access to USB, CD/DVD, network drives

·         To manage permissions and access control

 

1.2 Mount Point

A mount point is a directory in the currently running file system where another file system is attached.

Example:

·         In Linux: /mnt/usb, /media/disk

·         In Windows: a drive letter is used (C:, D:)

 

1.3 Mounting Process

When a device is mounted, the OS performs the following steps:

Step 1:

User requests mount (e.g., mount /dev/sda1 /mnt/disk).

Step 2:

OS reads the superblock of the file system:

·         File system type (ext4, NTFS…)

·         Block size

·         Free/allocated blocks

·         Volume information

Step 3:

The OS checks:

·         File system consistency

·         Permissions of the user

·         Device validity

Step 4:

If valid, OS attaches file system to mount point.

 

1.4 Mount Table

The OS maintains a mount table that stores:

·         List of mounted file systems

·         Their mount points

·         Device names

·         Access permissions (read-only, read-write)

Used to manage and track all active mounts.

 

1.5 Types of Mounting

 

a) Permanent Mounting

·         Defined in system configuration files

·         Automatically mounted at boot time
Example: /etc/fstab in Linux.

b) Temporary Mounting

·         Manual mounting by user

·         Can be unmounted after use
Example: mounting a USB drive.

c) Read-Only Mounting

·         For CDs, DVDs, or protected devices

·         Prevents modification

d) Network Mounting

·         Mounting remote file systems
Example: NFS, SMB, AFP.

 

2. PARTITIONS AND MOUNTING

A disk is divided into partitions, and each partition can hold a separate file system.

2.1 What is a Partition?

A partition is a logical division of a disk.
It divides a physical disk into multiple independent regions.

Why partitions are used?

·         To install multiple operating systems

·         To separate system files, user files, and swap space

·         To improve reliability and security (if one partition fails, others work)

2.2 Types of Partitions

1.      Primary Partition

o    Maximum of 4 on MBR disks

o    Can directly hold a file system

2.      Extended Partition

o    Only 1 allowed

o    Contains multiple logical partitions

3.      Logical Partition

o    Created inside extended partitions

o    Acts like primary partitions

4.      GPT Partitions (GUID Partition Table)

o    Supports unlimited partitions

o    New standard for large disks (>2 TB)

2.3 File System vs Partition

·         A partition is a disk division.

·         A file system is a structure created inside a partition.

Example:
Partition: /dev/sda1
File system inside it: ext4, NTFS, FAT32

 

2.4 Mounting Partitions

Each partition must be mounted before use.

Example in Linux:

mount /dev/sda1 /home

mount /dev/sdb2 /data

Each partition becomes part of the unified directory tree.

 

2.5 Un-mounting

Unmounting means detaching a partition from the system.

Command (Linux):

umount /mnt/usb

Unmounting is required to:

·         Prevent data corruption

·         Complete pending write operations

 

3. FILE SHARING

File sharing allows multiple users or processes to access the same file.

 

3.1 Need for File Sharing

·         Multi-user systems

·         Distributed systems

·         Collaboration among users

·         Reduced duplication of files

·         Efficient resource utilization

 

3.2 File Sharing in Multi-user OS

 

a) User-level sharing

Users share files with different permissions:

·         Read

·         Write

·         Execute

b) Group-level sharing

Files can be assigned to a specific group of users.

c) Public sharing

Everyone can access the file.

 

3.3 File Protection in Sharing

Protection mechanisms prevent unauthorized access.

i. Access Control Lists (ACLs)

Defines users and their allowed operations:

·         read (r), write (w), execute (x)

ii. Password Protection

Each shared file can have a password.

iii. File Permissions

Example in Linux:

rwx r-x r--

Owner Group Others

 

3.4 Consistency Issues in Sharing

When multiple users access the same file:

·         Concurrent Writes → Conflict

·         Concurrent Reads → Safe

To handle conflicts:

·         File-locking mechanisms

·         Read-lock

·         Write-lock

 

3.5 File Locking

Types:

1.      Shared Lock

o    Multiple processes can read

2.      Exclusive Lock

o    Only one process can read/write

Locking Modes:

·         Mandatory Locking

·         Advisory Locking

Used in databases, servers, distributed systems.

 

3.6 File Sharing in Distributed Systems

File sharing across a network using:

 

a) NFS (Network File System)

Used in Linux/Unix.

 

b) SMB/CIFS

Used in Windows.

 

c) AFS (Andrew File System)

Used for large-scale distributed systems.

Features:

·         Remote mounting

·         Transparent access

·         Cache consistency

 

PROTECTION IN OPERATING SYSTEM

Protection refers to the mechanisms used by an OS to control access to system resources (CPU, memory, files, devices) and ensure that only authorized users or processes perform allowed operations.

A protection system prevents:

• Unauthorized access
• Accidental misuse
• Malicious activities
• System failures due to faulty programs

 

GOALS OF PROTECTION

The goals define why protection is required in an OS.

 

2.1 Prevent Unauthorized Access

Only legitimate users and processes must access resources.
Prevents illegal viewing, modification, or deletion of data.

 

2.2 Ensure Fair Resource Allocation

Every process should get resources based on policy.
Avoids resource hogging by a single user/process.

 

2.3 Improve System Reliability

Protects OS from faulty or malicious programs.
Ensures system stability and avoids crashes.

 

2.4 Maintain System Integrity

System files, kernel data, and configuration must be safeguarded
from corruption or tampering.

 

2.5 Enable Controlled Sharing

Some resources must be shared safely among users.
Protection ensures access only within permissions.

 

2.6 Support Multiple Security Policies

Allows flexible access control for:

• Sensitive data
• Multi-user systems
• Network-based environments

 

PRINCIPLES OF PROTECTION

Protection systems are designed based on certain principles.

 

Principle of Least Privilege

A process/user should have only the minimum privileges required to perform tasks.
Reduces damage caused by errors.

Example: A text editor should not have access to kernel memory.

 

Principle of Separation of Duty

Responsibilities should be divided among users.
Prevents misuse of privileges.

Example: One person approves a transaction; another executes it.

 

Principle of Economy of Mechanism

Protection mechanisms must be simple and easy to implement.
Complex systems lead to improper use.

 

Principle of Fail-Safe Defaults

Access should be denied by default.
Permissions must be explicitly granted.

 

Principle of Complete Mediation

Every access to every object must be checked for authorization.
No shortcuts or cached permissions.

 

Principle of Open Design

Security should not depend on secrecy of design.
Only passwords/keys must be secret.

 

Principle of Least Common Mechanism

Shared mechanisms should be minimized to reduce risk.

 

Principle of Psychological Acceptability

Protection should not interfere with normal user behavior.
It should be easy and intuitive.

 

PROTECTION RINGS

Protection rings define levels of privilege in the system.
Lower ring number = higher privilege.

 

Ring Structure

Typically divided into four rings:

  Ring 0   - Kernel (highest privilege)

  Ring 1   - Device drivers

  Ring 2   - System utilities

  Ring 3   - User applications (lowest privilege)

 

Ring 0 – Kernel Mode

• Full access to hardware
• Executes critical instructions
• No restrictions
• Handles memory, process management

 

Ring 1 – System Software

• Used by device drivers
• Limited privileged instructions allowed

 

Ring 2 – Services

• Networking services
• I/O management services
• More privileges than user mode

 

Ring 3 – User Mode

• User applications
• Restricted from hardware access
• Cannot execute privileged instructions

Example:User-level processes cannot directly access I/O ports.

 

Purpose of Protection Rings

• Provide layered security
• Limit damage caused by faulty applications
• Enforce controlled access between layers

 

 

 

DOMAIN OF PROTECTION

A domain defines the set of resources and access rights that a process has.

A domain is a logical boundary within which a process has certain privileges.

Example:

• User domain
• Kernel domain
• File system domain

 

Types of Domains

 

a) User Domain

Contains resources owned by the user
(files, applications, CPU time)

 

b) System Domain

Includes OS kernel, system files, device drivers.

 

c) Process Domain

Each process has its own rights
(can read memory allocated to it)

 

Static vs Dynamic Domain Switching

Static Switching

A process stays in one domain throughout execution.

Dynamic Switching

A process may switch domains during execution
(e.g., system calls switch from user mode to kernel mode).

 

Domain Representation

Domains are represented as:

• Access control lists (ACLs)
• Capability lists
• Access matrices

 

ACCESS MATRIX

The Access Matrix is a fundamental model for defining who can access what.

Definition

An n × m matrix:

• Rows = Subjects (users/processes)
• Columns = Objects (files/devices)
• Entries = Access rights (read, write, execute)

 

Structure of Access Matrix

Example:

	File1	File2	Printer
User A	read,write	read	print
User B	read	—	print
Admin	r,w,x	r,w,x	Configure

 

Access Rights

Common rights include:

• read
• write
• execute
• append
• delete
• create
• own

 

Implementation of Access Matrix

 

a) Access Control List (ACL)

For each object, maintain a list of subjects and their rights.

Good for object-based protection.
Example (Linux file permissions).

 

b) Capability List

For each subject, maintain a list of objects and rights.

Good for subject-based protection.
Used in network systems and capability-based OS.

 

Advantages

• Clear representation of access rights
• Supports hierarchical and group permissions
• Helps implement secure systems

 

Limitations

• Large matrix for big systems
• Mostly sparse → lots of empty entries
• Hard to manage dynamically

 

 

 

 

***************** END OF UNIT V *****************