İşletim Sistemi Planlama algoritmaları
Bir İşlem Planlayıcı, belirli programlama algoritmalarına dayalı olarak CPU'ya atanacak farklı işlemleri planlar. Bu bölümde tartışacağımız altı popüler süreç çizelgeleme algoritması vardır -
- İlk Gelen, İlk Hizmet Verilen (FCFS) Planlama
- En Kısa İş Sonraki (SJN) Planlama
- Öncelikli Planlama
- Kalan En Kısa Süre
- Round Robin (RR) Çizelgeleme
- Çok Seviyeli Kuyruk Planlama
Bu algoritmalar ya non-preemptive or preemptive. Önleyici olmayan algoritmalar, bir işlem çalışma durumuna girdiğinde, ayrılan süreyi tamamlayana kadar ön işlemden geçirilemeyecek şekilde tasarlanırken, önleyici programlama önceliğe dayanır; süreç hazır duruma girer.
İlk Gelen İlk Servis (FCFS)
- İşler önce gelen ilk hizmet esasına göre yürütülür.
- Önleyici olmayan, önleyici bir programlama algoritmasıdır.
- Anlaması ve uygulaması kolay.
- Uygulanması FIFO kuyruğuna dayalıdır.
- Ortalama bekleme süresi yüksek olduğu için performansta zayıf.
Wait time her işlemin aşağıdaki gibidir -
İşlem | Bekleme Süresi: Hizmet Süresi - Varış Saati |
---|---|
P0 | 0 - 0 = 0 |
P1 | 5-1 = 4 |
P2 | 8-2 = 6 |
P3 | 16 - 3 = 13 |
Ortalama Bekleme Süresi: (0 + 4 + 6 + 13) / 4 = 5.75
Sonraki En Kısa İş (SJN)
Bu aynı zamanda shortest job firstveya SJF
Bu, önleyici olmayan, önleyici bir programlama algoritmasıdır.
Bekleme süresini en aza indirmek için en iyi yaklaşım.
Gerekli CPU zamanının önceden bilindiği Batch sistemlerinde uygulanması kolaydır.
Gerekli CPU zamanının bilinmediği etkileşimli sistemlerde uygulanması imkansızdır.
İşlemci, işlemin ne kadar zaman alacağını önceden bilmelidir.
Verilen: İşlem tablosu ve Varış zamanı, Yürütme zamanı
İşlem | Varış zamanı | Uygulama vakti | Servis zamanı |
---|---|---|---|
P0 | 0 | 5 | 0 |
P1 | 1 | 3 | 5 |
P2 | 2 | 8 | 14 |
P3 | 3 | 6 | 8 |
Waiting time her işlemin aşağıdaki gibidir -
İşlem | Bekleme süresi |
---|---|
P0 | 0 - 0 = 0 |
P1 | 5-1 = 4 |
P2 | 14-2 = 12 |
P3 | 8-3 = 5 |
Ortalama Bekleme Süresi: (0 + 4 + 12 + 5) / 4 = 21/4 = 5.25
Öncelik Tabanlı Planlama
Öncelikli programlama, öncelikli olmayan bir algoritmadır ve toplu iş sistemlerindeki en yaygın programlama algoritmalarından biridir.
Her işleme bir öncelik atanır. En yüksek önceliğe sahip süreç, ilk önce yürütülmelidir.
Aynı önceliğe sahip işlemler ilk gelen alır esasına göre gerçekleştirilir.
Önceliğe, bellek gereksinimlerine, zaman gereksinimlerine veya diğer herhangi bir kaynak gereksinimine göre karar verilebilir.
Verilen: İşlem tablosu ve bunların Varış zamanı, Yürütme zamanı ve önceliği. Burada 1'in en düşük öncelik olduğunu düşünüyoruz.
İşlem | Varış zamanı | Uygulama vakti | Öncelik | Servis zamanı |
---|---|---|---|---|
P0 | 0 | 5 | 1 | 0 |
P1 | 1 | 3 | 2 | 11 |
P2 | 2 | 8 | 1 | 14 |
P3 | 3 | 6 | 3 | 5 |
Waiting time her işlemin aşağıdaki gibidir -
İşlem | Bekleme süresi |
---|---|
P0 | 0 - 0 = 0 |
P1 | 11-1 = 10 |
P2 | 14-2 = 12 |
P3 | 5-3 = 2 |
Ortalama Bekleme Süresi: (0 + 10 + 12 + 2) / 4 = 24/4 = 6
Kalan En Kısa Süre
En kısa kalan süre (SRT), SJN algoritmasının önleyici versiyonudur.
İşlemci, tamamlanmaya en yakın işe tahsis edilir, ancak tamamlanması daha kısa olan daha yeni bir hazır iş tarafından önceliklendirilebilir.
Gerekli CPU zamanının bilinmediği etkileşimli sistemlerde uygulanması imkansızdır.
Genellikle kısa işlerin tercih edilmesi gereken toplu ortamlarda kullanılır.
Round Robin Zamanlama
Round Robin, önleyici süreç çizelgeleme algoritmasıdır.
Her işlemin yürütülmesi için bir düzeltme süresi sağlanır, buna quantum.
Bir işlem belirli bir süre boyunca yürütüldüğünde, önceden alınır ve diğer süreç belirli bir süre boyunca yürütülür.
Bağlam değiştirme, önceden alınmış işlemlerin durumlarını kaydetmek için kullanılır.
Wait time her işlemin aşağıdaki gibidir -
İşlem | Bekleme Süresi: Hizmet Süresi - Varış Saati |
---|---|
P0 | (0 - 0) + (12 - 3) = 9 |
P1 | (3-1) = 2 |
P2 | (6 - 2) + (14 - 9) + (20 - 17) = 12 |
P3 | (9 - 3) + (17 - 12) = 11 |
Ortalama Bekleme Süresi: (9 + 2 + 12 + 11) / 4 = 8.5
Çok Seviyeli Kuyruk Planlama
Çok seviyeli kuyruklar, bağımsız bir programlama algoritması değildir. Ortak özelliklere sahip işleri gruplamak ve programlamak için diğer mevcut algoritmalardan yararlanırlar.
- Ortak özelliklere sahip işlemler için birden çok kuyruk tutulur.
- Her kuyruğun kendi programlama algoritmaları olabilir.
- Her kuyruğa öncelikler atanır.
Örneğin, CPU'ya bağlı işler bir kuyrukta ve tüm G / Ç bağlantılı işler başka bir kuyrukta programlanabilir. İşlem Zamanlayıcı daha sonra dönüşümlü olarak her bir kuyruktan işleri seçer ve bunları kuyruğa atanan algoritmaya göre CPU'ya atar.