* Del 1 Vi antar att vi lämnade in en lösning lik b.c som svar på del 1. (Notera: a.c är helt korrekt, medan b.c innehåller fel.) * Del 2 ** Uppgift 1 Notera: Svaret nedan är ca 950 ord. Detta är ett svar som jag betraktar som 'mycket bra' och tar upp i princip allt som är konstigt med b.c. För G är det okej om några saker inte är perfekta eller glöms bort. Det viktiga är att lösningen förklarar varför b.c är fel, och hur de problemen ska lösas på ett bra sätt. I den här delen väljer jag att jämföra min lösning (b.c) med lösningen a.c. a. Det finns tyvärr ett par synkroniseringsfel i min lösning. Trots att jag har försökt skydda all delad data med lås inser jag att jag har misslyckats med att använda samma lås till samma data. Detta har 'a.c' lyckats med. I min lösning använder jag låset 'to_process_lock' i 'struct worker' och låset 'workers_lock' i 'struct thread_pool' för att skydda 'to_process' inuti 'struct worker'. I och med olika lås skyddar samma data innebär det att tråden som kör 'worker_main' kan läsa och skriva till variabeln 'to_process' samtidigt som en tråd som kör 'pool_handle_request'. Detta är alltid odefinierat - trots att den sekvens som står i källkoden råkar vara säker så får kompilatorn och hårdvaran ordna om operationerna så att det kan bli fel. För att lösa felet skulle jag helt enkelt ta bort låset 'workers_lock' och låsa 'worker->to_process_lock' i loopen i 'pool_handle_request'. Jag skulle också behöva flytta 'lock_acquire' till efter läsningen av '&pool->workers[id]'. Denna läsning behöver inte skyddas av något lås eftersom koden bara hämtar addressen till ett element, och eftersom ingen tråd ändrar på 'pool->workers'-variabeln (förutom 'init' och 'destroy', men det kan inte hända enligt specifikationen). Min lösning blir då väldigt lik lösningen 'a.c' i synkroniseringen. Ett annat problem med att använda två olika lås var att jag råkade använda olika lås för att skydda condition-variabeln 'wait_cond'. Jag måste såklart använda samma lås för min condition-variabel, annars är det återigen odefinierat vad som händer. Lösningen ovan skulle lösa även det problemet. b. Både min lösning (b.c) och a.c har försökt elliminera de instanser av busy-wait som fanns i originalkoden. Dessa är som följer: - En busy-wait fanns i funktionen 'worker_main'. Problemet här är att om tråden som kör 'worker_main' väntar på att 'w->to_process' ska innehålla något annat än NULL i en while-loop. Utöver att detta inte är korrekt synkroniserat så konsumerar tråden CPU-cykler helt i onödan. I min lösning har jag löst detta genom att låta tråden vänta med hjälp av 'cond_wait' i while-loopen. Detta gör att tråden sover tills den blir väckt av ett anrop till 'cond_broadcast' i stället för att göra busy-wait. Tråden som lägger till frågor anropar då 'cond_broadcast' i 'pool_handle_request' för att väcka worker-tråden. - En annan busy-wait fanns i funktionen 'pool_handle_request'. Här väntade originalimplementationen på att att det finns plats i en worker med hjälp av busy-wait. Detta blir därför bara ett problem om alla worker-trådar är upptagna. I min lösning har jag återigen valt att lösa detta genom att anropa 'cond_wait' när implementationen har letat igenom alla workers utan att hitta någonstans att lägga sin request. Tråden väcks då av ett motsvarande anrop till 'cond_broadcast' i 'worker_main'. En sak jag hade kunnat göra för att förbättra min lösning ytterligare hade varit att ha fler än ett condition. Implementationen behöver vänta på två olika 'saker': Dels behöver 'pool_handle_request' vänta på att det finns en ledig plats i 'thread_pool', och dels behöver 'worker_main' vänta på att det finns något att göra. Detta innebär att jag med fördel hade kunnat lägga till en 'struct condition has_work;' inuti 'struct worker'. Den skulle då motsvara att det finns något i 'to_process'. Då hade vi i 'worker_main' kunnat göra 'cond_wait(&w->has_work, ...);' i stället, samt uppdatera koden i 'pool_handle_request' så att den gör 'cond_signal(&worker->has_work, &worker->to_process_lock)' i stället. Den stora fördelen med detta är att vi inte behöver väcka alla trådar som väntar när vi har lagt in ett nytt element. I och med att vi har olika condition-variabler för de olika villkoren vet vi alltid att vi väcker 'rätt' tråd, och kan därmed alltid använda 'cond_signal' i stället för 'cond_broadcast'. Notera att detta betyder att jag behöver ha kvar låset 'workers_lock' inuti 'struct thread_pool'. Jag skulle dock bara använda det för att synkronisera condition-variabeln. Detta är okej trots att jag inte skyddar datan i "villkoret" för condition-variabeln, i och med att 'pool_handle_request' alltid lägger till data säkert, och att 'worker_main' alltid tar bort data säkert. c. Problemet med att inte vänta är att 'pool_worker'-trådarna inte nödvändigtvis har hunnit avslutas, vilket innebär att de kan läsa från sin 'to_process'-variabel efter det att minnet för den har frigjorts. Det kan leda till en krasch, eller till att 'pool_worker'-trådarna börjar göra konstiga saker. I min implementation har jag löst detta genom att ha en delad variabel, 'num_exited' som varje worker-tråd räknar upp precis innan de avslutar sig själva. Tråden i 'pool_destroy' kan då helt enkelt vänta på att 'num_exited == num_workers' med hjälp av en condition-variabel för att vara säker på att alla trådar har avslutats. a.c har löst detta med en semafor, vilket i princip är ekvivalent. d. Givet modifikationerna jag har föreslagit ovan blir min lösning och a.c näst intill ekvivalenta ur ett prestandaperspektiv. Detta i och med att min lösning efter modifikationerna inte längre väcker trådar i onödan, och inte heller längre låser onödigt mycket i 'pool_handle_request'. Det finns en mindre mindre saker som gör att min lösning är aningen sämre än a.c: a.c behöver inte leta efter en ledig worker i fallet då alla workers är lediga eftersom semaforen får den att vänta innan den går in i loopen. Alltså blir a.c aningen bättre här, men det lär inte vara märkbart i de flesta fall. ** Uppgift 2 a. Vi kontrollerar om systemet är i ett säkert läge: Max: A B C P1 9 6 2 P2 6 1 9 P3 9 9 4 Nuvarande: A B C P1 6 4 1 P2 6 0 8 P3 6 5 3 Sum 18 9 12 Kvar: A B C P1 3 2 1 P2 0 1 1 P3 3 4 1 Uträkning: A B C 1 2 2 P2: +6 0 8 ------------ 7 2 10 P1: +6 4 1 ------------ 13 6 11 P3: +6 5 3 ------------ 19 11 14 Alla processer kan köra klart - systemet är i ett säkert läge. b. P3 begär en extra B. Alltså ökar vi 'nuvarande' med 1, och uppdaterar 'kvar': Nuvarande: A B C P1 6 4 1 P2 6 0 8 P3 6 6 3 Sum 18 9 12 Kvar: A B C P1 3 2 1 P2 0 1 1 P3 3 3 1 Uträkning: A B C 1 1 2 P2: +6 0 8 ------------ 7 1 10 Varken P1 eller P3 kan sedan köras. Alltså ska begäran nekas - P3 får vänta tills någon annan process släpper en resurs. c. Eftersom begäran inte tilläts är den som i uppgiften, alltså: A B C P1 6 4 1 P2 6 0 8 P3 6 5 3 Sum 18 9 12 ** Uppgift 3 a. Se nedan: #+BEGIN_SRC c struct bad_sema { int current_value; }; void bad_sema_init(struct bad_sema *sema, int value) { sema->current_value = value; } void bad_sema_up(struct bad_sema *sema) { atomic_add(&sema->current_value++, 1); } void bad_sema_down(struct bad_sema *sema) { int old; do { old = atomic_read(&sema->current_value); if (old <= 0) continue; } while (compare_and_swap(&sema->current_value, old, old - 1) != old); } #+END_SRC b. För att eliminera busy-wait krävs att en tråd kan sova. Tråden kan inte själv sova, utan den måste be operativsystemet om det, så att schemaläggaren har möjlighet att göra något annat om så behövs. Detta kan inte atomiska operationer göra, de kan bara se till så att läsningar och skrivningar sker "korrekt".