Studiewijzer module RTSOF

© Harry Broeders.

onderwijseenheid:	Verdiepende minor Elektrotechniek EVMIN
onderwijsdeel:	EVMINX9: Real-Time Software (RTSOF)
studiebelasting:	84 SBU
semester / kwartaal:	ECV/2
contacturen:	2 uur/week college en 2 uur/week practicum
toetsing:	practicumbeoordeling (O/V), huiswerkopgave (cijfer) en eindopdracht (cijfer)
benodigde voorkennis:	PROS1 tot en met PROS3 en OPSYS.
verantwoordelijke docent:	Harry Broeders

Inleiding.

Software waarvan het resultaat niet alleen correct maar ook exact op tijd moet zijn wordt realtime software genoemd. Vooral het begrip voorspelbaarheid is erg belangrijk bij real-time systemen. Veel embedded systemen bevatten real-time software. Het is daarom van belang dat een elektrotechnisch ingenieur in staat is om real-time software te ontwikkelen.

Globale leerdoelen.

De beginnende elektrotechnische ingenieur die de cursus RTSOF heeft gevolgd is in staat om real-time software te ontwikkelen. Hij/zij is bekend met de specifieke kenmerken van realtime systemen en kent verschillende implementatievormen van real-time software.

Als je deze cursus met een voldoende hebt afgesloten:

• Ken je de verschillende definities van real-time systemen, de karakteristieke eigenschappen van real-time systemen en enkele voorbeelden van real-time systemen.
• Ken je het verschil tussen processes en threads, weet je wanneer ze te gebruiken en kun je ze gebruiken zowel in POSIX als in C++ (Boost).
• Kun je een concurrent programma in C (met POSIX) en in C++ (met Boost) implementeren.
• Ken je de voor- en nadelen van de synchronisatie via gemeenschappelijk geheugen versus synchronisatie via berichten.
• Kun je verschillende vormen van synchronisatie en communicatie via gemeenschappelijk geheugen toepassen, te weten: Mutex, semaphores, conditional critical regions, monitors en protected objects.
• Kun je verschillende vormen van synchronisatie en communicatie via berichten toepassen met behulp van POSIX messages.
• Kun je tijdvertragingen en tijdsynchronisatie toepassen in real-time systemen.
• Ken je de verschillen tussen scheduling in een general purpose en in een real-time OS.
• Ben je bekend met verschillende vormen van real-time scheduling.
• Weet je hoe je prioriteiten aan taken moet toekennen.
• Ken je het priority inversion probleem en de oplossingen daarvoor.
• Kun je blocking en response tijden uitrekenen.

Literatuur.

	Real-Time Systems and Programming Languages (Fourth Edition), Alan Burns and Andy Wellings, ISBN: 978-0-321-41745-9 (we gebruiken Hoofdstuk 4 t/m 6, 9, 11 en 12).		Getting started with QNX Neutino 2, Robert Krten, ISBN: ISBN 0-9682501-1-4 (dit boek kun je bij mij lenen).
	Als alternatief voor de bovenstaande 4de editie kun je ook de (oude) 3de editie gebruiken. Real-Time Systems and Programming Languages (Third Edition), Alan Burns and Andy Wellings, ISBN: 0201729881 (we gebruiken Hoofdstuk 7 t/m 10, 12 en 13).

Benodigde hard- en software.

C++, Boost, QNX (of een andere POSIX compatible RTOS).

Toetsing en beoordeling.

Er worden voor deze cursus drie deelresultaten vastgesteld waarbij het eerste en tweede resultaat (beoordeling practische eindopdracht en huiswerkopdacht) cijfers (1..10) zijn en het derde resultaat (practicum) een O(nvoldoende) of V(oldoende) is. Het eindresultaat wordt dan 0.2 * cijfer huiswerk + 0.8 * cijfer eindopdracht als het practicum Voldoende is en een 1 als het practicum Onvoldoende is. Het bodemcijfer is 4.5.

Je kunt naar keuze alleen werken of in tweetallen. Als je ervoor kiest om samen te werken met een partner kies dan wel een partner van ongeveer hetzelfde niveau.

Het practicum wordt beoordeeld met Onvoldoende of Voldoende. Alle opdrachten worden afzonderlijk beoordeeld met een voldoende of onvoldoende aan de hand van:

• de antwoorden die je geeft op de in de opdracht gestelde vragen en een demonstratie om de juiste werking van de software aan te tonen.
• een inhoudelijk gesprek over opzet en uitvoering van de implementatie. Tijdens dit gesprek zal de docent enkele vragen stellen over de manier van aanpak en/of de werking van het programma. Als je deze vragen (over je eigen programma) niet kunt beantwoorden dan krijg je onvoldoende! Als bij jou een opdracht met onvoldoende wordt beoordeeld krijg je 1 keer de kans een vervangende opdracht te maken.

Om het practicum met een voldoende af te sluiten moeten alle opdrachten voldoende zijn.

Weekplanning theorie.

Let op! Deze planning kan tijdens het geven van deze onderwijsmodule nog worden aangepast!

week	inhoud	sheets	boek 3de ed	boek 4de ed	leesvoer
1	Introductie, concurrent programming met de nadruk op Pthreads en shared variabele based synchronisation. Het opfrissen van de bij OPSYS opgedane kennis.	RTSOF_deel1.pps. RTSOF_deel1.pdf.	H7 en H8. Zie hieronder voor details.	H4 en H5. Zie hieronder voor details.	RTOS versus GPOS . Artikel uit Embedded Computer Design van januari 2005. Verplicht lezen! The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software  Artikel uit Dr. Jobb's Journal van maart 2005. Aanbevolen literatuur.
2	Concurrent programming in C++ met Boost.	RTSOF_deel2.pps. RTSOF_deel2.pdf.	Zie hieronder voor details.		Boost thread library documentatie Hoef je niet door te lezen maar heb je wel nodig op het practicum. What's New in Boost Threads? Artikel uit Dr. Jobb's Journal van oktober 2008. Aanbevolen literatuur.
3	Message-based synchronisation and communication. Voorbeeld van concurrent programming in een embedded systeem.	RTSOF_deel3.pps. RTSOF_deel3.pdf.	H7 en H9. Zie hieronder voor details.	H4 en H6. Zie hieronder voor details.	-
4	Real-time facilities.	RTSOF_deel4.pps. RTSOF_deel4.pdf.	H12. Zie hieronder voor details.	H9. Zie hieronder voor details.	-
5	Scheduling.	RTSOF_deel5.pps. RTSOF_deel5.pdf.	H13. Zie hieronder voor details.	H11. Zie hieronder voor details.	-
6 + 7	Uitloop + begeleiding bij de eindopdracht.	-	-		--

Gedetailleerde planning theorie.

Week 1. Introductie, concurrent programming met de nadruk op Pthreads en shared variabele based synchronisation.

• Boek 3de editie: hoofdstuk 7: hoofdstuk 7 t/m 7.3.4 bestuderen. Inleiding processen en threads. 7.3.5 overslaan. Occam wordt in de praktijk niet veel gebruikt. 7.3.6 overslaan. Ada wordt in Europa niet veel gebruikt. 7.3.7 overslaan. Java wordt (bijna) nooit gebruikt in real-time applicaties. 7.3.8 overslaan. 7.3.9 bestuderen. Threads in POSIX. Komt ook op het practicum aan de orde. Zie voor meer info: POSIX = IEEE Std 1003.1-2001 = The Open Group Base Specifications Issue 6 QNX documentation 7.4 nu overslaan. Komt in week 3 aan de orde.

  Boek 4de editie: hoofdstuk 4: hoofdstuk 4 t/m 4.3.3 bestuderen. Inleiding processen en threads. 4.4 overslaan. Ada wordt in Europa niet veel gebruikt. 4.5 overslaan. Java wordt (bijna) nooit gebruikt in real-time applicaties. 4.6 bestuderen. Threads in POSIX. Komt ook op het practicum aan de orde. Zie voor meer info: POSIX = IEEE Std 1003.1-2001 = The Open Group Base Specifications Issue 6 QNX documentation 4.7 overslaan. 4.8 nu overslaan. Komt in week 3 aan de orde. 4.9 bestuderen.

• Boek 3de editie: hoofdstuk 8: Inleiding, 8.1 en 8.2 bestuderen. De problemen bij gedeelde variabelen, de noodzaak tot synchronisatie en de oplossing met behulp van busy waiting zijn allemaal al bij OPSYS in semester EQ2r (of EP2mv) besproken. 8.3 overslaan. Het gebruik van suspend en resume lost wel het efficiency probleem van busy waiting op maar leidt tot critical races en is dus niet veilig. 8.4 t/m 8.4.4 bestuderen. Semaphoren zijn al besproken bij OPSYS in semester EQ2r (of EP2mv). 8.4.5 overslaan. 8.4.6 bestuderen. Semaphoren in POSIX. Komt ook op het practicum aan de orde. 8.4.7 bestuderen. Kritiek op semaphoren. 8.5 bestuderen. CCRs zijn een "opstapje" naar monitors. 8.6 tot 8.6.1 bestuderen. Monitors. 8.6.1 overslaan. Modula 1 wordt niet veel gebruikt. 8.6.2 overslaan. Mesa wordt niet veel gebruikt. 8.6.3 bestuderen. POSIX mutex en conditionele variabelen. 8.6.4 bestuderen. Genest aanroepen van monitors. 8.6.5 bestuderen. Kritiek op monitors. 8.7 overslaan. Protected objects worden in Ada gebruikt. 8.8 overslaan. Java wordt (bijna) nooit gebruikt in real-time applicaties.

  Boek 4de editie: hoofdstuk 5: Inleiding, 5.1 en 5.2 bestuderen. De problemen bij gedeelde variabelen, de noodzaak tot synchronisatie en de oplossing met behulp van busy waiting zijn allemaal al bij OPSYS in semester EQ2r (of EP2mv) besproken. 5.3 overslaan. Het gebruik van suspend en resume lost wel het efficiency probleem van busy waiting op maar leidt tot critical races en is dus niet veilig. 5.4 t/m 5.4.4 bestuderen. Semaphoren zijn al besproken bij OPSYS in semester EQ2r (of EP2mv). 5.4.5 en 5.4.6 overslaan. 5.4.7 bestuderen. Semaphoren in POSIX. Komt ook op het practicum aan de orde. 5.4.8 bestuderen. Kritiek op semaphoren. 5.5 bestuderen. CCRs zijn een "opstapje" naar monitors. 5.6 bestuderen. Monitors. 5.7 bestuderen. POSIX mutex en conditionele variabelen. 5.8 overslaan. Protected objects worden in Ada gebruikt. 5.9 overslaan. Java wordt (bijna) nooit gebruikt in real-time applicaties. 5.10 en 5.11 overslaan.

• Programma's:
  • Aanmaken van processen in POSIX zonder fflush: fork.c bijbehorende makefile en output.txt .
  • Aanmaken van processen in POSIX met fflush: fork.c bijbehorende makefile en output.txt .
  • Aanmaken van threads in POSIX zonder parameteroverdracht: pthread.c bijbehorende makefile en output.txt .
  • Aanmaken van threads in POSIX met parameteroverdracht: pthread.c bijbehorende makefile en output.txt .
  • Voorbeeld van het gebruik van een monitor die in POSIX geïmplementeerd wordt met een mutex en conditionele variabelen: teller.c bijbehorende makefile en output.txt .
• Extra leesvoer:
  • Concurrent programmeren zal in de toekomst ook erg belangrijk wordt in "general purpose" applicaties (en niet meer alleen in real-time applicaties). Deze bewering wordt gedaan door Herb Sutter en zijn artikel kun je lezen op: http://www.gotw.ca/publications/concurrency-ddj.htm.
  • Dit recent web seminar van Mentor Graphics beantwoord de vraag: Why do I need an RTOS anyway? http://go.mentor.com/c2vq

Week 2. Concurrent programming in C++ met Boost.

• Leerstof:
  • Boost thread library documentatie
  • What's New in Boost Threads? Een artikel uit Dr Jobbs van oktober 2008.
• Hopelijk bekende leerstof:
  • C++ exceptions: Zie paragraaf 6.6 van het PROS3 dictaat .
  • Boost lambda library (dit is bij het keuzevak ALDAT behandeld, als je geen ALDAT hebt gevolgd dan mag je het onderstaande programma waarin de Boost lambda library wordt gebruikt overslaan): lambda.htm
• Programma's:
  • Aanmaken van threads in Boost zonder parameteroverdracht: main.cpp en bijbehorende output.txt .
  • Aanmaken van threads in Boost met parameteroverdracht: main.cpp en bijbehorende output.txt .
  • Voorbeeld van een class Point die niet geschikt is om in een multithreaded omgeving te gebruiken: main.cpp en bijbehorende output.txt .
  • De class Point kan geschikt gemaakt worden om in een multithreaded omgeving te gebruiken met behulp van een mutex: main.cpp en bijbehorende output.txt .
    • Later zul je leren dat het beter (en eenvoudiger) is om een mutex in combinatie met een lock te gebruiken. 
  • Een uitbreiding van de bovenstaande class Piont die wel correct werkt maar waarbij je (mogelijk) onnodig moet wachten: main.cpp .
  • De oplossing van het bovenstaande "onnodig wachten" probleem met behulp van een shared_mutex: main.cpp .
    • Later zul je leren dat het beter (en eenvoudiger) is om een mutex in combinatie met een lock te gebruiken.
  • De class Point kan eenvoudiger en beter (lees: exception safe) geschikt gemaakt worden om in een multithreaded omgeving te gebruiken met behulp van een mutex in combinatie met een lock_guard: main.cpp .
  • De oplossing van het bovenstaande "onnodig wachten" probleem met behulp van een shared_mutex in combinatie met een lock_guard en een shared_lock: main.cpp .
  • Voorbeeld van het gebruik van een monitor die in Boost geïmplementeerd wordt met een mutex, een condition_variable, een unique_lock en een lock_guard: main.cpp en bijbehorende output.txt .
  • Andere versie van het bovenstaande monitor programma, in plaats van een simpele wait wordt nu een wait met een predicate gebruikt. De predicate specificeert de conditie waarop door de conditionele variabele gewacht wordt. In deze versie wordt een gewone functie gebruikt om de predicate te specificeren: main.cpp .
  • Nog een andere versie van het bovenstaande monitor programma, in dit geval wordt een C++0x lambda functie gebruikt om predicate te specificeren: main.cpp .
• Extra (niet verplicht) leesvoer: µC++ voegt concurrency toe aan C++ door middel van taalconstructies (onder andere task en monitor).
  • Examining µC++ , high-level object-oriented concurrency for C++. Een artikel uit DrDobbs van februari 2006.
    Zie eventueel ook: http://plg.uwaterloo.ca/~usystem/uC++.html

Week 3. Message-based synchronisation and communication + voorbeeld van concurrent programming in een embedded systeem.

• Boek 3de editie: hoofdstuk 9: Inleiding, 9.1 en 9.2 bestuderen. Inleiding messages. 9.3 en 9.4 overslaan. 9.5 bestuderen. POSIX messages. Zie: mqueue.h 9.6 overlaan. 9.7 overlaan.

  Boek 4de editie: hoofdstuk 6: Inleiding, 6.1 en 6.2 bestuderen. Inleiding messages. 6.3 t/m 6.6 overslaan. 6.7 bestuderen. POSIX messages. Zie: mqueue.h 6.8 overlaan. 6.9 overlaan.

• Boek 3de editie: hoofdstuk 7: 7.4 probleembeschrijving bestuderen. A simple embedded system.

  Boek 4de editie: hoofdstuk 4: 4.8 probleembeschrijving bestuderen. A simple embedded system.

  

• Programma's:
  • sequentiële oplossing: par74.c bijbehorende makefile en output.txt .
  • oplossing met processen: par74.c bijbehorende makefile en output.txt .
  • oplossing met pthreads zonder synchronisatie: par74.c bijbehorende makefile en output.txt .
  • oplossing met pthreads met synchronisatie: par74.c bijbehorende makefile en output.txt .
  • oplossing met C++ en Boost met synchronisatie: main.cpp en output.txt .
  • oplossing met pthreads met mqueue: par74.c bijbehorende makefile, output.txt en een screenshot van /dev/mqueue

Week 4. Real-time facilities.

• Boek 3de editie: hoofdstuk 10: 10.6 bestuderen. POSIX signals nodig voor het begrijpen van 12.7.1 en 12.8.1.

  Boek 4de editie: hoofdstuk 7: 7.5.1 bestuderen. POSIX signals nodig voor het begrijpen van 12.7.1 en 12.8.1.

• Boek 3de editie: hoofdstuk 12: Inleiding, 12.1 bestuderen. Inleiding time. 12.2 tot 12.2.1 bestuderen. Inleiding clock. 12.2.1 tot 12.2.4 overslaan. 12.2.4 bestuderen. Clocks in POSIX. Zie clock_xxx() en time.h . 12.3 bestuderen. Behalve: Ada voorbeeld in 12.3.1 en Ada en Occam voorbeeld in 12.3.2. 12.4 tot 12.4.2 bestuderen. Behalve: Real-Time Euclid en Ada voorbeeld in 12.4.1. 12.4.2 en 12.4.3 overlaan. 12.5 en 12.6 bestuderen. 12.7 tot 12.7.2 bestuderen. Behalve: Ada voorbeeld. 12.7.2 t/m 12.7.5 overlaan. 12.8 tot 12.8.1 overslaan. 12.8.1 bestuderen. Behalve: Ada en RTJ voorbeelden. 12.8.2 en 12.8.3 overslaan.

  Boek 4de editie: hoofdstuk 9: Inleiding, 9.1 bestuderen. Inleiding time. 9.2 tot 9.2.1 bestuderen. Inleiding clock. 9.2.1 tot 9.2.3 overslaan. 9.2.3 bestuderen. Clocks in POSIX. Zie clock_xxx() en time.h . 9.3 tot 9.3.2 bestuderen. 9.4 tot 9.4.2 bestuderen. 9.4.2 en 9.4.3 overlaan. 9.5 en 9.6 tot 9.6.1 bestuderen.

• Programma's:
  • Voorbeeld van het gebruik van een monitor die in POSIX geïmplementeerd wordt met een mutex en conditionele variabelen waarbij een pthread_cond_timedwait wordt gebruikt: teller.c bijbehorende makefile en output.txt .
  • Voorbeeld van het gebruik van een monitor die in Boost geïmplementeerd wordt met een mutex, een condition_variable, een unique_lock en een lock_guard waarbij een timed_wait wordt gebruikt: main.cpp en bijbehorende output.txt .

Week 5. Scheduling.

• Boek 3de editie: hoofdstuk 13: Inleiding, 13.1 tot 13.4.1 bestuderen. 13.4.1 overslaan. 13.5 bestuderen. 13.6 overslaan. 13.7 bestuderen. 13.8 tot 13.8.2 bestuderen. 13.8.2 en 13.8.3 overslaan. 13.9 en 13.10 bestuderen. Het priority inversion probleem dat hier wordt besproken is zelf op de planeet Mars al eens opgetreden. Zie http://www.youtube.com/watch?v=lyx7kARrGeM. 13.11 tot 13.11.3 bestuderen. 13.11.3 overslaan. 13.12 en 13.13 overslaan. 13.14 bestuderen. Behalve: 13.14.1 Ada en 13.14.3 RTJ. Opgaven 1, 2, 4, 5, 6 en 7 maken. Probeer het eerst zelf en controlleer jezelf met behulp van mijn uitwerkingen.

  Boek 4de editie: hoofdstuk 11: Inleiding, 11.1 tot 11.6.2 bestuderen. 11.6.2 overslaan. 11.7 t/m 11.9 bestuderen. Het priority inversion probleem dat in 11.8 wordt besproken is zelf op de planeet Mars al eens opgetreden. Zie http://www.youtube.com/watch?v=lyx7kARrGeM. 11.10 t/m 11.16 overslaan. Opgaven 1, 2, 4, 5, 6 en 7 maken. Probeer het eerst zelf en controlleer jezelf met behulp van mijn uitwerkingen.

• Extra leesvoer:
  • 3 Things Every Programmer Should Know About RMA (Rate Monotonic Algorithm): http://embeddedgurus.com/blog/2010/08/3-things-every-programmer-should-know-about-rma/ 

Weekplanning practicum.

Bij dit practicum wordt op een iets andere manier gewerkt dan dat je tot nu toe gewend was. De practicumopgaven worden in groepjes van 2 studenten uitgevoerd. Het is de bedoeling dat je ongeveer 4 uur/week aan dit practicum besteedt. Als je bij het werken aan het practicum tegen problemen aanloopt waardoor je niet verder kunt wacht dan niet tot het ingeroosterde uur maar stuur een mailtje naar J.Z.M.Broeders@hhs.nl.

week	opdracht	studiemateriaal	onderwerp
1	opdracht 1	Theorie van week 1.	Inleiding QNX.
2+3	opdracht 2	Theorie van week 1 en 3.	Multi-threaded programmeren in POSIX.
4	opdracht 3	Theorie van week 2.	Multi-threaded programmeren in C++.
5 t/m 7 + week 8	opdracht 4	-	Eindopdracht.