Лифт алгоритам
Лифт алгоритам (такође и 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

Референце 

Алторитми планирања
Алторитми планирања диска
Алгоритми сортирања
Лифт алгоритам ( такође и SCAN ) је алгоритам за планирање диска који одређује покрете руке и главе диска током читања и писања захтева . Овај алгоритам је назван по понашању лифта у згради , где се лифт креће тренутном путањом горе доле све док се не испразни , заустављајући се само да неко изађе или да покупи нове људе који се крећу у истом правцу . Из погледа имплементације , складиштење диска у баферу одржава нерешене захтеве за упис / испис , заједно са удруженим цилиндром броја наредби . Доњи цилиндарни бројеви показују да је цилиндар ближи осовини , и већи бројеви покзују да је цилиндар удаљенији . Опиc Када дође нови захтев док диск мирује , инцијални покрет руке / главе ће бити у смеру цилиндра где се подаци налазе , било да су унутра или споља . Како долазе нови захтеви , они се обрађују само у тренутном смеру руке док она не дође до краја диска . Када се ово догоди , смер руке се обрће , и захтеви који су били у супротном смеру се обрађују и тако даље . Варијације Једна варијација ове методе осигурава да се сви захтеви обрађују у само једном смеру , то јест , када глава дође до спољашње ивице диска , враћа се на почетак и обрађује нове захтеве у једном смеру ( или обрнуто ) . Ово је познато као " Кружни лифт алгоритам " или C-SCAN . Ово даје много боље перформансе за све позиције главе , зато што је очекивана раздаљина од главе увек половина максималне раздаљине , за разлику од стандардног лифт алгоритма где ће цилиндри у средини бити обрађени до два пута више него најдубљи и крајњи цилиндри . Остале варијације укључују : FSCAN LOOK ( и C-LOOK ) N-Step-SCAN Пример Следи пример како рачунати просечно време претраге диска и SCAN и C-SCAN алгоритама . Пример листе нерешених захтева( наведени су по пратећем броју ) : Пратећи број у примерима ће бити Листа ће бити сортирана навише : И SCAN и C-SCAN се понашају исто све док не дођу до последњет пратећег броја . Ради овог примера претпоставимо да SCAN алгоритам тренутно иде са нижег на већи пратећи број( као што и C-SCAN то ради ) . За обе методе , узимамо разлику у величини ( апсолутну вредност ) између следећег и тренутног пратећег броја . Претрага−= Претрага−= Претрага−= У овом тренутку оба су дошла до највишег ( последњег ) пратећег броја.SCAN ће само обрнути смер и обраду следећег најближег захтева диска ( у овом примеруа C-SCAN ће увек ићи дои онда почети да иде ка вишим пратећим бројевима . Претрага( SCAN ) :−= Претрага( SCAN ) :−= Укупно ( SCAN ) : Просек ( SCAN ) :÷= Претрага( C-SCAN ) :−=( C-SCAN увек иде назад до првог пратећег ) Претрага( C-SCAN ) :−= Претрага( C-SCAN ) :−= Укупно ( C-SCAN ) : Просек ( C-SCAN ) :÷= Белешка : Иако се прошло крозпретрага користећи C-SCAN , самоI / О је урађено . Дефиницја C-SCAN-a : C-SCAN помера главу са једног краја диска на други крај . Обрађују се захтеви успут . Глава се одмах по доласку на крај враћа на почетак диска али без обраде захтева у повратку . Анализа Број покрета руке је дакле увек дупло мањи од броја цилиндара у обе верзије лифт алгоритма . Варијација има предност да има мање варијација у времену одзива . Алгоритам је такође релативно једноставан . Међутим , лифт алгоритам није увек бољи од алгоритма најкраће претраге који је мало ближи оптималном али може дати велике варијације у одзивном времену чак и током гладовања док се нови захтеви константно обрађују уместо већ постојећих захтева . Технике анти-гладовања се могу применити на алгоритам најкраће претраге да би се обезбедило отимално време одзива . Видети такође FCFS FSCAN LOOK N-Step-SCAN Shortest seek time first Референце Алторитми планирања Алторитми планирања диска Алгоритми сортирања