Performance Evaluation of Two New Lightweight Real-Time Scheduling Mechanisms for Ubiquitous and Mobile Computing Environments

摘要

In ubiquitous and mobile computing environments, most of user requests have timing constraints. Therefore, for their execution, real-time scheduling mechanisms should be employed. In such environments, some mechanisms, such as Earliest Deadline First and Least Slack Time Rate (LSTR), are the most used real-time scheduling algorithms today. However, these existing mechanisms cannot guarantee the execution of the most critical user tasks. Furthermore, the results of executed tasks should also be provided to users on time so as to not waste the resources processing these tasks. The existing scheduling mechanisms, such as Dynamic Adjustment with Time Constraint and Dynamic Priority-based Heuristic action (DPH), are not suitable for this due to some limitations. The current paper proposes two new lightweight real-time mechanisms for scheduling input tasks (received requests) and output tasks (execution results) and evaluates their performance. The first mechanism satisfies users based on the classification of similar tasks and the use of the LSTR algorithm. The second mechanism is an improved form of the combination of the LSTR and DPH algorithms, and aims provide users with the maximum number of services by considering a possibility matrix. Extensive simulation experiments on real workload data demonstrate the superiority of the proposed mechanisms over existing algorithms, in terms of the percentage of executed tasks, makespan, and average turnaround time criteria.