Autronica Fire and Security (AFS)

320 ansatte, 565 mill NOK omsetning (2007) På Lade, her i Trondheim Samme sted, og for meg - seks logoer Autronica - børs - Whessoe - Navia AFS ble etablert som datterselskap til Autronica AS og solgt til Williams (UK, 1998) Autronica AS ble fusjonert sammen med Seatex til Navia Maritime (1998) som ble kjøpt av Kongsberg Maritime (NO, 2000) Williams ble splittet i Kidde og Chubb (UK). AFS ble med inn i Kidde, (UK, 2000). Maritim brann (og meg) hos Kongsberg ble solgt til AFS, sammen med Autronica-navnet (2002) Kidde kjøpt av United Technologies / UTC (US, 2005) "A UTC Fire & Security Company" - United Technologies Corporation, 210000 ansatte med selskap som bla.a. Otis, Pratt & Whitney, Hamilton Sundstrand, Carrier og tidligere Kidde (nå UTC Fire & Security, som vi er en del av)

Bare så det er sagt

Øyvind Teig (CV)

NTH, 1975 Autronica, 1976-nå (studentjobbing der fra 1972) HW og SW (mest SW) Har jobbet med embeddedsystemer hele tida Publisert en del - relativt uvanlig i industrien Hjemmesiden min: http://home.no.net/oyvteig

Pappesken (SW)

HW/SW for 30+ år i den pappesken Diverse assembler (78-80) PL/M (80-90) Modula-2 (88-90) MPP-Pascal (82-88) occam (90-01) C (02-nå) Java (97-00) Perl (02)
	Øverst til høyre (fra diplomen 1975) Den papirtapen inneholder programmet fremdeles Sann tid - går alt for fort!

Pappesken (mimre)

Pappesken (sanntidsmetodikk & produkt)

• 1978: Ikke noe kjøresystem, ren assembler - Dieselaggregat start/stopp nødstrøm
• 1979: MPP Pascal med prosessbegrep - Protokollkonvertering, radarbasert nivåmåling og brannvarsling
• 1980: PL/M med NTH-utviklet kjøresystem - Maskinromsovervåking
• 1982: Assembler med jobbsnekret kjøresystem - Brannvarsling
• 1988: PL/M med jobbsnekret kjøresystem - Brannvarsling
• 1988: Modula-2 med kjøpt kjøresystem - Brannvarsling
• 1990: occam med prosessbegrep - Motormålinger og effektberegninger
• 1995: C med VxWorks opsys/kjøresystem - Brannvarsling
• 2003-8: C med jobbsnekret SDL og kanal-lag "CHAN_CSP" kjøresystem - Brannvarsling

Lange år

• OO er fra sekstitallet
• I bruk nå, men lite i embedded (blir mer og mer!)
• Sanntidsmekanismene er fra 60-70+ tallet
• Semafor etc. i bruk siden da
• CSP etc. fra 70-tallet. Lite i bruk (ennå?)
• UML 2.0 ute - stort, og uten aksjonsspråk
• Java -"synchronized" - det første allment brukte språket som har concurrency-tankegang innebygd..
• ..og som er "livsfarlig" å bruke!
• ..men som det går an å bygge CSP oppå!

• Men, dette går da ikke fort!

Etter forelesningen ønsker jeg..

• At dere skal huske at å jobbe med (s) embeddedsystemer, er gøy
• Sa jeg (sivile)?

• At dere skal huske at kanaler mellom prosesser er et - av flere - verktøy 
  Som kan gjøre kompleks programvare enklere!
• wiki: "En sivilingeniør har til oppgave å løse praktiske problemer, ofte i team og i samarbeid med kunden".
  At dere skal huske å fortelle om det dere har lært i dette faget når dere havner i slike team!

SDL + CHAN_CSP lag = "kanaler"

Alt dette er kode som vi har utviklet sjøl. Først SDL (FSM-kjøresystem), så CHAN_CSP laget oppå

Kanal-lag teknologi i

1988-90 PL/M-51 Egenutviklet mailboksbasert kjøresystem Flere occam-system med transputer (90-95) Flere occam-system med SPoC og Texas DSP (95-00) 2005-nå Samme system i deler av ny brannsentral : I sløyfeprosessoren, som vi kaller "AutroLooper"
	C og egenutviklet SDL kjøresystem - asynkrone meldinger Egenutviklet CSP lag oppå, gir synkrone og blokkerende data-kanaler. Kooperativ scheduling

Artikler om kanal-laget

Ercim-2005 - Porto	CPA-2006 - Edinburgh	CPA-2007 - Surrey

• Dette foredraget henter mesteparten av stoffet fra disse tre artiklene
• 2005 (Porto) - om CSP lag over SDL i små kontrollere
  "From message queue to ready queue"
• 2006 (Edinburgh) - videreutvikling og mer om patterns
  "No Blocking on Yesterday's Embedded CSP Implementation"
• 2007 (Surrey) - samarbeid og egenarbeid
  "High Cohesion and Low Coupling: the Office Mapping Factor" ("Kontortilordningsfaktor")

Hvorfor vi lagde kanal-laget

• Erfaring med synkrone kanaler (med occam og occam/SPoC)

• Det kjentes derfor tryggere å bygge arkitekturen med denne metodikken
• Antatt komplekst system, med mange prosessser og meldinger - et reaktivt system
• Gjett om vi fikk rett (komplekst system)!

Hvorfor vi ikke burde ha gjort det

• Forklaringsproblem i ettertid
• Vanskelig å vise om dette funker bedre, like godt eller dårligere 
• enn tilsvarende bygd som "tradisjonelt meldingssystem"
• Forhåpentligvis vil tida komme oss i møte?
• Vi har et stort system, som også med vår løsning, er kompleks
• Feil har en tendens til å dukke opp tidlig, heller enn sent (men dette er vel egentlig en fordel)
• Ekstra state-maskin lag for å håndtere synkron kommunikasjon vha. C-kall er, tross alt, en tilleggskompleksitet (to skritt fram og ett tilbake)
• Alle liker vel best det de kan - og de fleste kan "tradisjonelle meldingssystem" 
• Det tar tid å lære seg denne "prosess-orienterte" tankegangen
• Se ekstranotatet, ref. siste side (her)

Hvorfor vi hadde gjort det igjen

• Tette prosesser med ryddige kommunikasjonsmønstre er kanskje de beste byggeklossene man har funnet på. Metodikken tilbyr akkurat det, uten kompliserende mekanismer
• Når vi har "lært oss" tankemåten, er det et nydelig verktøy å ha tilgjengelig og kunne bruke
• Faglig tungt
• Historisk: fagutvikling via Dijkstra (semafor, strukturert programmering), Nygaard, Dahl (OO), Brinch-Hansen (monitor), Hoare (CSP)
• Siste(1): occam-pi: http://www.occam-pi.org/ 
• Siste(2): Singularity OS fra Microsoft: http://research.microsoft.com/os/singularity/
• For å gå videre: prøve å forstå kultur og personlighetsforskjellene i framgangsmåte for å løse problem
• Seymour Papert (http://www.papert.org/) and Sherry Turkle: "Epistemological Pluralism and the Revaluation of the Concrete", http://www.papert.org/articles/EpistemologicalPluralism.html

Protokoller

• Det er vha. protokoller alle sanntidsprosesser snakker sammen. Her er noen tips om dette, for referanse.
• Å forstå hva en protokoll er - er viktig!
• Kommunikasjonsspråket mellom sw "prosesser" og mellom datamaskiner
• I hvilken grad skal en protokoll være lesbar av mennesker? (Mest mulig!)
• Navnekonvensjon om hva som ventes (navn, data-ref s39, s40, MSC hva er dette/neste:):
  Get_LooperDirDown_s39_AwaitRe_a :: Get_LooperDirDown_s40_IsRe_a
• To-fase (kvittering på mottatt melding først, så status på utført melding)
• Dir (spontant ned) »»»» Ack/Nack (synkront opp)
  Utført-Ack/Nack (spontan event opp) »»»» Ack/Nac (synkron kvittering ned) 
• Denne protokollen ovenfor dekobler rask kommando med treg utføring av handlingen (
• Timeout eller feilmelding fra lavere protokoll-lag betyr enten programmeringsfeil eller brutt forbindelse. Lett å synke seg opp
• Roller (senere)

Prosess-orientert programmering (POP)

• Prosess-orientert programmering: tette lettvekststråder som kommuniserer på en verifisert sikker måte
• Ikke dette: big loop + asynkrone interrupt
• Beskyttelse av felles data og data med asynkron I/O vha. CREW (Concurrent Read Exclusive Write)
• Om du ser at du begynner å håndtere mange tilstandsmaskiner, få tak i et kjøresystem som kjører prosessene
• La dem kommunisere vha. meldinger - ikke vha. pekere til felles data (mye vanskeligere å få det sikkert)
• Glem semaforer om du kan (pakk inn felles data i prosess med aksessmeldinger over kanaler)
• Et ikke-preemptivt kjøresystem er ofte mer enn godt nok (bla. a en delt stack til alle prosessene)
• Man har jo interrupt som tar seg av avbrudd
• Konstruer tilstandsmaskiner, en eller flere per prosess (gjerne vha. verktøy som Rhapsody)
• Vurder synkron mot asynkron meldingsformidling
• Trenger begge i verktøykassa, men i synkron er lettest å få til å funke & funke
• http://home.no.net/oyvteig/pub/notes/14_Process_objects.html

API i vårt kanal-lag (1)

API funksjoner er pakket i makroer:

#define CHAN_INIT_F (CHAN,SENDER,RECEIVER,ALTTAKEN)

#define CHAN_IN_F (CHAN,DATA,EVENT)

#define CHAN_IN_VARLEN_F (CHAN,LEN,DATA,EVENT)

#define ALT_CHAN_IN_F (GUARD,CHAN,DATA,EVENT,ALTTAKEN)

#define ALT_CHAN_IN_VARLEN_F (GUARD,CHAN,LEN,DATA,EVENT,ALTTAKEN)

#define ALT_CHAN_IN_ASYNC_SIGNAL_F (GUARD,CHAN,EVENT,ALTTAKEN) 

#define CHAN_OUT_F (CHAN,DATA,EVENT)

#define CHAN_OUT_VARLEN_F (CHAN,LEN,DATA,EVENT)

#define CHAN_OUT_ASYNC_SIGNAL_F (CHAN,RESCHEDULME) 

#define CHAN_IN_ASYNC_SIGNAL_F (CHAN,EVENT)|

#define ALT_TIMER_IN_F (GUARD,TIME,UNIT,EVENT,ALTSTATE,ALTTAKEN)

#define FSM_RESCHEDULE_F (EVENT)

ALT i vårt kanal-lag (2)

Eksempel på en ALT:

case ST_STATE_IN_ALT_200_202_204_301_A:

{ // CP er "ContextPtr"

ALT_CHAN_IN_ASYNC_SIGNAL_F (CP->Guard_202i, g_chan_202, S_EVENT_ALT_202_A, &alt_taken);

ALT_CHAN_IN_ASYNC_SIGNAL_F (CP->Guard_204i, g_chan_204, S_EVENT_ALT_204_A, &alt_taken);

ALT_CHAN_IN_F (CP->Guard_200i, g_chan_200, CP->Chan_200i, S_200_A, &alt_taken);

ALT_CHAN_IN_F (CP->Guard_301i, g_chan_301, CP->Chan_301i, S_301__A, &alt_taken);

ALT_TIMER_IN_F (P->Guard_Tim, CP->Tim, TU_MS_A, S_TIME_A, &g_ALT_LH &alt_taken);

CP->State = ST_STATE_IN_ALT_200_202_204_301_END_A;

} break;

"Fra meldingskø til readykø"

• Tradisjonell meldingskø == "Readykø"/"Schedulingkø" i kanal-lag implementasjonen
• SDL bunnlag: to N-lengde (konstant lengde lik maks) memcpy per overføring
• CSP lag: en n-lengde (så mye som trengs) memcpy i "rendezvous", ingen data i køa - bare ready-meldinger (som er tomme)
• Sum med CSP lag: to korte N-lengde (ready) pluss en n-lengde memcpy (data)
  Sum vil i snitt være mindre dataskufling

Bufferoverflyt

• Ved asynkrone meldingssystem kan man ikke forhindre at meldinger kan mistes 
• Kjøresystem buffer overflyt (kræsj) ved for rask produsent og for treg konsument
• Ved synkrone system må misting av data eksplisitt håndteres
• Maks kjøresystem kø-størrelse er lik antall prosesser, ikke en pos mer!
• Med begge system bør misting av data håndteres på (et eller annet) applikasjonsnivå
• Husk: verden der ute er i hovedsak asynkron! 
• En tekstmelding kan av og til være mye behageligere enn en oppringing!
  Men man treffer ikke han/henne på kino uten tilbakemelding!
• Et sanntidssystem kan ha 25++ prosesser som kommuniserer data internt over synkrone kanaler
• men som selvfølgelig må forholde seg til kravet om ikke å flyte over ved terminalene
• derfor: håndter overflyt på applikasjonsnivå (interrupt, driver eller prosessnivå)

Blokkerende prosesser

• Et system som består av blokkerende kommunikasjon for å overføre data får ikke gjort mer enn et system som ikke blokkerer
• Heller ikke mindre (som nesten alle tror)
• Sammenhengene kan være langs andre akser enn synkronisitet! [Ref]
• Jo flere prosesser og dermed "parallell slakkhet" - desto mer greier et synkront system
• De fleste funksjoner og prosesser er aktive kort tid om gangen - og passiv venting er hovedbeskjeftigelsen ("run to completion")
• OBS! Synkrone kanaler er ikke implementert i noen busy-poll mekanisme, og polles heller ikke av kjøresystemet. Derfor har du null overhead. De vurderes bare når partene ankommer

Data-komm. som alltid funker (1)

• Asynkron og data-løs: stiplet kanal (to nedover)
• Synkron: heltrukket (en oppover og en nedover)
• En asynkron kanal gir et pattern som umuliggjør vranglås: Den nederste kan når som helst sende opp, men den øverste sender først et asynkront data-løst "signal" ned om at den ønsker å bli forespurt om hva den har på hjertet
• Den andre asynkrone kanalen nedover er en "escape"-kanal, som kan terminere apllikasjonstilstandsmaskinen nede
• Siden de asynkrone meldingene er data-løse, må vi ha to kanaler istedet ("spør meg" og escape)
• Dette er en av våre mønstre hvor rollen er viktig. Nederste er master, øverste slave

Data-komm. som alltid funker (2)

• Her er to utgaver av samme problem: uten (venstre) og med (høyre) overflytbuffer
• Oppadgående alarmer (som aktivt "dras opp") kan nå krysse en nedadgående spontan melding, og samtidig kan en annen nedagående "gi meg mer"-melding eksistere
• Dette gjorde applikasjons-semantikken enklere (høy pri alarmer opp og meldinger ned)
• Vranglåsfritt så lenge protollen (kontrakten) holdes
  
• Rollene til venstre, for øverste/nederste, er forandret (fra slave/master til master(N=2)/master)

occam akkurat nå

• Wiki: http://en.wikipedia.org/wiki/Occam_programming_language
• KRoC: http://www.cs.kent.ac.uk/projects/ofa/kroc/
  
• occam-π: http://www.occam-pi.org/
• Transterpreter: http://www.transterpreter.org/ (Lego Mindstorms etc.)
• SPoC (occam til C, dette har jeg jobbet med i flere år, på Windows og Texas DSP): http://www.hpcc.ecs.soton.ac.uk/software/spoc/ 
• http://wotug.org
• Her burde det være mye å ta tak i for en sprek embedded-programmerer!
• Vi benytter ikke noen av disse verktøyene..
• Boka "Real-Time Systems and Programming Languages" av Alan Burns og Andy Wellings - ed. 4 (kommer 2009) er uten occam. "Nobody is using it" i følge Burns i en mail til meg. Han er like frustrert som jeg er over at gode alternativer til occam ikke finnes

CSP bibliotek

• JCSP: http://en.wikipedia.org/wiki/JCSP og hos
  University of Kent: http://www.cs.kent.ac.uk/projects/ofa/jcsp/
• Se referanselista med flere CSP bibliotek på
  http://en.wikipedia.org/wiki/Communicating_sequential_processes  
• VerilogCSP: http://en.wikipedia.org/wiki/VerilogCSP 
  beregnet for design av asynkron hardware - ref. Wikipedia
• C++CSP2 : http://www.cs.kent.ac.uk/projects/ofa/c++csp/
• libcsp2 (for linux) originalt var libcsp av Rick Beton, men vedlikeholdes nå av Bernhard Sputh. Sjekk dette for Linux, da!
• Vi benytter nok ikke noen av disse bibliotekene.. (men vi har jo vårt eget!)

Sanntidspatologi

• Vranglås, livlås (?livelock), utsulting: bruk mønster (pattern)
• Operativsystem meldingsbuffer overflyt: bruk synkronisering
• Heap overflyt: alloker alt med en gang, aldri frigi
• Stack overflyt: bruk kjør-til-ferdig preemptiv kjøring så trenger du bare en stack! 
• Om preemptiv kjøring, må du ha en stack per prosess med tilsvarende mange mulige stack overflyt!
• Uten rekursjon kunne stacksize vært beregnet av linkeren! (som i occam)
• Array index overflyt (programmer ordentlig!)
• Tilstandsmaskin (applikasjons) vranglås, livlås, utsulting, stopp
• Samme problemverden, ett hakk opp
  

Vranglås også i asynkrone system

• Asynkron kommunikasjon kan også gå i vranglås!
• Enten på applikasjonsnivå,
• eller på kjøresystemnivå
• buffere designes ofte med blokkerende semantikk når de går fulle (da må designet ta høyde for det)
• I MPI message passing standarden kalles et ”safe” system et som har null bufring og synkron komm. [Ref]
• ”k-safe” er et system som har k buffere og som garantert fungerer  

Likevel

• Du kan benytte asynkrone meldinger
• og sjekke om det er plass i bufferet før du sender
• Da unngår du meldingsoverflyt ..
• .. men adderer til gjengjeld kompleksitet i senderprosessen
• Når skal du prøve å sende igjen? (privat schedule)
• Når skal du gi opp, og kaste? (unødvendig overflyt?)
• Hvordan skal du beskytte deg mot uønskede meldinger?
• Tenn rød lampe om du ser at prosessene dine driver med (mye?) ”privat schedulering”

ALT - vakker mekanisme

ALT i occam alt i Limbo select i Ada (to-veis)
accept if/fi i Promela (N-buffer) alt  i UML 2.0 (men semantikken..) select  i Unix (men asynkron..)

"Office Mapping Factor"

• Med "Office Mapping Factor" ("Kontortilordningsfaktor"?) mener vi graden som en programarkitektur kan mappes til separate kontorer slik at individuelle programmerere kan jobbe separat 
• og hvor komplett (høy kohesjon) og uforstyrret (lav kobling) et slikt system er

Spilleregler

• Systemet må være godt dekomponert
• Vi tror at kontortilordningsfaktoren gir høy tilfredstillelse
• for programmereren vet hva han skal gjøre
• og trenger ikke tenke på hvordan de andre gjør sin del 
• Hvem kan hva vil influere på hvordan programvarearkitekturen blir
• Vi må iterere mellom funksjonell nedbrytning og kontorkunnskap og erfaring -type nedbrytning
• Så, kontortilordningsfaktoren er en funksjon av både innebygd og villet struktur 

Prosess-innkapsling sjekkliste (beta)

• For å få høy kontortilordningsfaktor
• Er prosesser i stand til å holde igjen meldinger fra andre prosesser (ved å lukke døra, så og si)?
• Eller må de håndtere alt - alltid?
• Er systembufferoverflyt mulig?
• Har du en god prosessmodell som kan inneholde objekter (som i OO) - og ikke motsatt?
• Sliter arv for mye på innkapsling?
• Har du aliasing - dvs. flere navn på samme variabler? Er dette på kryss av prosesser, er det rød lampe!
  
• Har du nok eller for mange prioriteter?
• Bruker du nok (og ikke for mye) assert-programmering (stopp og restart)?

Asynkron komm. er "vidt åpen"

• Meldingssekvens diagram er hellende: sending og mottak er ikke samtidig
• Dvs. tida går, både for sender og mottaker
• Enn om rekkeføglen på mottatt svar ovenfor var vesentlig?
• Tilsvarer det å løpe ut og inn av kontoret for å bli enige om hva den andre gjør i dag, etter at man trodde man var enig 
• Obs: Om dette er i orden på et nivå - kan det godt være et problem på et høyere nivå! Samme utfordring!

Synkron komm har “dør” som kan lukkes

• Meldingssekvens diagram er rent horisontale: sending og mottak er samtidig
• Dvs. tida står for førstemann, går bare for den som er nummer to på kanalen
• Her har man "What You See is What You Get" semantikk. (Titt bare på hva du sjøl skal gjøre og den omforente protokollen)
• Tilsvarer det å holde seg på kontoret for å gjøre seg ferdig, og diskutere med den andre bare dersom man ser at den avtalte protokollen ikke dekker behovet

Halvt det ene og det andre: sender-side helling

• En "pipe" kan sendes til så lenge "pipen" ikke er full (vi har vært innom dette før)
• Når "pipen" går full kan sematikken være å blokkere da (lik overflytbufferen i eksempelet ovenfor)
• Kontortilordningsfaktoren vil lide:
• Ting er "lett" helt til man blokkerer!
• Dette tror jeg er noe av årsaken til at "blokkering" har slik negativ klang - fordi det er for sen blokkering - og det er vanskelig og implementere og forstå
• Begynn heller med umiddelbar blokkering (ingen bufring), og legg inn slik bufring om det blir for komplisert (som vist i eksemplet ovenfor)

For høy kohesjon og for lav kobling == ikke bra

• For høy kohesjon vil gi for høy intern kompleksitet
• Programmereren har grodd fast på kontoret og gjør alt sjøl!
• Se opp for gjøkunger (vi må alle passe på at vi ikke blir en)
• For lav kobling kan også forårsake for høy intern kompleksitet
  
• Bare se forskjellen på eksemplene ovenfor (i "Data-komm. som alltid funker (2)")
• I det eksemplet ga mer kobling (kommunikasjon) og mindre kohesjon (interne tilstander) lavere kompleksitet

Testing av systemet

• Prosess enhetstester: lite (men ikke, ikke noe)
• Mest tester "in vivo", siden det er så mye som griper inn i hverandre
• Arkitekturen trengte lite test, men systemet ble testet vha. en applikasjonspotokoll (AutroAdit) som vi benytter for kommunikasjon med overordnet system. Eksempel:
• <SET:1-4,50,67-88.OperationClass=A1> <ACK>
<EVENTU:1-4,50,67-88.OperationClass=A1> <EACK>
• Vi holdt nøye sporing av feil. Åpne feil var nesten alltid mindre enn ti
  
• Og ga ut kort av en svarteper-kortstokk for hver feil som ble funnet (nå er vi tom!)
• Prøvde å lage en kultur for å være åpne om feil
• Men husk, "assert-programmering" (stopp og restart): aldri for eksterne påtrykk! ALDRI!

Konklusjon

• Om du benytter synkron kommunikasjon i bunnen
• og pakker inn delte ressurser i prosesser, som kan styre andres bruk av seg
• og designer bort vranglås, utsulting og livlås vha. mønstre
• er sanntidsprogrammering lett!
• Og, for all del – legg in asynkronitet der det er nødvendig!
• Samtidig programmering på flere kontor (høy kohesjon) med bare det nødvendige antallet møter (lav kobling) ser ut til å være en effekt av bruk av denne metodikken
• Vi tror dette ga høy "Office Mapping Factor" / "kontortilordningsfaktoren" (en term som jeg har funnet på)
• Men: Vi har ikke gjort noe forskning på om andre metodikker kan gi liknende resultat
• Min erfaring viser at du blir ferdig med slike system og kan gå videre og lage mye! (..i større grad.. etc..)
• Vil det til slutt overbevise sjefen din?
  
• Men obs! Alle har en sjef å overvbevise! Også jeg! 

Kontaktinfo

• Dette foredraget: http://www.teigfam.net/oyvind/pub/NTNU_2008/presentation_w3ref.html
• Dette faget på NTNU: http://www.itk.ntnu.no/fag/TTK4145/information/
  
• Og - søk jobb hos oss når vi annonserer!
• Noen besteforeldre må være på Autronica - i 2040 også (32 år fra 2008)

http://home.no.net/oyvteig/	http://www.autronicafire.com

Ekstranotat

• A scheduler is not as transparent as I thought - En norsk keynote presentasjon ble benyttet i forelesningen