Paralel Yazılım Geliştirme Sürecinde Yarış Durumu Denetimi
Transkript
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 telmas@ku.edu.tr stasiran@ku.edu.tr Ö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