Code Gear、 Data Gear に基づく OS のプロトタイプ
伊波 立樹 琉球大学理工学研究科

Gears OS

を指標とした Gears OS を設計してきた

Gears OS の並列性

message

Gears OS の柔軟性

等を柔軟に対応する

message

Gears OS の信頼性

この発表は

Code Gear、 Data Gear

message

Meta Computation

Meta Gear

message

Continuation based C

Continuation based C

Continuation based C

/* code1 define */
__code code1(List list) {
    ....
    goto code2(list)
}

/* code2 define */
__code code2(List list) {
    ...
}

CbC を用いた Gears OS の記述

__code code1(struct Array* array, struct LoopCounter* loopCounter) {
    ...
    goto code2(array);
}

__code meta_code1(struct Context* context, enum Code next) {
    goto (context->code[next])(context);
}

__code code2(struct Array* array) {
    ...
}

CbC の Gears OS サポート

__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
    ...
    goto meta_code1(context, Code2);
}

__code code1_stub(struct Context* context) {
    goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
}

__code meta_code1(struct Context* context, enum Code next) {
    goto (context->code[next])(context);
}

__code code2(struct Context* context, struct Array* array) {
    ...
}

__code code2_stub(struct Context* context) {
    goto code1(context, &context->data[Node]->node.value->array);
}

Context

Context

/* context define */
struct Context {
    int codeNum;
    __code (**code) (struct Context*);
    void* heapStart;
    void* heap;
    long heapLimit;
    int dataNum;
    union Data **data;
};

Context

enum Code {
    Code1,
    Code2,
    Code3,
    Exit,
};

Data Gear の表現

/* data Gear define */
union Data {
    struct Time {
        enum Code next;
        double time;
    } time;
    struct LoopCounter {
        int i;
    } loopCounter;
    ....
};

Code Gear の stub

__code code1(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) {
    ...
}

/* stub define */
__code code1_stub(struct Context* context) {
    goto code1(context, &context->data[Node]->node.value->array, &context->data[LoopCounter]->loopCounter);
}

Gears OS の構成

message

Gears OS の構成

message

Gears OS の構成

message

TaskQueue

// Data Gear define
union Data {
    struct Queue {
        struct Element* first;
        struct Element* last;
    } queue;

    struct Element {
        struct Task* task;
        struct Elemen* next;
    } element
};

TaskQueueの操作(Enqueue)

__code putQueue3(struct Queue* queue, struct Element* new_element) {
    struct Element* last = queue->last;

    if (__sync_bool_compare_and_swap(&queue->last, last, new_element)) {
        last->next = new_element;

        goto exit();
    } else {
        goto putQueue3(queue, new_element);
    }
}

Persistent Data Tree

Worker

TaskManger

// Meta Code Gear
__code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) {
    int i = loopCounter->i;

    if (i < worker->num) {
        struct Context* worker_context = &worker->contexts[i];
        worker_context->next = GetQueue;
        worker_context->data[Tree] = context->data[Tree];
        worker_context->data[ActiveQueue] = context->data[ActiveQueue];
        pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context);
        worker_context->thread_num = i;
        loopCounter->i++;

        goto meta(context, CreateWorker);
    }

    loopCounter->i = 0;
    goto meta(context, TaskManager);
}

プロトタイプの実行

Gears で実行する Code Gear 例

// Twice Code Gear
__code twice(struct LoopCounter* loopCounter, int index, int alignment, int* array) {
    int i = loopCounter->i;

    if (i < alignment) {
        array[i+index*alignment] = array[i+index*alignment]*2;
        loopCounter->i++;

        goto twice(loopCounter, index, alignment, array);
    }

    loopCounter->i = 0;

    goto exit();
}

並列処理の確認

Number of Processors Time(ms)
1 CPU 1315
2 CPUs 689
4 CPUs 366
8 CPUs 189
12 CPUs 111

Cerium との比較

既存の OS との比較

まとめ

今後の課題