## 2 Materials and Methods
### Memory Allocation for Non-Real-Time Tasks  
#### 2.2.1 Problem Description  
In the non-real-time zone, we model the memory allocation problem as a special type of knapsack problem, which can be described as follows: Suppose there are multiple items, each with a different value, and several knapsacks. For these items, we need to select a packing strategy that fits them into one or more knapsacks in order to maximize the packing value without exceeding the capacity of the knapsacks. In the memory allocation environment of edge PLCs, this problem can be described as allocating corresponding free memory blocks for multiple memory requests with the aim of achieving maximum allocation value. Table 1 shows the correspondence between the concepts in the knapsack problem and the memory allocation problem.  
Specifically, in this problem, the value of an item is not fixed. Instead, it is associated with the knapsack in which it will be placed. The value generated by a memory allocation decision is negatively correlated with the size of the memory fragmentation caused by that decision. The variables involved in the non-real-time zone are shown in Table 2.  
Considering a decision to allocate \(m_{i}\) to \(Req_{j}\), \(Value_{i}^{j}\) can be represented as:  
\[Value_{i}^{j}=\frac{MaxMem}{mSize_{i}-ReqSize_{j}+1} \tag{1}\]  
For an allocation decision, the smaller the fragmentation it produces, the greater the value generated by making that allocation. An allocation relationship cannot be established in the non-real-time zone when \(mSize_{i}\) is less than \(ReqSize_{j}\). In this case, we consider this allocation method to have no value, with a value of 0. Therefore, the value generated by the decision to allocate \(m_{i}\) to \(Req_{j}\) can be represented as follows:  
\[Value_{i}^{j}=\begin{cases}0&\text{if }mSize_{i}<ReqSize_{j},\\ \frac{MaxMem}{mSize_{i}-ReqSize_{j}+1}&\text{if }mSize_{i}\geq ReqSize_{j}. \end{cases} \tag{2}\]  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Concepts in Knapsack Problem** & **Concepts in Memory Allocation** \\ \hline Knapsack & Free memory block \\ Knapsack capacity & Size of free memory block \\ Item & Memory request \\ Item weight & Size of memory request \\ Item value & Value of the allocation decision for the item \\ Item selection scheme & Allocation decision for free memory blocks \\ \hline \hline \end{tabular}
\end{table}
Table 1: Correspondence between the knapsack problem and the memory allocation problem.  
\begin{table}
\begin{tabular}{c c} \hline \hline
**Variable** & **Meaning** \\ \hline \(Mem\) & Set of free memory blocks \\ \(m_{i}\) & Free memory block \(i\) \\ \(mSize_{i}\) & Size of free memory block \(i\) \\ \(Req_{i}\) & Memory request \(i\) \\ \(ReqSize_{i}\) & Size of memory request \(i\) \\ \(Dec_{i}\) & Allocation decision for memory request \(i\) \\ \(MaxMem\) & Maximum available memory size in edge PLC \\ \(MCF_{i}\) & Memory compression factor of free memory block \(i\) \\ \(Value_{i}^{j}\) & Value of allocating free memory block \(i\) to memory request \(j\) \\ \(HeadSize\) & Size of memory header information \\ \(S_{(i,j)}^{k}\) & State variable for memory request decision \\ \hline \hline \end{tabular}
\end{table}
Table 2: Variables in the non-real-time zone.  
During the process of solving this memory allocation problem using dynamic programming, considering an increasing number of memory requests simultaneously can lead to exponential growth in the required solution space, resulting in the curse of dimensionality. The high cost of the solution space is unaffordable for edge PLCs with limited memory resources. Therefore, this paper only considers scenarios where each allocation involves two memory requests in order to achieve a balance within the limited memory space. The memory allocation in the non-real-time zone is shown in Figure 4.  
The following sections will solve the memory allocation problem according to the general process of dynamic programming.