Chapter 7 : Proses Senkronizasyonu








Arka plan
Kritik Bölge Problemi
Donanımsal Senkranizasyon
Semaforlar
Klasik Problem Senkranizasyonu
Kritik Bölgeler
Monitörler
Senkranizasyon Solaris 2 ve Windows 2000
Arka plan
 Beraber çalışan ve veri paylaşan proseslerde tutarsızlık
olabilir.
 İşbirliği içindeki proseslerde veri tutarlılığını sağlamak için
mekanizma gerekebilir.
 Sınırlı tampon sorununda paylaşılan bellek(chapter-4) aynı
anda buffer da en çok n-1 ögeye izin verir.N buffer da
kullanılan çözüm basit değildir.

Değişken sayaç ekleyerek üretici-tüketici kodunu
değiştirdiğimizi varsayalım, her zaman 0 ile başlatılır ve
artan yeni bir öğe tampona eklenir
Sınırlı Buffer
 Paylaşılan veri
#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;
Sınırlı Buffer
 Üretici proses
item nextProduced;
while (1) {
while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
Sınırlı Buffer
 Tüketici Proses
item nextConsumed;
while (1) {
while (counter == 0)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
}
Sınırlı Buffer
 Durumlar
counter++;
counter--;
atomik olmalı
 Atomik işlemin anlamı kesilme olmadan icra edilmesi
demektir.
Sınırlı Buffer
 Count ++ durumu makine dilinde uygulanabilir.
register1 = counter
register1 = register1 + 1
counter = register1
 Count -- durumu makine dilinde uygulanabilir.
 register2 = counter
register2 = register2 – 1
counter = register2
Sınırlı Buffer
 Eğer üretici ve tüketici belleği aynı anda güncellemeye
çalışırsa makine dilinde durumlar iç içe geçebilir.
 İç içe geçmiş durumda proses nasıl planlanır.
Sınırlı Buffer
 Counter ın başlangıç değeri 5 olsun .Durumlar:
producer: register1 = counter (register1 = 5)
producer: register1 = register1 + 1 (register1 = 6)
consumer: register2 = counter (register2 = 5)
consumer: register2 = register2 – 1 (register2 = 4)
producer: counter = register1 (counter = 6)
consumer: counter = register2 (counter = 4)
Doğru sonucun 5 olması gereken yerde sayım değeri 4
veya 6 olabilir.
Yarış Koşulu
 Yarış koşulu: Aynı anda paylaşılan veriyi değiştirmek
istemesi yarış koşuludur. Çeşitli işlemlerde erişim
durumu ve aynı zamanda paylaşılan veriyi işlemek
paylaşılan verinin son değeri hangi prosesin sonra
bitirdiğine bağlıdır.
 Giderilmesi için birlikte çalışan prosesler senkronize
edilmelidir.
Kritik Bölge Problemi
 N adet proses paylaşılan veri kullanıyor.
 Her prosesin içindeki paylaşılan veri değişkenine
erişildiği kod segmenti kritik bölgedir.
 Problem ,bir proses kendi kritik bölgesini icra ediyorsa
diğer prosesin kritik bölgesine girmesine izin
verilmemelidir.
Kritik Bölge Çözümü
 Karşılıklı Dışlama: Eğer bir proses kritik bölgesindeyse
diğerleri kendi kritik bölgesine giremeyecek.
 İlerleme: Kritik bölgeye girmek için bekleyen prosesler
varsa ,mutlaka bir seçilip girmelidir.
 Sınırlı bekleme: Bir proses kendi kritik bölgesine
sürekli girip çıkış yapamaz ,çünkü diğerleri sonsuza
kadar bekletilemez
Sorunları Çözmek için İlk Girişimler
 Sadece 2 süreç , P0 ve P1
 Prosesin genel yapısı Pi (diğer process Pj)
do {
entry section
critical section
exit section
reminder section
} while (1);
 Süreç eylemlerini senkronize etmek için bazı ortak
değişkenler paylaşabiliriz.
Algoritma 1
 Paylaşılan değişkenler
 int turn;
initially turn = 0
 turn - i  Pi can enter its critical section
 Process Pi
do {
while (turn != i) ;
critical section
turn = j;
reminder section
} while (1);
 Proses ihlal ediliyor.
Algoritma 2
 Paylaşılan değişkenler
 boolean flag[2];
initially flag [0] = flag [1] = false.
 flag [i] = true  Pi ready to enter its critical section
 Process Pi
do {
flag[i] := true;
while (flag[j]) ;
critical section
flag [i] = false;
remainder section
} while (1);
 Karşılıklı dışlama ancak ilerleme gereksinimlerini karşılayamamaktadır.
Algoritma 3
 Algoritma 1 ve 2 deki ortak değişkenler kombine
 Process Pi
do {
flag [i]:= true;
turn = j;
while (flag [j] and turn = j) ;
critical section
flag [i] = false;
remainder section
} while (1);
 Her 3 gereksinimi karşılar iki işlem için kritik bölge problemini çözer.
Bakery Algoritması
 N tane proses için kritik bölge
 Kritik bölümüne girmeden önce, sürec bir numara
alır.Küçük sayı kritik bölümüne girer.
 Kimin önce kritik bölgesine gireceğini numara belirler.
 Numaralandırma düzeni her zaman sıralamanın artan
sipariş numaralarını oluşturur, yani, 1,2,3,3,3,3,4,5 ...
Bakery Algoritması
 Notasyon < sözlük sırası(ticket #, process id #)
 (a,b) < c,d) if a < c or if a = c and b < d
 max (a0,…, an-1) is a number, k, such that k  ai for i - 0,
…, n –
• Paylaşılan ve
boolean choosing[n];
int number[n];
Veri yapıları yanlış veya 0 olduğunda sırayla başlatılır.
Bakery Algoritması
do {
choosing[i] = true;
number[i] = max(number[0], number[1], …, number [n – 1])+1;
choosing[i] = false;
for (j = 0; j < n; j++) {
while (choosing[j]) ;
while ((number[j] != 0) && (number[j,j] < number[i,i])) ;
}
critical section
number[i] = 0;
remainder section
} while (1);
Senkranizasyon Donanım
 Atomik bir kelimen içeriğini değiştirme ve test etme
boolean TestAndSet(boolean &target) {
boolean rv = target;
tqrget = true;
return rv;
}
Test ve Set ile Karşılıklı Dışlama
 Paylaşılan data:
boolean lock = false;
 Process Pi
do {
while (TestAndSet(lock)) ;
critical section
lock = false;
remainder section
}
Senkronizasyon Donanım
 Atomically swap two variables.
void Swap(boolean &a, boolean &b) {
boolean temp = a;
a = b;
b = temp;
}
Swap ile Karşılıklı Dışlama
 Paylaşılan veri (initialized to false):
boolean lock;
boolean waiting[n];
 Process Pi
do {
key = true;
while (key == true)
Swap(lock,key);
critical section
lock = false;
remainder section
}
Semaforlar
 Senkranizasyon aracı meşgu beklemeyi gerektirmez.
 Semafor S –integer değişken
 sadece iki bölünmez (atom) işlemler üzerinden erişilebilir.
wait (S):
while S 0 do no-op;
S--;
signal (S):
S++;
N adet Prosesin Kritik Bölgesi
 Paylaşılan data :
semaphore mutex; //initially mutex = 1
 Process Pi:
do {
wait(mutex);
critical section
signal(mutex);
remainder section
} while (1);
Semafor Uygulaması
 Bir yapı olarak semafor tanımlayın
typedef struct {
int value;
struct process *L;
} semaphore;
 İki temel işlem vardır:
Blok:Çalışmakta olan prosesi bekleme
Wakeup:Beklemeden hazır kuyruğuna alma
Uygulama
wait(S):
signal(S):
S.value--;
if (S.value < 0) {
add this process to S.L;
block;
}
S.value++;
if (S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}
Genel Senkranizasyon Aracı olarak
Semaforlar
 B yi yürüt Pj içinde sonra A yürüt Pi içinde
 Semafor bayrağını 0 başlatarak kullan
 Code:
Pi
Pj


A
wait(flag)
signal(flag)
B
Kilitlenme ve Açlık
 Kilitlenme: 2 yada daha fazla prosesin bir olayın olmasını sonsuza
kadar beklemesi
 S ve Q 1 ile başlayan 2 semafor olsun
P0
P1
wait(S);
wait(Q);
wait(Q);
wait(S);


signal(S);
signal(Q);
signal(Q)
signal(S);
 Açlık :Bir şeyin sonsuz şekilde bloke edilmesi ,bir proses semafor
kuyruğundan kurtulmaz.
Semaforun 2 tipi
 Sayaç semaforlar:Tamsayı değeri kısıtlanmamış bir
etki alanı içinde uzanabilir
 Binary semaforlar:Tam sayı değeri 0 ile 1 arasında
değişir,uygulamak için basit olabilir.
 Ikili bir semafor olarak sayma semafor S
uygulayabilirsiniz.
İkili Semafor Gibi S Uygulama
 Veri Yapıları:
binary-semaphore S1, S2;
int C:
 Başlatma:
S1 = 1
S2 = 0
C = Semaforun S başlangıç değeri
Uygulama S
 operasyon bekle
wait(S1);
C--;
if (C < 0) {
signal(S1);
wait(S2);
}
signal(S1);
 operasyon sinyali
wait(S1);
C ++;
if (C <= 0)
signal(S2);
else
signal(S1);
Senkronizasyonun Klasik Sorunları
 Sınırlı Tampon Sorunu
 Okuyucular - Yazarlar Sorunu
 Yemek-Flozoflar Sorunu
Sınırlı Tampon Sorunu
 Paylaşılan veriler
semaphore full, empty, mutex;
Başlangıçta:
full = 0, empty = n, mutex = 1
Sınırlı Tampon Problemi Üretici Süreci
do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);
Sınırlı Tampon Problemi Tüketici
Süreci
do {
wait(full)
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);
Okuyucular - Yazarlar Sorunu
 Paylaşılan veri
semaphore mutex, wrt;
Başlangıçta
mutex = 1, wrt = 1, readcount = 0
Okuyucular-Yazarlar Sorunu Yazar
Süreci
wait(wrt);
…
yazma gerçekleştirilir
…
signal(wrt);
Okuyucular-Yazarlar Sorunu Okuyucu
Süreci
wait(mutex);
readcount++;
if (readcount == 1)
wait(rt);
signal(mutex);
…
okuma gerçekleştirilir
…
wait(mutex);
readcount--;
if (readcount == 0)
signal(wrt);
signal(mutex):
Yemek-Filozoflar Sorunu
• Paylaşılan veri
semaphore chopstick[5];
Başlangıçta tüm değerler 1
Yemek-Filozoflar Sorunu
 Filozof i:
do {
wait(chopstick[i])
wait(chopstick[(i+1) % 5])
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (1);
Kritik Bölgeler
 Yüksek seviyeli senkronizasyon yapısı
 T tipi bir paylaşılan v değişkeni olarak ilan edilir :
v: shared T
 Değişken v sadece deyim içinde erişilen.
region v when B do S
B’nin bir mantıksal ifade olduğu yerde.
 While ifadesinde S yürütülürken, başka bir işlem v değişkenine
erişemez.
Kritik Bölgeler
 Atıfta bölgeler paylaşılan değişkene başvurduğu
zaman birbirlerini dışlar..
 Bir süreç bölge deyimi yürütmeye çalıştığında
mantıksal B ifadesi değerlendirilir. Eğer B doğruysa, S
deyimi çalıştırılır. Eğer yanlışsa, proses B doğru hale
gelinceye kadar geciktirilen ve herhangi bir diğer
proses v ile ilişkili olan bir bölgede.
Örnek – Sınırlı Tampon
 Paylaşılan veri:
struct buffer {
int pool[n];
int count, in, out;
}
Sınırlı Tampon Yapımcı Süreci
 Paylaşılan tampona nextp yapımcı süreci ekler
region buffer when( count < n) {
pool[in] = nextp;
in:= (in+1) % n;
count++;
}
Sınırlı Tampon Tüketici Süreci
 Tüketici işlemi paylaşılan tampon bir öğeyi kaldırır ve
nextc koyar.
region buffer when (count > 0) {
nextc = pool[out];
out = (out+1) % n;
count--;
}
Uygulama Bölgesi x Zaman B S
Yapmak
 Paylaşılan x değişkeni, aşağıdaki değişkenler ile ilişkilendirmek :
semafor mutex, ikinci gecikme, birinci gecikme; int ilk sayı,
ikinci sayı;
 Kritik bölüm birbirini dışlayan erişim mutex tarafından
sağlanmaktadır.
 Eğer bir süreç kritik bölgeye giremiyorsa mantıksal B ifadesi
yanlıştır, başlangıçta ilk gecikme semafor bekler; B nin yeniden
değerlendirilmesine izin verilmeden önce ikinci gecikme semafor
taşındı.
Uygulama
 Sırasıyla ilk sayı ve ikinci sayı ile birinci gecikme ve
ikinci gecikme bekleyen işlem sayısını takip edin.
 Algoritma bir semafor için proseslerin kuyruk siparişini
bir FIFO varsayar.
 Keyfi bir kuyruk disiplini için, daha karmaşık bir
uygulama gereklidir.
Monitörler

Yüksek seviyeli senkronizasyon yapı eşzamanlı süreçler arasında bir soyut veri türü güvenli paylaşımı
sağlar.
monitor monitor-name
{
paylaşılan değişken bildirimleri
procedure body P1 (…) {
...
}
procedure body P2 (…) {
...
}
procedure body Pn (…) {
...
}
{
başlatma kodu
}
}
Monitörler
 Bir süreç monitör ile beklemesine izin vermek için bir koşul
değişkeni olarak x,y koşulu beyan edilmelidir;
 Durum değişkeni sadece bekleme ve sinyal işlemleri ile
kullanılabilir.
 Operasyon
x.wait();
başka br işlem çağırılana kadar bu işlem yürütmesi işlemini
askıya alma anlamına gelir.
x.signal();
 X.signal operasyonu tam bir süreci askıya almaya devam.
Hiçbir işlem askıya alınmazsa sinyal işleminin hiçbir etkisi
yoktur.
Bir Monitörün Şematik Görünümü
Durum Değişkenleri İle Monitör
Yemek Filozoflar Örnek
monitor dp
{
enum {thinking, hungry, eating} state[5];
condition self[5];
void pickup(int i)
// following slides
void putdown(int i) // following slides
void test(int i)
// following slides
void init() {
for (int i = 0; i < 5; i++)
state[i] = thinking;
}
}
Yemek Filozoflar
void pickup(int i) {
state[i] = hungry;
test[i];
if (state[i] != eating)
self[i].wait();
}
void putdown(int i) {
state[i] = thinking;
// test left and right neighbors
test((i+4) % 5);
test((i+1) % 5);
}
Yemek Flozoflar
void test(int i) {
if ( (state[(I + 4) % 5] != eating) &&
(state[i] == hungry) &&
(state[(i + 1) % 5] != eating)) {
state[i] = eating;
self[i].signal();
}
}
Semafor Kullanarak Monitör
Uygulama
 Değişkenler
semaphore mutex; // (initially = 1)
semaphore next; // (initially = 0)
int next-count = 0;
 Her dış prosedür F ile değiştirilecektir
wait(mutex);
…
body of F;
…
if (next-count > 0)
signal(next)
else
signal(mutex);
 Bir monitörün içinde karşılıklı dışlama sağlanır.
Monitör Uygulama
 Her koşul değişkeni x için biz sahibiz:
semaphore x-sem; // (initially = 0)
int x-count = 0;
 Operasyon x.wait olarak uygulanabilir :
x-count++;
if (next-count > 0)
signal(next);
else
signal(mutex);
wait(x-sem);
x-count--;
Monitör Uygulama
 Operasyon x.signal olarak uygulanabilir :
if (x-count > 0) {
next-count++;
signal(x-sem);
wait(next);
next-count--;
}
Monitör Uygulama
 Şartlı-bekleme yapısı: x.wait (c);
 c – bekleme işlemi çalıştırıldığında tamsayı ifade değerlendirilir.
 c değeri (bir öncelik değeri) askıya alınır işlemin adı ile birlikte
saklanır.
 x.signal çalıştırıldığında, küçük ilişkili öncelik numarası ile sonraki
işlem sürdürülür.
 Sistemin doğruluğunu kurmak için iki koşul kontrol edin :
 Kullanıcı işlemleri her zaman doğru sırayla monitör üzerindeki
görüşmeleri yapmak gerekir.
 Bir işbirliği yapmayan sürecin monitör tarafından sağlanan
karşılıklı dışlama geçidini görmezden gelip ve erişim protokollerini
kullanmadan, doğrudan paylaşılan kaynağa erişmeye
çalıştığmadığından emin olmamızı sağlar.
Solaris 2 Senkronizasyon
 Çoklu görev, çoklu iş parçacığı (gerçek zamanlı konuları dahil) ve
çoklu işlem desteklemek için çeşitli kilitler uygular.
 Kısa kod segmentleri verileri korurken verimliliği için adaptif
mutekslerini kullanır.
 Uzun kod bölümleri verilere erişim ihtiyacı olduğunda durum
değişkenleri ve okuyucu-yazar kilitleri kullanır.
 Ya bir adaptif mutekslere ya da okur - yazar kilidi elde etmek için
bekleyen konular listesini sipariş turnikeler kullanır.
Windows 2000 Senkronizasyon
 Tek işlemcili sistemlerde küresel kaynaklara erişimi
korumak için kesme maskeleri kullanır.
 Çok işlemcili sistemlerde döndürme kilitleri kullanır.
 Ayrıca muteksler ve semaforlar sindirmeye yönelik
sevkedici nesneleri sağlar.
 Sevkedici nesneler de olay sağlayabilir. Bir olay, bir koşul
değişken gibi davranır.
Download

while (1)