Real-Time Systems. Design Principles for Distributed Embedded Applications. Herman Kopetz. Second Edition (811374), страница 75
Текст из файла (страница 75)
The book byButazzo [But04] Hard Real-Time Computer Systems covers scheduling extensively. An excellent survey article on WCET analysis is contained in [Wil08].Anytime algorithms are described in [Zil96].Review Questions and Problems10.1 Give taxonomy of scheduling algorithms.10.2 Develop some necessary schedulability tests for scheduling a set of tasks ona single processor system.10.3 What are the differences between periodic tasks, sporadic tasks, andaperiodic tasks?10.4 Why is it hard to find the worst-case execution time (WCET) of a program?10.5 What is the worst-case administrative overhead (WCAO)?10.6 Given the following set of independent periodic tasks, where the deadlineinterval is equal to the period: {T1(5,8); T2(2,9); T3(4,13)}; (notation: taskname(CPU time, period)).(a) Calculate the laxities of these tasks.(b) Determine, using a necessary schedulability test, if this task set isschedulable on a single processor system.(c) Schedule this task set on a two-processor system with the LL algorithm.10.7 Given the following set of independent periodic tasks, where the deadlineinterval is equal to the period: {T1(5,8); T2(1,9); T3(1,5)}; (notation: taskname(CPU time, period)).(a) Why is this task set not schedulable with the rate monotonic algorithmon a single processor system?(b) Schedule this task set on a single processor system with the EDFalgorithm.10.8 Why is it not possible to design, in general, an optimal dynamic scheduler?10.9 Assume that the task set of Fig.
10.5 is executed without the priority ceilingprotocol. At what moment will a deadlock occur? Can this deadlock beresolved by priority inheritance? Determine the point where the priorityceiling protocol prevents a task from entering a critical section.10.10 Discuss the schedulability test of the priority ceiling protocol. What is theeffect of blocking on the processor utilization?10.11 What are the problems with dynamic scheduling in distributed systems?10.12 Discuss the issue of temporal performance in best-effort distributed system.10.13 What is the role of time in static scheduling?10.14 List some properties of anytime algorithms!10.15 What is feedback scheduling?Chapter 11System DesignOverview This chapter on architecture design starts with a discussion on design ingeneral.
The designer must get a deep insight into all different aspects of theproblem domain before she/he can design a proper structure for the application.In computer system design, the most important goal is controlling the complexity ofthe evolving artifact. A thorough analysis of the requirements and constraints limitsthe design space and avoids the investigation of unrealistic design alternatives.
Anykind of structure restricts the design space and has a negative impact on theperformance of a system, which must be carefully evaluated in real-time systems.The central step in the development of an architecture is concerned with theallocation of functions to nearly decomposable clusters of components. Components should have a high internal cohesion and simple external interfaces.
In thefollowing, different design styles such as model-based design and component-baseddesign are discussed. The design of safety-critical systems starts with the safetyanalysis such as fault tree analysis and/or failure mode and effect analysis (FMEA)of the envisioned application, and the development of a convincing safety case.Different standards that must be observed in the design of safety-critical system aredescribed, such as the IEC 61508 for electric and electronic equipment and theARINC DO 178B standard for airborne equipment software.
The elimination of alldesign errors, e.g., software errors or hardware errata of a large safety-criticalsystem is a major challenge. Design diversity can help to mitigate the problem ofdesign errors. The final section of this chapter is devoted to the topic of design formaintainability in order to reduce the overall life-cycle cost. Maintainability ofsoftware is needed to correct design errors in the software and to adapt the softwareto the never-ending needs of an evolving application scenario. If an embeddedsystem is connected to the Internet, a new threat, the remote attack of the system byan intruder to exploit existing vulnerabilities, must be considered.
The securedownload of a new software version via the Internet is an essential functionalitythat should be supported by any embedded system connected to the Internet.H. Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications,Real-Time Systems Series, DOI 10.1007/978-1-4419-8237-7_11,# Springer Science+Business Media, LLC 201125926011.111 System DesignSystem Design11.1.1 The Design ProcessDesign is an inherently creative activity, where both the intuitive and the rationalproblem solving systems of the human mind are heavily involved.
There is acommon core to design activities in many diverse fields: building design, productdesign, and computer system design are all closely related. The designer must find asolution that accommodates a variety of seemingly conflicting goals to solve anoften ill-specified design problem. In the end, what differentiates a good designfrom a bad design is often liable to subjective judgment.Example: Consider the design of an automobile.
An automobile is a complex massproduction product that is composed of a number of sophisticated subsystems (e.g., engine,transmission, chassis, etc.). Each of these subsystems itself contains hundreds of differentcomponents that must meet given constraints: functionality, efficiency, geometrical form,weight, dependability, and minimal cost. All these components must cooperate and interactsmoothly, to provide the emergent transportation service and the look and feel that thecustomer expects from the system car.During the purpose analysis phase, the organizational goals and the economic andtechnical constraints of an envisioned computer solution are established.
If theevaluation at the end of this phase results in a go ahead decision, a project team isformed to start the requirement analysis and the architecture design phase. Thereare two opposing empirical views how to proceed in these first life cycle phaseswhen designing a large system:1. A disciplined sequential approach, where every life-cycle phase is thoroughlycompleted and validated before the next one is started (grand design)2. A rapid-prototyping approach, where the implementation of a key part of thesolution is started before the requirements analysis has been completed (rapidprototyping)The rationale for the grand design is that a detailed and unbiased specification ofthe complete problem (the What?) must be available before a particular solution(the How?) is designed.
The difficulty with grand design is that there are no clearstopping rules. The analysis and understanding of a large problem is never complete and there are always good arguments for asking more questions concerningthe requirements before starting with the real design work. Furthermore, the worldevolves while the analysis is done, changing the original scenario. The phraseparalysis by analysis has been coined to point to this danger.The rationale for the rapid prototyping approach assumes that, by investigating aparticular solution at an early stage, a lot is learned about the problem space.
Thedifficulties met during the search for a concrete solution guide the designer inasking the right questions about the requirements. The dilemma of rapid prototyping is that ad hoc implementations are developed with great expense. Since the first11.1 System Design261prototype does address limited aspects of the design problem only, it is oftennecessary to completely discard the first prototypes and to start all over again.Both sides have valid arguments that suggest the following compromise: In thearchitecture design phase, a key designer should try to get a good understanding ofthe architectural properties, leaving detailed issues that affect only the internals of asubsystem open.
If it is not clear how to solve a particular problem, then apreliminary prototype of the most difficult part should be investigated with theexplicit intent of discarding the solution if the looked-for insight has been gained. Inhis recent book [Bro10], Fred Brook states that conceptual integrity of a design isthe result of a single mind.Some years ago, Peters [Pet79] argued in a paper about design that designbelongs to the set of wicked problems. Wicked problems are described by thefollowing characteristics:1. A wicked problem cannot be stated in a definite way, abstracted from itsenvironment.
Whenever one tries to isolate a wicked problem from its surroundings, the problem loses its peculiarity. Every wicked problem is somehowunique and cannot be treated in the abstract.2. A wicked problems cannot be specified without having a solution in mind. Thedistinction between specification (what?) and implementation (how?) is not aseasy as is often proclaimed in academia.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
