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

Реализуйте библиотеку с интерфейсом, как в приведенном ниже файле 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, noop в случае ошибки
void thread_send(uint8_t t_id, unsigned long value);

// остановить поток и ждать число, noop, если не в потоке
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