Paralel Yazılım Geliştirme Sürecinde Yarış Durumu Denetimi

YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
Paralel Yazılım Geliştirme Sürecinde Yarış Durumu Denetimi
Data-race Detection in Development Process of Concurrent Software
Tayfun Elmas
Bilgisayar Mühendisliği Bölümü
Koç Üniversitesi, İstanbul
Serdar Taşıran
Bilgisayar Mühendisliği Bölümü
Koç Üniversitesi, İstanbul
[email protected]
[email protected]
Özet
Yarış durumları paralel programlarda en çok rastlanan
hata durumudur. Yarış durumları istenmeyen, tutarsız
program davranışlarına yol açabileceği gibi birçok üst
düzey paralel çalışma hatasının da ön belirtisidir. Bu
bildirinin ana amacı, paralel yazılım geliştirme sürecinde
yarış durumlarına karşı bir farkındalık oluşturmaktır. Bu
nedenle yarış durumu tespit sistemlerinin yazılım
sürecine tümlenmesinin önemi vurgulanmakta ve
bildirinin yazarları tarafından Java programlama dili için
geliştirilen Goldilocks adında bir çalışma zamanı yarış
tespit algoritması tanıtılmaktadır. Bildiride bu
algoritmanın yazılım süreci içerisinde farklı kullanım
yaklaşımları önerilmekte ve üst-düzey eşleme
mekanizmaları için adapte edilebileceği anlatılmaktadır.
Abstract
Data-races are the mostly-seen errors in concurrent
programs. While data-races cause unexpected
discrepancies in the runtime behavior of the program,
many other kinds of concurrency errors manifest
themselves as data-races. The main goal of this paper is
to raise the issues about data-races during the software
development process. In this regard, we emphasize the
importance of integrating data-race detection systems
within the development process and present a runtime
algorithm, called Goldilocks, for Java programs. In this
paper, we propose various ways of exploiting our
algorithm inside the development process and explain
how to extend the algorithm for high-level, customized
synchronization mechanisms.
1. Giriş
Son yıllara damgasını vuran çok çekirdekli işlemci
(multi-core)
teknolojisi,
paralel
(concurrent)
programlama teknolojilerini tekrar gözler önüne getirdi.
Çok işlemcili süper bilgisayarlara sahip olmak masraflı
olsa da, çok çekirdekli işlemciler çoktan kişisel
bilgisayarlarda yerini almaya başladı. Bu gelişmeler
paralel programlama teknolojilerini önemli bir aşamaya
getirdi. Bu gelişmelerin bir yansıması, iş parçacığı
seviyesinde spekülasyon (thread-level speculation)
[17,22] gibi ardışık programları bile paralel donanımlar
üzerinde yüksek performansla çalıştırma temeline
dayanan tekniklerin önem kazanmasıdır. Ancak bu
otomatik teknikler programcı kaynaklı yaklaşımların
yanında sınırlı bir başarım artırımı sağlamaktadır.
Çok çekirdek teknolojisini kullanıcı seviyesinde
kullanmanın en etkin yolu, yazılımı doğrudan bir paralel
programlama çerçevesi içerisinde tasarlamak ve
gerçeklemekten geçmektedir. Bu gereksinimin doğal bir
sonucu olarak paralel yazılım geliştirme etkinliğinde
önemli bir artış gözlemlenmekte, paralel programlama
modellerinden en doğru ve etkin şekilde yararlanmayı
amaçlayan çalışmalar literatürde önemli bir pay sahibi
olmaya başlamaktadır [17,25,29].
Paralel programlama ortamları, etkin kaynak
kullanımı ve yüksek başarım sağlasa da, tasarım ve
gerçekleştirimi işlevsel doğruluğun sağlanması açısından
zorlaştıran bir model sunmaktadır. Bu modelin ardışık
modellerden en önemli farkı, bir yandan programın
işlevsel doğruluğunu sağlarken bir yandan da program
içerisinde bulunan ve paralel çalışan iş parçacıklarının
(thread) iletişimini performanstan fazla ödün
vermeyecek şekilde sağlamaktır. Bu da yazılımın
tamamını geniş bir perspektiften görerek akıl yürütmeyi
gerektirir.
Her ne kadar mesaj-tabanlı yöntemler belirli
alanlarda etkin olarak kullanılsa da, iş parçacıkları arası
iletişim için en çok tercih edilen yol paylaşımlı belleği
(shared-memory) kullanmaktır. Paylaşımlı bellek
yaklaşımında tüm paralel işlem birimleri ortak bir bellek
adres alanına okuyup yazarak haberleşirler. Farklı işlem
birimlerinin çalışma hızlarındaki farklar, iş örgüsü ve
paylaşımı (interleaving & thread scheduling), program
için girdiler dışında yeni bir rasgelelik kaynağı
oluşturmaktadır. Bu rasgelelik, çalışma zamanında
olacakları tahmin etmekten öte, her iş paylaşımı
durumunda doğru çalışacak kod yazmayı gerektireceği
için, paralel programları geliştirme sürecinde ardışık
programlara göre daha riskli programlar haline
getirmektedir.
Bu risklerden biri de ardışık programlarda
rastlanmayan yeni hata türleridir. Bu hatalar uygulamaya
göre farklı biçimlerde ortaya çıkıp, farklı sonuçlar
doğursa da hatanın meydana geliş biçimi ve
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
karakteristiğinde ortak nokta çoktur. Genellikle hata
paylaşılan bellek alanlarına farklı iş parçacıklarının aynı
anda ama birbirlerinden haberdar olmadan erişmeye
çalışmasıyla meydana gelir. Aynı iş parçacığı tarafından
atomik olarak yerine getirilmesi gereken bir dizi işlem,
bu işlemler ile çakışan farklı iş parçacıkları tarafından
kesilerek çalışma sonucunda programın tutarsız sonuçlar
üretmesine yol açar.
Bu bildiride, yukarıda değinilen hata durumlarının en
basit hali olan “ortak veriye erişim yarışı durumları”
(data-race condition), kısaca yarışlar ele alınacaktır.
Yarış durumu, aynı bellek alanına aynı anda en az iki iş
parçacığının ulaşmaya çalışması ve birbirleriyle
eşlenmemeleri, yani birbirlerinin işlemlerinden haberdar
olmamaları sonucu oluşur. Bu durumda yapılan erişimler
belleği programcının beklentileriyle tutarsız bir şekilde
değiştirecek ve program bu tutarsız bellek durumuyla
çalışmasına devam edecektir. Yarış durumlarının önemli
bir özelliği, hatanın uygulamadan bağımsız olarak kesin
olarak tespit edilebilmesidir. Bir başka ifadeyle, yarış
tespit sistemi uygulama mantığını anlamak ya da
uygulama üzerinde değişiklikler yapmak zorunda
değildir. Bu özellik, tespit sistemlerinin uygulanacağı
yazılımlardan bağımsız olarak geliştirilip yine programa
saydam bir şekilde uygulanmasına imkan vermektedir
Bölüm 2’de yarış durumlarının ayrıntılı bir tanımı
yapılacak ve literatürde bu durumların tespiti için
kullanılan yöntemler ve son yıllardaki gelişmelerden söz
edilecektir.
Bu bildirinin ana amacı, paralel yazılım geliştirme
sürecinde yarış durumlarına karşı bir farkındalık
oluşturmaktır. Bu nedenle yarış durumu denetim
sistemlerinin yazılım sürecine tümlenmesinin önemi
vurgulanacaktır. Bu doğrultuda Bölüm 3’de bildirinin
yazarları tarafından Java ortamı için geliştirilen
Goldilocks adında bir çalışma zamanı yarış tespit
algoritması tanıtılacaktır. Goldilocks algoritması yarış
denetimini geliştirme sürecine tümlemek için farklı
yaklaşımlar üretilebilmesine imkan vermektedir. Bölüm
4’de anlatılacak bu yaklaşımlar arasında algoritmayı bir
Java sanal makinesine gömerek hatayı çalışma sırasında
bir Java aykırı durumu (exception) yaratarak
programcıya sunmak ve programı model denetleyici
(model checker) içinde tam kapsamlı olarak sınamak
(stres testing) bulunmaktadır. Ayrıca Goldilocks
algoritması, Java’ya ait olmayan üst-düzey eşleme
(synchronization) öğelerinin de yarış denetimi için
işlenmelerine de imkan verecek şekilde adapte
edilebilmektedir. Bu yöntem Bölüm 5’de bir örnekle
açıklanacaktır.
2. Yarış durumları
Ortak veriye erişim yarışı durumu, kısaca yarışlar paralel
programlarda en çok rastlanan hata durumudur. En az iki
iş parçacığının aynı bellek alanına erişimde bulunması
ve bu erişimlerden en az birinin yazma işlemi olması
sonucu meydana gelir. Bu durumda iki erişim arasında
herhangi bir eşleme bulunmaz ve bu nedenle belleğin
son halini tahmin etmek mümkün olmayacaktır.
Yazılımın işlevsel doğruluğu açısından bu tür
yürütmeden yürütmeye değişen bir belirsizlik arzulanan
bir durum değildir.
public class Hesap {
int bakiye;
public void yatır(int miktar) {
bakiye = bakiye + miktar;
// sözde baytkodu
// 1: yazmaç = bakiye
// 2: yazmaç = yazmaç + miktar
// 3: bakiye = yazmaç
}
public void çek(int miktar) {
bakiye = bakiye – miktar;
// sözde baytkodu
// 1: yazmaç = bakiye
// 2: yazmaç = yazmaç - miktar
// 3: bakiye = yazmaç
}
}
Şekil 1: Bir yarış durumu örneği
Örnek bir yarış durumu Şekil 1’de gösterilmiştir.
Hesap adlı sınıfa ait bir nesnenin yatır ve çek adlı
yöntemlerini çağıran iki farklı iş parçacığını ele alalım.
Dikkat edilirse yöntemlerin gövdeleri herhangi bir
eşleme mekanizmasıyla korunmamaktadır. Ayrıca,
gövdeyi oluşturan satırlar birden fazla Java baytkomutuna (sözde bayt kodu şekilde verilmiştir)
derlenecektir. Sonuç olarak yatır ve çek
yöntemlerinin paralel çalışması sonucu bakiye alanına
olan erişimler yarış durumu meydana getirecektir. Her
iki yöntemin de 10 değeri ile çağırıldığını ve o andaki
bakiyenin de 10 olduğunu düşünelim. Arada eşleme
olmadığı için şu senaryo olasıdır: Her iki yöntem önce 1
numaralı sözde bayt kodu çalıştırıp yazmaç adlı yerel
değişkenlerine aynı bakiyeyi (10) okusun. Yerel
değişken ile yapılan işlem sonucu her iki yöntem de 2 ve
3 numaralı bayt kodları çalıştırıp bakiyeyi güncellesin.
Çalışma sonunda yatır ve çek’in hangi sırada bakiye
alanına yazdığına bağlı olarak bu alan 0 ya da 20
olacaktır. Ama bakiye için tutarlı tek son değer 10
olmalıdır. Farklı yarış durumu örnekleri ve ayrıntılı bir
tanımlama için [20]’e bakılabilir.
Yarış durumlarının olumsuz sonuçları ancak söz
konusu erişimlerin aynı anda ya da birbiriyle çalışacak
kadar yakın zaman dilimleri içerisinde meydana
gelmesiyle oluşur. Ancak bu eş zamanlı erişimi tespit
etmek, yazılımın çalışması dışında sanal makine ve
donanımı da (ön bellek ve bellek arası veri yolu gibi)
gözlemlemeyi gerektirir ve pratik değildir. Bu nedenle
bazı programlama sistemlerinde yarış durumunun, daha
pratik olarak tespit yapmak amacıyla biçimsel bellek
modeli üzerinden tanımları yapılmıştır. Örneğin, Java
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
bellek modeli (JMM), aynı bellek alanına yapılan ve
arasında Java’nın sunduğu herhangi bir eşleme öğesi
bulunmayan iki paralel erişimi yarış durumu olarak
nitelemiştir [14]. Daha farklı ifadeyle, aynı zamanda
gerçekleşmeseler de eğer iki iş parçacığı birbiriyle
eşlenmeden aynı alana erişiyorsa ve bunların aynı anda
meydana gelme olasılığı bulunuyorsa, bu durum bir yarış
olarak nitelenecektir. İki iş parçacığı arasındaki eşleme
Java’nın sunduğu monitor ve volatile değişkenler
gibi eşleme mekanizmalarıyla sağlanmaktadır. Bu
mekanizmaların
işlevsel
anlamları
(operational
semantics)
bellek modelinde biçimsel olarak
tanımlanmıştır ve bu anlamlar tüm derleyici ve sanal
makineler tarafından garanti edilmektedir.
Not edilmesi gereken bir husus, bazı istisna
senaryolarda yarışın hata olarak nitelendirilmemesidir.
Örneğin, programcı istatistik tutmak amaçlı sayaç
değişkenlerin güncellenmesi için eşleme kullanmak
istemeyebilir ve sayaçlar üzerine olan yarışları
önemsemeyebilir. Bunlar ancak istisna durumlardır ve
aşağıda anlatılan nedenlerden dolayı yarış durumları,
günümüz
literatüründe
paralel
programlamada
istenmeyen ya da ancak programcının kontrolünde izin
verilen bir durum olarak süregelmiştir [14].
Birinci neden, belleğin ulaşılan alanının yarışta rol
oynayan erişimler sonucunda ortaya çıkacak son halinin,
bu erişimlerin farklı sıralarda çalıştırılması sonucu
ortaya çıkacak durumdan bile farklı olabilmesidir.
Bunun bir nedeni, çoğu donanımda bellek erişimlerinin
atomik bir işlem olmamasıdır. Örneğin, Java ortamında
64 bitle temsil edilen long ve double veri tiplerine
yapılan bir okuma ya da yazma işleminin, JVM
tarafından tek bir atomik bellek erişimiyle
gerçekleneceği garantisi verilmemektedir. Nitekim bazı
JVM’ler bunu 32 bitlik iki ayrı bellek erişimi ile
gerçeklerken, bazıları da bu erişimlerin nasıl
yapılacağını tamamen donanıma bırakır. Bu durumda
örneğin long tipindeki bir değişkene yapılacak iki
eşzamanlı erişimin sonucu dört 32-bitlik erişimin her
hangi bir sıralamasını verebilecektir. Şekil 1’deki
örnekte görüldüğü gibi bakiye alanına yapılan oku-işleyaz sıralı işlemlerin atomik olmaması da 32 bitlik
işlemlerde bile bu problemin yaşanabileceğini
göstermektedir.
İkinci neden, bazı derleyici ve donanımların yarış
durumu içeren programların çalışma kuralları konusunda
sınırlı garantiler vermesidir. Örneğin, Java bellek
modelinde eşleme öğelerini doğru kullanan programlar
için ardışık tutarlılık modeli (sequential consistency)
kurallarıyla çalışma gibi çok sağlam ve iyi tanımlanmış
garantiler verilmektedir; böylece bu öğeleri kullanan
programcılar derleyici, JVM ya da donanım ne olursa
olsun programın çalışma zamanı davranışlarını
kestirebilirler. Ancak derleyici ve sanal makineler yarış
durumu içeren programlar için bu garantileri çok kısıtlı
tutmakta, programcının kolaylıkla tahmin edemeyeceği
çalışmalara yol açacak eniyilemeler yapabilmektedirler.
Üçüncü neden ise, yarış durumlarının, daha üst
düzey ve uygulamaya özgü hata durumlarının oluşması
sırasında gözlemlenebilmesidir. Bu durumların en
popüleri atomik çalışma ihlalleridir (atomicity violation)
[10]. Bu ihlaller, genellikle eşleme eksikliği ya da yanlış
kullanımı sonucu, bir iş parçacığı tarafından atomik
gerçekleştirilmesi gereken bir sıra işlemin, farklı bir iş
parçacığı tarafından bu işlemlerle çakışacak bir şekilde
bölünmesi sonucu ortaya çıkar. Her ne kadar atomik
çalışma ihlallerinin ve yarış durumlarının varlığının
birbirinin varlığından bağımsız şekilde oluşabileceği
gösterilmiş olsa da [10], yarış durumları genellikle eksik
bir eşlemeyi, yani muhtemel bir atomik çalışma ihlalini
gösterir [20].
Not edilmesi gereken bir unsur da, yarış
durumlarının belirli bir belirtisinin olmamasıdır. Yani
yarış durumu kendi başına programın hata verip
sonlanması gibi bir sonuca yol açmaz. Belirtiler
genellikle uygulamaya özgü hatalar olarak ortaya çıkar.
Örneğin Bölüm 4’de Şekil 2’deki yarış örneğinde
verinin beklenmeyen bir şekilde değiştirilmesi sonucu
NullPointerException hatası oluşur ve değişen
veriye ulaşan iş parçacığının sonlandırılmasıyla
sonuçlanır. Böyle senaryolarda olumsuz taraf, hatanın
ayıklanması sırasında asıl kaynağı olan eşleme
eksikliğine ulaşmanın zor oluşudur. En uç senaryoda,
yarışın sebep olduğu veri bozulması programın sonuna
kadar gözlenebilir bir hata yol açmayabilir ki bu, hatanın
kaynağını ve bozuk veriyi kalıcı kılar.
2.1 Yarış tespit yöntemleri
Literatürde çok sayıda yarış durumu tespit algoritması
yer almaktadır. Bu algoritmalar uygulanma biçimleri
dikkate alındığında iki ana grupta toplanırlar. Birinci
grupta yer alan durağan yöntemler, programın kaynak
kodunu analiz ederek çalışma sırasında aynı bellek
alanına gerçekleşmesi muhtemel eş zamanlı erişimleri
tespit etme temeline dayanırlar [1,2,3,4,5,9,16,18].
İkinci gruptaki dinamik yöntemler ise programı
çalışması sırasında gözlemleyerek yarış durumlarını
tespit ederler [6,7,8,11,19,21,23,24,27]. Durağan
yöntemler daha az maliyetli çözümler sunsalar da
algoritmaların kesinliği dinamik yöntemlere göre
sınırlıdır. Ayrıca durağan yöntemler programın tüm
yürütmelerini hesaba katmaktadırlar ve çözülmesi
amaçlanan problem karar verilemez niteliktedir
(undecidable). Dinamik yöntemler programın tek bir
yürütmesi ve ona ait gerçek çalışma verisi üzerinden
analiz yaptıkları için problem karar verilir hale gelir.
Dinamik yöntemlerin hata durumuna karar vermek için
durağan yöntemlere göre daha fazla bilgiye sahip
olmaları bu kararın kesinliğini olumlu yönde etkiler. Bir
sonraki bölümde tanıtılacak algoritma dinamik bir
algoritmadır.
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
Yarış tespit algoritmaları ayrıca uyguladıkları
politikalara göre lockset ve happens-before tabanlı
olmak üzere ikiye ayrılırlar. Lockset tabanlı algoritmalar
programın çalışması sırasında iş parçacıklarının
değişkenlere erişme esnasında sahip oldukları kilitleri
analiz ederek her bir değişkeni koruyan bir kilit kümesi
tahmin etmeye çalışırlar [1,9,15,23,27]. Bir değişkene,
iki ayrık kilit kümesine sahip olan iş parçacıkları
tarafından yapılan eş zamanlı erişimler yarış olarak
nitelendirilir. Happens-before (HB) tabanlı algoritmalar
ise erişimler arasında, iş parçacıklarının işlettiği eşleme
olayları ile belirlenen bir sıralama olup olmadığını
kontrol ederler [6,7,8]. Böyle bir sıralama iki erişimin
aynı anda gerçekleşemeyeceğini gösterir. Aşağıda
anlatılacak algoritma happens-before tabanlı bir
algoritmadır.
3. Goldilocks algoritması
Goldilocks algoritması bu bildirinin yazarları tarafından
geliştirilmiş bir dinamik yarış tespit algoritmasıdır [7,8].
Algoritmanın geliştirilmesindeki ana amaç, bir sonraki
bölümde irdeleneceği üzere, Java çalışma ortamına
null-işaretçi denetimi ya da dizi indisi denetimi gibi
sürekli aktif olacak bir yarış denetim mekanizması
eklemektir. Goldilocks bu alanda hem kesinlik (precise)
hem de sağlamlık (sound) sağlayan ilk algoritmadır.
Kesinlik özelliği algoritmanın yanlış hata (false alarm)
vermesini önleyerek programcıyı gereksiz hata
ayıklamaktan
kurtarırken,
sağlamlık
özelliği
algoritmanın
hatalı
programları
kaçırmasını
önlemektedir.
Goldilocks Java bellek modelindeki yarış durumu
tanımını temel alır. Algoritma daha sonra STM
(software transactional memory) mekanizmalarını da
destekler hale getirilmiştir [25], ancak bu bildiride bu ek
konulara girilmeyecektir. Aşağıda Java bellek modelinde
yer alan yarış durumu tanımı kısaca anlatılacaktır; daha
ayrıntılı bilgi için [14]’e bakılabilir.
Java bellek modeli yarış durumunu tanımlamak için,
Leslie Lamport tarafından ilk kez tanımlanmış olan
happens-before (HB) [12,15] sıralanışını kullanmaktadır.
HB sıralanışı, paralel bir çalışmada meydana gelen
olaylar arasında kısmi bir sıralamadır (partial-order). Bu
sıralanış genellikle programda (özellikle farklı iş
parçacıklarında) meydana gelen eşleme olayları
arasındaki tersinemez bir sıralamayı ifade eder ve
programın üreteceği sonuçlar hakkında çıkarımlar
yapmak için kullanılır. Sıralanış Java bellek modelinde
aşağıdaki gibi tanımlamıştır:
1.
2.
Bir iş parçacığında meydana gelen bir olayla
aynı iş parçacığında meydana gelen sonraki bir
olay arasında
Bir monitor’un serbest bırakılması ile aynı
monitor’un sonraki kilitlenmesi arasında
3.
4.
5.
volatile tipte bir değişkene yazma olayı ile
aynı değişkenden yazılan değeri gören sonraki
okumalar arasında
Bir
iş
parçacığının
başlatan
olay
(Thread.startThread yöntemi) ile yaratılan
iş parçacığında gerçekleşen tüm olaylar
arasında
Bir iş parçacığında gerçekleşen tüm olaylarla,
aynı iş parçacığıyla birleşen bir iş parçacığının
(Thread.join yöntemi) birleşmeden sonraki
olayları arasında
HB kısmi bir sıralama olduğu için geçişlilik kuralını
sağlar. Aynı değişkene yapılan iki ayrı erişimin bir yarış
oluşturmaması için bu erişimlerin yukarıdaki kurallar
çerçevesinde HB ile sıralanması gerekmektedir. Diğer
bir ifadeyle HB ile sıralanmayan her iki erişim programı
muhtemel bir yarış durumuna sokmaktadır.
Goldilocks algoritması, programın çalışması
sırasında meydana gelen tüm ilginç eşleme olaylarını ve
belleğe erişimleri gözlemleyerek HB sıralamasını
dinamik olarak belirlemek ve aralarında HB sırası
bulunmayan bellek erişimlerini, erişimin kendisi
gerçekleşmeden önce tespit etmek mantığına
dayanmaktadır.
Algoritma, çalışma süresince her değişken 1 için o
değişkenle ilişkilendirilen bir eşleme değişkeni kümesi
hesaplar. Eşleme değişkenleri, Java’nın eşleme
öğelerinde kullanılan monitor’ler, volatile tipindeki
değişkenler ve iş parçacıklarıdır. Bir değişkene ait
eşleme kümesinin herhangi bir andaki içeriği, o
değişkene bir sonraki erişimin yarış durumu
oluşturmaması için nasıl bir eşleme gerçekleştirilmesi
gerektiği ile ilgili bilgi verir. Örneğin, kümede yer alan
bir monitor, her hangi bir iş parçacığının o monitor’u
kilitlediği halde değişkene yapacağı bir erişimin yarış
durumu oluşturmayacağını gösterir.
Algoritma eşleme ve belleğe erişim olayları
gerçekleştikçe değişkenlere ait eşleme kümelerini
günceller. Belleğe yapılan her erişimde yarış durumu
oluşup oluşmadığına karar verir. Algoritmanın bunu,
değişkenin eşleme kümesinin o andaki içeriği üzerinden
akıl yürüterek, aynı değişkene son iki erişim arasında bir
HB sırası var olup olmadığını tespit ederek yapar.
Algoritmanın gerçekleştirimi için de pek çok
eniyileme
tekniği
kullanılmıştır.
Örneğin,
gerçekleştirimde algoritma, eşleme olaylarını ardışık bir
listede saklamakta, her bellek erişimi sırasında bu listeyi
analiz ederek erişim kümesini otomatik olarak
oluşturabilmektedir. Algoritmayı hızlandırmak için
eşleme listesini dolaşmadan önce HB sırasını daha kısa
sürede kontrol edecek ek sorgular çalıştırılmakta, böyle
Java dilinde bir programın değişken kümesi, her hangi
bir anda yığında bulunan tüm nesnelerin alanlarını ve
sanal makiye yüklenmiş static sınıf alanlarını içerir.
1
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
HB sırasının daha hızlı şekilde tespit edilebildiği
durumlarda
listenin
dolaşılmasını
gerektiren
algoritmanın asıl kısmı atlanabilmektedir. Bu
sorgulardan biri son iki erişimin aynı iş parçacığı
tarafından yapılıp yapılmadığıdır; aynı iş parçacığının
gerçekleştirdiği tüm olaylar HB ile sıralanmıştır. Diğer
bir sorgu, her değişkenle bir monitor’u eşleştirip,
değişkenin aynı monitor kilitli haldeyken erişimlerinde
diğer kontrolleri atlamaktır. Goldilocks algoritmasının
tasarım ve gerçekleştirim detayları için [7]’e bakılabilir.
Bir sonraki bölümde bu algoritmayı yarış yakalamak için
farklı kullanım yaklaşımları üzerinde durulacaktır.
4. Yazılım geliştirme sürecinde yarış denetimi
Yarış durumları paralel yazılım geliştirilme sürecinde en
çok dikkat gösterilmesi gereken hata durumu haline
gelmiştir. Bir önceki bölümlerde yarışın yol açtığı
istenmeyen durumlar vurgulandı. Bu bölümde bir yarış
tespit algoritmasının paralel yazılım geliştirmede farklı
tümleştirme yöntemleri tartışılacak ve Goldilocks
algoritmasının uygulanma deneyimleri aktarılacaktır.
Paralel yazılım geliştirme, paralel yazılımın
karakteristiğinden kaynaklanan nedenlerle tasarımdan
geliştirmeye önemli bir düşünce gücü harcanması
gereken bir süreçtir. Ardışık yazılımlarda programın
doğruluk ölçütleri süreç boyunca birim testlerle, sürecin
son
aşamalarında
da
bütünleşme
testleriyle
sınanmaktadır. Paralel programlar bu test sürecinin daha
dikkatli tasarlanmasını gerektirir. Örneğin, modülleri
paralel olarak işletilebilecek bir programın bir
modülünde gerçekleşecek paylaşılan belleğe bir erişim,
diğer bir modülde hemen fark edilemeyecek yan etkiler
meydana getirebilir. Bu nedenle modülerlik yeterince
sağlanmadığı sürece doğruluk, birim test gibi yerel
kontrollerden ziyade, sürekli olarak programın geneli
üzerinden çıkarım yapılmasını gerek kılar. Ayrıca
paralel ortamda ortaya çıkacak hata türleri de ardışık
programlardan farklı karakteristiklere sahiptir ve bu tür
hatalara özgü test planları geliştirilmesi gerekebilir.
Örneğin, paralel çalışmada ortaya çıkan hatalar iş
parçacıklarının planlamasına (thread scheduling) bağlı
oluşabilir; bir hata sadece belirli çalışmalarda ortaya
çıkabilir. Bu yüzden bir test kümesinin programın tüm
yürütme uzayında tarayacağı kısmını kestirmek zordur;
test planı aynı testin farklı çalışma örgülerini de
sınayabilecek şekilde zorlanmasını isteyebilir. Tüm bu
unsurlar, paralel programlara özel sınama yaklaşımları
geliştirilmesini zorunlu kılmaktadır.
Yarış durumlarının programcı açısından olumlu bir
özelliği,
uygulamadan
bağımsız
şekilde
denetlenebilmesidir. Böylece bir yarış denetleyici,
çalışma ortamında programcıya ve programa saydam bir
şekilde çalıştırılabilir ve yarış uygulamaya bağımlı (ve
daha zor ayıklanabilecek) bir hata türünü meydana
getirmeden önce programcı bilgilendirilebilir. Geliştirme
sürecinde programı sürekli olarak yarış durumları için
gözleyecek bir çalışma zamanı denetim sistemi bu
açıdan bir erken uyarı sistemi görevi üstlenecektir.
Ayrıca günümüzde farklı çalışma zamanı gözlem
teknikleriyle hataya yol açan yürütme izini sürmek
mümkün olabilmektedir. Farklı bir yürütmede hatanın
gözlemlenmeyebileceği göz önünde bulundurulduğunda
bu izin kusursuz bir şekilde belirlenmesinin önemi
ortadadır.
Bu yaklaşımın olurluğunu ve maliyetinin araştırmak
için Goldilocks algoritması Kaffe Java sanal makinesinin
içine gömülmüş, uygulama üzerinde her hangi bir
değişiklik yapmadan yarış denetlemesi yapılabilmesi
sağlanmıştır. Kaffe, Java ortamının tüm gereksinimlerini
karşılayan açık kaynak kodlu bir Java sanal makinesidir
[26]. Kaffe’nin komut yorumlayıcısı (byte-code
interpreter) değiştirilerek eşleme ve bellek erişim
komutları yorumlanırken algoritmanın tetiklenmesi
sağlanmıştır. Algoritma, eşleme olaylarını ardışık bir
listede saklamakta, her bellek erişimi sırasında bu listeyi
analiz ederek aynı alana bir önceki erişimle arasında bir
HB sırası olup olmadığını kontrol etmektedir.
Bu yöntemle yapılan denemeler sonucunda denektaşı
test programlarının çoğu için ortalama 2-4 arası bir
yavaşlama katsayısı gözlemlenmiştir. Bunun üzerine
Chord [16] adlı durağan bir yarış tespit aracı
kullanılarak programa bir ön analiz uygulanmış, yarışa
maruz kalmayacağı belirlenen değişkenlerin kontrolü, bu
.class
dosyaları
işaretlenerek
değişkenler
engellenmiştir. Bu aracın çalışma hızı birkaç dakika
seviyesindedir. Sonuç olarak yavaşlama katsayısı
ortalama
1-1.5
düzeyine
indirilmiştir. İleride
uygulanması düşünülen eniyileme teknikleriyle bu
katsayının
1-1.2
seviyesine
düşürülmesi
amaçlanmaktadır.
Bir başka gerçekleştirim yaklaşımı, bayt kod
mühendisliği yapılarak Java programı .class dosyasına
derlendikten sonra bayt-kodu değiştirilerek programın
içine gömülmesidir. Bu yaklaşım da sanal makineye
gömme yaklaşımında olduğu gibi programcının her
hangi bir müdahalesine gerek kalmadan otomatik olarak
gerçeklenebilmektedir.
Gelecek
çalışma
olarak
Goldilocks algoritmanın Valgrind ya da PIN gibi ikili
kod değiştirme araçları kullanılarak programın ana
koduna
gömecek
bir
aracın
geliştirilmesi
planlanmaktadır.
Bir yarış tespit algoritması tam kapsamlı bir
doğrulama sürecinde de (exhaustive verification)
kullanılabilir. Bu seçenek program hakkında kesin bir
doğruluk kararı vermek istendiği durumlarda seçilebilir.
Örneğin, Goldilocks algoritması Microsoft’un Chess adlı
model denetleyicisinde gerçeklenmiştir ve Windows
işletim sistemi cihaz sürücülerinin tam kapsamlı
sınanması için kullanılmaktadır [13]. Model denetleyici
belirli varsayımlar altında (maksimum iş parçacığı
bağlam değişimi sayısı) programın tüm yürütmelerini
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
benzetim yoluyla inceleyerek yarış durumu içeren bir
yürütme üretip üretemeyeceğine karar verir.
Model denetleme gibi tam kapsamlı teknikler paralel
programlardaki muhtemel yürütme sayısı ve karmaşıklık
hesaba katıldığında çok maliyetli olmaktadır. Ayrıca
programın bazı yürütmeleri girdiye bağımlı olabilir ve
bu girdiler sınama ön sırasında belirlenemeyebilir. Bu
durumda önerilen, model denetleyici gibi araçların
ancak tümleme testi öncesi gibi geliştirme yazılım
sürecinin belirli noktalarında kullanılmasıdır. Diğer
aşamalarda
yukarıda
değinilen,
yarış
tespit
algoritmasının programa kendi içine ya da programın
üzerinde çalışacağı çalışma ortamına gömülmesi gibi
yaklaşımlar tercih edilmelidir.
1 public void run() {
2 // ...
3 // Bağlantıyı ilkle
4 try {
5
do {
6
String commandLine =
m_reader.readLine();
7
...
8
m_request.parse(commandLine);
9
if(!hasPermission()) {
10
m_writer.send(530,
"permission", null);
11
continue;
12
}
13
// komutu çalıştır
14
service(m_request, m_writer);
15
} while(!m_isConnectionClosed);
16 } catch (DataRaceException e) {
17 // Error: "Connection closed!"
18
break;
29 }
30 }
1 public void close() {
2 try {
3
synchronized(this) {
4
if(m_isConnectionClosed) return;
5
m_isConnectionClosed = true;
6
}
7
...
8
m_request = null;
9
m_writer = null;
10 m_reader = null;
11 } catch (DataRaceException e) {
12 // Error: "Connection accessed!"
13
return;
14 }
15 }
Şekil 2: Bir yarış durumu örneği
Tespit sisteminin yanı sıra, yarış durumlarının Java
programlama
modelinin
bir
parçası
olması
önerilmektedir. Bu amaçla algoritmanın Kaffe
içerisindeki gerçekleştiriminde, yarış durumunun tespiti
halinde DataRaceException adında bir kural dışı
durum nesnesi yaratılmaktadır. Bu durumun işlenmemesi
halinde bellek erişimini gerçekleştiren iş parçacığı sona
erdirilmektedir.
Ancak
programcı
DataRaceException için bir kural dışı durum işleme
kodu yazarak, bu duruma reaksiyonda bulunabilir;
örneğin, iş parçacığının o erişimi atlayıp yarışa neden
olan durumu tespit ettikten sonra bir daha olmaması için
gerekli aktivitede bulunabilir. Böyle bir özellik, özellikle
dağıtımın hemen öncesindeki alfa ve beta testlerinde ve
dağıtım sonrası kullanımlarda paralel program hatalarına
karşı en etkili ve zararsız şekilde tedbir alınmasını
kolaylaştıracaktır.
Şekil 2’de DataRaceException’ın örnek bir
Apache
ağ
kullanımı
gösterilmiştir.
Şekilde
sunucusunun eski bir sürümünde yer alan Connection
sınıfına ait run ve close yöntemleri gösterilmiştir. Bu
yöntemlerinin farklı iş parçacıkları tarafından
çalıştırıldığı bir senaryoyu ele alalım. run yöntemi 6.
satırda bir ağdan komut okumakta, 8. satırda komutu
yorumlayıp 14. satırda çalıştırmaktadır. run 7. satırı
işlettikten sonra bağlantının close yöntemi çalışmaya
başlasın. Bu noktada close yönteminin tamamı, run
yöntemi ile arasında eşleme eksikliği nedeniyle
çalışabilir ve bağlantıya ait m_request, m_writer ve
m_reader alanlarının temizlenmesine yol açabilir.
Ardından run yöntemi 8. satırda m_reader alanına
erişmeye çalışacak ve NullPointerException aykırı
durumu oluşacaktır. Daha kötü bir durumda close
yönteminin run 14. satırı işletmeden hemen önce
çalıştığı senaryoyu ele alalım. Bu durumda
NullPointerException aykırı durumu service
yönteminin içinde, hatanın kaynağına uzak bir noktada,
meydana gelecek problemin analizini zorlaştıracaktır.
Şimdi de çalışma ortamında yarış tespit sisteminin
bulunduğunu düşünelim. Bu durumda close yöntemi
bağlantının alanlarına eşlemesiz bir şekilde erişmeye
çalıştığında yarış durumu oluşacak ve catch bloğu
içinde bu yöntem uygun bir şekilde sonlandırılacaktır.
run yöntemi ise işlemini sorunsuz bir şekilde
tamamlayacaktır. Alternatif yaklaşımlar bir günlüğe hata
kaydı yazılıp sonradan programcının incelemesi de
sağlanması ya da close yönteminin catch bloğu içinde
sonlandırılmaması, run yöntemi biter bitmez yeniden
çalıştırılarak bu kez başarılı olmasıdır. Geniş bir açıdan
düşünüldüğünde DataRaceException mekanizması,
uygulamaya özgü bir çakışma tespit sistemi inşa etmek
için de kullanılabilir.
5. Genişletilmiş HB sıralaması
Bu bölümde Goldilocks algoritmasının bir sonraki
sürümü için düşünülen ve geliştirilme aşamasında olan
bir genişletme yöntemi tartışılacaktır. Bu yöntem HB
sıralamasının tanımını genişleterek üst-düzey eşleme
mekanizmaları kullanan programlar için yarış tespitinin
maliyetini azaltmaya dayanmaktadır. Aşağıda bu
genişletmenin temel faydaları ve gerçekleştirme
teknikleri anlatılacaktır.
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
Java bellek modelinin HB sıralaması temelli yarış
durumu tanımı her ne kadar Java’nın sunduğu
mekanizmalar türünden yapılmış olsa da, HB sıralaması
paralel programlar üzerinden akıl yürütme için doğal bir
araçtır. Lamport’un tanımından sonra özellikle dağıtık
sistemlerde geniş çapta uygulama alanı bulmuş olan
yöntem, yarış durumları ve atomik çalışma ihlalleri için
de kullanılmaya başlanmıştır [12,15]. Java bellek modeli
dil içerisindeki standart yöntemler için bir HB kurallar
kümesi vermiş olsa da, aşağıda savunulacağı üzere bu
kümeyi daha üst seviye mekanizmalar için genişletmek
de mümkündür.
Üst-seviye eşleme mekanizmaları Java’nın sunduğu
temel öğeleri kullanan ama istemcilerine daha karmaşık
politikalar sunan sınıflar kümesi olarak gerçeklenen
eşleme
öğeleri
sunarlar.
Örneğin,
java.util.concurrent paketi atomik veri yapıları,
bariyerler, olay kuyrukları gibi pek çok alternatif eşleme
tekniği sunan sınıflardan oluşmaktadır. Bu gibi sınıflar
monitor,
volatile
elbette
gerçekleştirimde
değişkenler gibi temel öğelerden faydalanmaktadırlar.
Ancak, bu sınıfların işlevi, bu temel öğeler cinsinden
değil, daha soyut bir şekilde, bu sınıfların yöntemleri
aracılığıyla tanımlanmaktadır.
5.1 Bayrak Örneği
public class Semaphore {
int s; // kritik koda girmesine izin
// verilecek iş parçacığı sayısı
public Semaphore (int k) {
this.s = k;
}
// kritik koda girmeden çağrılır
public synchronized void P() {
while (s <= 0) {
this.wait();
}
s = s – 1;
}
// kritik koddan çıkarken çağrılır
public synchronized void V() {
s = s + 1;
this.notify();
}
}
Şekil 3: Örnek bir bayrak (semaphore) gerçekleştirimi
Algoritmanın genişletilme detaylarında girilmeden
önce bunun faydalarından birkaçını sıralamak faydalı
olacaktır. Bu noktaları örnek üzerinde vurgulamak
açısından
Şekil
3’deki
bayrak
(semaphore)
gerçekleştirimini ele alalım.
Bayrak veri yapısı, bir kritik kod parçasına girişte
azaltılan (P yöntemi ile) ve çıkışta artırılan (V yöntemi
ile) paylaşılan bir sayıyı temsil eder. Böylece kod
parçasının aynı anda sadece belirli bir üst sayıda iş
parçacığı tarafından paralel olarak işletilmesine izin
verilir 1 . s alanına yapılan erişimleri atomik hale
monitor’ler
getirmek
için
bayrak
sınıfı
(synchronized anahtar terimi ile) kullanılarak
gerçeklenmiştir. P yöntemi, s alanı sıfır ya da negatif
olduğu sürece bloke halde s alanının tekrar pozitif hale
gelmesini bekler; sonra s’i azaltarak kritik koda girer.
Çıkışta da tekrar s’i artırır ve P yönteminde bekleyen bir
iş parçacığı varsa onu uyandırır.
5.2 Üst-seviye eşleme mekanizmaları
Dikkat edilecek olursa, bayrak kullanan bir kod, P ve V
yöntemlerinin çağırdığı monitor kilitleme ve serbest
bırakma olayları arasında HB sıralanışı olması nedeniyle
yarış durumuna maruz kalmayacak ve bu orijinal
Goldilocks algoritması tarafından da onaylanacaktır.
Ancak algoritmanın Bölüm 3’de anlatılan hali aşağıda
anlatılacak masrafları getirecektir.
Goldilocks algoritması programın çalışması sırasında
gerçekleşen tüm eşleme olaylarını kaydetmektedir.
Böylece algoritmanın yol açtığı performans gideri,
meydana gelen eşleme olaylarının sayısıyla doğru
orantılı olarak artar. Tek bir olayın kaydedilme maliyeti
düşük olsa da, olay sayısı Java programının yürütme
boyutuna bağlı olarak binlerle ölçülebilen yüksek
değerlere ulaşabilmektedir. Ayrıca belleğe her erişimde
algoritma yarışın oluşup oluşmadığına karar vermek için
eşleme olay listesinin bir kısmını dolaşılmaktadır. En
kötü durumda, listenin tamamının dolaşılacağı göz
önüne alınınca, elenen her bir eşleme olayı tüm bellek
erişimlerinde bir az olayın ele alınmasını sağlayacaktır.
Bu durumda işlenecek eşleme olayı sayısının azaltılması
pek çok açıdan maliyeti azaltıcı bir rol oynayacaktır.
Örneğin Şekil 3’de P ve V yöntemleri en iyi durumda
ikişer eşleme olayı meydana getireceklerdir (monitorun
kilitlenmesi ve serbest bırakılması). Ancak kritik kodu
çalıştırmak isteyen iş parçacığı sayısı arttıkça bazı iş
parçacıkları wait yöntemini çalıştıracaklar, bu da P’nin
her çalışmasında çalışacak olay sayısını dörde
çıkaracaktır (Java’da wait yöntemi bir monitor serbest
bırakma ve kilitleme olayları içerir). Çok daha karmaşık
mekanizmalarda bu sayı onlarla ifade edilebilir hale
gelebilir.
Bir önemli nokta da bayrak sınıfının s alanının yarışa
maruz kalmamasıdır. P ve V yöntemlerinde s alanına
erişimlerde Goldilocks algoritmasını çalıştırmaya gerek
yoktur. Benzer şekilde bazı eşleme teknikleri yarışa
maruz kalan değişkenlerden de faydalanmaktadır. Bu tür
sınıflara
kullandıkları bazı değişkenleri yarış
kontrolünden atlatmaya imkan verilmelidir.
Birbirini dışlayıcılar (mutex) ikili bayraklar (k=2)
kullanılarak gerçeklenebilirler.
2
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
5.3 HB sıralanışının genişletilmesi
Monitor’ler
birbirini dışlama (mutual-exclusion)
politikası (aynı kritik kodu aynı anda sadece bir iş
parçacığı çalıştırabilir) sunarken, bayraklar aynı anda
birden fazla iş parçacığının kritik kodu çalıştırabilmesine
izin vermektedir. Bu durumda kullanıcı (ya da
programcı), bu politikayı yöntemlerin gövdesinde
kullanılan eşleme öğelerinin yarış tespit sistemi
tarafından işlenmesi yerine, daha üst seviyede bir
iletişimi tercih edebilir. Böylece eşleme sınıfının
gerçekleştirimi ve içerisindeki alanlar Goldilocks
algoritmasından saklanarak aynı zamanda modülerlik
sağlanabilir. Aşağıda algoritmanın bu yönde nasıl
değiştirilebileceği anlatılacaktır.
Burada önemli olan nokta, programcının, eşleme
kütüphanesiyle yarış tespit sistemine garantiler vermesi
ve bu garantiler çerçevesinde sistemin kütüphanedeki
yöntemler içerisindeki kod için kontroller yapmamasını
istemesidir. Aşağıda bu garantiler anlatılacak ve
programcı ile yarış kontrol sistemi arasında önerilen ara
yüz tarif edilecektir.
Goldilocks algoritmasının ama işlevi belleğe
erişimler arasında HB sıralaması olup olmadığının
tespitidir. Bu açıdan algoritmanı ana amacı sabit
tutularak, HB sıralamasının tanımında bir değişikliğe
gidilecektir. Şekil 3’deki bayrak sınıfının, yapılacak
değişikliklere adapte edilmiş hali Şekil 4’de verilmiştir.
İlk değişiklik sınıf içinde yarış kontrolü yapılmaması
istenen değişkenlerin @race-free açıklamasıyla
işaretlenmesidir. İşaretlenen değişkenlere erişimde
Goldilocks algoritması işletilmez. Örnekte s alanı
işaretlenerek kontrol edilmemesi istenmiştir. İkinci
değişiklik de çalışırken eşleme olayı oluşturmamsı
istenen yöntemlerin @sync-free açıklamasıyla
işaretlenmesidir. İşaretlenen yöntemlerin yarattığı
eşleme olayları algoritmaya aktarılmaz.
En önemli değişiklik P ve V yöntemlerinin sağladığı
eşleme mekanizmasının Goldilocks’a aktarılmasında
görülmektedir. Bu aktarım, P ve V yöntemlerinin
Goldilocks sınıfında tanımlanan yöntemlere çağrıda
bulunmasıyla gerçekleştirilir. Bu çağrılar Java’nın
sunduğu HB sıralamasına ek olarak algoritmaya, üstdüzey eşleme mekanizmasından kaynaklanan yeni
sıralamalar tanıtmaktadır. hbSource yöntemi, HB
sıralamasında o ile özdeşleştirilen bir çıkış düğüm
tanımlar. hbSink ise bu sıralamada o ile özdeşleştirilen
bir giriş düğümü tanımlar. Böylece, aynı argüman ile
özdeşleştirilen çıkış düğümleriyle, giriş düğümleri
arasında bir sıralama sağlanmış olur. Goldilocks’ın
önemli bir gereksinimi de bu hbSource ve hbSink
yöntem çağrılarının bir toplam sırada (total-order)
algoritmaya iletilmesi ve bu sıranın, eşleme
mekanizması açısından tutarlı bir sıra olmasıdır.
Örnekteki bayrak sınıfı bu yöntemleri P ve V
yöntemlerinin çalışmasıyla birlikte atomik olarak
çağırdığı için P ve V yöntemlerinin arasındaki eşleme
hbSource ve hbSink yöntemlerinin çağrılış sırasıyla
tutarlı hale gelmektedir.
public class Goldilocks {
public static native void hbSource
(Object syncObj, Thread currThr);
public static native void hbSink
(Object syncObj, Thread currThr);
}
public class Semaphore {
int s; // @race-free
public Semaphore (int k) {
this.s = k;
Goldilocks.hbSource(
this, Thread.currentThread());
}
// @sync-free
public synchronized void P() {
while (s <= 0) {
this.wait();
}
s = s – 1;
Goldilocks.hbSink(
this, Thread.currentThread());
}
// @sync-free
public synchronized void V() {
s = s + 1;
this.notify();
Goldilocks.hbSource(
this, Thread.currentThread());
}
}
Şekil 4: Bayrak sınıfının yeni gerçekleştirimi
Ancak
unutulmamalıdır
ki,
programcı
bu
açıklamaları eklemekle bir taahhütte bulunmaktadır.
Goldilocks algoritması yalnızca yalın haliyle (Java’nın
temel eşleme öğeleri için) sağlamlık ve tamlık garantisi
vermektedir. Sağlamlık garantisinin geçerli kalabilmesi
için ortada olmayan bir HB sıralamasının oluşmasını
önlemelidir. Örneğin, Şekil 4’deki bayrak sınıfının
işleyişi sırasında hbSource yöntemini çağıran bir V
yöntemi ile sonrasında gelen ve hbSink yöntemi çağıran
tüm P yöntemleri yarışa izin vermeyecek şekilde
eşlenmelidir. Tamlık garantisinin geçerli kalabilmesi için
de programcı mekanizmaya ait yöntemlerin çalışmasıyla
sağlanan her bir HB sırası için bir hbSource ve hbSink
yöntemlerinin çalışacağında emin olmalıdır, aksi
durumda algoritma yanlış alarm verecektir (bu
yöntemlerin oluşturduğu diğer olaylar @sync-free
açıklaması ile atlandığı için).
6. Sonuç
Çok çekirdekli işlemcilerin genel kullanıcılara
sunulmasıyla birlikte paralel yazılım geliştirme
etkinliğinde ve araştırmasında belirli bir artış
gözlemlenmektedir. Gelişen teknolojiden en iyi sonucu
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
alabilmek için etkin ve doğru paralel yazılım geliştirme
önemli bir rol oynayacaktır. Bu bildiride bu süreçte
programcıların karşısında en çok çıkacak problemlerden
biri olan yarış durumlarına karşı bir farkındalık
yaratılmak amaçlanmış ve yarış denetim sistemlerinin
yazılım sürecinde kullanılmasının önemi vurgulanmıştır.
Bu amaçla bildirinin yazarları tarafından geliştirilmiş bir
çalışma zamanı yarış tespit algoritması olan Goldilocks
anlatılmış, bu algoritmanın geliştirme sürecinde
kullanılma yaklaşımları değerlendirilmiştir. Paralel
yazılım ve donanım teknolojisinin, yazılım geliştirme
sürecini de pek çok yönden değişime uğratacağı açıktır
ve geliştiricilerin bu alandaki problemlere karşı hazırlığı
yazılım kalitesini olumlu olarak etkileyecektir.
7. Teşekkür
Bu bildirinin yazarları, Goldilocks algoritmasının
geliştirme sürecinde değerli katkılarından ve bu bildiride
anlatılan konulardaki fikirlerinden dolayı Shaz Qadeer’e
teşekkürlerini sunar.
8. Kaynaklar
[1] Abadi M., Flanagan C., and Freund S.N. Types for Safe
Locking: Static Race Detection for Java. ACM
Transactions on Programming Languages and Systems,
sayfa 207--255, 2006.
[2] Boyapati C., Lee R., and Rinard M. A type system for
preventing data races and deadlocks in Java programs.
OOPSLA 02: Object-Oriented Programming, Systems,
Languages and Applications, pages 211--230. ACM,
2002.
[3] Cheng G., Feng M., Leiserson C., Randall K., and Stark
A. Detecting data races in cilk programs that use locks.
ACM Symposium on Parallel Algorithms and
Architectures (SPAA '98), sayfa 298--309, Puerto
Vallarta, Mexico. 1998.
[4] Choi J.-D., Loginov A., and Sarkar V. Static datarace
analysis for multithreaded object-oriented programs.
Technical Report RC22146, IBM Research, 2001.
[5] Choi J.D., Lee K., Loginov A., O'Callahan R., Sarkar V.,
and Sridharan M.. Efficient and precise datarace
detection for multithreaded object-oriented programs.
PLDI 02: Programming Language Design and
Implementation, sayfa 258--269. ACM, 2002.
[6] Christiaens M. and De Bosschere K. Trade, a topological
approach to on-the-fly race detection in Java programs.
JVM 01: Java Virtual Machine Research and Technology
Symposium, sayfa 105--116. USENIX, 2001.
[7] Elmas T., Tasiran S, Qadeer S. Goldilocks: A Race and
Transaction-Aware Java Runtime. ACM SIGPLAN 2007
Conference on Programming Language Design and
Implementation (PLDI). San Diego, CA, USA, 2007.
[8] Elmas T., Qadeer S., and Tasiran S. Goldilocks:
Efficiently Computing the Happens-before Relation
Using Locksets. Workshop on Formal Approaches to
Testing and Runtime Verification (FATES/RV). 2006.
[9] Flanagan C. and Freund S.N. Type-based race detection
for Java. PLDI 00: Programming Language Design and
Implementation, sayfa 219--232. ACM, 2000.
[10] Flanagan, C. and Qadeer, S. 2003. A type and effect
system for atomicity. SIGPLAN Not. 38, 5, sayfa 338349. 2003.
[11] Harrow J.J. Runtime checking of multithreaded
applications with visual threads. SPIN 00: Workshop on
Model Checking and Software Verification, sayfa 331-342. Springer-Verlag, 2000.
[12] Lamport L. Time, clocks, and the ordering of events in a
distributed system. Communications of the ACM 21 (7):
sayfa 558-565. 1978.
[13] Musuvathi, M. and Qadeer, S. Iterative context bounding
for systematic testing of multithreaded programs.
SIGPLAN Not. 42, 6. sayfa 446-455. 2007.
[14] Manson J., Pugh W., and Adve S. The Java memory
model. POPL 05: Principles of Programming Languages,
sayfa 378--391. ACM Press, 2005.
[15] Mattern F. Virtual time and global states of distributed
systems. International Workshop on Parallel and
Distributed Algorithms, sayfa 215--226. North-Holland,
1989.
[16] Naik M., Aiken A., and Whaley J. Effective Static Race
Detection for Java. PLDI'06: Proc. of the 2006 ACM
SIGPLAN Conference on Programming Language
Design and Implementation}, sayfa. 308—319. 2006.
[17] Prabhu, M. K. and Olukotun, K. Using thread-level
speculation to simplify manual parallelization. SIGPLAN
Not. 38, 10 Oct. 2003.
[18] Praun C.von and Gross T.R. Object race detection.
OOPSLA 01: Object-Oriented Programming, Systems,
Languages and Applications, sayfa 70--82. ACM, 2001.
[19] Pozniansky E. and Schuster A. Efficient on-the-fly race
detection in multithreaded C++ programs. PPoPP 03:
Principles and Practice of Parallel Programming, sayfa
179--190. ACM, 2003.
[20] Robert H. B. Netzer and Barton P. Miller. What are race
conditions?: Some issues and formalizations. ACM Lett.
Program. Lang. Syst., sayfa 74--88, 1992.
[21] Ronsse M. and De Bosschere K. Recplay: A fully
integrated practical record/replay system. ACM
Transactions on Computer Systems, sayfa 133--152,
1999.
[22] Quiñones, C. G., Madriles, C., Sánchez, J., Marcuello, P.,
González, A., and Tullsen, D. M. Mitosis compiler: an
infrastructure for speculative threading based on precomputation slices. SIGPLAN Not. 40, 6, 269-279. 2005.
[23] Savage S., Burrows M., Nelson G., Sobalvarro P., and
Anderson T. Eraser: A dynamic data race detector for
multithreaded programs. ACM Transactions on
Computer Systems, sayfa 391--411, 1997.
[24] Schonberg E. On-the-fly detection of access anomalies.
PLDI 89: Programming Language Design and
Implementation, sayfa 313--327, 1989.
[25] Shavit S. and Touitou D. Software Transactional
Memory. 14th Annual ACM Symposium on Principles of
Distributed Computing, sayfa 204--213, ACM 1995.
[26] Wilkinson T. Kaffe: A JIT and interpreting virtual
machine to run Java code. http://www.transvirtual.com/,
1998.
[27] Yu Y., Rodeheffer T., and Chen W. Racetrack: efficient
detection of data race conditions via adaptive tracking.
YKGS2008: Yazılım Kalitesi ve Yazılım Geliştirme Araçları 2008 (9-10 ekim 2008, İstanbul)
SOSP 05: Symposium on Operating Systems Principles,
sayfa 221--234. ACM, 2005.
[28] Bridges M. J., Vachharajani N., Zhang Y., Jablin
T., August D. I. Revisiting the sequential
programming model for multi-core. The 40th
IEEE/ACM
International
Symposium
on
Microarchitecture (MICRO). 2007.
[29] Gordon M. I., Thies W., Amarasinghe S. Exploiting
coarse-grained task, data, pipeline parallelism in stream
programs. ACM ASPLOS. 2006