FREE ELECTRONIC LIBRARY - Abstracts, online materials

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

Also, the order in which we try the processors need not be the same throughout: we could simply try them randomly. However, it has been observed that first-fit is generally more successful in making task assignments than, say, heuristics which try to assign the next task to the processor with the lightest load (such an algorithm aims to balance the processor utilizations).

It is a common mistake to assume that the highest-priority task is always the one of greatest practical importance to the application. That is not necessarily true. The rate monotonic algorithm always assigns priority in order of the frequency with which a periodic task is executed. Under this assumption, and the assumption that the task deadline coincides with its period (i.e., that a particular iteration of a task has to be completed before the

next iteration arrives), it can be shown that this is an optimal static-priority uniprocessor scheduling algorithm:

static-priority because the relative priority of tasks are fixed for all time; optimal in that if this algorithm cannot find a feasible schedule for a set of tasks on a given single processor, there is no other static priority algorithm which can. By contrast, practical importance to the application depends on the needs of the application. There is no necessary link between the period of a task and its contribution to the application.

The reason is that in first-fit, the later-numbered processors tend to be less heavily loaded, so that long tasks are more likely to find themselves a home in them.

6.1.1 All Periods Equal We start with a particularly simple case: one in which all the tasks are periodic, have the same period, and are released at the same time [Oh and Son, 1992]. While this is simple, it is by no means uncommon in real-time systems. This approach is designed to protect against up to one failure.

The idea is to assign one copy of each task to processors, using, for example, the First-Fit procedure, with the tasks being assigned in decreasing order of their execution times. Then, provide each processor, P, with a twin and assign to that twin all the tasks assigned to P. In other words, processors are grouped in pairs and both processors in a pair are assigned exactly the same tasks. Checking that a set of tasks assigned to the same processor can all meet their deadlines is very simple when all tasks are released together and have the same period: simply check that the total execution time of the assigned tasks is not greater than their (common) period.

Once the tasks have been assigned, they can be scheduled. The tasks assigned to the same processor are scheduled in decreasing order of execution time. Then, a swapping procedure is carried out within the schedule of tasks in each pair to ensure that each task has a primary copy on one processor in a pair and a nonoverlapping backup copy on the other.

The swapping procedure proceeds as follows for each pair. For definiteness, label one processor PA and the other PB. Suppose the total length of the schedule for each processor in some pair is L. Let the task completion times be f1 ≤ f2 ≤ · · · ≤ fn. (Without loss of generality, number the tasks according to their finishing times in this schedule; that is, the finishing time of Ti is fi.) Let k be the largest number such that fk ≤ L/2. All tasks in the set τA = {T1, · · ·, Tk} are considered to be primary tasks in processor PA and backups in processor PB; tasks in the set τB = {Tk+1, · · ·, Tn} are considered to be primary tasks in processor PB and backups in processor PA.

Now, we proceed to swap the positions of the tasks in the schedule of processor PB. Move all the tasks in τB to the beginning of its schedule; shift the tasks in τA to after those in τB. It is possible to prove that the tasks will not overlap in time on the two processors.

It is trivial to see that each pair of processors can suffer up to one failure without any deadlines being missed. However, such a pairing approach cannot use backup overloading and this can be expected to require somewhat more processors than other approaches.

As an illustration, consider the task set with execution times e1 = 7, e2 = 5, e3 = 4, e4 = 3, e5 = 1. The common period of all the tasks is P = 20; note that all these tasks will (just about) fit on a single processor. Assign one copy of each task on each member of a processor pair.

–  –  –

their finishing times are f1 = 7, f2 = 12, f3 = 16, f4 = 19, and f5 = 20. f1 is the largest time that is no greater than ⌊P/2⌋ = 10. So, we label T1 on Processor 1 as the primary copy and all other tasks on that processor as backups. Conversely, the copies of tasks T2, T3, T4 and T5 assigned to Processor 2 are the primaries and those assigned to 1 are secondaries.

We now swap task positions in processor 2 so that the primaries on that processor are all scheduled ahead of the secondary. This is done by moving T1 to the end of the schedule and sliding the schedule for T2, T3, T4, and T5 up in time. At this point, we are done. See Figure 5.

6.1.2 General Task Periods We now relax the condition that all task periods are equal and introduce the fault-tolerant assignment algorithm of [Bertossi, et al., 1999]. As before, tasks have primary and backup

copies associated with them. These are defined as follows:

• Active or Primary Tasks: These are the tasks to be run in the absence of a failure.

• Backup Tasks: These will be activated upon a processor failure that affects their corresponding active task.

– Passive Backup Tasks: These tasks can be scheduled so that they start executing only after the scheduled completion time of their primary. As a result, they can remain dormant until that primary has failed.

– Active Backup Tasks: If the schedule is so tight that we cannot find time to schedule the tasks as passive backups, they must be scheduled as active backups. That is, they must start running even before we know that their primary has failed since there will be no time to execute them to completion if we wait until we know that the primary task has failed.

For the reasons mentioned earlier, we will restrict ourselves here to dealing with just one processor failure6. In such a case, once that failure has happened, we know that we will not be This does not mean that we only allow for one failure for the lifetime of the computer system. Rather, we assume that the system will only have to deal with one failure at a time; that a second failure will not come expected to deal with any other failure for the moment; hence, no backup (including active backups) whose primary is not on the failed processor need be executed. For this reason, to check the schedulability of active backups on any processor, we only need to ensure that

• For the no-failure case: All the primaries and active backups on that processor can execute without any deadlines being missed.

• When a failure happens, we are not required to be capable of responding to a second failure. So, we can immediately cancel the execution of all active backups and ignore the schedulability needs of all passive backups whose primaries are not on the failed processor.

By definition, a passive backup only executes if its primary has failed. This is only guaranteed to be known after the primary’s scheduled completion time. Hence, a primary backup may only be scheduled in the interval between the scheduled finishing time of its primary and its deadline.

The fault-tolerant assignment algorithm is shown in Figure 6. The logic behind this algorithm is quite straightforward. We want to be able to sustain up to one processor failure at any one time. When assigning a primary task, we want to ensure that the processor to which it is assigned has the ability to run this task together will all the active backups assigned to it as well as the passive backup sets that could possibly be activated. For each of the other m − 1 processors in the system, there is a set of passive backup tasks that must be activated on the failure of that processor.

Each backup task is classified as active or passive depending on the scheduling of its corresponding primary. If the primary finishes so late that there is not enough time left for a backup task to be initiated and then complete before its deadline, then the backup must be initiated even before we know that the primary has failed. Such a backup is therefore designated as active. All others are designated as passive.

An active backup must run only as long as:

• All processors are up, or

• One processor is down, and that processor was assigned the primary copy corresponding to that active backup.

Hence, when checking the schedulability of an active backup, we only check that it is schedulable for one of these two cases. Similarly, when checking for the schedulability of passive backup βi, we only need to check that the processor to which it is assigned can meet all the deadlines of its primaries as well as of those backups whose primaries are on the same processor as that of πi, the primary “partner” of βi.

Let us now turn to how the schedulability tests are done. Note that this problem differs from the traditional RM model in which task deadlines equal their periods; in our case, passive about before the first has been dealt with and the system schedule has been stabilized with, if necessary, the reassignment of tasks. That is, the second failure will not happen until the “memory” of the first failure has faded away.

Figure 6: Fault-Tolerant Assignment Algorithm backups may not start before the scheduled finishing time of their primaries. So, we cannot use the response time expression in Equation (1) to judge schedulability. However, the expression that we do end up with has the same logical foundation as (1).

We start by upper-bounding the cumulative work, ω(T, t), that arrives at some single processor, P, by task set T during any interval [0, t]7. Let Π be the set of primaries, βa the set of active backups, and βp the set of passive backups, assigned to processor P. Denote the finishing time of πi, the primary copy of Ti, by fi. Its deadline (relative to when it was released) is equal to the period, Pi. Denote the WCET of the primary of task Ti by ei and that of its backup by

ξi. Then, we can write:

–  –  –

Let us justify Equation (9) by examining its rhs term by term. The first term on the rhs is the contribution of the primary tasks assigned to processor P. The worst-case contribution of this term obviously occurs when the first iteration of all such tasks are released at time 0 (equivalently, we can say that the phasings of the primaries are all zero). The second term is the contribution of the active backups, assuming again that their phasings are zero. The third term accounts for the passive backups in set T. Now, in the worst case, the phasing of the primaries associated with these backups can be such that the first iterations of these primaries are scheduled (on whichever processor to which they have been assigned) to complete at time 0;

hence, we can assume that all the passive backups corresponding to these first iterations become eligible to execute starting at time 0. If t ≤ fi, then there can be only one such copy of each backup task which can be released over [0, t]; if t fi, this number is equal to 1 + ⌈(t − fi)/Pi⌉.

In order for task Ti ∈ T to meet its deadline, it is sufficient to have ω(T, t) ≤ 1 for some t ≤ Pi. This is justified as follows. The worst case response time for any task occurs when it is released at the same time as all the higher-priority tasks (whether primary or backup) in the system. So, if we assume that the first iteration of all tasks are released at time 0, the worst-case response time of any task is that seen by its first iteration. If ω(T, t) t for some t = τ, this means the total work that came in over the interval [0, t] was less than t; hence the processor must have been idle over some part of that interval. Hence, all the iterations that were released at time 0 must have been done by time τ (since otherwise the processor would not be idle). If τ ≤ Pi, then that must mean that the first iteration of task Ti met its deadline. If ω(T, t) = t for some t = τ, then all the tasks issued over [0, τ] are done by time τ and if τ ≤ Pi, the first iteration of Ti is done by its period.

From this, we can now write sufficient conditions for schedulability for each of the following two cases. For the fault-free case, no passive backups are activated; the task set Tfault−free that Do not confuse ω(T, t) with W(T, t) (encountered in Section 4.2). The former is the cumulative work that arrives during the interval [0, t]; the latter is the cumulative unfinished work at time t, regardless of when that unfinished work actually arrived at the system.

processor P needs to be able to run is the primaries and the active backups that have been assigned to it. For this case, we must have

–  –  –

The remaining case to consider is when some processor Pj (Pj = P) fails. This will require any passive backups (assigned to P) of primaries scheduled on Pj to be capable of running.

As mentioned earlier, once the system knows, at time tj, that Pj has failed, it has to run backups associated with primaries assigned to Pj, and not run any other backups (including active backups of other tasks). (Before the system knows that Pj has failed, it obviously has to keep running all active backups). Let us denote this set of tasks to be scheduled on P by TPj −fails: this set will not assume that any other backups execute after time tj.

The condition to be satisfied to ensure schedulability on P is of the same form as Equation (10), except that the task set is different:

–  –  –

One can think of several variations on this theme. We have already considered the possibility of assigning tasks in a different order to that of their RM priorities. This may result in more successful task assignments; however, the schedulability checks will be more time-consuming.

Pages:     | 1 |   ...   | 3 | 4 || 6 | 7 |   ...   | 8 |

Similar works:

«Public Disclosure Authorized Document of The World Bank FOR OFFICIAL USE ONLY Report No: PAD1273 INTERNATIONAL DEVELOPMENT ASSOCIATION Public Disclosure Authorized PROJECT APPRAISAL DOCUMENT ON A PROPOSED CREDIT IN THE AMOUNT OF SDR 21.4 MILLION (US$ 30 MILLION EQUIVALENT) Public Disclosure Authorized TO THE LAO PEOPLE’S DEMOCRATIC REPUBLIC FOR A POWER GRID IMPROVEMENT PROJECT June 2, 2015 Public Disclosure Authorized Energy and Extractives Global Practice East Asia and Pacific Region This...»

«THE PROJECT IS FUNDED BY THE EUROPEAN UNION Table of Contents Introduction Companies FOOD&BEVERAGES pages Ltd. “GFC Kula” 5-6 Ltd. “Aromaproduct” Ltd. “Marneuli Food Factory” Ltd. “Nergeta” Ltd. “Geoplant” Cooperative “Chai Surneli” Cooperative “Taphli Sachino” Cooperative “Vardisubani 2014’’ Cooperative “Khechili” Ltd. “Breti” Cooperative “Alvani” Ltd. “Paliastomi 2004” JSC “Healthy Water” JSC “Sarajishvili” Ltd. “Winery Khareba” 19...»

«BLS WORKING PAPERS U.S. Department of Labor U.S. Bureau of Labor Statistics Boston/New York Regional Office Women’s Increasing Wage Penalties from Being Overweight and Obese David Lempert, U.S. Bureau of Labor Statistics Working Paper 414 December 2007 All views expressed in this paper are those of the author and do not necessarily reflect the views or policies of the U.S. Bureau of Labor Statistics. Women’s Increasing Wage Penalties from Being Overweight and Obese* by David Lempert U.S....»

«Open Journal of Social Sciences, 2014, 2, 50-55 Published Online July 2014 in SciRes. http://www.scirp.org/journal/jss http://dx.doi.org/10.4236/jss.2014.27008 The Peculiarities of the Use of Electronic Course Books in the Process of Specialists’ Training at the University Gulshara Begarisheva Department of Computer Science and Computer Engineering at Caspian State University of Technologies and Engineering Named after S. Yesenov, Aktau City, The Republic of Kazakhstan Email: ggb_021@mail.ru...»

«Confronting context effects in intelligence analysis: How can mathematics help? Keith Devlin∗ July 15, 2005. INCOMPLETE DRAFT, UNDER DEVELOPMENT USE CAUTION WHEN OPENING AS CONTENTS MAY HAVE SHIFTED SINCE YOU LAST SAW THEM Abstract We use the interpretation of a key piece of information in the 2002 U.S. decision to invade Iraq to motivate a study of the role of context in decision making. Although our primary focus is intelligence analysis, our study seeks to adopt a mathematical approach....»

«viruses Review Subversion of the Immune Response by Rabies Virus Terence P. Scott and Louis H. Nel * Department of Microbiology and Plant Pathology, University of Pretoria, Pretoria 0002, South Africa; terence.scott@up.ac.za * Correspondence: louis.nel@up.ac.za; Tel.: +27-12-420-3622 Academic Editor: Alexander Ploss Received: 25 April 2016; Accepted: 12 August 2016; Published: 19 August 2016 Abstract: Rabies has affected mankind for several centuries and is one of the oldest known zoonoses. It...»

«The SPIRIT St Luke’s College NUMBER 6 TERM 2 Seek Truth and Justice St Luke’s Retreat Days The school holds Retreat days for all year groups. They are an integral part of Catholic school life. The term Retreat refers to time away from the normal school program where participants have the opportunity to reflect on their relationship with God. The emphasis is on students awareness of the presence of God in their lives. Retreats vary in style and duration. They include experiences of prayer,...»

«DEPARTMENT OF PUBLIC INFORMATION The United Nations Today asdf United Nations New York, 2008 Note: Every effort is made to keep basic information current up to the date of publication, including responsible officials, contact information, treaty ratifications, etc. All other data is current as of July 2007, unless stated otherwise. Published by the United Nations Department of Public Information Printed by the Publishing Section/DGACM United Nations Headquarters New York, NY 10017 www.un.org...»

«Southern Illinois University Carbondale OpenSIUC Research Papers Graduate School Spring 5-2011 Phonological Awareness and Reading Ability in Children Roberta J. Morton Southern Illinois University Carbondale, rmorton@siu.edu Follow this and additional works at: http://opensiuc.lib.siu.edu/gs_rp Recommended Citation Morton, Roberta J., Phonological Awareness and Reading Ability in Children (2011). Research Papers. Paper 94. http://opensiuc.lib.siu.edu/gs_rp/94 This Article is brought to you for...»

«Commission ANTONIO R. VILLARAIGOSA H. DAVlDNAHAT,. Ma),pr Chief Executtve Officer mid General A1anager LEE KANaN ALPERT, President EDITH RAlvlIREZ, 1~·c.Presider FORESCEE HOGAN-ROWLES JONATHAN PARFREY THOMAS S: SAYLES BARBARA E. MOSCHOS, Secretory October 23, 2009 The Honorable City Council clo Office of the City Clerk. Room 395, City Hall Mail Stop '160 Attention: Councilmember Jan Peny Chairperson, Energy and Environment Committee Honorable Members: Subject: Council File No, 09-1741 Status...»

«MILITARIA LONDON A Flintlock Sea Service Pistol, of A Percussion Saw-Handled Duelling A Flintlock Sea Service Pistol, of standard production specification, 30cm Pistol by Staudenmayer, converted from standard production specification, 30cm round steel barrel, flat border engraved flintlock, 26cm octagonal sighted barrel, round steel barrel, flat border engraved lock stamped with crowned ‘G.R’ and inscribed in gilt ‘Staudenmayer London’, lock stamped with crowned ‘G.R’, figured...»

«ISSN 0126-5539 PP2509/2/2007 W~LK?Z?~ @&@[1@@D PERSATUAN GEOLOGI MALAYSIA Newsletter of the gical Society of Malaysia 'Petrified Flow Spectacular Speleothems at Tambun Caves, /poh' By Dr Ng Tham Fatt Awarded the Second Prize in the 2005 GSM Photo Competition Jilid !Volume 32 No 3 May June 2006 PERSATUAN GEOLOGI MALAYSIA (GEOLOGICAL SOCIETY OF MALAYSIA) MAJLIS (COUNCIL) 2006/07 Presiden (president) Lee Chai Peng Naib Presiden (Vice-President) Yunus Abdul Razak Setiausaha (Secretary) Askury Abd....»

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