Abderrahmen Abdelli

Haythem Gharsa

Momtez Jmaï

Anne Gaucher

Mohamed Lotfi Efrit

Hedi M'rabet

Damien Prim
email: damien.prim@uvsq.fr

Versatile approach to densely substituted isoxazolines and pyrazolines: focus on a quaternary carbon center as a constitutive feature

Keywords:

A new family of isoxazolines has been obtained via 1,3-dipolar cycloaddition in good to high yields under mild conditions. Our approach focused on construction of the heterocyclic ring and direct access to a quaternary carbon center at position 5. The methodology has also been extended to pyrazoline analogues. The antibacterial activity of these compounds was evaluated, showing specific antibacterial activity against Staphylococcus aureus. Six members of these heterocycles exhibited MIC values of 4 µg/mL.

Introduction

Isoxazolines are partially hydrogenated five-membered heterocycles containing neighbouring oxygen and nitrogen atoms. Members of this family are key scaffolds of numerous naturally occurring and synthetic biologically active compounds. [1] The steady interest of the scientific community for modulating biological properties has resulted in the development of effective and appealing synthetic procedures towards densely substituted isoxazolines. [2][3][4][5][6][7][8][9][10] The incorporation of more diverse molecular functionalities to the isoxazoline core as well as the construction of targets displaying a quaternary center in position 5 are among the current challenges in this domain. Indeed, the C-5 site is crucial to tether isoxazoles to podophyllotoxin or coumarin derivatives in the elaboration of molecular architectures which display potent insecticide, acaricide or anticancer properties. [11,12] Moreover, the presence of a quaternary carbon center at position 5 of the isoxazoline ring prevents aromatization of the heterocycle into the related isoxazoles. Furthermore, the joint presence of a quaternary center and a functional group (CF 3 ) [5] were revealed to be crucial to the enhancement of the biological properties of isoxazoline derivatives. Access to differently substituted isoxazoline cores is reported through two main methodologies: cyclisation at the remote position or ring construction from oxime derivatives (Fig. 1).

Metal-mediated oxyhalogenation or oxidation of tertiary C-H bonds and photoredox processes are elegant procedures for promoting cyclisation at remote positions and thus the formation of isoxazolines. Such methods are especially useful to produce quaternary carbon centers substituted by aryl and alkyl groups as well as halides and di(tri)fluoromethyl groups. [6][7][8][9][10] Ring construction via conjugate addition or cycloaddition from oxime derivatives and nitrile oxide intermediates is a convenient approach allowing the formation of tertiary or quaternary C-5 centers mainly functionalized by alkyl, aryl or CF 3 groups. [2][3][4][5] However, the installation of carboxylic ester, sulfanyl or phosphonate groups at the C-5 position of the heterocycle remains less reported using both of the aforementioned strategies. [13] In most of these examples such functional groups substitute tertiary C-5 centers, with carboxylic esters being rarely found at a quaternary C-5 center. In this paper we have focused on the installation of two different functional groups, namely ethoxycarbonyl and phosphonomethyl at the quaternary C-5 center of isoxazolines. Our approach is based on the use of ethoxycarbonyl allylphosphonate [START_REF] Abdelli | For recent applications of ethoxycarbonyl allylphosphonate[END_REF] and nitrile oxides as the starting materials via a single step 1,3-dipolar cycloaddition under mild conditions. Our general methodology was further extended to the preparation of pyrazolines [15] from the same phosphonate precursor and nitrile imines. In this family of heterocycles, access to quaternary C-5 centers bearing valuable functional groups such as CO 2 R and CH 2 PO(OR) 2 remains a challenge. In addition, the preliminary biological activities of both isoxazolines and pyrazolines against Staphylococcus aureus have been evaluated for the development of potential new antibacterial agents.

A R T I C L E I N F O A B S T R A C T

Results and Discussion

1,3-Dipolar cycloaddition of alkenes to nitrile oxides, generated in situ from N-hydroximoyl chlorides, has been widely used for the synthesis of various heterocyclic structures. [16] We initially chose allylphosphonate 7 and hydroximoyl chloride 9 as model substrates to optimize the reaction conditions by testing several bases and solvents (Table 1). The reaction carried out in absence of a base led to the unchanged allylphosphonate 7 (Entry 1). We then decided to prepare the corresponding nitrile oxide in situ by treatment of chlorooxime 9 in the presence of a base. In addition, we were inspired by the reported methods for oxime cycloadditions, to use amine-type bases to access isooxazoline 12. Initially, we observed that protic or aprotic solvents had no significant effect on the reaction time or yield (Entries 2 and 5). Increasing the temperature reduced the reaction time, but unfortunately led to the formation of several by-products. Consequently, isoxazoline 12 was obtained with a poor yield (Entry 4).

Bases such as 1,8-diazabicyclo [5.4.0]undec-7-ene (DBU), pyridine and Et 3 N were successively tested (Entries 6-9). A significant increase in the yields and in allylphosphonate conversion was observed, after 18-24 h, when Et 3 N was used (Entries 2, 5, 8, 9). It should be noted that using more than 1.1 equivalent of Et 3 N has no significant effect on the reaction yield. Although only small differences were observed between the use of CH 2 Cl 2 and CHCl 3 , the latter led to cleaner crude material avoiding the presence of unidentified side-products. Thus, Et 3 N/CHCl 3 was determined as the most suitable base/solvent combination for the cycloaddition. With the optimized reaction conditions in hand, we proceeded to synthesize a new family of 5-phosphonomethylisoxazolines 12-17 in 67-82% yield (Scheme 1).

Scheme 1. Cycloaddition of hydroximoyl chlorides and allylphosphonates 7-8 towards phosphonomethylisoxazolines 12-17.

As reported in the literature, 1,3-dipolar cycloaddition can be regioselective or lead to the formation of a mixture of regioisomers. [17] In our case, the cycloaddition was selective as only one adduct could be identified according to 1 H and 13 C NMR data. Similarly, proton decoupled 31 P NMR spectroscopy confirmed the presence of a single adduct for isoxazolines 12-17, displaying a single signal in the range of 23-28 ppm. In our case, the steric effect may explain the regioselectivity of the reaction as previously noted in several 1,3-dipolar cycloadditions. [18] Plausibly, the formation of regioisomer (I) is favored in comparison with (II) (Fig. 2). Indeed, the formation of regioisomer (II) appears less favorable due to the steric hindrance between the aryl fragment of the nitrile oxide and the phosphonate-ethoxycarbonyl groups of dipolarophiles 7-8. The formation of regioisomer (I) was consistent with the 13 C NMR data which allowed discrimination between both potential adducts. The 13 C NMR spectra of isoxazolines 12-17 displayed a signal in the range 84-85 ppm, which precludes approach (II) and accounts for the formation of a quaternary carbon alpha to the oxygen atom, consistent with the spectroscopic data of regioisomer (I). In addition, 2D HMBC NMR spectroscopy undoubtedly confirmed that only regioisomer (I) was obtained. Indeed, protons H a and H b are privileged spectators of the structure of the heterocycle and thus of the cycloaddition selectivity. As shown in the ESI, 2D HMBC NMR spectroscopy exhibited characteristic correlations between H a and H b in complete agreement with the structure of regioisomer (I). At the same time, no correlation between H b and the (C=N) carbon of the heterocycle which potentially accounts for regioisomer (II) was observed. We next examined the transformation of allylphosphonates 7-8 into 5-phosphonomethylpyrazolines 21-25. Several studies have shown that 1,3-dipolar cycloaddition between dipolarophiles and hydrazonyl chlorides, which are used as a source of nitrile imines, is an efficient approach to access 5membered aza-heterocycles. [19,20] Scheme 2. Cycloaddition of hydrazonyl chlorides and allylphosphonates 7-8 towards 5-phosphonomethylpyrazolines 21-25.

In our case, we chose to examine the cycloaddition between allylphosphonates 7-8 and hydrazonyl chlorides. The latter can be easily generated in situ from hydrazones 18-20, using Nchlorosuccinimide (NCS) in pyridine (Scheme 2). The resulting hydrazonyl chlorides reacted smoothly with the allylphosphonates at room temperature to afford the expected pyrazoline derivatives. The cycloaddition process led to the formation of 5-phosphonomethylpyrazolines 21-25 in 70-90% yield (Scheme 2). Spectroscopic data were also consistent with the presence of a quaternary carbon center substituted by phosphonomethyl, methylcarboxylate and nitrogen fragments. Surprisingly, the cycloaddition between allylphosphonates 7-8 and hydrazones bearing an electron-withdrawing nitro group in both the meta and para positions did not allow the formation of the corresponding pyrazolines, even with prolonged reaction times and at higher reaction temperatures. This might be attributed to either the instability of the hydrazonyl chloride intermediate or the lack of reactivity of hydrazones bearing electron-withdrawing groups precluding in situ formation of the hydrazonyl chloride at an early stage of the reaction.

Antibacterial activity

The biological activities of nine compounds were evaluated for their antibacterial properties against several bacterial species; Staphylococcus aureus and Enterococcus faecalis classified as Gram-positive bacteria; Escherichia coli and Pseudomonas aeruginosa classified as Gram-negative bacteria. The antibacterial activity of isoxazolines 12-17 and pyrazolines 21-25 was assessed using the disc-diffusion and broth dilution methods. [21] Gram negative bacteria (Escherichia coli and Pseudomonas aeruginosa) and Enterococcus faecalis Gram positive bacteria isolates showed no sensitivity to the tested compounds. Interestingly, growth inhibition was observed in the Staphylococcus aureus strain that exhibited susceptibility to most of the evaluated compounds, especially 5phosphonomethylisoxazolines (12, 14 and 17) and 5phoshonomethylpyrazolines (22, 23 and 24) which exhibited the lowest MIC values of 4 µg/mL (Table 2). According to the antibacterial test results, the synthesized isoxazolines and pyrazolines showed specific activity against Staphylococcus aureus Gram positive bacteria.

Conclusion

In the present work, we have prepared novel 5phosphonomethyl-isoxazoline derivatives incorporating a quaternary carbon center at the C-5 position via 1,3-dipolar cycloaddition reactions from allylphosphonate precursors. This easy to implement and efficient strategy allowed the synthesis of densely functionalized isoxazolines. The cycloaddition process was shown to be highly selective, leading to a single adduct most plausibly due to steric factors. Our approach was also successfully extended to the preparation of 5-phosphonomethylpyrazolines starting from allylphosphonates. Biological activities of the synthesized isoxazolines and pyrazolines have been evaluated. Heterocycles bearing phosphonomethyl fragments exhibited specific activity against Staphylococcus aureus Gram positive bacteria. Functionalization of the phosphonated isoxazolines and pyrazolines as well as the study of its effect on their biological activities will be the subject of a forthcoming publication.

Figure 1 .

 1 Figure 1. Overview of literature methods and the construction of isoxazolines containing a quaternary C-5 center.

Figure 2 .

 2 Figure 2. Proposed regioselectivity control for the 1,3-dipolar cycloaddition.

Table 1 .

 1 Preparation of 5-phosphonomethylisoxazoline 12.

	Entry	Conditions a	Time (h) b	Yield 12
				(%)
	1	CH 2 Cl 2 , r.t	72	--
	2	Et 3 N, CH 2 Cl 2 , r.t	20	72
	3	Et 3 N, CH 3 CN, r.t	22	68
	4	Et 3 N, CH 2 Cl 2 , reflux	10	35
	5	Et 3 N, C 2 H 5 OH, r.t	24	68
	6	DBU, CHCl 3 , r.t	72	50
	7	pyridine, CH 3 CN, r.t	72	52
	8	Et 3 N, CHCl 3 , r.t	18	75
	9	Et 3 N, CHCl 3 , reflux	18	70

a Reaction was carried out using 7 (1 mmol), 9 (1.1 mmol) and base (1.1 mmol) in solvent (2 mL). b Reactions were monitored by TLC.

Table 2 .

 2 Antimicrobial activity assays and minimal inhibitory concentrations (MIC) against Staphylococcus aureus.

	Compounds	MIC (µg/mL)
	12	4
	14	4
	15	32
	17	4
	21	16
	22	4
	23	4
	24	4
	25	32
	Gentamicin	4

Acknowledgments

Authors are grateful to the Tunisian Ministry of Higher Education and Scientific Research, to the University of Tunis El Manar, to the CNRS and the University of Versailles-Saint-Quentin-en-Yvelines for financial support.

Supplementary Material

The supplementary material contains experimental procedures and spectroscopic data for all new compounds.

Click here to remove instruction text...

Graphical Abstract

To create your abstract, type over the instructions in the template box below.

Versatile approach to densely substituted isoxazolines and pyrazolines: focus on a quaternary carbon center as a constitutive feature Abderrahmen Abdelli a, *, Haythem Gharsa b , Momtez Jmaï a , Anne Gaucher c , Mohamed Lotfi Efrit a , Hedi M'rabet a , Damien Prim


domain: sde sdv

text:
Didier Cailhol

Lisa Ciadamidaro

Delphine Dupuy

Séverine Allegra

Françoise Girardot

Stéphane Pfendler
email: stephane.pfendler@gmail.com

Fungal and bacterial outbreak in the wine vinification area in the Saint-Marcel show cave

Keywords: Fungal outbreak, Sequencing, Show cave, Bacterial communities, Biodeterioration

In the Saint-Marcel cave (France), wood barrels and thousands of bottles containing red wine were stored for vinification. After storage began, a fungal and bacterial outbreak occurred, and the area was invaded by numerous types of mold colonizing the cave ceilings and all objects related to human activities (the stairwell and oenological materials). In this study, using the metabarcoding approach, we have studied the microbial outbreak and have linked the identified microorganisms to oenological activity. Both 16S and ITS primers were used to sequence the samples collected from the cave. The results showed that the dominant microorganisms proliferating in the cave were related to wine vinification. For instance, Zasmidium cellare, a strain known for living in dark and ethanol-rich environments, was the dominant fungus on the cave stairwell. Furthermore, Guehomyces pullulans, a cold-adapted yeast used for juice clarification, was recorded as the major species on the blackened limestone ceilings. These findings reveal a complex community structure in the studied cave based on the assembly of bacteria and fungi. Finally, our results demonstrate that oenological activities could seriously affect cave preservation, changing the natural microbial communities populating cave environments.

Introduction

For centuries, people have been visiting caves for tourism or recreation. As evidence of this activity, a signature dated from 1213 was found in the Postojna cave in Slovenia [START_REF] Cigna | Encyclopedia of caves[END_REF]. Currently, 250 million tourists visit more than 800 show caves around the world every year [START_REF] Cigna | Tourism and show caves[END_REF]. Tourist caves offer a wide range of activities to tourists (e.g., speleology, concerts, theatre, aquarium expositions, and wine tastings), generating 2.3 billion dollars per year [START_REF] Cigna | Development management and 'Lampenflora' and economy of show caves[END_REF]. However, natural site anthropization leads to microbial disturbances [START_REF] Cennamo | A Survey of the algal flora of anthropogenic caves of Campi Flegrei (Naples, Italy) archeological district[END_REF], even if ecological considerations become increasingly important. In the case of natural caves, microorganisms such as some bacteria or autotrophic protists can take advantage of the environmental changes (e.g., increased artificial light, carbon dioxide and organic matter) to proliferate. For instance, lampenflora are well known and widely described [START_REF] Borderie | Factors driving epilithic algal colonization in show caves and new insights into combating biofilm development with UV-C treatments[END_REF][START_REF] Cennamo | Diversity of phototrophic components in biofilms from Piperno historical stoneworks[END_REF]. The first observations were performed by Kyrle andGams in 1923 and1925, respectively [START_REF] Cigna | The problem of Lampenflora in show caves[END_REF][START_REF] Lamprinou | The show cave of Diros vs wild caves of Peloponnese, Greece -distribution patterns of Cyanobacteria[END_REF]. Since then, optical observations and the use of molecular methods have permitted a better overview of these organisms, which live together in a matrix called a biofilm. In addition to lampenflora, other microorganisms, such as fungi, have often been involved in microbial infestation of caves, such as the infestation that happened in the worldfamous Lascaux Cave (Bastian et al., 2009a(Bastian et al., , 2009b(Bastian et al., , 2009c)). The negative consequences of lampenflora and fungal outbreaks are numerous. In addition to creating a visual disturbance for tourists, microorganisms lead to limestone and wall painting degradation by physical or chemical actions [START_REF] Borderie | Factors driving epilithic algal colonization in show caves and new insights into combating biofilm development with UV-C treatments[END_REF]. Moreover, some microorganisms, such as fungi, can be dangerous for human health by inhalation of fungal spores [START_REF] Jurado | Fungal outbreak in a show cave[END_REF].

The Saint-Marcel cave is an important cave system located at the end of the "Gorges de l'Ardèche" (France). In addition to numerous other show caves around the world, this cavity suffers from lampenflora growth inside the tourist area. In France, sodium hypochlorite 4 is commonly used as a treatment against phototrophic and heterotrophic organism proliferation (Pfendler et al., 2017b). However, despite several treatments each year and a new lighting strategy consisting of limiting illumination to tourist hours, lampenflora growth in the Saint-Marcel cave continues. In addition, ceilings, some walls and some remarkable speleothems remain inaccessible to direct treatment, leading to a densification of microorganisms and a strong visual impact.

Furthermore, since April 2015, oenological activities have been undertaken in Saint-Marcel cave. To vinify red wine, several producers from Saint-Marcel village have stored 300 litres of wine in wooden barrels and one thousand wine bottles. Wine tastings in the cave, associated with guided speleological activities, are a part of an oenotourism project. However, after one year, strong fungal growth started on the wooden barrels and on the bottles in the wine storage section at the beginning of the tourist area, near the access gate and the "Gallery of Painters". Given the amount of mold, some other parts of the cave may be endangered by displaced spores due to the strong air dynamics that affect the speleological system. Several authors have described fungal communities in wine cellars [START_REF] Simeray | Annual variations of airborne fungal propagules in two wine cellars in French Jura[END_REF]Hass et al., 2010) or in natural cavities [START_REF] Stomeo | Assessment of bacterial and fungal growth on natural substrates: consequences for preserving caves with prehistoric paintings[END_REF][START_REF] Taylor | Cave entrance dependent spore dispersion of filamentous fungi isolated from various sediments of iron ore cave in Brazil: a colloquy on human threats whilecaving[END_REF]. However, as far as we know, fungal communities related to wine vinification in show caves have never been described.

The aim of this study was to assess the bacterial and fungal communities present following the establishment of oenological activities in a natural cavity. Widespread fungal and bacterial growth was observed on several types of materials present (metal, wood, PVC, and limestone) inside the Saint-Marcel cave. Samples were taken, and high-throughput sequencing (Illumina MiSeq) was used to determine microbial community structures. The ecological role of the microorganisms and their relation with wine storage are discussed.

Material and methods

Cave description

The catchment of the karst system on the Saint-Remeze plateau covers 70 km². The speleological network now extends more than 60 km, and five interconnected networks have been explored by speleologists. The lowest is a phreatic system 17 km long and -114 m deep, which has been explored by cave divers. Network I, studied in this present work, consists of the historical galleries of the cavity, and the increase in elevation from the natural entrance to the tourist part is 87 m. This area was the first part of the cave opened to tourism, which started in 1839. Most of the cave explorations started in this way. The morphologies of the galleries are typical of an old drainage system [START_REF] Mocochain | La grotte de Saint-Marcel (Ardèche)[END_REF], 4 km long, in several interconnected galleries. The current tourist part (104 m deep) dates from 1988 and is accessible from a dug tunnel; this part ends at the top of the mason vault, where it joins the cathedral, located 600 m from the natural entrance. The show cave in this area is four hundred metres long.

Two main modes of air circulation and intermediate modes operate according to seasonality. During the winter, the traffic mainly proceeds from the natural entrance and other low entrances towards the higher parts of the system connected with the surface (Aven du Deyspesse, etc.). During the summer, the direction of circulation is from high parts to low parts. During spring and fall, transitional systems are established over short periods of time depending on temperature differences between the surface and the galleries of the cave. The flow of air passing through the natural entrance has values of 7 to 11 l m 3 .s -1 and relatively high CO2 values from 1.5 to 2.5%. The airflow velocity was monitoring with a hot wire anemometer Testo 405 and an ibrid MX 6 Gas sensor with infrared CO2 and O2. The weekly 6 measurements led for 3 months. In April 2015, red wine vinification started in the Saint-Marcel cave. Thirteen wine barrels were stored 200 m from the cave entrance at 11 to 13.5°C [START_REF] Bondil | Appréhender le fonctionnement aérologique et climatologique de l'entrée de la grotte de Saint-Marcel au regard des enjeux d'habitat pour les Chiroptères[END_REF]. More than 2,500 bottles per year were maintained in zinc lockers, and 3,600 litres of wine were aged in oak barrels.

Fungal outbreak observations

In the Saint-Marcel show cave (Fig. 1), a fungal outbreak was detected in February 2019. In the entrance, substantial blue-grey molds were observed on the metal stairwell (Fig. 2 A). Below the stairwell, 13 stored wine barrels (Fig. 2 B) were contaminated with molds of different colours (e.g., green, yellow, white, and grey). These barrels were placed on wooden and limestone supports, which were also colonized with fungal mats. The fungal colonies showed several colours, sizes and structures (e.g., filamentous or cottony). For instance, some proliferations were 20-30 cm high and 15-20 cm wide (Fig. 2 C). Moreover, a fine and white mold was proliferating (Fig. 2 C) on a PVC garden hose, which was stored on the floor behind the barrels. Fig. 2 D shows black fungal proliferation on the limestone ceiling next to and above the wine barrels. Finally, green or white molds (Fig. 2 E) colonized wine bottles, more precisely on bottle corks.

Sampling in the wine storage area

Fifteen samples were collected in March 2019 in different contaminated parts of the wine storage area. Samples were taken in triplicate from stairwells, barrels, the PVC hose, and limestone and barrel supports, corresponding to the tourist pathway, wine equipment, cave soil and ceilings, respectively. In accordance with the sequencing platform (Microsynth AG, Balgach, Switzerland) protocol, at least 1 g of fresh matter was taken from each microbial growth instance. To avoid unwanted contamination, samples were directly scraped and collected in 50-ml sterile tubes. To keep the samples dry, 2 silica-gel bags were subsequently added to each tube. Samples were then maintained at room temperature during two days until total DNA extraction, amplification steps and sequencing.

Molecular methods and data analysis

The library creation, sequencing and data analysis described in this section were performed by Microsynth AG (Balgach, Switzerland). The V3 and V4 regions of the bacterial 16S rRNA gene were sequenced in a two-step Nextera PCR library procedure using the primer pair 341F (5′-CCT ACG GGN GGC WGC AG -3′) and 802R (5′-GAC TAC HVG GGT ATC TAA TCC -3′). To sequence the internal transcribed spacer (ITS2) regions of the fungal 18S rRNA gene, two-step Nextera PCR libraries using the primer pair ITS3 (5′-GCA TCG ATG AAG AAC GCA GC -3′) and ITS4 (5′-TCC TCC GCT TAT TGA TAT GC -3′) were created. The Illumina MiSeq platform and a v2 500 cycle kit were used to sequence the PCR libraries. Then,FastQC (v. 0.11.8) was used to assess read quality. The locus-specific V34 and ITS2 primers were trimmed from the sequencing reads with the software Cutadapt (v. 2.3). Paired-end reads were discarded if the primer could not be trimmed. Trimmed forward and reverse reads of each paired-end read were merged to in silico reform the sequenced molecule considering a minimum overlap of 15 bases using the software USEARCH (v. 11.0.667). Merged sequences were then quality filtered, allowing a maximum of one expected error per merged read and discarding those containing ambiguous bases.

From the remaining reads, the ITS2 subregions were extracted with the help of the ITSx software suite (v. 1.0.11) and its included fungi database. Reads that contained ambiguous bases or were outliers with respect to the amplicon size distribution were also discarded. The remaining reads were denoised using the UNOISE algorithm implemented in USEARCH to form operational taxonomic units (OTUs), discarding singletons and chimaeras in the process.

The resulting OTU abundance table was then filtered for possible bleed-in contaminations using the UNCROSS algorithm, and abundances were adjusted for 16S copy numbers using the UNBIAS algorithm. OTUs were compared against the reference sequences of the RDP 16S and UNITE databases, and taxonomies were predicted considering a minimum confidence threshold of 0.5 using the SINTAX algorithm implemented in USEARCH.

All statistical tests were performed at a significance level of 0.05. Indices of diversity were calculated using the Vegan package [START_REF] Legendre | Numerical and Ecology with R[END_REF] in R software v. 1.0.136 (R Development Core Team, 2016) and statistically tested using Kruskal-Wallis test.

Phylogenetic trees were obtained using SHAMAN software. Principal component analyses (PCAs) were performed using R software and statistically tested using the Kruskal-Wallis test.

Results

Taxonomic composition of samples

DNA of the bacteria and fungi was sequenced using an Illumina MiSeq device. A total of 539 fungal OTUs and 1319 bacterial OTUs were recorded. The 50 most abundant bacterial and fungal OTUs are listed in Tables S1 andS2.

Blue-grey mold on stairwell

The sequencing results obtained from the fungal growth on the stairwell (Fig. 2 A) showed that 83.6% of the total OTUs matched with Zasmidium cellare, 8.2% with Neodevriesia lagerstroemiae and 4.1% with Lecanicillium sp. Twenty-two other species were recorded but represented less than 1%. Actinobacteria (57.4%), Bacteroidetes (23.5%) and Proteobacteria (19.2) were the three dominant bacterial phyla recorded on the stairwell. Methylobacterium brachythecii, a Proteobacteria, was the most abundant species (11.9%), followed by Promicromonospora xylanilytica (9.7%), Olivibacter soli (9.7%), Pseudosphingobacterium domesticum (8.5%) and Promicromonospora iranensis (8.1%). In a less extensive proportion, Amycolatopsis lexingtonensis (2.8%) was also recorded.

Wine barrels and their supports

The fungal communities on wine barrels were predominantly composed of Talaromyces minioluteus (36.4%), Moristroma quercinum (30.4%), Penicillium corylophilum (14.3%) and Zygoascus meyerae (4.7%). Regarding bacteria, Proteobacteria (82%, mainly Pseudoxanthomonas spadix, Acidisoma sibiricum, Dyella jiangningensis and Tanticharoenia sakaeratensis, and Coxiella burnetii), Actinobacteria (9.4%), Acidobacteria (5.9%) and Bacteroidetes (2.7%) were the four phyla recorded on wine barrels.

The barrel supports were made of wood and placed on stones (Fig. 2

PVC hose

The major species recorded on the PVC hose was Candida railenensis (65.1%), followed by Sistotrema sp. (22.4%), Apiotrichum laibachii (5%) and 5 species (6.9%) of Penicillium (P. corylophilum, P. thomii, P. kongii, P. spinulosum, and P. marinum).

Actinobacteria (79.5%), Proteobacteria (17.1%) and Bacteroidetes (3.4%) represented the most abundant phyla on the stored hose. These phyla mainly consisted of the genera Streptomyces, Leifsonia, Kofleria, Agromyces and Pseudonocardia.

Limestone wall

Guehomyces pullulans was recorded as the major species on the limestone walls (33.5%), while Hypocreales (23.4%, mainly the genus Trichoderma), Mortierellales (12.1%), Pleosporales (9.6%), Sordariales (6.6%) and GS11 (6%, belonging to the phylum Rozellomycota) were the other major fungal orders.

Similar to the barrel supports, the limestone walls were mainly colonized by Proteobacteria (46.6%) and Actinobacteria (45.9%). The nine most abundant species that were recorded were Dongia mobilis, Segetibacter aerophilus, Pseudoxanthomonas yeongjuensis, Kofleria flava, Bradyrhizobium icense, Gaiella occulta, Methyloceanibacter caenitepidi, Ferrithrix thermotolerans and Hyphomicrobium hollandicum.

Indices of diversity

The species diversity and evenness were calculated using the Shannon and Pielou indices (Fig. 3). The results indicated higher fungal community diversity on limestone (4 and 0.7 bits.cell -1 , respectively) than metal (0.8 and 0.1 bits.cell -1 , respectively) and PVC supports (1.1 and 0.2 bits.cell -1 , respectively). Thus, the fungal communities colonizing wooden barrels and supports showed half the diversity of those on limestone. However, the bacterial communities sampled on each type of material (metal, wood, limestone and PVC) showed high diversity. In fact, the Shannon and Pielou indices ranged from 3 to 4.3 and 0.5 to 0.7 bits.cell -1 , respectively.

Influence of colonized substrate on communities

The results of phylogenetic trees (Fig. 4) and principal component analysis (Fig. 5) showed that the fungal communities were specific to the colonized support. The metallic stairwell and wood barrels were mainly colonized by Ascomycota, while a higher proportion of Basidiomycota were recorded for both the PVC hose and limestone supports. In fact, 93% of the metal-colonized fungi belonged to the order Capnodiales, while the PVC hose was colonized by 68% Saccharomycetales. Furthermore, 72% of the Eurotiales and Phaeomoniellales inhabited the wood, and 90% of the Hypocreales, Cystofilobasidiales and Pleosporales were recorded on limestone. The principal component analysis results were in accordance with phylogenetic trees. Indeed, the FL1 axis (40.93%) and FL2 axis (17.69%) showed clear fungal community differences between the limestone, metallic stairwell, wood and PVC. Moreover, the PCA results distinguished two types of samples: the first samples were collected near the wine on the floor (PVC hose and barrel supports), and the second samples were collected from above the wine storage area (stairwell and limestone ceiling), in contact with alcohol released from the wine barrels. Similar results were obtained for the bacterial communities (data not shown).

Discussion

Microbiology in show caves

Since bacteria and fungi play a crucial role in natural caves, several studies have assessed the microbial communities of such caves [START_REF] Jurado | The fungal colonisation of rock-art caves: experimental evidence[END_REF][START_REF] Pfendler | Biofilm biodiversity in French and Swiss show caves using the metabarcoding approach: first data[END_REF][START_REF] Long | Actinobacterial community in Shuanghe Cave using culture-dependent and -independent approaches[END_REF]. For instance, microorganisms are involved in cave and speleothem formation [START_REF] Kondratyeva | Role of the microbial community in formation of speleothem (moonmilk) in the 23 23 Snezhnaya carst cave (abkhazia)[END_REF], in limestone deterioration [START_REF] Coutinho | Biodeterioration of majolica glazed tiles by the fungus Devriesia imbrexigena[END_REF] and in bioactive molecule production [START_REF] Groth | Actinomycetes in karstic caves of northern Sapin (Altamira and Tito Bustillo)[END_REF]. In our previous studies, we showed the high diversity of microorganisms present in natural caves and their high adaptation and plasticity depending on the sampled cave section, especially for bacteria and autotrophic protists (Pfendler et al., 2018a). However, few studies have been carried out on fungal outbreaks in natural caves. Fungi naturally live in caves but are less abundant than bacteria. Thus, they are mostly found as degraders and have mainly been recorded on organic matter, such as dead insects, bat guano, decaying wood or plant roots penetrating into shallow caves [START_REF] Gunde-Cimerman | Mycoflora of cave cricket Troglophilus neglectus cadavers[END_REF][START_REF] Vanderwolf | A world review of fungi, yeasts, and slime molds in caves[END_REF]. Understanding the microorganism communities living in show caves is essential to understand cavity dynamics and operation.

Using modern technology, such as high-throughput sequencing, microorganism community assessment can give valuable information regarding cave ecology.

In the Saint-Marcel cave, we assessed the bacterial and fungal communities, and according to the results, we hypothesized that two types of communities may be distinguished. The first community may be related to oenological activities and cave tourism.

In fact, the results of this study show that each type of colonized surface (wood, PVC, metal, limestone) was mainly inhabited by wine storage-related communities. The second community has no direct link with wine ageing or tourism and may be considered a nonanthropized cave community.

Wine storage-related communities

Microorganisms inhabiting the metallic stairwell and limestone ceilings

A thick blue-grey mycelial mat colonized the stairwell at the entrance of the cave. This mycelium was identified as Zasmidium cellare, which is well known as cellar mold and lives in dark and ethanol-rich environments, such as wine and brandy cellars in central and southern Europe (Hass et al., 2010). As demonstrated in a previous study [START_REF] Tribe | Moulds that should be better known: the wine cellar mould, Racodium cellare Persoon[END_REF], alcohol that has leaked out of wine barrels may be used by Z. cellare as volatile carbon source. The use of ethanol by some mold species has been known for several decades and has been further demonstrated under laboratory conditions (Tribe and Mabadeje, 1972). As a result of this process, all available surfaces may be covered by a thick mycelial mat [START_REF] Tribe | Moulds that should be better known: the wine cellar mould, Racodium cellare Persoon[END_REF]. Accordingly, in our study, we observed a high proliferation of Z. cellare compared to other strains. It is well known that such proliferation can lead to an increase in spore concentrations in the air, as reported by Hass et al. (2010), which are dangerous for cave preservation, limestone degradation and human health by inhalation [START_REF] Jurado | Fungal outbreak in a show cave[END_REF] In addition to Z. cellare, Guehomyces pullulans was detected in both metallic-and limestone-colonized samples. This strain was found by [START_REF] Golden | Effect of chemical treatments on microbiological, sensory and physical qualities of individually shrink-wrapped produce[END_REF] on individually shrink-wrapped peaches. G. pullulans is described as a cold-adapted yeast capable of producing pectinases at low temperatures, leading to the clarification of fruit juice [START_REF] Cavello | Pectinolytic yeasts from cold environments: novel findings of Guehomyces pullulans, Cystofilobasidium infirmominiatum and Cryptococcus adeliensis producing pectinases[END_REF], such as grapes, by the breakdown of the substrate pectin. When pectin is decomposed by enzymes of microorganisms, the methyl esters combine with water to produce methanol. Then, the methanol can be oxidized by some prokaryotes, such as 14 Methyloceanibacter caenitepidi, a methanol-oxidizing bacterium [START_REF] Takeuchi | Methyloceanibacter caenitepidi gen. nov., sp. nov., a facultatively methylotrophic bacterium isolated from marine sediments near a hydrothermal vent[END_REF] mainly recorded on the limestone walls and ceilings of the Saint-Marcel cave.

Microbial communities on oak barrels

One-third of the fungal communities present on the oak wine barrels consisted of Talaromyces minioluteus. Since T. minioluteus has been described as a dextranase producer [START_REF] Sufiate | In vitro and in silico characterization of a novel dextranase from Pochonia chlamydosporia[END_REF], we can hypothesize that this strain is a wine-related fungus. In fact, the by-product of dextranase is dextran, which was discovered by Louis Pasteur as a microbial product in wine [START_REF] Pasteur | On the viscous fermentation and the butyrous fermentation[END_REF]. In our study, the second most dominant strain recorded on the oak barrel samples was Moristroma quercinum, consisting of >30% of the total species. [START_REF] Nordén | New species of Moristroma (Ascomycetes) and phylogenetic position of the genus[END_REF] on hard heartwood from attached or shed branches from Quercus robur and Q. petraea. This species can also be found on old oak stumps. This result is not surprising, knowing that in general, wine barrels, and specifically the wine barrels present in the Saint-Marcel cave, are made using oak wood. Finally, the fourth most abundant fungus, Zygoascus meyerae, is a yeast belonging to the class Saccharomycetes and has been isolated from environmental sources such as damaged grapes [START_REF] Ioakimidou | Candida hellenica var. hellenica as a possible cause of respiratory infection in a child with acute myeloid leukemia[END_REF].

M. quercinum was found by

The oak barrels were also colonized by wine-related bacteria, such as Acidisoma sibiricum, the second most abundant bacteria on the wood barrels. This species is an acidophilic (pH 3.0-7.6) and psychrotolerant (2-30 °C) bacterium [START_REF] Belova | Acidisoma tundrae gen. nov., sp. nov. and Acidisoma sibiricum sp. nov., two acidophilic, psychrotolerant members of the Alphaproteobacteria from acidic northern wetlands[END_REF] that can grow under the optimal conditions on wine barrels in the Saint-Marcel cave (wine pH=3-4 and cave temperature of 14°C). A second potential wine-related bacterium was Dyella jiangningensis, which represented 9% of the total bacteria and was isolated by [START_REF] Zhao | Dyella jiangningensis sp. nov., a γ-proteobacterium isolated from the surface of potassium-bearing rock[END_REF] from the surfaces of weathered potassic trachytes in China. We can thus hypothesize that this bacterium is linked to wine, given that potassium is found in an amount of 0.7 to 2% per litre in wine. Moreover, potassium bicarbonate is used for the deacidification of wine.

Microorganisms colonizing PVC

Both Candida railenensis and Sistotrema sp. were the most abundant fungi found on the PVC hose. [START_REF] Isaeva | The yeast Candida railenensis in the fruits of English oak (Quercus robur L.)[END_REF] reported that C. railenensis is a yeast colonizing oak fruits, but this fungus has also been described in decaying organic matter, such as trunks [START_REF] Ramírez | Two new species and one variety of nitrate-utilizing mycelial Candida isolated from decayed wood in the evergreen rainy Valdivian forest of southern Chile[END_REF]. Finally, the heavy metal-, tannin-and acid-tolerant microorganism P. spinulosum [START_REF] Hujslová | Extremely Acidic Soils are Dominated by Species-Poor and Highly Specific Fungal Communities[END_REF] may also be linked with oenological activity. However, no direct link has been established between the recorded bacteria and cave oenological activities.

Non-related bacteria and fungi to wine ageing

The second type of microbial community we propose consists of microorganisms that have no direct link with oenological activities. The obtained results show that these microorganisms were not the dominant microorganisms that were sequenced. Several entomopathogenic fungi were recorded on the stairwell, oak barrels and PVC. The presence of entomopathogenic fungi is not surprising since they are commonly described in show caves [START_REF] Vanderwolf | A world review of fungi, yeasts, and slime molds in caves[END_REF]. For instance, the genus Lecanicillium is known and used worldwide for the biological control of insects [START_REF] De Faria | Mycoinsecticides and Mycoacaricides: A Comprehensive List with Worldwide Coverage and International Classification of Formulation Types[END_REF]. P. corylophilum is a pathogen of mosquitoes that produces alkaloids such as epoxyagroclavine and citrinin [START_REF] Moraes | Fungal flora of the digestive tract of Rhodnius prolixus, Rhodnius neglectus, Diptelanogaster maximus and Panstrongylus megistus, vectors of Trypanosoma cruzi, Chagas, 1909[END_REF]. Other abundant fungi were recorded, such as those inhabiting wine barrels. One of the most abundant was Penicillium corylophilum, which is a species occurring in damp buildings in the United States, Canada and Western Europe [START_REF] Bok | Mass occurrence of Penicillium corylophilum in crawl spaces, south Sweden[END_REF]. It was reported that P. corylophilum is the completely dominant mould species in crawl spaces in 16 Sweden [START_REF] Bok | Mass occurrence of Penicillium corylophilum in crawl spaces, south Sweden[END_REF]. On PVC, several members of the genus Penicillium were recorded, such as the food spoiler P. thomii [START_REF] Jones | A critical examination of SEM ultrastructural features in two Penicillium thomii isolates from soil[END_REF], P. kongii, which lives on plant leaves [START_REF] Wang | Penicillium kongii, a new terverticillate species isolated from plant leaves in China[END_REF], and the roquefortine C producer P. marinum [START_REF] Wigley | An experimental strategy towards optimising directed biosynthesis of communes in analogues by Penicillium marinum in submerged fermentation[END_REF].

Similar to the fungi, the most abundant bacterial species consisted of wine-related bacteria. Among the other species, several known species were recorded, such as Pseudoxanthomonas spadix, which was isolated from gasoline-contaminated sediment and can metabolize all six BTEX (benzene, toluene, ethylbenzene, and o-, m-, and p-xylene) compounds [START_REF] Lee | Complete genome sequence of the BTEX-degrading bacterium Pseudoxanthomonas spadix BD-a59[END_REF]. One member of the genus Streptomyces (unknown species) dominated the bacterial community on the PVC hose, followed by Leifsonia antarctica, a bacterium isolated from a spade core sediment sample from the Antarctic Ocean (Pindi et al., 2009), Kofleria flava and Agromyces humatus. A. humatus was previously found on a wall of the Catacombs of Domitilla in Italy [START_REF] Jurado | Agromyces italicus sp. nov., Agromyces humatus sp. nov. and Agromyces lapidis sp. nov., isolated from Roman catacombs[END_REF].

Fungal outbreaks in show caves and treatment

Several outbreaks have been recorded in the literature, such as those in the Castañar and Lascaux caves (Bastian et al., 2009a(Bastian et al., , 2009b(Bastian et al., , 2009c;;[START_REF] Jurado | Fungal outbreak in a show cave[END_REF]. As already demonstrated, fungal outbreaks could have serious consequences on wall and painting preservation [START_REF] Pfendler | UV-C as a means to combat biofilm proliferation on prehistoric paintings: evidence from laboratory experiments[END_REF] and can lead to human pulmonary diseases (Pereira, 2011). To avoid potential uncontrolled and harmful proliferation, fungi should be eradicated as soon as possible and, if possible, by means of an environmentally friendly method [START_REF] Grobbelaar | Lithophytic algae: a major threat to the karst formation of show caves[END_REF][START_REF] Faimon | Environmentally acceptable effect of hydrogen peroxide on cave "lampflora", calcite speleothems and limestones[END_REF][START_REF] Mulec | Human impact on underground cultural and natural heritage sites, biological parameters of monitoring and remediation actions for insensitive surfaces: Case of Slovenian show caves[END_REF]. In the Saint-Marcel cave, fungi were removed manually, and then a chemical product (highly concentrated sodium hypochlorite) was applied. However, a few months later, the same outbreak was observed. The Saint-Marcel cave is a new example showing that the use of chemical compounds is unsuitable in show caves. Oenological activities contribute to increasing the carbon amount in the cave, necessarily leading to microbial proliferation. To protect the cave ecological balance, we suggest that oenological activities should be limited to wine testing and that wine vinification should be avoided as soon as possible. Further studies should be implemented to detect the presence of these wine-linked fungi and bacteria in the other parts of the 54-km-long Saint-Marcel cave.

Conclusions

This work has shown how human activities (oenology) have directly affected the Saint-Marcel cave microbiology. In fact, two types of microorganism communities were recorded. The first community consisted of unrelated wine cave bacteria and fungi, while the second community, which was dominant, was involved in wine vinification. Wine-related microorganisms were dominant and able to colonize all types of supports present in the cave (PVC, wood, limestone, and metal). This study has demonstrated that most of the recorded species are well known for their ability to use alcohol as a carbon source, for their involvement in wine fermentation or for their ability to degrade wood barrels. Therefore, a clear involvement of human activities in microorganism communities has been established.

Caves are mainly composed of carbonate rocks such as limestone, which over time undergoes significant deterioration phenomena via microorganism colonization. This deterioration may be amplified by numerous organisms from anthropogenic activities such as wine vinification.

Indeed, the darkening of the Saint-Marcel cave ceilings is an illustration of the consequences of human activities.

Acknowledgement

First, we are grateful to the curators of the Saint-Marcel cave and the mayor of Saint-Marcel village, who kindly gave us permission to access the cave and to carry out all our field experiments. We also thank the laboratory EVS-ISTHME for the financial contribution. We express our appreciation to the anonymous reviewers for helping to improve our paper. Below, wine barrels (B) were stored on wood supports. The PVC hose (C) was stored behind wine barrels. The limestone wall and roof next to the storage area were colonized by black mold (D). On wine bottles (E), green, orange and white fungi proliferated.

List of figures:

  D). Samples were collected on both wood and limestone supports. The results indicated that 25.6% of the OTUs matched with Crustoderma dryinum, 22.5% with Sordariomycetes class (undefined species), 18.2% with Kendrickiella phycomyces, 9.1% with Talaromyces rademirici and 3.7% with Penicillium spinulosum. Other OTUs were represented in a less extensive proportion. Actinobacteria (51.1%) and Proteobacteria (48.9%) were the only two phyla representing more than 1% of the OTUs. Promicromonospora sp. (Actinobacteria) and Pseudomonas sp. (Proteobacteria) represented 19.8% and 26.8%, respectively.

10

 10

Fig. 1 .

 1 Fig. 1. Map of Saint-Marcel show cave (Saint-Marcel, France).

Fig. 2 .

 2 Fig. 2. Illustration of the Saint-Marcel outbreak. (A) The tourist tour starts on the top of the stairwell.

Fig. 3 .

 3 Fig. 3. Shannon and Pielou indices for all types of colonized materials. Statistical analyses were carried out to compare limestone, metal, PVC and wood samples for both 16S and ITS primers. Significant differences are indicated using the letters a/a, b/b and c/c.

Fig. 4 .

 4 Fig. 4. Phylogenetic trees obtained with fungal metagenomic data.

Fig. 5 .

 5 Fig. 5. Principal component analysis (PCA) of fungal communities depending on the colonized substrate (PVC in red, wooden barrels and their supports in blue and purple, respectively, stairwell in green and limestone in orange).

Fig. 1 .

 1 Fig. 1. Map of Saint-Marcel show cave (Saint-Marcel, France).

Fig. 2 .

 2 Fig. 2. Illustration of Saint-Marcel outbreak. (A) Tourist tour starts on the top of the

Fig. 3 .

 3 Fig. 3. Shannon and Pielou indices are reported for all type of colonized materials.

Fig. 4 .

 4 Fig. 4. Phylogenetic trees obtained with fungal metagenomic data.

Fungal


L David
email: david@ensma.fr

F Cottet
email: cottet@ensma.fr

N Nissanke
email: nissanke@sbu.ac.uk

) Lisi-Ensma

) Scism

Jitter Control in On-line Scheduling of Dependent Real-Time Tasks

Keywords: Real-time, on-line scheduling, jitter, dependent periodic tasks

A typical characteristic of real-time systems is concurrent processing of tasks under strict timing requirements. These timing requirements may impose not only direct constraints, such as deadlines, but also indirect timing constraints in terms of inter-task dependencies. However, scheduling policies which can deal with some of these constraints effectively are limited, especially for the on-line context, and are not widely known within the real-time community. In this context, this paper presents a technique to control execution irregularities, namely, jitter. The technique is based on the modi£cation of task temporal parameters in the paradigm of the well known Deadline Monotonic (DM) and Earliest Deadline First (EDF) algorithms. The technique presents a way either to remove jitter completely (in the case of regularity constrained tasks) or to bound jitter releases. Moreover, the approach takes into account temporal dependencies of tasks on one another.

Introduction

A real-time system, controlling a physical device or a physical process, invariably performs two basic functions: sampling sensor readings and responding to different situations by sending control signals to actuators. With respect to process requirements, these tasks (sampling data systems, control systems, etc.) must often be periodic. However, * LISI -Laboratory of Applied Computer Science; ENSMA -National Engineering School in Mechanics and Aerotechnics.

† SCISM-SBU -School of Computing, Information Systems and Mathematics this is rarely the case in practice since periodicity cannot be achieved in an absolute sense. Indeed there are often timing requirements on the design in the form of permissible jitter [2] or timing tolerances. Basically, jitter arises due to the way algorithms, such as Rate Monotonic (RM), Deadline Monotonic (DM) and Earliest Deadline First (EDF) [19] algorithms, schedule multiple tasks for concurrent execution. These algorithms do not consider jitter requirements. Indeed, in the periodic task model of Liu and Layland [19], each instance of a task (an execution of a task within a given period) is considered completely independent from other instances. However, most real-time applications (e.g. multimedia data transmission [11], fault-tolerant systems, precision robotics [18], etc.) have regularity constraints on various tasks. Besides, jitter can arise due to different reasons at the implementation level, an example being the unpredictability in the actual timing of periodic events as generated by the RTOS [20]. However, this paper addresses only the jitter induced by scheduling at the application level.

Scheduling algorithms for controlling jitter are limited. An off-line scheduling technique based on simulated annealing methods due to Di Natale et al. [10] deals with end-to-end jitters in a distributed context. In this context, Coutinho et al. [8] propose a jitter minimization technique based on a genetic algorithm. Another off-line solution due to [6,7] consists of an exhaustive search of all valid sequences. Han and Lin [14] also suggest a distance constraint task system model (DCTS) in which execution regularity constraints are taken into account in some speci£c scheduling algorithms. In £xed priority scheduled systems, Bate et al.

[2] describe a task attribute handling mechanism which can deal with timing requirements, including jitter. Baruah et al. [1] propose an interesting technique for minimizing maximum jitter of a relatively small number of task in the EDF context, but without taking advantage of the pos-sibility to set offsets in order to reduce jitter and to handle systems of interdependent tasks. Based on a deadline assignment technique, Kim et al. [15] present a technique to reduce jitter in a set of independent tasks. In our work, we study in greater depth a) the issue of jitter control in the general on-line scheduling context, and b) con£gurations of interdependent tasks in the deadline based scheduling context, both in a uni-processor context.

Our discussion on jitter control proceeds as follows. Section 2 introduces different types of jitter. Section 3 introduces a set of task parameter handling tools to be used in Sections 4 and 5 in describing a complete jitter cancellation technique and a jitter bounding technique.

De£nitions of Jitter

Our work uses the periodic task model [19]. Each ith task is characterized by four parameters: r i,1 (the £rst request time or offset), C i (maximum execution time), D i (relative deadline) and T i (task period), each being, as appropriate, a non-negative or a positive integer; see Figure 1.

We consider two types of jitter: regularity jitter (execution irregularity within one task) and end-to-end jitter (response time irregularity, either within a set of two or more tasks forming an activity or within the same task in a repetitive sense). Both the above types of jitter can be de£ned over a scheduling period, or a major cycle (H)a reference pattern used for scheduling simulation. Authors of [13] generalize the results of [17] such that in every case H is bounded by max i (r i,1 ) + 2LCM i (T i ). A common approach to jitter de£nition is to use the maximum duration between successive activation times and completion times [1,5]. It is not unusual, however, to come across sequences of task instances where the intervals between successive completion times are more or less identical, resulting in a less accurate estimate of jitter. An advantage of using H is that in de£ning jitter it allows the use of statistical concepts, such as the mean, covering a range of completion times spread over H.

Regularity Jitter

Let s i,k and e i,k be, respectively, the k th execution start date and the k th execution end date of task τ i ; see Fig-ures 1 and 2. The length of time between two successive start dates of task τ i within the k th scheduling period is denoted by ∆s i,k , i.e. ∆s i,k = s i,k+1s i,k . Analogously, ∆e i,k = e i,k+1e i,k denotes the length of time between two successive end dates. Both ∆s i,k and ∆e i,k vary from 0 to 2T i , the two extremities corresponding to negligibly small execution times. Let us also introduce

j s i,k = |∆s i,k -T i | T i 100 % (1)
as a percentage relative measure of the execution start date irregularity between the k th and the (k + 1) th instances. Note that j s i,k = 0 % when the difference s i,k equals T i (i.e. the case of regular tasks) and j s i,k = 100 % when it equals 0 or 2T i (i.e. the case of maximum irregularity in execution). Analogous expressions apply for e i,k . Let us now introduce the de£nition:

DEFINITION 1 : Given a task τ i with characteristics (r i,1 , C i , D i , T i ), the mean regularity jitter of τ i is de£ned by: J M ean (τ i ) = 1 Ni Ni k=1 j s i,k
, N i being the number of instances of task τ i during H, and s i,k and j s i,k being as de£ned above. See Figure 2 for an illustration of the above for N i = 4.

Similarly, other statistics can be de£ned on jitter based on j s i,k , for example, the maximum jitter, the minimum jitter, etc. Note that if preemption is not permitted then regularity jitter based on s i,k or e i,k will be identical. Otherwise, they are linked through the cohesion jitter -a topic to be introduced in the next section.

End-to-End Jitter

This subsection de£nes end-to-end jitter for an activity such as a control activity. An activity may consist of just one periodic task or, alternatively, of several periodic tasks. In the former case, the end-to-end jitter measures the cohesion jitter and, in the latter, the response time irregularities. Thus, the end-to-end jitter is the irregularity in the elapsed time between the execution start date of one instance of a task and the execution end date of another instance of a task, with the two task instances not necessarily belonging to the same task. The corresponding response times are denoted by RT k (a), a being a given activity and k being an index ranging over the instances of a over a given scheduling interval.

Let a be an activity consisting of, for example, two tasks τ i and τ j , with outputs of τ i serving as inputs for τ j . In this case, a is a pair τ i , τ j . Note that τ i and τ j may not necessarily have the same rate [2], except when they are dependent. In Figure 3-a, τ i and τ j have two different rates and, in order to be more up-to-date when executing τ j , we choose the most recent instance of τ i for the last value RT 3 (a). What is of interest then is the elapsed time, within a given scheduling period, between the most recent execution start date of an instance of τ i and the execution end date of its succeeding instance of τ j ; see RT k In de£ning end-to-end jitter, it is necessary to compare RT k values de£ned above against a mean value, which could be computed either from RT k values themselves or, alternatively, using the data collected by monitoring the automation, for example, using a £tted response time curve which makes the system stable. Let us denote whatever the chosen value by RT . The end-to-end jitter can then be considered in terms of the difference:

∆ k = |RTk-RT |
RT 100 %. The latter is similar to (1) and leads to the following de£nition:

DEFINITION 2: Given the response times RT k (a) and RT k (τ i ) as introduced above, the mean end-toend jitter is de£ned as a percentage by: J M ean (a) =

Approach to Controlling Regularity Jitter

Let R and N R be two sets of periodic tasks with n R and n N R elements respectively and let their union characterize a real-time task con£guration. The tasks τ R in the £rst set are required to be regular in term of execution, whereas the tasks τ N R in the second set are not subject to such a requirement. Thus, the distinction between the two task sets is based on whether or not the periodicity is to be observed strictly. As was mentioned earlier, task execution irregularities arise due to the way scheduling algorithms work and do not affect other constraints such as deadlines. Task regularity constraints may be required in the case of sampling tasks and control tasks.

Execution windows of a task τ i correspond to intervals of the form [|r i,j ; e i,j |](j ∈ N * ). We assume that the periods are not alterable, since they usually come from process requirements. We also assume that the worst case execution characteristics of each task is known and £xed, and that rede£nition of release dates r i,1 would not lead to rede£nition of any relative deadlines (D i ) (offset free systems [12]). Obviously, even where it is permitted, any rede£nition of D i must result in a smaller value than its original value.

General scheme

The jitter control technique presented here is based on the idea that if two regular tasks have a non empty intersection of their execution windows, then one of them will be exposed to regularity or cohesion jitter. Let us illustrate this idea with an example involving a con£guration of three tasks (τ 1 , τ 2 , τ 3 ), which are to be scheduled with external priority (P rio i ); see table 1. Figure 4 shows the scheduling sequence where it can be noted that τ 2 is preempted by τ 1 , and τ 3 is preempted by both τ 1 and τ 2 . Equivalently, the intersection of task execution windows are effectively not empty, resulting in jitter on τ 2 and τ 3 . An interesting solution would be to cancel jitter by desynchronizing the release dates. Indeed, the triplet (r 1,1 , r 2,1 , r 3,1 ) = (1, 0, 6) results in an empty intersection of execution windows, eliminating the jitter completely; see Figure 5. Our technique is a generalization of the above idea and consists basically of adjusting execution windows of regular tasks through rede£nition of release dates and relative deadlines, but always maintaining the required interrelationships between tasks. Thus, the approach to jitter cancellation and jitter bounding can be summarized in four steps:

Step 1: release date desynchronization,

Step 2: maintenance of the precedence relation,

Step 3: restriction of execution windows to a certain bound,

Step 4: veri£cation of schedulability through tests. This above strategy can be accomplished with two different effects: either by completely eliminating regularity jitter (i.e. by forbidding preemption of R tasks by any N R task) or by bounding regularity jitter (i.e. by permitting preemption to a certain extent). This relies on three separate tools. The £rst tool searches for release dates for regular tasks so that each one of the tasks completes after a certain amount of time following its activation without causing an execution overlap. The second tool veri£es the maintenance of the precedence constraints on tasks. The third tool performs the rede£nition of relative deadlines in order to achieve the required task priorities.

Release date desynchronization

Let {τ 1 , ..., τ n } be a set of task to be desynchronized. For every task τ i , we de£ne a time value W i , W i ∈ N * and 0 < C i ≤ W i ≤ D i , such that by W i the execution of the corresponding instance of τ i is fully completed; see Figure 6. The problem of desynchronization of execution windows [9] consists then of a constraint satisfaction problem, namely, of £nding a solution (r 1,1 , . . . , r n,1 ) satisfying the inequalities:

(∀ i, j ∈ 1 • • • n; i < j) r i,1 -r j,1 = 0 mod (T i ∧ T j )      r i,1 -r j,1 = 1 mod (T i ∧ T j ) r i,1 -r j,1 = 2 mod (T i ∧ T j ) . . . . . . r i,1 -r j,1 = (W j -1) mod (T i ∧ T j )      and      r j,1 -r i,1 = 1 mod (T i ∧ T j ) r j,1 -r i,1 = 2 mod (T i ∧ T j ) . . . . . . r j,1 -r i,1 = (W i -1) mod (T i ∧ T j )      (2)
where ∧ denotes the greatest common divisor (GCD) of its operands, and mod the modulo symbol. These inequalities follow from the Generalized Chinese Remainder Theorem [12,16]. This is illustrated in the £gure 7, where r i,k (k ∈ N * ) is £xed and r j,k is to be de£ned at a location such that it would cause no overlap with other jobs from R tasks. A necessary condition for a solution to (2) is that the periods are NOT pairwise relatively prime. Let us attempt a proof of this claim by contradiction, assuming its negation and showing that this would make the £rst inequality inconsistent:

proof: Suppose that:

(∀ i, j ∈ 1 • • • n; i < j)(∃ r i,1 , r j,1 ∈ N * ) r i,1 -r j,1 = 0 mod (T i ∧T j )
with periods pairwise relatively prime. For p, q and m in N * , the de£-nition of congruence is given by p = q mod(m) ⇔ (∃ k ∈ Z * ) pq = k • m. In others words, p = q mod(m) ⇔ (∀ k ∈ Z * ) pq = k • m. In the £rst inequality of (2), pairs such as r i,1 , r j,1 are supposed to be known. Let d ij denote the difference r i,1r j,1 . It is necessarily the case that d ij is in Z * . The fact that r i,1r j,1 = d ij ensures the existence of k in Z * , such that r i,1r j,1 = k • 1. Hence, r i,1 = r j,1 mod(1) is false, leading to a contradiction. As a consequence we conclude that our original assumption is false, resulting in the following condition: periods T i and T j must not be pairwise relatively prime.

If it is possible to £nd (r 1,1 , ..., r n,1 ) subject to above conditions, and if the execution window of every task τ i (1 ≤ i ≤ n) is equal to W i , then the execution windows are guaranteed not to overlap. For the task con£guration of Figure 5, the above conditions are satis£ed for W 1 = 3, W 2 = 1 and W 3 = 2. In this case, for i = 1 and j = 2 the inequalities (2) take the form:

r 1,1 -r 2,1 = 0 mod (4) and r 2,1 -r 1,1 = 1 mod (4) r 2,1 -r 1,1 = 2 mod (4) (3)
Solving the problem stated in (2) can be quite complex, more so as n increases. Any precise analytical technique is likely to be of limited value and restricted to a particular set of conditions. Therefore, generally numerical techniques [9] are to be preferred. Though it is exponential, the problem complexity is not a critical factor in real time applications with a relatively small number of regular tasks, and with a relatively narrow time interval (W i ). Indeed, the regular tasks involved in this problem are mostly input-output tasks, usually with a maximum execution time (C i ) much smaller than the period (T i ) and with a choice of W i parameter close to C i in order to reduce jitter. As with other task parameters, r i,1 s are assumed to be non-negative integers [12]. Characteristics of applications dealt with by the authors comply with these assumptions.

Precedence Relation

One of the important constraints on an activity is the right execution order. Generally, tasks involved in an activity are dependent on one another and have the same period T , which also happens to be the activity period. In this work we rely on this as an assumption, and choose conditions that impose minimal restrictions on task temporal attributes. According to [4], in order to ensure precedence of τ i over τ j , it is necessary to impose that r i,1 ≤ r j,1 P rio i > P rio j or r i,1 < r j,1 P rio i ≥ P rio j .

Obviously, these conditions depend on the choice of the scheduling algorithm. For example, in DM the priority ordering P rio i > P rio j corresponds to D i < D j .

Priority Rede£nition

Let us examine here how to rede£ne relative deadlines so that tasks in R will always enjoy higher priorities compared to those in N R. Again, this would depend on the chosen scheduling algorithm. In DM, where tasks with the shorter deadlines will have higher priorities, the condition that needs to be veri£ed is

(∀τ i ∈ R) C i ≤ D * i ≤ min τj ∈N R (D i ; D j -1), (5)
where D * i denotes the new relative deadline to be considered for task τ i . In EDF, priorities are dynamic and, therefore, it is dif£cult to foresee the actual runtime priorities of tasks. However, there is a condition which enables the imposition of the required priority a priori, namely

(∀τ i ∈ R) D * i = C i , (6)
according to which every task τ i will have the highest priority whenever it requires, and acquires, the processor.

Elimination of Regularity Jitter

This section examines £rst the results obtained for independent task con£gurations and then, using an illustrative example, the case of dependent task con£gurations.

The Case of Independent Tasks

As the authors of [10] underline, controlling jitter is quite a complex problem in the presence of task preemptions. Thus, our approach is to ensure that no regular task is ever preempted, thus achieving the kind of scheduling sequence illustrated in Figure 8. Let us study the approach using an example [9]. Consider the task con£guration with characteristics given in Table 2 and with two of them τ Acq1 , τ Acq2 having an execution regularity constraint. Scheduling using DM, as well as EDF, leads to a sequence with non-negligible jitter on regular tasks (see table 2). Now let us modify the task temporal attributes. STEP 1: Apply the desynchronization scheme described in Section 3.2 on both regular tasks with W i = C i . According to an enumeration solution technique, we obtain a set of 377 pairs £tting this requirement. For example, one solution is the pair (r Acq1,1 , r Acq2,1 ) = (0, 2). STEP 3: To guaranty execution of regular tasks in R with no preemption, it is necessary to make tasks in R have

Figure 1 .

 1 Figure 1. Task model.

Figure 2 .

 2 Figure 2. Regularity jitter.

  (a) for 1 ≤ k ≤ 3 in Figure 3-a. On the other hand, with respect to cohesion jitter, what is of interest is the elapsed time between the start and end dates of execution of a given task instance; see RT k (τ i ) for 1 ≤ k ≤ 4 in Figure 3-b.

Figure 3 .

 3 Figure 3. (a) : End-to-end jitter for an activity (a =< τ i , τ j >) -(b) : cohesion jitter for a task.

  a being the the number of instances of the activity a. Analogously, the mean cohesion jitter as a percentage is de£ned byJ M ean,c (τ i ) = 1 Ni Ni k=1 |RT k (τi)-Ci| Ci100%, N i being the number of instances of the task τ i executed during H. The above are illustrated in Figures3-a and 3-b for N a = 3 and N i = 4. Our focus in Section 3 and 4 is on regularity jitter.

  L. David, F. Cottet and N. Nissanke. Jitter Control in On-Line Scheduling of Dependent Real-Time Tasks. Proc. of the 22 nd Real-Time Systems Symposium, pages 49-58, RTSS'01, December 2001, London, UK.

Figure 4 .

 4 Figure 4. τ 2 preemption by τ 1 , τ 3 preemption by τ 1 and τ 2 : jitter on τ 2 and τ 3 .

Figure 5 .

 5 Figure 5. Scheduling sequence with no jitter.

Figure 6 .

 6 Figure 6. The W i parameter used in task desynchronization.

Figure 7 .

 7 Figure 7. Illustrative diagram for task desynchonisation.

  L. David, F. Cottet and N. Nissanke. Jitter Control in On-Line Scheduling of Dependent Real-Time Tasks. Proc. of the 22 nd Real-Time Systems Symposium, pages 49-58, RTSS'01, December 2001, London, UK.

Table 1 . Example: Task characteristics.

 1

		ri,1 Ci Di Ti P rioi
	τ1	0	3	16 16	3
	τ2	0	1	4	4	2
	τ3	0	2	8	8	1

L. David, F. Cottet and N. Nissanke. Jitter Control in On-Line Scheduling of Dependent Real-Time Tasks. Proc. of the 22 nd Real-Time Systems Symposium, pages 49-58, RTSS'01, December 2001, London, UK.