Toetsbundel Deel 1 Concurrency 10 december 2015, Gerard Tel, Niet verspreiden 1!

Toetsbundel Deel 1 Concurrency 10 december 2015, Gerard Tel, Niet verspreiden1 !. Deze bundel bevat een collectie toetsvragen over het eerste deel van Concurrency. Je kunt deze bundel gebruiken voor je toetsvoorbereiding, maar enige relativering is geboden. Behalve dat “goede” antwoorden worden gegeven, worden ook de “foute” besproken, met korte uitleg waarom het niet klopt. Door andere uitleg op college, andere selectie van stof, of wijzigingen in techniek of standaarden, kan een “fout” antwoord later opeens kloppen of acceptabel zijn! Cijfer: De toetsen, met een duur van twee uur, zijn meestal genormeerd op 20 tot 25 punten.

1

Multithreading

1. Beantwoord met Amdahls Regel: Een programma bestaat voor 80% uit parallelliseerbare code en wordt gedraaid op een quad-core. (a) Welke speedup wordt gehaald? (b) Om de executie verder te versnellen kunnen we kiezen tussen (1) het programma verbeteren zodat 90% parallelliseerbaar is; (2) meer cores bijschakelen. Hoeveel cores heb je bij optie (2) nodig om dezelfde speedup te halen als bij optie (1)? Oplossing: (a) Volgens Amdahl wordt de executietijd (bij α parallelliseerbaarheid en p cores): (1 − α) + αp , dus hier: 0, 20 + 0,80 4 = 0, 4. De speedup is dan een factor 1/0, 4 = 2, 5. (b) Met α = 0, 90 wordt de executietijd op quad-core: 0, 1 + 0,9 4 = 0, 325. Om dat te bereiken 0,8 0,8 met α = 0, 8 moet gelden 0, 2 + p = 0, 325, wat geeft p = 0,125 = 6, 4. Beoordeling: Voor elk deelantwoord een punt. Beoordelingscodes: A = Verkeerde vraag beAntwoord (bv: hoeveel cores heb je nodig om de speedup uit (a) te halen als α = 0, 9, met antwoord 3). Geen punt. G = Vervang 6,4 door Geheel getal 6 of 7, prima, ook 1pt. F = Geen Amdahl gebruikt, onduidelijk wat berekend is. M = Goede Methode of formule maar verkeerd antwoord, halve punt. R = Benoem speedup als 0,4 (de Reciproke) ipv 2,5, dit is ook goed en levert 1pt. Z = Door bij (b) de speedup af te ronden op 3 krijg je Zes cores, dit is ook goed, 1pt.

1

Op deze bundel geldt namelijk auteursrecht. Je mag het bestand bekijken en ook afdrukken, en iemand naar dit bestand verwijzen, maar niet het bestand of de afdruk aan iemand anders geven.

2. Assignments: In een situatie waar x is 0 en v is true, worden deze twee threads opgestart: Thread 1: x = 1; v = false;

Thread 2: while (v) {}; y = x;

Is het zeker dat de waarde van y na afloop 1 is wanneer (a) read/write atomicity geldt? Waarom? (b) dit wordt uitgevoerd in Java of C#? Waarom? (c) v als volatile wordt gedeclareerd? Oplossing: (a) Ja. De waarde van x is al 1 voordat de toekenning aan v begint. Thread 2 ziet false in v voordat hij met lezen van x begint. Dus thread 2 begint met lezen nadat het schrijven is voltooid en leest zeker 1. (b) Nee. Het is door de interactie via v wel zeker dat thread 2 pas x gaat lezen nadat thread 1 met het schrijven ervan klaar is. Maar het is niet zeker dat die wijziging ook al zichtbaar is voor thread 2. (c) Ja. Declareren als volatile beperkt niet alleen herordening van operaties op v zelf, maar ook herordening van v ten opzichte van x. De volatile write op v komt gegarandeerd pas in het geheugen na elke operatie die ervoor zit2 . Het werken met volatile is overigens zo ingewikkeld dat het doorgaans wordt afgeraden3 . Beoordeling: Voor a 1pt, b 2pt, c 1pt. Beoordelingscodes: A = Zegt ten onrechte dat Read/Write in C# Atomair is (bij b); 0pt. M = Zegt bij (c) ja zonder motivatie; hoogstens 1/2, en helemaal 0 als bij (b) ook ja werd geantwoord. V = Geeft bij (c) het sceario dat de read op x van thread 2 nog de oude waarde geeft nadat v false gezien was. Slim, maar de Volatile op x voorkomt dit; 1/2pt.

3. Eigenschappen van methoden: (a) Wanneer zijn operaties atomair? (Boek: linearizable.) (b) Wanneer is een methode wachtvrij? (c) Wat wordt bedoeld met de aanname van fairness? Oplossing: (a) Operaties zijn atomair als de uitkomst ervan altijd gelijk is aan de uitvoering na elkaar, elke operatie op een punt in de tijd dat ligt binnen de daadwerkelijke uitvoering. (b) Wachtvrij betekent dat de methoden geen wacht- of lock- statements mogen bevatten, maar ook dat elke operatie in een beperkt aantal stappen termineert. (c) Fairness betekent dat elke stap die door een thread gedaan kan worden, ook ooit een keer in de executie aan de beurt komt. UNfair wil namelijk zeggen, dat er een oneindige reeks stappen plaatsvindt, waar een bepaalde stap niet in voorkomt terwijl die stap wel steeds toepasbaar is. Beoordeling:

2 3

http://msdn.microsoft.com/en-us/library/aa645755%28v=vs.71%29.aspx http://stackoverflow.com/questions/6526432/volatile-with-release-acquire-semantics

4. Interleavings: Bekijk alle interleavings van LOADA c ; INCRA ; STOREA c

LOADA c ; ADDA 2 ; STOREA c

(ADDA 2 is een instructie die 2 bij register A optelt.) Veronderstel dat de afzonderlijke instructies atomair (linearizable) zijn. In hoeveel interleavings wordt c uiteindelijk met 0, met 1, met 2 en met 3 opgehoogd? 6! Oplossing: Er zijn 3!·3! = 20 interleavings. Het mag duidelijk zijn dat geen hiervan c met 0 ophoogt. Waarde c wordt alleen met 3 opgehoogd indien de laatste instructie van thread 1 voor de eerste instructie van thread 2 komt, of andersom. Met andere woorden: als de threads niet overlappen. Hiervoor zijn 2 mogelijkheden. Er zijn nog 18 interleavings over. Deze moeten c met 1 of met 2 ophogen. Wegens de symmetrie van beide threads zal elk van deze twee in de helft van de overgebleven gevallen voorkomen. Dus: 0 interleavings hogen c met 0 op, 9 met 1, 9 met 2, en 2 met 3.

Beoordeling:

5. Fair executie: In dit programma kijkt thread 1 steeds naar variabele i, die door thread 2 afwisselend op 0 en 1 wordt gezet. Ga uit van read/write atomicity; initieel is i=0 en s=True: Thread 1: t = 0 while (i==0) { t = t + 1 } s = False

Thread 2: while (s) { i = 1 - i } print t

(a) Beschrijf van dit programma een executie waarin thread 2 de waarde 2 print. (b) Beschrijf een oneindige executie die niet kan voorkomen als de scheduler fair is. (c) Beschrijf een oneindige executie die wel mogelijk is onder een fair scheduler. Oplossing: (a) Een executie die 2 print: Laat thread 1 tweemaal door zijn lus gaan, dan zet thread 2 i op 1, dan springt thread 1 uit zijn while lus en zet s op false, thread 2 stopt en print 2. (b) Een oneindige executie die door fairness voorkomen wordt: Omdat beide threads pas stoppen na een actie van de ander, ontstaat er direct een oneindige executie wanneer slechts ´e´en thread stappen kan doen. Uiteraard wordt dit doemscenario door fair scheduling voorkomen. (c) Een oneindige executie die ook onder fairness kan: Omdat thread 1 termineert als hij i = 1 ziet, kan thread 2 niet alleen thread 1 blokkeren maar ook die blokkade weer opheffen, nl. door i weer op 0 te zetten. Je moet dus kijken naar executies, waar thread 2 telkens een even aantal wijzigingen schrijft tussen lees-operaties van thread 1. Omdat fairness alleen iets zegt over het voorkomen van operaties, maar niet over de volgorde (of situatie waarin het gebeurt), sluit fairness dit niet uit. Beoordeling: Voor elk deelantwoord 1 punt. A = Dit gaat over een Ander programma.

6. Fairness: In dit lusje zitten twee concurrente statements, die i op 0 en 1 zetten: i = 0 while (i == 0) { cobegin { i=0 } print i }

{ i=1 } coend

(a) Laat zien dat er voor elke k ∈ N een executie is die eerst k nullen en dan een 1 print. (b) Geef de definitie van fair scheduling (c) Is bovenstaand programma terminerend onder de aanname van fair scheduling? Leg uit! Oplossing: (a) Eerst wordt in de lus k keer de opdracht i=0 na i=1 uitgevoerd, en de volgende keer gaat het andersom. (b) Een scheduling is fair als er nooit een instructie die ready is, oneindig lang hoeft te wachten. (c) Nee, want scheduling zegt niets over de volgorde waarin ready opdrachten worden uitgevoerd. Het scenario waarin i=0 altijd als laatste wordt gedaan, is fair. Beoordeling: Max 3, een per deelvraag. Beoordelingscodes: A = De threads zitten Allebei in iedere ronde. B = Je Beschrijft de executie niet. E = “Iedere thread Evenveel rekentijd”, nee dat is het niet. K = Het is niet probabilistisch, dus heeft met Kansen niets te maken. T = “Elke thread Termineert”, nee, het gaat alleen om de volgende instructie. of de thread termineert hangt af van hoe hij geprogrammeerd is.

7. Safety of Liveness: Zeg van elk van deze uitspraken of ze een Safety of een Liveness eigenschap beschrijven en waarom (in 1 zin). (a) De relschoppers worden opgespoord, berecht en gestraft! (b) Asielaanvragen worden binnen zes maanden afgehandeld. (c) Als ´e´en of meer threads aan de operatie beginnen, zal tenminste ´e´en de operatie in eindige tijd kunnen voltooien. (d) Als een thread t2 de ticket-keuze begint nadat thread t1 de ticket-keuze heeft voltooid, ontvangt t2 een hoger ticket dan t1 . (e) De scheduler voor threads t1, t2 en t3 is fair. Oplossing: Een eigenschap is Safety als je een schending kunt constateren in eindige tijd. (a) Liveness, want zolang de relschoppers nog niet berecht zijn, kan het altijd later nog gebeuren. (b) Safety, want je kunt schending constateren wanneer een aanvraag niet binnen zes maanden is behandeld. (c) Liveness (vanwege de onbepaaldheid van “eindige tijd”): zolang alle threads nog bezig zijn, kan er altijd nog eentje afronden. (d) Safety (als je de uitspraak opvat als een bewering over de waarde van t2 ’s ticket en niet het verkrijgen ervan): te schenden in eindige tijd, namelijk als t2 toch een kleiner ticket krijgt. (e) Liveness, want hoe lang een thread ook stil staat, hij kan altijd later nog weer een instructie gaan uitvoeren. Beoordeling: Een halve punt per goed antwoord vanaf het tweede; dus 1 goed is 0pt, 2 goed is 1/2pt, etc. Beoordelingscodes: D = Safety bij (a) omdat je schending constateert bij Dood van relschopper; origineel en slim, reken goed. L = Safety bij (c) omdat je schending constateert bij Livelock; Fout omdat livelock niet de enige vorm van schending van de eigenschap is. M = Geen Motivatie, -1/2.

8. Interleavings: Hoeveel interleavings zijn er mogelijk bij het concurrent uitvoeren van: (a) een thread met twee instructies en een met ook twee instructies; (b) een thread met 7 instructies en een met 11 instructies; (c) een thread met 6, een thread met 7, en een thread met 9 instructies. Oplossing: (a) Dit kan op 6 manieren, werd genoemd op hoorcollege. (b) Er worden 18 instructies uitgevoerd, en elke interleaving correspondeert met een deelver  18 zameling van 7 posities waarop instucties van de eerste thread staan. Totaal dus 7 ofwel 31824. (c) Er zijn22 instructies. Eerst kun je de plaats van de 6 instructies van de eerste thread  22 kiezen op ofwel 74613 manieren. Van de andere 16 posities moet je er 7 aanwijzen 6   16 voor thread 2 wat kan op manieren dus 11440. Totaal is het product 853572720. 7 Beoordeling: Voor elke deelvraag 1pt.

9. Safety of Liveness: Zeg van elk van deze uitspraken of ze een Safety of een Liveness eigenschap beschrijven en waarom (in 1 zin). (a) Berichten worden afgeleverd in dezelfde volgorde als waarin ze zijn verstuurd. (b) Als een bericht aan een niet-bestaand adres wordt verzonden, wordt binnen 1500 ms een foutmelding getoond. (c) Na klikken op LOAD wordt het bestand in de edit-buffer geladen. (d) Een krant die in de zon ligt, wordt geel. (e) De waarde van counter A is strikt stijgend. Oplossing: Een eigenschap is Safety als je een schending kunt constateren in eindige tijd. (a) Safety, je ziet schending zodra een later verstuurd bericht eerder wordt afgeleverd. (b) Safety, door de tijdlimiet; als de foutmelder niet werkt kun je dat na 1,5sec aantonen. (c) Liveness, want er is geen limiet op hoe lang het kan duren, en zolang het niet geladen is kan dat altijd nog later gebeuren. (d) Liveness, als hij niet geel wordt kun je er niks van zeggen want het kan later nog gebeuren. (e) Safety, je ziet een schending als de waarde lager is dan een eerdere waarde. Beoordeling: Een halve punt per goed antwoord vanaf het tweede; dus 1 goed is 0pt, 2 goed is 1/2pt, etc. Beoordelingscodes: M = Geen Motivatie, -1/2.

10. Atomaire Queue: (a) Geef de definitie van atomaire operaties. (b) Geef een voorbeeld van drie operaties op een Queue (inclusief timing) die wel consistent zijn maar niet atomair. Oplossing: (a) Operaties zijn atomair als elke executie met overlappende aanroepen hetzelfde effect heeft als wanneer elke operatie zonder overlap is uitgevoerd, op een moment (contractiepunt) gedurende de tijd van daadwerkelijke uitvoering. (b) Laat de Queue de waarde A bevatten, thread 0 tweemaal een deq doen en thread 1 eenmaal een enq(B) die overlapt met beide acties van thread 0. Thread 0 krijgt eerst een B en dan een A. De antwoorden kloppen nu wel met elkaar, maar de operaties “gebeuren” in een volgorde die strijdig is met de eis van atomair. Beoordeling: Max 2, voor elke deelvraag 1. Beoordelingscodes: A = Gegeven voorbeeld is Atomair, 0pt. C = Gegeven voorbeeld is niet Consistent, 0pt. E = Niet aangegeven dat het om het Effect gaat, 0pt. K = Het Klopt niet meer als de op Klaar is, zoals een size die overlapt met een dequeue. Bij atomair gaat het niet om of het aan het eind van de methode klopt, maar of er een moment bestaat waarop het klopt (contractiepunt). 0pt. Q = Voorbeeld gaat niet over Queue, 1/2pt. R = Definitie voor Registers, niet algemeen atomair, 1/2pt. V = Restrictie op Volgorde ontbreekt, 0pt. Z = Werking als Zonder overlap ontbreekt, 0pt.

11. Terminatie van Threads: Twee threads delen variabele s, die door thread 1 steeds wordt opgehoogd. Thread 0 leest s en termineert beide threads als s even is: Thread0 Thread1 s = 0; t = 0; b = True; while (s%2 == 1) while (b) { t++ } { s++ } b = False; print(t); (a) Wanneer is een methode wait-free? (b) Is het programma van Thread0 waitfree? Is dat van Thread1 wait-free? (c) Is het programma terminerend onder de aannamen van read-write atomicity en fairness? Oplossing: a. Een methode is wait-free als elke aanroep gegarandeerd in een eindig (eigenlijk zelfs: begrensd) aantal stappen termineert (Boek p59). Het termineren mag daarbij niet afhankelijk zijn van het doen of laten van stappen door een andere thread. b. Thread0 is niet wait-free omdat hij, uitgaande van een oneven s (dus na 1 increment door thread 1), alleen kan termineren nadat Thread1 s weer heeft opgehoogd. Er is geen limiet aan het aantal stappen dat T0 hiervoor kan doen. Thread1 is niet wachtvrij omdat hij pas kan termineren na het resetten van b door Thread0. c. Als er fairness is (en R/W atomicity) zal Thread 1 willekeurig vaak s kunnen ophogen, en Thread 0 zal willekeurig vaak de waarde gaan lezen. Echter, het is mogelijk dat Thread0 alleen ONEVEN waarden van s ziet (als er steeds een even aantal increments van T1 tussen reads van T0 liggen). Je kunt zo’n gang van zaken op de duur onwaarschijnlijk vinden, maar het scenario wordt door Fairness NIET uitgesloten. Beoordeling: Voor (a) en (b) 1pt, voor (c) 2pt. Wachtvrij vereist, dat Th0 ook zijn werk solo kan afmaken als Th1 eerst eenmaal de increment heeft gedaan. A = Let er bij (a) ook op, dat terminatie wordt geeist, niet alleen dat de thread kan “doorgaan”. Dus: “niet Afhankelijk” is niet genoeg. F = Je voorbeeld is niet Fair. W = “Niet Wachten” is te vaag, want je kunt niet precies onderscheid maken tussen een lus en een busy wait. Daarom is de formele eis, dat het aantal stappen eindig moet zijn, die eis sluit namelijk een impliciete busy wait (zoals voorkomt in Thread0 en Thread1) ook uit.

2

Work-Span-Model

Uitleg over Efficient en Optimaal: Een parallel algoritme heeft twee complexiteitsparameters, work en span, beide uitgedrukt als functie van de invoergrootte n. Van een goed parallelliseerbaar algoritme accepteren we soms, dat de work hoger is dan de tijd van het beste sequenti¨ele algoritme. De verhouding van (work) gedeeld door (beste sequenti¨ele tijd) is de (parallelliserings-) overhead. Een algoritme heet efficient wanneer de span polylogaritmisch is en de overhead ook polylogaritmisch. Een algoritme heet optimaal wanneer de span polylogaritmisch is en de overhead constant. 12. Alternatieve Prefix P Sum: De prefix sum van een rij X[0..n − 1] is de rij Y [0..n − 1], gedefinieerd door Y [k] = ki=0 X[i]. Als alternatief voor het behandelde algoritme bekijken we deze methode: (1) bereken de prefix sum van de linkerhelft en de rechterhelft; (2) tel bij elke uitkomst van de rechterhelft, het totaal van de linkerhelft op. (a) Hoeveel rekenstappen kost het om de prefix sum met een sequentieel algoritme te bepalen? (b) Laat zien, hoe de alternatieve methode werkt, wanneer toegepast op de cijfers van je collegekaart (F=6 als die voorkomt). (c) Stel vergelijkingen op voor de span en het work van de alternatieve methode. (d) Wanneer is een parallel algoritme efficient? Is de alternatieve methode efficient? (e) Wanneer is een parallel algoritme optimaal? Is de alternatieve methode optimaal? Oplossing: (a) Sequentieel kost het O(n) optellingen met: Y[0] = X[0]; for(k=1;k < n;k++) Y[k] = Y[k-1]+X[k] (b) Stel je collegekaartnummer is 9 8 7 6 5 4 5. De linkerhelft is 9 8 7 6 en de rechterhelft is 5 4 5. Recursief bepaal je de Prefix Sums: links 9 17 24 30 en rechts 5 9 14. Bij de rechterreeks tel je 30 op: 35 39 44. Uitkomst is 9 17 24 30 35 39 44. (c) Span: Recursief linker- en rechterhelft berekenen kost S(n/2), maar dit kan tegelijk dus telt in de Span maar een keer. Het linkertotaal kan (op een CREW PRAM) in O(1) tijd worden verdeeld over de rechterprocessors en worden opgeteld bij de elementen rechts. Dus S(n) = S(n/2) + 1. Work: Recursief links en rechts berekenen kost steeds W (n/2), voor de Work moet je beide tellen. Dan nog n/2 optellingen om het linkertotaal bij elk getal van de rechterkant te tellen; totaal is W (n) = 2.W (n/2) + O(n). (d) Efficient is: Work hoogstens polylogaritmisch meer dan sequentieel, en span polylogaritmisch. Dan toch maar even de Master Theorem erbij. Span S(n) = S(n/2) + 1, bloga = 0 en f (n) = 1 = n0 . Dus nbloga = f (n), MT zegt: extra log erbij dus S(n) = O(lg n). Work W (n) = 2.W (n/2) + O(n), bloga = 1 en f (n) = n1 . Dus nbloga = f (n), MT zegt extra log erbij dus W (n) = O(n lg n). We zien een logaritmische Span en Overhead, de methode is dus efficient. (e) Optimaal is: geen (dwz O(1)) overhead en polylog span. De overhead is hier logaritmisch, dus teveel: NIET optimaal. Beoordeling: Elke deelvraag 1pt. Ik kan hier niet het hele verhaal over recursieve algoritmen en recurrente betrekkingen herhalen. De tijd van een recursief algoritme bepalen ZONDER het opstellen van een recurrente betrekking kan alleen Harry Potter!

13. Het Kleinste Verschil: We willen in een oplopend gesorteerde array A van n getallen, het kleinste verschil, KV, van twee opeenvolgende weten. Voorbeeld: in de rij (1, 3, 5, 7, 8, 12, 14, 25) is het KV 1 (namelijk het verschil tussen 8 en 7). Het best mogelijke sequenti¨ele algoritme kost Θ(n) stappen. (a) Kun je het KV berekenen uit het KV van de linkerhelft en het KV van de rechterhelft? (b) Geef een parallel algoritme dat KV berekent. (c) Analyseer work en span van je algoritme met de Master Theorem. (d) Is het algoritme efficient en optimaal? Oplossing: (a) Je moet er rekening mee houden dat het KV, ofwel het KV van links, het KV van rechts is, of het verschil van de laatste links en de eerste rechts. Dus als KV (p, r) het kleinste verschil is van de getallen van index p (inclusief) tot r (exclusief), geldt met q tussen p en r: KV (p, r) = min(KV (p, q), KV (q, r), (aq − aq−1 )). (b) Rijen korter dan 4 gaan direct. Vanaf 4: neem q = (p + r)/2 en doe twee (parallelle) KV’s en reken de formule uit (a) uit. (c) Work: we doen twee deelaanroepen op halve omvang en een constante hoeveelheid werk dus W (n) = 2W (n/2) + O(1). Met de Master Theorem volgt W (n) = O(n). Span: wat echt na elkaar moet gebeuren is het berekenen van q, `e`en deel-KV en het combineren, dus S(n) = S(n/2) + O(1). Met de Master Theorem volgt S(n) = O(lg n). (d) De span is logaritmisch, dus ook polylogaritmisch; de overhead is constant dus ook polylogaritmisch. Efficient betekent polylog span en polylog work, dit is hier van toepassing. Optimaal betekent polylog span en constante overhead, en is hier dus ook van toepassing. Beoordeling: Te behalen 4, voor elke deelvraag 1pt. L = Je kunt ook deel L en deel R laten overLappen. R = Herhaling en Recursie is dubbelop.

14. Parallelle Eennummers: Gegeven een reeks A van nullen en enen. Het eennummer van een positie met waarde 1 geeft aan, de hoeveelste opeenvolgende 1 het is. Een positie met waarde 0 heeft eennummer 0. Voor 11011011111000111 zijn de eennummers 12012012345000123. Piets Recursieve Eennummeraar berekent eerst de PRE van het linker- en rechterdeel: PRE(A,p,r) { // Zet A[p,...,r-1] om naar eennummers q=(p+r)/2 ; invoke PRE(A,p,q) en PRE(A,q,r) ; (a) Hoe ziet de voorbeeldrij er hierna uit, en wat moet er dan nog gebeuren? (b) Maak Piets programma af. (c) Analyseer work en span (met de Master Theorem). (d) Is Piets algoritme efficient en optimaal? Oplossing: (a) Het resultaat van 11011011 en 111000111 is 12012012 en 123000123. In de hele rij zijn de enen in het eerste segmentje van de rechter deelrij onderdeel van een langere run, en daar moet je het laatste antwoord van links (2) nog bijtellen. (b) Het ophogen van het eerste segment rechts kan zo: i = q ; while (i0) A[i++]+=A[q-1]; maar dat kost lineaire span. Slimmer is dat elke positie aan zijn uitkomst kan zien of hij in het beginsegment zit: pfor(i : q <= i < r) if (A[i] = i-q+1) A[i]+=A[q];. (Aan een rij van lengte 0 of 1 hoef je niks te doen dus vooraan hoort if (r <= p+1) return; maar voor die ene punt hoef je dat niet te zeggen.) (c) Beide oplossingen geven lineair veel extra werk, dus W (n) = 2W (n/2) + O(n) met oplossing n lg n. De tweede geeft constante extra span dus S(n) = S(n/2) + O(1) met oplossing lg n. (d) De span is logaritmisch, dus ook polylogaritmisch; de overhead is logaritmisch (sequentieel kan het lineair) dus ook polylogaritmisch. Efficient betekent polylog span en polylog overhead, dit is hier van toepassing. Optimaal betekent polylog span en constante overhead, en is hier niet van toepassing. Beoordeling: Totaal tot 4 pt, een per deelvraag. Voor de volle punten moest je de superparallelle combinatiemethode uitvinden, maar met inzicht in recursie en Master Theorem kon je al snel 3pt binnenharken. A = Je hebt iets Anders geanalyseerd dan je eigen methode. C = Jouw combinatiecode is een Complete sequenti¨ele oplossing. H = Bij (b) sequenti¨ele code maar bij (c) reken je O(1) span; Hoe? L = Beste sequenti¨ele tijd is Lineair. P = Verhoog rechts alle Positieve A[j]; Foute uitkomst. R = Snap je Recursie wel? Bij het ontwerpen ga je ervan uit dat een aanroep werkt, ook al heb je de methode nog niet geschreven. S = Als je Sequentieel combineert krijg je geen punt voor (b). Mogelijk nog voor c (als je lineaire span vindt) en d (nee, nee).

15. Parallel MaxOneRow: De MaxOneRow van een rij bits is het maximale aantal aaneengesloten 1-en; bv van 01011001111100111110 is de MaxOneRow 5 (zie posities 7 en 14). Je kunt de MaxOneRow berekenen met een recursieve module die van een rij bits deze drie waarden oplevert: p: het aantal 1-en waarmee de rij begint; i: de MaxOneRow; s: het aantal 1-en waar de rij op eindigt. (a) Wat is de beste sequentiele tijd om de MaxOneRow te berekenen? (b) Hoe vind je de p, i en s van een rij uit die van de linker- en rechterhelft? (c) Analyseer de work van het resulterende algoritme. (d) Analyseer de span van het resulterende algoritme. (e) Is het parallelle algoritme efficient en is het optimaal? Leg uit! Oplossing: (a) O(n). Het kan niet sublineair maar dat hoef je niet te bewijzen. Lineair algo: c=0; m=0; // Current en Max aantal enen op rij for (i=0; im) ? c : m; } (b) Stel rij S heeft linker- en rechterdeel L en R. S.p = (L.p < L.length) ? L.p : L.length + R.p; S.i = max(L.i, L.s+R.p, R.i); S.s = (R.s < R.length) ? R.s : R.length + L.s; (c) Het combineren is constant veel werk dus voor work vind je W (n) = 2.W (n/2) + O(1) met oplossing W (n) = O(n). (d) Het combineren is constant veel werk (de drie waarden kunnen zelfs parallel) en de deelrijen zijn onafhankelijk dus je vindt S(n) = S(n/2) + O(1) met oplossing S(n) = O(lg n). (e) De span is logaritmisch en het werk lineair, hetzelfde als de sequentiele berekening, dus er is constante overhead. Daarmee is het algoritme zowel efficient (polylog span en polylog overhead) als optimaal (polylog span en constante overhead). Beoordeling: Maximaal 5pt, per deelantwoord een punt indien juiste methodiek toegepast. Ik houd er geen casino op na dus gokken wordt niet beloond! Codes: B = Zegt dat vanwege Binaire operaties, span Ω(lg n) optimaal is. Onjuist, er is hier Superparallellisme mogelijk waarmee je MOR oplost in O(1) tijd. Ik weet nog niet of je O(n3 ) of O(n4 ) cores nodig hebt. C = Zegt: Het Cre¨eren van de sublijsten kost Ω(n). Nou, dat moest je dan maar gewoon niet doen! Geef nooit de lijsten zelf als argument mee, maar begin- en eindpositie van een segment ervan. D = Vergeet bij (b) het geval van Doorloop prefix (dus zegt: S.p = L.p), -1/2. H = Zegt bij (a) O(n) maar niet Hoe, 1/2. L = Vergelijk bij (b) de L.p en R.s met de lengte en niet met n/2; door afronding is dat niet altijd ’t zelfde. M = Motivatie/berekening onjuist of ontbreekt. R = Voor een Recursief algoritme moet je beschrijven hoe je deeloplossingen samenvoegt (daar werd ook expliciet om gevraagd), niet hoe je de instanties verder en verder verdeelt. S = Zegt niets over Span bij (e). U = Uitkomst ontbreekt of fout. V = Bij (c/d) heb je de berekeningen van work en span Verwisseld; samen 1pt. W = Bij (e) moet ook Work polylog zijn.

Uitleg over Greedy Schedule: Brent’s Lemma zegt dat een berekening met work w en span s, op p cores kan worden uitgevoerd in tijd Tp ≤ w−s p + s. Dit bereik je met een Greedy Schedule: het runtime-system moet ervoor zorgen dat in elk timeslot, zoveel mogelijk cores een berekening uitvoeren. Een timeslot waarin alle ready stappen worden verwerkt, maakt de berekeningsgraaf een laag korter en dit gebeurt s keer. Een timeslot waarin de berekeningsgraaf niet in hoogte afneemt, voert p stappen uit en dit gebeurt hoogstens (w−s)/p keer. 16. Goed en slecht Greedy Schedule: De lengte van een Greedy Schedule kan vari¨eren, afhankelijk van welke ready stappen de scheduler kiest. Geef een voorbeeld van een berekeningsgraaf en twee Greedy Schedules, elk op drie cores, waarbij het ene schedule minstens anderhalf keer zo lang duurt als het andere. Oplossing: De graaf heeft 180 knopen, zestig zijn sequentieel afhankelijk in een sliert, de andere 120 zijn helemaal onafhankelijk. Schedule 1: werk eerst de losse knopen af (die zijn allemaal ready) in 40 rondes, dan is de sliert nog over en die kost 60 rondes (waarin maar ´e´en core actief is). Schedule 2: neem per ronde de ene ready stap van de sliert en twee losse, dit kost 60 rondes. Beoordeling: Twee punten voor goed beargumenteerd en uitgewerkt voorbeeld. Codes: K = Idee wel aardig, maar je ratio is Kleiner dan 1,5. T = Dit zijn Twee verschillende berekeningen.

17. Greedy Schedule: Een paralelle berekening met work w en span s moet worden uitgevoerd op een machine met p cores en je wilt dit doen volgens een Greedy Schedule. (a) Beschrijf hoe een greedy schedule tot stand komt. (b) Waarom is de lengte t van dit schedule begrensd door wp + s? (c) Je baas vindt dit niet snel genoeg, volgens hem werkt de computer van jullie concurrent viermaal zo snel. Kun je de concurrent inhalen met een betere scheduling? Oplossing: (a) Het Greedy Schedule kiest in elke ronde een maximaal aantal ready stappen. Dit zijn er p in een “volle” (core-bound) ronde, of minder in een “lege” (ready-bound) ronde. (b) Omdat een volle ronde p stappen uitvoert, zijn er daavan hoogstens w/p. Omdat een lege ronde de span van de (resterende) berekening verlaagt, zijn er daar hoogstens s van. Het aantal rondes is dus begrensd door wp + s. (c) Met alleen betere scheduling zal dit niet gaan, omdat Greedy Scheduling 2-Optimaal is. Elk schedule gebruikt minstens max( wp , s) stappen, en dit is meer dan de helft van jullie aantal w p + s. Om viermaal zo snel te worden, zul je dus een beter algoritme of een snellere computer moeten maken. Beoordeling: Te behalen 3pt, voor elk onderdeel 1. N = Je “bewijst” wel dat w/p + s Nodig is, maar niet dat ’t voor dit schedule genoeg is. T = Voor volle punt moet de Twee-optimaliteit wel genoemd worden. W = Work en Span zijn geen aparte delen van de berekening (als in: verwerk eerst de work en daarna de span), maar twee eigenschappen ervan.

18. Omslagpunt work en span: Voor zekere taak heb je een parallel algoritme A1 met work w1 en span s1 . Er is een alternatief algoritme A2 met slechter work w2 > w1 maar betere span s2 < s1 . Voor welke aantallen cores, p, verwacht je van A2 een lagere rekentijd dan van A1? (Geef je antwoord asymptotisch, dus in grote-O of Θ.) Oplossing: Het antwoord is p ≥ w2 /s1 . Volgens de scheduling-theorie van Brent is de rekentijd van A ongeveer w/p zolang p ≤ w/s, de work-bound fase, en ongeveer s wanneer p ≥ w/s, de span-bound fase. Door dit in een grafiekje uit te beelden, zie je dat A2, A1 “inhaalt” bij p = w2 /s1 . Beoordeling: Voor goed antwoord met enige toelichting 3pt. Als je alleen hebt klein of groot aantal, dan 1pt. S = A1 wordt Span-bound bij p = w1 /s1 , maar pas “ingehaald” bij een iets hogere p.

19. Parallelle Polynoom-evaluatie: Een polynoom van graad n is een expressie van de vorm Pn k k=0 ak · x . Onder het evalueren verstaan we het uitrekenen van de waarde, gegeven de co¨effici¨enten a0 t/m an en het argument x. Sequentieel kan dit met n vermenigvuldigingen en n optellingen. Je kunt een snel parallel algoritme krijgen, door de expressie te herschrijven tot een polynoom van graad n/2 in de parameter x2 : a + b.x1 +c.x2 + d.x3 +e.x4 + f.x5 +g.x6 + h.x7 = (a + b.x) +(c + d.x).(x2 )1 +(e + f.x).(x2 )2 +(g + h.x).(x2 )3 (a) Geef expressies voor de co¨effici¨enten a00 t/m a0n/2 en de parameter x0 van het nieuwe polynoom. (b) Geef een recurrente betrekking voor de work en span van een parallel algoritme dat zo het polynoom evalueert. (c) Los de vergelijkingen voor work en span op met de Master Theorem. (d) Is deze methode efficient? En is hij optimaal? Leg uit! Oplossing: (a) Neem, voor k van 0 tot n/2: a0k = a2k + a2k+1 .x. (Detail mag je negeren: als n even is, loopt k tot precies n/2 en dan is 2.k + 1 groter dan n; neem dan an+1 = 0.) Neem x0 = x.x. (b) Het uitrekenen van a0k kost een vermenigvuldiging en een optelling, je moet dit n/2 keer doen, dus samen n handelingen. Het kwadrateren valt daarbij in het niet. Voor de work betekent dit W (n) = O(n) + W (n/2). Je kunt alle a0 en x0 parallel uitrekenen, dat kost maar 2 stappen na elkaar: S(n) = 2+S(n/2). b (c) Even met de MasterTheorem erover heen. Eerst W : n log a is n0 is 1, dus de basisterm n is polynomiaal meer zodat W (n) = O(n). b Dan S: n log a is n0 is constant, net als de basisterm. Ze zijn dus gelijk in O(), dus extra log erbij: S(n) = O(lg n). (d) De span is O(lg n), dat valt onder Polylogaritmisch. De overhead is werk/sequentieel is O(1) dus constant. Efficient wil zeggen: Polylog span en Polylog overhead, hieraan is voldaan. Optimaal wil zeggen: Polylog span en constante overhead, hieraan is voldaan. Het is dus efficient EN optimaal. Beoordeling: Voor elke deelvraag een punt. Verdere codes: Pn/2 C = Bij (a) een antwoord (bv. k=0 (a2k + a2k+1 x)(x2 )k ) met de gevraagde co¨efficienten in een Formule verpakt, volledige punt. D = Kent bij (d) Definitie van efficient en optimaal en past goed toe, 1pt. F = Bij (b) Foute formule zonder uitleg, 0pt. R = Betrekking bij (b) is helemaal niet Recurrent (bv W (n) = n/2 + O(n)), 0pt. S = Zegt bij (a) wel de Speciale gevallen a00 = a + bx en a01 = c + dx, maar niet de algemene formule, 1/2pt. V = Verkeerde Vergelijking goed opgelost bij (c), 1/2. Als je denkt dat je het nou goed snapt, probeer dan eens dezelfde vragen te beantwoorden met de formule: a + b.x1 + c.x2 + d.x3 +e.x4 + f.x5 + g.x6 + h.x7 = (a + b.x + c.x2 + d.x3 ) +(e + f.x + g.x2 + h.x3 ).x4

20. Integer vermenigvuldigen: Gegeven integers A en B, als rijen van n cijfers. Je moet het product C berekenen, als rij van 2n cijfers. Sequentieel kan dit in O(n2 ) tijd door elk cijfer van A te combineren met elk cijfer van B. (a) Geef een parallel algoritme met kwadratische work en lineaire span. (b) Is dit algoritme efficient, en is het optimaal? (c) Is een beter algoritme dan onder (a) mogelijk? Oplossing: (a) Het volgende, niet-recursieve, algoritme gebruikt 2n processors en lineaire tijd. Fase 1, inproduct: Processor i berekent de co¨efficient van 10i als Fi is som over j van Aj ∗Bi−j . Uitkomst is maximaal 81n. Fase 2, optellen: E´en processor berekent de cijfers van C van rechts naar links met (Ri , Ci ) = ((Fi + Ri−1 )/10, (Fi + Ri−1 )%10)). (b) Zowel optimaal als efficient vereisen polylogaritmische span, die je hier niet hebt, dus geen van beide. Overhead is O(1) dus goed genoeg voor beide, jammer van de Span! (c) Gebruik het recursieve algoritme op basis van drie vermenigvuldigingen van halve lengte. Met parallelle subvermenigvuldigingen krijg je S(n) = S(n/2) + O(n) = O(n) en W (n) = 3W (n/2) + O(n) = O(n1,585 ). Wel beter, nog steeds niet efficient of optimaal. Beoordeling: Totaal 3pt, een per deelvraag.

3

Locking

21. Fairness en TaS-lock: Het TaS-lock heeft als lock-methode het herhalen van de Test-andSet operatie, tot het resultaat 0 wordt gekregen: while (L.TaS ==1) {}. (a) Voldoet het TaS-lock aan No Starvation als fairness niet wordt aangenomen? (b) Voldoet het TaS-lock aan No Starvation als fairness wel wordt aangenomen? (c) Voldoet het TaS-lock aan No Deadlock als fairness wel wordt aangenomen? Oplossing: (a) Nee, een thread kan willekeurig vaak worden gepasseerd. Stel dat threads 0 en 1 elkaar afwisselen in de kritieke sectie: steeds wanneer de ene thread de CS verlaat, wil de andere erin en vraagt en krijgt het lock. De waarde van L wisselt willekeurig vaak tussen 0 en 1. Het is mogelijk dat daarnaast thread 2 in de lock aanvraag blijft, maar telkens valt zijn TaS op een moment dat L 1 is. (b) Het scenario beschreven in (a) is fair! Het is wel sneu voor thread 2 dat zijn operatie steeds op een ongunstig moment valt, maar hij komt wel oneindig vaak aan de beurt met een instructie. (c) Stel dat er een of meer threads het lock vragen, en de CS is onbezet. De laatst kritieke thread komt wegens fairness toe aan de instructie die L weer op 0 zet. Wegens fairness komen daarna alle wachtende threads weer aan de beurt voor een TaS instructie, en de eerste daarvan is succesvol. Beoordeling: Voor elk antwoord 1 punt. M = Motivatie ontbreekt of onzinnig. 22. LockOne: Hier staan de lock en unlock van de LockOne klasse (voor thread i). public void lock() { flag[i] = true; while (flag[j]) {}

public void unlock() { flag[i] = false ; } }

(a) Aan welke drie eisen moet een lock implementatie voldoen? (b) Welke van deze eisen is/zijn voor LockOne niet voldaan? Waarom? (c) Als je de twee regels in lock verwisselt, is dan het probleem opgelost? Oplossing: (a) Een lock moet voldoen aan (1) Mutual Exclusion: hoogstens 1 thread heeft het lock (2) No Deadlock: Als threads het lock willen krijgen, en het is vrij, moet eentje het krijgen (3) No Starvation: elke thread die het lock vraagt, zal het ooit krijgen. (b) LockOne voldoet aan mutual exclusion omdat een thread eerst zijn flag op true zet, en dan nog de andere op false moet zien voordat hij kritiek wordt (principe van Safe Sluice). LockOne voldoet niet aan No deadlock: als beide threads de lock methode beginnen, kunnen ze beide elkaar blokkeren en is er deadlock. De deadlock impliceert ook starvation; een tread kan overigens niet willekeurig vaak worden ingehaald. (c) Nee, dan krijg je de code van LockZero die geen mutual exclusion kent. Beoordeling: Voor a en c elk 1pt, voor b 2pt. Beoordelingscodes: A = Bij (b) wel iets over deadlock, maar Andere eisen niet genoemd; -1/2. N = Bij (a) worden de Namen genoemd maar geen omschrijving van de eisen; 1/2pt. S = Zegt NoStarvation bij (b). Omdat NoStarvation sterker is dan NoDeadlock, is schending van NoStarvation zwakker dan schending van NoDeadlock, daarom is dit een minder sterk antwoord; 1,5pt. W = Bij (b) wordt wel de geschonden eis genoemd, maar niet Wanneer die geschonden wordt (scenario); 1pt. Z = Ziet bij c de schending van ME over het hoofd, max 1/2.

23. LockTwo: Hier staan de lock en unlock van de LockTwo klasse (voor thread i). public void lock() { victim = i; while (victim == i) {}

public void unlock() { } }

(a) Aan welke drie eisen moet een lock implementatie voldoen? (b) Welke van deze eisen is/zijn voor LockTwo niet voldaan? Waarom? (c) Als je de opdracht victim = i verplaats naar de unlock, is dan het probleem opgelost? Oplossing: (a) Een lock moet voldoen aan (1) Mutual Exclusion: hoogstens 1 thread heeft het lock (2) No Deadlock: Als threads het lock willen krijgen, en het is vrij, moet eentje het krijgen (3) No Starvation: elke thread die het lock vraagt, zal het ooit krijgen. (b) LockTwo dwingt af dat de twee threads het lock om de beurt hebben. Het voldoet niet aan No deadlock: als een thread het lock wil en de andere is er niet in geinteresseerd, blijft de thread wachten, terwijl het lock vrij is. Omdat het strikt om de beurt gaat, is er wel No starvation mits beide threads steeds weer het lock vragen. (c) Nee, omdat threads willekeurig traag of snel kunnen werken, maakt het niet uit of je de eerste opdracht van lock verplaats naar het eind van unlock. Beoordeling: Voor a en c elk 1pt, voor b 2pt. Beoordelingscodes: D = Zegt bij (c) dat ’t nu misgaat bij Drie of meer threads. Dat is echter bij de gegeven LockTwo ook al, dus niet goed; 0pt. I = Zegt bij (c) dat er iets mis gaat omdat victim niet is ge¨ınitialiseerd. Reken ik niet goed omdat bij de wijziging natuurlijk ook de initialisatie aangepast kan worden. M = Bij (a) worden de namen genoemd maar geen oMschrijving van de eisen; 1/2pt. S = Zegt NoStarvation bij (b). Omdat NoStarvation sterker is dan NoDeadlock, is schending van NoStarvation zwakker dan schending van NoDeadlock, daarom is dit een minder sterk antwoord; 1,5pt. W = Bij (b) wordt wel de geschonden eis genoemd, maar niet Wanneer die geschonden wordt (scenario); 1pt.

24. Lock typen: Voor locken kennen we een spin-lock en een blocking lock. (a) Leg uit, wat het verschil is tussen deze twee type locks. (b) In welke situaties is een spin-lock beter, en wanneer is een blocking lock beter? (c) Wanneer is er een voordeel van een TTaS-lock boven een TaS-lock? Oplossing: a. Bij een spin-lock wacht een thread actief, door herhaald een variabele te bekijken totdat die een gewenste waarde heeft. Bij een blocking lock wordt de thread door het OS buiten de verdeling van processortijd gehouden. b. Je moet de kosten van het actief spinnen afwegen tegen de eenmalige kosten van het (de)activeren door het OS. Als je verwacht dat een thread slechts uiterst kort wacht, kan spinnen beter zijn, als de wachttijd hoger wordt, verdient blocking al snel de voorkeur. c. Het TTaS lock voorkomt dat er veel bus-verkeer is door het herhaald uitvoeren van een Test-And-Set. Als de kritieke threads weinig geheugen-operaties doen, zullen die van het bus-verkeer weinig vertraging ondervinden. Maar iha verwacht je van TTaS een verbetering, wanneer threads tijdens hun werk geheugentoegang willen. Beoordeling: Voor (a) 2pt, voor (b) en (c) elk 1pt. Enkelen merkten op, dat een spin-lock voor een eerlijker volgorde van toetreding tot de CS leidt. Dit is natuurlijk sterk afhankelijk van de precieze implementatie. Een puur TaS of TTaS lock heeft deze eigenschap absoluut niet. De queueing daarentegen die in OS wordt gebruikt, kan als redelijk eerlijk worden beschouwd. Dus je kunt dit niet in algemene zin als verschil aanhalen. Op een UNIcore geldt spinnen als uit den boze, want als de lock- houdende thread uitgeswapt is, kan een complete time-slice verspind worden. Bij een multicore heeft het natuurlijk alleen zin om ”zuinig”te wachten, als je de tijd van een geblockte thread kunt opvullen met een andere thread. Heb je geen extra threads voor latency hiding, dan blijft de core van de geblokkeerde thread idle.

25. Deadlocks: Geef een eenvoudig programma waarin elke lock voldoet aan de deadlock-freedomeigenschap, maar het toch voor kan komen dat het programma als geheel deadlockt. Oplossing: Kijk naar Dining Philosophers, waar elke filosoof eerst zijn linker- en dan zijn rechtervork pakt. Hier kan op filosoof-niveau deadlock ontstaan, ook wanneer het pakken van vorken deadlock-vrij verloopt. Beoordeling:

26. Bakery labels: In het Bakery algoritme kiest een thread i een label: l = 0; for (j=0; j l) l = label[j]; label[i] = l+1 (a) Geef een voorbeeld waarin thread a eerder klaar is met kiezen dan thread b, maar toch een groter label krijgt. (b) Is het een probleem dat twee threads een gelijk label kunnen krijgen? Licht toe! Oplossing: (a) Mijn voorbeeld heeft drie threads T0, T1 en T2. T1 gaat labelen en leest driemaal een nul, zet dus label[1] op 1. Thread T0 gaat ook labelen, leest label[0] (die op 0 staat), doet een dutje tot T1 geschreven heeft, en leest dan die 1 en de 0 van T2, zet een 2 in label[0] en sluit het labelen af. Thread T2 gaat ook labelen, leest de drie labels voordat T1 schrijft. Dan gaat hij slapen tot nadat T0 klaar is met labelen, schrijft de 1 in label[2] en termineert het labelen. Nu sluit T0 eerder af dan T2 maar met waarde 2, terwijl T2 een 1 heeft. (b) Gelijke tickets is niet gezond in Bakery, maar dit wordt opgelost door de ticket te nemen als de combinatie van label en threadnummer. Beoordeling: Voor deel (a) 1 punt en voor deel (b) twee punten. L = Denkt dat threads de l delen, maar die is priv´e. M = Als threads gelijke tickets hebben, geldt Mutual Exclusion niet! R = Bakery veronderstelt R/W atomicity. S = Zegt B overSchrijft L[a]; nee! T = Je signaleert het probleem, maar zegt niets over de oplossing met Threadnummers; –1.

27. TaS-lock: Een TaS-lock beschermt kritieke code. (a) Hoeveel test-and-set bits zijn nodig om een lock te maken voor n threads? Geef de code. (b) Noem enkele nadelen van het TaS-lock? Welk nadeel wordt opgeheven door het TTaSlock, en hoe? Oplossing: (a) Je hebt maar ´e´en bit nodig, en pakt het lock door hem van 0 op 1 te zetten: lock:

while (s.TaS == 1) { }

unlock:

s = 0;

(b) 1. Genereert veel cache verkeer doordat een TaS de cache invalideert; 2. Meerdere threads spinnen op dezelfde bit; 3. Spinnen kost rekenkracht ook al doe je niets; 4. Starvation. Het TTaS lock beperkt cache verkeer (nadeel 1) door het lock te testen met een gewone read, en alleen een TaS te proberen als hij 0 is. Beoordeling: Voor (a) 1pt als de code goed is, en bij (b) 1/2 voor twee of meer nadelen en 1/2 voor het voordeel van TTaS. Beoordelingscodes: E = Noemt maar E`en nadeel.

4

Registers

28. Safe Integer: Van een Safe bit kun je een Regular bit maken met de methode van silent writes. (a) Wanneer zal een Write operatie als silent uitgevoerd worden? (b) Is de methode van silent writes ook toe te passen om van een Safe Integer een regular Integer te maken? Oplossing: (a) Een Write operatie zal alleen daadwerkelijk schrijven als de waarde verschilt van de vorige; dus silent zijn als de wrtite-waarde gelijk is aan de vorige. (b) Voor integers werkt dit niet. Voor bits alleen omdat er maar twee waarden zijn, zodat tijdens een (actieve) write alle waarden uit het domein zijn toegestaan. Als je een safe int met waarde 0, overschrijft met een 1, kan een overlappende read waarde 2 opleveren. Beoordeling: Max 2, voor elke deelvraag 1. Codes: C = Een andere Constructie van regular integer werd niet gevraagd. M = Onvoldoede of onjuiste Motivatie.

29. Safe en Regular Bit: Bij het implementeren van registers kennen we een onderscheid tussen een safe register, een regular register en een atomic register. (a) Leg uit, waarom regular een sterkere eigenschap is dan safe. (b) Leg uit, waarom regular een zwakkere eigenschap is dan atomic. (c) Laat zien, hoe je met een safe bit, een regular bit kunt implementeren. Oplossing: (a) Bij safe is er niets gespecificeerd over de uitkomst van een read die met een write overlapt. Bij regular wel, dan heb je de garantie dat de opgeleverde waarde die van de laatste ervoor, of een overlappende write is. (b) Als het atomair is, lijkt het of elke operatie apart gebeurt op een moment binnen de werkelijke uitvoering. Voor een read betekent dat sowieso, dat de opgeleverde waarde er eentje is van een overlappende of de voorlaatste write. Maar bovendien kan er bij atomic geen inversie zijn: dat achtereenvolgende reads eerst een nieuwe, dan een oudere waarde opleveren. Bij regular kan dat wel, omdat regular wel iets zegt over de uitkomst van elke individuele read, maar niet over de relatie tussen de opgeleverde waarden. (c) Een regular bit mag de oude en nieuwe waarde opleveren als een read met een write overlapt. Een safe bit kan bij overlap sowieso alle waarden opleveren. Nu kent een bit maar twee waarden, 0 en 1, en als er dus sprake is van een werkelijke verandering, zijn oud en nieuw samen dus ook alles. Constructie, de Silent Write: gebruik een SAFE bit, maar de Writer houdt bij wat de laatste write waarde was. In een Write(x) wordt gekeken of x al in het register zit, en alleen als dat niet zo is, wordt een write werkelijk gedaan. De Read doet gewoon een read en levert de waarde op. Beoordeling: Een punt per deelvraag. R = Bij b niets over Regular. W = Willekeurige uitkomst alleen bij overlap.

30. Register uit bit: Om een m-waardig register te implementeren uit bits gebruiken we een unaire representatie. De Write(x) set bit r[x], en reset de lagere bits. De Read bekijkt bits van laag naar hoog, en returnt de eerste x waarvoor r[x] true is. Deze constructie is behandeld op college. (a) Een karakteristieke eigenschap van registers is: dat een Write alle voorgaande toestanden van het register uitwist. In deze register-implementatie zijn “oude” toestanden echter nog zichtbaar als 1-en in de array. Heeft deze implementatie dan wel de karakteristieke registereigenschap? (b) Een programmeur vindt het mooier om, in een Write(x), ook de hogere bits te resetten (zodat na de operatie, precies ´e´en bit true is). Laat zien, dat dit tot een foute uitkomst bij Read leidt. Oplossing: a. Je moet hier een onderscheid maken tussen de ¨ınterne”representatie van de toestand, en de ¨extern¨ aangeboden toegang. De oude toestanden die als 1 zichtbaar zijn, kun je alleen zien door inspectie van de interne toestand van het object. Als een Write-operatie eenmaal is afgerond, is geen van de daarvoor geschreven waarden nog te zien met een Readoperatie. b. Als je deze ”hogere”bits gaat resetten, kun je op zeker moment een bit resetten ZONDER dat er een hogere op 1 staat. Dit kan ertoe leiden dat een Read volledig uit de rij loopt. Beoordeling:

31. Atomaire en Regular Registers: Deze vraag gaat over Single Reader, Single Writer Registers. (a) Geef een voorbeeld van gedrag dat wel Regular is, maar niet Atomic. (b) Hoe kun je met een Regular register een Atomic register maken? Oplossing: (a) Bij Regular registers is een inversie acceptabel. Register heeft waarde 8 en er komt een write(5). Tijdens de write doet de reader twee reads, waarvan de eerste de 5 oplevert en de tweede de 8. (b) Gebruik sequence numbers. Writer houdt sn bij en doet Write(x) als write((x,++sn)). De Reader onthoudt de hoogst gekregen combinatie. Na een read pakt hij het hoogste sn, onthoudt en returnt die waarde. Beoordeling: Totaal 3, nl 1 voor (a) en 2 voor (b). Bedoeling van de opgave was, dat je kennis uit het college/boek met enige nauwkeurigheid zou weergeven. Voor sommigen was het al lastig, welke kennis moest worden opgeschreven. Het ging niet om het regular maken van safe bits, het multiread maken van singleread, het multivalued maken van bits! A = Wat je beschrijft is wel Atomair. H = Helpen door Readers was alleen bij Multireader maken. I = Je beschrijving van het gedrag is Incompleet. L = Locking mag absoluut niet want om dat te maken heb je eerst sterke registers nodig. M = Duplicatie gebruik je voor Multireader. N = Niet alleen opslaan, ook serieNummers erbij! R = Wat je beschrijft is niet Regular. S = Wat je opschrijft is niet Singlereader. U = Unair gebruik je om multivalued registers te maken. W = Je oplossing is niet Wachtvrij.

32. Multivalued register: Je kunt een m-waardig regular register maken uit een array van m regular bits. De Writer schrijft waarde x door bit x op 1 te zetten en de lagere bits op 0, de reader zoekt vanaf positie 0 naar de eerste 1: Write(x): r[x].write(1) for (i=x-1; i>=0; i--) r[i].write(0)

Read: for(i=0; i<m; i++) if (r[i].read == 1) return i

(a) Laat zien dat de Reader kan falen wanneer de Writer ook de hogere bits op 0 zet (met een loopje for (i=x+1; i<m; i++) r[i].write(0)). (b) Is het gebouwde register ook atomic? Leg uit! Oplossing: (a) Stel dat de Writer eerst Write(4) doet en dan Write(2). Na de Write(4) zijn alle bits voor positie 4 op 0, neem aan dat de Reader begint en de 0len leest tot positie 3. De Writer voert zijn complete Write(2) uit, daarna staan alle bits voorbij positie 2 op 0. De Reader gaat verder en leest alleen maar 0len. (b) Het is niet atomic, een inversie is mogelijk, omdat de gebruikte bits zelf alleen maar regular zijn. Scenario hiervoor: stel de waarde is 2 maar de Writer doet een Write(3). De Writer begint met r[3] op 1 te zetten, en gaat dan r[2] op 0 zetten met r[2].write(0). Tijdens deze write kan de Reader een volledige Read afwerken, waarbij de read op r[2], die met de r[2].write(0) overlapt, de nieuwe waarde al geeft zodat de Read resultaat 3 geeft. Daarna kan de Reader weer een volledige Read afwerken, waarbij de r[2].read, die weer met de r[2].write(0) overlapt, de oude waarde nog teruggeeft zodat deze Read 2 oplevert. (We vermoeden dat de constructie wel een atomair register zou opleveren als de gebruikte bits atomair zijn. Als dat klopt, kun je een scenario alleen maar geven door niet-atomair gedrag van bits erin te bouwen.) Beoordeling: Voor a en b elk 2pt. Beoordelingscodes: A = Motiveert een nee bij (b) met een Atomair scenario; 0pt. Bijvoorbeeld: een “inversie” bij twee overlappende reads, dit kan niet want als twee Reads overlappen kan nooit sprake zijn van inversie. B = Beredeneert bij (b) dat het atomair is, maar vanuit Atomaire bits. Slim, maar de gegeven bits zijn slechts regular; 1pt. D = Noemt alleen Definitie van atomic maar bewijst er niets over, 0pt. L = Beweert dat een Latere writewaarde kan worden geretourneerd. Kan niet, zou ook niet regular zijn; 0pt. M = Beredeneert bij (b) incorrectheid met een MultiWriter scenario, terwijl deze constructie alleen bedoeld is voor SingleWriter; 0pt. R = Beredeneert Regular ipv atomair, 0pt. S = Zegt bij (b) nee en noemt inversie, maar zonder Scenario te geven; 1pt. T = Beweert bij (b) dat het niet atomair is omdat Timestamps nodig zijn; 1pt. W = Voert bij (a) een scenario op waarin het fout gaat met twee Writers; zie M, 1pt.

33. Technieken voor Register-Implementatie: Om sterke registers te implementeren kunnen deze technieken worden gebruikt: Silent Write, Unaire notatie, Serienummers. (a) Hoe werkt de Silent Write? (b) Welke techniek gebruikt men om van een regular bit naar een m-valued register te gaan? Welke techniek gebruikt men om van een Safe bit naar een Regular bit te gaan? Oplossing: (a) De Writer onthoudt welke waarde hij als laatste geschreven heeft, en voert een write alleen uit als de nieuwe waarde anders is. (b) Dat gaat met unaire notatie. Dat gaat met Silent Write. Beoordeling: 2pt.

5

Consensushierarchie

Let op: Het onderwerp Consensushierarchie hoort helemaal bij de toets van 17 december 2015. 34. Consensus en Test-and-Set: Geef een wacht-vrije implementatie van 2-Consensus met een Test-and-Set. Oplossing: Gebruik een TaS arbiter en twee registers Prop[2] om de inputs op te slaan. Methode decide(x) voor thread i: Prop[i] = x if (arb.tas) return Prop[i] else return Prop[1-i] Beoordeling: Voor het correct opnoemen van deze procedure 2pt. Beoordeling: C = Code voor CaS ipv voor TaS, 1pt slechts. W = Het Wegschrijven van de input voor de tas opdracht vergeten. Dit is esentieel!! –1/2. X = Je gebruikt de TaS als eXchange, waar je een invoerwaarde in gaat opslaan. Kan niet, de TaS bevat maar 1 bit.

35. Lock-free snapshot: Een snapshot-object heeft voor elke thread een cel. De cel kan atomair geschreven worden door de thread (update), en de combinatie van cellen kan atomair gelezen worden (scan). (a) Geef het algoritme van double collect om te komen tot een atomair snapshot. Waarom is het opgeleverde snapshot correct? (b) Waarom is de double collect methode niet wait-free? Kan het snapshot-object wait-free worden gebouwd? Hoe? Oplossing: (a) Lees alle cellen (collect) en lees dan alle cellen nogmaals (double collect). Vergelijk de twee reeksen: als geen van de cellen veranderd is tussen de eerste en tweede collect, wordt de reeks waarden opgeleverd. Om op veranderingen te controleren zijn serienummers nodig (ABA probleem). Als er geen veranderingen zijn geweest, bevatte elke cel de gerapporteerde waarde continu tussen de eerste en tweede read. Dus op het moment tussen eerste en double collect bestonden die waarden tegelijkertijd. (b) De double collect kan ongeldig zijn als er een update tussendoor komt. Er is geen harde limiet op hoevaak dit gebeurt, het herhalen van de d.c. is dus een soort spinnen. Voor een wacht-vrije methode moet er een limiet op het aantal stappen zijn. De snapsot is wacht-vrij te bouwen, door updaters, scanners te laten helpen. Bij een update maak je eerst een scan, en sla de waarde op bij de cel. In een scan, neem de opgeslagen scan over van een “dubbelverstoorder”. Beoordeling: Voor (a) 2pt en (b) 1 voor elke deelvraag. Beoordeling: C = Maak ’m bij b wachtvrij door “1x Collect en dan maar fout antwoord”; 0pt. N = Zegt niets over serieNummers of ABA probleem, 1/2 aftrek. S = Noemt de collect in (a) “scan” en zegt niets over wat dat is, 1/2 aftrek.

36. Atomic Copy: Een CopyDog heeft als toestandsruimte een rij van waarden, en naast operaties write(i,x) (schrijf x in locatie i) en read(i) (geef waarde van locatie i), een operatie copy(i,j) die de waarde van locatie i kopieert naar j. Een CopyDog met twee locaties kan 2-Consensus implementeren. (a) In de propose(x) operatie zal thread i (0 of 1) precies eenmaal Arb.copy(i,1-i) uitvoeren. Hoe kun je de initi¨ele waarde van Arb kiezen om ervoor te zorgen dat alleen de eerste copy-operatie iets aan de inhoud verandert? (b) Hoe kan een thread na het uitvoeren van zijn copy zien, welke thread als eerste de copy deed? (Uitleg!) (c) Geef een wachtvrij algoritme dat een CopyDog gebruikt en 2-Consensus implementeert. (d) Kan een CopyDog wachtvrij worden ge¨ımplementeerd met registers? (e) Wat is het Consensusgetal van een CopyDog? Oplossing: (a) Een copy(0,1) of copy(1,0) verandert iets aan de toestand, precies wanneer de twee waarden verschillend zijn. Na de copy zijn de waarden sowieso gelijk, en als je daarna direct weer een copy doet, verandert die niets. We gaan er dus voor zorgen dat de twee waarden initieel verschillen: zet een 0 op locatie 0 en een 1 op locatie 1. (b) Als de copy(i,1-i) de eerste is, staat daarna de i op beide plaatsen, wat ook door een volgende copy niet anders wordt. Het threadnummer van de eerste copy staat dus op locatie 0 (en op 1). (c) CopyDog Arb initieel {0,1}; Register prop[2]; submit(x) prop[i] = x; Arb.copy(i,1-i); return prop[Arb.read(0)]; (d) Nee, registers hebben consensusgetal 1 en kunnen geen objecten implementeren waarmee je wachtvrij consensus kunt bereiken tussen twee threads. (e) Minstens 2. Beoordeling: Let er bij (c) op, dat een thread EERST zijn waarde zichtbaar moet maken (hier in de prop[i]) en DAN PAS een copy gaat doen. Je wilt geen situatie waar een ”verliezende”thread moet wachten op de winnaar om zijn waarde bekend te maken. Anders 0pt! Het is de bedoeling, dat de INVOER van de winnende thread wordt gegeven, niet de index ervan. De returnwaarde moet dus zijn prop[Arb.read(0)] en NIET Arb.read(0) zelf. Hoogstens 1pt. Een veelgemaakte fout was: dat een thread zijn x in Arb zet. Het idee dat de twee waarden in Arb gelijk zijn vanaf de eerste copy wordt natuurlijk verstoord als een thread dan een write(i,x) doet. Daarom levert deze oplossing GEEN consensus (en ook geen punten!): submit(x): Arb.write(i,x) Arb.copy(i,1-1) return Arb.read(i) Het antwoord bij (d) ”Nee, want een copy bestaat uit een read en een write, en je kan niet voorkomen dat de andere thread ertussendoor komt.¨ıs niet onjuist, maar wel onvolledig en getuigt van de afwezigheid van kennis omtrent de Consensus Hierarchie. Hoogstens 1pt wanneer in het antwoord niet over consensusgetallen gesproken wordt.

37. Atomic Copy: Een CopyDog object heeft als toestandsruimte een rij van waarden, en naast operaties write(i,x) (schrijf x in locatie i) en read(i) (geef waarde van locatie i), een operatie copy(i,j) die de waarde van locatie i atomair kopieert naar j. Een CopyDog met twee locaties kan 2-Consensus implementeren. (a) In de propose(x) operatie zal thread i (0 of 1) precies eenmaal Arb.copy(i,1-i) uitvoeren. Hoe kun je de initi¨ele waarde van Arb kiezen om ervoor te zorgen dat alleen de eerste copy-operatie iets aan de inhoud verandert? (b) Hoe kan een thread na het uitvoeren van zijn copy zien, welke thread als eerste de copy deed? (c) Geef een wachtvrij algoritme dat een CopyDog gebruikt en 2-Consensus implementeert. (d) Kan een CopyDog wachtvrij worden ge¨ımplementeerd met registers? Oplossing: (a) Een copy(0,1) of copy(1,0) verandert iets aan de toestand, precies wanneer de twee waarden verschillend zijn. Na de copy zijn de waarden sowieso gelijk, en als je daarna direct weer een copy doet, verandert die niets. We gaan er dus voor zorgen dat de twee waarden initieel verschillen: zet een 0 op locatie 0 en een 1 op locatie 1. (b) Als de copy(i,1-i) de eerste is, staat daarna de i op beide plaatsen, wat ook door een volgende copy niet anders wordt. Het threadnummer van de eerste copy staat dus op locatie 0 (en op 1). (c) Standaard constructie met opslag invoer en arbiter: CopyDog Arb initieel {0,1}; Register prop[2]; submit(x) prop[i] = x; Arb.copy(i, 1-i); return prop[Arb.read(0)]; (d) Nee, registers hebben consensusgetal 1 en kunnen geen objecten implementeren waarmee je wachtvrij consensus kunt bereiken tussen twee threads. Beoordeling: Totaal 4, een punt per deelantwoord. Beoordelingscodes: E = Let er bij (c) op, dat een thread Eerst zijn waarde zichtbaar moet maken;. Anders 0pt! I = Geef de Invoer van een thread, niet de index ervan. T = Bij (d) “Nee, want een copy bestaat uit een read en een write, en je kan niet voorkomen dat de andere thread erTussendoor komt.” is niet onjuist, maar wel onvolledig en getuigt van de afwezigheid van kennis omtrent de Consensus Hierarchie. W = Leg uit Waarom! “Nee” is niet genoeg bij (d). X = Een thread zet zijn X in Arb; het idee dat de twee waarden in Arb gelijk zijn vanaf de eerste copy wordt natuurlijk verstoord als een thread dan een write(i,x) doet; 0pt.

38. Electie en Consensus: Een electie-object gebruik je als een bepaalde taak door precies ´e´en thread moet worden gedaan, maar je kunt niet van tevoren bepalen welke dat is. Het atomaire object heeft slechts ´e´en methode boolean elect() en garandeert: Als elect() ´e´en of meerdere keren wordt aangeroepen, wordt precies ´e´en keer true teruggegeven en verder false. (a) Toon aan, dat als aanroepen na elkaar plaatsvinden, het altijd de eerste aanroep is die true oplevert. (b) Laat zien, dat je met het electie-object consensus kunt implementeren voor twee threads. (c) Kan het ook voor drie threads? (d) Wat is het consensus-getal van het electie-object? Oplossing: (a) Het object garandeert dat, als er aanroepen zijn, er 1 True terugkrijgt. Maar als de eerste false krijgt, en we stoppen dan het gebruik, is die eigenschap niet voldaan. Dus omdat het object “niet in de toekomst kan kijken” moet hij de true wel aan de eerste aanroep geven. (b) In a is betoogd, dat het object je eigenlijk gewoon zegt of je de eerste aanroep hebt gedaan. Dat kun je als arbiter gebruiken voor 2 threads: electie arb; waarde[2] prop; submit(x) voor thread i: prop[i] = a ; if (arb.elect()) return x else return prop[1-i] (c) Nee dat kan niet. Informeel kun je zeggen dat een thread die false krijgt, niet kan weten welke van de andere twee hij moet kiezen. Formeel gaat het bewijs ongeveer zo: Als je een consensus voor drie kunt maken, is daarin een situatie mogelijk waarin C BIvalent is, maar als thread i een elect doet wordt het 0-valent en als j een elect doet wordt het 1-valent. De twee verschillende configuraties (na stap van i en na stap van j) zijn echter k-gelijk (k is de derde thread). Daarmee is een verschil in valentie uitgesloten. (d) Het consensusgetal is 2. Bij b is aangetoond dat 2-Cons mogelijk is, bij c dat 3-Cons onmogelijk is. Beoordeling: Voor elk van de deelvragen 1 pt. Codes: G = Zegt niets over in Geheugen zetten van waarde voor aanroep elect; -1/2. I = Doet niets met Input, -1/2. K = Gebruik elect op een manier die niet Kan. M = Geen of onjuiste Motivatie. N = Zet waarde in geheugen Na elect, 0pt. T = Legt niet uit waarom de Tweede geen true zou kunnen geven, 0pt. W = Argument: je weet niet Wie eerst was bij (c). Informeel verhaal, sluit andere mogelijke algoritmen niet uit, 1/2.

39. Consensus met Swapper: Een Swapper is een array-object dat je per cel kunt lezen en schrijven (read(i) en write(i,x)) en een methode swap(i,j) heeft die de inhoud van cellen i en j atomair verwisselt. Om consensus te bereiken tussen n threads gebruiken we een swapper met n + 1 cellen, en initieel een 0 in cellen 0 t/m n − 1 en een 1 in cel n. (a) Bewijs: als elke thread i eenmaal swap(i,n) doet, verandert de toestand van de swapper alleen in de eerste aanroep. (b) Geef een wacht-vrije Consensus-implementatie met swapper. Oplossing: (a) Na de eerste aanroep door i bevatten alle cellen ongelijk i hetzelfde getal (namelijk 0), dus omwisselen maakt geen verschil. (b) Je moet eerst je input opslaan, en bedenken hoe je de Swapper s uitleest: decide(x) voor thread i: Prop[i] = x s.swap(i,n) for (j=0; j
return Prop[i]

Beoordeling: Onderdeel (a) is vrij klein, dus 1pt, bij (b) moet je ook het opslaan en uitlezen bedenken, 3pt. I = Geen Invoer geaccepteerd of teruggegeven, 0pt. T = Doet slechts Twee-Consensus.

40. Electie en Consensus: Een electie-object gebruik je om een thread te selecteren om een eenmalige taak uit te voeren. Het object heeft als methode boolean elect() en garandeert: Als elect() ´e´en of meerdere keren wordt aangeroepen, wordt precies ´e´en keer true teruggegeven en verder false. (a) Laat zien, dat je met het electie-object, consensus voor twee threads kunt implementeren. (b) Kan het ook voor drie threads? (c) Wat is het consensus-getal van het electie-object? Oplossing: (a) Het object zal altijd true teruggeven op de eerste aanroep, en vertelt je dus gewoon of je de eerste aanroep hebt gedaan. Dat kun je als arbiter gebruiken voor 2 threads: electie arb; waarde[] prop; submit(x) voor thread i: prop[i] = a if (arb.elect()) return x else return prop[1-i] (b) Nee dat kan niet. Informeel kun je zeggen dat een thread die false krijgt, niet kan weten welke van de andere twee hij moet kiezen. Voor dit informele argument kon je 1pt krijgen. Formeel gaat het bewijs ongeveer zo: Als je een consensus voor drie kunt maken, is daarin een situatie mogelijk waarin C BIvalent is, maar als thread i een elect doet wordt het 0-valent en als j een elect doet wordt het 1-valent. De twee verschillende configuraties (na stap van i en na stap van j) zijn echter k-gelijk (k is de derde thread) omdat de elect geen parameter heeft. Daarmee is een verschil in valentie uitgesloten. (c) Het consensusgetal is 2. Bij a is aangetoond dat 2-Cons mogelijk is, bij b dat 3-Cons onmogelijk is. Beoordeling: 1pt voor (a), 2pt voor (b) en 1 voor (c). Beoordelingscodes: A = Oplossing bij (a) wacht op Actie van thread die true krijgt, 0pt. I = Informeel bewijs bij (b), 1pt. T = Oplossing van (a) levert Thread Id op ipv input, 0pt. Voor Consensus is het vereist dat de input van een thread opgeleverd wordt, dus geen ThreadId of Leader/Nonleader! W = Bij (a) mist het Wegschrijven van de input voor de aanroep van elect: kijk hoe er verder mee omgegaan wordt, als A van toepassing 0, soms nog 1/2 mogelijk. Als je wilt weten of je het nu snapt, beantwoord dan dezelfde vragen voor het sterke electie object, dat elke thread de thread id van een aanroepende thread teruggeeft.

41. Electie en Consensus: Een electie-object gebruik je als een bepaalde taak door precies ´e´en thread moet worden gedaan, maar je kunt niet van tevoren bepalen welke dat is. Het atomaire object heeft slechts ´e´en methode boolean elect() en garandeert: Als elect() ´e´en of meerdere keren wordt aangeroepen, wordt precies ´e´en keer true teruggegeven en verder false. (a) Toon aan, dat als aanroepen na elkaar plaatsvinden, het altijd de eerste aanroep is die true oplevert. (b) Laat zien, dat je met het electie-object consensus kunt implementeren voor twee threads. (c) Kan het ook voor drie threads? (d) Wat is het consensus-getal van het electie-object? Oplossing: (a) Het object garandeert dat, als er aanroepen zijn, er 1 True terugkrijgt. Maar als de eerste false krijgt, en we stoppen dan het gebruik, is die eigenschap niet voldaan. Dus omdat het object “niet in de toekomst kan kijken” moet hij de true wel aan de eerste aanroep geven. (b) In a is betoogd, dat het object je eigenlijk gewoon zegt of je de eerste aanroep hebt gedaan. Dat kun je als arbiter gebruiken voor 2 threads: electie arb; waarde[2] prop; submit(x) voor thread i: prop[i] = a ; if (arb.elect()) return x else return prop[1-i] (c) Nee dat kan niet. Informeel kun je zeggen dat een thread die false krijgt, niet kan weten welke van de andere twee hij moet kiezen. Formeel gaat het bewijs ongeveer zo: Als je een consensus voor drie kunt maken, is daarin een situatie mogelijk waarin C BIvalent is, maar als thread i een elect doet wordt het 0-valent en als j een elect doet wordt het 1-valent. De twee verschillende configuraties (na stap van i en na stap van j) zijn echter k-gelijk (k is de derde thread). Daarmee is een verschil in valentie uitgesloten. (d) Het consensusgetal is 2. Bij b is aangetoond dat 2-Cons mogelijk is, bij c dat 3-Cons onmogelijk is. Beoordeling: Voor elk van de deelvragen 1 pt. Codes: G = Zegt niets over in Geheugen zetten van waarde voor aanroep elect; -1/2. I = Doet niets met Input, -1/2. K = Gebruik elect op een manier die niet Kan. M = Geen of onjuiste Motivatie. N = Zet waarde in geheugen Na elect, 0pt. T = Legt niet uit waarom de Tweede geen true zou kunnen geven, 0pt. W = Argument: je weet niet Wie eerst was bij (c). Informeel verhaal, sluit andere mogelijke algoritmen niet uit, 1/2.

42. Read en Increment: In haar softwareproject heeft Anneke behoefte aan een wachtvrij, atomair ticket object. Het heeft methode rinc (read-and-increment) die bij opeenvolgende aanroepen, opeenvolgende getallen teruggeeft. In haar vorige project heeft Anneke al een wachtvrij counter object gebouwd, met methoden increment en read. Wat is nodig om een wachtvrije ticket te bouwen met behulp van een wachtvrije counter? Oplossing: Dit is onmogelijk. De counter kan (bv via de tussenstap snapshot) wachtvrij gemaakt worden met registers en heeft dus consensusgetal 1. De ticket kan zelf gebruikt worden om 2-Consensus te maken en heeft dus consensusgetal (minstens) 2. Beoordeling: Tot 4 pt. 3pt voor correct en compleet bewijs als bovenstaand. Laatste punt als een van de volgende punten zijn gedetailleerd: (1) implementatie van counter uit registers, (2) implementatie van consensus uit ticket, (3) hoe ’t wel kan met Interlocked, (4) dat registers geen 2-Cons kunnen oplossen. B = Je gebruikt een Busy wait, dus niet wait free. I = Een oplossing met Interlocked methoden, mooi, maar je hebt niet bewezen dat dit ook nodig is; 1pt. N = Een increment en read Na elkaar is niet goed, want door interactie krijgen de aanroepers niet altijd opeenvolgende getallen.

43. Ticket met Maxer: In haar softwareproject heeft Anneke behoefte aan een wachtvrij, atomair ticket object (door meerdere threads te gebruiken). Het heeft methode rinc (read-andincrement) die bij meerdere aanroepen, opeenvolgende getallen teruggeeft. In haar vorige project heeft Anneke al een wachtvrij maxer object gebouwd, met methoden update(x) en curmax. De maxer houdt per thread de laatst met update ingevoerde x bij, en de methode curmax geeft atomair de hoogste huidige waarde. Kan het Ticket object met behulp van een Maxer (en registers) worden gebouwd? Leg uit! Oplossing: Dit is onmogelijk. De maxer kan wachtvrij gemaakt worden met registers en heeft dus consensusgetal (hoogstens) 1. Bijvoorbeeld via een Snapshot: update is gewoon de snapshot update, curmax doet een scan en berekent de hoogste waarde. De ticket kan zelf gebruikt worden om 2-Consensus te maken en heeft dus consensusgetal (minstens) 2. Bijvoorbeeld via de Arbiter-constructie: Sla argument op, trek een ticket en kijk of je het eerste was, lever je eigen of de anders argument op. En je kunt niet een object met hoger Consensusgetal wachtvrij maken. Beoordeling: 3pt voor correct en compleet bewijs als bovenstaand. Er moet dan wel iets bij staan over waarom de maxer 1 heeft en de ticket 2, alleen de claim dat ’t zo is, is niet genoeg. A = (Zelfs) met een object van CN 2 kun je niet Alles maken dat ook CN 2 heeft. B = Je gebruikt een Busy wait, dus niet wait free. D = Voor Definitie van CN kijken naar Consensus implementaties, niet naar welke operaties gebruikt zijn. E = Je zegt niet waarom de maxer CN Een heeft; -1pt. G = Onjuist: dat een object met CN 1 alleen maar door 1 thread Gebruikt kan worden. Natuurlijk kunnen meerdere threads zoiets aanroepen (vgl register), maar ze kunnen er geen consensus mee bereiken. I = Een oplossing met Interlocked methoden, mooi, maar je hebt niet bewezen dat dit ook nodig is; 1pt. L = Je gebruikt Locking dus niet wachtvrij. N = Een s=1+a.curmax en a.update(s) Na elkaar is niet goed, want door interactie krijgen de aanroepers niet altijd opeenvolgende getallen. R = De Rinc moet nog gemaakt worden, is dus niet beschikbaar. T = Je zegt niet waarom Ticket CN Twee heeft; -1pt.

44. Wisselgeheugen en Consensus: Valerie heeft een geheugenchip gemaakt (het wisselgeheugen) die je niet alleen per geheugenlocatie i atomair kunt lezen en schrijven (read(i) en write(i,x)), maar ook een instructie wissel(i,j) heeft die de inhoud van locaties i en j atomair verwisselt. Zij claimt dat haar product ConsensusGetal oneindig heeft. Voor consensus tussen threads 0 t/m n − 1 stoppen we eerst een 0 in locaties 0 t/m n − 1 en een 1 in plek n. (a) Bewijs: als elke thread i eenmaal wissel(i,n) doet, verandert de toestand van het geheugen alleen in de eerste aanroep. (b) Geef een wacht-vrije Consensus-implementatie voor n threads met wisselgeheugen. (c) Klopt de claim van Valerie? Oplossing: (a) Na de eerste aanroep door i bevatten alle cellen ongelijk i hetzelfde getal (namelijk 0), dus omwisselen maakt geen verschil. (b) Je moet eerst je input opslaan (Prop array gebruiken!), en bedenken hoe je uitleest welke thread eerst was: decide(x) voor thread i: Prop[i] = x; wissel(i, n); for (j=0; j
6

Synchronisatie

45. Pulse en PulseAll: Wat doet de methode Pulse (in Java heet deze: Notify)? Wat is het verschil tussen Pulse en PulseAll? Oplossing: Bij een monitor-object kunnen threads wachten op een conditie; zij hebben ooit het lock verkregen, maar (konden niet verder en) hebben zich geblokkeerd, dwz. in de acquirequeue geplaatst, door een Wait. De Pulse methode zet ´e´en thread uit de acquire queue in de ready queue, de PulseAll verplaatst ze allemaal naar de ready queue. Beoordeling: Voor elk antwoord 1pt. Codes: B = Pulse geeft aan dat een Berekening klaar is; hiermee oppassen, want hier praat je over de semantiek die de programmeur aan de conditie en Pulse gekoppeld heeft. I = Geef wachtende threads een interrupt; nee, omdat deze threads al stilstaan hoef je ze niet te interrupten. L = Pulse geeft het Lock over; nee dit is zeker niet zo: het monitor lock wordt afgegeven bij het verlaten van de methode. W = Zegt niet om Wat voor threads ’t gaat (wachtend in Wait).

46. Synchronisatiehulpmiddelen: Een thread0 gebruikt een waarde B, die initieel undef is en wordt berekend door thread1: Thread0: Thread1: ..; ..; s = s+B; B = pp+qq; ..; ..; (a) Thread0 mag de waarde van B niet gebruiken voordat die door Thread1 is uitgerekend en ingevuld. Welke statement(s) zou je hiervoor aan de code toevoegen? (b) Waarom wordt het gebruik van een wait statement binnen een loop van een Monitor, niet gezien als spinnen? (c) Stel dat de berekening en het gebruik van B onderdeel zijn van een herhaling: Thread0: Thread1: s = 0; while (..) while (..) { pp = "bereken iets"; { .. qq = "bereken iets"; s = s+B; B = pp+qq; } } Elke nieuwe waarde van B moet exact eenmaal worden bijgeteld bij s. Wat kun je toevoegen aan de code om dat voor elkaar te krijgen? Oplossing: (a) Je kunt voor de opdracht s=s+B een busy wait zetten while (B==undef) {}, wat wel werkt maar dit is een busy wait dus uitermate slecht (in dit geval heb je geen idee hoelang Th1 gaat rekenen). Beter is een semafoor s, initieel 0. VOOR de s=s+B zet je s.Acquire en NA de B=pp+qq zet je s.Release (of: P/V danwel wait en signal). (b) Een while(iets) wait; geldt niet als busy wait omdat de aanroepende thread in de wacht wordt gezet en dus geen cpu-tijd verbruikt, totdat een corresponderende notify is uitgevoerd. Het aantal keren dat de thread door de lus gaat (de wacht in en uit) is weliswaar niet a priori begrensd, maar de thread doet alleen iets als er ook een andere thread in de monitor actief is geweest. (c) Je moet de twee loops op een goede manier synchroniseren. Thr0 mag nooit vaker lezen dan Thr1 heeft geschreven en hiervoor dient de semafoor lees hieronder. Thr1 mag niet meer dan 1 keer vaker schrijven dan Thr0 heeft gelezen (anders verdwijnt er een waarde) en dat regelt semafoor schrijf. Semafoor lees(0), schrijf(1) Thread0: Thread1: s = 0; while (..) while (..) { pp = "bereken iets"; { lees.Acquire; qq = "bereken iets"; schrijf.Acquire; s = s+B; B = pp+qq; schrijf.Release; lees.Release; } } Beoordeling: Voor (a) en (c) 2pt, voor (b) 1pt. B = Busy Wait, max 1pt voor dit onderdeel. L = Acquire of wait in Thread 1 direct na de lees.release. Dit is niet zo goed omdat het de concurrency teveel remt, 1/2 pt aftrek. R = Een mechanisme dat T1 remt ontbreekt bij (c), maximaal 1 pt.

47. Synchronisatie met Barrier: Een barrier (voor n threads) kent een methode await() die door alle threads kan worden aangeroepen. In deze opgave kijken we naar een implementatie waarin elke thread i een eigen semafoor s[i] heeft. (a) Wat is de eigenschap waaraan de methode await() moet voldoen? (b) Beschrijf een situatie waarin je de barrier zinvol kunt gebruiken. Aan het eind van de await() doet thread i P-operaties op zijn eigen semafoor: void await() { ... for (int j=0; j
48. Synchronisatie: Barrier met Semafoor: Een barrier (voor n threads) kent een methode signalAndWait() (in Java: await) die door alle threads kan worden aangeroepen. In deze opgave kijken we naar een implementatie waarin elke thread i een eigen semafoor s[i] heeft. Aan het eind van de await() doet thread i een reeks van n Acquires op zijn eigen semafoor: void signalAndWait() { ... for (int j=0; j