Researches On Dependent Task Sheduling Algorithms For Heterogeneous Multiprocessors In Distributed Computing Environment

With continuous development of grid and cloud computing,heterogeneous distributed computing systems are received extensive attention.In the heterogeneous distributed computing environment,how to assign resources rationally for users is an important research content.At present,the research on task scheduling in a heterogeneous distributed computing environment has achieved some progress,but it still exists many problems that need to be further studied and resolved.This dissertation focus on some problems of task scheduling for heterogeneous mutiprocessors in a distributed computing environment to spread research,which is conducted in two aspects,namely,minimum makespan and guaranteed quality of service(Qos).The former makespan refers to the time from the start execution of the first task to finish execution of the last task,that is,the scheduling length,which is one of most important and common goals in task scheduling.In general,a lower makespan indicates a superior scheduling strategy.The latter quality of service is an important factor that must be considered in the task scheduling after the development of the “service-oriented” computing model in recent years.The main research work and innovations on this dissertation are summarized as follows:(1)To the problem of the minimization makespan for dependent tasks scheduling in a distributed computing environment with heterogeneous processors,a list scheduing algorithm called Improvement Predict Earliest Finish Time(IPEET)is proposed.The basic idea of IPEET is that it calculates the task priority with a pessimistic cost table and implements the feature prediction with a critical node cost table to select a processor for a task.IPEFT shortens the schedule length in two ways.First,the task priority is calculated based on the pessimistic cost table that may lead to tasks on the most time-cosuming paths are preferentially scheduled,which can reduce the schedule length.Second,to select the processors for a task based on the critical node cost table,the finish time of the chosen processor for the current task is not always the earliest,but this policy ensures a shorter finish time for critical tasks in the next steps.To verify the effectiveness of this scheduling method,experiments regarding aspects of randomly generated graphs and real-world application graphs are performed,and comparisons are made based on the scheduling length ratio,robustness,and frequency of the best result.The results demonstrate that the PEFT outperforms the Predict Earliest Finish Time and Heterogeneous Earliest Finish Time algorithms in terms of the schedule length ratio,frequency of the best result,and robustness while maintaining the same time complexity.(2)To the problem of the minimization makespan for dependent tasks scheduling in a distributed computing environment with heterogeneous processors,a synthesized heuristic scheduling algorithm called Merge Tasks and Predict Earliest Finish Time(MTPEET)is proposed.MTPEFT first uses merge strategy to reduce the dependency wait time between tasks,while taking into account the parallelism between tasks.Then assigns a priority for each task.Finally,selects processors for tasks.When MTPEFT selects processors,the impact of the chosen processor for the parent of a critical task on the critical task and the impact of the chosen processor for the task which is not the parent of a critical task on its child tasks are considered.MTPEFT effectively reduces the schedule length without increasing the algorithm time complexity.Experiments regarding aspects of randomly generated graphs and real-world application graphs are performed.The results show that the MTPEFT algorithm outperforms other algorithms in terms of the schedule length ratio,frequency of the best result and robustness.Particularly for an increasing value of CCR,the improvement of MTPEFT is significantly higher.(3)To the problem of dependent tasks scheduling under the specified budget and deadline constraints,a scheduling algorithm based on budget and deadline constraints called Budget-Deadline Constrained Workflow Scheduling(BDCWS)is proposed.BDCWS first considers the characteristics of inconsistent model and introduces a new strategy to assign a priority for each task,which takes into account the time and cost and can reduce both the time and cost.Then proposes a task available budget to control the range of processor selection.Finally,provides different processor selection strategies for the current task according to the optimistic spare budget,which can achieve a well trade-off between time and cost.The simulation experimental results reveal that the BDCWS outperforms the existing algorithms in terms of the planning successful rate,especially in the case of tight budgets.(4)To the problem of dynamic concurrent multiple DAGs scheduling under the specified budget and deadline constraints,a Multi-Workflow Heterogeneous Budget-Deadline Constrained Scheduling algorithm(MW-HBDCS)is proposed.Consideration to the time and cost,MW-HBDCS proposes a workflow and workgroup uniform rank to assign priorities for tasks.This strategy not only saves the calculation time in the task selection stage,but also can improve the planning successful rate of concurrent workflow scheduling.When MTPEFT selects processors,it uses the current task optimistic budget to control the range of processor selection and consideration to the sub-deadline and sub budget of tasks proposes a bi-factor.Then according to this bi-factor value to select processors for the current task,so as to achieve the purpose of improving the planning success rate of scheduling.From the analysis and experimental results we can see that the proposed MW-HBDCS compared to MW-DBS,modified version of the Min-Min and Max-Min algorithm obtains better performance in terms of the planning success rate of scheduling.In addition,an improved parameterized decomposition tree based obfuscation method with double flattening control flow is put forward to ensure the security of tasks in multiple workflows.On the basis of given upper bounds of depth,breadth and granularity,the method builds a decomposition tree,coordinates the whole tree with a cycle selection structure named while-switch,and then applies double flattering to relevant nodes that satisfy certain conditions.Experimental results indicate that,in comparison with the flattening obfuscation method of control flow on the basis of parameterized decomposition tree,the proposed method reduces the execution expense and solves the deep nonfeasance problem;and that,in comparison with the traditional method only with flattening control flow,the proposed method increases the difficulty in decompilation and reverse engineering.