# Affinity-Based Task Scheduling on Heterogeneous Multicore Systems Using CBS and QBICTM
## 2 Materials and Methods
### Quantum Based Intra Core Task Migration Load Balancing Scheduler  
Fair and even load balancing is performed on a heterogeneous system by using a quantum based intra core migration of tasks. The working mechanism of the quantum based intra core migration of tasks is presented in Figure 4.  
The processing speed of each core in a multicore architecture is computed. The cores are sorted in increasing order according to their respective processing speeds. Each task which is to be processed on a multicore system is given a fair and equal chance to run on the fastest core. A time quantum is introduced at the fastest core and tasks are being processed on a first come first served basis from each core's own private queue. Each core in a heterogeneous multicore system owns a private queue from where the tasks are allocated to a core and which functions like a ready queue for that core. The maximum and minimum threshold is defined for each core's queue for the total number of tasks present and as soon as the number of tasks in any queue is less than the defined minimum threshold, an intra core migration of tasks occurs. Every running task on each core is migrated to the next corresponding core's ready queue as shown in the Figure 4. When a task utilizes its quantum while running on the fastest core, the CPU is preempted from the task and it is migrated to the ready queue of the next in line processing core, i.e., 2 nd fastest core. When the CPU is preempted from a task running on the fastest core, the number of tasks in the queue of the fastest core falls below the minimum threshold. This is because the next task waiting in the queue will be allocated to the fastest core. In that case, the task running on the slowest core is migrated to the fastest core's private queue or ready queue and the current state of the task is saved. The total number of tasks in each queue of the multicore system is computed as  
\[Cl_{\text{a}}=\left\lceil\frac{t_{t}}{c_{c}}\right\rceil \tag{10}\]  
Whenever a quantum of a certain task running on the fastest core expires, the number of tasks in the queues of all the cores of a heterogeneous system fall below a defined minimum threshold and intra core migration of the tasks takes place. Using the described technique helps us eliminate problems related to load balancing on heterogeneous systems. The load balancing issue in heterogeneous systems, vis-a-vis that the fastest core finishes the tasks allocated much more quickly than the slowest core in the system, is addressed in our research and has been minimized. Our proposed technique ensures that the fastest core will always process a task as long as other cores are operating and the tasks are available for processing. Thus, the problem we dealt with to some extent is that one core may be under-loaded or idle while another core may be over-loaded even after fair and equal distribution through load balancing in heterogeneous systems. Algorithm 2 describes the QBICTM scheduling of tasks. When a quantum of a certain task expires the intra core migration of tasks takes place and the next task waiting is allocated to the fastest core. Figure 4: Working mechanism of QBICTM scheduler. ```
Inputs: Allocating each cluster \(\text{cl}_{a}\) to a Core \(c_{m}\) Outputs: BEGIN
1. Make clusters of tasks = Number of cores available
2. Tasks in each Cluster \(\text{Cl}_{a}=\left\lceil\frac{Total\ Number\ of\ tasks}{Total\ Cores\ available}\right\rceil\)
3. Compute processing speed of each core \(c_{m}\) in set of Cores C
4. Allocate one cluster \(\text{cl}_{a}\) to exactly one Core \(c_{m}\) ensuring load balancing with each core getting fair and equal number of tasks to process
5. Tasks T in each cluster \(\text{cl}_{a}\) are queued onto the core \(c_{m}\)
6. Introduce a time quantum at the fastest core, each task getting fairly equal time for processing at fastest core in one cycle
7. When time quantum for a task expires, preempt core \(c_{m}\) from the task \(t_{t}\) and allocate next task waiting in queue onto the core
8. for each core \(c_{m}\) do
9.