25:
184:
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.
270:
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
183:
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
175:. 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.
294:
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.
362:
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.
374:
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.
144:, 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.
159:
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.
167:
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
432:
42:
108:
383:
89:
61:
402:
46:
68:
437:
75:
326:
0 − 100 = 0 head movement as cylinders are treated as a circular list (C-SCAN always goes back to the first track)
35:
256:
The following is an example of how to calculate average disk seek times for both the SCAN and C-SCAN algorithms.
57:
245:
Only goes as far as the final request, then jumps to the first request and continues in the same direction.
236:
Goes to the last track (whether requested or not), then reverses direction and goes to the first track.
156:
370:, which is slightly closer to optimal, but can result in high variance in response time and even in
354:
Even though six seeks were performed using the C-SCAN algorithm, only five I/Os were actually done.
371:
367:
137:
algorithm to determine the motion of the disk's arm and head in servicing read and write requests.
82:
242:
Goes to the last track, then jumps to the first track and continues in the same direction.
196:
134:
271:
magnitude (i.e. absolute value) between the next track request and the current track.
426:
260:
Example list of pending disk requests (listed by track number): 100, 50, 10, 20, 75.
406:
239:
Only goes as far as the final request in that direction, then reverses direction.
208:
152:
24:
148:
130:
141:
266:
The list will need to be sorted in ascending order: 10, 20, 50, 75, 100.
201:
191:
18:
155:
of pending read/write requests, along with the associated
140:
This algorithm is named after the behavior of a building
263:
The starting track number for the examples will be 35.
49:. Unsourced material may be challenged and removed.
366:The elevator algorithm is not always better than
8:
213:
109:Learn how and when to remove this message
147:From an implementation perspective, the
394:
7:
47:adding citations to reliable sources
14:
384:FIFO (computing and electronics)
23:
34:needs additional citations for
1:
454:
433:Disk scheduling algorithms
187:Other variations include:
16:Disk-scheduling algorithm
58:"Elevator algorithm"
43:improve this article
368:shortest seek first
438:Sorting algorithms
123:elevator algorithm
403:"Disk scheduling"
348:Average (C-SCAN):
249:
248:
119:
118:
111:
93:
445:
418:
417:
415:
414:
405:. Archived from
399:
336:Seek 6 (C-SCAN):
330:Seek 5 (C-SCAN):
324:Seek 4 (C-SCAN):
233:Repeated Motion
214:
114:
107:
103:
100:
94:
92:
51:
27:
19:
453:
452:
448:
447:
446:
444:
443:
442:
423:
422:
421:
412:
410:
401:
400:
396:
392:
380:
360:
342:Total (C-SCAN):
318:Average (SCAN):
254:
181:
165:
115:
104:
98:
95:
52:
50:
40:
28:
17:
12:
11:
5:
451:
449:
441:
440:
435:
425:
424:
420:
419:
393:
391:
388:
387:
386:
379:
376:
359:
356:
352:
351:
345:
339:
333:
327:
321:
315:
309:
306:Seek 5 (SCAN):
303:
300:Seek 4 (SCAN):
292:
291:
285:
279:
268:
267:
264:
261:
253:
250:
247:
246:
243:
240:
237:
234:
230:
229:
226:
223:
220:
217:
212:
211:
206:
205:
204:
194:
180:
177:
164:
161:
117:
116:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
450:
439:
436:
434:
431:
430:
428:
409:on 2008-06-06
408:
404:
398:
395:
389:
385:
382:
381:
377:
375:
373:
369:
364:
357:
355:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
316:
313:
312:Total (SCAN):
310:
307:
304:
302:20 − 100 = 80
301:
298:
297:
296:
290:100 − 75 = 25
289:
286:
283:
280:
277:
274:
273:
272:
265:
262:
259:
258:
257:
251:
244:
241:
238:
235:
232:
231:
227:
224:
221:
218:
216:
215:
210:
207:
203:
200:
199:
198:
195:
193:
190:
189:
188:
185:
178:
176:
174:
170:
162:
160:
158:
154:
150:
145:
143:
138:
136:
132:
128:
124:
113:
110:
102:
99:November 2007
91:
88:
84:
81:
77:
74:
70:
67:
63:
60: –
59:
55:
54:Find sources:
48:
44:
38:
37:
32:This article
30:
26:
21:
20:
411:. Retrieved
407:the original
397:
365:
361:
353:
347:
341:
338:20 − 10 = 10
335:
329:
323:
320:155 ÷ 5 = 31
317:
311:
308:10 − 20 = 10
305:
299:
293:
287:
284:75 − 50 = 25
281:
278:50 − 35 = 15
275:
269:
255:
186:
182:
172:
168:
166:
151:maintains a
146:
139:
126:
122:
120:
105:
96:
86:
79:
72:
65:
53:
41:Please help
36:verification
33:
350:85 ÷ 5 = 17
332:10 − 0 = 10
209:N-Step-SCAN
163:Description
427:Categories
413:2008-01-21
390:References
372:starvation
179:Variations
135:scheduling
69:newspapers
378:See also
358:Analysis
157:cylinder
142:elevator
288:Seek 3:
282:Seek 2:
276:Seek 1:
252:Example
228:C-LOOK
225:C-SCAN
129:, is a
83:scholar
202:C-LOOK
153:buffer
85:
78:
71:
64:
56:
222:LOOK
219:SCAN
192:FSCAN
149:drive
125:, or
90:JSTOR
76:books
197:LOOK
131:disk
127:SCAN
121:The
62:news
314:155
173:out
171:or
45:by
429::
344:85
169:in
416:.
133:-
112:)
106:(
101:)
97:(
87:·
80:·
73:·
66:·
39:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
