Directory and Disk Structure

Directory and Disk Structure in Operating Systems

In an operating system, directories and disk structure play essential roles in organizing and managing data storage. They define how files are stored, accessed, and maintained on disk storage devices like hard drives, SSDs, or optical disks. Let's look at these concepts in detail.

Directory Structure

A directory is a specialized file that contains information about other files. The directory structure provides a way to organize and manage files on a disk. It acts as a table of contents for the files stored on the system, helping users and programs locate files quickly.

Types of Directory Structures

1. Single-Level Directory:

   • In a single-level directory, all files are stored in one central directory. This structure is very simple, but it has limitations, particularly when the number of files grows. There’s no way to organize files into subcategories.
   • Advantages: Simple to implement and manage.
   • Disadvantages: As the number of files increases, it becomes difficult to manage and access files due to name conflicts (i.e., different files can't have the same name) and lack of organization.

2. Two-Level Directory:

   • A two-level directory allows the creation of a master directory that contains directories for each user. Each user directory contains the files belonging to that user. This structure organizes files by user, making it easier to manage access and prevent name conflicts.
   • Advantages: More organized than the single-level directory and helps avoid name conflicts between different users.
   • Disadvantages: Still lacks hierarchical file organization.

3. Tree-Structured Directory:

   • A tree-structured directory allows for the creation of subdirectories, forming a tree-like structure where each directory can contain files or other directories. This structure is the most commonly used, as it provides both hierarchy and flexibility in organizing files.
   • Advantages: Highly organized, allows hierarchical organization of files and directories, and enables easy file access and management.
   • Disadvantages: Can become complex to navigate with deeply nested directories, especially in large systems.

4. Acyclic Graph Directory Structure:

   • An acyclic graph directory allows files and directories to be shared. A directory can contain links to files or directories in other locations, forming a graph. While the structure is hierarchical, it also supports non-hierarchical relationships through shared links.
   • Advantages: Allows for file sharing between different directories, reducing data duplication.
   • Disadvantages: More complex to implement and manage, and can lead to issues like circular references if not carefully handled.

5. General Graph Directory Structure:

   • A general graph directory structure allows directories to have links to each other, potentially forming cycles. While this structure is flexible, it can be complex and prone to confusion without careful management.
   • Advantages: Allows maximum flexibility in organizing files and directories.
   • Disadvantages: Can result in complicated relationships and potential issues with file access.

Directory Operations

1. File Creation:

   • When a file is created, the operating system places it in the appropriate directory and updates the directory structure to include an entry for the new file.

2. File Deletion:

   • When a file is deleted, the operating system removes the file's entry from the directory and marks the space occupied by the file as free.

3. File Lookup:

   • When accessing a file, the operating system traverses the directory structure (from the root to the relevant directory) to locate the file.

4. Directory Navigation:

   • Users or processes can navigate through the directory structure using commands (like cd in UNIX-like systems) to access specific files or subdirectories.

5. Renaming Files:

   • Files can be renamed by changing the file’s entry in the directory structure.

6. Listing Directory Contents:

   • A directory can be listed to show all the files and subdirectories it contains. This helps users or programs view and manage the contents.

Disk Structure

The disk structure refers to how data is physically stored on a disk, including how it is organized into blocks or sectors. It includes both the logical structure (the way data is represented in the file system) and the physical structure (how data is stored on the disk).

Components of Disk Structure

1. Disk Blocks/Clusters:

   • The disk is divided into fixed-size units called blocks (or clusters in some file systems). Each block is the smallest unit of storage that can be allocated to a file.
   • Block sizes typically range from 512 bytes to several kilobytes, depending on the file system and the disk type.

2. Disk Sectors:

   • A sector is a subunit of a disk block, usually 512 bytes in size. The operating system handles data in terms of disk blocks, but data is physically organized in sectors.

3. Cylinder:

   • A cylinder is a set of tracks (one per platter surface) that are vertically aligned across multiple disk platters. Disk heads can access data within a cylinder without having to move the arm.

4. Track:

   • A track is a circular path on the disk surface where data is stored. Tracks are concentric circles on the disk platters, and the data is written along these tracks. Each platter typically has several tracks.

5. Surface:

   • A surface is one side of a disk platter. Most modern hard disks use multiple platters, and each platter has two surfaces (top and bottom) for data storage.

6. Cylinder-Head-Sector (CHS) Addressing:

   • CHS is an old method of addressing data on the disk, which specifies the location of a block using three parameters: the cylinder number, the head (surface) number, and the sector number within the track.

Disk Allocation Methods

1. Contiguous Allocation:

   • In contiguous allocation, each file is stored as a single contiguous block of data on the disk. All file blocks are stored next to each other in consecutive disk sectors.
   • Advantages: Simple to implement, fast access (since the file’s blocks are physically adjacent).
   • Disadvantages: Leads to disk fragmentation as files are created and deleted over time, making it difficult to allocate contiguous space for new files.

2. Linked Allocation:

   • In linked allocation, each file consists of blocks that are scattered across the disk. Each block contains a pointer to the next block in the file. The blocks are not stored contiguously but are linked together via these pointers.
   • Advantages: Eliminates fragmentation, as blocks can be scattered across the disk.
   • Disadvantages: Slower access time because blocks are not contiguous, and the system has to follow pointers to access the next block.

3. Indexed Allocation:

   • In indexed allocation, an index block is used to store pointers to the data blocks of a file. The index block is stored at a known location, and it maps to all the blocks of the file.
   • Advantages: Provides direct access to any block of the file, eliminating the need to follow a chain of pointers (as in linked allocation).
   • Disadvantages: Requires extra space for the index block, and the index itself can become fragmented if the file is large.

4. Multi-Level Index Allocation:

   • Multi-level indexing is used when the index for a file is too large to fit in a single block. This method uses multiple levels of indexing to point to the file’s data blocks, similar to how a page table works in memory management.
   • Advantages: Handles large files efficiently.
   • Disadvantages: Involves additional complexity and overhead in managing multiple levels of indexing.

Disk Scheduling

Disk scheduling refers to the way the operating system orders the requests for disk access to optimize performance. Several algorithms are used for disk scheduling, including:

1. First-Come-First-Served (FCFS):

   • This is the simplest disk scheduling algorithm where disk requests are processed in the order in which they arrive.

2. Shortest Seek Time First (SSTF):

   • In SSTF, the disk scheduler selects the request that is closest to the current head position. This minimizes the seek time.

3. SCAN and C-SCAN:

   • In SCAN, the disk arm moves in one direction (either from the outermost track to the innermost track or vice versa), servicing requests until the end is reached, after which it reverses direction.
   • C-SCAN is a variation where the arm moves in one direction and, upon reaching the end, jumps back to the beginning to continue servicing requests in the same direction.

4. LOOK and C-LOOK:

   • These are variations of SCAN and C-SCAN that optimize seek times by stopping when the last request is serviced, rather than continuing to the end of the disk.

Conclusion

The directory structure is a vital part of the file system, organizing files into directories and subdirectories, making it easier to manage and access files. The disk structure is the physical layout of data on a storage device, and it includes disk blocks, sectors, tracks, and cylinders. Efficient directory and disk structures, combined with effective disk allocation and scheduling methods, are essential for the optimal performance of storage systems.