Project topics and materials
Get Complete Project Material File(s) Now! »
Partitioned/Global Scheduling
When tasks execute on a multiprocessor system, there are scheduling policies that define how tasks can execute on the different processors. Let us mention two policies:
pa r t i t i o n e d s c h e du l i n g In partitioned scheduling, each task is statically allocated on a pro-cessor [102, 86, 35, 40] and all the jobs generated by the task are required to execute upon that processor [11]. Tasks are scheduled locally on each processor as in a uniprocessor system. g l o b a l s c h e du l i n g In global scheduling, different jobs of the same task may execute on different processors and a preempted job may resume execution on a processor different from the one it has been executing on prior to preemption [7, 11, 40]. We say that jobs are allowed to arbitrarily migrate across processors during their execution [35].
Resource Synchronization Primitive
When tasks use a shared resource, the OS handles the protection of the shared resource by offering primitives that tasks call when they want to access the shared resource. The method used by the OS to protect the shared resource may have a consequence on the scheduling of tasks. A task may go from the executing state to the waiting state because a shared resource is un-available during its execution. If no precautions are taken, this may result in unbounded priority inversions and deadlocks in the system. These phenomenons may be defined as follows:
Definition 24 (Priority Inversion [127]). Priority inversion is the phenomenon where a task of higher priority is blocked by a lower priority task.
Definition 25 (Unbounded Priority Inversion [127]). Unbounded priority inversion is the phenomenon when a higher priority task is blocked by a lower priority task for an indefinite period of time.
Definition 26 (Deadlock [139]). A set of tasks is deadlocked if each task in the set is waiting for an event that only another task in the set can cause.
In the case of tasks using shared resources, a deadlock occurs when a task A is blocked by a task B due to some shared resource R1 and task B is blocked by task A due to some other shared resource R2.
Figure 1.5a) shows a deadlock. A low priority task L is released first, it asks for a resource R1, and locks it. In the critical section where L uses R1, it is preempted by a high priority task H. Task H later asks for R2, and locks it. In the critical section where H uses R2, it asks for R1 which is already locked by L so it waits for L to unlock it. L then continues execution and asks for R1 but fails because R1 is still locked by H. This results in a deadlock because H is waiting for R2 locked by L, which is waiting for R1 locked by H.
Figure 1.5b) shows a unbounded priority inversion. A low priority task L is released first, it asks for a resource R, and locks it. L is then preempted by a high priority task H. During execution of H, a mid priority task M is released. H asks for R during its execution and has to wait for L to unlock it. At this time, the highest priority released task is M so M executes, even if it is of lower priority than H and does not block H due to a shared resource. Therefore the priority inversion is unbounded because H not only has to wait for the end of the critical section of L but also the completion of any jobs of tasks of higher priority than L, released before the end of the critical section, even if the tasks are of lower priority than H.
Priority Inheritance Protocol
The Priority Inheritance Protocol (PIP) was proposed in [127] to solve the problem of unbounded priority inversions. In PIP, when a task gets access to a resource, its priority is modified to the highest priority of tasks that it blocks. The modification of its priority occurs whenever a higher priority task asks for access to the already locked shared resource. When a task unlocks a resource, its priority is re-computed according to resources it is still locking. When a task exits all of its critical sections, it regains its initial priority. PIP is only applicable to systems with fixed priority. It does not prevent deadlocks but it is possible to compute an upper-bound to the blocking time of tasks. With PIP, there are potentially very long WCBTs [127].
Priority Ceiling Protocol
The Priority Ceiling Protocol (PCP) proposed in [127] aims at reducing blocking times compared to PIP and prevent deadlocks. It is applicable to FP scheduling and later adapted for EDF in [31], which proposes the Dynamic Priority Ceiling Protocol (DPCP).
A ceiling priority is assigned to each shared resource. The ceiling priority of a resource is the highest priority of tasks that may use it. At a given time during execution, a system priority is defined as the highest ceiling priority of resources locked at the given time. When a task asks for access to a resource, it is given access only if its priority is strictly higher than the system priority. Otherwise the task is blocked and the task that already has access to the resource inherits the priority of the blocked task. With PCP, a task H can only be blocked by at most one critical section of a task L of lower priority, using a resource with a ceiling priority higher than the priority of H [127].
Stack Resource Policy
Another resource access protocol applicable to EDF scheduling is the Stack Resource Policy (SRP). This protocol is furthermore applicable to systems where a resource has several instances and a task may access several instances of the resource.
In this protocol, each task is assigned a preemption level, which reflects its relative deadline. For example tasks may be assigned preemption levels by the DM method. During execution, a resource is given a ceiling value, defined as the maximum of preemption levels of tasks that want to access more instances of the resource than what is available. In the same way as with system priority in PCP, in the SRP a system has a system ceiling value during execution. In PCP, tasks may be blocked when they asks to access resources. In the SRP, tasks may be blocked when they want to preempt another task. A task H can only preempt another task L when the following conditions are satisfied:
– Task H is of higher priority than task L.
– Task H’s preemption level is higher than task L’s.
– Task H’s preemption level is higher than the system ceiling value.
The general idea behind the SRP is thus to prevent a task from starting execution, before all of the resources the task needs are available. Like PCP, the SRP prevents deadlocks and bounds blocking times.
architecture description languages
A modeling language can be used to describe the – more or less abstract – architecture of the system. These kind of modeling languages are called Architecture Description Language (ADL) [97, 54], which can be defined as follows:
Definition 34 (Architecture Description Language [97]). An ADL focuses on the high-level structure of the overall system rather than the implementation details of any specific source module.
An ADL is a Component-Based Model (CBM) where architectural components, connectors, and architectural configurations are described [97].
Definition 35 (Component [97]). A component in an architecture is a unit of computation or a data store.
According to [97], an ADL must also offer the possibility to describe a component’s interface.
Definition 36 (Interface [97]). A component’s interface is a set of interaction points between it and the external world. The interface specifies the services a component provides, and services the component requires.
A service of a component can be defined as follows:
Definition 37 (Service [97]). A service is a set of functionalities that can be reused. Examples of services are messages, operations, and variables of the component.
Components are connected together, through their interface, by connectors.
Definition 38 (Connector [97]). Connectors are architectural building blocks used to model interactions among components and rules that govern those interactions.
RTES Domain-Specific Architecture Description Languages
Beside UML MARTE, there are several ADLs that are dedicated to a specific domain within the RTES domain. In the following sections three standard domain-specific ADLs are briefly introduced. For each ADL, entities and tool support are described.
AADL
Architecture Analysis & Description Language (AADL) [49] is a standard ADL of the Society of Automotive Engineers, proposed in 2004. AADL has strong roots in the avionics domain. e n t i t i e s o f a a d l m o d e l An architecture in AADL is described as a set of connected compo-nents, and interfaces. The components of AADL are separated according to three categories. The entities of a RTES, presented previously in this chapter, can be organized into these categories:
– Software: tasks and data
– Hardware: processors, memories and buses
– System: a component called « system » that wraps the software and hardware components t o o l s u p p o r t There exists several modelers that support AADL. For example OSATE [124] is an Eclipse plug-in that lets the user describe an AADL model either graphically, in textual format, or in the Exensible Markup Language (XML) format.
Schedulability Test for Periodic Tasks
The following paragraphs present a RTA schedulability test for tasks scheduled by a preemptive FP scheduling policy on a uniprocessor. The tasks are assumed synchronous. They are also assumed independent but we will see how the test can be extended for jitters and WCBTs. The WCRT of a periodic task τi is computed according to the following theorem: Theorem 10. [75] The WCRT of a task τi is the response time of one of its jobs that occur in the busy period of τi, starting at a critical instant where all tasks are released at the same time. By applying Theorem 10, the WCRT of a task τi is obtained by the following steps:
– Compute the length of the busy period of τi
– Compute the number of jobs of τi that occur in the busy period
– Compute the response time of each job and take the maximum response time as the WCRT of
τi In the following paragraphs, let us denote by hpi the set of tasks, different to τi, of higher or equal priority to task τi. l e n g t h o f b u s y p e r i o d Let us denote by Wi the function that computes workload of jobs of a periodic task τi and tasks in hpi, in an interval [0; t] [64]:
t ∀t > 0, Wi(t) = · Cj (13) Tj τj∈hpi∪{τi}.
Table of contents :
i state of the art
1 real-time embedded system
1.1 Generalities on Real-Time Embedded Systems
1.2 Software of a RTES
1.2.1 Concept of Task
1.2.2 Types of Task
1.2.3 Parameters of Task
1.2.4 Task Dependencies
1.2.5 Memory Partition
1.3 Operating System of a RTES
1.3.1 Scheduler
1.3.2 Resource Synchronization Primitive
1.4 Hardware of aRTES
1.4.1 Scheduling and Processors
1.4.2 Scheduling and Networks
1.5 Development Cycle
1.6 Model-Driven Engineering
1.6.1 Introduction to Models
1.6.2 Model Transformation
1.7 Architecture Description Languages
1.7.1 Generic ADL for RTES: UML MARTE
1.7.2 RTES Domain-Specific Architecture Description Languages
1.8 Conclusion
2 scheduling analysis
2.1 Methods of Scheduling Analysis
2.1.1 Empirical Methods
2.1.2 Analytical Methods
2.2 Task Models and Tests
2.3 Fundamental Models: Periodic and Sporadic
2.3.1 Definition
2.3.2 Processor Utilization Feasibility Tests
2.3.3 Response Time Schedulability Test
2.3.4 Processor Demand Feasibility Tests
2.4 Transaction Models: Illustration with Tree-Shaped
2.4.1 Definition
2.4.2 Offset-Based Response Time Analysis: A Historical Perspective
2.4.3 Basic Concepts of RTA of Transactions
2.4.4 The WCDOPS+ Test
2.5 Multiframe Models: Illustration with GMF
2.5.1 Definition
2.5.2 Processor Demand Feasibility Test
2.5.3 Response Time Schedulability Test
2.6 DAG Task Models: Illustration with Sporadic DAG Task
2.6.1 Definition
2.6.2 Generalizations Between DAG Task Models
2.6.3 Speedup Bound Feasibility Tests
2.6.4 Schedulability Tests
2.7 Conclusion
3 scheduling analysis of software radio protocol
3.1 Introduction to Radios
3.1.1 Radio Network
3.1.2 Radio Protocol Stack
3.1.3 Impact of TDMA on Radio Protocol Stack
3.1.4 From Application Constraints and Radio Protocol Configuration to Task Constraints
3.2 Context of Work
3.2.1 Software and Execution Platform Architecture
3.2.2 Type of Software Architecture of a Software Radio Protocol
3.2.3 Summary of Characteristics for Scheduling Analysis
3.2.4 Software Radio Protocol Development
3.3 Problem Statement
3.3.1 Applicability of Task Models
3.3.2 Availability of Analysis Methods Implemented in Tools
3.3.3 Applicability of ADLs
3.3.4 Summary of Problem Statement
3.4 Overview of the Solution
3.4.1 Applicability of Task Models Problem
3.4.2 Availability of Analysis Methods Implemented in Tools Problem
3.4.3 Applicability of ADLs Problem
3.5 Conclusion
ii contributions
4 experiment on scheduling analysis of software radio protocol
4.1 Case-Study of the Experiment
4.2 Applying the Periodic Task Model
4.2.1 High Level Software Architecture Model
4.2.2 Software and Execution Platform Architecture Model
4.2.3 Associations Between Entities
4.2.4 Transformation to Cheddar
4.3 Discussion on the Analysis Results
4.3.1 Software Design Mistake
4.3.2 Missed Deadline
4.3.3 Unbounded Priority Inversion
4.3.4 Pessimistic WCRTs
4.3.5 Limits of the Periodic Task Model
4.3.6 Summary of the Analysis Results
4.4 Conclusion
5 a task model for software radio protocols
5.1 Dependent General Multiframe
5.1.1 DGMF Definitions and Properties
5.1.2 DGMF Example
5.1.3 Applicability of GMF Analysis Methods on DGMF
5.2 DGMF Scheduling Analysis Using Transactions
5.2.1 Transaction Reminder and New Definitions
5.2.2 DGMF To Transaction
5.2.3 Transformation Example
5.2.4 Assessing Schedulability of Resulting Transactions
5.3 Summary of DGMF Analysis Method
5.4 Implementation in Cheddar
5.4.1 Cheddar
5.4.2 Implementation of DGMF and Transaction
5.4.3 Discussion on Implementation
5.5 Experiment and Evaluation
5.5.1 Transformation Correctness
5.5.2 Transformation Time Performance
5.5.3 Case-Study Modeling with DGMF
5.6 Conclusion
6 schedulability analysis of tree-shaped transactions with non-immediate tasks
6.1 Applicability of WCDOPS+ on Non-immediate Tasks
6.2 A Schedulability Test for Non-Immediate Tasks
6.2.1 Overview of the RTA Method
6.2.2 Op0: Task Sets and Execution Conflicts
6.2.3 Op1: Worst Case Scenario
6.2.4 Op2: Worst Case Interference
6.2.5 Op2 cont.: Worst Case Interference Algorithms
6.2.6 Op3: Worst Case Response Time
6.3 Experiment and Evaluation
6.3.1 WCDOPS+NIM Evaluation
6.3.2 Experimentation on Software Radio Protocol
6.4 Conclusion
7 an architecture model for automatic scheduling analysis
7.1 Exploiting Specification Documents
7.2 New Model for Scheduling Analysis: Service Model
7.2.1 Service Model Overview
7.2.2 Service Behavior View
7.2.3 Event Generator View
7.2.4 Thread Implementation View
7.3 Service to Cheddar
7.3.1 Overview of the Transformation
7.3.2 Algorithm Overview
7.4 Experiment and Evaluation
7.4.1 Simulation Setup
7.4.2 Results
7.5 Conclusion
Conclusion
a cheddar-adl
b complete software radio protocol case-study
c service model
c.1 Service Analysis View
c.1.1 Entities
c.1.2 Mapping to MARTE
c.1.3 Diagram Palette
c.2 Service Behavior View
c.2.1 Entities
c.2.2 Mapping to MARTE
c.2.3 Diagram Palette
c.3 Event Generator View
c.4 Thread Implementation View
c.4.1 Entities
c.4.2 Mapping to MARTE
c.4.3 Diagram Palette
c.5 Shared Resource Implementation View
c.5.1 Entities
c.5.2 Mapping to MARTE
c.5.3 Diagram Palette
c.6 Operating System Implementation View
c.6.1 Entities
c.6.2 Mapping to MARTE
c.6.3 Diagram Palette
c.7 Hardware Implementation View
c.7.1 Entities
c.7.2 Mapping to MARTE
c.7.3 Diagram Palette
d service to cheddar
d.1 Main Program
d.2 Node Processing
d.3 Step Processing
d.4 Thread Processing
d.5 Scheduler and Processor Processing
d.6 Partition Processing
d.7 Resource Acquisition Processing
