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.
This algorithm is named after the behavior of a building elevator, where the elevator continues to travel in its current direction (up or down) until empty, stopping only to let individuals off or to pick up new individuals heading in the same direction.
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.
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.
The scan algorithm (often known as prefix sum algorithm) is commonly used in computer science for problems that involve computing the cumulative sum or the cumulative result of a series of elements in an array or list. It operates by iterating through the list and maintaining an accumulated result up to the current element, and can be used in various scenarios such as parallel computation, reducing operations, or processing large data efficiently.
Here’s a real-world example where the scan algorithm is applied:
Example: Real-Time Data Processing in Stock Market Analysis Imagine a financial trading application that tracks the price changes of a stock over time and calculates the cumulative value or gain/loss of the stock at any given moment.
Scenario: You have a list of daily stock price changes (positive or negative values) for a particular stock over a period of days. The scan algorithm can be used to calculate the cumulative gain or loss at each day, showing the total change in stock price from the start up to that day.
Input data: A list of daily stock price changes:
csharp Copy code [10, -5, 3, 7, -2] Where:
10 represents a gain of $10 on day 1, -5 represents a loss of $5 on day 2, 3 represents a gain of $3 on day 3, 7 represents a gain of $7 on day 4, -2 represents a loss of $2 on day 5. Step-by-Step Execution (Scan Algorithm):
Start with an initial cumulative sum of 0. For each subsequent day, add the day's change to the cumulative sum: Day 1: 0 + 10 = 10 (Total gain so far: $10) Day 2: 10 + (-5) = 5 (Total gain so far: $5) Day 3: 5 + 3 = 8 (Total gain so far: $8) Day 4: 8 + 7 = 15 (Total gain so far: $15) Day 5: 15 + (-2) = 13 (Total gain so far: $13) Output: The cumulative gains after each day:
csharp Copy code [10, 5, 8, 15, 13] This cumulative list shows how the stock has performed in terms of total gain/loss at each day in the period. By using the scan algorithm, you efficiently compute these cumulative results in a single pass over the data.
Parallelism and Optimization: In a real-world application where the data set is large (e.g., tracking stock prices across thousands of days for multiple stocks), this scan algorithm can be parallelized to run faster. For example, using techniques like parallel prefix sum (where the input array is divided into chunks, processed in parallel, and then merged), large-scale data can be processed much more efficiently.
Use Cases Beyond Stock Market Analysis: Image Processing: Cumulative operations (like pixel intensities) for tasks such as convolution or blur filters. Distributed Systems: Aggregating values across multiple nodes to compute cumulative statistics. Database Systems: Efficiently computing running totals in financial applications or analytics. The scan algorithm is essential in scenarios where you need to process or aggregate data in a way that builds on prior computations, and its parallel implementation helps in scaling up for larger datasets.
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.
In computing, a cache is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewhere. A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot. Cache hits are served by reading data from the cache, which is faster than recomputing a result or reading from a slower data store; thus, the more requests that can be served from the cache, the faster the system performs.
A fast Fourier transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse factors. As a result, it manages to reduce the complexity of computing the DFT from , which arises if one simply applies the definition of DFT, to , where n is the data size. The difference in speed can be enormous, especially for long data sets where n may be in the thousands or millions. In the presence of round-off error, many FFT algorithms are much more accurate than evaluating the DFT definition directly or indirectly. There are many different FFT algorithms based on a wide range of published theories, from simple complex-number arithmetic to group theory and number theory.
In computing, load balancing is the process of distributing a set of tasks over a set of resources, with the aim of making their overall processing more efficient. Load balancing can optimize response time and avoid unevenly overloading some compute nodes while other compute nodes are left idle.
In computer science, algorithmic efficiency is a property of an algorithm which relates to the amount of computational resources used by the algorithm. Algorithmic efficiency can be thought of as analogous to engineering productivity for a repeating or continuous process.
In computer operating systems, memory paging is a memory management scheme by which a computer stores and retrieves data from secondary storage for use in main memory. In this scheme, the operating system retrieves data from secondary storage in same-size blocks called pages. Paging is an important part of virtual memory implementations in modern operating systems, using secondary storage to let programs exceed the size of available physical memory.
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.
General-purpose computing on graphics processing units is the use of a graphics processing unit (GPU), which typically handles computation only for computer graphics, to perform computation in applications traditionally handled by the central processing unit (CPU). The use of multiple video cards in one computer, or large numbers of graphics chips, further parallelizes the already parallel nature of graphics processing.
MapReduce is a programming model and an associated implementation for processing and generating big data sets with a parallel and distributed algorithm on a cluster.
In computing, a benchmark is the act of running a computer program, a set of programs, or other operations, in order to assess the relative performance of an object, normally by running a number of standard tests and trials against it.
Replication in computing involves sharing information so as to ensure consistency between redundant resources, such as software or hardware components, to improve reliability, fault-tolerance, or accessibility.
In computer science, stream processing is a programming paradigm which views streams, or sequences of events in time, as the central input and output objects of computation. Stream processing encompasses dataflow programming, reactive programming, and distributed data processing. Stream processing systems aim to expose parallel processing for data streams and rely on streaming algorithms for efficient implementation. The software stack for these systems includes components such as programming models and query languages, for expressing computation; stream management systems, for distribution and scheduling; and hardware components for acceleration including floating-point units, graphics processing units, and field-programmable gate arrays.
In parallel algorithms, the list ranking problem involves determining the position, or rank, of each item in a linked list. That is, the first item in the list should be assigned the number 1, the second item in the list should be assigned the number 2, etc. Although it is straightforward to solve this problem efficiently on a sequential computer, by traversing the list in order, it is more complicated to solve in parallel. As Anderson & Miller (1990) wrote, the problem was viewed as important in the parallel algorithms community both for its many applications and because solving it led to many important ideas that could be applied in parallel algorithms more generally.
In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes of the input sequence:
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 will not 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.
In computer storage, the standard RAID levels comprise a basic set of RAID configurations that employ the techniques of striping, mirroring, or parity to create large reliable data stores from multiple general-purpose computer hard disk drives (HDDs). The most common types are RAID 0 (striping), RAID 1 (mirroring) and its variants, RAID 5, and RAID 6. Multiple RAID levels can also be combined or nested, for instance RAID 10 or RAID 01. RAID levels and their associated data formats are standardized by the Storage Networking Industry Association (SNIA) in the Common RAID Disk Drive Format (DDF) standard. The numerical values only serve as identifiers and do not signify performance, reliability, generation, hierarchy, or any other metric.
Data parallelism is parallelization across multiple processors in parallel computing environments. It focuses on distributing the data across different nodes, which operate on the data in parallel. It can be applied on regular data structures like arrays and matrices by working on each element in parallel. It contrasts to task parallelism as another form of parallelism.
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.
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 .
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.
