Lift algoritam

Lift algoritam (takođe i SCAN) je algoritam za planiranje diska koji određuje pokrete ruke i glave diska tokom čitanja i pisanja zahteva.

Ovaj algoritam je nazvan po ponašanju lifta u zgradi, gde se lift kreće trenutnom putanjom gore dole sve dok se ne isprazni, zaustavljajući se samo da neko izađe ili da pokupi nove ljude koji se kreću u istom pravcu.

Iz pogleda implementacije, skladištenje diska u baferu održava nerešene zahteve za upis/ispis, zajedno sa udruženim cilindrom broja naredbi. Donji cilindarni brojevi pokazuju da je cilindar bliži osovini, i veći brojevi pokzuju da je cilindar udaljeniji.

Opic

Kada dođe novi zahtev dok disk miruje, incijalni pokret ruke/glave će biti u smeru cilindra gde se podaci nalaze, bilo da su unutra ili spolja. Kako dolaze novi zahtevi, oni se obrađuju samo u trenutnom smeru ruke dok ona ne dođe do kraja diska. Kada se ovo dogodi, smer ruke se obrće, i zahtevi koji su bili u suprotnom smeru se obrađuju i tako dalje.

Varijacije

Jedna varijacija ove metode osigurava da se svi zahtevi obrađuju u samo jednom smeru, to jest, kada glava dođe do spoljašnje ivice diska, vraća se na početak i obrađuje nove zahteve u jednom smeru (ili obrnuto). Ovo je poznato kao "Kružni lift algoritam" ili C-SCAN. Ovo daje mnogo bolje performanse za sve pozicije glave, zato što je očekivana razdaljina od glave uvek polovina maksimalne razdaljine, za razliku od standardnog lift algoritma gde će cilindri u sredini biti obrađeni do dva puta više nego najdublji i krajnji cilindri.

Ostale varijacije uključuju:

• FSCAN
• LOOK (i C-LOOK)
• N-Step-SCAN

Primer

Sledi primer kako računati prosečno vreme pretrage diska i SCAN i C-SCAN algoritama.

• Primer liste nerešenih zahteva(navedeni su po pratećem broju): 100, 50, 10, 20, 75.
• Prateći broj u primerima će biti 35.
• Lista će biti sortirana naviše: 10, 20, 50, 75, 100.

I SCAN i C-SCAN se ponašaju isto sve dok ne dođu do poslednjet pratećeg broja. Radi ovog primera pretpostavimo da SCAN algoritam trenutno ide sa nižeg na veći prateći broj(kao što i C-SCAN to radi). Za obe metode, uzimamo razliku u veličini (apsolutnu vrednost) između sledećeg i trenutnog pratećeg broja.

• Pretraga 1: 50 − 35 = 15
• Pretraga 2: 75 − 50 = 25
• Pretraga 3: 100 − 75 = 25

U ovom trenutku oba su došla do najvišeg (poslednjeg) pratećeg broja.SCAN će samo obrnuti smer i obradu sledećeg najbližeg zahteva diska (u ovom primeru 20) a C-SCAN će uvek ići do 0 i onda početi da ide ka višim pratećim brojevima.

• Pretraga 4 (SCAN): 20 − 100 = 80
• Pretraga 5 (SCAN): 10 − 20 = 10
• Ukupno (SCAN): 155
• Prosek (SCAN): 155 ÷ 5 = 31
• Pretraga 4 (C-SCAN): 0 − 100 = 100 (C-SCAN uvek ide nazad do prvog pratećeg)
• Pretraga 5 (C-SCAN): 10 − 0 = 10
• Pretraga 6 (C-SCAN): 20 − 10 = 10
• Ukupno (C-SCAN): 185
• Prosek (C-SCAN): 185 ÷ 5 = 37

Beleška: Iako se prošlo kroz 6 pretraga koristeći C-SCAN, samo 5 I/O je urađeno.

Definicja C-SCAN-a: C-SCAN pomera glavu sa jednog kraja diska na drugi kraj. Obrađuju se zahtevi usput. Glava se odmah po dolasku na kraj vraća na početak diska ali bez obrade zahteva u povratku.

Analiza

Broj pokreta ruke je dakle uvek duplo manji od broja cilindara u obe verzije lift algoritma. Varijacija ima prednost da ima manje varijacija u vremenu odziva. Algoritam je takođe relativno jednostavan. Međutim, lift algoritam nije uvek bolji od algoritma najkraće pretrage koji je malo bliži optimalnom ali može dati velike varijacije u odzivnom vremenu čak i tokom gladovanja dok se novi zahtevi konstantno obrađuju umesto već postojećih zahteva. Tehnike anti-gladovanja se mogu primeniti na algoritam najkraće pretrage da bi se obezbedilo otimalno vreme odziva.

Videti takođe

• FCFS
• FSCAN
• LOOK
• N-Step-SCAN
• Shortest seek time first