{'fraction_non_alphanumeric': 0.041637751561415685, 'fraction_numerical': 0.022017538325657688, 'mean_word_length': 4.351789331532748, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Application of non-uniform laxity to EDF for aperiodic tasks to improve task utilisation on multicore platforms

This paper proposes a new scheduler applying the concept of non-uniform laxity to Earliest deadline first (EDF) approach for aperiodic tasks. This scheduler improves task utilisation (Execution time / deadline) and also increases the number of tasks that are being scheduled. Laxity is a measure of the spare time permitted for the task before it misses its deadline, and is computed using the expression (deadline - (current time + execution time)). Weight decides the priority of the task and is defined by the expression (quantum slice time / allocated time)*total core time for the task. Quantum slice time is the time actually used, allocated time is the time allocated by the scheduler, and total core time is the time actually reserved by the core for execution of one quantum of the task. Non-uniform laxity enables scheduling of tasks that have higher priority before the normal execution of other tasks and is computed by multiplying the weight of the task with its laxity. The algorithm presented in the paper has been simulated on Cheddar, a real time scheduling tool and also on SESC, an architectural simulator for multicore platforms, for upto 5000 random task sets, and upto 5000 cores. This scheduler improves task utilisation by 35% and the number of tasks being scheduled by 36%, compared to conventional EDF.


I INTRODUCTION
In multicore platforms, when normal scheduling algorithms like EDF (Earliest Deadline First) are used, tasks are scheduled based on the actual allocation of resources. EDF schedules tasks in the order of increasing deadlines. In such approaches, task utilisation is poor, as there is no room for scheduling newly arriving tasks. This results in some tasks missing their deadline due to exhaustion of resources. Hence new techniques have to be incorporated to schedule newly arriving tasks as explained by Burchard et al in [1].
To overcome the above mentioned drawbacks of task utilisation, priority is used as one of the criterion for scheduling, as explained by Moir and Ramamurthy in [2]. Each task is assigned a weight that is based on the priority of the task.
The scheduling is carried out, according to this weight. Fairness is a criterion by which scheduling is decided. Fairness is granted to the task in proportion to the weight, and resources are allocated proportionate to fairness. This strategy is termed as proportionate fairness or pfairness. Here, tasks are scheduled by utilizing only a small portion of the allocated resource for each task. The remaining resource for each task is cumulated and later utilized for scheduling newly arriving tasks.
This strategy restricts the migration overhead around quantum bounds ranging from -(γ + cα/2) to +(γ + cα/2), where γ is the queue overhead, c is the average number of tasks in the queue and α is the start time for execution of first task in the execution queue as explained in [3] by Calandrino et al.
On applying the concept of proportionate fairness, only a small quantum of resources is utilized. The remaining of the allocated resources can be cumulated as laxity for use for newly arriving tasks. Laxity is a measure to identify the slack time and the urgency for the execution of tasks.
Laxity as applied to scheduling is of three categories namely zero laxity, least laxity first and uniform laxity.
In the zero laxity approach, a task is dispatched for execution when laxity becomes zero. In this approach, the scheduler does not act until laxity becomes zero. The overhead imposed on the scheduler increases rapidly, as a number of simultaneous decisions need to be taken if multiple tasks arrive with zero laxity. For a two core system under zero laxity condition, the task utilisation is modified by a factor of 1.5 + |u max -0.5| as discussed by Wen et al in [4]. Tasks can be scheduled on a two core system only if the task utilisation is less than or equal to (z+1) / 2 as explained by Piao et al in [5]. By applying a pure zero laxity condition to EDF scheduling strategy, task sets are not schedulable when U(T) > z * (1-(1/e)), where z is the number of cores and e is the Euler's number as explained by Yi-Hsiung Chao et al in [6]. Hence U(T) is always <( z * (1-(1/e))) for tasks to be always schedulable by the laxity condition.
In the least laxity approach, tasks are sorted in order of ascending laxity and tasks with least laxity are executed first. The main drawback in this approach is that the priority gets revised when tasks newly arrive, and the earlier laxity computation gets modified with respect to the revised priority as explained by Baker in [7].
While using uniform laxity, laxity is computed for tasks initially assigned on that core and for those that arrive later, ensuring equal priority for all tasks. When priorities vary, this strategy tends to break down as explained by Dertouzos and Mok in [8]. However, uniform laxity does not yield an improvement in task schedulability as the priority is treated as unity and there is possibility of over or under utilisation of resources allocated without recalculation of weights.
In this paper, a new approach namely non-uniform laxity is applied to EDF, wherein laxity is recomputed taking revised priority into account for newly arriving tasks. This facilitates scheduling tasks in proportion to the resources actually needed for execution.
The algorithm also ensures the scheduling constraint U(T) < Z* (1-(1/e)), where z is the number of cores, and e is Euler's number. Laxity is monitored with respect to the task utilisation based on the weight, which is a measure of priority.
The algorithm has been simulated on Cheddar, a real time scheduling tool in [9] and [10] to check the scheduling constraints and also on SESC, an architectural simulator in [11] and [12] to check the schedulability on multicore platforms. This algorithm has been tested varying random task sets upto 5000 and number of cores upto 100. The algorithm improves task utilisation by 35% and increases the number of tasks scheduled by 36%, compared to conventional EDF.
The paper is organized as follows: Section II discusses the algorithm and an example. Section III discusses the Cheddar and SESC simulation results of the algorithm in multicore platforms. Section IV concludes the work and presents the scope for future work.

II ALGORITHM
The main components of the algorithm are explained below: A. Laxity computation: The laxity of the task is a measure for slack time. The laxity is computed by the equation laxity = (deadline of task -(current time of task +execution time for task)).
The laxity gives an intuitive direction for task execution. The following are the three cases for laxity computation.
(i) Positive laxity: When laxity of a task is positive, the execution can be delayed, and the task can be placed in a holding queue. (ii) Zero laxity: When laxity of a task is zero, the task needs to be dispatched immediately to the execution queue, failure to do so might lead the task to miss its deadline. (iii) Negative laxity: When laxity of a task is negative, the task has missed its deadline and the same is discarded from the holding queue. Normally this condition is eliminated by the algorithm.

B. Weight computation:
Each task is assigned a weight in proportion to its respective priority. The weight of the task is computed based on the quantum slice time used for executing the task. The weight of the task is computed by the equation Weight of task = ((Quantum slice time used / Actual time allocated by the scheduler)*Total time allocated by each for each task).
The quantum slice time is the time actually used for execution of the task.
The actual time allocated is the time allocated initially by the scheduler for all tasks. This indicates the complete resources held by the scheduler.
The total core time for the task is the time allocated by the core for continuous execution of a single quantum of the task.

C. Non-uniform laxity:
The non-uniform laxity of each task is computed by the equation Non-uniform laxity = (laxity of the task * weight of the task) This modified laxity facilitates scheduling of tasks that arise due to preemption or tasks which arrive later.

D. Task utilisation:
The task utilisation is computed by the equation Original task utilisation = execution time of task / deadline of the task, for aperiodic tasks. Modification factor for task utilisation =1.5+ (|maximum task utilisation for task set -0.5 |) Modified task utilisation is computed by the equation Modified task utilisation = (Modification factor * original task utilisation).
The main steps of the algorithm are outlined below: • Start scheduling tasks using EDF.
• Execute tasks on the respective cores. // For more than 2 cores if (modified task utilisation <2), then append task to holding queue H. If (modified task utilisation >=2), then append task to execution queue X. • Execute the tasks on the respective cores.
//Compute the weight of the tasks. • Weight of task = ((quantum slice time/total allocated time by scheduler)*total core time for execution of one quantum of the particular task) //Compute laxity and non-uniform laxity of the tasks. • Laxity of the task = (deadline-(current time + execution time)) • Non-uniform laxity of the task = (laxity of the task * weight of the task). //Check non-uniform laxity conditions to remove task from holding queue and append to execution queue. • If (non-uniform laxity >0), then append task to holding queue. • If ((non-uniform laxity =0) & (modified task utilisation <2)), then urgently remove task from holding queue and append to execution queue. • Execute task on same core.
• If (modified task utilisation <2), then execute task on next core. • If ((non-uniform laxity<0) & (modified task utilisation > L)), then the task has missed its deadline. As a proof of concept, the working of this algorithm for an example task set is presented below:

A Example
A task set comprising of six tasks is assumed to be scheduled on four cores. The tasks are intra-sporadic. (Tasks can be scheduled in a random manner with respect to a particular core.). Table I indicates the arrival time, execution  time,   The weights for the tasks are calculated as a proportion based on the actual used time for execution. The weight for each task is computed, based on the relation weight=((quantum slice time / Allocated time for each task by the scheduler)*Total time on the core allocated for each task).
Laxity for the task T2 is (140 -(100 + 0)) (vide table I, row 2 ) = 40 units (vide table II, row 2). Task T2 uses (40*0.9) which is 36 units (vide table II, row 2) which is the non-uniform laxity. This is the time actually utilized by the task for execution out of the totally allocated time of 100 units (vide table I, row 2). The algorithm is simulated using Cheddar tool. Cheddar facilitates monitoring task utilisation and corresponding laxity. Cheddar also identifies tasks that have to be dispatched urgently to execution queue.  1 and table I). Task utilisation on core 1 is 0.87 (obtained by adding 0.64 and 0.23). Similarly task utilisation for core 2, core 3 and core 4 are 0.94, 0.87 and 0.66 respectively. The task utilisation for conventional EDF for aperiodic tasks is computed based on execution time and deadline. The execution cost / deadline is the task utilisation. For example, for task 1, utilisation is 80/125 (vide table I) i.e, 0.64 (vide table II). Similarly the other task utilisations can be computed and then the task utilisations on each core are summed up. This total task utilisation on each core does not exceed 1, as is obvious from Fig 1. The average task utilisation on core 1 is 0.44 (dividing 0.87 which is total task utilisation on core 1, by 2 which is the number of tasks scheduled on core 1). Similarly average task utilisations for core 2, core 3 and core 4 are 0.47, 0.43 and 0.16 respectively. The average task utilisations of the task without including the laxity factor comprising of task utilisations 0.44, 0.47,0.43 and 0.16 is 0.38. This value is the task utilisation of the entire task set for conventional EDF. This approach completely exhausts all the resources allocated by the scheduler initially, and newly arriving tasks can not be accommodated resulting in infeasible schedule.  Fig 2. shows the schedule after incorporating nonuniform laxity approach. Task utilisations are modified by the factor 1.5 + (| u max -0.5 |). The maximum of the task set is then computed. From table II u max = 0.32 (vide table II, row 1). u max is computed as the maximum task utilisation from the modified task utilisations (vide table II). The modification factor for task utilisation is then computed as 1.5+(|0.32-0.5|) i.e., 1.5+0.18=1.68. Tasks are monitored for the condition U(task i ) < (z * (1-(1/e))) so that no task misses the deadline. The value of (z*(1-(1/e))) is 2.528, where Euler's number e is 2.718 and the number of cores z is 4. The modified task utilisation is (1.68*0.71) =1.19 which is < 2.528. Task utilisation for a two core system is always less than (z+1) / 2. The task utilisation for conventional EDF for first two cores computed from fig 1, is 0.87+0.94 = 1.81 which is < 2. After incorporating non-uniform laxity, task utilisation for T1 and T4 are 0.64 and 0.54 respectively (derived from fig II). Hence the task utilisation on core 1 is 1.68*(0.64+0.54)=1.98, where 1.68 is the modification factor. Similarly for core 2, core 3 and core 4, the task utilisations are 1.19, 1.71 and 1.78 respectively. The average task utilisation on core 1 is 1.96/2=0.98 as number of tasks is 2 (vide fig 2). Similarly for core 2, core 3 and core 4 the average task utilisations are 1.19, 0.57 and 0.89 respectively. The average task utilisation for the entire task set having task utilisations 0.98,1.19,0.57 and 0.89 is 0.91. This value is the task utilisation of the task set after incorporating nonuniform laxity.
The algorithm has been simulated using Cheddar tool and the SESC simulator. The results are provided in the next section.

A Task Utilisation
The improvement in task utilisation has been analysed using Cheddar, a real time scheduling tool .  Table III indicates the percentage improvement in task utilisation for the algorithm proposed in this paper, compared to the conventional EDF. The average task utilisation is 0.75 for the proposed algorithm compared to 0.60 in conventional EDF. It can be seen that task utilisation improves by 31% with increase in number of cores. 5000 random task sets are simulated on 100 cores, so that an average of 50 task sets are scheduled on each core. It is seen from table III that per task utilisation on applying non-uniform laxity approach to EDF is 0.015 i.e., 0.75/50 where 0.75 is the average task utilisation and 50 is the average number of task sets per core. (Vide table III), whereas per task utilisation for conventional EDF is only 0.012 i.e., 0.60/50 (Vide table III). Hence there is a significant improvement in per task utilisation. It is observed that the task utilisation for EDF coupled with non-uniform laxity for 100 cores is 0.45, compared to 0.27 in conventional EDF thus improving task utilisation by 67% (vide Table III and fig 4). As such, application of nonuniform laxity significantly improves task utilisation in multicore platforms.  Table IV shows the task utilisation values when simulation was done using SESC, which are almost similar to the results obtained from Cheddar.

B Task Schedulability
Task schedulability is the number of tasks that are being scheduled. Task schedulability has been analysed using both Cheddar and SESC tools and results are tabulated in table V and VI respectively, which show that task schedulability increases by 36 %.