Oplossing Examenvragen Software-ontwerp ( )

1

Oplossing Examenvragen Software-ontwerp (2007-2008) door Faysal Boukayoua 1. Geef de definitie van real-time systemen. Een real-time systeem is een informatieverwerkend systeem dat moet reageren op extern gegenereerde signalen binnen een eindige, opgegegen tijd. Een laat antwoord = een slecht antwoord. 2. Wat betekent hard, soft, real en firm real-time? hard real-time: 1 laat antwoord = falen van systeem (hartmonitor, kerncentrale,...) soft real-time: 1 laat antwoord = kwaliteitsverlies. Herhaaldelijk missen van deadline = falen (vluchtreservatiesysteem, data-acquisitiesysteem). firm real-time: combinatie van 2 vorige (beademingstoestel: een paar seconden vertraging in beademing is niet erg) real real-time: hard real-time met zeer korte responstijden (raketgeleidingssysteem) 3. Geef de figuur voor een typisch embedded systeem en bespreek.

4. Wat zijn de kenmerken van real-time systemen? 1. Groot en complex ■

Groot, want grote verscheidenheid aan real-world gebeurtenissen waar op moet kunnen gereageerd worden

■

Complex, want systeem moet continu mee veranderen met wijzigende noden en activiteiten.

2. Werken met echte getallen: rekening houden met sampling en nauwkeurigheid (ADC's en DAC's)

2 3. Extremely reliable & safe ■

Hoe meer afhankelijkheid van computers, hoe erger de gevolgen kunnen zijn van iets dat mis loopt (economisch, milieu, mensenlevens)

■

Minimaliseren kans op menselijke fouten!

■

Rekening houden met moeilijkheden inherent aan toepassing + bij softwareontwikkeling

4. Concurrent control of seperate components ■

Nood aan parallele processing

■

Makkelijker als programmeertaal ondersteuning voor parallelisme heeft

5. Real-time facilities ■

Responstijd cruciaal  systeem krachtig genoeg nemen zodat worst case-gedrag geen ongewenste vertraging geeft tijdens kritische periodes

■

Nodig:

■

●

Opgeven tijdstip van uitvoering

●

Opgeven van deadlines

●

Reageren wanneer niet aan alle vereisten kan voldaan worden

●

Reageren op situaties waar tijdseiseisen dynamisch wijzigen (noodlanding vliegtuig)

Om antwoordtijden te halen  voorspelbaar gedrag nodig (=probleem!)

6. Interface met hardware (machine-afhankelijk) ■

Vroeger: OS en assembly language

■

Nu: tijd-kritisch. Huidige middelen geven verhoogde betrouwbaarheid en directe controle  geen low-level programming meer.

7. Efficiënte implementatie en uitvoeringsomgeving: ■

focus op oplossing  abstractie van implementatiedetails

■

indien reponstijden grootteorde µs, geen taalmogelijkheid gebruiken die grootteorde ms aankan

5. Bespreek het simple process model (fixed-priority-scheduling, rate monotonic assignment, schedulability test). 1. Simple process model ■

Vast aantal processen

■

Alle processen periodisch, met gekende periodes1

■

Processen onafhankelijk van elkaar

■

System overhead, context-switching,... verwaarloosd (= zero-cost )

1 Belangrijk onderscheid: ● Periodisch: vast tijdsinterval tussen elke release = periode ● Aperiodisch: helemaal geen regelmaat in tijd tussen elke release  moeilijk uit te drukken in scheduling ● Sporadisch: er zit een minimum tijdsinterval tussen elke release (minimum interarrival time). Proces mag minder vaak opgestart worden, maar niet vaker. = manier om beter te kunnen werken met aperiodische processen.

3 ■

Alle processen hebben deadline = periode (process moet voltooid zijn vooraleer het volgende keer losgelaten wordt)

■

Alle processen hebben een vaste worst-case execution time

2. Fixed-priority-scheduling ■

Meest gebruikt

■

elk proces heeft vaste, statische prioriteit (prioriteit vloeit voort uit tijdseisen)

■

volgorde van uitvoering bepaald door prioriteit

3. Rate monotonic assignment = toewijzen van prioriteit op basis van lengte van periode ■

 periodelengte   prioriteit: T i P j

■

Rate monotonic assignment is optimaal: als een reeks processen kan ge-scheduled worden met een fixed priority assignment scheme , dan kan deze ook steeds gescheduled worden met een rate monotonic assignment scheme.

■

!! prioriteit 1 is laagste (minst belangrijke) prioriteit

4. Schedulability test: dit is een test, aan de hand van een specifieke formule, op basis van dewelke men kan bepalen of een reeks processen kunnen ge-scheduled worden. Richtlijnen zijn: ■

Alle processen moeten schedulable zijn, gebruik makend van average execution times en average arrival rates

■

Alle hard real-time processen moeten schedulable zijn, gebruik makend van worst case execution times en worst case average arrival rates van alle processen (ook soft realtime)

6. Wat is het probleem bij scheduling als processen interageren (priority ceiling protocols)? ○

Probleem: proces van hogere prioriteit dat een resource nodig heeft die in het bezit is van een proces van lagere prioriteit en daardoor moet wachten (geblokkeerd) = priority inversion

○

Priority ceiling protocols: ■

■

Met deze protocollen wordt op 1 enkele processor: ●

een hogere-prioriteitsproces maximaal 1 keer geblokkeerd door een proces van lagere prioriteit

●

deadlocks vermeden

●

transitief blokkeren vermeden: transitief blokkeren = als proces van hogere prioriteit geblokkeerd  processen met lagere prioriteit ook geblokkeerd

●

wederzijdse uitsluiting gewaarborgd

Protocollen: ●

Original ceiling priority protocol (OCPP): ○

Default statische prioriteit voor elk proces

○

Dynamische prioriteit voor elk proces = max uit verzameling prioriteiten

4 gevormd door eigen statische prioriteit en prioriteiten die proces overerft2 door blokkeren van hogere-prioriteitsprocessen.

●

●

○

Static ceiling value voor elke resource = max prioriteit uit de verzameling processen die het gebruiken.

○

Een proces kan een resource vergrendelen als zijn dynamische prioriteit hoger is dan de ceiling van elke huidig vergrendelde (niet door het proces zelf) resource.

Illustration 1: Voorbeeld van OCPP Immediate ceiling priority protocol(ICPP): ○

Default statische prioriteit voor elk proces

○

Static ceiling value voor elke resource = max prioriteit uit de verzameling processen die het gebruiken.

○

Dynamische prioriteit voor elk proces = max uit verzameling gevormd door eigen prioriteit en ceiling values van resources die door het proces vergrendeld zijn.

○

(NIET ZEKER) Weerom: een proces kan een resource vergrendelen als zijn dynamische prioriteit hoger is dan de ceiling van elke huidig vergrendelde (niet door het proces zelf) resource.

○

Gevolg: Bij ICPP zal de blokkering van een proces helemaal in het begin plaatsvinden.

○

Eenmaal een proces begint met uitvoeren ZULLEN per definitie alle nodige resources vrij zijn. Indien niet, dan zou een ander proces een even hoge / hogere prioriteit krijgen en zou de uitvoering worden uitgesteld.

OCPP versus ICPP ○

Worst case-gedrag nagenoeg dezelfde.

2 Priority inheritance: als proces met prioriteit 1 een belangrijker proces met prioriteit 5 blokkeert, dan krijgt het eerste proces tijdelijk prioriteit 5, zodat geen priority inversion optreedt.

5 ○

ICPP makkelijkst te implementeren.

○

ICPP heeft minder context-switching want blokkeringen voornamelijk in het begin.

○

ICPP geeft meeste prioriteitsveranderingen  OCPP verandert prioriteit enkel indien er een echte blokkering komt

Illustration 2: Voorbeeld van ICPP 7. Leg de volgende formule uit:

Ri =Ci +B i 

∑

j∈hp  i



Ri +J j Tj



Cj

3

Di ≥Ri=Ci I i worst case reponse time = worst case computation time + total inteference time ○

Gedurende R, zal elke hogere-prioriteitstaak j een # keer uitvoeren. Ri = # releases van hogere-prioriteitstaak j. Tj

⌈ ⌉ ⌈ ⌉

Ri ×C j = totale interferentie door hogere-prioriteitstaak j Tj

Ii=

∑

j ∈hp i

⌈ ⌉

Ri ×C j = totale inteferentie op taak I van alle hogere-prioriteitstaken Tj

Ri =C iI i =C i

∑

j∈hp i

⌈ ⌉

Ri ×C j Tj

3 R: worst case response time C: worst case computation time I: interference time of higher priority tasks T: period D: deadline B: worst case blocking time J: release jitter

6 ○

Rekening houden met blocking: Ri =C iI i Bi=C i Bi

○

∑

j ∈hp i

⌈ ⌉

Ri ×C j Tj

Rekening houden met release jitter: sporadisch proces ge-released door een periodiek proces (met periode T) op 0, T-J, 2T-J, 3T-J ■

1 inteferentie als Ri ∈[0, T − J ]

■

2 inteferenties als

Ri ∈[T − J , 2T− J ]

■

3 inteferenties als

Ri ∈[2T− J , 3T− J ]

Ri =C iI i Bi=C i Bi

∑

j∈hp i

⌈

⌉

R i J i ×C j Tj

8. Wat zijn de problemen bij het instellen van de delay voor een proces? ○

Delay (absoluut of relatief) is minimum delay en niet maximum delay!

○

Problemen:

○

■

Lokale drift = over-run afkomstig van zowel absolute als relatieve delays: kan niet geëlimineerd worden!

■

Cumulatieve drift = over-run door cumuleren van alle lokale driften: kan wel verholpen worden

Oplossing: ■

Mét cumulatieve drift (verkeerd):

■

task T; task body T is begin loop Action; delay 5.0; //Kan niet minder dan 5 seconden vertragen (cumulatieve drift mogelijk) end loop; end T; Zonder cumulatieve drift (juiste manier): task body T is Interval : constant Duration := 5.0; //constante van 5 seconden Next_Time : Time; begin Next_Time := Clock + Interval; loop Action; delay until Next_Time; Next_Time := Next_Time + Interval; end loop; end T;

7 9. Hoe reageer je op het niet voorkomen van een extern event? Door het proces dat aan het draaien is, te laten wachten op de externe event. Indien deze niet binnen een opgegeven tijd plaatsvindt, dan wordt het proces afgebroken (timeout): ○

Ada: select delay 0.1; then abort -- action end select;

○

RT Java: via Timed, een subklasse van AsynchronouslyInterruptedException. Wanneer maximale tijd verstreken, wordt een AsynchronouslyInterruptedException opgeworpen, die dan kan worden afgehandeld.

10. Welke tijdseisen kan je stellen op processen? ○

Deadline: tegen wanneer ten laatste voltooid

○

Minimum delay: minimale tijd die voorbij moet zijn vooraleer proces start

○

Maximum delay: tijd die maximaal voorbij mag zijn vooraleer proces start

○

Maximum execution time: maximale verstreken rekentijd

○

Maximum elapse time:maximale verstreken tijd (tout court)

○

Hard real-time // soft real-time // firm real-time // interactief.

○

Periodisch // sporadisch //aperiodisch

11. Hoe detecteer je het overschrijden van tijdseisen en hoe ga je erop reageren? ○

Ada: er wordt bepaalde code voorzien die zou worden uitgevoerd met als delay de deadline van het proces. Indien de deadline gehaald wordt, wordt de code nooit uitgevoerd. !!!Stopt proces met uitvoering en begint recovery procedure

○

Java: Er wordt een asynchrone event opgeworpen wanneer bvb. de maximale rekentijd (cost) of de deadline zijn verstreken. Deze events worden afgehandeld met event handlers. !!!Proces kan gestopt worden of toegelaten worden om verder te werken (evt. met andere prioriteit)

12. Wat zijn atomische acties en wat zijn de eisen ervoor? ○

○

Wat? Actie atomisch als proces die het uitvoert ■

niet bewust is van andere actieve processen en vice versa;

■

niet communiceert met andere processen tijdens uitvoering actie;

■

er geen toestandswijzigingen zijn, behalve die die het proces zelf veroorzaakt. Proces zal ook zijn eigen toestandswijzigingen niet bekend maken tot de actie voltooid is (bvb: veranderen waarde van variabele)

■

als direct en ondeelbaar kan worden gezien door andere processen

Eisen: ■

goed gedefinieerde grenzen (begin, einde, scheiding tussen processen betrokken bij atomische actie en deze die dat niet zijn)

8 ■

Ondeelbaar: ●

geen uitwisseling informatie tussen interne en externe processen (behalve resourcemanagers)

●

waarde van gedeelde data na acties bepaald door strikte opeenvolging van acties in bepaalde volgorde orde

●

geen synchronisatie bij start: processen kunnen op  momenten binnenkomen

●

alle processen moeten wachten tot het mogelijk is om allemaal tegelijk de atomische actie te verlaten.

13. Bespreek conversations, dialogs en colloquys (hier: backward error recovery)4. ○

Conversation ■

//In proces P1: action A with (P2, P3) do ensure by -- primary module else by -- alternative module else by -- alternative module else error end A;

■

Wanneer processen binnenkomen, wordt hun toestand opgeslagen. De set van entry points (ingangen) vormt een recovery line .

■

Proces in conversation kan enkel communiceren met andere actieve processen in conversation en algemene resource managers. Aangezien een conversatie opgebouwd is uit atomische acties, wordt deze eigenschap ervan overgeërfd.

■

Om conversation te verlaten moeten alle processen slagen voor de acceptance test. ●

Geslaagd?  Conversation beëindigd en recovery points verwijderd

●

Niet geslaagd?  ALLE processen hersteld tot hun oorspronkelijke staat.

■

Bij faling  herstelling + overgaan tot alternatieve module.

■

Alle alternatieven falen ook?  recovery op hoger niveau

■

Verschil in opvatting: ●

Originele definitie: alle deelnemende processen moeten binnen zijn voor 1 eruit kan

●

Hier: zolang actieve processen in conversatie er niet mee willen communiceren, is het niet nodig dat een proces zich er bevindt.

●

Indien toch communicatie gewenst, kan het actieve proces wachten (blokkeren) tot nodige proces binnenkomt of voortdoen.

●

Voordelen:

4 Op de slides kon ik niet direct voor 100% terugvinden wat ik zocht. Een groot deel van het boek van real-time systems staat online als preview: http://books.google.be/books?id=0_LjXnAN6GEC&printsec=frontcover#PPP1,M1

9

■

○

○

○

Mogelijk om conversaties te specifiëren zonder verplichte deelname

○

Mogelijk dat processen met een deadline de conversatie verlaten en verder doen. Eventueel met uitvoer van een alternatieve code.

Kritieken ●

Bij faling  ALLE processen hersteld en in alternatieve modus

●

Voor 2de module kan het misschien zijn dat een proces met totaal andere processen zou moeten communiceren.

●

Acceptance test voor elke module kan anders zijn.

Dialogs ■

Processen die willen deelnemen aan een backward recoverable atomic action, voeren een DIALOG statement uit.

■

Elk proces dat wil deelnemen, definieert ook een DISCUSS-statement

■

De reeks DISCUSS statements vormt hier de recovery line

■

Dialog faalt?  processen hesteld tot hun oorspronkelijke staat.

■

Er zijn geen alternatieve modules!

■

Wel mogelijk om verschillende dialogs samen te nemen tot een dialog sequence: SELECT --dialog 1 OR --dialog 2 //Als dialog 1 faalt OR dialog 3 //Als dialog 2 faalt ELSE --laatste redmiddel //Als alle dialogs gefaald hebben END SELECT

Colloquy = gecombineerde uitvoering van verwante dialog sequences (1 in elk proces dat deelneemt)

14. Bespreek atomische acties en forward error recovery. ○

//Exception handling: action A with (P2, P3) do -- the action exception when exception_a => -- sequence of statements when exception_b => -- sequence of statements when others => raise atomic_action_failure; end A;

○

Exception in 1 proces van een atomic action?  Opgeworpen in alle deelnemende processen (alle deelnemende processen maken deel uit van de forward error recovery). =Asynchrone exception (want komt van een ander proces).

10 ○

Zowel termination als resumption model mogelijk

○

als geen opvang is in een van de deelnemende processen of als opvang faalt  atomic action faalt met een standaard exception atomic_action_failure, opgegooid in alle betrokken processen

○

Omgaan met 2 concurrent opgegooide exceptions:

○

■

2 handlers in elk proces  welke handler kiezen?

■

3e exception gebruiken die wijst op optreden van 2 vorige tegelijk.  exception tree: handler gebruiken voor exception op wortel van kleinste subtree die alle opgetreden exceptions bevat.

■

Onduidelijk hoe parameters van fouten combineren...

Omgaan met exceptions en geneste atomische acties ■

Probleemstelling: proces in een atomische actie gooit een exception op. ALLE processen moeten meedoen aan recovery. Een (nested) atomic action is echter ondeelbaar!

■

Mogelijke oplossingen: ●

●

Wachten met opgooien van exception tot geneste atomische actie voltooid. Dit is echter niet zo een goed idee want: ○

De exception kan iets te maken hebben met een gemiste deadline. De exception tijdelijk onderdrukken kan dus een nefaste impact hebben op tijdig reageren van het systeem.

○

De exception kan gerelateerd zijn aan een deadlock in de geneste atomische actie  geneste actie zal dan nooit voltooid worden.

Gebruik maken van een voorgedefinieerde abortion exception . ○

Dit zal ervoor zorgen dat de geneste atomische actie gestopt wordt, zodat alle processen kunnen deelnemen aan de recovery.

○

Indien er geen voorgedefinieerde abortion exception is, is er geen andere keuze dan te wachten op het voltooien van de geneste atomische actie.

15. Beschrijf kort het HRT HOOD proces. 1. Hard Real-time Hierarchical Object-Oriented Design 2. Focus op ontwikkeling van fysische en logische architectuur (architectural design). 3. object-gebaseerde notatie 4. onderverdelen in modules met goed gedefinieerde interfaces: ■

ofwel direct geïmplementeerd

■

ofwel verder onderverdeeld

5. gestandaardiseerd formalisme: tekstueel en grafisch 6. Regels automatisch laten checken: bvb scheduling, precondities,... 7. design = voortgang van alsmaar specifiekere commitments ■

commitments = eigenschappen van ontwerp die niet gewijzigd mogen worden door de ontwerpers die zich op een specifieker ontwerp-niveau bevinden.

11 ■

aspecten van design zonder commitment = obligations  te behandelen in lagere (specifiekere) niveaus.

8. ontwerpverfijning (obligations omzetten naar commitments) vooral beïnvloed door beperkingen van uitvoeringsomgeving: ■

resource constraints: CPU klokfrequentie, netwerkbandbreedte,...

■

mechanism constraints: interrupt priorities, task dispatching, data locking,

9. Obligations, commitments en constraints hebben belangrijke invloed op architectuur-design. Architectuur-design kan opgesplitst worden in 2 delen: ■

■

logical architecture: ●

onafhankelijk van uitvoeringsomgeving

●

doel: vooral voldoen aan functionele eisen

physical architecture: ●

vooral niet-functionele eisen

●

vormt een basis om a te gaan of aan functionele eisen voldaan wordt, na implementatie.

10. Verschillende soorten objecten: ■

Actief: ●

Controle over uitvoering eigen code

●

In staat andere objecten op te roepen

■

Passief: omgekeerde van actief

■

protected:

■

■

●

Controle over eigen operaties

●

Niet mogelijk om code van andere objecten op te roepen

●

Mogen geen arbitraire synchronisatiebeperkingen hebben

●

Blokkeertijden die ze veroorzakn bij hun oproepers, moeten analyseerbaar zijn

Cyclisch: ●

vertegenwoordigen periodieke activiteiten

●

spontaan oproepen van code van andere objecten

Sporadisch: ●

vertegenwoordigen sporadische activiteiten

●

spontaan oproepen code van andere objecten

11. Naar einde van ontwerp toe mag programma alle objecttypen bevatten, behalve actieve. ■

actieve objecten enkel voor achtergrondtaken

■

actieve objecten enkel gebruikt bij ontwerp  moeten naar einde toe veranderd worden naar ander type.

12 16. Beschrijf kort het ROPES proces. 1. Rapid Object-Oriented Process for Embedded Systems 2. ROPES Macro Cycle 1. Analysis: identificatie van alle aspecten voor correctheid ●

Requirements analysis ○

Informatie verkrijgen van klant in vorm van: 1. use cases 2. state charts (toestandsdiagrammen?) 3. beperkingen

○

Activiteiten: 1. use case maken 2. externe events identificeren 3. gedragsscenario's definiëren 4. beperkingen en interfaces naar andere systemen

○

Systeem in grote delen splitsen en gedrag uitwerken

○

externe actoren identificeren

○

messages uitwerken tussen systeem en actoren

○

protocols voor communicatie verfijnen

●

Systems analysis/engineering

●

Object analysis

2. Design ●

Architectural

●

Mechanistic (~mechanisms?)

●

Detailed

3. Translation 4. Testing