Etmen tabanlı bir grid sisteminde CSP yaklaşımı kullanılarak güçlü taşınabilirlikli görevlerle ağ trafiği yükü dengeleme

Abstract

Günümüzde düŞük maaliyetli ve yüksek hızlı bilgisayarların çoğalmasına ek olarak çok hızlı ve geniŞ bantlı bağlantı olanaklarının yaygınlaŞması ile bilgisayarlar arası kaynak paylaŞımına dayalı sistemler oldukça popüler bir hal almıŞtır. Grid sistemleri fiziksel olarak farklı tiplerde olan ve bir ağ üzerinde farklı konumlarda bulunan kaynakların, dağıtılmasını ve bu kaynaklara eriŞimlerinin koordine edilmesini sağlayan dağıtık sistemlerdir. Yazılım gridleri kullanılarak oluŞturulabilecek sanal organizasyonlar sayesinde süper bilgisayarlar seviyesinde iŞlemci kapasitesine sahip sistemler oldukça düŞük maaliyetlerle oluŞturulabilmektedir. Elde edilen iŞlem gücü ile ticari ve bilimsel alanlarda birçok karmaŞık hesaplama makul sürelerde yapılabilmektedir. Dağıtık hesaplamanın baŞka bir dalı olan etmen sistemleri yapay zeka ile dağıtık sistemlerin esnek bir birleŞimidir. Etmen sistemleri günümüzde ticari ve bilimsel birçok uygulama alanında üzerinde sıklıkla çalıŞılan bir bilgisayar bilimleri konusu olarak göze çarpmaktadır. Dağıtık sistemlerin kullanım alanlarının artması ve birbirinden bağımsız bir çok kullanıcının dağıtık sistemlerin sunduğu kaynak ve hizmetlerden yoğun olarak faydalanmasıyla birlikte çeŞitli yük dengeleme mekanizmaları dağıtık sistemler için oldukça önemli hale gelmiŞtir. Özellikle gridler gibi soyut ve gevŞek bağlı iliŞkilerin yoğun olduğu sistemlerde, kullanıcıların sunulan hizmetin veya dağıtılan kaynağın sürekli bir Şekilde kaliteli olarak sürdürülmesi beklentilerinin karŞılanması gereksinimi, bu tarz sistemlerde yük dengeleme ihtiyacını arttırmaktadır. TaŞınabilirlik bir uygulamanın çalıŞtığı bir sistemden alınıp çalıŞmasına baŞka bir sistemde devam etmesinin sağlanmasıdır. TaŞınabilirlik sayesinde dağıtık sistemlerde yük dengeleme, ağ iletiŞiminin azaltılması ve sistem sürekliliğinin sağlanması gibi iŞlemlerin yapılması mümkündür. Temelde güçlü ve zayıf taŞınabilirlik olmak üzere iki çeŞit taŞınabilirlik vardır. Güçlü taŞınabilirlikli sistemlerde taŞınan uygulama duraklatılarak hedef sistemde çalıŞmasını kaldığı yerden devam ettirilir. Zayıf taŞınabilirlikte ise taŞınan uygulama hedef sistemde çalıŞmasına baŞtan baŞlar.CSP?ler yapay zekanın çeŞitli problemlerinin formüle edilmesinde ve çözülmesinde kullanılan yaygın bir yöntemdir. CSP yani kısıt karŞılama problemleri belirli bir problemle ilgili tüm kısıt ve limit tanımlamaları yapıldıktan sonra bu kısıtları sağlayacak bir çözüm kümesini arama iŞlemi olarak tarif edilebilir. Ağırlıklı CSP?lerde(WCSP) ise tanımlanan kısıtlar için ağırlık değerleri belirlenebilmektedir. Bu tarz kısıtlar tanımlayabilmek bize problemimizde bir kısıtın gerçekleŞmesi durumunda sisteme getirebileceği maliyeti tanımlayabilme ve bu maliyetin en düŞük olacağı çözümü arama imkânı vermektedirTezimizde etmen tabanlı bir grid sistemine bir ağ trafiği yükü dengeleme mekanizması önerilmiŞtir. Bu kapsamda FIPA standartlarına uygun Şekilde tasarlanmıŞ etmenlerden oluŞan bir etmen tabanlı grid sistemine, gridde çalıŞtırılan uygulamaların(görevlerin) güçlü taŞınabilirlikli bir Şekilde taŞınarak çalıŞma zamanında ağ trafiği yükü dengelemesi yapabileceği mekanizmalar eklenmiŞtir. ?lgili mekanizmalar gerçeklenirken, kullanılan etmen tabanlı grid sisteminin yaŞam döngüsünde ve sunduğu mesajlaŞma altyapısında değiŞiklikler ve bunlara çeŞitli eklemeler yapılmıŞtır. Etmen tabanlı grid sisteminde güçlü taŞınabilirlik gerçeklenirken Java dilinde geliŞtirilmiŞ bir iplik serileŞtirme kütüphanesi kullanılmıŞtır. Güçlü taŞınabilirlikli görev göçünün sağlanmasında kullanılan serileŞtirme mekanizmalarına ait görev yürütücüsünün etmen tabanlı grid sistemimize entegrasyonu sırasında karŞılaŞılan sorunlar safha safha çözümlenerek sistem çalıŞır hale getirilmiŞtir. Güçlü taŞınabilirlik ve mesajlaŞma altyapılarına yapılan eklentilerle birlikte, etmen tabanlı grid sistemi çalıŞma zamanında yük dengeleme yapılabilecek bir uygulama alanı haline getirilmiŞtir.Tezimizin asıl önerisi olarak sunabileceğimiz yapı ise etmen tabanlı grid sistemine ait ağ trafiği dengeleme mekanizmasının bir ağırlıklı CSP(kısıt karŞılama problemi)Şeklinde formulize edilerek gerçeklenmesidir. Tezimizde ağ trafiği yükü dengeleme algoritmamız grid sistemi açısından yük olarak belirlediğimiz çeŞitli ağırlıkları olankısıtların oluŞturduğu bir CSP?nin çözümü olarak gerçeklenmiŞtir. Gerçeklenen bu mekanizma sayesinde sistemimiz açısından yük olarak gördüğümüz yeni bir grid parametresinin uygun formatta CSP?ye ağırlığıyla birlikte kısıt olarak eklenmesiyle ağ trafiği yükünü dengeleme algoritmamız yeni belirlediğimiz yüklere göre karar verir hale getirilebilmektedir. Bunlara ek olarak tezimizde kullandığımız tüm geliŞtirme araçları ve kütüphaneler Java dili tabanlı olduğundan, geliŞtirdiğimiz etmen tabanlı grid sisteminde ağ trafiği dengeleme iŞlemi Java dilinin sağlamıŞ olduğu platform bağımsız çalıŞabilme özelliğine uyumlu bir yapı arz etmektedir.Sonuç olarak verdiği kararlar bir CSP?ye kısıtlar ekleyerek değiŞtirilebilecek esneklikte, platform bağımsızlık konusunda desteği olan bir ağ trafik yüküdengeleme algoritması ortaya çıkmıŞtır.

Grid computing and multi agent systems are two popular research topics. Nowadays the combination of two topics is in an increasing trend. This thesis combines these topics via presenting a runtime dynamic task load balancing approach between software agents which are running on a grid system.Grids are hardware and software infrastructures which are new way of the parallel and distributed computing. Grids support the distribution, sharing and coordinated use of heterogeneous resources . The systems which are connected by a grid might be in the same location or distributed globally, running on different hardware or operating systems, and owned by different organizations.Agents are flexible, encapsulated and autonomous software components, which execute an assigned task by interacting with other components in the environment. Agents are also social components, which are able to make communication and coordination with other components in the environment. They can collaborate on an execution of a task or make collaboration to achieve a total goal. With the aid of heterogeneousness, coordination and distribution power of grids, agents become more efficient and adaptive solutions for variety types of tasks.In grids execution performance and efficiency are generally important expectations of users. Grids use effective load balancing algorithms for distribution of tasks to overcome these expectations. A load balancing algorithm aims to improve the total utilization of available resources and efficient assignment of tasks in the grid. Load balancing algorithms can be classified into two categories: static or dynamic. In static algorithms, load balance decisions making mechanisms are defined at compile time when resource requirements are estimated. A multicomputer with dynamic load balancing allocate/reallocate resources at runtime based on no a priori task information, which may determine when and whose tasks can be migrated. Process migration via strong mobility is an efficient mechanism to achieve dynamic load balancing. Strong mobility allows the transfer of an executing process from a source site to a distant site, where it resumes the execution from the interruption point. Strong mobility can be provided by various mechanisms. These mechanisms can be generally implemented in four levels of programming concept, these are operating system level, interpreter level, source code level, compiled code level. Each level has trade-offs between efficacity and portability In this thesis we used compiled code level approach which is implemented in Java. The portability of this technique is independent from the operating system and the JVM.CSP(Constraint Satisfaction Problem) is a problem composed of a finite set of variables each of which has a finite domain of values and a set of constraints. Each xxiof grid becomes a weighted CSP solving problem. We used a generic CSP solver library called Jacop which is implemented in Java to solve our migration analysis problem as WCSP. After execution of CSP problem Jacop generates value-variable assignments. These assignments are task-container (machine) matching which will reduce inter-container messaging count for our grid system. Then the grid applies the decisions of Jacop calculation on grid.Strong mobility can be provided by various mechanisms. The approach we used is compile code level which let us to work on standard JVMs. To be able to migrate a thread, its execution must be suspended and its stack and program counter must be captured in a serializable format which is then going to be sent to the target location.We used the Brakes library to implement the strong mobility. Brakes has a bytecode transformer which instruments Java classfiles so they can capture their internal states at any time. Basically Brakes can rewrite a Java classfile with including computation state information. That allows us to pause and resume Java threads whenever desirable. We used Brakes thread serialization technique to apply compiled code level strong mobility approach. All the tasks which is run on grid is rewrote at compiled code level to achieve strong mobility. The migration mechanism works as follows: Firstly the migration manager report the migratory worker agent of task to the migration acceptor worker agent which run the task that will be migrated. Secondly migratory worker captures the task execution with Brakes. Then migratory worker serializes the task and execution state with standard Java serialization. After that migratory worker sends the task to the migration acceptor worker which is assigned by the migration manager. Finally migration acceptor worker deserializes the task and resumes it with Brakes. The migration manager informs the worker agents after migration processes about changes of the locations of the migrated tasks.The migration mechanism is designed as having the ability of working highly seperate from grid execution. And we have also implemented a test tool allows us to create virtual grid environments which have tasks that are messaging each other. This provides us to test the migration algorithm separately from grid environment execution by generating virtual environments. The test tool can emulate data which our migration algorithm needs from grid to perform migration analysis. The migration algorithm can solve the real world grid data and the artificial grid data which is generated from test tool with the same way. So we applied two types of testsin this thesis, one of them is creating a real grid which has real tasks that have resource needing, realizes messaging of tasks with each other, contains multiple real machines and achieves real task migrations from a machine to another. The other test type is emulating a big sized grid environment data, which has virtual machines, messaging of tasks, resource needing of tasks, count of workers and clients. Both test types the algorithm makes decisions the same way.In this thesis we used weighted CSP approach for migration analysis on a grid environment. We presented a dynamic solution to implement different migration decisions. We can change easily the migration analysis algorithm by adding new loads for the grid system as constraints to the CSP problem. Adding new constraints changes the migration analysis algorithm and the migration decisions totally. Therefore the load balancing algorithm which we presented is so flexible for balancing of different purposes. For example if we add the processing power of each machine as a load for the grid, the algorithm will work as processing load balancer. xxiiAll grid components, algorithms and the applied migration approach are fully implemented in Java and the grid system can work over standard JVMs. This makes our approach platform independent.