1
Puntenverdeling
Labo 3/20 Opdracht UML 5/20 Examen 12/20
2
Mogelijke examenvragen
Op het examen zullen 3 of 4 vragen gesteld worden verdeeld over de leerstof. Er zal niets over de theorie van RT UML gevraagd worden. Wel moet je de opdracht over de Pacemaker kunnen toelichten (je eigen oplossing).
2.1 2.1.1
Inleiding Geef de definitie van een Real-Time systeem
Een real-time systeem is een systeem dat informatie verwerkt en een antwoord geeft binnen een bepaalde tijdspanne. De juistheid hangt dus niet enkel af van het resultaat maar ook van de responstijd. Niet tijdig een antwoord geven is even erg als geen of een fout antwoord. 2.1.2
Onderscheid hard; soft; real; firm systemen
• hard: systemen waar het absoluut noodzakelijk is dat er een antwoord is voor de deadline verstrijkt (vlucht controle systemen) • soft: systemen waar deadlines belangrijk zijn maar waar het system nog correct blijft functioneren wanneer er een deadline gemist wordt • real: harde realtime systemen waar de responstijd zeer kort is (raket sturingen) • firm: soft realtime systemen waar de data onbruikbaar is als er een late respons is een systeem kan zowel harde als zachte deadlines hebben (realiteit → kosten functie) 2.1.3
Teken de figuur over embedded systemen + leg uit
1
• computer: sampling van meettoestellen op regelmatige tijdstippen → real-time klok noodzakelijk • constant informeren van toestand systeem aan menselijke operator • toestandswijzigingen bijhouden (databank) – voor post mortems (systeem crash) – voor administratieve doeleinden 2.1.4
Geef de kenmerken van Real-Time systemen + leg uit
• Groot en complex – Reageren op real-world gebeurtenissen ∗ grote verscheidenheid → large ∗ noden en activiteiten wijzigen continu – Real-time talen en omgevingen → complexe omgevingen opdelen in handelbare systemen • Manipulatie van echte getallen: model nodig, oplossen differentiaalvergelijkingen, rekening houden met sampling en nauwkeurigheid • Extreem betrouwbaar en veilig: het mag niet falen, minimaliseren menselijke fout, moeilijkheden inherent aan de software en toepassing • Gelijktijdige controle van aparte systeem componenten – Controlleren robots, sensor , · · · – Op meerdere plaatsen → nood aan meerdere processoren – Nood aan programmeertalen die parallelle systemen ondersteunen • Responsetijd is cruciaal – Specifi¨eren van tijdstippen: wanneer uitvoeren (sensor uitlezen), wanneer antwoord – Reageren als er een tijdstip gemist wordt – Reageren als tijdseisen dynamisch wijzigen (vliegtuig noodlanding) – Om ontwoordtijden te kunnen halen → voorspelbaar gedrag nodig • Interactie met hardware interupts – device-afhankelijk, interrupts – vroeger: OS of assembly code – nu (real-time): ∗ tijd-kritisch → directe controle ∗ betrouwbaarheid → geen low-level programming • Effici¨ent implementeren en uitvoeren – high level taal → abstractie details – embedded: als vereiste antwoordtijd binnen microseconde → geen taal gebruiken die dit niet aankan
2
2.2 2.2.1
Atomic Actions H10 Wat zijn atomic actions en waarvoor zijn deze nodig
Een actie is atomisch als het uitvoerend proces: • zich niet bewust is van het bestaan van andere actieve processen en de andere actieve processen zijn zich niet bewust van de activiteit van het proces gedurende de actie • niet communiceert met andere processen terwijl het een actie uitvoert • geen state verandering kan detecteren behalve als ze die zelf veroorzaken • ondeelbaar is en zonder vertraging wordt uitgevoerd Waarvoor nodig: • parallellisme • soms moeten 2 processen 1 communicatie uitvoeren die niet mag onderbroken worden (banktransactie) • de betrokken processen moeten een consistente (niet-tegenstrijdige) systeem staat zien • interferentie met andere processen vermijden Atomic transactie → zelfde als actie maar moet ofwel slagen ofwel geen effect hebben (error recovery) Eigenschappen atomische acties: • start en einde zijn gedefinieerd • mogen geen informatie uitwisselen met buitenstaande processen • de processen mogen de atomische actie niet verlaten vooraleer alle deelnemende processen voltooid zijn (bij slagen van de atomische actie) • mogen nesten zolang er geen overlap is met andere atomic acties • meerdere atomische acties kunnen parallel worden uitgevoerd 2.2.2
Wat zijn conversations, dialogues en calloguys
Conversations:
• atomische acties voor rollback (=backward error recovery) worden conversations genoemd • bij het starten van de actie wordt de staat van de deelnemende processen opgeslagen in een recovery point
3
• binnen de actie (zie tek) wordt rollback van alle processen naar het recovery point voorzien als een proces faalt • enkel communicatie toegestaan met processen in de conversation • om de conversatie te verlaten moeten alle processen hun acceptance test voltooien • als de actie geslaagd is worden alle recovery points verwijderd • enkel strikte nesting toegestaan • als alle alternatieven (zie tek) falen moet de recovery op een hoger niveau afhandelen • deelname is niet verplicht (verlaten voor deadline te halen) – zolang er niet moet gecommuniceerd worden met een ontbrekend proces kan de conversatie voltooien – als er moet gecommuniceerd worden met een ontbrekend proces kan het proces wachten of voortdoen Kritiek op conversations: • alle processen gaan naar alternatief als er faling is • soms beter opnieuw proberen in plaats van over te gaan op alternatieve module • alternatieve module meestal andere acceptance tests Dialogs en colloquys: Dialog: • groep processen in atomische actie • bij fout wordt het recovery point hersteld en faalt de dialog Colloguy: • bevat groep dialogs • controleert de acties • beslist welke herstelactie wordt gestart bij een fout van een dialog • mogelijk om alternatieve dialogs te defini¨eren met mogelijk een andere groep processen Verder: • dialog statements zijn statements die gebruikt worden door te signaleren dat een groep processen wil deelnemen aan een backward recoverable atomic action • dialog statements hebben drie functies: – de atomic action identificeren – een globale acceptatie test declareren voor de atomic action – de variabelen die bij de atomic action zullen gebruikt worden specificeren • het dialog statement heeft volgende vorm: DIALOG name and acceptance test SHARES(variables) • elk process dat wil deelnemen aan de actie definieert een discuss statement dat de actie een naam geeft: 4
DISCUSS dialog name BY sequence of statements TO ARRANGE boolean expression;
• het discuss statement is een onderdeel van de atomic action • de groep discuss statements definieert de recovery line • de state van elk proces dat de dialog betreedt wordt opgeslaan • RULE: een process mag de dialog niet verlaten vooraleer alle acieve processen succesvol hun local en global acceptance test hebben afgelegd • slaagt men daar niet in, dan wordt hun oorpronkelijke state hersteld • er worden geen alternatieve modules uitgevoerd, in de plaats kunnen discuss statements gecombineerd worden door gebuik te maken van een ander statement, genaamd dialog sequence:
2.2.3
Leg uit: forward error recovery
• forward error recovery en exception handling worden gebruikt voor real-time applicaties waar geen roll back mogelijk is. • als er een exception in een process optreedt, wordt het asynchroon toegevoegd aan alle processen die deelnemen aan de actie. • zowel terminatie als voortzettings modellen zijn mogelijk – voortzetting: als een proces een exception veroorzaakt kan deze mogelijk door de handler worden opgelost waardoor het proces kan voortwerken alsof er niets is gebeurd – terminatie: als een proces een exception veroorzaakt zorgt de handler ervoor dat het proces wordt be¨eindigd – hybride: de handler kiest afhankelijk van de situatie of het proces wordt voortgezet of be¨eindigd • als er geen handler zit in ´e´en van de processen die bij de actie worden gebruikt of als ´e´en van de handlers faalt, dan faalt de atomic action met een standard exception: atomic action failure. Deze exception wordt toegevoegd aan alle betrokken processen. Resolutie van gelijktijdig voorkomende exceptions: • twee of meer exceptions die tegelijk voorkomen in een atomic action leiden tot twee afzonderlijke exception handlers in elk proces • moeilijkheid: welke moet afgehandeld worden? • exception tree om te kiezen 5
• RULE: als meerdere exception tegelijk voorkomen, dan wordt de exception gebruikt aan de wortel van de kleinste subtree die alle exceptions bevat • behandelen van concurrent exceptions: – elk onderdeel van een atomic action kan zijn eigen exception tree declareren – verscheidene processen die betrokken zijn bij een atomic action kunnen verschillende exception trees hebben Exceptions en interne atomische acties • geneste atomische acties: een proces dat deelneemt aan een actie geeft een exception als andere processen betrokken zijn bij een geneste actie • alle processen die betrokken zijn moeten deelnemen aan de recovery action. Spijtig genoeg is de interne actie ondeelbaar! → 2 oplossingen: – wacht met de exception te geven tot de interne actie gedaan is – laat interne actie een voorafgedefinieerde abortion exception hebben. Dit geeft aan dat een exception is gegeven in een omringende actie en dat de pre–conditions onder welke de exception gegeven is, niet langer geldig is.
2.3 2.3.1
Tijd H12 Wat zijn de problemen bij het instellen van de delay van een proces. Hoe kan men de lokale en cummulatieve drift vermijden.
• delay is de minimum delay en niet de maximum delay: – instellen proces 5sec wachten → delay = 5sec – na 5sec zal dit proces zijn beurt afwachten om uitgevoerd te worden + tijd voor proceswissel → 5sec = minimale delay • locale drift: het teveel aan tijd bij relatieve en absolute delays is de lokale drift en kan niet vermeden worden – wordt het proces bv uitgevoerd na 5.5 sec is de delay 5 seconden en de drift 0,5 • cumulatieve drift kan vermeden worden als de lokale driften elkaar mogen overlappen (superimpose) – stel dat een proces elke 10 seconden moet uitgevoerd worden
6
– als het proces pas uitgevoerd wordt na 11 seconden zal het proces de volgende keer pas worden uitgevoerd op 21 sec + eventuele drift, terwijl dit eigenlijk op 20 moest beginnen – ⇒ cumulatieve drift – op te lossen door het overlappen (zie vb) van driften
2.3.2
Hoe reageer je op het niet voorkomen van externe events (time-out). Hoe detecteer je deze en hoe vang je dit op.
• in Real-Time Java zijn time-outs op acties voorzien • subclasse van AsynchronouslyInterruptedException genaamd Timed • bij het verlopen van de timer wordt er een AsynchronouslyInterruptedException gegenereerd die dan kan opgevangen worden
Reageren?
7
2.3.3
Welke eisen kan je stellen aan een proces
• deadline (tijdstip van wanneer het voltooid moet zijn) • minimum delay: de minimium tijd voor het starten • maximum delay: de maximum tijd voor het starten • maximum execution time: • maximum elapse time: • tijdseisen: – periodisch – sporadisch – aperiodisch • deadlines: hard, soft, interactief, firm
8
2.3.4
Hoe detecteer je het overschrijden van de tijdseisen en hoe reageer je hierop
• We kunnen bij het opstarten dan een process met deadline een recovery procedure laten opstarten. De recovery procedure wordt uitgevoerd met een delay = deadline van dat proces. Indien de deadline toch gehaald is, dan wordt de procedure nooit uitgevoerd. • Nadeel: Deze methode veronderstelt dat de taak mag worden gestopt indien de deadline niet gehaald is. • Oplossing: De taak met een andere prioriteit uitvoeren. Om dit te verwezelijken is het geschikter om dit door een asynchroon event te laten gebeuren. (In Real Time Java zal de virtuele machine een asynchroon event handler uitvoeren bij het overschijden van de deadline) • Opmerking: Real Time Java kent ook sporadic event handlers maar die worden niet uitgevoerd bij het overschrijden van een deadline en worden dus enkel voor soft deadlines gebruikt.
Reageren? 2.4
Scheduling H13
B Worst-case blocking time for the process (if applicable) C Worst-case computation time (WCET) of the process D Deadline of the process I The interference time of the process J Release jitter of the process N Number of processes in the system P Priority assigned to the process (if applicable) R Worst-case response time of the process T Minimum time between process releases (process period) U The utilization of each process (equal to C/T) a-z The name of a process 2.4.1
Wat is:
• simple proces model – een vast aantal processen – periodisch met gekende periodes – processen zijn onafhankelijk van elkaar – overhead genegeerd en alle processen hebben een deadline gelijk aan hun periode – alle processen hebben een vaste worst case • fixed priority – meest gebruikt – elk proces heeft een vaste statisch prioriteit (pre runtime) – processen worden uitgevoerd volgens hun prioriteit • rate priority (rate monotonic priority assignment) – elk proces krijgt een unieke prioriteit toegewezen gebaseerd op zijn periode – hoe korter de periode, hoe hoger de prioriteit (1 = laagste prioriteit) – als een proces gescheduled kan worden met fixed priority, kan het ook gescheduled worden met rate priority 9
• assigned priority theorema: If process p is assigned the lowest priority and is feasible then, if a feasible priority ordering exists for the complete process set, an ordering exists with process p assigned the lowest priority – als proces p de laagste prioriteit wordt toegewezen en feasible is – en als er een feasible prioriteitsvolgorde bestaat voor de volledige set van processen – ⇒ dan bestaat er een volgorde waarbij proces p de laagste prioriteit heeft extra: • earliest deadline first – het process met de vroegste deadline wordt eerst uitgevoerd – dynamisch • value–based scheduling – overloading van een systeem → meer adaptief systeem nodig – maakt gebruik van een on-line value based scheduling algoritme 2.4.2
Schedubility tests toepassen op een kleine oefening
Zie voorbeeld slides • utilisation-based analysis (andere formule voor EDF) • response time analysis 2.4.3
Leg het interageren tussen processen uit:
Prioriteit inversie → een hoge prioriteit die moet wachten op een bewerking of bron van een lagere prioriteit
• pollen – te traag? • blocking oplossing (priority ceiling) – op een enkele processor: ∗ een hoge prioriteit kan maximaal maar 1 keer geblokeerd worden door een lagere prioriteit ∗ deadlocks zijn vermeden ∗ transitief blokken is verboden ∗ exclusieve toegang tot bronnen is verzekert
10
Figuur 1: prioriteitsinversie
– original ceiling priority protocol (OCPP) ∗ elk proces een statisch default prioriteit ∗ elke bron een statische ceiling waarde (de maximum prioriteit van de processen dat het gebruiken) ∗ een proces heeft een dynamisch prioriteitswaarde dat het maximum van zijn default prioriteit en de prioriteit die het erft door het blokkeren van een hogere prioriteit ∗ een proces kan enkel een bron reserveren als de dynamische prioriteit hoger is dan het plafond van eender elke andere gereserveerde bron (exclusief dat welke het proces zelf gereserveerd heeft)
Figuur 2: OCPP overerving – immediate ceiling priority protocol (ICPP) 11
∗ elk proces een statisch default prioriteit ∗ elke bron een statische ceiling waarde (de maximum prioriteit van de processen dat het gebruiken) ∗ een proces heeft een dynamisch prioriteitswaarde dat het maximum van zijn default prioriteit en de cealing prioriteit van de bronnen die het gereserveerd heeft ∗ als gevolg zal een proces enkel in het begin geblokkeerd zijn ∗ eens het proces start met executie moeten alle bronnen vrij zijn, is dit niet het geval dan is er een ander proces met dezelfde of een hogere prioriteit dat voorgang heeft
Figuur 3: ICPP overerving
• OCPP VS ICPP – ICPP is makkelijker implementeerbaar – ICPP heeft minder wisselingen omdat er geblokkeerd wordt voor executie – ICPP heeft meer prioriteit verschuivingen nodig – OCPP verandert de prioriteit als een block zich voordoet 2.4.4
Leg deze formule uit (formule wordt gegeven slide 66) X Ri + J j .Cj Ri = Bi + Ci + Tj j∈hp (i)
• om de invloed van sporadische processen op periodische processen na te gaan ⇒ release jitter • deze formule berekent de worst case response time van proces i • Ri + Jj ⇒ worst-case response time + release jitter • •
Ri +Jj Tj
h
⇒ aantal keer dat een sporadisch proces gereleased wordt i Ri +Jj .Cj ⇒ totale interferentie Tj 12
2.5
Methodologi¨ en
• Leg uit: – HRT-HOOD (nota’s) ∗ hard realtime hierarchial object oriented design ∗ logische architectuur onafhankelijk van de uitvoeringsomgeving → functionele eisen (tijdseisen zullen wel de compositie van logische architectuur sterk be¨ınvloeden ∗ passief object type: geen controle over oproep van hun methodes ∗ actief object: kunnen alles ∗ protected: controle over eigen operaties niet spontaan opgeroepen (door een ander object) ∗ cyclic: periodisch actief ∗ sporadic: slechts 1 operatie methode ∗ we streven naar geen actieve objecten te hebben omdat ze niet volledig geanalyseerd kunnen worden. ∗ fysische archtectuur → zeker zijn dat niet functionele eisen zullen voldaan zijn – ROPES (http://www.embedded.com/2000/0012/0012feat3.htm) So what’s a process? In ROPES, we define a process to be a sequenced set of activities performed by a collaborating set of workers resulting in a coherent set of project artifacts, one of which is the desired system. Although we have only touched the surface of the ROPES process in this article, we have seen that it specifies how to perform a number of activities relevant to real-time and embedded systems. We specifically showed, for example, how to identify functional and quality of service requirements, how to identify subsystems, and even more important, how to link these two things together. There’s much more to ROPES. For example, we didn’t touch on how design patterns are applied, the importance of executable models in effectively constructing spiral models, how to turn requirements scenarios into test vectors, or how to estimate cost and time for the spirals and prototypes. The ROPES process is highly scaleable. It’s suitable for single-person projects all the way through projects with hundreds of developers. Scaleability is largely done through selecting which artifacts need to be generated. In a small project, communication with a small team may require only a few artifacts and less detail, because the team members are all co-located and the system is simple. For large systems, more ritual and detail is necessary because there will be more diversity in the team members, the cost of failure is higher (relative to the cost of producing the artifacts), the teams may not be co-located and the system is very complex. In such systems, more rigor is required to ensure that the much larger number of requirements are properly rendered in the analysis and design, and to communicate the exponentially greater number of details that arise in a large complex system. The ROPES process has evolved out of my experience in constructing many different kinds of systems over the last 20-odd years. Ideas that didn’t work well were discarded, and successful ideas were more strongly supported. Currently, ROPES is a well-understood and successful approach to building systems of varying complexities. It is being used successfully on many projects. It can help yours too.
Zeker de 3 figuren kennen! 13
