اسم الباحث     :    Jamal Adnan Al-Sharjabi Ibrahim Ahmed Al-Baltah
سنة النشر     :    2017
ملخص البحث     :   

Abstract

Cloud computing and distributed systems have been emerging as the new era of computing model. The high capabilities and the ease of extendibility make them an attractive solution for the customers. Moreover, the reliability and openness make them a fertile ground for wide range of applications and systems. Therefore, the need of maximizing the resources utilization is a crucial issue in the aforementioned systems. To achieve that, resources scheduling should be carried out in a sound manner to assure satisfactory resources utilization. However, cloud computing systems are well-known by providing pay-per-use services by means of service level agreement (SLA) which enforces quality of service (QoS) mechanisms. With considering the heterogeneity of these systems, we aim to propose a QoS-Aware two-phase scheduling model to classify the tasks depends on its SLA. This model grantees sending and executing each task across the computing clusters (high or low performance clusters) according to their SLA.

Keywords: Distributes systems; Cloud computing scheduling; QoS-Aware Scheduling; SLA scheduling

1.    Introduction

Computing technology has witnessed massive changes since is emergence. Mainframe computers, in the mid-1970s, controlled the computing scene in view of the idea of one PC serving many individuals. In the 1980s, mainframes PCs offered up to PCs, and in the other hand, the accentuation was one PC to one individual. In the 1990s, with developed computing powers accessible at lower costs, we are seeing another time of personal computing, that is, a phenomenon in which different PCs are serving one individual[1].Nowadays, a huge volume of data in different areas is rapidly generated. It leads to an urgent need of processing those data and discovering the useful knowledge out of it[2].Besides, numerous applications comprise of various cooperative processes which ordinarily need extra processing power over single machine ability[3]. Therefore, distributed heterogeneous computing, which comprises loosely coupled computing nodes linked through Ethernet or different networks[4]. IT has evolved  as an effective computational paradigm[5]. From the real time perspective, distributed heterogeneous computing is increasingly being applied on critical real-time applications, in which each process must guarantee to meet its timing by means of using heterogeneous distributed computing capabilities, which includes various heterogeneous nodes that communicate with each other to solve a problem[6]. Moreover, Cloud computing and Service-Oriented Architectures (SOA) increase the need for distributed real-time systems by means of SLA, which is applied as a contract between customers and service providers[7].

Despite of that, scheduling in distributed systems forms an expansive process. This is because scheduling needs to understand the complex nature of present day PC clusters in addition to the types of applications that is executed in them. Scheduling may be job or task scheduling or resource allocation. The objective of task scheduling is to improve the resources usage and limit the bottleneck while executing those tasks. Scheduling can be dynamic,  choosing for current jobs and tasks, or it could schedule in advance the assignment of tasks from a given workflow[8],[9].The key factors in tuning distributed systems performance are the technique used to deploy its clusters topology  and the scheduling policy used in scheduler [10]. Due to that, the task scheduling is a standout amongst the most crucial issues in planning, managing and completion of the effective parallel applications[11]. On the other hand, the heuristic scheduling techniques can be classified into static scheduling and dynamic scheduling. In static scheduling, all the information of the tasks is known before scheduling and the resources are statically allocated to these tasks. This technique is easy to be implemented with less runtime overhead. In contrast, dynamic scheduling tasks are scheduled as soon as they arrive in the system, therefore, It leads to more runtime overhead[9].One of the most useful scheduling mechanisms is to break the scheduling mechanism into two distinct phases, because this approach allows us to investigate the impact of sorting policies on scheduling policies and vice versa[4].

Therefore, this paper aims to propose a modified model, which is inspired from TOPS model by extending its phases in order to meet the SLA-based quality of service requirements.

2.     Literature review

Tasks scheduling is a crucial issue in almost every field of computer science, not only in distributed systems. As a result, many studies have attempted to propose solutions to improve the scheduling process. Palmieri et al.[12] have introducedan uncoordinated fully distributed scheduling scheme for federated cloud organizations, with cosidring independent, contending, and self-interested job/task execution agent, driven by ideal social welfare criteria towards a Nash balance solution.

Due to the fact that scheduling have many related issues such as: reliability, priority, performance, among others. From the reliability perspective,  a two-phase scheme - Reliability Cost Driven scheduling (RCD)  is proposed by Qin et al. [6], which defines a tasks scheduling technique with priority limitations that uses a reliability measure as one of the goals in a real-time and heterogeneous distributed systems. They have devised a new off-line scheduling of communicating tasks, based on the concept of reliability cost, to schedule real-time tasks for maximized reliability. The simulated results have shown that their proposed scheme is significantly better than AEAP and ALAP.

Moreover, some works have focused on priority issues. Consequently, Jansen & Zhang[13]have studied the issue of scheduling malleable tasks with priority limitations. They are given m similar processors and n tasks. For every task the time of the processing is a function of the number of processors assigned to it. Furthermore, the tasks must be handled by means of the priority limitations. The objective is to reduce the make span (most extreme finish time) of the subsequent schedule. As a further matter, Chen et al. [14] have proposed an online heterogeneous dual-core scheduling framework for dynamic workloads with real-time limitations. The framework is designed to work by means of using a general purpose processor core and a synergistuc processor core, which are devoted to isolate schedulerts with various  scheduling policies , and priority limitations among tasks are managed through interacion between the two schedulers. The framework is additionally able to be configured for low priority inversion and high systems usage. Additionally, Xu et al. [15]have summarized some representative ordering and dispatching policies used in list schedulers, models the execution processes of these ordering and dispatching policies using Stochastic Petri Nets (SPN), and simulates the list scheduling process of cloud tasks.Li et al. [16]have presented a model for scheduling stochastic parallel applications on heterogeneous cluster systems. They have discussed stochastic scheduling and strategies to manage different arbitrary variables in scheduling stochastic tasks. They have proven that the expected makespan of scheduling stochastic tasks is more than or equivalent to the makespan of scheduling deterministic tasks, where all processing times and communication times are replaced by their expected values. To solve the issue of sceduling precedence obliged stochastic tasks effectively and adequately, they have proposed a Stochastic Dynamic Level Scheduling (SDLS) algorithm, which depends on stochastic bottom levels and stochastic dynamic levels.

Likewise, performance as a vital issue has been widely discussed. Leal et al. [17]have presented a decentralized model to schedule independent tasks in Federated Grids. This model comprises of an arrangement of meta-schedulers on each of the grid infrastructures of the Federated Grid. Each meta-scheduler needs to execute a mapping technique in order to enhance two of the most widely recognized functions of task scheduling issues: makespan and resource performance. They have considered four feasible algorithms that need to give a simple, decoupled, and coarse-grained aolution that might be deployed in any Grid. Their expermintal results and graphics are given to make a comparison of the different policies in regard to their behavior. Theanalysis uncovers that Dynamic Objective and Advance Scheduling (DO-AS) is an efficient echnique.Huang et al.[18] have presented Community-Aware Scheduling Algorithm (CASA) which is a dynamic decentralized sceduling approach. The CASA is a two-pahse scheduling technique contanins aset of heuristic sub-algorithms to accomplish an improved scheduling performance over the extent of general grid or cloud, rather than individual involved nodes. The broad exploratory assessment with a real grid workload trace dataset demonstrates that, when contrasted with the centerralized scheduling scheme with Best-Fit as the meta-scheduling policy, the utilization of CASA can prompt between30% and 61% improvement in regard to job slowdown , and between68% and 86% reduced average job waiting in a decentralized scheduling way without the need of detailed real-time processing information from involved nodes.Singh and Chana[19]have presented a proficient cloud workload management framework in which cloud workloads have been distinguished, investigated and clustered through K-means on the premise of weights allocated and their QoS necessities.Additionally scheduling has been done in light of various scheduling policies and their relating algorithms. The performance of the proposed algorithm has been avaluted using existing scheduling policies  through CloudSim toolkit. Karatza et al. [20]have investigated using simulation the performance of different policies for the scheduling of real-time directed acyclic graphs in a heterogeneous distibuted environment. They have applied bin packing mechanism through the processor selection phase of the scheduling procedure, so as to use scheduling gaps and thus improve list scheduling techniques. The simulation comes about demonstrate that the proposed policies outperform the other inspected algorithms. Socci et al. [21]have motivated and studied multiprocessor scheduling issue of a limited set of precedence-related mixed criticality jobs. They came up with an algorithm that, given a global fixed-priority assignment for jobs, can adjust it so as to enhanceits schedulability for mixed-criticality setting. The experiments demonstrate theincreasing of schedulable instances up to a maximum of 30% if compared to classical solutions for this category of scheduling problems. Orhean et al. [8]have proposed a strenthener learning algorithm for the scheduling issue in distributed systems. The machine learning mechanism puts into considerations the heterogeneity of the nodes and their attitude inside the grid, and the arrangement of tasks in a directed acyclic graph of dependencies, ultimately determining a scheduling policy for a better execution time.

On the other hand, there are uncountable issues other than the aforementioned issues including but not limited to the fault tolerant, which has been discussed by Zhu et al. [22], which is amid at  proposing a fault-tolerant satellite scheduling algorithm named FTSS, in which an overlapping technology is used to enhance the resourve usage. Moreover, the FTSS utilizes the task blending techniques to  improve the schedulability. Similarly, job-mapping issue has been widely discussed, for example, Selvi and Manimegalai [23]have done an inspection on implementing Two-Phase Variable Neighborhood Search (TPVNS) algorithm for scheduling independent jobs on computational grid. The proposed algorithm comprises of two modules with general variable neighborhood search and basic variable neighborhood search algorithm, that is to find a good mapping of grid jobs with grid nodes. The performance of TPVNS was assessed with other optimization algorithm, for a large diversity of test cases, and with the consideration of the heterogeneous environment of various configurations. The results of TPVNS are better for the majority of the instances. The computational outcomes show the estimation of the proposed TPVNS in solving the grid job issue and its computational proficiency.From the quality metric perspective, Cordasco et al. [24]have presented a new quality metric calledAREA, for schedules that execute computations having reliant interdependent constituent chores (jobs, tasks, and so forth.) on such platforms. AREA measures the average number of chores that a schedule renders qualified for execution at each step of a computation.

Besides, resource allocation plays an important factor within scheduling issues. Consequently, Sudhakar et al. [25]have attempted to mitigate resource allocation issue by proposing a model for both independent tasks scheduling and virtual machines allocation issues. They have proved that, regardless of the possibility that this extra requirement makes the resource allocation issue to be NP-Complete, just a little resource increase on the degree is adequate to accomplish optimality. Therefore, the issue size acquires a high vitality. Consequently,   Venugopalan and Sinnen[26] have proposed a mixed integer linear programming (MILP) solution for NP-hard problem.Although, scheduling issues are frequently hard to deal with by MILP solutions, the proposed MILP solution utilizes problem specific learning to take out the need to linearize the bi-linear equations emerging out of communication delays. Further, the size of the proposed formulation in terms of variables is independent of the processors number.