Elevator algorithm

Last updated September 30, 2023

The elevator algorithm, or SCAN, is a disk-scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests.

From an implementation perspective, the drive maintains a buffer of pending read/write requests, along with the associated cylinder number of the request, in which lower cylinder numbers generally indicate that the cylinder is closer to the spindle, and higher numbers indicate the cylinder is farther away.

Description

When a new request arrives while the drive is idle, the initial arm/head movement will be in the direction of the cylinder where the data is stored, either in or out. As additional requests arrive, requests are serviced only in the current direction of arm movement until the arm reaches the edge of the disk. When this happens, the direction of the arm reverses, and the requests that were remaining in the opposite direction are serviced, and so on.^[1]

Variations

One variation of this method ensures all requests are serviced in only one direction, that is, once the head has arrived at the outer edge of the disk, it returns to the beginning and services the new requests in this one direction only (or vice versa). This is known as the "Circular Elevator Algorithm" or C-SCAN. Although the time of the return seek is wasted, this results in more equal performance for all head positions, as the expected distance from the head is always half the maximum distance, unlike in the standard elevator algorithm where cylinders in the middle will be serviced as much as twice as often as the innermost or outermost cylinders.

Other variations include:

	SCAN	LOOK	C-SCAN	C-LOOK
Repeated Motion	Goes to the last track (whether requested or not), then reverses direction and goes to the first track.	Only goes as far as the final request in that direction, then reverses direction.	Goes to the last track, then jumps to the first track and continues in the same direction.	Only goes as far as the final request, then jumps to the first request and continues in the same direction.

Example

The following is an example of how to calculate average disk seek times for both the SCAN and C-SCAN algorithms.

Example list of pending disk requests (listed by track number): 100, 50, 10, 20, 75.
The starting track number for the examples will be 35.
The list will need to be sorted in ascending order: 10, 20, 50, 75, 100.

Both SCAN and C-SCAN behave in the same manner until they reach the last track queued. For the sake of this example let us assume that the SCAN algorithm is currently going from a lower track number to a higher track number (like the C-SCAN is doing). For both methods, one takes the difference in magnitude (i.e. absolute value) between the next track request and the current track.

Seek 1: 50 − 35 = 15
Seek 2: 75 − 50 = 25
Seek 3: 100 − 75 = 25

At this point both have reached the highest (end) track request. SCAN will just reverse direction and service the next closest disk request (in this example, 20) and C-SCAN will always go back to track 0 and start going to higher track requests.

Seek 4 (SCAN): 20 − 100 = 80
Seek 5 (SCAN): 10 − 20 = 10
Total (SCAN): 155
Average (SCAN): 155 ÷ 5 = 31
Seek 4 (C-SCAN): 0 − 100 = 0 head movement as cylinders are treated as a circular list (C-SCAN always goes back to the first track)
Seek 5 (C-SCAN): 10 − 0 = 10
Seek 6 (C-SCAN): 20 − 10 = 10
Total (C-SCAN): 85
Average (C-SCAN): 85 ÷ 5 = 17

Even though six seeks were performed using the C-SCAN algorithm, only five I/Os were actually done.

Analysis

For both versions of the elevator algorithm, the arm movement is less than twice the number of total cylinders and produces a smaller variance in response time. The algorithm is also relatively simple.

The elevator algorithm is not always better than shortest seek first, which is slightly closer to optimal, but can result in high variance in response time and even in starvation when new requests continually get serviced prior to existing requests. Anti-starvation techniques can be applied to the shortest seek time first algorithm to guarantee a maximum response time.

Related Research Articles

A hard disk drive (HDD), hard disk, hard drive, or fixed disk, is an electro-mechanical data storage device that stores and retrieves digital data using magnetic storage with one or more rigid rapidly rotating platters coated with magnetic material. The platters are paired with magnetic heads, usually arranged on a moving actuator arm, which read and write data to the platter surfaces. Data is accessed in a random-access manner, meaning that individual blocks of data can be stored and retrieved in any order. HDDs are a type of non-volatile storage, retaining stored data when powered off. Modern HDDs are typically in the form of a small rectangular box.

<span class="mw-page-title-main">Tower of Hanoi</span> Mathematical game or puzzle

The Tower of Hanoi is a mathematical game or puzzle consisting of three rods and a number of disks of various diameters, which can slide onto any rod. The puzzle begins with the disks stacked on one rod in order of decreasing size, the smallest at the top, thus approximating a conical shape. The objective of the puzzle is to move the entire stack to the last rod, obeying the following rules:

Only one disk may be moved at a time.
Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
No disk may be placed on top of a disk that is smaller than it.

In computing, scheduling is the action of assigning resources to perform tasks. The resources may be processors, network links or expansion cards. The tasks may be threads, processes or data flows.

<span class="mw-page-title-main">Defragmentation</span> Rearrangement of sectors on a hard disk into contiguous units

In the maintenance of file systems, defragmentation is a process that reduces the degree of fragmentation. It does this by physically organizing the contents of the mass storage device used to store files into the smallest number of contiguous regions. It also attempts to create larger regions of free space using compaction to impede the return of fragmentation. Some defragmentation utilities try to keep smaller files within a single directory together, as they are often accessed in sequence.

TRSDOS is the operating system for the Tandy TRS-80 line of eight-bit Zilog Z80 microcomputers that were sold through Radio Shack from 1977 through 1991. Tandy's manuals recommended that it be pronounced triss-doss. TRSDOS should not be confused with Tandy DOS, a version of MS-DOS licensed from Microsoft for Tandy's x86 line of personal computers (PCs).

IBM manufactured magnetic disk storage devices from 1956 to 2003, when it sold its hard disk drive business to Hitachi. Both the hard disk drive (HDD) and floppy disk drive (FDD) were invented by IBM and as such IBM's employees were responsible for many of the innovations in these products and their technologies. The basic mechanical arrangement of hard disk drives has not changed since the IBM 1301. Disk drive performance and characteristics are measured by the same standards now as they were in the 1950s. Few products in history have enjoyed such spectacular declines in cost and physical size along with equally dramatic improvements in capacity and performance.

Shortest seek first is a secondary storage scheduling algorithm to determine the motion of the disk read-and-write head in servicing read and write requests.

The IBM 3850 Mass Storage System (MSS) was an online tape library used to hold large amounts of infrequently accessed data. It was one of the earliest examples of nearline storage.

Infrared homing is a passive weapon guidance system which uses the infrared (IR) light emission from a target to track and follow it seamlessly. Missiles which use infrared seeking are often referred to as "heat-seekers" since infrared is radiated strongly by hot bodies. Many objects such as people, vehicle engines and aircraft generate and emit heat and so are especially visible in the infrared wavelengths of light compared to objects in the background.

Query optimization is a feature of many relational database management systems and other databases such as NoSQL and graph databases. The query optimizer attempts to determine the most efficient way to execute a given query by considering the possible query plans.

Tagged Command Queuing (TCQ) is a technology built into certain ATA and SCSI hard drives. It allows the operating system to send multiple read and write requests to a hard drive. ATA TCQ is not identical in function to the more efficient Native Command Queuing (NCQ) used by SATA drives. SCSI TCQ does not suffer from the same limitations as ATA TCQ.

FSCAN is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. It uses two sub-queues. During the scan, all of the requests are in the first queue and all new requests are put into the second queue. Thus, service of new requests is deferred until all of the old requests have been processed. When the scan ends, the arm is taken to the first queue entries and is started all over again.

N-Step-SCAN is a disk scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. It segments the request queue into subqueues of length N. Breaking the queue into segments of N requests makes service guarantees possible. Subsequent requests entering the request queue won't get pushed into N sized subqueues which are already full by the elevator algorithm. As such, starvation is eliminated and guarantees of service within N requests is possible.

Count key data (CKD) is a direct-access storage device (DASD) data recording format introduced in 1964, by IBM with its IBM System/360 and still being emulated on IBM mainframes. It is a self-defining format with each data record represented by a Count Area that identifies the record and provides the number of bytes in an optional Key Area and an optional Data Area. This is in contrast to devices using fixed sector size or a separate format track.

Input/output (I/O) scheduling is the method that computer operating systems use to decide in which order I/O operations will be submitted to storage volumes. I/O scheduling is sometimes called disk scheduling.

LOOK is a hard disk scheduling algorithm used to determine the order in which new disk read and write requests are processed.

An elevator or lift is a machine that vertically transports people or freight between levels. They are typically powered by electric motors that drive traction cables and counterweight systems such as a hoist, although some pump hydraulic fluid to raise a cylindrical piston like a jack.

The Independent Reference Model (I.R.M) is a conceptual model used in the analysis of storage system: disk drives, caches, etc.

Higher performance in hard disk drives comes from devices which have better performance characteristics. These performance characteristics can be grouped into two categories: access time and data transfer time.

The Commodore D9060/D9090 Hard Disks were the only family of hard drives that Commodore made for both the home and business market. The electronics are identical in the D9060 and the larger D9090 unit; the only difference is the size of the installed hard drive, with a jumper set to distinguish between 4 or 6 disk heads. Originally intended for the metal-cased PET/CBM series of computers, they are compatible with the VIC-20, Commodore 64 and later models with an adapter.

References

↑ "Disk scheduling". Archived from the original on 2008-06-06. Retrieved 2008-01-21.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] "Disk scheduling". Archived from the original on 2008-06-06. Retrieved 2008-01-21.

[1]