# Dynamic Task Scheduling Scheme for Processing Real-Time Stream Data in Storm Environments
## 3 The Proposed Dynamic Task Scheduling Scheme
### Dynamic Task Scheduling
#### 3.3.2 CPU Load-Based Scheduling  
When the computation of a task being processed in a worker node is complex, computation of the CPU increases, thus increasing the CPU usage. In this case, a delay in the task processing occurs when a load is applied on the CPU. When the CPU usage increases owing to the computation complexity of a task, the loads on the worker nodes are classified based on the CPU usage to examine whether the task can be redistributed to free nodes with less loads. When redistribution is possible, the throughput from redistributing the respective task to a free node is calculated, and the task is redistributed if the free node does not become loaded. If it is determined that a load occurs when a task is redistributed to a free node, another free node is selected again to be processed.  
Equation (2) is used for measuring the average CPU usage of each worker node, where \(CPU_{exp}\) is the average CPU usage of the entire worker node, \(N\) is the total number of worker nodes, and \(CPU_{n,use}\) is the CPU usage of worker node \(n\). The average CPU usage of all worker nodes is computed based on the above \(CPU_{exp}\) values. Using the \(CPU_{exp}\) values measured using Equation (2), the average CPU usage of all worker nodes is calculated, where the loaded and free nodes are distinguished based on the deviation between the \(CPU_{exp}\) and CPU usage of each worker node.  
\[CPU_{exp}=\frac{1}{N}\sum_{n=1}^{N}CPU_{n,use} \tag{2}\]  
Figure 4: Memory load-based scheduling.  
The loaded and free nodes can be determined using Equation (3) based on the CPU usage. Equation (3) finds the deviation in the CPU usage between \(CPU_{exp}\) and the CPU usage of each worker node, where \(CPU_{n,dev}\) is the deviation between \(CPU_{exp}\) and the CPU usage of worker node \(n\). A deviation value closer to a negative number indicates that the CPU usage exceeds the average value. A worker node with the smallest deviation value is classified as a loaded node, whereas that with the largest deviation is classified as a free node. When the free memory size of a worker node classified as a free node is less than the threshold, a loss of task may occur. In this case, a worker node with a large deviation is classified as a free node, excluding the worker node classified as a free node.  
\[CPU_{n,dev}=CPU_{exp}-CPU_{n,use} \tag{3}\]  
Among the loaded nodes classified using Equation (3), certain tasks being processed are migrated to the free nodes to balance the CPU usage of the loaded nodes. The tasks being processed in loaded nodes are selected based on the deadline and average CPU throughput of a worker node. If the average CPU throughput of a loaded node is higher than that of a free node, a task with a deadline far from the current time is selected, or a task with a close deadline is selected, to be migrated. The deadline value is calculated using Equation (1).  
Figure 5 shows the occurrence of a load on worker node 3 caused by an increase in the CPU usage. In the following scenario, the average CPU usage (56%) is calculated using Equation (2), and the CPU deviation is calculated using Equation (3) to select worker node 1 with a high deviation value as a free node. In worker node 3, a task to be migrated is selected based on the deadline and the average CPU throughput. Because worker node 3 has a higher throughput than worker node 1, it is more efficient to process a task with a closer deadline from worker node 3. Therefore, \(Task_{10}\) with a deadline that is relatively farther from worker node 3 is selected to be migrated. The selected task is migrated to worker node 1, and the NMonitor and load table are updated based on the migrated task. The average CPU usage is increased from 56% to 65%, whereas the load is balanced evenly.