Bulut sistemlerde görev çizelgeleme problemlerine metasezgisel bir çözüm modelinin geliştirilmesi
Developing a metaheuristic solution model to task scheduling problems in cloud systems
Yazar: MÜCAHİT BÜRKÜK
Danışman: DR. ÖĞR. ÜYESİ GÜNGÖR YILDIRIM
Fırat Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Donanım Bilim Dalı
Derece: Yüksek Lisans, 2022
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Arama algoritmaları = Search algorithms ; Bulut bilişim = Cloud computing ; Görev planlama = Mission planning ; Metasezgiseller = Metaheuristics

Özet:
Bulut bilişim teknolojisi birçok verinin internet ortamında barınmasını, değerlendirilebilmesini, kullanıcıların yalnızca tükettiği hizmet kadar ödeme yapmalarını sağlayan sanallaştırılabilir ve ölçeklenebilir kaynakların toplamıdır. İnternet altyapısının gelişmesi, Nesnelerin İnterneti teknolojisinin yaygınlaşması, büyük verinin hızlı artışı ve buna yönelik çalışmaların ortaya çıkması, yapay zekâ çalışmalarındaki gelişmeler gibi birçok sebep bulut teknolojilerinin yaygınlaşmasına neden olmuştur. Bulut bilişimin en önemli mekanizmalarından biri sanal makinelerdir. Sanal makineler müşterilerin ihtiyaçları doğrultusunda bulut sistem üzerindeki kaynaklardan oluşturulurlar. İş hacmine bağlı olarak müşterilerin sanal makine sayıları ve özellikleri çeşitlilik gösterebilir. Müşteriler bu sanal makinelerin özelliklerine ve kullanım sürelerine göre bulut sağlayıcıya belirli ücretler öderler. Sanal makineler üzerinde çalıştırılması gereken görevlerin yanlış çizelgelenmesi görev tamamlanma süresinin (makespan) artmasına ve doğal olarak da müşteri için maliyet artışına yol açar. Görev tamamlanma süresindeki bu artış, dolaylı olarak bulut sağlayıcının da enerji sarfiyatı ve bakım onarım maliyetlerini olumsuz etkiler. Bu sebeple bulut sitemlerde sanal makineler için iyi bir görev çizelgeleme algoritmasının kullanılması hem müşteri hem de bulut sağlayıcı açısından zorunludur.
Görev çizelgeleme, NP-hard tipi bir problemdir. Deterministtik yaklaşımlar yerine metasezgisel algoritmaların kullanılması performans açısından bu tip problemlerin çözümünde sıklıkla tercih edilmektedir. Ancak öte yandan, problem tipinden dolayı, rastgele arama temelli metasezgisel algoritmaların lokal minimalara takılma olasılıkları da yüksektir. Bu olasılık görev ve sanal makine sayılarının artmasıyla daha da artabilmektedir. Bu sebeple kullanılan metasezgisel algoritmaların bu sorunu aşacak mekanizmalar kullanması gerekmektedir. Bu çalışma bu sorunun çözümü için farklı bir yaklaşım mekanizması kullanan ve güncel metasezgisel algoritmalardan olan Denizanası Arama Optimizasyonu (Jellyfish Search Optimizer) temelli bir çözüm önermektedir. Önerilen yöntemin en özgün yanı, daha hızlı bir şekilde lokal minimalardan kurtulmak için farklı bir benzerlik kontrolü ile dinamik popülasyon artışına imkân vermesidir. Böylece arama uzayında daha verimli bir keşif süreci gerçekleştirilmiş olmaktadır. Buna ek olarak bu algoritmanın, görev çizelgeleme problemi için çoklu iş parçacığı (Multi-Thread) ve çoklu-süreç (Multi-Process) analizleri de bu tez kapsamında yapılmıştır. Önerilen yöntemin performansı, CloudSim simülatöründe farklı senaryolar için karşılaştırmalı olarak denenmiş ve ispatlanmıştır.

Abstract:
Cloud computing technology is the sum of virtualizable and scalable resources that enable data to be hosted and evaluated on the internet, and users to pay only for the resources they consume. Many reasons, such as the development of the Internet infrastructure, the spread of the Internet of Things technology, the rapid growth of big data and the emergence of studies on this, and the developments in artificial intelligence studies, have led to the widespread use of cloud technologies. One of the most important mechanisms of cloud computing is virtual machines. Virtual machines are created from resources on the cloud system in line with the needs of customers. Depending on the business volume, the number of virtual machines created by customers and their features may vary. Customers pay certain fees to the cloud provider based on the features and duration of use of these virtual machines. Incorrect scheduling of tasks that need to be run on virtual machines leads to increased task completion time (makespan), and naturally, increased cost for the customer. This increase in task completion time indirectly affects the energy consumption and maintenance costs of the cloud provider. For this reason, the use of a good task scheduling algorithm in cloud systems is mandatory for both the customer and the cloud provider.
Task scheduling is an NP-hard type problem. The use of metaheuristic algorithms instead of deterministic approaches is often preferred in solving such problems in terms of performance. However, due to the type of problem, metaheuristic algorithms based on random search may get stuck in local minimums. This possibility may increase in case where the number of tasks and virtual machines has increased. For this reason, the metaheuristic algorithms preferred should use efficient mechanisms to overcome this problem. This study proposes a solution based on Jellyfish Search Optimizer, one of the current metaheuristic algorithms, which uses a different approach mechanism to solve this problem. The most unique aspect of the proposed method is that it allows dynamic population growth with a different similarity control to get rid of local minimums more quickly. Thus, a more efficient exploration process is realized in the search space. In addition, the multi-thread and multi-process analyses of this algorithm for the task scheduling problem were also made within the scope of this thesis. The performance of the proposed method has been comparatively tested and proven for different scenarios in the CloudSim simulator.