An introduction to secondary storage and disk scheduling techniques.

Overview of Mass Storage Structure

secondary storage:

• HDDs: hard disk drives
• NVM: nonvolatile memory

HDD

A disk drive is treated as a large one-dimensional array of logical blocks, where the logical block is the smallest unit of data transfer. Low-level formatting creates the logical blocks on the physical medium, and these logical blocks are mapped sequentially onto the sectors of the disk.

Mapping order: the mapping proceeds in order through the sectors of a track, then through the remaining tracks of that cylinder, and finally through the remaining cylinders from the outermost to the innermost.

Bad sectors exist and are unusable

Average access time = average seek time + average latency

In disk I/O operations, the calculation of rotational delay is related to the disk’s rotation rate. The formula is:

$$Avg. rotational delay = \frac{1}{2} \times \frac{60}{rotation\ rate}$$

where rotation rate is the number of revolutions per minute (RPM, Revolutions Per Minute). This is because the disk rotates at a constant speed, and on average the time spent waiting for the data to arrive under the head is the time for half a rotation of the disk

Average I/O time = average access time + (amount to transfer / transfer rate) + controller overhead

Influencing factors: transfer rate, seek time, latency

NVM

Volatile Memory

• Volatile memory mainly refers to DRAM (dynamic random-access memory), whose defining characteristic is that the stored data is lost when power is cut. Technically it is not secondary storage in the strict sense, but in practice it is often used as a high-speed secondary storage device.
• Form of use: it usually appears in the form of a RAM drive. Such drives are treated as raw block devices and are generally formatted with a file system. They appear in many mainstream operating systems: for example, on Linux it corresponds to /dev/ram, on macOS it can be created with the diskutil command, and Linux’s /tmp file system of type tmpfs is also based on this principle. This lets users use standard file operations to store data temporarily in memory while keeping the data safe.
• Performance advantage: for operations such as creating, reading, writing and deleting files and their contents, I/O on a RAM drive is the fastest possible way. This gives it a huge advantage in scenarios that need high-speed temporary storage; for instance, when handling temporary data with extremely demanding read/write speed requirements, volatile memory can significantly improve processing efficiency.

Disk attachment

• Attached directly to the host
• Attached to the host over a network
• Cloud storage

Disk Scheduling

Disk I/O requests come from many sources, including the operating system, system processes and user processes. The operating system maintains a request queue for each disk or device. When the disk is idle, an I/O request can be serviced; if the disk is busy, new requests must wait in the queue.

The main goal of disk scheduling is to minimize seek time, because seek time accounts for a large share of disk access time, and reducing it can significantly improve disk performance. Rotational latency is hard for the operating system to compute precisely, so disk scheduling algorithms mainly optimize for seek time.

Scheduling Algorithms

• First-Come, First-Served (FCFS) Scheduling
• Shortest Seek Time First (SSTF) Scheduling
• SCAN Scheduling: move toward one end first, then reverse direction on arrival
• C-SCAN Scheduling: move toward one end first, then jump directly to the other end on arrival, which distributes seek time more evenly
• LOOK/C-LOOK Scheduling: an improvement on the two algorithms above; instead of moving all the way to the end, the head only moves to the track of the last request
• NVM Scheduling: NVM devices attached directly to the host usually need no scheduling, because they have no seek time or rotational delay
  • Pass-through scheduling
  • Write coalescing

Storage Device and Swap Space Management

Storage Device Management

• Low-level formatting / physical formatting: divide the disk into sectors, usually 512 bytes
• High-level formatting / logical formatting: create the file system, create the directory structure and the file allocation table. Disk I/O is done in units of blocks, file I/O in units of clusters

Root partition: holds the operating system, mounted at the root directory when the system boots

Mounting: integrating a storage device into the operating system’s file system directory structure, so that users and applications can operate on the data in the storage device as if accessing local files.

Boot block: the boot block is the first sector, or a sector at a specific location, on the storage device, and contains the initial program code needed to boot the computer

Swap-Space Management

When memory is insufficient, the operating system moves part of the memory contents to a swap space on disk, freeing memory for other processes to use. The swap space can be a dedicated partition or a file.

Storage Attachment

Host-Attached

The computer connects to storage devices through local I/O ports; if multiple storage devices need to be attached, storage buses can be used. High-end systems use Fibre Channel (FC, Fiber Channel) technology.

Network-Attached

• Definition and concept: NAS is a technology that lets storage devices provide storage services over a network rather than through a local connection (such as a bus). It allows file systems to be mounted remotely, so that multiple clients can access the files and data on the storage device over the network.
• Implementation protocols: common protocols are NFS (Network File System) and CIFS (Common Internet File System), which use remote procedure calls (RPC) to implement communication between hosts and storage devices over IP networks, usually transferring data over TCP or UDP. In addition, the iSCSI protocol carries the SCSI protocol over IP networks, making the network the means of connection between hosts and storage devices.
• Connection method: unlike the traditional approach of connecting hosts and storage devices with SCSI cables, network-attached storage uses the network as the interconnect between hosts and storage devices. Clients connect to the NAS device over a LAN (local area network) or WAN (wide area network) to access the storage resources.

Cloud Storage

1. Basic concept of cloud storage: cloud storage is similar to NAS in that both let users access storage resources over a network. But cloud storage accesses storage in a remote data center over the Internet or a wide area network (WAN), rather than over a local area network as NAS does. For example, when users use cloud storage services such as Dropbox, Microsoft OneDrive, Apple iCloud and Shanghai Jiao Tong University’s Jbox, the data is stored on servers in remote data centers, and users store and read data over the network.
2. Difference between cloud storage and NAS: NAS presents itself as an ordinary file system, which users can operate on just like a local file system. Cloud storage, on the other hand, provides its service through APIs (application programming interfaces), and applications access cloud storage by calling these APIs. This is because cloud storage faces a far more complex network environment, with higher latency and possible failures, which traditional NAS protocols cannot cope with well, so APIs are used to ensure reliable data transfer and access.

RAID Structure

Redundant Arrays of Independent Disks (RAIDs) combine multiple independent physical disks into a single logical disk unit to improve the performance, reliability and data redundancy of the storage system. The common structure levels are as follows:

---

Translated from the Chinese original.