An Improved LLF Scheduling for Reducing Maximum Heap Memory Consumption by Considering Laxity Time
Yuki Machigashira, Akio Nakata · 2018
Real-time embedded systems are often designed as multiprocessor systems in order to achieve both low power consumption and high-performance. Also, they are often implemented as multitasking systems in order to meet deadline constraints of response times for multiple external inputs. However, multitasking systems often increase heap memory consumption allocated for temporal use, because the allocated memories for tasks often remain allocated simultaneously when the tasks are suspended for switching to the other task. In order to reduce memory consumption in real-time multitasking, in this paper we propose an improved real-time scheduling algorithm based on LLF (Least Laxity First) to reduce maximal heap memory consumption by controlling multitask scheduling, without modifying the processing order of each task. The proposed algorithm firstly performs LLF schedulability analysis (proposed in [5]) in each scheduling cycle and then switches between LLF and our proposed Least Memory Consumption First (LMCF) scheduling policies appropriately according to the analysis result. The proposed LMCF scheduling assumes that the amount of the heap memory allocation in the next step near future for each task can be predicted and according to the prediction it selects the least ones as many as the number of the processors for schedule. We evaluate the effectiveness of the proposed algorithm by comparing the heap memory reduction ratio of the proposed algorithm with that of LLF scheduling.