Blog

Completely Fair Scheduler

Completely Fair Scheduler (Tamamen Adil Zamanlayıcı)

Merhaba !

CSF linux çekideğinin varsayılan zamanlayıcısı olan bir işlem zamnlayıcısıdır. CPU kaynak tahsisini yönetir ve performansı en üst düzeye çıkarmayı amaçlarken genel CPU kullanımını en üst düzeye çıkarmayı da amaçlamaktadır. CFS’nin yazarı Ingo Molnar’a göre, çekirdek tasarımı tek cümlede özetlenebilir: “CFS temel olarak gerçek donanım üzerinde ‘ideal, kesin bir çok görevli CPU’ modelliyor”.İdeal çok görevli CPU: Aynı anda birden fazla işlemi çalıştıran, işlem yapan ve her bir işlemciye eşit miktarda işlemci gücü veren bir donanım işlemcisidir.(Eşit zaman değil, Eşit güç)

 

CPU ve Belleğin sanallaştırılmasıyla gerçekleştirilir.

CPU sanallaştırması birden fazla süreç için CPU’nun paylaştırılmasıyla gerçekleştirilir.

Zamanlama algoritması için kullanılan veri yapısı, düğümerin özel zamanlama yapılarının olduğu kırmızı-siyah bir ağaçtır.

Her işlem için bir “maksimum işlem süresi” hesaplanır.Maksimum işlem süresi bir işlemin ideal işlemcide yürütülmesini beklediği zamandır.

 

Zamanlayıcı yeni bir işlemi çalıştırmak için çalıştırıldığında zamanlayıcının çalışması;

  1. Zamanlama ağacının en solundaki düğüm seçilir.Yani en düşük yürütme/işlem süresine sahip olan yürütülmek üzere CPU’ya gönderilir.
  2. İşlem yalnızca yürütme tamamlanırsa sistemden ve zamanlama ağacından kaldırılır.
  3. Süreç maksimum yürütme süresine ulaşırsa veya başka bir şekilde durdurulursa (istemli veya kesme ile) yeni yürütme süresine göre tekrar ağaç üzerinde konumlandırılır.
  4. Yinelemeli olarak en soldaki düğüm tekrar ağaçtan seçilir.

Source-Code : https://elixir.bootlin.com/linux/latest/source/kernel/sched/fair.c

 

Linux Completely Fair Scheduler – Cleanest Mink

Kırmızı-Siyah Ağaçları (Red Black Trees)

Veriyi ağaçta tutarken ağacın dengeli olmasını (balance) olmasını sağlayan bir algoritmadır.Algoritma veri tutma yöntemi şekli sayesinde arama, ekleme, silme gibi temel işlemleri x elaman için en kötü logx zamanda yapmaktadır.

Kırmızı-Siyah ağaçlarda herhangi bir düğümün solunda kendisinden küçük bir düğüm ve herhangi bir düğümün sağında ise kendisinden büyük verilerin bulunduğu bir düğüm olması gereklidir.

İsmindende anlaşıldığı üzere her düğüm bir renk değeri tutmaktadır.

Ağaçtaki herbir düğümün sahip olması ve uyması gereken bazı kurallar/özellikler vardır.

  1. Her düğüm bir renk ifadesine sahip olmalıdır. (kırımızı veya siyah.)
  2. Root Node (Kök) her zaman siyahtır.
  3. Yapraklar (Leaf Nodes)herzamanda siyahtır.
  4. Kırmızı bir düğümün tüm çocukları siyahtır.
  5. Root Node başlayarak herhangi bir yoldan Leaf Node’a kadar gidilen yolların hepsinde siyah düğüm sayısı eşit olmak zorundadır.

 

Ağaçlar (Trees)

Ağaçlar en önemli veri tutma yöntemlerinden birisidir.Bu yöntemde gerçek bir ağacın yapısında olduğu gibi veriler benzer şekilde tutulmaktadır. (Kök, Gövde, Yapraklar.)

 

Bu ağaç yapısı 7 adet düğümden (Node) oluşmakta ve yapraklarında 4 adet düğüm (Leaf Node) bulunmaktadır.

10 numaralı düğüm kök düğüm yani Root Node olarak ifade edilir.

6, 8, 15, 21 numaralı düğümler yaprak düğümler yani Leaf Node olarak ifade edilmektedir.

Herbir düğümün solunda kendisinden daha büyük veri olamaz ve aynı şekilde herbir düğümün sağında kendisinden daha küçük bir veri tutulamaz.

Veriler bu belirlenen yönteme göre sıralanmıştır ve bu sayede veri erişiminde avantaj sağlamaktadır.

 

 

Düğümlerin seviyeleri ;

0.Seviye Düğümler : 10
1.Seviye Düğümler : 6 – 18

2.Seviye Düğümler : 4 – 8 – 15 – 21

Yukarıda seviyeleri belirtilen (Level) ve resimde detaylarıyla görülen ağacın derinliği (depth) 2’dir.

Ayrıca her bir düğümün yalnızca 2’şer alt düğüme bağlantılı olması nedeniyle bu ağaç yapısı Binary Tree yani “İkili Ağaç” olarak adlandırılmaktadır.

NOT:

İkili Ağaç Özellikleri (Features of Binary Tree’s)

  • Her düğüm benzersiz bir anahtar içerir.
  • Sol altta kalan düğümler ana düğümden mutlaka daha küçük değerlere/verilere sahiptir.
  • Sağ altta kalan düğümler ana düğümden mutlaka daha büyük bir değerlere/verilere sahiptir.

SJF Algoritması (Shortest Job First – En Kısa İş İlkönce)

SJF bir zamamlama algoritmasıdır.

Elde bulunan processler işlenmek üzere, tamamen bitirilmesi için gereken sürelerine göre işlem sırasına alınmaktadır.İşlem süresi en kısa olan process’e öncelik verilir ve CPU tarafından işleme alınır.Daha sonrasında da bu sıra takip edilerek sürekli olarak en kısa süreye sahip olan süreç işleme alınmaktadır.

SJF kesintisiz bir zamanlama algoritması olması nedeniyle bir süreç işleme alındığı zaman başka bir süreç araya giremez, kesme yapılarak sürecin işlenmesi durdurulup başka bir sürecin işlenmesi aşamasına geçilemez.
İşleme alınan süreç tamamlandıktan sonra sıradaki süreç işlenmek üzere alınır ve aynı şekilde süreç işlemesi bitirilene kadar kesilemez ve araya girilemez.

SJF Algoritmasının mantığı/amacı sürekli en kısa sürecek olan işi yaparak işlenen process sayısını artırarak performans elde etmektir.Fakat her durumda iyi bir performans elde edildiği söylenemez.

Bu algoritmada en çok karşılaşılan problem kıtlık (starvation) adı verilen durumdur.

Şöyle ki;

İşlem Numarası

Süre

1

4

2

5

3

6

4

8

 

Yukarıdaki tabloda verilen süreçleri işlenme sürelerine göre sıraladığımızda öncelik 1. süreçte olacak ve işleme alınacaktır. 1. Süreç işlenirken yeni bir süreç kuyruğa eklenirse ve işleme süresi 2. 3. ve 4. süreçten daha kısa ise 2. süreç işlenmeden yeni gelen süreç işleme alınacaktır.Bunun bu şekilde sürekli hale gelmesi deme 2, 3 ve 4. süreçler için kıtlık demektir.Yani 2, 3 ve 4. süreçlere çok geç sıra gelmesi veya hiç sıra gelmemesi durumu söz konusudur.

FIFO : İlk giren önce çıkar algoritması
Kesintisiz bir zamanlama algoritmasıdır.

İşlemci tarafında işleme alındığı zaman kesmeye uğramaz.Proces bitirilene kadar çalışır ve

sonlandırılır.
Araya başka processler giremez.

LIFO : Son giren önce çıkar algoritması

Round Robin : Sırası gelen işlem işlemcide işi bitmese bile belirlenen süre dolduysa işlem bitmeden CPU’dan çıkarılır.

Kıtlık (starvation) yaşanması olası bir durum değildir.

Fair Share Scheduling : Adil paylaşımlı zamanlama
Örn//: 4 kullanıcı varsa CPU’yu %25’er olarak ayırır ve paylaştırı.
Gruplara ayrılan alanlarda grup içerisindeki kullanıcı sayısına göre bu oranlama local olarak yeniden yapılır.
Yani 4 grup varsa bir gruba %25’lik bir CPU düşer ve herbir grupta 5 kişi varsa herbir kullanıcıya %5’lik bir CPU ‘alanı düşmektedir.

Banker Algoritması : Üç durumu ve iki şartı olan bir algoritma.
Özellikler;

1) Her işlem ne kadar kaynağa ihtiyaç duyuyor?

2) Herbir işlemin elinde tuttuğu ne kadar kaynak var?
3) Ulaşılabilir olan ne kadar kaynak mevcut ?

Şartlar;

1) Talep edilen kaynak azami kaynaktan fazla ise kaynak verilmez.
2) Talep edilen kaynak elde var olan kaynaktan fazla ise, kaynak boşa çıkana işlem bekletilir.

 

 


 

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir