Лифт алгоритам

Лифт алгоритам (такође и SCAN) је алгоритам за планирање диска који одређује покрете руке и главе диска током читања и писања захтева.

Овај алгоритам је назван по понашању лифта у згради, где се лифт креће тренутном путањом горе доле све док се не испразни, заустављајући се само да неко изађе или да покупи нове људе који се крећу у истом правцу.

Из погледа имплементације, складиштење диска у баферу одржава нерешене захтеве за упис/испис, заједно са удруженим цилиндром броја наредби. Доњи цилиндарни бројеви показују да је цилиндар ближи осовини, и већи бројеви покзују да је цилиндар удаљенији.

Опиc

Када дође нови захтев док диск мирује, инцијални покрет руке/главе ће бити у смеру цилиндра где се подаци налазе, било да су унутра или споља. Како долазе нови захтеви, они се обрађују само у тренутном смеру руке док она не дође до краја диска. Када се ово догоди, смер руке се обрће, и захтеви који су били у супротном смеру се обрађују и тако даље.

Варијације

Једна варијација ове методе осигурава да се сви захтеви обрађују у само једном смеру, то јест, када глава дође до спољашње ивице диска, враћа се на почетак и обрађује нове захтеве у једном смеру (или обрнуто). Ово је познато као "Кружни лифт алгоритам" или C-SCAN. Ово даје много боље перформансе за све позиције главе, зато што је очекивана раздаљина од главе увек половина максималне раздаљине, за разлику од стандардног лифт алгоритма где ће цилиндри у средини бити обрађени до два пута више него најдубљи и крајњи цилиндри.

Остале варијације укључују:

• FSCAN
• 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 увек иде назад до првог пратећег)
• Претрага 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
• N-Step-SCAN
• Shortest seek time first