İş zamanlama (CPU Scheduling)

Günümüzde neredeyse her elektronik cihazda bulunan işletim sistemi, yüklü olan donanımların denetiminden ve yönetiminden sorumlu olan yazılımdır. İşletim sistemlerinin diğer bir görevi de işlemciyi kullanmak için sırada bekleyen proseslere işlemciyi (CPU) dağıtmaktır. Bu görevi üstlenen scheduler (zamanlayıcı), bekleme sırasında bulunan proseslerden hangisinin işlemciyi kullanacağını belirler. Bu sebepten dolayı işletim sistemleri tasarlanırken dikkat edinilmesi gereken en önemli hususlardan birisi zamanlayıcı algoritmasının (CPU scheduling algorithms) verimliliğidir.

Zamanlayıcı algoritmaları preemptive (kesintili) ve nonpreemptive (kesintisiz) olmak üzere 2 farklı gruba ayrılırlar. Bu iki grup arasındaki fark, kesintisiz algoritmalarda işlemci aldığı prosesi tamamlayana kadar başka bir prosese geçmez. Kesintili algoritmalarda ise işlemci aldığı prosesi yarıda bırakıp yeni bir prosesi işleme koyabilir. Bu iki algoritmaya örnek stratejiler aşağıdaki tabloda verilmiştir.

Yukarıdaki resimde 5 ayrı prosesin (P0…P4) bekleme sırasına giriş zamanları ve işlem süreleri verilmiştir.

FIFO:

FIFO (First In First Out) yada diğer bilinen adıyla FCFS (First Come First Served) stratejisinde bekleme sırasına giren prosesler sıranın en başından seçilerek işlemciye aktarılır.

Yukarıdaki proseslerin FIFO stratejisine göre işlemciye eklenmesi:

Resimde görüldüğü üzere bekleme sırasına giren ilk proses P1’dir. Bekleme sırasından çıkarılan P1 işlemciye yüklenir ve işlemci 7 birim zaman boyunca P1’i çalıştırır.

Bu sırada geçen 1 birimlik zaman içerisinde P0, 2 birimlik zamanın ardından P3 ve 7 birimlik zamanın ardından P2 prosesleri bekleme sırasına giriş yapar. Bekleme sırasına giriş yapan her proses bu sıranın en sonuna eklenir. Oluşturulan bekleme sırası {P0, P3, P2}. P1 işlemciden çıktığı anda sırada bekleyen ilk proses, P0, işlemciye alınır.

P0 işlemciye alındıktan sonra geçen 1 birimlik zaman içerisinde bekleme sırasına P4 girer ve bu proses sıranın en sonuna eklenir. Yeni bekleme sırası {P3, P2, P4}. P1 işlemciden çıktığı anda sırada bekleyen ilk proses işlemciye alınır, P3.

Önceki adımlarda olduğu gibi işlemci sırada bekleyen prosesleri işlem süreleri boyunca çalıştırmaya devam eder.

Proseslerin ortalama bekleme süreleri:

Ortalama bekleme süresi hesaplanırken proseslerin geliş zamanı ve işlemciye alınış zamanları göz önünde bulundurulur.

Bekleme zamanı hesaplama (1 kare = 1 zaman birimi):

0 numaralı prosesin bekleme sırasına giriş yapması gereken zaman proses tablosunda görüldüğü üzere 1. birim zamandır ancak P0’ın işlemciye giriş zamanı 6 birim zaman gecikmiştir. Bu sebepten dolayı P0’ın bekleme süresi 6 birim zaman olarak kaydedilir.

P1’in bekleme sırasına giriş ve işlemciye giriş zamanları aynı olduğu için P1 de herhangi bir gecikme söz konusu olmamıştır. Bu sebepten dolayı gecikme zamanı 0 olur.

Proses 3’ün işlemciye alınma zamanı tabloda 2 olarak verilmiştir ancak oluşan gecikmeden ötürü P3 işlemciye 12. birim zamanda girmiştir. P3′ ün bekleme süresi 12-2 = 10 birimdir.

Bu şekilde işlemciye giren her prosesin bekleme süresi toplanır ve aritmetik ortalamaları alınır:

(6+0+8+10+9) / 5 = 6.6 birim bekleme

LIFO:

LIFO (Last In First Out) stratejisi FIFO stratejisi ile neredeyse aynı prensipte çalışır. Aradaki tek fark FIFO’da bekleme sırasına giren prosesler, sıranın başından alınırken LIFO’da bekleme sırasının en sonundaki proses işlemciye alınır.

Aynı örnekteki proseslerin LIFO stratejisine göre işlemciye aktarılması:

FIFO stratejisinde olduğu gibi LIFO stratejisi için de bekleme sırasına giren ilk proses P1’dir.

İşlemci P1’i 7 birim zaman boyunca çalıştırdığı sırada bekleme sırasına P0, P3 ve P2 prosesleri girerler, Bekleme sırası = {P0, P3, P2}. LIFO’ yu FIFO’ dan ayıran nokta burada başlamaktadır. FIFO stratejisinde P0 işlemciye alınırken LIFO’ da bekleme sırasındaki en son proses işlemciye yüklenir, yani P2.

P2’nin işlemcide geçirdiği 1 birimlik zamanın ardından bekleme sırasına yeni bir proses eklenir, P4.

Yeni bekleme sırası = {P0, P3, P4}. P2′ nin ardından işlemciye yeni girecek proses LIFO stratejisinde P4 olur, çünkü P4 bekleme sırasının en sonunda olan prosestir.

İşlemci 5 birim zaman boyunca P4’ü çalıştırır ve ardından sırada bekleyen diğer proseslerden en sondakini seçer, yani P3’ü.

P3’ün ardından son olarak P0 işlemciye alınır.

Ortalama bekleme süresi hesaplama:

LIFO stratejisinde ortalama bekleme süresi FIFO stratejisinde olduğu gibi hesaplanır.

P0 = İşlemciye 1. birim zamanda girmesi gereken P0 işlemciye 16 birim zaman geç girmiştir.

P1 ve P2 işlemciye giriş zamanları ile bekleme sırasına giriş zamanları aynı olduğu için bu iki prosesin herhangi bir gecikme süresi olmamıştır.

Aynı şekilde P3 ve P4 için bekleme süreleri hesaplanır ve toplam sürenin aritmetik ortalaması alınır.

SPT:

SPT(Shortest Processing Time) stratejisinde, bekleme sırasında bekleyen proseslerin işlem süreleri baz alınarak işlemciye aktarılır. (bu stratejinin oluşturulabilmesi için proseslerin işlem sürelerinin BİLİNMESİ zorunludur.)

Örnekte verilen proses tablosundaki işlemcilerin SPT stratejisi ile işlemciye alınması:

Proseslerin geliş zamanlarına bakıldığında 0. birim zamanda gelen ilk ve tek proesesin P1 olduğu görülür. Bu sebepten dolayı P1 direkt işlemciye aktarılır.

İşlemci P1′ i çalıştırırken 1 birim zamanın ardından P3, 2 birim zamanın ardından P2 ve 6 birim zaman sonrasında P4 prosesleri giriş yapar, bekleme sırası {P3, P2, P4}.

P1 işlemciyi terk ettiği anda işlemciye yüklenecek diğer proses bekleme sırasındaki en düşük işlem süresine sahip olan proses olacaktır. P3, P2 ve P4′ ün işlem süreleri karşılaştırıldığında en düşük işlem süresine sahip olan P4 bekleme sırasından çıkarılıp işlemciye aktarılır.

Ardından biraz önce olduğu gibi kalan diğer 2 prosesin bekleme süreleri karşılaştırlır ve bu süreye göre P2 prosesi bekleme sırasını terk eder.

Son olarak bekleme sırasında kalan son proses P3 işlemciye yönlendirilir.

Ortalama bekleme süresi hesaplama:

Diğer stratejilerde olduğu gibi SPT stratejisindede proseslerin toplam bekleme süreleri bulunur ve bu sürenin aritmetik ortalaması alınır.