Studiewijzer module RTSYST

© Harry Broeders.

Inleiding.

Software waarvan het resultaat niet alleen correct maar ook exact op tijd moet zijn wordt real-time software genoemd. Vooral het begrip voorspelbaarheid is erg belangrijk bij real-time systemen. Om het ontwikkelen van real-time software eenvoudiger te maken wordt vaak gebruik gemaakt van een Real-Time Operating System (RTOS). 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 m.b.v. een RTOS.

Globale leerdoelen.

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

Als je dit vak 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++11.
• Kun je een concurrent programma in C (met POSIX) en in C++11 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: mutexes, semaphores, conditional critical regions en monitors.
• 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 responsetijden uitrekenen.

Literatuur.

Real-Time Systems and Programming Languages (Fourth Edition), Alan Burns and Andy Wellings, ISBN: 978-0-321-41745-9 (we gebruiken Hoofdstuk 1, 4 t/m 6, 9 en 11).

Getting started with QNX Neutino 2, Robert Krten, ISBN: ISBN 0-9682501-1-4 (dit boek kun je bij mij lenen).

Benodigde hard- en software.

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

Toetsing en beoordeling.

Er worden voor deze cursus twee resultaten vastgesteld die beide apart in OSIRIS worden gezet: RTSYST-co1|real-time systemen (TOETS01) en RTSYST-pr1|real-time systemen (TOETS02). Voor beide toetsen moet je inschrijven! RTSYST-co1 is een schriftelijke toets in week 8 met een herkansing in week 10, het resultaat is een cijfer (1..10). Bij het tentamen mag je boeken, dictaten, oude toetsen en aantekeningen gebruiken. Het tentamen bestaat uit open vragen. RTSYST-pr1 is een practicum beoordeling, het resultaat is een O(nvoldoende) of een V(oldoende). Het practicum moet afgerond zijn in week 7. In week 10 kan het practicum herkanst worden.

Op het practicum werk je in tweetallen. Kies 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 zal tijdens het geven van deze onderwijsmodule nog worden aangepast!

week	inhoud	sheets	boek	leesvoer
1	Introductie, concurrent programming met de nadruk op Pthreads.	RTSYST_week1.ppsx. RTSYST_week1.pdf.	H1 en H4. Zie hieronder voor details.	Verplicht lezen: RTOS versus GPOS . Artikel uit Embedded Computer Design van januari 2005. Aanbevolen literatuur: The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software  Artikel uit Dr. Jobb's Journal van maart 2005. TLAs: QNX, RIM, ARM, CES, RPM, and MPH An RTOS for the Automotively Inclined Artikel over populariteit en toepassingen QNX uit Electronic Engineering Journal van september 2012.
2	Shared variabele-based synchronisation and communication.	RTSYST_week2.ppsx. RTSYST_week2.pdf.	H5. Zie hieronder voor details.	-
3	Concurrent programming in C++11.	RTSYST_week3.ppsx. RTSYST_week3.pdf.	-	Aanbevolen literatuur: Blog over C++11 threads .
4	Message-based synchronisation and communication. Voorbeeld van concurrent programming in een embedded systeem.	RTSYST_week4.ppsx. RTSYST_week4.pdf.	H4 en H6. Zie hieronder voor details.	-
5	Real-time facilities.	RTSYST_week5.ppsx. RTSYST_week5.pdf.	klein deel H7,H9 en klein deel H13. Zie hieronder voor details.	-
6 en 7	Scheduling.	RTSYST_week6_en_7.ppsx. RTSYST_week6_en_7.pdf.	H11. Zie hieronder voor details.	-

Gedetailleerde planning theorie.

Week 1. Introductie, concurrent programming met de nadruk op Pthreads.

• Boek: hoofdstuk 1:
  • Inleiding, 1.1 t/m 1.3 bestuderen.
  • 1.4 en 1.5 overslaan.
• Boek: 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-2013: The Open Group Base Specifications Issue 7 of (via de bibliotheek van de HHS): http://ieeexplore.ieee.org.ezproxy.hhs.nl:2048/stamp/stamp.jsp?tp=&arnumber=6506091&tag=1 (3906 pagina's)
    • QNX documentation
  • 4.7 overslaan.
  • 4.8 nu overslaan. Komt in week 4 aan de orde.
  • 4.9 bestuderen.
• Programma's:
  • Herhaling programmeren in C: pointer naar functie pointerNaarFunctie.c en pointerNaarFunctieAfko.c .
  • C programmeren: void* void_pointer.c .
  • C en C++ programmeren: command line arguments command_line_arguments.c .
  • 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 .
• Verplicht leesvoer:
  • RTOS versus GPOS . In dit artikel uit Embedded Computer Design van januari 2005 wordt heel duidelijk uitgelegd wat het verschillen zijn tussen een RTOS (Real-Time Operating System) zoals QNX en een GPOS (General Purpose Operating System) zoals Windows of Linux.
• Extra leesvoer:
  • TLAs: QNX, RIM, ARM, CES, RPM, and MPH An RTOS for the Automotively Inclined . Artikel over populariteit en toepassingen QNX uit Electronic Engineering Journal van september 2012.
  • Concurrent programmeren is op dit moment ook erg belangrijk geworden in "general purpose" applicaties (en niet meer alleen in real-time applicaties). Dit werd in 2005 al voorspeld door Herb Sutter in zijn artikel: The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software.
  • Dit web seminar van Mentor Graphics beantwoord de vraag: Why do I need an RTOS anyway?

Week 2. Shared variabele-based synchronisation and communication.

• Boek: 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.
  • 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.
  • 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:
  • Probleem met gedeeld geheugen: mutex_problem.c bijbehorende makefile en output.txt .
  • Oplossing voor bovenstaand probleem met behulp van een mutex: mutex_solution.c bijbehorende makefile en output.txt .
  • Dining Philosophers: dining_philosophers.c met bijbehorende makefile.
  • Oplossing van het Dining Philosophers probleem waarbij een semaphore wordt gebruikt om er voor te zorgen dat er nooit meer dan 4 filosofen tegelijkertijd gaan (proberen om te) eten: dining_philosophers.c met bijbehorende makefile.
  • 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 .
  • Oplossing van het Dining Philosophers probleem waarbij een monitor (mutex in combinatie met een conditionele variabele) wordt gebruikt om er voor te zorgen dat er nooit meer dan 4 filosofen tegelijkertijd gaan (proberen om te) eten: dining_philosophers.c met bijbehorende makefile.
  • Oplossing van het Dining Philosophers probleem waarbij deadlock wordt voorkomen door de volgorde waarin de vorken worden opgepakt te variëren: dining_philosophers.c met bijbehorende makefile.

Week 3.Concurrent programming in C++11.

• Leerstof (niet verplicht):
  • C++11 lambda functies (zijn ook in het keuzevak ALGODS behandeld).
• Zelf te bestuderen leerstof:
  • C++ exceptions: Zie paragraaf 6.8 van het OGOPRG dictaat .
• Programma's (gebruik Microsoft Visual C++ 2013 of GCC4.8 met de optie -std=c++11):
  • Aanmaken van threads in C++11 zonder parameteroverdracht: main.cpp en bijbehorende output.txt .
  • Aanmaken van threads in C++11 met parameteroverdracht: main.cpp en bijbehorende output.txt .
  • Eenvoudig programma dat de "hardware concurrency" laat zien: main.cpp .
  • Voorbeeld van een class Point die niet geschikt is om in een multithreaded omgeving te gebruiken: main.cpp .
  • De class Point kan geschikt gemaakt worden om in een multithreaded omgeving te gebruiken met behulp van een mutex: main.cpp .
    • 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 .
  • Om het bovenstaande "onnodig wachten" probleem op te lossen moet je gebruik maken van boost::shared_mutex (standaard C++11 kent geen shared_mutex) of moet je zelf met behulp van een monitor een shared_mutex implementeren (Zie onderstaande opgave!).
  • 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 .
  • Voorbeeld van het gebruik van een monitor die in C++11 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 .
  • (niet verplicht) Nog een andere versie van het bovenstaande monitor programma, in dit geval wordt een C++11 lambda functie gebruikt om predicate te specificeren: main.cpp .
  • Voorbeeldprogramma dat eenvoudig concurrent gemaakt kan worden: main.cpp en de concurrent versie met async: main.cpp .
  • Hetzelfde programma maar dan met gebruik van auto: main.cpp .
  • Hetzelfde programma waarbij de programmeur heeft aangegeven of er een aparte thread gestart moet worden door async: main.cpp .
  • Voorbeedprogramma met async en StopWatch zodat je de snelheidswinst kunt meten (het programma werkt met gebruik van async 2x zo snel): main.cpp .
  • Voorbeeldprogramma dat laat zien wat het probleem is als meerder theads dezelfde globale variabele gebruiken: main.cpp .
  • Oplossing voor het bovenstaande probleem met behulp van een mutex: main.cpp .
  • Oplossing voor het bovenstaande probleem met behulp van een mutex en een lock_guard: main.cpp .
  • Oplossing voor het bovenstaande probleem met behulp van een atomic: main.cpp .
• Opgaven C++11:
  • Implementeer zelf een shared_mutex class met de in C++11 beschikbare mutex en condition_variable.
    • Uitwerking main.cpp  met output.txt .
    • Ander testprogramma main.cpp  met output.txt dat laat zien dat lezers ook toegang krijgen als er een schrijver staat te wachten.
    • Uitwerking waarbij lezers geen toegang meer krijgen als er een schrijver staat te wachten: main.cpp  met output.txt .
  • Implementeer zelf een barrier class met de in C++11 beschikbare mutex en condition_variable.
    • Uitwerking main.cpp  met output.txt .
    • Ander testprogramma met gesynchroniseerde output main.cpp .
    • Ander testprogramma zonder globale variabelen waarbij het aantal threads door de gebruiker kan worden opgegeven main.cpp met output.txt (voor 20 threads).
• Aanbevolen literatuur: Blog over C++11 threads .
• Extra (niet verplicht) leesvoer: C++ Concurrency in Action - Practical Multithreading, Anthony Williams, February 2012, 528 pages, ISBN: 9781933988771.
• 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.
  • Understanding Control Flow with Concurrent Programming using µC++. Een (draft van een) boek uit 2013.

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

• Boek: 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: hoofdstuk 4:
  • 4.8 probleembeschrijving bestuderen. A simple embedded system.

  

• Programma's:
  • sequentiële oplossing: 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++11 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 5.Real-time facilities.

• Boek: 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 . Zie ook: http://bd.eduweb.hhs.nl/micprg/time.htm
  • 9.2.4 bestuderen, behalve Ada en Real-Time Java.
  • 9.3 tot 9.3.2 bestuderen.
  • 9.3.2 overslaan.
  • 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.
  • 9.6.1 overslaan.
• Boek: hoofdstuk 7:
  • 7.5.1 bestuderen. POSIX signals nodig voor het begrijpen van 10.4.2, 13.2.3 en 13.3.1.
• Boek: hoofdstuk 10:
  • 10.4.2 bestuderen. Time-triggered events in C/Real-Time POSIX.
• Boek: hoofdstuk 13:
  • 13.2 en 13.2.3 bestuderen. Deadline overrun detectie.
  • 13.3 en 13.3.1 bestuderen. Maximum execution time overrun detectie.
• 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 C++11 geïmplementeerd wordt met een mutex, een condition_variable, een unique_lock en een lock_guard waarbij een wait_for wordt gebruikt: main.cpp en bijbehorende output.txt .

Week 6 en 7.Scheduling.

• Boek: 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 opgave: Oefenopgave RTSYST FPS-RMPA.pdf .
• 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.

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.