1. Introduction
Real-time systems are characterized not only by their functional traits but also by their temporal ones [
1]. For instance, in automotive systems, the wheel control system’s precise execution within a set timeframe, or deadline, is vital for accurate vehicle control. A key technique in designing such systems is real-time scheduling, which allows for the efficient distribution of computing resources like CPU and memory within the system. Real-time scheduling research primarily focuses on two critical areas: the design of scheduling algorithms and schedulability analysis. The former determines the execution order of real-time tasks, while the latter involves a mathematical assessment of whether a system can meet its deadlines under a scheduling algorithm [
2,
3,
4,
5].
In recent decades, real-time systems have made effective use of multiprocessor platforms to execute tasks with substantial computational demands [
6]. This trend has spurred extensive theoretical research in real-time scheduling. Some studies have introduced new real-time scheduling algorithms that effectively alter task priorities during runtime [
7], while others have concentrated on theoretical optimality or clarifying the relationships between different scheduling algorithms [
8]. Additional research has proposed execution techniques that can be incorporated with existing scheduling algorithms [
9,
10,
11].
Emphasizing the latter approach is vital, given its potential to enhance both current and future algorithm scheduling performance. The Zero-Laxity (ZL) [
9] policy and the Contention-Free (CF) policy [
10,
11] are successful examples of this approach. The ZL policy reduces deadline violations by assigning the highest priority to a real-time task at an instant where the task would fail to meet its deadline if not immediately executed. Conversely, the CF policy enhances the feasibility of executing other real-time tasks by assigning the lowest priority to a task at a moment when it is guaranteed not to miss its deadline during the remaining execution time [
12,
13,
14].
The CF policy has been extensively studied in the field of scheduling due to their broad applicability and the performance enhancement benefits they offer to existing scheduling algorithms. However, existing studies are largely confined to preemptive scheduling, leaving the efficiency and applicability of limited preemption scheduling unexplored. Limited preemption scheduling permits a job to execute to completion with a limited number of preemptions, distinguishing it from preemptive scheduling. This scheduling type is essential when preemption or migration overheads are either excessively large or unpredictable.
In this paper, we introduce SP-CF, a single preemption scheduling approach that incorporates the CF policy. SP-CF allows a preemption only once during each job’s execution, following a priority demotion under the CF policy. We also propose a new schedulability analysis method for SP-CF to judge whether each task is executed timely and without missing its deadline. The performance of this technique is evaluated using simulation-based experiments.
Section 3 discusses the system model and basic concepts targeted in this study.
Section 4 presents the operation of the single-preemption scheduling with the CF policy. In
Section 5, we extend the existing schedulability analysis called deadline-based (DA) analysis [
15] to our SP-CF scheduling.
Section 6 uses our Java simulator to analyze the performance of DA analysis, and
Section 2 presents the related work.
Section 8 provides the paper’s conclusion.
2. Related Work
In the past few decades, numerous research studies within the realm of real-time systems have been centered on creating scheduling algorithms for multiprocessor systems. The aim is to enhance the system’s schedulability. Notably, ER-Fair [
16], LLREF [
17], and RUN [
7] have been introduced as the optimal scheduling algorithms for multiprocessor systems, with each iteration refining the scheduling costs [
17]. A salient example is the RUN algorithm, which repurposes the multiprocessor task scheduling problem into a uniprocessor issue, thereby significantly reducing the amount of preemptions when compared to rate-based methodologies.
Simultaneously, an alternate approach has been pursued that involves the creation of scheduling policies designed to enhance schedulability analysis and can be integrated into most existing scheduling algorithms. The ZL and CF policies are prominent examples of such strategies. The ZL policy [
9] boosts a task’s priority to the highest level when it is scheduled to prevent any deadline misses, while the CF policy [
10,
11] reduces the priority to the lowest level when its schedulability is secured. Additional research into the CF policy was conducted to better utilize contention-free slots [
18]. Furthermore, a proposal was put forth for RTA associated with the CF policy.
Numerous studies have been conducted on non-preemptive scheduling for uniprocessor systems. Ekelin presented a scheduling algorithm designed for a set of independent jobs [
19]. Meanwhile, Nasri et al. proposed a scheduling algorithm specifically for the periodic (loose-) harmonic task model [
20,
21]. This model was later improved to support the general periodic task model [
22]. Furthermore, efforts have been made to develop new types of schedulability tests that provide timing guarantees for existing scheduling approaches [
23,
24]. The research has also extended beyond uniprocessor systems. One study examined the scheduling of mixed-criticality tasks [
25], while another research effort focused on scheduling within a multiprocessor environment, which necessitated information about future job release patterns [
6].
4. Single Preemption Scheduling with Cf Policy
In this section, we present the background of the fixed-priority non-preemptive scheduling algorithm with the CF policy and the calculation method for CF slots.
4.1. Scheduling
Firstly, we describe the scheduling patterns of both non-preemptive scheduling and SP-CF scheduling using an example task set.
Figure 1a depicts the scheduling pattern when three tasks,
,
, and
, are executed with the fixed-priority scheduling algorithm in a two-processor system.
Figure 1b illustrates the scheduling pattern when applying the CF policy to the scheduling algorithm. Here, each job is allowed to preempt only once following a priority demotion according to the SP-CF policy. There are numerous methods to assign priorities to tasks within the fixed-priority scheduling algorithm. For this example, we assume that task
has the highest priority, task
holds intermediate priority, and task
has the lowest priority.
As seen in
Figure 1a, tasks
and
are executed on individual processors in the time slots from 0 to 4. Upon completion of these two tasks, task
begins execution. However, the time slot required for task
to complete its execution exceeds the remaining time slots, resulting in a deadline violation at time 10.
Figure 1b portrays a scenario where the application of the CF policy to the fixed-priority scheduling algorithm ensures all tasks can execute without missing a deadline. Initially, the CF policy calculates the minimum number of CF slots existing within each task’s job’s release time and deadline (the method for calculating the number of CF slots will be detailed in
Section 4.2). This calculation reveals at least two CF slots between the release time and deadline of tasks
and
. Between the time slots 0 and 4, there are three runnable jobs and two processors, creating a need for contention slots. According to the CF policy, at time 2, tasks
and
receive the lowest priority, and task
commences its execution. This is because the calculation shows that tasks
and
have at least two CF slots. The lack of contention slots between 0 and 2 implies that the remaining executions can take place in CF slots, ensuring no deadline misses. Thus, by comparing the remaining execution time with the residual CF slots, it is feasible to dynamically lower the priority and efficiently utilize the computational power of the multiprocessor. Please note that a preemption occurs only for
at time 2, following a priority demotion by the CF policy.
As depicted in
Figure 1a, the duration when both processors are occupied is constrained to 4 units. However, as demonstrated in
Figure 1b, when implementing the CF policy, the utilization period of both processors extends to 6 units.
Algorithm 1 describes the execution procedure of the SP-CF scheduling. For each time slot at t, a job released by a task is placed in . The corresponding number of CF slots for the job is calculated, and the remaining execution time and remaining CF slots are initialized with and , respectively (lines 1–3).
Algorithm 1 SP-CF scheduling. |
At each time slot t, |
if a job from is released then |
Place the job into and initialize and . |
end if |
for each job in do |
if the job from satisfies then |
Transfer the job to . |
end if |
end for |
if is less or equal to m then |
Update for all jobs in |
end if |
Assign priorities to jobs within the following three groups: , , and . Group has a strictly higher priority than , and has a strictly higher priority than . Jobs of were executed at time and did not transition from to at time t. Jobs of were released at time t and are currently in . Jobs of that transitioned from to at time t or were present in but were not executed at time . |
Assign priorities to jobs released at t in according to the base algorithms such as EDF and RM. |
Decrease for the (at most) m highest-priority jobs in , , and . |
If a job exists in a time slot at t with a remaining execution time less than or equal to , the job is moved to (lines 4–8). For each job in , if the current time slot is a CF slot, decreases by 1 (lines 9–11). Priorities are then assigned to the jobs in based on a fixed priority algorithm (line 12). Finally, at most m jobs in and are executed, where all jobs in hold a strictly higher priority than all jobs in (line 13).
Priorities are assigned within the following three groups: , , and . The group has a strictly higher priority than , and has a strictly higher priority than .
- :
jobs that were executed at time and did not transition from to at time t.
- :
jobs that were released at time t and are currently in .
- :
jobs that transitioned from to at time t or were present in but were not executed at time .
The following lemma discusses a specific property of SP-CF scheduling concerning the number of preemptions for each job.
Lemma 1. For a given set of real-time tasks on m processors, each job experiences at most one preemption under SP-CF scheduling.
Proof. Let us suppose a job of can experience multiple preemptions. From line 12 in Algorithm 1, it can be observed that running jobs (i.e., jobs executed at time in ) that do not experience a priority demotion (i.e., jobs that do not transition from to ) at time t holds a highest priority compared to jobs in and . Moreover, this priority can only be altered when a job shifts from or to after experiencing a priority demotion, thereby inducing a preemption possibility. This contradicts our initial assumption for the lemma. □
4.2. Contention-Free Slots
As observed in Algorithm 1, the CF policy calculates the minimum number of CF slots that can exist before the deadline of each job (line 2). When the remaining execution time and remaining CF slots of a job become equal during execution, the job’s priority is demoted to the lowest (i.e., moved to ). Jobs with demoted priority can encounter at least as many CF slots as the remaining execution time, ensuring that no deadline miss occurs. In this section, we will explore how to calculate the number of CF slots for each task.
In real-time scheduling with the CF policy, the number of CF slots for each task is precalculated before execution, and its value decreases whenever a CF slot is encountered during execution. The fundamental concept used in calculating the number of CF slots is to analyze the execution loads of all possible jobs between the release time and the deadline of a single job. Afterward, we determine the maximum number of contention slots (i.e., time slots where competition occurs, and the number of running jobs exceeds the number of processors) that the jobs need to compete for processor usage. This value is referred to as the contention slot value. By subtracting the contention slot value from the existing time slots, we can calculate the minimum number of CF slots.
To determine the minimum number of CF slots between the release time and the deadline of job generated by , we first need to calculate the maximum possible execution load within that interval.
Figure 2 illustrates the maximum achievable execution load of within the interval between the release time and the deadline [
26]. As seen in
Figure 2, in the scenario where the maximum execution of occurs, the execution of the first job starts at the beginning of the interval
L and ends at the deadline of that job. The subsequent jobs are executed as soon as they are generated to maximize the amount of execution. The maximum achievable execution load of within the interval is calculated as the sum of the number of running jobs that can be executed and the execution load of jobs that cannot be executed.
Lemma 2 (Execution load of task
)
. The maximum execution load of a task within the interval L, denoted as , can be calculated as follows:where represents the total number of jobs that execute fully for within the interval L, and whose subsequent job release also exists within the interval L. Proof. By the definition of
, at most
jobs can fully execute for
units within the interval
L. The rest of the time in
L,
, can accommodate the execution of at most one more job. Therefore, the maximum execution load
is given by Equation (
1). □
For instance, in
Figure 1a, from
’s perspective, the deadlines of the first jobs of
and
come before the end of the interval of interest, which is the
interval of
. Therefore, these jobs belong to
. Note that
represents the maximum workload that can occur in the worst-case scenario, so the sum of the higher priority executions in the example of
Figure 1a, which depicts a real case, can be less than the maximum workload. Using the maximum execution load
, we can calculate the minimum number of CF slots that can exist in the interval
L. Assuming
m processors, the size of the available execution time space in the interval is
. In each contention time slot, at least
m tasks execute. Therefore, the number of contention slots that can exist in the interval
L cannot exceed the following value.
Lemma 3 (Contention slots [
11])
. The number of contention slots that can exist in the interval L does not exceed the following value: Proof. Given that each contention slot accommodates at least m tasks, the sum of the execution loads of all tasks in cannot exceed m times the number of contention slots. □
We can use the maximum contention slots obtained from Equation (
2) to calculate the minimum CF slots in the interval
of
as follows.
Theorem 1 (Minimum CF slots)
. The minimum number of CF slots that can exist in the interval of , denoted as , can be calculated as follows: Proof. From Lemma 3, the number of contention slots does not exceed . Since we are looking at the interval, there is necessarily only one job of within this interval. Therefore, the expression can be reduced to . Hence, the rest of the slots in must be CF slots. If the calculated number of CF slots is negative, it is corrected to zero. □
For example, in
Figure 1b, from
’s perspective, the deadlines of the first jobs of
and
come before the end of the interval of interest, which is the
interval of
. Therefore, these jobs belong to
. Additionally, the third and fourth executions of these jobs are run after their priorities are demoted, so they belong to
.
6. Evaluation
In this section, we assess the efficacy of our proposed SP-CF scheduling methodology, as applied to the fixed-priority and EDF scheduling. We conducted experiments based on a simulator we implemented ourselves in Java SE 21. We consider rate-monotonic (RM) scheduling as the most typical form of fixed-priority scheduling. RM assigns higher priority to tasks with shorter periods. We conduct our evaluation by performing experiments with a custom-built Java simulator, allowing us to ascertain the number of randomly generated task sets that can guarantee the absence of deadline violations under the evaluated techniques.
We evaluate the performance of our schedulability analysis by comparing its results with those of the scheduling process, specifically looking for any deadline violations. This comparison gives us a reliable measure of the scheduler’s accuracy, considering the integral relationship between the scheduling algorithm and the real-time analysis technique.
To gauge the efficiency of the methodologies, we create a range of task sets at random. This is achieved through the application of a task set generation method extensively employed in a variety of prior studies [
15,
27,
28]. The task sets generated are of two types, characterized by implicit and constrained deadlines, and are evaluated under four different processor numbers, i.e.,
. The utilization (
) of each task is determined by either a bimodal or exponential distribution, with input parameters drawn from the set
[
11]. Depending on the given bimodal parameter
p, a value for
is uniformly selected from the ranges
and
with probabilities
p and
, respectively. For a given exponential parameter
, the value is derived from the exponential distribution characterized by the probability density function
. Each task has a
value that is uniformly chosen within
, while
is determined by the bimodal or exponential parameter, and
is randomly selected within the range
. Based on these parameters, we generate task sets, beginning by creating an initial set of
tasks. The generated task set is then tested against the necessary feasibility condition described in [
29]. If the task set does not pass this test, it is discarded and a new set is generated. Conversely, if it meets the criteria, the set is included for further evaluation. This task set is then used as a basis for the next one by adding an additional task, and the process is repeated. The feasibility condition, used during testing, suggests that a task set with a system utilization
greater than
m cannot be scheduled by any algorithm. We generate a total of 10,000 task sets for each bimodal or exponential distribution with their respective input parameters (e.g., bimodal distribution with 0.1), each individual value of
m (e.g.,
), and each type of deadline (e.g., implicit deadline). Given the ten different distribution configurations, four different values of
m, and two types of deadlines, a total of 400,000 task sets (10,000 · 10 · 4) are generated.
We demonstrate the applicability of our synthetically produced task sets by illustrating a real-time system along with its task parameters, which is also presented in [
30]. A prominent instance of an expansive real-time system is a satellite system. Focusing on this realm, we delve into a reconnaissance satellite system that employs a specialized antenna capable of sending and receiving radio signals to capture images from the target region, regardless of obstructions like nighttime or overcast conditions. The Antenna Control System (ACSW) [
31] governs this specific antenna. Within the satellite system, tasks are orchestrated by RM on a specialized RTOS termed RTEMS (Real-Time Executive for Multi-Processor Systems) [
32]. The ACSW oversees five main tasks: tHigh, tMilbus, tOne, tTwo, and tSync, with the ensuing functionalities:
“tHigh” processes each macro command (MCMD) from the ground station queue and forwards relevant data to the other tasks.
“tMilbus” fetches MCMDs using the MIL-STD-1553B protocol [
33] and ensures the authenticity of each MCMD via methods such as CRC prior to queuing.
“tOne” supervises internal mode shifts, including equipment operations and telemetry relay via the SpaceWire protocol [
34].
“tTwo” manages processes like FDIR, and crafts packets encapsulating system details for transmission to ground control.
“tSync” prepares operations whenever there’s excess computational capability.
Task metrics for ACSW are tabulated in
Table 1. Parameters like
and
are architect-defined, while metrics such as BCET, WCET, and ACET are gauged from actual operational conditions on the target system. This system boasts a 256MB SDRAM and operates on a multi-processor system underpinning the FT Leon3 CPU architecture, clocked at 80 MHz, complemented by SPARC BSP [
35], which supports both MIL-STD-1553B (external) and SpaceWire (internal) communication protocols. Notably, tSync operates flexibly, running only when other tasks are not. Task frequencies align with their core purposes: MCMD retrieval every 62.5 ms, MCMD reception every 125 ms, equipment mode switches every 250 ms, and system status updates every 500 ms. The task set crafting technique previously explored yields multiple task combinations with assorted attributes. This versatility makes it adaptable for diverse real-time systems with tasks operating in varying contexts.
We consider the following approaches.
NPEDF: DA test for non-preemptive EDF that does not allow any preemption. For the test, Equation (
4) in Lemma 4 can be applied by substituting
and
by
and
where
.
SPEDF-CF: DA test for SP-CF with EDF in Theorem 3.
NPRM: DA test for non-preeemptive RM in Lemma 4 that does not allow any preemption.
SPRM-CF: DA test for SP-CF with RM in Theorem 3.
To evaluate the efficacy of the various schedulability analysis tests under consideration, we start by determining the quantity of task sets deemed schedulable by each respective technique. This is subsequently compared across different processor counts, ranging from 2 to 16 (denoted as
m). We further delve into understanding the effect of the average task set size (represented as
) and the average utilization of tasks in a set (denoted by
) on the performance of each schedulability analysis technique.
Figure 5 illustrates these considerations when
and 16. Here, we focus on bimodal distributions with
and exponential distributions with both
and
parameters. Among the ten task utilization distributions, the three are selected due to their distinct
(minimal, maximal, and median) and
(maximal, minimal, and median). Each subplot in
Figure 5 shows the quantity of task sets that each schedulability test deems schedulable against the shifting task set utilization (
) based on the assigned task utilization distribution.
Our initial analysis, grounded on data from
Figure 5, leads us to several observations as follows.
- O1.
As can be seen in
Figure 5b,e, all methods show high performance for distributions with a low task utilization
.
- O2.
In all cases, the RM series (i.e., LPRM-CF and NPRM) shows higher performance than the EDF series (i.e., LPEDF-CF and NPEDF).
- O3.
In all cases, the techniques with SP-CF applied dramatically improve the performance of RM and EDF for both and .
O1 is due to the non-preemptive (e.g., for NPEDF and NPRM) or single-preemptive (e.g., SPEDF-CF and SPRM-CF) characteristics of each approach. In such scheduling, a job of of interest can be blocked by at most one lower priority job. Therefore, when the distribution has a low average task utilization, the amount of blocking received from lower priority tasks decreases.
O2 arises due to the pessimism in the schedulability analysis of NPEDF and SPEDF-CF, compared to NPRM and SPRM-CF. Unlike RM, in the case of EDF, it assigns priority not to the task itself but to each individual job. Therefore, in the schedulability analysis of NPEDF and SPEDF-CF, when calculating the worst-case response time and comparing it with , it assumes interference from all tasks excluding the of interest. On the other hand, since NPRM and SPRM-CF only consider tasks with higher priority than the of interest to calculate the worst-case interference on , they show better performance than NPEDF and SPEDF-CF in terms of the efficiency of the analysis.
O3 demonstrates the efficiency of SPCF in improving schedulability. As shown in Theorems 2 and 3, under SPCF scheduling, the amount of interference received from higher-priority jobs is reduced to a minimum contention-free maximum of . This leads to the improved performance compared to NPRM and NPEDF.
7. Discussion
We discuss the time complexity of the proposed methods as follows. Equation (
7) is applied to each task
of the task set
. For the first term of this equation,
is needed, and for the second term,
is also required. Therefore, the total time complexity is
, and when applied to
n tasks, it becomes
. The same goes for Equation (
10).
In multi-processor real-time systems, global scheduling allows tasks to run on any processor, providing increased flexibility and aiding load balancing [
36]. However, this flexibility comes at the cost of potential migration overheads and cache consistency issues. EDF scheduling method prioritizes jobs with imminent deadlines due to their urgency and is considered optimal for single-processor platforms [
1]. Yet, in multi-processor contexts, achieving peak performance entails not just addressing job urgency but also leveraging the parallelism offered by using multiple processors concurrently. When setting priorities at the job level, algorithms like EQDF [
37] and SPDF [
8] often outshine EDF. We consider global scheduling, and their performance can be further enhanced by integrating them with contention-free policies.
On the flip side, semi-partitioned scheduling mainly designates tasks to specific processors while still allowing some tasks to migrate [
38,
39]. This approach melds the benefits of task partitioning with the versatility of migration, enhancing cache efficiency, reducing task contention, and curtailing wait times. Nevertheless, migration overheads and algorithmic intricacies remain concerns. For semi-partitioned approaches, maximizing the number of tasks allocated across processors is essential. Once designated, tasks can be managed using ideal single-processor policies: EDF for task-level fixed priority and RM for job-level fixed priority [
1]. It is worth noting, however, that task partitioning is a recognized NP-Hard challenge, and foundational partitioning techniques, like bin-packing, can exploit only half of the available multi-processor power to maintain schedulability. The CF policy strives for efficient multi-processor resource utilization. Given that EDF, which optimizes computing resources, is already optimal for single processors, applying the CF policy there would be superfluous. As such, integrating the CF policy within partitioned algorithms delineates a distinct research trajectory.