Talk:Elevator algorithm

I added the merging tags, because these two pages refer to the same thing. Is anyone opposed to making Elevator sort a redirect? --Jamuraa 18:31, 4 March 2006 (UTC)

Making elevator sort a redirect to this page sounds good to me, they're talking about exactly the same thing. GeorgeBills 12:47, 14 March 2006 (UTC)

Use of algorithm

Are disk scheduling algorithms actually in use? On which layer are they implemented? Operating system or hard disk? Thanks, --Abdull 19:04, 24 April 2006 (UTC)

Average Seek Time

When calculating the average seek time for the C-SCAN algorithm, the seek for returning to the begininng of the disk is included, so that the total number of seeks is 6. But the total number of actual disk I/Os is still 5, so should the average be:

185/5 = 37?

Wrong description?

The description says as following:

"As additional requests arrive, requests are serviced only in the current direction of arm movement until the arm reaches the edge of the disk."

But in Andrew S Tanenbaum's "Modern Operating Systems", 5.4.3. it says:

"When a request finishes, the disk or elevator driver checks the bit. If it is UP, the arm or cabin is moved to the next highest pending request. If no requests are pending at higher positions, the direction bit is reversed. When the bit is set to DOWN, the move is to the next lowest requested position, if any."

It seems as though the correct description would be something like:

"As additional requests arrive, requests are serviced only in the current direction of arm movement until the arm reaches the last request, then the arm turns and services the requests in the new direction."

Anyone agree with me?

   -trbox  —Preceding unsigned comment added by Trbox (talk • contribs) 14:59, 2 April 2008 (UTC) 

Hi Trbox. I'd say Tanenbaum is not correct here, or at least he described the algorithm of how a real elevator would be operated - which equals the LOOK algorithm. I base my opinion on this and other lecture notes I've read. I undid your edits. I hope this is fine for you :). Maybe Wikipedia is wrong... maybe it's correct to call LOOK the elevator algorithm. --Abdull (talk) 19:16, 7 August 2008 (UTC)

Clearing up the confusion with the example

As far as the algorithm is concerned the C-SCAN acts as a circular list, going to the next closest buffered seek. On the other hand SCAN inverts the order the list is being processed in. However as far as physical seek time goes one has to factor in the drive head returning back to the nearest cylinders because any drive head movement requires time and requests are still outstanding so this time counts towards the seek time.

• Example drive assumes 0 is innermost cylinder and 100 is outermost cylinder.
• 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.

• Seek 1: |50 − 35| = 15
• Seek 2: |75 − 50| = 25
• Seek 3: |100 − 75| = 25
• Sweep 1: |100 − 100| = 0 The head needs to sweep to outermost cylinder, but it is already there.

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): 15 + 25 + 25 + 80 + 10 = 155
• Average (SCAN): 155 ÷ 5 = 31

• Sweep 2 (C-SCAN): |0 − 100| = 100 The head needs to seek the innermost cylinder, but this time has to be counted towards average seek time as seeks are still outstanding.
• Seek 5 (C-SCAN): 10 − 0 = 10
• Seek 6 (C-SCAN): 20 − 10 = 10
• Total (C-SCAN): 15 + 25 + 25 + 100 + 10 + 10 = 185
• Average (C-SCAN): 185 ÷ 5 = 37

This matches the description in the Variations section that a return seek time is wasted, and hence one can expect larger average seek time for executing the same requests. The advantage to C-SCAN is that if one factors in return sweep delay the average seek will be a cylinder count away, as 1 outer to inner most sweep is wasted, and the worst case seek time will always be under 2 cylinder counts away. This is different from SCAN where the middle cylinder has a worst case seek time of under 1 cylinder count while the very edges have a worst case seek time of under 2 cylinder counts and so also have different average seek times depending on the cylinder being sought. As such C-SCAN is more fair as all cylinders are treated equally as opposed to SCAN where middle numbered cylinders perform better than outer numbered cylinders. SCAN has potentially better seek throughput as the middle numbered cylinders have better seek time performance than the outer numbered cylinders as opposed to C-SCAN where all cylinders have seek performance as bad as the SCAN outer numbered cylinders.

109.159.92.134 (talk) 09:29, 27 December 2017 (UTC) DrSuperGood