Algorytm LOOK

LOOK to algorytm planowania dysku używany do określania kolejności przetwarzania nowych żądań odczytu i zapisu na dysku.

Opis

Algorytm LOOK jest taki sam jak algorytm SCAN w tym, że honoruje również żądania w obu kierunkach przemiatania głowicy dysku, jednak ten algorytm „patrzy” przed siebie, aby sprawdzić, czy są jakieś oczekujące żądania w kierunku ruchu głowicy. Jeśli w kierunku ruchu głowicy nie ma oczekujących żądań, wówczas ruch głowicy dysku zostanie odwrócony w przeciwnym kierunku i można obsłużyć żądania w innym kierunku. W harmonogramie LOOK ramię przechodzi tylko do końcowych żądań w każdym kierunku, a następnie odwraca kierunek bez dochodzenia do końca. Rozważmy przykład, biorąc pod uwagę dysk z 200 cylindrami (0-199), załóżmy, że mamy 8 oczekujących żądań: 98, 183, 37, 122, 14, 124, 65, 67 i że głowica odczytu/zapisu znajduje się obecnie na cylindrze 53 Aby wykonać te żądania, ramię najpierw przesunie się w porządku rosnącym, a następnie po osiągnięciu końca przesunie się w porządku malejącym. Tak więc kolejność, w jakiej będzie wykonywana, to 65, 67, 98, 122, 124, 183, 37, 14.

LOOK zachowuje się prawie identycznie jak Shortest seek time first (SSTF), ale unika problemu głodu SSTF. Dzieje się tak dlatego, że LOOK jest ukierunkowany na ostatnio przebyty obszar i zdecydowanie faworyzuje ścieżki skupione na najbardziej zewnętrznych i najbardziej wewnętrznych krawędziach talerza. LOOK jest również stronniczy w kierunku nowych miejsc pracy (średnio).

Warianty

• C-LOOK (Circular LOOK)

Jednym z wariantów LOOK jest C-LOOK. Jest to próba usunięcia uprzedzeń w funkcji LOOK w poszukiwaniu klastrów ścieżek na krawędziach talerza. C-LOOK zasadniczo skanuje tylko w jednym kierunku. Albo zamiatasz od wewnątrz na zewnątrz, albo od zewnątrz do środka. Kiedy dojdziesz do końca, po prostu odchyl głowę z powrotem do początku. W rzeczywistości wykorzystuje to fakt, że wiele napędów może poruszaćgłowicą odczytu/zapisu z dużą szybkością, jeśli porusza się po dużej liczbieścieżek (np. czas wyszukiwania od ostatniej ścieżki do ścieżki 0 jest krótszy niż można by się spodziewać i zazwyczaj krótszy niż czas potrzebny na wyszukanie jednego utworu na raz). Ogromny skok z jednego końca żądania do drugiego nie jest uważany za ruch głowy, ponieważ cylindry są traktowane jako lista kołowa.

• N-LOOK i F-LOOK

N i F LOOK zostały zaprojektowane, aby zrównoważyć uprzedzenia LOOK do ostatnich zleceń. Oba algorytmy dzielą kolejkę żądań na mniejsze kolejki podrzędne i przetwarzają kolejki podrzędne w kolejności (od najstarszych). N-LOOK jest tak zwany, ponieważ kolejka żądań jest podzielona na N kolejki podrzędne. F-LOOK to uproszczenie, w którym są tylko 2 kolejki, ale są one używane w sposób podwójnie buforowany. Podczas gdy F-LOOK przetwarza jedną kolejkę, wszystkie nowe żądania trafiają do drugiej. Aby wyjaśnić te algorytmy, posłużymy się przykładem dysku z 200 ścieżkami, gdzie głowica odczytu/zapisu zaczyna się od ścieżki 100. Kolejka żądań zawiera kolejno żądania ścieżek: 55, 58, 18, 90, 160, 38 zakładamy, że kolejka żądań jest podzielona na dwie części, z których najstarsza zawiera żądania utworów: 55, 58, 18, 90. W tym przypadku N-LOOK i F-LOOK zachowują się tak samo. Zauważ również, że w tej konfiguracji nie ma znaczenia, w którym kierunku poruszała się głowica, wszystkie żądane ścieżki są mniejsze niż 100, więc będzie się poruszać tylko w kierunku ścieżek malejących.

Nawet jeśli średnia liczba przejechanych torów jest taka sama jak LOOK w najgorszym przypadku, N i F LOOK są w pewnym sensie bardziej sprawiedliwe niż zwykły stary LOOK. System kolejek podrzędnych ogranicza maksymalne opóźnienie, jakiego proces może oczekiwać między żądaniem a jego obsługą (w przeciwieństwie do SSTF, który może zagłodzić procesy na dowolny czas).

• WYGLĄD S

Algorytm Shortest LOOK (S-LOOK) jest rozszerzeniem algorytmu LOOK do obsługi przypadków, w których głowica dysku znajduje się między żądaniami odległego końca. Algorytm ma na celu podjęcie decyzji, który kierunek powinien być obsłużony jako pierwszy, zamiast kontynuacji poszukiwania w tym samym kierunku, zanim nadejdzie nowe żądanie. Ponieważ czas wyszukiwania jest wprost proporcjonalny do odległości wyszukiwania, naszym celem jest zminimalizowanie odległości wyszukiwania, a tym samym skrócenie czasu wyszukiwania.

Wydajność

LOOK ma nieco lepsze średnie czasy wyszukiwania niż SCAN. C-LOOK ma nieco mniejszą zmienność czasu wyszukiwania niż LOOK, ponieważ czas wyszukiwania w najgorszym przypadku jest prawie o połowę krótszy.

Zobacz też

Inne odmiany obejmują:

• SCAN - Algorytm windy
• FSCAN
• Skanowanie w krokach N