Abstract
This study addresses a two-tier job scheduling problem for SaaS cloud service providers which rely on resources leased from IaaS cloud providers to achieve elasticity to computational power. In our model, a project represents a user request which consists of multiple jobs; the SaaS is obligated to complete projects using multiple resources leased from IaaS or PaaS providers. The goals are to reduce the project turn-around time and to support priority scheduling by employing suitable scheduling algorithms. We propose a set of two-tier backfilling algorithms which extend the well-known conservative backfilling algorithm with project slack-time and priority concepts. Among the proposed algorithms, Two-Tier Strict Backfilling (2TSB) does not allow preemption in job waiting queues. On the other hand, preemption is allowable in Two-tier Flexible Backfilling which has two versions: 2TFB and 2TFB-SF (slack factor). In 2TFB, a new incoming project can preempt waiting jobs but not waiting projects, while 2TFB-SF permits preemption in both job and project waiting queues. Two-Tier Priority Backfilling (2TPB) algorithm takes priority into account such that only high-priority projects can preempt the low-priority ones. The experimental results indicate that, compared with 2TSB, 2TPB could reduce the mean turn-around time of high-priority projects by more than 25%
چکیده
این تحقیق یک مسئله زمان بندی برنامه دو لایه را برای سرویس دهنده های ابری SaaS مورد بررسی قرار می دهد که به منابع عاریه گرفته شده از سرویس دهنده های ابری laaS برای دستیابی به قابلیت انعطاف توان محاسباتی وابسته هستند. در مدل ما، یک پروژه یک درخواست کاربر را نشان می دهد که شامل چندین برنامه است؛ SaaS ملزم به تکمیل پروژه ها با استفاده از چندین منبع عاریه گرفته شده از سرویس دهنده های IaaS یا PaaS است. اهداف عبارتند از کاهش زمان برگشت پروژه و پشتیبانی از زمان بندی حق تقدم با بکارگیری الگوریتم های زمان بندی مناسب. ما مجموعه ای از الگوریتم های دولایه پرکننده را که الگوریتم پرکننده محافظه کارانه مشهور را با زمان سکوت پروژه و مفاهیم حق تقدم بسط می دهند، پیشنهاد می کنیم. در میان الگوریتمهای پیشنهادی، الگوریتم دو لایه کاملا پرکننده (2TSB) در صفهای انتظار برنامه، پیشدستی را مجاز نمی سازد. از طرف دیگر، پیش دستی در الگوریتم پرکننده قابل انعطاف دو لایه که دو نسخه 2TFB و 2TFB-SF (فاکتور انقطاع) دارد، مجاز است. در 2TFB، یک پروژه جدید می تواند بر وظایف در حال انتظار و نه وظایف پروژه های در حال انتظار پیشی بگیرد، در حالی که 2TFB-SF پیش دستی را هم در صفهای انتظار وظیفه و هم در صفهای انتظار پروژه مجاز می سازد. الگوریتم پرکننده با اولویت دو لایه (2TPB) اولویت را به گونه ای در نظر می گیرد که فقط پروژه های با اولویت بالا می تواند بر پروژه های با اولویت پایین پیشی بگیرند. نتایج تجربی نشان می دهد که در مقایسه با 2TSB، 2، توانست زمان برگشت میانگین پروژه های با اولویت بالا را بیش از 25 درصد کاهش دهد.
1.مقدمه
محاسبه ابری یک نمونه محاسبه مبتنی بر اینترنت است که به موجب آن منابع محاسباتی در اینترنت به عنوان یک وسیله جمعی به کاربران عرضه می شود (آی و همکارانش، 2011). مشتریان می توانند از ابر به عنوان نرم افزار (SaaS)، پایگاه (PaaS)، یا سرویس دهنده زیرساخت (IaaS) بر اساس پرداخت بر حسب استفاده بهره ببرند، و بنابراین از هزینه های نگهداری اجتناب می شود در حالی که از قابلیت انعطاف توان محاسباتی لذت می برند. پایگاه ابری گوگل نمونه خوبی از سرویس های محاسباتی ابری است که در آن زیرساخت، نرم افزار و حافظه، از راه دور میزبان قرار می گیرند و کاربران فقط به یک مرورگر وب برای دسترسی به سرویس نیاز دارند....