Tiny Threads

Zrealizuj bibliotekę z interfejsem, jak w poniższym pliku threads.h, która wspiera bardzo lekkie pseudowątki. Rozwiązaniem może być jeden plik z kodem w assemblerze, C99 lub C++17, lub archiwum zawierające kombinację takich plików. Pliki mogą używać tylko standardowych bibliotek oraz, w razie potrzeby, nagłówka threads.h.

#ifndef THREADS_H
#define THREADS_H

#include <stdint.h>

typedef void (*thread) ();

// pobierz aktualny identyfikator wątku lub 0, jeśli nie jesteś w żadnym wątku
uint8_t thread_id();

// utwórz wątek i zwróć jego identyfikator
uint8_t thread_start(thread);

// wyślij liczbę do wątku t_id, noop w przypadku błędu
void thread_send(uint8_t t_id, unsigned long value);

// zatrzymaj wątek i czekaj na liczbę, noop jeśli nie jesteś w wątku
unsigned long thread_receive();

#endif

Ten nagłówek będzie interpretowany zgodnie z konwencją języka C (w szczególności, nazwy funkcji nie podlegają name mangling) — w przypadku realizacji w języku C++ najlepiej owinąć go dyrektywą extern:

extern "C" {
#include "threads.h"
}

W przypadku realizacji rozwiązania w jednym pliku C/C++ zaleca się zastosowanie w rozwiązaniu wstawek assemblera (w składni AT&T) — poniżej znajduje się przykład zapisu i odczytu wartości z rejestrów. Oczywiście, w wstawkach można umieszczać również całe funkcje i używać call, jmp itd. Więcej wyjaśnień można znaleźć, na przykład, tutaj: http://www.ibiblio.org/gferg/ldp/GCC-Inline-Assembly-HOWTO.html

unsigned long multiply(unsigned long a) { return a * 10; }
unsigned long value = 7;
asm ("mov %0, %%rdi \n" :: "mr" (value)); // zapisz wartość w rdi
((void (*)())multiply)();
asm ("mov %%rax, %0\n" : "=mr" (value)); // odczytaj wartość z rax
assert(value == 70);

Zachowanie wątków powinno być następujące:

W danym momencie wykonuje się maksymalnie jeden wątek (nie ma prawdziwej wielowątkowości, są tylko przerwania wykonywania kodu w jednym miejscu i jego wznowienie w innym).

Możliwe jest tworzenie tylko wątków z identyfikatorami od 1 do 255 włącznie. Nowy wątek zawsze otrzymuje najmniejszy możliwy identyfikator, który nie jest zajęty przez inny (wcześniej uruchomiony) wątek. Jeśli nie ma wolnych identyfikatorów, tworzenie wątku kończy się niepowodzeniem (thread_start zwraca 0).

Należy zapewnić każdemu wątkowi co najmniej 32 KB pamięci dla stosu.

Wszystkie funkcje biblioteki mogą być wywoływane w dowolnym momencie (także z kodu wątków), przy czym thread_receive nic nie robi, jeśli jest wywoływana nie z wątku.

Funkcja thread_start tworzy nowy wątek i od razu zaczyna jego wykonanie — wątek, który wywołał, jest wstrzymywany. Funkcja thread_send wysyła dane do innego wątku, jeśli taki istnieje i jego aktualny stan to oczekiwanie na wywołanie thread_receive. W tej sytuacji funkcja thread_send przekazuje kontrolę wątkowi, który otrzymuje dane (wątek-nadawca jest wstrzymywany).

Funkcja thread_receive wstrzymuje aktualny wątek w oczekiwaniu na dane i zwraca kontrolę do tego wątku, który ostatnio wywołał thread_send lub thread_start, przy czym brane są pod uwagę tylko te wywołania, które jeszcze się nie zakończyły. Jeśli takiego wątku nie ma, przekazujemy kontrolę do głównego programu.

Momentem zakończenia wątku jest wyjście z funkcji przekazanej jako argument do thread_start. Po takim zdarzeniu kontrola jest przekazywana do następnego wątku, który czeka, wybieranego według tych samych zasad, co w przypadku thread_receive.

Przykład 1:

#include <stdio.h>
#include "threads.h"

void th() {
    printf("Wątek %d rozpoczęty\n", thread_id());
    if (thread_id() == 1) {
        thread_start(th);
    }
    printf("Wątek %d zwraca\n", thread_id());
}

int main() {
    printf("Rozpoczynanie wątków...\n");
    printf("Pierwszy identyfikator wątku to %d\n", thread_start(th));
    return 0;
}

Wynik:

Rozpoczynanie wątków...
Wątek 1 rozpoczęty
Wątek 2 rozpoczęty
Wątek 2 zwraca
Wątek 1 zwraca
Pierwszy identyfikator wątku to 1

Przykład 2:

#include <stdio.h>
#include "threads.h"

void th2() {
    printf("Wątek %u otrzymał %lu\n", thread_id(), thread_receive());
    printf("Wątek %u otrzymał %lu\n", thread_id(), thread_receive());
    printf("Wątek %d zwraca\n", thread_id());
}

void th1() {
    printf("Wątek %d utworzył wątek %d\n", thread_id(), thread_start(th2));
    printf("Wątek %d wysyła 10...\n", thread_id());
    thread_send(2, 10);
    printf("Wątek %d wysyła 20...\n", thread_id());
    thread_send(2, 20);
    printf("Wątek %d również zwraca\n", thread_id());
}

int main() {
    printf("Rozpoczynanie wątków...\n");
    printf("Pierwszy identyfikator wątku to %d\n", thread_start(th1));
    return 0;
}

Wynik:

Rozpoczynanie wątków...
Wątek 1 utworzył wątek 2
Wątek 1 wysyła 10...
Wątek 2 otrzymał 10
Wątek 1 wysyła 20...
Wątek 2 otrzymał 20
Wątek 2 zwraca
Wątek 1 również zwraca
Pierwszy identyfikator wątku to 1

Przykład 3:

#include <stdio.h>
#include "threads.h"

int count;

void counter() {
    count++;
    printf("Wątek %d drukuje float, aby sprawdzić wyrównanie stosu: %0.2f\n",
        thread_id(), count * 1.0);
    thread_start(counter);
}

int main() {
    printf("Ile wątków można utworzyć?...\n");
    count = 0;
    thread_start(counter);
    printf("Całkowita liczba: %d\n", count);
    return 0;
}

Wynik:

Ile wątków można utworzyć?...
Wątek 1 drukuje float, aby sprawdzić wyrównanie stosu: 1.00
Wątek 2 drukuje float, aby sprawdzić wyrównanie stosu: 2.00
Wątek 3 drukuje float, aby sprawdzić wyrównanie stosu: 3.00
(...)
Wątek 254 drukuje float, aby sprawdzić wyrównanie stosu: 254.00
Wątek 255 drukuje float, aby sprawdzić wyrównanie stosu: 255.00
Całkowita liczba: 255

Przykład 4:

#include <stdio.h>
#include "threads.h"

void filter() {
    unsigned long v;
    while ((v = thread_receive())) {
        if (v%2 == 0)
            printf("%lu\n", v);
    }
    printf("Zamykam...\n");
}

void fib() {
    unsigned long a = 0, b = 1;
    uint8_t tid = thread_start(filter);
    while (b < 1000000000) {
        thread_send(tid, b);
        unsigned long c = b;
        b += a;
        a = c;
    }
    thread_send(tid, 0);
}

int main() {
    thread_start(fib);
    return 0;
}

Wynik:

2
8
34
144
610
2584
10946
46368
196418
832040
3524578
14930352
63245986
267914296
Zamykam...

Przykład 5:

#include <stdio.h>
#include <assert.h>
#include "threads.h"

uint8_t next;

void add1() {
    uint8_t local_next = next;
    unsigned long v = thread_receive() + 1;
    thread_send(local_next, v);
    thread_send(local_next, v + 1000); // ignorowane
    thread_send(20 + local_next, v); // ignorowane
    printf("Wątek %u wysłał %lu do %u\n", thread_id(), v, local_next);
}

int main() {
    thread_receive(); // ignorowane
    assert(thread_id() == 0);
    for (next = 0; next < 10; next++)
        thread_start(add1);
    assert(thread_id() == 0);
    thread_receive(); // ignorowane
    thread_send(10, 1000);
    assert(thread_id() == 0);
    return 0;
}

Wynik:

Wątek 1 wysłał 1010 do 0
Wątek 2 wysłał 1009 do 1
Wątek 3 wysłał 1008 do 2
Wątek 4 wysłał 1007 do 3
Wątek 5 wysłał 1006 do 4
Wątek 6 wysłał 1005 do 5
Wątek 7 wysłał 1004 do 6
Wątek 8 wysłał 1003 do 7
Wątek 9 wysłał 1002 do 8
Wątek 10 wysłał 1001 do 9