UNIT -V

Mass Storage Structure: Overview of Mass Storage Structure- HDD scheduling – Swap Space
Management, I/O systems: I/O Hardware, Application I/O interface, Kernel I/O Subsystem, File System
Interface: File Concept – Access Methods – Directory Structure – Protection, File-System
Implementation: File-System Structure-File-System Operations - Directory Implementation - Allocation
Methods - Free-Space Management, Case Study-Linux

File definition:

A file is a named collection of related information that is recorded on secondary storage such as
magnetic disks, magnetic tapes and optical disks.

File Type

File types allow an operating system to recognize and manage files based on their function and
content. Many operating systems support many types of files. Operating system like MS-DOS and
UNIX have the following types of files

Ordinary files

These are the files that contain user information. The user can apply various operations on such
files like add, modify, delete or even remove the entire file.

Directory files

Directory files store a list of file names and associated metadata, such as permissions, size, and
modification dates.

Special Files (Device Files)

Special files are also referred to as device files. They represent physical or virtual devices
attached to the computer, such as disks, terminals, printers, and tape drives.

These files are of two types

Character special files − data is handled character by character as in case of terminals or printers.

Block special files − data is handled in blocks as in the case of disks and tapes

File Attributes

1. Name

• The human-readable name of the file. It is the main way users identify and access files.
• Example: document.txt, photo.jpg
2. Identifier

• A unique identifier, typically a number, that identifies the file within the file system. This
is used by the OS for efficient file management and is not human-readable.
• Example: File IDs or inodes in UNIX-based systems.

3. Type

• Indicates the file type, such as text, binary, executable, or directory.

• Example: .txt, .exe, .jpg

4. Location

• It includes information about the device and the physical location of the file.
• Example: Addressing details for sectors or blocks on a hard drive.

5. Size

• The current size of the file in bytes, words, or blocks.

• Example: 1.5 MB, 1024 KB

6. Protection

• Access-control settings that determine who can read, write, or execute the file. This
attribute helps secure files and control user permissions.
• Example: rwx (read, write, execute) permissions in UNIX.

7. Time, Date, and User Identification

• Stores information such as the file’s creation time, last modification time, and last access
time. It may also record the user or owner of the file.

File Operations

1. Creating a File

Two steps are necessary to create a file.

1. Space Allocation: The operating system locates and allocates space in the file system for the
new file.
2. Directory Entry: An entry for the file is created in the directory, recording its attributes and
location.

2. Writing a File

• Allows data to be added to a file at the current write pointer location.

• The system call specifies the file name and the data to be written.
• A write pointer keeps track of the location in the file where data is added.
• This pointer is updated with each write operation.

3. Reading a File

• Enables data to be accessed from the file for use in applications

• A system call specifies the file name and the memory location where the data should be
stored.
• A read pointer tracks the current position in the file for reading.

4. Repositioning within a File (File Seek)

• Allows moving to a specific location within a file without any actual I/O, useful for
navigating large files.

5. Deleting a File

• Frees up storage space for other files and removes the file entry from the directory.

6. Truncating a File

• Enables clearing a file’s contents without deleting it, preserving attributes.

Describe the various directory structures.

Directory

• A directory is a container that is used to contain folders and file.

• It organizes files and folders into a hierarchical manner.

Types of Directories :

There are many types of directory structure in Operating System. They are as follows :-

1. Single Level Directory

2. Two Level Directory

3. Tree Structured Directory

i) Single Level Directory :

• In Single Level Directory, all files are in the same directory. Simple to implement, but each
file must have a unique name.

• Single level directory structure is suitable only for single user. If user increases, it creates
the problem with assigning the name to files.

• In single level directory structure, no two files can have the same name.

• It is simple to implement and searching file is faster. This type of directory system is used
in Cameras and phones.

• Because of limitation of file names, this structure is rarely implemented.

• File name size varies according to the operating system. MS-DOS operating system
allows only 11 character file names and UNIX OS allows up to 255 characters.

Limitations of Single Level Directory

• Not suitable for a large number of files

• Limitation of unique file name.

• For large number of file, recalling file name is difficult.

Two Level Directory :

• As, a single level directory often leads to confusion of files names among different users hence
the solution to this problem is to create a separate directory for each user.

• In the two-level directory structure, each user has their own user files directory (UFD).

• The UFDs has similar structures, but each lists only the files of a single user. System’s master
file directory (MFD) is searches whenever a new user id=s logged in.

• The MFD is indexed by username or account number, and each entry points to the UFD for
that user.

Limitations of Two Level Directory

• The structure effectively isolates one user from another

Tree Structured Directory :

• A directory (or Sub directory) contains a set of files or sub directories. All directories has the
same internal format. Each user / process has the concept of a current directory from which all
(relative) searches take place.
• Files may be accessed using either absolute pathnames or relative pathnames.
• Directories are stored the same as any other file in the system, except there is a bit that
identifies them as directories, and they have some special structure that the OS understands.

Explain File Allocation Methods In Detail.

Allocation Methods

Three major methods of allocating disk space are:

1. Contiguous Allocation

2. Non – contiguous

1) Linked or chained Allocation

2) Indexed Allocation

1. Contiguous Allocation

• Description: In contiguous allocation, each file is stored in a single, continuous section

of disk blocks. The file's blocks are allocated sequentially.
• Advantages:
o Simple to implement.
o Provides excellent performance due to minimal seek time, as all blocks of a file
are close together.
• Disadvantages:
o Leads to external fragmentation over time as files are created and deleted.
o Difficult to extend files if there is no space adjacent to the allocated blocks.
2. Non-Contiguous Allocation

Non-contiguous allocation allows files to occupy multiple non-adjacent blocks. There are two
primary types:

a) Linked (Chained) Allocation

• Description: Each file is a linked list of disk blocks. The directory entry for a file contains
a pointer to the first disk block, and each block contains a pointer to the next block.
• Advantages:
o Eliminates external fragmentation since files don’t require contiguous blocks.
o Files can be easily extended by adding more blocks to the chain.
• Disadvantages:
o Random access is slow because each block must be read in sequence.
o Storage space is wasted by the pointers in each block.
b) Indexed Allocation

• Description: Each file has an index block, which contains pointers to all the disk blocks
used by the file. The index block allows direct access to each data block.
• Advantages:
o Supports direct access, allowing faster data retrieval.
o No external fragmentation, and files can be easily extended by adding new
blocks.
• Disadvantages:
o Overhead for maintaining the index block, which uses additional space.
o If the index block is full, handling large files can be complex
Explain File Access methods in detail.

File Access Methods

File access methods determine how data within a file is retrieved, allowing flexibility in how
files are read and managed. Here are the common access methods:

1. Sequential Access

• Files are accessed sequentially, meaning that data is read or written in order, one record
after another.
• Commonly used in applications where data needs to be processed in order, such as log files
or audio and video files.
• Advantages:
o Simple and straightforward to implement.
o Suitable for applications requiring ordered processing.
• Disadvantages:
o Inefficient for retrieving specific records quickly, as the file has to be read from
the beginning to the desired record.

2. Direct (Random) Access

• Direct access allows specific records to be read or written directly without reading the
previous records. Each record has a unique address, so data can be accessed in any order.
• Useful for databases or applications where individual records need to be frequently
accessed, such as in search engines or customer databases.
• Advantages:
o Faster access to specific records.
o Allows flexible data retrieval and updates.
• Disadvantages:
o Implementation is more complex than sequential access.
o Not suitable for all types of data, especially those requiring sequential pro
cessing.
3. Indexed Sequential Access

• This method combines features of both sequential and direct access. An index is
maintained, which contains pointers to various blocks of data. Files can be accessed
sequentially or directly using the index.
• Frequently used in databases and large systems where both sequential and direct access are
needed.
• Advantages:
o Efficient for both sequential and random access.
o Index improves access speed for direct access to records.
• Disadvantages:
o Additional overhead for maintaining the index.
o More complex than pure sequential or direct access methods.

Explain Free-Space Management in detail.

Free-Space Management

Free space management is essential to keep track of available disk space for efficient file storage. When
files are deleted, the blocks they occupied are added back to a free-space list. The operating system
maintains this free-space list and uses various techniques to manage it effectively.
1. Bit tables or bit vector
2. Chained free portions or linked list
3. Indexing or grouping
4. Free block list or counting

1. Bit Vector

• The free-space list is implemented as a bit table or bit vector. Each block is represented by
1 bit. If the block is free, the bit is 1; if the block is allocated, the bit is 0.
• For example, consider a disk where blocks 3, 4, 5, 7, 9, 14, 15, 19, 30, 31, 32, 35, 36, 37, 38 are
free blocks and rest of the blocks are allocated.
• The free space is shown below
111000101011110011101111111111000110000

Advantages
• Easy to find a free blocks.
• It is as small as possible.

2. Link list

• In this method, all free space disk blocks are linked, keeping a pointer to the first free block. All
file allocation methods used link list tree space techniques.
• There is small space overhead because there is no need for a disk allocation table. In the above
example, free blocks are 3, 4, 5, 7, 9, 14, 15, 19, 30, 31, 32, 35, 36, 37, 38.
• Here free block pointer is on block number 3. Block3 contains pointer to block 4, block4 contains
pointer to block 5 and block 5 contains pointer to block 7 and so on.
• This method is not efficient because to reach free block 9, we have to traverse block 3, 4, 5 and 7
then we will reach to block 9.
• Disk will become quite fragmented after some use. Many portions will be a single block long.

3. Grouping
• First free block contains the addresses of n free blocks. The first n-1 of these blocks is actually
free.
• The last block also contains the address of another n free block.
• When all the blocks in the group have been allocated, then use the block that held the pointer.
• Because of grouping method, address of a large number of free blocks can be found quickly.

4. Counting

Counting is a method for tracking free blocks in disk storage. Instead of listing each free block
individually, it keeps:

1. The address of the first free block in a sequence.

2. The number of contiguous free blocks following this starting block.

Each entry in the free space list has two main parts:

• Disk address: Points to the starting block of a contiguous sequence of free blocks.
• Count: Indicates how many consecutive free blocks are available after the starting block.
Explain File-System Structure in detail.

Three kinds of files

• Byte Sequence
• Record Sequence
• Tree Structure

1. Byte Sequence

• This is the simplest file structure, where a file is seen as a sequence of bytes with no
specific structure enforced by the file system.

Advantages:

• Simple, flexible, and versatile;

• It allows applications to define their own structure within the file.

Examples: Text files (.txt), binary executables (.exe), image files (.jpg, .png).

2. Record Sequence

• In this structure, the file is organized as a series of records. Each record typically has a
fixed format or a defined set of fields.

Advantages:

• Easier to handle structured data within the file.

• Accessing specific records is more efficient since each record has a predictable location
or structure.

Examples: Database files, indexed files, or files used by older mainframe systems (e.g., COBOL
applications).
3. Tree Structure

• Here, data within a file is organized hierarchically in a tree format, allowing for nested
structures and more complex relationships between data elements.

Advantages: Efficient for managing nested data structures, enabling faster access to related or
grouped data.

Examples: Directory files, XML files, JSON files, and certain types of databases

Explain Disk Scheduling Algorithms in detail.

Disk scheduling algorithm

Disk scheduling algorithms manage the order in which disk I/O requests are serviced. These algorithms
are designed to reduce seek time, which is the time it takes for the disk's read/write head to move to the
correct track.

1. FCFS (First Come First Serve)

FCFS is the simplest of all Disk Scheduling Algorithms. In the first-come, first-served (FCFS) algorithm,
requests are processed in the order that they arrive.

Example:

Suppose the order of request is- (82,170, 43, 140, 24, 16,190)

And current position of Read/Write head is: 50

So, total overhead movement = (82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16) =642

2. SSTF (Shortest Seek Time First)

In SSTF (Shortest Seek Time First), requests having the shortest seek time are executed first. So, the seek
time of every request is calculated in advance in the queue and then they are scheduled according to their
calculated seek time. As a result, the request near the disk arm will get executed first.

Suppose the order of request are (82,170, 43, 140, 24, 16,190)

And current position of Read/Write head is: 50

total overhead movement =(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170) =208

SCAN:

In SCAN algorithm the disk arm moves into a particular direction and services the requests coming in its
path and after reaching the end of disk, it reverses its direction and again services the request arriving in
its path. So, this algorithm works like an elevator and hence also known as elevator algorithm.

Suppose the requests to be addressed are 82,170,43,140,24,16,190. And the Read/Write arm is at 50,
and it is also given that the disk arm should move “towards the larger value”.

Therefore, the total overhead movement is calculated as

= (199-50) + (199-16) = 332

C-SCAN: ( Circular –SCAN)

In circular SCAN algorithm, when the edge of the disc is reached, it returns to the opposite edge without
dealing with any requests, and then starts again from there. This provides a slight speedup over the SCAN
algorithm.
Suppose the requests to be addressed are: 82,170,43,140,24,16,190. And the Read/Write arm is at 50,
and it is also given that the disk arm should move “towards the larger value”.

So, the total overhead movement is calculated as:

= (199-50) + (199-0) + (43-0) = 391

LOOK

The LOOK disk scheduling algorithm is indeed similar to the SCAN algorithm. The disk arm moves in one
direction, servicing all pending requests until it reaches the last request in that direction. Once it reaches
the last request, it reverses direction and services requests in the opposite direction, again stopping at
the last request in that path.

Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50,
and it is also given that the disk arm should move “towards the larger value”.

So, the total overhead movement is calculated as:

= (190-50) + (190-16) = 314

C-LOOK

CLOOK is similar to CSCAN disk scheduling algorithm. In C-Look, The arm moves in one direction, servicing
requests up to the last request in that direction. Once it reaches the last request, it immediately jumps
back to the first request in the opposite direction without servicing requests along the way. It then
continues servicing requests in the same initial direction.
Suppose the requests to be addressed are 82,170,43,140,24,16,190. And the Read/Write arm is at 50,
and it is also given that the disk arm should move “towards the larger value”

So, the total overhead movement (total distance covered by the disk arm) is calculated as = (190-50) +
(190-16) + (43-16) = 341