Disk Structure and Scheduling

Disk Structure and Scheduling in Operating Systems

In an operating system, managing disk storage is essential for storing data in a non-volatile manner. Disk scheduling and understanding the structure of the disk are crucial for optimizing read and write operations to improve the overall system performance. Let's break down these concepts in detail:

Disk Structure

Modern disks are typically hard disk drives (HDDs) or solid-state drives (SSDs), with distinct differences in structure and operation. Disk structure refers to the physical and logical organization of data on the disk. Here's how it's structured:

1. Physical Disk Structure (For HDDs):

   • Tracks: A track is a circular path on the disk's surface where data is stored. Each disk platter (disk surface) is divided into concentric tracks.

   • Sectors: A sector is the smallest unit of storage on a disk. Each track is divided into a number of sectors, typically 512 bytes or 4 KB in size.

   • Cylinders: A cylinder is a set of tracks at the same position on each platter. All the tracks aligned vertically across multiple platters form a cylinder.

   • Disk Platters: Disks consist of multiple platters (disk surfaces), and each platter can have a read/write head to access data. Multiple platters stack together to form a disk unit.

   • Heads: The heads are responsible for reading from and writing to the disk. The read/write heads move across the platters to access data.

   • Seek Time: The time it takes for the read/write head to move to the correct track.

   • Rotational Latency: The time it takes for the desired disk sector to rotate under the read/write head.

   • Transfer Time: The time it takes to transfer data once the head is positioned correctly on the correct sector.

2. Logical Disk Structure:

   • Logical Block Addressing (LBA): In modern systems, disk blocks are abstracted and managed using logical block addressing. It allows the operating system to treat the disk as a flat linear address space rather than dealing with tracks and sectors.
   • File System: The logical structure of the disk is managed by a file system (e.g., NTFS, ext4, FAT). The file system keeps track of file metadata (such as names, sizes, and locations) and organizes data on the disk.

Disk Scheduling

Disk scheduling refers to the techniques used to decide the order in which disk I/O requests are serviced. Since disk operations, especially on HDDs, are much slower compared to memory accesses, an effective disk scheduling algorithm helps minimize the latency in data retrieval.

Types of Disk Scheduling Algorithms

Here are the common algorithms used for disk scheduling:

1. First Come First Serve (FCFS):

   • Description: In FCFS, disk requests are serviced in the order they arrive in the queue.
   • Advantages: Simple and fair.
   • Disadvantages: It can lead to inefficient utilization of the disk, especially if requests are scattered across different parts of the disk, resulting in high seek time and rotational latency.

   Example:

   • Disk requests are made for cylinders 10, 15, 20, 5, and 30. FCFS would service them in the order 10 → 15 → 20 → 5 → 30.

2. Shortest Seek Time First (SSTF):

   • Description: SSTF selects the disk request that is closest to the current position of the disk’s head, minimizing the seek time.
   • Advantages: Reduces seek time compared to FCFS.
   • Disadvantages: Can lead to starvation (where some requests may never be serviced if closer requests keep coming). It doesn't guarantee fair access to all requests.

   Example:

   • If the current position of the disk head is 10, and the requests are for cylinders 15, 20, 5, and 30, SSTF will first serve the request for cylinder 5, then 15, 20, and 30, in that order.

3. SCAN (Elevator Algorithm):

   • Description: The disk arm moves in one direction, serving all requests in that direction. Once it reaches the end, it reverses direction and starts servicing requests in the opposite direction. It’s like an elevator that moves up and down.
   • Advantages: It avoids the problem of starvation and reduces the seek time by sweeping across the disk.
   • Disadvantages: It can be inefficient if requests are clustered near the ends of the disk, as the head may travel unnecessarily long distances.

   Example:

   • If the disk head starts at cylinder 15 and requests are for cylinders 5, 20, 10, and 30, SCAN will first serve requests 5 and 10 as it moves towards the beginning of the disk, then reverse and service requests 20 and 30.

4. C-SCAN (Circular SCAN):

   • Description: C-SCAN is similar to SCAN, but instead of reversing direction when it reaches the end, the head quickly returns to the starting position and starts scanning in the same direction again.
   • Advantages: Provides more uniform wait times compared to SCAN and prevents the long wait times that occur when requests are at the end of the disk.
   • Disadvantages: It may still have a high seek time in some cases, especially when requests are clustered near the start or end.

   Example:

   • If the head is at cylinder 15 and requests are for 5, 20, 10, and 30, C-SCAN will serve the requests in the order: 5 → 10 → 20 → 30, and then the head will return to the beginning (usually cylinder 0) and continue scanning.

5. LOOK:

   • Description: LOOK is a modification of SCAN. In LOOK, the disk head only moves as far as the last request in the current direction. It does not continue until the end of the disk, thus reducing unnecessary movements.
   • Advantages: Reduces unnecessary travel compared to SCAN.
   • Disadvantages: It can still result in unbalanced waiting times if requests are concentrated at one end of the disk.

   Example:

   • If the current position is at cylinder 15 and requests are for cylinders 5, 20, 10, and 30, LOOK will first serve requests 5 and 10 (moving towards the beginning), and then reverse direction and service requests 20 and 30.

6. N-Step-SCAN:

   • Description: N-Step-SCAN divides the requests into smaller groups and processes each group in a single sweep of the disk. The remaining requests wait for the next cycle.
   • Advantages: It limits the number of requests that the disk head needs to handle at any given time, which can help balance the workload and reduce waiting times.
   • Disadvantages: Dividing the requests into batches may delay some requests unnecessarily.

Disk Scheduling Considerations

1. Seek Time:

   • Seek time is the time taken by the disk's read/write head to move to the location of the data to be accessed. The goal of disk scheduling algorithms is to reduce seek time by minimizing head movements.

2. Rotational Latency:

   • Rotational latency refers to the delay caused by the disk's rotation before the desired sector is under the read/write head. Scheduling algorithms attempt to minimize rotational latency as well.

3. Fairness:

   • A good disk scheduling algorithm should strive to treat all requests fairly, preventing starvation, where certain requests might never be served.

4. Throughput:

   • Throughput is the number of disk I/O operations completed in a given period. The more efficient the disk scheduling, the higher the throughput.

Conclusion

Disk structure and disk scheduling are crucial components of operating system performance. Disk structure determines how data is physically and logically organized on a disk, while disk scheduling algorithms optimize the order of I/O requests to minimize time-consuming operations like seek time and rotational latency. Understanding and implementing efficient disk scheduling can greatly improve the performance and responsiveness of systems that rely heavily on disk I/O operations.