Лифт алгоритам — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
Нема описа измене |
||
Ред 19:
*[[LOOK algorithm|LOOK]] (и '''C-LOOK''')
*[[N-Step-SCAN]]
==Пример==
Следи пример како рачунати просечно време претраге диска и SCAN и C-SCAN алторитама.
* Пример листе нерешених захтева(наведени су по пратећем броју): 100, 50, 10, 20, 75.
* Пратећи број у примерима ће бити 35.
* Листа ће бити сортирана навише: 10, 20, 50, 75, 100.
И SCAN и C-SCAN се понашају исто све док не дођу до последњет пратећег броја. Ради овог примера претпоставимо да SCAN алторитан тренутно иде са нижет на већи пратећи број(као што и C-SCAN то ради). За обе методе, уѕимамо разлику у величини (апсолутну вредност) између следећег и тренутног пратећег броја.
* '''Претрага 1:''' 50 − 35 = 15
* '''Претрага 2:''' 75 − 50 = 25
* '''Претрага 3:''' 100 − 75 = 25
У овом тренутку оба су дошла до највишег (последњет) пратећег броја.SCAN ће само обрнути смер и обраду следећег најближег захтева диска (у овом примеру 20) а C-SCAN ће увек ићи до 0 и онда почети да иде ка вишим пратећим бројевима.
* '''Претрага 4 (SCAN):''' 20 − 100 = 80
* '''Претрага 5 (SCAN):''' 10 − 20 = 10
* '''Укупно (SCAN):''' 155
* '''Просек (SCAN):''' 155 ÷ 5 = 31
* '''Претрага 4 (C-SCAN):''' 0 − 100 = 100 (C-SCAN always goes back to the first track)
* '''Претрага 5 (C-SCAN):''' 10 − 0 = 10
* '''Претрага 6 (C-SCAN):''' 20 − 10 = 10
* '''Укупно (C-SCAN):''' 185
* '''Просек (C-SCAN):''' 185 ÷ 5 = 37
''Белешка:'' Иако се прошло кроз 6 претрага користећи C-SCAN, само 5 I/О је урађено.
''Дефиницја C-SCAN-a:'' C-SCAN помера главу са једног краја диска на други крај. Обрађују се захтеви успут. Глава се одмах по доласку на крај враћа на почетак диска али без обраде захтева у повратку.
==Анализа==
Покрет руке је дакле увек дупло мањи од броја цилиндара у обе верзије лифт алгоритма. Варијација има предност да има манје варијација у времену одзива. Алгоритам је такође релативно једноставан. Међутим, лифт алгоритам није увек бољи од алгоритма [[најкраћа претрага|најкраће претраге]] који је мало ближи оптималном али може дати велике варијације у одзивном времену чак и током [[гладовање ресурса(информатика)|гладовања]] док се нови захтеви константно обрађују уместо већ постојећих захтева. Технике анти-гладовања се могу применити на алторитам најкраће претраге да би се обезбедило отимално време одзива.
==Видети такође==
*[[ФИФО метода|FCFS]]
*[[FSCAN]]
*[[LOOK algorithm|LOOK]]
*[[N-Step-SCAN]]
*[[Shortest seek first|Shortest seek time first]]
== Референце ==
| |||