Finale Doğru

Final semaforlardan başlamakta ancak semaforların mantığını anlamak adına semaforların gerekçelerini aşağıda okuyacağınız senkronizasyon başlığı altıda öğrenebilirsiniz.

Proses Senkronizasyonu (Process Synchronization)

Beraber çalışan ve veri paylaşan prosesler maalesef beklendiği gibi düzgün çalışmayabilir. Bunun nedenleri kendi içerinde yapmış oldukları senkronizasyonun başarısız kalmasından kaynaklanır. Ayrıca işletim sisteminden kaynaklanabilecek bir etkide proseslerin senkronizasyonlarının bozulmasına neden olabilmektedir. Tampon bellek kullanarak yapılan senkronizasyon işlemleri; sınırlı uzunlukta bellek yüzünden bizi çözüme götürmek yerine daha büyük problemlerle karşılaşmamıza neden olmaktadır. Öyleyse proseslerin ahenk içinde çalışabilmesini sağlayacak bir senkronizasyon yapısının geliştirilmesi gereklidir.

Sınırlı Buffer (Bounded-Buffer)

İki prosestede aşağıdaki kodlar bulunmaktadır. Özetle paylaşılan bölge diyebiliriz;

#define BUFFER_SIZE 10 // bufferimizin boyutunu belirliyoruz
typedef struct {
 // ... bufferimizde saklayacağımız nesnelerin yapısını oluşturuyoruz.
} item; // bu yapıya item adını veriyoruz

item buffer[BUFFER_SIZE]; // item yapısından oluşan ve BUFFER_SIZE kadar alandan oluşan bir dizi tahsis ediyoruz.
// BUFFER_SIZE yerine direkt 10'da yazabilirdik buradaki amaç eğer birden fazla BUFFER_SIZE verisi kullanılacaksa derleyiciye iş bindirerek kendi işimizi kolaylaştırmak
// BUFFER_SIZE bir macrodur. Macrolar hakkında bilginiz yoksa https://gcc.gnu.org/onlinedocs/cpp/Macros.html adresinden okumanızı öneririz.

int in = 0; // buffere kaydedilmiş son verinin indexi
int out = 0; // bufferden okunuş son verinin indexi
int counter = 0; // bufferdeki veri sayısı

Üretici prosesinde olması gereken kodlar;

item nextProduced; // üretilmiş veri
while(1) { // sonsuz döngü içerisinde yazıyoruz
    while(counter == BUFFER_SIZE); // eğer üretilen verilerin sayısı bufferimize eşitse prosesimizin bu döngüde sıkışıp kalmasını sağlıyoruz. while(1); yazmak gibi kodumuz sürekli aynı yerde kalacaktır. Eğer BUFFER_SIZE ile üretilen veri sayısı eşit değilse kodlar çalışmaya devam edecektir.
    buffer[in] = nextProduced; // üretilmiş verimizi bufferimize yerleştiriyoruz.
    in = (in + 1) % BUFFER_SIZE; // giriş sayısını bir arttırıyoruz ve buffer boyutumuza göre modunu alıyoruz. Bu sayede in değişkenimiz ne olursa olsun 0 ile 9 arasında yer alacak.
    counter++; // Üretilen veri sayısını bir arttırıyoruz.
}

Tüketici prosesinde olması gereken kodlar;

item nextConsumed; // tüketilecek veri
while(1) {
    while(counter == 0); // eğer üretilmiş hiçbir veri yoksa burada durmasını ve ilerdeki kodların çalışmamasını sağlıyoruz.
    nextConsumed = buffer[out]; // tüketilecek veriyi bufferden alıyoruz.
    out = (out + 1) % BUFFER_SIZE; // okuduğumuz son verinin indexini bir arttırıyoruz ve BUFFER_SIZE'e göre modunu alıyoruz.
    counter--; // bufferdeki verinin bir tanesini okuduğumuz için bufferdeki veri sayısını bir azaltıyoruz.
}

Bu aşamada counter değişkeni kilit noktadır. counter++ ve counter-- işlemleri yapılırken işlemin ortasında işletim sistemi procesin çalışmasını durdurur ve başka prosese odaklanırsa bu aşamada odaklanan proses counter ile ilgili bir işlem yaparsa tüm yazmış olduğumuz bu algoritma çöp olacak ve ölümcül sonuçlar ortaya koyabilecektir.

Bu yüzden counter++ ve counter-- işlemleri atomik yani yarıda kesilemez olmalıdır. Bu işlemler risc işlemci mimarisinde 3 farklı makine koduyla üretilir. counter++ için makine kodları sırasıyla;

  • Bellekten counter değişkenin değerini akumulatore yükle (LD A, [COUNTER])
  • Akumulatorun değerini bir arttır. (INC A)
  • Akumulatorun değerini belleğe yaz (STR A, [COUNTER])

Eğer bu 3 işlem sırasında Akumulatorun değeri belleğe yazılmadan, başka bir process tarafından counter değeri değiştirilirse. Hatalı sonuçlar elde edilecektir. Bunula ilgili bir örnek aşağıda yapalım. Tüketici ve üreticinin akümülatör verilerini karıştırmamak için A ve B olarak ayırıyoruz.

(counter = 5)
üretici: LD A, [COUNTER] (A = 5)
üretici: INC A (A = 6)
----- kesme
tüketici: LD B, [COUNTER] (B = 5)
tüketici: DEC B (B = 4)
----- kesme
üretici: STR A, [COUNTER] (counter = 6)
tüketici: STR B, [COUNTER] (counter = 4)

Yukarıda da görüldüğü gibi atomik yapıda olmayan counter arttırma ve azaltma işlemleri bozulmaya neden olmaktadır. üretici counteri 6 yapmış ancak tüketici çalıştığında 4 olarak atamış bir verinin kayıp olmasına neden olmuştur.

Race Condition (Yarış Koşulu): Aynı anda paylaşılan veriyi değiştirmek istenmesine yarış koşulu denir. Çeşitli işlemlerde erişim durumu ve aynı zamanda paylaşılan veriyi işlemek paylaşılan verinin son değeri hangi prosesin sonra bittiğine bağlıdır. Bu problemin kalkması için senkronizasyon başarılı ile yapılması gerekir.

The Critical-Section Problem (Kritik Bölge Problemi): N adet farkı proses paylaşılan veriyi kullanıyorsa, her prosesin içerisindeki paylaşılan veri değişkenine erişildiği kod segmenti kritik bölgedir. Bir proses kendi kritik bölgesini icra ediyorsa diğer prosesin kritik bölgesine girmesine izin verilmemelidir.

Kritik Bölge Probleminin Çözümü:

  1. Karşılıklı Dışlama (Mutual Exclusion): Eğer bir proses kritik bölgedeyse diğeri kendi kritik bölgesine giremez.
  2. İlerleme (Progress): Kritik bölgeye girmek için bekleyen prosesler varsa, mutlaka seçilim yapıldıktan sonra sırayla girmelilerdir.
  3. Sınırlı Bekleme (Bounded Waiting): Bir proses kendi kritik bölgesine sürekli girip çıkamaz, çünkü diğerleri sonsuza kadar bekletilemez.

Geliştirilen Problem Çözümleriyle Girişimler

Problem çözümleriyle birlikte aşağıdakine benzer bir yapı geliştirmemiz gerektiğini bulduk.

while(1) {
    // entry section (kritik bölgeye giriş)
    kritik bölge
    // exit section (kritik bölgeden çıkış)
    // remainder section
}

Bir çok girişim bulunmaktadır, hepsini yazmaktansa sadece direkt olarak semaforlara geçeceğiz.

Semaforlar (Semaphores)

Semaforlar senkronizasyon için işletim sistemi tarafından sağlanmış atomik çağrı yapabilen araçlardır. Özetle önceleri yazılım yapıcıları senkronizasyon için kendi algoritmalarını geliştiriyorlardı ancak bu çaba her ne kadar iyimser olsada tüm problemleri ortadan kaldıramıyordu. İşletim sistemi atomik yani bölünemez çağrılar yapılabilmesi için bazı yapılar ortaya koydu işte semaforlar bu yapılara örnektir.

İki farklı operasyon vardır bunlar

  • wait: sayı sıfırdan küçük veya eşitse sanki while(1); yapılmışçasına kodlar ilerlemeyecektir. eğer sıfırdan büyükse 1 azaltılacak ve kodlar çalışmaya başlayacaktır.
  • signal: sayı değerini bir arttırır.
semaphore mutex; // değeri 1 olarak başlar
while(1) {
    wait(mutex);
    //kritik bölge
    signal(mutex);
}

Üstteki kodu incelersek wait(mutex) çağrısı ilk geldiğinde mutex 1 olduğu için kod bloğumuz çalışmaya devam edecek, mutex 1 azaltılacak ve 0 yapılacak. Kritik bölge çalıştırıldıktan sonra signal(mutex) çağrısıyla mutex değeri 1 arttırılacak. Kendi içerisinde senkronik bir biçimde prosesin çalışmasını sağlamış olduk.

Semaforun nasıl davranması gerektiğini yukarda öğrendik. Ancak bir mantıkla c programlama dilinde gerçekleme yapmadık. Haydi c dilinde yazılmış bir semafor örneği yapalım.

Programdan beklentimiz önce A daha sonrada B yazması ve bu işlemi sürekli tekrar etmesi. (ABABABABAB) Eğer ABB AAB şeklinde bir tekrar olursa veya BABABA şeklinde yazarsa başarısız olmuşuz demektir.

#include <stdio.h>
#include <unistd.h>
#include <sys/ipc.h>
#include <sys/sem.h>

int semaforA;
int semaforB;

#define KEY 12345 // semaforları oluştururken prosesler arasında birbirlerini tanıdıklarından emin olmak adına böyle bir key sistemi geliştirilmiştir. Bu sayede kötü niyetli gücü elinde tutmak isteyen yada hack niteliğindeki uygulamalar başka uygulamaların emafor numaralarını bilmediklerinden ötürü erişim sağlayamacaktır. Öte yandan forkla üretilmiş prosesler için bu durum gayet basittir ve sıkıntı yaratmaz.

int semGet(key_t key, int initval) { // semaforumuzu oluşturan fonksiyondur
    int id; // semafor numarasını tutacak gecici değişkenimiz

    if((id = semget(key, 1, 0700|IPC_CREAT)) < 0) { // verilen key'e göre semget çağrısı yapıyoruz
        return -1;
    }

    semctl(id, 0, SETVAL, initval); // semaforumuzun değerini initval olarak atıyoruz
    return id; // semafor numaramızı döndürüyoruz
}

void semWait(int id, int value) { // semaforu beklemeye yarar
    static struct sembuf semafor; // semaforumuzun yapısal nesnesini oluşturuyoruz. static olarak atandığından dolayı bellekte sabit bir şekilde sadece 1 tane tutulacaktır.
    semafor.sem_op = -value; // tutulan bu nesnenin sem_op değerini value kadar ayarlıyoruz. negatif bir şekilde ayarlarsak azaltma işlemi yapacaktır.
    semop(id, &semafor, 1); // semafor çağrısı yapıyoruz.
}

void semSignal(int id, int value) {
    static struct sembuf semafor; // semaforumuzun yapısal nesnesini oluşturuyoruz. static olarak atandığından dolayı bellekte sabit bir şekilde sadece 1 tane tutulacaktır.
    semafor.sem_op = value; // tutulan bu nesnenin sem_op değerini value kadar ayarlıyoruz.
    semop(id, &semafor, 1); // semafor çağrısı yapıyoruz.
}

int main() {
    semaforA = semGet(KEY, 1); // semaforunu belirtilen key ile 1 başlangıç değeriyle üretiyoruz
    semaforB = semGet(KEY + 1, 0); // semaforunu belirilen keyin 1 fazlası ile 0 başlangıç değeriyle üretiyoruz.

    int pid = fork(); // fork ile A ve B proseslerimizi oluşturalım
    if(pid == 0) { // yeni oluşturulan proses A olsun
        while(1) {
            // ilk başta A yazması gerektiğinden ötürü burada öyle bir semafor kullanmalıyızki başlangıç değeri 1 olsun, öyleyse kullanmamız gereken semafor tabiki A semaforu olacak
            semWait(semaforA, 1); // A semaforu eğer 0 dan fazlaysa kod çalışsın ve A'yı 1 azalt
            printf("A");
            semSignal(semaforB, 1); // B semaforunu 1 arttır
        }
    } else if(pid > 0) { // ana proses B olsun
        while(1) {
            // ilk A değerinin yazıldığından emin olmak adına burada kullanmamız gereken semaforun başlangıç değeri 0 olmalı bu yüzden B semaforunu kullandık.
            semWait(semaforB, 1); // B semaforu eğer 0 dan fazlaysa kod çalışsın ve B'yı 1 azalt
            printf("B");
            semSignal(semaforA, 1); // A semaforunu 1 arttır
        }

        semctl(semaforA, 0, IPC_RMID, 0); // semaforu siliyoruz
        semctl(semaforB, 0, IPC_RMID, 0); // semaforu siliyoruz.
    }

    return 0;
}

Not: Yukardaki kodun düzgün çalışmadığını düşünüyorsanız printf'lerin ardından fflush(stdout); kodunu eklemeyi deneyin. Muhtemelen stdout flush olmadığı için sırası yanlış görmektesiniz. buradan çıktısınıda görmeniz mümkün.

Çağrılar unutulabilir bu yüzden ayrı ayrı fonksiyonların işlevlerini aşağıda belirtiyorum;

  • semget semafor oluşturur. (key_t key, int nsems, int semflg) şeklinde parametreleri vardır. nsems = 1 ve semflg = 0700|IPC_CREAT olacak şekilde parametreleri ayarlarız. örneğin
int semaforA = semget(12345, 1, 0700|IPC_CREAT);
  • semop semafor için çağrı yapar. (int semid, struct sembuf *sops, unsigned nsops) şeklinde parametreleri vardır. sops'a oluşturuğumuz sembuf nesnesinin adresini veriyoruz. (sops = &semafor şeklinde) nsops = 1 olacak şekilde de bitiriyoruz. örneğin
// signal çağrısı
static struct sembuf semafor;
semafor.sem_op = 1;
semop(semaforA, &semafor, 1);
  • semctl semaforu kontrol eder, biz bu maddede yok etme amaçlı kullanacağız. (int semid, int semnum, int cmd, ...) şeklinde parametreleri vardır. Yok etmek için semnum = 0 ve cmd = IPC_RMID olmalıdır. son olarakta ... ekstra parametreleri yerine 0 ekliyoruz. örneğin
semctl(semaforA, 0, IPC_RMID, 0);
  • semctl semaforu kontrol eder dedik bu maddede semaforun değerini direkt değiştirmekte kullanacağız. bunun için parametreleri semnum = 0 ve cmd = SETVAL olmalıdır. Ekstra parametre olarak değeri yazıyoruz.
semctl(semaforA, 0, SETVAL, 2); // semaforA'nın değerini 2 yapar

Kilitlenme (Deadlock)

Bir sistemdeki çalışan bir proses (a prosesi diyelim) belirli bir kaynak talep ettiyse, ve bu kaynakta başka bir proses (b prosesi diyelim bunada) tarafından kullanılıyorsa a prosesimiz b prosesini bekleyecektir. Ancak a prosesi daha önceden bir kaynak daha almış olsun. Bu kaynakta b prosesi tarafından talep edilsin. Arz/Talep ilişkisi bir döngü haline gelecektir. İki proseste kaynakların boşalmasını bekleyecek ancak hiçbiri işini talep ettiği kaynağı alamadığı için bitiremediğinden prosesler kilitlenecektir.

Kod bazında bu işin nasıl gerçekleşebileceğini inceleyelim. Semaforların ilk değerleri 1 olarak verilsin.

// X prosesi
wait(A); // A = 0 olacaktır
-- kesme geldi
wait(B); // Kesme geldikten sonra Y prosesi çalışmış ve B'i 0 olarak atamıştır. O yüzden burada bekleyecektir.

// Y prosesi
wait(B); // B = 0 olacaktır.
wait(A); // X prosesi daha önce wait çağrısıyla A'yı 0 yaptığından ötürü burada bekleyecektir.

Gördüğünüz gibi iki proseste birbirini icra edilecek güç ve zaman olmasına rağmen sonsuza dek beklemektedir. Kilitlenmenin görünen sebebi incelerseniz kesmedir. Kesme olmasaydı X icrasını tamamlayacak Y'de işini halledebilecekti. Kesmenin geleceği kesin değildir. Bu bir olasılıktır. O yüzden kilitlenmeler olasılık bazlı hesaplanırlar.

Kilitlenmeyi anlamak için şu kriterlere bakabiliriz;

  • Karşılıklı Dışlama (Mutual Exclusion): Sadece 1 proses bir anda bir tane kaynak kullanabilir.
  • Tut ve Bekle (Hold and Wait): En azından bir kaynak kullanmakta olan bir process diğer kaynaklar tarafından kullanılan ek kaynakları edinmek için bekliyor.
  • Bırakmak Yok (No preemption): Bir kaynak ancak kendisini kullanan proses tarafından görevini tamamladıktan sonra gönüllü olarak bırakılabilir.
  • Döngüsel Bekleme (Circular wait): Döngüsel bir yapının oluşması.

Kaynak Tahsis Grafiği

Kilitlenmeleri anlamak için grafikleri kullanabiliriz. Bu sayede sistemde kilitlenme olup olmadığını dışardan görmemiz mümkündür.

Yukarıdaki grafikte bir kilitlenme yoktur. P3 çalışmaya devam edebilir.O işini tamamladığında P2, R3 kaynağını alacak ve çalışmaya başlayacak. P2 işini tamamladığında R1 ve R2 boşalmış olacak ve P1 işini yapıp bitirebilir.

Ancak grafik eğer aşağıdaki gibi olsaydı sistem kilitlenmiş olacaktı.

Döngü olmasına rağmen bazı durumlarda kilitlenme gözlenmez. Örneğin bu grafik;

P2 ve P4 işini yapacak, işleri tamamlandıktan sonra R1 ve R2 de birer boşluk olacak P1 ve P3 işlerini halledebileceklerdir.

Bu grafiklerden çıkabileceğimiz temel mantık

  • Döngü yoksa kilitlenme yok
  • Döngü varsa kilitlenme olma ihtimali vardır.

Kilitlenme olma ihtimali günümüz sistemlerinde ihmal edilmiştir. Zaman içerisinde bu problem giderek az yaşanmaya başlamış sistemler daha tutarlı çalışmaya başlamıştır. Bazı sistemlerde kilitlenmeyi incelemek için bir sistem yapılmış ancak bu kilitlenme durumunda olacaklardan daha fazla iş gücü harcadığı için geliştirmesi durmuş ölü bir teknoloji haline gelmiştir.

Banker's Algorithm

Algoritmada bir process kaynak talep ettiğine beklemek durumunda kalabilmektedir. Kaynağı aldıktan sonrada bir süre sonra iade etmelidir. Bir kaynaktan birden fazla örnek vardır. Her bir process kullanacağı kaynakları önceden belirtmelidir.

Tahsis edilmiş Maksimum Toplam Boşta Kaynak Gerekli Kaynak
ABC ABC ABC ABC
P1 010 753 332 743
P2 200 322 122
P3 302 902 600
P4 211 222 011
P5 002 433 431
TOPLAM 725

Gerekli Kaynak = Maksimum - Tahsis edilmiş

TOPLAM = Toplam tahsis edilen miktar

Bu sorularda tahsis miktarı, maksimum ve toplam kaynak verilir. Gerekli kaynak hesaplanmalıdır. Gerekli kaynak hesaplandıktan sonra sırayla prosesin çalışıp çalışmayacağını deneriz. Örneğin bu değerlerde P1 için 743 kaynak gerekir ancak 322 elimizde bulunmaktadır o yüzden çalışmayacaktır. P2 ise 122 gerektirir öyleyse P2 çalışacaktır ve Toplam boşta kaynağımız 532 olarak değişecektir çünkü P2 için tahsis edilmiş kaynaklar boşta kaynağa gelecektir.

P2 P4 P5 P1 P3 şeklinde proseslerin çalışması beklenmektedir.

Eğer sistemde hiçbir proses toplam boş kaynağı karşılayamıyorsa kilitlenmenin olduğunu anlarız. Peki kilitlenme olduğunda nasıl çözüm üretiriz? Tabi ki öldürerek Kilitlenmeye sebep olan tüm prosesler öldürülür. Tabi ki öldürülme de, öncelik, prosesin ne kadar iş yaptığı, kullandığı kaynaklar, ne kadar daha kaynağa ihtiyacı olduğu, kaç tane prosesin yok edileceği, kabukla beraber iş yapıp yapmadığı gibi durumlarında kontrol edilmesi gerektiğini unutmayalım.

Devam etmek için tıklayın