Resource Reservation and Energy Management Framework in Linux Kernel

A Linux kernel framework that involves Linux scheduler, timers, signals, system calls, sysfs interface and Android applications to reserve applications based on timing, cpu, and power constraints.

Part 1: Process Budget Accounting and Instrumentation
In real-time systems, it’s critical to guarantee that thread will never exceed its allowed compute time. However, threads are not that obedient in practice and may overrun their budget due to inference from non-realtime best effort tasks or an inaccurately estimated worst case execution time.
To maintain the safety of the system, we implement a resource reservation framework in the kernel that will keep track of and enforce the thread budgets. In this part, the main features includes periodic test applications, reserve management syscalls, kernel instrumentation for task utilization measurement, and task monitor android application. Figure 1. utilization data display

Figure 1 consists of two tasks onto which reserves with periods T0 = 10 ms and T1 = 8 ms respectively were set. Reserve on Task 0 was set before monitoring began. Task 0 does the same amount of computation (2.5 ms) each period: U0 = 2.5/10 = 0.25. Reserve on Task 1 was set while the monitoring was in progress. The utilization of Task 1 varied from 0.5 in its first recorded period to 0.75 in its second period and to 0.625 in its remaining two periods.

Part 2: Reservation Enforcement and Guarantee
In part 1, we associated a reservation with a thread and accounted the computation time it consumed. However, when a thread exceeded its budget the most our kernel did was to notify the offender with a harmless signal. In this part, we endow the reservation framework with the ultimate power of suspending and resuming threads so that a thread can only run while its budget lasts.
In this part, the detailed features includes reservation enforcement, reservation guarantees (reservation status, admission test on one processor, admission test on many processors).
In the admission test on many processors part, we implemented the following bin-packing heuristics for assigning tasks to processors. The “bins” are the physical processors that exist on the platform.

  • First-Fit
  • Next-Fit
  • Best-Fit
  • Worst-Fit

The following two figures show the overview of the resource reservation framework.
Figure 2. architecture of resource reservation part

Figure 2 shows the architecture. Basically, the Linux kernel of the framework provides two mechanisms to communicate with user application: sysfs interface and system call. ysfs interface can be used to query the framework information like task utilization for all the reserved tasks, energy consumption tracking and overall system power consumption. And system calls include reserve/cancel task reservation, and end a specific task. And user application can utilize the Android Java Native Interface to communicate with high level Android Application.

Figure 3. flow chart of resource reservation part

Figure 3 shows the processing flow of the framework. Basically, it will check the schedulability of a task and then determine which core it will be assigned to if the system detects that it can be scheduled.

Part 3: Energy Management
In the previous parts, we focused on the resource reservation framework, and in this part we switched to energy management for Linux tasks. The detailed features includes kernel support for energy tracking, energy monitor native application, energy-efficient task partitioning, and energy-efficient sleep scheduling. Also, we did the energy comparision experiment for different energy management algorithms like WFD, BFD, LST, ES-RHS+. Figure 4. energy consumption comparision experiment

Figure 4 shows the average energy consumption’s change when total task set utilization increases from 0.36 to 0.86. We can conclude that the energy saving effect of LST and ES-RHS+ are more efficient compared to WFD and BFD. This phenomenon is consistent with the explanation that “A corollary of a balanced load is that the load on each service provider is at the minimum. The latter property is particularly useful for energy-efficient task partitioning. Energy of a processor is determined by its frequency, which is constrained by the load allocated to the processor. The list policy can be naturally adapted into a bin packing or real-time task partitioning policy: assign a task to the core with the smallest load so far. The cores that currently have no tasks assigned to them have zero load and always participate as candidate bins. This differs from Worst-Fit-Decreasing policy which opens a new bin only when the current bins cannot accommodate the object. Since the list policy minimizes the load and hence the frequency on individual processors, it should save energy.”

Figure 5. energy simulation using Python

We also write a python program to simulate the energy consumption comparison experiment as shwon in Figure 5. We generate 35 tasks for every policy (5 tasks as a taskset) and control the average utility of those taskset in an ascending order. From the phote above, the energy consumption of WF and BF are similar, and LST and ES-RHS+ are similar. But, ES-RHS+ fluctuate more heavily than LST.

Written on December 21, 2016