Kesintisiz algoritmaların yanı sıra kesintili algoritmaların olduğundan ve kesintili algoritmalar da işlemcinin bir işi bitirmeden diğer işe geçebileceğinden bahsetmiştik. Bugün iki farklı kesintili algoritmanın çalışma prensibini inceleyeceğiz. Okumak için: iş zamanlama (CPU Scheduling). İnceleyeceğimiz algoritmalar: SRPT ve Round Robin.
SPT Algoritmasının kesintili versiyonu olan SRPT Algoritmasında, bekleme sırasında bulunan proseslerden işlem süresi en düşük olan proses işleme konulur. Bir örnek ile açıklayacak olursak:
Yukarıdaki tabloda 5 farklı prosesin bekleme sırasına giriş zamanları ve toplam işlem süreleri verilmiştir. Verilen tabloya göre ilk prosesin geliş zamanı 0’dır. Aynı zamanda bekleme sırasına giren başka bir proses olmadığı için P0 bekleme sırasından alınarak direkt olarak işleme konulur.
Bir birim zamanın ardından bekleme sırasına P1 prosesi girer(Bekleme sırası: {P1}). Ardından P0′ ın ve P1′ in işlem süreleri karşılaştırılır. P0 bir birim saniye işlendiği için yeni işlem süresi 8-1 = 7 birim zamandır, P1′ in işlem süresi ise sadece 4 birim zamandır. SRPT kesintili bir algoritma olduğu için, P0 prosesi duraklatılır, bekleme sırasına alınır ve yerine P1 prosesi işlenmek üzere beklenme sırasından alınarak işlemciye aktarılır (Yeni bekleme sırası: {P0}).
Aradan geçen 1 birim zamanın ardından bekleme sırasına yeni bir proses, P2, girer(Yeni bekleme sırası: {P0,P2}) ve tekrardan işlem süreleri karşılaştırılır. P1′ in yeni işlem süresi 4-1 = 3 birim zaman iken P2’nin işlem süresi 9 birim zamandır. Bu sebepten P2 bekleme sırasında bekletilir ve P1 işlenmeye devam eder. Bir birim süre ardından bekleme sırasına P3 girer (Yeni bekleme sırası:{P0,P2,P3}). P1’in işlem süresi P3’ün işlem süresinden daha az olduğu için P1 işlenmeye devam eder. P3’ten sonra bekleme sırasına giren P4’ün işlem süresiyle P1’in işlem süreleri karşılaştırılır. P1’in daha düşük işlem süresine sahip olmasından dolayı P1 işlemcideki yerini korur ve P4 bekleme sırasına alınır. Toplam 4 birim zamanın ardından P1 işlem süresini doldurmuştur. Bu sebepten P1 işlemciyi terkeder. Sahip olunan diğer prosesler (P0, P2, P3 ve P4) bekleme sırasında işlenmeyi beklemektedirler. İşlemciye alınacak bir sonraki proses tekrar işlem süresine göre seçilir. Bekleme sırasında bekleyen proseslerin işlem süreleri: P0 = 7, P2 = 9, P3 = 5 ve P4 = 3 birim zaman. Bu proseslerin içerisinden işlem süresi en düşük olan P4 işlemciye alınır ve işlenir.
Bekleme sırasına girecek başka bir proses olmadığı için bu adımdan sonra işlemciye sırasıyla işlem süresi en düşük olan proses alınır. Bunlar sırasıyla P3, P0 ve P2′ dir.
Round Robin Algoritması
Round robin kesintili algoritmasında, işlemciye alınan prosesler “Quantum-süresi” boyunca işlenir. Ardından bu proses duraklatılarak bekleme sırasında bekleyen diğer proseslerden birisi işleme alınır.
Yukarıda verilen tablodaki 4 prosesin Round Robin algoritmasına göre işlemciye alınmaları:
Quantum süresi 3 olsun:
Proseslerin bekleme sırasına giriş zamanları göz önünde bulundurulduğunda, P1′ in ilk geldiği gözlemlenir. P1 ile aynı anda başka bir proses bekleme sırasına girmediği için P1 işlemciye alınır.
Quantum-süresinin 3 birim olmasından dolayı, P1 3 birim zaman boyunca işlenir ve ardından duraklatılır. Geçen 3 birimlik zamanının ardından bekleme sırasına P2, P3 ve P4 prosesleri girer(Yeni bekleme sırası: {P2,P3,P4}). P1, 3 birimlik işlenme zamanının ardından duraklatıldığı için, P1 bekleme sırasının en sonuna konulur(Yeni bekleme sırası: {P2,P3,P4,P1}). Bekleme sırasında bekleyen ilk proses, P2, işlemciye alınır ve Quantum-süresi boyunca işlem görür.
3 birim zaman ardından P2 işlemciden çıkarılarak bekleme sırasının en sonuna eklenir. Bu şekilde P3, P4 prosesleri de işlemciye alınır, 3 Quantum-süresi boyunca işlenir ve tekrar bekleme sırasının sonuna eklenir.
İşlem süresi sadece 3 birim zaman olan P3 ilk işlenmenin ardından işlem süresini tamamladığı için, tekrardan bekleme sırasına eklenmez. Bu şekilde prosesler işlem süreleri tamamlanana kadar 3 Quantum-zaman birimi boyunca çalıştırılır.
Kalan proseslerin işlemciye alınışları:
P4 bekleme sırasının en sonuna eklendikten sonra sırada bekleyen ilk proses olan P1 işlemciye alınır.
3 birim Quantum-süresinin ardından P1 bekleme sırasına geri konulur ve bir sonraki proses işleme alınır.
Aynı şekilde, işlem süreleri tamamlanana kadar bekleyen prosesler işlemciye alınır.
Son olarak üç adet ek bilgi:
- Round Robin Algoritması’ nda Quantum süresi olarak ∞ süre seçilirse Round Robin-Algoritması kesintisiz bir algoritma olan FIFO-Algoritması ile aynı prensipte çalışır.
- Kesintili algoritmalar da proseslerin duraklatıldığı bilgisini edindik. Ancak bu duraklama 1-2 saniye gibi büyük bir zaman dilimi içerisinde gerçekleşmez. Bu duraklatılmalar milisaniyelerden de kısadır. Aynı zamanda işlenilen bir proses duraklatılıp tekrar işlemciye alındığında en baştan değil, duraklatıldığı noktan devam ettirilir. Bu sebepten proseslerin duraklatıldığını ek ekipmanlar olmadan anlamak mümkün değildir.
- Algoritmaların ortalama bekleme süreleri kesintisiz algoritmaların bekleme süreleri ile aynı şekilde hesaplanır.