## 4 Design of STUN
### Overview  
STUN is designed to use the Q-learning algorithm. For reinforcement learning, we tried the deep Q-network (DQN), which is most widely used for reinforcement learning. However, we decided not to use DQN because it consumes a lot of computational power and memory, and if it uses a CPU only without a GPU, takes too long for learning [17]. Actually, it cannot search the optimal parameters of a kernel scheduler within a reasonable time. The Q-learning algorithm is lighter than deep learning and consumes less memory. Therefore, STUN adopts the Q-learning algorithm, and this is a better choice considering the implementation of STUN within the Linux kernel later. Figure 2 shows the structure of STUN. STUN consists of an environment module and an agent module. The environment module defines the environment for kernel parameter optimization, and the agent module defines the Q-learning algorithm and executes the agent. The reset and step functions defined in the environment module are as follows. * **Reset (self, f = True)** This function initializes the parameters to optimize. The reset is used to prevent the excessive accumulation of rewards for a specific parameter value during learning. It initializes the value randomly up to half of the total number of learning times and the rest of them at the values showing the best performance. * **Step (self, action):*
* STUN returns a state, reward, and done after conducting a test workload with the changed parameter values according to an action value. The meaning of each variable is as follows. * This is a value that determines the increase or decrease in each parameter. When optimizing n parameters, it has n + 1 values from 0 to n. STUN changes the optimized values by adding or subtracting a predefined value \(\alpha\). \begin{table}
\begin{tabular}{c c c} \hline \hline
**Parameter** & **Default Value** & **Range** \\ \hline latency\_ns & 24,000,000 & 100,000\(\sim\)1,000,000,000 (1 s) \\ migration\_cost\_ns & 500,000 & 0\(\sim\)1,000,000,000 \\ min\_granularity\_ns & 3,000,000 & 100,000\(\sim\)1,000,000,000 (1 s) \\ nr\_migrate & 32 & 0\(\sim\)\(\sim\) \\ rr\_times\_times\_ & 100 & 0\(\sim\)1000 \\ rt\_period\_us & 1,000,000 & 900,000\(\sim\)1,000,000 \\ rt\_runtime\_us & 950,000 & 0\(\sim\)1,000,000 \\ cfs\_bandwidth\_slice\_us & 5000 & 0\(\sim\)1,000,000 \\ wakeup\_granularity\_ns & 4,000,000 & 0\(\sim\)1,000,000,000 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Initial settings of 9 scheduler parameters and modifiable ranges. Figure 2: Structure of STUN. **State:** This is an element used to indicate the value of the parameter to be learned for optimization. Each parameter is divided into equally 50 within the range that can be modified, and each state has a value of 0 to 49 and is expressed as \((s_{1},s_{2}\ldots s_{n})\). **Reward:** As a result of the test workload, this is used to determine whether better performance is achieved than under the previous state. **Done:** This is an element used to finish this episode of learning for efficiency. The \"done\" flag is initialized to true. If the result of the test workload is less than 20% of the default performance, it returns false. If more than a certain number of false values consecutively occur, the episode ends. The agent module defines the Q-table, which records the value of the action when a certain action is conducted under each state. STUN updates the Q-table by using the Q-learning model and the value function \(Q(s_{t},a_{t})\). The value obtained from the value function is the expected value that can be obtained in the future, rather than judging the good or poor values at the present moment, unlike the reward value. The Q-leaning algorithm updates the expected value of the state in the Q-table each time it acts, and then selects the action with the largest expected value. The formula for updating the Q-value is as follows.