Isletim Sistemleri Uygulama 6 - Ninova

Transkript

İşletim Sistemleri Uygulama 6
Unix’de semafor işlemleri
Bilgisayar Mühendisliği
İstanbul Teknik Üniversitesi
34469 Maslak, İstanbul
3 Nisan 2013
BM
BLG 312
Bugün
Uygulamada adım adım semafor kullanımı
Örnek Senkronizasyon Problemleri - H2 O
Örnek Senkronizasyon Problemleri - Sushi Bar
Örnek Senkronizasyon Problemleri - Parti
Problemi
BM
BLG 312
Örnek Senkronizasyon Problemleri - Parti Problemi
Problem
Amaç, bir yazıcı denetim uygulaması yazmaktır. Sistemde sadece bir yazıcı vardır. Bu
yazıcı yazdığı her sayfaya karşılık ekrana bir karakter basacak biçimde benzetilmiştir.
Bu uygulamaya kısa zaman içinde iki ayrı belgeden yüzer tane basma görevi verilmiştir.
Her iki tür belgenin sayfaları birbirine karışmadan baskı işi kotarılmalıdır.
BM
BLG 312
Senkronizasyon olmadan
1
6
11
16
// i n t s ; // c u r r e n t l y n o t u s e d
v o i d∗ p r i n t T h i s ( v o i d∗ t y p ){
int i , j ;
c h a r∗ s t r =( c h a r ) t y p== ’ a ’ ? ” a b c d e f g h i j ” : ” 0123456789 ” ;
// C r e a t e two t y p e s o f c o n t e n t f o r p r i n t j o b s
f o r ( i =0; i <100; i ++){ // 100 s e p a r a t e p r i n t j o b s
f o r ( j =0; j <10; j ++){ // o f 10 p a g e s e a c h .
p r i n t f ( ”%c ” , s t r [ j ] ) ;
// Each c h a r a c t e r r e p r e s e n t s a page
}
}
p t h r e a d e x i t (NULL ) ;
}
i n t main ( v o i d ){
pthread t a , n ;
s e t v b u f ( s t d o u t , ( c h a r ∗)NULL ,
IONBF , 0 ) ; // no−b u f f e r
printf
// s =1; // c u r r e n t l y n o t u s e d
21
p r i n t f ( ” I ’m t h e NO−SYNC p r i n t e r manager .\ n” ) ;
// Run two t h r e a d s on p r i n t T h i s f u n c t i o n w i t h s e p a r a t e params
p t h r e a d c r e a t e (&a , NULL , p r i n t T h i s , ( v o i d ∗) ’ a ’ ) ;
p t h r e a d c r e a t e (&n , NULL , p r i n t T h i s , ( v o i d ∗) ’ n ’ ) ;
26
// Wait f o r t h e t h r e a d s t o f i n i s h
p t h r e a d j o i n ( a , NULL ) ;
p t h r e a d j o i n ( n , NULL ) ;
31
return 0;
}
BM
BLG 312
Senkronizasyon olmadan oluşan örnek çıktı
I ’m t h e NO−SYNC p r i n t e r manager .
Oh ! Two h u n d r e d j o b s a r e s u b m i t t e d , and I g o t o n l y one p r i n t e r !
3
8
13
18
23
28
abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghij
abcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabc0123456
7890123456789012345678901234567890123456789012345678901234567890123456
7890123456789012345678901234567890123456789012345678901234567890123456
78901234567890123456789012345678901234567890123456789012345 d e f g h i j a b c d
efghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcdefghijabcd
efghijabcdefghij678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789012345678901234567890123456789
0123456789012345678901234567890123456789
BM
BLG 312
Senkronizasyon denemesi
1
6
11
16
int s ;
int i , j ;
f o r ( i =0; i <100; i ++){
i f ( s >0){ // C h e c k i n g f o r t h e v a l u e o f s th en ,
s−−; // m o d i f y i n g i t t o l o c k o t h e r t h r e a d s
f o r ( j =0; j <10; j ++){
p r i n t f ( ”%c ” , s t r [ j ] ) ;
}
s ++; // U n l o c k i n g o t h e r t h r e a d s .
}
}
}
i n t main ( v o i d ){
pthread t a , n ;
21
s =1;
p r i n t f ( ” I ’m t h e DUMMY−SYNC p r i n t e r manager .\ n” ) ;
26
31
return 0;
}
BM
BLG 312
printf
Senkronizasyon denemesinde oluşan örnek çıktı
3
8
13
18
ubuntu@ubuntu : ˜ / D e s k t o p $ . / a . o u t
I ’m t h e DUMMY−SYNC p r i n t e r manager .
When a p r i n t j o b i s s u b m i t t e d ,
I c r e a t e a new t h r e a d t o p r i n t t h e s t r i n g .
Oh ! Two h u n d r e d j o b s a r e s u b m i t t e d ,
and I g o t o n l y one p r i n t e r !
a b c d e f g h i j a b c d e f g h i j u b u n t u @ u b u n t u : ˜ / Desktop$
BM
BLG 312
Başarılı senkronizasyon
1
6
11
v o i d s e m s i g n a l ( i n t semid , i n t v a l ){
s t r u c t sembuf s e m a f o r ;
s e m a f o r . sem num =0;
s e m a f o r . sem op=v a l ;
s e m a f o r . s e m f l g =1;
semop ( semid , &s e m a f o r , 1 ) ;
}
v o i d s e m w a i t ( i n t semid , i n t v a l ){
s t r u c t sembuf s e m a f o r ;
s e m a f o r . sem num =0;
s e m a f o r . sem op=(−1∗ v a l ) ;
s e m a f o r . s e m f l g =1;
semop ( semid , &s e m a f o r , 1 ) ;
}
16
21
v o i d c r e a t e S e m a p h o r e ( c h a r ∗a r g v [ ] ) {
i n t someKey = f t o k ( s t r c a t ( g e t c u r r e n t d i r n a m e ( ) , a r g v [ 0 ] ) , 1 ) ;
s = s e m g e t ( someKey , 1 , 0 7 0 0 | IPC CREAT ) ;
s e m c t l ( s , 0 , SETVAL , 1 ) ;
}
BM
BLG 312
Başarılı senkronizasyonla oluşan örnek çıktı
int s ;
4
9
14
int i , j ;
f o r ( i =0; i <100; i ++){
s e m w a i t ( s , 1 ) ; // d e c r e a s e
f o r ( j =0; j <10; j ++){
p r i n t f ( ”%c ” , s t r [ j ] ) ;
}
s e m s i g n a l ( s , 1 ) ; // i n c r e a s e
}
}
i n t main ( i n t a r g c , c h a r ∗a r g v [ ] ) {
pthread t a , n ;
19
createSemaphore ( argv ) ;
p r i n t f ( ” I ’m t h e SEM−SYNC p r i n t e r manager .\ n” ) ;
24
s e m c t l ( s , 0 , IPC RMID , 0 ) ; // D e l e t e s
29
return 0;
}
BM
BLG 312
printf
Başarılı senkronizasyon
I ’m t h e SEM−SYNC p r i n t e r manager .
Oh ! Two h u n d r e d j o b s a r e s u b m i t t e d , and I g o t o n l y one p r i n t e r !
3
8
13
18
23
28
abcdefghijabcdefghijabcdefghij0123456789abcdefghij0123456789abcdefghij
0123456789 a b c d e f g h i j 0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j 0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j 0 1 2 3 4 5 6 7 8 9
abcdefghij0123456789abcdefghij0123456789abcdefghij0123456789abcdefghij
abcdefghij012345678901234567890123456789ubuntu@ubuntu : ˜ / Desktop$
BM
BLG 312
Su(H2 O) oluşumu problemi
I
Su molekülünün oluşumunu iki tip iplik(thread) kullanarak modellemek istiyoruz
I
Molekül oluşumu için eşik değeri (enerji, sıcaklık, vs) belirlenir. Eşik değerini aşan
iplik bag() fonksiyonunu çağırır.
I
Bir ipliğin, (i+1). molekül için bag() fonksiyonunu çağırması, ancak ve ancak i.
molekülü oluşturan için üç ipliğin de bag() fonksionunu çalıştırıp tamamlamış
olması gerekir.
I
I
I
Bir O ipliği eşiğe ulaşınca hiçbir H ipliği yoksa, iki H ipliğini bekler
Bir H ipliği eşiğe ulaşınca eşikte kendisinden başka hiçbir iplik yoksa, bir H ipliği ve bir
O ipliğini beklemek zorundadır
İplikler eşiği üçlü gruplar halinde geçmektedirler. Bir grup 2 H, 1 O ipliğinden
oluşmaktadır.
Sözkonusu kısıtları sağlayan senkronizasyon adımlarını H ve O iplikleri için oluşturunuz.
BM
BLG 312
Kullanılması gereken temel bileşenler ve ilk değerleri
I
mutex = Semafor(1) Mutex: Karşılıklı dışlama(MUTual EXclusion)
I
oksijen = 0 Mutex korumalı sayaç
I
hidrojen = 0 Mutex korumalı sayaç
I
barrier = Barrier(3) bag() fonksiyonunu çağıran üç iplik de eşiğe vardığı
zaman bir sonraki 3lü grubun çalışmaya başlamasına izin verilir
I
oxyQueue = Semafor(0) Oksijen ipliklerinin beklediği semafor
I
hydroQueue = Semafor(0) Hidrojen ipliklerinin beklediği semafor
Kuyruk yapılarına bağlı temel fonksiyonlar ise aşağıdaki gibi ismlendirilmiştir.
I
oxyQueue.wait() : Oksijen kuyruğuna katıl
I
hydroQueue.wait() : Hidrojen kuyruğuna katıl
I
oxyQueue.signal() : Oksijen kuyruğundan bir oksijen ipliğini serbest bırak
I
hydroQueue.signal() : Hidrojen kuyruğundan bir hidrojen ipliğini serbest bırak
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
I
I
I
I
I
I
I
I
I
BM
BLG 312
I
Başlangıçta hydroQueue ve oxyQueue semaforları kilitlenmiş durumda.
I
I
I
hydroQueue = 0
oxyQueue = 0
Eşiğe ulaşan bir O ipliği, 2 H ipliğinin işleme girmesine izin vermelidir
I
I
hydroQueue semaforunun değerini 2 arttırmalıdır.
Arttırma işleminden sonra H ipliklerinin eşiğe varmasını beklemelidir
BM
BLG 312
Oksijen için özet kod:
3
8
13
mutex . w a i t ( )
o k s i j e n++
i f ( h i d r o j e n >= 2 )
hydroQueue . s i g n a l ( 2 )
h i d r o j e n −= 2
oxyQueue . s i g n a l ( )
o k s i j e n −=1
else
mutex . s i g n a l ( )
oxyQueue . w a i t ( )
bag ( )
b a r r i e r . wait ()
BM
BLG 312
Hidrojen için özet kod:
1
6
11
mutex . w a i t ( )
h i d r o j e n++
i f ( h i d r o j e n >=2 and o k s i j e n >=1)
hydroQueue . s i g n a l ( 2 )
h i d r o j e n −= 2
oxyQueue . s i g n a l ( )
o k s i j e n −=1
else
hydroQueue . w a i t ( )
bag ( )
b a r r i e r . wait ()
BM
BLG 312
Sushi bar problemi
Imagine a sushi bar with 5 seats. If you arrive while there is an empty seat, you can
take a seat immediately. But if you arrive when all 5 seats are full, that means that all
of them are dining together, and you will have to wait for the entire party to leave
before you sit down.
BM
BLG 312
Çözümde kullanılacak değişkenler
2
eating = waiting = 0
mutex = Semaphore ( 1 )
b l o c k = Semaphore ( 0 )
m u s t w a i t = F a l s e //
// k e e p t r a c k o f t h e number o f t h r e a d s
// mutex p r o t e c t s b o t h c o u n t e r s
// i n c o m i n g c u s t o m e r s ’ qu eu e ( r e g u l a r meaning )
i n d i c a t e s that the bar i s f u l l
BM
BLG 312
Çözüm denemesi
1
mutex . w a i t ( )
i f must wait :
w a i t i n g += 1
block . wait ()
6
mutex . w a i t ( )
w a i t i n g −= 1
11
// r e a c q u i r e mutex
e a t i n g += 1
m u s t w a i t = ( e a t i n g == 5 )
// e a t s u s h i
16
21
mutex . w a i t ( )
e a t i n g −= 1
i f e a t i n g == 0 :
n = min ( 5 , w a i t i n g )
block . s i g n a l (n)
must wait = False
BM
BLG 312
Bir çözüm
3
8
mutex . w a i t ( )
i f must wait :
w a i t i n g += 1
block . wait ()
else :
e a t i n g += 1
m u s t w a i t = ( e a t i n g == 5 )
// e a t s u s h i
13
18
mutex . w a i t ( )
e a t i n g −= 1
i f e a t i n g == 0 :
n = min ( 5 , w a i t i n g )
w a i t i n g −= n
e a t i n g += n
m u s t w a i t = ( e a t i n g == 5 )
block . s i g n a l (n)
BM
BLG 312
Bir başka çözüm
4
9
mutex . w a i t ( )
i f must wait :
w a i t i n g += 1
block . wait ()
// when we resume , we h a v e t h e mutex
w a i t i n g −= 1
e a t i n g += 1
m u s t w a i t = ( e a t i n g == 5 )
i f w a i t i n g and n o t m u s t w a i t :
block . s i g n a l ()
// and p a s s t h e mutex
else :
14
// e a t s u s h i
19
mutex . w a i t ( )
e a t i n g −= 1
i f e a t i n g == 0 : m u s t w a i t = F a l s e
if
24
w a i t i n g and n o t m u s t w a i t :
block . s i g n a l ()
// and p a s s t h e mutex
else :
BM
BLG 312
Parti Problemi
Yurtta yapılacak bir parti için aşağıdaki kısıtlar geçerlidir:
I
I
Bir odada aynı anda birçok öğrenci bulunabilir
Yurt müdiresi bir odaya iki durumda dalabilir
I
I
Odada öğrenci yoksa, odayı aramak için
Odada 50den fazla öğrenci varsa partiyi dağıtmak için
I
Müdire odadayken başka öğrenci odaya giremez ancak öğrenciler odadan ayrılabilir
I
Müdire odayı ancak oda boşalınca terk eder.
I
Sadece bir müdire teftişten sorumludur.
Bütün bu kısıtları karşılayan bir simülsayon yazınız.
BM
BLG 312
Parti Problemi
I
ogrenci = 0 Öğrenci sayısı
I
mudire = ‘‘odada değil’’ Müdire durumunu tutan bir enum
I
mutex = Semafor(1) Öğrenci ve müdire durumlarını korumak için
I
turnike = Semaphore(1) Dekan odadayken öğrencileri dışarıda tutmak için
I
odaHazir = Semaphore(0) Müdire dışarıda ve oda boşsa
I
ogrencilerCikti = Semaphore(0) Müdire içeride ve oda boşaldıysa
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
I
I
I
I
I
I
BM
BLG 312
Parti Problemi
Mudire için özet kod:
1
mutex . w a i t ( )
i f o g r e n c i > 0 and o g r e n c i < 5 0 :
mudire =
bekliyor
odaHazir . wait ()
# and g e t mutex from t h e s t u d e n t .
6
# ogrenci
if
11
say
s
0 ya da >= 50 o l m a l
o g r e n c i >= 5 0 :
mudire =
odada
dagit ()
turnike . wait () # g i r i s i k i l i t l e
o g r e n c i l e r C i k t i . wait ()
turnike . signal ()
# g i r i s k i l i d i n i ac
16
else :
21
# ogrenci
ara ()
mudire =
odada
sayisi 0 olmali
degil
BM
BLG 312
Parti Problemi
Öğrenci için özet kod:
4
mutex . w a i t ( )
i f m u d i r e ==
odada
:
turnike . wait ()
turnike . signal ()
mutex . w a i t ( )
o g r e n c i += 1
9
if
o g r e n c i == 50 and m u d i r e ==
odaHazir . s i g n a l ()
else :
bekliyor
:
# mutexi mudireye aktar
party ()
14
mutex . w a i t ( )
o g r e n c i −= 1
if
19
24
o g r e n c i == 0 and m u d i r e ==
bekliyor
:
odaHazir . s i g n a l ()
# odaBos u m u d i r e y e a k t a r
e l i f o g r e n c i == 0 and m u d i r e ==
odada
:
# o g r e n c i l e r C i k t i y i mudireye aktar
o g r e n c i l e r C i k t i . signal ()
else :
BM
BLG 312

Isletim Sistemleri Uygulama 6 - Ninova

Transkript

Benzer belgeler

model atc-2004 - Nokta Elektronik

Isletim Sistemleri Uygulama 4 - Unix`de semafor islemleri

Isletim Sistemleri Uygulama 7 - Ölümcül kilitlenme

Beyin MR Takip Görüntülerinin Otomatik Ç akıstırılması Automatic

2013 Results Gauss Contests 2013 Résultats Concours