wiki.unix7.org

This is an example of implementation of cooperative multitasking on a single thread.
I used library makecontext() and company.

Это пример реализации кооперативной многозадачности на одном потоке.
Использованы библиотечные makecontext() и компания.
В шутку названа “Golang: Истоки”.

Если добавить массив thread pool с миграцией заданий, то получим еще один шаг к golang реализации.

Note: the code w/o check of return values.

go-origin.c

/*
 * Copyright 2022 Oleg Borodin  <borodin@unix7.org>
 */
 
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <ucontext.h>
#include <assert.h>
#include <time.h>
 
typedef struct igoroutine goroutine_t;
 
typedef void (*goroutine_f)(goroutine_t* goroutine);
 
struct igoroutine {
    int             ident;
    goroutine_f          func;
    ucontext_t*     scntx;
    ucontext_t*     tcntx;
    goroutine_t*         next;
    bool            done;
};
 
 
#define STACKSIZE SIGSTKSZ
 
void goroutine_start(goroutine_t* goroutine);
void goroutine_resume(goroutine_t* goroutine);
void goroutine_yield(goroutine_t* goroutine);
 
goroutine_t* new_goroutine(int ident, ucontext_t* scntx, goroutine_f func) {
    goroutine_t* goroutine = malloc(sizeof(goroutine_t));
    goroutine->scntx = scntx;
    goroutine->func = func;
    goroutine->done = false;
    goroutine->next = NULL;
    goroutine->ident = ident;
 
    ucontext_t* tcntx = malloc(sizeof(ucontext_t));
    getcontext(tcntx);
    tcntx->uc_stack.ss_sp = malloc(STACKSIZE);
    tcntx->uc_stack.ss_size = STACKSIZE;
    tcntx->uc_link = NULL;
    makecontext(tcntx, (void (*)())goroutine_start, 1, goroutine);
    goroutine->tcntx = tcntx;
 
    return goroutine;
}
 
void goroutine_resume(goroutine_t* goroutine) {
    swapcontext(goroutine->scntx, goroutine->tcntx);
}
 
void goroutine_start(goroutine_t* goroutine) {
    if (goroutine->done == true) { return; }
    goroutine->func(goroutine);
    printf("goroutine %d done\n", goroutine->ident);
    goroutine->done = true;
    swapcontext(goroutine->tcntx, goroutine->scntx);
}
 
void goroutine_yield(goroutine_t* goroutine) {
    swapcontext(goroutine->tcntx, goroutine->scntx);
}
 
void goroutine_free(goroutine_t* goroutine) {
    free(goroutine->tcntx);
    free(goroutine);
}
 
 
typedef struct ischeduler scheduler_t;
struct ischeduler{
    goroutine_t*         head;
    int             size;
    ucontext_t*     cntx;
    ucontext_t*     mcntx;
};
 
void scheduler_start(scheduler_t* scheduler);
 
scheduler_t* new_scheduler() {
    scheduler_t* scheduler = malloc(sizeof(scheduler_t));
    scheduler->size = 0;
    scheduler->head = NULL;
 
    ucontext_t* cntx = malloc(sizeof(ucontext_t));
    getcontext(cntx);
    cntx->uc_stack.ss_sp = malloc(STACKSIZE);
    cntx->uc_stack.ss_size = STACKSIZE;
    cntx->uc_link = NULL;
    makecontext(cntx, (void (*)())scheduler_start, 1, scheduler);
 
    scheduler->cntx = cntx;
 
    return scheduler;
}
 
goroutine_t* scheduler_getn(scheduler_t* scheduler) {
    int i = 0;
    int num = rand() % scheduler->size;
    goroutine_t* curr = scheduler->head;
    while (curr != NULL) {
        if (i == num) return curr;
        curr = curr->next;
        i++;
    };
    return NULL;
}
 
void scheduler_clean(scheduler_t* scheduler) {
    goroutine_t* curr = scheduler->head;
    while (curr->next != NULL) {
        if (curr->next->done) {
            goroutine_t* done = curr->next;
            curr->next = curr->next->next;
            goroutine_free(done);
            scheduler->size--;
            continue;
        }
        curr = curr->next;
    };
    if (scheduler->head != NULL) {
        if (scheduler->head->done) {
            goroutine_t* done = scheduler->head;
            scheduler->head = scheduler->head->next;
            goroutine_free(done);
            scheduler->size--;
        }
    }
    return;
}
 
void scheduler_run(scheduler_t* scheduler) {
    ucontext_t* mcntx = malloc(sizeof(ucontext_t));
    getcontext(mcntx);
    scheduler->mcntx = mcntx;
    swapcontext(scheduler->mcntx, scheduler->cntx);
 }
 
void scheduler_start(scheduler_t* scheduler) {
    printf("scheduler start\n");
    srand(time(NULL));
    while (scheduler->size > 0) {
        goroutine_t* todo = scheduler_getn(scheduler);
        goroutine_resume(todo);
        scheduler_clean(scheduler);
    }
    printf("scheduler end\n");
    swapcontext(scheduler->cntx, scheduler->mcntx);
    return;
}
 
void scheduler_add(scheduler_t* scheduler, goroutine_t* new) {
    if (scheduler->head == NULL) {
        scheduler->head = new;
        scheduler->size++;
        return;
    }
    goroutine_t* curr = scheduler->head;
    while (curr->next != NULL) {
        curr = curr->next;
    };
    curr->next = new;
    scheduler->size++;
    return;
}
 
void scheduler_free(scheduler_t* scheduler) {
    free(scheduler->cntx);
    free(scheduler->mcntx);
    free(scheduler);
}
 
 
void goroutine(goroutine_t* goroutine) {
    printf("goroutine %d #1\n", goroutine->ident);
    goroutine_yield(goroutine);
    printf("goroutine %d #2\n", goroutine->ident);
    goroutine_yield(goroutine);
    printf("goroutine %d #3\n", goroutine->ident);
    return;
}
 
int main(int argc, char **argv) {
 
    printf("main start\n");
    scheduler_t* scheduler = new_scheduler();
 
    int tcount = 5;
    for (int i = 0; i < tcount; i++) {
        scheduler_add(scheduler, new_goroutine(i, scheduler->cntx, goroutine));
    }
 
    scheduler_run(scheduler);
    scheduler_free(scheduler);
 
    printf("main end\n");
    return 0;
}

$ "./go-origin"
main start
scheduler start
goroutine 1 #1
goroutine 0 #1
goroutine 3 #1
goroutine 4 #1
goroutine 3 #2
goroutine 2 #1
goroutine 2 #2
goroutine 4 #2
goroutine 0 #2
goroutine 0 #3
goroutine 0 done
goroutine 4 #3
goroutine 4 done
goroutine 2 #3
goroutine 2 done
goroutine 3 #3
goroutine 3 done
goroutine 1 #2
goroutine 1 #3
goroutine 1 done
scheduler end
main end