# 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.1 Memory Load-Based Scheduling  
When there is no free memory, it indicates that the memory of all worker nodes is full. In this case, a loss occurs even when a task is distributed to a worker node, and the task results cannot be used. Therefore, this paper proposes a method for delaying tasks with lower priorities based on the deadline and the CPU usage according to a priority queue. Equation (1) is used for calculating the deadline of a task. \(T_{n,cpu}\) denotes the CPU usage of task \(T\) in worker node \(n\). \(T_{n,start}\) denotes the starting time of task \(T\) in worker node \(n\), whereas \(T_{n,dline}\) represents the deadline of task \(T\) in worker node \(n\). _Now_ refers to the current time. The current time is divided by the sum of the starting time and deadline. At this time, the closer the current time is to deadline, the closer the value is to 1. Since the closer the value is to 1, the closer the task is to deadline, it should be processed as soon as possible. Therefore, tasks with high values assign high priorities. If a task fails to process within the deadline, it is calculated as higher than 1 because the start time plus deadline is less than the current time value. In this case, since the value is also greater than 1, even \begin{table}
\begin{tabular}{c c} \hline \hline
**Notation** & **Definition** \\ \hline Task\({}_{\text{id}}\) & Task ID \\ Node\({}_{\text{id}}\) & Worker node ID \\ Time\({}_{\text{start}}\) & Task input time \\ Time\({}_{\text{dline}}\) & Task deadline \\ CPU\({}_{\text{use}}\) & Task’s CPU usage \\ Memory\({}^{\text{use}}\) & Task’s memory usage size \\ Network\({}^{\text{use}}\) & Task’s network usage \\ \hline \hline \end{tabular}
\end{table} 
Table 2: NMonitor table information. tasks that exceed deadline are assigned high priority. A high weight is assigned to a task closer to the deadline considering the CPU usage and the deadline of the task. The value is high as the CPU usage is high and the deadline is close. \(\alpha\) is a weight parameter that means how much more the task deadline will be considered. \[T_{n,dead}=T_{n,cpu}*\left(\alpha*\frac{Now}{T_{n,start}+T_{n,dline}}\right) \tag{1}\]  
When a memory load occurs, Equation (1) is used to calculate the priorities of the tasks. Subsequently, each worker node enqueues the tasks with the lowest priorities in the priority queue. This process is repeated until a memory space is in the acceptable space, and the tasks with higher priorities are processed first. When a task is processed in each worker node, those remaining in the priority queue are dequeued to continue the processing of the tasks. The memory load is reduced by this scheduling scheme; when a new task is requested during dynamic task scheduling based on the memory load, the task is enqueued based on the priority queue to prevent the memory load. For the CPU usage of a new task, the average CPU usage of the tasks in the priority queue is used. Figure 4 shows an example the memory load-based scheduling. Each worker node is allocated three tasks, where the CPU and memory usage of each task are assumed to be identical. Moreover, it is assumed that the memory usage of all worker nodes is \(\geq\)80% (no available memory). Assuming the current time (_now_) is 4, the starting time (s) and deadline (_d_) of each task are defined in advance. When the CPU usage and deadline of each task are calculated using Equation (1), they are provided at the top of the tasks. For instance, the starting time of _Task1_ is 1 and deadline is 5; thus, the result of Equation (1) is 0.66. In this study, a higher value indicates a higher priority. When a memory load occurs in this scenario, each worker node selects the tasks with the lowest priorities until free memory becomes available. Worker nodes 1, 2, and 3 select Tasks 4, 7, and 3, respectively. The selected task stops the task in a worker node and subsequently stores the respective task in a separately generated priority queue based on priorities.