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) {
    ...
}

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

message

Persistent Data Tree

を用いて木構造を表現する

union Data {
    struct Tree {
        struct Node* root;
    } tree;
    struct Node {
        // need to tree
        enum Code next;
        int key; // comparable data segment
        union Data* value;
        struct Node* left;
        struct Node* right;
        // need to balancing
        enum Color {
            Red,
            Black,
        } color;
    } node;
};

Worker

message
  • Worker は Task Queue から Task を取り出す(1. Dequeue Task)
  • 取り出した Task には Tree の key が入っているため Tree からその key に対応した Input Data Gear を読み込む(2. Read Data Gear)
  • Task に格納されている Code Gear を実行する
  • Code Gear を実行した結果、生成された Output Data Gear を Tree に書き出す(3.Write Data Gear)

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 との比較

まとめ

今後の課題