FREE ELECTRONIC LIBRARY - Abstracts, online materials

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

The next notification time is ν6 = 20. Until this time, we have to allow for the possibility that we may have to activate all the backups. Suppose at this time, we are notified that the T6 backup will not need to run: this releases [24, 39] from the schedule. This allows us to move T2 ahead to execute over the interval [20, 35]. At 35, T4 resumes and completes execution at time

46. T3 is now scheduled for [45, 61].

This schedule is used until the next notification time at ν7 = 40. This notification (that T7 won’t need to run) allows T3 to be moved up a little.

The final schedule to be used if none of the backups has to be activated is constructed by stitching together the appropriate portions of the contingency schedules. Of course, if any backup needs to be activated, the system will stay on that contingency schedule without switching.

7 Voltage Scaling

Circuit delays in processors are a strong function of their supply voltage:

–  –  –

Voltage scaling has become important because in recent years, the energy consumption of processors has emerged as a major concern. Energy consumption causes heating which can increase the failure rate and strains energy resources such as batteries. Running a processor at lower voltage dramatically reduces its energy consumption. In real-time systems, we can scale voltage to ensure that tasks are completed just before their deadlines. Time in the schedule that is released when tasks complete ahead of their worst-case execution times can be reclaimed by running the processor at a lower voltage. There is a substantial literature in this area: see, for example, [Unsal and Koren, 2003] for a review.

By running the processor at a slightly greater speed than is required to just meet task deadlines, we can build up a reserve of time which can then be used to execute tasks which have been affected by failure. This time reserve can be exploited by the scheduling algorithms that we have desribed above. We present here an approach along the lines of [Santos, et al., 2009].

For example, consider using this approach to deal with transient faults in a system which schedules tasks according to the Rate Monotonic (RM) algorithm. Recall from Section 4 that the response time of a task is obtained by adding its own execution time to the amount of time the task has to wait for higher-priority tasks to finish executing on the processor.

–  –  –

Since all tasks must meet their deadlines, it follows that tmin = mini{ti} is the system-wide time redundancy available. This time can be used to execute backup copies of failing tasks or to retry failed versions. Note that since the execution of backup copies is a rare occurrence, we can assume that this will be done at the highest supply voltage possible, i.e., at the highest speed setting of processor.

ei can be controlled by suitably selecting the supply voltage (within limits): we therefore have a tradeoff between the energy consumption and the time redundancy available for faulttolerance.

Consider the following simple example to illustrate this. Suppose we have a two-task system, with the execution time and period being: (e1, P1) = (1, 5) and (e2, P2) = (3, 12), where the execution times are specified at the highest speed of the processor. Further assume that we plan to run both tasks at the same slowdown factor, s. (Note that this is just to simplify our discussion: the slowdown factor can not only be different for different tasks, it can also change during the course of execution of a task. Furthermore, s may in practical instances only be able to take one of a set of discrete values, since the supply voltage may not be continuously tunable.

None of these facts changes the basis for this approach.)

–  –  –

From this, we have tmin = min{5 − s, 12 − 4s}. By adjusting the slowdown, we can control the amount of time redundancy available, and obtain a tradeoff between the available fault-tolerance and the energy consumption.

Many variations on this basic theme are possible. For example, as mentioned above, only discrete frequencies may be available. Furthermore, there can be an overhead every time the voltage and clock frequency are adjusted. Also, the failure rate is linked to the voltage level, which may affect the voltage level chosen [Zhu, et al., 2004, Pop, et al., 2007].

8 Discussion Real-time systems are becoming ever more widely used in life-critical applications, and the need for fault-tolerant scheduling can only grow in the years ahead.

In this paper, we have outlined some techniques for fault-tolerant scheduling in homogeneous systems. All of these algorithms have one objective: to guarantee that, despite a certain maximum number of faults, the tasks will have enough hardware and time redundancy to meet their deadlines. Many interesting challenges in this field remain.

While we have focused on homogeneous systems, these techniques can also be used, with some modifications, in heterogeneous systems as well. In a heterogeneous system, tasks can have different execution times on different processors. Some processors may have specialized hardware (like fast array-handling capabilities) that render them more suited to some applications than to others. One can define a matrix of execution times of tasks to processors and make task assignment decisions (for both primary and backup copies) based on this information.

If nodes are heterogeneous, they are also likely to differ in their failure characteristics; both in the rate with which they fail and also the temporal characteristics of their transient failure.

Algorithms to take such characteristics explicitly into account while assigning primary and backup copies are worth developing.

Another area that deserves greater attention is the impact of the task assignment and schedule itself on reliability. As the processor workload increases, its static and dynamic power consumption both increase, thereby increasing its temperature. With an increase in operating temperature comes an increase in the failure rate. Such an effect is likely to be exacerbated by the move into ever finer feature sizes. Thermal-aware fault-tolerant scheduling has not yet attracted the attention it deserves.

Fault-tolerant scheduling algorithms have concentrated on the processor, ignoring other aspects of the system. This is especially the case with voltage scaling. However, the processor is but one part of a complex that also includes memory, the interconnection network, and I/O devices. Taking account of these dimensions can alter the framework in which the scheduler operates. For example, the size of the memory footprint of each task can constrain the task assignment procedure as well as limit the range of options available to energy management algorithms (which have to reduce the sum of the static and dynamic energy consumption).

To summarize, while there is already a significant body of work in the area of fault-tolerant scheduling of real-time systems, many interesting problems remain.

Acknowledgements Preparation of this work was supported in part by the National Science Foundation under grant CNS-0931035.

Appendix: Table of Symbols and Acronyms

–  –  –

References [Ahn, et al. 1997] AHN, K., KIM, J. and HONG, S. Fault-Tolerant Real-Time Scheduling Using Passive Replicas Pacific Rim International Symposium on Fault-Tolerance.

(December 1997), 98–103.

[Al-Omari, et al. 2001] AL-OMARI, R., MANIMARAN, G., and SOMANI, A.K. An Efficient Backup Overloading for Fault-Tolerant Scheduling of Real-Time Tasks. International Parallel Processing Symposium (2001) 1291–1295.

[Bertossi and Mancini 1994] BERTOSSI, A.A. and MANCINI, L.V. Scheduling Algorithms for Fault Tolerance in Hard Real-Time Systems. Real-Time Systems, 7, 1 (1994), 229–245. Vol. 7, No. 3, 1994, pp. 229–245.

–  –  –

[Bertossi, et al., 2006] BERTOSSI, A.A., MANCINI, L.V., and MENAPACE, A., “Scheduling Hard-Real-Time Tasks with Backup Phasing Delay,” IEEE Symposium on Distributed Simulation and Real-Time Applications (DS-RT), 2006.

[Burns, et al. 1996] BURNS, A., DAVIS, R., and PUNNEKAT, S. Feasibility Analysis of FaultTolerant Real-Time Task Sets. Eighth Euromicro Workshop on Real-Time Systems: EUROWRTS, (1996) 29–33.

[Caccamo and Buttazzo, 1998] CACCAMO, M. and BUTTAZZO, M., “Optimal Scheduling for Fault-Tolerant and Firm Real-Time Systems,” IEEE Conference on Real-Time Computing Systems and Applications (RTCSA), 1998.

[Cheng, 2002] CHENG, A. Real-time Systems: Scheduling, Analysis and Verification. WileyInterscience (2002).

[Cormen, et al., 2004] CORMEN, T.H., LEISERSON, C.E., RIVEST, R.L., and STEIN, T., Introduction to Algorithms. MIT Press (2004).

[Garey and Johnson, 1979] GAREY, M.S. and JOHNSON, D.S. Computers and Intractability:

A Guide to the Theory of NP-Completeness. W. H. Freeman. (1979).

[Ghosh, et al., 1997] GHOSH, S., MELHEM, R. and MOSSE, D. Fault-Tolerance through Scheduling of Aperiodic Tasks in Hard Real-time Multiprocessor Systems.

IEEE Transactions on Parallel and Distributed Systems, 8, 3 (March 1997) 272–283.

[Gonzalez, et al., 1997] GONZALEZ, O., SHRIKUMAR, H., STANKOVIC, J.A., and RAMAMRITHAM, K., “Adaptive Fault Tolerance and Graceful Degradation Under Dynamic Hard Real-time Scheduling,” IEEE Real-Time Systems Symposium, 1997, pp. 79–89.

[Graham 1969] GRAHAM, R.L. Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics, 17, 2 (March 1969), 416–429.

[Han, et al., 2003] HAN, C.-C., SHIN, K.G., and WU, J. A Fault-Tolerant Scheduling Algorithm for Real-Time Periodic Tasks with Possible Software Faults. IEEE Transactions on Computers, 52, 3, (March 2003), 363–372.

[Hillier and Lieberman, 2001] HILLIER, F.S. and LIEBERMAN, G.J. Introduction to Operations Research. McGraw-Hill (2001).

[Johnson, 1989] JOHNSON, B. The Design and Analysis of Fault-Tolerant Digital Systems.

Addision-Wesley (1989).

[Joseph and Pandya, 1986] JOSEPH, M. and PANDYA, P. “Finding Response Times in a RealTime System,” Computer Journal. 29, 5 (October 1986), 390–395.

[Kopetz, 1997] KOPETZ, H., Real-Time Systems, Kluwer Academic Publishers, 1997.

[Kopetz and Bauer, 2003] KOPETZ, H. and BAUER, G., “The Time-Triggered Architecture,” Proceedings of the IEEE, Vol. 91, No. 1, January 2003, pp. 112–126.

[Kopetz and Millinger, 1999] KOPETZ, H., and MILLINGER, D., “The Transparent Implementation of Fault Tolerance in the Time-Triggered Architecture,” Dependable Computing for Critical Applications (A. Avizienis, H. Kopetz, and J.C.

Laprie, editors), 1999, pp. 192–205.

[Kopetz and Ochsenreiter, 1987] KOPETZ, H. and OCHSENREITER, W., “Clock Synchronization in Distributed Real-Time Systems,” IEEE Transactions on Computers, Vol. C-36, 1987, pp. 933–940.

[Koren and Krishna, 2007] KOREN, I. and KRISHNA, C.M. Fault-Tolerant Systems, MorganKaufman (2007).

[Krishna and Shin, 1987] KRISHNA, C.M. and SHIN, K.G. Performance Measures for Control Computers. Performance ’83 (1983) [Krishna and Shin, 1986] KRISHNA, C.M. and SHIN, K.G. Scheduling Tasks with a Quick Recovery from Failure. IEEE Transactions on Computers, C-35, 5 (May 1986), 448–455.

[Krishna and Shin, 1997] KRISHNA, C.M. and SHIN, K.G. Real-Time Systems. McGraw-Hill (1997).

[Lehoczky, et al. 1987] LEHOCZKY, J.P., SHA, L., and STROSNIDER, J.K. Enhanced Aperiodic Responsiveness in Hard Real-Time Environments. IEEE Real-Time Systems Symposium (1987), 261–270.

[Liao, et al., 2005] LIAO, W., HE, L., and LEPAK, K.M., “Temperature and Supply Voltage Aware Performance and Power Modeling at Microarchitecture Level,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, No. 7, July 2005, pp. 1042–1053.

[Liberato, et al., 2000] LIBERATO, F., MELHEM, R. and MOSSE, D. Tolerance to Multiple Transient Faults in Hard Real-Time Systems. IEEE Transactions on Computers, 49, 9 (September 2000), 906–914.

[Liestman and Campbell, 1986] LIESTMAN, A.L. and CAMPBELL, R.H. A Fault-Tolerant Scheduling Problem. IEEE Transactions on Software Engineering, 12, 11 (November 1986), 1089–1095.

[Liu and Layland, 1973] LIU, C.L., and LAYLAND, J.W. Scheduling Algorihtms for Multiprogramming in a Hard Real-Time Environment. Journal of the ACM, 20, 1 (January 1973), 40–61.

[Liu, 2000] LIU, J.W.S., Real-Time Systems, Wiley (2000).

[Murthy and Manimaran, 2001] SIVA RAM MURTHY, C. and MANIMARAN, G. Resource Management in Real-Time Systems and Networks. MIT Press (2001).

[Manimaran and Murthy, 1998] MANIMARAN, G., and SIVA RAM MURTHY, C. A FaultTolerant Dynamic Scheduling Algorithm for Multiprocessor Real-Time Systems and its Analysis. IEEE Transactions on Parallel and Distributed Processing Systems, 9, 11 (November 1998), 1137–1152.

[Naedele, 1999] NAEDELE, M. Fault-Tolerant Real-Time Scheduling under Real-Time Constraints. International Workshop on Real-Time Computing Systems and Applications (RTCSA) (1999), 392–395.

[Nissanke, 1997] NISSANKE, N. Realtime Systems. Prentice Hall (1997).

[Oh and Son, 1992] OH, Y. and SON, S.H., An Algorithm for Real-Time Fault-Tolerant Scheduling in Multiprocessor Systems. Euromicro Workshop on Real-Time Systems (1992), 190–195.

[Pandya and Malek, 1998] PANDYA, M. and MALEK, M. Minimum Achievable Utilization for Fault-Tolerant Processing of Periodic Tasks. IEEE Transactions on Computers, 47, 10 (October 1998), 1102–1112.

[Petersen, 1997] PETERSEN, E.L. Predictions and Observations of SEU Rates in Space. IEEE Transactions on Nuclear Science 44, 6 (December 1997), 2174–2187.

–  –  –

[Pop, et al., 2007] POP, P., POULSEN, K.H., IZOSIMOV, V., and ELES, P., “Scheduling and Voltage Scaling for Energy/Reliability Trade-offs in Fault-Tolerant TimeTriggered Embedded Systems,” CODES+ISSS, 2007, pp. 233–238.

[Pradhan, 1996] PRADHAN, D.K. Fault-Tolerant Computer System Design. Prentice Hall (1996).

[Qin and Jiang, 2006] QUI, X. and JIANG, H. A Novel Fault-Tolerant Scheduling Algorithm for Precedence Constrained Tasks in Real-Time Heterogeneous Systems. Parallel Computing, 32, 5 (2006), 331–356.

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

Similar works:

«2014 Missouri Valley Regional Meeting Doubletree by Hilton Hotel Omaha, NE April 4 – 5, 2014 Host Chapter: Gamma Kappa, University of NE at Omaha Welcome to the 2014 Beta Alpha Psi Missouri Valley Regional Meeting We appreciate those chapters who took the time to attend this meeting and prepare presentations. We also thank the Board of Directors, the BAP Professional Partners, our guest speakers, our Faculty Advisor, Susan Eldridge, our BAP Professional Partners Liaisons, and our Chapter...»

«The Long-Short Wars: Evidence of End-of-Year Price Manipulation by Short Sellers JESSE BLOCHER, JOSEPH ENGELBERG, AND ADAM V. REED* ABSTRACT Thus this paper identifies one of the few situations in which there are clear, exante predictions about exactly how short sellers would manipulate prices, and in this setting, we find patterns consistent with end-of-year price manipulation by short-sellers. Specifically, we find stocks with high short interest experience abnormally low returns on the last...»

«Two attempts to understand PK M. Pitk¨nen a Email: matpitka@luukku.com. http://tgdtheory.com/public_html/. October 15, 2012 Contents 1 Introduction 1 2 Quantum measurement theory option 2 3 ”Too-good-to-be-true” option 3 4 How the intention to increase/decrease the number of 1:s or 0:s could be realized? 3 5 Summary 6 Abstract The question how intentional action is concretely realized is not only a key question in quantum consciousness theory but also in attempts to understand...»

«Sulfur Volcanism on Io Kandis Lea Jessup, Dept. Space Studies, Southwest Research Institute, 1050 Walnut St., Suite 400, Boulder, CO 80302 John Spencer, Dept. Space Studies, Southwest Research Institute, 1050 Walnut St., Suite 400, Boulder, CO 80302 Roger Yelle, Lunar and Planetary Laboratory, University of Arizona, Tucson, AZ 85271 Submitted to Icarus 3/12/06 Pages: 44 Tables: 3 Figures: 7 Sulfur Volcanism on Io Kandis Lea Jessup Southwest Research Institute 1050 Walnut, Suite 400 Boulder, CO...»

«Page 1 of 22 Vivitrol (naltrexone for extended-release injectable suspension) [Alkermes] DESCRIPTION: VIVITROL® (naltrexone for extended-release injectable suspension) is supplied as a microsphere formulation of naltrexone for suspension, to be administered by intramuscular injection. Naltrexone is an opioid antagonist with little, if any, opioid agonist activity. Naltrexone is designated chemically as morphinan-6-one, 17-(cyclopropylmethyl)-4,5-epoxy-3,14dihydroxy-(5α) (CAS Registry #...»

«STATE OF GEORGIA Page 2 of 46 DEPARTMENT OF NATURAL RESOURCES Permit No. GAG610000 ENVIRONMENTAL PROTECTION DIVISION TABLE OF CONTENTS Part 1: Coverage under this Permit 4 1.1 Coverage 4 1.2 Definitions 5 Part 2: Criteria for Receiving Waters 5 Part 3: Notice of Intent 6 3.1 Obtaining Coverage 6 3.2 Submittal Deadline 6 Part 4: Storm Water Management Program 6 4.1 Requirements 7 4.2 Minimum Control Measures 7 4.2.1 Public Education and Outreach 7 4.2.2 Public Involvement 8 4.2.3 Illicit...»

«The Roadside Inspection Selection System (ISS) for Commercial Vehicles Brenda M. Lantz Upper Great Plains Transportation Institute Michael W. Blevins and Thomas J. Hillegass Federal Highway Administration, Office of Motor Carriers March 1997 Acknowledgments The authors are grateful to the FHWA/OMC for providing the funding for this study and are especially appreciative to all those individuals who contributed their comments and suggestions as the study progressed. TABLE OF CONTENTS INTRODUCTION...»

«Sypheara theluciferianrevolution blog sypheara@gmail.com Spirit Box Construction Introduction In this document, I will be describing the process through which I went about creating, consecrating, and empowering a spirit box on the night of Samhain 2013. A spirit box can be created and utilised for many different purposes, but in this case, the spirit box was crafted as a gift for the mighty, spirited dead, allowing them to communicate more easily with me and vice versa by offering them a...»

«Gastrointestinal Glossary of Terms Abdominoperineal resection Surgical removal of the anus, rectum and sigmoid colon, resulting in the need for a permanent colostomy. Adenoma Glandular lesion thought to be the precursor to colorectal cancer. Adhesion A band of scar tissue that connects two surfaces of the body that are normally separate. Air contrast barium enema An X-ray examination of the entire large intestine (colon) and rectum in which barium and air are introduced gradually into the colon...»

«43 Oversights in Energy Reference States C.M. Sliepcevich University of Oklahoma, Norman, OK 73069 The concept of energy reference states in thermodynamics is deceptively simple in that it is often misapplied. Several examples from the literature are used to illustrate some of these difficulties. Teaching graduate courses in chemical engineering thermodynamics for several hundred students from a variety of backgrounds over the past forty years has made it evident that their comprehension of the...»

«Cisco Systems, Inc. 2015 Annual Report Annual Report 2015 Letters to Shareholders To Our Shareholders, Fiscal 2015 was a great year for Cisco. As we marked A Winning Differentiated Strategy our thirtieth anniversary year, we witnessed the inflection Our strong financial performance and our market leadership point in the next wave of the Internet. This next wave will in most areas clearly show that our vision and strategy are have five to ten times the impact of the first. As fifty billion...»

«Atmos. Meas. Tech. Discuss., doi:10.5194/amt-2015-331, 2016 Manuscript under review for journal Atmos. Meas. Tech. Published: 10 February 2016 c Author(s) 2016. CC-BY 3.0 License. Using Low Cost Sensors to Measure Ambient Particulate Matter Concentrations and On-Road Emissions Factors Karoline K. Johnson1, Michael H. Bergin1, Armistead G. Russell2, Gayle S. W. Hagler3 School of Civil and Environmental Engineering, Duke University, Durham, NC, 27708, USA 5 School of Civil and Environmental...»

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