Elevátor algoritmus

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

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

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 lemezmeghajtó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 cilinderre kell pozicionálni, ahol vagy írási vagy olvasási műveletet kell majd végrehajtani. A kisebb cilinderszámok (címek) a lemez 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ü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 (valamint 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 kérés egy irányba haladva legyen kiszolgálva. Azaz elindul az adott irányba, és teljesíti a kéréseket, amit arra haladva teljesíteni tud, a többit tárolja. Ha már nincs több ilyen kérés, akkor visszatér az elejére és újra kezdi. 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ő cilinderek több mint kétszer olyan gyakran kerülnek kiszolgálásra, mint a legbelső és legkülső cilinderek.

A fejmozgá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.