Elevator algorithm - Revision history

Okterakt: Revert edit by User:13vishalyadav (talk). Contains unrelated information and is possibly a WP:COPYVIO. Related talk topic: User talk:13vishalyadav#Elevator_algorithm

2025-05-13T12:38:55Z

Revert edit by User:13vishalyadav (talk). Contains unrelated information and is possibly a WP:COPYVIO. Related talk topic: User talk:13vishalyadav#Elevator_algorithm

← Previous revision		Revision as of 12:38, 13 May 2025
Line 60:		Line 60:

	Even though six seeks were performed using the C-SCAN algorithm, only five I/Os were actually done.		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 ==		== Analysis ==

Amitosh.swain: /* Example */ Removed out of context link

2025-01-24T07:28:38Z

Example: Removed out of context link

← Previous revision		Revision as of 07:28, 24 January 2025
Line 63:		Line 63:
	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.		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 ~~[https://examrevisor.com/what-is-scan-algorithm-in-hindi/~~ scan algorithm] is applied:		Here’s a real-world example where the scan algorithm is applied:

	Example: Real-Time Data Processing in Stock Market Analysis		Example: Real-Time Data Processing in Stock Market Analysis

13vishalyadav: /* Example */

2024-11-27T16:36:23Z

Example

← Previous revision		Revision as of 16:36, 27 November 2024
Line 60:		Line 60:

	Even though six seeks were performed using the C-SCAN algorithm, only five I/Os were actually done.		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 [https://examrevisor.com/what-is-scan-algorithm-in-hindi/ 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 ==		== Analysis ==

Jarfuls of Tweed: /* Variations */ Fixed false claims and made descriptions more clear

2023-09-29T18:30:16Z

Variations: Fixed false claims and made descriptions more clear

← Previous revision		Revision as of 18:30, 29 September 2023
Line 28:		Line 28:
	! C-LOOK		! C-LOOK
	\|-		\|-
	! Motion		! Repeated Motion
	\| ~~Moves~~ ~~towards~~ the ~~end~~ of ~~the~~ ~~queue~~, ~~reversing~~ direction at the ~~end~~.		\| 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.		\| Only goes as far as the final request in that direction, then reverses direction.
	\| Goes to the ~~end~~ ~~of the queue~~, then jumps to the ~~beginning~~ of the ~~queue~~.		\| 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 ~~in that direction~~, then jumps to the first request in the ~~opposite~~ direction.		\| Only goes as far as the final request, then jumps to the first request and continues in the same direction.
	\|-
	! Effect
	\| Can lead to starvation of requests at the extremes of the disk.
	\| Efficient and reduces the total seek time compared to SCAN.
	\| Provides uniform wait times, avoids starvation, but can result in higher average response time.
	\| More efficient compared to C-SCAN, doesn’t traverse the entire disk. Provides uniform wait times and avoids starvation.
	\|-
	! Goal
	\| Fairness between high and low priority requests, but can lead to increased wait times at the ends.
	\| Optimization of seek time by avoiding unnecessary movements to the ends of the disk.
	\| Uniform wait times and avoidance of starvation at the ends of the disk.
	\| Efficient and uniform service, avoids unnecessary movements across the entire disk.
	\|}		\|}
	== Example ==		== Example ==

Jarfuls of Tweed: /* Variations */ Added table to specify the primary differences between variations.

2023-09-29T18:04:11Z

Variations: Added table to specify the primary differences between variations.

@@ Line 21: / Line 21: @@
 * [[N-Step-SCAN]]
 == Example ==
 The following is an example of how to calculate average disk seek times for both the SCAN and C-SCAN algorithms.

Kvng: WP:ASTONISH

2023-08-10T14:48:30Z

WP:ASTONISH

← Previous revision		Revision as of 14:48, 10 August 2023
Line 54:		Line 54:

	==See also==		==See also==
	*[[FIFO (computing and electronics)~~\|FCFS~~]]		*[[FIFO (computing and electronics)]]

	== References ==		== References ==

Widefox: /* Variations */ fix style and link

2023-08-07T14:25:29Z

Variations: fix style and link

← Previous revision		Revision as of 14:25, 7 August 2023
Line 13:		Line 13:

	== Variations ==		== 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.		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:		Other variations include:
	*[[FSCAN]]		* [[FSCAN]]
	*[[LOOK algorithm\|LOOK]] ~~(and '''~~C-LOOK~~''')~~		* [[LOOK algorithm\|LOOK]]
			** [[C-LOOK]]
	*[[N-Step-SCAN]]		* [[N-Step-SCAN]]

	== Example ==		== Example ==

Widefox: /* top */ improve Eng

2023-08-07T11:25:42Z

top: improve Eng

← Previous revision		Revision as of 11:25, 7 August 2023
Line 2:		Line 2:
	{{Refimprove\|date=November 2007}}		{{Refimprove\|date=November 2007}}

	The '''elevator algorithm''' ~~(also~~ '''SCAN''') is a [[hard disk\|disk]]-[[I/O scheduling\|scheduling]] algorithm to determine the motion of the disk's arm and head in servicing read and write requests.		The '''elevator algorithm''', or '''SCAN''', is a [[hard disk\|disk]]-[[I/O scheduling\|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.		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.

Widefox: /* See also */ already in body per WP:SEEALSO / WP:OVERLINK

2023-08-07T10:58:32Z

See also: already in body per WP:SEEALSO / WP:OVERLINK

← Previous revision		Revision as of 10:58, 7 August 2023
Line 54:		Line 54:
	==See also==		==See also==
	*[[FIFO (computing and electronics)\|FCFS]]		*[[FIFO (computing and electronics)\|FCFS]]
	*[[Shortest seek first\|Shortest seek time first]]

	== References ==		== References ==

Kvng: ce and clarifications. combine short related sentences and paragraphs.

2022-04-29T13:36:11Z

ce and clarifications. combine short related sentences and paragraphs.

← Previous revision		Revision as of 13:36, 29 April 2022
Line 48:		Line 48:

	== Analysis ==		== Analysis ==
	~~The~~ arm movement is ~~thus always~~ less than twice the number of total cylinders ~~then, for both versions of the elevator algorithm. The variation has the advantage to~~ ~~have~~ a smaller variance in response time. The algorithm is also relatively simple.		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.

	~~However, 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 [[Resource starvation\|starvation]] when new requests continually get serviced prior to existing requests.		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 [[Resource starvation\|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.

	Anti-starvation techniques can be applied to the shortest seek time first algorithm to guarantee an optimum response time.

	==See also==		==See also==
Line 60:		Line 58:
	== References ==		== References ==
	<references />		<references />

	[[Category:Disk scheduling algorithms]]		[[Category:Disk scheduling algorithms]]
	[[Category:Sorting algorithms]]		[[Category:Sorting algorithms]]