FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 8 |

«Real-time systems are one of the most important applications of computers, both in commercial terms and in terms of social impact. Increasingly, ...»

-- [ Page 4 ] --

Quite often, they are simpler versions of the original software: the aim is to provide some rudimentary alternative that will allow the system to continue functioning acceptably. As mentioned before, a rudimentary piece of code is often easier to debug than one which is more complex and can therefore be more reliable. Also, it can take less time, and might therefore fit more easily into a schedule.

All tasks in the system are assumed to be periodic. If the LCM of the periods is P, then the algorithm carries out preprocessing to fix the position of the alternatives in the schedule over the interval [0, P]. This same schedule then repeats endlessly. That is, if an alternative is scheduled to execute at some point in time t ∈ [0, P], it is also scheduled to execute at times t + P, t + 2P, · · ·.

The basic idea behind this algorithm can be stated as follows. The alternatives are the key to reliability: we have to ensure that they have enough time to be executed. We reserve time in the schedule to ensure that this happens (barring a failure of the alternatives). Outside this reserved area, the system can execute primary versions, secure in the fact that enough time is available to run an alternative.

If both the primary and its backup fail, there is no remedy left. However, the same approach can be applied recursively, i.e., one can have backups to the backups, and so on.

The algorithm can be broken down into two phases: offline and online. In the offline phase, we develop a task schedule for the alternatives over the period [0, P]. In the online phase, we use

this task schedule as a guide to deciding which task to run. The details are broadly as follows:

• Offline Phase:

– Over the interval [0, P], schedule all the alternatives, according to principles we will describe later. Denote by A the union of intervals during which the alternatives are scheduled. This schedule repeats with a period of P, i.e., if t ∈ A over [0, P], we must have t + iP ∈ A as well for i = 1, 2, · · ·. Denote by αi the time when the alternative to task Ti is scheduled to start executing.

• Online Phase:

– Different priority schemes apply depending on whether we are in an interval within A or not. Within A, the alternative that is scheduled for that time has priority over everything else. Outside A, the primaries have priority; these can be scheduled according to any priority rule. RM and EDF are obvious alternatives; however, the task priorities may also be modulated by the value that the task confers on the system.

– Before any primary starts executing, the system checks to see if enough time is available in the schedule to complete it. If not, execution of the primary is abandoned.

– If the primary of task Ti finishes before αi, its alternative is cancelled and its assigned interval within the schedule is removed from A.

– If the primary of task Ti does not finish before αi, or it is known to have failed before then, all further execution of the primary is abandoned and the alternative starts executing.

– While αi is the point at which a backup for task Ti is supposed to start executing, if the processor finds itself idle before then, it can start executing backups early.

However, as mentioned above, outside the set of intervals, A, however, the backup(s) have lower priority than primary tasks.

We can pick any mechanism to schedule the alternatives that allows their deadlines to be met. However, logic dictates that the primaries be given as much of a chance to finish executing as possible. The obvious heuristic is to schedule the backups as late as possible. The approach taken is to start at the end of the scheduling interval [0, P] and work backwards. That is, we schedule a backup with execution time eb and absolute deadline P to occupy the interval

–  –  –

[P − eb, P]. We then go backwards from this point, scheduling backups in this way in descending order of their absolute deadlines, with ties being broken arbitrarily.

Let us now consider an example. We have a task set with the parameters shown in Figure 3a.

The LCM of the periods is 12. First, we generate an offline schedule of the backups over the interval [0, 12]. This is shown in Figure 3(b).

At time 0, the first iterations of T1 and T2 are issued. Let us use the RM algorithm to schedule the primaries. Task T1 is issued and its primary, π1, runs to completion; it finishes at time 2. Since T1 has executed successfully, its backup, B1 (scheduled for the interval [2, 3]), can be cancelled. There is now time for the primary of T2 to execute. Suppose π2 fails to produce its output by time 3. Then, it is aborted and its backup runs in the slot provided for it (in the interval [3, 4]).

A time 3, the second iteration of T1 is released; however, it is not allowed to start executing since the processor is running a backup in its assigned slot. So, it has to wait until time 4. At time 4, the processor checks that there is not enough time to finish π1 by time 5, so the primary of T1 is abandoned. At time 4, the second iteration of T2 arrives: it has lower priority than the primary of T1, but since that has been abandoned, it is allowed to start executing. Suppose now that this primary finishes early: at time 4.5. This causes its backup (scheduled for the interval [7, 8]) to be cancelled. At time 4.5, there is no primary waiting to execute, so the backup for task T1 can start early. This backup runs over the interval [4.5, 5.5], at which time the processor falls idle. At time 6, the third iteration of T1 arrives. It is again abandoned since there is insufficient time to execute it. And so on. See Figure 3(c).

In the above discussion, we assumed that we know precisely how long we should allow for the primary to execute before abandoning it. The actual execution time, however, is a random variable, which can differ substantially from its estimated worst-case execution time. In many instances, not allowing a task to start running may be overly conservative. Letting a primary run if the available time is less than its worst-case execution time, is a gamble: if it finishes, we have gained a primary execution (which, presumably, is superior in quality to that of its backup);

if it fails, we have wasted processor time that could well have been used to successfully execute some other primary. If we have the probability distribution function of the primary execution time, we could conduct offline experiments to determine what primary execution time we should allow for in order to obtain good results. The more mathematically ambitious could conduct an analysis based on Markov Decision Theory [Hillier and Lieberman, 2001] to determine what the appropriate primary execution time allowance should be. Note that we can safely gamble on the execution time required by the primary, since there is always enough time for the backup to execute if the primary should fail to deliver on time.

In the special case where periods are multiples of one another, i.e., Pi = miPi−1 where mi ∈ {1, 2, · · ·}, we can use the approach of [Liestman and Campbell, 1986]. Once again, the aim is to ensure that the backups always have enough time to execute successfully; the primary versions are regarded as contributing to performance but not essential to reliability. Hence, the aim is to schedule all backups feasibly and do a best-effort attempt on the primary versions.

We start by drawing up a schedule over [0, P1]. This always contains the backup B1; if there is enough time, it includes the primary, π1. Call this schedule S1. Next, we move to construct S2, a fault-tolerant schedule over [0, P2], consisting of tasks {T1, T2}, then S3 over [0, P3], and so on.

To construct Si, we start by laying out mi copies of Si−1 end-to-end. Then, Bi is scheduled on top of this schedule, removing one or more already-scheduled primary copies if necessary. Then, we check to see if there is enough idle time to schedule πi. If there is, we do so. Otherwise, we may either give up trying to schedule πi or explore the possibility of dropping one or more copies of some other primary, πj to make room for it.

As an example, consider a three-task system, with task periods P1 = 10, P2 = 20, P3 = 40;

the primary execution times are e1 = 7, e2 = 4, e3 = 6 and the backup execution times are ξ1 = 2, ξ2 = 3, ξ3 = 3. Figure 4 shows the process of constructing the fault-tolerant schedule.

We start by constructing S1, consisting of just the task T1. It is easy to check that there is enough time to schedule both the primary and backup copies.

To construct S2, we concatenate two copies of S1 and use that as a framework within which to schedule T2. We have a total of 2 time-units available: this is not enough to schedule either the primary or backup of T2. Hence, we drop one of the two iterations of π1: this releases enough time to schedule B2.

Finally, we construct S3. Concatenate two copies of S2: there is enough time to fit both a π1 B1

–  –  –

primary and a backup copy of T3 in this schedule.

Finally, if we can accelerate the processor by means of voltage scaling, the time required to be reserved for the backups will be reduced. This, however, is only acceptable so long as the probability of activating the backups is small enough that the additional expected energy expenditure is affordable.

An online variation on this problem has been addressed as well [Caccamo and Buttazzo, 1998].

The focus is on tasks that are scheduled as they arrive; as before, each task has primary and backup copies. Primary copies are susceptible to timing overruns, while backup tasks have welldefined worst-case execution times. If the primary cannot be scheduled before the backup is to run, we rely on the output of the backup. If it is scheduled, based on its estimated execution time, and then proceeds to overrun this time, the primary is aborted and the backup is executed. If, on the other hand, the primary completes successfully without overrunning its time, the backup need not execute; its budgeted execution time can be released for use by other tasks.

The scheduling algorithm must ensure that, at all times, the backup has enough time to execute successfully in the event that the primary does not.

6 Permanent Faults

To deal with permanent faults, we obviously require hardware redundancy. By far the simplest way to deal with such faults is to have spare processors in the system. These are idle to begin with; when a processor fails, its schedule is switched over to that of the replacement processor.

Such an approach, while simple, may not be appropriate as an emergency (rather than as a

long-term) response for the following reasons:

• If, as is generally the case, we have processors with private, rather than shared, memory,

then one of two possibilities exist:

– Copies of all the tasks that this spare processor may have to execute are preloaded in its memory. This may require more memory capacity at each of the spares than we can afford.

– Once the system knows which tasks need to be run on the spare processor, those tasks can be loaded into its memory. This obviously takes time, which may not be available in a real-time system. (As mentioned earlier, this may well be a good long-term response to a failure; we are concentrating in this paper on short-term responses).

• Having idle spares usually wastes energy. If all the available processors are actively involved in executing the workload, the workload per processor is less. As a result, processors can be run at a lower clock rate and still meet all task deadlines. This, in turn, allows us to use a lower supply voltage, which saves energy. Recall that energy consumption to execute a given workload is a quadratic function of the supply voltage.

6.1 Periodic Tasks The task set, which is known in advance, consists of periodic tasks. We make the common assumption that the deadline of each task iteration is equal to its period, i.e., the deadline of an iteration occurs at the same time as the release time of the next iteration of that task.

The overall task scheduling problem breaks down into two parts. The first is an assignment of tasks to processors. The second is to use the selected uniprocessor algorithm to schedule the assigned tasks on each processor.

The problem of task assignment and multiprocessor scheduling has long been known to be NP-complete [Garey and Johnson, 1979]. Heuristics must therefore be used. The 0-1 knapsack heuristics [Cormen, et al., 2004] are probably the most commonly used such procedures. In particular, we will explore here the use of the first fit assignment algorithm.

In the first-fit algorithm, one tries to assign tasks to processors one by one in some order.

A task is assigned to the first processor on which it can be feasibly scheduled. Let us start by illustrating such an assignment procedure without any provision for fault-tolerance.

Suppose we are using the RM scheduling algorithm. We pick one task after another, in order of their RM priority (ties may be broken arbitrarily). Recall that the RM priority5 of a task is inversely related to its period.

For each task, we identify the first processor on which it can be feasibly assigned. By feasible assignment, we mean that this task together with the tasks, if any, already assigned to that processor, can all meet their deadlines. This can be checked by using the response-time expression (Equation 1) encountered earlier.

There are variations on this algorithm that immediately suggest themselves. First, the order in which the tasks are assigned need not be in RM priority order. They could follow some other ordering, e.g., we could choose to order the longer tasks (i.e., those with a longer WCET) first or simply pick them at random. However, the convenience in assigning tasks in descending order of priority is that once we calculate the worst-case response time of an assigned task, that time does not change with subsequently assigned tasks, since these are always of lower priority.

Pages:     | 1 |   ...   | 2 | 3 || 5 | 6 |   ...   | 8 |

Similar works:

«Appel à Projets Mobilité électrique durable Edition 2016 1 Objet de l’appel à projets La problématique des modes de déplacements basés sur la prépondérance du véhicule individuel couplée à un mix électrique très carboné, nous oblige à repenser et à encadrer le développement du véhicule électrique en Guadeloupe. En effet, le simple remplacement du véhicule thermique classique pour le particulier par un véhicule électrique ne saurait représenter une alternative...»

«Kappa Alpha Order National Administrative Office THE CONVIVIUM MANUAL (Third Edition) TABLE OF CONTENTS Page Foreword to the First Edition 3 Introduction 4 Explanation of Format for Convivium Facilities and Locations 5 Invitations and Convivium Contact Committee 6 Master of Ceremonies 7 Guest Speakers and Special Guests 8 Presentation of Special Awards 9 Instructions for Toast to Lee and Ammen 10 Toasts to Lee and Ammen 11 Example of Convivium Program 14 Helpful Hints and Resources 15 Kappa...»

«EN Case No COMP/M.4561 GE / SMITHS AEROSPACE Only the English text is available and authentic. REGULATION (EC) No 139/2004 MERGER PROCEDURE Article 6(1)(b) NON-OPPOSITION Date: 23/04/2007 In electronic form on the EUR-Lex website under document number 32007M4561 Office for Official Publications of the European Communities L-2985 Luxembourg COMMISSION OF THE EUROPEAN COMMUNITIES Brussels, 23/04/2007 SG-Greffe(2007) D/202442 In the published version of this decision, some PUBLIC VERSION...»

«UNITED STATES AIR FORCE COURT OF CRIMINAL APPEALS UNITED STATES v. Airman First Class DUSTIN M. HART United States Air Force ACM 36253 30 November 2006 Sentence adjudged 20 December 2004 by GCM convened at Charleston Air Force Base, South Carolina. Military Judge: Kevin P. Koehler. Approved sentence: Bad-conduct discharge, confinement for 185 days, forfeiture of all pay and allowances, reduction to E-1, and a reprimand. Appellate Counsel for Appellant: Colonel Nikki A. Hall, Lieutenant Colonel...»

«MINUTES VILLAGE COUNCIL MEETING KEY BISCAYNE, FLORIDA TUESDAY, OCTOBER 28, 2003 COUNCIL CHAMBER 560 CRANDON BOULEVARD 1. CALL TO ORDER/ROLL CALL OF MEMBERS: The meeting was called to order by the Mayor at 7:00 p.m. Present were Councilmembers Martha F. Broucek, Carol Diaz-Castro, Mortimer Fried, James L. Peters, Robert L. Vernon, Vice Mayor Jorge Mendia and Mayor Robert Oldakowski. Also present were Village Manager Jacqueline R. Menendez, Village Clerk Conchita H. Alvarez and Village Attorneys...»

«VIKINGS AND TIGERS: Finland, Sweden, and adoption of environmental technologies in Southeast Asia's pulp and paper industries David A. Sonnenfeld Department of Sociology, Washington State University Published: Journal of World-Systems Research, Vol. 5(1), 1999, pp. 26-47 -iVIKINGS AND TIGERS: Finland, Sweden, and adoption of environmental technologies in Southeast Asia's pulp and paper industries 1 Abstract This paper examines structural dimensions of the influence of core-periphery relations...»

«“Science Park or Innovation Pole? Descriptive results of a questionnaire investigation about physical and virtual locations” Fabrizio Conicella – Elisa Salvador May 2012 BIOINDUSTRY PARK SILVANO FUMERO S.p.A. • Bi.P.Ca. S.p.A. • 10010 Colleretto Giacosa TO • Via Ribes 5 • Tel +39 0125 561311 • Fax +39 0125 538350 www.bioindustrypark.eu • e-mail: bipca@bioindustrypark.it • Capitale Sociale i.v. Euro 12.581.663, al 31/12/2009 Euro 12.581.663 Registro imprese Torino n. 799923...»

«Sustainability 2014, 6, 7666-7688; doi:10.3390/su6117666 OPEN ACCESS sustainability ISSN 2071-1050 www.mdpi.com/journal/sustainability Article Identification and Characterization of Particulate Matter Concentrations at Construction Jobsites Ingrid P. S. Araújo 1,†, Dayana B. Costa 2,†,* and Rita J. B. de Moraes 2,† Department of Structural and Construction Engineering, School of Engineering, Federal University of Bahia, Aristides Novis, 2, Federação, Salvador 40210-630, Brazil; E-Mail:...»

«Mijn bezoek aan Jan Holland in den zomer van 2016 Een normatieve analyse van het werk van Jan Holland Bachelorscriptie Letterkunde Eerste Versie Cecile Collin s4347870 Eerste lezer: Dr. Rob van de Schoor Tweede lezer: Prof. Dr. Jos Joosten Nederlandse Taal en Cultuur 4 juli 2015 Inhoudsopgave Abstract 3 Inleiding 3 Methode 5 Deelonderwerp 1: vrouwenemancipatie 7 Deelonderwerp 2: godsdienst 11 Deelonderwerp 3: onderwijs, kunst en wetenschap 15 Deelonderwerp 4: politiek, oorlog en macht 21...»

«University of Bolton Financial Statements 2014-15 Contents Page Operating and Financial Review 2014-15 2 Members of the Board of Governors 18 Principal Advisers to the University 20 Statement of Corporate Governance and Control 21 Responsibilities of the Board of Governors 27 Independent Auditor’s Report to the Governing Body of the University of Bolton Statement of Principal Accounting Policies 29 Income and Expenditure Account 33 Balance Sheet 34 Cash Flow Statement 35 Statement of...»

«Risk Attitudes, Development, and Growth ∗ Evidence from Experiments in 30 Countries Ferdinand M. Vieider† Thorsten Chmura‡ Peter Martinsson§ February 6, 2016 Abstract We measure risk attitudes in 30 different countries in a controlled, incentivised experiment with university students (N=2939). At the aggregate level, we find a strong and highly significant negative correlation between risk tolerance and income per capita. We exclude systematic selection effects of students by...»

«This opinion is not intended for publication UNITED STATES BANKRUPTCY COURT NORTHERN DISTRICT OF OHIO In re: ) Case No. 01-17917 ) PHILIP J. TROPKOFF and ) Chapter 7 TRACI A. TROPKOFF, ) Debtors. ) Adversary Proceeding No. 01-1460 ) WALDEMAR J. WOJCIK, ) Judge Arthur I. Harris CHAPTER 7 TRUSTEE, ) Plaintiff, ) ) v. ) ) HOMEQ SERVICING CORP., et al., ) Defendants. ) MEMORANDUM OPINION AND DECISION The Chapter 7 Trustee filed this Adversary Proceeding in order to determine the validity, priority,...»

<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.