1. Teori bakom trådad programmering

På denna sida kommer teorin bakom trådar och trådad programmering att undersökas. Det kommer visa sig att trådad programmering är mycket mer komplicerad än normal programmering, och därför måste man använda sig av ett formellt resonemang för att garantera att inga fel uppkommer. Nya begrepp intorduceras som atomära handlingar, at-most-one och försäkrande resonemang.

2. Processer och trådar

Ett operativsystem klarar nu för tiden att hålla flera program igång samtidigt. Den lyckas med detta genom att lägga varje program i en egen process, och snabbt hoppa mellan de olika processerna så att alla ser ut att köra samtidigt. En process (ett program) kan också göra flera saker samtidigt, men då kallas det att processen har flera trådar. De flesta program man skriver behöver bara en tråd; den som kör main(). Skillnade mellan en process och en tråd är:

• En process är tung i den bemärkelse att den kräver en hel del extraarbete att starta och hållar reda på av operativsystemet.
• En tråd är lätt, d.v.s. att den går snabbt att starta och knyter upp lite systemresurser.

3. Kommunikation mellan trådar

Ofta behöver trådar något sätt att kommunicera med varandra. Kommunikation kan bara ske på två sätt:

1. Kommunikation kan ske med delade variabler. En tråd skriver till en variabel och en annan läser från samma variabel. Används: då trådarna kör på samma dator, d.v.s. de kan komma åt samma minne.
2. Kommunikation kan ske med meddelanden. I detta fall skickas ett meddelande från en tråd till en annan. Används: då trådarna inte kör på samma dator.

4. Atomära handlingar

Om ett icke trådat program består av ett antal satser (kodrader), så kommer de de olika satserna utförs i följd. I ett trådat program kan en tråd när som helst avbrytas av en annan (med högre prioritet) som börjar arbeta med någonting annat.



I bilden ovan blir tråd 1 avbruten av tråd 2 efter sats 4. Tråd 2 utför satserna 21 till 30 innan tråd 1 tillåts fortsätta med sats 5. När man talar om multitrådade program inför man begreppet atomära handlingar. Varje stas består av en eller flera atomära handlingar. En atomär handling kännetecknas av att den inte kan avbrytas mitt i av någon annan tråd. Antingen har handlingen skett, eller så har den inte det.

• Problem: Om vi utgår från att vi har T trådar som utför A atomära handlingar, så kommer totalt 3*A handlingar att utföras. Varje tråd kommer att utföra sina A stycken handlingar i ordning, men kan när som helst avbrytas av någon annan tråd. På hur många sätt kan dessa 3*A handlingar utföras?

5. Debugga trådade program

I Exempel2 ovan visade det sig att ett program med 3 trådar som utför 2 atomära handlingar kan utföras på 90 olika sätt. Större program kan exekveras på miljontals sätt. Det går alltså inte att testköra ett trådat program på samma sätt som ett icke trådat eftersom en lyckad testkörning inte garanterar att programmet fungerar. Ett fel kanske bara uppkommer var miljonte testkörning, och ingen orkar testköra ett program en miljon gånger. När man vill debugga ett trådat program måste man därför använda sig av andra metoder, den metod som Gregory R. Andrews rekommenderar i Foundations of multithreaded.. är försäkrande resonemang (assertional reasoning). Förenklat kan man säga att det försäkrande resonemanget går ut på att man ställer upp olika tillstånd för programmet. Ett tillstånd kan vara x>0 eller Y<X. Varje atomär handling är en modifierar tillstånden. Målet med denna metod är att logiskt bevisa att ett visst oönskat tillstånd inte kan uppkomma, oavsett vilken ordning de atomära handlingarna utförs.

6. Är x++; atomär?

Vi har tidigare sagt att en sats består av en eller flera atomära handlingar.

• Fråga: Hur många atomära handlingar består satsen x++; av?
• Svar: Minst 2 (use & assign). Svaret beror på om x finns laddad till trådens arbetsminne eller inte.

7. At-Most-One

Nu presenteras en regel som kallas för at-most-one och definieras på detta sätt: En sats x=expr; kan ses som atomär om:

• x läses inte av någon annan tråd OCH expr innehåller max en variabel som ändras av en annan tråd, eller
• x kanske läses av någon annan tråd OCH expr innehåller ingen variabel som ändras av en annan tråd.

Nedan ges ett exempel taget från dokumentationen av JVM:

class Sample { int a = 1, b = 2; void hither() { a = b; } void yon() { b = a; } }

• Fråga: En tråd går in i metoden hither() och en annan går in i yon(). När båda trådarna är färdiga, vad har då a resp. b för värde?
• Svar: a=b=1, a=b=2 eller a=2,b=1.

Varför får vi detta märkliga resultat? Om satserna a=b; och b=a; är atomära blir svaret lätt. Antingen är a=b=1 eller a=b=2, beroende på vilken sats som exekveras först.

• Fråga: Uppfyller satsen: a=b; at-most-one?
• Svar: Nej. Satsen a = b; har både en variabel a som läses av en annan tråd OCH ett uttryck som innehåller en variabel (b) som ändras i den andra tråden.

Satserna kan inte ses som atomära eftersom de inte uppfyller at-most-one, därför kommer det oväntade resultatet med. Följande bild beskriver de olika atomära händelserna hos funktionerna:



En möjlig väg är alltså denna:

1. hither-tråden börjar köra hither() men blir avbruten precis efter use b (alltså man har laddat värdet 2 till exekveringsmotorn).
2. yon-tråden kör yon() från början till slut och b tilldelas 1.
3. hither-tråden får fortsätta och eftersom det gamla värdet på b ligger laddat i exekveringsmotorn kommer assign a att ge a värdet 2.

Vi har nu fått det märkliga resultatet a=2,b=1.

8. Programmeringslogik

För att kunna utföra våra försäkrande resonemang krävs lite programmeringslogik. Programmeringslogik formuleras i formler som allmänt har följande utseende:

{P} Sats {Q}

Där P och Q beskriver vilka värden programmets variabler har före och efter satsen Sats har körts. Ett exempel på en formel är:

{x==0} x=x+1; {x==1}

Denna formel kallas för ett teorem eftersom den är giltig. Även följande formel är ett teorem:

{x==0} x=x+1; {x>0}

En av de enklaste lagarna för formler är kompositionslagen:

Om: {P} Sats1 {Q}, {Q} Sats2 {R} Så: {P} Sats1 Sats2 {R}

Man använder kompositionslagen för att bevisa att tillstånd P kommer resultera i tillståndet R genom att beskriva alla mellanled. Till exempel, bevisa:

{x==0} Tråd1: x=x+1; Tråd2: x=x+2; {x==3}

om varje sats antas vara atomär. För att bevisa detta måste man beskriva alla möjliga vägar som progammet kan gå som teorem. Det snabbaste sättet att skriva beviset är detta:

{x==0} Tråd1: {x==0 eller x==2} x=x+1; {x==1 eller x==3} (Tråd1 dör) Tråd2: {x==0 eller x==1} x=x+2; {x==2 eller x==3} (Tråd2 dör) {x==3}

Beviset är trivialt, men illustrerar ändå principen.

9. Konflikter

Ofta finns det tillstånd som man alltid vill ska gälla, och målet med försäkrande resonemang är att garantera att dessa tillstånd alltid bevaras. Därför vill man ofta att samtliga tilldelningssatser i ett program ska vara konfliktfria med det känsliga tillståndet. En tilldelningssats A med grundtillståndet P är konfliktfritt med avseende på ett tillstånd C om:

{C och P} A {C}

Alltså: Om C gäller innan tilldelningssatsen A kommer C även gälla efter satsen.

10. Synkronsisering

Det finns två typer av synkronisering:

• Låsning: Ofta vill man garantera att endast en tråd åt gången kan få tillgång till en viss resurs. För att se till att endast en tråd använder resursen brukar man säga att tråden låser resursen, och då en annan tråd försöker få tillgång till resursen tvingas den att vänta på sin tur. Exempel: Om två trådar samtidigt försöker skriva till en fil är det svårt att förutsäga resultatet, därför är det bättre att varje tråd låser filen innan den skriver.
• Villkorssynkronisering: Denna typ av synkronisering tvingar en tråd att vänta tills ett visst villkor är uppfyllt. Exempel: Vi har en tråd som ska läsa ur en buffert men oftast är bufferten tom. Det enklaste sättet är att låta tråden läsa från bufferten hela tiden. Men genom att använda koordinerad synkronisering kan man tvinga tråden att vänta tills bufferten innehåller något, och först då väcker man tråden. Detta förfarande sparar processorkraft eftersom den väntande processen aldrig försöker läsa ur den tomma bufferten.

11. Deadlock

Trådprogrammerarens fasa är deadlock, det inträffar då tråd1 låser objektA och vill även låsa objektB. En annan tråd, tråd2 har låst objektB och väntar på att även få låsa objektA. När detta dödläge inträffar hänger sig programmet, och man måste stänga av det. Det är programmerarens uppgift att se till att deadlock inte inträffar, men det är svårt att förutse alla situationer som kan uppkomma då flera trådar körs samtidigt.

12. Typer av probelm

Det finns några grundproblem man kan råka på:

1. Iterativ parallellism: När ett program har flera identiska trådar som innehåller loopar. Varje tråd är ett iterativt program. Alla trådarna arbetar tillsammans för att lösa ett gemensamt problem. Används: för att snabba upp beräkningar på multiprocessorsystem. Genom att använda trådar delas arbetsbördan mellan procesessorerna eftersom varje processor tilldelas varsin tråd.
2. Rekursiv parallellism: När ett program har flera rekursiva trådar som är oberoende, dvs de arbetar med olika delar av de delade varablerna. Används: vid sortering och kombinatoriska problem, t.ex. schack.
3. Producent och konsument: I detta mönster finn två trådar, producent och konsument. Här flödar informationen åt ett håll, från producenten till konsumenten. Både producenten och konsumenten bearbetar data parallellt. Används: till exempel i operativsystem som Unix: pipe (|).
4. Client/Server: I detta mönster finn två trådar, klient och server. Klienten skickar en förfrågan och servern returnerar ett svar. Används: Detta är den dominerande interaktionen i nätverk och på internet. Då man programmerar t.ex. programmerar en webbserver är det bra att låter en ny tråd startas för varje inkommande HTTP-förfrågan. Detta ger fördelen att även då servern är hårt belastad behöver en snabb förfrågan inte vänta på att alla långsamma förfrågningar ska ha kört klart.
5. Interagerande jämlikar: Förekommer i distribuerade program där de olika processerna på de olika maskinerna exekverar samma kod och utbyter meddelanden med varandra. Används: vid distribuerade parallella program, speciellt iterativ parallellism. Vissa internetprogram som t.ex. Napster.