FREE ELECTRONIC LIBRARY - Abstracts, online materials

Pages:     | 1 |   ...   | 4 | 5 || 7 | 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 6 ] --

Work along these lines is presented in [Bertossi, et al., 2006]. If tasks are assigned in descending order of RM priority, the assignment of a new task can never affect the schedulability of a previously assigned task (since all previously assigned tasks would be of higher priority than the one currently being assigned).

We have assumed in our discussion that the system is able to rapidly carry out the feasibility check of tasks as they arrive. A variation on this is where the incoming tasks are queued and there is a central scheduler which carries out the feasibility check every so often on the tasks that it finds in that queue [Manimaran and Murthy, 1998]. When faced with multiple tasks to be scheduled, the scheduler can either assign them one by one (without any concern for how the scheduling of one task may affect the schedulability of others) or use some backtracking strategy. This strategy checks if scheduling one task creates constraints that make it impossible to schedule some other task; if so, it backtracks and tries to revise the schedule of the first task to relax such a constraint.

Another variation consists of the classification of backup tasks into passive and active. A passive task is constrained to execute within the interval between the finishing time of its primary and its deadline. If this interval is very short, then the available slack may not be sufficient to obtain a feasible schedule in many cases. Hence, if a passive backup cannot be feasibly scheduled, the algorithm might consider reclassifying it as active; this immediately relaxes the constraint that the backup be scheduled entirely after the scheduled finishing time of its primary. The algorithm can then make another attempt to assign it.

Further, note that we are assuming that an active backup needs to continue executing through to completion. We do need to start such a backup before we know whether or not its primary has failed; however, if such information becomes available before its active backup has finished executing, the backup can safely be aborted, thus yielding additional slack in the schedule. We can also split what would have been an active backup into two parts: the part that is scheduled for before the finish time of its primary and the rest. The former can remain designated an active backup while the latter can be made passive. An approach along these lines is outlined in [Tsuchiya, et al., 1995a, Tsuchiya, et al., 1995b].

In the approach covered above, any processor which does not carry the primary is a candidate for being allocated the backup. An alternative that has been suggested is that processors be organized into multiple groups with the proviso that both the primary and the backup must be allocated to processors within the same group [Al-Omari, et al. 2001]. Groups may be formed either statically or dynamically; dynamic groups offer somewhat better guarantee rates.

Finally, there is the use of checkpointing [Ahn, et al. 1997, Speirs and Barrett, 1989]. A real-time task can checkpoint as it goes. Every so often, it records its state. If its processor should fail and the checkpoint is preserved by putting it in safe place, the backup can resume execution not from the beginning but from the latest checkpoint. Evaluation of such an approach should include the overhead for taking checkpoints.

6.2 Aperiodic and Non-Preemptive Tasks We now turn to scheduling a workload of aperiodic and non-preemptive tasks [Ghosh, et al., 1997].

Here, tasks arrive dynamically and the system has to build its schedule as it goes along. Since the workload is not known in advance, it cannot be checked for schedulability. Instead, when a task arrives (along with information about its worst-case execution time, and its deadline), the system determines if it has enough time to guarantee its execution. If so, the task is accepted;

if not, the task is rejected, and is no longer its responsibility.

As before, we use backup copies for fault-tolerance: the system will not guarantee a task unless it can feasibly schedule both its primary and backup.

The algorithm starts by scheduling the primary copy of the incoming task. As before, one can use a first-fit approach to choose the processor that will be allocated the primary. Alternatively, some other order may be chosen in which to try the processors. If we find a processor that can feasibly schedule this primary, we try to identify a processor that can feasibly schedule its backup according to Principles A1 to A3 listed in Section 1. We evaluate the goodness of the backup scheduling on each of the processors (except, obviously, the one that has been assigned the primary) according to a figure-of-merit function which we will describe next. The backup is assigned to whichever processor maximizes this figure-of-merit. If no such processor is found, we have to look for some other processor which can accept the primary (and satisfying A1 to A3) and repeat this process to find a home for its backup. If we are unable to find such a pair of processors for the primary and backup copies, the system rejects the task.

The figure-of-merit mentioned in the algorithm arises because there are two, often contradictory, impulses driving the scheduling of the backup. One is to schedule the backup as late as possible. This is important because the backup can be deallocated once the primary succeeds;

having a long interval between when the primary succeeds and when the backup was scheduled to start gives the system a better opportunity to find something else to fill the slot vacated by the backup. The second impulse is to exploit the conditional transparency of backups and maximize the overlap between this backup and any others that may already be scheduled. Quite often, maximizing the overlap may lead us to schedule the backup for earlier than we otherwise might; while delaying the backup by as long as possible may reduce the overlap that we may otherwise be able to exploit.

This issue can be resolved by creating a figure-of-merit, composed of a weighted sum of the

two quantities:

F = α(tprimaryfinish − tbackupstart) + (1 − α)overlap length (12) where α ∈ [0, 1] is a tuning parameter. Users may experiment with various tuning parameters for the type of workloads they anticipate in order to pick a suitable one.

6.3 Integrating Task Cost Functions

We present now a dynamic programming approach [Krishna and Shin, 1986]. This is an offline technique, in which two schedules are constructed for each processor. The first is the backup schedule and the second a primary schedule. In the absence of faults, the primary schedule is executed. When a backup needs to be activated, this is done according to the backup schedule, with primary tasks having to give way to the backups. The primary schedule is constructed by invoking a dynamic programming algorithm, taking into account the notification time of each backup, i.e., the time by which the system will be made aware of the need to execute that backup.

This dynamic programming approach allows the user to introduce cost functions for the various tasks. That is, the aim is not just to meet all real-time deadlines; in addition, each task Ti has a cost function Fi(Ri) of its response time, Ri, which represents the cost to the system of having such a response time. Such cost functions are relevant when the computer is in the control of some cyber-physical control system. In such a case, the computer is in the feedback loop of the controlled process and any incremental delay of the controller potentially contributes to a degradation in the quality of control provided. Such degradation is captured in the form of cost functions. It is beyond the scope of this paper to describe how these functions may be obtained: see [Krishna and Shin, 1987, Shin and Cui, 1995, Shin and Krishna, 1987] for ways by which the control dynamics of the controlled process can translate into cost functions.

Such cost functions can be used to calculate the total cost of a schedule: this is given by Fi(Ri).

i As a foundation upon which to construct fault-tolerant schedules, the dynamic programming approach can use any scheduling algorithm which consist of a task assignment part (Algorithm Alloc) and a uniprocessor scheduling part (Algorithm Sched) which is responsible for scheduling on each processor the tasks assigned to it by Alloc. Both Alloc and Sched may take both task deadlines and cost functions into account: they are heuristics which seek to reduce the total cost of the schedule while ensuring that all deadlines are met. These heuristics are not the focus of our discussion; rather, we are concerned with how they can be used as subroutines to obtain fault-tolerant schedules. That is, our focus is the fault-tolerant component which calls these subroutines.

The tasks assigned to a processor are numbered in order of their notification time. In what follows, we will concentrate on showing how to schedule tasks on some processor, P: the same activity will be carried out independently for every other processor in the system. Denote by Pζ(1), Pζ(2), · · ·, Pζ(θ) the θ primaries and by Bψ(1), Bψ(2), · · ·, Bψ(γ) the γ backups assigned to processor P, respectively, where ζ(i) and ψ(i) denote the tasks whose primaries and backups are assigned to P, respectively. The backup task cost functions are all zero: the focus of their scheduling is on meeting deadlines.

Once a processor has been assigned a set of primary tasks, the holes in its schedule can be identified. A hole is a interval of time in which it is impossible to schedule any of the primaries allocated to that processor due to their release times and deadlines. For example, if we have a processor assigned a single aperiodic task whose release time is r and absolute deadline is d, then the following intervals are holes created by that task: [0, r) and (d, ∞). The hole resulting from a set of tasks is the intersection of the holes induced by each of them. Holes are important in that backups can be scheduled on them without affecting the primary schedule. Assume that the set of primaries and backups assigned to a given processor are denoted by P and B, respectively.

We can improve the efficiency of the scheme by tuning Algorithm Sched to schedule backups in the holes to the extent possible and to allow it to overlap backups according to Principle A2. Let νBψ(1), νBψ(2), · · ·, νBψ(γ) be the notification times of backups respectively assigned to that processor. For convenience, set νbψ (0) = 0, and νbψ(γ+1) = ∞. The algorithm generates a sequence of γ + 1 primary schedules, Sp0, Sp1, · · ·, Spγ, and then pieces them together.

The algorithm is shown in Figure 7. In Step 1, the task allocation algorithm, Alloc, is called, to assign tasks to processors. Such an assignment specifies the holes in the schedule of each processor.

In Step 2, the uniprocessor scheduling algorithm is executed on a task set comprising the primaries and all the backups. The position of the backups in this schedule is recorded in a backup schedule, SB. The position of the primaries in the schedule is recorded in schedule Sp0.

In Step 5 (some auxiliary steps are taken in Steps 3 and 4), we move to the first notification time, νBψ(1). By this time, the system will know whether or not the primary (on some other processor) associated with backup Bψ(1) has failed. If not, then there is no need to reserve space in the schedule for backup Bψ(1): any space reserved for Bψ(1) beyond time νψ(1) in Sb can be released. We run algorithm Sched on a workload comprising the primary workload not scheduled over [0, νbψ(1) ]. Such scheduling is done based on the assumption that the processor is not available to the primaries over the periods occupied by backups in Sb. The schedule of tasks is obtained and recorded as Sp1.

We do the same thing with respect to each of the remaining notification times as we proceed through the Step 5 loop. After exiting this loop, in Step 6, we schedule any remaining primary workload and end the algorithm.

The output of the algorithm is a backup schedule and and a set of primary schedules, Sp1, Sp2, · · ·, Spγ.

1. Record the holes as defined by the task allocation.

–  –  –

6. If all the primary workload has not yet been scheduled, schedule the remaining primary workload beyond νBψ(γ).

If any primary task cannot be scheduled to finish before its deadline, declare failure and exit.

Figure 7: Dynamic Programming Fault-Tolerant Scheduling Algorithm

–  –  –

Figure 8: Example of Schedules Followed by Dynamic Programming Algorithm

During operation, we use these schedules as a template as follows in the absence of any faults:

over the interval [νBψ(i), νBψi+1 ), we execute primaries according to schedule Spi. If backup bi is the first one to have to be activated, the machine will follow Spi throughout and never switch to Spi+1. This is illustrated in Figure 8.

To illustrate this algorithm, consider the following example. Assume that primaries of aperiodic tasks T1, T2, T3 and T4, and backups of aperiodic tasks T5, T6, T7 and T8 have been assigned to some processor. Assume also (just for this example) that the execution time of the primary and backup copies of a task are the same and that the backups are not allowed to overlap since their primaries have been assigned to the same processor. We now show how a schedule for that processor is constructed.

–  –  –

We first set up the schedule of backups: for this, schedule the entire primary and backup tasks and record the position of the backups in this schedule. Next, we list the positions of the primaries in this schedule: this becomes contingency schedule Sp0. Note that because of deadline considerations, we are forced to run T4 ahead of T1, even though it would incur less cost to do T1 first. Similarly, we are forced to execute T3 before T2.

We now deal with what happens once we are notified that the backup of T6 will not have to be activated: this removes the need to reserve time in the schedule for T5. This information becomes available at time ν4 = 0. Once the need is removed to reserve the interval [8, 23] for the T5 backup, we now have the time to run task T1 first and then T4. This is contingency schedule Sp1.

Pages:     | 1 |   ...   | 4 | 5 || 7 | 8 |

Similar works:

«WATER TREATMENT 404 CONTINUING EDUCATION PROFESSIONAL DEVELOPMENT COURSE WT404  9/1/2016 (866) 557-1746 Fax (928) 468-0675 Printing and Saving Instructions The best thing to do is to download this pdf document to your computer desktop and open it with Adobe Acrobat DC reader. Adobe Acrobat DC reader is a free computer software program and you can find it at Adobe Acrobat’s website. You can complete the course by viewing the course materials on your computer or you can print it out. We give...»

«Sun, L. (2014) The role of diversity on freedom of speech in democratic societies. International Journal of Sustainable Human Development, 2(2), 44-51. The role of diversity on freedom of speech in democratic societies Lasa Sun Macquarie University, Australia, lasa.sun@students.mq.edu.au There is no doubt that freedom of speech plays an important role in the process of democratization. Freedom of speech is a guarantee to citizens to participate effectively in the working of democracy. Likewise,...»

«1 Protokół 66. posiedzenia Komisji Standaryzacji Nazw Geograficznych poza Granicami Rzeczypospolitej Polskiej, które odbyło się 7 grudnia 2011 roku w gmachu Głównego Urzędu Geodezji i Kartografii przy ul. Wspólnej 2 w Warszawie. W posiedzeniu uczestniczyli członkowie Komisji  według załączonej listy obecności (zał. 1).Wstępny porządek obrad obejmował: 1. Zagajenie.2. Przyjęcie protokołu 65. posiedzenia Komisji z dnia 23 listopada 2011 roku. 3. Sprawy bieżące. 4....»

«Market Discipline and Bank Charter Value: The Case of Two Safe Banking Industries Mamiza Haq, Amine Tarazi, Necmi Avkiran, Ana Rosa Fonceca To cite this version: Mamiza Haq, Amine Tarazi, Necmi Avkiran, Ana Rosa Fonceca. Market Discipline and Bank Charter Value: The Case of Two Safe Banking Industries. 2013. hal-00955135 HAL Id: hal-00955135 https://hal-unilim.archives-ouvertes.fr/hal-00955135 Submitted on 3 Mar 2014 HAL is a multi-disciplinary open access L’archive ouverte pluridisciplinaire...»

«INTERNATIONAL MARITIME ORGANIZATION E IMO ASSEMBLY A 24/Res.982 24th session 6 February 2006 Agenda item 11 Original: ENGLISH Resolution A.982(24) Adopted on 1 December 2005 (Agenda item 11) REVISED GUIDELINES FOR THE IDENTIFICATION AND DESIGNATION OF PARTICULARLY SENSITIVE SEA AREAS THE ASSEMBLY, RECALLING Article 15(j) of the Convention on the International Maritime Organization concerning the functions of the Assembly in relation to regulations and guidelines concerning maritime safety, the...»

«1 COGNITIVE PROCESSES AND THE LEARNING OF PHYSICS PART II: MEDIATED ACTION Valerie K. Otero School of Education University of Colorado at Boulder Boulder, CO USA To appear in: Proceedings of the International School of Physics Enrico Fermi, edited by M. Vicentini and E.F. Redish (IOS Press, Amsterdam), July, 2003, Varenna, Italy.1. Introduction Socio-cultural theoretical perspectives have been used within the mathematics and science education research communities for over 20 years [1] [2] [3]...»

«Compaq Computer Corporation Phoenix Technologies Ltd. Intel Corporation Plug and Play BIOS Specification Version 1.0A May 5, 1994 This specification has been made available to the public. You are hereby granted the right to use, implement, reproduce, and distribute this specification with the foregoing rights at no charge. This specification is, and shall remain, the property of Compaq Computer Corporation (Compaq) Phoenix Technologies LTD (Phoenix) and Intel corporation (Intel). NEITHER...»

«1 Authority, Liberty, and Responsibility in Milton’s Paradise Lost GEORGE B. MARTIN know of only one reason for doing literary criticism or literary I exegesis: to enrich a reader’s response to the work. This essay seeks to focus the reader’s attention on authority, liberty, and responsibility in Milton’s Paradise Lost. When I first read the poem about Milton’s conception of liberty, my response was not an eccentric one, as it turned out, for it was shared by some mighty influential...»

«Badger Pass Ski Area, Source: Kenny Karst, 2008. Badger Pass Ski Area Determination of Eligibility Final – August 13, 2009 Yosemite National Park, California August 2009 Prepared for Delaware North Company Yosemite National Park, California Prepared by 724 Pine Street, San Francisco, California 94108 415.362.5154 / www.page-turnbull.com Badger Pass Ski Area Yosemite National Park This Page is left intentionally blank Determination of Eligibility Page 2 STATE OF CALIFORNIA – THE RESOURCES...»

«This chapter appears (with neater figures) as: Scholl, B. J., & Leslie, A. M. (1999). In E. Lepore & Z. Pylyshyn (Eds.), What is Cognitive Science? Oxford: Blackwell.Explaining the Infant’s Object Concept: Beyond the Perception/Cognition Dichotomy Brian J. Scholl and Alan M. Leslie 1. Introduction Some of the most exciting research in recent cognitive science has involved the demonstration that young infants possess a remarkable array of discriminative abilities. Infants a few months old have...»

«The Dynamical Theory of Tilings and Quasicrystallography E. Arthur Robinson, Jr. 1 Department of Mathematics The George Washington University Washington, DC 20052 ABSTRACT A tiling x of Rn is almost periodic if a copy of any patch in x occurs within a fixed distance from an arbitrary location in x. Periodic tilings are almost periodic, but aperiodic almost periodic tilings also exist; for example, the well known Penrose tilings have this property. This paper develops a generalized symmetry...»

«PANDORA DAC ROMULUS CD Player-DAC Owner’s Manual Aesthetix Audio Corporation 5220 Gabbert Rd., Suite A ♦ Moorpark, CA. 93021 Phone: (805) 529-9901 The lightning flash with arrowhead symbol, within an equilateral triangle, is intended to alert the user to the presence of uninsulated “dangerous voltage” within the product’s enclosure that may be of significant magnitude to constitute a risk of electric shock to persons. The exclamation point within an equilateral triangle is intended to...»

<<  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.