Victor Court
email: victor.court@ifpen.fr

Francis Declerck
email: declerck@essec.edu

Jean-Pierre Indjehagopian
email: indjehagopian@essec.edu

Frédéric Lantz
email: frederic.lantz@ifpen.fr

Dynamics of biofuel prices on the European market: Impact of the EU environmental policy on the resources markets

Keywords: biofuel, oil market, structural changes, switching regime model O13, Q16, Q41, Q42

La collection "Les Cahiers de l'Économie" a pour objectif de présenter les travaux réalisés à IFP Energies nouvelles et IFP School qui traitent d'économie, de finance ou de gestion de la transition énergétique. La forme et le fond peuvent encore être provisoires, notamment pour susciter des échanges de points de vue sur les sujets abordés. Les opinions exprimées dans cette collection appartiennent à leurs auteurs et ne reflètent pas nécessairement le point de vue d'IFP Energies nouvelles ou d'IFP School. Ni ces institutions ni les auteurs n'acceptent une quelconque responsabilité pour les pertes ou dommages éventuellement subis suite à l'utilisation ou à la confiance accordée au contenu de ces publications.

Pour toute information sur le contenu, contacter directement l'auteur.

INTRODUCTION

This paper examines the links between biodiesel prices in Europe and prices of agricultural commodity resources and prices of gasoil used for automotive fuels. There is a lack of literature linking gasoil and biodiesel prices. The topic is original because it focuses on the dynamics of market price links to find a structural relationship between biodiesel and agricultural resources and gasoil. The paper focused on the European biodiesel market. EU biodiesel is mainly an ester processed from domestic rapeseed.

The use of biofuels has sharply increased in the EU since the 2003/30 EU Directive through financial incentives. Further national governments added tax constraints for refiners who do not blend diesel with biofuels. The 2003/30 Directive was replaced by the 2009 Renewable Energy Directive (RED) that was modified by the 2015/1513 Directive on the quality of automotive fuels.

Using monthly data from November 2006 to January 2016, no cointegration involving biodiesel, rapeseed and gasoil prices was found over the entire period. Several tests for breaks were performed. Unit-root tests with breaks were used: [START_REF] Zivot | Further evidence on the great crash, the oil price shock and the unit root test hypothesis[END_REF] tests enabled to find a break in the winter of 2008-2009, in December 2008or February 2009. The [START_REF] Bai | Estimating and testing linear models with multiple structural changes[END_REF] Bai and Perron. We decided therefore to use a regime-switching model in order to search for a relationship with a changing regime.

We thus estimated the relationships between different variables, enabling us to find two different regimes.

Regime 1 is characterized by biodiesel prices driven more by gasoil prices than by rapeseed prices, in times of high oil prices: 2007-2008, late 2010 -late 2012. Regime 2 is characterized by biodiesel prices mainly driven by rapeseed prices in times of low oil prices: the year 2009, December 2010 -2014. From that point in time, oil prices and agricultural (rapeseed and biodiesel) prices no longer moved quite in the same way. While oil prices dropped sharply, rapeseed and biodiesel prices have remained quite stable. Such new dynamics may be due to the annual harvest of agricultural oilseeds leading to short-term price inelasticity of production and compulsory blending of biodiesel in fuels because of policy regulations.

The second section provides an economic and empirical analysis of the biodiesel market. The third section presents the review of the literature. The following section introduces the methodology and the data. The fifth section delivers and analyzes the results, which are discussed in the sixth section. Finally conclusions are drawn.

ECONOMIC AND EMPIRICAL ANALYSIS

Biofuels are liquid or gaseous transport fuels made from biomass. In Europe, they serve as a renewable alternative to fossil fuels in the transport sector, contributing to a reduction in greenhouse gas emissions and improving the EU security of supply. The two major biofuels are biodiesel (11.1 million tons of oil equivalent Mtoe in 2015) and bioethanol (2.7 Mtoe).

Biodiesel is the most common biofuel in Europe since diesel deliveries (211 Mtoe in 2015) amount to about 2.6 times gasoline deliveries (81.7 Mtoe). It comes from oils or fats after trans-esterification. It is a liquid consisting mainly of fatty acid methyl (or ethyl) esters, commonly named FAMEs. Among them, rapeseed methyl ester (RAME) is the major biodiesel in Europe. It is produced from rapeseed, an agricultural commodity mostly produced locally.

This policy is aimed at reducing the emissions of greenhouse gases and improving energetic -7% of 1 st generation biofuels from oilseeds (mainly rapeseed) or cereals (mainly soft wheat) or sugar beets.

-3% that is twice 1.5% of 2 nd generation biofuels from biomass that cannot be used for food production (wood, leaves, straw and specific plants).

To achieve these targets, the EU allows its member States to use different tools like green certificates and tax shelters.

Overall, biofuel production met up to 3.1% of global fuel needs for road transportation worldwide in 2014 4 . This share reached 4.7% within the EU in 2015 5 . Since 2010, biofuel consumption has stabilized at around 11 Mtoe for biodiesel and 2.7 Mtoe for bioethanol (figure 1). Increasing EU consumption is met by a growing domestic agricultural production and imports as pointed out by the rapeseed uses (Table 1). In 2016, EU rapeseed uses for biodiesel production accounted for 60% of EU rapeseed production. The EU energy policy was inspired by the Brazilian one. After the fourfold increase in oil prices in 1973, Brazil set up a program to replace imported fossil fuels by domestic renewable sources of liquid fuels: bioethanol from corn in the 1970s and biodiesel from soybean in 2004.

In 2005, Brazilian law allowed blending 2% biodiesel to diesel. Biodiesel blending became mandatory in 2008. However, [START_REF] Sorda | An overview of biodiesel policies across the world[END_REF], [START_REF] Padula | The emergence of the biodiesel industry in Brazil : Current figures and future prospects[END_REF] questioned the economic efficiency of Brazilian biodiesel production because it is heavily supported by tax incentives and production and marketing subsidies.

The availability of crops and biomass is crucial to supplying the biofuel industry. [START_REF] Britz | Impacts of EU biofuels directives on global markets and EU environmental quality: An integrated PE, global CGE analysis[END_REF] use the CAPRI model to show that the development of biofuel will lead to an expansion of crops. [START_REF] Carriquiry | World market impacts of high biofuel use in the European Union[END_REF] point out that a large increase in the European biofuel supply will have some implications on agricultural markets. In this context, the analysis of the interactions between the oil market and biodiesel prices is a key point for the potential development of biofuel in Europe.

REVIEW OF LITERATURE

Since the beginning of the eighties, research has aimed at studying the potential of biofuels being disruptive to agricultural commodity prices and being affected by oil prices [START_REF] Barnard | Gasohol/ethanol: a review of national and regional policy and feasibility issues[END_REF]. Filip et al (2017 provided a review of the literature on the relationship between energy prices and agricultural prices, using an econometric approach based on vector error correction models (VECM) and GARCH models focused on market volatility. They raised some questions about the relationships between energy prices, natural resources prices and biofuel prices. They also questioned the stability of such relationships over time. [START_REF] Campiche | Examining the Evolving Correspondence Between Petroleum Prices and Agricultural Commodity Prices[END_REF] examined the co-movements between crude oil prices and corn, sorghum, sugar, soybeans, soybean oil, and palm oil prices during the 2003-2007 period through Johansen cointegration tests. The analysis revealed no cointegrating relationships over the full sample period. However, an analysis of the sub-sample over 2006-2007 revealed that soybean and corn prices were cointegrated with crude oil. Since the production of biodiesel has increased a lot from 2002, our analysis may provide better understanding about the links between rapeseed, biodiesel and gasoil markets. [START_REF] Natanelov | Is there comovement of agricultural commodities futures prices and crude oil?[END_REF] and [START_REF] Natanelov | Commodity futures markets: dynamic interrelationships between financial asset markets, energy markets and traditional agricultural commodity markets[END_REF] found co-movement of agricultural commodities (cocoa, coffee, corn, soybeans, sugar, etc.) and gold futures and crude oil prices using data from 1989 to 2011.

They found strong a cointegration relationship between crude oil and gold prices. Focusing on biofuels, several authors have tried to link energy market prices and agricultural commodity market prices. [START_REF] Harri | The Relationship between oil, exchange rates, and commodity prices[END_REF] found long-term equilibria in the agricultural and oil markets in the United

States from a sample covering the period 2003-2007[START_REF] Hertel | Commodity price volatility in the biofuel era: an examination of the linkage between energy and agricultural markets[END_REF] studied the relationship between these markets over the period 2001-2008 and focused on substitutions between inputs for bioethanol production. They highlight a phenomenon of volatility that they attribute to the blending obligations (blend wall) of bioethanol in gasoline. [START_REF] Peñaranda | The Emergence of Biofuels and the Co-Movement between Crude Oil and Agricultural Prices[END_REF] studied the relationship between different commodity prices (soybean, corn, sugar, oil) over the period 1990-2011, highlighting the equilibrium between agricultural and oil prices with breaks, in using tests designed by [START_REF] Bai | Estimating and testing linear models with multiple structural changes[END_REF], 2003a, 2003b). [START_REF] Peri | Vegetable oil market and biofuel policy: an asymmetric cointegration approach[END_REF] looked at the relationship between resource and diesel prices in Europe over the 2005-2007 period using a VECM econometric approach with threshold effect proposed by [START_REF] Balke | Threshold cointegration[END_REF]. This found two thresholds in the price dynamics.

Tyner (2010) offered a microeconomic analysis about the impact of bioethanol blending regulations on the bioethanol market price equilibrium during the oil price increase in 2008. Thus, the present research is an extension of this literature and is focused on relationships between rapeseed methyl ester (RAME) also named biodiesel, diesel oil and rapeseed prices.

In these relationships, breaks are detected. This leads to find an appropriate approach to explain the price of biodiesel taking into account both the evolution of oil markets and rapeseed market and also environmental policy through the fuel blending policy. Hence, the present research enlarges that literature in focusing on the relationships between biodiesel, diesel and rapeseed prices.

So the present research is very complementary to previous publications in searching for a structural relationship between is biodiesel, diesel oil and rapeseed prices, taking into account the large fluctuations of the oil prices.

METHODOLOGY AND DATA

In this section, the long-term relationships between biodiesel, rapeseed and gasoil prices are studied using econometric analysis of cointegration. The analysis is based on the time series of the different product prices. Since agricultural commodity markets for rapeseed and biodiesel are quoted in euros while oil and gasoil prices are quoted in US dollars, the euro/US dollar rate is also taken into account in the model. The analysis requires performing unit-root tests and cointegration tests. We show some breaks in the long-term relationship between the variables. Then, a Markov chain with changing regime is estimated.

The hypothesis to be tested is that there exists a long-term relationship between the price of biodiesel and the price of rapeseed resources and gasoil. It is assumed that oil distributors may adjust the content in biodiesel in the distributed oil according to costs and regulation rules such as compulsory blending of biodiesel into diesel, incentives and penalties.

The search for a long-term relationship between different variables was originally based on the use of the model from [START_REF] Engle | Cointegration and error correction: representation, estimation and testing[END_REF] when only a single relationship had to be tested. It was enlarged by [START_REF] Johansen | Statistical analysis of cointegration vectors[END_REF] in the multivariate case. Nevertheless, the standard Augmented [START_REF] Dickey | Distribution of the estimators for autoregressive time series with a unit root[END_REF] and [START_REF] Phillips | Testing for a unit root in time series regression[END_REF] tests (respectively denoted ADF and PP) on the residual values of the cointegration model and on the observed series, leading to non-rejection of a unit root, is difficult when the sample under consideration incorporates structural changes. Thus, the structural break detection successively carries out tests for unit root, first on the series and then on the cointegration models. The more general problem of estimating linear models with multiple structural changes, which concerns us more closely, was studied by Bai andPerron (1998, 2003a, b). These tests are synthetized in appendix A.1.

Since our research is focused on two markets, a commodity market and an energy market, tests are carried out on multivariate models based on the Johansen approach.

Monthly data are used from November 2006 when methyl ester of rapeseed oil, that is biodiesel, was quoted for the first time in Europe. The sample ends in January 2016 and consists of 111 observations. All prices are in euros per ton since major European oil refiners and biodiesel processors operate in the euro zone (France, Germany, etc. The potential relationships between the prices are tested with the prices in logarithm terms.

First, the stationarity of the data series is tested. Then, structural break tests presented before are performed and finally a Markov chain model between biodiesel, rapeseed oil and diesel prices is estimated.

EMPIRICAL RESULTS

The results concern the econometric analysis of the relationship between ester (biofuel), rapeseed and diesel prices. The section focuses on structural breaks within the series and the relationships between them. Test for stationarity of the data series with several unit-root tests, including the ADF and PP tests and the [START_REF] Zivot | Further evidence on the great crash, the oil price shock and the unit root test hypothesis[END_REF] regime is determined according to oil price levels.

Test of multiple breaks in the price relationship between ester, rapeseed and gasoil

The existence of multiple breaks in the relationship between ln(Pester), ln(Prapeseed) and ln(Pgdoe) is tested in using several tests proposed by Bai-Perron which are described above.

Thus, we assess the following model:

0, 1 , 2, -1 ln( ) ln( ) ln( )
           (1)
We carry out the sequential test 1/ ll  , the sequential test all subsets, the test global l versus none, the test 1 l  versus l globally determined, the structural break test based on the

2012M03

Finally, we consider the estimations over m+1=6 sub-samples following the Udmax test. They indicate that the impact of rapeseed and diesel prices are different according to the breakpoints (table 4). We run regression models on the sub-samples above defined with first difference variables to avoid spurious regressions (Phillips, 1986). When oil prices are low (2009m07-2010m10 and 2014m01-2016m01), biodiesel prices variations are depending on the rapeseed price variations. Because biodiesel blending is compulsory, the impact of diesel prices remained significant from 2012m3 to 2013m12 when rapeseed prices decreased whilst oil prices were still high. Note: *** significant at the threshold of 1%, ** 5%, * 10%.

Markov chain model with switching regime

Since break tests lead to finding several structural changes matching very strong price movements, it seems that high oil or gasoil diesel prices drive ester prices and it seems that low oil or gasoil diesel prices do not have the same impact on ester prices. So a Markov chain model is tested with two regimes explaining ln(pester) by ln(prapeseed) and ln(pgdoe). A detailed presentation of such switching model estimation is proposed by [START_REF] Hamilton | Regime-Switching Models[END_REF]. A dummy variable is added for January 2009 (D2009M1), matching both low oil prices and the enforcement of new specifications on automotive fuels in the EU. The transition probability from one regime to another may be explained by oil prices ln(pbrente) and by the euro/US dollar parity, written as ln(eurusd).

The model estimation with Eviews provides the following results:

Regime 1:

(0,299) (0,094) (0,067) ln( ) 4,212 0,309ln( ) 0,133ln( )

t t t t pester prapeseed pgdoe     
(2)

Regime21:

(0,142) (0,034) (0,026) ln( ) 3,218 0,488ln( ) 0,099ln( )

t t t t pester prapeseed pgdoe      (3)
           (5)
The probability of regime 1 is estimated over the period as shown in figure 5 (the unconditional probability of regime 2 is the complement of the unconditional probability of regime 1). Regime 1 is characterized by high oil prices in 2008 and over the period from the end of 2010 to spring 2012.

Figure 5 -Unconditional probability of regime 1

The econometric estimation of biodiesel prices results in a gasoil price coefficient of 0.133 in regime 1 and 0.099 in regime 2. So the gasoil price coefficient difference is 0.034. The gasoil price coefficient is about 3.4% higher in regime 1 than in regime 2. It means that gasoil prices have a stronger impact on biodiesel prices in regime 1 when oil prices are high. Biodiesel price elasticity with respect to gasoil prices is 3.4% higher in regime 1 than in regime 2. In contrast, the rapeseed price coefficient has a stronger impact on biodiesel prices in regime 2 since the coefficient is 0.309 in regime 1 and 0.488 in regime 2. Biodiesel price elasticity with respect to rapeseed prices is 17.8% lower in regime 1 than in regime 2. Hence, when oil prices are high, regime 1 prevails with biodiesel prices mainly impacted by gasoil prices than by rapeseed prices. And when oil prices are low, regime 2 prevails with biodiesel prices mainly impacted by rapeseed prices than by gasoil prices.

Finally, we assess the link between gasoil and ester prices. For this purpose, a Granger causality test is performed between the two series expressed in price first difference Δln(pgdoe) and Δln(pester). Two lags have been considered according to the BIC and the Hannan Quinn criteria. The Fisher statistics is significant for a 5% risk since F(2, 103) = 4.186 > 3.084 as shown in table 6. So, the test result allows accepting the alternative hypothesis that gasoil prices Granger-cause biodiesel prices in the sense of Granger without any feedback effect. From an economic viewpoint, global economics is slightly booming, so oil demand is still low and oil price is low. So the demand for biodiesel is only bound by the "blend wall", that is the legal requirement of biodiesel blending into diesel. Consequently, biodiesel price is related mainly to its raw material price that is rapeseed price.

In phase 2, from March 2008 to June 2009: the sub-period was a phase of rise until July 2008 and then a sharp fall in the oil price. The rapeseed price fluctuated in the same direction but less marked: the oilseeds (soybean on CBOT and canola on the Winnipeg Futures market) markets were experiencing lower voltages than oil markets, with supply and food demand remaining more stable. Two tests, (l/l+1) and "all sample" tests, (Table 3) signal a potential break in February 2009. This can be explained by the introduction new standards (10 ppm sulphur content) on automotive fuels in the EU and the increase in biofuel blending targets.

Thus, it may explain the slight rebound in the Brent oil price and the rapeseed price. However, higher demand for biodiesel might have involved anticipations of forthcoming higher blending rate of biodiesel in diesel for transportation, due to pressures from national governments on the EU Commission. The European governments wanted to improve their state commercial balance and national employment rate in blending more renewable energies coming from oilseeds (mainly rapeseed) produced locally. The EU was working on new EU directive to increase the blending rate of biofuels in order to pass the law on the following year as stated by the EU Renewable Energy Directive (RED1) 2009/28.

Consequently, EU biodiesel price departed from the economic rapeseed supply and demand equilibrium. Biodiesel price was higher and seemed drawn by the higher oil price.

In phase 3, from July 2009 to October 2010, the biodiesel price was driven mainly by the price of rapeseed over the sub-period. Rapeseed price was much higher than gasoil price (figure 4). This could be explained by the increasing blending targets up to 10% level in the EU by 2020 (Directive 2009/28/CE, April 2009) and euro/dollar exchange rate effect. The blending target was then reduced to 7% for biofuel from agricultural products.

From an economic viewpoint, global economics was stagnant, so oil demand was low and oil price was low. The EU economics was also stagnant. The EU imports of rapeseed went down from 3,353 thousand tons in 2008-2009 to 2,082 thousand tons in 2009-2010. The EU demand for biodiesel was only bound by the EU "blend wall", meaning the legal requirement of biodiesel blending in the diesel pool. Consequently, biodiesel price was related mainly to rapeseed price.

The EU Renewable Energy Directive (RED1) 2009/28 on renewable has been enforced in 2009. In terms of energy content, the objective was to increase from 5.75% to 7% the blending rate of biodiesel into diesel used for transportation.

In phase 4, from November 2010 and February 2012: the biodiesel price was more driven by the oil price over the sub-period. The period was marked by a sharp increase in the oil price, mainly linked to geopolitical tensions, including tensions in Libya, affecting oil markets.

From an economic viewpoint, global economics was booming strongly with very high oil demand and very high oil price. The EU biodiesel "blend wall" was binding. The EU imports of rapeseed went up from 2,082 thousand tons in 2009-2010 to 2,624 thousand tons in 2010-2011 and to 3,752 thousand tons in 2011-2012 as shown in table 1. Again, higher demand for biodiesel was bound not only the "blend wall" but may also involve anticipations of forthcoming increase in biodiesel blending due to pressures from national governments even though some NGO did not share governments views.

Consequently, EU biodiesel price departed from the economic rapeseed supply and demand equilibrium. EU biodiesel price was higher and seemed drawn by the higher oil price.

In phase 5, from March 2012 to January 2016: the biodiesel price was driven mainly by the rapeseed price over the sub-period. From an economic viewpoint the EU economics grew very slowly with low oil demand while world shale oil production increases so strongly that oil price was low. The evolution of EU rapeseed imports confirmed the low demand for diesel. The EU imports of rapeseed went down from 3,752 thousand tons in 2011-2012 to 3,378 thousand tons in 2012-2013 and even further down to 2,317 thousand tons in 2014-2015 as shown in table 1.

Hence the EU demand for biodiesel was only bound by the "blend wall". Consequently, biodiesel price was related mainly to rapeseed price.

In a microeconomic perspective expressed on figure 6, the five sub-periods could be interpreted as follows.

In phases 1, 3 and 5, the biodiesel price is driven mainly by the price of rapeseed due to low oil demand. So the demand for biodiesel is only bound by the "blend wall". Consequently, biodiesel price is related mainly to its raw material price that is rapeseed price (named "Regime 2" on figure 6).

In phases 2 and 4, global economics is booming strongly with very high oil demand and very high oil price. higher demand for biodiesel is bound not only the "blend wall" but may also involve anticipations of forthcoming increase in biodiesel blending due to pressures from national governments even though some NGO do not share governments views.

Consequently, EU biodiesel price departs from the economic rapeseed supply and demand equilibrium. EU biodiesel price is higher and seems drawn by the higher oil price (named "Regime 1" on figure 6). The biodiesel price is therefore mainly related 1/ to rapeseed prices which are very inelastic since harvest only occurs once a year, 2/ to the market prices of edible oils (rapeseed, soybean, palm, etc.) which are used for food usage, and 3/ to the strong incentive to incorporate esters into gasoil to avoid tax on polluting activities in Europe.

After drops in oil prices, the biodiesel and the rapeseed prices seem no longer in the same long-term relationship with gas diesel oil prices. Oil product taxes in EU countries are high enough to create a strong incentive for fuel processors-distributors to blend biofuels with petroleum fuels. Hence, biodiesel prices are balanced between resource (rapeseed) prices and gasoil automotive fuel prices.

The estimation method considered by BP is based on the OLS technique: for each m-partition 1 (T , ,T ) m , the OLS estimation of β and δ (i=1, ,m) i is obtained by minimizing the sum of squared residuals:

    -1 1 2 '' 1 11 ,..., - - i m Ti T m t t t i i t T S T T y x z        (7)
The OLS estimation of β and δ i using the m-partition 1m

Testing for the existence of breaks

The statistics proposed by BP for multiple breaks are generalizations of the [START_REF] Andrews | Test for parameter instability and structural change with unknown change point[END_REF] test for the single structural change using the maximal value of F-statistics (or Wald statistic). The BP tests are robust to serial correlation of the error terms and to heteroscedasticity of the error terms.

    -1 1 - 1 - 1 ˆˆ, ..., ; ' '( ( ) ') Tk T k q p F q R RV R R T kq           (10)
where R is the matrix that allows  

' ' ' ' ' 1 2 k k+1
Rδ =δ -δ ,...,δ -δ .

Furthermore, V(δ) is an estimator of the variance covariance matrix of δ that is robust to serial and or heteroscedasticity (HAC estimator).

Following [START_REF] Andrews | Test for parameter instability and structural change with unknown change point[END_REF], the sup-F statistics is defined as follows:

      1 1 ,..., sup ; sup ,..., ; T k k T F k q F q      (11)
We can show that

    1 ˆŝup ; ,..., ; T k T F k q F q   (12)
where   1k ˆλ ,...,λ minimize the global residuals sum under the specified trimming ε .

The asymptotic critical values of sup T F depends on both the number of structural breaks k, the q variables have coefficients that are regime specific and the trimming ε . These critical values were obtained by simulation (BP 1998(BP , 2003 b) b).

Test 2: Double maximum tests

The number of breaks has to be fixed in the previous test.

        1 1 1 ,..., 1 1 max , max sup ,..., ; ˆˆ max ,..., ; m m T m T mM m T m mM WD F M q a F q a F q          (14)
When the weights a 1 ,… a M are defined as a 1 = 1 and for 1 mM  such as a m = c(q, α, 1)/c(q, α, m) where c(q, α, m) represents the asymptotic critical value of the test .

Furthermore, the number of breaks can be specified by using the Bayesian Information Criterion (BIC) suggested by [START_REF] Yao | Estimating the Number of Change-points via Schwarz' Criterion[END_REF] or a modified criterion derived from the Schwarz criterion. [START_REF] Liu | On segmented multivariate regression[END_REF] propose a modified Schwarz criterion (denoted LWZ).

This process consists in minimizing the LWZ criterion to get the number of breakpoints 1 m  . So it tests whether there exists only one break and, if so, it tests the existence of a possible second one, and so forth.

A.2 Tests for the stationarity of oil, rapeseed and biodiesel prices

Unit-root tests show that prices and log prices are not stationary. So, the stationarity of prices of log returns (first difference of logs) is checked by Augmented Dickey-Fuller (ADF) and Considering all the studied series, unit root with structural break tests result (Zivot and Andrews) in accepting the assumptions of structural changes (see table A2.1). The regression coefficients estimated for the different test specifications are all significant for the specification 'intercept and trend' with Δln (pbrente) Δln (pgdoe) and Δln (pester). Thus, the series expressed in first difference are stationary with a break in level and trend in December Note: DF Augmented Dickey-Fuller test, PP Phillips-Perron test , ZA Zivot-Andrews test. *** significant at the threshold of 1%, ** 5%, * 10%. The number of lags is determined using the BIC criterion. In the ZA test, the date is the last month of the sub-period before the break A cointegration analysis was performed between ester gasoil and rapeseed oil prices on the European market. From the Trace test, we show that no cointegration was found over the entire period from November 2006 to January 2016 (Table A2.3). However, significant results

were obtained when the test was performed on a subsample from November 2006 to June 2009, before the rise of ester and rapeseed oil prices (Table A2.4).

Table A2.3 Cointegration test on the global sample 2006m11 -2016m1

Series: LPESTER LPRAPESEED LPGDOE Lags interval (in first differences): 1 to 1

  test for structural change in the relationship between biodiesel and diesel price was used. It led to the identification of five breaks involving a changing regime in March 2012, January 2014, March 2008, January 2009 and November 2010. These breaks matched strong movements on oil market prices. The two breaks in March 2012 and January 2014 were detected by different tests proposed by

  independency among oil importing countries and supply security. It led to the emergence of biofuels in the 2000s. EU Parliament debates on farm land use resulted in revising the objectives of biofuel blending into automotive fuels in the 2000s, particularly during the 2008 crisis characterized by high agricultural prices. The EU Renewable Energy Directive 2003/30/CE (EnR directive) on renewable has been enforced in 2006. In terms of energy content, the objective is to blend 5.75% of biodiesel in diesel used for transportation. The 2003 and 2005 EU directives define the EU 'integrated climate and energy policy'. The latter sets out to achieve the following goals: (i) to increase energy supply security, (ii) to ensure the competitiveness of European economics and the availability of affordable energy supply, (iii) to promote the environmental viability and fight climate change. In 2008 the EU decided the '20-20-20 Initiative' with three main goals to be reached by 2020: cutting by 20% European greenhouse gas emissions from 1990 level, improving by 20% European energy efficiency and reaching a renewable energy share of 20% in the final energy consumption. This last objective has been updated by the EU Commission up to 27% in 2030. The 2009 Renewable Energy Directive (RED), slightly modified by the 2015/1513 Directive, sets constraining targets about renewable energy use in the final energy mix. It aims at blending at least 10%, expressed in energy content, of biofuel in automotive fuels only by 2020:

Figure 1 :

 1 Figure 1: Production of ethanol and biodiesel in Europe

  [START_REF] Zhang | Can the U.S. ethanol industry compete in the alternative fuels market?[END_REF] analyze the competition of bioethanol refiners on the US market with other oxygenate compounds (Methyl tert-butyl ether, MTBE) and the imports prices. Their analysis is based on a Structural VAR model (SVAR). They point out the difficulty to develop the US domestic bioethanol supply due to the strong competition on this market.[START_REF] Zhang | Ethanol, Corn, and Soybean Price Relations in a Volatile Vehicle-Fuels Market[END_REF][START_REF] Zhang | Food versus fuel: What does price tell us?[END_REF] investigated the long-term equilibriums among agricultural commodity prices and their short-term dynamics using monthly data from March 1989 to July 2008. They found that sugar prices influenced all the other agricultural prices except rice. But they did not focus on oilseeds.[START_REF] Serra | Nonlinearities in the U.S. corn-ethanol-oil-gasoline price system[END_REF] focus on transition phases during the period 1990-2008 by using a smooth transition vector error correction model estimated on monthly data. They point out the relationships between bioethanol, corn, gasoline and oil prices.Ciaian and d'Artics (2011) used weekly data from January 1994 and confirmed that nine major agricultural commodity prices, including corn, wheat, rice, sugar, soybeans, cotton, banana, sorghum and tea, were interdependent with crude oil prices, even though some of those agricultural commodities were not used directly in biofuel production. Finally, Filip et al. (2017) used the same data set as the Zhang et al (2010) by extending it to 2016. Authors used a cointegration approach and detected several sub-periods they associated with the end of the agricultural market crises in 2008 and 2010.

  Schwarz Information and Liu, Wu and Zidel (LWZ) criterion and finally the tests based on a fixed number of structural break dates. Tests are performed with the Eviews 11 software. In this paragraph, we focus on the results of the test 14 show the results of the three types of Bai-Perron tests. The five tests detect common break dates in March 2012 and January 2014, matching strong falls in the price difference between biodiesel and gasoil as shown in figure 4. The refining oil into gasoil results in a significant gross margin. The test 1/ ll  Three breaks are found to be significant as shown in table 3. By decreasing order of significance, the three breaks are found in March 2012, January 2014 the threshold value at a 5% risk. Each of these dates matches some important oil or gasoil diesel price movement: the end of the oil price increase in March 2012, the strong decrease in gasoil diesel prices in January 2009 and the end of high oil prices in January 2014. The next detected break dates are March 2008 and July 2009, at times of high oil price increases as shown in figures 2 and 3. When a fifth break date is found, it is in November 2010 at time of high biodiesel and gasoil price differential in winter. Profit margin seems a major criterion to explain breaks. Tests that do not use the heteroscedasticity and autocorrelation consistent (HAC) estimator also identify March 2009 as a break date. It is also found using the Zivot and Andrews test applied to a model with a constant and a trend. From an economic viewpoint, March 2009 is characterized by a strong decrease in oil price.

Figure 6 :

 6 Figure 6: Demand for biodiesel, rapeseed and oil

  is performed on all the possible partitions. The search of the possible dates is restricted by introducing a minimum number of observations in each segment i i+1(T ,T ) . This is defined through a trimming parameter ε (generally ε=0.15)for computing global minimization based on the principle of dynamic programming is proposed by BP (2003a).

Phillips-

  Perron tests. Tests for stationarity assessment are performed on series in first difference. All coefficients of the model are significant. The observation place for a potential break is on February 2009. That is firstly when fuel prices recovered in early 2009 after they plummeted in the second semester of 2008 and secondly when new environmental fuel standards were enforced. These facts help provide an economic interpretation of that date rupture.

  2008 to Δln (pbrente) and in February 2009 for both products (gasoil and ester) from these raw materials Δln (pgdoe) and Δln (pester). The breaks found for a rank of observation outside [15%, 85%] are not considered. Consequently, the ranks 15 (date of January 2008) and 108 (date of November 2015) found for Δln(prapeseed) and Δln(pgdoe) respectively are not considered. So, only are valid the breaks at the bottom oil price (Brent price expressed in euros) in December 2008 and the bottom gasoil diesel price in February 2009, while automotive fuel norms were modified in the EU in January 2009.

Table 1 -The EU rapeseed use for biodiesel production from 2005 to 2016

 1 Unit: thousand tons Source: Eurostat https://ec.europa.eu/eurostat/fr/web/agriculture/data/database EU countries' blending targets are between 2.06% for Croatia and 7.57% for France. In this last case, the biofuel share reached around 7% in 2014 with 0.4 Mtoe of ethanol and 2.5 Mtoe of biodiesel. Germany and France are the leading countries for biofuel production, each representing around 21% of EU production. Overall, in 2014, biofuel consumption amounted to about 11 Mtoe for biodiesel and 2.6 Mtoe for bioethanol in the European Union.

ester (biodiesel) and gasoil prices in Europe, in euro/ton Figure 3 -Brent, rapeseed, ester (biodiesel) and gasoil prices in Europe, in dollar/ton

  ). Brent prices are converted from $/barrel into €/t. The Platts dated Brent crude is chosen as an assessment of the price of physical light North Sea crude oil. The analysis therefore focuses on the four Furthermore, oil distributors buy gasoil and biodiesel to produce and sell diesel in conformity with environmental regulations on biodiesel blending. Facing oil and ester prices, they decide upon the blending level according to spread prices between biodiesel and diesel prices. As shown in figure4, the spread declined sharply in late 2011 and only increased again in the late months of 2015.

	variables, quoted in €/t:
	-PGDOE: price of gasoil, 10 ppm North West Europe destination Germany,
	-PRapeseed: rapeseed price at the nearest maturity on the Euronext Paris futures market,
	-PEster: methyl ester price rapeseed, that is biodiesel, destination Germany, Figure 4 -
	-PBrente: crude oil prices of North Sea (dated Brent) quoted in London.
	These variables are plotted on figure 2 from November 2006 to January 2016.
	1,400									1,800
	1,200									1,600
										1,400
	1,000
										1,200
	800
										1,000
	600									800
										600
	400
										400
	200
	2006 2007	2008	2009	2010	2011	2012	2013	2014	2015	200
										2006 2007	2008	2009	2010	2011	2012	2013	2014	2015
				PRAPESEED	PBRENT
				PGDO		PESTER				PRAPESEEDD	PESTERD
											PBRENTT	PGDO

In our modeling, all prices are expressed in euros. However the Brent and the gasoil prices are quoted in US dollars. The comparison between the prices in euros (figure

2

) and in dollars (figure

3

) shows that the peak of all variables expressed in euros is in January 2011 while the peak of all variables expressed in US dollars is in July 2008. This will lead to taking into account the euro/US dollar parity in our modeling approach. Figure 2 -Brent, rapeseed, Unit: €/t Unit: $/t Source: Argus, Platts, Euronext Source: Argus, Platts, Euronext

Spread between ester and gasoil prices

Unit : €/t Source: Argus, Platts, Euronext

  over the entire period from November 2006 to January 2016. However, significant results were obtained when the test was performed on a subsample from November 2006 to December 2009, before the rise of ester and rapeseed oil prices in 2010. The sequential test Bai and Perron shows multiple break points which are discussed. A Markov chain model with changing regime is estimated. The probability of being in each

	600
	500
	400
	300
	200
	100
	0
	2006 2007	2008	2009	2010	2011	2012	2013	2014	2015

test are summarized in appendix A.2. Moreover, a cointegration analysis was performed between ester gasoil and rapeseed oil prices on the European market. The test shows that no cointegration was found

Table 5 -Least-squares estimation of the relationship between biodiesel, diesel and rapeseed prices

 5

	period	Intercept	Δ(lprapeseed)	Δ(lpgdoe)
	2006m12-2008m02	-0.00568 ***	0.60702	0.125242
	2008m03-2009m06	-0.007658	0.247325	0.267156
	2009m07-2010m10	0.0103	0.320145 *	-0.053295
	2010m11-2012m02	-0.000861	0.690817	0.079361
	2012m03-2013m12	-0.00758	0.101475	0.231411 *
	2014m01-2016m01	-0.00152	0.268475 **	0.015433

Table 6 -Granger causality test between gasoil and ester prices

 6 All the above econometric tests, unit root test with rupture, cointegration test with multiple breaks and Markov chain model, provide results leading to convergent explanations. They enable to distinguish five sub-periods (denoted phases) from 2006 to 2016.

	Null Hypothesis:	Obs	F-Statistic Prob.
	Δln(pester) does not Granger-cause Δln(pgdoe)	108	0.03817 0.9626
	Δln(pgdoe) does not Granger-cause Δln(pester)		4.18660 0.0179
	Note: Number of lags for the Granger causality test =2
	6. DISCUSSION

from November 2006 to February 2007: the

  sub-period experienced the start of the biodiesel market with the introduction of biofuel quotes on Euronext.Biodiesel production has increased as a result of EU directives, leading to blending targets and the system of reducing taxes on biofuels and penalties on fossil fuels. In the European Union, the required blending rate of biodiesel (measured in the amount of energy) increased from 2% in 2006 to 3.8% in 2008. Over the sub-period, the results of the Markov Chain model show that biodiesel prices are rather driven by renewable resource prices.

  Nevertheless, this latter rupture is detected under the hypothesis of common variability over all sub-periods. It leads to not consider February 2009 as a structural break. From March 2008 to June 2009, biofuel price appears to be driven mainly by oil price.

	From an economic viewpoint, demand for biodiesel was booming. The biodiesel "blend wall"
	was binding. This explains that the EU imports of biodiesel increased by 77% from 1,140
	billion liters (that is 1.01 million tons) in 2007 to 2.02 billion liters (that is 1.71 million tons)
	in 2008. Furthermore, higher demand for biodiesel was not only bound by the "blend wall".
	The EU imports of rapeseed increased 4.8 times from 685 thousand tons in 2007-2008 to
	3,353 thousand tons in 2008-2009 as shown in table 1. Furthermore, exports went down over
	the same period.

  Test 1: No structural break versus a fixed number of breaks BP propose a sup-F type test to test the null hypothesis of m=0 break versus some arbitrary number of breaks, m=k . They built an F-test in the following manner, where break dates

1k

(T , ,T ) are not investigated directly, but indirectly using the fraction ii λ = T T, i=1,2,...,k :

  Thus, BP suggest two versions of the null hypothesis (no structural break) against the alternative hypothesis (the number of breaks m is unknown) to endogenously determine the number of breaks. An upper bound of M breaks is specified to carry out the test. This test is named 'double maximum' because it uses the maximum of a sup expression. Two versions of the test are defined considering either an equal-weight for the F-statistics or a weight for each of them. The equal-weighted version of the test, UDmax is given by:

	UD	max	 F M q , T			1 max mM 		 sup ,..., m  1  	 Tm 1 ,..., ; F 	q		(13)
	An alternative approach, denoted WDmax, applies weights to the individual statistics. This
	version can be expressed as follows:

Table A2 .1 Unit root test in level term

 A2 DF Augmented Dickey-Fuller test, PP Phillips-Perron test , ZA Zivot-Andrews test. *** significant at the threshold of 1%, ** 5%, * 10%. The number of lags is determined using the BIC criterion. In the ZA test, the date is the last month of the sub-period before the break

	Test		ln(pbrente)	ln(prapeseed) ln(pgdoe)	ln(pester)
	ADF	none	-0.543	0.270	-0.547	0.051
		intercept	-1.315	-2.204	-1.037	-2.052
		trend	-0.863	-2.047	-0.528	-2.041
	PP	none	-0.465	0.275	-0.521	-0.003
		intercept	-1.287	-2.252	-1.205	-2.029
		trend	-0.419	-2.124	-0.595	-2.003

Note:

Table A2 .2 -Unit-root tests on price series

 A2

	Test		Δln(pbrente)	Δln(prapeseed)	Δln(pgdoe)	Δln(pester)
	ADF	none	-5.090***	-5.935***	-4.482***	-5.161***
		intercept	-5.076***	-5.920***	-4.475***	-5.138***
		trend	-5.391***	-5.963***	-4.815***	-5.167***
	PP	none	-7.121***	-7.962 ***	-7.500 ***	-7.652 ***
		intercept	-7.109***	-7.936 ***	-7.491 ***	-7.618 ***
		trend	-7.255 ***	-7.942 ***	-7.722 ***	-7.621 ***
	ZA	intercept	-8.034***	-8.147***	-8.477***	-7.862***
		date	December-08	February-08	November-15	January-11
		trend	-7.662***	-7.858***	-8.338***	-7.644***
		date	November-15	August-08	November-15	April-07
		intercept + trend	-8.693***	-8.524***	-8.783***	-8.495***
		date	December-08	December-08	February-09	February-09

APPENDIX

A.1. Tests for multiple structural breaks in the cointegration relationship

In the framework of a multiple regression model, Bai andPerron (1998, 2003a, b), denoted BP, suggest detecting multiple structural changes and to estimate break dates that are unknown. A general review of literature on structural break is proposed by [START_REF] Perron | Dealing with structural breaks[END_REF]. In its general version, the Bai-Perron process enables to identify structural regime changes and estimate break dates that are common to a sub-set of regressors.

The starting point for the analysis is a multiple linear regression with T observations and m potential breaks which involves m+1 regimes: The structural break dates or break points 1 (T , , T ) m are unknown and in line with BP, we have adopted the convention that 0 T0  and m+1 TT  .

The purpose is to estimate the unknown regression coefficients together with the break points in the sample of T observations.


Julien Forget
email: julien.forget@univ-lille1.fr

École Temps Réel 2017 Uniprocessor real-time scheduling

A real-time system is a computer system where it is just as important to compute a correct value as it is to compute this value at the right time. Such a system is usually modelled as a set of tasks that must satisfy real-time constraints (periods and deadlines mainly). Real-time scheduling consists in finding a task execution order that satisfies all real-time constraints.

In this paper, we provide a brief overview of real-time scheduling on uniprocessor systems. We present classic scheduling policies and associated schedulability analyses. In addition, the paper gives some background on the relation between the classic real-time task model and dynamics of the modelled system. It also emphasizes the role of data-dependencies, how they are implemented and their impact on scheduling. [1], [2] have been great sources of inspiration for this paper.

I. INTRODUCTION

A real-time system is a computer system subject to a set of real-time constraints: not only does such a system need to compute the correct values, it must do so in a timely manner. For instance, let us consider the longitudinal flight control system of an airplane, such as [START_REF] Pagetti | The ROSACE case study: From simulink specification to multi/many-core execution[END_REF]. This system controls the angle of the control surfaces of the plane based on the current state of the plane and on the altitude required by the pilot. An important real-constraint is that the time required for the system to adjust the control surfaces in reaction to a pilot order or to a gust of wind must respect a predefined delay, in order to ensure the plane stability. Similar constraints can be found in many other areas, such as for instance in assisted driving systems in the automotive domain, in nuclear plant surveillance systems, in video processing systems, ... A real-time system is usually modelled as a set of tasks, each with its own dedicated functionality and real-time constraints. Real-time scheduling consists in finding an execution order for tasks, which satisfies all the task real-time constraints. This is a twofold problem. On one hand, we must choose a scheduling policy capable of satisfying the realtime constraints. General purpose scheduling policies (FIFO, Round-Robin, etc) are not well-adapted to real-time systems, since they usually focus on reducing the average response time of processes. In a real-time system, what matters is that tasks respect their real-time constraints in the worst-case. On the other hand, real-time systems are usually critical, so developers need a schedulability analysis, which ensures before execution that, for a given scheduling policy, the resulting execution will always respect the system real-time constraints.

In this paper, we focus on the scheduling of systems executing on a single computation core. The paper first details the classic way to model a real-time system (Section II). In addition to providing usual definitions on task real-time characteristics, it tries to relate these constraints to the dynamics of the system, and also gives a brief overview on how real-time tasks are usually implemented. Though the classic real-time task model assumes independent tasks, tasks are actually often related by data-dependencies. Section III discusses the modeling and implementation of such dependencies. Scheduling terminology and problem definition are provided in Section IV. Main results on uniprocessor schedulability analysis are provided in Section V, for fixed-task priority scheduling, and in Section VI, for fixed-job priority scheduling. Scheduling of dependent tasks is presented in Section VII.

II. REAL-TIME TASKS

Real-time systems can be separated into two sub-classes: event-driven systems and sampled systems. In an event-driven system, the system waits for an input event to occur and then computes its reaction. In a sampled system, the system acquires its inputs at regular intervals of time and computes its reaction for each sample of its inputs. While the eventdriven model is potentially more expressive, sampled systems are usually easier to analyze and their behaviour is more predictable, especially concerning the real-time aspects. Furthermore, in many event-driven systems, the time that separates the occurrence of two events can be lower-bounded, in which case the scheduling problem becomes quite similar to that of sampled systems (see sporadic tasks below).

A. Real-time constraints a) Period: A periodic task executes at regular intervals of time, as defined by its period. The period of a task is chosen as follows. On one hand, the period of a task must be below some bound, related to the inertia and physical characteristics of the device it controls. Above this value, the safety of the device (e.g. the stability of the airplane) is not ensured. This bound differs between the different physical devices of the controlled system. For instance, the propulsion devices of a space vehicle must be controlled very fast to ensure the stability of the vehicle, while the position of its solar panels can be controlled a little slower as a little energy loss has less dramatic impact on the vehicle. On the other hand, the period must be above some bound, below which the device will not be able to apply the commands fast enough or may get damaged. Of course, this lower bound also differs from one device to another. The period is usually chosen as close to the upper bound as possible, which spares unnecessary computations and thus enables the use of less powerful hardware, reduces energy consumption, and so on.

b) Deadline: The deadline of a task bounds the maximum time allowed between the task invocation and the task completion. In many real-time systems, it is equal to the task period, meaning that one invocation of a task must complete before the next invocation of that task. In some systems, the deadline can be lower than the period. While this may, in rare cases, correspond to a constraint related to the system dynamics, in most cases it is used as a way to artificially influence the system schedule, because tasks with shorter deadlines will usually be scheduled first (see scheduling techniques for dependent tasks in Section VII for instance). Systems where the deadline of a task can be higher than its period are quite uncommon, though they have been studied in the literature.

c) Offset: In some systems, offsets are associated to tasks. Instead of releasing tasks simultaneously at system startup, tasks are released at the date specified by their offset. This parameter is rarely related to the system dynamics but rather to implementation concerns (again, see Section VII for instance).

d) WCET: Performing a schedulability analysis requires the knowledge of the execution time of each task. Since the exact execution time of a task can be very hard to predict, an approximate worst-case execution time (WCET) is usually considered. It is pessimistic, in the sense that actual execution time might be lower, but safe, in the sense that the actual execution time will definitely be lower. WCET is not a realtime constraint per se, since we do not need to force a task to execute for as long as its WCET. It is nonetheless essential for system analysis.

e) Task model: We will use the following notations. A real-time task is denoted τ i (C i , T i , D i O i ), where C i is the WCET of τ i , T i is its activation period, D i is its relative deadline and O i its offset. In this paper, we assume that D i ≤ T i and O i ≥ 0, though more commonly it is assumed that D i = T i and O i = 0.

We denote τ i.k the k th (k ≥ 0) invocation, or job, of τ i . For periodic tasks, the job τ i.k is released at time o i.k = O i + kT i . For sporadic tasks, we have o i.k ≥ O i + kT i instead. In both models, every job τ i.k must be completed before its absolute deadline d i.k = o i.k + D i . In the following, we will focus on periodic tasks. The hyperperiod of a task set, which we will denote HP , is defined as the least common multiple of the periods of the tasks.

Figure 1 illustrates task real-time parameters for a periodic task τ i [START_REF] Pagetti | The ROSACE case study: From simulink specification to multi/many-core execution[END_REF][START_REF]FreeRTOS website[END_REF][START_REF]Rtai website[END_REF]0). Gray rectangles correspond to the execution of τ i , while hatched rectangles correspond to time intervals during which the system is busy executing another task. τ i.1 is preempted after it starts its execution to execute another task (about preemption, see Section IV). τ i.2 executes for less than

B. Implementation

A real-time task is usually implemented using mechanisms akin to threads, provided by the (Real-Time) Operating System. While the exact code is dependent on the target OS, the global structure remains more or less the same. Algorithm 1 details the typical implementation of a periodic task in pseudo-C code, while Algorithm 2 illustrates how to invoke such tasks. Concerning Algorithm 1:

1) The task first goes through an initialization phase and then waits for its initial release. In RTOS derived from Linux (for instance RTAI [START_REF]Rtai website[END_REF] or the ptask API [START_REF] Ptask | Periodic real-time task interface to pthreads[END_REF]), tasks start executing as soon as they are created, just like threads. Since creating all the tasks takes time, the programmer needs to implement in this phase mechanisms that synchronize the initial release of tasks (e.g. a synchronization barrier). In other RTOS, such as FreeR-TOS for instance [START_REF]FreeRTOS website[END_REF], tasks start only when the scheduler is explicitly invoked (start_scheduler in Algorithm 2), so only tasks with offsets need to explicitly wait for the initial release; 2) Once the initialization phase is complete, the task starts executing periodically. It repeats indefinitely the same behaviour: 1) execute the code corresponding to the actual functionality of the task; 2) wait for the next task activation (typically, wait for the next period). Concerning Algorithm 2:

• The task creation primitive usually takes, at least, three parameters: 1) a pointer to the task function that defines the task functional behaviour (like periodic_task1); 2) the arguments (often empty) to pass to that function (here, to function periodic_task1); 3) the real-time parameters of the task; • In a RTOS where tasks start executing as soon as they are created, we usually add an infinite idle loop (while(1);) at the end of the main function, because the termination of the main function causes the termination of the tasks.

In other systems, the execution of tasks starts when the scheduler is explicitly invoked (start_scheduler). Even though the task structure presented here is very common, RTOS usually allow more complex task implementations, where for instance the code executed by the task changes from one iteration to the next, where the period can be modified dynamically, etc. For instance, a common rookie mistake is to forget to wait for the next period at the end of a task iteration. This is in no way verified by the OS or by the compiler, even though this causes obvious problems at execution. So, it is up to the programmer to ensure that the program respects the task model that was used to perform the schedulability analysis.

RTOS that follow the OSEK standard [START_REF] Osek | Osek/vdx operating system -version 2[END_REF], including Trampoline [START_REF]Trampoline website[END_REF], opt for a more rigid approach where the task set and its real-time characteristics are defined statically in a dedicated OIL file [START_REF] Osek | Osek/vdx system generation -oil : Osek implementation language -version 2.5[END_REF]. The task implementation model is predefined and the user only provides the function corresponding to a single iteration of the task (the task_functionality() function in Algorithm 1), which is automatically repeated by the RTOS at each task invocation. This model is less permissive, but it prevents some design mistakes, such as those discussed earlier for instance (immediate loops or main function finishing and killing tasks).

III. DATA-DEPENDENCIES

The seminal work on real-time scheduling of periodic tasks by Liu & Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF], and a very large portion of the real-time scheduling literature, assume real-time systems consisting of independent tasks, meaning that there is no apriory ordering constraint relating tasks. Obviously though, tasks collaborate to compute the system outputs and as a result are related by data-dependencies, meaning that some tasks produce data used by some other tasks to perform their own computations.

A. Communication semantics

There are mainly two possible semantics for datacommunications. With register-based communications, used for instance in the automotive domain [START_REF]AUTOSAR website[END_REF], when a task executes it consumes the last value produced, not considering when it was produced. With such communications, the relative order between the task producing the data and the task consuming it remains unconstrained. On the contrary, with causal communications, the task producing the data must complete its execution before the task consuming it starts its execution. Such communications yield more deterministic systems and are thus preferred in critical systems, such as avionics systems for instance [START_REF] Pagetti | The ROSACE case study: From simulink specification to multi/many-core execution[END_REF].

Causal communications introduce additional real-time constraints, called precedence constraints: a precedence constraint requires one task to execute before another. A dependent task set is modelled as a directed acyclic task graph G = (S, E),

where S = ({τ i (C i , D i , T i , O i )} 1≤i≤n
) is a set of tasks, as defined previously, and E ⊆ S ×S. A precedence constraint, is denoted τ i → τ j , with τ i → τ j ≡ (τ i , τ j ) ∈ E. If T i = T j , we say that τ i → τ j is a simple precedence constraints. Otherwise we say that it is an extended precedence constraint.

B. Extended precedence constraints

In the general case, precedence constraints may relate tasks with different periods. Such a system is illustrated in Figure 2, which describes the tasks of the longitudinal flight control system of an aircraft (this description is based on [START_REF] Wyss | Calcul de propriétés temps réel de bout-en-bout dans un programme synchrone multi-périodique[END_REF]). This system controls the angle of the control surface (order) based on: the current surface angle (angle), the current aircraft vertical speed (vz), the current aircraft altitude (altitude) and the altitude required by the pilot (required altitude). The software architecture consists of six tasks that make up three computation chains:

• A fast chain operating at 30 ms from EF to EL, which controls the control surface according to a required angle; • A multi-rate chain from vzF (period 30 ms) to vzL (period 40 ms), then to EL (period 30 ms), which controls the vertical speed; • A multi-rate chain from hF (period 60 ms), to hHL (period 60 ms), to vzL (period 40 ms), to EL (period 30 ms), which controls the trajectory the plane follows to reach the altitude ordered by the pilot.

An extended precedence constraint τ i → τ j (where T i = T j ) only imposes precedence constraints on a subset of the jobs of τ i and τ j . The system model must thus specify the set of pairs (p, q) such that τ i.p → τ j.q .

In most real-time applications and design tools, such as Simulink [START_REF]Simulink: User's Guide[END_REF], AADL [START_REF] Feiler | The architecture analysis & design language (AADL): an introduction[END_REF] or Prelude [START_REF] Pagetti | Multitask implementation of multi-periodic synchronous programs[END_REF] for instance, extended precedence constraints follow patterns repeated periodically on the tasks hyperperiod. Some examples of extended precedence constraints are illustrated in Figure 3 (see [START_REF] Forget | Dynamic Priority Scheduling of Periodic Tasks with Extended Precedences[END_REF] for more details on extended precedence constraints models). The programmer can use the patterns of Figures 3(a

τ i τ i τ i τ i τ i τ i τ j τ j
(a) Sampling, at earliest of the same task: on one hand the slow task scatters the content of a big array between successive jobs of its consumer and on the other hand it gathers array fragments from its producer to construct a big array. These two patterns behave in a fashion similar to the MPI_gather and MPI_scatter primitives of the popular Message Passing Interface (MPI) API [START_REF] Gropp | Using MPI, 2nd Edition[END_REF].

τ i τ i τ j τ j τ j τ j τ j τ j (b) Selection, at latest τ i τ i τ i τ i τ i τ i τ j τ j (c) Array gathering τ i τ i τ j τ j τ j τ j τ j τ j (

IV. REAL-TIME SCHEDULING: PROBLEM DEFINITION

As mentioned earlier, scheduling real-time systems requires to:

1) Design a scheduling policy that will decide how to order the execution of tasks; 2) Design a schedulability test that will ensure, before system execution, that the execution order produced by the scheduling policy will respect the real-time constraints.

A. Schedulability

The execution of a set of real-time tasks is controlled by a scheduler that decides at each instant which task to execute on the processor. For a given schedule (produced by the chosen scheduler), we let e(τ i.k ) denote the start time of τ i.k in the schedule and s(τ i.k ) denote its completion time. The validity of a schedule is established as follows: Definition 1. A schedule is feasible if it respects the following constraints:

∀τ i.p , s(τ i.p ) ≥ o i.p
(1) ∀τ i.p , e(τ i.p ) ≤ d i.p

(2) ∀τ i.p → τ j.q , e(τ i.p ) ≤ s(τ j.q )

A scheduling policy is a set of rules that dictates how the scheduler will choose which task to execute. A task set is schedulable by a given scheduling policy if and only if the schedule it produces is feasible. A schedulability analysis checks whether a given task set is schedulable by a given scheduling policy. This analysis is usually performed statically, that is to say before system execution. Except for simplified problems, schedulability analysis is NP-hard. Therefore, existing analyses are either exact and have exponential complexity, or are pessimistic and have a polynomial or pseudo-polynomial complexity. With a sufficient schedulability test, all task sets considered schedulable by the test are actually schedulable. With a necessary schedulability test, all task sets considered unschedulable by the test are in fact unschedulable. An exact test if both sufficient and necessary.

B. Scheduling policy classes

Scheduling policies can be separated in different classes of policies. A scheduling policy is preemptive if it allows interrupting a job during its execution and resuming it later (e.g. to execute a higher priority task). Off-line scheduling consists in computing a (cyclic) feasible schedule before system execution. In that case, the scheduler becomes a simple dispatcher that repeats indefinitely the off-line schedule during execution. With on-line scheduling, the scheduler computes the schedule as execution progresses, based on the chosen scheduling policy. Most on-line scheduling policies are priority-based, meaning that they only define how to assign priorities to tasks and that the scheduler then always chooses to execute the highest priority ready task.

A scheduling policy P is optimal within a certain class of policies if the following holds: if a task set is schedulable by some policy of this class, then it is schedulable by P. For instance, we will see that the Deadline Monotonic policy is optimal within the class of fixed-task priority policies, for independent task sets without offsets. In this paper, we will focus on on-line priority based preemptive policies.

C. Fixed-tasks vs fixed-job priority policies

With a fixed-task priority scheduling policy (FTP), the priority of a task remains unchanged during the whole system execution. It is the most widely used class of policies for scheduling real-time systems and every RTOS provides support for it. With a fixed-job priority scheduling policy (FJP), the priority can differ between jobs of the same task, but remains unchanged for a given job. Liu and Layland [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] proposed the rate-monotonic (RM) fixed-task priority policy, where tasks with a shorter period are affected a higher priority and the earliest-deadline-first (EDF) fixed-job priority policy, where jobs with a shorter absolute deadline are affected a higher priority. RM is optimal within the class of fixed-task priority policies for periodic task sets with T i = D i and O i = 0. It can be extended to the deadline-monotonic policy (DM) [START_REF] Leung | On the complexity of fixed-priority scheduling of periodic, real-time tasks[END_REF], to schedule optimally a set of tasks with D i ≤ T i and O i = 0. For the case where O i ≥ 0, an optimal algorithm based on DM was defined by Audsley in [START_REF] Audsley | Optimal priority assignment and feasibility of static priority tasks with arbitrary start times[END_REF]. EDF is optimal in the class of fixed-job priority policies for scheduling a set of periodic tasks with D i ≤ T i and O i ≥ 0.

RM tends to be favored instead of EDF by real-time developers, at least for uniprocessor systems. A detailed comparison is available in [START_REF] Buttazzo | Rate Monotonic vs. EDF: Judgement Day[END_REF], it can be summarized as follows:

• Implementation: With FTP, task priorities can be computed before run-time (either by the programmer or at start-up by the OS), while with FJP they must be computed by the scheduler at run-time, each time a task is released. Furthermore, RTOS always provide support for fixed-task priority scheduling, while it is not always the case for fixed-job priority scheduling; • Run-time overhead: FJP requires to compute task priorities at run-time, which introduces a run-time overhead that does not exist with FTP. However, when context switches are taken into account, FJP introduces less overhead than FTP because the number of preemptions that occur with FJP is usually much lower than with FTP; • Task jitter: The task jitter is the variation between the response times of different jobs of the task. FTP reduces the jitter of high priority tasks but increases that of low priority tasks, while FJP treats tasks more equally. As a result, when the utilization factor of the processor is high (i.e. when the processor has few idle times), the average task jitter of the task set is lower with FJP than with FTP; • Overloads: When the total execution time demand of tasks exceeds the processor capacity, FTP causes less deadline misses than FJP. The problem with FJP is that if a task misses its deadline and carries on anyway, it causes other tasks to miss their deadlines (domino effect);

• Processor utilization: FJP enables better processor utilization (up to 100%) than FTP (around 70-80%), thus allowing more complex computations to be performed.

V. SCHEDULABILITY WITH FIXED-TASK PRIORITY A. Busy period

The concept of busy period plays a central role in the schedulability analysis of FTP. A k-busy period is a time interval where the processor is kept busy executing task of priority higher than or equal to k. This is illustrated in Figure 4. The step function corresponds to the cumulative demand for execution on the processor, also called the Demand Function. At time 0, three jobs are released so the Demand Function steps for an amount equal to the sum of the three jobs WCET. This starts the first 3 -busy period of the system. This period finishes when the Demand Function meets the Time Function w = t (at time t, the processor has executed t units of work). Such a meeting point is called an idle time: the processor remains idle until the next job release.

The response-time of a job is the time interval from the job release to the job completion. The worst-case response-time of a task is the greatest response-time of its jobs. A task-set is schedulable if and only the worst-case response-time of each task is lower than its deadline. The following theorem enables to relate response times to busy periods Theorem 1 ([19], [START_REF] Audsley | Applying new scheduling theory to static priority pre-emptive scheduling[END_REF]). The worst-case response time of a task of priority k is equal to the longest k-busy period.

So, to check system schedulability, we can compute the longest k-busy period of each task τ k and compare it to its deadline. A busy period always ends on the condition that the processor utilization ratio U = n i=1 Ci Ti ≤ 1 (note that this is also a trivial necessary schedulability condition for FTP). In other words, if this condition is fulfilled, then there is at least one idle time. Let n be the lowest priority of the system, if U = 1 then the length of the longest n-busy period is equal to the hyperperiod of the task set (HP ). Since HP is the least common multiple of the periods of the task set, HP is exponential with respect to the number of tasks of the task set.

In [START_REF] Joseph | Finding response times in real-time system[END_REF], authors propose a pseudo-polynomial solution for computing the length of the longest i-busy period B i . It is computed as the least fixed-point of the following equation (where hp(i) denotes the tasks with higher priority than τ i ):

B i,0 = C i B i,k+1 = C i + j∈hp(i) B i,k T i C j

B. Schedulability tests

Response-time analysis (RTA) based on the busy period, as presented in the previous section, provides a feasibility test that is actually independent of the scheduling policy. Indeed, since it is a necessary and sufficient schedulability condition, then any optimal scheduling policy can rely on time workload w=t

• idle point • idle time • 3-busy period τ 1 τ 2 τ 3
Fig. 4. Time demand function this condition. Unfortunately, RTA does not have polynomial complexity. In this section we discuss some less complex specific schedulability tests. For RM, the following sufficient schedulability test was proposed in [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF]:

U = n(2 1/n -1)
It is however quite pessimistic. It yields maximum processor utilization ratios between 80% (for smaller values n) and 70% (for greater values of n), while simulations show that the average bound is around 88% [START_REF] Lehoczky | The rate monotonic scheduling algorithm: Exact characterization and average case behavior[END_REF]. Tighter utilization bound tests have been proposed in [START_REF] Bini | Rate monotonic analysis: the hyperbolic bound[END_REF], [START_REF] Bini | Schedulability analysis of periodic fixed priority systems[END_REF].

For DM, exact exponential schedulability tests have been proposed in [START_REF] Lehoczky | Fixed priority scheduling theory for hard real-time systems[END_REF], [START_REF] Manabe | A feasibility decision algorithm for rate monotonic and deadline monotonic scheduling[END_REF].

Le us now consider systems with offsets. A critical instant occurs when all the tasks are released simultaneously. It was proved in [START_REF] Audsley | Optimal priority assignment and feasibility of static priority tasks with arbitrary start times[END_REF] that the longest busy period is initiated the critical instant. For systems without offsets, this means at date 0. For systems with offsets however, the critical instant may not exist, which means that we need to study all the busy periods up to max(O i ) + 2HP [START_REF] Leung | On the complexity of fixed-priority scheduling of periodic, real-time tasks[END_REF], [START_REF] Choquet-Geniet | Minimal schedulability interval for real-time systems of periodic tasks with offsets[END_REF].

C. Shared resources

Using mutual exclusion mechanisms to handle shared resources in real-time application scheduled with FTP, via either mutexes or semaphores, introduces two well-known sources of bugs: priority inversion and scheduling anomalies.

A scheduling anomaly occurs when the system is deemed schedulable by a schedulability test, but the schedule produced at execution is infeasible, due to a task executing for less than its WCET. This is illustrated in Figure 5. We consider a task set without offsets S = {τ 1 (2, 8, 6), τ 2 [START_REF]FreeRTOS website[END_REF][START_REF] Forget | Dynamic Priority Scheduling of Periodic Tasks with Extended Precedences[END_REF][START_REF] Pagetti | Multitask implementation of multi-periodic synchronous programs[END_REF], τ 3 [START_REF]FreeRTOS website[END_REF][START_REF] Forget | Dynamic Priority Scheduling of Periodic Tasks with Extended Precedences[END_REF][START_REF] Forget | Dynamic Priority Scheduling of Periodic Tasks with Extended Precedences[END_REF]} where tasks sharing a resource using mutexes are depicted in gray. When C 2 = 6, the schedule is feasible, while it is not when C 2 = 5 (τ 1 misses its deadline). This phenomenon is quite counter-intuitive, since here reducing an execution time produces a worse case. This implies that we cannot rely on a simple simulation to test the feasibility of a task set with shared resources.

A priority inversion occurs when a task is delayed by a lower priority task, even though it does not share a resource with it. This is illustrated in Figure 6. We consider a task set with offsets, where mutual exclusion sections are depicted in gray. In this example, τ 2 is running while the highest priority task τ 1 is waiting for τ 3 to complete its critical section, which causes τ 1 to miss its deadline.

An intuitive solution to prevent priority inversion is the Priority Inheritance Protocol (PIP) [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF]: when a task gains control of a shared resource, it inherits the priority of the highest priority task that shares this resource, until completion of its critical section. This completely prevents priority inver- sions, however the number of times a task can be blocked when trying to enter its critical section can be quite high.

Authors of [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF] instead proposed the Priority Ceiling Protocol (IPCP, here we consider the "immediate" variation of the protocol), which reduces blocking times. Each resource has a priority ceiling equal to the highest priority amongst task using it. When a task executes, its priority becomes the maximum of the priority ceilings of the resources it uses. As a consequence, a task can only be blocked once, at the beginning of its execution. Indeed, to start executing all the resources it requires must be free, otherwise it is blocked (by higher priority tasks). IPCP is readily available in many real-time executives (e.g. Real-Time POSIX, OSEK/VDX, Real-Time Java).

VI. SCHEDULABILITY WITH FIXED-JOB PRIORITY

A. Schedulability tests

When D i = T i and O i = 0, schedulability with EDF is a very simple problem: it was proved in [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard-real-time environment[END_REF] that U ≤ 1 is an exact schedulability condition.

When D i ≤ T i and O i = 0, the problem becomes much more difficult. Unfortunately, the worst-case response time does not occur at a critical instant, which makes responsetime analysis for EDF quite difficult. Instead, schedulability tests for EDF rely on the concept of processor demand [START_REF] Baruah | Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor[END_REF]. The processor demand h(t), which represents the amount of work that must be completed before time t, can be computed as follows:

h(t) = n i=1 t + T i -D i T i C i
As the load must never exceed the available processing time, schedulability can be stated as: ∀t, h(t) ≤ t Schedulability analysis checks this condition on a limited number of values of t, by noting that: 1) h(t) only increases at job deadlines; 2) there exists an upper bound L on the values of t that must be checked. Two formulas have been provided to compute L. The first bound L a is computed as follows:

L a = max{D 1 , . . . , D n , n i=1 (T i -D i )C i /T i 1 -U }
The second bound L b is the least fixed-point of the following recurrence:

w 0 = n i=1 C i w j+1 = n i=1 w j T i C i
Schedulability can then be tested by verifying that h(t) ≤ t for each deadline in L = min(L a , L b ). When D i ≤ T i and O i ≥ 0, a schedulability test was proposed in [START_REF] Spuri | Analysis of deadline scheduled real-time systems[END_REF].

B. Shared resources

Several solutions have been proposed to support shared resources with FJP. An adapted version of PCP was described in [START_REF] Chen | Dynamic priority ceilings: A concurrency control protocol for real-time systems[END_REF], however it has high run-time overhead. A better version, which retains the properties of PCP, is available in [START_REF] Baker | Stack-based scheduling of realtime processes[END_REF].

VII. SCHEDULABILITY OF DEPENDENT TASK SETS A. Precedence encoding

An elegant solution for scheduling dependent tasks was presented in [START_REF] Chetto | Dynamic scheduling of realtime tasks under precedence constraints[END_REF]. Authors proposed to encode precedence constraints in task real-time constraints. Let preds(τ i ) denote the set of all predecessors of τ i and succs(τ i ) the set of its successors. For simple precedence constraints, the encoding consists in adjusting the release date and deadline of every task as follows:

O * i = max(Oi, max τ j ∈preds(τ i ) (O * j )) (4)
d * i = min(di, min τ j ∈succs(τ i ) (d * j -Cj)) (5)
The intuition is that a task must finish early enough for its successors to have sufficient time to complete before their own deadline. For each precedence constraint τ i → τ j , Equation 4ensures that τ i is released before τ j . Assuming that priorities are assigned based on deadlines (e.g. with EDF or DM), Equation 5ensures that τ i will have a higher priority than τ j . As a consequence, τ i will be scheduled before τ j .

Theorem The consequence of this theorem is that we obtain a schedulability for dependent tasks with simple precedence constraints that works as follows ( [START_REF] Chetto | Dynamic scheduling of realtime tasks under precedence constraints[END_REF], [START_REF] Forget | Scheduling Dependent Periodic Tasks Without Synchronization Mechanisms[END_REF], [START_REF] Forget | Dynamic Priority Scheduling of Periodic Tasks with Extended Precedences[END_REF]):

1) Perform the precedence encoding; 2) Apply a schedulability test for an optimal scheduling policy for independent tasks (DM, Audsley's policy, or EDF) on the modified task set.

B. Extended precedence constraints

For extended precedence constraints, the encoding technique requires to assign different deadlines and offsets for different jobs of the same task. Let us for instance consider the tasks set S 1 = {τ i , τ j }, with (O i = 0, C i = 2, D i = T i , T i = 4), (O j = 0, C j = 4, D j = 6, T j = 8). The precedence pattern for τ i → τ j is defined informally as follows:

τ i τ i τ i τ i τ j τ j
If we set the same adjusted relative deadline for all jobs of τ i , that is D * i.n = 2 for n ∈ N, then τ j.0 will miss its deadline (date 6). However, if we set D * i.n = 2 for n ∈ 2N and D * i.n = 4 for n ∈ 2N + 1, S * is schedulable with EDF (we obtain the schedule depicted above). Let preds(τ j.q ) denote the predecessors of jobτ j.q and succs(τ i.p ) denote its successors. The encoding rule becomes: o * j.q = max(o j.q , max τi.p∈preds(τj.q)

(o * i.p ))

d * i.p = min(d i.p , min τj.q∈succs(τi.p) (d * j.q -C j ))

For schedulability analysis, extended precedence constraints usually follow patterns repeated on the tasks hyperperiod. So, for FTP, for each task we can basically take the maximum adjusted release date of its jobs over one hyperperiod and the minimum adjusted deadline [START_REF] Forget | Scheduling Dependent Periodic Tasks Without Synchronization Mechanisms[END_REF]. For FJP, we can unfold the extended precedence graph on the hyperperiod of the tasks (as suggested in [START_REF] Richard | Validation temporelle d'un logiciel temps réel : application à un laminoir industriel[END_REF]) and apply the encoding on the unfolded graph, which only contains simple precedence constraints [START_REF] Forget | Dynamic Priority Scheduling of Periodic Tasks with Extended Precedences[END_REF].

C. Note on synchronizations

When dealing with precedence constraints, one could expect problems similar to those encountered with shared resources. This is however not the case. First, concerning scheduling anomalies, let us consider our previous example of Figure 5. Figure 7 considers two different extended precedence constraints and shows that the anomaly does not occur anymore: the inversion between jobs of τ 1 and τ 3 does not happen when the execution time of τ 2.0 is reduced. This is because the relative order of τ 1 and τ 3 remains unchanged due to the precedence constraint, no matter what the execution time of τ 2 may be.

Concerning priority inversion, let us consider our previous example of Figure 6. Figure 8 shows that the inversion does not occur anymore. Assume we have a precedence constraint τ 3.0 → τ 1.0 . Due to the precedence encoding, the deadline of τ 3 is reduced, this prevents τ 2 from preempting it, which was the cause of the priority inversion previously. The inversion is avoided because, in a way, precedence encoding mimics Priority Inheritance: the predecessor task (τ 3 ) "inherits" the deadline of the successor task (τ 1 ).

VIII. CONCLUSION

This paper presented a quick overview of real-time uniprocessor scheduling. It does not aim at providing an exhaustive list of existing results on this topic, but instead focuses on the main ones. Furthermore, it tries to take the perspective of the programmer, instead of only considering purely theoretical aspects. For starters, it provides some insights on where realtime constraints come from during the design process. Then, it gives an overview of how to implement a multi-task realtime system. Finally, it focuses on the scheduling of dependent tasks, that is to say systems where data-communications play a non-negligible role.

Fig. 1 .

 1 Fig. 1. Execution of a real-time task

Algorithm 1 Algorithm 2

 12 Typical implementation of a periodic task void * periodic_task1(void * args) { //initialization wait_for_release(); Typical program for invoking two tasks int main() { // initialize real-time parameters params1 create_task(periodic_task1,args1,params1); // initialize real-time parameters params2 create_task(periodic_task2,args2,params2); // either start_scheduler(); or while(1); // This should never be reached return 1; }

Fig. 2 .

 2 Fig. 2. Vertical speed control

Fig. 3 .

 3 Fig. 3. Extended precedence constraints

3 Fig. 6 .

 36 Fig. 5. Scheduling anomaly

3 (Fig. 7 . 3 Fig. 8 .

 3738 Fig. 7. No scheduling anomaly with precedence constraints

  2 ([34],[START_REF] Forget | Scheduling Dependent Periodic Tasks Without Synchronization Mechanisms[END_REF]). Let S = {τ i (C i , T i , D i , O i )} be a dependent task set with simple precedence constraints. LetS * = {τ i (O * i , C i , D * i , T i )}be a set of independent tasks such that O * i and D * i are given by the previous formulas: S is feasible if and only if S * is feasible.