# Schedulability Analysis in Fixed-Priority Real-Time Multicore Systems with Contention
## 1 Introduction  
Multicore platforms are growing in importance in critical systems, such as automotive or avionic applications. In these systems, failure to meet any requirement may lead to catastrophic consequences. Therefore, compliance with deadlines in hard real-time multicore systems is a crucial aspect. The scheduling problem in multicore systems in turn requires solving two problems: (1) decide which tasks are executed in each core (allocation problem) and (2) execute each task to meet all the deadlines (scheduling problem). In partitioned multicore systems where migration is not allowed, each core can be executed independently, so that monocore scheduling theory can be applied. But this is not possible when shared hardware resources exist. When a task runs in parallel with other tasks in other cores, it may lead to delays due to shared hardware resources, such as caches, buses, and memories [1, 2]. In this case, interference among cores is produced, and it causes unpredictability, which is undesired in critical systems. Modeling interference is not an easy task, and it has been a hot topic in recent years. There are two main trends to take into account for interference in the temporal model. On the one hand, there are methods that focus on the modeling and interference mitigation of specific hardware resources [3]. These methods are only valid for this type of resources, but they are able to adjust the interference produced in a very accurate way. On the other hand, other methods analyze contention for multiple resources and their integration in schedulability analysis. When multiple shared resources are considered, the contention model must cope with any of the resources, so a general contention model is required [4]. The drawback is that the interference produced is overestimated, but sometimes, it is the only feasible approach when the chip vendor does not provide details about hardware behavior. In addition to modeling interference, it is also necessary to act in both the allocation and scheduling stages to reduce the overall interference produced. The allocation problem is recognized to be NP-hard in the strictest sense [5]. In multicore systems, the way tasks areallocated to cores largely determines the global interference [6]. Some of the main allocation techniques are heuristics based on bin packing, such as First Fit, Worst Fit [7; 8], etc. These techniques consist of mapping tasks to cores according to their loads (or utilization), without considering interference. But the allocation strategy Wmin, presented in [4], reduces overall interference, as it aims to group tasks with interference in the same core, whenever possible. This work assumes a general model for interference where this parameter is added to the traditional parameters of a task. If the allocation strategy greatly reduces interference, as is the case with Wmin, traditional scheduling algorithms such as fixed or dynamic priorities can be adopted in the scheduling phase. Because the temporal task model is modified by the inclusion of interference due to contention, it is necessary to provide new schedulability tests for these models. The work presented in [9] presents schedulability tests for dynamic priorities under the assumption of the temporal model presented in [4]. When it comes to schedulability tests for fixed priorities, they are based on worst-case response time (WCRT). WCRT is the length of the longest interval from a task's release till its completion [10]. These schedulability tests do not consider interference, so this work fills this gap. Furthermore, when interference is taken into account, the worst-case scenario may occur at any point in time during the entire execution window, not necessarily upon the first activation of the task [9]. Extending the concept of WCRT to consider this is also challenging.