James Carey

James C Fettinger

Rinaldo Poli
email: rinaldo.poli@u-bourgogne.fr

Kevin M Smith

Synthesis and characterization of [Mo(m-EPh)(CO) 3 (CH 3 CN)] 2 (E= Se, Te), including the X-ray structure of the tellurium derivative

Keywords: Crystal structures, Molybdenum complexes, Tellurium complexes

The reaction of Mo(CO) 3 (MeCN) 3 and E 2 Ph 2 (E= Se, Te) yields the edge-sharing bioctahedral, metal metal bonded Mo(I) products [Mo(CO) 3 (MeCN)(m-EPh)] 2 . The structure of the tellurolato derivative was confirmed by X-ray crystallography: triclinic, space group P1 ( , a=7.3149(17), b=9.6959(16), c=9.7090(10) A , , h=80.366(10), i =76.563(13), k = 72.877(16)°, V = 636.43(19) A , 3 , D calc =2.222 Mg m -3 , v= 3.271 mm -1 , R 1 =0.0418, wR 2 = 0.0689 for 163 parameters and 2238 data with I\ 2|(I). The interaction of these compounds with excess E 2 Ph 2 as a possible entry to homoleptic Mo(EPh) 3 has been investigated.

Introduction

The reaction of carbonyl compounds with reagents containing a single E E bond between elements of Groups 17 (halogens), 16 (chalcogens) and 15 (pnictogens) presents an interesting dichotomy between two fundamental reaction pathways in organometallic chemistry, namely coordinative addition (Eq. ( 1)) or oxidative addition (Eq. ( 2)). The outcome of the reaction is dictated by the oxidative power of E E and by the susceptibility of the carbonyl compound to oxidation [1].

L n M + E EL n -1 M(h 1 -E E) or L n -1 M(m:h 1 ,h 1 -E E)ML n -1 (1)
L n M + E EL n -1 M(E) 2 or [L n -2 M(m-E)] 2 (2)
For instance, while S 2 Me 2 oxidatively adds to [Cp-Mo(CO) 3 ] 2 to afford [CpMo(m-SMe) 2 ] 2 [2], compounds E 2 Ph 2 (E=S, Se, Te) only coordinatively add to MnX(CO) 5 and ReX(CO) 3 (THF) 2 (X=Br, I), to afford [M(m-X)(m-E 2 Ph 2 )(CO) 3 ] 2 (M= Mn or Re, respectively) [3,4]. The stronger oxidant I 2 , on the other hand, is able to oxidize the same Re(I) starting material to ReI 3 -(CO) 3 or to mixed-valence Re(I) Re(III) or Re(I) Re(IV) products [5,6].

The addition of I 2 to Mo(CO) 6 generates MoI 3 and represents a clean method for the formation of anhydrous Mo(III) iodide [7]. Homoleptic alkyl-and arylsulfido Mo(III) materials have also been obtained by thermal interaction of S 2 R 2 and Mo(CO) 6 under forcing conditions [8,9]. It would be interesting to establish whether an analogous approach could lead to homoleptic alkylselenides and tellurides, which are a relatively unexplored class of compounds [10] with potential use as precursors to semiconducting metal selenides and tellurides. The reaction between Mo(CO) 6 and the heavier dichalcogenide Te 2 Ph 2 has been studied by two different groups under different conditions (in refluxing toluene, or upon UV irradiation in refluxing THF) [11,12]. In both cases, a Mo(I) complex, [Mo(m-TePh)(CO) 4 ] 2 , was isolated and structurally characterized. Since the elimination of the tightly bonded CO ligand is a difficult process for low-valent molybdenum, a more promising route is the use of partially substituted Mo(0) carbonyl derivatives, such as (h 6 -C 6 H 5 CH 3 )Mo(CO) 3 or Mo(CO) 3 (MeCN) 3 . The room temperature (r.t.) reaction of Mo(CO) 3 (MeCN) 3 and S 2 Ph 2 in MeCN affords a Mo(I) product, [Mo(m-SPh)(CO) 3 (MeCN)] 2 , whose X-ray structure has been determined [13]. We have investigated the same reactions with the heavier dichalcogenides Se 2 Ph 2 and Te 2 Ph 2 and report here the results of these studies.

Experimental

All operations were carried in a protective atmosphere of dinitrogen by using standard Schlenk-line and glove box techniques. Solvents were dried by conventional methods (THF over Na/K; heptane over Na; MeCN over type 4 A , molecular sieves (Fischer) and then reflux over CaH 2 ) before being distilled. Solution IR spectra were taken on a Perkin -Elmer 1600 series FT spectrophotometer with KBr optics. Elemental analyses were by Atlantic Microlab, Inc., Norcross, GA. (h 6 -C 6 H 5 CH 3 )Mo(CO) 3 was prepared according to the literature method [14]. Ph 2 Te 2 and Ph 2 Se 2 (Aldrich) were used as received. The compound (h 6 -C 6 H 5 CH 3 )Mo(CO) 3 (651 mg, 2.39 mmol) was placed in a Schlenk flask equipped with a magnetic stirrer bar. CH 3 CN (50 ml) was added with stirring. A clear yellow solution immediately formed. An IR spectrum showed CO stretching bands at 1920 and 1797 cm -1 , which were assigned to Mo(CO) 3 -(MeCN) 3 by comparison with the literature [15]. To this solution was added Ph 2 Te 2 (980 mg, 2.39 mmol), inducing an instant color change to dark red. An IR spectrum of the resulting solution recorded immediately showed the prominence of the bands of the starting material and new bands, which can be assigned to the final product. The reaction was allowed to continue for 24 h at r.t., resulting in the formation of a dark green microcrystalline solid. The precipitate was isolated by filtration, washed twice with 5 ml portions of heptane, and dried in vacuo (10 -2 mmHg) for 1 h. Yield 317 mg (30.1%). Anal. Calc.: C, 31.03; H, 1.89; N, 3.29. Found: C, 29.68; H, 1.82; N, 3.06%. IR (cm -1 , CH 3 CN): 1961 (s), 1926 (w), 1873 (m). X-ray quality crystals were grown by recrystallizing 61.8 mg of the product from 50 ml of hot MeCN. The compound (h 6 -C 6 H 5 CH 3 )Mo(CO) 3 (889 mg, 3.27 mmol) was placed in a Schlenk flask equipped with a magnetic stirrer bar. CH 3 CN (40 ml) was added with stirring. A clear yellow solution immediately formed. To this solution was added Ph 2 Se 2 (1.019 g, 3.27 mmol), inducing an instant color change to dark red. The reaction was allowed to continue for 24 h at r.t., resulting in the formation of a dark green microcrystalline solid. The mixture was cooled to -20°C for an additional 24 h, then filtered. The precipitate was washed with heptane and dried in vacuo (10

Preparation of Mo

In a 1:1 ratio

The compound Mo 2 (SeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2 (135 mg, 0.18 mmol) was placed in a Schlenk flask equipped with a magnetic stirrer bar. Toluene (40 ml) was added with stirring, giving a green solution. To this solution was added Ph 2 Se 2 (57 mg, 0.18 mmol), inducing a color change to green-brown. After 90 min at r.t., the reaction was heated to reflux for 1 h, resulting in the formation of a dark brown precipitate. The mixture was cooled to r.t., then filtered. The precipitate was washed with toluene (4×5 ml) and dried in vacuo (10 -2 mmHg) for 1 h. Yield 143 mg (80%). The IR spectrum (Nujol mull) of this product was identical to that obtained from the reaction of Mo 2 (SeC 6 H 5 ) 2 -(CO) 6 (CH 3 CN) 2 with 2 equiv. of Ph 2 Se 2 .

2.6. X-ray crystallography for the compound Mo 2 (TeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2 A dark green plate with dimensions 0.250× 0.125× 0.013 mm was placed on the Enraf -Nonius CAD-4 diffractometer. The crystal final cell parameters and orientation matrix were determined from 25 reflections in the range 8.9B q B17.7°and confirmed with axial photographs. Relevant crystal and data collection parameters are listed in Table 1. All data (9 h 9 k 9 l) were collected, resulting in the measurement of 4473 reflections, of which 2238 were unique [R int =0.0468]. Three periodically monitored standard reflections re- vealed minor (B 3%) variations in intensity; the data were not corrected for decay. Data were corrected for Lorentz and polarization factors and for absorption based upon crystal faces with transmission factors ranging from 0.7098 to 0.9599. Intensity statistics clearly favored the centrosymmetric case. The structure was determined by direct methods with the successful location of a majority of the non-hydrogen atoms. The remaining non-hydrogen atoms were found from a series of difference-Fourier maps. The structure was refined to convergence [Z/|5 0.001] by full-matrix least-squares cycles in SHELXTL [START_REF] Sheldrick | Nicolet[END_REF]. Hydrogen atoms were placed in calculated positions and refined by the riding method with unconstrained isotropic thermal parameters. All non-hydrogen atoms were refined anisotropically. The final difference-Fourier map was featureless, indicating that the structure is both correct and complete. Selected bond distances and angles are listed in Table 2.

Results and discussion

The reaction between Mo(CO) 3 (MeCN) 3 (generated in situ from (h 6 -C 6 H 5 CH 3 )Mo(CO) 3 in the MeCN solvent) and E 2 Ph 2 (E=Se, Te) affords the corresponding metal metal bonded dinuclear complexes [Mo(CO) 3 -(MeCN)(m-EPh)] 2 (see Eq. ( 3)) by analogy with the previously reported formation of the phenylthiolato analog [13]. does not react with excess Te 2 Ph 2 upon prolonged reflux in MeCN. The oxidizing properties of the E 2 Ph 2 ligands should follow the order TeB SeB S. Thus, the reaction of the selenolato derivative was investigated in greater detail. No interaction between [Mo(CO) 3 -(MeCN)(m-SePh)] 2 and excess Se 2 Ph 2 occurs at r.t., but reflux in toluene with 1 equiv. of Se 2 Ph 2 afforded a new compound. The solid state IR spectrum of this product shows the presence of CO ligands and the N elemental analysis shows that the MeCN ligand has been partially retained. The most consistent formulation is Mo 2 (SePh) 4 (CO) 5 (MeCN). The blue-shift of the CO stretching vibrations relative to the starting Mo(I) complex indicates that oxidation has occurred. Therefore, the product is more likely a Mo 2 (SePh) 4 derivative of Mo(II) than a Mo 2 (SePh) 2 (Se 2 Ph 2 ) derivative of Mo(I). Unfortunately, a more complete characterization of this product was prevented by its sparing solubility in all common solvents. When 2 equiv. of Se 2 Ph 2 per Mo(I) dimer were employed, the same product was obtained, indicating that the oxidation state III is not attainable via this route. It can be concluded that this synthetic strategy is not a viable one as an entry to the hitherto unknown Mo(EPh) 3 (E=Se, Te) derivatives.

2Mo(CO) 3 (MeCN) 3 +E 2 Ph 2 [Mo(CO) 3 (MeCN)(m-EPh)] 2 +4MeCN (3)
These reactions are therefore new examples of oxidative additions of reagents containing a single E E bond, i.e. reactions of type (2). No evidence for the formation of a coordinative addition intermediate (Eq. ( 1)) is shown by IR monitoring. The products exhibit a pattern of CO stretching bands in the IR spectrum similar to that previously reported for the sulfido analog [13], a redshift being observed on going from S to Se to Te as expected.

The tellurolato derivative was characterized by X-ray crystallography. The molecule sits on an inversion center (see Fig. 1) and can be described as an edge-shared bioctahedron. The geometry is identical in all respects with that of the sulfido analog, [Mo(CO) 3 (MeCN)(m-SPh)] 2 [13]. The distance between the two metals is 3.1288(13) A , . By comparison, the Mo Mo separation is 2.982(1) A , in the sulfido analog [13] and 3.116(1) A , in [Mo(CO) 4 (m-TePh)] 2 [11,12]. Thus, the substitution of a CO ligand with MeCN results in a slight lengthening of the Mo Mo distance. Although this distance is rather long due to the size of the bridging groups, the presence of a metal metal bonding interaction is clearly shown by the acute Mo(1) Te(1) Mo(1A) angle [69.55(3)°]. This is similar to the value observed in the compound [Mo(CO) 4 (m-TePh)] 2 [68.8(1)°]. It is well established that the absence of metal metal bonding in edge-shared bioctahedral compounds results in M (m-X) M angles greater than 90° [START_REF] Cotton | [END_REF].

An attempt to further oxidize these materials has only met with limited success. The tellurolato derivative

Fig. 1 .

 1 Fig. 1. An ORTEP view of the molecular geometry for the compound Mo 2 (TeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2 . Ellipsoids are drawn at the 30% probability level.

  2 (TeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2

  2.2. Attempted reaction between Mo 2 (TeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2 and Te 2 Ph 2 Compounds Mo 2 (TeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2 (100 mg, 0.225 mmol) and Te 2 Ph 2 (100 mg, 0.244 mmol) were mixed together in CH 3 CN (80 ml), giving a red solution with a green precipitate. The mixture was refluxed for 10 h, with no apparent change. 2.3. Preparation of Mo 2 (SeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2

  Reaction between Mo 2 (SeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2 and Se 2 Ph 2 2.4.1. In a 1:2 ratioThe compound Mo 2 (SeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2 (48 mg, 0.064 mmol) was placed in a Schlenk flask equipped with a magnetic stirrer bar. Toluene (20 ml) was added with stirring, giving a green solution. To this solution was added Ph 2 Se 2 (38 mg, 0.123 mmol), inducing a color change to green-brown. After 1 h at r.t., no new IR bands were observed in the CO stretching region. The reaction was heated to reflux for 1 h, resulting in the formation of a dark brown precipitate. The mixture was cooled to r.t., then filtered. The precipitate was washed with toluene (5 ml) and dried in vacuo (10 -2 mmHg) for 30 min. Yield 47 mg (74%). Anal. Calc. for C 31 H 23 Mo 2 NO 5 Se 4 [Mo 2 (SePh) 4 (CO) 5 -

	-2 mmHg)
	for 1 h. Yield 403 mg (32.7%). Anal. Calc.: C, 35.04; H,
	2.14; N, 3.71. Found: C, 34.72; H, 2.08; N, 3.57%. IR
	(cm -1 , CH 3 CN): 1967 (s), 1932 (m), 1873 (m), 1830
	(w). IR (cm -1 , Nujol mull): 1980 (s), 1940 (vs), 1891
	(s), 1861 (vs).
	2.4. (MeCN)]: C, 37.34; H, 2.32; N, 1.40. Found: C, 37.84;
	H, 2.58; N, 1.01%. IR (cm -1 , Nujol mull): 2012 (s),
	1959 (vs), 1937 (vs), 1878 (s).

Table 2

 2 Selected bond distances (A , ) and angles (°) for Mo 2 (TeC 6 H 5 ) 2 -(CO) 6 (CH 3 CN) 2

	Bond distances
	Mo(1) Mo(1A)	3.1288(13) Mo(1) C(3)	1.988(7)
	Mo(1) Te(1)	2.7447(9)	Te(1) C(11)	2.153(6)
	Mo(1) Te(1A)	2.7409(9)	N(1) C(4)	1.148(9)
	Mo(1) N(1)	2.200(6)	C(1) O(1)	1.159(8)
	Mo(1) C(1)	1.949(7) C(2) O(2)	1.144(8)
	Mo(1) C(2)	1.999(8) C(3) O(3)	1.164(8)
	Bond angles
	Mo(1A) Mo(1) Te(1)	55.17(2)	N(1) Mo(1) C(1)	175.9(3)
	Mo(1A) Mo(1) Te(1A)	55.28(2)	N(1) Mo(1) C(2)	98.8(3)
	Mo(1A) Mo(1) N(1)	85.36(16) N(1) Mo(1) C(3)	88.5(3)
	Mo(1A) Mo(1) C(1)	92.8(2)	C(1) Mo(1) C(2)	85.0(3)
	Mo(1A) Mo(1) C(2)	138.67(19) C(1) Mo(1) C(3)	90.4(3)
	Mo(1A) Mo(1) C(3)	137.6(2)	C(2) Mo(1) C(3)	83.7(3)
	Te(1) Mo(1) Te(1A)	110.45(3) Mo(1) Te(1) Mo(1A) 69.55(3)
	Te(1) Mo(1) N(1)	89.11(16) Mo(1) Te(1) C(11)	104.88(19)
	Te(1) Mo(1) C(1)	86.8(2)	Mo(1A) Te(1) C(11) 107.32(19)
	Te(1) Mo(1) C(2)	164.2(2) Mo(1) N(1) C(4)	169.6(6)
	Te(1) Mo(1) C(3)	82.9(2)	Mo(1) C(1) O(1)	177.6(6)
	Te(1A) Mo(1) N(1)	85.59(15)	Mo(1) C(2) O(2)	174.3(7)
	Te(1A) Mo(1) C(1)	96.4(2) Mo(1) C(3) O(3)	176.4(6)
	Te(1A) Mo(1) C(2)	83.9(2)	N(1) C(4) C(5)	176.9(8)
	Te(1A) Mo(1) C(3)	165.3(2)

Table 1

 1 Crystal data for the compound Mo 2 (TeC 6 H 5 ) 2 (CO) 6 (CH 3 CN) 2

	Formula weight	851.45
	Temperature (K)	153(2)
	Wavelength (A , )	0.71073
	Crystal system	triclinic
	Space group	P1(
	Unit cell dimensions
	a (A , )	7.3149(17)
	b (A , )	9.6959(16)
	c (A , )	9.7090(10)
	h (°)	80.366(10)
	i (°)	76.563(13)
	k (°)	72.877(16)
	V (A , 3 )	636.43(19)
	Z	1
	D calc (Mg m -3 )	2.222
	Absorption coefficient (mm -1 )	3.271
	F(000)	398
	Crystal size (mm 3 )	0.2500×0.1250×0.0125
	q Range for data collection (°)	2.93-24.97
	Index ranges	-85h58, -115k511,
		-115l511
	Reflections collected	4473
	Independent reflections	2238 [R int = 0.0468]
	Completeness to q = 24.97°(%)	99.9
	Absorption correction	integration
	Max/min transmission	0.9599, 0.7098
	Refinement method	full-matrix least-squares on F 2
	Data/restraints/parameters	2238/0/163
	Goodness-of-fit on F 2	1.126
	Final R indices [I\2|(I)]	R 1 = 0.0418, wR 2 = 0.0689
		[1719 data]
	R indices (all data)	R 1 = 0.0676, wR 2 = 0.0747
	Largest difference peak and hole	1.332 and -1.253
	(e A , -3 )

Acknowledgements

We are grateful to the National Science Foundation (grant CHE-9508521) for support of this work.

Supplementary material

The crystallographic data have been deposited with the Cambridge Crystallographic Data Centre (CCDC No. 132771) and may be obtained free of charge on application to The Director, CCDC, 12 Union Road, Cambridge, CB2 1EZ, UK (fax: + 44-1223-336033; e-mail: deposit@ccdc.cam.ac.uk or www: http://www. ccdc.cam.ac.uk).


Antonio Mancina
email: a.mancina@sssup.it

Giuseppe Lipari
email: lipari@sssup.it

Jorrit N Herder
email: jnherder@cs.vu.nl

Ben Gras
email: beng@cs.vu.nl

Andrew S Tanenbaum

Enhancing a Dependable Multiserver Operating System with Temporal Protection via Resource Reservations

MINIX 3 is a microkernel-based, multiserver operating system for uniprocessors that is designed to be highly dependable. Servers are restricted according to the principle of least privilege. For example, access to resources such as system memory and device I/O is fully protected. Although MINIX 3 is a potential candidate for embedded platforms, it currently cannot safeguard processes with stringent timing requirements, such as real-time applications.

In this paper, we present the design and the implementation of a user-space resource-reservation framework (RRES) in order to augment MINIX 3's dependability infrastructure with temporal protection. In particular, we implemented the Constant Bandwidth Server (CBS), either in Soft or in Hard Reservation (CBS-HR) mode and the Idle-time Reclaiming Improved Server (IRIS) resource reservation algorithms. Important, practical applications of temporal protection include real-time computing as well as prevention of certain denial of service (DoS) attacks that monopolize the CPU. Experiments on a prototype implementation showed improved dependability in the temporal domain.

INTRODUCTION

Modern computer users are increasingly concerned about system dependability. While end-user requirements used to represent a trade-off between performance and costs, developers nowadays have to meet the demand for hard safety guarantees. This includes security and privacy, robustness against failures, timeliness of operation, quality of service, and so on. The dependability axis we explore in this work concerns the temporal domain. One particularly important problem in this domain is how to prevent applications from using excessive CPU time, thereby disrupting timeliness of operation and degrading quality of service.

A recent study [START_REF] Tsafrir | Secretly Monopolizing the CPU Without Superuser Privileges[END_REF] showed that common process scheduling mechanisms can be subverted in a practical manner without superuser privileges in order to monopolize the CPU. This is a threat to not only timesharing systems, but also embedded systems such as cell phones, PDAs, etc. The cheating process effectively gains the maximum priority, performing a denial of service (DoS) attack on other tasks. It was shown that almost all current operating systems, including MINIX 3 according to our analysis, are affected by this problem.

Furthermore, timeliness of operation is important in many application domains, including multimedia, VOIP, peer-topeer services, interactive computer games and so on. Each of these domains has its own peculiarities, but all of them share an equal need of a minimum guaranteed service level. A best-effort service based on heuristic algorithms is usually adopted in order to improve the end-user perception of the overall quality, but this approach fails to provide minimum service guarantees. For example, in an attempt to keep the highest possible throughput, the performance of certain critical services may be heavily degraded under high-load conditions, which may lead to a low quality of service as perceived by the end user.

In order to improve the every-day user experience for such time-sensitive applications, a real-time operating system (RTOS) adapts the computational resources granted to each application based on its quality-of-service requirements. To date much development has focused on adding real-time features to commodity, monolithic, PC operating systems, such as Linux [START_REF] Abeni | Integrating multimedia applications in hard real-time systems[END_REF][START_REF] Kaneko | Integrated scheduling of multimedia and hard real-time tasks[END_REF][START_REF] Rajkumar | Resource Kernels: A Resource-Centric Approach to Real-Time and Multimedia Systems[END_REF]. In contrast, the work in this paper provides real-time support on MINIX 3, a novel microkernel-based, multiserver operating system. This focus allowed for a highly modular design and implementation of a reservation framework with only modest modifications to the base system.

MINIX 3

MINIX 3 is a microkernel-based multiserver operating system for uniprocessors that is designed to be extremely faulttolerant. All system services run as highly restricted usermode processes in order to isolate faults occurring in one component and prevent the damage from spreading, so that the rest of the system can continue to function normally. In contrast, a bug in a kernel module in a classic monolithic operating system could easily hang or crash the entire system due to the lack of isolation. In addition, the extension manager can detect certain error conditions, including failures relating to CPU or MMU exceptions, internal panics or infinite loops, and restart faulty processes. These features greatly improve the system's dependability [START_REF] Herder | Construction of a Highly Dependable Operating System[END_REF][START_REF] Herder | Failure resilience for Device Drivers[END_REF].

In addition to dependability, MINIX 3's highly modular structure makes it a good candidate as a real-time operating system for embedded platforms. Its code base is several orders of magnitude smaller than Linux, it is easy to remove unwanted components in order to get a minimal configuration, and the simple structure results in a small memory footprint. Moreover, MINIX 3 already has good response times due to the following design choices:

• the user-mode operating system servers and drivers have short servicing times and are fully preemptible by higher-priority processes,

• the kernel has very short interrupt latencies because its generic interrupt handler only masks the IRQ line and sends a notification message, whereas the actual interrupt handling is done by a user-mode driver, and

• finally, the kernel has short atomic kernel calls, which results in low stuck-in-kernel latencies.

However, MINIX 3 did not yet explicitly address other real-time application requirements. Realizing real-time behavior is not straightforward, since standard MINIX 3 versions lack important real-time properties, including:

• a way to describe a task's real-time constraints and schedule it accordingly,

• a temporal profile of each component in the system in order to achieve a complete system predictability, and

• typical resource access protocols, such as Priority Inheritance [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF] or Stack-Based Resource Protocol [START_REF] Baker | A stack-based allocation policy for realtime processes[END_REF], in order to avoid priority inversion phenomena.

Resource Reservations

In order to provide temporal protection on MINIX 3, we have made several modifications to the scheduler and designed and implemented a resource reservation (RRES) framework. Resource reservations are a class of real-time algorithms that grant Q resource units every period P [START_REF] Rajkumar | Resource Kernels: A Resource-Centric Approach to Real-Time and Multimedia Systems[END_REF]. In principle, the resource can be any system facility, including CPU, memory, network and storage devices. However, we are interested in CPU reservations, which have proven to be an effective technique to serve time-sensitive applications on general-purpose operating systems [START_REF] Abeni | Implementing resource reservations in linux[END_REF][START_REF] Abeni | Qos management through adaptive reservations[END_REF].

To the best of our knowledge, we are the first to implement resource reservations in MINIX 3. In particular, we have provided a complete implementation of CBS [START_REF] Abeni | Integrating multimedia applications in hard real-time systems[END_REF], CBS-HR and IRIS [START_REF] Marzario | Iris: A new reclaiming algorithm for server-based real-time systems[END_REF], which are among the first and most effective ones. The new resource reservation framework improves MINIX 3 in three important ways:

1. RRES brings soft real-time support, so that benefits can be gained in many application domains, like the ones mentioned above. Correct accounting is achieved under the assumption of MINIX 3's low-latency response times discussed above. Moreover, infrequent deadline misses are tolerable due to the nature of soft real-time applications; the end user will perceive a missed deadline as a quality-of-service degradation rather than a fatal error.

2. Although our primary focus is soft real-time support, the RRES framework also provides limited hard realtime support for applications that do not rely on the standard system servers and drivers, such as sensoring applications using memory-mapped I/O. The only critical code is the kernel's generic interrupt handler, which has a short, strictly bounded execution time.

3. Our work improves dependability by enabling temporally isolated execution in order to prevent denial of service attacks [START_REF] Tsafrir | Secretly Monopolizing the CPU Without Superuser Privileges[END_REF]. Reliable accounting is realized by using the TSC cycle counter independent from the programmable interrupt timer (PIT), as detailed in Sec. 4.4.

Paper Outline

The remainder of the paper is organized as follows. Sec. 2 briefly surveys related work. Sec. 3 introduce the CBS, CBS-HR and IRIS resource reservation algorithms. Sec. 4 describe how we implemented the resource reservation (RRES) framework. Secs. 5 and 6 present a case study and the results of performance measurements on the introduced latency. Finally, Sec. 7 describes the current framework status and our planned future work.

RELATED WORK

We distinguish different operating system structures, since each structure leads to different real-time properties.

Monolithic Operating System Structure

In spite of significant research efforts, introducing realtime support in monolithic systems, such as Linux, is still considered an open problem. Real-time scheduling turned out to be difficult, mainly due to the presence of many other highly unpredictable system activities, such as interrupt handling, paging and process management.

Two approaches have been adopted in order to minimize latencies and improve response times. First, shortening nonpreemptible kernel code sections. This changes local code sections, but keeps the same monolithic kernel structure. As an example, Red Hat staff has contributed a series of kernel low-latency patches to the Linux community [START_REF] Molnar | s RT Tree[END_REF]. The patches have proven to be effective and are a substantial step towards a real-time Linux.

Second, introducing an additional real-time layer between the operating system and the real hardware in order to actively handle real hardware interrupts and mask them to the operating system when needed. This results in an hybrid ar-chitecture with a monolithic kernel running on top of a microkernel layer. The most important projects are RTAI [START_REF]RTAI home page[END_REF], RT-Linux [START_REF]RTLinux home page[END_REF] and Xenomai [START_REF]XENOMAI home[END_REF]. All these projects adopt a similar approach to the problem: a new interrupt dispatcher is added below the standard kernel which traps the peripheral interrupts and reroutes them to Linux whenever it is necessary. However, this approach means that real-time tasks cannot directly access standard Linux services and existing device drivers due to potentially high and unpredictable delays. For this reason, developers often have to (re)write their own real-time drivers.

Multiserver Operating System Structure

Real-time work also has been done in the context of multiserver systems. Here, low interrupt latencies and good response times are easier to achieve than in a monolithic system, since all services are already scheduled independently. Below, we discuss related work in three systems.

Resource reservations and temporal protection have been tested before on Real-Time Mach (RT-Mach) [START_REF] Mercer | Temporal Protection in Real-Time Operating Systems[END_REF][START_REF] Mercer | Processor Capacity Reserves: An Abstraction for Managing Processor Usage[END_REF][START_REF] Tokuda | Real-Time Mach: Towards Predictable Real-Time Systems[END_REF]. RT-Mach enforced the concept of resource reservation using a fixed-priority schemes like RM [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF], or, at most, a dynamic-priority scheme based on old algorithms like TBS [START_REF] Spuri | Efficient aperiodic service under the earliest deadline scheduling[END_REF], which cannot achieve full CPU utilization. In contrast, MINIX 3 implements the newer CBS, CBS-HR and IRIS algorithms. Furthermore, RT-Mach seems to have fixed the scheduling policy in the kernel, whereas we promote a minimally invasive, modular design.

Real-time support in L4 [START_REF] Liedtke | Toward real microkernels[END_REF] is based on the statistical approaches Quality-Assuring Scheduling (QAS) [START_REF] Hamann | Quality-Assuring Scheduling[END_REF] and Quality-Rate-Monotonic Scheduling (QRMS) [START_REF] Hamann | Probabilistic admission control to govern real-time systems under overload[END_REF]. By extracting task properties, the system can guarantee that the deadlines of the mandatory part are met, while deadline misses in the optional part are tolerated. However, in order to enforce the mandatory-optional splitting principle, DROPS' real-time applications require modifications at source code level, whereas our framework can directly serve any existing applications in a real-time fashion. Furthermore, QAS and QRMS can provide guarantees for only periodic tasks, whereas CBS, CBS-HR and IRIS also support aperiodic tasks with real-time requirements. We also believe that our implementation can be simpler, since no complexity is introduced at admission and reservation level, whereas QAS performs these tasks using the distribution of execution times.

Finally, two projects based on earlier versions of MINIX should be mentioned. First, Minix4RT [START_REF] Pessolani | MINIX4RT: A Real-Time Operating System Based on MINIX[END_REF] aims to mimic the low-latency RT-Linux architecture in MINIX 2. Second, RT-Minix [START_REF] Rogina | New real-time extensions to the minix operating system[END_REF][START_REF] Rogina | Extending rt-minix with fault tolerance capabilities[END_REF] consists of a set of system calls added to MINIX 2 in order to explicitly invoke real-time services provided by the kernel level. The former project has been made obsolete by MINIX 3, since its generic interrupt handler achieves low interrupt latencies in a much simpler way. Furthermore, these approaches are too invasive with respect to the base system and cannot be easily ported to MINIX 3. Moreover, our work provides the first-ever implementation of resource reservations and temporal protection based on CBS, CBS-HR and IRIS in the context of MINIX 3.

RESOURCE RESERVATIONS

Resource reservations are a powerful concept providing temporal protection for time-sensitive applications. The underlying idea is to reserve a fraction of the CPU in order to ensure isolated execution. Resource reservations are typically used to run both periodic and aperiodic tasks, since they allow the scheduler to enforce classical Earliest Deadline First (EDF) [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF] scheduling decisions, even in presence of misbehaving tasks that execute longer than expected or unexpectedly introduced tasks that impose a temporary increase on the global utilization.

Before we continue, we briefly introduce EDF, which is the most widely adopted uniprocessor real-time scheduling algorithms in the dynamic priorities field. The EDF algorithm states: "for each t, the task with the earliest absolute deadline is executed." Despite a higher computational complexity than Rate Monotonic (RM) [START_REF] Liu | Scheduling algorithms for multiprogramming in a hard real-time environment[END_REF], which is the industrial standard for the fixed priorities field, EDF, in contrast to RM, can always achieve full CPU utilization without any deadline misses, which is an important goal in our work.

Achieving Temporal Protection

Temporal protection refers to the scheduler's ability to prevent one task from affecting the execution of other tasks by executing longer than expected due to, for example, a programming bug. Traditional real-time operating systems do not protect against such schedule overruns, as depicted in Fig. 1. Here, the overrunning task T 2 that is scheduled according to the EDF algorithm causes the other tasks to violate their deadlines in a so-called domino effect. In contrast, the use of resource reservations provides temporally isolated execution environments in which all tasks can complete within their deadlines despite of the overrun of the faulty task. The mechanism that enforces the reservation is referred to as a Virtual Resource (VRES) R that grants a CPU budget Q for each period P . An overrunning task can request additional CPU budget from its VRES, but this causes its deadline to be postponed by one period-so that other tasks with an earlier deadline are scheduled first. Fig. 2 shows how this happens three times for task T 2 . In the end, T 2 misses a deadline, but T 1 and T 3 run unaffected. We describe such an environment as compartmentalized from the scheduling point of view.

Resource Reservation Algorithms

We now briefly introduce the resource reservation algorithms that we implemented in MINIX 3: CBS [START_REF] Abeni | Integrating multimedia applications in hard real-time systems[END_REF], CBS-HR and IRIS [START_REF] Marzario | Iris: A new reclaiming algorithm for server-based real-time systems[END_REF], which are among the most widely recognized resource reservation algorithms. Other algorithms have also been proposed, e.g. [START_REF] Caccamo | Capacity sharing for overrun control[END_REF][START_REF] Caccamo | Efficient reclaiming in reservation-based real-time systems with variable execution times[END_REF][START_REF] Lipari | Greedy reclamation of unused bandwidth in constant bandwidth servers[END_REF]], but we chose CBS, CBS-HR and IRIS because their simplicity and low overhead allowed for a clean and minimally invasive implementation.

CBS

The Constant Bandwidth Server (CBS) [START_REF] Abeni | Integrating multimedia applications in hard real-time systems[END_REF] is a resource reservations algorithm with dynamic priorities that uses the EDF algorithm at the lowest level. CBS can achieve full CPU utilization and solves many classic real-time scheduling problems, such as managing unpredictable instances of aperiodic tasks. We briefly recall the algorithm here:

1. each virtual resource (VRES) is assigned a maximum budget Q, a period P , a current budget c and a current deadline d; 2. a virtual resource is active if its task is active, inactive otherwise; initially, all virtual resources are inactive, and c = 0 and d = 0; 3. when a task is activated:

• if d ≤ t or c > (d -t) Q P , then c = Q and d = t + P ,
• else, the current scheduling parameters are used 4. at each time t, the active virtual resource with the earliest current deadline d is chosen, and its task gets executed; 5. as long as T runs, the budget c of the virtual resource decreases at a rate δc = -δt; 6. whenever the virtual resource budget is exhausted (c = 0), it is immediately recharged (c = Q) and its deadline is postponed (d = d + P ); as a consequence, rule 4 is applied and another virtual resource might be scheduled.

Since the CBS algorithm is based on EDF, and the virtual resources can be approximated as sporadic tasks with a worst-case execution time Q and minimum interarrival time P , it is possible to allocate 100% of the processor bandwidth. In addition, the CBS reclamation scheme provides temporal protection against overruning tasks. CBS rule 6 ensures that the priority of a misbehaving task is decreased by postponing the deadline of its virtual resource. The task is kept in the ready queue, but cannot execute if other tasks with an earlier deadline exist, as shown in Fig. 2.

CBS-HR and IRIS

Due to its simple reclamation scheme, the CBS algorithm suffers from a problem called deadline aging [START_REF] Marzario | Iris: A new reclaiming algorithm for server-based real-time systems[END_REF]. If a CPU-bound, non-real-time task T 1 (e.g. a compilation with gcc) is the only active task in the system, CBS' deadlinepostponement rule is continuously triggered for R 1 . Under the assumption that T 1 was granted only a fraction of the CPU, its deadline will be somewhere in the far future after consuming several budgets Q. If another task T 2 (e.g. bun-zip2) starts executing, it will have the highest EDF priority for a long time, during which T 1 cannot execute. Hence, the end user will perceive T 1 as a non-responsive task.

The problem of deadline aging has been addressed by CBS-HR through a concept known as hard-reservation mode. If the virtual resource's budget is exhausted, replenishment only happens at the beginning of the next period. This ensures that the virtual resource's deadline is not repeatedly postponed and stays synchronized with respect to task execution. However, CPU cycles may be wasted while recharging, which led to the notion of time warping in IRIS [START_REF] Marzario | Iris: A new reclaiming algorithm for server-based real-time systems[END_REF]. CBS-HR extends the standard CBS policy with rule 7, whereas IRIS extends CBS-HR with rule 8: 7. when budget c is exhausted, the task is suspended and the virtual resource moved to the recharging state until the current deadline d, when the the budget is replenished to c = Q and the deadline postponed to d = d + P ; 8. if all virtual resources are in recharging state at time t and no virtual resource is currently active, they can be all recharged and their deadlines updated to d = t + P . These extensions result in a more responsive system and a better reclamation policy, respectively. As an example, Fig. 3 shows how IRIS prevents deadline aging for the above scenario of two aperiodic, CPU-bound tasks.

DESIGN AND IMPLEMENTATION

This section describes how we implemented a resource reservation (RRES) framework in MINIX 3 with support for the CBS, CBS-HR and IRIS resource reservation algorithms. Three important design guidelines for the implementation of the RRES framework were:

1. pluggable real-time support next to best effort; 2. minimizing the amount of intrusive kernel code; 3. maximizing the policy-mechanism separation.

First, we did not want to break the standard MINIX 3 distribution for reasons of acceptance and backward compatibility. Therefore, we designed the RRES framework as an optional component that can be started at run-time to enhance the system with real-time support when needed. Second, a general dependability strategy in MINIX 3 is to move as much code as possible out of the kernel into user space. Since kernelmode code runs with all privileges of the machine it must be fully trusted, whereas user-mode bugs may be confined to the process in which they occurred. Third, separating the scheduling policies from mechanisms leads to a flexible, easily adaptable system. Fortunately, these guidelines go hand in hand, as discussed below.

High-level Design Overview

Based on the above design criteria we decided to introduce a separate user-space scheduler, called the RRES manager or RRES for short, which is logically located at the MINIX 3 server level. RRES can be started through the MINIX 3 extension manager at run-time like all other extensions [START_REF] Herder | Failure resilience for Device Drivers[END_REF]. The basic idea then is to let the kernel execute user-space scheduling requests for real-time applications on behalf of RRES. In particular, the kernel's built-in best-effort scheduling policies should be temporarily suspended, so that the real-time task is not affected by the heuristics of the standard scheduler. In other words, the scheduling policy is enforced in user-space, but the kernel provides mechanisms for starting and stopping a task and for accounting its execution. Logically, this leads to a separate RRES scheduler next to the MINIX 3 scheduler.

As an aside, we provided three different implementations of the RRES manager, one for each resource reservation algorithm supported: CBS, CBS-HR, and IRIS. The algorithm used is statically chosen with a compiler flag. It is currently not possible to let different VRESes serve their task using different algorithms, since the theoretical analysis to make this possible is still in progress. The reason for supporting CBS and CBS-HR next to IRIS is a matter of usability. With IRIS' time warping rule, all CPU cycles would be used for real-time task and non-real-time applications would not get a chance to execute. In such a scenario, every application should be enclosed in a reservation, resulting in a system that is harder to analyze and maintain.

In addition to the RRES manager, three helper utilities were created in order to manage real-time applications. First, rres create can be used to start a new real-time application by passing the binary's name its period P and budget Q. Second, rres change can be used to change the scheduling parameters at run-time. Third, the rres destroy utility can be used to stop a running real-time task. Fig. 4 gives a highlevel overview of the RRES framework.

Implementation of the RRES Manager

The RRES manager has the same code structure as other MINIX 3 servers. After the initialization of its data structures, RRES starts a never-ending loop in which it accepts new requests, processes them and sends back an answer.

RRES Data Structures

The main RRES data structure has three scheduling queues for the virtual resources that are uniquely associated with the real-time tasks. The queues are ordered by increasing current VRES deadline, so that RRES can quickly decide which task to schedule based on the underlying EDF policy.

• The ACTIVE queue keeps track of ready-to-run VRE-

Ses. The first VRES on this queue is the currently scheduled one, that is, the associated task is the running process in the system.

• The RECHARGING queue comprises all the VRE-Ses which exhausted their budget and need it to be replenished. This queue is only used for CBS-HR and IRIS. With plain CBS it is always empty since hardreservation mode is not used. Conceptually, all VRESes in this queue are recharging, but RRES only sets a single alarm for the first recharging event.

• The BLOCKED queue, finally, contains the VRESes that blocked during their execution, for example, because they have to wait for some event to happen.

RRES Interactions

As shown in Fig. 4, the RRES manager has several interactions with both the RRES help utilities and the kernel tasks.

The exact messages that are exchanged are shown in Fig. 5. First, the RRES helper utilities can request RRES to CRE-ATE, CHANGE or DESTROY virtual resources. In order to prevent random tasks from changing their scheduling policy only the system administrator is allowed to send RRES requests. RRES verifies this by asking the MINIX 3 process manager for the requester's user ID. Second, although RRES is responsible for the scheduling policy, it relies on kernel mechanisms to perform the actual RRES scheduling. In particular, the following messages are exchanged with the kernel's system task:

• CALIBRATE TSC: used at RRES initialization time to determine the number of CPU cycles per microsecond; the kernel programs the timer to a known frequency, reads the TSC cycle counter start value, waits 1000 timer ticks, and reads the TSC end value.

• START RT TASK: tell that a process now is a real-time task and needs to be treated in a special manner.

• STOP RT TASK: inform the kernel that a real-time task has been destroyed so that special events related to this task are no longer forwarded to RRES.

• START SCHEDULE: tell the kernel to start scheduling a real-time task using the RRES scheduler rather than the standard scheduler.

• STOP SCHEDULE: issued whenever RRES needs to stop the currently scheduled real-time task.

• START RECHARGE: if a VRES becomes the head of the RECHARGING queue, RRES schedules an alarm to be notified when the recharging time is reached.

• STOP RECHARGE: used to handle a time warping event in IRIS and if the scheduling parameters of a currently recharging task are changed.

• GET MESSAGES: whenever the kernel's mechanisms encounter a special event, as shown in Fig. 5, the RRES manager is notified with an RRES EVENT message; the RRES manager then makes a callback to find out which event triggered the notification.

While this modularity brings many benefits with respect to flexibility, the message passing interactions between RRES and the kernel introduces a small latency. Experiments on a prototype implementation have shown, however, that the incurred context-switching overhead is not at all prohibitive, as discussed in Sec. 6.

Kernel and Scheduler Modifications

Scheduling in the standard MINIX 3 kernel is done on best-effort basis using a multilevel-feedback-queue scheduler (MLFQ) [START_REF] Torrey | A comparison of interactivity in the linux 2.6 scheduler and an mlfq scheduler[END_REF]. Processes with the same priority reside in the same queue and are scheduled round-robin. When a process is scheduled, its quantum is decreased every clock tick until it reaches zero and the scheduler gets to run again. To prevent starvation of low-priority processes, a process' priority is degraded whenever it consumes a full quantum. Since CPU-bound processes are penalized more often, interactive applications have good response times. Periodically, all process priorities are increased if not at their initial value.

As mentioned above, the kernel should bypass the standard scheduler for real-time tasks managed by RRES. Therefore, the MINIX 3 kernel and scheduler were changed in two ways. First, we added rres f flag to the process structure in order to tell whether a task should be scheduled in the context of MLFQ or RRES. This flag is set when RRES sends a START SERVE request to the kernel. Second, the scheduler data structure was extended with two new scheduling queues at the highest priorities, as shown in Fig. 6.

• RRES PRIO: the highest priority in the system is now used for the RRES manager, so that it can always immediately react to the various kinds of events, such as budget exhaustion and budget recharged events. Depending on the kind of event RRES may schedule another real-time task. When RRES has processed the event, it returns to its main loop and blocks waiting for the next event-allowing a real-time task to run.

• RT PRIO: the second highest priority is reserved for the real-time tasks served by the RRES manager. At most a single task can be active at any given time. When there is a task to schedule, it runs uninterrupted until either its budget is exhausted or some other RRES event makes a higher-priority task ready to run. In the latter case, preemption occurs and RRES requests the kernel to schedule the higher-priority task.

Third, we identified the points which needed change in order to modify the default scheduler behavior. In particular, if a real-time task needs to be scheduled, that is, if a process' rres f flag is set, the scheduler simply picks the queue with priority level RT PRIO rather than its MLFQ priority. Also, a task running in the RT PRIO queue is not affected by the heuristics of the normal MLFQ algorithm, such as decreasing the process priority of long-running processes and periodic balancing of the scheduling queues. Finally, we changed the scheduler to cope with blocking and unblocking events. Whenever a real-time task blocks the kernel sends an event notification to RRES, so that it can schedule another task. Blocking can occur, for example, during synchronous service requests or while waiting for an I/O completion interrupt. We decided to consider a task's blocking and unblocking events as job completion and activation times respectively in order to be able to provide the classic real-time properties previously described. The blocked task's VRES is put on RRES' BLOCKED queue. When the kernel notifies RRES that the task is unblocked, RRES moves the corresponding VRES to the ACTIVE queue and may schedule it depending on its current priority.

CPU Time Accounting

In order to serve real-time tasks the RRES framework requires a reliable source of high-precision timing. Our implementation is based on the x86's TSC cycle counter, but depending on the system architecture, other timing sources may also be available. The TSC cycle counter is convenient because it is accessible to both the user-space RRES manager and the kernel's scheduling code. However, since the TSC cycle counter is read-only and cannot interrupt when a task's budget is exhausted or needs to be replenished, an interruptbased programmable timer is also needed. For this, we decided to modify the standard MINIX 3 system timer, which is based on the i8259 Programmable Interval Timer (PIT). Another option would have been to use the CMOS 'Real-Time Clock', but it is already in use for the MINIX 3 profiling code [START_REF] Meurs | Building Performance Measurement Tools for the MINIX 3 OS. Mas[END_REF] and having two sources of timer interrupts would have complicated the kernel's code.

Working of RRES Accounting

Although the PIT ticks come at a lower frequency than the TSC cycle counter, the RRES framework can do its work as follows. During initialization RRES calibrates the TSC cycle counter using the CALIBRATE TSC in order to determine the number of cycles per microsecond. Budget exhaustion and budget replenishment events are expressed in CPU cycles rather than PIT ticks in order to prevent rounding errors in the calculation. This number is reported to the kernel on START SCHEDULE and START RECHARGE, respectively, which stores the count in a global variable and compares it to the current cycle counter value on each PIT tick. If the current cycle counter value exceeds the exhaustion or recharging time, the kernel deschedules the task (in the former case only) and sends an RRES EVENT notification to the user-space RRES manager. One important decision was at which frequency the TSC counter should be read, that is, the PIT interrupt frequencysince a higher frequency leads to a lower worst-case accounting error. The maximum usable frequency is limited, however, since each PIT interrupt requires reprogramming the timer. After some experimentation we decided to use a PIT frequency of 4000 Hz, which limits RRES accounting error to at most 250 µs. Moreover, task overruns are taken into account by the RRES manager by reading the TSC cycle counter after the RRES EVENT notification, comparing it with the original deadline, and reducing the task's CPU budget in its next execution frame.

Although RRES accounting works at 4000 Hz, we used a frequency of 500 Hz for the system's normal tick facility. This distinction takes place in the clock task's interrupt handler, which scales the hardware PIT frequency into lowerfrequency system-wide ticks, that is, only 1 in every 8 interrupts is transformed into a system tick.

Eliminating CPU Monopolization

An important benefit of our design is that denial of service (DoS) attacks that monopolize the CPU [START_REF] Tsafrir | Secretly Monopolizing the CPU Without Superuser Privileges[END_REF] are structurally eliminated. By basing accounting on the actual number of CPU cycles used, independent of the PIT ticks, a task can no longer cause another task to be billed by suspending execution just before a PIT tick occurs. In contrast, whenever a task served by RRES stops execution, the RRES manager is informed and the current TSC cycle counter is read to decrease its remaining budget with the number of CPU cycles consumed. Processes that use MINIX 3's standard scheduling facilities are still vulnerable, but real-time tasks and, in fact, any application with stringent timing requirements can use the new RRES framework for temporal protection.

RRES CASE STUDY

To better clarify how the framework works, we now discuss an example that shows the interactions of the RRES framework, configured to use CBS with hard-reservation mode (CBS-HR). We analyze the sequence of events for two real-time tasks, T 1 and T 2 , producing the schedule shown in Fig. 7. Initially, the administrator starts the tasks using the rres create utility. The command entered is $ rres create <budget> <period> <binary> where the request parameters are <budget>: CPU budget given in each period (Q) in µs; <period>: the VRES granularity (P ) in µs; <binary>: the application to be managed by RRES.

This request has to be made for both task T 1 and T 2 with parameter Q 1 = 3000 µs, P 1 = 9000 µs and Q 2 = 2000 µs, P 2 = 3000 µs. The sum of the fractions Q P gives the CPU utilization and is 100% in this example.

For both tasks, the rres create utility forks a new process, sends a CREATE message to the RRES manager to inform it about the new real-time task's parameters, and executes the binary. RRES first checks if the user is authorized and then performs an admission test. Since the CPU utilization does not exceed 100%, RRES accepts the requests, creates two virtual resources R 1 and R 2 with the required parameters, and sends a START RT TASK message to the kernel to tell that T 1 and T 2 are real-time tasks from now on. The virtual resources, R 1 and R 2 , will be enqueued in RRES' ACTIVE queue, with task T 2 at the head of the queue, since T 2 's initial deadline is earlier than that of T 1 . We will now analyze the interactions between the RRES manager and kernel during the execution of tasks T 1 and T 2 , which produces the schedule shown in Fig. 7. As discussed in Sec. 4.4, the RRES manager uses the TSC cycle counter for accounting. For reasons of simplicity, however, all times below are expressed in milliseconds.

At time T = 0, RRES issues a RRES SCHEDULE request to the kernel specifying the task to be scheduled, in this case T 2 , and the amount of CPU budget, that is, how long the task is allowed to execute, in this case 2. The kernel accepts the RRES request, sets up the time at which the budget is exhausted, and schedules the task in the queue with priority level RT PRIO.

At time T = 2, the kernel notifies RRES about the budget exhaustion of T 2 . RRES moves R 2 from the ACTIVE to the RECHARGING queue and, since hard-reservation mode is used, asks the kernel to recharge R 2 's budget until the absolute time of R 2 's deadline, T = 3. RRES also tells the kernel to schedule task T 1 with budget Q = 3

At time T = 3, the kernel notifies RRES about R 2 's budget being recharged, so that RRES moves it from the RECHARGING queue back into the ACTIVE one. Since R 2 has the earliest deadline, T 1 is preempted and RRES asks the kernel to schedule task T 2 with a budget of 2.

At time T = 4, task T 2 experiences a blocking event. The kernel notifies RRES, which in turn moves T 2 's virtual resource, R 2 , to the BLOCKED queue. Then RRES asks the kernel to resume execution of T 1 with a budget of 2.

At time T = 5, task T 2 unblocks. RRES is notified by the kernel and computes the test in CBS rule 3. Since the remaining budget c = 1 ≥ (6 -5) 2 3 = 2 3 a new deadline is placed at T = 8 and the budget is recharged. R 2 is moved to the ACTIVE queue and task T 1 is preempted by T 2 .

At time T = 7, R 2 's budget is exhausted again. RRES is notified by the kernel, moves R 2 to the RECHARGING queue, and tells the kernel to recharge until T = 8. RRES also requests the kernel to resume execution of task T 1 with R 1 's remaining budget of 1.

At time T = 8, two things happen: R 1 's budget is exhausted and R 2 's budget is recharged. R 1 is moved to the RECHARGING queue and the kernel is told to recharge the task until R 1 's absolute deadline, T = 9. In addition, RRES ask the kernel to schedule task T 2 with a budget of 2.

This example shows how a user-space scheduler can do all the work using a small number of interactions with the kernel, obtaining the schedule produced in Fig. 7. In the following section we will see how these interactions impose a very limited timing overhead on the system.

EXPERIMENTAL EVALUATION

In addition to the above case study, we ran several experiments on a prototype implementation to evaluate the RRES framework. The results are presented below.

Timing Measurements

As explained in Sec. 4.4, time accounting is done using the TSC cycle counter. The TSC facility is available in both kernel space and user space, allowing RRES to be kept synchronized with the kernel time line. In addition, this enabled precise timing measurements, depending on CPU speed only. The tests were conducted on a Fujitsu-Siemens desktop PC with a 2.8 GHz AMD Athlon64 CPU and 1 GB RAM. None of the tests required to access the disk.

First, we measured the latency introduced by MINIX 3's message passing subsystem, which is independent from the RRES framework. In particular, we measured the time between issuing a request in a user process (just before IPC SEND) and the moment that the kernel starts working on it (just after IPC RECEIVE), that is, the time purely spent on delivering the message from the user process to the SYS-TEM task. We found a message delivery time of 1.5 µs.

Second, we measured the latency introduced by the RRES framework. These tests were done in the context of the case study discussed in Sec. 5. We ran several tests and computed the mean result rounded to microsecond precision.

• Time between receiving a rres create command in the RRES framework and the moment that the kernel schedules the new real-time task: 192µs.

• Time between budget exhaustion in the kernel, causing an RRES EVENT notification processed by the userspace RRES framework, and the moment that the kernel puts the VRES in the recharging state: 43µs.

• Time between detecting a budget-recharged event in the kernel, notifying RRES, and the moment that the kernel reschedules the corresponding task: 41µs.

These results clearly show a very limited overhead imposed by the RRES framework on the system in order to enforce the CBS, CBS-HR and IRIS algorithms. It is important to realize that these values are not dependent on the presence of other real-time tasks, because (1) the kernel's interrupt handler always preempts running tasks and (2) messages that are exchanged upon RRES events are delivered and handled at the highest priority, as shown in Fig. 6.

The measured values have to be compared with the resolution the system is able to grant to the framework. Since time accounting is done at 4000 Hz, the minimum amount of budget and period can, in principle, be 250µs. However, to prevent compromising the requested parameters, they should be at least an order of magnitude larger. Therefore, the budget and period should be set starting from 5-10 ms in practice.

Impact on Kernel and User-Space Code

With help of the Source Code Line Counter [START_REF] Sclc | the Source Code Line Counter[END_REF] tool available on the Internet we collected data on the total engineering effort required. The number of executable lines of code for both the standard and modified version of the MINIX 3 kernel are shown in Fig. 8. Similar statistics for the new user-space RRES manager are shown in Fig. 9

RRES Tracer and Simulations

We also created a tool written in Ruby to trace the execution of RRES real-time tasks. The tool parses a log file generated by the RRES server and produces a graphical representation of the scheduling decisions taken. Fig. 11 represents a piece of the scheduling of the task set in Fig. 10 that is scheduled according to CBS-HR (CBS with hard reservations); IRIS' time warping is not used. The tasks used are an infinite CPU-bound program (cpuload) that performs calculations in a loop and a finite I/O-bound program (interactive) that does some work, sleeps one second, and continues calculating. The tracer output shows three aspects:

• cpuload continuously triggers CBS' deadline postponement rule, as is clear in the first two task lines where arcs connect consecutive deadlines;

• since interactive has a large budget, it can execute whenever there is a free slot, unless it blocks on the sleep() system call;

• at that point, the hard-reservation mode becomes evident, since the two cpuload utilities run without time warping (the scheduling is not work-conserving).

Numerous other simulations have been run to verify the behaviour of our implementation in few real cases, but we refrained from including them here due to space limitations.

CONCLUSIONS AND FUTURE WORK

MINIX 3 is a dependable multiserver operating system for uniprocessor systems. Its modular design makes it a likely candidate for embedded systems, but MINIX 3 currently lacks real-time support. Therefore, we have enhanced MINIX 3 with temporal protection via resource reservations. To the best of our knowledge, this had not been done before. Long latencies and slow response times caused by the message passing mechanism were a potential bottleneck, but measurements on a prototype implementation have shown that this effect is very limited and can be mitigated by carefully designing the framework interactions.

Our resource reservation framework (RRES) implements the CBS, CBS-HR and IRIS resource reservation algorithms and provides temporal protection in order to prevent ordinary users from monopolizing the CPU. Our design enables running soft real-time applications on MINIX 3. The current status is that correct time accounting happens in presence of nonblocking tasks. If blocking events occur, the framework operates correctly under the assumption of short server and driver execution times. Since kernel's generic interrupt handler has a short strictly bounded execution time, limited hard real-time support is provided for tasks that do not rely on the standard MINIX 3 services. In addition, the RRES framework eliminates denial of service (DoS) attacks [START_REF] Tsafrir | Secretly Monopolizing the CPU Without Superuser Privileges[END_REF] targeting the scheduler, because time accounting uses the TSC cycle counter independent the system tick facility. Work in the context of FRESCOR [START_REF]FRESCOR -Framework for Real-time Embedded Systems based on COntRacts[END_REF] is in progress to implement a microkernel equivalent of bandwidth inheritance [START_REF] Lamastra | A bandwidth inheritance algorithm for real-time task synchronization in open systems[END_REF] algorithm so that the drivers and servers working on behalf of a real-time task can use its RRES parameters during the servicing time. This gives two important benefits, namely, correct time accounting and a very simple resource-access protocol, priority inheritance, in order to prevent priority-inversion phenomena. In addition, we intend to analyze the possibility of reserving other resources types, such as file system and network access, through the RRES framework. Success in this area would result in a completely compartmentalized and fully protected resource environment, enabling full hard real-time support.

Figure 1 :

 1 Figure 1: Produced schedule with misbehaving task T2. The tasks' computation times and deadlines are shown at the left.

Figure 2 :

 2 Figure 2: Same schedule with temporal protection. The VRES' timeline is shown below the task's timeline.

Figure 3 :

 3 Figure 3: IRIS solves the deadline aging problem by having VRE-Ses wait until the next deadline before replenishing their budget. The replenishment can be instantaneous due to time warping.

Figure 4 :

 4 Figure 4: High-level architecture over the resource reservation framework. Messages exchanged between the RRES helper utilities, RRES manager and kernel are shown.

Figure 6 :

 6 Figure 6: RRES-enhanced MINIX 3 scheduling queue data structure. Two new queues at the two highest priority levels were added for the RRES manager and the current real-time task.

Figure 7 :

 7 Figure 7: Schedule of the case study in milliseconds.

Figure 9 :Figure 10 :

 910 Figure 9: Lines of executable code (LoC) for the RRES server. Task Type Budget (ms) Period (ms) cpuload CPU-bound 100 400 cpuload CPU-bound 200 2000 interactive I/O-bound 10000 20000 Figure 10: Task set and reservation parameters used for tracer simulation. The execution is shown in Fig. 11.

Figure 11 :

 11 Figure 11: Actual schedule executed for the task set of Fig. 10 produced by the RRES tracer based on RRES server logs.

  Lines of executable code (LoC) for the standard MINIX 3 kernel and the modified version with the RRES framework.

	File proc.h proc.c clock.c system.c rres.h rres.c do resres.c Total Changes Figure 8: Header Files LoC glo.h 42 inc.h 29 proto.h 51 rres.h 106 Source Files LoC main.c 158 rres.c 543 rres kernel.c 254 rres userspace.c 251 Header Total 156 Source Total 1206	Standard 99 482 115 314 ---	RRES MINIX 3 103 500 137 327 24 197 131	Delta +4 +18 +22 +13 +24 +197 +131 +339