زمان‌بندی آینده‌نگرانه وظایف در محاسبات ابری مبتنی بر یادگیری تقویتی

نویسندگان

گروه مهندسی کامپیوتر – دانشگاه یزد

چکیده

با پیدایش رایانش ابری، کاربران منابع محاسباتی را بر اساس قانون پرداخت در ازای استفاده از ارائه‌دهندگان سرویس ابری دریافت می‌کنند. با توجه به محدودیت و پویایی منابع ابری برای اجرای درخواست‌های متنوع و متغیر با زمان کاربران، نیازمند یک مکانیزم زمان‌بندی مؤثر هستیم که خود را با شرایط پویای سیستم وفق داده و بهره‌وری منابع و رضایت کاربران را در بلندمدت تأمین نماید. الگوریتم‌های زمان‌بندی موجود تلاش می‌کنند با توجه به وضعیت فعلی سیستم، زمان‌بندی بهینه را بیابند که با توجه به پویایی درخواست‌های کاربران و عدم درک صحیح زمان‌بند از محیط  لزوماً منجر به دستیابی به نتیجه بهینه در بلند مدت نمی‌گردند و غالباً این الگوریتم‌ها توانسته‌اند تنها یکی از  پارامترهای کیفیت سرویس را بهبود ببخشند. در ابن مقاله یک روش زمان‌بندی مبتنی بر روش یادگیری تقویتی پیشنهاد می‌شود که به دلیل قابلیت تطبیق با محیط و ارائه پاسخ مناسب به  درخواست‌های متغیر با زمان، با تخصیص آینده‌نگرانه وظایف به منابع منجر به افزایش کارایی سیستم در بلندمدت می‌گردد. نتایج این مقاله نشان می‌دهد که روش پیشنهادی نه تنها منجر به کاهش زمان پاسخ، زمان انتظار و زمان تکمیل کار می‌گردد بلکه نرخ بهره‌وری منابع را هم به عنوان هدف فرعی افزایش می‌دهد. روش پیشنهادی در محدوده تعداد وظایف بالا، زمان پاسخ را به طور میانگین حدود 52/49 درصد نسبت به Random، 03/46 نسبت به Mix، 99/43 نسبت به FIFO، 53/43 نسبت به Greedy و 68/38 درصد نسبت به Q-sch بهبود ببخشیده است.

کلیدواژه‌ها


عنوان مقاله [English]

Reinforcement-Learning-based Foresighted Task Scheduling in Cloud Computing

نویسندگان [English]

  • S. Mostafavi
  • F. Ahmadi
  • M. Agha Sarram
Department of Computer Engineering, Yazd University, Yazd, Iran
چکیده [English]

With the apperance of cloud computing, users receive computing resources according to pay as you go of cloud service provider. An optimized scheduling approach for mapping all the tasks to the resources is an essential problem due to the limitations and dynamics of resources for requests which vary during the time. This solution may lead to improvement of system's efficiency. There are different methods for cloud computing scheduling with different parameters such as response time, makespan, waiting time, energy consumption, cost, utilization rate, and load balancing. But many of these methods are not suitable for improving scheduling performance in a condition that users requests change during the time. So in this thesis a scheduling method based on reinforcement learning is proposed. Adopting with environment conditions and responding to unsteady requests, reinforcement learning can cause a long-term increase in system's performance. The results show that this proposed method can not only reduce the response time and makespan but also increase resource efficiency as a minor goal. Our proposed illustrates improvements in response time for 49.52%, 46.03%, 43.99%, 43.53% and 38.68% over Random, Mix, FIFO, Greedy and Q-sch algorithms, respectively. 

کلیدواژه‌ها [English]

  • Cloud computing
  • Task scheduling
  • reinforcement learning
  • Foresighted task scheduling
  • Response time
[1]      A. A. Buhussain, R. E. D. Grande and A. Boukerche, “Performance analysis of Bio-Inspired scheduling algorithms for cloud,” IEEE International parallel and distributed processing symposium workshops, pp. 776-785, 2016.
[2]      Z. Peng, D. Cui, J. Zuo, Q. Li, B. Xu and W. Lin, “Random task scheduling scheme based on reinforcement learning in cloud computing,” Cluster computing, vol. 18, pp. 1595-1607, 2015.
[3]      E. Barrett, E. Howley and J. Duggan, “Applying reinforcement learning towards automating resource allocation and application scalability in the cloud,” Concurrency and computation: practice and experience, vol. 25, no. 12, pp. 1656-1674, 2013.
[4]      B. Yang, X. Xu, F. Tan and D. H. Park, “An utility-based job scheduling algorithm for cloud computing considering reliability factor,” Proceeding of international conference on cloud and service computing, pp. 95-102, 2011.
[5]      M. Hussin, C. Young and A. Zomaya, “Efficient energy management using adaptive reinforcement learning-based scheduling in large-scale distributed systems,” Proceeding of the international conference on parallel processing, pp. 385-393, 2011.
[6]      M. Hussin, N. Hamid and K. Kasmiran, “Improving reliability in resource management through adaptive reinforcement learning for distributed systems,” Journal of parallel and distributed computing, vol. 75, pp. 93-100, 2015.
[7]      Z. Peng, D. Cui, Y. Ma, J. Xiong, B. Xu and W. Lin, “A Reinforcement Learning-based Mixed Job Scheduler Scheme for Cloud,” in IEEE transactions on cloud computing, 2017.
[8]      M. Cheng, J. Li and S. Nazarian, “DRL-Cloud: Deep Reinforcement Learning-Based Resource,” in Proceedings of the 23rd Asia and south pacific design automation conference, pp. 129/134, 2018.
[9]      Y. Zhao, X. Mingqing and G. Yawei, “Dynamic resource scheduling of cloud-based automatic test system using reinforcement learning” in IEEE 13th international conference on electronic measurement & instruments, pp. 159-165, 2017.
[10]      سیمین قاسمی فلاورجانی و محمد علی نعمت بخش و بهروز شاهقلی قهفرخی، « تخصیص وظایف چندهدفه در واگذاری به ابر سیار،» مجله مهندسی برق دانشگاه تبریز، دوره 46، شماره 4، صفحات 217-232، 1395.
[11]      شهرام جمالی و سپیده ملک تاجی و مرتضی آنالویی، « مکان‌یابی ماشین‌های مجازی با استفاده از الگوریتم رقابت استعماری،» مجله مهندسی برق دانشگاه تبریز، دوره 46، شماره 1، صفحات 53-62، 1395.
[12]         R. S. Sutton and A. G. Barto, Reinforcement Learning: an introduction, Cambridge press, 1998.
    L. P. Kaelbling, M. L. Littman and A. W. Moore, “Reinforcement learning: a survey,” Artificial intelligence research, no. 4, pp. 237-285, 1996.