Маленькі нитки

Реалізуйте бібліотеку з інтерфейсом, як у наведеному нижче файлі threads.h, що підтримує дуже легкі псевдопотоки. Розв’язком може бути один файл із кодом на асемблері, C99 або C++17, або архів, що містить комбінацію таких файлів. Файли можуть використовувати лише стандартні бібліотеки та, за потреби, заголовок threads.h.

#ifndef THREADS_H
#define THREADS_H

#include <stdint.h>

typedef void (*thread) ();

// отримати ідентифікатор поточного потоку або 0, якщо не в жодному потоці
uint8_t thread_id();

// створити потік і повернути його ідентифікатор
uint8_t thread_start(thread);

// надіслати число потоку t_id, нічого не робити, якщо помилка
void thread_send(uint8_t t_id, unsigned long value);

// зупинити потік і чекати на число, нічого не робити, якщо не в потоці
unsigned long thread_receive();

#endif

Цей заголовок інтерпретуватиметься згідно з конвенцією мови C (зокрема, імена функцій не підлягають name mangling) — у разі реалізації мовою C++ найкраще обгорнути його директивою extern:

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

У разі реалізації розв’язку в одному файлі C/C++ рекомендується застосувати у рішенні вставки асемблера (у синтаксисі AT&T) — нижче наведено приклад запису та зчитування значень із регістрів. Звісно, у вставках можна розміщувати й цілі функції та використовувати call, jmp тощо. Більше пояснень можна знайти, наприклад, тут: 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)); // зберегти значення в rdi
((void (*)())multiply)();
asm ("mov %%rax, %0\n" : "=mr" (value)); // зчитати значення з rax
assert(value == 70);

Поведінка потоків має бути такою:

У будь-який момент часу виконується щонайбільше один потік (немає справжньої багатопоточності, є лише переривання виконання коду в одних місцях і його відновлення в інших).

Можливе створення лише потоків з ідентифікаторами від 1 до 255 включно. Новий потік завжди отримує найменший можливий ідентифікатор, який не зайнятий іншим (раніше запущеним) потоком. Якщо немає вільних ідентифікаторів, створення потоку завершується невдачею (thread_start повертає 0).

Слід забезпечити кожному потоку щонайменше 32 КБ пам’яті для стека.

Усі функції бібліотеки можуть бути викликані в будь-який момент (також із коду потоків), причому thread_receive нічого не робить, якщо її викликано не з потоку.

Функція thread_start створює новий потік і відразу починає його виконання — потік, що викликав, призупиняється. Функція thread_send надсилає дані іншому потоку, якщо такий існує і його поточний стан — очікування на виклику thread_receive. У цій ситуації функція thread_send передає керування потоку, який отримує дані (потік-відправник призупиняється).

Функція thread_receive призупиняє поточний потік в очікуванні даних і повертає керування до того потоку, який останнім викликав thread_send або thread_start, причому розглядаються лише ті виклики, які ще не завершилися. Якщо такого потоку немає, передаємо керування головній програмі.

Моментом завершення потоку вважається вихід із функції, переданої як аргумент до thread_start. Після такої події керування передається наступному потоку, що очікує, якого обираємо за тим самим правилом, що й у випадку thread_receive.

Приклад 1:

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

void th() {
    printf("Thread %d started\n", thread_id());
    if (thread_id() == 1) {
        thread_start(th);
    }
    printf("Thread %d returning\n", thread_id());
}

int main() {
    printf("Starting threads...\n");
    printf("First thread ID was %d\n", thread_start(th));
    return 0;
}

Вивід:

Starting threads...
Thread 1 started
Thread 2 started
Thread 2 returning
Thread 1 returning
First thread ID was 1

Приклад 2:

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

void th2() {
    printf("Thread %u received %lu\n", thread_id(), thread_receive());
    printf("Thread %u received %lu\n", thread_id(), thread_receive());
    printf("Thread %d returning\n", thread_id());
}

void th1() {
    printf("Thread %d created thread %d\n", thread_id(), thread_start(th2));
    printf("Thread %d sending 10...\n", thread_id());
    thread_send(2, 10);
    printf("Thread %d sending 20...\n", thread_id());
    thread_send(2, 20);
    printf("Thread %d returning too\n", thread_id());
}

int main() {
    printf("Starting threads...\n");
    printf("First thread ID was %d\n", thread_start(th1));
    return 0;
}

Вивід:

Starting threads...
Thread 1 created thread 2
Thread 1 sending 10...
Thread 2 received 10
Thread 1 sending 20...
Thread 2 received 20
Thread 2 returning
Thread 1 returning too
First thread ID was 1

Приклад 3:

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

int count;

void counter() {
    count++;
    printf("Thread %d prints a float to check stack alignment: %0.2f\n",
        thread_id(), count * 1.0);
    thread_start(counter);
}

int main() {
    printf("How many threads is it possible to create?...\n");
    count = 0;
    thread_start(counter);
    printf("Total count: %d\n", count);
    return 0;
}

Вивід:

How many threads is it possible to create?...
Thread 1 prints a float to check stack alignment: 1.00
Thread 2 prints a float to check stack alignment: 2.00
Thread 3 prints a float to check stack alignment: 3.00
(...)
Thread 254 prints a float to check stack alignment: 254.00
Thread 255 prints a float to check stack alignment: 255.00
Total count: 255

Приклад 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("Exiting...\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;
}

Вивід:

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

Приклад 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); // ігнорується
    thread_send(20 + local_next, v); // ігнорується
    printf("Thread %u sent %lu to %u\n", thread_id(), v, local_next);
}

int main() {
    thread_receive(); // ігнорується
    assert(thread_id() == 0);
    for (next = 0; next < 10; next++)
        thread_start(add1);
    assert(thread_id() == 0);
    thread_receive(); // ігнорується
    thread_send(10, 1000);
    assert(thread_id() == 0);
    return 0;
}

Вивід:

Thread 1 sent 1010 to 0
Thread 2 sent 1009 to 1
Thread 3 sent 1008 to 2
Thread 4 sent 1007 to 3
Thread 5 sent 1006 to 4
Thread 6 sent 1005 to 5
Thread 7 sent 1004 to 6
Thread 8 sent 1003 to 7
Thread 9 sent 1002 to 8
Thread 10 sent 1001 to 9