Asansör algoritması - Elevator algorithm

Asansör algoritması (ayrıca TARAMA ) bir olduğunu diski - zamanlama okuma ve yazma istekleri hizmet içinde diskin kol ve başın hareketini belirlemek için algoritma.

Bu algoritma, asansörün boş olana kadar mevcut yönünde (yukarı veya aşağı) hareket etmeye devam ettiği, yalnızca bireyleri inmek veya aynı yöne giden yeni bireyleri almak için durduğu bir bina asansörünün davranışından sonra adlandırılır .

Uygulama açısından bakıldığında, sürücü , talebin ilişkili silindir numarası ile birlikte bekleyen okuma/yazma isteklerinin bir arabelleğini tutar . (Düşük silindir sayıları genellikle silindirin iş miline daha yakın olduğunu ve daha yüksek sayılar silindirin daha uzakta olduğunu gösterir.)

Açıklama

Sürücü boştayken yeni bir istek geldiğinde, ilk kol / kafa hareketi verileri ya depolanır silindir yönünde olacak içinde veya dışında . Ek istekler geldikçe, kol diskin kenarına ulaşana kadar isteklere yalnızca kol hareketinin geçerli yönünde hizmet verilir. Bu olduğunda, kolun yönü tersine döner ve ters yönde kalan isteklere hizmet verilir vb.

Varyasyonlar

Bu yöntemin bir varyasyonu, tüm isteklere yalnızca bir yönde hizmet verilmesini sağlar, yani, kafa diskin dış kenarına ulaştığında, başa döner ve yeni isteklere yalnızca bu yönde hizmet verir (veya tam tersi). ). Bu, "Dairesel Asansör Algoritması" veya C-SCAN olarak bilinir. Geri dönüş arama süresi boşa harcansa da, kafadan beklenen mesafe her zaman maksimum mesafenin yarısı olduğundan, ortadaki silindirlerin servis edildiği standart asansör algoritmasının aksine, bu, tüm kafa konumları için daha eşit performans sağlar. en içteki veya en dıştaki silindirlerin iki katı sıklıkta.

Diğer varyasyonlar şunları içerir:

• FSCAN
• BAK (ve C-LOOK )
• N-Adım-TARAMA

Örnek

Aşağıda hem SCAN hem de C-SCAN algoritmaları için ortalama disk arama sürelerinin nasıl hesaplanacağına ilişkin bir örnek verilmiştir.

• Bekleyen disk isteklerinin örnek listesi (parça numarasına göre listelenmiştir): 100, 50, 10, 20, 75.
• Örnekler için başlangıç ​​parça numarası 35 olacaktır.
• Listenin artan düzende sıralanması gerekecektir: 10, 20, 50, 75, 100.

Hem SCAN hem de C-SCAN, kuyruğa alınan son parçaya ulaşana kadar aynı şekilde davranır. Bu örnek için, SCAN algoritmasının şu anda daha düşük bir parça numarasından daha yüksek bir parça numarasına (C-SCAN yaptığı gibi) gittiğini varsayalım. Her iki yöntem için de, bir sonraki iz talebi ile mevcut iz arasındaki büyüklük (yani mutlak değer) farkı alınır.

• Ara 1: 50 − 35 = 15
• 2. Arama: 75 − 50 = 25
• Ara 3: 100 − 75 = 25

Bu noktada her ikisi de en yüksek (son) parça talebine ulaştı. SCAN sadece yönü tersine çevirir ve bir sonraki en yakın disk talebine hizmet eder (bu örnekte, 20) ve C-SCAN her zaman 0. ize geri döner ve daha yüksek iz isteklerine gitmeye başlar.

• Arama 4 (TARAMA): 20 − 100 = 80
• Arama 5 (TARAMA): 10 − 20 = 10
• Toplam (TARAMA): 155
• Ortalama (TARAMA): 155 ÷ 5 = 31
• Arama 4 (C-SCAN): Silindirler dairesel bir liste olarak ele alındığından 0 − 100 = 0 kafa hareketi (C-SCAN her zaman ilk parçaya geri döner)
• Arama 5 (C-SCAN): 10 − 0 = 10
• Arama 6 (C-SCAN): 20 − 10 = 10
• Toplam (C-SCAN): 85
• Ortalama (C-SCAN): 85 ÷ 5 = 17

C-SCAN algoritması kullanılarak altı arama gerçekleştirilmesine rağmen, gerçekte yalnızca beş G/Ç yapılmıştır.

analiz

Bu nedenle kol hareketi, asansör algoritmasının her iki versiyonu için her zaman toplam silindir sayısının iki katından azdır. Varyasyon, yanıt süresinde daha küçük bir varyansa sahip olma avantajına sahiptir. Algoritma da nispeten basittir.

Bununla birlikte, asansör algoritması her zaman en kısa ilk önce aramadan daha iyi değildir , bu optimuma biraz daha yakındır, ancak yanıt süresinde yüksek farklılıklara ve hatta yeni isteklere sürekli olarak mevcut isteklerden önce hizmet verildiğinde aç kalmayla sonuçlanabilir .

Optimum yanıt süresini garanti etmek için en kısa arama süresi ilk algoritmasına açlık önleme teknikleri uygulanabilir.

Ayrıca bakınız

• FCFS
• Önce en kısa arama süresi

Referanslar