Elevátor algoritmus

A Wikipédiából, a szabad lexikonból.

Az elevátor algoritmus vagy lift algoritmus (ismert még, mint SCAN) egy diszk ütemezési algoritmus, ami meghatározza a diszk fejet tartó karjának (és fejének) mozgatását az olvasási és írási kérelmek kiszolgálásához.

[szerkesztés] Leírása

Az algoritmust a lift működéséhez való hasonlóságáról nevezték el így. Az egyszerűség kedvéért képzeljük el a diszk meghajtót úgy, hogy annak a működését egy bemeneti puffer tárolóba érkező kérések vezérlik, amelyek meghatározzák, hogy a fejeket mozgató kart melyik ciliderre kell pozicionálni, ahol vagy írási vagy olvasási műveletet kell majd végrehajtani. A kisebb cilinder számok (címek) a diszk tengelyéhez közelebbi, a nagyobb számok pedig a távolabbi cilindereket jelölik.

A kar/fej valamilyen kiinduló helyzetétől számítva, egy bejövő kérés hatására elindul egy irányba. Lesz egy indikátor, ami azt mutatja, hogy az aktuális mozgás kifelé vagy befelé irányú. Ha egy kérés érkezik, az mindaddig teljesítésre kerül, amíg az az aktuális mozgás irányába esik, ellenkező esetben tárolódik. Ha nincs ilyen aktuális kérés, akkor a kar irányt vált, és az eddig tárolt kéréseket hajtja végre (valamit azokat a bejövő kéréseket, amelyek "ebbe az irányba esnek"), majd ismét az ellenkező irányú mozgás következik, és így tovább.

A módszer egy változata biztosítja, hogy minden egy irányba eső kérés kiszolgálásra kerüljön, és ha például a kar/fej elérte a külső cilinder, akkor irányt vált, és elindul a belső cilinder felé (vagy ellenkezőelg), közben a kéréseket teljesíti (ebben az irányban, a többieket tárolja), aztán megint irányt vált és így tovább. Ez a módszer mint "cirkuláris elevátor" (magyarul: páternoszter) vagy "C-SCAN" néven ismert. A megoldás nagyjából azonos teljesítményt ad minden fejpozíció esetében, mivel a fejtől a várható távolság mindig a maximális távolság fele, a normál algoritmus esetében pedig a középső ciliderek több, mint kétszer olyan gyakran kerülnek kiszolgálásra, mint legbelső és legkülső cilinderek.

[szerkesztés] Elemzés

A fejmozás mindkét algoritmus változatban kevesebb, mint a kétszerese az összes cilinderek számánál. A második változat előnye, hogy kisebb a válaszidő varianciája. Maga az algoritmus viszonylag egyszerű.

Bár a lift algoritmus nem mindig jobb a rövidebb mozgás először algoritmusnál, ami csaknem megközelíti az optimálist, de a válaszidő varianciája sokkal magasabb.

Más nyelveken