LOOK algorithm - Revision history

ImSalv: /* Link lead to wrong page */

2024-02-09T13:23:45Z

Link lead to wrong page

← Previous revision		Revision as of 13:23, 9 February 2024
Line 7:		Line 7:

	==Description==		==Description==
	The LOOK algorithm, similar to the [[SCAN]] algorithm, honors requests on both sweep directions of the disk head, however, it additionally "looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served. In LOOK scheduling, the arm goes only as far as final requests in each direction and then reverses direction without going all the way to the end. Consider an example, Given a disk with 200 cylinders (0-199), suppose we have 8 pending requests: 98, 183, 37, 122, 14, 124, 65, 67 and that the read/write head is currently at cylinder 53. In order to complete these requests, the arm will move in the increasing order first and then will move in decreasing order after reaching the end. So, the order in which it will execute is 65, 67, 98, 122, 124, 183, 37, 14.<ref>{{cite web \|url=http://courses.teresco.org/cs432_f02/lectures/17-files/17-files.html \|title=Lecture 17 - Disk Scheduling }}</ref>		The LOOK algorithm, similar to the [[Elevator algorithm\|SCAN]] algorithm, honors requests on both sweep directions of the disk head, however, it additionally "looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served. In LOOK scheduling, the arm goes only as far as final requests in each direction and then reverses direction without going all the way to the end. Consider an example, Given a disk with 200 cylinders (0-199), suppose we have 8 pending requests: 98, 183, 37, 122, 14, 124, 65, 67 and that the read/write head is currently at cylinder 53. In order to complete these requests, the arm will move in the increasing order first and then will move in decreasing order after reaching the end. So, the order in which it will execute is 65, 67, 98, 122, 124, 183, 37, 14.<ref>{{cite web \|url=http://courses.teresco.org/cs432_f02/lectures/17-files/17-files.html \|title=Lecture 17 - Disk Scheduling }}</ref>

	LOOK avoids the starvation problem of [[shortest seek time first]] (SSTF). This is because LOOK is biased against the area recently traversed, and favors tracks clustered at the outermost and innermost edges of the platter. LOOK is also biased towards more recently arriving jobs (on average).		LOOK avoids the starvation problem of [[shortest seek time first]] (SSTF). This is because LOOK is biased against the area recently traversed, and favors tracks clustered at the outermost and innermost edges of the platter. LOOK is also biased towards more recently arriving jobs (on average).

Widefox: convert to sections ready for incoming R to sections, and fix MOS:ACRO / MOS:BOLD , fix Eng

2023-08-07T12:09:01Z

convert to sections ready for incoming R to sections, and fix MOS:ACRO / MOS:BOLD , fix Eng

← Previous revision		Revision as of 12:09, 7 August 2023
Line 4:		Line 4:
	}}		}}

	'''LOOK''' is a disk [[I/O scheduling\|scheduling]] algorithm used to determine the order in which new disk read and write requests are processed.		'''LOOK''' is a [[hard disk]] [[I/O scheduling\|scheduling]] algorithm used to determine the order in which new disk read and write requests are processed.

	==Description==		==Description==
	The ~~'''~~LOOK~~'''~~ algorithm is ~~the same as~~ the ~~'''~~SCAN~~'''~~ algorithm ~~in that it also~~ honors requests on both sweep ~~direction~~ of the disk head, however, ~~this~~ ~~algorithm~~ "~~Looks~~" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served. In LOOK scheduling, the arm goes only as far as final requests in each direction and then reverses direction without going all the way to the end. Consider an example, Given a disk with 200 cylinders (0-199), suppose we have 8 pending requests: 98, 183, 37, 122, 14, 124, 65, 67 and that the read/write head is currently at cylinder 53. In order to complete these requests, the arm will move in the increasing order first and then will move in decreasing order after reaching the end. So, the order in which it will execute is 65, 67, 98, 122, 124, 183, 37, 14.<ref>{{cite web \|url=http://courses.teresco.org/cs432_f02/lectures/17-files/17-files.html \|title=Lecture 17 - Disk Scheduling }}</ref>		The LOOK algorithm, similar to the [[SCAN]] algorithm, honors requests on both sweep directions of the disk head, however, it additionally "looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served. In LOOK scheduling, the arm goes only as far as final requests in each direction and then reverses direction without going all the way to the end. Consider an example, Given a disk with 200 cylinders (0-199), suppose we have 8 pending requests: 98, 183, 37, 122, 14, 124, 65, 67 and that the read/write head is currently at cylinder 53. In order to complete these requests, the arm will move in the increasing order first and then will move in decreasing order after reaching the end. So, the order in which it will execute is 65, 67, 98, 122, 124, 183, 37, 14.<ref>{{cite web \|url=http://courses.teresco.org/cs432_f02/lectures/17-files/17-files.html \|title=Lecture 17 - Disk Scheduling }}</ref>

	LOOK avoids the starvation problem of [[~~Shortest~~ seek time first]] (SSTF). This is because LOOK is biased against the area recently traversed, and favors tracks clustered at the outermost and innermost edges of the platter. LOOK is also biased towards more recently arriving jobs (on average).		LOOK avoids the starvation problem of [[shortest seek time first]] (SSTF). This is because LOOK is biased against the area recently traversed, and favors tracks clustered at the outermost and innermost edges of the platter. LOOK is also biased towards more recently arriving jobs (on average).

	==Variants==		==Variants==
			===C-LOOK===
	* '''C-LOOK''' (Circular LOOK)
	: One variant of LOOK is C-LOOK. It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time). The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list.		One variant of LOOK is circular LOOK (C-LOOK). It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time). The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list.

	* '''N-LOOK~~'''~~ and ~~'''~~F-LOOK~~'''~~		===N-LOOK and F-LOOK===
	: N and F LOOK were designed to offset LOOK’s bias towards recent jobs. Both algorithms partition the request queue into smaller sub queues and process the sub queues in order (oldest first). N-LOOK is so-called because the request queue is divided into ''N'' sub queues. F-LOOK is a simplification where there are only 2 queues, but they are used in a double-buffered fashion. While F-LOOK is processing one queue, all new requests go into the other one. To explain these algorithms we’re going to use the example of a disk with 200 tracks, and the read/write head starts at track 100. The request queue, in order, contains requests for tracks: 55, 58, 18, 90, 160, 38, we assume that the request queue is split into two, with the oldest one containing the requests for tracks: 55, 58, 18, 90. In this instance, N-LOOK and F-LOOK behave the same. Also notice, that in this configuration, it doesn’t matter which direction the head was moving in, all requested tracks are less than 100 so it will only move in the direction of decreasing tracks.		N and F LOOK were designed to offset LOOK’s bias towards recent jobs. Both algorithms partition the request queue into smaller sub queues and process the sub queues in order (oldest first). N-LOOK is so-called because the request queue is divided into ''N'' sub queues. F-LOOK is a simplification where there are only 2 queues, but they are used in a double-buffered fashion. While F-LOOK is processing one queue, all new requests go into the other one. To explain these algorithms we’re going to use the example of a disk with 200 tracks, and the read/write head starts at track 100. The request queue, in order, contains requests for tracks: 55, 58, 18, 90, 160, 38, we assume that the request queue is split into two, with the oldest one containing the requests for tracks: 55, 58, 18, 90. In this instance, N-LOOK and F-LOOK behave the same. Also notice, that in this configuration, it doesn’t matter which direction the head was moving in, all requested tracks are less than 100 so it will only move in the direction of decreasing tracks.
	: Even through the average number of tracks traversed is the same as LOOK in the worst case, N and F LOOK are in some sense, more fair than plain old LOOK. The sub queue system caps the maximum latency a process can expect between a request and it being serviced (unlike SSTF that can starve processes for arbitrary lengths of time).		Even through the average number of tracks traversed is the same as LOOK in the worst case, N and F LOOK are in some sense, more fair than plain old LOOK. The sub queue system caps the maximum latency a process can expect between a request and it being serviced (unlike SSTF that can starve processes for arbitrary lengths of time).

	* '''S-LOOK~~'''~~		===S-LOOK===
	: The ~~Shortest~~ LOOK (S-LOOK) algorithm is an extension of the LOOK algorithm to handle the cases where the disk head is located between the far-end requests. The algorithm is designed to make a decision of which direction should be served first instead of only continuing to seek in the same direction before the new requests have arrived. Since the seek time is directly proportional to the seek distance, our goal is to minimize the seek distance, and hence, reduce the seek time.		The shortest LOOK (S-LOOK) algorithm is an extension of the LOOK algorithm to handle the cases where the disk head is located between the far-end requests. The algorithm is designed to make a decision of which direction should be served first instead of only continuing to seek in the same direction before the new requests have arrived. Since the seek time is directly proportional to the seek distance, our goal is to minimize the seek distance, and hence, reduce the seek time.

	==Performance==		==Performance==
Line 26:		Line 26:

	==See also==		==See also==
	Other variations include:
	*[[Elevator algorithm\|SCAN]] - Elevator algorithm		*[[Elevator algorithm\|SCAN]] - Elevator algorithm
	*[[FSCAN]]		*[[FSCAN]]

Towopedia: /* Description */ remove the unsubstantiated claim that LOOK is almost identical to SSTF

2023-07-20T14:51:25Z

Description: remove the unsubstantiated claim that LOOK is almost identical to SSTF

← Previous revision		Revision as of 14:51, 20 July 2023
Line 9:		Line 9:
	The '''LOOK''' algorithm is the same as the '''SCAN''' algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served. In LOOK scheduling, the arm goes only as far as final requests in each direction and then reverses direction without going all the way to the end. Consider an example, Given a disk with 200 cylinders (0-199), suppose we have 8 pending requests: 98, 183, 37, 122, 14, 124, 65, 67 and that the read/write head is currently at cylinder 53. In order to complete these requests, the arm will move in the increasing order first and then will move in decreasing order after reaching the end. So, the order in which it will execute is 65, 67, 98, 122, 124, 183, 37, 14.<ref>{{cite web \|url=http://courses.teresco.org/cs432_f02/lectures/17-files/17-files.html \|title=Lecture 17 - Disk Scheduling }}</ref>		The '''LOOK''' algorithm is the same as the '''SCAN''' algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served. In LOOK scheduling, the arm goes only as far as final requests in each direction and then reverses direction without going all the way to the end. Consider an example, Given a disk with 200 cylinders (0-199), suppose we have 8 pending requests: 98, 183, 37, 122, 14, 124, 65, 67 and that the read/write head is currently at cylinder 53. In order to complete these requests, the arm will move in the increasing order first and then will move in decreasing order after reaching the end. So, the order in which it will execute is 65, 67, 98, 122, 124, 183, 37, 14.<ref>{{cite web \|url=http://courses.teresco.org/cs432_f02/lectures/17-files/17-files.html \|title=Lecture 17 - Disk Scheduling }}</ref>

	LOOK ~~behaves~~ ~~almost~~ ~~identically~~ to [[Shortest seek time first]] (SSTF)~~, but avoids the starvation problem of SSTF~~. This is because LOOK is biased against the area recently traversed, and ~~heavily~~ favors tracks clustered at the outermost and innermost edges of the platter. LOOK is also biased towards more recently arriving jobs (on average).		LOOK avoids the starvation problem of [[Shortest seek time first]] (SSTF). This is because LOOK is biased against the area recently traversed, and favors tracks clustered at the outermost and innermost edges of the platter. LOOK is also biased towards more recently arriving jobs (on average).

	==Variants==		==Variants==

Mandarax: .The->. The - Fix a typo in one click

2019-12-22T08:30:42Z

.The->. The - Fix a typo in one click

← Previous revision		Revision as of 08:30, 22 December 2019
Line 13:		Line 13:
	==Variants==		==Variants==
	* '''C-LOOK''' (Circular LOOK)		* '''C-LOOK''' (Circular LOOK)
	: One variant of LOOK is C-LOOK. It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time).The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list.		: One variant of LOOK is C-LOOK. It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time). The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list.

	* '''N-LOOK''' and '''F-LOOK'''		* '''N-LOOK''' and '''F-LOOK'''

Frap: /* Variants */

2018-12-14T19:26:41Z

Variants

← Previous revision		Revision as of 19:26, 14 December 2018
Line 16:		Line 16:

	* '''N-LOOK''' and '''F-LOOK'''		* '''N-LOOK''' and '''F-LOOK'''
	: N and F LOOK were designed to offset LOOK’s bias towards recent jobs. Both algorithms partition the request queue into smaller sub queues and process the sub queues in order (oldest first). N-LOOK is so-called because the request queue is divided into N sub queues. F-LOOK is a simplification where there are only 2 queues, but they are used in a double-buffered fashion. While F-LOOK is processing one queue, all new requests go into the other one. To explain these algorithms we’re going to use the example of a disk with 200 tracks, and the read/write head starts at track 100. The request queue, in order, contains requests for tracks: 55, 58, 18, 90, 160, 38, we assume that the request queue is split into two, with the oldest one containing the requests for tracks: 55, 58, 18, 90. In this instance, N-LOOK and F-LOOK behave the same. Also notice, that in this configuration, it doesn’t matter which direction the head was moving in, all requested tracks are less than 100 so it will only move in the direction of decreasing tracks.		: N and F LOOK were designed to offset LOOK’s bias towards recent jobs. Both algorithms partition the request queue into smaller sub queues and process the sub queues in order (oldest first). N-LOOK is so-called because the request queue is divided into ''N'' sub queues. F-LOOK is a simplification where there are only 2 queues, but they are used in a double-buffered fashion. While F-LOOK is processing one queue, all new requests go into the other one. To explain these algorithms we’re going to use the example of a disk with 200 tracks, and the read/write head starts at track 100. The request queue, in order, contains requests for tracks: 55, 58, 18, 90, 160, 38, we assume that the request queue is split into two, with the oldest one containing the requests for tracks: 55, 58, 18, 90. In this instance, N-LOOK and F-LOOK behave the same. Also notice, that in this configuration, it doesn’t matter which direction the head was moving in, all requested tracks are less than 100 so it will only move in the direction of decreasing tracks.
	: Even through the average number of tracks traversed is the same as LOOK in the worst case, N and F LOOK are in some sense, more fair than plain old LOOK. The sub queue system caps the maximum latency a process can expect between a request and it being serviced (unlike SSTF that can starve processes for arbitrary lengths of time).		: Even through the average number of tracks traversed is the same as LOOK in the worst case, N and F LOOK are in some sense, more fair than plain old LOOK. The sub queue system caps the maximum latency a process can expect between a request and it being serviced (unlike SSTF that can starve processes for arbitrary lengths of time).

Abelmoschus Esculentus: Reverted good faith edits by 103.27.164.5 (talk): not RS (HG) (3.4.5)

2018-12-05T04:09:16Z

Reverted good faith edits by 103.27.164.5 (talk): not RS (HG) (3.4.5)

← Previous revision		Revision as of 04:09, 5 December 2018
Line 30:		Line 30:
	*[[FSCAN]]		*[[FSCAN]]
	*[[N-Step-SCAN]]		*[[N-Step-SCAN]]
	<ref>https://ultratechbits.blogspot.com/search/label/Operating%20System</ref>

	==References==		==References==

103.27.164.5: /* See also */

2018-12-05T04:09:06Z

Shubhamsharma8305: /* Variants */Corrected some wrong information.

2017-12-08T05:08:18Z

Variants: Corrected some wrong information.

← Previous revision		Revision as of 05:08, 8 December 2017
Line 13:		Line 13:
	==Variants==		==Variants==
	* '''C-LOOK''' (Circular LOOK)		* '''C-LOOK''' (Circular LOOK)
	: One variant of LOOK is C-LOOK. It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time).The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list. ~~[This sentence makes no sense]~~		: One variant of LOOK is C-LOOK. It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time).The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list.

	* '''N-LOOK''' and '''F-LOOK'''		* '''N-LOOK''' and '''F-LOOK'''

14.139.196.6: /* Variants */

2017-11-29T15:44:32Z

Variants

← Previous revision		Revision as of 15:44, 29 November 2017
Line 13:		Line 13:
	==Variants==		==Variants==
	* '''C-LOOK''' (Circular LOOK)		* '''C-LOOK''' (Circular LOOK)
	: One variant of LOOK is C-LOOK. It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time).The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list.		: One variant of LOOK is C-LOOK. It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time).The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list. [This sentence makes no sense]

	* '''N-LOOK''' and '''F-LOOK'''		* '''N-LOOK''' and '''F-LOOK'''

PhilKnight: Reverted good faith edits by KHOLAAADESH (talk) - formatting errors

2017-10-24T19:05:13Z

Reverted good faith edits by KHOLAAADESH (talk) - formatting errors

@@ Line 25: / Line 25: @@
 LOOK has slightly better average seek times than SCAN. C-LOOK has a slightly lower variance in seek time than LOOK since the worst case seek time is nearly cut in half.
 ==See also==
 Other variations include:
@@ Line 34: / Line 30: @@
 *[[FSCAN]]
 *[[N-Step-SCAN]]
 ==References==